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 * Comparison function that is needed to find out the correct
22 * location for a node in the tree
24 int (*compare)(struct quadtree *a, struct quadtree *b);
27 * Calculates required statistical information for a node
29 void (*recalculate_stats)(struct quadtree *node);
32 static inline void init_quadtree(struct quadtree *t)
34 memset(t, 0, sizeof(*t));
37 #define QUADTREE_UPLEFT 0x1
38 #define QUADTREE_UPRIGHT 0x2
39 #define QUADTREE_DOWNLEFT 0x4
40 #define QUADTREE_DOWNRIGHT 0x8
41 #define QUADTREE_SELF 0x10
43 struct quadtree_iterator {
44 struct quadtree *head;
47 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
48 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
51 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
52 struct quadtree_ops *ops);
54 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
56 int walk_quadtree(const struct quadtree_iterator *iterator);
59 /* quadtree_find_parent - return the highest parent of the node */
60 static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
62 struct quadtree *t = (struct quadtree *)node;
70 * Recursively walk through the tree and propagate changes made to the
71 * given node up until the highest parent.
73 static inline void quadtree_recalculate_parent_stats(struct quadtree *node,
74 struct quadtree_ops *ops)
82 for (i = 0; i < 4; i++) {
86 node->depth = MAX(node->depth,
87 node->child[i]->depth + 1);
88 node->children += node->child[i]->children + 1;
91 if (ops->recalculate_stats)
92 ops->recalculate_stats(node);