From 23092e17ca23f5bc4a214062c6583c911e24f1e9 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Mon, 9 May 2011 11:46:30 -0600
Subject: Make dmnsn_new_prtree() more scalable.
---
libdimension/prtree.c | 595 +++++++++++++++++++-------------------------------
1 file changed, 223 insertions(+), 372 deletions(-)
(limited to 'libdimension')
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index 9a329ce..2738d40 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -30,8 +30,8 @@
/** Number of children per PR-node. */
#define DMNSN_PRTREE_B 8
-/** Number of children per pseudo-PR-node (must be 2*ndimensions). */
-#define DMNSN_PSEUDO_PRTREE_B 6
+/** Number of priority leaves per pseudo-PR-node (must be 2*ndimensions). */
+#define DMNSN_PSEUDO_B 6
/** A flat node for storing in an array for fast pre-order traversal. */
typedef struct dmnsn_flat_prnode {
@@ -40,45 +40,55 @@ typedef struct dmnsn_flat_prnode {
size_t skip;
} dmnsn_flat_prnode;
+/** The side of the split that a node ended up on. */
+typedef enum dmnsn_prnode_location {
+ DMNSN_PRTREE_LEAF, /**< Priority leaf. */
+ DMNSN_PRTREE_LEFT, /**< Left child. */
+ DMNSN_PRTREE_RIGHT /**< Right child. */
+} dmnsn_prnode_location;
+
/** Pseudo PR-tree node. */
-typedef struct dmnsn_prtree_node {
+typedef struct dmnsn_prnode {
dmnsn_bounding_box bounding_box;
- /* Children (objects or subtrees) */
- bool is_leaf;
- void *children[DMNSN_PRTREE_B];
-} dmnsn_prtree_node;
+ dmnsn_object *object;
+ struct dmnsn_prnode *children[DMNSN_PRTREE_B];
-/** Pseudo PR-tree leaf node. */
-typedef struct dmnsn_pseudo_prleaf {
- void *children[DMNSN_PRTREE_B];
- bool is_leaf;
- dmnsn_bounding_box bounding_box;
-} dmnsn_pseudo_prleaf;
-
-typedef struct dmnsn_pseudo_prtree dmnsn_pseudo_prtree;
-
-/** Pseudo PR-tree internal node. */
-typedef struct dmnsn_pseudo_prnode {
- dmnsn_pseudo_prtree *left, *right;
- dmnsn_pseudo_prleaf children[DMNSN_PSEUDO_PRTREE_B];
-} dmnsn_pseudo_prnode;
-
-/** Pseudo PR-tree. */
-struct dmnsn_pseudo_prtree {
- bool is_leaf;
- union {
- dmnsn_pseudo_prleaf leaf;
- dmnsn_pseudo_prnode node;
- } pseudo;
-};
+ dmnsn_prnode_location location;
+} dmnsn_prnode;
+
+/** Construct an empty PR-node. */
+static inline dmnsn_prnode *
+dmnsn_new_prnode()
+{
+ dmnsn_prnode *node = dmnsn_malloc(sizeof(dmnsn_prnode));
+ node->bounding_box = dmnsn_zero_bounding_box();
+ node->object = NULL;
+ node->location = DMNSN_PRTREE_LEFT; /* Mustn't be _LEAF */
+ for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
+ node->children[i] = NULL;
+ }
+ return node;
+}
+
+/** Free a non-flat PR-tree. */
+static void
+dmnsn_delete_prnode(dmnsn_prnode *node)
+{
+ if (node) {
+ for (size_t i = 0; i < DMNSN_PRTREE_B && node->children[i]; ++i) {
+ dmnsn_delete_prnode(node->children[i]);
+ }
+ dmnsn_free(node);
+ }
+}
/** Expand a node to contain the bounding box \p box. */
static void
-dmnsn_pseudo_prleaf_swallow(dmnsn_pseudo_prleaf *leaf, dmnsn_bounding_box box)
+dmnsn_prnode_swallow(dmnsn_prnode *node, dmnsn_bounding_box box)
{
- leaf->bounding_box.min = dmnsn_vector_min(leaf->bounding_box.min, box.min);
- leaf->bounding_box.max = dmnsn_vector_max(leaf->bounding_box.max, box.max);
+ node->bounding_box.min = dmnsn_vector_min(node->bounding_box.min, box.min);
+ node->bounding_box.max = dmnsn_vector_max(node->bounding_box.max, box.max);
}
/** Comparator types. */
@@ -93,379 +103,259 @@ enum {
/** Get a coordinate of the bounding box of a node. */
static inline double
-dmnsn_priority_get(const dmnsn_list_iterator *i, bool is_object, int comparator)
+dmnsn_get_coordinate(const dmnsn_list_iterator *i, int comparator)
{
- dmnsn_bounding_box box;
-
- if (is_object) {
- dmnsn_object **object = dmnsn_list_at(i);
- box = (*object)->bounding_box;
- } else {
- dmnsn_prtree_node **prnode = dmnsn_list_at(i);
- box = (*prnode)->bounding_box;
- }
+ dmnsn_prnode **node = dmnsn_list_at(i);
switch (comparator) {
case DMNSN_XMIN:
- return box.min.x;
+ return (*node)->bounding_box.min.x;
case DMNSN_YMIN:
- return box.min.y;
+ return (*node)->bounding_box.min.y;
case DMNSN_ZMIN:
- return box.min.z;
+ return (*node)->bounding_box.min.z;
case DMNSN_XMAX:
- return -box.max.x;
+ return -(*node)->bounding_box.max.x;
case DMNSN_YMAX:
- return -box.max.y;
+ return -(*node)->bounding_box.max.y;
case DMNSN_ZMAX:
- return -box.max.z;
+ return -(*node)->bounding_box.max.z;
default:
dmnsn_assert(false, "Invalid comparator.");
- return 0.0;
+ return 0.0; /* Shut up compiler */
}
}
/* List sorting comparators */
static bool
-dmnsn_xmin_object_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
-{
- double lval = dmnsn_priority_get(l, true, DMNSN_XMIN);
- double rval = dmnsn_priority_get(r, true, DMNSN_XMIN);
- return lval < rval;
-}
-
-static bool
-dmnsn_xmin_prnode_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
-{
- double lval = dmnsn_priority_get(l, false, DMNSN_XMIN);
- double rval = dmnsn_priority_get(r, false, DMNSN_XMIN);
- return lval < rval;
-}
-
-static bool
-dmnsn_ymin_object_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
+dmnsn_xmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
{
- double lval = dmnsn_priority_get(l, true, DMNSN_YMIN);
- double rval = dmnsn_priority_get(r, true, DMNSN_YMIN);
+ double lval = dmnsn_get_coordinate(l, DMNSN_XMIN);
+ double rval = dmnsn_get_coordinate(r, DMNSN_XMIN);
return lval < rval;
}
static bool
-dmnsn_ymin_prnode_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
+dmnsn_ymin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
{
- double lval = dmnsn_priority_get(l, false, DMNSN_YMIN);
- double rval = dmnsn_priority_get(r, false, DMNSN_YMIN);
+ double lval = dmnsn_get_coordinate(l, DMNSN_YMIN);
+ double rval = dmnsn_get_coordinate(r, DMNSN_YMIN);
return lval < rval;
}
static bool
-dmnsn_zmin_object_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
+dmnsn_zmin_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
{
- double lval = dmnsn_priority_get(l, true, DMNSN_ZMIN);
- double rval = dmnsn_priority_get(r, true, DMNSN_ZMIN);
+ double lval = dmnsn_get_coordinate(l, DMNSN_ZMIN);
+ double rval = dmnsn_get_coordinate(r, DMNSN_ZMIN);
return lval < rval;
}
static bool
-dmnsn_zmin_prnode_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
+dmnsn_xmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
{
- double lval = dmnsn_priority_get(l, false, DMNSN_ZMIN);
- double rval = dmnsn_priority_get(r, false, DMNSN_ZMIN);
+ double lval = dmnsn_get_coordinate(l, DMNSN_XMAX);
+ double rval = dmnsn_get_coordinate(r, DMNSN_XMAX);
return lval < rval;
}
static bool
-dmnsn_xmax_object_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
+dmnsn_ymax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
{
- double lval = dmnsn_priority_get(l, true, DMNSN_XMAX);
- double rval = dmnsn_priority_get(r, true, DMNSN_XMAX);
+ double lval = dmnsn_get_coordinate(l, DMNSN_YMAX);
+ double rval = dmnsn_get_coordinate(r, DMNSN_YMAX);
return lval < rval;
}
static bool
-dmnsn_xmax_prnode_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
+dmnsn_zmax_comp(const dmnsn_list_iterator *l, const dmnsn_list_iterator *r)
{
- double lval = dmnsn_priority_get(l, false, DMNSN_XMAX);
- double rval = dmnsn_priority_get(r, false, DMNSN_XMAX);
+ double lval = dmnsn_get_coordinate(l, DMNSN_ZMAX);
+ double rval = dmnsn_get_coordinate(r, DMNSN_ZMAX);
return lval < rval;
}
-static bool
-dmnsn_ymax_object_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
-{
- double lval = dmnsn_priority_get(l, true, DMNSN_YMAX);
- double rval = dmnsn_priority_get(r, true, DMNSN_YMAX);
- return lval < rval;
-}
-
-static bool
-dmnsn_ymax_prnode_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
-{
- double lval = dmnsn_priority_get(l, false, DMNSN_YMAX);
- double rval = dmnsn_priority_get(r, false, DMNSN_YMAX);
- return lval < rval;
-}
-
-static bool
-dmnsn_zmax_object_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
-{
- double lval = dmnsn_priority_get(l, true, DMNSN_ZMAX);
- double rval = dmnsn_priority_get(r, true, DMNSN_ZMAX);
- return lval < rval;
-}
-
-static bool
-dmnsn_zmax_prnode_comp(const dmnsn_list_iterator *l,
- const dmnsn_list_iterator *r)
-{
- double lval = dmnsn_priority_get(l, false, DMNSN_ZMAX);
- double rval = dmnsn_priority_get(r, false, DMNSN_ZMAX);
- return lval < rval;
-}
-
-/** Leaf node comparators. */
-static dmnsn_list_comparator_fn *dmnsn_object_comparators[6] = {
- [DMNSN_XMIN] = dmnsn_xmin_object_comp,
- [DMNSN_YMIN] = dmnsn_ymin_object_comp,
- [DMNSN_ZMIN] = dmnsn_zmin_object_comp,
- [DMNSN_XMAX] = dmnsn_xmax_object_comp,
- [DMNSN_YMAX] = dmnsn_ymax_object_comp,
- [DMNSN_ZMAX] = dmnsn_zmax_object_comp
-};
-
-/** Internal node comparators. */
-static dmnsn_list_comparator_fn *dmnsn_prnode_comparators[6] = {
- [DMNSN_XMIN] = dmnsn_xmin_prnode_comp,
- [DMNSN_YMIN] = dmnsn_ymin_prnode_comp,
- [DMNSN_ZMIN] = dmnsn_zmin_prnode_comp,
- [DMNSN_XMAX] = dmnsn_xmax_prnode_comp,
- [DMNSN_YMAX] = dmnsn_ymax_prnode_comp,
- [DMNSN_ZMAX] = dmnsn_zmax_prnode_comp
+/** All comparators. */
+static dmnsn_list_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
+ [DMNSN_XMIN] = dmnsn_xmin_comp,
+ [DMNSN_YMIN] = dmnsn_ymin_comp,
+ [DMNSN_ZMIN] = dmnsn_zmin_comp,
+ [DMNSN_XMAX] = dmnsn_xmax_comp,
+ [DMNSN_YMAX] = dmnsn_ymax_comp,
+ [DMNSN_ZMAX] = dmnsn_zmax_comp
};
-/** Select an extreme node based on a comparator. */
-static dmnsn_list_iterator *
-dmnsn_priority_search(dmnsn_list *leaves, bool are_objects, int comparator)
-{
- dmnsn_list_iterator *i = dmnsn_list_first(leaves);
- if (i) {
- double candidate = dmnsn_priority_get(i, are_objects, comparator);
-
- for (dmnsn_list_iterator *j = dmnsn_list_next(i);
- j != NULL;
- j = dmnsn_list_next(j))
- {
- double new_candidate = dmnsn_priority_get(j, are_objects, comparator);
- if (new_candidate < candidate) {
- candidate = new_candidate;
- i = j;
+/** Add the priority leaves for this level. */
+static void
+dmnsn_add_priority_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
+ dmnsn_list *new_leaves, int comparator)
+{
+ for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+ dmnsn_prnode *leaf = dmnsn_new_prnode();
+ size_t count = 0;
+ dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
+ while (count < DMNSN_PRTREE_B && j) {
+ /* Skip all the previously found extreme nodes */
+ dmnsn_prnode **node;
+ do {
+ node = dmnsn_list_at(j);
+ j = dmnsn_list_next(j);
+ } while ((*node)->location == DMNSN_PRTREE_LEAF && j);
+
+ if ((*node)->location != DMNSN_PRTREE_LEAF) {
+ (*node)->location = DMNSN_PRTREE_LEAF;
+ leaf->children[count++] = *node;
+ dmnsn_prnode_swallow(leaf, (*node)->bounding_box);
}
}
- }
- return i;
-}
-
-/** Build a pseudo PR-tree. */
-static dmnsn_pseudo_prtree *
-dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator)
-{
- dmnsn_pseudo_prtree *pseudo = dmnsn_malloc(sizeof(dmnsn_pseudo_prtree));
-
- if (dmnsn_list_size(leaves) <= DMNSN_PRTREE_B) {
- /* Make a leaf */
- pseudo->is_leaf = true;
- pseudo->pseudo.leaf.bounding_box = dmnsn_zero_bounding_box();
-
- size_t i;
- dmnsn_list_iterator *ii;
- if (are_objects) {
- pseudo->pseudo.leaf.is_leaf = true;
- for (i = 0, ii = dmnsn_list_first(leaves);
- ii != NULL;
- ++i, ii = dmnsn_list_next(ii))
- {
- dmnsn_object *object;
- dmnsn_list_get(ii, &object);
-
- pseudo->pseudo.leaf.children[i] = object;
- dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.leaf, object->bounding_box);
- }
+ if (count > 0) {
+ dmnsn_list_push(new_leaves, &leaf);
} else {
- pseudo->pseudo.leaf.is_leaf = false;
- for (i = 0, ii = dmnsn_list_first(leaves);
- ii != NULL;
- ++i, ii = dmnsn_list_next(ii))
- {
- dmnsn_prtree_node *prnode;
- dmnsn_list_get(ii, &prnode);
-
- pseudo->pseudo.leaf.children[i] = prnode;
- dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.leaf, prnode->bounding_box);
- }
+ dmnsn_delete_prnode(leaf);
+ return;
}
+ }
+}
- for (; i < DMNSN_PRTREE_B; ++i) {
- pseudo->pseudo.leaf.children[i] = NULL;
- }
- } else {
- /* Make an internal node */
- pseudo->is_leaf = false;
- 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();
+/** Split the sorted lists into the left and right subtrees. */
+static bool
+dmnsn_split_sorted_leaves(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
+ dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B],
+ size_t i)
+{
+ /* Get rid of the extreme nodes */
+ dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
+ while (j) {
+ dmnsn_list_iterator *next = dmnsn_list_next(j);
+ dmnsn_prnode **node = dmnsn_list_at(j);
+ if ((*node)->location == DMNSN_PRTREE_LEAF) {
+ dmnsn_list_remove(sorted_leaves[i], j);
}
+ j = next;
+ }
- /* Fill the priority leaves */
- size_t i, 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[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[i].children[j] = prnode;
- dmnsn_pseudo_prleaf_swallow(&pseudo->pseudo.node.children[i],
- prnode->bounding_box);
- }
-
- dmnsn_list_remove(leaves, k);
- }
+ if (dmnsn_list_size(sorted_leaves[i]) == 0) {
+ return false;
+ }
- if (dmnsn_list_size(leaves) == 0)
- break;
- }
+ /* Split the appropriate list and mark the left and right child nodes */
+ right_sorted_leaves[i] = dmnsn_list_split(sorted_leaves[i]);
+ for (dmnsn_list_iterator *j = dmnsn_list_first(sorted_leaves[i]);
+ j != NULL;
+ j = dmnsn_list_next(j))
+ {
+ dmnsn_prnode **node = dmnsn_list_at(j);
+ (*node)->location = DMNSN_PRTREE_LEFT;
+ }
+ for (dmnsn_list_iterator *j = dmnsn_list_first(right_sorted_leaves[i]);
+ j != NULL;
+ j = dmnsn_list_next(j))
+ {
+ dmnsn_prnode **node = dmnsn_list_at(j);
+ (*node)->location = DMNSN_PRTREE_RIGHT;
+ }
- /* Set remaining space in the priority leaves to NULL */
- for (; i < DMNSN_PSEUDO_PRTREE_B; ++i) {
- for (; j < DMNSN_PRTREE_B; ++j) {
- pseudo->pseudo.node.children[i].children[j] = NULL;
+ /* Split the rest of the lists */
+ for (size_t j = 0; j < DMNSN_PSEUDO_B; ++j) {
+ if (j != i) {
+ right_sorted_leaves[j] = dmnsn_new_list(sizeof(dmnsn_prnode *));
+
+ dmnsn_list_iterator *k = dmnsn_list_first(sorted_leaves[j]);
+ while (k) {
+ dmnsn_list_iterator *next = dmnsn_list_next(k);
+ dmnsn_prnode **node = dmnsn_list_at(k);
+ if ((*node)->location == DMNSN_PRTREE_LEAF) {
+ dmnsn_list_remove(sorted_leaves[j], k);
+ } else if ((*node)->location == DMNSN_PRTREE_RIGHT) {
+ dmnsn_list_iterator_remove(sorted_leaves[j], k);
+ dmnsn_list_iterator_insert(right_sorted_leaves[j], NULL, k);
+ }
+ k = next;
}
- j = 0;
}
-
- /* Recursively build the subtrees */
- if (are_objects)
- dmnsn_list_sort(leaves, dmnsn_object_comparators[comparator]);
- else
- dmnsn_list_sort(leaves, dmnsn_prnode_comparators[comparator]);
-
- dmnsn_list *half = dmnsn_list_split(leaves);
- pseudo->pseudo.node.left
- = dmnsn_new_pseudo_prtree(leaves, are_objects, (comparator + 1)%6);
- pseudo->pseudo.node.right
- = dmnsn_new_pseudo_prtree(half, are_objects, (comparator + 1)%6);
- dmnsn_delete_list(half);
}
- return pseudo;
+ return true;
}
-/** Delete a pseudo-PR-tree. */
+/** Recursively constructs an implicit pseudo-PR-tree and collects the priority
+ leaves. */
static void
-dmnsn_delete_pseudo_prtree(dmnsn_pseudo_prtree *pseudo)
+dmnsn_priority_leaves_recursive(dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B],
+ dmnsn_list *new_leaves,
+ int comparator)
{
- if (pseudo) {
- if (!pseudo->is_leaf) {
- dmnsn_delete_pseudo_prtree(pseudo->pseudo.node.left);
- dmnsn_delete_pseudo_prtree(pseudo->pseudo.node.right);
+ dmnsn_add_priority_leaves(sorted_leaves, new_leaves, comparator);
+
+ dmnsn_list *right_sorted_leaves[DMNSN_PSEUDO_B];
+ if (dmnsn_split_sorted_leaves(sorted_leaves, right_sorted_leaves, comparator))
+ {
+ dmnsn_priority_leaves_recursive(right_sorted_leaves, new_leaves,
+ (comparator + 1)%DMNSN_PSEUDO_B);
+ for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+ dmnsn_delete_list(right_sorted_leaves[i]);
}
- dmnsn_free(pseudo);
+
+ dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves,
+ (comparator + 1)%DMNSN_PSEUDO_B);
}
}
-/** Construct a node from a pseudo leaf. */
-static dmnsn_prtree_node *
-dmnsn_new_prtree_node(const dmnsn_pseudo_prleaf *leaf)
+/** Constructs an implicit pseudo-PR-tree and returns the priority leaves. */
+static dmnsn_list *
+dmnsn_priority_leaves(const dmnsn_list *leaves)
{
- dmnsn_prtree_node *node = dmnsn_malloc(sizeof(dmnsn_prtree_node));
- node->is_leaf = leaf->is_leaf;
- node->bounding_box = leaf->bounding_box;
-
- for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
- node->children[i] = leaf->children[i];
+ dmnsn_list *sorted_leaves[DMNSN_PSEUDO_B];
+ for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+ sorted_leaves[i] = dmnsn_copy_list(leaves);
+ dmnsn_list_sort(sorted_leaves[i], dmnsn_comparators[i]);
}
- return node;
-}
+ dmnsn_list *new_leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
+ dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves, 0);
-/** Free a PR-tree node. */
-static void
-dmnsn_delete_prtree_node(dmnsn_prtree_node *node)
-{
- if (node) {
- if (!node->is_leaf) {
- for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
- dmnsn_delete_prtree_node(node->children[i]);
- }
- }
- dmnsn_free(node);
+ for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
+ dmnsn_delete_list(sorted_leaves[i]);
}
-}
-/** Add a pseudo leaf to a list of leaves. */
-static void
-dmnsn_pseudo_prtree_add_leaf(const dmnsn_pseudo_prleaf *leaf,
- dmnsn_list *leaves)
-{
- /* Don't add empty leaves */
- if (leaf->children[0]) {
- dmnsn_prtree_node *prnode = dmnsn_new_prtree_node(leaf);
- dmnsn_list_push(leaves, &prnode);
- }
+ return new_leaves;
}
-/** Recursively extract the leaves of a pseudo-PR-tree. */
-static void
-dmnsn_pseudo_prtree_leaves_recursive(const dmnsn_pseudo_prtree *node,
- dmnsn_list *leaves)
+/** Construct a non-flat PR-tree. */
+static dmnsn_prnode *
+dmnsn_make_prtree(const dmnsn_list *objects)
{
- if (node->is_leaf) {
- dmnsn_pseudo_prtree_add_leaf(&node->pseudo.leaf, leaves);
- } else {
- 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);
- dmnsn_pseudo_prtree_leaves_recursive(node->pseudo.node.right, leaves);
+ if (dmnsn_list_size(objects) == 0) {
+ return NULL;
}
-}
-/** Extract the leaves of a pseudo PR-tree. */
-static dmnsn_list *
-dmnsn_pseudo_prtree_leaves(const dmnsn_pseudo_prtree *pseudo)
-{
- dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prtree_node *));
- dmnsn_pseudo_prtree_leaves_recursive(pseudo, leaves);
+ /* Make the initial list of leaves */
+ dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prnode *));
+ for (dmnsn_list_iterator *i = dmnsn_list_first(objects);
+ i != NULL;
+ i = dmnsn_list_next(i))
+ {
+ dmnsn_object **object = dmnsn_list_at(i);
+ dmnsn_prnode *node = dmnsn_new_prnode();
+ node->bounding_box = (*object)->bounding_box;
+ node->object = *object;
+ dmnsn_list_push(leaves, &node);
+ }
- if (dmnsn_list_size(leaves) == 0) {
- dmnsn_prtree_node *prnode = dmnsn_new_prtree_node(&pseudo->pseudo.leaf);
- dmnsn_list_push(leaves, &prnode);
+ while (dmnsn_list_size(leaves) > 1) {
+ dmnsn_list *new_leaves = dmnsn_priority_leaves(leaves);
+ dmnsn_delete_list(leaves);
+ leaves = new_leaves;
}
- return leaves;
+ dmnsn_prnode **leaf = dmnsn_list_at(dmnsn_list_first(leaves));
+ dmnsn_prnode *root = *leaf;
+ dmnsn_delete_list(leaves);
+ return root;
}
/** Add an object or its children, if any, to a list. */
@@ -500,10 +390,9 @@ dmnsn_split_unbounded(dmnsn_list *objects)
dmnsn_list_iterator *i = dmnsn_list_first(objects);
while (i) {
- dmnsn_object *object;
- dmnsn_list_get(i, &object);
+ dmnsn_object **object = dmnsn_list_at(i);
- if (dmnsn_bounding_box_is_infinite(object->bounding_box)) {
+ if (dmnsn_bounding_box_is_infinite((*object)->bounding_box)) {
dmnsn_list_iterator *next = dmnsn_list_next(i);
dmnsn_list_iterator_remove(objects, i);
dmnsn_list_iterator_insert(unbounded, NULL, i);
@@ -516,59 +405,19 @@ dmnsn_split_unbounded(dmnsn_list *objects)
return unbounded;
}
-/* Construct a non-flat PR-tree */
-static dmnsn_prtree_node *
-dmnsn_make_prtree(dmnsn_list *leaves)
-{
- dmnsn_prtree_node *root = NULL;
-
- if (dmnsn_list_size(leaves) > 0) {
- dmnsn_pseudo_prtree *pseudo = dmnsn_new_pseudo_prtree(leaves, true, 0);
- dmnsn_delete_list(leaves);
- leaves = dmnsn_pseudo_prtree_leaves(pseudo);
- dmnsn_delete_pseudo_prtree(pseudo);
-
- while (dmnsn_list_size(leaves) > 1) {
- pseudo = dmnsn_new_pseudo_prtree(leaves, false, 0);
- dmnsn_delete_list(leaves);
- leaves = dmnsn_pseudo_prtree_leaves(pseudo);
- dmnsn_delete_pseudo_prtree(pseudo);
- }
-
- dmnsn_list_get(dmnsn_list_first(leaves), &root);
- }
-
- dmnsn_delete_list(leaves);
- return root;
-}
-
/** Recursively flatten a PR-tree into an array of flat nodes. */
static void
-dmnsn_flatten_prtree_recursive(dmnsn_prtree_node *node, dmnsn_array *flat)
+dmnsn_flatten_prtree_recursive(dmnsn_prnode *node, dmnsn_array *flat)
{
size_t currenti = dmnsn_array_size(flat);
dmnsn_array_resize(flat, currenti + 1);
dmnsn_flat_prnode *flatnode = dmnsn_array_at(flat, currenti);
flatnode->bounding_box = node->bounding_box;
- flatnode->object = NULL;
-
- for (size_t i = 0; i < DMNSN_PRTREE_B; ++i) {
- if (!node->children[i])
- break;
-
- if (node->is_leaf) {
- dmnsn_object *object = node->children[i];
+ flatnode->object = node->object;
- dmnsn_array_resize(flat, dmnsn_array_size(flat) + 1);
- dmnsn_flat_prnode *objnode = dmnsn_array_last(flat);
-
- objnode->bounding_box = object->bounding_box;
- objnode->object = object;
- objnode->skip = 1;
- } else {
- dmnsn_flatten_prtree_recursive(node->children[i], flat);
- }
+ for (size_t i = 0; i < DMNSN_PRTREE_B && node->children[i]; ++i) {
+ dmnsn_flatten_prtree_recursive(node->children[i], flat);
}
/* Array could have been realloc()'d somewhere else above */
@@ -578,7 +427,7 @@ dmnsn_flatten_prtree_recursive(dmnsn_prtree_node *node, dmnsn_array *flat)
/** Flatten a PR-tree into an array of flat nodes. */
static dmnsn_array *
-dmnsn_flatten_prtree(dmnsn_prtree_node *root)
+dmnsn_flatten_prtree(dmnsn_prnode *root)
{
dmnsn_array *flat = dmnsn_new_array(sizeof(dmnsn_flat_prnode));
if (root) {
@@ -596,15 +445,17 @@ dmnsn_new_prtree(const dmnsn_array *objects)
{
dmnsn_prtree *prtree = dmnsn_malloc(sizeof(dmnsn_prtree));
- dmnsn_list *leaves = dmnsn_object_list(objects);
- dmnsn_list *unbounded = dmnsn_split_unbounded(leaves);
+ dmnsn_list *object_list = dmnsn_object_list(objects);
+ dmnsn_list *unbounded = dmnsn_split_unbounded(object_list);
prtree->unbounded = dmnsn_array_from_list(unbounded);
- dmnsn_prtree_node *root = dmnsn_make_prtree(leaves);
+
+ dmnsn_prnode *root = dmnsn_make_prtree(object_list);
prtree->bounded = dmnsn_flatten_prtree(root);
- dmnsn_delete_prtree_node(root);
+ dmnsn_delete_prnode(root);
dmnsn_delete_list(unbounded);
+ dmnsn_delete_list(object_list);
if (dmnsn_array_size(prtree->unbounded) > 0) {
prtree->bounding_box = dmnsn_infinite_bounding_box();
--
cgit v1.2.3