11 struct quadtree *child[4];
12 struct quadtree *parent;
15 long int children; /* The total number of children */
16 long int depth; /* The deepest subtree branch */
21 * Calculates required statistical information for a node
23 void (*recalculate_stats)(struct quadtree *node);
26 static inline void init_quadtree(struct quadtree *t)
28 memset(t, 0, sizeof(*t));
31 #define QUADTREE_UPLEFT 0x1
32 #define QUADTREE_UPRIGHT 0x2
33 #define QUADTREE_DOWNLEFT 0x4
34 #define QUADTREE_DOWNRIGHT 0x8
35 #define QUADTREE_SELF 0x10
37 struct quadtree_iterator {
38 struct quadtree *head;
41 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
42 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
45 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
46 struct quadtree_ops *ops);
48 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
50 int walk_quadtree(const struct quadtree_iterator *iterator);
53 /* quadtree_find_parent - return the highest parent of the node */
54 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
56 struct quadtree *t = (struct quadtree *)node;
64 * Recursively walk through the tree and propagate changes made to the
65 * given node up until the highest parent.
67 static inline void quadtree_recalculate_parent_stats(struct quadtree *node,
68 struct quadtree_ops *ops)
76 for (i = 0; i < 4; i++) {
80 node->depth = MAX(node->depth,
81 node->child[i]->depth + 1);
82 node->children += node->child[i]->children + 1;
85 if (ops->recalculate_stats)
86 ops->recalculate_stats(node);