This source file includes following definitions.
- gl_linkedhash_nx_create_empty
- gl_linkedhash_size
- gl_linkedhash_search
- gl_linkedhash_nx_getput
- gl_linkedhash_getremove
- gl_linkedhash_free
- gl_linkedhash_iterator
- gl_linkedhash_iterator_next
- gl_linkedhash_iterator_free
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 #include <config.h>
19
20
21 #include "gl_linkedhash_map.h"
22
23 #include <stdint.h>
24 #include <stdlib.h>
25
26 #include "xsize.h"
27
28
29
30 #include "gl_anyhash1.h"
31
32
33 struct gl_list_node_impl
34 {
35 struct gl_hash_entry h;
36 struct gl_list_node_impl *next;
37 struct gl_list_node_impl *prev;
38 const void *key;
39 const void *value;
40 };
41 typedef struct gl_list_node_impl * gl_list_node_t;
42
43
44 struct gl_map_impl
45 {
46 struct gl_map_impl_base base;
47 gl_mapkey_hashcode_fn hashcode_fn;
48
49 struct gl_hash_entry **table;
50 size_t table_size;
51
52
53
54 struct gl_list_node_impl root;
55
56 size_t count;
57 };
58
59 #define CONTAINER_T gl_map_t
60 #define CONTAINER_COUNT(map) (map)->count
61 #include "gl_anyhash2.h"
62
63
64
65
66
67
68
69
70
71
72
73
74 #ifdef SIGNAL_SAFE_MAP
75 # define ASYNCSAFE(type) *(type volatile *)&
76 #else
77 # define ASYNCSAFE(type)
78 #endif
79
80
81
82 static gl_map_t
83 gl_linkedhash_nx_create_empty (gl_map_implementation_t implementation,
84 gl_mapkey_equals_fn equals_fn,
85 gl_mapkey_hashcode_fn hashcode_fn,
86 gl_mapkey_dispose_fn kdispose_fn,
87 gl_mapvalue_dispose_fn vdispose_fn)
88 {
89 struct gl_map_impl *map =
90 (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl));
91
92 if (map == NULL)
93 return NULL;
94
95 map->base.vtable = implementation;
96 map->base.equals_fn = equals_fn;
97 map->base.kdispose_fn = kdispose_fn;
98 map->base.vdispose_fn = vdispose_fn;
99 map->hashcode_fn = hashcode_fn;
100 map->table_size = 11;
101 map->table =
102 (gl_hash_entry_t *) calloc (map->table_size, sizeof (gl_hash_entry_t));
103 if (map->table == NULL)
104 goto fail;
105 map->root.next = &map->root;
106 map->root.prev = &map->root;
107 map->count = 0;
108
109 return map;
110
111 fail:
112 free (map);
113 return NULL;
114 }
115
116 static size_t _GL_ATTRIBUTE_PURE
117 gl_linkedhash_size (gl_map_t map)
118 {
119 return map->count;
120 }
121
122 static bool _GL_ATTRIBUTE_PURE
123 gl_linkedhash_search (gl_map_t map, const void *key, const void **valuep)
124 {
125 size_t hashcode =
126 (map->hashcode_fn != NULL
127 ? map->hashcode_fn (key)
128 : (size_t)(uintptr_t) key);
129 size_t bucket = hashcode % map->table_size;
130 gl_mapkey_equals_fn equals = map->base.equals_fn;
131
132
133 gl_list_node_t node;
134
135 for (node = (gl_list_node_t) map->table[bucket];
136 node != NULL;
137 node = (gl_list_node_t) node->h.hash_next)
138 if (node->h.hashcode == hashcode
139 && (equals != NULL
140 ? equals (key, node->key)
141 : key == node->key))
142 {
143 *valuep = node->value;
144 return true;
145 }
146 return false;
147 }
148
149 static int
150 gl_linkedhash_nx_getput (gl_map_t map, const void *key, const void *value,
151 const void **oldvaluep)
152 {
153 size_t hashcode =
154 (map->hashcode_fn != NULL
155 ? map->hashcode_fn (key)
156 : (size_t)(uintptr_t) key);
157 size_t bucket = hashcode % map->table_size;
158 gl_mapkey_equals_fn equals = map->base.equals_fn;
159
160
161 {
162 gl_list_node_t node;
163
164 for (node = (gl_list_node_t) map->table[bucket];
165 node != NULL;
166 node = (gl_list_node_t) node->h.hash_next)
167 if (node->h.hashcode == hashcode
168 && (equals != NULL
169 ? equals (key, node->key)
170 : key == node->key))
171 {
172 *oldvaluep = node->value;
173 node->value = value;
174 return 0;
175 }
176 }
177
178
179 gl_list_node_t node =
180 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
181
182 if (node == NULL)
183 return -1;
184
185 ASYNCSAFE(const void *) node->key = key;
186 ASYNCSAFE(const void *) node->value = value;
187 node->h.hashcode = hashcode;
188
189
190 node->h.hash_next = map->table[bucket];
191 map->table[bucket] = &node->h;
192
193
194 ASYNCSAFE(gl_list_node_t) node->next = &map->root;
195 node->prev = map->root.prev;
196 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
197 map->root.prev = node;
198 map->count++;
199
200 hash_resize_after_add (map);
201
202 return 1;
203 }
204
205 static bool
206 gl_linkedhash_getremove (gl_map_t map, const void *key, const void **oldvaluep)
207 {
208 size_t hashcode =
209 (map->hashcode_fn != NULL
210 ? map->hashcode_fn (key)
211 : (size_t)(uintptr_t) key);
212 size_t bucket = hashcode % map->table_size;
213 gl_mapkey_equals_fn equals = map->base.equals_fn;
214
215
216 gl_list_node_t *nodep;
217
218 for (nodep = (gl_list_node_t *) &map->table[bucket];
219 *nodep != NULL;
220 nodep = (gl_list_node_t *) &(*nodep)->h.hash_next)
221 {
222 gl_list_node_t node = *nodep;
223 if (node->h.hashcode == hashcode
224 && (equals != NULL
225 ? equals (key, node->key)
226 : key == node->key))
227 {
228 *oldvaluep = node->value;
229
230
231 *nodep = (gl_list_node_t) node->h.hash_next;
232
233
234 {
235 gl_list_node_t prev = node->prev;
236 gl_list_node_t next = node->next;
237
238 ASYNCSAFE(gl_list_node_t) prev->next = next;
239 next->prev = prev;
240 }
241 map->count--;
242
243 if (map->base.kdispose_fn != NULL)
244 map->base.kdispose_fn (node->key);
245 free (node);
246 return true;
247 }
248 }
249
250 return false;
251 }
252
253 static void
254 gl_linkedhash_free (gl_map_t map)
255 {
256 gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
257 gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
258 gl_list_node_t node;
259
260 for (node = map->root.next; node != &map->root; )
261 {
262 gl_list_node_t next = node->next;
263 if (vdispose != NULL)
264 vdispose (node->value);
265 if (kdispose != NULL)
266 kdispose (node->key);
267 free (node);
268 node = next;
269 }
270 free (map->table);
271 free (map);
272 }
273
274
275
276
277
278
279 static gl_map_iterator_t
280 gl_linkedhash_iterator (gl_map_t map)
281 {
282 gl_map_iterator_t result;
283
284 result.vtable = map->base.vtable;
285 result.map = map;
286 result.p = map->root.next;
287 result.q = &map->root;
288 #if defined GCC_LINT || defined lint
289 result.i = 0;
290 result.j = 0;
291 result.count = 0;
292 #endif
293
294 return result;
295 }
296
297 static bool
298 gl_linkedhash_iterator_next (gl_map_iterator_t *iterator,
299 const void **keyp, const void **valuep)
300 {
301 if (iterator->p != iterator->q)
302 {
303 gl_list_node_t node = (gl_list_node_t) iterator->p;
304 *keyp = node->key;
305 *valuep = node->value;
306 iterator->p = node->next;
307 return true;
308 }
309 else
310 return false;
311 }
312
313 static void
314 gl_linkedhash_iterator_free (gl_map_iterator_t *iterator)
315 {
316 }
317
318
319 const struct gl_map_implementation gl_linkedhash_map_implementation =
320 {
321 gl_linkedhash_nx_create_empty,
322 gl_linkedhash_size,
323 gl_linkedhash_search,
324 gl_linkedhash_nx_getput,
325 gl_linkedhash_getremove,
326 gl_linkedhash_free,
327 gl_linkedhash_iterator,
328 gl_linkedhash_iterator_next,
329 gl_linkedhash_iterator_free
330 };