1 /* Set 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_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 struct gl_list_node_impl *next;
37 struct gl_list_node_impl *prev;
38 const void *value;
39 };
40 typedef struct gl_list_node_impl * gl_list_node_t;
41
42 /* Concrete gl_set_impl type, valid for this file only. */
43 struct gl_set_impl
44 {
45 struct gl_set_impl_base base;
46 gl_setelement_hashcode_fn hashcode_fn;
47 /* A hash table: managed as an array of collision lists. */
48 struct gl_hash_entry **table;
49 size_t table_size;
50 /* A circular list anchored at root.
51 The first node is = root.next, the last node is = root.prev.
52 The root's value is unused. */
53 struct gl_list_node_impl root;
54 /* Number of list nodes, excluding the root. */
55 size_t count;
56 };
57
58 #define CONTAINER_T gl_set_t
59 #define CONTAINER_COUNT(set) (set)->count
60 #include "gl_anyhash2.h"
61
62 /* If the symbol SIGNAL_SAFE_SET is defined, the code is compiled in such
63 a way that a gl_set_t data structure may be used from within a signal
64 handler. The operations allowed in the signal handler are:
65 gl_set_iterator, gl_set_iterator_next, gl_set_iterator_free.
66 The set and node fields that are therefore accessed from the signal handler
67 are:
68 set->root, node->next, node->value.
69 We are careful to make modifications to these fields only in an order
70 that maintains the consistency of the list data structure at any moment,
71 and we use 'volatile' assignments to prevent the compiler from reordering
72 such assignments. */
73 #ifdef SIGNAL_SAFE_SET
74 # define ASYNCSAFE(type) *(type volatile *)&
75 #else
76 # define ASYNCSAFE(type)
77 #endif
78
79 /* --------------------------- gl_set_t Data Type --------------------------- */
80
81 static gl_set_t
gl_linkedhash_nx_create_empty(gl_set_implementation_t implementation,gl_setelement_equals_fn equals_fn,gl_setelement_hashcode_fn hashcode_fn,gl_setelement_dispose_fn dispose_fn)82 gl_linkedhash_nx_create_empty (gl_set_implementation_t implementation,
83 gl_setelement_equals_fn equals_fn,
84 gl_setelement_hashcode_fn hashcode_fn,
85 gl_setelement_dispose_fn dispose_fn)
86 {
87 struct gl_set_impl *set =
88 (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl));
89
90 if (set == NULL)
91 return NULL;
92
93 set->base.vtable = implementation;
94 set->base.equals_fn = equals_fn;
95 set->base.dispose_fn = dispose_fn;
96 set->hashcode_fn = hashcode_fn;
97 set->table_size = 11;
98 set->table =
99 (gl_hash_entry_t *) calloc (set->table_size, sizeof (gl_hash_entry_t));
100 if (set->table == NULL)
101 goto fail;
102 set->root.next = &set->root;
103 set->root.prev = &set->root;
104 set->count = 0;
105
106 return set;
107
108 fail:
109 free (set);
110 return NULL;
111 }
112
113 static size_t _GL_ATTRIBUTE_PURE
gl_linkedhash_size(gl_set_t set)114 gl_linkedhash_size (gl_set_t set)
115 {
116 return set->count;
117 }
118
119 static bool _GL_ATTRIBUTE_PURE
gl_linkedhash_search(gl_set_t set,const void * elt)120 gl_linkedhash_search (gl_set_t set, const void *elt)
121 {
122 size_t hashcode =
123 (set->hashcode_fn != NULL
124 ? set->hashcode_fn (elt)
125 : (size_t)(uintptr_t) elt);
126 size_t bucket = hashcode % set->table_size;
127 gl_setelement_equals_fn equals = set->base.equals_fn;
128
129 /* Look for a match in the hash bucket. */
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 true;
140 return false;
141 }
142
143 static int
gl_linkedhash_nx_add(gl_set_t set,const void * elt)144 gl_linkedhash_nx_add (gl_set_t set, const void *elt)
145 {
146 size_t hashcode =
147 (set->hashcode_fn != NULL
148 ? set->hashcode_fn (elt)
149 : (size_t)(uintptr_t) elt);
150 size_t bucket = hashcode % set->table_size;
151 gl_setelement_equals_fn equals = set->base.equals_fn;
152
153 /* Look for a match in the hash bucket. */
154 {
155 gl_list_node_t node;
156
157 for (node = (gl_list_node_t) set->table[bucket];
158 node != NULL;
159 node = (gl_list_node_t) node->h.hash_next)
160 if (node->h.hashcode == hashcode
161 && (equals != NULL
162 ? equals (elt, node->value)
163 : elt == node->value))
164 return 0;
165 }
166
167 /* Allocate a new node. */
168 gl_list_node_t node =
169 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
170
171 if (node == NULL)
172 return -1;
173
174 ASYNCSAFE(const void *) node->value = elt;
175 node->h.hashcode = hashcode;
176
177 /* Add node to the hash table. */
178 node->h.hash_next = set->table[bucket];
179 set->table[bucket] = &node->h;
180
181 /* Add node to the set. */
182 ASYNCSAFE(gl_list_node_t) node->next = &set->root;
183 node->prev = set->root.prev;
184 ASYNCSAFE(gl_list_node_t) node->prev->next = node;
185 set->root.prev = node;
186 set->count++;
187
188 hash_resize_after_add (set);
189
190 return 1;
191 }
192
193 static bool
gl_linkedhash_remove(gl_set_t set,const void * elt)194 gl_linkedhash_remove (gl_set_t set, const void *elt)
195 {
196 size_t hashcode =
197 (set->hashcode_fn != NULL
198 ? set->hashcode_fn (elt)
199 : (size_t)(uintptr_t) elt);
200 size_t bucket = hashcode % set->table_size;
201 gl_setelement_equals_fn equals = set->base.equals_fn;
202
203 /* Look for the first match in the hash bucket. */
204 gl_list_node_t *nodep;
205
206 for (nodep = (gl_list_node_t *) &set->table[bucket];
207 *nodep != NULL;
208 nodep = (gl_list_node_t *) &(*nodep)->h.hash_next)
209 {
210 gl_list_node_t node = *nodep;
211 if (node->h.hashcode == hashcode
212 && (equals != NULL
213 ? equals (elt, node->value)
214 : elt == node->value))
215 {
216 /* Remove node from the hash table. */
217 *nodep = (gl_list_node_t) node->h.hash_next;
218
219 /* Remove node from the list. */
220 {
221 gl_list_node_t prev = node->prev;
222 gl_list_node_t next = node->next;
223
224 ASYNCSAFE(gl_list_node_t) prev->next = next;
225 next->prev = prev;
226 }
227 set->count--;
228
229 if (set->base.dispose_fn != NULL)
230 set->base.dispose_fn (node->value);
231 free (node);
232 return true;
233 }
234 }
235
236 return false;
237 }
238
239 static void
gl_linkedhash_free(gl_set_t set)240 gl_linkedhash_free (gl_set_t set)
241 {
242 gl_setelement_dispose_fn dispose = set->base.dispose_fn;
243 gl_list_node_t node;
244
245 for (node = set->root.next; node != &set->root; )
246 {
247 gl_list_node_t next = node->next;
248 if (dispose != NULL)
249 dispose (node->value);
250 free (node);
251 node = next;
252 }
253 free (set->table);
254 free (set);
255 }
256
257 /* ---------------------- gl_set_iterator_t Data Type ---------------------- */
258
259 /* Iterate through the list, not through the hash buckets, so that the order
260 in which the elements are returned is predictable. */
261
262 static gl_set_iterator_t
gl_linkedhash_iterator(gl_set_t set)263 gl_linkedhash_iterator (gl_set_t set)
264 {
265 gl_set_iterator_t result;
266
267 result.vtable = set->base.vtable;
268 result.set = set;
269 result.p = set->root.next;
270 result.q = &set->root;
271 #if defined GCC_LINT || defined lint
272 result.i = 0;
273 result.j = 0;
274 result.count = 0;
275 #endif
276
277 return result;
278 }
279
280 static bool
gl_linkedhash_iterator_next(gl_set_iterator_t * iterator,const void ** eltp)281 gl_linkedhash_iterator_next (gl_set_iterator_t *iterator, const void **eltp)
282 {
283 if (iterator->p != iterator->q)
284 {
285 gl_list_node_t node = (gl_list_node_t) iterator->p;
286 *eltp = node->value;
287 iterator->p = node->next;
288 return true;
289 }
290 else
291 return false;
292 }
293
294 static void
gl_linkedhash_iterator_free(gl_set_iterator_t * iterator)295 gl_linkedhash_iterator_free (gl_set_iterator_t *iterator)
296 {
297 }
298
299
300 const struct gl_set_implementation gl_linkedhash_set_implementation =
301 {
302 gl_linkedhash_nx_create_empty,
303 gl_linkedhash_size,
304 gl_linkedhash_search,
305 gl_linkedhash_nx_add,
306 gl_linkedhash_remove,
307 gl_linkedhash_free,
308 gl_linkedhash_iterator,
309 gl_linkedhash_iterator_next,
310 gl_linkedhash_iterator_free
311 };
312