Messages in this thread Patch in this message |  | | From | David Woodhouse <> | Subject | [PATCH] rb_prev and rb_next. | Date | Fri, 30 Aug 2002 17:19:19 +0100 |
| |
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/
|  |