src/lib/eina_quadtree.c

   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), 32);
 917    eina_quadtree_root_mp = eina_mempool_add(choice, "QuadTree Root", NULL,
 918                                             sizeof (Eina_QuadTree_Root), 8);
 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