lib/gl_anytree_list2.h

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