lib/gl_rbtree_oset.c

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