lib/gl_hash_set.c

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