Adding upstream version 2.9.4.upstream/2.9.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1028 insertions, 0 deletions

diff --git a/gl/lib/gl_anyrbtree_list2.h b/gl/lib/gl_anyrbtree_list2.h
new file mode 100644
index 0000000..f14eda0
--- /dev/null
+++ b/gl/lib/gl_anyrbtree_list2.h
@@ -0,0 +1,1028 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006-2007, 2009-2020 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c.  */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Creates a subtree for count >= 1 elements.
+   Its black-height bh is passed as argument, with
+   2^bh - 1 <= count <= 2^(bh+1) - 1.  bh == 0 implies count == 1.
+   Its height is h where 2^(h-1) <= count <= 2^h - 1.
+   Return NULL upon out-of-memory.  */
+static gl_list_node_t
+create_subtree_with_contents (unsigned int bh,
+                              size_t count, const void **contents)
+{
+  size_t half1 = (count - 1) / 2;
+  size_t half2 = count / 2;
+  /* Note: half1 + half2 = count - 1.  */
+  gl_list_node_t node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+  if (node == NULL)
+    return NULL;
+
+  if (half1 > 0)
+    {
+      /* half1 > 0 implies count > 1, implies bh >= 1, implies
+           2^(bh-1) - 1 <= half1 <= 2^bh - 1.  */
+      node->left =
+        create_subtree_with_contents (bh - 1, half1, contents);
+      if (node->left == NULL)
+        goto fail1;
+      node->left->parent = node;
+    }
+  else
+    node->left = NULL;
+
+  node->value = contents[half1];
+
+  if (half2 > 0)
+    {
+      /* half2 > 0 implies count > 1, implies bh >= 1, implies
+           2^(bh-1) - 1 <= half2 <= 2^bh - 1.  */
+      node->right =
+       create_subtree_with_contents (bh - 1, half2, contents + half1 + 1);
+      if (node->right == NULL)
+        goto fail2;
+      node->right->parent = node;
+    }
+  else
+    node->right = NULL;
+
+  node->color = (bh == 0 ? RED : BLACK);
+
+  node->branch_size = count;
+
+  return node;
+
+ fail2:
+  if (node->left != NULL)
+    free_subtree (node->left);
+ fail1:
+  free (node);
+  return NULL;
+}
+
+static gl_list_t
+gl_tree_nx_create (gl_list_implementation_t implementation,
+                   gl_listelement_equals_fn equals_fn,
+                   gl_listelement_hashcode_fn hashcode_fn,
+                   gl_listelement_dispose_fn dispose_fn,
+                   bool allow_duplicates,
+                   size_t count, const void **contents)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl));
+
+  if (list == NULL)
+    return NULL;
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_fn;
+  list->base.dispose_fn = dispose_fn;
+  list->base.allow_duplicates = allow_duplicates;
+#if WITH_HASHTABLE
+  {
+    size_t estimate = xsum (count, count / 2); /* 1.5 * count */
+    if (estimate < 10)
+      estimate = 10;
+    list->table_size = next_prime (estimate);
+    if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t))))
+      goto fail1;
+    list->table =
+      (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t));
+    if (list->table == NULL)
+      goto fail1;
+  }
+#endif
+  if (count > 0)
+    {
+      /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose
+         upper bh levels are black, and only the partially present lowest
+         level is red.  */
+      unsigned int bh;
+      {
+        size_t n;
+        for (n = count + 1, bh = 0; n > 1; n = n >> 1)
+          bh++;
+      }
+
+      list->root = create_subtree_with_contents (bh, count, contents);
+      if (list->root == NULL)
+        goto fail2;
+      list->root->parent = NULL;
+
+#if WITH_HASHTABLE
+      /* Now that the tree is built, node_position() works.  Now we can
+         add the nodes to the hash table.  */
+      if (add_nodes_to_buckets (list) < 0)
+        goto fail3;
+#endif
+    }
+  else
+    list->root = NULL;
+
+  return list;
+
+#if WITH_HASHTABLE
+ fail3:
+  free_subtree (list->root);
+#endif
+ fail2:
+#if WITH_HASHTABLE
+  free (list->table);
+ fail1:
+#endif
+  free (list);
+  return NULL;
+}
+
+/* Rotates left a subtree.
+
+                         B                         D
+                       /   \                     /   \
+                     A       D       -->       B       E
+                            / \               / \
+                           C   E             A   C
+
+   Changes the tree structure, updates the branch sizes.
+   The caller must update the colors and register D as child of its parent.  */
+static gl_list_node_t
+rotate_left (gl_list_node_t b_node, gl_list_node_t d_node)
+{
+  gl_list_node_t a_node = b_node->left;
+  gl_list_node_t c_node = d_node->left;
+  gl_list_node_t e_node = d_node->right;
+
+  b_node->right = c_node;
+  d_node->left = b_node;
+
+  d_node->parent = b_node->parent;
+  b_node->parent = d_node;
+  if (c_node != NULL)
+    c_node->parent = b_node;
+
+  b_node->branch_size =
+    (a_node != NULL ? a_node->branch_size : 0)
+    + 1 + (c_node != NULL ? c_node->branch_size : 0);
+  d_node->branch_size =
+    b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0);
+
+  return d_node;
+}
+
+/* Rotates right a subtree.
+
+                           D                     B
+                         /   \                 /   \
+                       B       E     -->     A       D
+                      / \                           / \
+                     A   C                         C   E
+
+   Changes the tree structure, updates the branch sizes.
+   The caller must update the colors and register B as child of its parent.  */
+static gl_list_node_t
+rotate_right (gl_list_node_t b_node, gl_list_node_t d_node)
+{
+  gl_list_node_t a_node = b_node->left;
+  gl_list_node_t c_node = b_node->right;
+  gl_list_node_t e_node = d_node->right;
+
+  d_node->left = c_node;
+  b_node->right = d_node;
+
+  b_node->parent = d_node->parent;
+  d_node->parent = b_node;
+  if (c_node != NULL)
+    c_node->parent = d_node;
+
+  d_node->branch_size =
+    (c_node != NULL ? c_node->branch_size : 0)
+    + 1 + (e_node != NULL ? e_node->branch_size : 0);
+  b_node->branch_size =
+    (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size;
+
+  return b_node;
+}
+
+/* Ensures the tree is balanced, after an insertion operation.
+   Also assigns node->color.
+   parent is the given node's parent, known to be non-NULL.  */
+static void
+rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent)
+{
+  for (;;)
+    {
+      /* At this point, parent = node->parent != NULL.
+         Think of node->color being RED (although node->color is not yet
+         assigned.)  */
+      gl_list_node_t grandparent;
+      gl_list_node_t uncle;
+
+      if (parent->color == BLACK)
+        {
+          /* A RED color for node is acceptable.  */
+          node->color = RED;
+          return;
+        }
+
+      grandparent = parent->parent;
+      /* Since parent is RED, we know that
+         grandparent is != NULL and colored BLACK.  */
+
+      if (grandparent->left == parent)
+        uncle = grandparent->right;
+      else if (grandparent->right == parent)
+        uncle = grandparent->left;
+      else
+        abort ();
+
+      if (uncle != NULL && uncle->color == RED)
+        {
+          /* Change grandparent from BLACK to RED, and
+             change parent and uncle from RED to BLACK.
+             This makes it acceptable for node to be RED.  */
+          node->color = RED;
+          parent->color = uncle->color = BLACK;
+          node = grandparent;
+        }
+      else
+        {
+          /* grandparent and uncle are BLACK.  parent is RED.  node wants
+             to be RED too.
+             In this case, recoloring is not sufficient.  Need to perform
+             one or two rotations.  */
+          gl_list_node_t *grandparentp;
+
+          if (grandparent->parent == NULL)
+            grandparentp = &list->root;
+          else if (grandparent->parent->left == grandparent)
+            grandparentp = &grandparent->parent->left;
+          else if (grandparent->parent->right == grandparent)
+            grandparentp = &grandparent->parent->right;
+          else
+            abort ();
+
+          if (grandparent->left == parent)
+            {
+              if (parent->right == node)
+                {
+                  /* Rotation between node and parent.  */
+                  grandparent->left = rotate_left (parent, node);
+                  node = parent;
+                  parent = grandparent->left;
+                }
+              /* grandparent and uncle are BLACK.  parent and node want to be
+                 RED.  parent = grandparent->left.  node = parent->left.
+
+                      grandparent              parent
+                         bh+1                   bh+1
+                         /   \                 /   \
+                     parent  uncle    -->   node  grandparent
+                      bh      bh             bh      bh
+                      / \                           / \
+                   node  C                         C  uncle
+                    bh   bh                       bh    bh
+               */
+              *grandparentp = rotate_right (parent, grandparent);
+              parent->color = BLACK;
+              node->color = grandparent->color = RED;
+            }
+          else /* grandparent->right == parent */
+            {
+              if (parent->left == node)
+                {
+                  /* Rotation between node and parent.  */
+                  grandparent->right = rotate_right (node, parent);
+                  node = parent;
+                  parent = grandparent->right;
+                }
+              /* grandparent and uncle are BLACK.  parent and node want to be
+                 RED.  parent = grandparent->right.  node = parent->right.
+
+                    grandparent                    parent
+                       bh+1                         bh+1
+                       /   \                       /   \
+                   uncle  parent     -->   grandparent  node
+                     bh     bh                  bh       bh
+                            / \                 / \
+                           C  node          uncle  C
+                          bh   bh            bh    bh
+               */
+              *grandparentp = rotate_left (grandparent, parent);
+              parent->color = BLACK;
+              node->color = grandparent->color = RED;
+            }
+          return;
+        }
+
+      /* Start again with a new (node, parent) pair.  */
+      parent = node->parent;
+
+      if (parent == NULL)
+        {
+          /* Change node's color from RED to BLACK.  This increases the
+             tree's black-height.  */
+          node->color = BLACK;
+          return;
+        }
+    }
+}
+
+/* Ensures the tree is balanced, after a deletion operation.
+   CHILD was a grandchild of PARENT and is now its child.  Between them,
+   a black node was removed.  CHILD is also black, or NULL.
+   (CHILD can also be NULL.  But PARENT is non-NULL.)  */
+static void
+rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent)
+{
+  for (;;)
+    {
+      /* At this point, we reduced the black-height of the CHILD subtree by 1.
+         To make up, either look for a possibility to turn a RED to a BLACK
+         node, or try to reduce the black-height tree of CHILD's sibling
+         subtree as well.  */
+      gl_list_node_t *parentp;
+
+      if (parent->parent == NULL)
+        parentp = &list->root;
+      else if (parent->parent->left == parent)
+        parentp = &parent->parent->left;
+      else if (parent->parent->right == parent)
+        parentp = &parent->parent->right;
+      else
+        abort ();
+
+      if (parent->left == child)
+        {
+          gl_list_node_t sibling = parent->right;
+          /* sibling's black-height is >= 1.  In particular,
+             sibling != NULL.
+
+                      parent
+                       /   \
+                   child  sibling
+                     bh    bh+1
+           */
+
+          if (sibling->color == RED)
+            {
+              /* sibling is RED, hence parent is BLACK and sibling's children
+                 are non-NULL and BLACK.
+
+                      parent                       sibling
+                       bh+2                         bh+2
+                       /   \                        /   \
+                   child  sibling     -->       parent    SR
+                     bh    bh+1                  bh+1    bh+1
+                            / \                  / \
+                          SL   SR            child  SL
+                         bh+1 bh+1             bh  bh+1
+               */
+              *parentp = rotate_left (parent, sibling);
+              parent->color = RED;
+              sibling->color = BLACK;
+
+              /* Concentrate on the subtree of parent.  The new sibling is
+                 one of the old sibling's children, and known to be BLACK.  */
+              parentp = &sibling->left;
+              sibling = parent->right;
+            }
+          /* Now we know that sibling is BLACK.
+
+                      parent
+                       /   \
+                   child  sibling
+                     bh    bh+1
+           */
+          if (sibling->right != NULL && sibling->right->color == RED)
+            {
+              /*
+                      parent                     sibling
+                     bh+1|bh+2                  bh+1|bh+2
+                       /   \                      /   \
+                   child  sibling    -->      parent    SR
+                     bh    bh+1                bh+1    bh+1
+                            / \                / \
+                          SL   SR           child  SL
+                          bh   bh             bh   bh
+               */
+              *parentp = rotate_left (parent, sibling);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->right->color = BLACK;
+              return;
+            }
+          else if (sibling->left != NULL && sibling->left->color == RED)
+            {
+              /*
+                      parent                   parent
+                     bh+1|bh+2                bh+1|bh+2
+                       /   \                    /   \
+                   child  sibling    -->    child    SL
+                     bh    bh+1               bh    bh+1
+                            / \                     /  \
+                          SL   SR                 SLL  sibling
+                          bh   bh                 bh     bh
+                         /  \                           /   \
+                       SLL  SLR                       SLR    SR
+                       bh    bh                       bh     bh
+
+                 where SLL, SLR, SR are all black.
+               */
+              parent->right = rotate_right (sibling->left, sibling);
+              /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
+              sibling->color = RED;
+              sibling = parent->right;
+              sibling->color = BLACK;
+
+              /* Now do as in the previous case.  */
+              *parentp = rotate_left (parent, sibling);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->right->color = BLACK;
+              return;
+            }
+          else
+            {
+              if (parent->color == BLACK)
+                {
+                  /* Change sibling from BLACK to RED.  Then the entire
+                     subtree at parent has decreased its black-height.
+                              parent                   parent
+                               bh+2                     bh+1
+                               /   \                    /   \
+                           child  sibling    -->    child  sibling
+                             bh    bh+1               bh     bh
+                   */
+                  sibling->color = RED;
+
+                  child = parent;
+                }
+              else
+                {
+                  /* Change parent from RED to BLACK, but compensate by
+                     changing sibling from BLACK to RED.
+                              parent                   parent
+                               bh+1                     bh+1
+                               /   \                    /   \
+                           child  sibling    -->    child  sibling
+                             bh    bh+1               bh     bh
+                   */
+                  parent->color = BLACK;
+                  sibling->color = RED;
+                  return;
+                }
+            }
+        }
+      else if (parent->right == child)
+        {
+          gl_list_node_t sibling = parent->left;
+          /* sibling's black-height is >= 1.  In particular,
+             sibling != NULL.
+
+                      parent
+                       /   \
+                  sibling  child
+                    bh+1     bh
+           */
+
+          if (sibling->color == RED)
+            {
+              /* sibling is RED, hence parent is BLACK and sibling's children
+                 are non-NULL and BLACK.
+
+                      parent                 sibling
+                       bh+2                    bh+2
+                       /   \                  /   \
+                  sibling  child    -->     SR    parent
+                    bh+1     ch            bh+1    bh+1
+                    / \                            / \
+                  SL   SR                        SL  child
+                 bh+1 bh+1                      bh+1   bh
+               */
+              *parentp = rotate_right (sibling, parent);
+              parent->color = RED;
+              sibling->color = BLACK;
+
+              /* Concentrate on the subtree of parent.  The new sibling is
+                 one of the old sibling's children, and known to be BLACK.  */
+              parentp = &sibling->right;
+              sibling = parent->left;
+            }
+          /* Now we know that sibling is BLACK.
+
+                      parent
+                       /   \
+                  sibling  child
+                    bh+1     bh
+           */
+          if (sibling->left != NULL && sibling->left->color == RED)
+            {
+              /*
+                       parent                 sibling
+                      bh+1|bh+2              bh+1|bh+2
+                        /   \                  /   \
+                   sibling  child    -->     SL   parent
+                     bh+1     bh            bh+1   bh+1
+                     / \                           / \
+                   SL   SR                       SR  child
+                   bh   bh                       bh    bh
+               */
+              *parentp = rotate_right (sibling, parent);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->left->color = BLACK;
+              return;
+            }
+          else if (sibling->right != NULL && sibling->right->color == RED)
+            {
+              /*
+                      parent                       parent
+                     bh+1|bh+2                    bh+1|bh+2
+                       /   \                        /   \
+                   sibling  child    -->          SR    child
+                    bh+1      bh                 bh+1     bh
+                     / \                         /  \
+                   SL   SR                  sibling  SRR
+                   bh   bh                    bh      bh
+                       /  \                  /   \
+                     SRL  SRR               SL   SRL
+                     bh    bh               bh    bh
+
+                 where SL, SRL, SRR are all black.
+               */
+              parent->left = rotate_left (sibling, sibling->right);
+              /* Change sibling from BLACK to RED and SL from RED to BLACK.  */
+              sibling->color = RED;
+              sibling = parent->left;
+              sibling->color = BLACK;
+
+              /* Now do as in the previous case.  */
+              *parentp = rotate_right (sibling, parent);
+              sibling->color = parent->color;
+              parent->color = BLACK;
+              sibling->left->color = BLACK;
+              return;
+            }
+          else
+            {
+              if (parent->color == BLACK)
+                {
+                  /* Change sibling from BLACK to RED.  Then the entire
+                     subtree at parent has decreased its black-height.
+                              parent                   parent
+                               bh+2                     bh+1
+                               /   \                    /   \
+                           sibling  child    -->    sibling  child
+                            bh+1      bh              bh       bh
+                   */
+                  sibling->color = RED;
+
+                  child = parent;
+                }
+              else
+                {
+                  /* Change parent from RED to BLACK, but compensate by
+                     changing sibling from BLACK to RED.
+                              parent                   parent
+                               bh+1                     bh+1
+                               /   \                    /   \
+                           sibling  child    -->    sibling  child
+                            bh+1      bh              bh       bh
+                   */
+                  parent->color = BLACK;
+                  sibling->color = RED;
+                  return;
+                }
+            }
+        }
+      else
+        abort ();
+
+      /* Start again with a new (child, parent) pair.  */
+      parent = child->parent;
+
+#if 0 /* Already handled.  */
+      if (child != NULL && child->color == RED)
+        {
+          child->color = BLACK;
+          return;
+        }
+#endif
+
+      if (parent == NULL)
+        return;
+    }
+}
+
+static void
+gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node)
+{
+  gl_list_node_t parent = node->parent;
+
+  if (node->left == NULL)
+    {
+      /* Replace node with node->right.  */
+      gl_list_node_t child = node->right;
+
+      if (child != NULL)
+        {
+          child->parent = parent;
+          /* Since node->left == NULL, child must be RED and of height 1,
+             hence node must have been BLACK.  Recolor the child.  */
+          child->color = BLACK;
+        }
+      if (parent == NULL)
+        list->root = child;
+      else
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          /* Update branch_size fields of the parent nodes.  */
+          {
+            gl_list_node_t p;
+
+            for (p = parent; p != NULL; p = p->parent)
+              p->branch_size--;
+          }
+
+          if (child == NULL && node->color == BLACK)
+            rebalance_after_remove (list, child, parent);
+        }
+    }
+  else if (node->right == NULL)
+    {
+      /* It is not absolutely necessary to treat this case.  But the more
+         general case below is more complicated, hence slower.  */
+      /* Replace node with node->left.  */
+      gl_list_node_t child = node->left;
+
+      child->parent = parent;
+      /* Since node->right == NULL, child must be RED and of height 1,
+         hence node must have been BLACK.  Recolor the child.  */
+      child->color = BLACK;
+      if (parent == NULL)
+        list->root = child;
+      else
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          /* Update branch_size fields of the parent nodes.  */
+          {
+            gl_list_node_t p;
+
+            for (p = parent; p != NULL; p = p->parent)
+              p->branch_size--;
+          }
+        }
+    }
+  else
+    {
+      /* Replace node with the rightmost element of the node->left subtree.  */
+      gl_list_node_t subst;
+      gl_list_node_t subst_parent;
+      gl_list_node_t child;
+      color_t removed_color;
+
+      for (subst = node->left; subst->right != NULL; )
+        subst = subst->right;
+
+      subst_parent = subst->parent;
+
+      child = subst->left;
+
+      removed_color = subst->color;
+
+      /* The case subst_parent == node is special:  If we do nothing special,
+         we get confusion about node->left, subst->left and child->parent.
+           subst_parent == node
+           <==> The 'for' loop above terminated immediately.
+           <==> subst == subst_parent->left
+                [otherwise subst == subst_parent->right]
+         In this case, we would need to first set
+           child->parent = node; node->left = child;
+         and later - when we copy subst into node's position - again
+           child->parent = subst; subst->left = child;
+         Altogether a no-op.  */
+      if (subst_parent != node)
+        {
+          if (child != NULL)
+            child->parent = subst_parent;
+          subst_parent->right = child;
+        }
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = subst_parent; p != NULL; p = p->parent)
+          p->branch_size--;
+      }
+
+      /* Copy subst into node's position.
+         (This is safer than to copy subst's value into node, keep node in
+         place, and free subst.)  */
+      if (subst_parent != node)
+        {
+          subst->left = node->left;
+          subst->left->parent = subst;
+        }
+      subst->right = node->right;
+      subst->right->parent = subst;
+      subst->color = node->color;
+      subst->branch_size = node->branch_size;
+      subst->parent = parent;
+      if (parent == NULL)
+        list->root = subst;
+      else if (parent->left == node)
+        parent->left = subst;
+      else /* parent->right == node */
+        parent->right = subst;
+
+      if (removed_color == BLACK)
+        {
+          if (child != NULL && child->color == RED)
+            /* Recolor the child.  */
+            child->color = BLACK;
+          else
+            /* Rebalancing starts at child's parent, that is subst_parent -
+               except when subst_parent == node.  In this case, we need to use
+               its replacement, subst.  */
+            rebalance_after_remove (list, child,
+                                    subst_parent != node ? subst_parent : subst);
+        }
+    }
+}
+
+static gl_list_node_t
+gl_tree_nx_add_first (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (list->root == NULL)
+    {
+      new_node->color = BLACK;
+      list->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      for (node = list->root; node->left != NULL; )
+        node = node->left;
+
+      node->left = new_node;
+      new_node->parent = node;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = node; p != NULL; p = p->parent)
+          p->branch_size++;
+      }
+
+      /* Color and rebalance.  */
+      rebalance_after_add (list, new_node, node);
+    }
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_last (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (list->root == NULL)
+    {
+      new_node->color = BLACK;
+      list->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      for (node = list->root; node->right != NULL; )
+        node = node->right;
+
+      node->right = new_node;
+      new_node->parent = node;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+        gl_list_node_t p;
+
+        for (p = node; p != NULL; p = p->parent)
+          p->branch_size++;
+      }
+
+      /* Color and rebalance.  */
+      rebalance_after_add (list, new_node, node);
+    }
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (node->left == NULL)
+    node->left = new_node;
+  else
+    {
+      for (node = node->left; node->right != NULL; )
+        node = node->right;
+      node->right = new_node;
+    }
+  new_node->parent = node;
+
+  /* Update branch_size fields of the parent nodes.  */
+  {
+    gl_list_node_t p;
+
+    for (p = node; p != NULL; p = p->parent)
+      p->branch_size++;
+  }
+
+  /* Color and rebalance.  */
+  rebalance_after_add (list, new_node, node);
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->branch_size = 1;
+  new_node->value = elt;
+#if WITH_HASHTABLE
+  new_node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (new_node->value)
+     : (size_t)(uintptr_t) new_node->value);
+#endif
+
+  /* Add it to the tree.  */
+  if (node->right == NULL)
+    node->right = new_node;
+  else
+    {
+      for (node = node->right; node->left != NULL; )
+        node = node->left;
+      node->left = new_node;
+    }
+  new_node->parent = node;
+
+  /* Update branch_size fields of the parent nodes.  */
+  {
+    gl_list_node_t p;
+
+    for (p = node; p != NULL; p = p->parent)
+      p->branch_size++;
+  }
+
+  /* Color and rebalance.  */
+  rebalance_after_add (list, new_node, node);
+
+#if WITH_HASHTABLE
+  /* Add node to the hash table.
+     Note that this is only possible _after_ the node has been added to the
+     tree structure, because add_to_bucket() uses node_position().  */
+  if (add_to_bucket (list, new_node) < 0)
+    {
+      gl_tree_remove_node_from_tree (list, new_node);
+      free (new_node);
+      return NULL;
+    }
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}