lib/gl_anytreehash_list2.h

   1 /* Sequential list data type implemented by a hash table with a binary tree.
   2    Copyright (C) 2006-2007, 2009-2024 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 static gl_list_node_t
  21 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
  22                         const void *elt)
  23 {
  24   if (!(start_index <= end_index
  25         && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
  26     /* Invalid arguments.  */
  27     abort ();
  28   {
  29     size_t hashcode =
  30       (list->base.hashcode_fn != NULL
  31        ? list->base.hashcode_fn (elt)
  32        : (size_t)(uintptr_t) elt);
  33     size_t bucket = hashcode % list->table_size;
  34     gl_listelement_equals_fn equals = list->base.equals_fn;
  35     gl_hash_entry_t entry;
  36
  37     if (list->base.allow_duplicates)
  38       {
  39         for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
  40           if (entry->hashcode == hashcode)
  41             {
  42               if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
  43                 {
  44                   /* An entry representing multiple nodes.  */
  45                   gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
  46                   /* The first node is interesting.  */
  47                   gl_list_node_t node = gl_oset_first (nodes);
  48                   if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  49                     {
  50                       /* All nodes in the entry are equal to the given ELT.  */
  51                       if (start_index == 0)
  52                         {
  53                           /* We have to return only the one at the minimal
  54                              position, and this is the first one in the ordered
  55                              set.  */
  56                           if (end_index == list->root->branch_size
  57                               || node_position (node) < end_index)
  58                             return node;
  59                         }
  60                       else
  61                         {
  62                           /* We have to return only the one at the minimal
  63                              position >= start_index.  */
  64                           const void *nodes_elt;
  65                           if (gl_oset_search_atleast (nodes,
  66                                                       compare_position_threshold,
  67                                                       (void *)(uintptr_t)start_index,
  68                                                       &nodes_elt))
  69                             {
  70                               node = (gl_list_node_t) nodes_elt;
  71                               if (end_index == list->root->branch_size
  72                                   || node_position (node) < end_index)
  73                                 return node;
  74                             }
  75                         }
  76                       break;
  77                     }
  78                 }
  79               else
  80                 {
  81                   /* An entry representing a single node.  */
  82                   gl_list_node_t node = (struct gl_list_node_impl *) entry;
  83                   if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  84                     {
  85                       bool position_in_bounds;
  86                       if (start_index == 0 && end_index == list->root->branch_size)
  87                         position_in_bounds = true;
  88                       else
  89                         {
  90                           size_t position = node_position (node);
  91                           position_in_bounds =
  92                             (position >= start_index && position < end_index);
  93                         }
  94                       if (position_in_bounds)
  95                         return node;
  96                       break;
  97                     }
  98                 }
  99             }
 100       }
 101     else
 102       {
 103         /* If no duplicates are allowed, multiple nodes are not needed.  */
 104         for (entry = list->table[bucket]; entry != NULL; entry = entry->hash_next)
 105           if (entry->hashcode == hashcode)
 106             {
 107               gl_list_node_t node = (struct gl_list_node_impl *) entry;
 108               if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 109                 {
 110                   bool position_in_bounds;
 111                   if (start_index == 0 && end_index == list->root->branch_size)
 112                     position_in_bounds = true;
 113                   else
 114                     {
 115                       size_t position = node_position (node);
 116                       position_in_bounds =
 117                         (position >= start_index && position < end_index);
 118                     }
 119                   if (position_in_bounds)
 120                     return node;
 121                   break;
 122                 }
 123             }
 124       }
 125
 126     return NULL;
 127   }
 128 }
 129
 130 static size_t
 131 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 132                          const void *elt)
 133 {
 134   gl_list_node_t node =
 135     gl_tree_search_from_to (list, start_index, end_index, elt);
 136
 137   if (node != NULL)
 138     return node_position (node);
 139   else
 140     return (size_t)(-1);
 141 }
 142
 143 static void
 144 gl_tree_list_free (gl_list_t list)
 145 {
 146   if (list->base.allow_duplicates)
 147     {
 148       /* Free the ordered sets in the hash buckets.  */
 149       size_t i;
 150
 151       for (i = list->table_size; i > 0; )
 152         {
 153           gl_hash_entry_t entry = list->table[--i];
 154
 155           while (entry != NULL)
 156             {
 157               gl_hash_entry_t next = entry->hash_next;
 158
 159               if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
 160                 {
 161                   gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
 162
 163                   gl_oset_free (nodes);
 164                   free (entry);
 165                 }
 166
 167               entry = next;
 168             }
 169         }
 170     }
 171
 172   /* Iterate across all elements in post-order.  */
 173   {
 174     gl_list_node_t node = list->root;
 175     iterstack_t stack;
 176     iterstack_item_t *stack_ptr = &stack[0];
 177
 178     for (;;)
 179       {
 180         /* Descend on left branch.  */
 181         for (;;)
 182           {
 183             if (node == NULL)
 184               break;
 185             stack_ptr->node = node;
 186             stack_ptr->rightp = false;
 187             node = node->left;
 188             stack_ptr++;
 189           }
 190         /* Climb up again.  */
 191         for (;;)
 192           {
 193             if (stack_ptr == &stack[0])
 194               goto done_iterate;
 195             stack_ptr--;
 196             node = stack_ptr->node;
 197             if (!stack_ptr->rightp)
 198               break;
 199             /* Free the current node.  */
 200             if (list->base.dispose_fn != NULL)
 201               list->base.dispose_fn (node->value);
 202             free (node);
 203           }
 204         /* Descend on right branch.  */
 205         stack_ptr->rightp = true;
 206         node = node->right;
 207         stack_ptr++;
 208       }
 209   }
 210  done_iterate:
 211   free (list->table);
 212   free (list);
 213 }