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

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index a0ec4cebd3bad3ded394e08e658cf6dd4b2a27d4..94a37c1775f438bbc0e44bbc1fafc402c5dc480d 100644 (file)
--- 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);