Commit | Line | Data |
---|---|---|
fff3fd8a ML |
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 | ||
11 | static struct rb_root root = RB_ROOT; | |
12 | static struct interval_tree_node nodes[NODES]; | |
13 | static u32 queries[SEARCHES]; | |
14 | ||
15 | static struct rnd_state rnd; | |
16 | ||
17 | static inline unsigned long | |
18 | search(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 | ||
29 | static void init(void) | |
30 | { | |
31 | int i; | |
32 | for (i = 0; i < NODES; i++) { | |
33 | u32 a = prandom32(&rnd), b = prandom32(&rnd); | |
34 | if (a <= b) { | |
35 | nodes[i].start = a; | |
36 | nodes[i].last = b; | |
37 | } else { | |
38 | nodes[i].start = b; | |
39 | nodes[i].last = a; | |
40 | } | |
41 | } | |
42 | for (i = 0; i < SEARCHES; i++) | |
43 | queries[i] = prandom32(&rnd); | |
44 | } | |
45 | ||
46 | static int interval_tree_test_init(void) | |
47 | { | |
48 | int i, j; | |
49 | unsigned long results; | |
50 | cycles_t time1, time2, time; | |
51 | ||
52 | printk(KERN_ALERT "interval tree insert/remove"); | |
53 | ||
54 | prandom32_seed(&rnd, 3141592653589793238ULL); | |
55 | init(); | |
56 | ||
57 | time1 = get_cycles(); | |
58 | ||
59 | for (i = 0; i < PERF_LOOPS; i++) { | |
60 | for (j = 0; j < NODES; j++) | |
61 | interval_tree_insert(nodes + j, &root); | |
62 | for (j = 0; j < NODES; j++) | |
63 | interval_tree_remove(nodes + j, &root); | |
64 | } | |
65 | ||
66 | time2 = get_cycles(); | |
67 | time = time2 - time1; | |
68 | ||
69 | time = div_u64(time, PERF_LOOPS); | |
70 | printk(" -> %llu cycles\n", (unsigned long long)time); | |
71 | ||
72 | printk(KERN_ALERT "interval tree search"); | |
73 | ||
74 | for (j = 0; j < NODES; j++) | |
75 | interval_tree_insert(nodes + j, &root); | |
76 | ||
77 | time1 = get_cycles(); | |
78 | ||
79 | results = 0; | |
80 | for (i = 0; i < SEARCH_LOOPS; i++) | |
81 | for (j = 0; j < SEARCHES; j++) | |
82 | results += search(queries[j], &root); | |
83 | ||
84 | time2 = get_cycles(); | |
85 | time = time2 - time1; | |
86 | ||
87 | time = div_u64(time, SEARCH_LOOPS); | |
88 | results = div_u64(results, SEARCH_LOOPS); | |
89 | printk(" -> %llu cycles (%lu results)\n", | |
90 | (unsigned long long)time, results); | |
91 | ||
92 | return -EAGAIN; /* Fail will directly unload the module */ | |
93 | } | |
94 | ||
95 | static void interval_tree_test_exit(void) | |
96 | { | |
97 | printk(KERN_ALERT "test exit\n"); | |
98 | } | |
99 | ||
100 | module_init(interval_tree_test_init) | |
101 | module_exit(interval_tree_test_exit) | |
102 | ||
103 | MODULE_LICENSE("GPL"); | |
104 | MODULE_AUTHOR("Michel Lespinasse"); | |
105 | MODULE_DESCRIPTION("Interval Tree test"); |