lkml.org 
[lkml]   [2002]   [Aug]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH] rb_prev and rb_next.
Date
Functions to find the next or previous item in an rbtree. I accidentally 
violated the coding style of the file by letting a comment slip in; I can
remove it if that's a problem :)

===== lib/rbtree.c 1.2 vs edited =====
--- 1.2/lib/rbtree.c Wed Mar 27 13:07:17 2002
+++ edited/lib/rbtree.c Fri Aug 30 17:13:42 2002
@@ -294,3 +294,43 @@
__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 (node->rb_left) {
+ node = node->rb_left;
+ while(node->rb_right)
+ node = node->rb_right;
+ return node;
+ }
+
+ while (node->rb_parent && node == node->rb_parent->rb_left)
+ node = node->rb_parent;
+
+ return node->rb_parent;
+}
+EXPORT_SYMBOL(rb_prev);
===== include/linux/rbtree.h 1.1 vs edited =====
--- 1.1/include/linux/rbtree.h Tue Feb 5 20:18:53 2002
+++ edited/include/linux/rbtree.h Fri Aug 30 17:03:06 2002
@@ -120,6 +120,8 @@

extern void rb_insert_color(rb_node_t *, rb_root_t *);
extern void rb_erase(rb_node_t *, rb_root_t *);
+extern rb_node_t *rb_next(rb_node_t *);
+extern rb_node_t *rb_prev(rb_node_t *);

static inline void rb_link_node(rb_node_t * node, rb_node_t * parent, rb_node_t ** rb_link)
{
--
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/

\
 
 \ /
  Last update: 2005-03-22 13:28    [W:0.023 / U:4.516 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site