| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Fri, 2 May 2014 09:52:03 -0400
From: j.glisse@...il.com
To: linux-mm@...ck.org, linux-kernel@...r.kernel.org,
linux-fsdevel@...r.kernel.org
Cc: Jérôme Glisse <jglisse@...hat.com>
Subject: [PATCH 04/11] interval_tree: helper to find previous item of a node in rb interval tree
From: Jérôme Glisse <jglisse@...hat.com>
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@...hat.com>
---
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@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists