From: Timo Kokkonen <kaapeli@itanic.dy.fi>
Date: Mon, 5 Apr 2010 12:43:43 +0000 (+0300)
Subject: quadtree: Be more careful when deleting a node from the tree
X-Git-Url: http://git.itanic.dy.fi/?p=sdl-planets;a=commitdiff_plain;h=f0c70d1e652544a70f2ffc3c3c052916834e47a2

quadtree: Be more careful when deleting a node from the tree

Before attempting to move nodes back to the main tree, detach the
subtree completely from the main tree. When detaching individual nodes
from the tree, also ensure that each node has its old children
removed.

If these measures are not taken into account, loops will form in the
tree.

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

diff --git a/quadtree.c b/quadtree.c
index a0ec4ce..94a37c1 100644
--- a/quadtree.c
+++ b/quadtree.c
@@ -162,15 +162,35 @@ struct quadtree *quadtree_del(struct quadtree *node,
 	}
 
 	/*
-	 * We are not deleting the parent. Just relocate the children
-	 * and detach the node from the tree.
+	 * We are not deleting the parent. Detach the node from the
+	 * parent abd relocate the children. The node will be then
+	 * detached from the tree.
 	 */
+
+	for (i = 0; i < 4; i++) {
+		if (node->parent->child[i] == node) {
+			node->parent->child[i] = 0;
+			break;
+		}
+	}
+	if (i == 4) {
+		printf("%s:%d Fatal! Tree inconsistency detected\n",
+		       __FUNCTION__, __LINE__);
+		trap();
+	}
+
+	/*
+	 * The sub branch is now detached from the main tree. Continue
+	 * relocating the detached branch.
+	 */
+
 	for (i = 0; i < 4; i++) {
 		if (!node->child[i])
 			continue;
 
 		_quadtree_reposition_reqursively(node->parent, node->child[i],
 						 compare);
+		node->child[i] = 0;
 	}
 
 	parent = quadtree_find_parent(node);
@@ -207,7 +227,6 @@ static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
 	return count;
 }
 
-
 int walk_tree(const struct quadtree_iterator *it)
 {
 	return _walk_tree(it->head, it);