1 /* Map data type implemented by a hash table with a linked list.
2 Copyright (C) 2006, 2008-2021 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2018.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 /* Specification. */
21 #include "gl_linkedhash_map.h"
22
23 #include <stdint.h> /* for uintptr_t, SIZE_MAX */
24 #include <stdlib.h>
25
26 #include "xsize.h"
27
28 /* --------------------------- gl_map_t Data Type --------------------------- */
29
30 #include "gl_anyhash1.h"
31
32 /* Concrete list node implementation, valid for this file only. */
33 struct gl_list_node_impl
34 {
35 struct gl_hash_entry h; /* hash table entry fields; must be first */
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 /* Concrete gl_map_impl type, valid for this file only. */
44 struct gl_map_impl
45 {
46 struct gl_map_impl_base base;
47 gl_mapkey_hashcode_fn hashcode_fn;
48 /* A hash table: managed as an array of collision lists. */
49 struct gl_hash_entry **table;
50 size_t table_size;
51 /* A circular list anchored at root.
52 The first node is = root.next, the last node is = root.prev.
53 The root's value is unused. */
54 struct gl_list_node_impl root;
55 /* Number of list nodes, excluding the root. */
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 /* If the symbol SIGNAL_SAFE_MAP is defined, the code is compiled in such
64 a way that a gl_map_t data structure may be used from within a signal
65 handler. The operations allowed in the signal handler are:
66 gl_map_iterator, gl_map_iterator_next, gl_map_iterator_free.
67 The map and node fields that are therefore accessed from the signal handler
68 are:
69 map->root, node->next, node->value.
70 We are careful to make modifications to these fields only in an order
71 that maintains the consistency of the list data structure at any moment,
72 and we use 'volatile' assignments to prevent the compiler from reordering
73 such assignments. */
74 #ifdef SIGNAL_SAFE_MAP
75 # define ASYNCSAFE(type) *(type volatile *)&
76 #else
77 # define ASYNCSAFE(type)
78 #endif
79
80 /* --------------------------- gl_map_t Data Type --------------------------- */
81
82 static gl_map_t
gl_linkedhash_nx_create_empty(gl_map_implementation_t implementation,gl_mapkey_equals_fn equals_fn,gl_mapkey_hashcode_fn hashcode_fn,gl_mapkey_dispose_fn kdispose_fn,gl_mapvalue_dispose_fn vdispose_fn)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
gl_linkedhash_size(gl_map_t map)117 gl_linkedhash_size (gl_map_t map)
118 {
119 return map->count;
120 }
121
122 static bool _GL_ATTRIBUTE_PURE
gl_linkedhash_search(gl_map_t map,const void * key,const void ** valuep)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 /* Look for a match in the hash bucket. */
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
gl_linkedhash_nx_getput(gl_map_t map,const void * key,const void * value,const void ** oldvaluep)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 /* Look for a match in the hash bucket. */
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 /* Allocate a new node. */
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 /* Add node to the hash table. */
190 node->h.hash_next = map->table[bucket];
191 map->table[bucket] = &node->h;
192
193 /* Add node to the map. */
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
gl_linkedhash_getremove(gl_map_t map,const void * key,const void ** oldvaluep)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 /* Look for the first match in the hash bucket. */
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 /* Remove node from the hash table. */
231 *nodep = (gl_list_node_t) node->h.hash_next;
232
233 /* Remove node from the list. */
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
gl_linkedhash_free(gl_map_t map)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 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
275
276 /* Iterate through the list, not through the hash buckets, so that the order
277 in which the pairs are returned is predictable. */
278
279 static gl_map_iterator_t
gl_linkedhash_iterator(gl_map_t map)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
gl_linkedhash_iterator_next(gl_map_iterator_t * iterator,const void ** keyp,const void ** valuep)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
gl_linkedhash_iterator_free(gl_map_iterator_t * iterator)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 };
331