lib/gl_anytreehash_list1.h

   1 /* Sequential list data type implemented by a hash table with a binary tree.
   2    Copyright (C) 2006 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 2, or (at your option)
   8    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, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c.  */
  20
  21 /* Hash table entry representing the same value at more than one position.  */
  22 struct gl_multiple_nodes
  23 {
  24   struct gl_hash_entry h;           /* hash table entry fields; must be first */
  25   void *magic;                      /* used to distinguish from single node */
  26   gl_oset_t nodes;                  /* set of nodes, sorted by position */
  27 };
  28 /* A value that cannot occur at the corresponding field (->left) in
  29    gl_list_node_impl.  */
  30 #define MULTIPLE_NODES_MAGIC  (void *) -1
  31
  32 /* Resize the hash table if needed, after list->count was incremented.  */
  33 static inline void
  34 hash_resize_after_add (gl_list_t list)
  35 {
  36   size_t count = (list->root != 0 ? list->root->branch_size : 0);
  37   size_t estimate = xsum (count, count / 2); /* 1.5 * count */
  38   if (estimate > list->table_size)
  39     hash_resize (list, estimate);
  40 }
  41
  42 /* Return the position of the given node in the tree.  */
  43 static size_t
  44 node_position (gl_list_node_t node)
  45 {
  46   size_t position = 0;
  47
  48   if (node->left != NULL)
  49     position += node->left->branch_size;
  50   for (;;)
  51     {
  52       gl_list_node_t parent = node->parent;
  53
  54       if (parent == NULL)
  55         return position;
  56       /* position is now relative to the subtree of node.  */
  57       if (parent->right == node)
  58         {
  59           position += 1;
  60           if (parent->left != NULL)
  61             position += parent->left->branch_size;
  62         }
  63       /* position is now relative to the subtree of parent.  */
  64       node = parent;
  65     }
  66 }
  67
  68 /* Compares two nodes by their position in the tree.  */
  69 static int
  70 compare_by_position (const void *x1, const void *x2)
  71 {
  72   gl_list_node_t node1 = (gl_list_node_t) x1;
  73   gl_list_node_t node2 = (gl_list_node_t) x2;
  74   size_t position1 = node_position (node1);
  75   size_t position2 = node_position (node2);
  76
  77   return (position1 > position2 ? 1 :
  78           position1 < position2 ? -1 : 0);
  79 }
  80
  81 /* Compares a node's position in the tree with a given threshold.  */
  82 static bool
  83 compare_position_threshold (const void *x, const void *threshold)
  84 {
  85   gl_list_node_t node = (gl_list_node_t) x;
  86   size_t position = node_position (node);
  87   return (position >= (uintptr_t)threshold);
  88 }
  89
  90 /* Return the first element of a non-empty ordered set of nodes.  */
  91 static inline gl_list_node_t
  92 gl_oset_first (gl_oset_t set)
  93 {
  94   gl_oset_iterator_t iter = gl_oset_iterator (set);
  95   const void *first;
  96
  97   if (!gl_oset_iterator_next (&iter, &first))
  98     abort ();
  99   gl_oset_iterator_free (&iter);
 100   return (gl_list_node_t) first;
 101 }
 102
 103 /* Add a node to the hash table structure.
 104    If duplicates are allowed, this function performs in average time
 105    O((log n)^2): gl_oset_add may need to add an element to an ordered set of
 106    size O(n), needing O(log n) comparison function calls.  The comparison
 107    function is compare_by_position, which is O(log n) worst-case.
 108    If duplicates are forbidden, this function is O(1).  */
 109 static void
 110 add_to_bucket (gl_list_t list, gl_list_node_t new_node)
 111 {
 112   size_t index = 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[index]; *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                       gl_oset_add (nodes, new_node);
 139                       return;
 140                     }
 141                 }
 142               else
 143                 {
 144                   /* An entry representing a single node.  */
 145                   gl_list_node_t node = (struct gl_list_node_impl *) entry;
 146                   if (equals != NULL ? equals (value, node->value) : value == node->value)
 147                     {
 148                       /* Found already a node with the same value.  Turn it
 149                          into an ordered set, and add new_node to it.  */
 150                       gl_oset_t nodes;
 151                       struct gl_multiple_nodes *multi_entry;
 152
 153                       nodes =
 154                         gl_oset_create_empty (OSET_TREE_FLAVOR,
 155                                               compare_by_position);
 156
 157                       gl_oset_add (nodes, node);
 158                       gl_oset_add (nodes, new_node);
 159
 160                       multi_entry =
 161                         (struct gl_multiple_nodes *) xmalloc (sizeof (struct gl_multiple_nodes));
 162                       multi_entry->h.hash_next = entry->hash_next;
 163                       multi_entry->h.hashcode = entry->hashcode;
 164                       multi_entry->magic = MULTIPLE_NODES_MAGIC;
 165                       multi_entry->nodes = nodes;
 166                       *entryp = &multi_entry->h;
 167                       return;
 168                     }
 169                 }
 170             }
 171         }
 172     }
 173   /* If no duplicates are allowed, multiple nodes are not needed.  */
 174   new_node->h.hash_next = list->table[index];
 175   list->table[index] = &new_node->h;
 176 }
 177
 178 /* Remove a node from the hash table structure.
 179    If duplicates are allowed, this function performs in average time
 180    O((log n)^2): gl_oset_remove may need to remove an element from an ordered
 181    set of size O(n), needing O(log n) comparison function calls.  The
 182    comparison function is compare_by_position, which is O(log n) worst-case.
 183    If duplicates are forbidden, this function is O(1) on average.  */
 184 static void
 185 remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
 186 {
 187   size_t index = old_node->h.hashcode % list->table_size;
 188
 189   if (list->base.allow_duplicates)
 190     {
 191       size_t hashcode = old_node->h.hashcode;
 192       const void *value = old_node->value;
 193       gl_listelement_equals_fn equals = list->base.equals_fn;
 194       gl_hash_entry_t *entryp;
 195
 196       for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
 197         {
 198           gl_hash_entry_t entry = *entryp;
 199
 200           if (entry == &old_node->h)
 201             {
 202               /* Found old_node as a single node in the bucket.  Remove it.  */
 203               *entryp = old_node->h.hash_next;
 204               break;
 205             }
 206           if (entry == NULL)
 207             /* node is not in the right bucket.  Did the hash codes
 208                change inadvertently?  */
 209             abort ();
 210           if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
 211               && entry->hashcode == hashcode)
 212             {
 213               /* An entry representing multiple nodes.  */
 214               gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
 215               /* Only the first node is interesting.  */
 216               gl_list_node_t node = gl_oset_first (nodes);
 217               if (equals != NULL ? equals (value, node->value) : value == node->value)
 218                 {
 219                   /* Found multiple nodes with the same value.
 220                      old_node must be one of them.  Remove it.  */
 221                   if (!gl_oset_remove (nodes, old_node))
 222                     abort ();
 223                   if (gl_oset_size (nodes) == 1)
 224                     {
 225                       /* Replace a one-element set with a single node.  */
 226                       node = gl_oset_first (nodes);
 227                       node->h.hash_next = entry->hash_next;
 228                       *entryp = &node->h;
 229                       gl_oset_free (nodes);
 230                       free (entry);
 231                     }
 232                   break;
 233                 }
 234             }
 235         }
 236     }
 237   else
 238     {
 239       /* If no duplicates are allowed, multiple nodes are not needed.  */
 240       gl_hash_entry_t *entryp;
 241
 242       for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
 243         {
 244           if (*entryp == &old_node->h)
 245             {
 246               *entryp = old_node->h.hash_next;
 247               break;
 248             }
 249           if (*entryp == NULL)
 250             /* node is not in the right bucket.  Did the hash codes
 251                change inadvertently?  */
 252             abort ();
 253         }
 254     }
 255 }
 256
 257 /* Build up the hash table during initialization: Store all the nodes of
 258    list->root in the hash table.  */
 259 static inline void
 260 add_nodes_to_buckets (gl_list_t list)
 261 {
 262   /* Iterate across all nodes.  */
 263   gl_list_node_t node = list->root;
 264   iterstack_t stack;
 265   iterstack_item_t *stack_ptr = &stack[0];
 266
 267   for (;;)
 268     {
 269       /* Descend on left branch.  */
 270       for (;;)
 271         {
 272           if (node == NULL)
 273             break;
 274           stack_ptr->node = node;
 275           stack_ptr->rightp = false;
 276           node = node->left;
 277           stack_ptr++;
 278         }
 279       /* Climb up again.  */
 280       for (;;)
 281         {
 282           if (stack_ptr == &stack[0])
 283             return;
 284           stack_ptr--;
 285           if (!stack_ptr->rightp)
 286             break;
 287         }
 288       node = stack_ptr->node;
 289       /* Add the current node to the hash table.  */
 290       node->h.hashcode =
 291         (list->base.hashcode_fn != NULL
 292          ? list->base.hashcode_fn (node->value)
 293          : (size_t)(uintptr_t) node->value);
 294       add_to_bucket (list, node);
 295       /* Descend on right branch.  */
 296       stack_ptr->rightp = true;
 297       node = node->right;
 298       stack_ptr++;
 299     }
 300 }