src/tests/eina_bench_quad.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2010 Cedric BAIL
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library;
  16  * if not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #define WIDTH 720
  20 #define HEIGHT 576
  21
  22 #include <stdlib.h>
  23
  24 #include "eina_main.h"
  25 #include "eina_mempool.h"
  26 #include "eina_rectangle.h"
  27 #include "eina_quadtree.h"
  28 #include "eina_list.h"
  29 #include "eina_bench.h"
  30
  31 static void
  32 eina_bench_render_loop(int request)
  33 {
  34    Eina_List *objects = NULL;
  35    Eina_Rectangle *r;
  36    int i;
  37    int j;
  38
  39    eina_init();
  40
  41    for (i = 0; i < request; ++i)
  42       objects = eina_list_append(objects,
  43                                  eina_rectangle_new((rand() * WIDTH) / RAND_MAX,
  44                                                     (rand() *
  45                                                      HEIGHT) / RAND_MAX,
  46                                                     (rand() * WIDTH /
  47                                                      2) / RAND_MAX,
  48                                                     (rand() * HEIGHT /
  49                                                      2) / RAND_MAX));
  50
  51    for (j = 0; j < 100; ++j)
  52      {
  53         Eina_Rectangle *collide;
  54         Eina_List *collided = NULL;
  55         Eina_List *changed = NULL;
  56         Eina_List *l;
  57
  58         /* Delete 25% of all objects */
  59         i = request * 25 / 100;
  60         for (; i > 0; --i)
  61           {
  62              eina_rectangle_free(eina_list_data_get(objects));
  63              objects = eina_list_remove_list(objects, objects);
  64           }
  65
  66         /* Add them back */
  67         i = request * 25 / 100;
  68         for (; i > 0; --i)
  69           {
  70              r = eina_rectangle_new((rand() * WIDTH) / RAND_MAX,
  71                                     (rand() * HEIGHT) / RAND_MAX,
  72                                     (rand() * WIDTH / 3) / RAND_MAX,
  73                                     (rand() * HEIGHT / 3) / RAND_MAX);
  74              objects = eina_list_prepend(objects, r);
  75              changed = eina_list_append(changed, r);
  76           }
  77
  78         /* Do one collide search */
  79         collide = eina_rectangle_new((rand() * WIDTH) / RAND_MAX,
  80                                      (rand() * HEIGHT) / RAND_MAX,
  81                                      (rand() * WIDTH / 4) / RAND_MAX,
  82                                      (rand() * HEIGHT / 4) / RAND_MAX);
  83         EINA_LIST_FOREACH(objects, l, r)
  84         if (eina_rectangles_intersect(r, collide))
  85            collided = eina_list_append(collided, r);
  86
  87         collided = eina_list_free(collided);
  88         eina_rectangle_free(collide);
  89
  90         /* Modify 50% of all objects */
  91         i = request * 50 / 100;
  92         for (; i > 0; --i)
  93           {
  94              r = eina_list_data_get(eina_list_last(objects));
  95              objects = eina_list_remove_list(objects, eina_list_last(objects));
  96
  97              r->x = (rand() * WIDTH) / RAND_MAX;
  98              r->y = (rand() * HEIGHT) / RAND_MAX;
  99              r->w = (rand() * WIDTH / 3) / RAND_MAX;
 100              r->h = (rand() * HEIGHT / 3) / RAND_MAX;
 101
 102              objects = eina_list_prepend(objects, r);
 103              changed = eina_list_append(changed, r);
 104           }
 105
 106         /* Emulating the render loop by colliding all modified
 107            object with all intersecting object */
 108         EINA_LIST_FREE(changed, r)
 109         {
 110            EINA_LIST_FOREACH(objects, l, collide)
 111            if (r != collide && eina_rectangles_intersect(collide, r))
 112               collided = eina_list_append(collided, collide);
 113
 114            collided = eina_list_append(collided, r);
 115         }
 116
 117         /* Ok, we compute it, now it's done */
 118         collided = eina_list_free(collided);
 119      }
 120
 121    EINA_LIST_FREE(objects, r)
 122    eina_rectangle_free(r);
 123
 124    eina_shutdown();
 125 }
 126
 127 typedef struct _Eina_Bench_Quad Eina_Bench_Quad;
 128 struct _Eina_Bench_Quad
 129 {
 130    Eina_Rectangle r;
 131    Eina_QuadTree_Item *item;
 132 };
 133
 134 static Eina_Quad_Direction
 135 _eina_bench_quadtree_vertical(const void *object, size_t middle)
 136 {
 137    const Eina_Bench_Quad *b = object;
 138    size_t y;
 139
 140    y = b->r.y < 0 ? 0 : (size_t)b->r.y;
 141
 142    if (y + b->r.h < middle)
 143       return EINA_QUAD_LEFT;
 144
 145    if (y > middle)
 146       return EINA_QUAD_RIGHT;
 147
 148    return EINA_QUAD_BOTH;
 149 }
 150
 151 static Eina_Quad_Direction
 152 _eina_bench_quadtree_horizontal(const void *object, size_t middle)
 153 {
 154    const Eina_Bench_Quad *b = object;
 155    size_t x;
 156
 157    x = b->r.x < 0 ? 0 : (size_t)b->r.x;
 158
 159    if (x + b->r.w < middle)
 160       return EINA_QUAD_LEFT;
 161
 162    if (x > middle)
 163       return EINA_QUAD_RIGHT;
 164
 165    return EINA_QUAD_BOTH;
 166 }
 167
 168 static void
 169 eina_bench_quadtree_render_loop(int request)
 170 {
 171    Eina_List *objects = NULL;
 172    Eina_Inlist *possibility;
 173    Eina_Bench_Quad *b;
 174    Eina_QuadTree *q;
 175    Eina_Mempool *mp;
 176    int i;
 177    int j;
 178
 179    eina_init();
 180
 181    mp = eina_mempool_add("chained_mempool", "bench-quad", NULL,
 182                          sizeof (Eina_Bench_Quad), 320);
 183
 184    q = eina_quadtree_new(WIDTH, HEIGHT,
 185                          _eina_bench_quadtree_vertical,
 186                          _eina_bench_quadtree_horizontal);
 187
 188    /* Create requested object */
 189    for (i = 0; i < request; ++i)
 190      {
 191         b = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad));
 192         EINA_RECTANGLE_SET(&b->r,
 193                            (rand() * WIDTH) / RAND_MAX,
 194                            (rand() * HEIGHT) / RAND_MAX,
 195                            (rand() * WIDTH / 2) / RAND_MAX,
 196                            (rand() * HEIGHT / 2) / RAND_MAX);
 197         b->item = eina_quadtree_add(q, b);
 198
 199         objects = eina_list_append(objects, b);
 200      }
 201
 202    for (j = 0; j < 100; ++j)
 203      {
 204         Eina_Bench_Quad *collide;
 205         Eina_List *changed = NULL;
 206         Eina_List *collided = NULL;
 207
 208         /* Delete 25% of all objects */
 209         i = request * 25 / 100;
 210         for (; i > 0; --i)
 211           {
 212              b = eina_list_data_get(objects);
 213              eina_quadtree_del(b->item);
 214              eina_mempool_free(mp, b);
 215
 216              objects = eina_list_remove_list(objects, objects);
 217           }
 218
 219         /* Add them back */
 220         i = request * 25 / 100;
 221         for (; i > 0; --i)
 222           {
 223              b = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad));
 224              EINA_RECTANGLE_SET(&b->r,
 225                                 (rand() * WIDTH) / RAND_MAX,
 226                                 (rand() * HEIGHT) / RAND_MAX,
 227                                 (rand() * WIDTH / 3) / RAND_MAX,
 228                                 (rand() * HEIGHT / 3) / RAND_MAX);
 229              b->item = eina_quadtree_add(q, b);
 230
 231              objects = eina_list_prepend(objects, b);
 232              changed = eina_list_append(changed, b);
 233           }
 234
 235         /* Do one collide search */
 236         collide = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad));
 237              EINA_RECTANGLE_SET(&collide->r,
 238                            (rand() * WIDTH) / RAND_MAX,
 239                            (rand() * HEIGHT) / RAND_MAX,
 240                            (rand() * WIDTH / 4) / RAND_MAX,
 241                            (rand() * HEIGHT / 4) / RAND_MAX);
 242         possibility = eina_quadtree_collide(q,
 243                                             collide->r.x, collide->r.y,
 244                                             collide->r.w, collide->r.h);
 245         while (possibility)
 246           {
 247              b = eina_quadtree_object(possibility);
 248              possibility = possibility->next;
 249
 250              if (eina_rectangles_intersect(&b->r, &collide->r))
 251                 collided = eina_list_append(collided, b);
 252           }
 253
 254         collided = eina_list_free(collided);
 255         eina_mempool_free(mp, collide);
 256
 257         /* Modify 50% of all objects */
 258         i = request * 50 / 100;
 259         for (; i > 0; --i)
 260           {
 261              b = eina_list_data_get(eina_list_last(objects));
 262              objects = eina_list_remove_list(objects, eina_list_last(objects));
 263
 264              b->r.x = (rand() * WIDTH) / RAND_MAX;
 265              b->r.y = (rand() * HEIGHT) / RAND_MAX;
 266              b->r.w = (rand() * WIDTH / 3) / RAND_MAX;
 267              b->r.h = (rand() * HEIGHT / 3) / RAND_MAX;
 268
 269              eina_quadtree_change(b->item);
 270
 271              objects = eina_list_prepend(objects, b);
 272              changed = eina_list_append(changed, b);
 273           }
 274
 275         /* Emulating the render loop by colliding all modified
 276            object with all intersecting object */
 277         EINA_LIST_FREE(changed, b)
 278         {
 279            possibility = eina_quadtree_collide(q,
 280                                                b->r.x, b->r.y, b->r.w, b->r.h);
 281            while (possibility)
 282              {
 283                 collide = eina_quadtree_object(possibility);
 284                 possibility = possibility->next;
 285
 286                 if (collide != b &&
 287                     eina_rectangles_intersect(&b->r, &collide->r))
 288                    collided = eina_list_append(collided, collide);
 289              }
 290
 291            collided = eina_list_append(collided, b);
 292         }
 293
 294         /* Ok, we compute it, now it's done */
 295         collided = eina_list_free(collided);
 296      }
 297
 298    EINA_LIST_FREE(objects, b)
 299    {
 300       eina_quadtree_del(b->item);
 301       eina_mempool_free(mp, b);
 302    }
 303
 304    eina_mempool_del(mp);
 305
 306    eina_quadtree_free(q);
 307
 308    eina_shutdown();
 309 }
 310
 311 void
 312 eina_bench_quadtree(Eina_Benchmark *bench)
 313 {
 314    eina_benchmark_register(bench, "collide-all",
 315                            EINA_BENCHMARK(eina_bench_render_loop),
 316                            100, 1500, 50);
 317    eina_benchmark_register(bench, "collide-quad-tree",
 318                            EINA_BENCHMARK(eina_bench_quadtree_render_loop),
 319                            100, 1500, 50);
 320 }