1 /* Set data type implemented by a hash table.
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_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
gl_hash_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)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
gl_hash_size(gl_set_t set)89 gl_hash_size (gl_set_t set)
90 {
91   return set->count;
92 }
93 
94 static bool _GL_ATTRIBUTE_PURE
gl_hash_search(gl_set_t set,const void * elt)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
gl_hash_nx_add(gl_set_t set,const void * elt)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
gl_hash_remove(gl_set_t set,const void * elt)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
gl_hash_free(gl_set_t set)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
gl_hash_iterator(gl_set_t set)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
gl_hash_iterator_next(gl_set_iterator_t * iterator,const void ** eltp)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
gl_hash_iterator_free(gl_set_iterator_t * iterator)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   };
314