lib/gl_linkedhash_set.c

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