lib/gl_anyrbtree_list2.h

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