lib/gl_anyrbtree_list2.h

   1 /* Sequential list 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 /* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c.  */
  20
  21 /* -------------------------- gl_list_t Data Type -------------------------- */
  22
  23 /* Create a subtree for count >= 1 elements.
  24    Its black-height bh is passed as argument, with
  25    2^bh - 1 <= count <= 2^(bh+1) - 1.  bh == 0 implies count == 1.
  26    Its height is h where 2^(h-1) <= count <= 2^h - 1.  */
  27 static gl_list_node_t
  28 create_subtree_with_contents (unsigned int bh,
  29                               size_t count, const void **contents)
  30 {
  31   size_t half1 = (count - 1) / 2;
  32   size_t half2 = count / 2;
  33   /* Note: half1 + half2 = count - 1.  */
  34   gl_list_node_t node = XMALLOC (struct gl_list_node_impl);
  35
  36   if (half1 > 0)
  37     {
  38       /* half1 > 0 implies count > 1, implies bh >= 1, implies
  39            2^(bh-1) - 1 <= half1 <= 2^bh - 1.  */
  40       node->left =
  41         create_subtree_with_contents (bh - 1, half1, contents);
  42       node->left->parent = node;
  43     }
  44   else
  45     node->left = NULL;
  46
  47   node->value = contents[half1];
  48
  49   if (half2 > 0)
  50     {
  51       /* half2 > 0 implies count > 1, implies bh >= 1, implies
  52            2^(bh-1) - 1 <= half2 <= 2^bh - 1.  */
  53       node->right =
  54        create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
  55       node->right->parent = node;
  56     }
  57   else
  58     node->right = NULL;
  59
  60   node->color = (bh == 0 ? RED : BLACK);
  61
  62   node->branch_size = count;
  63
  64   return node;
  65 }
  66
  67 static gl_list_t
  68 gl_tree_create (gl_list_implementation_t implementation,
  69                 gl_listelement_equals_fn equals_fn,
  70                 gl_listelement_hashcode_fn hashcode_fn,
  71                 bool allow_duplicates,
  72                 size_t count, const void **contents)
  73 {
  74   struct gl_list_impl *list = XMALLOC (struct gl_list_impl);
  75
  76   list->base.vtable = implementation;
  77   list->base.equals_fn = equals_fn;
  78   list->base.hashcode_fn = hashcode_fn;
  79   list->base.allow_duplicates = allow_duplicates;
  80 #if WITH_HASHTABLE
  81   {
  82     size_t estimate = xsum (count, count / 2); /* 1.5 * count */
  83     if (estimate < 10)
  84       estimate = 10;
  85     list->table_size = next_prime (estimate);
  86     list->table = XCALLOC (list->table_size, gl_hash_entry_t);
  87   }
  88 #endif
  89   if (count > 0)
  90     {
  91       /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
  92          upper bh levels are black, and only the partially present lowest
  93          level is red.  */
  94       unsigned int bh;
  95       {
  96         size_t n;
  97         for (n = count + 1, bh = 0; n > 1; n = n >> 1)
  98           bh++;
  99       }
 100
 101       list->root = create_subtree_with_contents (bh, count, contents);
 102       list->root->parent = NULL;
 103
 104 #if WITH_HASHTABLE
 105       /* Now that the tree is built, node_position() works.  Now we can
 106          add the nodes to the hash table.  */
 107       add_nodes_to_buckets (list);
 108 #endif
 109     }
 110   else
 111     list->root = NULL;
 112
 113   return list;
 114 }
 115
 116 /* Rotate left a subtree.
 117
 118                          B                         D
 119                        /   \                     /   \
 120                      A       D       -->       B       E
 121                             / \               / \
 122                            C   E             A   C
 123
 124    Change the tree structure, update the branch sizes.
 125    The caller must update the colors and register D as child of its parent.  */
 126 static inline gl_list_node_t
 127 rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
 128 {
 129   gl_list_node_t a_node = b_node->left;
 130   gl_list_node_t c_node = d_node->left;
 131   gl_list_node_t e_node = d_node->right;
 132
 133   b_node->right = c_node;
 134   d_node->left = b_node;
 135
 136   d_node->parent = b_node->parent;
 137   b_node->parent = d_node;
 138   if (c_node != NULL)
 139     c_node->parent = b_node;
 140
 141   b_node->branch_size =
 142     (a_node != NULL ? a_node->branch_size : 0)
 143     + 1 + (c_node != NULL ? c_node->branch_size : 0);
 144   d_node->branch_size =
 145     b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
 146
 147   return d_node;
 148 }
 149
 150 /* Rotate right a subtree.
 151
 152                            D                     B
 153                          /   \                 /   \
 154                        B       E     -->     A       D
 155                       / \                           / \
 156                      A   C                         C   E
 157
 158    Change the tree structure, update the branch sizes.
 159    The caller must update the colors and register B as child of its parent.  */
 160 static inline gl_list_node_t
 161 rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
 162 {
 163   gl_list_node_t a_node = b_node->left;
 164   gl_list_node_t c_node = b_node->right;
 165   gl_list_node_t e_node = d_node->right;
 166
 167   d_node->left = c_node;
 168   b_node->right = d_node;
 169
 170   b_node->parent = d_node->parent;
 171   d_node->parent = b_node;
 172   if (c_node != NULL)
 173     c_node->parent = d_node;
 174
 175   d_node->branch_size =
 176     (c_node != NULL ? c_node->branch_size : 0)
 177     + 1 + (e_node != NULL ? e_node->branch_size : 0);
 178   b_node->branch_size =
 179     (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
 180
 181   return b_node;
 182 }
 183
 184 /* Ensure the tree is balanced, after an insertion operation.
 185    Also assigns node->color.
 186    parent is the given node's parent, known to be non-NULL.  */
 187 static void
 188 rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
 189 {
 190   for (;;)
 191     {
 192       /* At this point, parent = node->parent != NULL.
 193          Think of node->color being RED (although node->color is not yet
 194          assigned.)  */
 195       gl_list_node_t grandparent;
 196       gl_list_node_t uncle;
 197
 198       if (parent->color == BLACK)
 199         {
 200           /* A RED color for node is acceptable.  */
 201           node->color = RED;
 202           return;
 203         }
 204
 205       grandparent = parent->parent;
 206       /* Since parent is RED, we know that
 207          grandparent is != NULL and colored BLACK.  */
 208
 209       if (grandparent->left == parent)
 210         uncle = grandparent->right;
 211       else if (grandparent->right == parent)
 212         uncle = grandparent->left;
 213       else
 214         abort ();
 215
 216       if (uncle != NULL && uncle->color == RED)
 217         {
 218           /* Change grandparent from BLACK to RED, and
 219              change parent and uncle from RED to BLACK.
 220              This makes it acceptable for node to be RED.  */
 221           node->color = RED;
 222           parent->color = uncle->color = BLACK;
 223           node = grandparent;
 224         }
 225       else
 226         {
 227           /* grandparent and uncle are BLACK.  parent is RED.  node wants
 228              to be RED too.
 229              In this case, recoloring is not sufficient.  Need to perform
 230              one or two rotations.  */
 231           gl_list_node_t *grandparentp;
 232
 233           if (grandparent->parent == NULL)
 234             grandparentp = &list->root;
 235           else if (grandparent->parent->left == grandparent)
 236             grandparentp = &grandparent->parent->left;
 237           else if (grandparent->parent->right == grandparent)
 238             grandparentp = &grandparent->parent->right;
 239           else
 240             abort ();
 241
 242           if (grandparent->left == parent)
 243             {
 244               if (parent->right == node)
 245                 {
 246                   /* Rotation between node and parent.  */
 247                   grandparent->left = rotate_left (parent, node);
 248                   node = parent;
 249                   parent = grandparent->left;
 250                 }
 251               /* grandparent and uncle are BLACK.  parent and node want to be
 252                  RED.  parent = grandparent->left.  node = parent->left.
 253
 254                       grandparent              parent
 255                          bh+1                   bh+1
 256                          /   \                 /   \
 257                      parent  uncle    -->   node  grandparent
 258                       bh      bh             bh      bh
 259                       / \                           / \
 260                    node  C                         C  uncle
 261                     bh   bh                       bh    bh
 262                */
 263               *grandparentp = rotate_right (parent, grandparent);
 264               parent->color = BLACK;
 265               node->color = grandparent->color = RED;
 266             }
 267           else /* grandparent->right == parent */
 268             {
 269               if (parent->left == node)
 270                 {
 271                   /* Rotation between node and parent.  */
 272                   grandparent->right = rotate_right (node, parent);
 273                   node = parent;
 274                   parent = grandparent->right;
 275                 }
 276               /* grandparent and uncle are BLACK.  parent and node want to be
 277                  RED.  parent = grandparent->right.  node = parent->right.
 278
 279                     grandparent                    parent
 280                        bh+1                         bh+1
 281                        /   \                       /   \
 282                    uncle  parent     -->   grandparent  node
 283                      bh     bh                  bh       bh
 284                             / \                 / \
 285                            C  node          uncle  C
 286                           bh   bh            bh    bh
 287                */
 288               *grandparentp = rotate_left (grandparent, parent);
 289               parent->color = BLACK;
 290               node->color = grandparent->color = RED;
 291             }
 292           return;
 293         }
 294
 295       /* Start again with a new (node, parent) pair.  */
 296       parent = node->parent;
 297
 298       if (parent == NULL)
 299         {
 300           /* Change node's color from RED to BLACK.  This increases the
 301              tree's black-height.  */
 302           node->color = BLACK;
 303           return;
 304         }
 305     }
 306 }
 307
 308 /* Ensure the tree is balanced, after a deletion operation.
 309    CHILD was a grandchild of PARENT and is now its child.  Between them,
 310    a black node was removed.  CHILD is also black, or NULL.
 311    (CHILD can also be NULL.  But PARENT is non-NULL.)  */
 312 static void
 313 rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
 314 {
 315   for (;;)
 316     {
 317       /* At this point, we reduced the black-height of the CHILD subtree by 1.
 318          To make up, either look for a possibility to turn a RED to a BLACK
 319          node, or try to reduce the black-height tree of CHILD's sibling
 320          subtree as well.  */
 321       gl_list_node_t *parentp;
 322
 323       if (parent->parent == NULL)
 324         parentp = &list->root;
 325       else if (parent->parent->left == parent)
 326         parentp = &parent->parent->left;
 327       else if (parent->parent->right == parent)
 328         parentp = &parent->parent->right;
 329       else
 330         abort ();
 331
 332       if (parent->left == child)
 333         {
 334           gl_list_node_t sibling = parent->right;
 335           /* sibling's black-height is >= 1.  In particular,
 336              sibling != NULL.
 337
 338                       parent
 339                        /   \
 340                    child  sibling
 341                      bh    bh+1
 342            */
 343
 344           if (sibling->color == RED)
 345             {
 346               /* sibling is RED, hence parent is BLACK and sibling's children
 347                  are non-NULL and BLACK.
 348
 349                       parent                       sibling
 350                        bh+2                         bh+2
 351                        /   \                        /   \
 352                    child  sibling     -->       parent    SR
 353                      bh    bh+1                  bh+1    bh+1
 354                             / \                  / \
 355                           SL   SR            child  SL
 356                          bh+1 bh+1             bh  bh+1
 357                */
 358               *parentp = rotate_left (parent, sibling);
 359               parent->color = RED;
 360               sibling->color = BLACK;
 361
 362               /* Concentrate on the subtree of parent.  The new sibling is
 363                  one of the old sibling's children, and known to be BLACK.  */
 364               parentp = &sibling->left;
 365               sibling = parent->right;
 366             }
 367           /* Now we know that sibling is BLACK.
 368
 369                       parent
 370                        /   \
 371                    child  sibling
 372                      bh    bh+1
 373            */
 374           if (sibling->right != NULL && sibling->right->color == RED)
 375             {
 376               /*
 377                       parent                     sibling
 378                      bh+1|bh+2                  bh+1|bh+2
 379                        /   \                      /   \
 380                    child  sibling    -->      parent    SR
 381                      bh    bh+1                bh+1    bh+1
 382                             / \                / \
 383                           SL   SR           child  SL
 384                           bh   bh             bh   bh
 385                */
 386               *parentp = rotate_left (parent, sibling);
 387               sibling->color = parent->color;
 388               parent->color = BLACK;
 389               sibling->right->color = BLACK;
 390               return;
 391             }
 392           else if (sibling->left != NULL && sibling->left->color == RED)
 393             {
 394               /*
 395                       parent                   parent
 396                      bh+1|bh+2                bh+1|bh+2
 397                        /   \                    /   \
 398                    child  sibling    -->    child    SL
 399                      bh    bh+1               bh    bh+1
 400                             / \                     /  \
 401                           SL   SR                 SLL  sibling
 402                           bh   bh                 bh     bh
 403                          /  \                           /   \
 404                        SLL  SLR                       SLR    SR
 405                        bh    bh                       bh     bh
 406
 407                  where SLL, SLR, SR are all black.
 408                */
 409               parent->right = rotate_right (sibling->left, sibling);
 410               /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
 411               sibling->color = RED;
 412               sibling = parent->right;
 413               sibling->color = BLACK;
 414
 415               /* Now do as in the previous case.  */
 416               *parentp = rotate_left (parent, sibling);
 417               sibling->color = parent->color;
 418               parent->color = BLACK;
 419               sibling->right->color = BLACK;
 420               return;
 421             }
 422           else
 423             {
 424               if (parent->color == BLACK)
 425                 {
 426                   /* Change sibling from BLACK to RED.  Then the entire
 427                      subtree at parent has decreased its black-height.
 428                               parent                   parent
 429                                bh+2                     bh+1
 430                                /   \                    /   \
 431                            child  sibling    -->    child  sibling
 432                              bh    bh+1               bh     bh
 433                    */
 434                   sibling->color = RED;
 435
 436                   child = parent;
 437                 }
 438               else
 439                 {
 440                   /* Change parent from RED to BLACK, but compensate by
 441                      changing sibling from BLACK to RED.
 442                               parent                   parent
 443                                bh+1                     bh+1
 444                                /   \                    /   \
 445                            child  sibling    -->    child  sibling
 446                              bh    bh+1               bh     bh
 447                    */
 448                   parent->color = BLACK;
 449                   sibling->color = RED;
 450                   return;
 451                 }
 452             }
 453         }
 454       else if (parent->right == child)
 455         {
 456           gl_list_node_t sibling = parent->left;
 457           /* sibling's black-height is >= 1.  In particular,
 458              sibling != NULL.
 459
 460                       parent
 461                        /   \
 462                   sibling  child
 463                     bh+1     bh
 464            */
 465
 466           if (sibling->color == RED)
 467             {
 468               /* sibling is RED, hence parent is BLACK and sibling's children
 469                  are non-NULL and BLACK.
 470
 471                       parent                 sibling
 472                        bh+2                    bh+2
 473                        /   \                  /   \
 474                   sibling  child    -->     SR    parent
 475                     bh+1     ch            bh+1    bh+1
 476                     / \                            / \
 477                   SL   SR                        SL  child
 478                  bh+1 bh+1                      bh+1   bh
 479                */
 480               *parentp = rotate_right (sibling, parent);
 481               parent->color = RED;
 482               sibling->color = BLACK;
 483
 484               /* Concentrate on the subtree of parent.  The new sibling is
 485                  one of the old sibling's children, and known to be BLACK.  */
 486               parentp = &sibling->right;
 487               sibling = parent->left;
 488             }
 489           /* Now we know that sibling is BLACK.
 490
 491                       parent
 492                        /   \
 493                   sibling  child
 494                     bh+1     bh
 495            */
 496           if (sibling->left != NULL && sibling->left->color == RED)
 497             {
 498               /*
 499                        parent                 sibling
 500                       bh+1|bh+2              bh+1|bh+2
 501                         /   \                  /   \
 502                    sibling  child    -->     SL   parent
 503                      bh+1     bh            bh+1   bh+1
 504                      / \                           / \
 505                    SL   SR                       SR  child
 506                    bh   bh                       bh    bh
 507                */
 508               *parentp = rotate_right (sibling, parent);
 509               sibling->color = parent->color;
 510               parent->color = BLACK;
 511               sibling->left->color = BLACK;
 512               return;
 513             }
 514           else if (sibling->right != NULL && sibling->right->color == RED)
 515             {
 516               /*
 517                       parent                       parent
 518                      bh+1|bh+2                    bh+1|bh+2
 519                        /   \                        /   \
 520                    sibling  child    -->          SR    child
 521                     bh+1      bh                 bh+1     bh
 522                      / \                         /  \
 523                    SL   SR                  sibling  SRR
 524                    bh   bh                    bh      bh
 525                        /  \                  /   \
 526                      SRL  SRR               SL   SRL
 527                      bh    bh               bh    bh
 528
 529                  where SL, SRL, SRR are all black.
 530                */
 531               parent->left = rotate_left (sibling, sibling->right);
 532               /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
 533               sibling->color = RED;
 534               sibling = parent->left;
 535               sibling->color = BLACK;
 536
 537               /* Now do as in the previous case.  */
 538               *parentp = rotate_right (sibling, parent);
 539               sibling->color = parent->color;
 540               parent->color = BLACK;
 541               sibling->left->color = BLACK;
 542               return;
 543             }
 544           else
 545             {
 546               if (parent->color == BLACK)
 547                 {
 548                   /* Change sibling from BLACK to RED.  Then the entire
 549                      subtree at parent has decreased its black-height.
 550                               parent                   parent
 551                                bh+2                     bh+1
 552                                /   \                    /   \
 553                            sibling  child    -->    sibling  child
 554                             bh+1      bh              bh       bh
 555                    */
 556                   sibling->color = RED;
 557
 558                   child = parent;
 559                 }
 560               else
 561                 {
 562                   /* Change parent from RED to BLACK, but compensate by
 563                      changing sibling from BLACK to RED.
 564                               parent                   parent
 565                                bh+1                     bh+1
 566                                /   \                    /   \
 567                            sibling  child    -->    sibling  child
 568                             bh+1      bh              bh       bh
 569                    */
 570                   parent->color = BLACK;
 571                   sibling->color = RED;
 572                   return;
 573                 }
 574             }
 575         }
 576       else
 577         abort ();
 578
 579       /* Start again with a new (child, parent) pair.  */
 580       parent = child->parent;
 581
 582 #if 0 /* Already handled.  */
 583       if (child != NULL && child->color == RED)
 584         {
 585           child->color = BLACK;
 586           return;
 587         }
 588 #endif
 589
 590       if (parent == NULL)
 591         return;
 592     }
 593 }
 594
 595 static gl_list_node_t
 596 gl_tree_add_first (gl_list_t list, const void *elt)
 597 {
 598   /* Create new node.  */
 599   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 600
 601   new_node->left = NULL;
 602   new_node->right = NULL;
 603   new_node->branch_size = 1;
 604   new_node->value = elt;
 605 #if WITH_HASHTABLE
 606   new_node->h.hashcode =
 607     (list->base.hashcode_fn != NULL
 608      ? list->base.hashcode_fn (new_node->value)
 609      : (size_t)(uintptr_t) new_node->value);
 610 #endif
 611
 612   /* Add it to the tree.  */
 613   if (list->root == NULL)
 614     {
 615       new_node->color = BLACK;
 616       list->root = new_node;
 617       new_node->parent = NULL;
 618     }
 619   else
 620     {
 621       gl_list_node_t node;
 622
 623       for (node = list->root; node->left != NULL; )
 624         node = node->left;
 625
 626       node->left = new_node;
 627       new_node->parent = node;
 628
 629       /* Update branch_size fields of the parent nodes.  */
 630       {
 631         gl_list_node_t p;
 632
 633         for (p = node; p != NULL; p = p->parent)
 634           p->branch_size++;
 635       }
 636
 637       /* Color and rebalance.  */
 638       rebalance_after_add (list, new_node, node);
 639     }
 640
 641 #if WITH_HASHTABLE
 642   /* Add node to the hash table.
 643      Note that this is only possible _after_ the node has been added to the
 644      tree structure, because add_to_bucket() uses node_position().  */
 645   add_to_bucket (list, new_node);
 646   hash_resize_after_add (list);
 647 #endif
 648
 649   return new_node;
 650 }
 651
 652 static gl_list_node_t
 653 gl_tree_add_last (gl_list_t list, const void *elt)
 654 {
 655   /* Create new node.  */
 656   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 657
 658   new_node->left = NULL;
 659   new_node->right = NULL;
 660   new_node->branch_size = 1;
 661   new_node->value = elt;
 662 #if WITH_HASHTABLE
 663   new_node->h.hashcode =
 664     (list->base.hashcode_fn != NULL
 665      ? list->base.hashcode_fn (new_node->value)
 666      : (size_t)(uintptr_t) new_node->value);
 667 #endif
 668
 669   /* Add it to the tree.  */
 670   if (list->root == NULL)
 671     {
 672       new_node->color = BLACK;
 673       list->root = new_node;
 674       new_node->parent = NULL;
 675     }
 676   else
 677     {
 678       gl_list_node_t node;
 679
 680       for (node = list->root; node->right != NULL; )
 681         node = node->right;
 682
 683       node->right = new_node;
 684       new_node->parent = node;
 685
 686       /* Update branch_size fields of the parent nodes.  */
 687       {
 688         gl_list_node_t p;
 689
 690         for (p = node; p != NULL; p = p->parent)
 691           p->branch_size++;
 692       }
 693
 694       /* Color and rebalance.  */
 695       rebalance_after_add (list, new_node, node);
 696     }
 697
 698 #if WITH_HASHTABLE
 699   /* Add node to the hash table.
 700      Note that this is only possible _after_ the node has been added to the
 701      tree structure, because add_to_bucket() uses node_position().  */
 702   add_to_bucket (list, new_node);
 703   hash_resize_after_add (list);
 704 #endif
 705
 706   return new_node;
 707 }
 708
 709 static gl_list_node_t
 710 gl_tree_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 711 {
 712   /* Create new node.  */
 713   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 714
 715   new_node->left = NULL;
 716   new_node->right = NULL;
 717   new_node->branch_size = 1;
 718   new_node->value = elt;
 719 #if WITH_HASHTABLE
 720   new_node->h.hashcode =
 721     (list->base.hashcode_fn != NULL
 722      ? list->base.hashcode_fn (new_node->value)
 723      : (size_t)(uintptr_t) new_node->value);
 724 #endif
 725
 726   /* Add it to the tree.  */
 727   if (node->left == NULL)
 728     node->left = new_node;
 729   else
 730     {
 731       for (node = node->left; node->right != NULL; )
 732         node = node->right;
 733       node->right = new_node;
 734     }
 735   new_node->parent = node;
 736
 737   /* Update branch_size fields of the parent nodes.  */
 738   {
 739     gl_list_node_t p;
 740
 741     for (p = node; p != NULL; p = p->parent)
 742       p->branch_size++;
 743   }
 744
 745   /* Color and rebalance.  */
 746   rebalance_after_add (list, new_node, node);
 747
 748 #if WITH_HASHTABLE
 749   /* Add node to the hash table.
 750      Note that this is only possible _after_ the node has been added to the
 751      tree structure, because add_to_bucket() uses node_position().  */
 752   add_to_bucket (list, new_node);
 753   hash_resize_after_add (list);
 754 #endif
 755
 756   return new_node;
 757 }
 758
 759 static gl_list_node_t
 760 gl_tree_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 761 {
 762   /* Create new node.  */
 763   gl_list_node_t new_node = XMALLOC (struct gl_list_node_impl);
 764
 765   new_node->left = NULL;
 766   new_node->right = NULL;
 767   new_node->branch_size = 1;
 768   new_node->value = elt;
 769 #if WITH_HASHTABLE
 770   new_node->h.hashcode =
 771     (list->base.hashcode_fn != NULL
 772      ? list->base.hashcode_fn (new_node->value)
 773      : (size_t)(uintptr_t) new_node->value);
 774 #endif
 775
 776   /* Add it to the tree.  */
 777   if (node->right == NULL)
 778     node->right = new_node;
 779   else
 780     {
 781       for (node = node->right; node->left != NULL; )
 782         node = node->left;
 783       node->left = new_node;
 784     }
 785   new_node->parent = node;
 786
 787   /* Update branch_size fields of the parent nodes.  */
 788   {
 789     gl_list_node_t p;
 790
 791     for (p = node; p != NULL; p = p->parent)
 792       p->branch_size++;
 793   }
 794
 795   /* Color and rebalance.  */
 796   rebalance_after_add (list, new_node, node);
 797
 798 #if WITH_HASHTABLE
 799   /* Add node to the hash table.
 800      Note that this is only possible _after_ the node has been added to the
 801      tree structure, because add_to_bucket() uses node_position().  */
 802   add_to_bucket (list, new_node);
 803   hash_resize_after_add (list);
 804 #endif
 805
 806   return new_node;
 807 }
 808
 809 static bool
 810 gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
 811 {
 812   gl_list_node_t parent;
 813
 814 #if WITH_HASHTABLE
 815   /* Remove node from the hash table.
 816      Note that this is only possible _before_ the node is removed from the
 817      tree structure, because remove_from_bucket() uses node_position().  */
 818   remove_from_bucket (list, node);
 819 #endif
 820
 821   parent = node->parent;
 822
 823   if (node->left == NULL)
 824     {
 825       /* Replace node with node->right.  */
 826       gl_list_node_t child = node->right;
 827
 828       if (child != NULL)
 829         {
 830           child->parent = parent;
 831           /* Since node->left == NULL, child must be RED and of height 1,
 832              hence node must have been BLACK.  Recolor the child.  */
 833           child->color = BLACK;
 834         }
 835       if (parent == NULL)
 836         list->root = child;
 837       else
 838         {
 839           if (parent->left == node)
 840             parent->left = child;
 841           else /* parent->right == node */
 842             parent->right = child;
 843
 844           /* Update branch_size fields of the parent nodes.  */
 845           {
 846             gl_list_node_t p;
 847
 848             for (p = parent; p != NULL; p = p->parent)
 849               p->branch_size--;
 850           }
 851
 852           if (child == NULL && node->color == BLACK)
 853             rebalance_after_remove (list, child, parent);
 854         }
 855     }
 856   else if (node->right == NULL)
 857     {
 858       /* It is not absolutely necessary to treat this case.  But the more
 859          general case below is more complicated, hence slower.  */
 860       /* Replace node with node->left.  */
 861       gl_list_node_t child = node->left;
 862
 863       child->parent = parent;
 864       /* Since node->right == NULL, child must be RED and of height 1,
 865          hence node must have been BLACK.  Recolor the child.  */
 866       child->color = BLACK;
 867       if (parent == NULL)
 868         list->root = child;
 869       else
 870         {
 871           if (parent->left == node)
 872             parent->left = child;
 873           else /* parent->right == node */
 874             parent->right = child;
 875
 876           /* Update branch_size fields of the parent nodes.  */
 877           {
 878             gl_list_node_t p;
 879
 880             for (p = parent; p != NULL; p = p->parent)
 881               p->branch_size--;
 882           }
 883         }
 884     }
 885   else
 886     {
 887       /* Replace node with the rightmost element of the node->left subtree.  */
 888       gl_list_node_t subst;
 889       gl_list_node_t subst_parent;
 890       gl_list_node_t child;
 891       color_t removed_color;
 892
 893       for (subst = node->left; subst->right != NULL; )
 894         subst = subst->right;
 895
 896       subst_parent = subst->parent;
 897
 898       child = subst->left;
 899
 900       removed_color = subst->color;
 901
 902       /* The case subst_parent == node is special:  If we do nothing special,
 903          we get confusion about node->left, subst->left and child->parent.
 904            subst_parent == node
 905            <==> The 'for' loop above terminated immediately.
 906            <==> subst == subst_parent->left
 907                 [otherwise subst == subst_parent->right]
 908          In this case, we would need to first set
 909            child->parent = node; node->left = child;
 910          and later - when we copy subst into node's position - again
 911            child->parent = subst; subst->left = child;
 912          Altogether a no-op.  */
 913       if (subst_parent != node)
 914         {
 915           if (child != NULL)
 916             child->parent = subst_parent;
 917           subst_parent->right = child;
 918         }
 919
 920       /* Update branch_size fields of the parent nodes.  */
 921       {
 922         gl_list_node_t p;
 923
 924         for (p = subst_parent; p != NULL; p = p->parent)
 925           p->branch_size--;
 926       }
 927
 928       /* Copy subst into node's position.
 929          (This is safer than to copy subst's value into node, keep node in
 930          place, and free subst.)  */
 931       if (subst_parent != node)
 932         {
 933           subst->left = node->left;
 934           subst->left->parent = subst;
 935         }
 936       subst->right = node->right;
 937       subst->right->parent = subst;
 938       subst->color = node->color;
 939       subst->branch_size = node->branch_size;
 940       subst->parent = parent;
 941       if (parent == NULL)
 942         list->root = subst;
 943       else if (parent->left == node)
 944         parent->left = subst;
 945       else /* parent->right == node */
 946         parent->right = subst;
 947
 948       if (removed_color == BLACK)
 949         {
 950           if (child != NULL && child->color == RED)
 951             /* Recolor the child.  */
 952             child->color = BLACK;
 953           else
 954             /* Rebalancing starts at child's parent, that is subst_parent -
 955                except when subst_parent == node.  In this case, we need to use
 956                its replacement, subst.  */
 957             rebalance_after_remove (list, child,
 958                                     subst_parent != node ? subst_parent : subst);
 959         }
 960     }
 961
 962   free (node);
 963   return true;
 964 }