Add debug and improve tree validation

diff --git a/quadtree.c b/quadtree.c
index f7513462cf77f4823550bf2cc93e7e467e4c8966..d1d9c8a481811b1c896c6a18c7623fa552cc91ff 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -11,8 +11,10 @@
 
 static void trap(void)
 {
-       if (debug)
+       if (debug) {
+               printf("Trapped, use debugger to get backtrace\n");
                exit(1);
+       }
 }
 
 static void validate_subtree(const struct quadtree *node)
@@ -95,8 +97,26 @@ static void validate_subtree(const struct quadtree *node)
 
 static void validate_tree(const struct quadtree *node)
 {
-       if (debug)
-               validate_subtree(quadtree_find_parent(node));
+       int i;
+
+       if (!debug)
+               return;
+
+       if (!node->parent)
+               return validate_subtree(node);
+
+       for (i = 0; i < 4; i++)
+               if (node->parent->child[i] == node)
+                       break;
+
+       if (i == 4) {
+               printf("%s:%d Tree inconsistency detected! Wrong parent\n",
+                      __func__, __LINE__);
+               fflush(stdout);
+               trap();
+       }
+
+       validate_tree(node->parent);
 }
 
 static int quadtree_compare_coord(struct vector *a, struct vector *b)
@@ -424,7 +444,7 @@ static void optimally_move_tree(struct quadtree *tree, struct quadtree *parent,
 
        if (debug) {
                printf("Relocating node %p under parent %p\n", t, parent);
-               printf("There are %d child nodes left\n", tree->children);
+               printf("There are %ld child nodes left\n", tree->children);
                fflush(stdout);
        }
        _quadtree_del(t, tree);
@@ -546,9 +566,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
        }
 
 out:
-       parent = quadtree_find_parent(parent);
        validate_tree(parent);
-       return parent;
+       return quadtree_find_parent(parent);
 }