1 files changed, 318 insertions, 0 deletions

diff --git a/libraries/eina/src/tests/eina_bench_quad.c b/libraries/eina/src/tests/eina_bench_quad.c
new file mode 100644
index 0000000..76d6667
--- /dev/null
+++ b/libraries/eina/src/tests/eina_bench_quad.c
@@ -0,0 +1,318 @@
+/* EINA - EFL data type library
+ * Copyright (C) 2010 Cedric BAIL
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library;
+ * if not, see <http://www.gnu.org/licenses/>.
+ */
+
+#define WIDTH 720
+#define HEIGHT 576
+
+#include "eina_main.h"
+#include "eina_mempool.h"
+#include "eina_rectangle.h"
+#include "eina_quadtree.h"
+#include "eina_list.h"
+#include "eina_bench.h"
+
+static void
+eina_bench_render_loop(int request)
+{
+   Eina_List *objects = NULL;
+   Eina_Rectangle *r;
+   int i;
+   int j;
+
+   eina_init();
+
+   for (i = 0; i < request; ++i)
+      objects = eina_list_append(objects,
+                                 eina_rectangle_new((rand() * WIDTH) / RAND_MAX,
+                                                    (rand() *
+                                                     HEIGHT) / RAND_MAX,
+                                                    (rand() * WIDTH /
+                                                     2) / RAND_MAX,
+                                                    (rand() * HEIGHT /
+                                                     2) / RAND_MAX));
+
+   for (j = 0; j < 100; ++j)
+     {
+        Eina_Rectangle *collide;
+        Eina_List *collided = NULL;
+        Eina_List *changed = NULL;
+        Eina_List *l;
+
+        /* Delete 25% of all objects */
+        i = request * 25 / 100;
+        for (; i > 0; --i)
+          {
+             eina_rectangle_free(eina_list_data_get(objects));
+             objects = eina_list_remove_list(objects, objects);
+          }
+
+        /* Add them back */
+        i = request * 25 / 100;
+        for (; i > 0; --i)
+          {
+             r = eina_rectangle_new((rand() * WIDTH) / RAND_MAX,
+                                    (rand() * HEIGHT) / RAND_MAX,
+                                    (rand() * WIDTH / 3) / RAND_MAX,
+                                    (rand() * HEIGHT / 3) / RAND_MAX);
+             objects = eina_list_prepend(objects, r);
+             changed = eina_list_append(changed, r);
+          }
+
+        /* Do one collide search */
+        collide = eina_rectangle_new((rand() * WIDTH) / RAND_MAX,
+                                     (rand() * HEIGHT) / RAND_MAX,
+                                     (rand() * WIDTH / 4) / RAND_MAX,
+                                     (rand() * HEIGHT / 4) / RAND_MAX);
+        EINA_LIST_FOREACH(objects, l, r)
+        if (eina_rectangles_intersect(r, collide))
+           collided = eina_list_append(collided, r);
+
+        collided = eina_list_free(collided);
+        eina_rectangle_free(collide);
+
+        /* Modify 50% of all objects */
+        i = request * 50 / 100;
+        for (; i > 0; --i)
+          {
+             r = eina_list_data_get(eina_list_last(objects));
+             objects = eina_list_remove_list(objects, eina_list_last(objects));
+
+             r->x = (rand() * WIDTH) / RAND_MAX;
+             r->y = (rand() * HEIGHT) / RAND_MAX;
+             r->w = (rand() * WIDTH / 3) / RAND_MAX;
+             r->h = (rand() * HEIGHT / 3) / RAND_MAX;
+
+             objects = eina_list_prepend(objects, r);
+             changed = eina_list_append(changed, r);
+          }
+
+        /* Emulating the render loop by colliding all modified
+           object with all intersecting object */
+        EINA_LIST_FREE(changed, r)
+        {
+           EINA_LIST_FOREACH(objects, l, collide)
+           if (r != collide && eina_rectangles_intersect(collide, r))
+              collided = eina_list_append(collided, collide);
+
+           collided = eina_list_append(collided, r);
+        }
+
+        /* Ok, we compute it, now it's done */
+        collided = eina_list_free(collided);
+     }
+
+   EINA_LIST_FREE(objects, r)
+   eina_rectangle_free(r);
+
+   eina_shutdown();
+}
+
+typedef struct _Eina_Bench_Quad Eina_Bench_Quad;
+struct _Eina_Bench_Quad
+{
+   Eina_Rectangle r;
+   Eina_QuadTree_Item *item;
+};
+
+static Eina_Quad_Direction
+_eina_bench_quadtree_vertical(const void *object, size_t middle)
+{
+   const Eina_Bench_Quad *b = object;
+   size_t y;
+
+   y = b->r.y < 0 ? 0 : (size_t)b->r.y;
+
+   if (y + b->r.h < middle)
+      return EINA_QUAD_LEFT;
+
+   if (y > middle)
+      return EINA_QUAD_RIGHT;
+
+   return EINA_QUAD_BOTH;
+}
+
+static Eina_Quad_Direction
+_eina_bench_quadtree_horizontal(const void *object, size_t middle)
+{
+   const Eina_Bench_Quad *b = object;
+   size_t x;
+
+   x = b->r.x < 0 ? 0 : (size_t)b->r.x;
+
+   if (x + b->r.w < middle)
+      return EINA_QUAD_LEFT;
+
+   if (x > middle)
+      return EINA_QUAD_RIGHT;
+
+   return EINA_QUAD_BOTH;
+}
+
+static void
+eina_bench_quadtree_render_loop(int request)
+{
+   Eina_List *objects = NULL;
+   Eina_Inlist *possibility;
+   Eina_Bench_Quad *b;
+   Eina_QuadTree *q;
+   Eina_Mempool *mp;
+   int i;
+   int j;
+
+   eina_init();
+
+   mp = eina_mempool_add("chained_mempool", "bench-quad", NULL,
+                         sizeof (Eina_Bench_Quad), 320);
+
+   q = eina_quadtree_new(WIDTH, HEIGHT,
+                         _eina_bench_quadtree_vertical,
+                         _eina_bench_quadtree_horizontal);
+
+   /* Create requested object */
+   for (i = 0; i < request; ++i)
+     {
+        b = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad));
+        EINA_RECTANGLE_SET(&b->r,
+                           (rand() * WIDTH) / RAND_MAX,
+                           (rand() * HEIGHT) / RAND_MAX,
+                           (rand() * WIDTH / 2) / RAND_MAX,
+                           (rand() * HEIGHT / 2) / RAND_MAX);
+        b->item = eina_quadtree_add(q, b);
+
+        objects = eina_list_append(objects, b);
+     }
+
+   for (j = 0; j < 100; ++j)
+     {
+        Eina_Bench_Quad *collide;
+        Eina_List *changed = NULL;
+        Eina_List *collided = NULL;
+
+        /* Delete 25% of all objects */
+        i = request * 25 / 100;
+        for (; i > 0; --i)
+          {
+             b = eina_list_data_get(objects);
+             eina_quadtree_del(b->item);
+             eina_mempool_free(mp, b);
+
+             objects = eina_list_remove_list(objects, objects);
+          }
+
+        /* Add them back */
+        i = request * 25 / 100;
+        for (; i > 0; --i)
+          {
+             b = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad));
+             EINA_RECTANGLE_SET(&b->r,
+                                (rand() * WIDTH) / RAND_MAX,
+                                (rand() * HEIGHT) / RAND_MAX,
+                                (rand() * WIDTH / 3) / RAND_MAX,
+                                (rand() * HEIGHT / 3) / RAND_MAX);
+             b->item = eina_quadtree_add(q, b);
+
+             objects = eina_list_prepend(objects, b);
+             changed = eina_list_append(changed, b);
+          }
+
+        /* Do one collide search */
+        collide = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad));
+             EINA_RECTANGLE_SET(&collide->r,
+                           (rand() * WIDTH) / RAND_MAX,
+                           (rand() * HEIGHT) / RAND_MAX,
+                           (rand() * WIDTH / 4) / RAND_MAX,
+                           (rand() * HEIGHT / 4) / RAND_MAX);
+        possibility = eina_quadtree_collide(q,
+                                            collide->r.x, collide->r.y,
+                                            collide->r.w, collide->r.h);
+        while (possibility)
+          {
+             b = eina_quadtree_object(possibility);
+             possibility = possibility->next;
+
+             if (eina_rectangles_intersect(&b->r, &collide->r))
+                collided = eina_list_append(collided, b);
+          }
+
+        collided = eina_list_free(collided);
+        eina_mempool_free(mp, collide);
+
+        /* Modify 50% of all objects */
+        i = request * 50 / 100;
+        for (; i > 0; --i)
+          {
+             b = eina_list_data_get(eina_list_last(objects));
+             objects = eina_list_remove_list(objects, eina_list_last(objects));
+
+             b->r.x = (rand() * WIDTH) / RAND_MAX;
+             b->r.y = (rand() * HEIGHT) / RAND_MAX;
+             b->r.w = (rand() * WIDTH / 3) / RAND_MAX;
+             b->r.h = (rand() * HEIGHT / 3) / RAND_MAX;
+
+             eina_quadtree_change(b->item);
+
+             objects = eina_list_prepend(objects, b);
+             changed = eina_list_append(changed, b);
+          }
+
+        /* Emulating the render loop by colliding all modified
+           object with all intersecting object */
+        EINA_LIST_FREE(changed, b)
+        {
+           possibility = eina_quadtree_collide(q,
+                                               b->r.x, b->r.y, b->r.w, b->r.h);
+           while (possibility)
+             {
+                collide = eina_quadtree_object(possibility);
+                possibility = possibility->next;
+
+                if (collide != b &&
+                    eina_rectangles_intersect(&b->r, &collide->r))
+                   collided = eina_list_append(collided, collide);
+             }
+
+           collided = eina_list_append(collided, b);
+        }
+
+        /* Ok, we compute it, now it's done */
+        collided = eina_list_free(collided);
+     }
+
+   EINA_LIST_FREE(objects, b)
+   {
+      eina_quadtree_del(b->item);
+      eina_mempool_free(mp, b);
+   }
+
+   eina_mempool_del(mp);
+
+   eina_quadtree_free(q);
+
+   eina_shutdown();
+}
+
+void
+eina_bench_quadtree(Eina_Benchmark *bench)
+{
+   eina_benchmark_register(bench, "collide-all",
+                           EINA_BENCHMARK(eina_bench_render_loop),
+                           100, 1500, 50);
+   eina_benchmark_register(bench, "collide-quad-tree",
+                           EINA_BENCHMARK(eina_bench_quadtree_render_loop),
+                           100, 1500, 50);
+}