libext2fs: add rbtree library

This commit adds rbtree library into e2fsprogs so it can be used for
various internal data structures. The rbtree implementation is ripped of
kernel rbtree implementation with small changes needed for it to work
outside kernel.

[ I prefixed the exported symbols and interface with ext2fs_ to keep
  avoid pulluting the namespace exported by the libext2fs shared
  library.  -- tytso ]

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

3 files changed, 640 insertions, 2 deletions

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 37f5ee5d..cdf53b89 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -83,7 +83,8 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
 	unix_io.o \
 	unlink.o \
 	valid_blk.o \
-	version.o
+	version.o \
+	rbtree.o
 
 SRCS= ext2_err.c \
 	$(srcdir)/alloc.c \
@@ -162,7 +163,8 @@ SRCS= ext2_err.c \
 	$(srcdir)/unlink.c \
 	$(srcdir)/valid_blk.c \
 	$(srcdir)/version.c \
-	$(srcdir)/write_bb_file.c
+	$(srcdir)/write_bb_file.c \
+	$(srcdir)/rbtree.c \
 
 HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
 	tdb.h qcow2.h
@@ -919,3 +921,8 @@ write_bb_file.o: $(srcdir)/write_bb_file.c $(top_builddir)/lib/config.h \
  $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
  $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
+rbtree.o: $(srcdir)/rbtree.c $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
+ $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
+ $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
+ $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
diff --git a/lib/ext2fs/rbtree.c b/lib/ext2fs/rbtree.c
new file mode 100644
index 00000000..7467e10e
--- /dev/null
+++ b/lib/ext2fs/rbtree.c
@@ -0,0 +1,451 @@
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  (C) 2002  David Woodhouse <dwmw2@infradead.org>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 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, write to the Free Software
+  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+  linux/lib/rbtree.c
+*/
+
+#include "rbtree.h"
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *right = node->rb_right;
+	struct rb_node *parent = ext2fs_rb_parent(node);
+
+	if ((node->rb_right = right->rb_left))
+		ext2fs_rb_set_parent(right->rb_left, node);
+	right->rb_left = node;
+
+	ext2fs_rb_set_parent(right, parent);
+
+	if (parent)
+	{
+		if (node == parent->rb_left)
+			parent->rb_left = right;
+		else
+			parent->rb_right = right;
+	}
+	else
+		root->rb_node = right;
+	ext2fs_rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *left = node->rb_left;
+	struct rb_node *parent = ext2fs_rb_parent(node);
+
+	if ((node->rb_left = left->rb_right))
+		ext2fs_rb_set_parent(left->rb_right, node);
+	left->rb_right = node;
+
+	ext2fs_rb_set_parent(left, parent);
+
+	if (parent)
+	{
+		if (node == parent->rb_right)
+			parent->rb_right = left;
+		else
+			parent->rb_left = left;
+	}
+	else
+		root->rb_node = left;
+	ext2fs_rb_set_parent(node, left);
+}
+
+void ext2fs_rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *parent, *gparent;
+
+	while ((parent = ext2fs_rb_parent(node)) && ext2fs_rb_is_red(parent))
+	{
+		gparent = ext2fs_rb_parent(parent);
+
+		if (parent == gparent->rb_left)
+		{
+			{
+				register struct rb_node *uncle = gparent->rb_right;
+				if (uncle && ext2fs_rb_is_red(uncle))
+				{
+					ext2fs_rb_set_black(uncle);
+					ext2fs_rb_set_black(parent);
+					ext2fs_rb_set_red(gparent);
+					node = gparent;
+					continue;
+				}
+			}
+
+			if (parent->rb_right == node)
+			{
+				register struct rb_node *tmp;
+				__rb_rotate_left(parent, root);
+				tmp = parent;
+				parent = node;
+				node = tmp;
+			}
+
+			ext2fs_rb_set_black(parent);
+			ext2fs_rb_set_red(gparent);
+			__rb_rotate_right(gparent, root);
+		} else {
+			{
+				register struct rb_node *uncle = gparent->rb_left;
+				if (uncle && ext2fs_rb_is_red(uncle))
+				{
+					ext2fs_rb_set_black(uncle);
+					ext2fs_rb_set_black(parent);
+					ext2fs_rb_set_red(gparent);
+					node = gparent;
+					continue;
+				}
+			}
+
+			if (parent->rb_left == node)
+			{
+				register struct rb_node *tmp;
+				__rb_rotate_right(parent, root);
+				tmp = parent;
+				parent = node;
+				node = tmp;
+			}
+
+			ext2fs_rb_set_black(parent);
+			ext2fs_rb_set_red(gparent);
+			__rb_rotate_left(gparent, root);
+		}
+	}
+
+	ext2fs_rb_set_black(root->rb_node);
+}
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+			     struct rb_root *root)
+{
+	struct rb_node *other;
+
+	while ((!node || ext2fs_rb_is_black(node)) && node != root->rb_node)
+	{
+		if (parent->rb_left == node)
+		{
+			other = parent->rb_right;
+			if (ext2fs_rb_is_red(other))
+			{
+				ext2fs_rb_set_black(other);
+				ext2fs_rb_set_red(parent);
+				__rb_rotate_left(parent, root);
+				other = parent->rb_right;
+			}
+			if ((!other->rb_left || ext2fs_rb_is_black(other->rb_left)) &&
+			    (!other->rb_right || ext2fs_rb_is_black(other->rb_right)))
+			{
+				ext2fs_rb_set_red(other);
+				node = parent;
+				parent = ext2fs_rb_parent(node);
+			}
+			else
+			{
+				if (!other->rb_right || ext2fs_rb_is_black(other->rb_right))
+				{
+					ext2fs_rb_set_black(other->rb_left);
+					ext2fs_rb_set_red(other);
+					__rb_rotate_right(other, root);
+					other = parent->rb_right;
+				}
+				ext2fs_rb_set_color(other, ext2fs_rb_color(parent));
+				ext2fs_rb_set_black(parent);
+				ext2fs_rb_set_black(other->rb_right);
+				__rb_rotate_left(parent, root);
+				node = root->rb_node;
+				break;
+			}
+		}
+		else
+		{
+			other = parent->rb_left;
+			if (ext2fs_rb_is_red(other))
+			{
+				ext2fs_rb_set_black(other);
+				ext2fs_rb_set_red(parent);
+				__rb_rotate_right(parent, root);
+				other = parent->rb_left;
+			}
+			if ((!other->rb_left || ext2fs_rb_is_black(other->rb_left)) &&
+			    (!other->rb_right || ext2fs_rb_is_black(other->rb_right)))
+			{
+				ext2fs_rb_set_red(other);
+				node = parent;
+				parent = ext2fs_rb_parent(node);
+			}
+			else
+			{
+				if (!other->rb_left || ext2fs_rb_is_black(other->rb_left))
+				{
+					ext2fs_rb_set_black(other->rb_right);
+					ext2fs_rb_set_red(other);
+					__rb_rotate_left(other, root);
+					other = parent->rb_left;
+				}
+				ext2fs_rb_set_color(other, ext2fs_rb_color(parent));
+				ext2fs_rb_set_black(parent);
+				ext2fs_rb_set_black(other->rb_left);
+				__rb_rotate_right(parent, root);
+				node = root->rb_node;
+				break;
+			}
+		}
+	}
+	if (node)
+		ext2fs_rb_set_black(node);
+}
+
+void ext2fs_rb_erase(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *child, *parent;
+	int color;
+
+	if (!node->rb_left)
+		child = node->rb_right;
+	else if (!node->rb_right)
+		child = node->rb_left;
+	else
+	{
+		struct rb_node *old = node, *left;
+
+		node = node->rb_right;
+		while ((left = node->rb_left) != NULL)
+			node = left;
+
+		if (ext2fs_rb_parent(old)) {
+			if (ext2fs_rb_parent(old)->rb_left == old)
+				ext2fs_rb_parent(old)->rb_left = node;
+			else
+				ext2fs_rb_parent(old)->rb_right = node;
+		} else
+			root->rb_node = node;
+
+		child = node->rb_right;
+		parent = ext2fs_rb_parent(node);
+		color = ext2fs_rb_color(node);
+
+		if (parent == old) {
+			parent = node;
+		} else {
+			if (child)
+				ext2fs_rb_set_parent(child, parent);
+			parent->rb_left = child;
+
+			node->rb_right = old->rb_right;
+			ext2fs_rb_set_parent(old->rb_right, node);
+		}
+
+		node->rb_parent_color = old->rb_parent_color;
+		node->rb_left = old->rb_left;
+		ext2fs_rb_set_parent(old->rb_left, node);
+
+		goto color;
+	}
+
+	parent = ext2fs_rb_parent(node);
+	color = ext2fs_rb_color(node);
+
+	if (child)
+		ext2fs_rb_set_parent(child, parent);
+	if (parent)
+	{
+		if (parent->rb_left == node)
+			parent->rb_left = child;
+		else
+			parent->rb_right = child;
+	}
+	else
+		root->rb_node = child;
+
+ color:
+	if (color == RB_BLACK)
+		__rb_erase_color(child, parent, root);
+}
+
+static void ext2fs_rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
+{
+	struct rb_node *parent;
+
+up:
+	func(node, data);
+	parent = ext2fs_rb_parent(node);
+	if (!parent)
+		return;
+
+	if (node == parent->rb_left && parent->rb_right)
+		func(parent->rb_right, data);
+	else if (parent->rb_left)
+		func(parent->rb_left, data);
+
+	node = parent;
+	goto up;
+}
+
+/*
+ * after inserting @node into the tree, update the tree to account for
+ * both the new entry and any damage done by rebalance
+ */
+void ext2fs_rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
+{
+	if (node->rb_left)
+		node = node->rb_left;
+	else if (node->rb_right)
+		node = node->rb_right;
+
+	ext2fs_rb_augment_path(node, func, data);
+}
+
+/*
+ * before removing the node, find the deepest node on the rebalance path
+ * that will still be there after @node gets removed
+ */
+struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node)
+{
+	struct rb_node *deepest;
+
+	if (!node->rb_right && !node->rb_left)
+		deepest = ext2fs_rb_parent(node);
+	else if (!node->rb_right)
+		deepest = node->rb_left;
+	else if (!node->rb_left)
+		deepest = node->rb_right;
+	else {
+		deepest = ext2fs_rb_next(node);
+		if (deepest->rb_right)
+			deepest = deepest->rb_right;
+		else if (ext2fs_rb_parent(deepest) != node)
+			deepest = ext2fs_rb_parent(deepest);
+	}
+
+	return deepest;
+}
+
+/*
+ * after removal, update the tree to account for the removed entry
+ * and any rebalance damage.
+ */
+void ext2fs_rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
+{
+	if (node)
+		ext2fs_rb_augment_path(node, func, data);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *ext2fs_rb_first(const struct rb_root *root)
+{
+	struct rb_node	*n;
+
+	n = root->rb_node;
+	if (!n)
+		return NULL;
+	while (n->rb_left)
+		n = n->rb_left;
+	return n;
+}
+
+struct rb_node *ext2fs_rb_last(const struct rb_root *root)
+{
+	struct rb_node	*n;
+
+	n = root->rb_node;
+	if (!n)
+		return NULL;
+	while (n->rb_right)
+		n = n->rb_right;
+	return n;
+}
+
+struct rb_node *ext2fs_rb_next(const struct rb_node *node)
+{
+	struct rb_node *parent;
+
+	if (ext2fs_rb_parent(node) == node)
+		return NULL;
+
+	/* If we have a right-hand child, go down and then left as far
+	   as we can. */
+	if (node->rb_right) {
+		node = node->rb_right;
+		while (node->rb_left)
+			node=node->rb_left;
+		return (struct rb_node *)node;
+	}
+
+	/* No right-hand children.  Everything down and left is
+	   smaller than us, so any 'next' node must be in the general
+	   direction of our parent. Go up the tree; any time the
+	   ancestor is a right-hand child of its parent, keep going
+	   up. First time it's a left-hand child of its parent, said
+	   parent is our 'next' node. */
+	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_right)
+		node = parent;
+
+	return parent;
+}
+
+struct rb_node *ext2fs_rb_prev(const struct rb_node *node)
+{
+	struct rb_node *parent;
+
+	if (ext2fs_rb_parent(node) == node)
+		return NULL;
+
+	/* If we have a left-hand child, go down and then right as far
+	   as we can. */
+	if (node->rb_left) {
+		node = node->rb_left;
+		while (node->rb_right)
+			node=node->rb_right;
+		return (struct rb_node *)node;
+	}
+
+	/* No left-hand children. Go up till we find an ancestor which
+	   is a right-hand child of its parent */
+	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_left)
+		node = parent;
+
+	return parent;
+}
+
+void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new,
+			  struct rb_root *root)
+{
+	struct rb_node *parent = ext2fs_rb_parent(victim);
+
+	/* Set the surrounding nodes to point to the replacement */
+	if (parent) {
+		if (victim == parent->rb_left)
+			parent->rb_left = new;
+		else
+			parent->rb_right = new;
+	} else {
+		root->rb_node = new;
+	}
+	if (victim->rb_left)
+		ext2fs_rb_set_parent(victim->rb_left, new);
+	if (victim->rb_right)
+		ext2fs_rb_set_parent(victim->rb_right, new);
+
+	/* Copy the pointers/colour from the victim to the replacement */
+	*new = *victim;
+}
diff --git a/lib/ext2fs/rbtree.h b/lib/ext2fs/rbtree.h
new file mode 100644
index 00000000..972297bf
--- /dev/null
+++ b/lib/ext2fs/rbtree.h
@@ -0,0 +1,180 @@
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 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, write to the Free Software
+  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+  linux/include/linux/rbtree.h
+
+  To use rbtrees you'll have to implement your own insert and search cores.
+  This will avoid us to use callbacks and to drop drammatically performances.
+  I know it's not the cleaner way,  but in C (not in C++) to get
+  performances and genericity...
+
+  Some example of insert and search follows here. The search is a plain
+  normal search over an ordered tree. The insert instead must be implemented
+  in two steps: First, the code must insert the element in order as a red leaf
+  in the tree, and then the support library function rb_insert_color() must
+  be called. Such function will do the not trivial work to rebalance the
+  rbtree, if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+						 unsigned long offset)
+{
+	struct rb_node * n = inode->i_rb_page_cache.rb_node;
+	struct page * page;
+
+	while (n)
+	{
+		page = rb_entry(n, struct page, rb_page_cache);
+
+		if (offset < page->offset)
+			n = n->rb_left;
+		else if (offset > page->offset)
+			n = n->rb_right;
+		else
+			return page;
+	}
+	return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+						   unsigned long offset,
+						   struct rb_node * node)
+{
+	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+	struct rb_node * parent = NULL;
+	struct page * page;
+
+	while (*p)
+	{
+		parent = *p;
+		page = rb_entry(parent, struct page, rb_page_cache);
+
+		if (offset < page->offset)
+			p = &(*p)->rb_left;
+		else if (offset > page->offset)
+			p = &(*p)->rb_right;
+		else
+			return page;
+	}
+
+	rb_link_node(node, parent, p);
+
+	return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+						 unsigned long offset,
+						 struct rb_node * node)
+{
+	struct page * ret;
+	if ((ret = __rb_insert_page_cache(inode, offset, node)))
+		goto out;
+	rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+	return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef	_LINUX_RBTREE_H
+#define	_LINUX_RBTREE_H
+
+#include <stdlib.h>
+
+#undef offsetof
+#ifdef __compiler_offsetof
+#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
+#else
+#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+#endif
+
+#define container_of(ptr, type, member) ({			\
+	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+
+struct rb_node
+{
+	unsigned long  rb_parent_color;
+#define	RB_RED		0
+#define	RB_BLACK	1
+	struct rb_node *rb_right;
+	struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+    /* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root
+{
+	struct rb_node *rb_node;
+};
+
+
+#define ext2fs_rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define ext2fs_rb_color(r)   ((r)->rb_parent_color & 1)
+#define ext2fs_rb_is_red(r)   (!ext2fs_rb_color(r))
+#define ext2fs_rb_is_black(r) ext2fs_rb_color(r)
+#define ext2fs_rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
+#define ext2fs_rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void ext2fs_rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void ext2fs_rb_set_color(struct rb_node *rb, int color)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
+#define RB_ROOT	(struct rb_root) { NULL, }
+#define	ext2fs_rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define EXT2FS_RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
+#define EXT2FS_RB_EMPTY_NODE(node)	(ext2fs_rb_parent(node) == node)
+#define EXT2FS_RB_CLEAR_NODE(node)	(ext2fs_rb_set_parent(node, node))
+
+extern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *);
+extern void ext2fs_rb_erase(struct rb_node *, struct rb_root *);
+
+typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+
+extern void ext2fs_rb_augment_insert(struct rb_node *node,
+			      rb_augment_f func, void *data);
+extern struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node);
+extern void ext2fs_rb_augment_erase_end(struct rb_node *node,
+				 rb_augment_f func, void *data);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *ext2fs_rb_next(const struct rb_node *);
+extern struct rb_node *ext2fs_rb_prev(const struct rb_node *);
+extern struct rb_node *ext2fs_rb_first(const struct rb_root *);
+extern struct rb_node *ext2fs_rb_last(const struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new,
+				 struct rb_root *root);
+
+static inline void ext2fs_rb_link_node(struct rb_node * node,
+				     struct rb_node * parent,
+				     struct rb_node ** rb_link)
+{
+	node->rb_parent_color = (unsigned long )parent;
+	node->rb_left = node->rb_right = NULL;
+
+	*rb_link = node;
+}
+
+#endif	/* _LINUX_RBTREE_H */