diff options
| author | Davidlohr Bueso <dave@stgolabs.net> | 2017-07-11 01:51:52 +0300 |
|---|---|---|
| committer | Greg Kroah-Hartman <gregkh@linuxfoundation.org> | 2018-12-21 16:08:47 +0300 |
| commit | 042a1f48116fdc4d67210beca37cdba313a2dda1 (patch) | |
| tree | 7692a24acd62f183db892cfd22b4e1f98e211928 | |
| parent | cf283dbec32fdb55e6f32e8861aaaa76e3f4e326 (diff) | |
| download | linux-042a1f48116fdc4d67210beca37cdba313a2dda1.tar.xz | |
lib/interval_tree_test.c: allow full tree search
[ Upstream commit c46ecce431ebe6b1a9551d1f530eb432dae5c39b ]
... 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@stgolabs.net
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Sasha Levin <sashal@kernel.org>
| -rw-r--r-- | lib/interval_tree_test.c | 15 |
1 files changed, 10 insertions, 5 deletions
diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c index 1093f0496d5e..409383463879 100644 --- a/lib/interval_tree_test.c +++ b/lib/interval_tree_test.c @@ -15,6 +15,7 @@ __param(int, perf_loops, 100000, "Number of iterations modifying the tree"); __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"); static struct rb_root root = RB_ROOT; @@ -24,13 +25,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; } @@ -99,8 +100,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; |