quadtree: Collect tree statistics

[sdl-planets] / quadtree.h

diff --git a/quadtree.h b/quadtree.h
index 23b79cebd7595d51875618fadedc42129fd0d5b8..3d8f51835ddad4a2c6c549b856ab12b1fad2a3c2 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -1,18 +1,22 @@
 #ifndef _QUADTREE_H_
 #define _QUADTREE_H_
 
+#include <string.h>
+
+#include "utils.h"
+
 struct quadtree {
        struct quadtree *child[4];
        struct quadtree *parent;
+
+       /* statistics */
+       long int children;      /* The total number of children */
+       long int depth;         /* The deepest subtree branch */
 };
 
 static inline void init_quadtree(struct quadtree *t)
 {
-       int i;
-
-       for (i = 0; i < 4; i++)
-               t->child[i] = 0;
-       t->parent = 0;
+       memset(t, 0, sizeof(*t));
 }
 
 #define QUADTREE_UPLEFT                0x1
@@ -51,4 +55,29 @@ static inline struct quadtree *quadtree_find_parent(const struct quadtree *node)
        return t;
 }
 
+/*
+ * 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)
+{
+       int i;
+
+       while (node) {
+               node->depth = 0;
+               node->children = 0;
+
+               for (i = 0; i < 4; i++) {
+                       if (!node->child[i])
+                               continue;
+
+                       node->depth = MAX(node->depth,
+                                         node->child[i]->depth + 1);
+                       node->children += node->child[i]->children + 1;
+               }
+
+               node = node->parent;
+       }
+}
+
 #endif