src/lib/eina_tiler.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2007-2008 Gustavo Sverzut Barbieri, Jorge Luis Zapata Muga
   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 /* TODO
  20  * it is possible to have more than one tiler algorithm, but for now the
  21  * version Gustavo did is hardcoded here
  22  * http://blog.gustavobarbieri.com.br/2007/06/03/evas-now-using-rectangle-split-and-merge/
  23  */
  24
  25 #ifdef HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31
  32 #include "eina_config.h"
  33 #include "eina_private.h"
  34 #include "eina_tiler.h"
  35 #include "eina_error.h"
  36
  37 /*============================================================================*
  38 *                                  Local                                     *
  39 *============================================================================*/
  40
  41 /* The splitter data types */
  42 typedef struct list_node list_node_t;
  43 typedef struct list list_t;
  44 typedef struct rect rect_t;
  45 typedef struct rect_node rect_node_t;
  46
  47 struct list_node
  48 {
  49    struct list_node *next;
  50 };
  51
  52 struct list
  53 {
  54    struct list_node *head;
  55    struct list_node *tail;
  56 };
  57
  58 struct rect
  59 {
  60    short right;
  61    short bottom;
  62    short left;
  63    short top;
  64    short width;
  65    short height;
  66    int area;
  67 };
  68
  69 struct rect_node
  70 {
  71    struct list_node _lst;
  72    struct rect rect;
  73 };
  74
  75 typedef struct splitter
  76 {
  77    Eina_Bool need_merge;
  78    list_t rects;
  79 } splitter_t;
  80
  81 typedef struct list_node_pool
  82 {
  83    list_node_t *node;
  84    int len;
  85    int max;
  86 } list_node_pool_t;
  87
  88
  89 static const list_node_t list_node_zeroed = { NULL };
  90 static const list_t list_zeroed = { NULL, NULL };
  91 static list_node_pool_t list_node_pool = { NULL, 0, 1024 };
  92
  93
  94 typedef struct _Eina_Iterator_Tiler
  95 {
  96    Eina_Iterator iterator;
  97    const Eina_Tiler *tiler;
  98    list_node_t *curr;
  99    Eina_Rectangle r;
 100    EINA_MAGIC
 101 } Eina_Iterator_Tiler;
 102
 103 struct _Eina_Tiler
 104 {
 105    struct
 106    {
 107       int w, h;
 108    } tile;
 109    Eina_Rectangle area;
 110    EINA_MAGIC
 111    splitter_t splitter;
 112 };
 113
 114 #define EINA_MAGIC_CHECK_TILER(d, ...)                                  \
 115    do {                                                            \
 116         if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_TILER))             \
 117           {                                                       \
 118              EINA_MAGIC_FAIL(d, EINA_MAGIC_TILER);           \
 119              return __VA_ARGS__;                             \
 120           }                                                       \
 121      } while(0)
 122
 123
 124 #define EINA_MAGIC_CHECK_TILER_ITERATOR(d, ...)                         \
 125    do {                                                            \
 126         if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_TILER_ITERATOR))    \
 127           {                                                       \
 128              EINA_MAGIC_FAIL(d, EINA_MAGIC_TILER_ITERATOR);  \
 129              return __VA_ARGS__;                             \
 130           }                                                       \
 131      } while(0)
 132
 133 /* The Splitter algorithm */
 134 static inline void rect_init(rect_t *r, int x, int y, int w, int h)
 135 {
 136    r->area = w * h;
 137
 138    r->left = x;
 139    r->top = y;
 140
 141    r->right = x + w;
 142    r->bottom = y + h;
 143
 144    r->width = w;
 145    r->height = h;
 146 }
 147
 148 static inline list_node_t *
 149 rect_list_node_pool_get(void)
 150 {
 151    if (list_node_pool.node)
 152      {
 153         list_node_t *node;
 154
 155         node = list_node_pool.node;
 156         list_node_pool.node = node->next;
 157         list_node_pool.len--;
 158
 159         return node;
 160      }
 161    else
 162       return malloc(sizeof(rect_node_t));
 163 }
 164
 165
 166 static inline void rect_list_concat(list_t *rects, list_t *other)
 167 {
 168    if (!other->head)
 169       return;
 170
 171    if (rects->tail)
 172      {
 173         rects->tail->next = other->head;
 174         rects->tail = other->tail;
 175      }
 176    else
 177      {
 178         rects->head = other->head;
 179         rects->tail = other->tail;
 180      }
 181
 182    *other = list_zeroed;
 183 }
 184
 185 static inline void rect_list_append_node(list_t *rects, list_node_t *node)
 186 {
 187    if (rects->tail)
 188      {
 189         rects->tail->next = node;
 190         rects->tail = node;
 191      }
 192    else
 193      {
 194         rects->head = node;
 195         rects->tail = node;
 196      }
 197 }
 198
 199 static inline void rect_list_append(list_t *rects, const rect_t r)
 200 {
 201    rect_node_t *rect_node;
 202
 203    rect_node = (rect_node_t *)rect_list_node_pool_get();
 204    rect_node->rect = r;
 205    rect_node->_lst = list_node_zeroed;
 206
 207    rect_list_append_node(rects, (list_node_t *)rect_node);
 208 }
 209
 210 static inline void rect_list_append_xywh(list_t *rects,
 211                                          int x,
 212                                          int y,
 213                                          int w,
 214                                          int h)
 215 {
 216    rect_t r;
 217
 218    rect_init(&r, x, y, w, h);
 219    rect_list_append(rects, r);
 220 }
 221
 222 static inline void _calc_intra_rect_area(const rect_t a, const rect_t b,
 223                                          int *width, int *height)
 224 {
 225    int max_left, min_right, max_top, min_bottom;
 226
 227    if (a.left < b.left)
 228       max_left = b.left;
 229    else
 230       max_left = a.left;
 231
 232    if (a.right < b.right)
 233       min_right = a.right;
 234    else
 235       min_right = b.right;
 236
 237    *width = min_right - max_left;
 238
 239    if (a.top < b.top)
 240       max_top = b.top;
 241    else
 242       max_top = a.top;
 243
 244    if (a.bottom < b.bottom)
 245       min_bottom = a.bottom;
 246    else
 247       min_bottom = b.bottom;
 248
 249    *height = min_bottom - max_top;
 250 }
 251
 252 static inline void _split_strict(list_t *dirty, const rect_t current, rect_t r)
 253 {
 254    int h_1, h_2, w_1, w_2;
 255
 256    h_1 = current.top - r.top;
 257    h_2 = r.bottom - current.bottom;
 258    w_1 = current.left - r.left;
 259    w_2 = r.right - current.right;
 260
 261    if (h_1 > 0)
 262      {
 263         /*    .--.r (b)                .---.r2
 264          *    |  |                     |   |
 265          *  .-------.cur (a) .---.r    '---'
 266          *  | |  |  |     -> |   |   +
 267          *  | `--'  |        `---'
 268          *  `-------'
 269          */
 270         rect_list_append_xywh(dirty, r.left, r.top, r.width, h_1);
 271         r.height -= h_1;
 272         r.top = current.top;
 273      }
 274
 275    if (h_2 > 0)
 276      {
 277         /*  .-------.cur (a)
 278          *  | .---. |        .---.r
 279          *  | |   | |    ->  |   |
 280          *  `-------'        `---'   +  .---.r2
 281          *    |   |                     |   |
 282          *    `---'r (b)                `---'
 283          */
 284         rect_list_append_xywh(dirty, r.left, current.bottom, r.width,
 285                               h_2);
 286         r.height -= h_2;
 287      }
 288
 289    if (w_1 > 0)
 290       /* (b) r  .----.cur (a)
 291        *     .--|-.  |      .--.r2   .-.r
 292        *     |  | |  |  ->  |  |   + | |
 293        *     `--|-'  |      `--'     `-'
 294        *        `----'
 295        */
 296         rect_list_append_xywh(dirty, r.left, r.top, w_1, r.height);  /* not necessary to keep these, r (b) will be destroyed */
 297
 298    /* r.width -= w_1; */
 299    /* r.left = current.left; */
 300
 301    if (w_2 > 0)
 302       /*  .----.cur (a)
 303        *  |    |
 304        *  |  .-|--.r (b)  .-.r   .--.r2
 305        *  |  | |  |    -> | |  + |  |
 306        *  |  `-|--'       `-'    `--'
 307        *  `----'
 308        */
 309         rect_list_append_xywh(dirty, current.right, r.top, w_2,
 310                             r.height);  /* not necessary to keep this, r (b) will be destroyed */
 311
 312    /* r.width -= w_2; */
 313 }
 314
 315 static inline void _calc_intra_outer_rect_area(const rect_t a, const rect_t b,
 316                                                rect_t *intra, rect_t *outer)
 317 {
 318    int min_left, max_left, min_right, max_right;
 319    int min_top, max_top, min_bottom, max_bottom;
 320
 321    if (a.left < b.left)
 322      {
 323         max_left = b.left;
 324         min_left = a.left;
 325      }
 326    else
 327      {
 328         max_left = a.left;
 329         min_left = b.left;
 330      }
 331
 332    if (a.right < b.right)
 333      {
 334         min_right = a.right;
 335         max_right = b.right;
 336      }
 337    else
 338      {
 339         min_right = b.right;
 340         max_right = a.right;
 341      }
 342
 343    intra->left = max_left;
 344    intra->right = min_right;
 345    intra->width = min_right - max_left;
 346
 347    outer->left = min_left;
 348    outer->right = max_right;
 349    outer->width = max_right - min_left;
 350
 351    if (a.top < b.top)
 352      {
 353         max_top = b.top;
 354         min_top = a.top;
 355      }
 356    else
 357      {
 358         max_top = a.top;
 359         min_top = b.top;
 360      }
 361
 362    if (a.bottom < b.bottom)
 363      {
 364         min_bottom = a.bottom;
 365         max_bottom = b.bottom;
 366      }
 367    else
 368      {
 369         min_bottom = b.bottom;
 370         max_bottom = a.bottom;
 371      }
 372
 373    intra->top = max_top;
 374    intra->bottom = min_bottom;
 375    intra->height = min_bottom - max_top;
 376    if ((intra->width > 0) && (intra->height > 0))
 377       intra->area = intra->width * intra->height;
 378    else
 379       intra->area = 0;
 380
 381    outer->top = min_top;
 382    outer->bottom = max_bottom;
 383    outer->height = max_bottom - min_top;
 384    outer->area = outer->width * outer->height;
 385 }
 386
 387 enum
 388 {
 389    SPLIT_FUZZY_ACTION_NONE,
 390    SPLIT_FUZZY_ACTION_SPLIT,
 391    SPLIT_FUZZY_ACTION_MERGE
 392 };
 393
 394 static inline int _split_fuzzy(list_t *dirty, const rect_t a, rect_t *b)
 395 {
 396    int h_1, h_2, w_1, w_2, action;
 397
 398    h_1 = a.top - b->top;
 399    h_2 = b->bottom - a.bottom;
 400    w_1 = a.left - b->left;
 401    w_2 = b->right - a.right;
 402
 403    action = SPLIT_FUZZY_ACTION_NONE;
 404
 405    if (h_1 > 0)
 406      {
 407         /*    .--.r (b)                .---.r2
 408          *    |  |                     |   |
 409          *  .-------.cur (a) .---.r    '---'
 410          *  | |  |  |     -> |   |   +
 411          *  | `--'  |        `---'
 412          *  `-------'
 413          */
 414         rect_list_append_xywh(dirty, b->left, b->top, b->width, h_1);
 415         b->height -= h_1;
 416         b->top = a.top;
 417         action = SPLIT_FUZZY_ACTION_SPLIT;
 418      }
 419
 420    if (h_2 > 0)
 421      {
 422         /*  .-------.cur (a)
 423          *  | .---. |        .---.r
 424          *  | |   | |    ->  |   |
 425          *  `-------'        `---'   +  .---.r2
 426          *    |   |                     |   |
 427          *    `---'r (b)                `---'
 428          */
 429         rect_list_append_xywh(dirty, b->left, a.bottom, b->width, h_2);
 430         b->height -= h_2;
 431         action = SPLIT_FUZZY_ACTION_SPLIT;
 432      }
 433
 434    if (((w_1 > 0) || (w_2 > 0)) && (a.height == b->height))
 435       return SPLIT_FUZZY_ACTION_MERGE;
 436
 437    if (w_1 > 0)
 438      {
 439         /* (b)  r  .----.cur (a)
 440          *      .--|-.  |      .--.r2   .-.r
 441          *      |  | |  |  ->  |  |   + | |
 442          *      `--|-'  |      `--'     `-'
 443          *         `----'
 444          */
 445         rect_list_append_xywh(dirty, b->left, b->top, w_1, b->height);
 446         /* not necessary to keep these, r (b) will be destroyed */
 447         /* b->width -= w_1; */
 448         /* b->left = a.left; */
 449         action = SPLIT_FUZZY_ACTION_SPLIT;
 450      }
 451
 452    if (w_2 > 0)
 453      {
 454         /* .----.cur (a)
 455          * |    |
 456          * |  .-|--.r (b)  .-.r   .--.r2
 457          * |  | |  |    -> | |  + |  |
 458          * |  `-|--'       `-'    `--'
 459          * `----'
 460          */
 461         rect_list_append_xywh(dirty, a.right, b->top, w_2, b->height);
 462         /* not necessary to keep these, r (b) will be destroyed */
 463         /* b->width -= w_2; */
 464         action = SPLIT_FUZZY_ACTION_SPLIT;
 465      }
 466
 467    return action;
 468 }
 469
 470 #if 0
 471 static void rect_list_node_pool_set_max(int max)
 472 {
 473    int diff;
 474
 475    diff = list_node_pool.len - max;
 476    for (; diff > 0 && list_node_pool.node != NULL; diff--)
 477      {
 478         list_node_t *node;
 479
 480         node = list_node_pool.node;
 481         list_node_pool.node = node->next;
 482         list_node_pool.len--;
 483
 484         free(node);
 485      }
 486
 487    list_node_pool.max = max;
 488 }
 489 #endif
 490
 491 static void rect_list_node_pool_flush(void)
 492 {
 493    while (list_node_pool.node)
 494      {
 495         list_node_t *node;
 496
 497         node = list_node_pool.node;
 498         list_node_pool.node = node->next;
 499         list_node_pool.len--;
 500
 501         free(node);
 502      }
 503 }
 504
 505
 506
 507 static inline void rect_list_node_pool_put(list_node_t *node)
 508 {
 509    if (list_node_pool.len < list_node_pool.max)
 510      {
 511         node->next = list_node_pool.node;
 512         list_node_pool.node = node;
 513         list_node_pool.len++;
 514      }
 515    else
 516         free(node);
 517 }
 518
 519 #if 0
 520 static void rect_print(const rect_t r)
 521 {
 522         printf("<rect(%d, %d, %d, %d)>", r.left, r.top, r.width, r.height);
 523 }
 524
 525 static void rect_list_print(const list_t rects)
 526 {
 527    list_node_t *node;
 528    int len;
 529
 530    len = 0;
 531    for (node = rects.head; node != NULL; node = node->next)
 532       len++;
 533
 534         printf("[");
 535    for (node = rects.head; node != NULL; node = node->next)
 536      {
 537         rect_print(((rect_node_t *)node)->rect);
 538         if (node->next)
 539           {
 540                   putchar(',');
 541              if (len < 4)
 542                   putchar(' ');
 543              else
 544                {
 545                   putchar('\n');
 546                   putchar(' ');
 547                }
 548           }
 549      }
 550    printf("]\n");
 551 }
 552 #endif
 553
 554 static inline list_node_t *
 555 rect_list_unlink_next(list_t *rects, list_node_t *parent_node)
 556 {
 557    list_node_t *node;
 558
 559    if (parent_node)
 560      {
 561         node = parent_node->next;
 562         parent_node->next = node->next;
 563      }
 564    else
 565      {
 566         node = rects->head;
 567         rects->head = node->next;
 568      }
 569
 570    if (rects->tail == node)
 571       rects->tail = parent_node;
 572
 573    *node = list_node_zeroed;
 574    return node;
 575 }
 576
 577 static inline void rect_list_del_next(list_t *rects, list_node_t *parent_node)
 578 {
 579    list_node_t *node;
 580
 581    node = rect_list_unlink_next(rects, parent_node);
 582         rect_list_node_pool_put(node);
 583 }
 584
 585 static void rect_list_clear(list_t *rects)
 586 {
 587    list_node_t *node;
 588
 589    node = rects->head;
 590    while (node)
 591      {
 592         list_node_t *aux;
 593
 594         aux = node->next;
 595         rect_list_node_pool_put(node);
 596         node = aux;
 597      }
 598    *rects = list_zeroed;
 599 }
 600
 601 static void rect_list_del_split_strict(list_t *rects, const rect_t del_r)
 602 {
 603    list_t modified = list_zeroed;
 604    list_node_t *cur_node, *prev_node;
 605
 606    prev_node = NULL;
 607    cur_node = rects->head;
 608    while (cur_node)
 609      {
 610         int intra_width, intra_height;
 611         rect_t current;
 612
 613         current = ((rect_node_t *)cur_node)->rect;
 614
 615         _calc_intra_rect_area(del_r, current, &intra_width,
 616                               &intra_height);
 617         if ((intra_width <= 0) || (intra_height <= 0))
 618           {
 619              /*  .---.current      .---.del_r
 620               *  |   |             |   |
 621               *  `---+---.del_r    `---+---.current
 622               *      |   |             |   |
 623               *      `---'             `---'
 624               * no intersection, nothing to do
 625               */
 626              prev_node = cur_node;
 627              cur_node = cur_node->next;
 628           }
 629         else if ((intra_width == current.width) && (intra_height
 630                                                     == current.height))
 631           {
 632              /*  .-------.del_r
 633               *  | .---. |
 634               *  | |   | |
 635               *  | `---'current
 636               *  `-------'
 637               * current is contained, remove from rects
 638               */
 639              cur_node = cur_node->next;
 640              rect_list_del_next(rects, prev_node);
 641           }
 642         else
 643           {
 644              _split_strict(&modified, del_r, current);
 645              cur_node = cur_node->next;
 646              rect_list_del_next(rects, prev_node);
 647           }
 648      }
 649
 650    rect_list_concat(rects, &modified);
 651 }
 652
 653 #if 0
 654 static void rect_list_add_split_strict(list_t *rects, list_node_t *node)
 655 {
 656    list_t dirty = list_zeroed;
 657    list_t new_dirty = list_zeroed;
 658    list_node_t *cur_node;
 659
 660    if (!rects->head)
 661      {
 662         rect_list_append_node(rects, node);
 663         return;
 664      }
 665
 666         rect_list_append_node(&dirty, node);
 667
 668    cur_node = rects->head;
 669    while (dirty.head)
 670      {
 671         rect_t current;
 672
 673         if (!cur_node)
 674           {
 675              rect_list_concat(rects, &dirty);
 676              break;
 677           }
 678
 679         current = ((rect_node_t *)cur_node)->rect;
 680
 681         while (dirty.head)
 682           {
 683              int intra_width, intra_height;
 684              rect_t r;
 685
 686              r = ((rect_node_t *)dirty.head)->rect;
 687              _calc_intra_rect_area(r, current, &intra_width,
 688                                    &intra_height);
 689              if ((intra_width == r.width) && (intra_height
 690                                               == r.height))
 691                 /*  .-------.cur
 692                  *  | .---.r|
 693                  *  | |   | |
 694                  *  | `---' |
 695                  *  `-------'
 696                  */
 697                 rect_list_del_next(&dirty, NULL);
 698              else if ((intra_width <= 0) || (intra_height <= 0))
 699                {
 700                   /*  .---.cur     .---.r
 701                    *  |   |        |   |
 702                    *  `---+---.r   `---+---.cur
 703                    *      |   |        |   |
 704                    *      `---'        `---'
 705                    */
 706                   list_node_t *tmp;
 707                   tmp = rect_list_unlink_next(&dirty, NULL);
 708                   rect_list_append_node(&new_dirty, tmp);
 709                }
 710              else
 711                {
 712                   _split_strict(&new_dirty, current, r);
 713                   rect_list_del_next(&dirty, NULL);
 714                }
 715           }
 716         dirty = new_dirty;
 717         new_dirty = list_zeroed;
 718
 719         cur_node = cur_node->next;
 720      }
 721 }
 722 #endif
 723
 724 static list_node_t *
 725 rect_list_add_split_fuzzy(list_t *rects, list_node_t *node, int accepted_error)
 726 {
 727    list_t dirty = list_zeroed;
 728    list_node_t *old_last;
 729
 730    old_last = rects->tail;
 731
 732    if (!rects->head)
 733      {
 734         rect_list_append_node(rects, node);
 735         return old_last;
 736      }
 737
 738         rect_list_append_node(&dirty, node);
 739    while (dirty.head)
 740      {
 741         list_node_t *d_node, *cur_node, *prev_cur_node;
 742         int keep_dirty;
 743         rect_t r;
 744
 745         d_node = rect_list_unlink_next(&dirty, NULL);
 746         r = ((rect_node_t *)d_node)->rect;
 747
 748         prev_cur_node = NULL;
 749         cur_node = rects->head;
 750         keep_dirty = 1;
 751         while (cur_node)
 752           {
 753              int area, action;
 754              rect_t current, intra, outer;
 755
 756              current = ((rect_node_t *)cur_node)->rect;
 757
 758              _calc_intra_outer_rect_area(r, current, &intra, &outer);
 759              area = current.area + r.area - intra.area;
 760
 761              if ((intra.width == r.width) && (intra.height
 762                                               == r.height))
 763                {
 764                   /*  .-------.cur
 765                    *  | .---.r|
 766                    *  | |   | |
 767                    *  | `---' |
 768                    *  `-------'
 769                    */
 770                   keep_dirty = 0;
 771                   break;
 772                }
 773              else if ((intra.width == current.width)
 774                       && (intra.height == current.height))
 775                {
 776                   /* .-------.r
 777                    * | .---.cur
 778                    * | |   | |
 779                    * | `---' |
 780                    * `-------'
 781                    */
 782                   if (old_last == cur_node)
 783                      old_last = prev_cur_node;
 784
 785                   cur_node = cur_node->next;
 786                   rect_list_del_next(rects, prev_cur_node);
 787                }
 788              else if ((outer.area - area) <= accepted_error)
 789                {
 790                   /* .-----------. bounding box (outer)
 791                    * |.---. .---.|
 792                    * ||cur| |r  ||
 793                    * ||   | |   ||
 794                    * |`---' `---'|
 795                    * `-----------'
 796                    * merge them, remove both and add merged
 797                    */
 798                   rect_node_t *n;
 799
 800                   if (old_last == cur_node)
 801                      old_last = prev_cur_node;
 802
 803                   n = (rect_node_t *)rect_list_unlink_next(
 804                         rects, prev_cur_node);
 805                   n->rect = outer;
 806                        rect_list_append_node(&dirty, (list_node_t *)n);
 807
 808                   keep_dirty = 0;
 809                   break;
 810                }
 811              else if (intra.area <= accepted_error)
 812                {
 813                   /*  .---.cur     .---.r
 814                    *  |   |        |   |
 815                    *  `---+---.r   `---+---.cur
 816                    *      |   |        |   |
 817                    *      `---'        `---'
 818                    *  no split, no merge
 819                    */
 820                   prev_cur_node = cur_node;
 821                   cur_node = cur_node->next;
 822                }
 823              else
 824                {
 825                   /* split is required */
 826                   action = _split_fuzzy(&dirty, current, &r);
 827                   if (action == SPLIT_FUZZY_ACTION_MERGE)
 828                     {
 829 /* horizontal merge is possible: remove both, add merged */
 830                        rect_node_t *n;
 831
 832                        if (old_last == cur_node)
 833                           old_last = prev_cur_node;
 834
 835                        n
 836                           = (rect_node_t *)rect_list_unlink_next(
 837                                 rects,
 838                                 prev_cur_node);
 839
 840                        n->rect.left = outer.left;
 841                        n->rect.width = outer.width;
 842                        n->rect.right = outer.right;
 843                        n->rect.area = outer.width * r.height;
 844                        rect_list_append_node(&dirty,
 845                                              (list_node_t *)n);
 846                     }
 847                   else if (action == SPLIT_FUZZY_ACTION_NONE)
 848                     {
 849 /*
 850  * this rect check was totally useless,
 851  * should never happen
 852  */
 853 /* prev_cur_node = cur_node; */
 854 /* cur_node = cur_node->next; */
 855                        printf("Should not get here!\n");
 856                        abort();
 857                     }
 858
 859                   keep_dirty = 0;
 860                   break;
 861                }
 862           }
 863         if (EINA_UNLIKELY(keep_dirty))
 864            rect_list_append_node(rects, d_node);
 865         else
 866            rect_list_node_pool_put(d_node);
 867      }
 868
 869    return old_last;
 870 }
 871
 872 static inline void _calc_outer_rect_area(const rect_t a, const rect_t b,
 873                                          rect_t *outer)
 874 {
 875    int min_left, max_right;
 876    int min_top, max_bottom;
 877
 878    if (a.left < b.left)
 879       min_left = a.left;
 880    else
 881       min_left = b.left;
 882
 883    if (a.right < b.right)
 884       max_right = b.right;
 885    else
 886       max_right = a.right;
 887
 888    outer->left = min_left;
 889    outer->right = max_right;
 890    outer->width = max_right - min_left;
 891
 892    if (a.top < b.top)
 893       min_top = a.top;
 894    else
 895       min_top = b.top;
 896
 897    if (a.bottom < b.bottom)
 898       max_bottom = b.bottom;
 899    else
 900       max_bottom = a.bottom;
 901
 902    outer->top = min_top;
 903    outer->bottom = max_bottom;
 904    outer->height = max_bottom - min_top;
 905
 906    outer->area = outer->width * outer->height;
 907 }
 908
 909 static void rect_list_merge_rects(list_t *rects,
 910                                   list_t *to_merge,
 911                                   int accepted_error)
 912 {
 913    while (to_merge->head)
 914      {
 915         list_node_t *node, *parent_node;
 916         rect_t r1;
 917         int merged;
 918
 919         r1 = ((rect_node_t *)to_merge->head)->rect;
 920
 921         merged = 0;
 922         parent_node = NULL;
 923         node = rects->head;
 924         while (node)
 925           {
 926              rect_t r2, outer;
 927              int area;
 928
 929              r2 = ((rect_node_t *)node)->rect;
 930
 931              _calc_outer_rect_area(r1, r2, &outer);
 932              area = r1.area + r2.area; /* intra area is taken as 0 */
 933              if (outer.area - area <= accepted_error)
 934                {
 935                   /*
 936                    * remove both r1 and r2, create r3
 937                    * actually r3 uses r2 instance, saves memory
 938                    */
 939                   rect_node_t *n;
 940
 941                   n = (rect_node_t *)rect_list_unlink_next(
 942                         rects, parent_node);
 943                   n->rect = outer;
 944                   rect_list_append_node(to_merge,
 945                                         (list_node_t *)n);
 946                   merged = 1;
 947                   break;
 948                }
 949
 950              parent_node = node;
 951              node = node->next;
 952           }
 953
 954         if (!merged)
 955           {
 956              list_node_t *n;
 957              n = rect_list_unlink_next(to_merge, NULL);
 958                   rect_list_append_node(rects, n);
 959           }
 960         else
 961                   rect_list_del_next(to_merge, NULL);
 962      }
 963 }
 964
 965 static void rect_list_add_split_fuzzy_and_merge(list_t *rects,
 966                                                 list_node_t *node,
 967                                                 int split_accepted_error,
 968                                                 int merge_accepted_error)
 969 {
 970    list_node_t *n;
 971
 972    n = rect_list_add_split_fuzzy(rects, node, split_accepted_error);
 973    if (n && n->next)
 974      {
 975         list_t to_merge;
 976
 977         /* split list into 2 segments, already merged and to merge */
 978         to_merge.head = n->next;
 979         to_merge.tail = rects->tail;
 980         rects->tail = n;
 981         n->next = NULL;
 982
 983         rect_list_merge_rects(rects, &to_merge, merge_accepted_error);
 984      }
 985 }
 986
 987 static inline void _splitter_new(Eina_Tiler *t)
 988 {
 989    t->splitter.rects = list_zeroed;
 990    t->splitter.need_merge = EINA_FALSE;
 991 }
 992
 993 static inline void _splitter_del(Eina_Tiler *t)
 994 {
 995    rect_list_clear(&t->splitter.rects);
 996    rect_list_node_pool_flush();
 997 }
 998
 999 static inline void _splitter_tile_size_set(Eina_Tiler *t,
1000                                            int w __UNUSED__,
1001                                            int h __UNUSED__)
1002 {
1003    /* TODO are w and h used for something? */
1004    t->splitter.rects = list_zeroed;
1005 }
1006
1007 static inline Eina_Bool _splitter_rect_add(Eina_Tiler *t, Eina_Rectangle *rect)
1008 {
1009    rect_node_t *rn;
1010
1011    //printf("ACCOUNTING[1]: add_redraw: %4d,%4d %3dx%3d\n", x, y, w, h);
1012    rect->x >>= 1;
1013    rect->y >>= 1;
1014    rect->w += 2;
1015    rect->w >>= 1;
1016    rect->h += 2;
1017    rect->h >>= 1;
1018
1019    rn = (rect_node_t *)rect_list_node_pool_get();
1020    rn->_lst = list_node_zeroed;
1021    rect_init(&rn->rect, rect->x, rect->y, rect->w, rect->h);
1022    //printf("ACCOUNTING[2]: add_redraw: %4d,%4d %3dx%3d\n", x, y, w, h);
1023    //testing on my core2 duo desktop - fuzz of 32 or 48 is best.
1024 #define FUZZ 32
1025    rect_list_add_split_fuzzy_and_merge(&t->splitter.rects,
1026                                        (list_node_t *)rn,
1027                                        FUZZ * FUZZ,
1028                                        FUZZ * FUZZ);
1029    return EINA_TRUE;
1030 }
1031
1032 static inline void _splitter_rect_del(Eina_Tiler *t, Eina_Rectangle *rect)
1033 {
1034    rect_t r;
1035
1036    if (!t->splitter.rects.head)
1037       return;
1038
1039    rect->x += 1;
1040    rect->y += 1;
1041    rect->x >>= 1;
1042    rect->y >>= 1;
1043    rect->w -= 1;
1044    rect->w >>= 1;
1045    rect->h -= 1;
1046    rect->h >>= 1;
1047
1048    if ((rect->w <= 0) || (rect->h <= 0))
1049       return;
1050
1051    rect_init(&r, rect->x, rect->y, rect->w, rect->h);
1052    //fprintf(stderr, "ACCOUNTING: del_redraw: %4d,%4d %3dx%3d\n", x, y, w, h);
1053
1054    rect_list_del_split_strict(&t->splitter.rects, r);
1055    t->splitter.need_merge = EINA_TRUE;
1056    return;
1057 }
1058
1059 static inline void _splitter_clear(Eina_Tiler *t)
1060 {
1061    rect_list_clear(&t->splitter.rects);
1062    t->splitter.need_merge = EINA_FALSE;
1063 }
1064 /* end of splitter algorithm */
1065
1066 static Eina_Bool _iterator_next(Eina_Iterator_Tiler *it, void **data)
1067 {
1068    list_node_t *n;
1069
1070    for (n = it->curr; n; n = n->next)
1071      {
1072         rect_t cur;
1073
1074         cur = ((rect_node_t *)n)->rect;
1075
1076         it->r.x = cur.left << 1;
1077         it->r.y = cur.top << 1;
1078         it->r.w = cur.width << 1;
1079         it->r.h = cur.height << 1;
1080
1081         if (eina_rectangle_intersection(&it->r, &it->tiler->area) == EINA_FALSE)
1082            continue;
1083
1084         if ((it->r.w <= 0) || (it->r.h <= 0))
1085            continue;
1086
1087         it->curr = n->next;
1088         *(Eina_Rectangle **)data = &it->r;
1089         return EINA_TRUE;
1090      }
1091    return EINA_FALSE;
1092 }
1093
1094 static void *_iterator_get_container(Eina_Iterator_Tiler *it)
1095 {
1096    EINA_MAGIC_CHECK_TILER_ITERATOR(it, NULL);
1097    return (void *)it->tiler;
1098 }
1099
1100 static void _iterator_free(Eina_Iterator_Tiler *it)
1101 {
1102    EINA_MAGIC_CHECK_TILER_ITERATOR(it);
1103    free(it);
1104 }
1105
1106 /*============================================================================*
1107 *                                 Global                                     *
1108 *============================================================================*/
1109
1110 /*============================================================================*
1111 *                                   API                                      *
1112 *============================================================================*/
1113
1114 EAPI Eina_Tiler *eina_tiler_new(int w, int h)
1115 {
1116    Eina_Tiler *t;
1117
1118    t = calloc(1, sizeof(Eina_Tiler));
1119    t->area.w = w;
1120    t->area.h = h;
1121    t->tile.w = w;
1122    t->tile.h = h;
1123    EINA_MAGIC_SET(t, EINA_MAGIC_TILER);
1124    _splitter_new(t);
1125    return t;
1126 }
1127
1128 EAPI void eina_tiler_free(Eina_Tiler *t)
1129 {
1130    if (!t)
1131      return;
1132
1133    EINA_MAGIC_CHECK_TILER(t);
1134    _splitter_del(t);
1135    free(t);
1136 }
1137
1138 EAPI void eina_tiler_tile_size_set(Eina_Tiler *t, int w, int h)
1139 {
1140    EINA_MAGIC_CHECK_TILER(t);
1141    if ((w <= 0) || (h <= 0))
1142       return;
1143
1144    t->tile.w = w;
1145    t->tile.h = h;
1146    _splitter_tile_size_set(t, w, h);
1147 }
1148
1149 EAPI Eina_Bool eina_tiler_rect_add(Eina_Tiler *t, const Eina_Rectangle *r)
1150 {
1151    Eina_Rectangle tmp;
1152
1153    EINA_MAGIC_CHECK_TILER(t, EINA_FALSE);
1154    if ((r->w <= 0) || (r->h <= 0))
1155       return EINA_FALSE;
1156
1157    tmp = *r;
1158    if (eina_rectangle_intersection(&tmp, &t->area) == EINA_FALSE)
1159       return EINA_FALSE;
1160
1161    if ((tmp.w <= 0) || (tmp.h <= 0))
1162       return EINA_FALSE;
1163
1164    return _splitter_rect_add(t, &tmp);
1165 }
1166
1167 EAPI void eina_tiler_rect_del(Eina_Tiler *t, const Eina_Rectangle *r)
1168 {
1169    Eina_Rectangle tmp;
1170
1171    EINA_MAGIC_CHECK_TILER(t);
1172    if ((r->w <= 0) || (r->h <= 0))
1173       return;
1174
1175    tmp = *r;
1176    if (eina_rectangle_intersection(&tmp, &t->area) == EINA_FALSE)
1177       return;
1178
1179    if ((tmp.w <= 0) || (tmp.h <= 0))
1180       return;
1181
1182    _splitter_rect_del(t, &tmp);
1183 }
1184
1185 EAPI void eina_tiler_clear(Eina_Tiler *t)
1186 {
1187    EINA_MAGIC_CHECK_TILER(t);
1188    _splitter_clear(t);
1189 }
1190
1191
1192 EAPI Eina_Iterator *eina_tiler_iterator_new(const Eina_Tiler *t)
1193 {
1194    Eina_Iterator_Tiler *it;
1195
1196    EINA_MAGIC_CHECK_TILER(t, NULL);
1197
1198    it = calloc(1, sizeof (Eina_Iterator_Tiler));
1199    if (!it)
1200       return NULL;
1201
1202    it->tiler = t;
1203
1204    if (t->splitter.need_merge == EINA_TRUE)
1205      {
1206         list_t to_merge;
1207         splitter_t *sp;
1208
1209         sp = (splitter_t *)&(t->splitter);
1210         to_merge = t->splitter.rects;
1211         sp->rects = list_zeroed;
1212         rect_list_merge_rects(&sp->rects, &to_merge, FUZZ * FUZZ);
1213         sp->need_merge = 0;
1214      }
1215
1216    it->curr = it->tiler->splitter.rects.head;
1217
1218    it->iterator.version = EINA_ITERATOR_VERSION;
1219    it->iterator.next = FUNC_ITERATOR_NEXT(_iterator_next);
1220    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1221          _iterator_get_container);
1222    it->iterator.free = FUNC_ITERATOR_FREE(_iterator_free);
1223
1224    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1225    EINA_MAGIC_SET(it,            EINA_MAGIC_TILER_ITERATOR);
1226
1227    return &it->iterator;
1228 }
1229
1230 struct _Eina_Tile_Grid_Slicer_Iterator
1231 {
1232    Eina_Iterator iterator;
1233    Eina_Tile_Grid_Slicer priv;
1234 };
1235
1236 typedef struct _Eina_Tile_Grid_Slicer_Iterator Eina_Tile_Grid_Slicer_Iterator;
1237
1238 static void
1239 eina_tile_grid_slicer_iterator_free(Eina_Tile_Grid_Slicer_Iterator *it)
1240 {
1241    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE);
1242    free(it);
1243 }
1244
1245 static Eina_Bool
1246 eina_tile_grid_slicer_iterator_next(Eina_Tile_Grid_Slicer_Iterator *it,
1247                                     void **data)
1248 {
1249    return eina_tile_grid_slicer_next
1250              (&it->priv, (const Eina_Tile_Grid_Info **)data);
1251 }
1252
1253 EAPI Eina_Iterator *
1254 eina_tile_grid_slicer_iterator_new(int x,
1255                                    int y,
1256                                    int w,
1257                                    int h,
1258                                    int tile_w,
1259                                    int tile_h)
1260 {
1261    Eina_Tile_Grid_Slicer_Iterator *it;
1262
1263    it = calloc(1, sizeof(*it));
1264    if (!it)
1265      {
1266         eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1267         return NULL;
1268      }
1269
1270    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1271
1272    it->iterator.version = EINA_ITERATOR_VERSION;
1273    it->iterator.next = FUNC_ITERATOR_NEXT(eina_tile_grid_slicer_iterator_next);
1274    it->iterator.free = FUNC_ITERATOR_FREE(eina_tile_grid_slicer_iterator_free);
1275
1276    eina_tile_grid_slicer_setup(&it->priv, x, y, w, h, tile_w, tile_h);
1277
1278    return &it->iterator;
1279 }