maint/gnulib/lib/gl_hash

/* */
This source file includes following definitions.
gl_hash_nx_create_empty
gl_hash_size
gl_hash_search
gl_hash_nx_add
gl_hash_remove
gl_hash_free
gl_hash_iterator
gl_hash_iterator_next
gl_hash_iterator_free
   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
  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   };
/* */
root/maint/gnulib/lib/gl_hash_set.c

DEFINITIONS
