1 /* Set data type implemented by a hash table.
2 Copyright (C) 2006, 2008-2023 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_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 gl_list_node_t node;
106
107 for (node = (gl_list_node_t) set->table[bucket];
108 node != NULL;
109 node = (gl_list_node_t) node->h.hash_next)
110 if (node->h.hashcode == hashcode
111 && (equals != NULL
112 ? equals (elt, node->value)
113 : elt == node->value))
114 return true;
115 return false;
116 }
117
118 static int
119 gl_hash_nx_add (gl_set_t set, const void *elt)
120 {
121 size_t hashcode =
122 (set->hashcode_fn != NULL
123 ? set->hashcode_fn (elt)
124 : (size_t)(uintptr_t) elt);
125 size_t bucket = hashcode % set->table_size;
126 gl_setelement_equals_fn equals = set->base.equals_fn;
127
128 /* Look for a match in the hash bucket. */
129 {
130 gl_list_node_t node;
131
132 for (node = (gl_list_node_t) set->table[bucket];
133 node != NULL;
134 node = (gl_list_node_t) node->h.hash_next)
135 if (node->h.hashcode == hashcode
136 && (equals != NULL
137 ? equals (elt, node->value)
138 : elt == node->value))
139 return 0;
140 }
141
142 /* Allocate a new node. */
143 gl_list_node_t node =
144 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
145
146 if (node == NULL)
147 return -1;
148
149 node->value = elt;
150 node->h.hashcode = hashcode;
151
152 /* Add node to the hash table. */
153 node->h.hash_next = set->table[bucket];
154 set->table[bucket] = &node->h;
155
156 /* Add node to the set. */
157 set->count++;
158
159 hash_resize_after_add (set);
160
161 return 1;
162 }
163
164 static bool
165 gl_hash_remove (gl_set_t set, const void *elt)
166 {
167 size_t hashcode =
168 (set->hashcode_fn != NULL
169 ? set->hashcode_fn (elt)
170 : (size_t)(uintptr_t) elt);
171 size_t bucket = hashcode % set->table_size;
172 gl_setelement_equals_fn equals = set->base.equals_fn;
173
174 /* Look for the first match in the hash bucket. */
175 gl_list_node_t *nodep;
176
177 for (nodep = (gl_list_node_t *) &set->table[bucket];
178 *nodep != NULL;
179 nodep = (gl_list_node_t *) &(*nodep)->h.hash_next)
180 {
181 gl_list_node_t node = *nodep;
182 if (node->h.hashcode == hashcode
183 && (equals != NULL
184 ? equals (elt, node->value)
185 : elt == node->value))
186 {
187 /* Remove node from the hash table. */
188 *nodep = (gl_list_node_t) node->h.hash_next;
189
190 /* Remove node from the set. */
191 set->count--;
192
193 if (set->base.dispose_fn != NULL)
194 set->base.dispose_fn (node->value);
195 free (node);
196 return true;
197 }
198 }
199
200 return false;
201 }
202
203 static void
204 gl_hash_free (gl_set_t set)
205 {
206 if (set->count > 0)
207 {
208 gl_setelement_dispose_fn dispose = set->base.dispose_fn;
209 struct gl_hash_entry **table = set->table;
210 size_t i;
211
212 for (i = set->table_size; i > 0; )
213 {
214 gl_hash_entry_t node = table[--i];
215
216 while (node != NULL)
217 {
218 gl_hash_entry_t next = node->hash_next;
219
220 /* Free the entry. */
221 if (dispose != NULL)
222 dispose (((gl_list_node_t) node)->value);
223 free (node);
224
225 node = next;
226 }
227 }
228 }
229
230 free (set->table);
231 free (set);
232 }
233
234 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */
235
236 /* Here we iterate through the hash buckets. Therefore the order in which the
237 elements are returned is unpredictable. */
238
239 static gl_set_iterator_t
240 gl_hash_iterator (gl_set_t set)
241 {
242 gl_set_iterator_t result;
243
244 result.vtable = set->base.vtable;
245 result.set = set;
246 result.p = NULL; /* runs through the nodes of a bucket */
247 result.i = 0; /* index of the bucket that p points into + 1 */
248 result.j = set->table_size;
249 #if defined GCC_LINT || defined lint
250 result.q = NULL;
251 result.count = 0;
252 #endif
253
254 return result;
255 }
256
257 static bool
258 gl_hash_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
259 {
260 if (iterator->p != NULL)
261 {
262 /* We're traversing a bucket. */
263 gl_list_node_t node = (gl_list_node_t) iterator->p;
264 *eltp = node->value;
265 iterator->p = (gl_list_node_t) node->h.hash_next;
266 return true;
267 }
268 else
269 {
270 /* Find the next bucket that is not empty. */
271 size_t j = iterator->j;
272 size_t i = iterator->i;
273
274 if (i < j)
275 {
276 gl_hash_entry_t *table = iterator->set->table;
277 do
278 {
279 gl_list_node_t node = (gl_list_node_t) table[i++];
280 if (node != NULL)
281 {
282 *eltp = node->value;
283 iterator->p = (gl_list_node_t) node->h.hash_next;
284 iterator->i = i;
285 return true;
286 }
287 }
288 while (i < j);
289 }
290 /* Here iterator->p is still NULL, and i == j. */
291 iterator->i = j;
292 return false;
293 }
294 }
295
296 static void
297 gl_hash_iterator_free (gl_set_iterator_t *iterator)
298 {
299 }
300
301
302 const struct gl_set_implementation gl_hash_set_implementation =
303 {
304 gl_hash_nx_create_empty,
305 gl_hash_size,
306 gl_hash_search,
307 gl_hash_nx_add,
308 gl_hash_remove,
309 gl_hash_free,
310 gl_hash_iterator,
311 gl_hash_iterator_next,
312 gl_hash_iterator_free
313 };