summaryrefslogtreecommitdiff
path: root/lib/interval_tree_test.c
diff options
context:
space:
mode:
authorChris Wilson <chris@chris-wilson.co.uk>2014-03-17 16:21:54 +0400
committerDaniel Vetter <daniel.vetter@ffwll.ch>2014-05-05 11:09:14 +0400
commita88cc108f6f39e56577793f66ac69eb0e18ae099 (patch)
treeea07f899e8d482e15654d06d7df9aae857166dda /lib/interval_tree_test.c
parent8d4eee9cd7a170342dc6fbc2ee19ae77031a8cd5 (diff)
downloadlinux-a88cc108f6f39e56577793f66ac69eb0e18ae099.tar.xz
lib: Export interval_tree
lib/interval_tree.c provides a simple interface for an interval-tree (an augmented red-black tree) but is only built when testing the generic macros for building interval-trees. For drivers with modest needs, export the simple interval-tree library as is. v2: Lots of help from Michel Lespinasse to only compile the code as required: - make INTERVAL_TREE a config option - make INTERVAL_TREE_TEST select the library functions and sanitize the filenames & Makefile - prepare interval_tree for being built as a module if required Signed-off-by: Chris Wilson <chris@chris-wilson.co.uk> Cc: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Cc: Andrew Morton <akpm@linux-foundation.org> Reviewed-by: Michel Lespinasse <walken@google.com> [Acked for inclusion via drm/i915 by Andrew Morton.] [danvet: switch to _GPL as per the mailing list discussion.] Signed-off-by: Daniel Vetter <daniel.vetter@ffwll.ch>
Diffstat (limited to 'lib/interval_tree_test.c')
-rw-r--r--lib/interval_tree_test.c106
1 files changed, 106 insertions, 0 deletions
diff --git a/lib/interval_tree_test.c b/lib/interval_tree_test.c
new file mode 100644
index 000000000000..245900b98c8e
--- /dev/null
+++ b/lib/interval_tree_test.c
@@ -0,0 +1,106 @@
+#include <linux/module.h>
+#include <linux/interval_tree.h>
+#include <linux/random.h>
+#include <asm/timex.h>
+
+#define NODES 100
+#define PERF_LOOPS 100000
+#define SEARCHES 100
+#define SEARCH_LOOPS 10000
+
+static struct rb_root root = RB_ROOT;
+static struct interval_tree_node nodes[NODES];
+static u32 queries[SEARCHES];
+
+static struct rnd_state rnd;
+
+static inline unsigned long
+search(unsigned long query, struct rb_root *root)
+{
+ 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))
+ results++;
+ return results;
+}
+
+static void init(void)
+{
+ int i;
+ for (i = 0; i < NODES; i++) {
+ u32 a = prandom_u32_state(&rnd);
+ u32 b = prandom_u32_state(&rnd);
+ if (a <= b) {
+ nodes[i].start = a;
+ nodes[i].last = b;
+ } else {
+ nodes[i].start = b;
+ nodes[i].last = a;
+ }
+ }
+ for (i = 0; i < SEARCHES; i++)
+ queries[i] = prandom_u32_state(&rnd);
+}
+
+static int interval_tree_test_init(void)
+{
+ int i, j;
+ unsigned long results;
+ cycles_t time1, time2, time;
+
+ printk(KERN_ALERT "interval tree insert/remove");
+
+ prandom_seed_state(&rnd, 3141592653589793238ULL);
+ init();
+
+ time1 = get_cycles();
+
+ for (i = 0; i < PERF_LOOPS; i++) {
+ for (j = 0; j < NODES; j++)
+ interval_tree_insert(nodes + j, &root);
+ for (j = 0; j < NODES; j++)
+ interval_tree_remove(nodes + j, &root);
+ }
+
+ time2 = get_cycles();
+ time = time2 - time1;
+
+ time = div_u64(time, PERF_LOOPS);
+ printk(" -> %llu cycles\n", (unsigned long long)time);
+
+ printk(KERN_ALERT "interval tree search");
+
+ for (j = 0; j < NODES; j++)
+ interval_tree_insert(nodes + j, &root);
+
+ time1 = get_cycles();
+
+ results = 0;
+ for (i = 0; i < SEARCH_LOOPS; i++)
+ for (j = 0; j < SEARCHES; j++)
+ results += search(queries[j], &root);
+
+ time2 = get_cycles();
+ time = time2 - time1;
+
+ time = div_u64(time, SEARCH_LOOPS);
+ results = div_u64(results, SEARCH_LOOPS);
+ printk(" -> %llu cycles (%lu results)\n",
+ (unsigned long long)time, results);
+
+ return -EAGAIN; /* Fail will directly unload the module */
+}
+
+static void interval_tree_test_exit(void)
+{
+ printk(KERN_ALERT "test exit\n");
+}
+
+module_init(interval_tree_test_init)
+module_exit(interval_tree_test_exit)
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Michel Lespinasse");
+MODULE_DESCRIPTION("Interval Tree test");