summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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) {