summaryrefslogtreecommitdiffstats
path: root/lib/interval_tree.c
diff options
context:
space:
mode:
authorMichel Lespinasse <walken@google.com>2012-10-08 16:31:25 -0700
committerLinus Torvalds <torvalds@linux-foundation.org>2012-10-09 16:22:39 +0900
commit6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08 (patch)
tree422ed8d7ac2fe45069f20cfba84a9a097bf444af /lib/interval_tree.c
parentfff3fd8a1210a165252cd7cd01206da7a90d3a06 (diff)
downloadlinux-6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08.tar.gz
linux-6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08.tar.bz2
linux-6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08.zip
mm: replace vma prio_tree with an interval tree
Implement an interval tree as a replacement for the VMA prio_tree. The algorithms are similar to lib/interval_tree.c; however that code can't be directly reused as the interval endpoints are not explicitly stored in the VMA. So instead, the common algorithm is moved into a template and the details (node type, how to get interval endpoints from the node, etc) are filled in using the C preprocessor. Once the interval tree functions are available, using them as a replacement to the VMA prio tree is a relatively simple, mechanical job. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/interval_tree.c')
-rw-r--r--lib/interval_tree.c166
1 files changed, 10 insertions, 156 deletions
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
index 6fd540b1e499..77a793e0644b 100644
--- a/lib/interval_tree.c
+++ b/lib/interval_tree.c
@@ -1,159 +1,13 @@
#include <linux/init.h>
#include <linux/interval_tree.h>
-/* Callbacks for augmented rbtree insert and remove */
-
-static inline unsigned long
-compute_subtree_last(struct interval_tree_node *node)
-{
- unsigned long max = node->last, subtree_last;
- if (node->rb.rb_left) {
- subtree_last = rb_entry(node->rb.rb_left,
- struct interval_tree_node, rb)->__subtree_last;
- if (max < subtree_last)
- max = subtree_last;
- }
- if (node->rb.rb_right) {
- subtree_last = rb_entry(node->rb.rb_right,
- struct interval_tree_node, rb)->__subtree_last;
- if (max < subtree_last)
- max = subtree_last;
- }
- return max;
-}
-
-RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb,
- unsigned long, __subtree_last, compute_subtree_last)
-
-/* Insert / remove interval nodes from the tree */
-
-void interval_tree_insert(struct interval_tree_node *node,
- struct rb_root *root)
-{
- struct rb_node **link = &root->rb_node, *rb_parent = NULL;
- unsigned long start = node->start, last = node->last;
- struct interval_tree_node *parent;
-
- while (*link) {
- rb_parent = *link;
- parent = rb_entry(rb_parent, struct interval_tree_node, rb);
- if (parent->__subtree_last < last)
- parent->__subtree_last = last;
- if (start < parent->start)
- link = &parent->rb.rb_left;
- else
- link = &parent->rb.rb_right;
- }
-
- node->__subtree_last = last;
- rb_link_node(&node->rb, rb_parent, link);
- rb_insert_augmented(&node->rb, root, &augment_callbacks);
-}
-
-void interval_tree_remove(struct interval_tree_node *node,
- struct rb_root *root)
-{
- rb_erase_augmented(&node->rb, root, &augment_callbacks);
-}
-
-/*
- * Iterate over intervals intersecting [start;last]
- *
- * Note that a node's interval intersects [start;last] iff:
- * Cond1: node->start <= last
- * and
- * Cond2: start <= node->last
- */
-
-static struct interval_tree_node *
-subtree_search(struct interval_tree_node *node,
- unsigned long start, unsigned long last)
-{
- while (true) {
- /*
- * Loop invariant: start <= node->__subtree_last
- * (Cond2 is satisfied by one of the subtree nodes)
- */
- if (node->rb.rb_left) {
- struct interval_tree_node *left =
- rb_entry(node->rb.rb_left,
- struct interval_tree_node, rb);
- if (start <= left->__subtree_last) {
- /*
- * Some nodes in left subtree satisfy Cond2.
- * Iterate to find the leftmost such node N.
- * If it also satisfies Cond1, that's the match
- * we are looking for. Otherwise, there is no
- * matching interval as nodes to the right of N
- * can't satisfy Cond1 either.
- */
- node = left;
- continue;
- }
- }
- if (node->start <= last) { /* Cond1 */
- if (start <= node->last) /* Cond2 */
- return node; /* node is leftmost match */
- if (node->rb.rb_right) {
- node = rb_entry(node->rb.rb_right,
- struct interval_tree_node, rb);
- if (start <= node->__subtree_last)
- continue;
- }
- }
- return NULL; /* No match */
- }
-}
-
-struct interval_tree_node *
-interval_tree_iter_first(struct rb_root *root,
- unsigned long start, unsigned long last)
-{
- struct interval_tree_node *node;
-
- if (!root->rb_node)
- return NULL;
- node = rb_entry(root->rb_node, struct interval_tree_node, rb);
- if (node->__subtree_last < start)
- return NULL;
- return subtree_search(node, start, last);
-}
-
-struct interval_tree_node *
-interval_tree_iter_next(struct interval_tree_node *node,
- unsigned long start, unsigned long last)
-{
- struct rb_node *rb = node->rb.rb_right, *prev;
-
- while (true) {
- /*
- * Loop invariants:
- * Cond1: node->start <= last
- * rb == node->rb.rb_right
- *
- * First, search right subtree if suitable
- */
- if (rb) {
- struct interval_tree_node *right =
- rb_entry(rb, struct interval_tree_node, rb);
- if (start <= right->__subtree_last)
- return subtree_search(right, start, last);
- }
-
- /* Move up the tree until we come from a node's left child */
- do {
- rb = rb_parent(&node->rb);
- if (!rb)
- return NULL;
- prev = &node->rb;
- node = rb_entry(rb, struct interval_tree_node, rb);
- rb = node->rb.rb_right;
- } while (prev == rb);
-
- /* Check if the node intersects [start;last] */
- if (last < node->start) /* !Cond1 */
- return NULL;
- else if (start <= node->last) /* Cond2 */
- return node;
- }
-}
+#define ITSTRUCT struct interval_tree_node
+#define ITRB rb
+#define ITTYPE unsigned long
+#define ITSUBTREE __subtree_last
+#define ITSTART(n) ((n)->start)
+#define ITLAST(n) ((n)->last)
+#define ITSTATIC
+#define ITPREFIX interval_tree
+
+#include <linux/interval_tree_tmpl.h>