12 static void trap(void)
18 static void validate_subtree(const struct quadtree *node)
25 printf("Attempted to validate a null pointer\n");
30 for (i = 0; i < 4; i++) {
34 if (node->child[i]->parent != node) {
35 printf("%s:%d Fatal! Tree inconsistency detected at "
36 "child %d %p in node %p, incorrent parent %p\n",
37 __func__, __LINE__, i, node->child[i], node,
38 node->child[i]->parent);
44 if (node->child[i] == node->parent) {
45 printf("%s:%d Fatal! Tree loop detected "
46 "at child %d in node %p\n",
47 __func__, __LINE__, i, node);
53 children += node->child[i]->children + 1;
55 validate_subtree(node->child[i]);
58 if (node->depth < 0) {
59 printf("%s:%d Tree statistics inconsistency detected! "
60 "Negative depth: %ld\n",
61 __func__, __LINE__, node->depth);
64 if (node->children != children) {
65 printf("%s:%d Tree statistics inconsistency detected! "
66 "child count mismatch. Expected %ld, got %ld\n",
67 __func__, __LINE__, children, node->children);
72 for (i = 0; i < 4 && node->children; i++) {
76 if (node->depth == node->child[i]->depth + 1)
79 if (node->child[i]->depth > node->depth) {
80 printf("%s:%d Tree statistics inconsistency detected! "
81 "child depth mismatch %ld > %ld\n",
82 __func__, __LINE__, node->child[i]->depth,
88 printf("%s:%d Tree statistics inconsistency detected! "
89 "child depth mismatch.",
96 static void validate_tree(const struct quadtree *node)
99 validate_subtree(quadtree_find_parent(node));
103 * quadtree_add - add a node to a quadtree
104 * @parent: parent node
105 * @new: the new node to be added
106 * @compare: pointer to a comparison function
108 * Add a node to a quadtree. The tree is kept in order, the new node
109 * is placed in the end of appropriate branch. The compare function is
110 * used to compare the new node against a branch in the tree. The
111 * comparison function must have following return value depending on
112 * the position of node a compared to the position of node b:
119 * The case of nodes sharing identical coordinates is not taken into
123 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
124 struct quadtree_ops *ops)
130 validate_tree(parent);
132 ret = ops->compare(parent, new);
134 if (ret < 0 || ret >= 4) {
135 printf("Invalid comparison result of %d\n", ret);
139 if (parent->child[ret])
140 return quadtree_add(parent->child[ret], new, ops);
142 parent->child[ret] = new;
143 new->parent = parent;
144 for (i = 0; i < 4; i++)
148 printf("adding node %p to parent %p\n", new, parent);
152 quadtree_recalculate_parent_stats(new, ops);
160 * _qt_optimal_del - Delete nodes from a detached subtree in optimal order
162 * All nodes are moved under the new parent node
164 static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
165 struct quadtree_ops *ops, int parents)
167 struct quadtree *child[4] = {0};
168 int i, children = 0, max_c, max_i;
170 for (i = 0; i < 4; i++) {
171 if (!node->child[i]) {
176 child[children] = node->child[i];
177 node->child[i] = NULL;
182 * Try to remove the nodes in such order that the node which
183 * has child number one quarter of the parent's child numer
184 * gets deleted first.
187 if (node->children <= parents / 4) {
189 printf("%d: Moving node %p away from parent %p\n",
190 __LINE__, node, parent);
193 validate_tree(parent);
194 quadtree_add(parent, node, ops);
202 for (i = 0; i < 4; i++) {
206 if (max_c < child[i]->children) {
207 max_c = child[i]->children;
212 _qt_optimal_del(parent, child[max_i], ops, parents / 4);
218 validate_tree(parent);
220 printf("%d: Moving node %p away from parent %p\n",
221 __LINE__, node, parent);
224 quadtree_add(parent, node, ops);
229 * quadtree_del - Detach a node from the tree
231 * Return value: The new root node of the tree. If we are detaching
232 * anything but the root node of the entire tree, the returned root
233 * value will be the original root of the tree.
235 struct quadtree *quadtree_del(struct quadtree *node,
236 struct quadtree_ops *ops)
238 struct quadtree *parent = 0;
242 printf("Deleting node %p under parent %p\n",
247 * We are deleting the root node. This means we have to select
248 * a new root node and reconstruct the entire tree under it
252 for (i = 0; i < 4; i++) {
257 parent = node->child[i];
261 _qt_optimal_del(parent, node->child[i], ops,
270 * We are not deleting the parent. Detach the node from the
271 * parent abd relocate the children. The node will be then
272 * detached from the tree.
275 for (i = 0; i < 4; i++) {
276 if (node->parent->child[i] == node) {
277 node->parent->child[i] = 0;
284 parent = node->parent;
287 * The sub branch is now detached from the main tree. Fix the
290 quadtree_recalculate_parent_stats(node->parent, ops);
292 parent = quadtree_find_parent(parent);
294 if (node->children) {
295 for (i = 0; i < 4; i++) {
299 _qt_optimal_del(parent, node->child[i], ops,
304 validate_tree(parent);
309 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
311 int direction, count = 0;
313 direction = it->direction(head, (struct quadtree_iterator *)it);
315 if ((direction & QUADTREE_UPLEFT) && head->child[0])
316 count += _walk_tree(head->child[0], it);
318 if ((direction & QUADTREE_UPRIGHT) && head->child[1])
319 count += _walk_tree(head->child[1], it);
321 if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
322 count += _walk_tree(head->child[2], it);
324 if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
325 count += _walk_tree(head->child[3], it);
327 if ((direction & QUADTREE_SELF) && it->callback) {
328 it->callback(head, (struct quadtree_iterator *)it);
335 int walk_quadtree(const struct quadtree_iterator *it)
337 return _walk_tree(it->head, it);