commit b4eba17564b216b75eb89f6b06a62b572a69ac2e
Author: Bob Peterson <bob@ganesha.peterson>
Date:   Thu Jan 21 12:16:10 2010 -0600

    fsck.gfs2: convert dup_list to a rbtree
    
    This patch uses a new include file, osi_tree.h to implement
    the duplicates list as a red-black tree.  This will speed up
    the duplicate processing considerably.
    
    rhbz#455300

diff --git a/gfs2/fsck/fsck.h b/gfs2/fsck/fsck.h
index 5594548..fadb73e 100644
--- a/gfs2/fsck/fsck.h
+++ b/gfs2/fsck/fsck.h
@@ -14,6 +14,7 @@
 #define _FSCK_H
 
 #include "libgfs2.h"
+#include "osi_tree.h"
 
 #define FSCK_HASH_SHIFT         (13)
 #define FSCK_HASH_SIZE          (1 << FSCK_HASH_SHIFT)
@@ -60,6 +61,31 @@ struct dir_status {
 	uint32_t entry_count;
 };
 
+struct duptree {
+	struct osi_node node;
+	int first_ref_found; /* Has the original reference been found? */
+	int refs;
+	uint64_t block;
+	osi_list_t ref_inode_list; /* list of inodes referencing a dup block */
+	osi_list_t ref_invinode_list; /* list of invalid inodes referencing */
+};
+
+enum dup_ref_type {
+	ref_as_data = 0,
+	ref_as_meta = 1,
+	ref_as_ea   = 2,
+	ref_types   = 3
+};
+
+struct inode_with_dups {
+	osi_list_t list;
+	uint64_t block_no;
+	int dup_count;
+	int ea_only;
+	uint64_t parent;
+	char *name;
+};
+
 enum rgindex_trust_level { /* how far can we trust our RG index? */
 	blind_faith = 0, /* We'd like to trust the rgindex. We always used to
 			    before bz 179069. This should cover most cases. */
@@ -71,12 +97,6 @@ enum rgindex_trust_level { /* how far can we trust our RG index? */
 			  gfs2_grow or something.  Count the RGs by hand. */
 };
 
-struct dup_blks {
-	osi_list_t list;
-	uint64_t block;
-	osi_list_t ref_inode_list;
-};
-
 extern struct gfs2_inode *fsck_load_inode(struct gfs2_sbd *sbp, uint64_t block);
 extern struct gfs2_inode *fsck_inode_get(struct gfs2_sbd *sdp,
 				  struct gfs2_buffer_head *bh);
@@ -93,9 +113,11 @@ extern int pass3(struct gfs2_sbd *sbp);
 extern int pass4(struct gfs2_sbd *sbp);
 extern int pass5(struct gfs2_sbd *sbp);
 extern int rg_repair(struct gfs2_sbd *sdp, int trust_lvl, int *rg_count);
+extern void gfs2_dup_free(void);
 extern int fsck_query(const char *format, ...)
 	__attribute__((format(printf,1,2)));
 extern struct dir_info *dirtree_find(uint64_t block);
+extern void dup_delete(struct duptree *b);
 extern void dirtree_delete(struct dir_info *b);
 
 /* FIXME: Hack to get this going for pass2 - this should be pulled out
@@ -113,6 +135,6 @@ extern int skip_this_pass, fsck_abort;
 extern int errors_found, errors_corrected;
 extern uint64_t last_data_block;
 extern uint64_t first_data_block;
-extern struct dup_blks dup_blocks;
+extern struct osi_root dup_blocks;
 
 #endif /* _FSCK_H */
diff --git a/gfs2/fsck/initialize.c b/gfs2/fsck/initialize.c
index 7aad96e..48859eb 100644
--- a/gfs2/fsck/initialize.c
+++ b/gfs2/fsck/initialize.c
@@ -72,17 +72,14 @@ static int block_mounters(struct gfs2_sbd *sbp, int block_em)
 	return 0;
 }
 
-static void gfs2_dup_free(void)
+void gfs2_dup_free(void)
 {
-	struct dup_blks *f;
-
-	while(!osi_list_empty(&dup_blocks.list)) {
-		f = osi_list_entry(dup_blocks.list.next, struct dup_blks,
-				   list);
-		while (!osi_list_empty(&f->ref_inode_list))
-			osi_list_del(&f->ref_inode_list);
-		osi_list_del(&f->list);
-		free(f);
+	struct osi_node *n;
+	struct duptree *dt;
+
+	while ((n = osi_first(&dup_blocks))) {
+		dt = (struct duptree *)n;
+		dup_delete(dt);
 	}
 }
 
@@ -117,10 +114,9 @@ static void empty_super_block(struct gfs2_sbd *sdp)
 		}
 	}
 
-	if (bl) {
+	if (bl)
 		gfs2_bmap_destroy(sdp, bl);
-		gfs2_dup_free();
-	}
+	gfs2_dup_free();
 }
 
 
@@ -411,7 +407,6 @@ static int init_system_inodes(struct gfs2_sbd *sdp)
 		log_crit( _("Please increase your swap space by that amount and run gfs2_fsck again.\n"));
 		goto fail;
 	}
-	osi_list_init(&dup_blocks.list);
 	return 0;
  fail:
 	empty_super_block(sdp);
diff --git a/gfs2/fsck/main.c b/gfs2/fsck/main.c
index 3b5bfac..24f9500 100644
--- a/gfs2/fsck/main.c
+++ b/gfs2/fsck/main.c
@@ -43,7 +43,7 @@ uint64_t last_data_block;
 uint64_t first_data_block;
 const char *prog_name = "gfs2_fsck"; /* needed by libgfs2 */
 int preen = 0, force_check = 0;
-struct dup_blks dup_blocks;
+struct osi_root dup_blocks = (struct osi_root) { NULL, };
 
 /* This function is for libgfs2's sake.                                      */
 void print_it(const char *label, const char *fmt, const char *fmt2, ...)
diff --git a/gfs2/fsck/metawalk.c b/gfs2/fsck/metawalk.c
index b547f44..dae71ab 100644
--- a/gfs2/fsck/metawalk.c
+++ b/gfs2/fsck/metawalk.c
@@ -29,20 +29,6 @@
 
 #define COMFORTABLE_BLKS 5242880 /* 20GB in 4K blocks */
 
-struct dup_blks *dupfind(uint64_t num)
-{
-	osi_list_t *head = &dup_blocks.list;
-	osi_list_t *tmp;
-	struct dup_blks *b;
-
-	for (tmp = head->next; tmp != head; tmp = tmp->next) {
-		b = osi_list_entry(tmp, struct dup_blks, list);
-		if (b->block == num)
-			return b;
-	}
-	return NULL;
-}
-
 static struct gfs2_inode *get_system_inode(struct gfs2_sbd *sbp,
 					   uint64_t block)
 {
@@ -67,6 +53,23 @@ static struct gfs2_inode *get_system_inode(struct gfs2_sbd *sbp,
 	return is_system_inode(sbp, block);
 }
 
+struct duptree *dupfind(uint64_t block)
+{
+	struct osi_node *node = dup_blocks.osi_node;
+
+	while (node) {
+		struct duptree *data = (struct duptree *)node;
+
+		if (block < data->block)
+			node = node->osi_left;
+		else if (block > data->block)
+			node = node->osi_right;
+		else
+			return data;
+	}
+	return NULL;
+}
+
 /* fsck_load_inode - same as gfs2_load_inode() in libgfs2 but system inodes
    get special treatment. */
 struct gfs2_inode *fsck_load_inode(struct gfs2_sbd *sbp, uint64_t block)
diff --git a/gfs2/fsck/metawalk.h b/gfs2/fsck/metawalk.h
index 1c1a646..497a1bf 100644
--- a/gfs2/fsck/metawalk.h
+++ b/gfs2/fsck/metawalk.h
@@ -44,7 +44,7 @@ extern int delete_eattr_indir(struct gfs2_inode *ip, uint64_t block,
 extern int delete_eattr_leaf(struct gfs2_inode *ip, uint64_t block,
 			     uint64_t parent, struct gfs2_buffer_head **bh,
 			     void *private);
-extern struct dup_blks *dupfind(uint64_t num);
+extern struct duptree *dupfind(uint64_t block);
 
 #define is_duplicate(dblock) ((dupfind(dblock)) ? 1 : 0)
 
diff --git a/gfs2/fsck/pass1b.c b/gfs2/fsck/pass1b.c
index 57e4c47..d035e4f 100644
--- a/gfs2/fsck/pass1b.c
+++ b/gfs2/fsck/pass1b.c
@@ -26,15 +26,6 @@
 #include "metawalk.h"
 #include "inode_hash.h"
 
-struct inode_with_dups {
-	osi_list_t list;
-	uint64_t block_no;
-	int dup_count;
-	int ea_only;
-	uint64_t parent;
-	char *name;
-};
-
 struct fxn_info {
 	uint64_t block;
 	int found;
@@ -42,7 +33,7 @@ struct fxn_info {
 };
 
 struct dup_handler {
-	struct dup_blks *b;
+	struct duptree *b;
 	struct inode_with_dups *id;
 	int ref_inode_count;
 	int ref_count;
@@ -127,13 +118,14 @@ static int find_dentry(struct gfs2_inode *ip, struct gfs2_dirent *de,
 		       struct gfs2_buffer_head *bh, char *filename,
 		       uint16_t *count, void *priv)
 {
-	osi_list_t *tmp1, *tmp2;
-	struct dup_blks *b;
+	struct osi_node *n;
+	osi_list_t *tmp2;
+	struct duptree *b;
 	struct inode_with_dups *id;
 	struct gfs2_leaf leaf;
 
-	osi_list_foreach(tmp1, &dup_blocks.list) {
-		b = osi_list_entry(tmp1, struct dup_blks, list);
+	for (n = osi_first(&dup_blocks); n; n = osi_next(n)) {
+		b = (struct duptree *)n;
 		osi_list_foreach(tmp2, &b->ref_inode_list) {
 			id = osi_list_entry(tmp2, struct inode_with_dups,
 					    list);
@@ -328,7 +320,7 @@ static int clear_eattr_extentry(struct gfs2_inode *ip, uint64_t *ea_data_ptr,
 }
 
 /* Finds all references to duplicate blocks in the metadata */
-static int find_block_ref(struct gfs2_sbd *sbp, uint64_t inode, struct dup_blks *b)
+static int find_block_ref(struct gfs2_sbd *sbp, uint64_t inode, struct duptree *b)
 {
 	struct gfs2_inode *ip;
 	struct fxn_info myfi = {b->block, 0, 1};
@@ -382,7 +374,7 @@ static int find_block_ref(struct gfs2_sbd *sbp, uint64_t inode, struct dup_blks
 	return 0;
 }
 
-static int handle_dup_blk(struct gfs2_sbd *sbp, struct dup_blks *b)
+static int handle_dup_blk(struct gfs2_sbd *sbp, struct duptree *b)
 {
 	osi_list_t *tmp;
 	struct inode_with_dups *id;
@@ -506,10 +498,10 @@ static int handle_dup_blk(struct gfs2_sbd *sbp, struct dup_blks *b)
  * use in pass2 */
 int pass1b(struct gfs2_sbd *sbp)
 {
-	struct dup_blks *b;
+	struct duptree *b;
 	uint64_t i;
 	uint8_t q;
-	osi_list_t *tmp = NULL, *x;
+	struct osi_node *n;
 	struct metawalk_fxns find_dirents = {0};
 	int rc = FSCK_OK;
 	find_dirents.check_dentry = &find_dentry;
@@ -517,7 +509,7 @@ int pass1b(struct gfs2_sbd *sbp)
 	log_info( _("Looking for duplicate blocks...\n"));
 
 	/* If there were no dups in the bitmap, we don't need to do anymore */
-	if(osi_list_empty(&dup_blocks.list)) {
+	if (dup_blocks.osi_node == NULL) {
 		log_info( _("No duplicate blocks found\n"));
 		return FSCK_OK;
 	}
@@ -541,9 +533,8 @@ int pass1b(struct gfs2_sbd *sbp)
 		   (q == gfs2_inode_chr) ||
 		   (q == gfs2_inode_fifo) ||
 		   (q == gfs2_inode_sock)) {
-			osi_list_foreach_safe(tmp, &dup_blocks.list, x) {
-				b = osi_list_entry(tmp, struct dup_blks,
-						   list);
+			for (n = osi_first(&dup_blocks); n; n = osi_next(n)) {
+				b = (struct duptree *)n;
 				if(find_block_ref(sbp, i, b)) {
 					stack;
 					rc = FSCK_ERROR;
@@ -560,8 +551,8 @@ int pass1b(struct gfs2_sbd *sbp)
 	 * it later */
 	log_info( _("Handling duplicate blocks\n"));
 out:
-        osi_list_foreach_safe(tmp, &dup_blocks.list, x) {
-                b = osi_list_entry(tmp, struct dup_blks, list);
+        for (n = osi_first(&dup_blocks); n; n = osi_next(n)) {
+                b = (struct duptree *)n;
 		if (!skip_this_pass && !rc) /* no error & not asked to skip the rest */
 			handle_dup_blk(sbp, b);
 		/* Do not attempt to free the dup_blocks list or its parts
diff --git a/gfs2/fsck/pass2.c b/gfs2/fsck/pass2.c
index 1547e6e..55a5be3 100644
--- a/gfs2/fsck/pass2.c
+++ b/gfs2/fsck/pass2.c
@@ -678,7 +678,6 @@ int pass2(struct gfs2_sbd *sbp)
 	int filename_len;
 	char tmp_name[256];
 	int error = 0;
-	struct dup_blks *b;
 
 	/* Check all the system directory inodes. */
 	if (check_system_dir(sbp->md.jiinode, "jindex", build_jindex)) {
@@ -824,12 +823,7 @@ int pass2(struct gfs2_sbd *sbp)
 	   deleting it from both inodes referencing it. Note: The other
 	   returns from this function are premature exits of the program
 	   and gfs2_block_list_destroy should get rid of the list for us. */
-	while (!osi_list_empty(&dup_blocks.list)) {
-		b = osi_list_entry(dup_blocks.list.next,
-				   struct dup_blks, list);
-		osi_list_del(&b->list);
-		free(b);
-	}
+	gfs2_dup_free();
 	return FSCK_OK;
 }
 
diff --git a/gfs2/fsck/util.c b/gfs2/fsck/util.c
index 264489a..6af2b41 100644
--- a/gfs2/fsck/util.c
+++ b/gfs2/fsck/util.c
@@ -197,18 +197,49 @@ int fsck_query(const char *format, ...)
 	return ret;
 }
 
-void gfs2_dup_set(uint64_t block)
+struct duptree *gfs2_dup_set(uint64_t dblock)
 {
-	struct dup_blks *b;
+	struct osi_node **newn = &dup_blocks.osi_node, *parent = NULL;
+	struct duptree *data;
+
+	/* Figure out where to put new node */
+	while (*newn) {
+		struct duptree *cur = (struct duptree *)*newn;
+
+		parent = *newn;
+		if (dblock < cur->block)
+			newn = &((*newn)->osi_left);
+		else if (dblock > cur->block)
+			newn = &((*newn)->osi_right);
+		else
+			return cur;
+	}
 
-	if (dupfind(block))
-		return;
-	b = malloc(sizeof(struct dup_blks));
-	if (b) {
-		memset(b, 0, sizeof(*b));
-		b->block = block;
-		osi_list_init(&b->ref_inode_list);
-		osi_list_add(&b->list, &dup_blocks.list);
+	data = malloc(sizeof(struct duptree));
+	memset(data, 0, sizeof(struct duptree));
+	/* Add new node and rebalance tree. */
+	data->block = dblock;
+	data->refs = 2; /* first call is the second reference to the block */
+	osi_list_init(&data->ref_inode_list);
+	osi_link_node(&data->node, parent, newn);
+	osi_insert_color(&data->node, &dup_blocks);
+
+	return data;
+}
+
+void dup_delete(struct duptree *b)
+{
+	struct inode_with_dups *id;
+	osi_list_t *tmp;
+
+	while (!osi_list_empty(&b->ref_inode_list)) {
+		tmp = (&b->ref_inode_list)->next;
+		id = osi_list_entry(tmp, struct inode_with_dups, list);
+		if (id->name)
+			free(id->name);
+		osi_list_del(&id->list);
+		free(id);
 	}
-	return;
+	osi_erase(&b->node, &dup_blocks);
+	free(b);
 }
diff --git a/gfs2/fsck/util.h b/gfs2/fsck/util.h
index 3a0d959..0113bdb 100644
--- a/gfs2/fsck/util.h
+++ b/gfs2/fsck/util.h
@@ -25,7 +25,7 @@ struct di_info *search_list(osi_list_t *list, uint64_t addr);
 void big_file_comfort(struct gfs2_inode *ip, uint64_t blks_checked);
 void warm_fuzzy_stuff(uint64_t block);
 const char *block_type_string(uint8_t q);
-void gfs2_dup_set(uint64_t block);
+struct duptree *gfs2_dup_set(uint64_t dblock);
 
 static inline uint8_t block_type(uint64_t bblock)
 {
diff --git a/gfs2/include/osi_tree.h b/gfs2/include/osi_tree.h
new file mode 100644
index 0000000..4ffae94
--- /dev/null
+++ b/gfs2/include/osi_tree.h
@@ -0,0 +1,395 @@
+#ifndef __OSI_RBTREE_DOT_H__
+#define __OSI_RBTREE_DOT_H__
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <assert.h>
+
+/* Adapted from the kernel's rbtree.c */
+struct osi_node {
+	unsigned long  osi_parent_color;
+#define	OSI_RED		0
+#define	OSI_BLACK	1
+	struct osi_node *osi_left;
+	struct osi_node *osi_right;
+	struct osi_node *osi_parent;
+};
+
+#define osi_parent(r)   ((struct osi_node *)((r)->osi_parent_color & ~3))
+#define osi_color(r)   ((r)->osi_parent_color & 1)
+#define osi_is_red(r)   (!osi_color(r))
+#define osi_is_black(r) osi_color(r)
+#define osi_set_red(r)  do { (r)->osi_parent_color &= ~1; } while (0)
+#define osi_set_black(r)  do { (r)->osi_parent_color |= 1; } while (0)
+
+struct osi_root
+{
+	struct osi_node *osi_node;
+};
+
+static inline void osi_set_color(struct osi_node *rb, int color)
+{
+	rb->osi_parent_color = (rb->osi_parent_color & ~1) | color;
+}
+
+static inline void osi_set_parent(struct osi_node *rb, struct osi_node *p)
+{
+        rb->osi_parent_color = (rb->osi_parent_color & 3) | (unsigned long)p;
+}
+
+static inline void osi_link_node(struct osi_node *node,
+				 struct osi_node *parent,
+				 struct osi_node **osi_link)
+{
+	node->osi_parent_color = (unsigned long )parent;
+	node->osi_left = node->osi_right = NULL;
+
+	*osi_link = node;
+}
+
+static inline void __osi_rotate_left(struct osi_node *node,
+				     struct osi_root *root)
+{
+	struct osi_node *right = node->osi_right;
+	struct osi_node *parent = osi_parent(node);
+
+	if ((node->osi_right = right->osi_left))
+		osi_set_parent(right->osi_left, node);
+	right->osi_left = node;
+
+	osi_set_parent(right, parent);
+
+	if (parent) {
+		if (node == parent->osi_left)
+			parent->osi_left = right;
+		else
+			parent->osi_right = right;
+	}
+	else
+		root->osi_node = right;
+	osi_set_parent(node, right);
+}
+
+static inline void __osi_rotate_right(struct osi_node *node,
+				      struct osi_root *root)
+{
+	struct osi_node *left = node->osi_left;
+	struct osi_node *parent = osi_parent(node);
+
+	if ((node->osi_left = left->osi_right))
+		osi_set_parent(left->osi_right, node);
+	left->osi_right = node;
+
+	osi_set_parent(left, parent);
+
+	if (parent) {
+		if (node == parent->osi_right)
+			parent->osi_right = left;
+		else
+			parent->osi_left = left;
+	} else
+		root->osi_node = left;
+	osi_set_parent(node, left);
+}
+
+static inline void osi_insert_color(struct osi_node *node,
+				    struct osi_root *root)
+{
+	struct osi_node *parent, *gparent;
+
+	while ((parent = osi_parent(node)) && osi_is_red(parent)) {
+		gparent = osi_parent(parent);
+
+		if (parent == gparent->osi_left) {
+			{
+				register struct osi_node *uncle = gparent->osi_right;
+				if (uncle && osi_is_red(uncle)) {
+					osi_set_black(uncle);
+					osi_set_black(parent);
+					osi_set_red(gparent);
+					node = gparent;
+					continue;
+				}
+			}
+
+			if (parent->osi_right == node) {
+				register struct osi_node *tmp;
+
+				__osi_rotate_left(parent, root);
+				tmp = parent;
+				parent = node;
+				node = tmp;
+			}
+
+			osi_set_black(parent);
+			osi_set_red(gparent);
+			__osi_rotate_right(gparent, root);
+		} else {
+			{
+				register struct osi_node *uncle = gparent->osi_left;
+				if (uncle && osi_is_red(uncle)) {
+					osi_set_black(uncle);
+					osi_set_black(parent);
+					osi_set_red(gparent);
+					node = gparent;
+					continue;
+				}
+			}
+
+			if (parent->osi_left == node) {
+				register struct osi_node *tmp;
+				__osi_rotate_right(parent, root);
+				tmp = parent;
+				parent = node;
+				node = tmp;
+			}
+
+			osi_set_black(parent);
+			osi_set_red(gparent);
+			__osi_rotate_left(gparent, root);
+		}
+	}
+
+	osi_set_black(root->osi_node);
+}
+
+static inline void __osi_erase_color(struct osi_node *node,
+				     struct osi_node *parent,
+				     struct osi_root *root)
+{
+	struct osi_node *other;
+
+	while ((!node || osi_is_black(node)) && node != root->osi_node) {
+		if (parent->osi_left == node) {
+			other = parent->osi_right;
+			if (osi_is_red(other)) {
+				osi_set_black(other);
+				osi_set_red(parent);
+				__osi_rotate_left(parent, root);
+				other = parent->osi_right;
+			}
+			if ((!other->osi_left || osi_is_black(other->osi_left)) &&
+			    (!other->osi_right || osi_is_black(other->osi_right)))
+			{
+				osi_set_red(other);
+				node = parent;
+				parent = osi_parent(node);
+			} else {
+				if (!other->osi_right || osi_is_black(other->osi_right))
+				{
+					struct osi_node *o_left;
+					if ((o_left = other->osi_left))
+						osi_set_black(o_left);
+					osi_set_red(other);
+					__osi_rotate_right(other, root);
+					other = parent->osi_right;
+				}
+				osi_set_color(other, osi_color(parent));
+				osi_set_black(parent);
+				if (other->osi_right)
+					osi_set_black(other->osi_right);
+				__osi_rotate_left(parent, root);
+				node = root->osi_node;
+				break;
+			}
+		} else {
+			other = parent->osi_left;
+			if (osi_is_red(other)) {
+				osi_set_black(other);
+				osi_set_red(parent);
+				__osi_rotate_right(parent, root);
+				other = parent->osi_left;
+			}
+			if ((!other->osi_left || osi_is_black(other->osi_left)) &&
+			    (!other->osi_right || osi_is_black(other->osi_right)))
+			{
+				osi_set_red(other);
+				node = parent;
+				parent = osi_parent(node);
+			} else {
+				if (!other->osi_left || osi_is_black(other->osi_left))
+				{
+					register struct osi_node *o_right;
+					if ((o_right = other->osi_right))
+						osi_set_black(o_right);
+					osi_set_red(other);
+					__osi_rotate_left(other, root);
+					other = parent->osi_left;
+				}
+				osi_set_color(other, osi_color(parent));
+				osi_set_black(parent);
+				if (other->osi_left)
+					osi_set_black(other->osi_left);
+				__osi_rotate_right(parent, root);
+				node = root->osi_node;
+				break;
+			}
+		}
+	}
+	if (node)
+		osi_set_black(node);
+}
+
+static inline void osi_erase(struct osi_node *node, struct osi_root *root)
+{
+	struct osi_node *child, *parent;
+	int color;
+
+	if (!node->osi_left)
+		child = node->osi_right;
+	else if (!node->osi_right)
+		child = node->osi_left;
+	else {
+		struct osi_node *old = node, *left;
+
+		node = node->osi_right;
+		while ((left = node->osi_left) != NULL)
+			node = left;
+		child = node->osi_right;
+		parent = osi_parent(node);
+		color = osi_color(node);
+
+		if (child)
+			osi_set_parent(child, parent);
+		if (parent == old) {
+			parent->osi_right = child;
+			parent = node;
+		} else
+			parent->osi_left = child;
+
+		node->osi_parent_color = old->osi_parent_color;
+		node->osi_right = old->osi_right;
+		node->osi_left = old->osi_left;
+
+		if (osi_parent(old)) {
+			if (osi_parent(old)->osi_left == old)
+				osi_parent(old)->osi_left = node;
+			else
+				osi_parent(old)->osi_right = node;
+		} else
+			root->osi_node = node;
+
+		osi_set_parent(old->osi_left, node);
+		if (old->osi_right)
+			osi_set_parent(old->osi_right, node);
+		goto color;
+	}
+
+	parent = osi_parent(node);
+	color = osi_color(node);
+
+	if (child)
+		osi_set_parent(child, parent);
+	if (parent)
+	{
+		if (parent->osi_left == node)
+			parent->osi_left = child;
+		else
+			parent->osi_right = child;
+	}
+	else
+		root->osi_node = child;
+
+ color:
+	if (color == OSI_BLACK)
+		__osi_erase_color(child, parent, root);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+static inline struct osi_node *osi_first(struct osi_root *root)
+{
+	struct osi_node	*n;
+
+	n = root->osi_node;
+	if (!n)
+		return NULL;
+	while (n->osi_left)
+		n = n->osi_left;
+	return n;
+}
+
+static inline struct osi_node *osi_last(struct osi_root *root)
+{
+	struct osi_node	*n;
+
+	n = root->osi_node;
+	if (!n)
+		return NULL;
+	while (n->osi_right)
+		n = n->osi_right;
+	return n;
+}
+
+static inline struct osi_node *osi_next(struct osi_node *node)
+{
+	struct osi_node *parent;
+
+	/* If we have a right-hand child, go down and then left as far
+	   as we can. */
+	if (node->osi_right) {
+		node = node->osi_right; 
+		while (node->osi_left)
+			node=node->osi_left;
+		return 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 = osi_parent(node)) && node == parent->osi_right)
+		node = parent;
+
+	return parent;
+}
+
+static inline struct osi_node *osi_prev(struct osi_node *node)
+{
+	struct osi_node *parent;
+
+	/* If we have a left-hand child, go down and then right as far
+	   as we can. */
+	if (node->osi_left) {
+		node = node->osi_left; 
+		while (node->osi_right)
+			node=node->osi_right;
+		return node;
+	}
+
+	/* No left-hand children. Go up till we find an ancestor which
+	   is a right-hand child of its parent */
+	while ((parent = osi_parent(node)) && node == parent->osi_left)
+		node = parent;
+
+	return parent;
+}
+
+static inline void osi_replace_node(struct osi_node *victim,
+				    struct osi_node *new,
+				    struct osi_root *root)
+{
+	struct osi_node *parent = osi_parent(victim);
+
+	/* Set the surrounding nodes to point to the replacement */
+	if (parent) {
+		if (victim == parent->osi_left)
+			parent->osi_left = new;
+		else
+			parent->osi_right = new;
+	} else {
+		root->osi_node = new;
+	}
+	if (victim->osi_left)
+		osi_set_parent(victim->osi_left, new);
+	if (victim->osi_right)
+		osi_set_parent(victim->osi_right, new);
+
+	/* Copy the pointers/colour from the victim to the replacement */
+	*new = *victim;
+}
+
+#endif