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