quadtree: Collect tree statistics

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index 7d9273c363d5626dc95b7bcf6245506281efd2c0..e827595309fe549425c6594a51a7a7a56ef0178c 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -18,6 +18,8 @@ static void trap(void )
 static void validate_subtree(const struct quadtree *node)
 {
        int i;
+       long int children;
+       children = 0;
 
        for (i = 0; i < 4; i++) {
                if (!node->child[i])
@@ -29,6 +31,7 @@ static void validate_subtree(const struct quadtree *node)
                               __func__, __LINE__, i, node);
                        trap();
                }
+
                if (node->parent) {
                        if (node->child[i] == node->parent) {
                                printf("%s:%d Fatal! Tree loop detected "
@@ -38,8 +41,45 @@ static void validate_subtree(const struct quadtree *node)
                        }
                }
 
+               children += node->child[i]->children + 1;
+
                validate_subtree(node->child[i]);
        }
+
+       if (node->depth < 0) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "Negative depth: %ld\n",
+                      __func__, __LINE__, node->depth);
+       }
+
+       if (node->children != children) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "child count mismatch. Expected %ld, got %ld\n",
+                      __func__, __LINE__, children, node->children);
+               trap();
+       }
+
+       for (i = 0; i < 4 && node->children; i++) {
+               if (!node->child[i])
+                       continue;
+
+               if (node->depth == node->child[i]->depth + 1)
+                       break;
+
+               if (node->child[i]->depth > node->depth) {
+                       printf("%s:%d Tree statistics inconsistency detected! "
+                              "child depth mismatch %ld > %ld\n",
+                              __func__, __LINE__, node->child[i]->depth,
+                              node->depth);
+               }
+       }
+
+       if (i == 4) {
+               printf("%s:%d Tree statistics inconsistency detected! "
+                      "child depth mismatch.",
+                      __func__, __LINE__);
+               trap();
+       }
 }
 
 static void validate_tree(const struct quadtree *node)
@@ -93,6 +133,8 @@ struct quadtree *quadtree_add(struct quadtree *parent,
        parent->child[ret] = new;
        new->parent = parent;
 
+       quadtree_recalculate_parent_stats(parent);
+
        validate_tree(new);
 
        return new;
@@ -127,6 +169,10 @@ _quadtree_reposition_reqursively(struct quadtree *root,
                node->child[i] = 0;
        }
 
+       /* There are no children left, reset stats */
+       node->depth = 0;
+       node->children = 0;
+
        /* Then remove this node under the new root. */
        quadtree_add(root, node, compare);
 }
@@ -186,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.
@@ -203,6 +252,9 @@ struct quadtree *quadtree_del(struct quadtree *node,
        parent = quadtree_find_parent(node);
        node->parent = 0;
 
+       node->children = 0;
+       node->depth = 0;
+
        validate_tree(parent);
        return parent;
 }