quadtree: validator: Catch missing leaf node

This patch will make the validator to catch error when a leaf node has
a pointer to a parent which does not have pointer back to the leaf
node.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index b392e639b84f8c8f045f4136ebee2a16d2fcd3a8..da3b43d9b81f925b26c4a4608371f8e0e775ad51 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -138,8 +138,34 @@ 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 %p for node %p\n",
+                       __func__, __LINE__, node->parent, node);
+               fflush(stdout);
+               trap();
+       }
+
+       validate_tree(node->parent);
+}
+
+void _quadtree_validate_tree(const struct quadtree *node)
+{
+       validate_tree(node);
+}
+
 }
 
 /**