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