diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/tests/eina_bench_quad.c | 318 |
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 @@ | |||
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 "eina_main.h" | ||
23 | #include "eina_mempool.h" | ||
24 | #include "eina_rectangle.h" | ||
25 | #include "eina_quadtree.h" | ||
26 | #include "eina_list.h" | ||
27 | #include "eina_bench.h" | ||
28 | |||
29 | static void | ||
30 | eina_bench_render_loop(int request) | ||
31 | { | ||
32 | Eina_List *objects = NULL; | ||
33 | Eina_Rectangle *r; | ||
34 | int i; | ||
35 | int j; | ||
36 | |||
37 | eina_init(); | ||
38 | |||
39 | for (i = 0; i < request; ++i) | ||
40 | objects = eina_list_append(objects, | ||
41 | eina_rectangle_new((rand() * WIDTH) / RAND_MAX, | ||
42 | (rand() * | ||
43 | HEIGHT) / RAND_MAX, | ||
44 | (rand() * WIDTH / | ||
45 | 2) / RAND_MAX, | ||
46 | (rand() * HEIGHT / | ||
47 | 2) / RAND_MAX)); | ||
48 | |||
49 | for (j = 0; j < 100; ++j) | ||
50 | { | ||
51 | Eina_Rectangle *collide; | ||
52 | Eina_List *collided = NULL; | ||
53 | Eina_List *changed = NULL; | ||
54 | Eina_List *l; | ||
55 | |||
56 | /* Delete 25% of all objects */ | ||
57 | i = request * 25 / 100; | ||
58 | for (; i > 0; --i) | ||
59 | { | ||
60 | eina_rectangle_free(eina_list_data_get(objects)); | ||
61 | objects = eina_list_remove_list(objects, objects); | ||
62 | } | ||
63 | |||
64 | /* Add them back */ | ||
65 | i = request * 25 / 100; | ||
66 | for (; i > 0; --i) | ||
67 | { | ||
68 | r = eina_rectangle_new((rand() * WIDTH) / RAND_MAX, | ||
69 | (rand() * HEIGHT) / RAND_MAX, | ||
70 | (rand() * WIDTH / 3) / RAND_MAX, | ||
71 | (rand() * HEIGHT / 3) / RAND_MAX); | ||
72 | objects = eina_list_prepend(objects, r); | ||
73 | changed = eina_list_append(changed, r); | ||
74 | } | ||
75 | |||
76 | /* Do one collide search */ | ||
77 | collide = eina_rectangle_new((rand() * WIDTH) / RAND_MAX, | ||
78 | (rand() * HEIGHT) / RAND_MAX, | ||
79 | (rand() * WIDTH / 4) / RAND_MAX, | ||
80 | (rand() * HEIGHT / 4) / RAND_MAX); | ||
81 | EINA_LIST_FOREACH(objects, l, r) | ||
82 | if (eina_rectangles_intersect(r, collide)) | ||
83 | collided = eina_list_append(collided, r); | ||
84 | |||
85 | collided = eina_list_free(collided); | ||
86 | eina_rectangle_free(collide); | ||
87 | |||
88 | /* Modify 50% of all objects */ | ||
89 | i = request * 50 / 100; | ||
90 | for (; i > 0; --i) | ||
91 | { | ||
92 | r = eina_list_data_get(eina_list_last(objects)); | ||
93 | objects = eina_list_remove_list(objects, eina_list_last(objects)); | ||
94 | |||
95 | r->x = (rand() * WIDTH) / RAND_MAX; | ||
96 | r->y = (rand() * HEIGHT) / RAND_MAX; | ||
97 | r->w = (rand() * WIDTH / 3) / RAND_MAX; | ||
98 | r->h = (rand() * HEIGHT / 3) / RAND_MAX; | ||
99 | |||
100 | objects = eina_list_prepend(objects, r); | ||
101 | changed = eina_list_append(changed, r); | ||
102 | } | ||
103 | |||
104 | /* Emulating the render loop by colliding all modified | ||
105 | object with all intersecting object */ | ||
106 | EINA_LIST_FREE(changed, r) | ||
107 | { | ||
108 | EINA_LIST_FOREACH(objects, l, collide) | ||
109 | if (r != collide && eina_rectangles_intersect(collide, r)) | ||
110 | collided = eina_list_append(collided, collide); | ||
111 | |||
112 | collided = eina_list_append(collided, r); | ||
113 | } | ||
114 | |||
115 | /* Ok, we compute it, now it's done */ | ||
116 | collided = eina_list_free(collided); | ||
117 | } | ||
118 | |||
119 | EINA_LIST_FREE(objects, r) | ||
120 | eina_rectangle_free(r); | ||
121 | |||
122 | eina_shutdown(); | ||
123 | } | ||
124 | |||
125 | typedef struct _Eina_Bench_Quad Eina_Bench_Quad; | ||
126 | struct _Eina_Bench_Quad | ||
127 | { | ||
128 | Eina_Rectangle r; | ||
129 | Eina_QuadTree_Item *item; | ||
130 | }; | ||
131 | |||
132 | static Eina_Quad_Direction | ||
133 | _eina_bench_quadtree_vertical(const void *object, size_t middle) | ||
134 | { | ||
135 | const Eina_Bench_Quad *b = object; | ||
136 | size_t y; | ||
137 | |||
138 | y = b->r.y < 0 ? 0 : (size_t)b->r.y; | ||
139 | |||
140 | if (y + b->r.h < middle) | ||
141 | return EINA_QUAD_LEFT; | ||
142 | |||
143 | if (y > middle) | ||
144 | return EINA_QUAD_RIGHT; | ||
145 | |||
146 | return EINA_QUAD_BOTH; | ||
147 | } | ||
148 | |||
149 | static Eina_Quad_Direction | ||
150 | _eina_bench_quadtree_horizontal(const void *object, size_t middle) | ||
151 | { | ||
152 | const Eina_Bench_Quad *b = object; | ||
153 | size_t x; | ||
154 | |||
155 | x = b->r.x < 0 ? 0 : (size_t)b->r.x; | ||
156 | |||
157 | if (x + b->r.w < middle) | ||
158 | return EINA_QUAD_LEFT; | ||
159 | |||
160 | if (x > middle) | ||
161 | return EINA_QUAD_RIGHT; | ||
162 | |||
163 | return EINA_QUAD_BOTH; | ||
164 | } | ||
165 | |||
166 | static void | ||
167 | eina_bench_quadtree_render_loop(int request) | ||
168 | { | ||
169 | Eina_List *objects = NULL; | ||
170 | Eina_Inlist *possibility; | ||
171 | Eina_Bench_Quad *b; | ||
172 | Eina_QuadTree *q; | ||
173 | Eina_Mempool *mp; | ||
174 | int i; | ||
175 | int j; | ||
176 | |||
177 | eina_init(); | ||
178 | |||
179 | mp = eina_mempool_add("chained_mempool", "bench-quad", NULL, | ||
180 | sizeof (Eina_Bench_Quad), 320); | ||
181 | |||
182 | q = eina_quadtree_new(WIDTH, HEIGHT, | ||
183 | _eina_bench_quadtree_vertical, | ||
184 | _eina_bench_quadtree_horizontal); | ||
185 | |||
186 | /* Create requested object */ | ||
187 | for (i = 0; i < request; ++i) | ||
188 | { | ||
189 | b = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad)); | ||
190 | EINA_RECTANGLE_SET(&b->r, | ||
191 | (rand() * WIDTH) / RAND_MAX, | ||
192 | (rand() * HEIGHT) / RAND_MAX, | ||
193 | (rand() * WIDTH / 2) / RAND_MAX, | ||
194 | (rand() * HEIGHT / 2) / RAND_MAX); | ||
195 | b->item = eina_quadtree_add(q, b); | ||
196 | |||
197 | objects = eina_list_append(objects, b); | ||
198 | } | ||
199 | |||
200 | for (j = 0; j < 100; ++j) | ||
201 | { | ||
202 | Eina_Bench_Quad *collide; | ||
203 | Eina_List *changed = NULL; | ||
204 | Eina_List *collided = NULL; | ||
205 | |||
206 | /* Delete 25% of all objects */ | ||
207 | i = request * 25 / 100; | ||
208 | for (; i > 0; --i) | ||
209 | { | ||
210 | b = eina_list_data_get(objects); | ||
211 | eina_quadtree_del(b->item); | ||
212 | eina_mempool_free(mp, b); | ||
213 | |||
214 | objects = eina_list_remove_list(objects, objects); | ||
215 | } | ||
216 | |||
217 | /* Add them back */ | ||
218 | i = request * 25 / 100; | ||
219 | for (; i > 0; --i) | ||
220 | { | ||
221 | b = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad)); | ||
222 | EINA_RECTANGLE_SET(&b->r, | ||
223 | (rand() * WIDTH) / RAND_MAX, | ||
224 | (rand() * HEIGHT) / RAND_MAX, | ||
225 | (rand() * WIDTH / 3) / RAND_MAX, | ||
226 | (rand() * HEIGHT / 3) / RAND_MAX); | ||
227 | b->item = eina_quadtree_add(q, b); | ||
228 | |||
229 | objects = eina_list_prepend(objects, b); | ||
230 | changed = eina_list_append(changed, b); | ||
231 | } | ||
232 | |||
233 | /* Do one collide search */ | ||
234 | collide = eina_mempool_malloc(mp, sizeof (Eina_Bench_Quad)); | ||
235 | EINA_RECTANGLE_SET(&collide->r, | ||
236 | (rand() * WIDTH) / RAND_MAX, | ||
237 | (rand() * HEIGHT) / RAND_MAX, | ||
238 | (rand() * WIDTH / 4) / RAND_MAX, | ||
239 | (rand() * HEIGHT / 4) / RAND_MAX); | ||
240 | possibility = eina_quadtree_collide(q, | ||
241 | collide->r.x, collide->r.y, | ||
242 | collide->r.w, collide->r.h); | ||
243 | while (possibility) | ||
244 | { | ||
245 | b = eina_quadtree_object(possibility); | ||
246 | possibility = possibility->next; | ||
247 | |||
248 | if (eina_rectangles_intersect(&b->r, &collide->r)) | ||
249 | collided = eina_list_append(collided, b); | ||
250 | } | ||
251 | |||
252 | collided = eina_list_free(collided); | ||
253 | eina_mempool_free(mp, collide); | ||
254 | |||
255 | /* Modify 50% of all objects */ | ||
256 | i = request * 50 / 100; | ||
257 | for (; i > 0; --i) | ||
258 | { | ||
259 | b = eina_list_data_get(eina_list_last(objects)); | ||
260 | objects = eina_list_remove_list(objects, eina_list_last(objects)); | ||
261 | |||
262 | b->r.x = (rand() * WIDTH) / RAND_MAX; | ||
263 | b->r.y = (rand() * HEIGHT) / RAND_MAX; | ||
264 | b->r.w = (rand() * WIDTH / 3) / RAND_MAX; | ||
265 | b->r.h = (rand() * HEIGHT / 3) / RAND_MAX; | ||
266 | |||
267 | eina_quadtree_change(b->item); | ||
268 | |||
269 | objects = eina_list_prepend(objects, b); | ||
270 | changed = eina_list_append(changed, b); | ||
271 | } | ||
272 | |||
273 | /* Emulating the render loop by colliding all modified | ||
274 | object with all intersecting object */ | ||
275 | EINA_LIST_FREE(changed, b) | ||
276 | { | ||
277 | possibility = eina_quadtree_collide(q, | ||
278 | b->r.x, b->r.y, b->r.w, b->r.h); | ||
279 | while (possibility) | ||
280 | { | ||
281 | collide = eina_quadtree_object(possibility); | ||
282 | possibility = possibility->next; | ||
283 | |||
284 | if (collide != b && | ||
285 | eina_rectangles_intersect(&b->r, &collide->r)) | ||
286 | collided = eina_list_append(collided, collide); | ||
287 | } | ||
288 | |||
289 | collided = eina_list_append(collided, b); | ||
290 | } | ||
291 | |||
292 | /* Ok, we compute it, now it's done */ | ||
293 | collided = eina_list_free(collided); | ||
294 | } | ||
295 | |||
296 | EINA_LIST_FREE(objects, b) | ||
297 | { | ||
298 | eina_quadtree_del(b->item); | ||
299 | eina_mempool_free(mp, b); | ||
300 | } | ||
301 | |||
302 | eina_mempool_del(mp); | ||
303 | |||
304 | eina_quadtree_free(q); | ||
305 | |||
306 | eina_shutdown(); | ||
307 | } | ||
308 | |||
309 | void | ||
310 | eina_bench_quadtree(Eina_Benchmark *bench) | ||
311 | { | ||
312 | eina_benchmark_register(bench, "collide-all", | ||
313 | EINA_BENCHMARK(eina_bench_render_loop), | ||
314 | 100, 1500, 50); | ||
315 | eina_benchmark_register(bench, "collide-quad-tree", | ||
316 | EINA_BENCHMARK(eina_bench_quadtree_render_loop), | ||
317 | 100, 1500, 50); | ||
318 | } | ||