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