avltree-omap: New module.

* lib/gl_avltree_omap.h: New file.
* lib/gl_avltree_omap.c: New file.
* lib/gl_avltree_ordered.h: Code moved to here from
lib/gl_avltree_oset.c. Parameterize.
* lib/gl_avltree_oset.c: Include gl_avltree_ordered.h.
* lib/gl_anytree_omap.h: New file.
* modules/avltree-omap: New file.
* modules/avltree-oset (Files): Add lib/gl_avltree_ordered.h.
(Makefile.am): Add gl_avltree_ordered.h to lib_SOURCES.

8 files changed, 1014 insertions, 528 deletions

diff --git a/ChangeLog b/ChangeLog
index 81963bdfd5..906dc5e354 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,16 @@
 2018-12-11  Bruno Haible  <bruno@clisp.org>
 
+	avltree-omap: New module.
+	* lib/gl_avltree_omap.h: New file.
+	* lib/gl_avltree_omap.c: New file.
+	* lib/gl_avltree_ordered.h: Code moved to here from
+	lib/gl_avltree_oset.c. Parameterize.
+	* lib/gl_avltree_oset.c: Include gl_avltree_ordered.h.
+	* lib/gl_anytree_omap.h: New file.
+	* modules/avltree-omap: New file.
+	* modules/avltree-oset (Files): Add lib/gl_avltree_ordered.h.
+	(Makefile.am): Add gl_avltree_ordered.h to lib_SOURCES.
+
 	array-omap: New module.
 	* lib/gl_array_omap.h: New file.
 	* lib/gl_array_omap.c: New file.
diff --git a/lib/gl_anytree_omap.h b/lib/gl_anytree_omap.h
new file mode 100644
index 0000000000..0b43712369
--- /dev/null
+++ b/lib/gl_anytree_omap.h
@@ -0,0 +1,305 @@
+/* Ordered map data type implemented by a binary tree.
+   Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2018.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* Common code of gl_avltree_omap.c and gl_rbtree_omap.c.  */
+
+/* An item on the stack used for iterating across the elements.  */
+typedef struct
+{
+  gl_omap_node_t node;
+  bool rightp;
+} iterstack_item_t;
+
+/* A stack used for iterating across the elements.  */
+typedef iterstack_item_t iterstack_t[MAXHEIGHT];
+
+static gl_omap_t
+gl_tree_nx_create_empty (gl_omap_implementation_t implementation,
+                         gl_mapkey_compar_fn compar_fn,
+                         gl_mapkey_dispose_fn kdispose_fn,
+                         gl_mapvalue_dispose_fn vdispose_fn)
+{
+  struct gl_omap_impl *map =
+    (struct gl_omap_impl *) malloc (sizeof (struct gl_omap_impl));
+
+  if (map == NULL)
+    return NULL;
+
+  map->base.vtable = implementation;
+  map->base.compar_fn = compar_fn;
+  map->base.kdispose_fn = kdispose_fn;
+  map->base.vdispose_fn = vdispose_fn;
+  map->root = NULL;
+  map->count = 0;
+
+  return map;
+}
+
+static size_t
+gl_tree_size (gl_omap_t map)
+{
+  return map->count;
+}
+
+static bool
+gl_tree_search (gl_omap_t map, const void *key, const void **valuep)
+{
+  gl_mapkey_compar_fn compar = map->base.compar_fn;
+  gl_omap_node_t node;
+
+  for (node = map->root; node != NULL; )
+    {
+      int cmp = (compar != NULL
+                 ? compar (node->key, key)
+                 : (node->key > key ? 1 :
+                    node->key < key ? -1 : 0));
+
+      if (cmp < 0)
+        node = node->right;
+      else if (cmp > 0)
+        node = node->left;
+      else /* cmp == 0 */
+        {
+          /* We have a key equal to KEY.  */
+          *valuep = node->value;
+          return true;
+        }
+    }
+  return false;
+}
+
+static bool
+gl_tree_search_atleast (gl_omap_t map,
+                        gl_mapkey_threshold_fn threshold_fn,
+                        const void *threshold,
+                        const void **keyp, const void **valuep)
+{
+  gl_omap_node_t node;
+
+  for (node = map->root; node != NULL; )
+    {
+      if (! threshold_fn (node->key, threshold))
+        node = node->right;
+      else
+        {
+          /* We have a key >= THRESHOLD.  But we need the leftmost such
+             element.  */
+          gl_omap_node_t found = node;
+          node = node->left;
+          for (; node != NULL; )
+            {
+              if (! threshold_fn (node->key, threshold))
+                node = node->right;
+              else
+                {
+                  found = node;
+                  node = node->left;
+                }
+            }
+          *keyp = found->key;
+          *valuep = found->value;
+          return true;
+        }
+    }
+  return false;
+}
+
+static int
+gl_tree_nx_getput (gl_omap_t map, const void *key, const void *value,
+                   const void **oldvaluep)
+{
+  gl_mapkey_compar_fn compar;
+  gl_omap_node_t node = map->root;
+
+  if (node == NULL)
+    {
+      if (gl_tree_nx_add_first (map, key, value) == NULL)
+        return -1;
+      return true;
+    }
+
+  compar = map->base.compar_fn;
+
+  for (;;)
+    {
+      int cmp = (compar != NULL
+                 ? compar (node->key, key)
+                 : (node->key > key ? 1 :
+                    node->key < key ? -1 : 0));
+
+      if (cmp < 0)
+        {
+          if (node->right == NULL)
+            {
+              if (gl_tree_nx_add_after (map, node, key, value) == NULL)
+                return -1;
+              return true;
+            }
+          node = node->right;
+        }
+      else if (cmp > 0)
+        {
+          if (node->left == NULL)
+            {
+              if (gl_tree_nx_add_before (map, node, key, value) == NULL)
+                return -1;
+              return true;
+            }
+          node = node->left;
+        }
+      else /* cmp == 0 */
+        {
+          *oldvaluep = node->value;
+          node->value = value;
+          return false;
+        }
+    }
+}
+
+static bool
+gl_tree_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
+{
+  gl_mapkey_compar_fn compar = map->base.compar_fn;
+  gl_omap_node_t node;
+
+  for (node = map->root; node != NULL; )
+    {
+      int cmp = (compar != NULL
+                 ? compar (node->key, key)
+                 : (node->key > key ? 1 :
+                    node->key < key ? -1 : 0));
+
+      if (cmp < 0)
+        node = node->right;
+      else if (cmp > 0)
+        node = node->left;
+      else /* cmp == 0 */
+        {
+          /* We have a key equal to KEY.  */
+          *oldvaluep = node->value;
+          gl_tree_remove_node (map, node);
+          return true;
+        }
+    }
+  return false;
+}
+
+static void
+gl_tree_omap_free (gl_omap_t map)
+{
+  /* Iterate across all elements in post-order.  */
+  gl_omap_node_t node = map->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.  */
+          if (map->base.vdispose_fn != NULL)
+            map->base.vdispose_fn (node->value);
+          if (map->base.kdispose_fn != NULL)
+            map->base.kdispose_fn (node->key);
+          free (node);
+        }
+      /* Descend on right branch.  */
+      stack_ptr->rightp = true;
+      node = node->right;
+      stack_ptr++;
+    }
+ done_iterate:
+  free (map);
+}
+
+/* --------------------- gl_omap_iterator_t Data Type --------------------- */
+
+static gl_omap_iterator_t
+gl_tree_iterator (gl_omap_t map)
+{
+  gl_omap_iterator_t result;
+  gl_omap_node_t node;
+
+  result.vtable = map->base.vtable;
+  result.map = map;
+  /* Start node is the leftmost node.  */
+  node = map->root;
+  if (node != NULL)
+    while (node->left != NULL)
+      node = node->left;
+  result.p = node;
+  /* End point is past the rightmost node.  */
+  result.q = NULL;
+#if defined GCC_LINT || defined lint
+  result.i = 0;
+  result.j = 0;
+  result.count = 0;
+#endif
+
+  return result;
+}
+
+static bool
+gl_tree_iterator_next (gl_omap_iterator_t *iterator,
+                       const void **keyp, const void **valuep)
+{
+  if (iterator->p != iterator->q)
+    {
+      gl_omap_node_t node = (gl_omap_node_t) iterator->p;
+      *keyp = node->key;
+      *valuep = node->value;
+      /* 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_omap_iterator_t *iterator)
+{
+}
diff --git a/lib/gl_avltree_omap.c b/lib/gl_avltree_omap.c
new file mode 100644
index 0000000000..f205eb5e7c
--- /dev/null
+++ b/lib/gl_avltree_omap.c
@@ -0,0 +1,75 @@
+/* Ordered map data type implemented by a binary tree.
+   Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2018.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+/* Specification.  */
+#include "gl_avltree_omap.h"
+
+#include <stdlib.h>
+
+/* -------------------------- gl_omap_t Data Type -------------------------- */
+
+/* Parameterization of gl_avltree_ordered.h.  */
+#define CONTAINER_T gl_omap_t
+#define CONTAINER_IMPL gl_omap_impl
+#define CONTAINER_IMPL_BASE gl_omap_impl_base
+#define NODE_IMPL gl_omap_node_impl
+#define NODE_T gl_omap_node_t
+#define NODE_PAYLOAD_FIELDS \
+  const void *key; \
+  const void *value;
+#define NODE_PAYLOAD_PARAMS \
+  const void *key, const void *value
+#define NODE_PAYLOAD_ASSIGN(node) \
+  node->key = key; \
+  node->value = value;
+#define NODE_PAYLOAD_DISPOSE \
+  if (container->base.vdispose_fn != NULL) \
+    container->base.vdispose_fn (node->value); \
+  if (container->base.kdispose_fn != NULL) \
+    container->base.kdispose_fn (node->key);
+
+#include "gl_avltree_ordered.h"
+
+/* Generic binary tree code.  */
+#include "gl_anytree_omap.h"
+
+/* For debugging.  */
+void
+gl_avltree_omap_check_invariants (gl_omap_t map)
+{
+  size_t counter = 0;
+  if (map->root != NULL)
+    check_invariants (map->root, NULL, &counter);
+  if (!(map->count == counter))
+    abort ();
+}
+
+const struct gl_omap_implementation gl_avltree_omap_implementation =
+  {
+    gl_tree_nx_create_empty,
+    gl_tree_size,
+    gl_tree_search,
+    gl_tree_search_atleast,
+    gl_tree_nx_getput,
+    gl_tree_getremove,
+    gl_tree_omap_free,
+    gl_tree_iterator,
+    gl_tree_iterator_next,
+    gl_tree_iterator_free
+  };
diff --git a/lib/gl_avltree_omap.h b/lib/gl_avltree_omap.h
new file mode 100644
index 0000000000..02db892191
--- /dev/null
+++ b/lib/gl_avltree_omap.h
@@ -0,0 +1,34 @@
+/* Ordered map data type implemented by a binary tree.
+   Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2018.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+#ifndef _GL_AVLTREE_OMAP_H
+#define _GL_AVLTREE_OMAP_H
+
+#include "gl_omap.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_omap_implementation gl_avltree_omap_implementation;
+#define GL_AVLTREE_OMAP &gl_avltree_omap_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_AVLTREE_OMAP_H */
diff --git a/lib/gl_avltree_ordered.h b/lib/gl_avltree_ordered.h
new file mode 100644
index 0000000000..5d06386d6b
--- /dev/null
+++ b/lib/gl_avltree_ordered.h
@@ -0,0 +1,547 @@
+/* Ordered {set,map} data type implemented by a binary tree.
+   Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
+   Written by Bruno Haible <bruno@clisp.org>, 2006.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+/* 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.
+ */
+
+/* Tree node implementation, valid for this file only.  */
+struct NODE_IMPL
+{
+  struct NODE_IMPL *left;   /* left branch, or NULL */
+  struct 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 NODE_T can be returned without
+     memory allocation, on which the functions <container>_remove_node,
+     <container>_add_before, <container>_add_after can be implemented.  */
+  struct NODE_IMPL *parent;
+  int balance;                      /* heightof(right) - heightof(left),
+                                       always = -1 or 0 or 1 */
+  NODE_PAYLOAD_FIELDS
+};
+typedef struct NODE_IMPL * NODE_T;
+
+/* Concrete CONTAINER_IMPL type, valid for this file only.  */
+struct CONTAINER_IMPL
+{
+  struct CONTAINER_IMPL_BASE base;
+  struct 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) - 1 [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 - 1 elements, and because even on 64-bit machines,
+     sizeof (NODE_IMPL) * (F_87 - 1) > 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 (CONTAINER_T container,
+           NODE_T node, int height_diff, NODE_T parent)
+{
+  for (;;)
+    {
+      NODE_T child;
+      int previous_balance;
+      int balance_diff;
+      NODE_T nodeleft;
+      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.  */
+          NODE_T *nodep;
+
+          if (node->parent == NULL)
+            /* node == container->root */
+            nodep = &container->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
+               */
+              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
+
+                   */
+                  NODE_T L = nodeleft->right = nodeleftright->left;
+                  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
+               */
+              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
+
+                   */
+                  NODE_T L = node->right = noderightleft->left;
+                  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 NODE_T
+gl_tree_nx_add_first (CONTAINER_T container, NODE_PAYLOAD_PARAMS)
+{
+  /* Create new node.  */
+  NODE_T new_node =
+    (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  NODE_PAYLOAD_ASSIGN(new_node)
+
+  /* Add it to the tree.  */
+  if (container->root == NULL)
+    {
+      container->root = new_node;
+      new_node->parent = NULL;
+    }
+  else
+    {
+      NODE_T node;
+
+      for (node = container->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 (container, node, 1, node->parent);
+    }
+
+  container->count++;
+  return new_node;
+}
+
+static NODE_T
+gl_tree_nx_add_before (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
+{
+  /* Create new node.  */
+  NODE_T new_node =
+    (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
+  bool height_inc;
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  NODE_PAYLOAD_ASSIGN(new_node)
+
+  /* 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 (container, node, 1, node->parent);
+
+  container->count++;
+  return new_node;
+}
+
+static NODE_T
+gl_tree_nx_add_after (CONTAINER_T container, NODE_T node, NODE_PAYLOAD_PARAMS)
+{
+  /* Create new node.  */
+  NODE_T new_node =
+    (struct NODE_IMPL *) malloc (sizeof (struct NODE_IMPL));
+  bool height_inc;
+
+  if (new_node == NULL)
+    return NULL;
+
+  new_node->left = NULL;
+  new_node->right = NULL;
+  new_node->balance = 0;
+  NODE_PAYLOAD_ASSIGN(new_node)
+
+  /* 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 (container, node, 1, node->parent);
+
+  container->count++;
+  return new_node;
+}
+
+static bool
+gl_tree_remove_node (CONTAINER_T container, NODE_T node)
+{
+  NODE_T parent = node->parent;
+
+  if (node->left == NULL)
+    {
+      /* Replace node with node->right.  */
+      NODE_T child = node->right;
+
+      if (child != NULL)
+        child->parent = parent;
+      if (parent == NULL)
+        container->root = child;
+      else
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          rebalance (container, 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.  */
+      NODE_T child = node->left;
+
+      child->parent = parent;
+      if (parent == NULL)
+        container->root = child;
+      else
+        {
+          if (parent->left == node)
+            parent->left = child;
+          else /* parent->right == node */
+            parent->right = child;
+
+          rebalance (container, child, -1, parent);
+        }
+    }
+  else
+    {
+      /* Replace node with the rightmost element of the node->left subtree.  */
+      NODE_T subst;
+      NODE_T subst_parent;
+      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)
+        container->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 (container, child, -1, subst_parent != node ? subst_parent : subst);
+    }
+
+  container->count--;
+  NODE_PAYLOAD_DISPOSE
+  free (node);
+  return true;
+}
+
+/* For debugging.  */
+static unsigned int
+check_invariants (NODE_T node, 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);
+}
diff --git a/lib/gl_avltree_oset.c b/lib/gl_avltree_oset.c
index ead337c0e1..4bda91eaae 100644
--- a/lib/gl_avltree_oset.c
+++ b/lib/gl_avltree_oset.c
@@ -22,542 +22,30 @@
 
 #include <stdlib.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 */
+/* Parameterization of gl_avltree_ordered.h.  */
+#define CONTAINER_T gl_oset_t
+#define CONTAINER_IMPL gl_oset_impl
+#define CONTAINER_IMPL_BASE gl_oset_impl_base
+#define NODE_IMPL gl_oset_node_impl
+#define NODE_T gl_oset_node_t
+#define NODE_PAYLOAD_FIELDS \
   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) - 1 [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 - 1 elements, and because even on 64-bit machines,
-     sizeof (gl_oset_node_impl) * (F_87 - 1) > 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;
+#define NODE_PAYLOAD_PARAMS \
+  const void *elt
+#define NODE_PAYLOAD_ASSIGN(node) \
+  node->value = elt;
+#define NODE_PAYLOAD_DISPOSE \
+  if (container->base.dispose_fn != NULL) \
+    container->base.dispose_fn (node->value);
 
-                  *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_nx_add_first (gl_oset_t set, const void *elt)
-{
-  /* Create new node.  */
-  gl_oset_node_t new_node =
-    (struct gl_oset_node_impl *) malloc (sizeof (struct gl_oset_node_impl));
-
-  if (new_node == NULL)
-    return NULL;
-
-  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_nx_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 *) malloc (sizeof (struct gl_oset_node_impl));
-  bool height_inc;
-
-  if (new_node == NULL)
-    return NULL;
-
-  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_nx_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 *) malloc (sizeof (struct gl_oset_node_impl));
-  bool height_inc;
-
-  if (new_node == NULL)
-    return NULL;
-
-  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--;
-  if (set->base.dispose_fn != NULL)
-    set->base.dispose_fn (node->value);
-  free (node);
-  return true;
-}
+#include "gl_avltree_ordered.h"
 
 /* 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)
 {
diff --git a/modules/avltree-omap b/modules/avltree-omap
new file mode 100644
index 0000000000..60e0dc6cd2
--- /dev/null
+++ b/modules/avltree-omap
@@ -0,0 +1,25 @@
+Description:
+Ordered map data type implemented by a binary tree.
+
+Files:
+lib/gl_avltree_omap.h
+lib/gl_avltree_omap.c
+lib/gl_avltree_ordered.h
+lib/gl_anytree_omap.h
+
+Depends-on:
+omap
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_avltree_omap.h gl_avltree_omap.c gl_avltree_ordered.h gl_anytree_omap.h
+
+Include:
+"gl_avltree_omap.h"
+
+License:
+GPL
+
+Maintainer:
+all
diff --git a/modules/avltree-oset b/modules/avltree-oset
index 2946737d5f..5bdb482e8f 100644
--- a/modules/avltree-oset
+++ b/modules/avltree-oset
@@ -4,6 +4,7 @@ Ordered set data type implemented by a binary tree.
 Files:
 lib/gl_avltree_oset.h
 lib/gl_avltree_oset.c
+lib/gl_avltree_ordered.h
 lib/gl_anytree_oset.h
 
 Depends-on:
@@ -12,7 +13,7 @@ oset
 configure.ac:
 
 Makefile.am:
-lib_SOURCES += gl_avltree_oset.h gl_avltree_oset.c gl_anytree_oset.h
+lib_SOURCES += gl_avltree_oset.h gl_avltree_oset.c gl_avltree_ordered.h gl_anytree_oset.h
 
 Include:
 "gl_avltree_oset.h"