>From 0c9a09fe0d2ca8c2338df88787d906215ae9528c Mon Sep 17 00:00:00 2001
From: Bruno Haible
Date: Mon, 10 Dec 2018 01:12:56 +0100
Subject: [PATCH 4/8] rbtree-omap: New module.
* lib/gl_rbtree_omap.h: New file.
* lib/gl_rbtree_omap.c: New file.
* lib/gl_rbtree_ordered.h: Code moved to here from lib/gl_rbtree_oset.c.
Parameterize.
* lib/gl_rbtree_oset.c: Include gl_rbtree_ordered.h.
* modules/rbtree-omap: New file.
* modules/rbtree-oset (Files): Add lib/gl_rbtree_ordered.h.
(Makefile.am): Add gl_rbtree_ordered.h to lib_SOURCES.
---
ChangeLog | 10 +
lib/gl_rbtree_omap.c | 75 +++++
lib/gl_rbtree_omap.h | 34 +++
lib/gl_rbtree_ordered.h | 778 ++++++++++++++++++++++++++++++++++++++++++++++++
lib/gl_rbtree_oset.c | 773 +----------------------------------------------
modules/rbtree-omap | 25 ++
modules/rbtree-oset | 3 +-
7 files changed, 939 insertions(+), 759 deletions(-)
create mode 100644 lib/gl_rbtree_omap.c
create mode 100644 lib/gl_rbtree_omap.h
create mode 100644 lib/gl_rbtree_ordered.h
create mode 100644 modules/rbtree-omap
diff --git a/ChangeLog b/ChangeLog
index eb99a16..83a5a88 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,15 @@
2018-12-09 Bruno Haible
+ rbtree-omap: New module.
+ * lib/gl_rbtree_omap.h: New file.
+ * lib/gl_rbtree_omap.c: New file.
+ * lib/gl_rbtree_ordered.h: Code moved to here from lib/gl_rbtree_oset.c.
+ Parameterize.
+ * lib/gl_rbtree_oset.c: Include gl_rbtree_ordered.h.
+ * modules/rbtree-omap: New file.
+ * modules/rbtree-oset (Files): Add lib/gl_rbtree_ordered.h.
+ (Makefile.am): Add gl_rbtree_ordered.h to lib_SOURCES.
+
avltree-omap: New module.
* lib/gl_avltree_omap.h: New file.
* lib/gl_avltree_omap.c: New file.
diff --git a/lib/gl_rbtree_omap.c b/lib/gl_rbtree_omap.c
new file mode 100644
index 0000000..11540aa
--- /dev/null
+++ b/lib/gl_rbtree_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 , 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 . */
+
+#include
+
+/* Specification. */
+#include "gl_rbtree_omap.h"
+
+#include
+
+/* -------------------------- gl_omap_t Data Type -------------------------- */
+
+/* Parameterization of gl_rbtree_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_rbtree_ordered.h"
+
+/* Generic binary tree code. */
+#include "gl_anytree_omap.h"
+
+/* For debugging. */
+void
+gl_rbtree_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_rbtree_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_rbtree_omap.h b/lib/gl_rbtree_omap.h
new file mode 100644
index 0000000..596952f
--- /dev/null
+++ b/lib/gl_rbtree_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 , 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 . */
+
+#ifndef _GL_RBTREE_OMAP_H
+#define _GL_RBTREE_OMAP_H
+
+#include "gl_omap.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+extern const struct gl_omap_implementation gl_rbtree_omap_implementation;
+#define GL_RBTREE_OMAP &gl_rbtree_omap_implementation
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _GL_RBTREE_OMAP_H */
diff --git a/lib/gl_rbtree_ordered.h b/lib/gl_rbtree_ordered.h
new file mode 100644
index 0000000..7d62301
--- /dev/null
+++ b/lib/gl_rbtree_ordered.h
@@ -0,0 +1,778 @@
+/* Ordered {set,map} data type implemented by a binary tree.
+ Copyright (C) 2006-2007, 2009-2018 Free Software Foundation, Inc.
+ Written by Bruno Haible , 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 . */
+
+/* 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
+ alternately black-red-black-red-...-black-red.) The height of the tree
+ therefore is >= bh, <= 2*bh.
+ */
+
+/* Color of a node. */
+typedef enum color { BLACK, RED } color_t;
+
+/* 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 _remove_node,
+ _add_before, _add_after can be implemented. */
+ struct NODE_IMPL *parent;
+ color_t color; /* node's color */
+ 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 */
+};
+
+/* 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 (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 NODE_T
+rotate_left (NODE_T b_node, NODE_T d_node)
+{
+ 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 NODE_T
+rotate_right (NODE_T b_node, NODE_T d_node)
+{
+ 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 (CONTAINER_T container, NODE_T node, NODE_T parent)
+{
+ for (;;)
+ {
+ /* At this point, parent = node->parent != NULL.
+ Think of node->color being RED (although node->color is not yet
+ assigned.) */
+ NODE_T grandparent;
+ 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. */
+ NODE_T *grandparentp;
+
+ if (grandparent->parent == NULL)
+ grandparentp = &container->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 (CONTAINER_T container, NODE_T child, 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. */
+ NODE_T *parentp;
+
+ if (parent->parent == NULL)
+ parentp = &container->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)
+ {
+ 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)
+ {
+ 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 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;
+ NODE_PAYLOAD_ASSIGN(new_node)
+
+ /* Add it to the tree. */
+ if (container->root == NULL)
+ {
+ new_node->color = BLACK;
+ 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;
+
+ /* Color and rebalance. */
+ rebalance_after_add (container, new_node, node);
+ }
+
+ 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));
+
+ if (new_node == NULL)
+ return NULL;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+ NODE_PAYLOAD_ASSIGN(new_node)
+
+ /* 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 (container, new_node, node);
+
+ 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));
+
+ if (new_node == NULL)
+ return NULL;
+
+ new_node->left = NULL;
+ new_node->right = NULL;
+ NODE_PAYLOAD_ASSIGN(new_node)
+
+ /* 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 (container, new_node, node);
+
+ 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;
+ /* 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)
+ container->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 (container, 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. */
+ 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)
+ container->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. */
+ NODE_T subst;
+ NODE_T subst_parent;
+ 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)
+ container->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 (container, child,
+ 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_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);
+}
diff --git a/lib/gl_rbtree_oset.c b/lib/gl_rbtree_oset.c
index 521d3d5..c3c0a76 100644
--- a/lib/gl_rbtree_oset.c
+++ b/lib/gl_rbtree_oset.c
@@ -22,773 +22,30 @@
#include
-/* 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
- alternately 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 */
+/* Parameterization of gl_rbtree_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 */
-};
-
-/* 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 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 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;
+#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);
- 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_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->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_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));
-
- if (new_node == NULL)
- return NULL;
-
- 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_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));
-
- if (new_node == NULL)
- return NULL;
-
- 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--;
- if (set->base.dispose_fn != NULL)
- set->base.dispose_fn (node->value);
- free (node);
- return true;
-}
+#include "gl_rbtree_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_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)
{
diff --git a/modules/rbtree-omap b/modules/rbtree-omap
new file mode 100644
index 0000000..f828ae0
--- /dev/null
+++ b/modules/rbtree-omap
@@ -0,0 +1,25 @@
+Description:
+Ordered map data type implemented by a binary tree.
+
+Files:
+lib/gl_rbtree_omap.h
+lib/gl_rbtree_omap.c
+lib/gl_rbtree_ordered.h
+lib/gl_anytree_omap.h
+
+Depends-on:
+omap
+
+configure.ac:
+
+Makefile.am:
+lib_SOURCES += gl_rbtree_omap.h gl_rbtree_omap.c gl_rbtree_ordered.h gl_anytree_omap.h
+
+Include:
+"gl_rbtree_omap.h"
+
+License:
+GPL
+
+Maintainer:
+all
diff --git a/modules/rbtree-oset b/modules/rbtree-oset
index 299f257..7b7d3ca 100644
--- a/modules/rbtree-oset
+++ b/modules/rbtree-oset
@@ -4,6 +4,7 @@ Ordered set data type implemented by a binary tree.
Files:
lib/gl_rbtree_oset.h
lib/gl_rbtree_oset.c
+lib/gl_rbtree_ordered.h
lib/gl_anytree_oset.h
Depends-on:
@@ -12,7 +13,7 @@ oset
configure.ac:
Makefile.am:
-lib_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_anytree_oset.h
+lib_SOURCES += gl_rbtree_oset.h gl_rbtree_oset.c gl_rbtree_ordered.h gl_anytree_oset.h
Include:
"gl_rbtree_oset.h"
--
2.7.4