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