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