quadtree: Factor out tree area stats calculation

This makes it possible to only update the tree area statistics, in
case nothing else has updated from the tree.

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

diff --git a/quadtree.c b/quadtree.c
index 81552f6e89312a40ec0073df386c53539e11b189..e35505dffb9c1de3c827cc9fc4fe5f10114f605d 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -189,6 +189,37 @@ static struct quadtree *_quadtree_add(struct quadtree *parent,
        return new;
 }
 
+static void _recalculate_node_area_stats(struct quadtree *node)
+{
+               /* The space covered by the parent node's corner
+                * points needs be as wide as its widest child node's
+                * corners.
+                */
+#define CHILD_CORNER_SAFE(node, ch_idx, cor_idx, axis)              \
+               (node)->child[ch_idx] ?                              \
+                       (node)->child[ch_idx]->corner[cor_idx].axis : \
+                       (node)->pos.axis
+
+               node->corner[0].x = MIN(CHILD_CORNER_SAFE(node, 0, 0, x),
+                                       CHILD_CORNER_SAFE(node, 2, 0, x));
+               node->corner[0].y = MIN(CHILD_CORNER_SAFE(node, 0, 0, y),
+                                       CHILD_CORNER_SAFE(node, 1, 0, y));
+               node->corner[1].x = MAX(CHILD_CORNER_SAFE(node, 1, 1, x),
+                                       CHILD_CORNER_SAFE(node, 3, 1, x));
+               node->corner[1].y = MAX(CHILD_CORNER_SAFE(node, 2, 1, y),
+                                       CHILD_CORNER_SAFE(node, 3, 1, y));
+#undef CHILD_CORNER_SAFE
+}
+
+static void recalculate_parent_area_stats(struct quadtree *node)
+{
+       while (node) {
+               _recalculate_node_area_stats(node);
+
+               node = node->parent;
+       }
+}
+
 /*
  * Recursively walk through the tree and propagate changes made to the
  * given node up until the highest parent.
@@ -211,24 +242,7 @@ static void quadtree_recalculate_parent_stats(struct quadtree *node,
                        node->children += node->child[i]->children + 1;
                }
 
-               /* The space covered by the parent node's corner
-                * points needs be as wide as its widest child node's
-                * corners.
-                */
-#define CHILD_CORNER_SAFE(node, ch_idx, cor_idx, axis)              \
-               (node)->child[ch_idx] ?                              \
-                       (node)->child[ch_idx]->corner[cor_idx].axis : \
-                       (node)->pos.axis
-
-               node->corner[0].x = MIN(CHILD_CORNER_SAFE(node, 0, 0, x),
-                                       CHILD_CORNER_SAFE(node, 2, 0, x));
-               node->corner[0].y = MIN(CHILD_CORNER_SAFE(node, 0, 0, y),
-                                       CHILD_CORNER_SAFE(node, 1, 0, y));
-               node->corner[1].x = MAX(CHILD_CORNER_SAFE(node, 1, 1, x),
-                                       CHILD_CORNER_SAFE(node, 3, 1, x));
-               node->corner[1].y = MAX(CHILD_CORNER_SAFE(node, 2, 1, y),
-                                       CHILD_CORNER_SAFE(node, 3, 1, y));
-#undef CHILD_CORNER_SAFE
+               _recalculate_node_area_stats(node);
 
                if (ops->recalculate_stats)
                        ops->recalculate_stats(node);