lib/gl_anyavltree_list2.h

   1 /* Sequential list data type implemented by a binary tree.
   2    Copyright (C) 2006-2007 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 2, or (at your option)
   8    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, write to the Free Software Foundation,
  17    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  18
  19 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c.  */
  20
  21 /* -------------------------- gl_list_t Data Type -------------------------- */
  22
  23 /* Create a subtree for count >= 1 elements.
  24    Its height is h where 2^(h-1) <= count <= 2^h - 1.  */
  25 static gl_list_node_t
  26 create_subtree_with_contents (size_t count, const void **contents)
  27 {
  28   size_t half1 = (count - 1) / 2;
  29   size_t half2 = count / 2;
  30   /* Note: half1 + half2 = count - 1.  */
  31   gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
  32
  33   if (half1 > 0)
  34     {
  35       node->left = create_subtree_with_contents (half1, contents);
  36       node->left->parent = node;
  37     }
  38   else
  39     node->left = NULL;
  40
  41   node->value = contents[half1];
  42
  43   if (half2 > 0)
  44     {
  45       node->right = create_subtree_with_contents (half2, contents + half1 + 1);
  46       node->right->parent = node;
  47     }
  48   else
  49     node->right = NULL;
  50
  51   /* balance is 0, except when count is a power of two and > 1.
  52      Reason: half1 <= half2 <= half1 + 1, and the two branches can have
  53      different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
  54      case, count = half1 + half2 + 1 = 2^(h+1).  */
  55   node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
  56
  57   node->branch_size = count;
  58
  59   return node;
  60 }
  61
  62 static gl_list_t
  63 gl_tree_create (gl_list_implementation_t implementation,
  64                 gl_listelement_equals_fn equals_fn,
  65                 gl_listelement_hashcode_fn hashcode_fn,
  66                 gl_listelement_dispose_fn dispose_fn,
  67                 bool allow_duplicates,
  68                 size_t count, const void **contents)
  69 {
  70   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  71
  72   list->base.vtable = implementation;
  73   list->base.equals_fn = equals_fn;
  74   list->base.hashcode_fn = hashcode_fn;
  75   list->base.dispose_fn = dispose_fn;
  76   list->base.allow_duplicates = allow_duplicates;
  77 #if WITH_HASHTABLE
  78   {
  79     size_t estimate = xsum (count, count / 2); /* 1.5 * count */
  80     if (estimate < 10)
  81       estimate = 10;
  82     list->table_size = next_prime (estimate);
  83     list->table = XCALLOC (list->table_size, gl_hash_entry_t);
  84   }
  85 #endif
  86   if (count > 0)
  87     {
  88       list->root = create_subtree_with_contents (count, contents);
  89       list->root->parent = NULL;
  90
  91 #if WITH_HASHTABLE
  92       /* Now that the tree is built, node_position() works.  Now we can
  93          add the nodes to the hash table.  */
  94       add_nodes_to_buckets (list);
  95 #endif
  96     }
  97   else
  98     list->root = NULL;
  99
 100   return list;
 101 }
 102
 103 /* Ensure the tree is balanced, after an insertion or deletion operation.
 104    The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
 105    PARENT = NODE->parent.  (NODE can also be NULL.  But PARENT is non-NULL.)
 106    Rotation operations are performed starting at PARENT (not NODE itself!).  */
 107 static void
 108 rebalance (gl_list_t list,
 109            gl_list_node_t node, int height_diff, gl_list_node_t parent)
 110 {
 111   for (;;)
 112     {
 113       gl_list_node_t child;
 114       int previous_balance;
 115       int balance_diff;
 116       gl_list_node_t nodeleft;
 117       gl_list_node_t noderight;
 118
 119       child = node;
 120       node = parent;
 121
 122       previous_balance = node->balance;
 123
 124       /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
 125          branch's height has increased by 1 or the left branch's height has
 126          decreased by 1, -1 if the right branch's height has decreased by 1 or
 127          the left branch's height has increased by 1, 0 if no height change.  */
 128       if (node->left != NULL || node->right != NULL)
 129         balance_diff = (child == node->right ? height_diff : -height_diff);
 130       else
 131         /* Special case where above formula doesn't work, because the caller
 132            didn't tell whether node's left or right branch shrunk from height 1
 133            to NULL.  */
 134         balance_diff = - previous_balance;
 135
 136       node->balance += balance_diff;
 137       if (balance_diff == previous_balance)
 138         {
 139           /* node->balance is outside the range [-1,1].  Must rotate.  */
 140           gl_list_node_t *nodep;
 141
 142           if (node->parent == NULL)
 143             /* node == list->root */
 144             nodep = &list->root;
 145           else if (node->parent->left == node)
 146             nodep = &node->parent->left;
 147           else if (node->parent->right == node)
 148             nodep = &node->parent->right;
 149           else
 150             abort ();
 151
 152           nodeleft = node->left;
 153           noderight = node->right;
 154
 155           if (balance_diff < 0)
 156             {
 157               /* node->balance = -2.  The subtree is heavier on the left side.
 158                  Rotate from left to right:
 159
 160                                   *
 161                                 /   \
 162                              h+2      h
 163                */
 164               gl_list_node_t nodeleftleft = nodeleft->left;
 165               gl_list_node_t nodeleftright = nodeleft->right;
 166               if (nodeleft->balance <= 0)
 167                 {
 168                   /*
 169                               *                    h+2|h+3
 170                             /   \                  /    \
 171                          h+2      h      -->      /   h+1|h+2
 172                          / \                      |    /    \
 173                        h+1 h|h+1                 h+1  h|h+1  h
 174                    */
 175                   node->left = nodeleftright;
 176                   nodeleft->right = node;
 177
 178                   nodeleft->parent = node->parent;
 179                   node->parent = nodeleft;
 180                   if (nodeleftright != NULL)
 181                     nodeleftright->parent = node;
 182
 183                   nodeleft->balance += 1;
 184                   node->balance = - nodeleft->balance;
 185
 186                   node->branch_size =
 187                     (nodeleftright != NULL ? nodeleftright->branch_size : 0)
 188                     + 1 + (noderight != NULL ? noderight->branch_size : 0);
 189                   nodeleft->branch_size =
 190                     nodeleftleft->branch_size + 1 + node->branch_size;
 191
 192                   *nodep = nodeleft;
 193                   height_diff = (height_diff < 0
 194                                  ? /* noderight's height had been decremented from
 195                                       h+1 to h.  The subtree's height changes from
 196                                       h+3 to h+2|h+3.  */
 197                                    nodeleft->balance - 1
 198                                  : /* nodeleft's height had been incremented from
 199                                       h+1 to h+2.  The subtree's height changes from
 200                                       h+2 to h+2|h+3.  */
 201                                    nodeleft->balance);
 202                 }
 203               else
 204                 {
 205                   /*
 206                             *                     h+2
 207                           /   \                 /     \
 208                        h+2      h      -->    h+1     h+1
 209                        / \                    / \     / \
 210                       h  h+1                 h   L   R   h
 211                          / \
 212                         L   R
 213
 214                    */
 215                   gl_list_node_t L = nodeleft->right = nodeleftright->left;
 216                   gl_list_node_t R = node->left = nodeleftright->right;
 217                   nodeleftright->left = nodeleft;
 218                   nodeleftright->right = node;
 219
 220                   nodeleftright->parent = node->parent;
 221                   if (L != NULL)
 222                     L->parent = nodeleft;
 223                   if (R != NULL)
 224                     R->parent = node;
 225                   nodeleft->parent = nodeleftright;
 226                   node->parent = nodeleftright;
 227
 228                   nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
 229                   node->balance = (nodeleftright->balance < 0 ? 1 : 0);
 230                   nodeleftright->balance = 0;
 231
 232                   nodeleft->branch_size =
 233                     (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
 234                     + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
 235                   node->branch_size =
 236                     (node->left != NULL ? node->left->branch_size : 0)
 237                     + 1 + (node->right != NULL ? node->right->branch_size : 0);
 238                   nodeleftright->branch_size =
 239                     nodeleft->branch_size + 1 + node->branch_size;
 240
 241                   *nodep = nodeleftright;
 242                   height_diff = (height_diff < 0
 243                                  ? /* noderight's height had been decremented from
 244                                       h+1 to h.  The subtree's height changes from
 245                                       h+3 to h+2.  */
 246                                    -1
 247                                  : /* nodeleft's height had been incremented from
 248                                       h+1 to h+2.  The subtree's height changes from
 249                                       h+2 to h+2.  */
 250                                    0);
 251                 }
 252             }
 253           else
 254             {
 255               /* node->balance = 2.  The subtree is heavier on the right side.
 256                  Rotate from right to left:
 257
 258                                   *
 259                                 /   \
 260                               h      h+2
 261                */
 262               gl_list_node_t noderightleft = noderight->left;
 263               gl_list_node_t noderightright = noderight->right;
 264               if (noderight->balance >= 0)
 265                 {
 266                   /*
 267                               *                    h+2|h+3
 268                             /   \                   /    \
 269                           h      h+2     -->    h+1|h+2   \
 270                                  / \            /    \    |
 271                              h|h+1 h+1         h   h|h+1 h+1
 272                    */
 273                   node->right = noderightleft;
 274                   noderight->left = node;
 275
 276                   noderight->parent = node->parent;
 277                   node->parent = noderight;
 278                   if (noderightleft != NULL)
 279                     noderightleft->parent = node;
 280
 281                   noderight->balance -= 1;
 282                   node->balance = - noderight->balance;
 283
 284                   node->branch_size =
 285                     (nodeleft != NULL ? nodeleft->branch_size : 0)
 286                     + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
 287                   noderight->branch_size =
 288                     node->branch_size + 1 + noderightright->branch_size;
 289
 290                   *nodep = noderight;
 291                   height_diff = (height_diff < 0
 292                                  ? /* nodeleft's height had been decremented from
 293                                       h+1 to h.  The subtree's height changes from
 294                                       h+3 to h+2|h+3.  */
 295                                    - noderight->balance - 1
 296                                  : /* noderight's height had been incremented from
 297                                       h+1 to h+2.  The subtree's height changes from
 298                                       h+2 to h+2|h+3.  */
 299                                    - noderight->balance);
 300                 }
 301               else
 302                 {
 303                   /*
 304                             *                    h+2
 305                           /   \                /     \
 306                         h      h+2    -->    h+1     h+1
 307                                / \           / \     / \
 308                              h+1  h         h   L   R   h
 309                              / \
 310                             L   R
 311
 312                    */
 313                   gl_list_node_t L = node->right = noderightleft->left;
 314                   gl_list_node_t R = noderight->left = noderightleft->right;
 315                   noderightleft->left = node;
 316                   noderightleft->right = noderight;
 317
 318                   noderightleft->parent = node->parent;
 319                   if (L != NULL)
 320                     L->parent = node;
 321                   if (R != NULL)
 322                     R->parent = noderight;
 323                   node->parent = noderightleft;
 324                   noderight->parent = noderightleft;
 325
 326                   node->balance = (noderightleft->balance > 0 ? -1 : 0);
 327                   noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
 328                   noderightleft->balance = 0;
 329
 330                   node->branch_size =
 331                     (node->left != NULL ? node->left->branch_size : 0)
 332                     + 1 + (node->right != NULL ? node->right->branch_size : 0);
 333                   noderight->branch_size =
 334                     (noderight->left != NULL ? noderight->left->branch_size : 0)
 335                     + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
 336                   noderightleft->branch_size =
 337                     node->branch_size + 1 + noderight->branch_size;
 338
 339                   *nodep = noderightleft;
 340                   height_diff = (height_diff < 0
 341                                  ? /* nodeleft's height had been decremented from
 342                                       h+1 to h.  The subtree's height changes from
 343                                       h+3 to h+2.  */
 344                                    -1
 345                                  : /* noderight's height had been incremented from
 346                                       h+1 to h+2.  The subtree's height changes from
 347                                       h+2 to h+2.  */
 348                                    0);
 349                 }
 350             }
 351           node = *nodep;
 352         }
 353       else
 354         {
 355           /* No rotation needed.  Only propagation of the height change to the
 356              next higher level.  */
 357           if (height_diff < 0)
 358             height_diff = (previous_balance == 0 ? 0 : -1);
 359           else
 360             height_diff = (node->balance == 0 ? 0 : 1);
 361         }
 362
 363       if (height_diff == 0)
 364         break;
 365
 366       parent = node->parent;
 367       if (parent == NULL)
 368         break;
 369     }
 370 }
 371
 372 static gl_list_node_t
 373 gl_tree_add_first (gl_list_t list, const void *elt)
 374 {
 375   /* Create new node.  */
 376   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 377
 378   new_node->left = NULL;
 379   new_node->right = NULL;
 380   new_node->balance = 0;
 381   new_node->branch_size = 1;
 382   new_node->value = elt;
 383 #if WITH_HASHTABLE
 384   new_node->h.hashcode =
 385     (list->base.hashcode_fn != NULL
 386      ? list->base.hashcode_fn (new_node->value)
 387      : (size_t)(uintptr_t) new_node->value);
 388 #endif
 389
 390   /* Add it to the tree.  */
 391   if (list->root == NULL)
 392     {
 393       list->root = new_node;
 394       new_node->parent = NULL;
 395     }
 396   else
 397     {
 398       gl_list_node_t node;
 399
 400       for (node = list->root; node->left != NULL; )
 401         node = node->left;
 402
 403       node->left = new_node;
 404       new_node->parent = node;
 405       node->balance--;
 406
 407       /* Update branch_size fields of the parent nodes.  */
 408       {
 409         gl_list_node_t p;
 410
 411         for (p = node; p != NULL; p = p->parent)
 412           p->branch_size++;
 413       }
 414
 415       /* Rebalance.  */
 416       if (node->right == NULL && node->parent != NULL)
 417         rebalance (list, node, 1, node->parent);
 418     }
 419
 420 #if WITH_HASHTABLE
 421   /* Add node to the hash table.
 422      Note that this is only possible _after_ the node has been added to the
 423      tree structure, because add_to_bucket() uses node_position().  */
 424   add_to_bucket (list, new_node);
 425   hash_resize_after_add (list);
 426 #endif
 427
 428   return new_node;
 429 }
 430
 431 static gl_list_node_t
 432 gl_tree_add_last (gl_list_t list, const void *elt)
 433 {
 434   /* Create new node.  */
 435   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 436
 437   new_node->left = NULL;
 438   new_node->right = NULL;
 439   new_node->balance = 0;
 440   new_node->branch_size = 1;
 441   new_node->value = elt;
 442 #if WITH_HASHTABLE
 443   new_node->h.hashcode =
 444     (list->base.hashcode_fn != NULL
 445      ? list->base.hashcode_fn (new_node->value)
 446      : (size_t)(uintptr_t) new_node->value);
 447 #endif
 448
 449   /* Add it to the tree.  */
 450   if (list->root == NULL)
 451     {
 452       list->root = new_node;
 453       new_node->parent = NULL;
 454     }
 455   else
 456     {
 457       gl_list_node_t node;
 458
 459       for (node = list->root; node->right != NULL; )
 460         node = node->right;
 461
 462       node->right = new_node;
 463       new_node->parent = node;
 464       node->balance++;
 465
 466       /* Update branch_size fields of the parent nodes.  */
 467       {
 468         gl_list_node_t p;
 469
 470         for (p = node; p != NULL; p = p->parent)
 471           p->branch_size++;
 472       }
 473
 474       /* Rebalance.  */
 475       if (node->left == NULL && node->parent != NULL)
 476         rebalance (list, node, 1, node->parent);
 477     }
 478
 479 #if WITH_HASHTABLE
 480   /* Add node to the hash table.
 481      Note that this is only possible _after_ the node has been added to the
 482      tree structure, because add_to_bucket() uses node_position().  */
 483   add_to_bucket (list, new_node);
 484   hash_resize_after_add (list);
 485 #endif
 486
 487   return new_node;
 488 }
 489
 490 static gl_list_node_t
 491 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 492 {
 493   /* Create new node.  */
 494   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 495   bool height_inc;
 496
 497   new_node->left = NULL;
 498   new_node->right = NULL;
 499   new_node->balance = 0;
 500   new_node->branch_size = 1;
 501   new_node->value = elt;
 502 #if WITH_HASHTABLE
 503   new_node->h.hashcode =
 504     (list->base.hashcode_fn != NULL
 505      ? list->base.hashcode_fn (new_node->value)
 506      : (size_t)(uintptr_t) new_node->value);
 507 #endif
 508
 509   /* Add it to the tree.  */
 510   if (node->left == NULL)
 511     {
 512       node->left = new_node;
 513       node->balance--;
 514       height_inc = (node->right == NULL);
 515     }
 516   else
 517     {
 518       for (node = node->left; node->right != NULL; )
 519         node = node->right;
 520       node->right = new_node;
 521       node->balance++;
 522       height_inc = (node->left == NULL);
 523     }
 524   new_node->parent = node;
 525
 526   /* Update branch_size fields of the parent nodes.  */
 527   {
 528     gl_list_node_t p;
 529
 530     for (p = node; p != NULL; p = p->parent)
 531       p->branch_size++;
 532   }
 533
 534   /* Rebalance.  */
 535   if (height_inc && node->parent != NULL)
 536     rebalance (list, node, 1, node->parent);
 537
 538 #if WITH_HASHTABLE
 539   /* Add node to the hash table.
 540      Note that this is only possible _after_ the node has been added to the
 541      tree structure, because add_to_bucket() uses node_position().  */
 542   add_to_bucket (list, new_node);
 543   hash_resize_after_add (list);
 544 #endif
 545
 546   return new_node;
 547 }
 548
 549 static gl_list_node_t
 550 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 551 {
 552   /* Create new node.  */
 553   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 554   bool height_inc;
 555
 556   new_node->left = NULL;
 557   new_node->right = NULL;
 558   new_node->balance = 0;
 559   new_node->branch_size = 1;
 560   new_node->value = elt;
 561 #if WITH_HASHTABLE
 562   new_node->h.hashcode =
 563     (list->base.hashcode_fn != NULL
 564      ? list->base.hashcode_fn (new_node->value)
 565      : (size_t)(uintptr_t) new_node->value);
 566 #endif
 567
 568   /* Add it to the tree.  */
 569   if (node->right == NULL)
 570     {
 571       node->right = new_node;
 572       node->balance++;
 573       height_inc = (node->left == NULL);
 574     }
 575   else
 576     {
 577       for (node = node->right; node->left != NULL; )
 578         node = node->left;
 579       node->left = new_node;
 580       node->balance--;
 581       height_inc = (node->right == NULL);
 582     }
 583   new_node->parent = node;
 584
 585   /* Update branch_size fields of the parent nodes.  */
 586   {
 587     gl_list_node_t p;
 588
 589     for (p = node; p != NULL; p = p->parent)
 590       p->branch_size++;
 591   }
 592
 593   /* Rebalance.  */
 594   if (height_inc && node->parent != NULL)
 595     rebalance (list, node, 1, node->parent);
 596
 597 #if WITH_HASHTABLE
 598   /* Add node to the hash table.
 599      Note that this is only possible _after_ the node has been added to the
 600      tree structure, because add_to_bucket() uses node_position().  */
 601   add_to_bucket (list, new_node);
 602   hash_resize_after_add (list);
 603 #endif
 604
 605   return new_node;
 606 }
 607
 608 static bool
 609 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
 610 {
 611   gl_list_node_t parent;
 612
 613 #if WITH_HASHTABLE
 614   /* Remove node from the hash table.
 615      Note that this is only possible _before_ the node is removed from the
 616      tree structure, because remove_from_bucket() uses node_position().  */
 617   remove_from_bucket (list, node);
 618 #endif
 619
 620   parent = node->parent;
 621
 622   if (node->left == NULL)
 623     {
 624       /* Replace node with node->right.  */
 625       gl_list_node_t child = node->right;
 626
 627       if (child != NULL)
 628         child->parent = parent;
 629       if (parent == NULL)
 630         list->root = child;
 631       else
 632         {
 633           if (parent->left == node)
 634             parent->left = child;
 635           else /* parent->right == node */
 636             parent->right = child;
 637
 638           /* Update branch_size fields of the parent nodes.  */
 639           {
 640             gl_list_node_t p;
 641
 642             for (p = parent; p != NULL; p = p->parent)
 643               p->branch_size--;
 644           }
 645
 646           rebalance (list, child, -1, parent);
 647         }
 648     }
 649   else if (node->right == NULL)
 650     {
 651       /* It is not absolutely necessary to treat this case.  But the more
 652          general case below is more complicated, hence slower.  */
 653       /* Replace node with node->left.  */
 654       gl_list_node_t child = node->left;
 655
 656       child->parent = parent;
 657       if (parent == NULL)
 658         list->root = child;
 659       else
 660         {
 661           if (parent->left == node)
 662             parent->left = child;
 663           else /* parent->right == node */
 664             parent->right = child;
 665
 666           /* Update branch_size fields of the parent nodes.  */
 667           {
 668             gl_list_node_t p;
 669
 670             for (p = parent; p != NULL; p = p->parent)
 671               p->branch_size--;
 672           }
 673
 674           rebalance (list, child, -1, parent);
 675         }
 676     }
 677   else
 678     {
 679       /* Replace node with the rightmost element of the node->left subtree.  */
 680       gl_list_node_t subst;
 681       gl_list_node_t subst_parent;
 682       gl_list_node_t child;
 683
 684       for (subst = node->left; subst->right != NULL; )
 685         subst = subst->right;
 686
 687       subst_parent = subst->parent;
 688
 689       child = subst->left;
 690
 691       /* The case subst_parent == node is special:  If we do nothing special,
 692          we get confusion about node->left, subst->left and child->parent.
 693            subst_parent == node
 694            <==> The 'for' loop above terminated immediately.
 695            <==> subst == subst_parent->left
 696                 [otherwise subst == subst_parent->right]
 697          In this case, we would need to first set
 698            child->parent = node; node->left = child;
 699          and later - when we copy subst into node's position - again
 700            child->parent = subst; subst->left = child;
 701          Altogether a no-op.  */
 702       if (subst_parent != node)
 703         {
 704           if (child != NULL)
 705             child->parent = subst_parent;
 706           subst_parent->right = child;
 707         }
 708
 709       /* Update branch_size fields of the parent nodes.  */
 710       {
 711         gl_list_node_t p;
 712
 713         for (p = subst_parent; p != NULL; p = p->parent)
 714           p->branch_size--;
 715       }
 716
 717       /* Copy subst into node's position.
 718          (This is safer than to copy subst's value into node, keep node in
 719          place, and free subst.)  */
 720       if (subst_parent != node)
 721         {
 722           subst->left = node->left;
 723           subst->left->parent = subst;
 724         }
 725       subst->right = node->right;
 726       subst->right->parent = subst;
 727       subst->balance = node->balance;
 728       subst->branch_size = node->branch_size;
 729       subst->parent = parent;
 730       if (parent == NULL)
 731         list->root = subst;
 732       else if (parent->left == node)
 733         parent->left = subst;
 734       else /* parent->right == node */
 735         parent->right = subst;
 736
 737       /* Rebalancing starts at child's parent, that is subst_parent -
 738          except when subst_parent == node.  In this case, we need to use
 739          its replacement, subst.  */
 740       rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
 741     }
 742
 743   if (list->base.dispose_fn != NULL)
 744     list->base.dispose_fn (node->value);
 745   free (node);
 746   return true;
 747 }