12 static void trap(void )
18 static void validate_subtree(const struct quadtree *node)
22 for (i = 0; i < 4; i++) {
26 if (node->child[i]->parent != node) {
27 printf("%s:%d Fatal! Tree inconsistency detected "
28 "at child %d in node %p\n",
29 __FUNCTION__, __LINE__, i, node);
33 if (node->child[i] == node->parent) {
34 printf("%s:%d Fatal! Tree loop detected "
35 "at child %d in node %p\n",
36 __FUNCTION__, __LINE__, i, node);
41 validate_subtree(node->child[i]);
45 static void validate_tree(const struct quadtree *node)
48 validate_subtree(quadtree_find_parent(node));
52 * quadtree_add - add a node to a quadtree
53 * @parent: parent node
54 * @new: the new node to be added
55 * @compare: pointer to a comparison function
57 * Add a node to a quadtree. The tree is kept in order, the new node
58 * is placed in the end of appropriate branch. The compare function is
59 * used to compare the new node against a branch in the tree. The
60 * comparison function must have following return value depending on
61 * the position of node a compared to the position of node b:
68 * The case of nodes sharing identical coordinates is not taken into
72 struct quadtree *quadtree_add(struct quadtree *parent,
74 int (*compare)(struct quadtree *a,
81 validate_tree(parent);
83 ret = compare(parent, new);
85 if (ret < 0 || ret >= 4) {
86 printf("Invalid comparison result of %d\n", ret);
90 if (parent->child[ret])
91 return quadtree_add(parent->child[ret], new, compare);
93 parent->child[ret] = new;
102 * _quadtree_reposition_reqursively - Move everything under and
103 * including a given node under the new root node
107 _quadtree_reposition_reqursively(struct quadtree *root,
108 struct quadtree *node,
109 int (*compare)(struct quadtree *a,
116 /* First remove all children, if any */
118 for (i = 0; i < 4; i++) {
122 if (node->child[i] == node ||
123 node->child[i] == node->parent)
126 _quadtree_reposition_reqursively(root, node->child[i], compare);
130 /* Then remove this node under the new root. */
131 quadtree_add(root, node, compare);
135 * quadtree_del - Detach a node from the tree
137 * Return value: The new root node of the tree. If we are detaching
138 * anything but the root node of the entire tree, the returned root
139 * value will be the original root of the tree.
141 struct quadtree *quadtree_del(struct quadtree *node,
142 int (*compare)(struct quadtree *a,
145 struct quadtree *parent = 0;
149 * We are deleting the root node. This means we have to select
150 * a new root node and reconstruct the entire tree under it
154 for (i = 0; i < 4; i++) {
159 parent = node->child[i];
162 _quadtree_reposition_reqursively(parent,
172 * We are not deleting the parent. Detach the node from the
173 * parent abd relocate the children. The node will be then
174 * detached from the tree.
177 for (i = 0; i < 4; i++) {
178 if (node->parent->child[i] == node) {
179 node->parent->child[i] = 0;
184 printf("%s:%d Fatal! Tree inconsistency detected\n",
185 __FUNCTION__, __LINE__);
190 * The sub branch is now detached from the main tree. Continue
191 * relocating the detached branch.
194 for (i = 0; i < 4; i++) {
198 _quadtree_reposition_reqursively(node->parent, node->child[i],
203 parent = quadtree_find_parent(node);
206 validate_tree(parent);
211 static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
213 int direction, count = 0;
215 direction = it->direction(head, (struct quadtree_iterator *)it);
217 if ((direction & QUADTREE_UPLEFT) && head->child[0])
218 count += _walk_tree(head->child[0], it);
220 if ((direction & QUADTREE_UPRIGHT) && head->child[1])
221 count += _walk_tree(head->child[1], it);
223 if ((direction & QUADTREE_DOWNLEFT) && head->child[2])
224 count += _walk_tree(head->child[2], it);
226 if ((direction & QUADTREE_DOWNRIGHT) && head->child[3])
227 count += _walk_tree(head->child[3], it);
229 if ((direction & QUADTREE_SELF) && it->callback) {
230 it->callback(head, (struct quadtree_iterator *)it);
237 int walk_quadtree(const struct quadtree_iterator *it)
239 return _walk_tree(it->head, it);