From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Mon, 5 Apr 2010 12:41:39 +0000 (+0300)
Subject: quadtree: Add a tree validator
X-Git-Url: http://git.itanic.dy.fi/?p=sdl-planets;a=commitdiff_plain;h=2bc55e40ff87fae2b9f7306a9e78e29c999862f7

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 5e1eea7..25b8ad6 100644
--- 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