1#include <linux/module.h>
  2#include <linux/interval_tree.h>
  3#include <linux/random.h>
  4#include <asm/timex.h>
  5
  6#define NODES        100
  7#define PERF_LOOPS   100000
  8#define SEARCHES     100
  9#define SEARCH_LOOPS 10000
 10
 11static struct rb_root root = RB_ROOT;
 12static struct interval_tree_node nodes[NODES];
 13static u32 queries[SEARCHES];
 14
 15static struct rnd_state rnd;
 16
 17static inline unsigned long
 18search(unsigned long query, struct rb_root *root)
 19{
 20	struct interval_tree_node *node;
 21	unsigned long results = 0;
 22
 23	for (node = interval_tree_iter_first(root, query, query); node;
 24	     node = interval_tree_iter_next(node, query, query))
 25		results++;
 26	return results;
 27}
 28
 29static void init(void)
 30{
 31	int i;
 32	for (i = 0; i < NODES; i++) {
 33		u32 a = prandom_u32_state(&rnd);
 34		u32 b = prandom_u32_state(&rnd);
 35		if (a <= b) {
 36			nodes[i].start = a;
 37			nodes[i].last = b;
 38		} else {
 39			nodes[i].start = b;
 40			nodes[i].last = a;
 41		}
 42	}
 43	for (i = 0; i < SEARCHES; i++)
 44		queries[i] = prandom_u32_state(&rnd);
 45}
 46
 47static int interval_tree_test_init(void)
 48{
 49	int i, j;
 50	unsigned long results;
 51	cycles_t time1, time2, time;
 52
 53	printk(KERN_ALERT "interval tree insert/remove");
 54
 55	prandom_seed_state(&rnd, 3141592653589793238ULL);
 56	init();
 57
 58	time1 = get_cycles();
 59
 60	for (i = 0; i < PERF_LOOPS; i++) {
 61		for (j = 0; j < NODES; j++)
 62			interval_tree_insert(nodes + j, &root);
 63		for (j = 0; j < NODES; j++)
 64			interval_tree_remove(nodes + j, &root);
 65	}
 66
 67	time2 = get_cycles();
 68	time = time2 - time1;
 69
 70	time = div_u64(time, PERF_LOOPS);
 71	printk(" -> %llu cycles\n", (unsigned long long)time);
 72
 73	printk(KERN_ALERT "interval tree search");
 74
 75	for (j = 0; j < NODES; j++)
 76		interval_tree_insert(nodes + j, &root);
 77
 78	time1 = get_cycles();
 79
 80	results = 0;
 81	for (i = 0; i < SEARCH_LOOPS; i++)
 82		for (j = 0; j < SEARCHES; j++)
 83			results += search(queries[j], &root);
 84
 85	time2 = get_cycles();
 86	time = time2 - time1;
 87
 88	time = div_u64(time, SEARCH_LOOPS);
 89	results = div_u64(results, SEARCH_LOOPS);
 90	printk(" -> %llu cycles (%lu results)\n",
 91	       (unsigned long long)time, results);
 92
 93	return -EAGAIN; /* Fail will directly unload the module */
 94}
 95
 96static void interval_tree_test_exit(void)
 97{
 98	printk(KERN_ALERT "test exit\n");
 99}
100
101module_init(interval_tree_test_init)
102module_exit(interval_tree_test_exit)
103
104MODULE_LICENSE("GPL");
105MODULE_AUTHOR("Michel Lespinasse");
106MODULE_DESCRIPTION("Interval Tree test");