summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2009-10-25 23:27:37 +0000
committerTavian Barnes <tavianator@gmail.com>2009-10-25 23:27:37 +0000
commit58a3e7f99534be1e5fcd501b138e0be8b274b326 (patch)
tree69e03805be0946a4035958125a148a52bc97742f
parent1742345f241268e493dcbfe4b54e62c77ccbfadc (diff)
downloaddimension-58a3e7f99534be1e5fcd501b138e0be8b274b326.tar.xz
Benchmark dmnsn_kD_splay().
-rw-r--r--bench/libdimension/kD_splay_tree.c45
1 files changed, 45 insertions, 0 deletions
diff --git a/bench/libdimension/kD_splay_tree.c b/bench/libdimension/kD_splay_tree.c
index 63edb0f..ee8e975 100644
--- a/bench/libdimension/kD_splay_tree.c
+++ b/bench/libdimension/kD_splay_tree.c
@@ -43,10 +43,45 @@ dmnsn_random_vector(dmnsn_vector min)
return ret;
}
+dmnsn_kD_splay_node *
+dmnsn_kD_splay_deepest_recursive(dmnsn_kD_splay_node *node,
+ unsigned int depth, unsigned int *deepest)
+{
+ dmnsn_kD_splay_node *left = NULL, *right = NULL;
+ unsigned int left_depth = 0, right_depth = 0;
+ if (node->contains) {
+ left = dmnsn_kD_splay_deepest_recursive(node->contains,
+ depth + 1, &left_depth);
+ }
+ if (node->container) {
+ right = dmnsn_kD_splay_deepest_recursive(node->container,
+ depth + 1, &right_depth);
+ }
+
+ if (right && right_depth > left_depth) {
+ *deepest = right_depth;
+ return right;
+ } else if (left) {
+ *deepest = left_depth;
+ return left;
+ } else {
+ *deepest = depth;
+ return node;
+ }
+}
+
+dmnsn_kD_splay_node *
+dmnsn_kD_splay_deepest(dmnsn_kD_splay_tree *tree)
+{
+ unsigned int deepest = 0;
+ return dmnsn_kD_splay_deepest_recursive(tree->root, 0, &deepest);
+}
+
int
main()
{
dmnsn_kD_splay_tree *tree;
+ dmnsn_kD_splay_node *node;
dmnsn_intersection *intersection;
dmnsn_line ray;
const unsigned int nobjects = 128;
@@ -101,6 +136,16 @@ main()
dmnsn_delete_intersection(intersection);
printf("dmnsn_kD_splay_search(): %ld\n", sandglass.grains);
+ /* dmnsn_kD_splay() */
+ grains = 0;
+ for (i = 0; i < nobjects; ++i) {
+ node = dmnsn_kD_splay_deepest(tree);
+ sandglass_bench_noprecache(&sandglass, dmnsn_kD_splay(tree, node));
+ sandglass.grains += grains;
+ grains = sandglass.grains;
+ }
+ printf("dmnsn_kD_splay(): %ld\n", sandglass.grains/nobjects);
+
/* Cleanup */
dmnsn_delete_kD_splay_tree(tree);
for (i = 0; i < nobjects; ++i) {