lib/gl_anytree_oset.h

   1 /* Ordered set data type implemented by 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_avltree_oset.c and gl_rbtree_oset.c.  */
  19
  20 /* An item on the stack used for iterating across the elements.  */
  21 typedef struct
  22 {
  23   gl_oset_node_t node;
  24   bool rightp;
  25 } iterstack_item_t;
  26
  27 /* A stack used for iterating across the elements.  */
  28 typedef iterstack_item_t iterstack_t[MAXHEIGHT];
  29
  30 static gl_oset_t
  31 gl_tree_nx_create_empty (gl_oset_implementation_t implementation,
  32                          gl_setelement_compar_fn compar_fn,
  33                          gl_setelement_dispose_fn dispose_fn)
  34 {
  35   struct gl_oset_impl *set =
  36     (struct gl_oset_impl *) malloc (sizeof (struct gl_oset_impl));
  37
  38   if (set == NULL)
  39     return NULL;
  40
  41   set->base.vtable = implementation;
  42   set->base.compar_fn = compar_fn;
  43   set->base.dispose_fn = dispose_fn;
  44   set->root = NULL;
  45   set->count = 0;
  46
  47   return set;
  48 }
  49
  50 static size_t
  51 gl_tree_size (gl_oset_t set)
  52 {
  53   return set->count;
  54 }
  55
  56 static bool
  57 gl_tree_search (gl_oset_t set, const void *elt)
  58 {
  59   gl_setelement_compar_fn compar = set->base.compar_fn;
  60   gl_oset_node_t node;
  61
  62   for (node = set->root; node != NULL; )
  63     {
  64       int cmp = (compar != NULL
  65                  ? compar (node->value, elt)
  66                  : (node->value > elt ? 1 :
  67                     node->value < elt ? -1 : 0));
  68
  69       if (cmp < 0)
  70         node = node->right;
  71       else if (cmp > 0)
  72         node = node->left;
  73       else /* cmp == 0 */
  74         /* We have an element equal to ELT.  */
  75         return true;
  76     }
  77   return false;
  78 }
  79
  80 static bool
  81 gl_tree_search_atleast (gl_oset_t set,
  82                         gl_setelement_threshold_fn threshold_fn,
  83                         const void *threshold,
  84                         const void **eltp)
  85 {
  86   gl_oset_node_t node;
  87
  88   for (node = set->root; node != NULL; )
  89     {
  90       if (! threshold_fn (node->value, threshold))
  91         node = node->right;
  92       else
  93         {
  94           /* We have an element >= VALUE.  But we need the leftmost such
  95              element.  */
  96           gl_oset_node_t found = node;
  97           node = node->left;
  98           for (; node != NULL; )
  99             {
 100               if (! threshold_fn (node->value, threshold))
 101                 node = node->right;
 102               else
 103                 {
 104                   found = node;
 105                   node = node->left;
 106                 }
 107             }
 108           *eltp = found->value;
 109           return true;
 110         }
 111     }
 112   return false;
 113 }
 114
 115 static gl_oset_node_t
 116 gl_tree_search_node (gl_oset_t set, const void *elt)
 117 {
 118   gl_setelement_compar_fn compar = set->base.compar_fn;
 119   gl_oset_node_t node;
 120
 121   for (node = set->root; node != NULL; )
 122     {
 123       int cmp = (compar != NULL
 124                  ? compar (node->value, elt)
 125                  : (node->value > elt ? 1 :
 126                     node->value < elt ? -1 : 0));
 127
 128       if (cmp < 0)
 129         node = node->right;
 130       else if (cmp > 0)
 131         node = node->left;
 132       else /* cmp == 0 */
 133         /* We have an element equal to ELT.  */
 134         return node;
 135     }
 136   return NULL;
 137 }
 138
 139 static int
 140 gl_tree_nx_add (gl_oset_t set, const void *elt)
 141 {
 142   gl_setelement_compar_fn compar;
 143   gl_oset_node_t node = set->root;
 144
 145   if (node == NULL)
 146     {
 147       if (gl_tree_nx_add_first (set, elt) == NULL)
 148         return -1;
 149       return true;
 150     }
 151
 152   compar = set->base.compar_fn;
 153
 154   for (;;)
 155     {
 156       int cmp = (compar != NULL
 157                  ? compar (node->value, elt)
 158                  : (node->value > elt ? 1 :
 159                     node->value < elt ? -1 : 0));
 160
 161       if (cmp < 0)
 162         {
 163           if (node->right == NULL)
 164             {
 165               if (gl_tree_nx_add_after (set, node, elt) == NULL)
 166                 return -1;
 167               return true;
 168             }
 169           node = node->right;
 170         }
 171       else if (cmp > 0)
 172         {
 173           if (node->left == NULL)
 174             {
 175               if (gl_tree_nx_add_before (set, node, elt) == NULL)
 176                 return -1;
 177               return true;
 178             }
 179           node = node->left;
 180         }
 181       else /* cmp == 0 */
 182         return false;
 183     }
 184 }
 185
 186 static bool
 187 gl_tree_remove (gl_oset_t set, const void *elt)
 188 {
 189   gl_oset_node_t node = gl_tree_search_node (set, elt);
 190
 191   if (node != NULL)
 192     return gl_tree_remove_node (set, node);
 193   else
 194     return false;
 195 }
 196
 197 static void
 198 gl_tree_oset_free (gl_oset_t set)
 199 {
 200   /* Iterate across all elements in post-order.  */
 201   gl_oset_node_t node = set->root;
 202   iterstack_t stack;
 203   iterstack_item_t *stack_ptr = &stack[0];
 204
 205   for (;;)
 206     {
 207       /* Descend on left branch.  */
 208       for (;;)
 209         {
 210           if (node == NULL)
 211             break;
 212           stack_ptr->node = node;
 213           stack_ptr->rightp = false;
 214           node = node->left;
 215           stack_ptr++;
 216         }
 217       /* Climb up again.  */
 218       for (;;)
 219         {
 220           if (stack_ptr == &stack[0])
 221             goto done_iterate;
 222           stack_ptr--;
 223           node = stack_ptr->node;
 224           if (!stack_ptr->rightp)
 225             break;
 226           /* Free the current node.  */
 227           if (set->base.dispose_fn != NULL)
 228             set->base.dispose_fn (node->value);
 229           free (node);
 230         }
 231       /* Descend on right branch.  */
 232       stack_ptr->rightp = true;
 233       node = node->right;
 234       stack_ptr++;
 235     }
 236  done_iterate:
 237   free (set);
 238 }
 239
 240 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 241
 242 static gl_oset_iterator_t
 243 gl_tree_iterator (gl_oset_t set)
 244 {
 245   gl_oset_iterator_t result;
 246   gl_oset_node_t node;
 247
 248   result.vtable = set->base.vtable;
 249   result.set = set;
 250   /* Start node is the leftmost node.  */
 251   node = set->root;
 252   if (node != NULL)
 253     while (node->left != NULL)
 254       node = node->left;
 255   result.p = node;
 256   /* End point is past the rightmost node.  */
 257   result.q = NULL;
 258 #ifdef lint
 259   result.i = 0;
 260   result.j = 0;
 261   result.count = 0;
 262 #endif
 263
 264   return result;
 265 }
 266
 267 static bool
 268 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 269 {
 270   if (iterator->p != iterator->q)
 271     {
 272       gl_oset_node_t node = (gl_oset_node_t) iterator->p;
 273       *eltp = node->value;
 274       /* Advance to the next node.  */
 275       if (node->right != NULL)
 276         {
 277           node = node->right;
 278           while (node->left != NULL)
 279             node = node->left;
 280         }
 281       else
 282         {
 283           while (node->parent != NULL && node->parent->right == node)
 284             node = node->parent;
 285           node = node->parent;
 286         }
 287       iterator->p = node;
 288       return true;
 289     }
 290   else
 291     return false;
 292 }
 293
 294 static void
 295 gl_tree_iterator_free (gl_oset_iterator_t *iterator)
 296 {
 297 }