lib/gl_rbtree_oset.c

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