From 466216f90330cccb2db509f828172a3ccece7c86 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Tue, 19 Jul 2011 20:10:14 +0300 Subject: [PATCH] quadtree: Optimize recalculate_parent_area_stats() 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 --- quadtree.c | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/quadtree.c b/quadtree.c index 72973c8..cb4add6 100644 --- a/quadtree.c +++ b/quadtree.c @@ -213,10 +213,21 @@ static void _recalculate_node_area_stats(struct quadtree *node) 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; } } -- 2.45.0