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
___________________________________
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Tue Jul 15 2003 - 22:00:39 EST