diff options
Diffstat (limited to 'src/tests/eina_bench_quad.c')
| -rw-r--r-- | src/tests/eina_bench_quad.c | 318 |
1 files changed, 318 insertions, 0 deletions
diff --git a/src/tests/eina_bench_quad.c b/src/tests/eina_bench_quad.c new file mode 100644 index 0000000..76d6667 --- /dev/null +++ b/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); +} |