Version:  2.0.40 2.2.26 2.4.37 3.13 3.14 3.15 3.16 3.17 3.18 3.19 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Linux/lib/interval_tree_test.c

  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 = 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 
 47 static 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 
 96 static void interval_tree_test_exit(void)
 97 {
 98         printk(KERN_ALERT "test exit\n");
 99 }
100 
101 module_init(interval_tree_test_init)
102 module_exit(interval_tree_test_exit)
103 
104 MODULE_LICENSE("GPL");
105 MODULE_AUTHOR("Michel Lespinasse");
106 MODULE_DESCRIPTION("Interval Tree test");
107 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us