Another optimization try..

diff --git a/planet.c b/planet.c
index 5d14d24db99adfab1cafa3fad70cd2f6eaa495d0..5b227c0f62e7a11b8ca44b2a4b24c5d855c2bd0c 100644 (file)
--- a/planet.c
+++ b/planet.c
@@ -450,7 +450,6 @@ struct planet *move_planet(struct planet *p, const double time)
 struct planet *prune_planet_tree(struct planet *p)
 {
        struct quadtree *tree_parent = &p->tree;
-       struct list_head *head = &p->list, *start = &p->list;
        int i;
 /*
        while (head != start) {

diff --git a/quadtree.c b/quadtree.c
index 61a26997c1555a7ee5c3419633d67164051bee28..9e4164464b4a5c8ab72641d7b3866ba979a9f8e3 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -225,6 +225,57 @@ static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
        }
 }
 
+static int add_to_relocation_list(struct quadtree *node,
+                                  struct list_head *head)
+{
+       int nodes = 0;
+
+       if (node->child[0])
+               nodes += add_to_relocation_list(node->child[0], head);
+       if (node->child[1])
+               nodes += add_to_relocation_list(node->child[1], head);
+
+       list_add(&node->list, head);
+       nodes++;
+
+       if (node->child[2])
+               nodes += add_to_relocation_list(node->child[2], head);
+       if (node->child[3])
+               nodes += add_to_relocation_list(node->child[3], head);
+
+       return nodes;
+}
+
+static void relocate_from_list(struct quadtree *start, struct quadtree *end,
+                              int nodes, struct quadtree *parent,
+                              struct quadtree_ops *ops)
+{
+       struct quadtree *tmp = start, *node;
+       int i;
+
+       for (i = 0; i < nodes / 2; i++)
+               tmp = list_to_tree(tmp->list.next);
+
+       node = tmp;
+
+       tmp = list_to_tree(node->list.prev);
+
+       if (debug) {
+               printf("Moving node %p\n", node);
+               fflush(stdout);
+       }
+       list_del(&node->list);
+       quadtree_add(parent, node, ops);
+       node = list_to_tree(tmp->list.next);
+
+       if (nodes / 2 - 1 > 0)
+               relocate_from_list(start, tmp, nodes / 2 - 1, parent, ops);
+
+       if (nodes > 2)
+               relocate_from_list(node, end, nodes - nodes / 2 - 1, parent,
+                                  ops);
+}
+
 /*
  * quadtree_del - Detach a node from the tree
  *
@@ -235,8 +286,9 @@ static void _qt_optimal_del(struct quadtree *parent, struct quadtree *node,
 struct quadtree *quadtree_del(struct quadtree *node,
                              struct quadtree_ops *ops)
 {
-       struct quadtree *parent = 0;
-       int i;
+       struct quadtree *parent = 0, *start, *end;
+       struct list_head *head = NULL;
+       int i, nodes = 0;
 
        if (debug) {
                printf("Deleting node %p under parent %p\n",
@@ -258,11 +310,19 @@ struct quadtree *quadtree_del(struct quadtree *node,
                                parent->parent = 0;
                                continue;
                        }
-                       _qt_optimal_del(parent, node->child[i], ops,
-                                       node->children);
-                       node->child[i] = 0;
+                       if (!head) {
+                               head = &node->child[i]->list;
+                               INIT_LIST_HEAD(head);
+                       }
+
+                       nodes += add_to_relocation_list(node->child[i], head);
                }
 
+               start = list_to_tree(head);
+               end = list_to_tree(head->prev);
+
+               relocate_from_list(start, end, nodes, parent, ops);
+
                return parent;
        }
 
@@ -296,9 +356,18 @@ struct quadtree *quadtree_del(struct quadtree *node,
                        if (!node->child[i])
                                continue;
 
-                       _qt_optimal_del(parent, node->child[i], ops,
-                                       node->children);
+                       if (!head) {
+                               head = &node->child[i]->list;
+                               INIT_LIST_HEAD(head);
+                       }
+
+                       nodes += add_to_relocation_list(node->child[i], head);
                }
+
+               start = list_to_tree(head);
+               end = list_to_tree(head->prev);
+
+               relocate_from_list(start, end, nodes, parent, ops);
        }
 
        validate_tree(parent);

diff --git a/quadtree.h b/quadtree.h
index 0784147d50c58264ee08b02296b59eea3bbde3b9..30cfd1461c6f700b7e30bb1c172e0a239c04e2c5 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -3,17 +3,21 @@
 
 #include <string.h>
 
+#include "list.h"
 #include "utils.h"
 
 struct quadtree {
        struct quadtree *child[4];
        struct quadtree *parent;
+       struct list_head list;  /* This list is used when balancing the tree */
 
        /* statistics */
        long int children;      /* The total number of children */
        long int depth;         /* The deepest subtree branch */
 };
 
+#define list_to_tree(list_head) container_of((list_head), struct quadtree, list)
+
 struct quadtree_ops {
        /*
         * Comparison function that is needed to find out the correct

diff --git a/utils.h b/utils.h
index bceaa27290a031ef0edbac49dd50392a436ae57f..6c9a272a6b37ff85c4c2e0e70e22e0e7ed18d2a1 100644 (file)
--- a/utils.h
+++ b/utils.h
@@ -1,6 +1,8 @@
 #ifndef _UTILS_H
 #define _UTILS_H
 
+#include <stddef.h>
+
 #define MAX(a,b) ((a) > (b) ? (a) : (b))
 #define MIN(a,b) ((a) < (b) ? (a) : (b))