lib/gl_linkedhash_map.c

   1 /* Map data type implemented by a hash table with a linked list.
   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_linkedhash_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   struct gl_list_node_impl *next;
  41   struct gl_list_node_impl *prev;
  42   const void *key;
  43   const void *value;
  44 };
  45 typedef struct gl_list_node_impl * gl_list_node_t;
  46
  47 /* Concrete gl_map_impl type, valid for this file only.  */
  48 struct gl_map_impl
  49 {
  50   struct gl_map_impl_base base;
  51   gl_mapkey_hashcode_fn hashcode_fn;
  52   /* A hash table: managed as an array of collision lists.  */
  53   struct gl_hash_entry **table;
  54   size_t table_size;
  55   /* A circular list anchored at root.
  56      The first node is = root.next, the last node is = root.prev.
  57      The root's value is unused.  */
  58   struct gl_list_node_impl root;
  59   /* Number of list nodes, excluding the root.  */
  60   size_t count;
  61 };
  62
  63 #define CONTAINER_T gl_map_t
  64 #define CONTAINER_COUNT(map) (map)->count
  65 #include "gl_anyhash2.h"
  66
  67 /* If the symbol SIGNAL_SAFE_MAP is defined, the code is compiled in such
  68    a way that a gl_map_t data structure may be used from within a signal
  69    handler.  The operations allowed in the signal handler are:
  70      gl_map_iterator, gl_map_iterator_next, gl_map_iterator_free.
  71    The map and node fields that are therefore accessed from the signal handler
  72    are:
  73      map->root, node->next, node->value.
  74    We are careful to make modifications to these fields only in an order
  75    that maintains the consistency of the list data structure at any moment,
  76    and we use 'volatile' assignments to prevent the compiler from reordering
  77    such assignments.  */
  78 #ifdef SIGNAL_SAFE_MAP
  79 # define ASYNCSAFE(type) *(type volatile *)&
  80 #else
  81 # define ASYNCSAFE(type)
  82 #endif
  83
  84 /* --------------------------- gl_map_t Data Type --------------------------- */
  85
  86 static gl_map_t
  87 gl_linkedhash_nx_create_empty (gl_map_implementation_t implementation,
  88                                gl_mapkey_equals_fn equals_fn,
  89                                gl_mapkey_hashcode_fn hashcode_fn,
  90                                gl_mapkey_dispose_fn kdispose_fn,
  91                                gl_mapvalue_dispose_fn vdispose_fn)
  92 {
  93   struct gl_map_impl *map =
  94     (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl));
  95
  96   if (map == NULL)
  97     return NULL;
  98
  99   map->base.vtable = implementation;
 100   map->base.equals_fn = equals_fn;
 101   map->base.kdispose_fn = kdispose_fn;
 102   map->base.vdispose_fn = vdispose_fn;
 103   map->hashcode_fn = hashcode_fn;
 104   map->table_size = 11;
 105   map->table =
 106     (gl_hash_entry_t *) calloc (map->table_size, sizeof (gl_hash_entry_t));
 107   if (map->table == NULL)
 108     goto fail;
 109   map->root.next = &map->root;
 110   map->root.prev = &map->root;
 111   map->count = 0;
 112
 113   return map;
 114
 115  fail:
 116   free (map);
 117   return NULL;
 118 }
 119
 120 static size_t _GL_ATTRIBUTE_PURE
 121 gl_linkedhash_size (gl_map_t map)
 122 {
 123   return map->count;
 124 }
 125
 126 static bool _GL_ATTRIBUTE_PURE
 127 gl_linkedhash_search (gl_map_t map, const void *key, const void **valuep)
 128 {
 129   size_t hashcode =
 130     (map->hashcode_fn != NULL
 131      ? map->hashcode_fn (key)
 132      : (size_t)(uintptr_t) key);
 133   size_t bucket = hashcode % map->table_size;
 134   gl_mapkey_equals_fn equals = map->base.equals_fn;
 135
 136   /* Look for a match in the hash bucket.  */
 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         *valuep = node->value;
 148         return true;
 149       }
 150   return false;
 151 }
 152
 153 static int
 154 gl_linkedhash_nx_getput (gl_map_t map, const void *key, const void *value,
 155                          const void **oldvaluep)
 156 {
 157   size_t hashcode =
 158     (map->hashcode_fn != NULL
 159      ? map->hashcode_fn (key)
 160      : (size_t)(uintptr_t) key);
 161   size_t bucket = hashcode % map->table_size;
 162   gl_mapkey_equals_fn equals = map->base.equals_fn;
 163
 164   /* Look for a match in the hash bucket.  */
 165   {
 166     gl_list_node_t node;
 167
 168     for (node = (gl_list_node_t) map->table[bucket];
 169          node != NULL;
 170          node = (gl_list_node_t) node->h.hash_next)
 171       if (node->h.hashcode == hashcode
 172           && (equals != NULL
 173               ? equals (key, node->key)
 174               : key == node->key))
 175         {
 176           *oldvaluep = node->value;
 177           node->value = value;
 178           return 0;
 179         }
 180   }
 181
 182   /* Allocate a new node.  */
 183   gl_list_node_t node =
 184     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 185
 186   if (node == NULL)
 187     return -1;
 188
 189   ASYNCSAFE(const void *) node->key = key;
 190   ASYNCSAFE(const void *) node->value = value;
 191   node->h.hashcode = hashcode;
 192
 193   /* Add node to the hash table.  */
 194   node->h.hash_next = map->table[bucket];
 195   map->table[bucket] = &node->h;
 196
 197   /* Add node to the map.  */
 198   ASYNCSAFE(gl_list_node_t) node->next = &map->root;
 199   node->prev = map->root.prev;
 200   ASYNCSAFE(gl_list_node_t) node->prev->next = node;
 201   map->root.prev = node;
 202   map->count++;
 203
 204   hash_resize_after_add (map);
 205
 206   return 1;
 207 }
 208
 209 static bool
 210 gl_linkedhash_getremove (gl_map_t map, const void *key, const void **oldvaluep)
 211 {
 212   size_t hashcode =
 213     (map->hashcode_fn != NULL
 214      ? map->hashcode_fn (key)
 215      : (size_t)(uintptr_t) key);
 216   size_t bucket = hashcode % map->table_size;
 217   gl_mapkey_equals_fn equals = map->base.equals_fn;
 218
 219   /* Look for the first match in the hash bucket.  */
 220   gl_list_node_t *nodep;
 221
 222   for (nodep = (gl_list_node_t *) &map->table[bucket];
 223        *nodep != NULL;
 224        nodep = (gl_list_node_t *) &(*nodep)->h.hash_next)
 225     {
 226       gl_list_node_t node = *nodep;
 227       if (node->h.hashcode == hashcode
 228           && (equals != NULL
 229               ? equals (key, node->key)
 230               : key == node->key))
 231         {
 232           *oldvaluep = node->value;
 233
 234           /* Remove node from the hash table.  */
 235           *nodep = (gl_list_node_t) node->h.hash_next;
 236
 237           /* Remove node from the list.  */
 238           {
 239             gl_list_node_t prev = node->prev;
 240             gl_list_node_t next = node->next;
 241
 242             ASYNCSAFE(gl_list_node_t) prev->next = next;
 243             next->prev = prev;
 244           }
 245           map->count--;
 246
 247           if (map->base.kdispose_fn != NULL)
 248             map->base.kdispose_fn (node->key);
 249           free (node);
 250           return true;
 251         }
 252     }
 253
 254   return false;
 255 }
 256
 257 static void
 258 gl_linkedhash_free (gl_map_t map)
 259 {
 260   gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn;
 261   gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn;
 262   gl_list_node_t node;
 263
 264   for (node = map->root.next; node != &map->root; )
 265     {
 266       gl_list_node_t next = node->next;
 267       if (vdispose != NULL)
 268         vdispose (node->value);
 269       if (kdispose != NULL)
 270         kdispose (node->key);
 271       free (node);
 272       node = next;
 273     }
 274   free (map->table);
 275   free (map);
 276 }
 277
 278 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
 279
 280 /* Iterate through the list, not through the hash buckets, so that the order
 281    in which the pairs are returned is predictable.  */
 282
 283 static gl_map_iterator_t
 284 gl_linkedhash_iterator (gl_map_t map)
 285 {
 286   gl_map_iterator_t result;
 287
 288   result.vtable = map->base.vtable;
 289   result.map = map;
 290   result.p = map->root.next;
 291   result.q = &map->root;
 292 #if defined GCC_LINT || defined lint
 293   result.i = 0;
 294   result.j = 0;
 295   result.count = 0;
 296 #endif
 297
 298   return result;
 299 }
 300
 301 static bool
 302 gl_linkedhash_iterator_next (gl_map_iterator_t *iterator,
 303                              const void **keyp, const void **valuep)
 304 {
 305   if (iterator->p != iterator->q)
 306     {
 307       gl_list_node_t node = (gl_list_node_t) iterator->p;
 308       *keyp = node->key;
 309       *valuep = node->value;
 310       iterator->p = node->next;
 311       return true;
 312     }
 313   else
 314     return false;
 315 }
 316
 317 static void
 318 gl_linkedhash_iterator_free (gl_map_iterator_t *iterator)
 319 {
 320 }
 321
 322
 323 const struct gl_map_implementation gl_linkedhash_map_implementation =
 324   {
 325     gl_linkedhash_nx_create_empty,
 326     gl_linkedhash_size,
 327     gl_linkedhash_search,
 328     gl_linkedhash_nx_getput,
 329     gl_linkedhash_getremove,
 330     gl_linkedhash_free,
 331     gl_linkedhash_iterator,
 332     gl_linkedhash_iterator_next,
 333     gl_linkedhash_iterator_free
 334   };