lib/gl_hash_map.c

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