Debian Codegraph @

lib/gl_hash_set.c

raw
1 /* Set data type implemented by a hash table.
2 Copyright (C) 2006, 2008-2026 Free Software Foundation, Inc.
3 Written by Bruno Haible <[email protected]>, 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_hash_set.h"
22
23 #include <stdint.h> /* for uintptr_t, SIZE_MAX */
24 #include <stdlib.h>
25
26 #include "xsize.h"
27
28 /* --------------------------- gl_set_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 const void *value;
37 };
38 typedef struct gl_list_node_impl * gl_list_node_t;
39
40 /* Concrete gl_set_impl type, valid for this file only. */
41 struct gl_set_impl
42 {
43 struct gl_set_impl_base base;
44 gl_setelement_hashcode_fn hashcode_fn;
45 /* A hash table: managed as an array of collision lists. */
46 struct gl_hash_entry **table;
47 size_t table_size;
48 /* Number of hash table entries. */
49 size_t count;
50 };
51
52 #define CONTAINER_T gl_set_t
53 #define CONTAINER_COUNT(set) (set)->count
54 #include "gl_anyhash2.h"
55
56 /* --------------------------- gl_set_t Data Type --------------------------- */
57
58 static gl_set_t
59 gl_hash_nx_create_empty (gl_set_implementation_t implementation,
60 gl_setelement_equals_fn equals_fn,
61 gl_setelement_hashcode_fn hashcode_fn,
62 gl_setelement_dispose_fn dispose_fn)
63 {
64 struct gl_set_impl *set =
65 (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl));
66
67 if (set == NULL)
68 return NULL;
69
70 set->base.vtable = implementation;
71 set->base.equals_fn = equals_fn;
72 set->base.dispose_fn = dispose_fn;
73 set->hashcode_fn = hashcode_fn;
74 set->table_size = 11;
75 set->table =
76 (gl_hash_entry_t *) calloc (set->table_size, sizeof (gl_hash_entry_t));
77 if (set->table == NULL)
78 goto fail;
79 set->count = 0;
80
81 return set;
82
83 fail:
84 free (set);
85 return NULL;
86 }
87
88 static size_t _GL_ATTRIBUTE_PURE
89 gl_hash_size (gl_set_t set)
90 {
91 return set->count;
92 }
93
94 static bool _GL_ATTRIBUTE_PURE
95 gl_hash_search (gl_set_t set, const void *elt)
96 {
97 size_t hashcode =
98 (set->hashcode_fn != NULL
99 ? set->hashcode_fn (elt)
100 : (size_t)(uintptr_t) elt);
101 size_t bucket = hashcode % set->table_size;
102 gl_setelement_equals_fn equals = set->base.equals_fn;
103
104 /* Look for a match in the hash bucket. */
105 for (gl_list_node_t node = (gl_list_node_t) set->table[bucket];
106 node != NULL;
107 node = (gl_list_node_t) node->h.hash_next)
108 if (node->h.hashcode == hashcode
109 && (equals != NULL
110 ? equals (elt, node->value)
111 : elt == node->value))
112 return true;
113 return false;
114 }
115
116 static int
117 gl_hash_nx_add (gl_set_t set, const void *elt)
118 {
119 size_t hashcode =
120 (set->hashcode_fn != NULL
121 ? set->hashcode_fn (elt)
122 : (size_t)(uintptr_t) elt);
123 size_t bucket = hashcode % set->table_size;
124 gl_setelement_equals_fn equals = set->base.equals_fn;
125
126 /* Look for a match in the hash bucket. */
127 for (gl_list_node_t node = (gl_list_node_t) set->table[bucket];
128 node != NULL;
129 node = (gl_list_node_t) node->h.hash_next)
130 if (node->h.hashcode == hashcode
131 && (equals != NULL
132 ? equals (elt, node->value)
133 : elt == node->value))
134 return 0;
135
136 /* Allocate a new node. */
137 gl_list_node_t node =
138 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
139
140 if (node == NULL)
141 return -1;
142
143 node->value = elt;
144 node->h.hashcode = hashcode;
145
146 /* Add node to the hash table. */
147 node->h.hash_next = set->table[bucket];
148 set->table[bucket] = &node->h;
149
150 /* Add node to the set. */
151 set->count++;
152
153 hash_resize_after_add (set);
154
155 return 1;
156 }
157
158 static bool
159 gl_hash_remove (gl_set_t set, const void *elt)
160 {
161 size_t hashcode =
162 (set->hashcode_fn != NULL
163 ? set->hashcode_fn (elt)
164 : (size_t)(uintptr_t) elt);
165 size_t bucket = hashcode % set->table_size;
166 gl_setelement_equals_fn equals = set->base.equals_fn;
167
168 /* Look for the first match in the hash bucket. */
169 for (gl_list_node_t *nodep = (gl_list_node_t *) &set->table[bucket];
170 *nodep != NULL;
171 nodep = (gl_list_node_t *) &(*nodep)->h.hash_next)
172 {
173 gl_list_node_t node = *nodep;
174 if (node->h.hashcode == hashcode
175 && (equals != NULL
176 ? equals (elt, node->value)
177 : elt == node->value))
178 {
179 /* Remove node from the hash table. */
180 *nodep = (gl_list_node_t) node->h.hash_next;
181
182 /* Remove node from the set. */
183 set->count--;
184
185 if (set->base.dispose_fn != NULL)
186 set->base.dispose_fn (node->value);
187 free (node);
188 return true;
189 }
190 }
191
192 return false;
193 }
194
195 static void
196 gl_hash_free (gl_set_t set)
197 {
198 if (set->count > 0)
199 {
200 gl_setelement_dispose_fn dispose = set->base.dispose_fn;
201 struct gl_hash_entry **table = set->table;
202
203 for (size_t i = set->table_size; i > 0; )
204 {
205 gl_hash_entry_t node = table[--i];
206
207 while (node != NULL)
208 {
209 gl_hash_entry_t next = node->hash_next;
210
211 /* Free the entry. */
212 if (dispose != NULL)
213 dispose (((gl_list_node_t) node)->value);
214 free (node);
215
216 node = next;
217 }
218 }
219 }
220
221 free (set->table);
222 free (set);
223 }
224
225 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */
226
227 /* Here we iterate through the hash buckets. Therefore the order in which the
228 elements are returned is unpredictable. */
229
230 static gl_set_iterator_t
231 gl_hash_iterator (gl_set_t set)
232 {
233 gl_set_iterator_t result;
234
235 result.vtable = set->base.vtable;
236 result.set = set;
237 result.p = NULL; /* runs through the nodes of a bucket */
238 result.i = 0; /* index of the bucket that p points into + 1 */
239 result.j = set->table_size;
240 #if defined GCC_LINT || defined lint
241 result.q = NULL;
242 result.count = 0;
243 #endif
244
245 return result;
246 }
247
248 static bool
249 gl_hash_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
250 {
251 if (iterator->p != NULL)
252 {
253 /* We're traversing a bucket. */
254 gl_list_node_t node = (gl_list_node_t) iterator->p;
255 *eltp = node->value;
256 iterator->p = (gl_list_node_t) node->h.hash_next;
257 return true;
258 }
259 else
260 {
261 /* Find the next bucket that is not empty. */
262 size_t j = iterator->j;
263 size_t i = iterator->i;
264
265 if (i < j)
266 {
267 gl_hash_entry_t *table = iterator->set->table;
268 do
269 {
270 gl_list_node_t node = (gl_list_node_t) table[i++];
271 if (node != NULL)
272 {
273 *eltp = node->value;
274 iterator->p = (gl_list_node_t) node->h.hash_next;
275 iterator->i = i;
276 return true;
277 }
278 }
279 while (i < j);
280 }
281 /* Here iterator->p is still NULL, and i == j. */
282 iterator->i = j;
283 return false;
284 }
285 }
286
287 static void
288 gl_hash_iterator_free (gl_set_iterator_t *iterator)
289 {
290 }
291
292
293 const struct gl_set_implementation gl_hash_set_implementation =
294 {
295 gl_hash_nx_create_empty,
296 gl_hash_size,
297 gl_hash_search,
298 gl_hash_nx_add,
299 gl_hash_remove,
300 gl_hash_free,
301 gl_hash_iterator,
302 gl_hash_iterator_next,
303 gl_hash_iterator_free
304 };