lib/gl_anyrbtree_list2.h

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