lib/gl_anytree_list2.h

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