lib/gl_anytree_list2.h

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