Back to home page

LXR

 
 

    


0001 #include <linux/module.h>
0002 #include <linux/interval_tree.h>
0003 #include <linux/random.h>
0004 #include <asm/timex.h>
0005 
0006 #define NODES        100
0007 #define PERF_LOOPS   100000
0008 #define SEARCHES     100
0009 #define SEARCH_LOOPS 10000
0010 
0011 static struct rb_root root = RB_ROOT;
0012 static struct interval_tree_node nodes[NODES];
0013 static u32 queries[SEARCHES];
0014 
0015 static struct rnd_state rnd;
0016 
0017 static inline unsigned long
0018 search(unsigned long query, struct rb_root *root)
0019 {
0020     struct interval_tree_node *node;
0021     unsigned long results = 0;
0022 
0023     for (node = interval_tree_iter_first(root, query, query); node;
0024          node = interval_tree_iter_next(node, query, query))
0025         results++;
0026     return results;
0027 }
0028 
0029 static void init(void)
0030 {
0031     int i;
0032     for (i = 0; i < NODES; i++) {
0033         u32 a = prandom_u32_state(&rnd);
0034         u32 b = prandom_u32_state(&rnd);
0035         if (a <= b) {
0036             nodes[i].start = a;
0037             nodes[i].last = b;
0038         } else {
0039             nodes[i].start = b;
0040             nodes[i].last = a;
0041         }
0042     }
0043     for (i = 0; i < SEARCHES; i++)
0044         queries[i] = prandom_u32_state(&rnd);
0045 }
0046 
0047 static int interval_tree_test_init(void)
0048 {
0049     int i, j;
0050     unsigned long results;
0051     cycles_t time1, time2, time;
0052 
0053     printk(KERN_ALERT "interval tree insert/remove");
0054 
0055     prandom_seed_state(&rnd, 3141592653589793238ULL);
0056     init();
0057 
0058     time1 = get_cycles();
0059 
0060     for (i = 0; i < PERF_LOOPS; i++) {
0061         for (j = 0; j < NODES; j++)
0062             interval_tree_insert(nodes + j, &root);
0063         for (j = 0; j < NODES; j++)
0064             interval_tree_remove(nodes + j, &root);
0065     }
0066 
0067     time2 = get_cycles();
0068     time = time2 - time1;
0069 
0070     time = div_u64(time, PERF_LOOPS);
0071     printk(" -> %llu cycles\n", (unsigned long long)time);
0072 
0073     printk(KERN_ALERT "interval tree search");
0074 
0075     for (j = 0; j < NODES; j++)
0076         interval_tree_insert(nodes + j, &root);
0077 
0078     time1 = get_cycles();
0079 
0080     results = 0;
0081     for (i = 0; i < SEARCH_LOOPS; i++)
0082         for (j = 0; j < SEARCHES; j++)
0083             results += search(queries[j], &root);
0084 
0085     time2 = get_cycles();
0086     time = time2 - time1;
0087 
0088     time = div_u64(time, SEARCH_LOOPS);
0089     results = div_u64(results, SEARCH_LOOPS);
0090     printk(" -> %llu cycles (%lu results)\n",
0091            (unsigned long long)time, results);
0092 
0093     return -EAGAIN; /* Fail will directly unload the module */
0094 }
0095 
0096 static void interval_tree_test_exit(void)
0097 {
0098     printk(KERN_ALERT "test exit\n");
0099 }
0100 
0101 module_init(interval_tree_test_init)
0102 module_exit(interval_tree_test_exit)
0103 
0104 MODULE_LICENSE("GPL");
0105 MODULE_AUTHOR("Michel Lespinasse");
0106 MODULE_DESCRIPTION("Interval Tree test");