lib/gl_anyavltree_list2.h

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