From de230c00b7eeca451963224b006f0b6d3e3589af Mon Sep 17 00:00:00 2001 From: cedric Date: Fri, 30 Apr 2010 17:04:28 +0000 Subject: [PATCH] * eina: improve QuadTree API. git-svn-id: http://svn.enlightenment.org/svn/e/trunk/eina@48482 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- src/include/eina_quadtree.h | 8 +++-- src/lib/eina_quadtree.c | 76 ++++++++++++++++++++++++++++++++---------- src/tests/eina_bench.c | 14 ++++---- src/tests/eina_bench_quad.c | 41 +++++++++++++---------- src/tests/eina_test_quadtree.c | 71 ++++++++++++++++++++++++++------------- 5 files changed, 140 insertions(+), 70 deletions(-) diff --git a/src/include/eina_quadtree.h b/src/include/eina_quadtree.h index 14ebaca..3a4f661 100644 --- a/src/include/eina_quadtree.h +++ b/src/include/eina_quadtree.h @@ -21,7 +21,7 @@ #include "eina_config.h" -#include "eina_array.h" +#include "eina_inlist.h" typedef struct _Eina_QuadTree Eina_QuadTree; typedef struct _Eina_QuadTree_Item Eina_QuadTree_Item; @@ -39,6 +39,7 @@ EAPI Eina_QuadTree *eina_quadtree_new(size_t w, size_t h, Eina_Quad_Callback horizontal); EAPI void eina_quadtree_free(Eina_QuadTree *q); EAPI void eina_quadtree_resize(Eina_QuadTree *q, size_t w, size_t h); +EAPI void eina_quadtree_cycle(Eina_QuadTree *q); EAPI Eina_QuadTree_Item *eina_quadtree_add(Eina_QuadTree *q, const void *object); EAPI Eina_Bool eina_quadtree_del(Eina_QuadTree_Item *object); @@ -46,7 +47,8 @@ EAPI Eina_Bool eina_quadtree_change(Eina_QuadTree_Item *object); EAPI Eina_Bool eina_quadtree_hide(Eina_QuadTree_Item *object); EAPI Eina_Bool eina_quadtree_show(Eina_QuadTree_Item *object); -EAPI void eina_quadtree_collide(Eina_Array *result, Eina_QuadTree *q, - int x, int y, size_t w, size_t h); +EAPI Eina_Inlist *eina_quadtree_collide(Eina_QuadTree *q, + int x, int y, int w, int h); +EAPI void *eina_quadtree_object(Eina_Inlist *list); #endif diff --git a/src/lib/eina_quadtree.c b/src/lib/eina_quadtree.c index bcb10d8..7314916 100644 --- a/src/lib/eina_quadtree.c +++ b/src/lib/eina_quadtree.c @@ -94,6 +94,9 @@ struct _Eina_QuadTree Eina_Trash *root_trash; Eina_Mempool *root_mp; + Eina_Inlist *cached; + Eina_Rectangle target; + size_t index; struct { @@ -107,6 +110,7 @@ struct _Eina_QuadTree } geom; Eina_Bool resize : 1; + Eina_Bool lost : 1; }; struct _Eina_QuadTree_Root @@ -591,6 +595,8 @@ eina_quadtree_new(size_t w, size_t h, result->root_mp = eina_mempool_add("chained_mempool", "QuadTree Root", NULL, sizeof (Eina_QuadTree_Root), 32); + result->lost = EINA_TRUE; + EINA_MAGIC_SET(result, EINA_MAGIC_QUADTREE); return result; @@ -718,11 +724,19 @@ eina_quadtree_hide(Eina_QuadTree_Item *object) EAPI Eina_Bool eina_quadtree_show(Eina_QuadTree_Item *object) { + size_t index; + EINA_MAGIC_CHECK_QUADTREE_ITEM(object, EINA_FALSE); - object->index = object->quad->index++; + index = object->quad->index++; + if (object->index == index + && object->visible) + return EINA_TRUE; + + object->index = index; if (object->root) object->root->sorted = EINA_FALSE; + object->quad->lost = EINA_TRUE; if (object->visible) return EINA_TRUE; @@ -733,19 +747,12 @@ eina_quadtree_show(Eina_QuadTree_Item *object) return EINA_TRUE; } -EAPI void -eina_quadtree_collide(Eina_Array *result, - Eina_QuadTree *q, int x, int y, size_t w, size_t h) +EAPI Eina_Inlist * +eina_quadtree_collide(Eina_QuadTree *q, int x, int y, int w, int h) { - Eina_Inlist *head = NULL; - Eina_QuadTree_Item *current; - Eina_QuadTree_Item *p = NULL; Eina_Rectangle canvas; - Eina_Rectangle target; - Eina_Array_Iterator it; - unsigned int i; - EINA_MAGIC_CHECK_QUADTREE(q); + EINA_MAGIC_CHECK_QUADTREE(q, NULL); /* Now we need the tree to be up to date, so it's time */ if (q->resize) /* Full rebuild needed ! */ @@ -764,15 +771,40 @@ eina_quadtree_collide(Eina_Array *result, EINA_FALSE, &canvas); } - EINA_RECTANGLE_SET(&target, x, y, w, h); + if (q->target.x != x + || q->target.y != y + || q->target.w != w + || q->target.h != h) + { + DBG("new target"); + EINA_RECTANGLE_SET(&q->target, x, y, w, h); + q->lost = EINA_TRUE; + } + + if (q->lost) + { + DBG("computing collide"); + q->cached = _eina_quadtree_collide(NULL, q->root, + EINA_FALSE, &canvas, + &q->target); + } + + return q->cached; +} + +EAPI void * +eina_quadtree_object(Eina_Inlist *item) +{ + Eina_QuadTree_Item *qi; + + if (!item) return NULL; - DBG("colliding content"); - head = _eina_quadtree_collide(NULL, q->root, - EINA_FALSE, &canvas, - &target); + qi = EINA_INLIST_CONTAINER_GET(item, Eina_QuadTree_Item); + if (!qi) return NULL; - EINA_INLIST_FOREACH(head, current) - eina_array_push(result, current->object); + EINA_MAGIC_CHECK_QUADTREE_ITEM(qi, NULL); + + return (void*) qi->object; } EAPI void @@ -789,6 +821,14 @@ eina_quadtree_resize(Eina_QuadTree *q, size_t w, size_t h) q->geom.h = h; } +EAPI void +eina_quadtree_cycle(Eina_QuadTree *q) +{ + EINA_MAGIC_CHECK_QUADTREE(q); + + q->index = 0; +} + Eina_Bool eina_quadtree_init(void) { diff --git a/src/tests/eina_bench.c b/src/tests/eina_bench.c index 1371a7f..4479f8f 100644 --- a/src/tests/eina_bench.c +++ b/src/tests/eina_bench.c @@ -35,13 +35,13 @@ struct _Eina_Benchmark_Case }; static const Eina_Benchmark_Case etc[] = { - { "Hash", eina_bench_hash }, - { "Array vs List vs Inlist", eina_bench_array }, - { "Stringshare", eina_bench_stringshare }, - { "Convert", eina_bench_convert }, - { "Sort", eina_bench_sort }, - { "Mempool", eina_bench_mempool }, - { "Rectangle_Pool", eina_bench_rectangle_pool }, + /* { "Hash", eina_bench_hash }, */ + /* { "Array vs List vs Inlist", eina_bench_array }, */ + /* { "Stringshare", eina_bench_stringshare }, */ + /* { "Convert", eina_bench_convert }, */ + /* { "Sort", eina_bench_sort }, */ + /* { "Mempool", eina_bench_mempool }, */ + /* { "Rectangle_Pool", eina_bench_rectangle_pool }, */ { "Render Loop", eina_bench_quadtree }, { NULL, NULL } }; diff --git a/src/tests/eina_bench_quad.c b/src/tests/eina_bench_quad.c index 600926a..0a0702a 100644 --- a/src/tests/eina_bench_quad.c +++ b/src/tests/eina_bench_quad.c @@ -159,7 +159,7 @@ static void eina_bench_quadtree_render_loop(int request) { Eina_List *objects = NULL; - Eina_Array *possibility; + Eina_Inlist *possibility; Eina_Bench_Quad *b; Eina_QuadTree *q; Eina_Mempool *mp; @@ -189,15 +189,11 @@ eina_bench_quadtree_render_loop(int request) objects = eina_list_append(objects, b); } - possibility = eina_array_new(64); - for (j = 0; j < 100; ++j) { Eina_Bench_Quad *collide; Eina_List *changed = NULL; Eina_List *collided = NULL; - Eina_Array_Iterator it; - unsigned int k; /* Delete 25% of all objects */ i = request * 25 / 100; @@ -233,15 +229,20 @@ eina_bench_quadtree_render_loop(int request) (rand() * HEIGHT) / RAND_MAX, (rand() * WIDTH / 4) / RAND_MAX, (rand() * HEIGHT / 4) / RAND_MAX); - eina_quadtree_collide(possibility, q, - collide->r.x, collide->r.y, - collide->r.w, collide->r.h); - EINA_ARRAY_ITER_NEXT(possibility, k, b, it) - if (eina_rectangles_intersect(&b->r, &collide->r)) - collided = eina_list_append(collided, b); + 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); - eina_array_clean(possibility); /* Modify 50% of all objects */ i = request * 50 / 100; @@ -265,12 +266,16 @@ eina_bench_quadtree_render_loop(int request) object with all intersecting object */ EINA_LIST_FREE(changed, b) { - eina_quadtree_collide(possibility, q, - b->r.x, b->r.y, b->r.w, b->r.h); - EINA_ARRAY_ITER_NEXT(possibility, k, collide, it) - if (collide != b && eina_rectangles_intersect(&b->r, &collide->r)) - collided = eina_list_append(collided, collide); - eina_array_clean(possibility); + 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); } diff --git a/src/tests/eina_test_quadtree.c b/src/tests/eina_test_quadtree.c index 015792b..1e9bdbd 100644 --- a/src/tests/eina_test_quadtree.c +++ b/src/tests/eina_test_quadtree.c @@ -79,10 +79,9 @@ START_TEST(eina_quadtree_collision) int hidden[] = { 4, 5, 6, 8, 10 }; int show[] = { 0, 1, 2 }; Eina_QuadTree *q; - Eina_Array *result; + Eina_Inlist *head; Eina_Rectangle *r; - Eina_Array_Iterator it; - unsigned int j; + int count; int i; fail_if(!eina_init()); @@ -100,52 +99,76 @@ START_TEST(eina_quadtree_collision) fail_if(!eina_quadtree_show(objects[i].item)); } - result = eina_array_new(16); - fail_if(!result); + eina_quadtree_resize(q, 640, 480); for (i = 0; tests[i].count != -1; ++i) { - eina_quadtree_collide(result, q, - tests[i].r.x, tests[i].r.y, tests[i].r.w, tests[i].r.h); - fail_if(eina_array_count_get(result) != (unsigned int) tests[i].count); + head = eina_quadtree_collide(q, + tests[i].r.x, tests[i].r.y, + tests[i].r.w, tests[i].r.h); - EINA_ARRAY_ITER_NEXT(result, j, r, it) + count = 0; + while (head) { int k; + r = eina_quadtree_object(head); + for (k = 0; k < tests[i].count; ++k) { if (&objects[tests[i].result[k]].r == r) break; } fail_if(k == tests[i].count); - } - eina_array_clean(result); + head = head->next; + count++; + } + fail_if(count != tests[i].count); } - for (j = 0; j < sizeof (hidden) / sizeof (int); ++j) - eina_quadtree_hide(objects[hidden[j]].item); - for (j = 0; j < sizeof (show) / sizeof (int); ++j) - eina_quadtree_show(objects[show[j]].item); + for (i = 0; i < (int) (sizeof (hidden) / sizeof (int)); ++i) + eina_quadtree_hide(objects[hidden[i]].item); + for (i = 0; i < (int) (sizeof (show) / sizeof (int)); ++i) + eina_quadtree_show(objects[show[i]].item); - eina_quadtree_collide(result, q, - tests[1].r.x, tests[1].r.y, tests[1].r.w, tests[1].r.h); - fail_if(eina_array_count_get(result) != 3); + head = eina_quadtree_collide(q, + tests[1].r.x, tests[1].r.y, + tests[1].r.w, tests[1].r.h); - EINA_ARRAY_ITER_NEXT(result, j, r, it) - fail_if(r != &objects[tests[1].result[show[j]]].r); + count = 0; + while (head) + { + r = eina_quadtree_object(head); + + fail_if(r != &objects[tests[1].result[show[count]]].r); - eina_array_clean(result); + head = head->next; + count++; + } + fail_if(count != 3); + eina_quadtree_cycle(q); eina_quadtree_show(objects[4].item); eina_quadtree_show(objects[5].item); eina_quadtree_del(objects[5].item); eina_quadtree_change(objects[10].item); - eina_quadtree_collide(result, q, - tests[0].r.x, tests[0].r.y, tests[0].r.w, tests[0].r.h); - fail_if(eina_array_count_get(result) != 1); + eina_quadtree_resize(q, 641, 480); + + head = eina_quadtree_collide(q, + tests[0].r.x, tests[0].r.y, + tests[0].r.w, tests[0].r.h); + + count = 0; + while (head) + { + r = eina_quadtree_object(head); + + head = head->next; + count++; + } + fail_if(count != 1); eina_quadtree_free(q); -- 2.7.4