Eric Lee / smarc-fsl-linux-kernel

Blame view

lib/interval_tree_test.c 2.31 KB
edit raw normal view history
fff3fd8a1   Michel Lespinasse   rbtree: add prio ... 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
  #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++) {
496f2f93b   Akinobu Mita   random32: rename ... 
33
34
 
  		u32 a = prandom_u32_state(&rnd);
  		u32 b = prandom_u32_state(&rnd);
fff3fd8a1   Michel Lespinasse   rbtree: add prio ... 
35
36
37
38
39
40
41
42
43
 
  		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++)
496f2f93b   Akinobu Mita   random32: rename ... 
44
 
  		queries[i] = prandom_u32_state(&rnd);
fff3fd8a1   Michel Lespinasse   rbtree: add prio ... 
45
46
47
48
49
50
51
52
53
 
  }
  
  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");
496f2f93b   Akinobu Mita   random32: rename ... 
54
 
  	prandom_seed_state(&rnd, 3141592653589793238ULL);
fff3fd8a1   Michel Lespinasse   rbtree: add prio ... 
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
  	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
  ", (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)
  ",
  	       (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
  ");
  }
  
  module_init(interval_tree_test_init)
  module_exit(interval_tree_test_exit)
  
  MODULE_LICENSE("GPL");
  MODULE_AUTHOR("Michel Lespinasse");
  MODULE_DESCRIPTION("Interval Tree test");