gl_anytree_list2.h 26 KB
Newer Older
1
/* Sequential list data type implemented by a binary tree.
2
   Copyright (C) 2006-2010 Free Software Foundation, Inc.
3 4
   Written by Bruno Haible <bruno@clisp.org>, 2006.

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 8
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.
9 10 11 12 13 14 15

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   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 19 20 21

/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
                  gl_avltreehash_list.c, gl_rbtreehash_list.c.  */

static gl_list_t
22 23 24 25 26
gl_tree_nx_create_empty (gl_list_implementation_t implementation,
                         gl_listelement_equals_fn equals_fn,
                         gl_listelement_hashcode_fn hashcode_fn,
                         gl_listelement_dispose_fn dispose_fn,
                         bool allow_duplicates)
27
{
28 29 30 31
  struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));

  if (list == NULL)
    return NULL;
32 33 34 35

  list->base.vtable = implementation;
  list->base.equals_fn = equals_fn;
  list->base.hashcode_fn = hashcode_fn;
36
  list->base.dispose_fn = dispose_fn;
37 38 39
  list->base.allow_duplicates = allow_duplicates;
#if WITH_HASHTABLE
  list->table_size = 11;
40 41 42 43
  list->table =
    (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
  if (list->table == NULL)
    goto fail;
44 45 46 47
#endif
  list->root = NULL;

  return list;
48 49 50 51 52 53

#if WITH_HASHTABLE
 fail:
  free (list);
  return NULL;
#endif
54 55 56 57 58 59 60 61 62 63 64 65 66 67
}

static size_t
gl_tree_size (gl_list_t list)
{
  return (list->root != NULL ? list->root->branch_size : 0);
}

static const void *
gl_tree_node_value (gl_list_t list, gl_list_node_t node)
{
  return node->value;
}

68 69
static int
gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt)
70 71 72 73 74
{
#if WITH_HASHTABLE
  if (elt != node->value)
    {
      size_t new_hashcode =
75 76 77
        (list->base.hashcode_fn != NULL
         ? list->base.hashcode_fn (elt)
         : (size_t)(uintptr_t) elt);
78 79

      if (new_hashcode != node->h.hashcode)
80 81 82 83
        {
          remove_from_bucket (list, node);
          node->value = elt;
          node->h.hashcode = new_hashcode;
84 85 86 87 88 89 90 91 92
          if (add_to_bucket (list, node) < 0)
            {
              /* Out of memory.  We removed node from a bucket but cannot add
                 it to another bucket.  In order to avoid inconsistencies, we
                 must remove node entirely from the list.  */
              gl_tree_remove_node_from_tree (list, node);
              free (node);
              return -1;
            }
93
        }
94
      else
95
        node->value = elt;
96 97 98 99
    }
#else
  node->value = elt;
#endif
100
  return 0;
101 102
}

103 104 105 106 107 108 109
static gl_list_node_t
gl_tree_next_node (gl_list_t list, gl_list_node_t node)
{
  if (node->right != NULL)
    {
      node = node->right;
      while (node->left != NULL)
110
        node = node->left;
111 112 113 114
    }
  else
    {
      while (node->parent != NULL && node->parent->right == node)
115
        node = node->parent;
116 117 118 119 120 121 122 123 124 125 126 127
      node = node->parent;
    }
  return node;
}

static gl_list_node_t
gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
{
  if (node->left != NULL)
    {
      node = node->left;
      while (node->right != NULL)
128
        node = node->right;
129 130 131 132
    }
  else
    {
      while (node->parent != NULL && node->parent->left == node)
133
        node = node->parent;
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
      node = node->parent;
    }
  return node;
}

/* Return the node at the given position < gl_tree_size (list).  */
static inline gl_list_node_t
node_at (gl_list_node_t root, size_t position)
{
  /* Here we know that root != NULL.  */
  gl_list_node_t node = root;

  for (;;)
    {
      if (node->left != NULL)
149 150 151 152 153 154 155 156
        {
          if (position < node->left->branch_size)
            {
              node = node->left;
              continue;
            }
          position -= node->left->branch_size;
        }
157
      if (position == 0)
158
        break;
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
      position--;
      node = node->right;
    }
  return node;
}

static const void *
gl_tree_get_at (gl_list_t list, size_t position)
{
  gl_list_node_t node = list->root;

  if (!(node != NULL && position < node->branch_size))
    /* Invalid argument.  */
    abort ();
  node = node_at (node, position);
  return node->value;
}

static gl_list_node_t
178
gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt)
179 180 181 182 183 184 185 186 187 188 189
{
  gl_list_node_t node = list->root;

  if (!(node != NULL && position < node->branch_size))
    /* Invalid argument.  */
    abort ();
  node = node_at (node, position);
#if WITH_HASHTABLE
  if (elt != node->value)
    {
      size_t new_hashcode =
190 191 192
        (list->base.hashcode_fn != NULL
         ? list->base.hashcode_fn (elt)
         : (size_t)(uintptr_t) elt);
193 194

      if (new_hashcode != node->h.hashcode)
195 196 197 198
        {
          remove_from_bucket (list, node);
          node->value = elt;
          node->h.hashcode = new_hashcode;
199 200 201 202 203 204 205 206 207
          if (add_to_bucket (list, node) < 0)
            {
              /* Out of memory.  We removed node from a bucket but cannot add
                 it to another bucket.  In order to avoid inconsistencies, we
                 must remove node entirely from the list.  */
              gl_tree_remove_node_from_tree (list, node);
              free (node);
              return NULL;
            }
208
        }
209
      else
210
        node->value = elt;
211 212 213 214 215 216 217 218 219 220
    }
#else
  node->value = elt;
#endif
  return node;
}

#if !WITH_HASHTABLE

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 227 228 229 230 231 232 233 234 235 236 237
    /* Invalid arguments.  */
    abort ();
  {
    gl_listelement_equals_fn equals = list->base.equals_fn;
    /* Iterate across all elements.  */
    gl_list_node_t node = list->root;
    iterstack_t stack;
    iterstack_item_t *stack_ptr = &stack[0];
    size_t index = 0;

    if (start_index == 0)
      {
238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271
        /* Consider all elements.  */
        for (;;)
          {
            /* Descend on left branch.  */
            for (;;)
              {
                if (node == NULL)
                  break;
                stack_ptr->node = node;
                stack_ptr->rightp = 0;
                node = node->left;
                stack_ptr++;
              }
            /* Climb up again.  */
            for (;;)
              {
                if (stack_ptr == &stack[0])
                  return NULL;
                stack_ptr--;
                if (!stack_ptr->rightp)
                  break;
              }
            node = stack_ptr->node;
            /* Test against current element.  */
            if (equals != NULL ? equals (elt, node->value) : elt == node->value)
              return node;
            index++;
            if (index >= end_index)
              return NULL;
            /* Descend on right branch.  */
            stack_ptr->rightp = 1;
            node = node->right;
            stack_ptr++;
          }
272 273 274
      }
    else
      {
275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326
        /* Consider only elements at indices >= start_index.
           In this case, rightp contains the difference between the start_index
           for the parent node and the one for the child node (0 when the child
           node is the parent's left child, > 0 when the child is the parent's
           right child).  */
        for (;;)
          {
            /* Descend on left branch.  */
            for (;;)
              {
                if (node == NULL)
                  break;
                if (node->branch_size <= start_index)
                  break;
                stack_ptr->node = node;
                stack_ptr->rightp = 0;
                node = node->left;
                stack_ptr++;
              }
            /* Climb up again.  */
            for (;;)
              {
                if (stack_ptr == &stack[0])
                  return NULL;
                stack_ptr--;
                if (!stack_ptr->rightp)
                  break;
                start_index += stack_ptr->rightp;
              }
            node = stack_ptr->node;
            {
              size_t left_branch_size1 =
                (node->left != NULL ? node->left->branch_size : 0) + 1;
              if (start_index < left_branch_size1)
                {
                  /* Test against current element.  */
                  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
                    return node;
                  /* Now that we have considered all indices < left_branch_size1,
                     we can increment start_index.  */
                  start_index = left_branch_size1;
                }
              index++;
              if (index >= end_index)
                return NULL;
              /* Descend on right branch.  */
              start_index -= left_branch_size1;
              stack_ptr->rightp = left_branch_size1;
            }
            node = node->right;
            stack_ptr++;
          }
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 338 339 340 341 342 343 344 345 346 347 348
    /* Invalid arguments.  */
    abort ();
  {
    gl_listelement_equals_fn equals = list->base.equals_fn;
    /* Iterate across all elements.  */
    gl_list_node_t node = list->root;
    iterstack_t stack;
    iterstack_item_t *stack_ptr = &stack[0];
    size_t index = 0;

    if (start_index == 0)
      {
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382
        /* Consider all elements.  */
        for (;;)
          {
            /* Descend on left branch.  */
            for (;;)
              {
                if (node == NULL)
                  break;
                stack_ptr->node = node;
                stack_ptr->rightp = 0;
                node = node->left;
                stack_ptr++;
              }
            /* Climb up again.  */
            for (;;)
              {
                if (stack_ptr == &stack[0])
                  return (size_t)(-1);
                stack_ptr--;
                if (!stack_ptr->rightp)
                  break;
              }
            node = stack_ptr->node;
            /* Test against current element.  */
            if (equals != NULL ? equals (elt, node->value) : elt == node->value)
              return index;
            index++;
            if (index >= end_index)
              return (size_t)(-1);
            /* Descend on right branch.  */
            stack_ptr->rightp = 1;
            node = node->right;
            stack_ptr++;
          }
383 384 385
      }
    else
      {
386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437
        /* Consider only elements at indices >= start_index.
           In this case, rightp contains the difference between the start_index
           for the parent node and the one for the child node (0 when the child
           node is the parent's left child, > 0 when the child is the parent's
           right child).  */
        for (;;)
          {
            /* Descend on left branch.  */
            for (;;)
              {
                if (node == NULL)
                  break;
                if (node->branch_size <= start_index)
                  break;
                stack_ptr->node = node;
                stack_ptr->rightp = 0;
                node = node->left;
                stack_ptr++;
              }
            /* Climb up again.  */
            for (;;)
              {
                if (stack_ptr == &stack[0])
                  return (size_t)(-1);
                stack_ptr--;
                if (!stack_ptr->rightp)
                  break;
                start_index += stack_ptr->rightp;
              }
            node = stack_ptr->node;
            {
              size_t left_branch_size1 =
                (node->left != NULL ? node->left->branch_size : 0) + 1;
              if (start_index < left_branch_size1)
                {
                  /* Test against current element.  */
                  if (equals != NULL ? equals (elt, node->value) : elt == node->value)
                    return index;
                  /* Now that we have considered all indices < left_branch_size1,
                     we can increment start_index.  */
                  start_index = left_branch_size1;
                }
              index++;
              if (index >= end_index)
                return (size_t)(-1);
              /* Descend on right branch.  */
              start_index -= left_branch_size1;
              stack_ptr->rightp = left_branch_size1;
            }
            node = node->right;
            stack_ptr++;
          }
438 439
      }
  }
440 441 442 443 444
}

#endif

static gl_list_node_t
445
gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt)
446 447 448 449 450 451 452
{
  size_t count = (list->root != NULL ? list->root->branch_size : 0);

  if (!(position <= count))
    /* Invalid argument.  */
    abort ();
  if (position == count)
453
    return gl_tree_nx_add_last (list, elt);
454
  else
455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473
    return gl_tree_nx_add_before (list, node_at (list->root, position), elt);
}

static bool
gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
{
#if WITH_HASHTABLE
  /* Remove node from the hash table.
     Note that this is only possible _before_ the node is removed from the
     tree structure, because remove_from_bucket() uses node_position().  */
  remove_from_bucket (list, node);
#endif

  gl_tree_remove_node_from_tree (list, node);

  if (list->base.dispose_fn != NULL)
    list->base.dispose_fn (node->value);
  free (node);
  return true;
474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490
}

static bool
gl_tree_remove_at (gl_list_t list, size_t position)
{
  gl_list_node_t node = list->root;

  if (!(node != NULL && position < node->branch_size))
    /* Invalid argument.  */
    abort ();
  node = node_at (node, position);
  return gl_tree_remove_node (list, node);
}

static bool
gl_tree_remove (gl_list_t list, const void *elt)
{
491 492 493
  if (list->root != NULL)
    {
      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 503 504 505 506 507 508 509 510 511 512 513 514 515
}

#if !WITH_HASHTABLE

static void
gl_tree_list_free (gl_list_t list)
{
  /* Iterate across all elements in post-order.  */
  gl_list_node_t node = list->root;
  iterstack_t stack;
  iterstack_item_t *stack_ptr = &stack[0];

  for (;;)
    {
      /* Descend on left branch.  */
      for (;;)
516 517 518 519 520 521 522 523
        {
          if (node == NULL)
            break;
          stack_ptr->node = node;
          stack_ptr->rightp = false;
          node = node->left;
          stack_ptr++;
        }
524 525
      /* Climb up again.  */
      for (;;)
526 527 528 529 530 531 532 533 534 535 536 537
        {
          if (stack_ptr == &stack[0])
            goto done_iterate;
          stack_ptr--;
          node = stack_ptr->node;
          if (!stack_ptr->rightp)
            break;
          /* Free the current node.  */
          if (list->base.dispose_fn != NULL)
            list->base.dispose_fn (node->value);
          free (node);
        }
538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566
      /* Descend on right branch.  */
      stack_ptr->rightp = true;
      node = node->right;
      stack_ptr++;
    }
 done_iterate:
  free (list);
}

#endif

/* --------------------- gl_list_iterator_t Data Type --------------------- */

static gl_list_iterator_t
gl_tree_iterator (gl_list_t list)
{
  gl_list_iterator_t result;
  gl_list_node_t node;

  result.vtable = list->base.vtable;
  result.list = list;
  /* Start node is the leftmost node.  */
  node = list->root;
  if (node != NULL)
    while (node->left != NULL)
      node = node->left;
  result.p = node;
  /* End point is past the rightmost node.  */
  result.q = NULL;
567 568 569 570 571
#ifdef lint
  result.i = 0;
  result.j = 0;
  result.count = 0;
#endif
572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590

  return result;
}

static gl_list_iterator_t
gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
{
  size_t count = (list->root != NULL ? list->root->branch_size : 0);
  gl_list_iterator_t result;

  if (!(start_index <= end_index && end_index <= count))
    /* Invalid arguments.  */
    abort ();
  result.vtable = list->base.vtable;
  result.list = list;
  /* Start node is the node at position start_index.  */
  result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
  /* End point is the node at position end_index.  */
  result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
591 592 593 594 595
#ifdef lint
  result.i = 0;
  result.j = 0;
  result.count = 0;
#endif
596 597 598 599 600 601

  return result;
}

static bool
gl_tree_iterator_next (gl_list_iterator_t *iterator,
602
                       const void **eltp, gl_list_node_t *nodep)
603 604 605 606 607 608
{
  if (iterator->p != iterator->q)
    {
      gl_list_node_t node = (gl_list_node_t) iterator->p;
      *eltp = node->value;
      if (nodep != NULL)
609
        *nodep = node;
610 611
      /* Advance to the next node.  */
      if (node->right != NULL)
612 613 614 615 616
        {
          node = node->right;
          while (node->left != NULL)
            node = node->left;
        }
617
      else
618 619 620 621 622
        {
          while (node->parent != NULL && node->parent->right == node)
            node = node->parent;
          node = node->parent;
        }
623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638
      iterator->p = node;
      return true;
    }
  else
    return false;
}

static void
gl_tree_iterator_free (gl_list_iterator_t *iterator)
{
}

/* ---------------------- Sorted gl_list_t Data Type ---------------------- */

static gl_list_node_t
gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
639
                           const void *elt)
640 641 642 643 644 645 646 647
{
  gl_list_node_t node;

  for (node = list->root; node != NULL; )
    {
      int cmp = compar (node->value, elt);

      if (cmp < 0)
648
        node = node->right;
649
      else if (cmp > 0)
650
        node = node->left;
651
      else /* cmp == 0 */
652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673
        {
          /* We have an element equal to ELT.  But we need the leftmost such
             element.  */
          gl_list_node_t found = node;
          node = node->left;
          for (; node != NULL; )
            {
              int cmp2 = compar (node->value, elt);

              if (cmp2 < 0)
                node = node->right;
              else if (cmp2 > 0)
                /* The list was not sorted.  */
                abort ();
              else /* cmp2 == 0 */
                {
                  found = node;
                  node = node->left;
                }
            }
          return found;
        }
674 675 676 677
    }
  return NULL;
}

678 679
static gl_list_node_t
gl_tree_sortedlist_search_from_to (gl_list_t list,
680 681 682
                                   gl_listelement_compar_fn compar,
                                   size_t low, size_t high,
                                   const void *elt)
683 684 685 686
{
  gl_list_node_t node;

  if (!(low <= high
687
        && high <= (list->root != NULL ? list->root->branch_size : 0)))
688 689 690 691 692 693
    /* Invalid arguments.  */
    abort ();

  for (node = list->root; node != NULL; )
    {
      size_t left_branch_size =
694
        (node->left != NULL ? node->left->branch_size : 0);
695 696

      if (low > left_branch_size)
697 698 699 700 701
        {
          low -= left_branch_size + 1;
          high -= left_branch_size + 1;
          node = node->right;
        }
702
      else if (high <= left_branch_size)
703
        node = node->left;
704
      else
705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
        {
          /* Here low <= left_branch_size < high.  */
          int cmp = compar (node->value, elt);

          if (cmp < 0)
            {
              low = 0;
              high -= left_branch_size + 1;
              node = node->right;
            }
          else if (cmp > 0)
            node = node->left;
          else /* cmp == 0 */
            {
              /* We have an element equal to ELT.  But we need the leftmost
                 such element.  */
              gl_list_node_t found = node;
              node = node->left;
              for (; node != NULL; )
                {
                  size_t left_branch_size2 =
                    (node->left != NULL ? node->left->branch_size : 0);

                  if (low > left_branch_size2)
                    {
                      low -= left_branch_size2 + 1;
                      node = node->right;
                    }
                  else
                    {
                      /* Here low <= left_branch_size2.  */
                      int cmp2 = compar (node->value, elt);

                      if (cmp2 < 0)
                        {
                          low = 0;
                          node = node->right;
                        }
                      else if (cmp2 > 0)
                        /* The list was not sorted.  */
                        abort ();
                      else /* cmp2 == 0 */
                        {
                          found = node;
                          node = node->left;
                        }
                    }
                }
              return found;
            }
        }
756 757 758 759
    }
  return NULL;
}

760 761
static size_t
gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
762
                            const void *elt)
763 764 765 766 767 768 769 770 771
{
  gl_list_node_t node;
  size_t position;

  for (node = list->root, position = 0; node != NULL; )
    {
      int cmp = compar (node->value, elt);

      if (cmp < 0)
772 773 774 775 776 777
        {
          if (node->left != NULL)
            position += node->left->branch_size;
          position++;
          node = node->right;
        }
778
      else if (cmp > 0)
779
        node = node->left;
780
      else /* cmp == 0 */
781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810
        {
          /* We have an element equal to ELT.  But we need the leftmost such
             element.  */
          size_t found_position =
            position + (node->left != NULL ? node->left->branch_size : 0);
          node = node->left;
          for (; node != NULL; )
            {
              int cmp2 = compar (node->value, elt);

              if (cmp2 < 0)
                {
                  if (node->left != NULL)
                    position += node->left->branch_size;
                  position++;
                  node = node->right;
                }
              else if (cmp2 > 0)
                /* The list was not sorted.  */
                abort ();
              else /* cmp2 == 0 */
                {
                  found_position =
                    position
                    + (node->left != NULL ? node->left->branch_size : 0);
                  node = node->left;
                }
            }
          return found_position;
        }
811 812 813 814
    }
  return (size_t)(-1);
}

815 816
static size_t
gl_tree_sortedlist_indexof_from_to (gl_list_t list,
817 818 819
                                    gl_listelement_compar_fn compar,
                                    size_t low, size_t high,
                                    const void *elt)
820 821 822 823 824
{
  gl_list_node_t node;
  size_t position;

  if (!(low <= high
825
        && high <= (list->root != NULL ? list->root->branch_size : 0)))
826 827 828 829 830 831
    /* Invalid arguments.  */
    abort ();

  for (node = list->root, position = 0; node != NULL; )
    {
      size_t left_branch_size =
832
        (node->left != NULL ? node->left->branch_size : 0);
833 834

      if (low > left_branch_size)
835 836 837 838 839 840
        {
          low -= left_branch_size + 1;
          high -= left_branch_size + 1;
          position += left_branch_size + 1;
          node = node->right;
        }
841
      else if (high <= left_branch_size)
842
        node = node->left;
843
      else
844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896
        {
          /* Here low <= left_branch_size < high.  */
          int cmp = compar (node->value, elt);

          if (cmp < 0)
            {
              low = 0;
              high -= left_branch_size + 1;
              position += left_branch_size + 1;
              node = node->right;
            }
          else if (cmp > 0)
            node = node->left;
          else /* cmp == 0 */
            {
              /* We have an element equal to ELT.  But we need the leftmost
                 such element.  */
              size_t found_position =
                position + (node->left != NULL ? node->left->branch_size : 0);
              node = node->left;
              for (; node != NULL; )
                {
                  size_t left_branch_size2 =
                    (node->left != NULL ? node->left->branch_size : 0);

                  if (low > left_branch_size2)
                    {
                      low -= left_branch_size2 + 1;
                      node = node->right;
                    }
                  else
                    {
                      /* Here low <= left_branch_size2.  */
                      int cmp2 = compar (node->value, elt);

                      if (cmp2 < 0)
                        {
                          position += left_branch_size2 + 1;
                          node = node->right;
                        }
                      else if (cmp2 > 0)
                        /* The list was not sorted.  */
                        abort ();
                      else /* cmp2 == 0 */
                        {
                          found_position = position + left_branch_size2;
                          node = node->left;
                        }
                    }
                }
              return found_position;
            }
        }
897 898 899 900
    }
  return (size_t)(-1);
}

901
static gl_list_node_t
902 903
gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar,
                           const void *elt)
904 905 906 907
{
  gl_list_node_t node = list->root;

  if (node == NULL)
908
    return gl_tree_nx_add_first (list, elt);
909 910 911 912 913 914

  for (;;)
    {
      int cmp = compar (node->value, elt);

      if (cmp < 0)
915 916
        {
          if (node->right == NULL)
917
            return gl_tree_nx_add_after (list, node, elt);
918 919
          node = node->right;
        }
920
      else if (cmp > 0)
921 922
        {
          if (node->left == NULL)
923
            return gl_tree_nx_add_before (list, node, elt);
924 925
          node = node->left;
        }
926
      else /* cmp == 0 */
927
        return gl_tree_nx_add_before (list, node, elt);
928 929 930 931 932
    }
}

static bool
gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
933
                           const void *elt)
934 935 936 937 938 939 940
{
  gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
  if (node != NULL)
    return gl_tree_remove_node (list, node);
  else
    return false;
}