From 2bc55e40ff87fae2b9f7306a9e78e29c999862f7 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Mon, 5 Apr 2010 15:41:39 +0300 Subject: [PATCH] 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 --- quadtree.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) 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 -- 2.45.0