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 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);
        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);
        }
 
        parent = quadtree_find_parent(node);


@@ -207,7 +227,6 @@ static int _walk_tree(struct quadtree *head, const struct quadtree_iterator *it)
        return count;
 }
 
        return count;
 }
 

-

 int walk_tree(const struct quadtree_iterator *it)
 {
        return _walk_tree(it->head, it);
 int walk_tree(const struct quadtree_iterator *it)
 {
        return _walk_tree(it->head, it);