Ordered set data type implemented by a binary tree.

10 files changed, 1797 insertions, 0 deletions

diff --git a/lib/gl_avltree_oset.c b/lib/gl_avltree_oset.c
new file mode 100644
index 0000000000..e57b4de95d
--- /dev/null
+++ b/lib/gl_avltree_oset.c
@@ -0,0 +1,576 @@
+/* Ordered set 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.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+/* Specification.  */
+#include "gl_avltree_oset.h"
+
+#include <stdlib.h>
+
+#include "xalloc.h"
+
+/* 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_oset_t Data Type -------------------------- */
+
+/* Tree node implementation, valid for this file only.  */
+struct gl_oset_node_impl
+{
+  struct gl_oset_node_impl *left;   /* left branch, or NULL */
+  struct gl_oset_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_oset_node_t can be returned
+     without memory allocation, on which the functions gl_oset_remove_node,
+     gl_oset_add_before, gl_oset_add_after can be implemented.  */
+  struct gl_oset_node_impl *parent;
+  int balance;                      /* heightof(right) - heightof(left),
+				       always = -1 or 0 or 1 */
+  const void *value;
+};
+typedef struct gl_oset_node_impl * gl_oset_node_t;
+
+/* Concrete gl_oset_impl type, valid for this file only.  */
+struct gl_oset_impl
+{
+  struct gl_oset_impl_base base;
+  struct gl_oset_node_impl *root;   /* root node or NULL */
+  size_t count;                     /* number of nodes */
+};
+
+/* 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_oset_node_impl) * F_87 > 2^64
+   this would exceed the address space of the machine.  */
+#define MAXHEIGHT 83
+
+/* 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_oset_t set,
+	   gl_oset_node_t node, int height_diff, gl_oset_node_t parent)
+{
+  for (;;)
+    {
+      gl_oset_node_t child;
+      int previous_balance;
+      int balance_diff;
+      gl_oset_node_t nodeleft;
+      gl_oset_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_oset_node_t *nodep;
+
+	  if (node->parent == NULL)
+	    /* node == set->root */
+	    nodep = &set->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_oset_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;
+
+		  *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_oset_node_t L = nodeleft->right = nodeleftright->left;
+		  gl_oset_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;
+
+		  *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_oset_node_t noderightleft = noderight->left;
+	      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;
+
+		  *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_oset_node_t L = node->right = noderightleft->left;
+		  gl_oset_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;
+
+		  *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_oset_node_t
+gl_tree_add_first (gl_oset_t set, const void *elt)
+{
+  /* Create new node.  */
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  new_node->value = elt;
+
+  /* Add it to the tree.  */
+  if (set->root == NULL)
+    {
+      set->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_oset_node_t node;
+
+      for (node = set->root; node->left != NULL; )
+	node = node->left;
+
+      node->left = new_node;
+      new_node->parent = node;
+      node->balance--;
+
+      /* Rebalance.  */
+      if (node->right == NULL && node->parent != NULL)
+	rebalance (set, node, 1, node->parent);
+    }
+
+  set->count++;
+  return new_node;
+}
+
+static gl_oset_node_t
+gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
+  bool height_inc;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  new_node->value = elt;
+
+  /* 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;
+
+  /* Rebalance.  */
+  if (height_inc && node->parent != NULL)
+    rebalance (set, node, 1, node->parent);
+
+  set->count++;
+  return new_node;
+}
+
+static gl_oset_node_t
+gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
+  bool height_inc;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  new_node->value = elt;
+
+  /* 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;
+
+  /* Rebalance.  */
+  if (height_inc && node->parent != NULL)
+    rebalance (set, node, 1, node->parent);
+
+  set->count++;
+  return new_node;
+}
+
+static bool
+gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
+{
+  gl_oset_node_t parent = node->parent;
+
+  if (node->left == NULL)
+    {
+      /* Replace node with node->right.  */
+      gl_oset_node_t child = node->right;
+
+      if (child != NULL)
+	child->parent = parent;
+      if (parent == NULL)
+	set->root = child;
+      else
+	{
+	  if (parent->left == node)
+	    parent->left = child;
+	  else /* parent->right == node */
+	    parent->right = child;
+
+	  rebalance (set, 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_oset_node_t child = node->left;
+
+      child->parent = parent;
+      if (parent == NULL)
+	set->root = child;
+      else
+	{
+	  if (parent->left == node)
+	    parent->left = child;
+	  else /* parent->right == node */
+	    parent->right = child;
+
+	  rebalance (set, child, -1, parent);
+	}
+    }
+  else
+    {
+      /* Replace node with the rightmost element of the node->left subtree.  */
+      gl_oset_node_t subst;
+      gl_oset_node_t subst_parent;
+      gl_oset_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;
+	}
+
+      /* 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->parent = parent;
+      if (parent == NULL)
+	set->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 (set, child, -1, subst_parent != node ? subst_parent : subst);
+    }
+
+  set->count--;
+  free (node);
+  return true;
+}
+
+/* Generic binary tree code.  */
+#include "gl_anytree_oset.h"
+
+/* For debugging.  */
+static unsigned int
+check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
+{
+  unsigned int left_height =
+    (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
+  unsigned int right_height =
+    (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
+  int balance = (int)right_height - (int)left_height;
+
+  if (!(node->parent == parent))
+    abort ();
+  if (!(balance >= -1 && balance <= 1))
+    abort ();
+  if (!(node->balance == balance))
+    abort ();
+
+  (*counterp)++;
+
+  return 1 + (left_height > right_height ? left_height : right_height);
+}
+void
+gl_avltree_oset_check_invariants (gl_oset_t set)
+{
+  size_t counter = 0;
+  if (set->root != NULL)
+    check_invariants (set->root, NULL, &counter);
+  if (!(set->count == counter))
+    abort ();
+}
+
+const struct gl_oset_implementation gl_avltree_oset_implementation =
+  {
+    gl_tree_create_empty,
+    gl_tree_size,
+    gl_tree_search,
+    gl_tree_add,
+    gl_tree_remove,
+    gl_tree_oset_free,
+    gl_tree_iterator,
+    gl_tree_iterator_next,
+    gl_tree_iterator_free
+  };
diff --git a/lib/gl_avltree_oset.h b/lib/gl_avltree_oset.h
new file mode 100644
index 0000000000..27f75d22d0
--- /dev/null
+++ b/lib/gl_avltree_oset.h
@@ -0,0 +1,35 @@
+/* Ordered set 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.  */
+
+#ifndef _GL_AVLTREE_OSET_H
+#define _GL_AVLTREE_OSET_H
+
+#include "gl_oset.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_oset_implementation gl_avltree_oset_implementation;
+#define GL_AVLTREE_OSET &gl_avltree_oset_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_AVLTREE_OSET_H */
diff --git a/lib/gl_rbtree_oset.c b/lib/gl_rbtree_oset.c
new file mode 100644
index 0000000000..2ca4fbccda
--- /dev/null
+++ b/lib/gl_rbtree_oset.c
@@ -0,0 +1,807 @@
+/* Ordered set 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.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+/* Specification.  */
+#include "gl_rbtree_oset.h"
+
+#include <stdlib.h>
+
+#include "xalloc.h"
+
+/* 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_oset_t Data Type -------------------------- */
+
+/* Color of a node.  */
+typedef enum color { BLACK, RED } color_t;
+
+/* Tree node implementation, valid for this file only.  */
+struct gl_oset_node_impl
+{
+  struct gl_oset_node_impl *left;   /* left branch, or NULL */
+  struct gl_oset_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_oset_node_t can be returned
+     without memory allocation, on which the functions gl_oset_remove_node,
+     gl_oset_add_before, gl_oset_add_after can be implemented.  */
+  struct gl_oset_node_impl *parent;
+  color_t color;                    /* node's color */
+  const void *value;
+};
+typedef struct gl_oset_node_impl * gl_oset_node_t;
+
+/* Concrete gl_oset_impl type, valid for this file only.  */
+struct gl_oset_impl
+{
+  struct gl_oset_impl_base base;
+  struct gl_oset_node_impl *root;   /* root node or NULL */
+  size_t count;                     /* number of nodes */
+};
+
+/* 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_oset_node_impl) * (2^59 - 1) > 2^64
+   this would exceed the address space of the machine.  */
+#define MAXHEIGHT 116
+
+/* 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_oset_node_t
+rotate_left (gl_oset_node_t b_node, gl_oset_node_t d_node)
+{
+  gl_oset_node_t c_node = d_node->left;
+
+  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;
+
+  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_oset_node_t
+rotate_right (gl_oset_node_t b_node, gl_oset_node_t d_node)
+{
+  gl_oset_node_t c_node = b_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;
+
+  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_oset_t set, gl_oset_node_t node, gl_oset_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_oset_node_t grandparent;
+      gl_oset_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_oset_node_t *grandparentp;
+
+	  if (grandparent->parent == NULL)
+	    grandparentp = &set->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_oset_t set, gl_oset_node_t child, gl_oset_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_oset_node_t *parentp;
+
+      if (parent->parent == NULL)
+	parentp = &set->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_oset_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_oset_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_oset_node_t
+gl_tree_add_first (gl_oset_t set, const void *elt)
+{
+  /* Create new node.  */
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->value = elt;
+
+  /* Add it to the tree.  */
+  if (set->root == NULL)
+    {
+      new_node->color = BLACK;
+      set->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      gl_oset_node_t node;
+
+      for (node = set->root; node->left != NULL; )
+	node = node->left;
+
+      node->left = new_node;
+      new_node->parent = node;
+
+      /* Color and rebalance.  */
+      rebalance_after_add (set, new_node, node);
+    }
+
+  set->count++;
+  return new_node;
+}
+
+static gl_oset_node_t
+gl_tree_add_before (gl_oset_t set, gl_oset_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->value = elt;
+
+  /* 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;
+
+  /* Color and rebalance.  */
+  rebalance_after_add (set, new_node, node);
+
+  set->count++;
+  return new_node;
+}
+
+static gl_oset_node_t
+gl_tree_add_after (gl_oset_t set, gl_oset_node_t node, const void *elt)
+{
+  /* Create new node.  */
+  gl_oset_node_t new_node =
+    (struct gl_oset_node_impl *) xmalloc (sizeof (struct gl_oset_node_impl));
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->value = elt;
+
+  /* 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;
+
+  /* Color and rebalance.  */
+  rebalance_after_add (set, new_node, node);
+
+  set->count++;
+  return new_node;
+}
+
+static bool
+gl_tree_remove_node (gl_oset_t set, gl_oset_node_t node)
+{
+  gl_oset_node_t parent = node->parent;
+
+  if (node->left == NULL)
+    {
+      /* Replace node with node->right.  */
+      gl_oset_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)
+	set->root = child;
+      else
+	{
+	  if (parent->left == node)
+	    parent->left = child;
+	  else /* parent->right == node */
+	    parent->right = child;
+
+	  if (child == NULL && node->color == BLACK)
+	    rebalance_after_remove (set, 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_oset_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)
+	set->root = child;
+      else
+	{
+	  if (parent->left == node)
+	    parent->left = child;
+	  else /* parent->right == node */
+	    parent->right = child;
+	}
+    }
+  else
+    {
+      /* Replace node with the rightmost element of the node->left subtree.  */
+      gl_oset_node_t subst;
+      gl_oset_node_t subst_parent;
+      gl_oset_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;
+	}
+
+      /* 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->parent = parent;
+      if (parent == NULL)
+	set->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 (set, child,
+				    subst_parent != node ? subst_parent : subst);
+	}
+    }
+
+  set->count--;
+  free (node);
+  return true;
+}
+
+/* Generic binary tree code.  */
+#include "gl_anytree_oset.h"
+
+/* For debugging.  */
+static unsigned int
+check_invariants (gl_oset_node_t node, gl_oset_node_t parent, size_t *counterp)
+{
+  unsigned int left_blackheight =
+    (node->left != NULL ? check_invariants (node->left, node, counterp) : 0);
+  unsigned int right_blackheight =
+    (node->right != NULL ? check_invariants (node->right, node, counterp) : 0);
+
+  if (!(node->parent == parent))
+    abort ();
+  if (!(node->color == BLACK || node->color == RED))
+    abort ();
+  if (parent == NULL && !(node->color == BLACK))
+    abort ();
+  if (!(left_blackheight == right_blackheight))
+    abort ();
+
+  (*counterp)++;
+
+  return left_blackheight + (node->color == BLACK ? 1 : 0);
+}
+void
+gl_rbtree_oset_check_invariants (gl_oset_t set)
+{
+  size_t counter = 0;
+  if (set->root != NULL)
+    check_invariants (set->root, NULL, &counter);
+  if (!(set->count == counter))
+    abort ();
+}
+
+const struct gl_oset_implementation gl_rbtree_oset_implementation =
+  {
+    gl_tree_create_empty,
+    gl_tree_size,
+    gl_tree_search,
+    gl_tree_add,
+    gl_tree_remove,
+    gl_tree_oset_free,
+    gl_tree_iterator,
+    gl_tree_iterator_next,
+    gl_tree_iterator_free
+  };
diff --git a/lib/gl_rbtree_oset.h b/lib/gl_rbtree_oset.h
new file mode 100644
index 0000000000..fc81b276cd
--- /dev/null
+++ b/lib/gl_rbtree_oset.h
@@ -0,0 +1,35 @@
+/* Ordered set 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.  */
+
+#ifndef _GL_RBTREE_OSET_H
+#define _GL_RBTREE_OSET_H
+
+#include "gl_oset.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_oset_implementation gl_rbtree_oset_implementation;
+#define GL_RBTREE_OSET &gl_rbtree_oset_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_RBTREE_OSET_H */
diff --git a/modules/avltree-oset b/modules/avltree-oset
new file mode 100644
index 0000000000..4a7a3f8552
--- /dev/null
+++ b/modules/avltree-oset
@@ -0,0 +1,26 @@
+Description:
+Ordered set data type implemented by a binary tree.
+
+Files:
+lib/gl_avltree_oset.h
+lib/gl_avltree_oset.c
+lib/gl_anytree_oset.h
+
+Depends-on:
+oset
+xalloc
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_avltree_oset.h gl_avltree_oset.c gl_anytree_oset.h
+
+Include:
+"gl_avltree_oset.h"
+
+License:
+GPL
+
+Maintainer:
+Bruno Haible
+
diff --git a/modules/avltree-oset-tests b/modules/avltree-oset-tests
new file mode 100644
index 0000000000..06d74f96c2
--- /dev/null
+++ b/modules/avltree-oset-tests
@@ -0,0 +1,12 @@
+Files:
+tests/test-avltree_oset.c
+
+Depends-on:
+array-oset
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-avltree_oset$(EXEEXT)
+check_PROGRAMS += test-avltree_oset
+
diff --git a/modules/rbtree-oset b/modules/rbtree-oset
new file mode 100644
index 0000000000..63253d314d
--- /dev/null
+++ b/modules/rbtree-oset
@@ -0,0 +1,26 @@
+Description:
+Ordered set data type implemented by a binary tree.
+
+Files:
+lib/gl_rbtree_oset.h
+lib/gl_rbtree_oset.c
+lib/gl_anytree_oset.h
+
+Depends-on:
+oset
+xalloc
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_anytree_oset.h
+
+Include:
+"gl_rbtree_oset.h"
+
+License:
+GPL
+
+Maintainer:
+Bruno Haible
+
diff --git a/modules/rbtree-oset-tests b/modules/rbtree-oset-tests
new file mode 100644
index 0000000000..e561e457e8
--- /dev/null
+++ b/modules/rbtree-oset-tests
@@ -0,0 +1,12 @@
+Files:
+tests/test-rbtree_oset.c
+
+Depends-on:
+array-oset
+
+configure.ac:
+
+Makefile.am:
+TESTS += test-rbtree_oset$(EXEEXT)
+check_PROGRAMS += test-rbtree_oset
+
diff --git a/tests/test-avltree_oset.c b/tests/test-avltree_oset.c
new file mode 100644
index 0000000000..02066f6401
--- /dev/null
+++ b/tests/test-avltree_oset.c
@@ -0,0 +1,134 @@
+/* Test of ordered set data type implementation.
+   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.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_array_oset.h"
+#include "gl_avltree_oset.h"
+
+extern void gl_avltree_oset_check_invariants (gl_oset_t set);
+
+static const char *objects[30] =
+  {
+    "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
+    "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
+  };
+
+#define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
+#define ASSERT(condition) if (!(condition)) abort ()
+#define RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+static void
+check_equals (gl_oset_t set1, gl_oset_t set2)
+{
+  size_t n = gl_oset_size (set1);
+  gl_oset_iterator_t iter1, iter2;
+  const void *elt1;
+  const void *elt2;
+  size_t i;
+
+  iter1 = gl_oset_iterator (set1);
+  iter2 = gl_oset_iterator (set2);
+  for (i = 0; i < n; i++)
+    {
+      ASSERT (gl_oset_iterator_next (&iter1, &elt1));
+      ASSERT (gl_oset_iterator_next (&iter2, &elt2));
+      ASSERT (elt1 == elt2);
+    }
+  ASSERT (!gl_oset_iterator_next (&iter1, &elt1));
+  ASSERT (!gl_oset_iterator_next (&iter2, &elt2));
+  gl_oset_iterator_free (&iter1);
+  gl_oset_iterator_free (&iter2);
+}
+
+static void
+check_all (gl_oset_t set1, gl_oset_t set2)
+{
+  gl_avltree_oset_check_invariants (set2);
+  check_equals (set1, set2);
+}
+
+int
+main (int argc, char *argv[])
+{
+  gl_oset_t set1, set2;
+
+  /* Allow the user to provide a non-default random seed on the command line.  */
+  if (argc > 1)
+    srand (atoi (argv[1]));
+
+  {
+    size_t initial_size = RANDOM (20);
+    size_t i;
+    unsigned int repeat;
+
+    /* Create set1.  */
+    set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn) strcmp);
+
+    /* Create set2.  */
+    set2 = gl_oset_create_empty (GL_AVLTREE_OSET, (gl_setelement_compar_fn) strcmp);
+
+    check_all (set1, set2);
+
+    /* Initialize them.  */
+    for (i = 0; i < initial_size; i++)
+      {
+        const char *obj = RANDOM_OBJECT ();
+        ASSERT (gl_oset_add (set1, obj) == gl_oset_add (set2, obj));
+        check_all (set1, set2);
+      }
+
+    for (repeat = 0; repeat < 100000; repeat++)
+      {
+        unsigned int operation = RANDOM (3);
+        switch (operation)
+          {
+          case 0:
+            {
+              const char *obj = RANDOM_OBJECT ();
+              ASSERT (gl_oset_search (set1, obj) == gl_oset_search (set2, obj));
+            }
+            break;
+          case 1:
+            {
+              const char *obj = RANDOM_OBJECT ();
+              ASSERT (gl_oset_add (set1, obj) == gl_oset_add (set2, obj));
+            }
+            break;
+          case 2:
+            {
+              const char *obj = RANDOM_OBJECT ();
+              ASSERT (gl_oset_remove (set1, obj) == gl_oset_remove (set2, obj));
+            }
+            break;
+          }
+        check_all (set1, set2);
+      }
+
+    gl_oset_free (set1);
+    gl_oset_free (set2);
+  }
+
+  return 0;
+}
diff --git a/tests/test-rbtree_oset.c b/tests/test-rbtree_oset.c
new file mode 100644
index 0000000000..f6c3e69ef4
--- /dev/null
+++ b/tests/test-rbtree_oset.c
@@ -0,0 +1,134 @@
+/* Test of ordered set data type implementation.
+   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.  */
+
+#ifdef HAVE_CONFIG_H
+# include <config.h>
+#endif
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "gl_array_oset.h"
+#include "gl_rbtree_oset.h"
+
+extern void gl_rbtree_oset_check_invariants (gl_oset_t set);
+
+static const char *objects[30] =
+  {
+    "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
+    "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
+  };
+
+#define SIZEOF(array) (sizeof (array) / sizeof (array[0]))
+#define ASSERT(condition) if (!(condition)) abort ()
+#define RANDOM(n) (rand () % (n))
+#define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
+
+static void
+check_equals (gl_oset_t set1, gl_oset_t set2)
+{
+  size_t n = gl_oset_size (set1);
+  gl_oset_iterator_t iter1, iter2;
+  const void *elt1;
+  const void *elt2;
+  size_t i;
+
+  iter1 = gl_oset_iterator (set1);
+  iter2 = gl_oset_iterator (set2);
+  for (i = 0; i < n; i++)
+    {
+      ASSERT (gl_oset_iterator_next (&iter1, &elt1));
+      ASSERT (gl_oset_iterator_next (&iter2, &elt2));
+      ASSERT (elt1 == elt2);
+    }
+  ASSERT (!gl_oset_iterator_next (&iter1, &elt1));
+  ASSERT (!gl_oset_iterator_next (&iter2, &elt2));
+  gl_oset_iterator_free (&iter1);
+  gl_oset_iterator_free (&iter2);
+}
+
+static void
+check_all (gl_oset_t set1, gl_oset_t set2)
+{
+  gl_rbtree_oset_check_invariants (set2);
+  check_equals (set1, set2);
+}
+
+int
+main (int argc, char *argv[])
+{
+  gl_oset_t set1, set2;
+
+  /* Allow the user to provide a non-default random seed on the command line.  */
+  if (argc > 1)
+    srand (atoi (argv[1]));
+
+  {
+    size_t initial_size = RANDOM (20);
+    size_t i;
+    unsigned int repeat;
+
+    /* Create set1.  */
+    set1 = gl_oset_create_empty (GL_ARRAY_OSET, (gl_setelement_compar_fn) strcmp);
+
+    /* Create set2.  */
+    set2 = gl_oset_create_empty (GL_RBTREE_OSET, (gl_setelement_compar_fn) strcmp);
+
+    check_all (set1, set2);
+
+    /* Initialize them.  */
+    for (i = 0; i < initial_size; i++)
+      {
+        const char *obj = RANDOM_OBJECT ();
+        ASSERT (gl_oset_add (set1, obj) == gl_oset_add (set2, obj));
+        check_all (set1, set2);
+      }
+
+    for (repeat = 0; repeat < 100000; repeat++)
+      {
+        unsigned int operation = RANDOM (3);
+        switch (operation)
+          {
+          case 0:
+            {
+              const char *obj = RANDOM_OBJECT ();
+              ASSERT (gl_oset_search (set1, obj) == gl_oset_search (set2, obj));
+            }
+            break;
+          case 1:
+            {
+              const char *obj = RANDOM_OBJECT ();
+              ASSERT (gl_oset_add (set1, obj) == gl_oset_add (set2, obj));
+            }
+            break;
+          case 2:
+            {
+              const char *obj = RANDOM_OBJECT ();
+              ASSERT (gl_oset_remove (set1, obj) == gl_oset_remove (set2, obj));
+            }
+            break;
+          }
+        check_all (set1, set2);
+      }
+
+    gl_oset_free (set1);
+    gl_oset_free (set2);
+  }
+
+  return 0;
+}