Stats appear to be working

diff --git a/quadtree.c b/quadtree.c
index eb311babf00afe296edbcccddcc9960ec4ec15f1..e827595309fe549425c6594a51a7a7a56ef0178c 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -2,7 +2,6 @@
 #include <stdlib.h>
 
 #include "quadtree.h"
-#include "utils.h"
 
 #ifdef DEBUG
 #define debug 1
@@ -42,17 +41,11 @@ static void validate_subtree(const struct quadtree *node)
                        }
                }
 
-               children += node->child[i] + 1;
+               children += node->child[i]->children + 1;
 
                validate_subtree(node->child[i]);
        }
 
-       if (node->children < 0) {
-               printf("%s:%d Tree statistics inconsistency detected! "
-                      "Negative child count: %ld\n",
-                      __func__, __LINE__, node->children);
-       }
-
        if (node->depth < 0) {
                printf("%s:%d Tree statistics inconsistency detected! "
                       "Negative depth: %ld\n",
@@ -134,18 +127,14 @@ struct quadtree *quadtree_add(struct quadtree *parent,
                return 0;
        }
 
-       parent->children++;
-
-       if (parent->child[ret]) {
-               quadtree_add(parent->child[ret], new, compare);
-               parent->depth = MAX(parent->depth,
-                                   parent->child[ret]->depth + 1);
-               return new;
-       }
+       if (parent->child[ret])
+               return quadtree_add(parent->child[ret], new, compare);
 
        parent->child[ret] = new;
        new->parent = parent;
 
+       quadtree_recalculate_parent_stats(parent);
+
        validate_tree(new);
 
        return new;
@@ -199,7 +188,7 @@ struct quadtree *quadtree_del(struct quadtree *node,
                              int (*compare)(struct quadtree *a,
                                             struct quadtree *b))
 {
-       struct quadtree *parent = 0, *tmp;
+       struct quadtree *parent = 0;
        int i;
 
        /*
@@ -243,6 +232,9 @@ struct quadtree *quadtree_del(struct quadtree *node,
                trap();
        }
 
+       /* Fix parent stats */
+       quadtree_recalculate_parent_stats(node->parent);
+
        /*
         * The sub branch is now detached from the main tree. Continue
         * relocating the detached branch.
@@ -257,19 +249,6 @@ struct quadtree *quadtree_del(struct quadtree *node,
                node->child[i] = 0;
        }
 
-       /* Fix parent stats */
-       tmp = parent;
-       while (tmp) {
-               tmp->children -= node->children;
-               tmp->depth = 0;
-               for (i = 0; i < 4; i++) {
-                       if (tmp->child[i])
-                               tmp->depth = MAX(tmp->depth,
-                                                tmp->child[i]->depth + 1);
-               }
-               tmp = tmp->parent;
-       }
-
        parent = quadtree_find_parent(node);
        node->parent = 0;
 

diff --git a/quadtree.h b/quadtree.h
index 3589b5e1da6a4ab43b3a4f5f3c5c6c6e5d4fcc19..3d8f51835ddad4a2c6c549b856ab12b1fad2a3c2 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -3,6 +3,8 @@
 
 #include <string.h>
 
+#include "utils.h"
+
 struct quadtree {
        struct quadtree *child[4];
        struct quadtree *parent;
@@ -53,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