quadtree: Add a tree validator

This will find some typical erros in the tree and print error messages
when such erros are found.

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

diff --git a/quadtree.c b/quadtree.c
index 5e1eea746c5616e142933953be37730de3473e8d..25b8ad63d8e7944c54cecc1ee733867c072f9684 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -2,6 +2,45 @@
 
 #include "quadtree.h"
 
+void trap(void )
+{
+       exit(1);
+}
+
+static void validate_subtree(const struct quadtree *node)
+{
+       int i;
+
+       for (i = 0; i < 4; i++) {
+               if (!node->child[i])
+                       continue;
+
+               if (node->child[i]->parent != node) {
+                       printf("%s:%d Fatal! Tree inconsistency detected "
+                              "at child %d in node %p\n",
+                              __FUNCTION__, __LINE__, i, node);
+                       trap();
+               }
+               if (node->parent) {
+                       if (node->child[i] == node->parent) {
+                       printf("%s:%d Fatal! Tree loop detected "
+                              "at child %d in node %p\n",
+                              __FUNCTION__, __LINE__, i, node);
+                       trap();
+                       }
+               }
+
+               validate_subtree(node->child[i]);
+       }
+}
+
+static void validate_tree(const struct quadtree *node)
+{
+       const struct quadtree *parent = quadtree_find_parent(node);
+
+       validate_subtree(parent);
+}
+
 /**
  * quadtree_add - add a node to a quadtree
  * @parent: parent node