lib/gl_anyrbtree_list2.h

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