lib/gl_anytreehash_list1.h

   1 /* Sequential list data type implemented by a hash table with a binary tree.
   2    Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   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 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c.  */
  19
  20 /* Hash table entry representing the same value at more than one position.  */
  21 struct gl_multiple_nodes
  22 {
  23   struct gl_hash_entry h;           /* hash table entry fields; must be first */
  24   void *magic;                      /* used to distinguish from single node */
  25   gl_oset_t nodes;                  /* set of nodes, sorted by position */
  26 };
  27 /* A value that cannot occur at the corresponding field (->left) in
  28    gl_list_node_impl.  */
  29 #define MULTIPLE_NODES_MAGIC  (void *) -1
  30
  31 /* Return the position of the given node in the tree.  */
  32 static size_t
  33 node_position (gl_list_node_t node)
  34 {
  35   size_t position = 0;
  36
  37   if (node->left != NULL)
  38     position += node->left->branch_size;
  39   for (;;)
  40     {
  41       gl_list_node_t parent = node->parent;
  42
  43       if (parent == NULL)
  44         return position;
  45       /* position is now relative to the subtree of node.  */
  46       if (parent->right == node)
  47         {
  48           position += 1;
  49           if (parent->left != NULL)
  50             position += parent->left->branch_size;
  51         }
  52       /* position is now relative to the subtree of parent.  */
  53       node = parent;
  54     }
  55 }
  56
  57 /* Compares two nodes by their position in the tree.  */
  58 static int
  59 compare_by_position (const void *x1, const void *x2)
  60 {
  61   gl_list_node_t node1 = (gl_list_node_t) x1;
  62   gl_list_node_t node2 = (gl_list_node_t) x2;
  63   size_t position1 = node_position (node1);
  64   size_t position2 = node_position (node2);
  65
  66   return (position1 > position2 ? 1 :
  67           position1 < position2 ? -1 : 0);
  68 }
  69
  70 /* Compares a node's position in the tree with a given threshold.  */
  71 static bool
  72 compare_position_threshold (const void *x, const void *threshold)
  73 {
  74   gl_list_node_t node = (gl_list_node_t) x;
  75   size_t position = node_position (node);
  76   return (position >= (uintptr_t)threshold);
  77 }
  78
  79 /* Return the first element of a non-empty ordered set of nodes.  */
  80 static gl_list_node_t
  81 gl_oset_first (gl_oset_t set)
  82 {
  83   gl_oset_iterator_t iter = gl_oset_iterator (set);
  84   const void *first;
  85
  86   if (!gl_oset_iterator_next (&iter, &first))
  87     abort ();
  88   gl_oset_iterator_free (&iter);
  89   return (gl_list_node_t) first;
  90 }
  91
  92 /* Add a node to the hash table structure.
  93    If duplicates are allowed, this function performs in average time
  94    O((log n)^2): gl_oset_nx_add may need to add an element to an ordered set
  95    of size O(n), needing O(log n) comparison function calls.  The comparison
  96    function is compare_by_position, which is O(log n) worst-case.
  97    If duplicates are forbidden, this function is O(1).
  98    Return 0 upon success, -1 upon out-of-memory.  */
  99 static int
 100 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
 101 {
 102   size_t bucket = new_node->h.hashcode % list->table_size;
 103
 104   /* If no duplicates are allowed, multiple nodes are not needed.  */
 105   if (list->base.allow_duplicates)
 106     {
 107       size_t hashcode = new_node->h.hashcode;
 108       const void *value = new_node->value;
 109       gl_listelement_equals_fn equals = list->base.equals_fn;
 110       gl_hash_entry_t *entryp;
 111
 112       for (entryp = &list->table[bucket]; *entryp != NULL; entryp = &(*entryp)->hash_next)
 113         {
 114           gl_hash_entry_t entry = *entryp;
 115
 116           if (entry->hashcode == hashcode)
 117             {
 118               if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
 119                 {
 120                   /* An entry representing multiple nodes.  */
 121                   gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
 122                   /* Only the first node is interesting.  */
 123                   gl_list_node_t node = gl_oset_first (nodes);
 124                   if (equals != NULL ? equals (value, node->value) : value == node->value)
 125                     {
 126                       /* Found already multiple nodes with the same value.
 127                          Add the new_node to it.  */
 128                       return gl_oset_nx_add (nodes, new_node);
 129                     }
 130                 }
 131               else
 132                 {
 133                   /* An entry representing a single node.  */
 134                   gl_list_node_t node = (struct gl_list_node_impl *) entry;
 135                   if (equals != NULL ? equals (value, node->value) : value == node->value)
 136                     {
 137                       /* Found already a node with the same value.  Turn it
 138                          into an ordered set, and add new_node to it.  */
 139                       gl_oset_t nodes;
 140                       struct gl_multiple_nodes *multi_entry;
 141
 142                       nodes =
 143                         gl_oset_nx_create_empty (OSET_TREE_FLAVOR,
 144                                                  compare_by_position, NULL);
 145                       if (nodes == NULL)
 146                         return -1;
 147
 148                       if (gl_oset_nx_add (nodes, node) < 0)
 149                         goto fail;
 150                       if (gl_oset_nx_add (nodes, new_node) < 0)
 151                         goto fail;
 152
 153                       multi_entry =
 154                        (struct gl_multiple_nodes *) malloc (sizeof (struct gl_multiple_nodes));
 155                       if (multi_entry == NULL)
 156                         goto fail;
 157                       multi_entry->h.hash_next = entry->hash_next;
 158                       multi_entry->h.hashcode = entry->hashcode;
 159                       multi_entry->magic = MULTIPLE_NODES_MAGIC;
 160                       multi_entry->nodes = nodes;
 161                       *entryp = &multi_entry->h;
 162                       return 0;
 163
 164                     fail:
 165                       gl_oset_free (nodes);
 166                       return -1;
 167                     }
 168                 }
 169             }
 170         }
 171     }
 172   /* If no duplicates are allowed, multiple nodes are not needed.  */
 173   new_node->h.hash_next = list->table[bucket];
 174   list->table[bucket] = &new_node->h;
 175   return 0;
 176 }
 177 /* Tell GCC that the likely return value is 0.  */
 178 #define add_to_bucket(list,node) \
 179     __builtin_expect ((add_to_bucket) (list, node), 0)
 180
 181 /* Remove a node from the hash table structure.
 182    If duplicates are allowed, this function performs in average time
 183    O((log n)^2): gl_oset_remove may need to remove an element from an ordered
 184    set of size O(n), needing O(log n) comparison function calls.  The
 185    comparison function is compare_by_position, which is O(log n) worst-case.
 186    If duplicates are forbidden, this function is O(1) on average.  */
 187 static void
 188 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
 189 {
 190   size_t bucket = old_node->h.hashcode % list->table_size;
 191
 192   if (list->base.allow_duplicates)
 193     {
 194       size_t hashcode = old_node->h.hashcode;
 195       const void *value = old_node->value;
 196       gl_listelement_equals_fn equals = list->base.equals_fn;
 197       gl_hash_entry_t *entryp;
 198
 199       for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
 200         {
 201           gl_hash_entry_t entry = *entryp;
 202
 203           if (entry == &old_node->h)
 204             {
 205               /* Found old_node as a single node in the bucket.  Remove it.  */
 206               *entryp = old_node->h.hash_next;
 207               break;
 208             }
 209           if (entry == NULL)
 210             /* node is not in the right bucket.  Did the hash codes
 211                change inadvertently?  */
 212             abort ();
 213           if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
 214               && entry->hashcode == hashcode)
 215             {
 216               /* An entry representing multiple nodes.  */
 217               gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
 218               /* Only the first node is interesting.  */
 219               gl_list_node_t node = gl_oset_first (nodes);
 220               if (equals != NULL ? equals (value, node->value) : value == node->value)
 221                 {
 222                   /* Found multiple nodes with the same value.
 223                      old_node must be one of them.  Remove it.  */
 224                   if (!gl_oset_remove (nodes, old_node))
 225                     abort ();
 226                   if (gl_oset_size (nodes) == 1)
 227                     {
 228                       /* Replace a one-element set with a single node.  */
 229                       node = gl_oset_first (nodes);
 230                       node->h.hash_next = entry->hash_next;
 231                       *entryp = &node->h;
 232                       gl_oset_free (nodes);
 233                       free (entry);
 234                     }
 235                   break;
 236                 }
 237             }
 238         }
 239     }
 240   else
 241     {
 242       /* If no duplicates are allowed, multiple nodes are not needed.  */
 243       gl_hash_entry_t *entryp;
 244
 245       for (entryp = &list->table[bucket]; ; entryp = &(*entryp)->hash_next)
 246         {
 247           if (*entryp == &old_node->h)
 248             {
 249               *entryp = old_node->h.hash_next;
 250               break;
 251             }
 252           if (*entryp == NULL)
 253             /* node is not in the right bucket.  Did the hash codes
 254                change inadvertently?  */
 255             abort ();
 256         }
 257     }
 258 }
 259
 260 /* Build up the hash table during initialization: Store all the nodes of
 261    list->root in the hash table.
 262    Return 0 upon success, -1 upon out-of-memory.  */
 263 static int
 264 add_nodes_to_buckets (gl_list_t list)
 265 {
 266   /* Iterate across all nodes.  */
 267   gl_list_node_t node = list->root;
 268   iterstack_t stack;
 269   iterstack_item_t *stack_ptr = &stack[0];
 270
 271   for (;;)
 272     {
 273       /* Descend on left branch.  */
 274       for (;;)
 275         {
 276           if (node == NULL)
 277             break;
 278           stack_ptr->node = node;
 279           stack_ptr->rightp = false;
 280           node = node->left;
 281           stack_ptr++;
 282         }
 283       /* Climb up again.  */
 284       for (;;)
 285         {
 286           if (stack_ptr == &stack[0])
 287             goto done;
 288           stack_ptr--;
 289           if (!stack_ptr->rightp)
 290             break;
 291         }
 292       node = stack_ptr->node;
 293       /* Add the current node to the hash table.  */
 294       node->h.hashcode =
 295         (list->base.hashcode_fn != NULL
 296          ? list->base.hashcode_fn (node->value)
 297          : (size_t)(uintptr_t) node->value);
 298       if (add_to_bucket (list, node) < 0)
 299         goto fail;
 300       /* Descend on right branch.  */
 301       stack_ptr->rightp = true;
 302       node = node->right;
 303       stack_ptr++;
 304     }
 305  done:
 306   return 0;
 307
 308  fail:
 309   /* Undo everything.  */
 310   for (;;)
 311     {
 312       /* Descend on left branch.  */
 313       stack_ptr->rightp = false;
 314       node = node->left;
 315       stack_ptr++;
 316       /* Descend on right branch.  */
 317       for (;;)
 318         {
 319           if (node == NULL)
 320             break;
 321           stack_ptr->node = node;
 322           stack_ptr->rightp = true;
 323           node = node->right;
 324           stack_ptr++;
 325         }
 326       /* Climb up again.  */
 327       for (;;)
 328         {
 329           if (stack_ptr == &stack[0])
 330             goto fail_done;
 331           stack_ptr--;
 332           if (stack_ptr->rightp)
 333             break;
 334         }
 335       node = stack_ptr->node;
 336       /* Remove the current node from the hash table.  */
 337       remove_from_bucket (list, node);
 338     }
 339  fail_done:
 340   return -1;
 341 }
 342 /* Tell GCC that the likely return value is 0.  */
 343 #if __GNUC__ >= 3
 344 # define add_nodes_to_buckets(list) \
 345     __builtin_expect ((add_nodes_to_buckets) (list), 0)
 346 #endif