There is no need to go through the entire tree in case one leaf node
has a minimal change in it. As long as we have gone high enough in the
tree that there is no more any changes to the corner vectors, we can
stop walking the tree up. According to perf measurements, this
optimization reduces the tree area recalculation overhead about 50%.
Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>
static void recalculate_parent_area_stats(struct quadtree *node)
{
+ struct vector old_corner[2];
+
while (node) {
+ memcpy(&old_corner, &node->corner, sizeof(old_corner));
+
_recalculate_node_area_stats(node);
- node = node->parent;
+ /*
+ * Stop propagating the changes up in the tree if
+ * nothing has changed
+ */
+ if (memcmp(&old_corner, &node->corner, sizeof(old_corner)))
+ node = node->parent;
+ else
+ node = NULL;
}
}