12 static void trap(void )
18 static void validate_subtree(const struct quadtree *node)
24 for (i = 0; i < 4; i++) {
28 if (node->child[i]->parent != node) {
29 printf("%s:%d Fatal! Tree inconsistency detected "
30 "at child %d in node %p\n",
31 __func__, __LINE__, i, node);
36 if (node->child[i] == node->parent) {
37 printf("%s:%d Fatal! Tree loop detected "
38 "at child %d in node %p\n",
39 __func__, __LINE__, i, node);
44 children += node->child[i]->children + 1;
46 validate_subtree(node->child[i]);
49 if (node->depth < 0) {
50 printf("%s:%d Tree statistics inconsistency detected! "
51 "Negative depth: %ld\n",
52 __func__, __LINE__, node->depth);
55 if (node->children != children) {
56 printf("%s:%d Tree statistics inconsistency detected! "
57 "child count mismatch. Expected %ld, got %ld\n",
58 __func__, __LINE__, children, node->children);
62 for (i = 0; i < 4 && node->children; i++) {
66 if (node->depth == node->child[i]->depth + 1)
69 if (node->child[i]->depth > node->depth) {
70 printf("%s:%d Tree statistics inconsistency detected! "
71 "child depth mismatch %ld > %ld\n",
72 __func__, __LINE__, node->child[i]->depth,
78 printf("%s:%d Tree statistics inconsistency detected! "
79 "child depth mismatch.",
85 static void validate_tree(const struct quadtree *node)
88 validate_subtree(quadtree_find_parent(node));
92 * quadtree_add - add a node to a quadtree
93 * @parent: parent node
94 * @new: the new node to be added
95 * @compare: pointer to a comparison function
97 * Add a node to a quadtree. The tree is kept in order, the new node
98 * is placed in the end of appropriate branch. The compare function is
99 * used to compare the new node against a branch in the tree. The
100 * comparison function must have following return value depending on
101 * the position of node a compared to the position of node b:
108 * The case of nodes sharing identical coordinates is not taken into
112 struct quadtree *quadtree_add(struct quadtree *parent,
113 struct quadtree *new,
114 int (*compare)(struct quadtree *a,
121 validate_tree(parent);
123 ret = compare(parent, new);
125 if (ret < 0 || ret >= 4) {
126 printf("Invalid comparison result of %d\n", ret);
130 if (parent->child[ret])
131 return quadtree_add(parent->child[ret], new, compare);
133 parent->child[ret] = new;
134 new->parent = parent;
136 quadtree_recalculate_parent_stats(parent);
144 * _quadtree_reposition_reqursively - Move everything under and
145 * including a given node under the new root node
149 _quadtree_reposition_reqursively(struct quadtree *root,
150 struct quadtree *node,
151 int (*compare)(struct quadtree *a,
158 /* First remove all children, if any */
160 for (i = 0; i < 4; i++) {
164 if (node->child[i] == node ||
165 node->child[i] == node->parent)
168 _quadtree_reposition_reqursively(root, node->child[i], compare);
172 /* There are no children left, reset stats */
176 /* Then remove this node under the new root. */
177 quadtree_add(root, node, compare);
181 * quadtree_del - Detach a node from the tree
183 * Return value: The new root node of the tree. If we are detaching
184 * anything but the root node of the entire tree, the returned root
185 * value will be the original root of the tree.
187 struct quadtree *quadtree_del(struct quadtree *node,
188 int (*compare)(struct quadtree *a,
191 struct quadtree *parent = 0;
195 * We are deleting the root node. This means we have to select
196 * a new root node and reconstruct the entire tree under it
200 for (i = 0; i < 4; i++) {
205 parent = node->child[i];
208 _quadtree_reposition_reqursively(parent,
218 * We are not deleting the parent. Detach the node from the
219 * parent abd relocate the children. The node will be then
220 * detached from the tree.
223 for (i = 0; i < 4; i++) {
224 if (node->parent->child[i] == node) {
225 node->parent->child[i] = 0;
230 printf("%s:%d Fatal! Tree inconsistency detected\n",
235 /* Fix parent stats */
236 quadtree_recalculate_parent_stats(node->parent);
239 * The sub branch is now detached from the main tree. Continue
240 * relocating the detached branch.
243 for (i = 0; i < 4; i++) {
247 _quadtree_reposition_reqursively(node->parent, node->child[i],
252 parent = quadtree_find_parent(node);
258 validate_tree(parent);
263 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
265 int direction, count = 0;
267 direction = it->direction(head, (struct quadtree_iterator *)it);
269 if ((direction & QUADTREE_UPLEFT) && head->child[0])
270 count += _walk_tree(head->child[0], it);
272 if ((direction & QUADTREE_UPRIGHT) && head->child[1])
273 count += _walk_tree(head->child[1], it);
275 if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
276 count += _walk_tree(head->child[2], it);
278 if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
279 count += _walk_tree(head->child[3], it);
281 if ((direction & QUADTREE_SELF) && it->callback) {
282 it->callback(head, (struct quadtree_iterator *)it);
289 int walk_quadtree(const struct quadtree_iterator *it)
291 return _walk_tree(it->head, it);