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 */
17 static inline void init_quadtree(struct quadtree *t)
19 memset(t, 0, sizeof(*t));
22 #define QUADTREE_UPLEFT 0x1
23 #define QUADTREE_UPRIGHT 0x2
24 #define QUADTREE_DOWNLEFT 0x4
25 #define QUADTREE_DOWNRIGHT 0x8
26 #define QUADTREE_SELF 0x10
28 struct quadtree_iterator {
29 struct quadtree *head;
32 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
33 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
36 struct quadtree *quadtree_add(struct quadtree *parent,
38 int (*compare)(struct quadtree *a,
41 struct quadtree *quadtree_del(struct quadtree *node,
42 int (*compare)(struct quadtree *a,
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;