[PATCH 2.5.75mm1] rbtree branch access

[PATCH 2.5.75mm1] rbtree branch access

[ffrederick]

Andrew,

	Here is a patch to bring more functionnalities in rbtree.

Regards,
Fabian

Fabian Frederick
	-rbtree : add branch erase
	-rbtree : add get last node

--- linux-2.5.75mm1/include/linux/rbtree.h	2003-07-10 22:08:08.000000000 +0200
+++ linux-2.5.75mm1ff1/include/linux/rbtree.h	2003-07-11 14:42:14.000000000 +0200
@@ -118,11 +118,12 @@ struct rb_root
 
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
-
+extern void rb_erase_branch(struct rb_node *, struct rb_root *);
 /* Find logical next and previous nodes in a tree */
 extern struct rb_node *rb_next(struct rb_node *);
 extern struct rb_node *rb_prev(struct rb_node *);
-extern struct rb_node *rb_first(struct rb_root *);
+extern struct rb_node *rb_first(struct rb_root *); /* get first node in sort order */
+extern struct rb_node *rb_last(struct rb_root *);  /* get last node in sort order */
 
 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
--- linux-2.5.75mm1/lib/rbtree.c	2003-07-10 22:12:09.000000000 +0200
+++ linux-2.5.75mm1ff1/lib/rbtree.c	2003-07-11 15:20:54.000000000 +0200
@@ -2,6 +2,8 @@
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
   (C) 2002  David Woodhouse <dwmw2@infradead.org>
+
+  07/2003  branch access - Fabian Frederick <ffrederick@users.sourceforge.net>
   
   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
@@ -221,6 +223,18 @@ static void __rb_erase_color(struct rb_n
 		node->rb_color = RB_BLACK;
 }
 
+void rb_erase_branch(struct rb_node *node, struct rb_root *root)
+{
+
+ if(node->rb_left)
+	  return rb_erase_branch(node->rb_left, root);
+     else if (node->rb_right) 
+		return rb_erase_branch(node->rb_right, root);
+	   else return rb_erase(node, root);
+
+}
+
+EXPORT_SYMBOL(rb_erase_branch);
 void rb_erase(struct rb_node *node, struct rb_root *root)
 {
 	struct rb_node *child, *parent;
@@ -312,6 +326,17 @@ struct rb_node *rb_first(struct rb_root 
 }
 EXPORT_SYMBOL(rb_first);
 
+struct rb_node *rb_last(struct rb_root *root)
+{
+	struct rb_node *n;
+	n=root->rb_node;
+	if (!n)
+		return 0;
+	while(n->rb_right)
+		n = n->rb_right;
+	return n;
+}
+EXPORT_SYMBOL (rb_last);
 struct rb_node *rb_next(struct rb_node *node)
 {
 	/* If we have a right-hand child, go down and then left as far


___________________________________