From: Jérôme Glisse <[email protected]> It is often usefull to find the entry right before a given one in an rb interval tree.
Signed-off-by: Jérôme Glisse <[email protected]> --- include/linux/interval_tree_generic.h | 79 +++++++++++++++++++++++++++++++++++ 1 file changed, 79 insertions(+) diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h index 58370e1..97dd71b 100644 --- a/include/linux/interval_tree_generic.h +++ b/include/linux/interval_tree_generic.h @@ -188,4 +188,83 @@ ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ else if (start <= ITLAST(node)) /* Cond2 */ \ return node; \ } \ +} \ + \ +static ITSTRUCT * \ +ITPREFIX ## _subtree_rmost(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ +{ \ + while (true) { \ + /* \ + * Loop invariant: last >= ITSTART(node) \ + * (Cond1 is satisfied) \ + */ \ + if (node->ITRB.rb_right) { \ + ITSTRUCT *right = rb_entry(node->ITRB.rb_right, \ + ITSTRUCT, ITRB); \ + if (last >= ITSTART(right)) { \ + /* \ + * Some nodes in right subtree satisfy Cond1. \ + * Iterate to find the rightmost such node N. \ + * If it also satisfies Cond2, that's the \ + * match we are looking for. \ + */ \ + node = right; \ + continue; \ + } \ + /* Left branch might still have a candidate. */ \ + if (right->ITRB.rb_left) { \ + right = rb_entry(right->ITRB.rb_left, \ + ITSTRUCT, ITRB); \ + if (last >= ITSTART(right)) { \ + node = right; \ + continue; \ + } \ + } \ + } \ + /* At this point node is the rightmost candidate. */ \ + if (last >= ITSTART(node)) { /* Cond1 */ \ + if (start <= ITLAST(node)) /* Cond2 */ \ + return node; /* node is rightmost match */ \ + } \ + return NULL; /* No match */ \ + } \ +} \ + \ +ITSTATIC ITSTRUCT * \ +ITPREFIX ## _iter_prev(ITSTRUCT *node, ITTYPE start, ITTYPE last) \ +{ \ + struct rb_node *rb = node->ITRB.rb_left, *prev; \ + \ + while (true) { \ + /* \ + * Loop invariants: \ + * Cond2: start <= ITLAST(node) \ + * rb == node->ITRB.rb_left \ + * \ + * First, search left subtree if suitable \ + */ \ + if (rb) { \ + ITSTRUCT *left = rb_entry(rb, ITSTRUCT, ITRB); \ + if (start <= left->ITSUBTREE) \ + return ITPREFIX ## _subtree_rmost(left, \ + start, \ + last); \ + } \ + \ + /* Move up the tree until we come from a node's right child */\ + do { \ + rb = rb_parent(&node->ITRB); \ + if (!rb) \ + return NULL; \ + prev = &node->ITRB; \ + node = rb_entry(rb, ITSTRUCT, ITRB); \ + rb = node->ITRB.rb_left; \ + } while (prev == rb); \ + \ + /* Check if the node intersects [start;last] */ \ + if (start > ITLAST(node)) /* !Cond2 */ \ + return NULL; \ + else if (ITSTART(node) <= last) /* Cond1 */ \ + return node; \ + } \ } -- 1.9.0 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
