[PATCH 04/11] interval_tree: helper to find previous item of a node in rb interval tree

[j . glisse]

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 from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/