From 58a3e7f99534be1e5fcd501b138e0be8b274b326 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Sun, 25 Oct 2009 23:27:37 +0000
Subject: Benchmark dmnsn_kD_splay().

---
 bench/libdimension/kD_splay_tree.c | 45 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)

(limited to 'bench')

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) {
-- 
cgit v1.2.3