From: Jérôme Glisse <jglisse@xxxxxxxxxx>
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 <jglisse@xxxxxxxxxx>
---
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@xxxxxxxxx. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>