lib/gl_rbtree_ordered.h

   1 /* Ordered {set,map} data type implemented by a binary tree.
   2    Copyright (C) 2006-2007, 2009-2020 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 <https://www.gnu.org/licenses/>.  */
  17
  18 /* A red-black tree is a binary tree where every node is colored black or
  19    red such that
  20    1. The root is black.
  21    2. No red node has a red parent.
  22       Or equivalently: No red node has a red child.
  23    3. All paths from the root down to any NULL endpoint contain the same
  24       number of black nodes.
  25    Let's call this the "black-height" bh of the tree.  It follows that every
  26    such path contains exactly bh black and between 0 and bh red nodes.  (The
  27    extreme cases are a path containing only black nodes, and a path colored
  28    alternately black-red-black-red-...-black-red.)  The height of the tree
  29    therefore is >= bh, <= 2*bh.
  30  */
  31
  32 /* Color of a node.  */
  33 typedef enum color { BLACK, RED } color_t;
  34
  35 /* Tree node implementation, valid for this file only.  */
  36 struct NODE_IMPL
  37 {
  38   struct NODE_IMPL *left;   /* left branch, or NULL */
  39   struct NODE_IMPL *right;  /* right branch, or NULL */
  40   /* Parent pointer, or NULL. The parent pointer is not needed for most
  41      operations.  It is needed so that a NODE_T can be returned without
  42      memory allocation, on which the functions <container>_remove_node,
  43      <container>_add_before, <container>_add_after can be implemented.  */
  44   struct NODE_IMPL *parent;
  45   color_t color;                    /* node's color */
  46   NODE_PAYLOAD_FIELDS
  47 };
  48 typedef struct NODE_IMPL * NODE_T;
  49
  50 /* Concrete CONTAINER_IMPL type, valid for this file only.  */
  51 struct CONTAINER_IMPL
  52 {
  53   struct CONTAINER_IMPL_BASE base;
  54   struct NODE_IMPL *root;           /* root node or NULL */
  55   size_t count;                     /* number of nodes */
  56 };
  57
  58 /* A red-black tree of height h has a black-height bh >= ceil(h/2) and
  59    therefore at least 2^ceil(h/2) - 1 elements.  So, h <= 116 (because a tree
  60    of height h >= 117 would have at least 2^59 - 1 elements, and because even
  61    on 64-bit machines,
  62      sizeof (NODE_IMPL) * (2^59 - 1) > 2^64
  63    this would exceed the address space of the machine.  */
  64 #define MAXHEIGHT 116
  65
  66 /* Rotates left a subtree.
  67
  68                          B                         D
  69                        /   \                     /   \
  70                      A       D       -->       B       E
  71                             / \               / \
  72                            C   E             A   C
  73
  74    Changes the tree structure, updates the branch sizes.
  75    The caller must update the colors and register D as child of its parent.  */
  76 static NODE_T
  77 rotate_left (NODE_T b_node, NODE_T d_node)
  78 {
  79   NODE_T c_node = d_node->left;
  80
  81   b_node->right = c_node;
  82   d_node->left = b_node;
  83
  84   d_node->parent = b_node->parent;
  85   b_node->parent = d_node;
  86   if (c_node != NULL)
  87     c_node->parent = b_node;
  88
  89   return d_node;
  90 }
  91
  92 /* Rotates right a subtree.
  93
  94                            D                     B
  95                          /   \                 /   \
  96                        B       E     -->     A       D
  97                       / \                           / \
  98                      A   C                         C   E
  99
 100    Changes the tree structure, updates the branch sizes.
 101    The caller must update the colors and register B as child of its parent.  */
 102 static NODE_T
 103 rotate_right (NODE_T b_node, NODE_T d_node)
 104 {
 105   NODE_T c_node = b_node->right;
 106
 107   d_node->left = c_node;
 108   b_node->right = d_node;
 109
 110   b_node->parent = d_node->parent;
 111   d_node->parent = b_node;
 112   if (c_node != NULL)
 113     c_node->parent = d_node;
 114
 115   return b_node;
 116 }
 117
 118 /* Ensures the tree is balanced, after an insertion operation.
 119    Also assigns node->color.
 120    parent is the given node's parent, known to be non-NULL.  */
 121 static void
 122 rebalance_after_add (CONTAINER_T container, NODE_T node, NODE_T parent)
 123 {
 124   for (;;)
 125     {
 126       /* At this point, parent = node->parent != NULL.
 127          Think of node->color being RED (although node->color is not yet
 128          assigned.)  */
 129       NODE_T grandparent;
 130       NODE_T uncle;
 131
 132       if (parent->color == BLACK)
 133         {
 134           /* A RED color for node is acceptable.  */
 135           node->color = RED;
 136           return;
 137         }
 138
 139       grandparent = parent->parent;
 140       /* Since parent is RED, we know that
 141          grandparent is != NULL and colored BLACK.  */
 142
 143       if (grandparent->left == parent)
 144         uncle = grandparent->right;
 145       else if (grandparent->right == parent)
 146         uncle = grandparent->left;
 147       else
 148         abort ();
 149
 150       if (uncle != NULL && uncle->color == RED)
 151         {
 152           /* Change grandparent from BLACK to RED, and
 153              change parent and uncle from RED to BLACK.
 154              This makes it acceptable for node to be RED.  */
 155           node->color = RED;
 156           parent->color = uncle->color = BLACK;
 157           node = grandparent;
 158         }
 159       else
 160         {
 161           /* grandparent and uncle are BLACK.  parent is RED.  node wants
 162              to be RED too.
 163              In this case, recoloring is not sufficient.  Need to perform
 164              one or two rotations.  */
 165           NODE_T *grandparentp;
 166
 167           if (grandparent->parent == NULL)
 168             grandparentp = &container->root;
 169           else if (grandparent->parent->left == grandparent)
 170             grandparentp = &grandparent->parent->left;
 171           else if (grandparent->parent->right == grandparent)
 172             grandparentp = &grandparent->parent->right;
 173           else
 174             abort ();
 175
 176           if (grandparent->left == parent)
 177             {
 178               if (parent->right == node)
 179                 {
 180                   /* Rotation between node and parent.  */
 181                   grandparent->left = rotate_left (parent, node);
 182                   node = parent;
 183                   parent = grandparent->left;
 184                 }
 185               /* grandparent and uncle are BLACK.  parent and node want to be
 186                  RED.  parent = grandparent->left.  node = parent->left.
 187
 188                       grandparent              parent
 189                          bh+1                   bh+1
 190                          /   \                 /   \
 191                      parent  uncle    -->   node  grandparent
 192                       bh      bh             bh      bh
 193                       / \                           / \
 194                    node  C                         C  uncle
 195                     bh   bh                       bh    bh
 196                */
 197               *grandparentp = rotate_right (parent, grandparent);
 198               parent->color = BLACK;
 199               node->color = grandparent->color = RED;
 200             }
 201           else /* grandparent->right == parent */
 202             {
 203               if (parent->left == node)
 204                 {
 205                   /* Rotation between node and parent.  */
 206                   grandparent->right = rotate_right (node, parent);
 207                   node = parent;
 208                   parent = grandparent->right;
 209                 }
 210               /* grandparent and uncle are BLACK.  parent and node want to be
 211                  RED.  parent = grandparent->right.  node = parent->right.
 212
 213                     grandparent                    parent
 214                        bh+1                         bh+1
 215                        /   \                       /   \
 216                    uncle  parent     -->   grandparent  node
 217                      bh     bh                  bh       bh
 218                             / \                 / \
 219                            C  node          uncle  C
 220                           bh   bh            bh    bh
 221                */
 222               *grandparentp = rotate_left (grandparent, parent);
 223               parent->color = BLACK;
 224               node->color = grandparent->color = RED;
 225             }
 226           return;
 227         }
 228
 229       /* Start again with a new (node, parent) pair.  */
 230       parent = node->parent;
 231
 232       if (parent == NULL)
 233         {
 234           /* Change node's color from RED to BLACK.  This increases the
 235              tree's black-height.  */
 236           node->color = BLACK;
 237           return;
 238         }
 239     }
 240 }
 241
 242 /* Ensures the tree is balanced, after a deletion operation.
 243    CHILD was a grandchild of PARENT and is now its child.  Between them,
 244    a black node was removed.  CHILD is also black, or NULL.
 245    (CHILD can also be NULL.  But PARENT is non-NULL.)  */
 246 static void
 247 rebalance_after_remove (CONTAINER_T container, NODE_T child, NODE_T parent)
 248 {
 249   for (;;)
 250     {
 251       /* At this point, we reduced the black-height of the CHILD subtree by 1.
 252          To make up, either look for a possibility to turn a RED to a BLACK
 253          node, or try to reduce the black-height tree of CHILD's sibling
 254          subtree as well.  */
 255       NODE_T *parentp;
 256
 257       if (parent->parent == NULL)
 258         parentp = &container->root;
 259       else if (parent->parent->left == parent)
 260         parentp = &parent->parent->left;
 261       else if (parent->parent->right == parent)
 262         parentp = &parent->parent->right;
 263       else
 264         abort ();
 265
 266       if (parent->left == child)
 267         {
 268           NODE_T sibling = parent->right;
 269           /* sibling's black-height is >= 1.  In particular,
 270              sibling != NULL.
 271
 272                       parent
 273                        /   \
 274                    child  sibling
 275                      bh    bh+1
 276            */
 277
 278           if (sibling->color == RED)
 279             {
 280               /* sibling is RED, hence parent is BLACK and sibling's children
 281                  are non-NULL and BLACK.
 282
 283                       parent                       sibling
 284                        bh+2                         bh+2
 285                        /   \                        /   \
 286                    child  sibling     -->       parent    SR
 287                      bh    bh+1                  bh+1    bh+1
 288                             / \                  / \
 289                           SL   SR            child  SL
 290                          bh+1 bh+1             bh  bh+1
 291                */
 292               *parentp = rotate_left (parent, sibling);
 293               parent->color = RED;
 294               sibling->color = BLACK;
 295
 296               /* Concentrate on the subtree of parent.  The new sibling is
 297                  one of the old sibling's children, and known to be BLACK.  */
 298               parentp = &sibling->left;
 299               sibling = parent->right;
 300             }
 301           /* Now we know that sibling is BLACK.
 302
 303                       parent
 304                        /   \
 305                    child  sibling
 306                      bh    bh+1
 307            */
 308           if (sibling->right != NULL && sibling->right->color == RED)
 309             {
 310               /*
 311                       parent                     sibling
 312                      bh+1|bh+2                  bh+1|bh+2
 313                        /   \                      /   \
 314                    child  sibling    -->      parent    SR
 315                      bh    bh+1                bh+1    bh+1
 316                             / \                / \
 317                           SL   SR           child  SL
 318                           bh   bh             bh   bh
 319                */
 320               *parentp = rotate_left (parent, sibling);
 321               sibling->color = parent->color;
 322               parent->color = BLACK;
 323               sibling->right->color = BLACK;
 324               return;
 325             }
 326           else if (sibling->left != NULL && sibling->left->color == RED)
 327             {
 328               /*
 329                       parent                   parent
 330                      bh+1|bh+2                bh+1|bh+2
 331                        /   \                    /   \
 332                    child  sibling    -->    child    SL
 333                      bh    bh+1               bh    bh+1
 334                             / \                     /  \
 335                           SL   SR                 SLL  sibling
 336                           bh   bh                 bh     bh
 337                          /  \                           /   \
 338                        SLL  SLR                       SLR    SR
 339                        bh    bh                       bh     bh
 340
 341                  where SLL, SLR, SR are all black.
 342                */
 343               parent->right = rotate_right (sibling->left, sibling);
 344               /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
 345               sibling->color = RED;
 346               sibling = parent->right;
 347               sibling->color = BLACK;
 348
 349               /* Now do as in the previous case.  */
 350               *parentp = rotate_left (parent, sibling);
 351               sibling->color = parent->color;
 352               parent->color = BLACK;
 353               sibling->right->color = BLACK;
 354               return;
 355             }
 356           else
 357             {
 358               if (parent->color == BLACK)
 359                 {
 360                   /* Change sibling from BLACK to RED.  Then the entire
 361                      subtree at parent has decreased its black-height.
 362                               parent                   parent
 363                                bh+2                     bh+1
 364                                /   \                    /   \
 365                            child  sibling    -->    child  sibling
 366                              bh    bh+1               bh     bh
 367                    */
 368                   sibling->color = RED;
 369
 370                   child = parent;
 371                 }
 372               else
 373                 {
 374                   /* Change parent from RED to BLACK, but compensate by
 375                      changing sibling from BLACK to RED.
 376                               parent                   parent
 377                                bh+1                     bh+1
 378                                /   \                    /   \
 379                            child  sibling    -->    child  sibling
 380                              bh    bh+1               bh     bh
 381                    */
 382                   parent->color = BLACK;
 383                   sibling->color = RED;
 384                   return;
 385                 }
 386             }
 387         }
 388       else if (parent->right == child)
 389         {
 390           NODE_T sibling = parent->left;
 391           /* sibling's black-height is >= 1.  In particular,
 392              sibling != NULL.
 393
 394                       parent
 395                        /   \
 396                   sibling  child
 397                     bh+1     bh
 398            */
 399
 400           if (sibling->color == RED)
 401             {
 402               /* sibling is RED, hence parent is BLACK and sibling's children
 403                  are non-NULL and BLACK.
 404
 405                       parent                 sibling
 406                        bh+2                    bh+2
 407                        /   \                  /   \
 408                   sibling  child    -->     SR    parent
 409                     bh+1     ch            bh+1    bh+1
 410                     / \                            / \
 411                   SL   SR                        SL  child
 412                  bh+1 bh+1                      bh+1   bh
 413                */
 414               *parentp = rotate_right (sibling, parent);
 415               parent->color = RED;
 416               sibling->color = BLACK;
 417
 418               /* Concentrate on the subtree of parent.  The new sibling is
 419                  one of the old sibling's children, and known to be BLACK.  */
 420               parentp = &sibling->right;
 421               sibling = parent->left;
 422             }
 423           /* Now we know that sibling is BLACK.
 424
 425                       parent
 426                        /   \
 427                   sibling  child
 428                     bh+1     bh
 429            */
 430           if (sibling->left != NULL && sibling->left->color == RED)
 431             {
 432               /*
 433                        parent                 sibling
 434                       bh+1|bh+2              bh+1|bh+2
 435                         /   \                  /   \
 436                    sibling  child    -->     SL   parent
 437                      bh+1     bh            bh+1   bh+1
 438                      / \                           / \
 439                    SL   SR                       SR  child
 440                    bh   bh                       bh    bh
 441                */
 442               *parentp = rotate_right (sibling, parent);
 443               sibling->color = parent->color;
 444               parent->color = BLACK;
 445               sibling->left->color = BLACK;
 446               return;
 447             }
 448           else if (sibling->right != NULL && sibling->right->color == RED)
 449             {
 450               /*
 451                       parent                       parent
 452                      bh+1|bh+2                    bh+1|bh+2
 453                        /   \                        /   \
 454                    sibling  child    -->          SR    child
 455                     bh+1      bh                 bh+1     bh
 456                      / \                         /  \
 457                    SL   SR                  sibling  SRR
 458                    bh   bh                    bh      bh
 459                        /  \                  /   \
 460                      SRL  SRR               SL   SRL
 461                      bh    bh               bh    bh
 462
 463                  where SL, SRL, SRR are all black.
 464                */
 465               parent->left = rotate_left (sibling, sibling->right);
 466               /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
 467               sibling->color = RED;
 468               sibling = parent->left;
 469               sibling->color = BLACK;
 470
 471               /* Now do as in the previous case.  */
 472               *parentp = rotate_right (sibling, parent);
 473               sibling->color = parent->color;
 474               parent->color = BLACK;
 475               sibling->left->color = BLACK;
 476               return;
 477             }
 478           else
 479             {
 480               if (parent->color == BLACK)
 481                 {
 482                   /* Change sibling from BLACK to RED.  Then the entire
 483                      subtree at parent has decreased its black-height.
 484                               parent                   parent
 485                                bh+2                     bh+1
 486                                /   \                    /   \
 487                            sibling  child    -->    sibling  child
 488                             bh+1      bh              bh       bh
 489                    */
 490                   sibling->color = RED;
 491
 492                   child = parent;
 493                 }
 494               else
 495                 {
 496                   /* Change parent from RED to BLACK, but compensate by
 497                      changing sibling from BLACK to RED.
 498                               parent                   parent
 499                                bh+1                     bh+1
 500                                /   \                    /   \
 501                            sibling  child    -->    sibling  child
 502                             bh+1      bh              bh       bh
 503                    */
 504                   parent->color = BLACK;
 505                   sibling->color = RED;
 506                   return;
 507                 }
 508             }
 509         }
 510       else
 511         abort ();
 512
 513       /* Start again with a new (child, parent) pair.  */
 514       parent = child->parent;
 515
 516 #if 0 /* Already handled.  */
 517       if (child != NULL && child->color == RED)
 518         {
 519           child->color = BLACK;
 520           return;
 521         }
 522 #endif
 523
 524       if (parent == NULL)
 525         return;
 526     }
 527 }
 528
 529 static NODE_T
 530 gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS)
 531 {
 532   /* Create new node.  */
 533   NODE_T new_node =
 534     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 535
 536   if (new_node == NULL)
 537     return NULL;
 538
 539   new_node->left = NULL;
 540   new_node->right = NULL;
 541   NODE_PAYLOAD_ASSIGN(new_node)
 542
 543   /* Add it to the tree.  */
 544   if (container->root == NULL)
 545     {
 546       new_node->color = BLACK;
 547       container->root = new_node;
 548       new_node->parent = NULL;
 549     }
 550   else
 551     {
 552       NODE_T node;
 553
 554       for (node = container->root; node->left != NULL; )
 555         node = node->left;
 556
 557       node->left = new_node;
 558       new_node->parent = node;
 559
 560       /* Color and rebalance.  */
 561       rebalance_after_add (container, new_node, node);
 562     }
 563
 564   container->count++;
 565   return new_node;
 566 }
 567
 568 /* Adds the already allocated NEW_NODE to the tree, right before NODE.  */
 569 static void
 570 gl_tree_add_node_before (CONTAINER_T container, NODE_T node, NODE_T new_node)
 571 {
 572   new_node->left = NULL;
 573   new_node->right = NULL;
 574
 575   /* Add it to the tree.  */
 576   if (node->left == NULL)
 577     node->left = new_node;
 578   else
 579     {
 580       for (node = node->left; node->right != NULL; )
 581         node = node->right;
 582       node->right = new_node;
 583     }
 584   new_node->parent = node;
 585
 586   /* Color and rebalance.  */
 587   rebalance_after_add (container, new_node, node);
 588
 589   container->count++;
 590 }
 591
 592 static NODE_T
 593 gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
 594 {
 595   /* Create new node.  */
 596   NODE_T new_node =
 597     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 598
 599   if (new_node == NULL)
 600     return NULL;
 601
 602   NODE_PAYLOAD_ASSIGN(new_node)
 603
 604   gl_tree_add_node_before (container, node, new_node);
 605   return new_node;
 606 }
 607
 608 /* Adds the already allocated NEW_NODE to the tree, right after NODE.  */
 609 static void
 610 gl_tree_add_node_after (CONTAINER_T container, NODE_T node, NODE_T new_node)
 611 {
 612   new_node->left = NULL;
 613   new_node->right = NULL;
 614
 615   /* Add it to the tree.  */
 616   if (node->right == NULL)
 617     node->right = new_node;
 618   else
 619     {
 620       for (node = node->right; node->left != NULL; )
 621         node = node->left;
 622       node->left = new_node;
 623     }
 624   new_node->parent = node;
 625
 626   /* Color and rebalance.  */
 627   rebalance_after_add (container, new_node, node);
 628
 629   container->count++;
 630 }
 631
 632 static NODE_T
 633 gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
 634 {
 635   /* Create new node.  */
 636   NODE_T new_node =
 637     (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
 638
 639   if (new_node == NULL)
 640     return NULL;
 641
 642   NODE_PAYLOAD_ASSIGN(new_node)
 643
 644   gl_tree_add_node_after (container, node, new_node);
 645   return new_node;
 646 }
 647
 648 static void
 649 gl_tree_remove_node_no_free (CONTAINER_T container, NODE_T node)
 650 {
 651   NODE_T parent = node->parent;
 652
 653   if (node->left == NULL)
 654     {
 655       /* Replace node with node->right.  */
 656       NODE_T child = node->right;
 657
 658       if (child != NULL)
 659         {
 660           child->parent = parent;
 661           /* Since node->left == NULL, child must be RED and of height 1,
 662              hence node must have been BLACK.  Recolor the child.  */
 663           child->color = BLACK;
 664         }
 665       if (parent == NULL)
 666         container->root = child;
 667       else
 668         {
 669           if (parent->left == node)
 670             parent->left = child;
 671           else /* parent->right == node */
 672             parent->right = child;
 673
 674           if (child == NULL && node->color == BLACK)
 675             rebalance_after_remove (container, child, parent);
 676         }
 677     }
 678   else if (node->right == NULL)
 679     {
 680       /* It is not absolutely necessary to treat this case.  But the more
 681          general case below is more complicated, hence slower.  */
 682       /* Replace node with node->left.  */
 683       NODE_T child = node->left;
 684
 685       child->parent = parent;
 686       /* Since node->right == NULL, child must be RED and of height 1,
 687          hence node must have been BLACK.  Recolor the child.  */
 688       child->color = BLACK;
 689       if (parent == NULL)
 690         container->root = child;
 691       else
 692         {
 693           if (parent->left == node)
 694             parent->left = child;
 695           else /* parent->right == node */
 696             parent->right = child;
 697         }
 698     }
 699   else
 700     {
 701       /* Replace node with the rightmost element of the node->left subtree.  */
 702       NODE_T subst;
 703       NODE_T subst_parent;
 704       NODE_T child;
 705       color_t removed_color;
 706
 707       for (subst = node->left; subst->right != NULL; )
 708         subst = subst->right;
 709
 710       subst_parent = subst->parent;
 711
 712       child = subst->left;
 713
 714       removed_color = subst->color;
 715
 716       /* The case subst_parent == node is special:  If we do nothing special,
 717          we get confusion about node->left, subst->left and child->parent.
 718            subst_parent == node
 719            <==> The 'for' loop above terminated immediately.
 720            <==> subst == subst_parent->left
 721                 [otherwise subst == subst_parent->right]
 722          In this case, we would need to first set
 723            child->parent = node; node->left = child;
 724          and later - when we copy subst into node's position - again
 725            child->parent = subst; subst->left = child;
 726          Altogether a no-op.  */
 727       if (subst_parent != node)
 728         {
 729           if (child != NULL)
 730             child->parent = subst_parent;
 731           subst_parent->right = child;
 732         }
 733
 734       /* Copy subst into node's position.
 735          (This is safer than to copy subst's value into node, keep node in
 736          place, and free subst.)  */
 737       if (subst_parent != node)
 738         {
 739           subst->left = node->left;
 740           subst->left->parent = subst;
 741         }
 742       subst->right = node->right;
 743       subst->right->parent = subst;
 744       subst->color = node->color;
 745       subst->parent = parent;
 746       if (parent == NULL)
 747         container->root = subst;
 748       else if (parent->left == node)
 749         parent->left = subst;
 750       else /* parent->right == node */
 751         parent->right = subst;
 752
 753       if (removed_color == BLACK)
 754         {
 755           if (child != NULL && child->color == RED)
 756             /* Recolor the child.  */
 757             child->color = BLACK;
 758           else
 759             /* Rebalancing starts at child's parent, that is subst_parent -
 760                except when subst_parent == node.  In this case, we need to use
 761                its replacement, subst.  */
 762             rebalance_after_remove (container, child,
 763                                     subst_parent != node ? subst_parent : subst);
 764         }
 765     }
 766
 767   container->count--;
 768 }
 769
 770 static bool
 771 gl_tree_remove_node (CONTAINER_T container, NODE_T node)
 772 {
 773   gl_tree_remove_node_no_free (container, node);
 774   NODE_PAYLOAD_DISPOSE (container, node)
 775   free (node);
 776   return true;
 777 }
 778
 779 /* For debugging.  */
 780 static unsigned int
 781 check_invariants (NODE_T node, NODE_T parent, size_t *counterp)
 782 {
 783   unsigned int left_blackheight =
 784     (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
 785   unsigned int right_blackheight =
 786     (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
 787
 788   if (!(node->parent == parent))
 789     abort ();
 790   if (!(node->color == BLACK || node->color == RED))
 791     abort ();
 792   if (parent == NULL && !(node->color == BLACK))
 793     abort ();
 794   if (!(left_blackheight == right_blackheight))
 795     abort ();
 796
 797   (*counterp)++;
 798
 799   return left_blackheight + (node->color == BLACK ? 1 : 0);
 800 }