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 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 = XMALLOC (struct gl_oset_node_impl);
 546
 547   new_node->left = NULL;
 548   new_node->right = NULL;
 549   new_node->value = elt;
 550
 551   /* Add it to the tree.  */
 552   if (set->root == NULL)
 553     {
 554       new_node->color = BLACK;
 555       set->root = new_node;
 556       new_node->parent = NULL;
 557     }
 558   else
 559     {
 560       gl_oset_node_t node;
 561
 562       for (node = set->root; node->left != NULL; )
 563         node = node->left;
 564
 565       node->left = new_node;
 566       new_node->parent = node;
 567
 568       /* Color and rebalance.  */
 569       rebalance_after_add (set, new_node, node);
 570     }
 571
 572   set->count++;
 573   return new_node;
 574 }
 575
 576 static gl_oset_node_t
 577 gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
 578 {
 579   /* Create new node.  */
 580   gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
 581
 582   new_node->left = NULL;
 583   new_node->right = NULL;
 584   new_node->value = elt;
 585
 586   /* Add it to the tree.  */
 587   if (node->left == NULL)
 588     node->left = new_node;
 589   else
 590     {
 591       for (node = node->left; node->right != NULL; )
 592         node = node->right;
 593       node->right = new_node;
 594     }
 595   new_node->parent = node;
 596
 597   /* Color and rebalance.  */
 598   rebalance_after_add (set, new_node, node);
 599
 600   set->count++;
 601   return new_node;
 602 }
 603
 604 static gl_oset_node_t
 605 gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
 606 {
 607   /* Create new node.  */
 608   gl_oset_node_t new_node = XMALLOC (struct gl_oset_node_impl);
 609
 610   new_node->left = NULL;
 611   new_node->right = NULL;
 612   new_node->value = elt;
 613
 614   /* Add it to the tree.  */
 615   if (node->right == NULL)
 616     node->right = new_node;
 617   else
 618     {
 619       for (node = node->right; node->left != NULL; )
 620         node = node->left;
 621       node->left = new_node;
 622     }
 623   new_node->parent = node;
 624
 625   /* Color and rebalance.  */
 626   rebalance_after_add (set, new_node, node);
 627
 628   set->count++;
 629   return new_node;
 630 }
 631
 632 static bool
 633 gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
 634 {
 635   gl_oset_node_t parent = node->parent;
 636
 637   if (node->left == NULL)
 638     {
 639       /* Replace node with node->right.  */
 640       gl_oset_node_t child = node->right;
 641
 642       if (child != NULL)
 643         {
 644           child->parent = parent;
 645           /* Since node->left == NULL, child must be RED and of height 1,
 646              hence node must have been BLACK.  Recolor the child.  */
 647           child->color = BLACK;
 648         }
 649       if (parent == NULL)
 650         set->root = child;
 651       else
 652         {
 653           if (parent->left == node)
 654             parent->left = child;
 655           else /* parent->right == node */
 656             parent->right = child;
 657
 658           if (child == NULL && node->color == BLACK)
 659             rebalance_after_remove (set, child, parent);
 660         }
 661     }
 662   else if (node->right == NULL)
 663     {
 664       /* It is not absolutely necessary to treat this case.  But the more
 665          general case below is more complicated, hence slower.  */
 666       /* Replace node with node->left.  */
 667       gl_oset_node_t child = node->left;
 668
 669       child->parent = parent;
 670       /* Since node->right == NULL, child must be RED and of height 1,
 671          hence node must have been BLACK.  Recolor the child.  */
 672       child->color = BLACK;
 673       if (parent == NULL)
 674         set->root = child;
 675       else
 676         {
 677           if (parent->left == node)
 678             parent->left = child;
 679           else /* parent->right == node */
 680             parent->right = child;
 681         }
 682     }
 683   else
 684     {
 685       /* Replace node with the rightmost element of the node->left subtree.  */
 686       gl_oset_node_t subst;
 687       gl_oset_node_t subst_parent;
 688       gl_oset_node_t child;
 689       color_t removed_color;
 690
 691       for (subst = node->left; subst->right != NULL; )
 692         subst = subst->right;
 693
 694       subst_parent = subst->parent;
 695
 696       child = subst->left;
 697
 698       removed_color = subst->color;
 699
 700       /* The case subst_parent == node is special:  If we do nothing special,
 701          we get confusion about node->left, subst->left and child->parent.
 702            subst_parent == node
 703            <==> The 'for' loop above terminated immediately.
 704            <==> subst == subst_parent->left
 705                 [otherwise subst == subst_parent->right]
 706          In this case, we would need to first set
 707            child->parent = node; node->left = child;
 708          and later - when we copy subst into node's position - again
 709            child->parent = subst; subst->left = child;
 710          Altogether a no-op.  */
 711       if (subst_parent != node)
 712         {
 713           if (child != NULL)
 714             child->parent = subst_parent;
 715           subst_parent->right = child;
 716         }
 717
 718       /* Copy subst into node's position.
 719          (This is safer than to copy subst's value into node, keep node in
 720          place, and free subst.)  */
 721       if (subst_parent != node)
 722         {
 723           subst->left = node->left;
 724           subst->left->parent = subst;
 725         }
 726       subst->right = node->right;
 727       subst->right->parent = subst;
 728       subst->color = node->color;
 729       subst->parent = parent;
 730       if (parent == NULL)
 731         set->root = subst;
 732       else if (parent->left == node)
 733         parent->left = subst;
 734       else /* parent->right == node */
 735         parent->right = subst;
 736
 737       if (removed_color == BLACK)
 738         {
 739           if (child != NULL && child->color == RED)
 740             /* Recolor the child.  */
 741             child->color = BLACK;
 742           else
 743             /* Rebalancing starts at child's parent, that is subst_parent -
 744                except when subst_parent == node.  In this case, we need to use
 745                its replacement, subst.  */
 746             rebalance_after_remove (set, child,
 747                                     subst_parent != node ? subst_parent : subst);
 748         }
 749     }
 750
 751   set->count--;
 752   if (set->base.dispose_fn != NULL)
 753     set->base.dispose_fn (node->value);
 754   free (node);
 755   return true;
 756 }
 757
 758 /* Generic binary tree code.  */
 759 #include "gl_anytree_oset.h"
 760
 761 /* For debugging.  */
 762 static unsigned int
 763 check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
 764 {
 765   unsigned int left_blackheight =
 766     (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
 767   unsigned int right_blackheight =
 768     (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
 769
 770   if (!(node->parent == parent))
 771     abort ();
 772   if (!(node->color == BLACK || node->color == RED))
 773     abort ();
 774   if (parent == NULL && !(node->color == BLACK))
 775     abort ();
 776   if (!(left_blackheight == right_blackheight))
 777     abort ();
 778
 779   (*counterp)++;
 780
 781   return left_blackheight + (node->color == BLACK ? 1 : 0);
 782 }
 783 void
 784 gl_rbtree_oset_check_invariants (gl_oset_t set)
 785 {
 786   size_t counter = 0;
 787   if (set->root != NULL)
 788     check_invariants (set->root, NULL, &counter);
 789   if (!(set->count == counter))
 790     abort ();
 791 }
 792
 793 const struct gl_oset_implementation gl_rbtree_oset_implementation =
 794   {
 795     gl_tree_create_empty,
 796     gl_tree_size,
 797     gl_tree_search,
 798     gl_tree_search_atleast,
 799     gl_tree_add,
 800     gl_tree_remove,
 801     gl_tree_oset_free,
 802     gl_tree_iterator,
 803     gl_tree_iterator_next,
 804     gl_tree_iterator_free
 805   };