From e6b6d291ce01dfd25af19aa1f4b494559d87a7d0 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Sun, 11 Apr 2010 19:14:57 +0300 Subject: [PATCH] quadtree: Allow updating other than just quadtree stats Signed-off-by: Timo Kokkonen --- quadtree.c | 4 ++-- quadtree.h | 15 ++++++++++++++- 2 files changed, 16 insertions(+), 3 deletions(-) diff --git a/quadtree.c b/quadtree.c index ec683aa..8efd8ad 100644 --- a/quadtree.c +++ b/quadtree.c @@ -131,7 +131,7 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new, parent->child[ret] = new; new->parent = parent; - quadtree_recalculate_parent_stats(parent); + quadtree_recalculate_parent_stats(new, ops); validate_tree(new); @@ -229,7 +229,7 @@ struct quadtree *quadtree_del(struct quadtree *node, } /* Fix parent stats */ - quadtree_recalculate_parent_stats(node->parent); + quadtree_recalculate_parent_stats(node->parent, ops); /* * The sub branch is now detached from the main tree. Continue diff --git a/quadtree.h b/quadtree.h index 917abd5..0784147 100644 --- a/quadtree.h +++ b/quadtree.h @@ -15,7 +15,16 @@ struct quadtree { }; struct quadtree_ops { + /* + * Comparison function that is needed to find out the correct + * location for a node in the tree + */ int (*compare)(struct quadtree *a, struct quadtree *b); + + /* + * Calculates required statistical information for a node + */ + void (*recalculate_stats)(struct quadtree *node); }; static inline void init_quadtree(struct quadtree *t) @@ -59,7 +68,8 @@ static inline struct quadtree *quadtree_find_parent(const struct quadtree *node) * Recursively walk through the tree and propagate changes made to the * given node up until the highest parent. */ -static inline void quadtree_recalculate_parent_stats(struct quadtree *node) +static inline void quadtree_recalculate_parent_stats(struct quadtree *node, + struct quadtree_ops *ops) { int i; @@ -76,6 +86,9 @@ static inline void quadtree_recalculate_parent_stats(struct quadtree *node) node->children += node->child[i]->children + 1; } + if (ops->recalculate_stats) + ops->recalculate_stats(node); + node = node->parent; } } -- 2.45.0