Common code several concrete list implementations.

12 files changed, 3937 insertions, 0 deletions

diff --git a/lib/gl_anyavltree_list1.h b/lib/gl_anyavltree_list1.h
new file mode 100644
index 0000000000..8bf2604acd
--- /dev/null
+++ b/lib/gl_anyavltree_list1.h
@@ -0,0 +1,71 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltree_list.c and gl_avltreehash_list.c.  */
+
+/* An AVL tree is a binary tree where
+   1. The height of each node is calculated as
+	heightof(node) = 1 + max (heightof(node.left), heightof(node.right)).
+   2. The heights of the subtrees of each node differ by at most 1:
+	| heightof(right) - heightof(left) | <= 1.
+   3. The index of the elements in the node.left subtree are smaller than
+      the index of node.
+      The index of the elements in the node.right subtree are larger than
+      the index of node.
+ */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Concrete list node implementation, valid for this file only.  */
+struct gl_list_node_impl
+{
+#if WITH_HASHTABLE
+  struct gl_hash_entry h;           /* hash table entry fields; must be first */
+#endif
+  struct gl_list_node_impl *left;   /* left branch, or NULL */
+  struct gl_list_node_impl *right;  /* right branch, or NULL */
+  /* Parent pointer, or NULL. The parent pointer is not needed for most
+     operations.  It is needed so that a gl_list_node_t can be returned
+     without memory allocation, on which the functions gl_list_remove_node,
+     gl_list_add_before, gl_list_add_after can be implemented.  */
+  struct gl_list_node_impl *parent;
+  int balance;                      /* heightof(right) - heightof(left),
+				       always = -1 or 0 or 1 */
+  size_t branch_size;               /* number of nodes in this branch,
+				       = branchsize(left)+branchsize(right)+1 */
+  const void *value;
+};
+
+/* Concrete gl_list_impl type, valid for this file only.  */
+struct gl_list_impl
+{
+  struct gl_list_impl_base base;
+#if WITH_HASHTABLE
+  /* A hash table: managed as an array of collision lists.  */
+  struct gl_hash_entry **table;
+  size_t table_size;
+#endif
+  struct gl_list_node_impl *root;   /* root node or NULL */
+};
+
+/* An AVL tree of height h has at least F_(h+2) [Fibonacci number] and at most
+   2^h - 1 elements.  So, h <= 84 (because a tree of height h >= 85 would have
+   at least F_87 elements, and because even on 64-bit machines,
+     sizeof (gl_list_node_impl) * F_87 > 2^64
+   this would exceed the address space of the machine.  */
+#define MAXHEIGHT 83
diff --git a/lib/gl_anyavltree_list2.h b/lib/gl_anyavltree_list2.h
new file mode 100644
index 0000000000..a4c26c58eb
--- /dev/null
+++ b/lib/gl_anyavltree_list2.h
@@ -0,0 +1,750 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltree_list.c and gl_avltreehash_list.c.  */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Create a subtree for count >= 1 elements.
+   Its height is h where 2^(h-1) <= count <= 2^h - 1.  */
+static gl_list_node_t
+create_subtree_with_contents (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 *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  if (half1 > 0)
+    {
+      node->left = create_subtree_with_contents (half1, contents);
+      node->left->parent = node;
+    }
+  else
+    node->left = NULL;
+
+  node->value = contents[half1];
+
+  if (half2 > 0)
+    {
+      node->right = create_subtree_with_contents (half2, contents + half1 + 1);
+      node->right->parent = node;
+    }
+  else
+    node->right = NULL;
+
+  /* balance is 0, except when count is a power of two and > 1.
+     Reason: half1 <= half2 <= half1 + 1, and the two branches can have
+     different heights only if half1 = 2^h - 1 and half2 = 2^h; in this
+     case, count = half1 + half2 + 1 = 2^(h+1).  */
+  node->balance = (count > 1 && (count & (count - 1)) == 0 ? 1 : 0);
+
+  node->branch_size = count;
+
+  return node;
+}
+
+static gl_list_t
+gl_tree_create (gl_list_implementation_t implementation,
+		gl_listelement_equals_fn equals_fn,
+		gl_listelement_hashcode_fn hashcode_fn,
+		bool allow_duplicates,
+		size_t count, const void **contents)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_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);
+    list->table =
+      (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+  }
+#endif
+  if (count > 0)
+    {
+      list->root = create_subtree_with_contents (count, contents);
+      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.  */
+      add_nodes_to_buckets (list);
+#endif
+    }
+  else
+    list->root = NULL;
+
+  return list;
+}
+
+/* Ensure the tree is balanced, after an insertion or deletion operation.
+   The height of NODE is incremented by HEIGHT_DIFF (1 or -1).
+   PARENT = NODE->parent.  (NODE can also be NULL.  But PARENT is non-NULL.)
+   Rotation operations are performed starting at PARENT (not NODE itself!).  */
+static void
+rebalance (gl_list_t list,
+	   gl_list_node_t node, int height_diff, gl_list_node_t parent)
+{
+  for (;;)
+    {
+      gl_list_node_t child;
+      int previous_balance;
+      int balance_diff;
+      gl_list_node_t nodeleft;
+      gl_list_node_t noderight;
+
+      child = node;
+      node = parent;
+
+      previous_balance = node->balance;
+
+      /* The balance of NODE is incremented by BALANCE_DIFF: +1 if the right
+	 branch's height has increased by 1 or the left branch's height has
+	 decreased by 1, -1 if the right branch's height has decreased by 1 or
+	 the left branch's height has increased by 1, 0 if no height change.  */
+      if (node->left != NULL || node->right != NULL)
+	balance_diff = (child == node->right ? height_diff : -height_diff);
+      else
+	/* Special case where above formula doesn't work, because the caller
+	   didn't tell whether node's left or right branch shrunk from height 1
+	   to NULL.  */
+	balance_diff = - previous_balance;
+
+      node->balance += balance_diff;
+      if (balance_diff == previous_balance)
+	{
+	  /* node->balance is outside the range [-1,1].  Must rotate.  */
+	  gl_list_node_t *nodep;
+
+	  if (node->parent == NULL)
+	    /* node == list->root */
+	    nodep = &list->root;
+	  else if (node->parent->left == node)
+	    nodep = &node->parent->left;
+	  else if (node->parent->right == node)
+	    nodep = &node->parent->right;
+	  else
+	    abort ();
+
+	  nodeleft = node->left;
+	  noderight = node->right;
+
+	  if (balance_diff < 0)
+	    {
+	      /* node->balance = -2.  The subtree is heavier on the left side.
+		 Rotate from left to right:
+
+				  *
+				/   \
+			     h+2      h
+	       */
+	      gl_list_node_t nodeleftleft = nodeleft->left;
+	      gl_list_node_t nodeleftright = nodeleft->right;
+	      if (nodeleft->balance <= 0)
+		{
+		  /*
+			      *                    h+2|h+3
+			    /   \                  /    \
+			 h+2      h      -->      /   h+1|h+2
+			 / \                      |    /    \
+		       h+1 h|h+1                 h+1  h|h+1  h
+		   */
+		  node->left = nodeleftright;
+		  nodeleft->right = node;
+
+		  nodeleft->parent = node->parent;
+		  node->parent = nodeleft;
+		  if (nodeleftright != NULL)
+		    nodeleftright->parent = node;
+
+		  nodeleft->balance += 1;
+		  node->balance = - nodeleft->balance;
+
+		  node->branch_size =
+		    (nodeleftright != NULL ? nodeleftright->branch_size : 0)
+		    + 1 + (noderight != NULL ? noderight->branch_size : 0);
+		  nodeleft->branch_size =
+		    nodeleftleft->branch_size + 1 + node->branch_size;
+
+		  *nodep = nodeleft;
+		  height_diff = (height_diff < 0
+				 ? /* noderight's height had been decremented from
+				      h+1 to h.  The subtree's height changes from
+				      h+3 to h+2|h+3.  */
+				   nodeleft->balance - 1
+				 : /* nodeleft's height had been incremented from
+				      h+1 to h+2.  The subtree's height changes from
+				      h+2 to h+2|h+3.  */
+				   nodeleft->balance);
+		}
+	      else
+		{
+		  /*
+			    *                     h+2
+			  /   \                 /     \
+		       h+2      h      -->    h+1     h+1
+		       / \                    / \     / \
+		      h  h+1                 h   L   R   h
+			 / \
+			L   R
+
+		   */
+		  gl_list_node_t L = nodeleft->right = nodeleftright->left;
+		  gl_list_node_t R = node->left = nodeleftright->right;
+		  nodeleftright->left = nodeleft;
+		  nodeleftright->right = node;
+
+		  nodeleftright->parent = node->parent;
+		  if (L != NULL)
+		    L->parent = nodeleft;
+		  if (R != NULL)
+		    R->parent = node;
+		  nodeleft->parent = nodeleftright;
+		  node->parent = nodeleftright;
+
+		  nodeleft->balance = (nodeleftright->balance > 0 ? -1 : 0);
+		  node->balance = (nodeleftright->balance < 0 ? 1 : 0);
+		  nodeleftright->balance = 0;
+
+		  nodeleft->branch_size =
+		    (nodeleft->left != NULL ? nodeleft->left->branch_size : 0)
+		    + 1 + (nodeleft->right != NULL ? nodeleft->right->branch_size : 0);
+		  node->branch_size =
+		    (node->left != NULL ? node->left->branch_size : 0)
+		    + 1 + (node->right != NULL ? node->right->branch_size : 0);
+		  nodeleftright->branch_size =
+		    nodeleft->branch_size + 1 + node->branch_size;
+
+		  *nodep = nodeleftright;
+		  height_diff = (height_diff < 0
+				 ? /* noderight's height had been decremented from
+				      h+1 to h.  The subtree's height changes from
+				      h+3 to h+2.  */
+				   -1
+				 : /* nodeleft's height had been incremented from
+				      h+1 to h+2.  The subtree's height changes from
+				      h+2 to h+2.  */
+				   0);
+		}
+	    }
+	  else
+	    {
+	      /* node->balance = 2.  The subtree is heavier on the right side.
+		 Rotate from right to left:
+
+				  *
+				/   \
+			      h      h+2
+	       */
+	      gl_list_node_t noderightleft = noderight->left;
+	      gl_list_node_t noderightright = noderight->right;
+	      if (noderight->balance >= 0)
+		{
+		  /*
+			      *                    h+2|h+3
+			    /   \                   /    \
+			  h      h+2     -->    h+1|h+2   \
+				 / \            /    \    |
+			     h|h+1 h+1         h   h|h+1 h+1
+		   */
+		  node->right = noderightleft;
+		  noderight->left = node;
+
+		  noderight->parent = node->parent;
+		  node->parent = noderight;
+		  if (noderightleft != NULL)
+		    noderightleft->parent = node;
+
+		  noderight->balance -= 1;
+		  node->balance = - noderight->balance;
+
+		  node->branch_size =
+		    (nodeleft != NULL ? nodeleft->branch_size : 0)
+		    + 1 + (noderightleft != NULL ? noderightleft->branch_size : 0);
+		  noderight->branch_size =
+		    node->branch_size + 1 + noderightright->branch_size;
+
+		  *nodep = noderight;
+		  height_diff = (height_diff < 0
+				 ? /* nodeleft's height had been decremented from
+				      h+1 to h.  The subtree's height changes from
+				      h+3 to h+2|h+3.  */
+				   - noderight->balance - 1
+				 : /* noderight's height had been incremented from
+				      h+1 to h+2.  The subtree's height changes from
+				      h+2 to h+2|h+3.  */
+				   - noderight->balance);
+		}
+	      else
+		{
+		  /*
+			    *                    h+2
+			  /   \                /     \
+			h      h+2    -->    h+1     h+1
+			       / \           / \     / \
+			     h+1  h         h   L   R   h
+			     / \
+			    L   R
+
+		   */
+		  gl_list_node_t L = node->right = noderightleft->left;
+		  gl_list_node_t R = noderight->left = noderightleft->right;
+		  noderightleft->left = node;
+		  noderightleft->right = noderight;
+
+		  noderightleft->parent = node->parent;
+		  if (L != NULL)
+		    L->parent = node;
+		  if (R != NULL)
+		    R->parent = noderight;
+		  node->parent = noderightleft;
+		  noderight->parent = noderightleft;
+
+		  node->balance = (noderightleft->balance > 0 ? -1 : 0);
+		  noderight->balance = (noderightleft->balance < 0 ? 1 : 0);
+		  noderightleft->balance = 0;
+
+		  node->branch_size =
+		    (node->left != NULL ? node->left->branch_size : 0)
+		    + 1 + (node->right != NULL ? node->right->branch_size : 0);
+		  noderight->branch_size =
+		    (noderight->left != NULL ? noderight->left->branch_size : 0)
+		    + 1 + (noderight->right != NULL ? noderight->right->branch_size : 0);
+		  noderightleft->branch_size =
+		    node->branch_size + 1 + noderight->branch_size;
+
+		  *nodep = noderightleft;
+		  height_diff = (height_diff < 0
+				 ? /* nodeleft's height had been decremented from
+				      h+1 to h.  The subtree's height changes from
+				      h+3 to h+2.  */
+				   -1
+				 : /* noderight's height had been incremented from
+				      h+1 to h+2.  The subtree's height changes from
+				      h+2 to h+2.  */
+				   0);
+		}
+	    }
+	  node = *nodep;
+	}
+      else
+	{
+	  /* No rotation needed.  Only propagation of the height change to the
+	     next higher level.  */
+	  if (height_diff < 0)
+	    height_diff = (previous_balance == 0 ? 0 : -1);
+	  else
+	    height_diff = (node->balance == 0 ? 0 : 1);
+	}
+
+      if (height_diff == 0)
+	break;
+
+      parent = node->parent;
+      if (parent == NULL)
+	break;
+    }
+}
+
+static gl_list_node_t
+gl_tree_add_first (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  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)
+    {
+      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;
+      node->balance--;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+	gl_list_node_t p;
+
+	for (p = node; p != NULL; p = p->parent)
+	  p->branch_size++;
+      }
+
+      /* Rebalance.  */
+      if (node->right == NULL && node->parent != NULL)
+	rebalance (list, node, 1, node->parent);
+    }
+
+#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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_add_last (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  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)
+    {
+      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;
+      node->balance++;
+
+      /* Update branch_size fields of the parent nodes.  */
+      {
+	gl_list_node_t p;
+
+	for (p = node; p != NULL; p = p->parent)
+	  p->branch_size++;
+      }
+
+      /* Rebalance.  */
+      if (node->left == NULL && node->parent != NULL)
+	rebalance (list, node, 1, node->parent);
+    }
+
+#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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_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 *) xmalloc (sizeof (struct gl_list_node_impl));
+  bool height_inc;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  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;
+      node->balance--;
+      height_inc = (node->right == NULL);
+    }
+  else
+    {
+      for (node = node->left; node->right != NULL; )
+	node = node->right;
+      node->right = new_node;
+      node->balance++;
+      height_inc = (node->left == NULL);
+    }
+  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++;
+  }
+
+  /* Rebalance.  */
+  if (height_inc && node->parent != NULL)
+    rebalance (list, node, 1, node->parent);
+
+#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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_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 *) xmalloc (sizeof (struct gl_list_node_impl));
+  bool height_inc;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  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;
+      node->balance++;
+      height_inc = (node->left == NULL);
+    }
+  else
+    {
+      for (node = node->right; node->left != NULL; )
+	node = node->left;
+      node->left = new_node;
+      node->balance--;
+      height_inc = (node->right == NULL);
+    }
+  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++;
+  }
+
+  /* Rebalance.  */
+  if (height_inc && node->parent != NULL)
+    rebalance (list, node, 1, node->parent);
+
+#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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static bool
+gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
+{
+  gl_list_node_t parent;
+
+#if WITH_HASHTABLE
+  /* Remove node from the hash table.
+     Note that this is only possible _before_ the node is removed from the
+     tree structure, because remove_from_bucket() uses node_position().  */
+  remove_from_bucket (list, node);
+#endif
+
+  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;
+      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--;
+	  }
+
+	  rebalance (list, child, -1, 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;
+      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--;
+	  }
+
+	  rebalance (list, child, -1, parent);
+	}
+    }
+  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;
+
+      for (subst = node->left; subst->right != NULL; )
+	subst = subst->right;
+
+      subst_parent = subst->parent;
+
+      child = subst->left;
+
+      /* 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->balance = node->balance;
+      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;
+
+      /* 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 (list, child, -1, subst_parent != node ? subst_parent : subst);
+    }
+
+  free (node);
+  return true;
+}
diff --git a/lib/gl_anyhash_list1.h b/lib/gl_anyhash_list1.h
new file mode 100644
index 0000000000..1f1351e7ac
--- /dev/null
+++ b/lib/gl_anyhash_list1.h
@@ -0,0 +1,28 @@
+/* Sequential list data type implemented by a hash table with another list.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of
+   gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
+
+/* Hash table entry.  */
+struct gl_hash_entry
+{
+  struct gl_hash_entry *hash_next;  /* chain of entries in same bucket */
+  size_t hashcode;                  /* cache of values' common hash code */
+};
+typedef struct gl_hash_entry * gl_hash_entry_t;
diff --git a/lib/gl_anyhash_list2.h b/lib/gl_anyhash_list2.h
new file mode 100644
index 0000000000..eb8d6e9771
--- /dev/null
+++ b/lib/gl_anyhash_list2.h
@@ -0,0 +1,128 @@
+/* Sequential list data type implemented by a hash table with another list.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of
+   gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
+
+/* Array of primes, approximately in steps of factor 1.2.
+   This table was computed by executing the Common Lisp expression
+     (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i))))
+   and feeding the result to PARI/gp.  */
+static const size_t primes[] =
+  {
+    11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199,
+    239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543,
+    3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899,
+    22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849,
+    140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887,
+    723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277,
+    3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307,
+    13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233,
+    47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469,
+    171731387, 206077643, 247293161, 296751781, 356102141, 427322587,
+    512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331,
+    1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL,
+    3810050851UL,
+#if SIZE_MAX > 4294967295UL
+    4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL,
+    11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL,
+    28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL,
+    70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL,
+    146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL,
+    302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL,
+    628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL,
+    1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL,
+    2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL,
+    5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL,
+    11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL,
+    24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL,
+    49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL,
+    103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL,
+    214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL,
+    445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL,
+    923114351670013UL, 1107737222003791UL, 1329284666404567UL,
+    1595141599685509UL, 1914169919622551UL, 2297003903547091UL,
+    2756404684256459UL, 3307685621107757UL, 3969222745329323UL,
+    4763067294395177UL, 5715680753274209UL, 6858816903929113UL,
+    8230580284714831UL, 9876696341657791UL, 11852035609989371UL,
+    14222442731987227UL, 17066931278384657UL, 20480317534061597UL,
+    24576381040873903UL, 29491657249048679UL, 35389988698858471UL,
+    42467986438630267UL, 50961583726356109UL, 61153900471627387UL,
+    73384680565952851UL, 88061616679143347UL, 105673940014972061UL,
+    126808728017966413UL, 152170473621559703UL, 182604568345871671UL,
+    219125482015045997UL, 262950578418055169UL, 315540694101666193UL,
+    378648832921999397UL, 454378599506399233UL, 545254319407679131UL,
+    654305183289214771UL, 785166219947057701UL, 942199463936469157UL,
+    1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL,
+    1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL,
+    3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL,
+    5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL,
+    10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL,
+    17419784962119465179UL,
+#endif
+    SIZE_MAX /* sentinel, to ensure the search terminates */
+  };
+
+/* Return a suitable prime >= ESTIMATE.  */
+static size_t
+next_prime (size_t estimate)
+{
+  size_t i;
+
+  for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++)
+    if (primes[i] >= estimate)
+      return primes[i];
+  return SIZE_MAX; /* not a prime, but better than nothing */
+}
+
+/* Resize the hash table with a new estimated size.  */
+static void
+hash_resize (gl_list_t list, size_t estimate)
+{
+  size_t new_size = next_prime (estimate);
+
+  if (new_size > list->table_size)
+    {
+      gl_hash_entry_t *old_table = list->table;
+      /* Allocate the new table.  */
+      gl_hash_entry_t *new_table =
+	(gl_hash_entry_t *) xzalloc (new_size * sizeof (gl_hash_entry_t));
+      size_t i;
+
+      /* Iterate through the entries of the old table.  */
+      for (i = list->table_size; i > 0; )
+	{
+	  gl_hash_entry_t node = old_table[--i];
+
+	  while (node != NULL)
+	    {
+	      gl_hash_entry_t next = node->hash_next;
+	      /* Add the entry to the new table.  */
+	      size_t index = node->hashcode % new_size;
+	      node->hash_next = new_table[index];
+	      new_table[index] = node;
+
+	      node = next;
+	    }
+	}
+
+      list->table = new_table;
+      list->table_size = new_size;
+      free (old_table);
+    }
+}
diff --git a/lib/gl_anylinked_list1.h b/lib/gl_anylinked_list1.h
new file mode 100644
index 0000000000..988657e5c4
--- /dev/null
+++ b/lib/gl_anylinked_list1.h
@@ -0,0 +1,49 @@
+/* Sequential list data type implemented by a linked list.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_linked_list.c and gl_linkedhash_list.c.  */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Concrete list node implementation, valid for this file only.  */
+struct gl_list_node_impl
+{
+#if WITH_HASHTABLE
+  struct gl_hash_entry h;           /* hash table entry fields; must be first */
+#endif
+  struct gl_list_node_impl *next;
+  struct gl_list_node_impl *prev;
+  const void *value;
+};
+
+/* Concrete gl_list_impl type, valid for this file only.  */
+struct gl_list_impl
+{
+  struct gl_list_impl_base base;
+#if WITH_HASHTABLE
+  /* A hash table: managed as an array of collision lists.  */
+  struct gl_hash_entry **table;
+  size_t table_size;
+#endif
+  /* A circular list anchored at root.
+     The first node is = root.next, the last node is = root.prev.
+     The root's value is unused.  */
+  struct gl_list_node_impl root;
+  /* Number of list nodes, excluding the root.  */
+  size_t count;
+};
diff --git a/lib/gl_anylinked_list2.h b/lib/gl_anylinked_list2.h
new file mode 100644
index 0000000000..d2fb089743
--- /dev/null
+++ b/lib/gl_anylinked_list2.h
@@ -0,0 +1,843 @@
+/* Sequential list data type implemented by a linked list.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_linked_list.c and gl_linkedhash_list.c.  */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+static gl_list_t
+gl_linked_create_empty (gl_list_implementation_t implementation,
+			gl_listelement_equals_fn equals_fn,
+			gl_listelement_hashcode_fn hashcode_fn,
+			bool allow_duplicates)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_fn;
+  list->base.allow_duplicates = allow_duplicates;
+#if WITH_HASHTABLE
+  list->table_size = 11;
+  list->table =
+    (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+#endif
+  list->root.next = &list->root;
+  list->root.prev = &list->root;
+  list->count = 0;
+
+  return list;
+}
+
+static gl_list_t
+gl_linked_create (gl_list_implementation_t implementation,
+		  gl_listelement_equals_fn equals_fn,
+		  gl_listelement_hashcode_fn hashcode_fn,
+		  bool allow_duplicates,
+		  size_t count, const void **contents)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+  gl_list_node_t tail;
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_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);
+    list->table =
+      (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+  }
+#endif
+  list->count = count;
+  tail = &list->root;
+  for (; count > 0; contents++, count--)
+    {
+      gl_list_node_t node =
+	(struct gl_list_node_impl *)
+	xmalloc (sizeof (struct gl_list_node_impl));
+
+      node->value = *contents;
+#if WITH_HASHTABLE
+      node->h.hashcode =
+	(list->base.hashcode_fn != NULL
+	 ? list->base.hashcode_fn (node->value)
+	 : (size_t)(uintptr_t) node->value);
+
+      /* Add node to the hash table.  */
+      add_to_bucket (list, node);
+#endif
+
+      /* Add node to the list.  */
+      node->prev = tail;
+      tail->next = node;
+      tail = node;
+    }
+  tail->next = &list->root;
+  list->root.prev = tail;
+
+  return list;
+}
+
+static size_t
+gl_linked_size (gl_list_t list)
+{
+  return list->count;
+}
+
+static const void *
+gl_linked_node_value (gl_list_t list, gl_list_node_t node)
+{
+  return node->value;
+}
+
+static gl_list_node_t
+gl_linked_next_node (gl_list_t list, gl_list_node_t node)
+{
+  return (node->next != &list->root ? node->next : NULL);
+}
+
+static gl_list_node_t
+gl_linked_previous_node (gl_list_t list, gl_list_node_t node)
+{
+  return (node->prev != &list->root ? node->prev : NULL);
+}
+
+static const void *
+gl_linked_get_at (gl_list_t list, size_t position)
+{
+  size_t count = list->count;
+  gl_list_node_t node;
+
+  if (!(position < count))
+    /* Invalid argument.  */
+    abort ();
+  /* Here we know count > 0.  */
+  if (position <= ((count - 1) / 2))
+    {
+      node = list->root.next;
+      for (; position > 0; position--)
+	node = node->next;
+    }
+  else
+    {
+      position = count - 1 - position;
+      node = list->root.prev;
+      for (; position > 0; position--)
+	node = node->prev;
+    }
+  return node->value;
+}
+
+static gl_list_node_t
+gl_linked_set_at (gl_list_t list, size_t position, const void *elt)
+{
+  size_t count = list->count;
+  gl_list_node_t node;
+
+  if (!(position < count))
+    /* Invalid argument.  */
+    abort ();
+  /* Here we know count > 0.  */
+  if (position <= ((count - 1) / 2))
+    {
+      node = list->root.next;
+      for (; position > 0; position--)
+	node = node->next;
+    }
+  else
+    {
+      position = count - 1 - position;
+      node = list->root.prev;
+      for (; position > 0; position--)
+	node = node->prev;
+    }
+#if WITH_HASHTABLE
+  if (elt != node->value)
+    {
+      size_t new_hashcode =
+	(list->base.hashcode_fn != NULL
+	 ? list->base.hashcode_fn (elt)
+	 : (size_t)(uintptr_t) elt);
+
+      if (new_hashcode != node->h.hashcode)
+	{
+	  remove_from_bucket (list, node);
+	  node->value = elt;
+	  node->h.hashcode = new_hashcode;
+	  add_to_bucket (list, node);
+	}
+      else
+	node->value = elt;
+    }
+#else
+  node->value = elt;
+#endif
+  return node;
+}
+
+static gl_list_node_t
+gl_linked_search (gl_list_t list, const void *elt)
+{
+#if WITH_HASHTABLE
+  size_t hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (elt)
+     : (size_t)(uintptr_t) elt);
+  size_t index = hashcode % list->table_size;
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+
+  if (!list->base.allow_duplicates)
+    {
+      /* Look for the first match in the hash bucket.  */
+      gl_list_node_t node;
+
+      for (node = (gl_list_node_t) list->table[index];
+	   node != NULL;
+	   node = (gl_list_node_t) node->h.hash_next)
+	if (node->h.hashcode == hashcode
+	    && (equals != NULL
+		? equals (elt, node->value)
+		: elt == node->value))
+	  return node;
+      return NULL;
+    }
+  else
+    {
+      /* Look whether there is more than one match in the hash bucket.  */
+      bool multiple_matches = false;
+      gl_list_node_t first_match = NULL;
+      gl_list_node_t node;
+
+      for (node = (gl_list_node_t) list->table[index];
+	   node != NULL;
+	   node = (gl_list_node_t) node->h.hash_next)
+	if (node->h.hashcode == hashcode
+	    && (equals != NULL
+		? equals (elt, node->value)
+		: elt == node->value))
+	  {
+	    if (first_match == NULL)
+	      first_match = node;
+	    else
+	      {
+		multiple_matches = true;
+		break;
+	      }
+	  }
+      if (!multiple_matches)
+	return first_match;
+      else
+	{
+	  /* We need the match with the smallest index.  But we don't have
+	     a fast mapping node -> index.  So we have to walk the list.  */
+	  for (node = list->root.next; node != &list->root; node = node->next)
+	    if (node->h.hashcode == hashcode
+		&& (equals != NULL
+		    ? equals (elt, node->value)
+		    : elt == node->value))
+	      return node;
+	  /* We know there are at least two matches.  */
+	  abort ();
+	}
+    }
+#else
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  gl_list_node_t node;
+
+  if (equals != NULL)
+    {
+      for (node = list->root.next; node != &list->root; node = node->next)
+	if (equals (elt, node->value))
+	  return node;
+    }
+  else
+    {
+      for (node = list->root.next; node != &list->root; node = node->next)
+	if (elt == node->value)
+	  return node;
+    }
+  return NULL;
+#endif
+}
+
+static size_t
+gl_linked_indexof (gl_list_t list, const void *elt)
+{
+#if WITH_HASHTABLE
+  /* Here the hash table doesn't help much.  It only allows us to minimize
+     the number of equals() calls, by looking up first the node and then
+     its index.  */
+  size_t hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (elt)
+     : (size_t)(uintptr_t) elt);
+  size_t index = hashcode % list->table_size;
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  gl_list_node_t node;
+
+  /* First step: Look up the node.  */
+  if (!list->base.allow_duplicates)
+    {
+      /* Look for the first match in the hash bucket.  */
+      for (node = (gl_list_node_t) list->table[index];
+	   node != NULL;
+	   node = (gl_list_node_t) node->h.hash_next)
+	if (node->h.hashcode == hashcode
+	    && (equals != NULL
+		? equals (elt, node->value)
+		: elt == node->value))
+	  break;
+    }
+  else
+    {
+      /* Look whether there is more than one match in the hash bucket.  */
+      bool multiple_matches = false;
+      gl_list_node_t first_match = NULL;
+
+      for (node = (gl_list_node_t) list->table[index];
+	   node != NULL;
+	   node = (gl_list_node_t) node->h.hash_next)
+	if (node->h.hashcode == hashcode
+	    && (equals != NULL
+		? equals (elt, node->value)
+		: elt == node->value))
+	  {
+	    if (first_match == NULL)
+	      first_match = node;
+	    else
+	      {
+		multiple_matches = true;
+		break;
+	      }
+	  }
+      if (multiple_matches)
+	{
+	  /* We need the match with the smallest index.  But we don't have
+	     a fast mapping node -> index.  So we have to walk the list.  */
+	  size_t index;
+
+	  for (node = list->root.next, index = 0;
+	       node != &list->root;
+	       node = node->next, index++)
+	    if (node->h.hashcode == hashcode
+		&& (equals != NULL
+		    ? equals (elt, node->value)
+		    : elt == node->value))
+	      return index;
+	  /* We know there are at least two matches.  */
+	  abort ();
+	}
+      node = first_match;
+    }
+
+  /* Second step: Look up the index of the node.  */
+  if (node == NULL)
+    return (size_t)(-1);
+  else
+    {
+      size_t index = 0;
+
+      for (; node->prev != &list->root; node = node->prev)
+	index++;
+
+      return index;
+    }
+#else
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  gl_list_node_t node;
+
+  if (equals != NULL)
+    {
+      size_t index;
+      for (node = list->root.next, index = 0;
+	   node != &list->root;
+	   node = node->next, index++)
+	if (equals (elt, node->value))
+	  return index;
+    }
+  else
+    {
+      size_t index;
+      for (node = list->root.next, index = 0;
+	   node != &list->root;
+	   node = node->next, index++)
+	if (elt == node->value)
+	  return index;
+    }
+  return (size_t)(-1);
+#endif
+}
+
+static gl_list_node_t
+gl_linked_add_first (gl_list_t list, const void *elt)
+{
+  gl_list_node_t node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  node->value = elt;
+#if WITH_HASHTABLE
+  node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (node->value)
+     : (size_t)(uintptr_t) node->value);
+
+  /* Add node to the hash table.  */
+  add_to_bucket (list, node);
+#endif
+
+  /* Add node to the list.  */
+  node->prev = &list->root;
+  node->next = list->root.next;
+  node->next->prev = node;
+  list->root.next = node;
+  list->count++;
+
+#if WITH_HASHTABLE
+  hash_resize_after_add (list);
+#endif
+
+  return node;
+}
+
+static gl_list_node_t
+gl_linked_add_last (gl_list_t list, const void *elt)
+{
+  gl_list_node_t node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  node->value = elt;
+#if WITH_HASHTABLE
+  node->h.hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (node->value)
+     : (size_t)(uintptr_t) node->value);
+
+  /* Add node to the hash table.  */
+  add_to_bucket (list, node);
+#endif
+
+  /* Add node to the list.  */
+  node->next = &list->root;
+  node->prev = list->root.prev;
+  node->prev->next = node;
+  list->root.prev = node;
+  list->count++;
+
+#if WITH_HASHTABLE
+  hash_resize_after_add (list);
+#endif
+
+  return node;
+}
+
+static gl_list_node_t
+gl_linked_add_before (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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);
+
+  /* Add new_node to the hash table.  */
+  add_to_bucket (list, new_node);
+#endif
+
+  /* Add new_node to the list.  */
+  new_node->next = node;
+  new_node->prev = node->prev;
+  new_node->prev->next = new_node;
+  node->prev = new_node;
+  list->count++;
+
+#if WITH_HASHTABLE
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_linked_add_after (gl_list_t list, gl_list_node_t node, const void *elt)
+{
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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);
+
+  /* Add new_node to the hash table.  */
+  add_to_bucket (list, new_node);
+#endif
+
+  /* Add new_node to the list.  */
+  new_node->prev = node;
+  new_node->next = node->next;
+  new_node->next->prev = new_node;
+  node->next = new_node;
+  list->count++;
+
+#if WITH_HASHTABLE
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_linked_add_at (gl_list_t list, size_t position, const void *elt)
+{
+  size_t count = list->count;
+  gl_list_node_t new_node;
+
+  if (!(position <= count))
+    /* Invalid argument.  */
+    abort ();
+
+  new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+  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);
+
+  /* Add new_node to the hash table.  */
+  add_to_bucket (list, new_node);
+#endif
+
+  /* Add new_node to the list.  */
+  if (position <= (count / 2))
+    {
+      gl_list_node_t node;
+
+      node = &list->root;
+      for (; position > 0; position--)
+	node = node->next;
+      new_node->prev = node;
+      new_node->next = node->next;
+      new_node->next->prev = new_node;
+      node->next = new_node;
+    }
+  else
+    {
+      gl_list_node_t node;
+
+      position = count - position;
+      node = &list->root;
+      for (; position > 0; position--)
+	node = node->prev;
+      new_node->next = node;
+      new_node->prev = node->prev;
+      new_node->prev->next = new_node;
+      node->prev = new_node;
+    }
+  list->count++;
+
+#if WITH_HASHTABLE
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static bool
+gl_linked_remove_node (gl_list_t list, gl_list_node_t node)
+{
+  gl_list_node_t prev;
+  gl_list_node_t next;
+
+#if WITH_HASHTABLE
+  /* Remove node from the hash table.  */
+  remove_from_bucket (list, node);
+#endif
+
+  /* Remove node from the list.  */
+  prev = node->prev;
+  next = node->next;
+
+  prev->next = next;
+  next->prev = prev;
+  list->count--;
+
+  free (node);
+  return true;
+}
+
+static bool
+gl_linked_remove_at (gl_list_t list, size_t position)
+{
+  size_t count = list->count;
+  gl_list_node_t removed_node;
+
+  if (!(position < count))
+    /* Invalid argument.  */
+    abort ();
+  /* Here we know count > 0.  */
+  if (position <= ((count - 1) / 2))
+    {
+      gl_list_node_t node;
+      gl_list_node_t after_removed;
+
+      node = &list->root;
+      for (; position > 0; position--)
+	node = node->next;
+      removed_node = node->next;
+      after_removed = node->next->next;
+      node->next = after_removed;
+      after_removed->prev = node;
+    }
+  else
+    {
+      gl_list_node_t node;
+      gl_list_node_t before_removed;
+
+      position = count - 1 - position;
+      node = &list->root;
+      for (; position > 0; position--)
+	node = node->prev;
+      removed_node = node->prev;
+      before_removed = node->prev->prev;
+      node->prev = before_removed;
+      before_removed->next = node;
+    }
+#if WITH_HASHTABLE
+  remove_from_bucket (list, removed_node);
+#endif
+  list->count--;
+
+  free (removed_node);
+  return true;
+}
+
+static bool
+gl_linked_remove (gl_list_t list, const void *elt)
+{
+  gl_list_node_t node = gl_linked_search (list, elt);
+
+  if (node != NULL)
+    return gl_linked_remove_node (list, node);
+  else
+    return false;
+}
+
+static void
+gl_linked_list_free (gl_list_t list)
+{
+  gl_list_node_t node;
+
+  for (node = list->root.next; node != &list->root; )
+    {
+      gl_list_node_t next = node->next;
+      free (node);
+      node = next;
+    }
+#if WITH_HASHTABLE
+  free (list->table);
+#endif
+  free (list);
+}
+
+/* --------------------- gl_list_iterator_t Data Type --------------------- */
+
+static gl_list_iterator_t
+gl_linked_iterator (gl_list_t list)
+{
+  gl_list_iterator_t result;
+
+  result.vtable = list->base.vtable;
+  result.list = list;
+  result.p = list->root.next;
+  result.q = &list->root;
+
+  return result;
+}
+
+static gl_list_iterator_t
+gl_linked_iterator_from_to (gl_list_t list,
+			    size_t start_index, size_t end_index)
+{
+  gl_list_iterator_t result;
+  size_t n1, n2, n3;
+
+  if (!(start_index <= end_index && end_index <= list->count))
+    /* Invalid arguments.  */
+    abort ();
+  result.vtable = list->base.vtable;
+  result.list = list;
+  n1 = start_index;
+  n2 = end_index - start_index;
+  n3 = list->count - end_index;
+  /* Find the maximum among n1, n2, n3, so as to reduce the number of
+     loop iterations to n1 + n2 + n3 - max(n1,n2,n3).  */
+  if (n1 > n2 && n1 > n3)
+    {
+      /* n1 is the maximum, use n2 and n3.  */
+      gl_list_node_t node;
+      size_t i;
+
+      node = &list->root;
+      for (i = n3; i > 0; i--)
+	node = node->prev;
+      result.q = node;
+      for (i = n2; i > 0; i--)
+	node = node->prev;
+      result.p = node;
+    }
+  else if (n2 > n3)
+    {
+      /* n2 is the maximum, use n1 and n3.  */
+      gl_list_node_t node;
+      size_t i;
+
+      node = list->root.next;
+      for (i = n1; i > 0; i--)
+	node = node->next;
+      result.p = node;
+
+      node = &list->root;
+      for (i = n3; i > 0; i--)
+	node = node->prev;
+      result.q = node;
+    }
+  else
+    {
+      /* n3 is the maximum, use n1 and n2.  */
+      gl_list_node_t node;
+      size_t i;
+
+      node = list->root.next;
+      for (i = n1; i > 0; i--)
+	node = node->next;
+      result.p = node;
+      for (i = n2; i > 0; i--)
+	node = node->next;
+      result.q = node;
+    }
+
+  return result;
+}
+
+static bool
+gl_linked_iterator_next (gl_list_iterator_t *iterator,
+			 const void **eltp, gl_list_node_t *nodep)
+{
+  if (iterator->p != iterator->q)
+    {
+      gl_list_node_t node = (gl_list_node_t) iterator->p;
+      *eltp = node->value;
+      if (nodep != NULL)
+	*nodep = node;
+      iterator->p = node->next;
+      return true;
+    }
+  else
+    return false;
+}
+
+static void
+gl_linked_iterator_free (gl_list_iterator_t *iterator)
+{
+}
+
+/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
+
+static gl_list_node_t
+gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
+			     const void *elt)
+{
+  gl_list_node_t node;
+
+  for (node = list->root.next; node != &list->root; node = node->next)
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp > 0)
+	break;
+      if (cmp == 0)
+	return node;
+    }
+  return NULL;
+}
+
+static size_t
+gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+			      const void *elt)
+{
+  gl_list_node_t node;
+  size_t index;
+
+  for (node = list->root.next, index = 0;
+       node != &list->root;
+       node = node->next, index++)
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp > 0)
+	break;
+      if (cmp == 0)
+	return index;
+    }
+  return (size_t)(-1);
+}
+
+static gl_list_node_t
+gl_linked_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
+			  const void *elt)
+{
+  gl_list_node_t node;
+
+  for (node = list->root.next; node != &list->root; node = node->next)
+    if (compar (node->value, elt) >= 0)
+      return gl_linked_add_before (list, node, elt);
+  return gl_linked_add_last (list, elt);
+}
+
+static bool
+gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
+			     const void *elt)
+{
+  gl_list_node_t node;
+
+  for (node = list->root.next; node != &list->root; node = node->next)
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp > 0)
+	break;
+      if (cmp == 0)
+	return gl_linked_remove_node (list, node);
+    }
+  return false;
+}
diff --git a/lib/gl_anyrbtree_list1.h b/lib/gl_anyrbtree_list1.h
new file mode 100644
index 0000000000..de77066820
--- /dev/null
+++ b/lib/gl_anyrbtree_list1.h
@@ -0,0 +1,77 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c.  */
+
+/* A red-black tree is a binary tree where every node is colored black or
+   red such that
+   1. The root is black.
+   2. No red node has a red parent.
+      Or equivalently: No red node has a red child.
+   3. All paths from the root down to any NULL endpoint contain the same
+      number of black nodes.
+   Let's call this the "black-height" bh of the tree.  It follows that every
+   such path contains exactly bh black and between 0 and bh red nodes.  (The
+   extreme cases are a path containing only black nodes, and a path colored
+   alternatingly black-red-black-red-...-black-red.)  The height of the tree
+   therefore is >= bh, <= 2*bh.
+ */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Color of a node.  */
+typedef enum color { BLACK, RED } color_t;
+
+/* Concrete list node implementation, valid for this file only.  */
+struct gl_list_node_impl
+{
+#if WITH_HASHTABLE
+  struct gl_hash_entry h;           /* hash table entry fields; must be first */
+#endif
+  struct gl_list_node_impl *left;   /* left branch, or NULL */
+  struct gl_list_node_impl *right;  /* right branch, or NULL */
+  /* Parent pointer, or NULL. The parent pointer is not needed for most
+     operations.  It is needed so that a gl_list_node_t can be returned
+     without memory allocation, on which the functions gl_list_remove_node,
+     gl_list_add_before, gl_list_add_after can be implemented.  */
+  struct gl_list_node_impl *parent;
+  color_t color;                    /* node's color */
+  size_t branch_size;               /* number of nodes in this branch,
+				       = branchsize(left)+branchsize(right)+1 */
+  const void *value;
+};
+
+/* Concrete gl_list_impl type, valid for this file only.  */
+struct gl_list_impl
+{
+  struct gl_list_impl_base base;
+#if WITH_HASHTABLE
+  /* A hash table: managed as an array of collision lists.  */
+  struct gl_hash_entry **table;
+  size_t table_size;
+#endif
+  struct gl_list_node_impl *root;   /* root node or NULL */
+};
+
+/* A red-black tree of height h has a black-height bh >= ceil(h/2) and
+   therefore at least 2^ceil(h/2) - 1 elements.  So, h <= 116 (because a tree
+   of height h >= 117 would have at least 2^59 - 1 elements, and because even
+   on 64-bit machines,
+     sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64
+   this would exceed the address space of the machine.  */
+#define MAXHEIGHT 116
diff --git a/lib/gl_anyrbtree_list2.h b/lib/gl_anyrbtree_list2.h
new file mode 100644
index 0000000000..07eebcd43e
--- /dev/null
+++ b/lib/gl_anyrbtree_list2.h
@@ -0,0 +1,971 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c.  */
+
+/* -------------------------- gl_list_t Data Type -------------------------- */
+
+/* Create 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.  */
+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 *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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);
+      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);
+      node->right->parent = node;
+    }
+  else
+    node->right = NULL;
+
+  node->color = (bh == 0 ? RED : BLACK);
+
+  node->branch_size = count;
+
+  return node;
+}
+
+static gl_list_t
+gl_tree_create (gl_list_implementation_t implementation,
+		gl_listelement_equals_fn equals_fn,
+		gl_listelement_hashcode_fn hashcode_fn,
+		bool allow_duplicates,
+		size_t count, const void **contents)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_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);
+    list->table =
+      (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+  }
+#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);
+      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.  */
+      add_nodes_to_buckets (list);
+#endif
+    }
+  else
+    list->root = NULL;
+
+  return list;
+}
+
+/* Rotate left a subtree.
+
+			 B                         D
+		       /   \                     /   \
+		     A       D       -->       B       E
+			    / \               / \
+			   C   E             A   C
+
+   Change the tree structure, update the branch sizes.
+   The caller must update the colors and register D as child of its parent.  */
+static inline 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;
+}
+
+/* Rotate right a subtree.
+
+			   D                     B
+			 /   \                 /   \
+		       B       E     -->     A       D
+		      / \                           / \
+		     A   C                         C   E
+
+   Change the tree structure, update the branch sizes.
+   The caller must update the colors and register B as child of its parent.  */
+static inline 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;
+}
+
+/* Ensure 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;
+	}
+    }
+}
+
+/* Ensure 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 gl_list_node_t
+gl_tree_add_first (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_add_last (gl_list_t list, const void *elt)
+{
+  /* Create new node.  */
+  gl_list_node_t new_node =
+    (struct gl_list_node_impl *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_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 *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static gl_list_node_t
+gl_tree_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 *) xmalloc (sizeof (struct gl_list_node_impl));
+
+  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().  */
+  add_to_bucket (list, new_node);
+  hash_resize_after_add (list);
+#endif
+
+  return new_node;
+}
+
+static bool
+gl_tree_remove_node (gl_list_t list, gl_list_node_t node)
+{
+  gl_list_node_t parent;
+
+#if WITH_HASHTABLE
+  /* Remove node from the hash table.
+     Note that this is only possible _before_ the node is removed from the
+     tree structure, because remove_from_bucket() uses node_position().  */
+  remove_from_bucket (list, node);
+#endif
+
+  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);
+	}
+    }
+
+  free (node);
+  return true;
+}
diff --git a/lib/gl_anytree_list1.h b/lib/gl_anytree_list1.h
new file mode 100644
index 0000000000..cfc0008469
--- /dev/null
+++ b/lib/gl_anytree_list1.h
@@ -0,0 +1,30 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
+                  gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
+
+/* An item on the stack used for iterating across the elements.  */
+typedef struct
+{
+  gl_list_node_t node;
+  bool rightp;
+} iterstack_item_t;
+
+/* A stack used for iterating across the elements.  */
+typedef iterstack_item_t iterstack_t[MAXHEIGHT];
diff --git a/lib/gl_anytree_list2.h b/lib/gl_anytree_list2.h
new file mode 100644
index 0000000000..19ecae5f70
--- /dev/null
+++ b/lib/gl_anytree_list2.h
@@ -0,0 +1,547 @@
+/* Sequential list data type implemented by a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltree_list.c, gl_rbtree_list.c,
+                  gl_avltreehash_list.c, gl_rbtreehash_list.c.  */
+
+static gl_list_t
+gl_tree_create_empty (gl_list_implementation_t implementation,
+		      gl_listelement_equals_fn equals_fn,
+		      gl_listelement_hashcode_fn hashcode_fn,
+		      bool allow_duplicates)
+{
+  struct gl_list_impl *list =
+    (struct gl_list_impl *) xmalloc (sizeof (struct gl_list_impl));
+
+  list->base.vtable = implementation;
+  list->base.equals_fn = equals_fn;
+  list->base.hashcode_fn = hashcode_fn;
+  list->base.allow_duplicates = allow_duplicates;
+#if WITH_HASHTABLE
+  list->table_size = 11;
+  list->table =
+    (gl_hash_entry_t *) xzalloc (list->table_size * sizeof (gl_hash_entry_t));
+#endif
+  list->root = NULL;
+
+  return list;
+}
+
+static size_t
+gl_tree_size (gl_list_t list)
+{
+  return (list->root != NULL ? list->root->branch_size : 0);
+}
+
+static const void *
+gl_tree_node_value (gl_list_t list, gl_list_node_t node)
+{
+  return node->value;
+}
+
+static gl_list_node_t
+gl_tree_next_node (gl_list_t list, gl_list_node_t node)
+{
+  if (node->right != NULL)
+    {
+      node = node->right;
+      while (node->left != NULL)
+	node = node->left;
+    }
+  else
+    {
+      while (node->parent != NULL && node->parent->right == node)
+	node = node->parent;
+      node = node->parent;
+    }
+  return node;
+}
+
+static gl_list_node_t
+gl_tree_previous_node (gl_list_t list, gl_list_node_t node)
+{
+  if (node->left != NULL)
+    {
+      node = node->left;
+      while (node->right != NULL)
+	node = node->right;
+    }
+  else
+    {
+      while (node->parent != NULL && node->parent->left == node)
+	node = node->parent;
+      node = node->parent;
+    }
+  return node;
+}
+
+/* Return the node at the given position < gl_tree_size (list).  */
+static inline gl_list_node_t
+node_at (gl_list_node_t root, size_t position)
+{
+  /* Here we know that root != NULL.  */
+  gl_list_node_t node = root;
+
+  for (;;)
+    {
+      if (node->left != NULL)
+	{
+	  if (position < node->left->branch_size)
+	    {
+	      node = node->left;
+	      continue;
+	    }
+	  position -= node->left->branch_size;
+	}
+      if (position == 0)
+	break;
+      position--;
+      node = node->right;
+    }
+  return node;
+}
+
+static const void *
+gl_tree_get_at (gl_list_t list, size_t position)
+{
+  gl_list_node_t node = list->root;
+
+  if (!(node != NULL && position < node->branch_size))
+    /* Invalid argument.  */
+    abort ();
+  node = node_at (node, position);
+  return node->value;
+}
+
+static gl_list_node_t
+gl_tree_set_at (gl_list_t list, size_t position, const void *elt)
+{
+  gl_list_node_t node = list->root;
+
+  if (!(node != NULL && position < node->branch_size))
+    /* Invalid argument.  */
+    abort ();
+  node = node_at (node, position);
+#if WITH_HASHTABLE
+  if (elt != node->value)
+    {
+      size_t new_hashcode =
+	(list->base.hashcode_fn != NULL
+	 ? list->base.hashcode_fn (elt)
+	 : (size_t)(uintptr_t) elt);
+
+      if (new_hashcode != node->h.hashcode)
+	{
+	  remove_from_bucket (list, node);
+	  node->value = elt;
+	  node->h.hashcode = new_hashcode;
+	  add_to_bucket (list, node);
+	}
+      else
+	node->value = elt;
+    }
+#else
+  node->value = elt;
+#endif
+  return node;
+}
+
+#if !WITH_HASHTABLE
+
+static gl_list_node_t
+gl_tree_search (gl_list_t list, const void *elt)
+{
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  /* Iterate across all elements.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+
+  for (;;)
+    {
+      /* Descend on left branch.  */
+      for (;;)
+	{
+	  if (node == NULL)
+	    break;
+	  stack_ptr->node = node;
+	  stack_ptr->rightp = false;
+	  node = node->left;
+	  stack_ptr++;
+	}
+      /* Climb up again.  */
+      for (;;)
+	{
+	  if (stack_ptr == &stack[0])
+	    return NULL;
+	  stack_ptr--;
+	  if (!stack_ptr->rightp)
+	    break;
+	}
+      node = stack_ptr->node;
+      /* Test against current element.  */
+      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	return node;
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+}
+
+static size_t
+gl_tree_indexof (gl_list_t list, const void *elt)
+{
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  /* Iterate across all elements.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+  size_t index = 0;
+
+  for (;;)
+    {
+      /* Descend on left branch.  */
+      for (;;)
+	{
+	  if (node == NULL)
+	    break;
+	  stack_ptr->node = node;
+	  stack_ptr->rightp = false;
+	  node = node->left;
+	  stack_ptr++;
+	}
+      /* Climb up again.  */
+      for (;;)
+	{
+	  if (stack_ptr == &stack[0])
+	    return (size_t)(-1);
+	  stack_ptr--;
+	  if (!stack_ptr->rightp)
+	    break;
+	}
+      node = stack_ptr->node;
+      /* Test against current element.  */
+      if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	return index;
+      index++;
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+}
+
+#endif
+
+static gl_list_node_t
+gl_tree_add_at (gl_list_t list, size_t position, const void *elt)
+{
+  size_t count = (list->root != NULL ? list->root->branch_size : 0);
+
+  if (!(position <= count))
+    /* Invalid argument.  */
+    abort ();
+  if (position == count)
+    return gl_tree_add_last (list, elt);
+  else
+    return gl_tree_add_before (list, node_at (list->root, position), elt);
+}
+
+static bool
+gl_tree_remove_at (gl_list_t list, size_t position)
+{
+  gl_list_node_t node = list->root;
+
+  if (!(node != NULL && position < node->branch_size))
+    /* Invalid argument.  */
+    abort ();
+  node = node_at (node, position);
+  return gl_tree_remove_node (list, node);
+}
+
+static bool
+gl_tree_remove (gl_list_t list, const void *elt)
+{
+  gl_list_node_t node = gl_tree_search (list, elt);
+
+  if (node != NULL)
+    return gl_tree_remove_node (list, node);
+  else
+    return false;
+}
+
+#if !WITH_HASHTABLE
+
+static void
+gl_tree_list_free (gl_list_t list)
+{
+  /* Iterate across all elements in post-order.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+
+  for (;;)
+    {
+      /* Descend on left branch.  */
+      for (;;)
+	{
+	  if (node == NULL)
+	    break;
+	  stack_ptr->node = node;
+	  stack_ptr->rightp = false;
+	  node = node->left;
+	  stack_ptr++;
+	}
+      /* Climb up again.  */
+      for (;;)
+	{
+	  if (stack_ptr == &stack[0])
+	    goto done_iterate;
+	  stack_ptr--;
+	  node = stack_ptr->node;
+	  if (!stack_ptr->rightp)
+	    break;
+	  /* Free the current node.  */
+	  free (node);
+	}
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+ done_iterate:
+  free (list);
+}
+
+#endif
+
+/* --------------------- gl_list_iterator_t Data Type --------------------- */
+
+static gl_list_iterator_t
+gl_tree_iterator (gl_list_t list)
+{
+  gl_list_iterator_t result;
+  gl_list_node_t node;
+
+  result.vtable = list->base.vtable;
+  result.list = list;
+  /* Start node is the leftmost node.  */
+  node = list->root;
+  if (node != NULL)
+    while (node->left != NULL)
+      node = node->left;
+  result.p = node;
+  /* End point is past the rightmost node.  */
+  result.q = NULL;
+
+  return result;
+}
+
+static gl_list_iterator_t
+gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index)
+{
+  size_t count = (list->root != NULL ? list->root->branch_size : 0);
+  gl_list_iterator_t result;
+
+  if (!(start_index <= end_index && end_index <= count))
+    /* Invalid arguments.  */
+    abort ();
+  result.vtable = list->base.vtable;
+  result.list = list;
+  /* Start node is the node at position start_index.  */
+  result.p = (start_index < count ? node_at (list->root, start_index) : NULL);
+  /* End point is the node at position end_index.  */
+  result.q = (end_index < count ? node_at (list->root, end_index) : NULL);
+
+  return result;
+}
+
+static bool
+gl_tree_iterator_next (gl_list_iterator_t *iterator,
+		       const void **eltp, gl_list_node_t *nodep)
+{
+  if (iterator->p != iterator->q)
+    {
+      gl_list_node_t node = (gl_list_node_t) iterator->p;
+      *eltp = node->value;
+      if (nodep != NULL)
+	*nodep = node;
+      /* Advance to the next node.  */
+      if (node->right != NULL)
+	{
+	  node = node->right;
+	  while (node->left != NULL)
+	    node = node->left;
+	}
+      else
+	{
+	  while (node->parent != NULL && node->parent->right == node)
+	    node = node->parent;
+	  node = node->parent;
+	}
+      iterator->p = node;
+      return true;
+    }
+  else
+    return false;
+}
+
+static void
+gl_tree_iterator_free (gl_list_iterator_t *iterator)
+{
+}
+
+/* ---------------------- Sorted gl_list_t Data Type ---------------------- */
+
+static gl_list_node_t
+gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar,
+			   const void *elt)
+{
+  gl_list_node_t node;
+
+  for (node = list->root; node != NULL; )
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp < 0)
+	node = node->right;
+      else if (cmp > 0)
+	node = node->left;
+      else /* cmp == 0 */
+	{
+	  /* We have an element equal to ELT.  But we need the leftmost such
+	     element.  */
+	  gl_list_node_t found = node;
+	  node = node->left;
+	  for (; node != NULL; )
+	    {
+	      int cmp2 = compar (node->value, elt);
+
+	      if (cmp2 < 0)
+		node = node->right;
+	      else if (cmp2 > 0)
+		/* The list was not sorted.  */
+		abort ();
+	      else /* cmp2 == 0 */
+		{
+		  found = node;
+		  node = node->left;
+		}
+	    }
+	  return found;
+	}
+    }
+  return NULL;
+}
+
+static size_t
+gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar,
+			    const void *elt)
+{
+  gl_list_node_t node;
+  size_t position;
+
+  for (node = list->root, position = 0; node != NULL; )
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp < 0)
+	{
+	  if (node->left != NULL)
+	    position += node->left->branch_size;
+	  position++;
+	  node = node->right;
+	}
+      else if (cmp > 0)
+	node = node->left;
+      else /* cmp == 0 */
+	{
+	  /* We have an element equal to ELT.  But we need the leftmost such
+	     element.  */
+	  size_t found_position =
+	    position + (node->left != NULL ? node->left->branch_size : 0);
+	  node = node->left;
+	  for (; node != NULL; )
+	    {
+	      int cmp2 = compar (node->value, elt);
+
+	      if (cmp2 < 0)
+		{
+		  if (node->left != NULL)
+		    position += node->left->branch_size;
+		  position++;
+		  node = node->right;
+		}
+	      else if (cmp2 > 0)
+		/* The list was not sorted.  */
+		abort ();
+	      else /* cmp2 == 0 */
+		{
+		  found_position =
+		    position
+		    + (node->left != NULL ? node->left->branch_size : 0);
+		  node = node->left;
+		}
+	    }
+	  return found_position;
+	}
+    }
+  return (size_t)(-1);
+}
+
+static gl_list_node_t
+gl_tree_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar,
+			const void *elt)
+{
+  gl_list_node_t node = list->root;
+
+  if (node == NULL)
+    return gl_tree_add_first (list, elt);
+
+  for (;;)
+    {
+      int cmp = compar (node->value, elt);
+
+      if (cmp < 0)
+	{
+	  if (node->right == NULL)
+	    return gl_tree_add_after (list, node, elt);
+	  node = node->right;
+	}
+      else if (cmp > 0)
+	{
+	  if (node->left == NULL)
+	    return gl_tree_add_before (list, node, elt);
+	  node = node->left;
+	}
+      else /* cmp == 0 */
+	return gl_tree_add_before (list, node, elt);
+    }
+}
+
+static bool
+gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar,
+			   const void *elt)
+{
+  gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt);
+  if (node != NULL)
+    return gl_tree_remove_node (list, node);
+  else
+    return false;
+}
diff --git a/lib/gl_anytreehash_list1.h b/lib/gl_anytreehash_list1.h
new file mode 100644
index 0000000000..7f38180c9c
--- /dev/null
+++ b/lib/gl_anytreehash_list1.h
@@ -0,0 +1,291 @@
+/* Sequential list data type implemented by a hash table with a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c.  */
+
+/* Hash table entry representing the same value at more than one position.  */
+struct gl_multiple_nodes
+{
+  struct gl_hash_entry h;           /* hash table entry fields; must be first */
+  void *magic;                      /* used to distinguish from single node */
+  gl_oset_t nodes;                  /* set of nodes, sorted by position */
+};
+/* A value that cannot occur at the corresponding field (->left) in
+   gl_list_node_impl.  */
+#define MULTIPLE_NODES_MAGIC  (void *) -1
+
+/* Resize the hash table if needed, after list->count was incremented.  */
+static inline void
+hash_resize_after_add (gl_list_t list)
+{
+  size_t count = (list->root != 0 ? list->root->branch_size : 0);
+  size_t estimate = xsum (count, count / 2); /* 1.5 * count */
+  if (estimate > list->table_size)
+    hash_resize (list, estimate);
+}
+
+/* Return the position of the given node in the tree.  */
+static size_t
+node_position (gl_list_node_t node)
+{
+  size_t position = 0;
+
+  if (node->left != NULL)
+    position += node->left->branch_size;
+  for (;;)
+    {
+      gl_list_node_t parent = node->parent;
+
+      if (parent == NULL)
+	return position;
+      /* position is now relative to the subtree of node.  */
+      if (parent->right == node)
+	{
+	  position += 1;
+	  if (parent->left != NULL)
+	    position += parent->left->branch_size;
+	}
+      /* position is now relative to the subtree of parent.  */
+      node = parent;
+    }
+}
+
+/* Compares two nodes by their position in the tree.  */
+static int
+compare_by_position (const void *x1, const void *x2)
+{
+  gl_list_node_t node1 = (gl_list_node_t) x1;
+  gl_list_node_t node2 = (gl_list_node_t) x2;
+  size_t position1 = node_position (node1);
+  size_t position2 = node_position (node2);
+
+  return (position1 > position2 ? 1 :
+	  position1 < position2 ? -1 : 0);
+}
+
+/* Return the first element of a non-empty ordered set of nodes.  */
+static inline gl_list_node_t
+gl_oset_first (gl_oset_t set)
+{
+  gl_oset_iterator_t iter = gl_oset_iterator (set);
+  const void *first;
+
+  if (!gl_oset_iterator_next (&iter, &first))
+    abort ();
+  gl_oset_iterator_free (&iter);
+  return (gl_list_node_t) first;
+}
+
+/* Add a node to the hash table structure.
+   If duplicates are allowed, this function performs in average time
+   O((log n)^2): gl_oset_add may need to add an element to an ordered set of
+   size O(n), needing O(log n) comparison function calls.  The comparison
+   function is compare_by_position, which is O(log n) worst-case.
+   If duplicates are forbidden, this function is O(1).  */
+static void
+add_to_bucket (gl_list_t list, gl_list_node_t new_node)
+{
+  size_t index = new_node->h.hashcode % list->table_size;
+
+  /* If no duplicates are allowed, multiple nodes are not needed.  */
+  if (list->base.allow_duplicates)
+    {
+      size_t hashcode = new_node->h.hashcode;
+      const void *value = new_node->value;
+      gl_listelement_equals_fn equals = list->base.equals_fn;
+      gl_hash_entry_t *entryp;
+
+      for (entryp = &list->table[index]; *entryp != NULL; entryp = &(*entryp)->hash_next)
+	{
+	  gl_hash_entry_t entry = *entryp;
+
+	  if (entry->hashcode == hashcode)
+	    {
+	      if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
+		{
+		  /* An entry representing multiple nodes.  */
+		  gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
+		  /* Only the first node is interesting.  */
+		  gl_list_node_t node = gl_oset_first (nodes);
+		  if (equals != NULL ? equals (value, node->value) : value == node->value)
+		    {
+		      /* Found already multiple nodes with the same value.
+			 Add the new_node to it.  */
+		      gl_oset_add (nodes, new_node);
+		      return;
+		    }
+		}
+	      else
+		{
+		  /* An entry representing a single node.  */
+		  gl_list_node_t node = (struct gl_list_node_impl *) entry;
+		  if (equals != NULL ? equals (value, node->value) : value == node->value)
+		    {
+		      /* Found already a node with the same value.  Turn it
+			 into an ordered set, and add new_node to it.  */
+		      gl_oset_t nodes;
+		      struct gl_multiple_nodes *multi_entry;
+
+		      nodes =
+			gl_oset_create_empty (OSET_TREE_FLAVOR,
+					      compare_by_position);
+
+		      gl_oset_add (nodes, node);
+		      gl_oset_add (nodes, new_node);
+
+		      multi_entry =
+			(struct gl_multiple_nodes *) xmalloc (sizeof (struct gl_multiple_nodes));
+		      multi_entry->h.hash_next = entry->hash_next;
+		      multi_entry->h.hashcode = entry->hashcode;
+		      multi_entry->magic = MULTIPLE_NODES_MAGIC;
+		      multi_entry->nodes = nodes;
+		      *entryp = &multi_entry->h;
+		      return;
+		    }
+		}
+	    }
+	}
+    }
+  /* If no duplicates are allowed, multiple nodes are not needed.  */
+  new_node->h.hash_next = list->table[index];
+  list->table[index] = &new_node->h;
+}
+
+/* Remove a node from the hash table structure.
+   If duplicates are allowed, this function performs in average time
+   O((log n)^2): gl_oset_remove may need to remove an element from an ordered
+   set of size O(n), needing O(log n) comparison function calls.  The
+   comparison function is compare_by_position, which is O(log n) worst-case.
+   If duplicates are forbidden, this function is O(1) on average.  */
+static void
+remove_from_bucket (gl_list_t list, gl_list_node_t old_node)
+{
+  size_t index = old_node->h.hashcode % list->table_size;
+
+  if (list->base.allow_duplicates)
+    {
+      size_t hashcode = old_node->h.hashcode;
+      const void *value = old_node->value;
+      gl_listelement_equals_fn equals = list->base.equals_fn;
+      gl_hash_entry_t *entryp;
+
+      for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
+	{
+	  gl_hash_entry_t entry = *entryp;
+
+	  if (entry == &old_node->h)
+	    {
+	      /* Found old_node as a single node in the bucket.  Remove it.  */
+	      *entryp = old_node->h.hash_next;
+	      break;
+	    }
+	  if (entry == NULL)
+	    /* node is not in the right bucket.  Did the hash codes
+	       change inadvertently?  */
+	    abort ();
+	  if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC
+	      && entry->hashcode == hashcode)
+	    {
+	      /* An entry representing multiple nodes.  */
+	      gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
+	      /* Only the first node is interesting.  */
+	      gl_list_node_t node = gl_oset_first (nodes);
+	      if (equals != NULL ? equals (value, node->value) : value == node->value)
+		{
+		  /* Found multiple nodes with the same value.
+		     old_node must be one of them.  Remove it.  */
+		  if (!gl_oset_remove (nodes, old_node))
+		    abort ();
+		  if (gl_oset_size (nodes) == 1)
+		    {
+		      /* Replace a one-element set with a single node.  */
+		      node = gl_oset_first (nodes);
+		      node->h.hash_next = entry->hash_next;
+		      *entryp = &node->h;
+		      gl_oset_free (nodes);
+		      free (entry);
+		    }
+		  break;
+		}
+	    }
+	}
+    }
+  else
+    {
+      /* If no duplicates are allowed, multiple nodes are not needed.  */
+      gl_hash_entry_t *entryp;
+
+      for (entryp = &list->table[index]; ; entryp = &(*entryp)->hash_next)
+	{
+	  if (*entryp == &old_node->h)
+	    {
+	      *entryp = old_node->h.hash_next;
+	      break;
+	    }
+	  if (*entryp == NULL)
+	    /* node is not in the right bucket.  Did the hash codes
+	       change inadvertently?  */
+	    abort ();
+	}
+    }
+}
+
+/* Build up the hash table during initialization: Store all the nodes of
+   list->root in the hash table.  */
+static inline void
+add_nodes_to_buckets (gl_list_t list)
+{
+  /* Iterate across all nodes.  */
+  gl_list_node_t node = list->root;
+  iterstack_t stack;
+  iterstack_item_t *stack_ptr = &stack[0];
+
+  for (;;)
+    {
+      /* Descend on left branch.  */
+      for (;;)
+	{
+	  if (node == NULL)
+	    break;
+	  stack_ptr->node = node;
+	  stack_ptr->rightp = false;
+	  node = node->left;
+	  stack_ptr++;
+	}
+      /* Climb up again.  */
+      for (;;)
+	{
+	  if (stack_ptr == &stack[0])
+	    return;
+	  stack_ptr--;
+	  if (!stack_ptr->rightp)
+	    break;
+	}
+      node = stack_ptr->node;
+      /* Add the current node to the hash table.  */
+      node->h.hashcode =
+	(list->base.hashcode_fn != NULL
+	 ? list->base.hashcode_fn (node->value)
+	 : (size_t)(uintptr_t) node->value);
+      add_to_bucket (list, node);
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+}
diff --git a/lib/gl_anytreehash_list2.h b/lib/gl_anytreehash_list2.h
new file mode 100644
index 0000000000..10fbe109d4
--- /dev/null
+++ b/lib/gl_anytreehash_list2.h
@@ -0,0 +1,152 @@
+/* Sequential list data type implemented by a hash table with a binary tree.
+   Copyright (C) 2006 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 2, 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, write to the Free Software Foundation,
+   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
+
+/* Common code of gl_avltreehash_list.c and gl_rbtreehash_list.c.  */
+
+static gl_list_node_t
+gl_tree_search (gl_list_t list, const void *elt)
+{
+  size_t hashcode =
+    (list->base.hashcode_fn != NULL
+     ? list->base.hashcode_fn (elt)
+     : (size_t)(uintptr_t) elt);
+  size_t index = hashcode % list->table_size;
+  gl_listelement_equals_fn equals = list->base.equals_fn;
+  gl_hash_entry_t entry;
+
+  if (list->base.allow_duplicates)
+    {
+      for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
+	if (entry->hashcode == hashcode)
+	  {
+	    if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
+	      {
+		/* An entry representing multiple nodes.  */
+		gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
+		/* Only the first node is interesting.  */
+		gl_list_node_t node = gl_oset_first (nodes);
+		if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		  /* All nodes in the entry are equal to the given ELT.
+		     But we have to return only the one at the minimal position,
+		     and this is the first one in the ordered set.  */
+		  return node;
+	      }
+	    else
+	      {
+		/* An entry representing a single node.  */
+		gl_list_node_t node = (struct gl_list_node_impl *) entry;
+		if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+		  return node;
+	      }
+	  }
+    }
+  else
+    {
+      /* If no duplicates are allowed, multiple nodes are not needed.  */
+      for (entry = list->table[index]; entry != NULL; entry = entry->hash_next)
+	if (entry->hashcode == hashcode)
+	  {
+	    gl_list_node_t node = (struct gl_list_node_impl *) entry;
+	    if (equals != NULL ? equals (elt, node->value) : elt == node->value)
+	      return node;
+	  }
+    }
+
+  return NULL;
+}
+
+static size_t
+gl_tree_indexof (gl_list_t list, const void *elt)
+{
+  gl_list_node_t node = gl_tree_search (list, elt);
+
+  if (node != NULL)
+    return node_position (node);
+  else
+    return (size_t)(-1);
+}
+
+static void
+gl_tree_list_free (gl_list_t list)
+{
+  if (list->base.allow_duplicates)
+    {
+      /* Free the ordered sets in the hash buckets.  */
+      size_t i;
+
+      for (i = list->table_size; i > 0; )
+	{
+	  gl_hash_entry_t entry = list->table[--i];
+
+	  while (entry != NULL)
+	    {
+	      gl_hash_entry_t next = entry->hash_next;
+
+	      if (((struct gl_multiple_nodes *) entry)->magic == MULTIPLE_NODES_MAGIC)
+		{
+		  gl_oset_t nodes = ((struct gl_multiple_nodes *) entry)->nodes;
+
+		  gl_oset_free (nodes);
+		  free (entry);
+		}
+
+	      entry = next;
+	    }
+	}
+    }
+
+  /* Iterate across all elements in post-order.  */
+  {
+    gl_list_node_t node = list->root;
+    iterstack_t stack;
+    iterstack_item_t *stack_ptr = &stack[0];
+
+    for (;;)
+      {
+	/* Descend on left branch.  */
+	for (;;)
+	  {
+	    if (node == NULL)
+	      break;
+	    stack_ptr->node = node;
+	    stack_ptr->rightp = false;
+	    node = node->left;
+	    stack_ptr++;
+	  }
+	/* Climb up again.  */
+	for (;;)
+	  {
+	    if (stack_ptr == &stack[0])
+	      goto done_iterate;
+	    stack_ptr--;
+	    node = stack_ptr->node;
+	    if (!stack_ptr->rightp)
+	      break;
+	    /* Free the current node.  */
+	    free (node);
+	  }
+	/* Descend on right branch.  */
+	stack_ptr->rightp = true;
+	node = node->right;
+	stack_ptr++;
+      }
+  }
+ done_iterate:
+  free (list->table);
+  free (list);
+}