summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-08-01 13:05:02 -0600
committerTavian Barnes <tavianator@gmail.com>2010-08-01 13:05:02 -0600
commit52148d309a9588f5c3a14695133d6a6182c1b8d0 (patch)
tree0fe229d90c2f64234ac2c3eaaf4b56a86af9f22b
parentfb9dcc629630fe77840574088412eeb12b8d7ddb (diff)
downloaddimension-52148d309a9588f5c3a14695133d6a6182c1b8d0.tar.xz
Fix PR-tree implementation.
Grab priority leaves all at once instead of round-robin.
-rw-r--r--bench/libdimension/prtree.c2
-rw-r--r--libdimension/prtree.c27
2 files changed, 15 insertions, 14 deletions
diff --git a/bench/libdimension/prtree.c b/bench/libdimension/prtree.c
index 0df0509..c67d3e7 100644
--- a/bench/libdimension/prtree.c
+++ b/bench/libdimension/prtree.c
@@ -66,7 +66,7 @@ dmnsn_new_fake_object(void)
int
main(void)
{
- const size_t nobjects = 128;
+ const size_t nobjects = 10000;
sandglass_t sandglass;
if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) {
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index 69a70a4..a7a2c26 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -23,6 +23,7 @@
/* Number of children per node */
#define DMNSN_PRTREE_B 6
+#define DMNSN_PSEUDO_PRTREE_B 6
struct dmnsn_prtree_node {
dmnsn_bounding_box bounding_box;
@@ -43,7 +44,7 @@ typedef struct dmnsn_pseudo_prtree dmnsn_pseudo_prtree;
typedef struct dmnsn_pseudo_prnode {
dmnsn_pseudo_prtree *left, *right;
- dmnsn_pseudo_prleaf children[6];
+ dmnsn_pseudo_prleaf children[DMNSN_PSEUDO_PRTREE_B];
} dmnsn_pseudo_prnode;
struct dmnsn_pseudo_prtree {
@@ -291,30 +292,30 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator)
} else {
/* Make an internal node */
pseudo->is_leaf = false;
- for (size_t i = 0; i < 6; ++i) {
+ for (size_t i = 0; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
pseudo->pseudo.node.children[i].is_leaf = are_objects;
pseudo->pseudo.node.children[i].bounding_box = dmnsn_zero_bounding_box();
}
/* Fill the priority leaves */
size_t i, j;
- for (i = 0; i < DMNSN_PRTREE_B; ++i) {
- for (j = 0; j < 6; ++j) {
- dmnsn_list_iterator *k = dmnsn_priority_search(leaves, are_objects, j);
+ for (i = 0; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
+ for (j = 0; j < DMNSN_PRTREE_B; ++j) {
+ dmnsn_list_iterator *k = dmnsn_priority_search(leaves, are_objects, i);
if (!k)
break;
if (are_objects) {
dmnsn_object *object;
dmnsn_list_get(k, &object);
- pseudo->pseudo.node.children[j].children[i] = object;
- dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[j],
+ pseudo->pseudo.node.children[i].children[j] = object;
+ dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[i],
object->bounding_box);
} else {
dmnsn_prtree_node *prnode;
dmnsn_list_get(k, &prnode);
- pseudo->pseudo.node.children[j].children[i] = prnode;
- dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[j],
+ pseudo->pseudo.node.children[i].children[j] = prnode;
+ dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[i],
prnode->bounding_box);
}
@@ -326,9 +327,9 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator)
}
/* Set remaining space in the priority leaves to NULL */
- for (; i < DMNSN_PRTREE_B; ++i) {
- for (; j < 6; ++j) {
- pseudo->pseudo.node.children[j].children[i] = NULL;
+ for (; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
+ for (; j < DMNSN_PRTREE_B; ++j) {
+ pseudo->pseudo.node.children[i].children[j] = NULL;
}
j = 0;
}
@@ -405,7 +406,7 @@ dmnsn_pseudo_prtree_leaves_recursive(const dmnsn_pseudo_prtree *node,
if (node->is_leaf) {
dmnsn_pseudo_prtree_add_leaf(&node->pseudo.leaf, leaves);
} else {
- for (size_t i = 0; i < 6; ++i) {
+ for (size_t i = 0; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
dmnsn_pseudo_prtree_add_leaf(&node->pseudo.node.children[i], leaves);
}
dmnsn_pseudo_prtree_leaves_recursive(node->pseudo.node.left, leaves);