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