The patch titled
Subject: lib/interval_tree_test.c: allow full tree search
has been added to the -mm tree. Its filename is
lib-interval_tree_test-allow-full-tree-search.patch
This patch should soon appear at
http://ozlabs.org/~akpm/mmots/broken-out/lib-interval_tree_test-allow-full-tree-search.patch
and later at
http://ozlabs.org/~akpm/mmotm/broken-out/lib-interval_tree_test-allow-full-tree-search.patch
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/SubmitChecklist when testing your code ***
The -mm tree is included into linux-next and is updated
there every 3-4 working days
------------------------------------------------------
From: Davidlohr Bueso <dave@xxxxxxxxxxxx>
Subject: lib/interval_tree_test.c: allow full tree search
... such that a user can specify visiting all the nodes in the tree
(intersects with the world). This is a nice opposite from the very basic
default query which is a single point.
Link: http://lkml.kernel.org/r/20170518174936.20265-5-dave@xxxxxxxxxxxx
Signed-off-by: Davidlohr Bueso <dbueso@xxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/interval_tree_test.c | 15 ++++++++++-----
1 file changed, 10 insertions(+), 5 deletions(-)
diff -puN lib/interval_tree_test.c~lib-interval_tree_test-allow-full-tree-search lib/interval_tree_test.c
--- a/lib/interval_tree_test.c~lib-interval_tree_test-allow-full-tree-search
+++ a/lib/interval_tree_test.c
@@ -15,6 +15,7 @@ __param(int, perf_loops, 100000, "Number
__param(int, nsearches, 100, "Number of searches to the interval tree");
__param(int, search_loops, 10000, "Number of iterations searching the tree");
+__param(bool, search_all, false, "Searches will iterate all nodes in the tree");
__param(uint, max_endpoint, ~0, "Largest value for the interval's endpoint");
@@ -25,13 +26,13 @@ static u32 *queries = NULL;
static struct rnd_state rnd;
static inline unsigned long
-search(unsigned long query, struct rb_root *root)
+search(struct rb_root *root, unsigned long start, unsigned long last)
{
struct interval_tree_node *node;
unsigned long results = 0;
- for (node = interval_tree_iter_first(root, query, query); node;
- node = interval_tree_iter_next(node, query, query))
+ for (node = interval_tree_iter_first(root, start, last); node;
+ node = interval_tree_iter_next(node, start, last))
results++;
return results;
}
@@ -102,8 +103,12 @@ static int interval_tree_test_init(void)
results = 0;
for (i = 0; i < search_loops; i++)
- for (j = 0; j < nsearches; j++)
- results += search(queries[j], &root);
+ for (j = 0; j < nsearches; j++) {
+ unsigned long start = search_all ? 0 : queries[j];
+ unsigned long last = search_all ? max_endpoint : queries[j];
+
+ results += search(&root, start, last);
+ }
time2 = get_cycles();
time = time2 - time1;
_
Patches currently in -mm which might be from dave@xxxxxxxxxxxx are
lib-interval_tree_test-allow-the-module-to-be-compiled-in.patch
lib-interval_tree_test-make-test-options-module-parameters.patch
lib-interval_tree_test-allow-users-to-limit-scope-of-endpoint.patch
lib-interval_tree_test-allow-full-tree-search.patch
--
To unsubscribe from this list: send the line "unsubscribe mm-commits" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
