lib/gl_rbtree_oset.c

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