lib/gl_anytree_list2.h

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