lib/gl_anytree_list2.h

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