quadtree: Move quadtree_add function in quadtree.c

The function in question is higly recursive. It is not likely the compiler will
be able to optimize it if it is kept in the header file as an inline function.

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

diff --git a/quadtree.c b/quadtree.c
new file mode 100644 (file)
index 0000000..b1475c5
--- /dev/null
+++ b/quadtree.c
@@ -0,0 +1,46 @@
+#include "quadtree.h"
+
+/**
+ * quadtree_add - add a node to a quadtree
+ * @parent: parent node
+ * @new: the new node to be added
+ * @compare: pointer to a comparison function
+ *
+ * Add a node to a quadtree. The tree is kept in order, the new node
+ * is placed in the end of appropriate branch. The compare function is
+ * used to compare the new node against a branch in the tree. The
+ * comparison function must have following return value depending on
+ * the position of node a compared to the position of node b:
+ *
+ * 0: upper left
+ * 1: upper right
+ * 2: lower left
+ * 3: lower right
+ *
+ * The case of nodes sharing identical coordinates is not taken into
+ * account at all.
+ */
+
+struct quadtree *quadtree_add(struct quadtree *parent,
+                             struct quadtree *new,
+                             int (*compare)(struct quadtree *a,
+                                            struct quadtree *b))
+{
+       int ret;
+
+       ret = compare(parent, new);
+
+       if (ret < 0 || ret >= 4) {
+               printf("Invalid comparison result of %d\n", ret);
+               return 0;
+       }
+
+       if (parent->child[ret])
+               return quadtree_add(parent->child[ret], new, compare);
+
+       parent->child[ret] = new;
+       new->parent = parent;
+
+       return new;
+}
+

diff --git a/quadtree.h b/quadtree.h
index fe31e04753e68ecbc8f49128a4af5d4133f9d590..dee62d6b90f5d1d4af1072f58863321fd9c179f6 100644 (file)
--- a/quadtree.h
+++ b/quadtree.h
@@ -15,48 +15,4 @@ static inline void init_quadtree(struct quadtree *t)
        t->parent = 0;
 }
 
-/**
- * quadtree_add - add a node to a quadtree
- * @parent: parent node
- * @new: the new node to be added
- * @compare: pointer to a comparison function
- *
- * Add a node to a quadtree. The tree is kept in order, the new node
- * is placed in the end of appropriate branch. The compare function is
- * used to compare the new node against a branch in the tree. The
- * comparison function must have following return value depending on
- * the position of node a compared to the position of node b:
- *
- * 0: upper left
- * 1: upper right
- * 2: lower left
- * 3: lower right
- *
- * The case of nodes sharing identical coordinates is not taken into
- * account at all.
- */
-
-static inline struct quadtree *quadtree_add(struct quadtree *parent,
-                                           struct quadtree *new,
-                                           int (*compare)(struct quadtree *a,
-                                                          struct quadtree *b))
-{
-       int ret;
-
-       ret = compare(parent, new);
-
-       if (ret < 0 || ret >= 4) {
-               printf("Invalid comparison result of %d\n", ret);
-               return 0;
-       }
-
-       if (parent->child[ret])
-               return quadtree_add(parent->child[ret], new, compare);
-
-       parent->child[ret] = new;
-       new->parent = parent;
-
-       return new;
-}
-
 #endif