maint/gnulib/lib/gl_linkedhash

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

DEFINITIONS
