9 struct quadtree *child[4];
10 struct quadtree *parent;
13 long int children; /* The total number of children */
14 long int depth; /* The deepest subtree branch */
18 int (*compare)(struct quadtree *a, struct quadtree *b);
21 static inline void init_quadtree(struct quadtree *t)
23 memset(t, 0, sizeof(*t));
26 #define QUADTREE_UPLEFT 0x1
27 #define QUADTREE_UPRIGHT 0x2
28 #define QUADTREE_DOWNLEFT 0x4
29 #define QUADTREE_DOWNRIGHT 0x8
30 #define QUADTREE_SELF 0x10
32 struct quadtree_iterator {
33 struct quadtree *head;
36 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
37 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
40 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
41 struct quadtree_ops *ops);
43 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
45 int walk_quadtree(const struct quadtree_iterator *iterator);
48 /* quadtree_find_parent - return the highest parent of the node */
49 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
51 struct quadtree *t = (struct quadtree *)node;
59 * Recursively walk through the tree and propagate changes made to the
60 * given node up until the highest parent.
62 static inline void quadtree_recalculate_parent_stats(struct quadtree *node)
70 for (i = 0; i < 4; i++) {
74 node->depth = MAX(node->depth,
75 node->child[i]->depth + 1);
76 node->children += node->child[i]->children + 1;