This is the first of two rbtree patches which can be pulled from
master.kernel.org:/home/dwmw2/BK/rbtree-2.5
This adds three new rbtree functions. rb_next() and rb_prev() are used for
traversing a tree, and rb_replace_node() is for replacing a single node
without having to erase, rebalance, insert the replacement and rebalance
again.
# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
# ChangeSet 1.621 -> 1.622
# lib/rbtree.c 1.2 -> 1.3
# include/linux/rbtree.h 1.1 -> 1.2
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 02/09/09 dwmw2@infradead.org 1.622
# Add three functions for rbtree manipulation -- rb_next(), rb_prev() and rb_replace_node()
#
# rb_next() and rb_prev() return the next and previous nodes in the tree, respectively.
#
# rb_replace_node() allows fast replacement of a single node without having to remove the
# victim, rebalance the tree, insert the replacement and then rebalance again to the original
# topology.
# --------------------------------------------
#
diff -Nru a/include/linux/rbtree.h b/include/linux/rbtree.h
--- a/include/linux/rbtree.h Thu Sep 12 13:49:39 2002
+++ b/include/linux/rbtree.h Thu Sep 12 13:49:39 2002
@@ -121,6 +121,13 @@
extern void rb_insert_color(rb_node_t *, rb_root_t *);
extern void rb_erase(rb_node_t *, rb_root_t *);
+/* Find logical next and previous nodes in a tree */
+extern rb_node_t *rb_next(rb_node_t *);
+extern rb_node_t *rb_prev(rb_node_t *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void rb_replace_node(rb_node_t *victim, rb_node_t *new, rb_root_t *root);
+
static inline void rb_link_node(rb_node_t * node, rb_node_t * parent, rb_node_t ** rb_link)
{
node->rb_parent = parent;
diff -Nru a/lib/rbtree.c b/lib/rbtree.c
--- a/lib/rbtree.c Thu Sep 12 13:49:39 2002
+++ b/lib/rbtree.c Thu Sep 12 13:49:39 2002
@@ -1,6 +1,7 @@
/*
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
@@ -294,3 +295,70 @@
__rb_erase_color(child, parent, root);
}
EXPORT_SYMBOL(rb_erase);
+
+rb_node_t *rb_next(rb_node_t *node)
+{
+ /* 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 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 (node->rb_parent && node == node->rb_parent->rb_right)
+ node = node->rb_parent;
+
+ return node->rb_parent;
+}
+EXPORT_SYMBOL(rb_next);
+
+rb_node_t *rb_prev(rb_node_t *node)
+{
+ /* 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 node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while (node->rb_parent && node == node->rb_parent->rb_left)
+ node = node->rb_parent;
+
+ return node->rb_parent;
+}
+EXPORT_SYMBOL(rb_prev);
+
+void rb_replace_node(rb_node_t *victim, rb_node_t *new, rb_root_t *root)
+{
+ rb_node_t *parent = victim->rb_parent;
+
+ /* 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)
+ victim->rb_left->rb_parent = new;
+ if (victim->rb_right)
+ victim->rb_right->rb_parent = new;
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
+EXPORT_SYMBOL(rb_replace_node);
-- dwmw2- 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 : Sun Sep 15 2002 - 22:00:29 EST