lib/gl_anytree_oset.h

   1 /* Ordered set data type implemented by a binary tree.
   2    Copyright (C) 2006-2007, 2009-2021 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_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 _GL_ATTRIBUTE_PURE
  51 gl_tree_size (gl_oset_t set)
  52 {
  53   return set->count;
  54 }
  55
  56 /* Returns the next node in the tree, or NULL if there is none.  */
  57 static inline gl_oset_node_t _GL_ATTRIBUTE_PURE
  58 gl_tree_next_node (gl_oset_node_t node)
  59 {
  60   if (node->right != NULL)
  61     {
  62       node = node->right;
  63       while (node->left != NULL)
  64         node = node->left;
  65     }
  66   else
  67     {
  68       while (node->parent != NULL && node->parent->right == node)
  69         node = node->parent;
  70       node = node->parent;
  71     }
  72   return node;
  73 }
  74
  75 /* Returns the previous node in the tree, or NULL if there is none.  */
  76 static inline gl_oset_node_t _GL_ATTRIBUTE_PURE
  77 gl_tree_prev_node (gl_oset_node_t node)
  78 {
  79   if (node->left != NULL)
  80     {
  81       node = node->left;
  82       while (node->right != NULL)
  83         node = node->right;
  84     }
  85   else
  86     {
  87       while (node->parent != NULL && node->parent->left == node)
  88         node = node->parent;
  89       node = node->parent;
  90     }
  91   return node;
  92 }
  93
  94 static bool
  95 gl_tree_search (gl_oset_t set, const void *elt)
  96 {
  97   gl_setelement_compar_fn compar = set->base.compar_fn;
  98   gl_oset_node_t node;
  99
 100   for (node = set->root; node != NULL; )
 101     {
 102       int cmp = (compar != NULL
 103                  ? compar (node->value, elt)
 104                  : (node->value > elt ? 1 :
 105                     node->value < elt ? -1 : 0));
 106
 107       if (cmp < 0)
 108         node = node->right;
 109       else if (cmp > 0)
 110         node = node->left;
 111       else /* cmp == 0 */
 112         /* We have an element equal to ELT.  */
 113         return true;
 114     }
 115   return false;
 116 }
 117
 118 static bool
 119 gl_tree_search_atleast (gl_oset_t set,
 120                         gl_setelement_threshold_fn threshold_fn,
 121                         const void *threshold,
 122                         const void **eltp)
 123 {
 124   gl_oset_node_t node;
 125
 126   for (node = set->root; node != NULL; )
 127     {
 128       if (! threshold_fn (node->value, threshold))
 129         node = node->right;
 130       else
 131         {
 132           /* We have an element >= THRESHOLD.  But we need the leftmost such
 133              element.  */
 134           gl_oset_node_t found = node;
 135           node = node->left;
 136           for (; node != NULL; )
 137             {
 138               if (! threshold_fn (node->value, threshold))
 139                 node = node->right;
 140               else
 141                 {
 142                   found = node;
 143                   node = node->left;
 144                 }
 145             }
 146           *eltp = found->value;
 147           return true;
 148         }
 149     }
 150   return false;
 151 }
 152
 153 static gl_oset_node_t
 154 gl_tree_search_node (gl_oset_t set, const void *elt)
 155 {
 156   gl_setelement_compar_fn compar = set->base.compar_fn;
 157   gl_oset_node_t node;
 158
 159   for (node = set->root; node != NULL; )
 160     {
 161       int cmp = (compar != NULL
 162                  ? compar (node->value, elt)
 163                  : (node->value > elt ? 1 :
 164                     node->value < elt ? -1 : 0));
 165
 166       if (cmp < 0)
 167         node = node->right;
 168       else if (cmp > 0)
 169         node = node->left;
 170       else /* cmp == 0 */
 171         /* We have an element equal to ELT.  */
 172         return node;
 173     }
 174   return NULL;
 175 }
 176
 177 static int
 178 gl_tree_nx_add (gl_oset_t set, const void *elt)
 179 {
 180   gl_setelement_compar_fn compar;
 181   gl_oset_node_t node = set->root;
 182
 183   if (node == NULL)
 184     {
 185       if (gl_tree_nx_add_first (set, elt) == NULL)
 186         return -1;
 187       return true;
 188     }
 189
 190   compar = set->base.compar_fn;
 191
 192   for (;;)
 193     {
 194       int cmp = (compar != NULL
 195                  ? compar (node->value, elt)
 196                  : (node->value > elt ? 1 :
 197                     node->value < elt ? -1 : 0));
 198
 199       if (cmp < 0)
 200         {
 201           if (node->right == NULL)
 202             {
 203               if (gl_tree_nx_add_after (set, node, elt) == NULL)
 204                 return -1;
 205               return true;
 206             }
 207           node = node->right;
 208         }
 209       else if (cmp > 0)
 210         {
 211           if (node->left == NULL)
 212             {
 213               if (gl_tree_nx_add_before (set, node, elt) == NULL)
 214                 return -1;
 215               return true;
 216             }
 217           node = node->left;
 218         }
 219       else /* cmp == 0 */
 220         return false;
 221     }
 222 }
 223
 224 static bool
 225 gl_tree_remove (gl_oset_t set, const void *elt)
 226 {
 227   gl_oset_node_t node = gl_tree_search_node (set, elt);
 228
 229   if (node != NULL)
 230     return gl_tree_remove_node (set, node);
 231   else
 232     return false;
 233 }
 234
 235 static int
 236 gl_tree_update (gl_oset_t set, const void *elt,
 237                 void (*action) (const void * /*elt*/, void * /*action_data*/),
 238                 void *action_data)
 239 {
 240   /* Like gl_tree_remove, action (...), gl_tree_nx_add, except that we don't
 241      actually remove ELT.  */
 242   /* Remember the old node.  Don't free it.  */
 243   gl_oset_node_t old_node = gl_tree_search_node (set, elt);
 244   /* Invoke ACTION.  */
 245   action (elt, action_data);
 246   /* Determine where to put the node now.  */
 247   if (old_node != NULL)
 248     {
 249       if (set->count > 1)
 250         {
 251           gl_setelement_compar_fn compar = set->base.compar_fn;
 252
 253           gl_oset_node_t prev_node = gl_tree_prev_node (old_node);
 254           gl_oset_node_t next_node = gl_tree_next_node (old_node);
 255           if (!(compar != NULL
 256                 ? (prev_node == NULL || compar (prev_node->value, elt) < 0)
 257                   && (next_node == NULL || compar (next_node->value, elt) > 0)
 258                 : (prev_node == NULL || prev_node->value < elt)
 259                   && (next_node == NULL || next_node->value > elt)))
 260             {
 261               /* old_node needs to move in the tree.  */
 262               gl_oset_node_t node;
 263
 264               /* Remove the node from the tree.  Don't free it.  */
 265               gl_tree_remove_node_no_free (set, old_node);
 266
 267               node = set->root;
 268
 269               for (;;)
 270                 {
 271                   int cmp = (compar != NULL
 272                              ? compar (node->value, elt)
 273                              : (node->value > elt ? 1 :
 274                                 node->value < elt ? -1 : 0));
 275
 276                   if (cmp < 0)
 277                     {
 278                       if (node->right == NULL)
 279                         {
 280                           gl_tree_add_node_after (set, node, old_node);
 281                           return true;
 282                         }
 283                       node = node->right;
 284                     }
 285                   else if (cmp > 0)
 286                     {
 287                       if (node->left == NULL)
 288                         {
 289                           gl_tree_add_node_before (set, node, old_node);
 290                           return true;
 291                         }
 292                       node = node->left;
 293                     }
 294                   else /* cmp == 0 */
 295                     {
 296                       /* Two elements are the same.  */
 297                       NODE_PAYLOAD_DISPOSE (set, old_node)
 298                       free (old_node);
 299                       return -1;
 300                     }
 301                 }
 302             }
 303         }
 304     }
 305   return 0;
 306 }
 307
 308 static void
 309 gl_tree_oset_free (gl_oset_t set)
 310 {
 311   /* Iterate across all elements in post-order.  */
 312   gl_oset_node_t node = set->root;
 313   iterstack_t stack;
 314   iterstack_item_t *stack_ptr = &stack[0];
 315
 316   for (;;)
 317     {
 318       /* Descend on left branch.  */
 319       for (;;)
 320         {
 321           if (node == NULL)
 322             break;
 323           stack_ptr->node = node;
 324           stack_ptr->rightp = false;
 325           node = node->left;
 326           stack_ptr++;
 327         }
 328       /* Climb up again.  */
 329       for (;;)
 330         {
 331           if (stack_ptr == &stack[0])
 332             goto done_iterate;
 333           stack_ptr--;
 334           node = stack_ptr->node;
 335           if (!stack_ptr->rightp)
 336             break;
 337           /* Free the current node.  */
 338           if (set->base.dispose_fn != NULL)
 339             set->base.dispose_fn (node->value);
 340           free (node);
 341         }
 342       /* Descend on right branch.  */
 343       stack_ptr->rightp = true;
 344       node = node->right;
 345       stack_ptr++;
 346     }
 347  done_iterate:
 348   free (set);
 349 }
 350
 351 /* --------------------- gl_oset_iterator_t Data Type --------------------- */
 352
 353 static gl_oset_iterator_t _GL_ATTRIBUTE_PURE
 354 gl_tree_iterator (gl_oset_t set)
 355 {
 356   gl_oset_iterator_t result;
 357   gl_oset_node_t node;
 358
 359   result.vtable = set->base.vtable;
 360   result.set = set;
 361   /* Start node is the leftmost node.  */
 362   node = set->root;
 363   if (node != NULL)
 364     while (node->left != NULL)
 365       node = node->left;
 366   result.p = node;
 367   /* End point is past the rightmost node.  */
 368   result.q = NULL;
 369 #if defined GCC_LINT || defined lint
 370   result.i = 0;
 371   result.j = 0;
 372   result.count = 0;
 373 #endif
 374
 375   return result;
 376 }
 377
 378 static gl_oset_iterator_t
 379 gl_tree_iterator_atleast (gl_oset_t set,
 380                           gl_setelement_threshold_fn threshold_fn,
 381                           const void *threshold)
 382 {
 383   gl_oset_iterator_t result;
 384   gl_oset_node_t node;
 385
 386   result.vtable = set->base.vtable;
 387   result.set = set;
 388   /* End point is past the rightmost node.  */
 389   result.q = NULL;
 390 #if defined GCC_LINT || defined lint
 391   result.i = 0;
 392   result.j = 0;
 393   result.count = 0;
 394 #endif
 395
 396   for (node = set->root; node != NULL; )
 397     {
 398       if (! threshold_fn (node->value, threshold))
 399         node = node->right;
 400       else
 401         {
 402           /* We have an element >= THRESHOLD.  But we need the leftmost such
 403              element.  */
 404           gl_oset_node_t found = node;
 405           node = node->left;
 406           for (; node != NULL; )
 407             {
 408               if (! threshold_fn (node->value, threshold))
 409                 node = node->right;
 410               else
 411                 {
 412                   found = node;
 413                   node = node->left;
 414                 }
 415             }
 416           result.p = found;
 417           return result;
 418         }
 419     }
 420   result.p = NULL;
 421   return result;
 422 }
 423
 424 static bool
 425 gl_tree_iterator_next (gl_oset_iterator_t *iterator, const void **eltp)
 426 {
 427   if (iterator->p != iterator->q)
 428     {
 429       gl_oset_node_t node = (gl_oset_node_t) iterator->p;
 430       *eltp = node->value;
 431       /* Advance to the next node.  */
 432       node = gl_tree_next_node (node);
 433       iterator->p = node;
 434       return true;
 435     }
 436   else
 437     return false;
 438 }
 439
 440 static void
 441 gl_tree_iterator_free (gl_oset_iterator_t *iterator _GL_ATTRIBUTE_MAYBE_UNUSED)
 442 {
 443 }