12 struct quadtree *child[4];
13 struct quadtree *parent;
14 struct list_head list; /* This list is used when balancing the tree */
17 long int children; /* The total number of children */
18 long int depth; /* The deepest subtree branch */
21 #define list_to_tree(list_head) container_of((list_head), struct quadtree, list)
25 * Calculates required statistical information for a node
27 void (*recalculate_stats)(struct quadtree *node);
30 static inline void init_quadtree(struct quadtree *t)
32 memset(t, 0, sizeof(*t));
35 #define QUADTREE_UPLEFT 0x1
36 #define QUADTREE_UPRIGHT 0x2
37 #define QUADTREE_DOWNLEFT 0x4
38 #define QUADTREE_DOWNRIGHT 0x8
39 #define QUADTREE_SELF 0x10
41 struct quadtree_iterator {
42 struct quadtree *head;
45 int (*direction)(struct quadtree *head, struct quadtree_iterator *it);
46 void (*callback)(struct quadtree *head, struct quadtree_iterator *it);
49 struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
50 struct quadtree_ops *ops);
52 struct quadtree *quadtree_del(struct quadtree *node, struct quadtree_ops *ops);
53 struct quadtree *quadtree_move(struct quadtree *node, struct vector new_pos,
54 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);
98 void _quadtree_validate_tree(const struct quadtree *node);
100 static inline void quadtree_validate_tree(struct quadtree *node)
103 _quadtree_validate_tree(node);