| Geant4 Cross Reference |
1 // see license file for original license. 1 // see license file for original license.
2 2
3 #ifndef tools_glutess_dict_list 3 #ifndef tools_glutess_dict_list
4 #define tools_glutess_dict_list 4 #define tools_glutess_dict_list
5 5
6 /* Use #define's so that another heap implemen 6 /* Use #define's so that another heap implementation can use this one */
7 7
8 #define DictKey DictListKey 8 #define DictKey DictListKey
9 #define Dict DictList 9 #define Dict DictList
10 #define DictNode DictListNode 10 #define DictNode DictListNode
11 11
12 #define dictNewDict(frame,leq) __gl_dictLis 12 #define dictNewDict(frame,leq) __gl_dictListNewDict(frame,leq)
13 #define dictDeleteDict(dict) __gl_dictListD 13 #define dictDeleteDict(dict) __gl_dictListDeleteDict(dict)
14 14
15 #define dictSearch(dict,key) __gl_dictListS 15 #define dictSearch(dict,key) __gl_dictListSearch(dict,key)
16 #define dictInsert(dict,key) __gl_dictListI 16 #define dictInsert(dict,key) __gl_dictListInsert(dict,key)
17 #define dictInsertBefore(dict,node,key) __gl_d 17 #define dictInsertBefore(dict,node,key) __gl_dictListInsertBefore(dict,node,key)
18 #define dictDelete(dict,node) __gl_dictListD 18 #define dictDelete(dict,node) __gl_dictListDelete(dict,node)
19 19
20 #define dictKey(n) __gl_dictListKey(n) 20 #define dictKey(n) __gl_dictListKey(n)
21 #define dictSucc(n) __gl_dictListSucc(n) 21 #define dictSucc(n) __gl_dictListSucc(n)
22 #define dictPred(n) __gl_dictListPred(n) 22 #define dictPred(n) __gl_dictListPred(n)
23 #define dictMin(d) __gl_dictListMin(d) 23 #define dictMin(d) __gl_dictListMin(d)
24 #define dictMax(d) __gl_dictListMax(d) 24 #define dictMax(d) __gl_dictListMax(d)
25 25
26 typedef void *DictKey; 26 typedef void *DictKey;
27 typedef struct Dict Dict; 27 typedef struct Dict Dict;
28 typedef struct DictNode DictNode; 28 typedef struct DictNode DictNode;
29 29
30 #define __gl_dictListKey(n) ((n)->key) 30 #define __gl_dictListKey(n) ((n)->key)
31 #define __gl_dictListSucc(n) ((n)->next) 31 #define __gl_dictListSucc(n) ((n)->next)
32 #define __gl_dictListPred(n) ((n)->prev) 32 #define __gl_dictListPred(n) ((n)->prev)
33 #define __gl_dictListMin(d) ((d)->head.next) 33 #define __gl_dictListMin(d) ((d)->head.next)
34 #define __gl_dictListMax(d) ((d)->head.prev) 34 #define __gl_dictListMax(d) ((d)->head.prev)
35 #define __gl_dictListInsert(d,k) (dictInsertBe 35 #define __gl_dictListInsert(d,k) (dictInsertBefore((d),&(d)->head,(k)))
36 36
37 /*** Private data structures ***/ 37 /*** Private data structures ***/
38 38
39 struct DictNode { 39 struct DictNode {
40 DictKey key; 40 DictKey key;
41 DictNode *next; 41 DictNode *next;
42 DictNode *prev; 42 DictNode *prev;
43 }; 43 };
44 44
45 struct Dict { 45 struct Dict {
46 DictNode head; 46 DictNode head;
47 void *frame; 47 void *frame;
48 int (*leq)(void *frame, DictKey key1, Dict 48 int (*leq)(void *frame, DictKey key1, DictKey key2);
49 }; 49 };
50 50
51 ////////////////////////////////////////////// 51 ////////////////////////////////////////////////////////
52 /// inlined C code : ///////////////////////// 52 /// inlined C code : ///////////////////////////////////
53 ////////////////////////////////////////////// 53 ////////////////////////////////////////////////////////
54 #include <cstddef> 54 #include <cstddef>
55 #include "memalloc" 55 #include "memalloc"
56 56
57 inline Dict *dictNewDict( void *frame,int (*le 57 inline Dict *dictNewDict( void *frame,int (*leq)(void *frame, DictKey key1, DictKey key2) ) {
58 Dict *dict = (Dict *) memAlloc( sizeof( Dict 58 Dict *dict = (Dict *) memAlloc( sizeof( Dict ));
59 DictNode *head; 59 DictNode *head;
60 60
61 if (dict == NULL) return NULL; 61 if (dict == NULL) return NULL;
62 62
63 head = &dict->head; 63 head = &dict->head;
64 64
65 head->key = NULL; 65 head->key = NULL;
66 head->next = head; 66 head->next = head;
67 head->prev = head; 67 head->prev = head;
68 68
69 dict->frame = frame; 69 dict->frame = frame;
70 dict->leq = leq; 70 dict->leq = leq;
71 71
72 return dict; 72 return dict;
73 } 73 }
74 74
75 inline void dictDeleteDict( Dict *dict ) { 75 inline void dictDeleteDict( Dict *dict ) {
76 DictNode *node, *next; 76 DictNode *node, *next;
77 77
78 for( node = dict->head.next; node != &dict-> 78 for( node = dict->head.next; node != &dict->head; node = next ) {
79 next = node->next; 79 next = node->next;
80 memFree( node ); 80 memFree( node );
81 } 81 }
82 memFree( dict ); 82 memFree( dict );
83 } 83 }
84 84
85 /* Search returns the node with the smallest k 85 /* Search returns the node with the smallest key greater than or equal
86 * to the given key. If there is no such key, 86 * to the given key. If there is no such key, returns a node whose
87 * key is NULL. Similarly, Succ(Max(d)) has a 87 * key is NULL. Similarly, Succ(Max(d)) has a NULL key, etc.
88 */ 88 */
89 89
90 inline DictNode *dictInsertBefore( Dict *dict, 90 inline DictNode *dictInsertBefore( Dict *dict, DictNode *node, DictKey key ) {
91 DictNode *newNode; 91 DictNode *newNode;
92 92
93 do { 93 do {
94 node = node->prev; 94 node = node->prev;
95 } while( node->key != NULL && ! (*dict->leq) 95 } while( node->key != NULL && ! (*dict->leq)(dict->frame, node->key, key));
96 96
97 newNode = (DictNode *) memAlloc( sizeof( Dic 97 newNode = (DictNode *) memAlloc( sizeof( DictNode ));
98 if (newNode == NULL) return NULL; 98 if (newNode == NULL) return NULL;
99 99
100 newNode->key = key; 100 newNode->key = key;
101 newNode->next = node->next; 101 newNode->next = node->next;
102 node->next->prev = newNode; 102 node->next->prev = newNode;
103 newNode->prev = node; 103 newNode->prev = node;
104 node->next = newNode; 104 node->next = newNode;
105 105
106 return newNode; 106 return newNode;
107 } 107 }
108 108
109 inline void dictDelete( Dict * /*dict*/, DictN 109 inline void dictDelete( Dict * /*dict*/, DictNode *node ) /*ARGSUSED*/
110 { 110 {
111 node->next->prev = node->prev; 111 node->next->prev = node->prev;
112 node->prev->next = node->next; 112 node->prev->next = node->next;
113 memFree( node ); 113 memFree( node );
114 } 114 }
115 115
116 inline DictNode *dictSearch( Dict *dict, DictK 116 inline DictNode *dictSearch( Dict *dict, DictKey key )
117 { 117 {
118 DictNode *node = &dict->head; 118 DictNode *node = &dict->head;
119 119
120 do { 120 do {
121 node = node->next; 121 node = node->next;
122 } while( node->key != NULL && ! (*dict->leq) 122 } while( node->key != NULL && ! (*dict->leq)(dict->frame, key, node->key));
123 123
124 return node; 124 return node;
125 } 125 }
126 126
127 #endif 127 #endif