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 (gl_list_t list, const void *elt)
  23 {
  24   size_t hashcode =
  25     (list->base.hashcode_fn != NULL
  26      ? list->base.hashcode_fn (elt)
  27      : (size_t)(uintptr_t) elt);
  28   size_t index = hashcode % list->table_size;
  29   gl_listelement_equals_fn equals = list->base.equals_fn;
  30   gl_hash_entry_t entry;
  31
  32   if (list->base.allow_duplicates)
  33     {
  34       for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
  35         if (entry->hashcode == hashcode)
  36           {
  37             if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
  38               {
  39                 /* An entry representing multiple nodes.  */
  40                 gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
  41                 /* Only the first node is interesting.  */
  42                 gl_list_node_t node = gl_oset_first (nodes);
  43                 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  44                   /* All nodes in the entry are equal to the given ELT.
  45                      But we have to return only the one at the minimal position,
  46                      and this is the first one in the ordered set.  */
  47                   return node;
  48               }
  49             else
  50               {
  51                 /* An entry representing a single node.  */
  52                 gl_list_node_t node = (struct gl_list_node_impl *) entry;
  53                 if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  54                   return node;
  55               }
  56           }
  57     }
  58   else
  59     {
  60       /* If no duplicates are allowed, multiple nodes are not needed.  */
  61       for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
  62         if (entry->hashcode == hashcode)
  63           {
  64             gl_list_node_t node = (struct gl_list_node_impl *) entry;
  65             if (equals != NULL ? equals (elt, node->value) : elt == node->value)
  66               return node;
  67           }
  68     }
  69
  70   return NULL;
  71 }
  72
  73 static size_t
  74 gl_tree_indexof (gl_list_t list, const void *elt)
  75 {
  76   gl_list_node_t node = gl_tree_search (list, elt);
  77
  78   if (node != NULL)
  79     return node_position (node);
  80   else
  81     return (size_t)(-1);
  82 }
  83
  84 static void
  85 gl_tree_list_free (gl_list_t list)
  86 {
  87   if (list->base.allow_duplicates)
  88     {
  89       /* Free the ordered sets in the hash buckets.  */
  90       size_t i;
  91
  92       for (i = list->table_size; i > 0; )
  93         {
  94           gl_hash_entry_t entry = list->table[--i];
  95
  96           while (entry != NULL)
  97             {
  98               gl_hash_entry_t next = entry->hash_next;
  99
 100               if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
 101                 {
 102                   gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
 103
 104                   gl_oset_free (nodes);
 105                   free (entry);
 106                 }
 107
 108               entry = next;
 109             }
 110         }
 111     }
 112
 113   /* Iterate across all elements in post-order.  */
 114   {
 115     gl_list_node_t node = list->root;
 116     iterstack_t stack;
 117     iterstack_item_t *stack_ptr = &stack[0];
 118
 119     for (;;)
 120       {
 121         /* Descend on left branch.  */
 122         for (;;)
 123           {
 124             if (node == NULL)
 125               break;
 126             stack_ptr->node = node;
 127             stack_ptr->rightp = false;
 128             node = node->left;
 129             stack_ptr++;
 130           }
 131         /* Climb up again.  */
 132         for (;;)
 133           {
 134             if (stack_ptr == &stack[0])
 135               goto done_iterate;
 136             stack_ptr--;
 137             node = stack_ptr->node;
 138             if (!stack_ptr->rightp)
 139               break;
 140             /* Free the current node.  */
 141             free (node);
 142           }
 143         /* Descend on right branch.  */
 144         stack_ptr->rightp = true;
 145         node = node->right;
 146         stack_ptr++;
 147       }
 148   }
 149  done_iterate:
 150   free (list->table);
 151   free (list);
 152 }