lib/gl_hash_set.c

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