From 37b38f60d066777ac07750924c0885e0e6623970 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Tue, 7 Dec 2010 22:07:55 +0200 Subject: [PATCH] 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 --- quadtree.c | 30 ++++++++++++++++++++++++++++-- 1 file changed, 28 insertions(+), 2 deletions(-) diff --git a/quadtree.c b/quadtree.c index b392e63..da3b43d 100644 --- 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); +} + } /** -- 2.45.0