lib/gl_anytree_list2.h

   1 /* Sequential list data type implemented by a binary tree.
   2    Copyright (C) 2006-2007 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_list.c, gl_rbtree_list.c,
  19                   gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
  20
  21 static gl_list_t
  22 gl_tree_create_empty (gl_list_implementation_t implementation,
  23                       gl_listelement_equals_fn equals_fn,
  24                       gl_listelement_hashcode_fn hashcode_fn,
  25                       gl_listelement_dispose_fn dispose_fn,
  26                       bool allow_duplicates)
  27 {
  28   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  29
  30   list->base.vtable = implementation;
  31   list->base.equals_fn = equals_fn;
  32   list->base.hashcode_fn = hashcode_fn;
  33   list->base.dispose_fn = dispose_fn;
  34   list->base.allow_duplicates = allow_duplicates;
  35 #if WITH_HASHTABLE
  36   list->table_size = 11;
  37   list->table = XCALLOC (list->table_size, gl_hash_entry_t);
  38 #endif
  39   list->root = NULL;
  40
  41   return list;
  42 }
  43
  44 static size_t
  45 gl_tree_size (gl_list_t list)
  46 {
  47   return (list->root != NULL ? list->root->branch_size : 0);
  48 }
  49
  50 static const void *
  51 gl_tree_node_value (gl_list_t list, gl_list_node_t node)
  52 {
  53   return node->value;
  54 }
  55
  56 static gl_list_node_t
  57 gl_tree_next_node (gl_list_t list, gl_list_node_t node)
  58 {
  59   if (node->right != NULL)
  60     {
  61       node = node->right;
  62       while (node->left != NULL)
  63         node = node->left;
  64     }
  65   else
  66     {
  67       while (node->parent != NULL && node->parent->right == node)
  68         node = node->parent;
  69       node = node->parent;
  70     }
  71   return node;
  72 }
  73
  74 static gl_list_node_t
  75 gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
  76 {
  77   if (node->left != NULL)
  78     {
  79       node = node->left;
  80       while (node->right != NULL)
  81         node = node->right;
  82     }
  83   else
  84     {
  85       while (node->parent != NULL && node->parent->left == node)
  86         node = node->parent;
  87       node = node->parent;
  88     }
  89   return node;
  90 }
  91
  92 /* Return the node at the given position < gl_tree_size (list).  */
  93 static inline gl_list_node_t
  94 node_at (gl_list_node_t root, size_t position)
  95 {
  96   /* Here we know that root != NULL.  */
  97   gl_list_node_t node = root;
  98
  99   for (;;)
 100     {
 101       if (node->left != NULL)
 102         {
 103           if (position < node->left->branch_size)
 104             {
 105               node = node->left;
 106               continue;
 107             }
 108           position -= node->left->branch_size;
 109         }
 110       if (position == 0)
 111         break;
 112       position--;
 113       node = node->right;
 114     }
 115   return node;
 116 }
 117
 118 static const void *
 119 gl_tree_get_at (gl_list_t list, size_t position)
 120 {
 121   gl_list_node_t node = list->root;
 122
 123   if (!(node != NULL && position < node->branch_size))
 124     /* Invalid argument.  */
 125     abort ();
 126   node = node_at (node, position);
 127   return node->value;
 128 }
 129
 130 static gl_list_node_t
 131 gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
 132 {
 133   gl_list_node_t node = list->root;
 134
 135   if (!(node != NULL && position < node->branch_size))
 136     /* Invalid argument.  */
 137     abort ();
 138   node = node_at (node, position);
 139 #if WITH_HASHTABLE
 140   if (elt != node->value)
 141     {
 142       size_t new_hashcode =
 143         (list->base.hashcode_fn != NULL
 144          ? list->base.hashcode_fn (elt)
 145          : (size_t)(uintptr_t) elt);
 146
 147       if (new_hashcode != node->h.hashcode)
 148         {
 149           remove_from_bucket (list, node);
 150           node->value = elt;
 151           node->h.hashcode = new_hashcode;
 152           add_to_bucket (list, node);
 153         }
 154       else
 155         node->value = elt;
 156     }
 157 #else
 158   node->value = elt;
 159 #endif
 160   return node;
 161 }
 162
 163 #if !WITH_HASHTABLE
 164
 165 static gl_list_node_t
 166 gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index,
 167                         const void *elt)
 168 {
 169   if (!(start_index <= end_index
 170         && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
 171     /* Invalid arguments.  */
 172     abort ();
 173   {
 174     gl_listelement_equals_fn equals = list->base.equals_fn;
 175     /* Iterate across all elements.  */
 176     gl_list_node_t node = list->root;
 177     iterstack_t stack;
 178     iterstack_item_t *stack_ptr = &stack[0];
 179     size_t index = 0;
 180
 181     if (start_index == 0)
 182       {
 183         /* Consider all elements.  */
 184         for (;;)
 185           {
 186             /* Descend on left branch.  */
 187             for (;;)
 188               {
 189                 if (node == NULL)
 190                   break;
 191                 stack_ptr->node = node;
 192                 stack_ptr->rightp = 0;
 193                 node = node->left;
 194                 stack_ptr++;
 195               }
 196             /* Climb up again.  */
 197             for (;;)
 198               {
 199                 if (stack_ptr == &stack[0])
 200                   return NULL;
 201                 stack_ptr--;
 202                 if (!stack_ptr->rightp)
 203                   break;
 204               }
 205             node = stack_ptr->node;
 206             /* Test against current element.  */
 207             if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 208               return node;
 209             index++;
 210             if (index >= end_index)
 211               return NULL;
 212             /* Descend on right branch.  */
 213             stack_ptr->rightp = 1;
 214             node = node->right;
 215             stack_ptr++;
 216           }
 217       }
 218     else
 219       {
 220         /* Consider only elements at indices >= start_index.
 221            In this case, rightp contains the difference between the start_index
 222            for the parent node and the one for the child node (0 when the child
 223            node is the parent's left child, > 0 when the child is the parent's
 224            right child).  */
 225         for (;;)
 226           {
 227             /* Descend on left branch.  */
 228             for (;;)
 229               {
 230                 if (node == NULL)
 231                   break;
 232                 if (node->branch_size <= start_index)
 233                   break;
 234                 stack_ptr->node = node;
 235                 stack_ptr->rightp = 0;
 236                 node = node->left;
 237                 stack_ptr++;
 238               }
 239             /* Climb up again.  */
 240             for (;;)
 241               {
 242                 if (stack_ptr == &stack[0])
 243                   return NULL;
 244                 stack_ptr--;
 245                 if (!stack_ptr->rightp)
 246                   break;
 247                 start_index += stack_ptr->rightp;
 248               }
 249             node = stack_ptr->node;
 250             {
 251               size_t left_branch_size1 =
 252                 (node->left != NULL ? node->left->branch_size : 0) + 1;
 253               if (start_index < left_branch_size1)
 254                 {
 255                   /* Test against current element.  */
 256                   if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 257                     return node;
 258                   /* Now that we have considered all indices < left_branch_size1,
 259                      we can increment start_index.  */
 260                   start_index = left_branch_size1;
 261                 }
 262               index++;
 263               if (index >= end_index)
 264                 return NULL;
 265               /* Descend on right branch.  */
 266               start_index -= left_branch_size1;
 267               stack_ptr->rightp = left_branch_size1;
 268             }
 269             node = node->right;
 270             stack_ptr++;
 271           }
 272       }
 273   }
 274 }
 275
 276 static size_t
 277 gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index,
 278                          const void *elt)
 279 {
 280   if (!(start_index <= end_index
 281         && end_index <= (list->root != NULL ? list->root->branch_size : 0)))
 282     /* Invalid arguments.  */
 283     abort ();
 284   {
 285     gl_listelement_equals_fn equals = list->base.equals_fn;
 286     /* Iterate across all elements.  */
 287     gl_list_node_t node = list->root;
 288     iterstack_t stack;
 289     iterstack_item_t *stack_ptr = &stack[0];
 290     size_t index = 0;
 291
 292     if (start_index == 0)
 293       {
 294         /* Consider all elements.  */
 295         for (;;)
 296           {
 297             /* Descend on left branch.  */
 298             for (;;)
 299               {
 300                 if (node == NULL)
 301                   break;
 302                 stack_ptr->node = node;
 303                 stack_ptr->rightp = 0;
 304                 node = node->left;
 305                 stack_ptr++;
 306               }
 307             /* Climb up again.  */
 308             for (;;)
 309               {
 310                 if (stack_ptr == &stack[0])
 311                   return (size_t)(-1);
 312                 stack_ptr--;
 313                 if (!stack_ptr->rightp)
 314                   break;
 315               }
 316             node = stack_ptr->node;
 317             /* Test against current element.  */
 318             if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 319               return index;
 320             index++;
 321             if (index >= end_index)
 322               return (size_t)(-1);
 323             /* Descend on right branch.  */
 324             stack_ptr->rightp = 1;
 325             node = node->right;
 326             stack_ptr++;
 327           }
 328       }
 329     else
 330       {
 331         /* Consider only elements at indices >= start_index.
 332            In this case, rightp contains the difference between the start_index
 333            for the parent node and the one for the child node (0 when the child
 334            node is the parent's left child, > 0 when the child is the parent's
 335            right child).  */
 336         for (;;)
 337           {
 338             /* Descend on left branch.  */
 339             for (;;)
 340               {
 341                 if (node == NULL)
 342                   break;
 343                 if (node->branch_size <= start_index)
 344                   break;
 345                 stack_ptr->node = node;
 346                 stack_ptr->rightp = 0;
 347                 node = node->left;
 348                 stack_ptr++;
 349               }
 350             /* Climb up again.  */
 351             for (;;)
 352               {
 353                 if (stack_ptr == &stack[0])
 354                   return (size_t)(-1);
 355                 stack_ptr--;
 356                 if (!stack_ptr->rightp)
 357                   break;
 358                 start_index += stack_ptr->rightp;
 359               }
 360             node = stack_ptr->node;
 361             {
 362               size_t left_branch_size1 =
 363                 (node->left != NULL ? node->left->branch_size : 0) + 1;
 364               if (start_index < left_branch_size1)
 365                 {
 366                   /* Test against current element.  */
 367                   if (equals != NULL ? equals (elt, node->value) : elt == node->value)
 368                     return index;
 369                   /* Now that we have considered all indices < left_branch_size1,
 370                      we can increment start_index.  */
 371                   start_index = left_branch_size1;
 372                 }
 373               index++;
 374               if (index >= end_index)
 375                 return (size_t)(-1);
 376               /* Descend on right branch.  */
 377               start_index -= left_branch_size1;
 378               stack_ptr->rightp = left_branch_size1;
 379             }
 380             node = node->right;
 381             stack_ptr++;
 382           }
 383       }
 384   }
 385 }
 386
 387 #endif
 388
 389 static gl_list_node_t
 390 gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
 391 {
 392   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 393
 394   if (!(position <= count))
 395     /* Invalid argument.  */
 396     abort ();
 397   if (position == count)
 398     return gl_tree_add_last (list, elt);
 399   else
 400     return gl_tree_add_before (list, node_at (list->root, position), elt);
 401 }
 402
 403 static bool
 404 gl_tree_remove_at (gl_list_t list, size_t position)
 405 {
 406   gl_list_node_t node = list->root;
 407
 408   if (!(node != NULL && position < node->branch_size))
 409     /* Invalid argument.  */
 410     abort ();
 411   node = node_at (node, position);
 412   return gl_tree_remove_node (list, node);
 413 }
 414
 415 static bool
 416 gl_tree_remove (gl_list_t list, const void *elt)
 417 {
 418   if (list->root != NULL)
 419     {
 420       gl_list_node_t node =
 421         gl_tree_search_from_to (list, 0, list->root->branch_size, elt);
 422
 423       if (node != NULL)
 424         return gl_tree_remove_node (list, node);
 425     }
 426   return false;
 427 }
 428
 429 #if !WITH_HASHTABLE
 430
 431 static void
 432 gl_tree_list_free (gl_list_t list)
 433 {
 434   /* Iterate across all elements in post-order.  */
 435   gl_list_node_t node = list->root;
 436   iterstack_t stack;
 437   iterstack_item_t *stack_ptr = &stack[0];
 438
 439   for (;;)
 440     {
 441       /* Descend on left branch.  */
 442       for (;;)
 443         {
 444           if (node == NULL)
 445             break;
 446           stack_ptr->node = node;
 447           stack_ptr->rightp = false;
 448           node = node->left;
 449           stack_ptr++;
 450         }
 451       /* Climb up again.  */
 452       for (;;)
 453         {
 454           if (stack_ptr == &stack[0])
 455             goto done_iterate;
 456           stack_ptr--;
 457           node = stack_ptr->node;
 458           if (!stack_ptr->rightp)
 459             break;
 460           /* Free the current node.  */
 461           if (list->base.dispose_fn != NULL)
 462             list->base.dispose_fn (node->value);
 463           free (node);
 464         }
 465       /* Descend on right branch.  */
 466       stack_ptr->rightp = true;
 467       node = node->right;
 468       stack_ptr++;
 469     }
 470  done_iterate:
 471   free (list);
 472 }
 473
 474 #endif
 475
 476 /* --------------------- gl_list_iterator_t Data Type --------------------- */
 477
 478 static gl_list_iterator_t
 479 gl_tree_iterator (gl_list_t list)
 480 {
 481   gl_list_iterator_t result;
 482   gl_list_node_t node;
 483
 484   result.vtable = list->base.vtable;
 485   result.list = list;
 486   /* Start node is the leftmost node.  */
 487   node = list->root;
 488   if (node != NULL)
 489     while (node->left != NULL)
 490       node = node->left;
 491   result.p = node;
 492   /* End point is past the rightmost node.  */
 493   result.q = NULL;
 494 #ifdef lint
 495   result.i = 0;
 496   result.j = 0;
 497   result.count = 0;
 498 #endif
 499
 500   return result;
 501 }
 502
 503 static gl_list_iterator_t
 504 gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
 505 {
 506   size_t count = (list->root != NULL ? list->root->branch_size : 0);
 507   gl_list_iterator_t result;
 508
 509   if (!(start_index <= end_index && end_index <= count))
 510     /* Invalid arguments.  */
 511     abort ();
 512   result.vtable = list->base.vtable;
 513   result.list = list;
 514   /* Start node is the node at position start_index.  */
 515   result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
 516   /* End point is the node at position end_index.  */
 517   result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
 518 #ifdef lint
 519   result.i = 0;
 520   result.j = 0;
 521   result.count = 0;
 522 #endif
 523
 524   return result;
 525 }
 526
 527 static bool
 528 gl_tree_iterator_next (gl_list_iterator_t *iterator,
 529                        const void **eltp, gl_list_node_t *nodep)
 530 {
 531   if (iterator->p != iterator->q)
 532     {
 533       gl_list_node_t node = (gl_list_node_t) iterator->p;
 534       *eltp = node->value;
 535       if (nodep != NULL)
 536         *nodep = node;
 537       /* Advance to the next node.  */
 538       if (node->right != NULL)
 539         {
 540           node = node->right;
 541           while (node->left != NULL)
 542             node = node->left;
 543         }
 544       else
 545         {
 546           while (node->parent != NULL && node->parent->right == node)
 547             node = node->parent;
 548           node = node->parent;
 549         }
 550       iterator->p = node;
 551       return true;
 552     }
 553   else
 554     return false;
 555 }
 556
 557 static void
 558 gl_tree_iterator_free (gl_list_iterator_t *iterator)
 559 {
 560 }
 561
 562 /* ---------------------- Sorted gl_list_t Data Type ---------------------- */
 563
 564 static gl_list_node_t
 565 gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
 566                            const void *elt)
 567 {
 568   gl_list_node_t node;
 569
 570   for (node = list->root; node != NULL; )
 571     {
 572       int cmp = compar (node->value, elt);
 573
 574       if (cmp < 0)
 575         node = node->right;
 576       else if (cmp > 0)
 577         node = node->left;
 578       else /* cmp == 0 */
 579         {
 580           /* We have an element equal to ELT.  But we need the leftmost such
 581              element.  */
 582           gl_list_node_t found = node;
 583           node = node->left;
 584           for (; node != NULL; )
 585             {
 586               int cmp2 = compar (node->value, elt);
 587
 588               if (cmp2 < 0)
 589                 node = node->right;
 590               else if (cmp2 > 0)
 591                 /* The list was not sorted.  */
 592                 abort ();
 593               else /* cmp2 == 0 */
 594                 {
 595                   found = node;
 596                   node = node->left;
 597                 }
 598             }
 599           return found;
 600         }
 601     }
 602   return NULL;
 603 }
 604
 605 static gl_list_node_t
 606 gl_tree_sortedlist_search_from_to (gl_list_t list,
 607                                    gl_listelement_compar_fn compar,
 608                                    size_t low, size_t high,
 609                                    const void *elt)
 610 {
 611   gl_list_node_t node;
 612
 613   if (!(low <= high
 614         && high <= (list->root != NULL ? list->root->branch_size : 0)))
 615     /* Invalid arguments.  */
 616     abort ();
 617
 618   for (node = list->root; node != NULL; )
 619     {
 620       size_t left_branch_size =
 621         (node->left != NULL ? node->left->branch_size : 0);
 622
 623       if (low > left_branch_size)
 624         {
 625           low -= left_branch_size + 1;
 626           high -= left_branch_size + 1;
 627           node = node->right;
 628         }
 629       else if (high <= left_branch_size)
 630         node = node->left;
 631       else
 632         {
 633           /* Here low <= left_branch_size < high.  */
 634           int cmp = compar (node->value, elt);
 635
 636           if (cmp < 0)
 637             {
 638               low = 0;
 639               high -= left_branch_size + 1;
 640               node = node->right;
 641             }
 642           else if (cmp > 0)
 643             node = node->left;
 644           else /* cmp == 0 */
 645             {
 646               /* We have an element equal to ELT.  But we need the leftmost
 647                  such element.  */
 648               gl_list_node_t found = node;
 649               node = node->left;
 650               for (; node != NULL; )
 651                 {
 652                   size_t left_branch_size2 =
 653                     (node->left != NULL ? node->left->branch_size : 0);
 654
 655                   if (low > left_branch_size2)
 656                     {
 657                       low -= left_branch_size2 + 1;
 658                       node = node->right;
 659                     }
 660                   else
 661                     {
 662                       /* Here low <= left_branch_size2.  */
 663                       int cmp2 = compar (node->value, elt);
 664
 665                       if (cmp2 < 0)
 666                         {
 667                           low = 0;
 668                           node = node->right;
 669                         }
 670                       else if (cmp2 > 0)
 671                         /* The list was not sorted.  */
 672                         abort ();
 673                       else /* cmp2 == 0 */
 674                         {
 675                           found = node;
 676                           node = node->left;
 677                         }
 678                     }
 679                 }
 680               return found;
 681             }
 682         }
 683     }
 684   return NULL;
 685 }
 686
 687 static size_t
 688 gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
 689                             const void *elt)
 690 {
 691   gl_list_node_t node;
 692   size_t position;
 693
 694   for (node = list->root, position = 0; node != NULL; )
 695     {
 696       int cmp = compar (node->value, elt);
 697
 698       if (cmp < 0)
 699         {
 700           if (node->left != NULL)
 701             position += node->left->branch_size;
 702           position++;
 703           node = node->right;
 704         }
 705       else if (cmp > 0)
 706         node = node->left;
 707       else /* cmp == 0 */
 708         {
 709           /* We have an element equal to ELT.  But we need the leftmost such
 710              element.  */
 711           size_t found_position =
 712             position + (node->left != NULL ? node->left->branch_size : 0);
 713           node = node->left;
 714           for (; node != NULL; )
 715             {
 716               int cmp2 = compar (node->value, elt);
 717
 718               if (cmp2 < 0)
 719                 {
 720                   if (node->left != NULL)
 721                     position += node->left->branch_size;
 722                   position++;
 723                   node = node->right;
 724                 }
 725               else if (cmp2 > 0)
 726                 /* The list was not sorted.  */
 727                 abort ();
 728               else /* cmp2 == 0 */
 729                 {
 730                   found_position =
 731                     position
 732                     + (node->left != NULL ? node->left->branch_size : 0);
 733                   node = node->left;
 734                 }
 735             }
 736           return found_position;
 737         }
 738     }
 739   return (size_t)(-1);
 740 }
 741
 742 static size_t
 743 gl_tree_sortedlist_indexof_from_to (gl_list_t list,
 744                                     gl_listelement_compar_fn compar,
 745                                     size_t low, size_t high,
 746                                     const void *elt)
 747 {
 748   gl_list_node_t node;
 749   size_t position;
 750
 751   if (!(low <= high
 752         && high <= (list->root != NULL ? list->root->branch_size : 0)))
 753     /* Invalid arguments.  */
 754     abort ();
 755
 756   for (node = list->root, position = 0; node != NULL; )
 757     {
 758       size_t left_branch_size =
 759         (node->left != NULL ? node->left->branch_size : 0);
 760
 761       if (low > left_branch_size)
 762         {
 763           low -= left_branch_size + 1;
 764           high -= left_branch_size + 1;
 765           position += left_branch_size + 1;
 766           node = node->right;
 767         }
 768       else if (high <= left_branch_size)
 769         node = node->left;
 770       else
 771         {
 772           /* Here low <= left_branch_size < high.  */
 773           int cmp = compar (node->value, elt);
 774
 775           if (cmp < 0)
 776             {
 777               low = 0;
 778               high -= left_branch_size + 1;
 779               position += left_branch_size + 1;
 780               node = node->right;
 781             }
 782           else if (cmp > 0)
 783             node = node->left;
 784           else /* cmp == 0 */
 785             {
 786               /* We have an element equal to ELT.  But we need the leftmost
 787                  such element.  */
 788               size_t found_position =
 789                 position + (node->left != NULL ? node->left->branch_size : 0);
 790               node = node->left;
 791               for (; node != NULL; )
 792                 {
 793                   size_t left_branch_size2 =
 794                     (node->left != NULL ? node->left->branch_size : 0);
 795
 796                   if (low > left_branch_size2)
 797                     {
 798                       low -= left_branch_size2 + 1;
 799                       node = node->right;
 800                     }
 801                   else
 802                     {
 803                       /* Here low <= left_branch_size2.  */
 804                       int cmp2 = compar (node->value, elt);
 805
 806                       if (cmp2 < 0)
 807                         {
 808                           position += left_branch_size2 + 1;
 809                           node = node->right;
 810                         }
 811                       else if (cmp2 > 0)
 812                         /* The list was not sorted.  */
 813                         abort ();
 814                       else /* cmp2 == 0 */
 815                         {
 816                           found_position = position + left_branch_size2;
 817                           node = node->left;
 818                         }
 819                     }
 820                 }
 821               return found_position;
 822             }
 823         }
 824     }
 825   return (size_t)(-1);
 826 }
 827
 828 static gl_list_node_t
 829 gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
 830                         const void *elt)
 831 {
 832   gl_list_node_t node = list->root;
 833
 834   if (node == NULL)
 835     return gl_tree_add_first (list, elt);
 836
 837   for (;;)
 838     {
 839       int cmp = compar (node->value, elt);
 840
 841       if (cmp < 0)
 842         {
 843           if (node->right == NULL)
 844             return gl_tree_add_after (list, node, elt);
 845           node = node->right;
 846         }
 847       else if (cmp > 0)
 848         {
 849           if (node->left == NULL)
 850             return gl_tree_add_before (list, node, elt);
 851           node = node->left;
 852         }
 853       else /* cmp == 0 */
 854         return gl_tree_add_before (list, node, elt);
 855     }
 856 }
 857
 858 static bool
 859 gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
 860                            const void *elt)
 861 {
 862   gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
 863   if (node != NULL)
 864     return gl_tree_remove_node (list, node);
 865   else
 866     return false;
 867 }