Better optimization perhaps

diff --git a/planet.c b/planet.c
index fae7086e78dcef3cb083b5af758875adb17a3dcf..5d14d24db99adfab1cafa3fad70cd2f6eaa495d0 100644 (file)
--- a/planet.c
+++ b/planet.c
@@ -449,9 +449,27 @@ struct planet *move_planet(struct planet *p, const double time)
 
 struct planet *prune_planet_tree(struct planet *p)
 {
-       struct quadtree *tree_parent;
+       struct quadtree *tree_parent = &p->tree;
+       struct list_head *head = &p->list, *start = &p->list;
        int i;
+/*
+       while (head != start) {
+               p = list_to_planet(head);
+               if (p->to_be_deleted) {
+                       if (head == start)
+                               start = head->next;
+                       list_del(&p->list);
+                       tree_parent = quadtree_del(&p->tree, &planet_ops);
+                       head = head->next;
+                       free(p);
+                       continue;
+               }
+
+               head = head->next;
+       }
 
+       return tree_to_planet(tree_parent);
+*/
        for (i = 0; i < 4; i++) {
                if (!p->tree.child[i])
                        continue;

diff --git a/quadtree.c b/quadtree.c
index c3b28106052ecd30fc52b84a33330a2f53b39301..9d1232bb26c1187715bea010413777dcc25532be 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -21,14 +21,22 @@ static void validate_subtree(const struct quadtree *node)
        long int children;
        children = 0;
 
+       if (!node) {
+               printf("Attempted to validate a null pointer\n");
+               fflush(stdout);
+               trap();
+       }
+
        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",
-                              __func__, __LINE__, i, node);
+                       printf("%s:%d Fatal! Tree inconsistency detected at "
+                              "child %d %p in node %p, incorrent parent %p\n",
+                              __func__, __LINE__, i, node->child[i], node,
+                              node->child[i]->parent);
+                       fflush(stdout);
                        trap();
                }
 
@@ -37,6 +45,7 @@ static void validate_subtree(const struct quadtree *node)
                                printf("%s:%d Fatal! Tree loop detected "
                                       "at child %d in node %p\n",
                                       __func__, __LINE__, i, node);
+                               fflush(stdout);
                                trap();
                        }
                }
@@ -56,6 +65,7 @@ static void validate_subtree(const struct quadtree *node)
                printf("%s:%d Tree statistics inconsistency detected! "
                       "child count mismatch. Expected %ld, got %ld\n",
                       __func__, __LINE__, children, node->children);
+               fflush(stdout);
                trap();
        }
 
@@ -78,6 +88,7 @@ static void validate_subtree(const struct quadtree *node)
                printf("%s:%d Tree statistics inconsistency detected! "
                       "child depth mismatch.",
                       __func__, __LINE__);
+               fflush(stdout);
                trap();
        }
 }
@@ -133,6 +144,11 @@ struct quadtree *quadtree_add(struct quadtree *parent, struct quadtree *new,
        for (i = 0; i < 4; i++)
                new->child[i] = 0;
 
+       if (debug) {
+               printf("adding node %p to parent %p\n", new, parent);
+               fflush(stdout);
+       }
+
        quadtree_recalculate_parent_stats(new, ops);
 
        validate_tree(new);
@@ -206,7 +222,7 @@ _quadtree_reposition_reqursively(struct quadtree *root,
 static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
                       struct quadtree_ops *ops, int parents)
 {
-       struct quadtree *child[4];
+       struct quadtree *child[4] = {0};
        int i, children = 0, max_c, max_i;
 
        for (i = 0; i < 4; i++) {
@@ -227,6 +243,11 @@ static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
         */
 
        if (node->children <= parents / 4) {
+               if (debug) {
+                       printf("%d: Moving node %p away from parent %p\n",
+                              __LINE__, node, parent);
+                       fflush(stdout);
+               }
                validate_tree(parent);
                quadtree_add(parent, node, ops);
                node = NULL;
@@ -253,6 +274,11 @@ static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
 
        if (node) {
                validate_tree(parent);
+               if (debug) {
+                       printf("%d: Moving node %p away from parent %p\n",
+                              __LINE__, node, parent);
+                       fflush(stdout);
+               }
                quadtree_add(parent, node, ops);
        }
 }
@@ -270,6 +296,11 @@ struct quadtree *quadtree_del(struct quadtree *node,
        struct quadtree *parent = 0;
        int i;
 
+       if (debug) {
+               printf("Deleting node %p under parent %p\n",
+                              node, node->parent);
+               fflush(stdout);
+       }
        /*
         * We are deleting the root node. This means we have to select
         * a new root node and reconstruct the entire tree under it
@@ -285,9 +316,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
                                parent->parent = 0;
                                continue;
                        }
-                       _quadtree_reposition_reqursively(parent,
-                                                        node->child[i],
-                                                        ops);
+                       _qt_optimal_del(parent, node->child[i], ops,
+                                       node->children);
                        node->child[i] = 0;
                }
 
@@ -306,6 +336,8 @@ struct quadtree *quadtree_del(struct quadtree *node,
                        break;
                }
        }
+       if (i == 4)
+               trap();
 
        parent = node->parent;
 
@@ -315,15 +347,18 @@ struct quadtree *quadtree_del(struct quadtree *node,
         */
        quadtree_recalculate_parent_stats(node->parent, ops);
 
-       if (node->children)
-               _qt_optimal_del(parent, node, ops, node->children);
+       parent = quadtree_find_parent(parent);
 
-       node->parent = 0;
+       if (node->children) {
+               for (i = 0; i < 4; i++) {
+                       if (!node->child[i])
+                               continue;
 
-       node->children = 0;
-       node->depth = 0;
+                       _qt_optimal_del(parent, node->child[i], ops,
+                                       node->children);
+               }
+       }
 
-       parent = quadtree_find_parent(parent);
        validate_tree(parent);
        return parent;
 }