diff options
Diffstat (limited to 'libraries/eina/src/lib/eina_quadtree.c')
-rw-r--r-- | libraries/eina/src/lib/eina_quadtree.c | 935 |
1 files changed, 0 insertions, 935 deletions
diff --git a/libraries/eina/src/lib/eina_quadtree.c b/libraries/eina/src/lib/eina_quadtree.c deleted file mode 100644 index daf03d0..0000000 --- a/libraries/eina/src/lib/eina_quadtree.c +++ /dev/null | |||
@@ -1,935 +0,0 @@ | |||
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 | /** | ||
20 | * @page tutorial_quadtree_page QuadTree Tutorial | ||
21 | * | ||
22 | * to be written... | ||
23 | * | ||
24 | */ | ||
25 | |||
26 | #ifdef HAVE_CONFIG_H | ||
27 | # include "config.h" | ||
28 | #endif | ||
29 | |||
30 | #include <stdlib.h> | ||
31 | #include <stdio.h> | ||
32 | |||
33 | #ifdef HAVE_EVIL | ||
34 | # include <Evil.h> | ||
35 | #endif | ||
36 | |||
37 | #include "eina_quadtree.h" | ||
38 | #include "eina_magic.h" | ||
39 | #include "eina_mempool.h" | ||
40 | #include "eina_list.h" | ||
41 | #include "eina_inlist.h" | ||
42 | #include "eina_trash.h" | ||
43 | #include "eina_log.h" | ||
44 | #include "eina_rectangle.h" | ||
45 | |||
46 | #include "eina_private.h" | ||
47 | |||
48 | typedef struct _Eina_QuadTree_Root Eina_QuadTree_Root; | ||
49 | |||
50 | static const char EINA_MAGIC_QUADTREE_STR[] = "Eina QuadTree"; | ||
51 | static const char EINA_MAGIC_QUADTREE_ROOT_STR[] = "Eina QuadTree Root"; | ||
52 | static const char EINA_MAGIC_QUADTREE_ITEM_STR[] = "Eina QuadTree Item"; | ||
53 | |||
54 | #define EINA_MAGIC_CHECK_QUADTREE(d, ...) \ | ||
55 | do { \ | ||
56 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_QUADTREE)) \ | ||
57 | { \ | ||
58 | EINA_MAGIC_FAIL(d, EINA_MAGIC_QUADTREE); \ | ||
59 | return __VA_ARGS__; \ | ||
60 | } \ | ||
61 | } while(0); | ||
62 | |||
63 | #define EINA_MAGIC_CHECK_QUADTREE_ROOT(d, ...) \ | ||
64 | do { \ | ||
65 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_QUADTREE_ROOT)) \ | ||
66 | { \ | ||
67 | EINA_MAGIC_FAIL(d, EINA_MAGIC_QUADTREE_ROOT); \ | ||
68 | return __VA_ARGS__; \ | ||
69 | } \ | ||
70 | } while(0); | ||
71 | |||
72 | #define EINA_MAGIC_CHECK_QUADTREE_ITEM(d, ...) \ | ||
73 | do { \ | ||
74 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_QUADTREE_ITEM)) \ | ||
75 | { \ | ||
76 | EINA_MAGIC_FAIL(d, EINA_MAGIC_QUADTREE_ITEM); \ | ||
77 | return __VA_ARGS__; \ | ||
78 | } \ | ||
79 | } while(0); | ||
80 | |||
81 | struct _Eina_QuadTree | ||
82 | { | ||
83 | Eina_QuadTree_Root *root; | ||
84 | |||
85 | Eina_List *hidden; | ||
86 | |||
87 | size_t root_count; | ||
88 | size_t items_count; | ||
89 | |||
90 | Eina_Trash *items_trash; | ||
91 | Eina_Trash *root_trash; | ||
92 | |||
93 | Eina_Inlist *change; | ||
94 | Eina_Inlist *cached; | ||
95 | Eina_Rectangle target; | ||
96 | |||
97 | size_t index; | ||
98 | |||
99 | struct | ||
100 | { | ||
101 | Eina_Quad_Callback v; | ||
102 | Eina_Quad_Callback h; | ||
103 | } func; | ||
104 | |||
105 | struct | ||
106 | { | ||
107 | size_t w; | ||
108 | size_t h; | ||
109 | } geom; | ||
110 | |||
111 | Eina_Bool resize : 1; | ||
112 | Eina_Bool lost : 1; | ||
113 | |||
114 | EINA_MAGIC | ||
115 | }; | ||
116 | |||
117 | struct _Eina_QuadTree_Root | ||
118 | { | ||
119 | Eina_QuadTree_Root *parent; | ||
120 | Eina_QuadTree_Root *left; | ||
121 | Eina_QuadTree_Root *right; | ||
122 | |||
123 | Eina_List *both; | ||
124 | |||
125 | Eina_Bool sorted : 1; | ||
126 | |||
127 | EINA_MAGIC | ||
128 | }; | ||
129 | |||
130 | struct _Eina_QuadTree_Item | ||
131 | { | ||
132 | EINA_INLIST; | ||
133 | |||
134 | Eina_QuadTree *quad; | ||
135 | Eina_QuadTree_Root *root; | ||
136 | |||
137 | const void *object; | ||
138 | |||
139 | size_t index; | ||
140 | |||
141 | Eina_Bool change : 1; | ||
142 | Eina_Bool delete_me : 1; | ||
143 | Eina_Bool visible : 1; | ||
144 | Eina_Bool hidden : 1; | ||
145 | |||
146 | EINA_MAGIC | ||
147 | }; | ||
148 | |||
149 | static int _eina_quadtree_log_dom = -1; | ||
150 | static Eina_Mempool *eina_quadtree_root_mp = NULL; | ||
151 | static Eina_Mempool *_eina_quadtree_items_mp = NULL; | ||
152 | |||
153 | #ifdef ERR | ||
154 | #undef ERR | ||
155 | #endif | ||
156 | #define ERR(...) EINA_LOG_DOM_ERR(_eina_quadtree_log_dom, __VA_ARGS__) | ||
157 | |||
158 | #ifdef DBG | ||
159 | #undef DBG | ||
160 | #endif | ||
161 | #define DBG(...) EINA_LOG_DOM_DBG(_eina_quadtree_log_dom, __VA_ARGS__) | ||
162 | |||
163 | |||
164 | static int | ||
165 | _eina_quadtree_item_cmp(const void *a, const void *b) | ||
166 | { | ||
167 | const Eina_QuadTree_Item *i = a; | ||
168 | const Eina_QuadTree_Item *j = b; | ||
169 | |||
170 | return i->index - j->index; | ||
171 | } | ||
172 | |||
173 | static Eina_QuadTree_Root * | ||
174 | eina_quadtree_root_free(Eina_QuadTree *q, Eina_QuadTree_Root *root) | ||
175 | { | ||
176 | Eina_QuadTree_Item *item; | ||
177 | |||
178 | if (!root) | ||
179 | return NULL; | ||
180 | |||
181 | EINA_MAGIC_CHECK_QUADTREE_ROOT(root, NULL); | ||
182 | |||
183 | EINA_LIST_FREE(root->both, item) | ||
184 | eina_mempool_free(_eina_quadtree_items_mp, item); | ||
185 | |||
186 | root->left = eina_quadtree_root_free(q, root->left); | ||
187 | root->right = eina_quadtree_root_free(q, root->right); | ||
188 | |||
189 | EINA_MAGIC_SET(root, 0); | ||
190 | eina_mempool_free(eina_quadtree_root_mp, root); | ||
191 | |||
192 | return NULL; | ||
193 | } | ||
194 | |||
195 | static Eina_QuadTree_Root * | ||
196 | eina_quadtree_root_rebuild_pre(Eina_QuadTree *q, | ||
197 | Eina_Inlist **change, | ||
198 | Eina_QuadTree_Root *root) | ||
199 | { | ||
200 | Eina_QuadTree_Item *item; | ||
201 | |||
202 | if (!root) | ||
203 | return NULL; | ||
204 | |||
205 | EINA_LIST_FREE(root->both, item) | ||
206 | { | ||
207 | if (item->visible) | ||
208 | *change = eina_inlist_append(*change, EINA_INLIST_GET(item)); | ||
209 | else if (!item->hidden) | ||
210 | { | ||
211 | q->hidden = eina_list_append(q->hidden, item); | ||
212 | item->hidden = EINA_TRUE; | ||
213 | item->root = NULL; | ||
214 | } | ||
215 | } | ||
216 | |||
217 | root->left = eina_quadtree_root_rebuild_pre(q, change, root->left); | ||
218 | root->right = eina_quadtree_root_rebuild_pre(q, change, root->right); | ||
219 | |||
220 | EINA_MAGIC_SET(root, 0); | ||
221 | if (q->root_count > 50) | ||
222 | eina_mempool_free(eina_quadtree_root_mp, root); | ||
223 | else | ||
224 | { | ||
225 | eina_trash_push(&q->root_trash, root); | ||
226 | q->root_count++; | ||
227 | } | ||
228 | |||
229 | return NULL; | ||
230 | } | ||
231 | |||
232 | static size_t | ||
233 | _eina_quadtree_split(Eina_Inlist *objects, | ||
234 | Eina_QuadTree_Root *root, | ||
235 | Eina_Inlist **left, | ||
236 | Eina_Inlist **right, | ||
237 | Eina_Quad_Callback func, | ||
238 | int border, | ||
239 | int middle) | ||
240 | { | ||
241 | Eina_QuadTree_Item *object; | ||
242 | |||
243 | middle /= 2; | ||
244 | |||
245 | if (middle <= 4) | ||
246 | while (objects) | ||
247 | { | ||
248 | object = EINA_INLIST_CONTAINER_GET(objects, Eina_QuadTree_Item); | ||
249 | objects = objects->next; | ||
250 | |||
251 | object->change = EINA_FALSE; | ||
252 | if (!object->visible) | ||
253 | { | ||
254 | if (!object->hidden) | ||
255 | { | ||
256 | object->hidden = EINA_TRUE; | ||
257 | object->quad->hidden = eina_list_append( | ||
258 | object->quad->hidden, | ||
259 | object); | ||
260 | } | ||
261 | |||
262 | continue; | ||
263 | } | ||
264 | |||
265 | if (object->hidden) | ||
266 | { | ||
267 | object->hidden = EINA_FALSE; | ||
268 | object->quad->hidden = eina_list_remove(object->quad->hidden, | ||
269 | object); | ||
270 | } | ||
271 | |||
272 | if (!object->delete_me) | ||
273 | { | ||
274 | if (root->sorted) | ||
275 | root->both = eina_list_sorted_insert(root->both, | ||
276 | _eina_quadtree_item_cmp, | ||
277 | object); | ||
278 | else | ||
279 | root->both = eina_list_append(root->both, object); | ||
280 | |||
281 | object->root = root; | ||
282 | } | ||
283 | else | ||
284 | eina_quadtree_del(object); | ||
285 | } | ||
286 | else | ||
287 | while (objects) | ||
288 | { | ||
289 | object = EINA_INLIST_CONTAINER_GET(objects, Eina_QuadTree_Item); | ||
290 | objects = objects->next; | ||
291 | |||
292 | object->change = EINA_FALSE; | ||
293 | if (!object->visible) | ||
294 | { | ||
295 | if (!object->hidden) | ||
296 | { | ||
297 | object->hidden = EINA_TRUE; | ||
298 | object->quad->hidden = eina_list_append( | ||
299 | object->quad->hidden, | ||
300 | object); | ||
301 | } | ||
302 | |||
303 | continue; | ||
304 | } | ||
305 | |||
306 | if (object->hidden) | ||
307 | { | ||
308 | object->hidden = EINA_FALSE; | ||
309 | object->quad->hidden = eina_list_remove(object->quad->hidden, | ||
310 | object); | ||
311 | } | ||
312 | |||
313 | if (!object->delete_me) | ||
314 | { | ||
315 | switch (func(object->object, border + middle)) | ||
316 | { | ||
317 | case EINA_QUAD_LEFT: | ||
318 | *left = eina_inlist_append(*left, EINA_INLIST_GET(object)); | ||
319 | break; | ||
320 | |||
321 | case EINA_QUAD_RIGHT: | ||
322 | *right = | ||
323 | eina_inlist_append(*right, EINA_INLIST_GET(object)); | ||
324 | break; | ||
325 | |||
326 | case EINA_QUAD_BOTH: | ||
327 | root->both = eina_list_append(root->both, object); | ||
328 | object->root = root; | ||
329 | break; | ||
330 | |||
331 | default: | ||
332 | abort(); | ||
333 | } | ||
334 | } | ||
335 | else | ||
336 | eina_quadtree_del(object); | ||
337 | } | ||
338 | |||
339 | return middle; | ||
340 | } | ||
341 | |||
342 | |||
343 | static Eina_QuadTree_Root * | ||
344 | _eina_quadtree_update(Eina_QuadTree *q, Eina_QuadTree_Root *parent, | ||
345 | Eina_QuadTree_Root *root, Eina_Inlist *objects, | ||
346 | Eina_Bool direction, Eina_Rectangle *size) | ||
347 | { | ||
348 | Eina_Inlist *right = NULL; | ||
349 | Eina_Inlist *left = NULL; | ||
350 | size_t w2; | ||
351 | size_t h2; | ||
352 | |||
353 | if (!objects) | ||
354 | return root; | ||
355 | |||
356 | if (!root) | ||
357 | { | ||
358 | root = eina_trash_pop(&q->root_trash); | ||
359 | if (!root) | ||
360 | root = eina_mempool_malloc(eina_quadtree_root_mp, sizeof (Eina_QuadTree_Root)); | ||
361 | else | ||
362 | q->root_count--; | ||
363 | |||
364 | if (!root) | ||
365 | /* FIXME: NOT GOOD TIMING, WE ARE GOING TO LEAK MORE MEMORY */ | ||
366 | return NULL; | ||
367 | |||
368 | root->parent = parent; | ||
369 | root->both = NULL; | ||
370 | root->left = NULL; | ||
371 | root->right = NULL; | ||
372 | root->sorted = EINA_TRUE; | ||
373 | |||
374 | EINA_MAGIC_SET(root, EINA_MAGIC_QUADTREE_ROOT); | ||
375 | } | ||
376 | |||
377 | w2 = 0; | ||
378 | h2 = 0; | ||
379 | |||
380 | if (direction) | ||
381 | w2 = _eina_quadtree_split(objects, root, | ||
382 | &left, &right, | ||
383 | q->func.h, size->x, size->w); | ||
384 | else | ||
385 | h2 = _eina_quadtree_split(objects, root, | ||
386 | &left, &right, | ||
387 | q->func.v, size->y, size->h); | ||
388 | |||
389 | size->w -= w2; size->h -= h2; | ||
390 | root->left = _eina_quadtree_update(q, root, | ||
391 | root->left, left, | ||
392 | !direction, size); | ||
393 | size->x += w2; size->y += h2; | ||
394 | root->right = _eina_quadtree_update(q, root, | ||
395 | root->right, right, | ||
396 | !direction, size); | ||
397 | size->x -= w2; size->y -= h2; | ||
398 | size->w += w2; size->h += h2; | ||
399 | |||
400 | return root; | ||
401 | } | ||
402 | |||
403 | static Eina_Inlist * | ||
404 | _eina_quadtree_merge(Eina_Inlist *result, | ||
405 | Eina_List *both) | ||
406 | { | ||
407 | Eina_QuadTree_Item *item; | ||
408 | Eina_QuadTree_Item *b; | ||
409 | Eina_Inlist *moving; | ||
410 | |||
411 | if (!both) | ||
412 | return result; | ||
413 | |||
414 | if (!result) | ||
415 | { | ||
416 | Eina_List *l; | ||
417 | |||
418 | EINA_LIST_FOREACH(both, l, item) | ||
419 | if (item->visible) | ||
420 | result = eina_inlist_append(result, EINA_INLIST_GET(item)); | ||
421 | |||
422 | return result; | ||
423 | } | ||
424 | |||
425 | moving = result; | ||
426 | |||
427 | item = EINA_INLIST_CONTAINER_GET(moving, Eina_QuadTree_Item); | ||
428 | b = eina_list_data_get(both); | ||
429 | |||
430 | while (both && moving) | ||
431 | { | ||
432 | if (!b->visible) | ||
433 | { | ||
434 | both = eina_list_next(both); | ||
435 | b = eina_list_data_get(both); | ||
436 | continue; | ||
437 | } | ||
438 | |||
439 | if (_eina_quadtree_item_cmp(item, b) < 0) | ||
440 | { | ||
441 | /* moving is still lower than item, so we can continue to the next one. */ | ||
442 | moving = moving->next; | ||
443 | item = EINA_INLIST_CONTAINER_GET(moving, Eina_QuadTree_Item); | ||
444 | } | ||
445 | else | ||
446 | { | ||
447 | /* we just get above the limit of both, so insert it */ | ||
448 | result = eina_inlist_prepend_relative(result, | ||
449 | EINA_INLIST_GET(b), | ||
450 | moving); | ||
451 | both = eina_list_next(both); | ||
452 | b = eina_list_data_get(both); | ||
453 | } | ||
454 | } | ||
455 | |||
456 | item = EINA_INLIST_CONTAINER_GET(result->last, Eina_QuadTree_Item); | ||
457 | |||
458 | while (both) | ||
459 | { | ||
460 | b = eina_list_data_get(both); | ||
461 | if (b->visible) | ||
462 | { | ||
463 | if (_eina_quadtree_item_cmp(item, b) < 0) | ||
464 | break; | ||
465 | |||
466 | result = eina_inlist_prepend_relative(result, | ||
467 | EINA_INLIST_GET(b), | ||
468 | result->last); | ||
469 | } | ||
470 | |||
471 | both = eina_list_next(both); | ||
472 | } | ||
473 | |||
474 | while (both) | ||
475 | { | ||
476 | b = eina_list_data_get(both); | ||
477 | if (b->visible) | ||
478 | result = eina_inlist_append(result, EINA_INLIST_GET(b)); | ||
479 | |||
480 | both = eina_list_next(both); | ||
481 | } | ||
482 | |||
483 | return result; | ||
484 | } | ||
485 | |||
486 | static Eina_Inlist * | ||
487 | _eina_quadtree_collide(Eina_Inlist *result, | ||
488 | Eina_QuadTree_Root *root, | ||
489 | Eina_Bool direction, Eina_Rectangle *size, | ||
490 | Eina_Rectangle *target) | ||
491 | { | ||
492 | if (!root) | ||
493 | return result; | ||
494 | |||
495 | if (!root->sorted) | ||
496 | { | ||
497 | root->both = eina_list_sort(root->both, -1, _eina_quadtree_item_cmp); | ||
498 | root->sorted = EINA_TRUE; | ||
499 | } | ||
500 | |||
501 | result = _eina_quadtree_merge(result, root->both); | ||
502 | DBG("%p: %i in both for (%i, %i - %i, %i)", | ||
503 | root, eina_list_count(root->both), | ||
504 | size->x, size->y, size->w, size->h); | ||
505 | |||
506 | if (direction) | ||
507 | { | ||
508 | int middle = size->w / 2; | ||
509 | |||
510 | size->w -= middle; | ||
511 | if (eina_spans_intersect(size->x, size->w, target->x, target->w)) | ||
512 | result = _eina_quadtree_collide(result, root->left, | ||
513 | !direction, size, | ||
514 | target); | ||
515 | |||
516 | size->x += middle; | ||
517 | if (eina_spans_intersect(size->x, size->w, target->x, target->w)) | ||
518 | result = _eina_quadtree_collide(result, root->right, | ||
519 | !direction, size, | ||
520 | target); | ||
521 | |||
522 | size->x -= middle; | ||
523 | size->w += middle; | ||
524 | } | ||
525 | else | ||
526 | { | ||
527 | int middle = size->h / 2; | ||
528 | |||
529 | size->h -= middle; | ||
530 | if (eina_spans_intersect(size->y, size->h, target->y, target->h)) | ||
531 | result = _eina_quadtree_collide(result, root->left, | ||
532 | !direction, size, | ||
533 | target); | ||
534 | |||
535 | size->y += middle; | ||
536 | if (eina_spans_intersect(size->y, size->h, target->y, target->h)) | ||
537 | result = _eina_quadtree_collide(result, root->right, | ||
538 | !direction, size, | ||
539 | target); | ||
540 | |||
541 | size->y -= middle; | ||
542 | size->h += middle; | ||
543 | } | ||
544 | |||
545 | return result; | ||
546 | } | ||
547 | |||
548 | static void | ||
549 | _eina_quadtree_remove(Eina_QuadTree_Item *object) | ||
550 | { | ||
551 | if (!object->root) | ||
552 | return; | ||
553 | |||
554 | object->root->both = eina_list_remove(object->root->both, object); | ||
555 | if (object->root->both) | ||
556 | goto end; | ||
557 | |||
558 | if (object->root->left) | ||
559 | goto end; | ||
560 | |||
561 | if (object->root->right) | ||
562 | goto end; | ||
563 | |||
564 | /* The root is not useful anymore... */ | ||
565 | if (object->root->parent) | ||
566 | { | ||
567 | if (object->root->parent->left == object->root) | ||
568 | object->root->parent->left = NULL; | ||
569 | else | ||
570 | object->root->parent->right = NULL; | ||
571 | |||
572 | object->root->parent = NULL; | ||
573 | } | ||
574 | else | ||
575 | object->quad->root = NULL; | ||
576 | |||
577 | if (object->quad->root_count > 50) | ||
578 | eina_mempool_free(eina_quadtree_root_mp, object->root); | ||
579 | else | ||
580 | { | ||
581 | eina_trash_push(&object->quad->root_trash, object->root); | ||
582 | object->quad->root_count++; | ||
583 | } | ||
584 | |||
585 | end: | ||
586 | object->root = NULL; | ||
587 | } | ||
588 | |||
589 | EAPI Eina_QuadTree * | ||
590 | eina_quadtree_new(size_t w, size_t h, | ||
591 | Eina_Quad_Callback vertical, Eina_Quad_Callback horizontal) | ||
592 | { | ||
593 | Eina_QuadTree *result; | ||
594 | |||
595 | if (!vertical || !horizontal || h == 0 || w == 0) | ||
596 | return NULL; | ||
597 | |||
598 | result = calloc(1, sizeof (Eina_QuadTree)); | ||
599 | if (!result) | ||
600 | return NULL; | ||
601 | |||
602 | result->func.v = vertical; | ||
603 | result->func.h = horizontal; | ||
604 | |||
605 | result->geom.w = w; | ||
606 | result->geom.h = h; | ||
607 | |||
608 | result->change = NULL; | ||
609 | |||
610 | result->lost = EINA_TRUE; | ||
611 | |||
612 | EINA_MAGIC_SET(result, EINA_MAGIC_QUADTREE); | ||
613 | |||
614 | return result; | ||
615 | } | ||
616 | |||
617 | EAPI void | ||
618 | eina_quadtree_free(Eina_QuadTree *q) | ||
619 | { | ||
620 | Eina_QuadTree_Item *item; | ||
621 | |||
622 | if (!q) | ||
623 | return; | ||
624 | |||
625 | EINA_MAGIC_CHECK_QUADTREE(q); | ||
626 | |||
627 | while (q->change) | ||
628 | { | ||
629 | item = EINA_INLIST_CONTAINER_GET(q->change, Eina_QuadTree_Item); | ||
630 | q->change = q->change->next; | ||
631 | if (!item->hidden) | ||
632 | eina_mempool_free(_eina_quadtree_items_mp, item); | ||
633 | } | ||
634 | |||
635 | EINA_LIST_FREE(q->hidden, item) | ||
636 | eina_mempool_free(_eina_quadtree_items_mp, item); | ||
637 | |||
638 | eina_quadtree_root_free(q, q->root); | ||
639 | |||
640 | while (q->items_trash) | ||
641 | { | ||
642 | item = eina_trash_pop(&q->items_trash); | ||
643 | eina_mempool_free(_eina_quadtree_items_mp, item); | ||
644 | } | ||
645 | |||
646 | while (q->root_trash) | ||
647 | { | ||
648 | Eina_QuadTree_Root *root; | ||
649 | |||
650 | root = eina_trash_pop(&q->root_trash); | ||
651 | eina_mempool_free(eina_quadtree_root_mp, root); | ||
652 | } | ||
653 | |||
654 | EINA_MAGIC_SET(q, 0); | ||
655 | free(q); | ||
656 | } | ||
657 | |||
658 | EAPI Eina_QuadTree_Item * | ||
659 | eina_quadtree_add(Eina_QuadTree *q, const void *object) | ||
660 | { | ||
661 | Eina_QuadTree_Item *result; | ||
662 | |||
663 | EINA_MAGIC_CHECK_QUADTREE(q, NULL); | ||
664 | |||
665 | if (!object) | ||
666 | return NULL; | ||
667 | |||
668 | result = eina_trash_pop(&q->items_trash); | ||
669 | if (!result) | ||
670 | result = eina_mempool_malloc(_eina_quadtree_items_mp, sizeof (Eina_QuadTree_Item)); | ||
671 | else | ||
672 | q->items_count--; | ||
673 | |||
674 | if (!result) | ||
675 | return NULL; | ||
676 | |||
677 | result->quad = q; | ||
678 | result->root = NULL; | ||
679 | result->object = object; | ||
680 | |||
681 | result->index = q->index++; | ||
682 | |||
683 | result->change = EINA_TRUE; | ||
684 | result->delete_me = EINA_FALSE; | ||
685 | result->visible = EINA_TRUE; | ||
686 | result->hidden = EINA_FALSE; | ||
687 | |||
688 | EINA_MAGIC_SET(result, EINA_MAGIC_QUADTREE_ITEM); | ||
689 | |||
690 | /* Insertion is delayed until we really need to use it */ | ||
691 | q->change = eina_inlist_append(q->change, EINA_INLIST_GET(result)); | ||
692 | |||
693 | return result; | ||
694 | } | ||
695 | |||
696 | EAPI Eina_Bool | ||
697 | eina_quadtree_del(Eina_QuadTree_Item *object) | ||
698 | { | ||
699 | if (!object) | ||
700 | return EINA_FALSE; | ||
701 | |||
702 | EINA_MAGIC_CHECK_QUADTREE_ITEM(object, EINA_FALSE); | ||
703 | |||
704 | _eina_quadtree_remove(object); | ||
705 | |||
706 | if (object->change) | ||
707 | { | ||
708 | /* This object is still in the update array, delaying it's removal !*/ | ||
709 | object->delete_me = EINA_TRUE; | ||
710 | object->visible = EINA_TRUE; | ||
711 | return EINA_TRUE; | ||
712 | } | ||
713 | |||
714 | if (object->hidden) | ||
715 | { | ||
716 | object->quad->hidden = eina_list_remove(object->quad->hidden, object); | ||
717 | object->hidden = EINA_TRUE; | ||
718 | } | ||
719 | |||
720 | /* This object is not anymore inside the tree, we can remove it now !*/ | ||
721 | EINA_MAGIC_SET(object, 0); | ||
722 | if (object->quad->items_count > 256) | ||
723 | eina_mempool_free(_eina_quadtree_items_mp, object); | ||
724 | else | ||
725 | { | ||
726 | object->quad->items_count++; | ||
727 | eina_trash_push(&object->quad->items_trash, object); | ||
728 | } | ||
729 | |||
730 | return EINA_TRUE; | ||
731 | } | ||
732 | |||
733 | EAPI Eina_Bool | ||
734 | eina_quadtree_change(Eina_QuadTree_Item *object) | ||
735 | { | ||
736 | EINA_MAGIC_CHECK_QUADTREE_ITEM(object, EINA_FALSE); | ||
737 | |||
738 | if (object->delete_me || !object->visible) | ||
739 | return EINA_FALSE; | ||
740 | |||
741 | if (object->quad->resize) | ||
742 | return EINA_TRUE; | ||
743 | |||
744 | /* Delaying change until needed */ | ||
745 | if (!object->change) | ||
746 | object->quad->change = eina_inlist_append(object->quad->change, | ||
747 | EINA_INLIST_GET(object)); | ||
748 | |||
749 | object->change = EINA_TRUE; | ||
750 | |||
751 | _eina_quadtree_remove(object); | ||
752 | |||
753 | return EINA_TRUE; | ||
754 | } | ||
755 | |||
756 | EAPI Eina_Bool | ||
757 | eina_quadtree_hide(Eina_QuadTree_Item *object) | ||
758 | { | ||
759 | EINA_MAGIC_CHECK_QUADTREE_ITEM(object, EINA_FALSE); | ||
760 | |||
761 | object->visible = EINA_FALSE; | ||
762 | |||
763 | return EINA_TRUE; | ||
764 | } | ||
765 | |||
766 | EAPI Eina_Bool | ||
767 | eina_quadtree_show(Eina_QuadTree_Item *object) | ||
768 | { | ||
769 | EINA_MAGIC_CHECK_QUADTREE_ITEM(object, EINA_FALSE); | ||
770 | |||
771 | object->quad->lost = EINA_TRUE; | ||
772 | |||
773 | if (object->visible) | ||
774 | return EINA_TRUE; | ||
775 | |||
776 | object->visible = EINA_TRUE; | ||
777 | if (!object->change) | ||
778 | return eina_quadtree_change(object); | ||
779 | |||
780 | return EINA_TRUE; | ||
781 | } | ||
782 | |||
783 | EAPI Eina_Inlist * | ||
784 | eina_quadtree_collide(Eina_QuadTree *q, int x, int y, int w, int h) | ||
785 | { | ||
786 | Eina_Rectangle canvas; | ||
787 | |||
788 | EINA_MAGIC_CHECK_QUADTREE(q, NULL); | ||
789 | |||
790 | /* Now we need the tree to be up to date, so it's time */ | ||
791 | if (q->resize) /* Full rebuild needed ! */ | ||
792 | { | ||
793 | DBG("resizing quadtree"); | ||
794 | q->root = eina_quadtree_root_rebuild_pre(q, &q->change, q->root); | ||
795 | q->resize = EINA_FALSE; | ||
796 | } | ||
797 | |||
798 | EINA_RECTANGLE_SET(&canvas, 0, 0, q->geom.w, q->geom.h); | ||
799 | |||
800 | if (q->change) | ||
801 | { | ||
802 | DBG("updating quadtree content"); | ||
803 | q->root = _eina_quadtree_update(q, NULL, q->root, q->change, | ||
804 | EINA_FALSE, &canvas); | ||
805 | q->change = NULL; | ||
806 | q->lost = EINA_TRUE; | ||
807 | } | ||
808 | |||
809 | if (q->target.x != x | ||
810 | || q->target.y != y | ||
811 | || q->target.w != w | ||
812 | || q->target.h != h) | ||
813 | { | ||
814 | DBG("new target"); | ||
815 | EINA_RECTANGLE_SET(&q->target, x, y, w, h); | ||
816 | q->lost = EINA_TRUE; | ||
817 | } | ||
818 | |||
819 | if (q->lost) | ||
820 | { | ||
821 | DBG("computing collide"); | ||
822 | q->cached = _eina_quadtree_collide(NULL, q->root, | ||
823 | EINA_FALSE, &canvas, | ||
824 | &q->target); | ||
825 | q->lost = EINA_FALSE; | ||
826 | } | ||
827 | |||
828 | return q->cached; | ||
829 | } | ||
830 | |||
831 | EAPI void * | ||
832 | eina_quadtree_object(Eina_Inlist *item) | ||
833 | { | ||
834 | Eina_QuadTree_Item *qi; | ||
835 | |||
836 | if (!item) | ||
837 | return NULL; | ||
838 | |||
839 | qi = EINA_INLIST_CONTAINER_GET(item, Eina_QuadTree_Item); | ||
840 | if (!qi) | ||
841 | return NULL; | ||
842 | |||
843 | EINA_MAGIC_CHECK_QUADTREE_ITEM(qi, NULL); | ||
844 | |||
845 | if (!qi->visible) | ||
846 | return NULL; | ||
847 | |||
848 | return (void *)qi->object; | ||
849 | } | ||
850 | |||
851 | EAPI void | ||
852 | eina_quadtree_resize(Eina_QuadTree *q, size_t w, size_t h) | ||
853 | { | ||
854 | EINA_MAGIC_CHECK_QUADTREE(q); | ||
855 | |||
856 | if (q->geom.w == w | ||
857 | && q->geom.h == h) | ||
858 | return; | ||
859 | |||
860 | q->resize = EINA_TRUE; | ||
861 | q->geom.w = w; | ||
862 | q->geom.h = h; | ||
863 | } | ||
864 | |||
865 | EAPI void | ||
866 | eina_quadtree_cycle(Eina_QuadTree *q) | ||
867 | { | ||
868 | EINA_MAGIC_CHECK_QUADTREE(q); | ||
869 | |||
870 | q->index = 0; | ||
871 | } | ||
872 | |||
873 | EAPI void | ||
874 | eina_quadtree_increase(Eina_QuadTree_Item *object) | ||
875 | { | ||
876 | size_t tmp; | ||
877 | |||
878 | tmp = object->quad->index++; | ||
879 | if (object->index == tmp) | ||
880 | return; | ||
881 | |||
882 | object->index = tmp; | ||
883 | if (object->root) | ||
884 | object->root->sorted = EINA_FALSE; | ||
885 | } | ||
886 | |||
887 | Eina_Bool | ||
888 | eina_quadtree_init(void) | ||
889 | { | ||
890 | const char *choice, *tmp; | ||
891 | |||
892 | _eina_quadtree_log_dom = eina_log_domain_register("eina_quadtree", | ||
893 | EINA_LOG_COLOR_DEFAULT); | ||
894 | if (_eina_quadtree_log_dom < 0) | ||
895 | { | ||
896 | EINA_LOG_ERR("Could not register log domain: eina_quadtree"); | ||
897 | return EINA_FALSE; | ||
898 | } | ||
899 | |||
900 | #define EMS(n) eina_magic_string_static_set(n, n ## _STR) | ||
901 | EMS(EINA_MAGIC_QUADTREE); | ||
902 | EMS(EINA_MAGIC_QUADTREE_ROOT); | ||
903 | EMS(EINA_MAGIC_QUADTREE_ITEM); | ||
904 | #undef EMS | ||
905 | |||
906 | #ifdef EINA_DEFAULT_MEMPOOL | ||
907 | choice = "pass_through"; | ||
908 | #else | ||
909 | choice = "chained_mempool"; | ||
910 | #endif | ||
911 | tmp = getenv("EINA_MEMPOOL"); | ||
912 | if (tmp && tmp[0]) | ||
913 | choice = tmp; | ||
914 | |||
915 | _eina_quadtree_items_mp = eina_mempool_add(choice, "QuadTree Item", NULL, | ||
916 | sizeof (Eina_QuadTree_Item), 320); | ||
917 | eina_quadtree_root_mp = eina_mempool_add(choice, "QuadTree Root", NULL, | ||
918 | sizeof (Eina_QuadTree_Root), 32); | ||
919 | |||
920 | return EINA_TRUE; | ||
921 | } | ||
922 | |||
923 | Eina_Bool | ||
924 | eina_quadtree_shutdown(void) | ||
925 | { | ||
926 | eina_mempool_del(eina_quadtree_root_mp); | ||
927 | eina_mempool_del(_eina_quadtree_items_mp); | ||
928 | |||
929 | eina_log_domain_unregister(_eina_quadtree_log_dom); | ||
930 | _eina_quadtree_log_dom = -1; | ||
931 | return EINA_TRUE; | ||
932 | } | ||
933 | |||
934 | |||
935 | |||