lib/gl_hash_map.c

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