lib/gl_linkedhash_set.c

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