From a88cc108f6f39e56577793f66ac69eb0e18ae099 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Mon, 17 Mar 2014 12:21:54 +0000 Subject: 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 Cc: Michel Lespinasse Cc: Rik van Riel Cc: Peter Zijlstra Cc: Andrea Arcangeli Cc: David Woodhouse Cc: Andrew Morton Reviewed-by: Michel Lespinasse [Acked for inclusion via drm/i915 by Andrew Morton.] [danvet: switch to _GPL as per the mailing list discussion.] Signed-off-by: Daniel Vetter --- lib/interval_tree_test_main.c | 106 ------------------------------------------ 1 file changed, 106 deletions(-) delete mode 100644 lib/interval_tree_test_main.c (limited to 'lib/interval_tree_test_main.c') diff --git a/lib/interval_tree_test_main.c b/lib/interval_tree_test_main.c deleted file mode 100644 index 245900b98c8e..000000000000 --- a/lib/interval_tree_test_main.c +++ /dev/null @@ -1,106 +0,0 @@ -#include -#include -#include -#include - -#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"); -- cgit v1.2.3