lib/gl_anyavltree_list2.h

   1 /* Sequential list data type implemented by a binary tree.
   2    Copyright (C) 2006-2007, 2009-2024 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2006.
   4
   5    This file is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU Lesser General Public License as
   7    published by the Free Software Foundation; either version 2.1 of the
   8    License, or (at your option) any later version.
   9
  10    This file 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 Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 /* Common code of gl_avltree_list.c and gl_avltreehash_list.c.  */
  19
  20 /* -------------------------- gl_list_t Data Type -------------------------- */
  21
  22 /* Creates a subtree for count >= 1 elements.
  23    Its height is h where 2^(h-1) <= count <= 2^h - 1.
  24    Returns NULL upon out-of-memory.  */
  25 static gl_list_node_t
  26 create_subtree_with_contents (size_t count, const void **contents)
  27 {
  28   size_t half1 = (count - 1) / 2;
  29   size_t half2 = count / 2;
  30   /* Note: half1 + half2 = count - 1.  */
  31   gl_list_node_t node =
  32     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
  33   if (node == NULL)
  34     return NULL;
  35
  36   if (half1 > 0)
  37     {
  38       node->left = create_subtree_with_contents (half1, contents);
  39       if (node->left == NULL)
  40         goto fail1;
  41       node->left->parent = node;
  42     }
  43   else
  44     node->left = NULL;
  45
  46   node->value = contents[half1];
  47
  48   if (half2 > 0)
  49     {
  50       node->right = create_subtree_with_contents (half2, contents + half1 + 1);
  51       if (node->right == NULL)
  52         goto fail2;
  53       node->right->parent = node;
  54     }
  55   else
  56     node->right = NULL;
  57
  58   /* balance is 0, except when count is a power of two and > 1.
  59      Reason: half1 <= half2 <= half1 + 1, and the two branches can have
  60      different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
  61      case, count = half1 + half2 + 1 = 2^(h+1).  */
  62   node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
  63
  64   node->branch_size = count;
  65
  66   return node;
  67
  68  fail2:
  69   if (node->left != NULL)
  70     free_subtree (node->left);
  71  fail1:
  72   free (node);
  73   return NULL;
  74 }
  75
  76 static gl_list_t
  77 gl_tree_nx_create (gl_list_implementation_t implementation,
  78                    gl_listelement_equals_fn equals_fn,
  79                    gl_listelement_hashcode_fn hashcode_fn,
  80                    gl_listelement_dispose_fn dispose_fn,
  81                    bool allow_duplicates,
  82                    size_t count, const void **contents)
  83 {
  84   struct gl_list_impl *list =
  85     (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
  86
  87   if (list == NULL)
  88     return NULL;
  89
  90   list->base.vtable = implementation;
  91   list->base.equals_fn = equals_fn;
  92   list->base.hashcode_fn = hashcode_fn;
  93   list->base.dispose_fn = dispose_fn;
  94   list->base.allow_duplicates = allow_duplicates;
  95 #if WITH_HASHTABLE
  96   {
  97     size_t estimate = xsum (count, count / 2); /* 1.5 * count */
  98     if (estimate < 10)
  99       estimate = 10;
 100     list->table_size = next_prime (estimate);
 101     if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
 102       goto fail1;
 103     list->table =
 104       (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
 105     if (list->table == NULL)
 106       goto fail1;
 107   }
 108 #endif
 109   if (count > 0)
 110     {
 111       list->root = create_subtree_with_contents (count, contents);
 112       if (list->root == NULL)
 113         goto fail2;
 114       list->root->parent = NULL;
 115
 116 #if WITH_HASHTABLE
 117       /* Now that the tree is built, node_position() works.  Now we can
 118          add the nodes to the hash table.  */
 119       if (add_nodes_to_buckets (list) < 0)
 120         goto fail3;
 121 #endif
 122     }
 123   else
 124     list->root = NULL;
 125
 126   return list;
 127
 128 #if WITH_HASHTABLE
 129  fail3:
 130   free_subtree (list->root);
 131 #endif
 132  fail2:
 133 #if WITH_HASHTABLE
 134   free (list->table);
 135  fail1:
 136 #endif
 137   free (list);
 138   return NULL;
 139 }
 140
 141 /* Ensures the tree is balanced, after an insertion or deletion operation.
 142    The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
 143    PARENT = NODE->parent.  (NODE can also be NULL.  But PARENT is non-NULL.)
 144    Rotation operations are performed starting at PARENT (not NODE itself!).  */
 145 static void
 146 rebalance (gl_list_t list,
 147            gl_list_node_t node, int height_diff, gl_list_node_t parent)
 148 {
 149   for (;;)
 150     {
 151       gl_list_node_t child;
 152       int previous_balance;
 153       int balance_diff;
 154       gl_list_node_t nodeleft;
 155       gl_list_node_t noderight;
 156
 157       child = node;
 158       node = parent;
 159
 160       previous_balance = node->balance;
 161
 162       /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
 163          branch's height has increased by 1 or the left branch's height has
 164          decreased by 1, -1 if the right branch's height has decreased by 1 or
 165          the left branch's height has increased by 1, 0 if no height change.  */
 166       if (node->left != NULL || node->right != NULL)
 167         balance_diff = (child == node->right ? height_diff : -height_diff);
 168       else
 169         /* Special case where above formula doesn't work, because the caller
 170            didn't tell whether node's left or right branch shrunk from height 1
 171            to NULL.  */
 172         balance_diff = - previous_balance;
 173
 174       node->balance += balance_diff;
 175       if (balance_diff == previous_balance)
 176         {
 177           /* node->balance is outside the range [-1,1].  Must rotate.  */
 178           gl_list_node_t *nodep;
 179
 180           if (node->parent == NULL)
 181             /* node == list->root */
 182             nodep = &list->root;
 183           else if (node->parent->left == node)
 184             nodep = &node->parent->left;
 185           else if (node->parent->right == node)
 186             nodep = &node->parent->right;
 187           else
 188             abort ();
 189
 190           nodeleft = node->left;
 191           noderight = node->right;
 192
 193           if (balance_diff < 0)
 194             {
 195               /* node->balance = -2.  The subtree is heavier on the left side.
 196                  Rotate from left to right:
 197
 198                                   *
 199                                 /   \
 200                              h+2      h
 201                */
 202               gl_list_node_t nodeleftleft = nodeleft->left;
 203               gl_list_node_t nodeleftright = nodeleft->right;
 204               if (nodeleft->balance <= 0)
 205                 {
 206                   /*
 207                               *                    h+2|h+3
 208                             /   \                  /    \
 209                          h+2      h      -->      /   h+1|h+2
 210                          / \                      |    /    \
 211                        h+1 h|h+1                 h+1  h|h+1  h
 212                    */
 213                   node->left = nodeleftright;
 214                   nodeleft->right = node;
 215
 216                   nodeleft->parent = node->parent;
 217                   node->parent = nodeleft;
 218                   if (nodeleftright != NULL)
 219                     nodeleftright->parent = node;
 220
 221                   nodeleft->balance += 1;
 222                   node->balance = - nodeleft->balance;
 223
 224                   node->branch_size =
 225                     (nodeleftright != NULL ? nodeleftright->branch_size : 0)
 226                     + 1 + (noderight != NULL ? noderight->branch_size : 0);
 227                   nodeleft->branch_size =
 228                     nodeleftleft->branch_size + 1 + node->branch_size;
 229
 230                   *nodep = nodeleft;
 231                   height_diff = (height_diff < 0
 232                                  ? /* noderight's height had been decremented from
 233                                       h+1 to h.  The subtree's height changes from
 234                                       h+3 to h+2|h+3.  */
 235                                    nodeleft->balance - 1
 236                                  : /* nodeleft's height had been incremented from
 237                                       h+1 to h+2.  The subtree's height changes from
 238                                       h+2 to h+2|h+3.  */
 239                                    nodeleft->balance);
 240                 }
 241               else
 242                 {
 243                   /*
 244                             *                     h+2
 245                           /   \                 /     \
 246                        h+2      h      -->    h+1     h+1
 247                        / \                    / \     / \
 248                       h  h+1                 h   L   R   h
 249                          / \
 250                         L   R
 251
 252                    */
 253                   gl_list_node_t L = nodeleft->right = nodeleftright->left;
 254                   gl_list_node_t R = node->left = nodeleftright->right;
 255                   nodeleftright->left = nodeleft;
 256                   nodeleftright->right = node;
 257
 258                   nodeleftright->parent = node->parent;
 259                   if (L != NULL)
 260                     L->parent = nodeleft;
 261                   if (R != NULL)
 262                     R->parent = node;
 263                   nodeleft->parent = nodeleftright;
 264                   node->parent = nodeleftright;
 265
 266                   nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
 267                   node->balance = (nodeleftright->balance < 0 ? 1 : 0);
 268                   nodeleftright->balance = 0;
 269
 270                   nodeleft->branch_size =
 271                     (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
 272                     + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
 273                   node->branch_size =
 274                     (node->left != NULL ? node->left->branch_size : 0)
 275                     + 1 + (node->right != NULL ? node->right->branch_size : 0);
 276                   nodeleftright->branch_size =
 277                     nodeleft->branch_size + 1 + node->branch_size;
 278
 279                   *nodep = nodeleftright;
 280                   height_diff = (height_diff < 0
 281                                  ? /* noderight's height had been decremented from
 282                                       h+1 to h.  The subtree's height changes from
 283                                       h+3 to h+2.  */
 284                                    -1
 285                                  : /* nodeleft's height had been incremented from
 286                                       h+1 to h+2.  The subtree's height changes from
 287                                       h+2 to h+2.  */
 288                                    0);
 289                 }
 290             }
 291           else
 292             {
 293               /* node->balance = 2.  The subtree is heavier on the right side.
 294                  Rotate from right to left:
 295
 296                                   *
 297                                 /   \
 298                               h      h+2
 299                */
 300               gl_list_node_t noderightleft = noderight->left;
 301               gl_list_node_t noderightright = noderight->right;
 302               if (noderight->balance >= 0)
 303                 {
 304                   /*
 305                               *                    h+2|h+3
 306                             /   \                   /    \
 307                           h      h+2     -->    h+1|h+2   \
 308                                  / \            /    \    |
 309                              h|h+1 h+1         h   h|h+1 h+1
 310                    */
 311                   node->right = noderightleft;
 312                   noderight->left = node;
 313
 314                   noderight->parent = node->parent;
 315                   node->parent = noderight;
 316                   if (noderightleft != NULL)
 317                     noderightleft->parent = node;
 318
 319                   noderight->balance -= 1;
 320                   node->balance = - noderight->balance;
 321
 322                   node->branch_size =
 323                     (nodeleft != NULL ? nodeleft->branch_size : 0)
 324                     + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
 325                   noderight->branch_size =
 326                     node->branch_size + 1 + noderightright->branch_size;
 327
 328                   *nodep = noderight;
 329                   height_diff = (height_diff < 0
 330                                  ? /* nodeleft's height had been decremented from
 331                                       h+1 to h.  The subtree's height changes from
 332                                       h+3 to h+2|h+3.  */
 333                                    - noderight->balance - 1
 334                                  : /* noderight's height had been incremented from
 335                                       h+1 to h+2.  The subtree's height changes from
 336                                       h+2 to h+2|h+3.  */
 337                                    - noderight->balance);
 338                 }
 339               else
 340                 {
 341                   /*
 342                             *                    h+2
 343                           /   \                /     \
 344                         h      h+2    -->    h+1     h+1
 345                                / \           / \     / \
 346                              h+1  h         h   L   R   h
 347                              / \
 348                             L   R
 349
 350                    */
 351                   gl_list_node_t L = node->right = noderightleft->left;
 352                   gl_list_node_t R = noderight->left = noderightleft->right;
 353                   noderightleft->left = node;
 354                   noderightleft->right = noderight;
 355
 356                   noderightleft->parent = node->parent;
 357                   if (L != NULL)
 358                     L->parent = node;
 359                   if (R != NULL)
 360                     R->parent = noderight;
 361                   node->parent = noderightleft;
 362                   noderight->parent = noderightleft;
 363
 364                   node->balance = (noderightleft->balance > 0 ? -1 : 0);
 365                   noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
 366                   noderightleft->balance = 0;
 367
 368                   node->branch_size =
 369                     (node->left != NULL ? node->left->branch_size : 0)
 370                     + 1 + (node->right != NULL ? node->right->branch_size : 0);
 371                   noderight->branch_size =
 372                     (noderight->left != NULL ? noderight->left->branch_size : 0)
 373                     + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
 374                   noderightleft->branch_size =
 375                     node->branch_size + 1 + noderight->branch_size;
 376
 377                   *nodep = noderightleft;
 378                   height_diff = (height_diff < 0
 379                                  ? /* nodeleft's height had been decremented from
 380                                       h+1 to h.  The subtree's height changes from
 381                                       h+3 to h+2.  */
 382                                    -1
 383                                  : /* noderight's height had been incremented from
 384                                       h+1 to h+2.  The subtree's height changes from
 385                                       h+2 to h+2.  */
 386                                    0);
 387                 }
 388             }
 389           node = *nodep;
 390         }
 391       else
 392         {
 393           /* No rotation needed.  Only propagation of the height change to the
 394              next higher level.  */
 395           if (height_diff < 0)
 396             height_diff = (previous_balance == 0 ? 0 : -1);
 397           else
 398             height_diff = (node->balance == 0 ? 0 : 1);
 399         }
 400
 401       if (height_diff == 0)
 402         break;
 403
 404       parent = node->parent;
 405       if (parent == NULL)
 406         break;
 407     }
 408 }
 409
 410 static void
 411 gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
 412 {
 413   gl_list_node_t parent = node->parent;
 414
 415   if (node->left == NULL)
 416     {
 417       /* Replace node with node->right.  */
 418       gl_list_node_t child = node->right;
 419
 420       if (child != NULL)
 421         child->parent = parent;
 422       if (parent == NULL)
 423         list->root = child;
 424       else
 425         {
 426           if (parent->left == node)
 427             parent->left = child;
 428           else /* parent->right == node */
 429             parent->right = child;
 430
 431           /* Update branch_size fields of the parent nodes.  */
 432           {
 433             gl_list_node_t p;
 434
 435             for (p = parent; p != NULL; p = p->parent)
 436               p->branch_size--;
 437           }
 438
 439           rebalance (list, child, -1, parent);
 440         }
 441     }
 442   else if (node->right == NULL)
 443     {
 444       /* It is not absolutely necessary to treat this case.  But the more
 445          general case below is more complicated, hence slower.  */
 446       /* Replace node with node->left.  */
 447       gl_list_node_t child = node->left;
 448
 449       child->parent = parent;
 450       if (parent == NULL)
 451         list->root = child;
 452       else
 453         {
 454           if (parent->left == node)
 455             parent->left = child;
 456           else /* parent->right == node */
 457             parent->right = child;
 458
 459           /* Update branch_size fields of the parent nodes.  */
 460           {
 461             gl_list_node_t p;
 462
 463             for (p = parent; p != NULL; p = p->parent)
 464               p->branch_size--;
 465           }
 466
 467           rebalance (list, child, -1, parent);
 468         }
 469     }
 470   else
 471     {
 472       /* Replace node with the rightmost element of the node->left subtree.  */
 473       gl_list_node_t subst;
 474       gl_list_node_t subst_parent;
 475       gl_list_node_t child;
 476
 477       for (subst = node->left; subst->right != NULL; )
 478         subst = subst->right;
 479
 480       subst_parent = subst->parent;
 481
 482       child = subst->left;
 483
 484       /* The case subst_parent == node is special:  If we do nothing special,
 485          we get confusion about node->left, subst->left and child->parent.
 486            subst_parent == node
 487            <==> The 'for' loop above terminated immediately.
 488            <==> subst == subst_parent->left
 489                 [otherwise subst == subst_parent->right]
 490          In this case, we would need to first set
 491            child->parent = node; node->left = child;
 492          and later - when we copy subst into node's position - again
 493            child->parent = subst; subst->left = child;
 494          Altogether a no-op.  */
 495       if (subst_parent != node)
 496         {
 497           if (child != NULL)
 498             child->parent = subst_parent;
 499           subst_parent->right = child;
 500         }
 501
 502       /* Update branch_size fields of the parent nodes.  */
 503       {
 504         gl_list_node_t p;
 505
 506         for (p = subst_parent; p != NULL; p = p->parent)
 507           p->branch_size--;
 508       }
 509
 510       /* Copy subst into node's position.
 511          (This is safer than to copy subst's value into node, keep node in
 512          place, and free subst.)  */
 513       if (subst_parent != node)
 514         {
 515           subst->left = node->left;
 516           subst->left->parent = subst;
 517         }
 518       subst->right = node->right;
 519       subst->right->parent = subst;
 520       subst->balance = node->balance;
 521       subst->branch_size = node->branch_size;
 522       subst->parent = parent;
 523       if (parent == NULL)
 524         list->root = subst;
 525       else if (parent->left == node)
 526         parent->left = subst;
 527       else /* parent->right == node */
 528         parent->right = subst;
 529
 530       /* Rebalancing starts at child's parent, that is subst_parent -
 531          except when subst_parent == node.  In this case, we need to use
 532          its replacement, subst.  */
 533       rebalance (list, child, -1, subst_parent != node ? subst_parent : subst);
 534     }
 535 }
 536
 537 static gl_list_node_t
 538 gl_tree_nx_add_first (gl_list_t list, const void *elt)
 539 {
 540   /* Create new node.  */
 541   gl_list_node_t new_node =
 542     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 543
 544   if (new_node == NULL)
 545     return NULL;
 546
 547   new_node->left = NULL;
 548   new_node->right = NULL;
 549   new_node->balance = 0;
 550   new_node->branch_size = 1;
 551   new_node->value = elt;
 552 #if WITH_HASHTABLE
 553   new_node->h.hashcode =
 554     (list->base.hashcode_fn != NULL
 555      ? list->base.hashcode_fn (new_node->value)
 556      : (size_t)(uintptr_t) new_node->value);
 557 #endif
 558
 559   /* Add it to the tree.  */
 560   if (list->root == NULL)
 561     {
 562       list->root = new_node;
 563       new_node->parent = NULL;
 564     }
 565   else
 566     {
 567       gl_list_node_t node;
 568
 569       for (node = list->root; node->left != NULL; )
 570         node = node->left;
 571
 572       node->left = new_node;
 573       new_node->parent = node;
 574       node->balance--;
 575
 576       /* Update branch_size fields of the parent nodes.  */
 577       {
 578         gl_list_node_t p;
 579
 580         for (p = node; p != NULL; p = p->parent)
 581           p->branch_size++;
 582       }
 583
 584       /* Rebalance.  */
 585       if (node->right == NULL && node->parent != NULL)
 586         rebalance (list, node, 1, node->parent);
 587     }
 588
 589 #if WITH_HASHTABLE
 590   /* Add node to the hash table.
 591      Note that this is only possible _after_ the node has been added to the
 592      tree structure, because add_to_bucket() uses node_position().  */
 593   if (add_to_bucket (list, new_node) < 0)
 594     {
 595       gl_tree_remove_node_from_tree (list, new_node);
 596       free (new_node);
 597       return NULL;
 598     }
 599   hash_resize_after_add (list);
 600 #endif
 601
 602   return new_node;
 603 }
 604
 605 static gl_list_node_t
 606 gl_tree_nx_add_last (gl_list_t list, const void *elt)
 607 {
 608   /* Create new node.  */
 609   gl_list_node_t new_node =
 610     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 611
 612   if (new_node == NULL)
 613     return NULL;
 614
 615   new_node->left = NULL;
 616   new_node->right = NULL;
 617   new_node->balance = 0;
 618   new_node->branch_size = 1;
 619   new_node->value = elt;
 620 #if WITH_HASHTABLE
 621   new_node->h.hashcode =
 622     (list->base.hashcode_fn != NULL
 623      ? list->base.hashcode_fn (new_node->value)
 624      : (size_t)(uintptr_t) new_node->value);
 625 #endif
 626
 627   /* Add it to the tree.  */
 628   if (list->root == NULL)
 629     {
 630       list->root = new_node;
 631       new_node->parent = NULL;
 632     }
 633   else
 634     {
 635       gl_list_node_t node;
 636
 637       for (node = list->root; node->right != NULL; )
 638         node = node->right;
 639
 640       node->right = new_node;
 641       new_node->parent = node;
 642       node->balance++;
 643
 644       /* Update branch_size fields of the parent nodes.  */
 645       {
 646         gl_list_node_t p;
 647
 648         for (p = node; p != NULL; p = p->parent)
 649           p->branch_size++;
 650       }
 651
 652       /* Rebalance.  */
 653       if (node->left == NULL && node->parent != NULL)
 654         rebalance (list, node, 1, node->parent);
 655     }
 656
 657 #if WITH_HASHTABLE
 658   /* Add node to the hash table.
 659      Note that this is only possible _after_ the node has been added to the
 660      tree structure, because add_to_bucket() uses node_position().  */
 661   if (add_to_bucket (list, new_node) < 0)
 662     {
 663       gl_tree_remove_node_from_tree (list, new_node);
 664       free (new_node);
 665       return NULL;
 666     }
 667   hash_resize_after_add (list);
 668 #endif
 669
 670   return new_node;
 671 }
 672
 673 static gl_list_node_t
 674 gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
 675 {
 676   /* Create new node.  */
 677   gl_list_node_t new_node;
 678   bool height_inc;
 679
 680   new_node =
 681     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 682   if (new_node == NULL)
 683     return NULL;
 684
 685   new_node->left = NULL;
 686   new_node->right = NULL;
 687   new_node->balance = 0;
 688   new_node->branch_size = 1;
 689   new_node->value = elt;
 690 #if WITH_HASHTABLE
 691   new_node->h.hashcode =
 692     (list->base.hashcode_fn != NULL
 693      ? list->base.hashcode_fn (new_node->value)
 694      : (size_t)(uintptr_t) new_node->value);
 695 #endif
 696
 697   /* Add it to the tree.  */
 698   if (node->left == NULL)
 699     {
 700       node->left = new_node;
 701       node->balance--;
 702       height_inc = (node->right == NULL);
 703     }
 704   else
 705     {
 706       for (node = node->left; node->right != NULL; )
 707         node = node->right;
 708       node->right = new_node;
 709       node->balance++;
 710       height_inc = (node->left == NULL);
 711     }
 712   new_node->parent = node;
 713
 714   /* Update branch_size fields of the parent nodes.  */
 715   {
 716     gl_list_node_t p;
 717
 718     for (p = node; p != NULL; p = p->parent)
 719       p->branch_size++;
 720   }
 721
 722   /* Rebalance.  */
 723   if (height_inc && node->parent != NULL)
 724     rebalance (list, node, 1, node->parent);
 725
 726 #if WITH_HASHTABLE
 727   /* Add node to the hash table.
 728      Note that this is only possible _after_ the node has been added to the
 729      tree structure, because add_to_bucket() uses node_position().  */
 730   if (add_to_bucket (list, new_node) < 0)
 731     {
 732       gl_tree_remove_node_from_tree (list, new_node);
 733       free (new_node);
 734       return NULL;
 735     }
 736   hash_resize_after_add (list);
 737 #endif
 738
 739   return new_node;
 740 }
 741
 742 static gl_list_node_t
 743 gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
 744 {
 745   /* Create new node.  */
 746   gl_list_node_t new_node;
 747   bool height_inc;
 748
 749   new_node =
 750     (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
 751   if (new_node == NULL)
 752     return NULL;
 753
 754   new_node->left = NULL;
 755   new_node->right = NULL;
 756   new_node->balance = 0;
 757   new_node->branch_size = 1;
 758   new_node->value = elt;
 759 #if WITH_HASHTABLE
 760   new_node->h.hashcode =
 761     (list->base.hashcode_fn != NULL
 762      ? list->base.hashcode_fn (new_node->value)
 763      : (size_t)(uintptr_t) new_node->value);
 764 #endif
 765
 766   /* Add it to the tree.  */
 767   if (node->right == NULL)
 768     {
 769       node->right = new_node;
 770       node->balance++;
 771       height_inc = (node->left == NULL);
 772     }
 773   else
 774     {
 775       for (node = node->right; node->left != NULL; )
 776         node = node->left;
 777       node->left = new_node;
 778       node->balance--;
 779       height_inc = (node->right == NULL);
 780     }
 781   new_node->parent = node;
 782
 783   /* Update branch_size fields of the parent nodes.  */
 784   {
 785     gl_list_node_t p;
 786
 787     for (p = node; p != NULL; p = p->parent)
 788       p->branch_size++;
 789   }
 790
 791   /* Rebalance.  */
 792   if (height_inc && node->parent != NULL)
 793     rebalance (list, node, 1, node->parent);
 794
 795 #if WITH_HASHTABLE
 796   /* Add node to the hash table.
 797      Note that this is only possible _after_ the node has been added to the
 798      tree structure, because add_to_bucket() uses node_position().  */
 799   if (add_to_bucket (list, new_node) < 0)
 800     {
 801       gl_tree_remove_node_from_tree (list, new_node);
 802       free (new_node);
 803       return NULL;
 804     }
 805   hash_resize_after_add (list);
 806 #endif
 807
 808   return new_node;
 809 }