src/lib/engines/common/evas_tiler.c

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