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