quadtree: Allow updating other than just quadtree stats

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index ec683aaa0e8d4e872215e337f3348f5896a21e70..8efd8ad7a465b6a682ff5859350b345e653a02f7 100644 (file)
--- 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 917abd501b34dec4e6fea636c51590ddfef44bc4..0784147d50c58264ee08b02296b59eea3bbde3b9 100644 (file)
--- 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;
        }
 }