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