diff options
| author | Davidlohr Bueso <dave@stgolabs.net> | 2017-09-09 02:14:49 +0300 |
|---|---|---|
| committer | Linus Torvalds <torvalds@linux-foundation.org> | 2017-09-09 04:26:48 +0300 |
| commit | 977bd8d5e1e61dc877c468e8937a4ab3094e53eb (patch) | |
| tree | 686fec5f47d38fe03b729934ae02f282bf1a556b /lib | |
| parent | 223f8911eace60c787f8767c25148b80ece9732a (diff) | |
| download | linux-977bd8d5e1e61dc877c468e8937a4ab3094e53eb.tar.xz | |
lib/rbtree_test.c: add (inorder) traversal test
This adds a second test for regular rb-tree testing in that there is no
need to repeat it for the augmented flavor.
Link: http://lkml.kernel.org/r/20170719014603.19029-6-dave@stgolabs.net
Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/rbtree_test.c | 25 |
1 files changed, 23 insertions, 2 deletions
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c index e83331aa1b7f..967999ff46db 100644 --- a/lib/rbtree_test.c +++ b/lib/rbtree_test.c @@ -183,6 +183,7 @@ static int __init rbtree_test_init(void) { int i, j; cycles_t time1, time2, time; + struct rb_node *node; nodes = kmalloc(nnodes * sizeof(*nodes), GFP_KERNEL); if (!nodes) @@ -206,8 +207,28 @@ static int __init rbtree_test_init(void) time = time2 - time1; time = div_u64(time, perf_loops); - printk(" -> %llu cycles\n", (unsigned long long)time); + printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time); + for (i = 0; i < nnodes; i++) + insert(nodes + i, &root); + + time1 = get_cycles(); + + for (i = 0; i < perf_loops; i++) { + for (node = rb_first(&root); node; node = rb_next(node)) + ; + } + + time2 = get_cycles(); + time = time2 - time1; + + time = div_u64(time, perf_loops); + printk(" -> test 2 (latency of inorder traversal): %llu cycles\n", (unsigned long long)time); + + for (i = 0; i < nnodes; i++) + erase(nodes + i, &root); + + /* run checks */ for (i = 0; i < check_loops; i++) { init(); for (j = 0; j < nnodes; j++) { @@ -238,7 +259,7 @@ static int __init rbtree_test_init(void) time = time2 - time1; time = div_u64(time, perf_loops); - printk(" -> %llu cycles\n", (unsigned long long)time); + printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n", (unsigned long long)time); for (i = 0; i < check_loops; i++) { init(); |