aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/lib/eina_quadtree.c
diff options
context:
space:
mode:
authorDavid Walter Seikel2013-01-13 17:29:19 +1000
committerDavid Walter Seikel2013-01-13 17:29:19 +1000
commit07274513e984f0b5544586c74508ccd16e7dcafa (patch)
treeb32ff2a9136fbc1a4a6a0ed1e4d79cde0f5f16d9 /libraries/eina/src/lib/eina_quadtree.c
parentAdded Irrlicht 1.8, but without all the Windows binaries. (diff)
downloadSledjHamr-07274513e984f0b5544586c74508ccd16e7dcafa.zip
SledjHamr-07274513e984f0b5544586c74508ccd16e7dcafa.tar.gz
SledjHamr-07274513e984f0b5544586c74508ccd16e7dcafa.tar.bz2
SledjHamr-07274513e984f0b5544586c74508ccd16e7dcafa.tar.xz
Remove EFL, since it's been released now.
Diffstat (limited to 'libraries/eina/src/lib/eina_quadtree.c')
-rw-r--r--libraries/eina/src/lib/eina_quadtree.c935
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
48typedef struct _Eina_QuadTree_Root Eina_QuadTree_Root;
49
50static const char EINA_MAGIC_QUADTREE_STR[] = "Eina QuadTree";
51static const char EINA_MAGIC_QUADTREE_ROOT_STR[] = "Eina QuadTree Root";
52static 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
81struct _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
117struct _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
130struct _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
149static int _eina_quadtree_log_dom = -1;
150static Eina_Mempool *eina_quadtree_root_mp = NULL;
151static 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
164static 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
173static Eina_QuadTree_Root *
174eina_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
195static Eina_QuadTree_Root *
196eina_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
232static 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
343static 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
403static 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
486static 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
548static 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
585end:
586 object->root = NULL;
587}
588
589EAPI Eina_QuadTree *
590eina_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
617EAPI void
618eina_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
658EAPI Eina_QuadTree_Item *
659eina_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
696EAPI Eina_Bool
697eina_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
733EAPI Eina_Bool
734eina_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
756EAPI Eina_Bool
757eina_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
766EAPI Eina_Bool
767eina_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
783EAPI Eina_Inlist *
784eina_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
831EAPI void *
832eina_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
851EAPI void
852eina_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
865EAPI void
866eina_quadtree_cycle(Eina_QuadTree *q)
867{
868 EINA_MAGIC_CHECK_QUADTREE(q);
869
870 q->index = 0;
871}
872
873EAPI void
874eina_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
887Eina_Bool
888eina_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
923Eina_Bool
924eina_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