aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/lib/eina_tiler.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/lib/eina_tiler.c')
-rw-r--r--libraries/eina/src/lib/eina_tiler.c1276
1 files changed, 1276 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_tiler.c b/libraries/eina/src/lib/eina_tiler.c
new file mode 100644
index 0000000..69b944e
--- /dev/null
+++ b/libraries/eina/src/lib/eina_tiler.c
@@ -0,0 +1,1276 @@
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 */
42typedef struct list_node list_node_t;
43typedef struct list list_t;
44typedef struct rect rect_t;
45typedef struct rect_node rect_node_t;
46
47struct list_node
48{
49 struct list_node *next;
50};
51
52struct list
53{
54 struct list_node *head;
55 struct list_node *tail;
56};
57
58struct 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
69struct rect_node
70{
71 struct list_node _lst;
72 struct rect rect;
73};
74
75typedef struct splitter
76{
77 Eina_Bool need_merge;
78 list_t rects;
79} splitter_t;
80
81typedef struct list_node_pool
82{
83 list_node_t *node;
84 int len;
85 int max;
86} list_node_pool_t;
87
88
89static const list_node_t list_node_zeroed = { NULL };
90static const list_t list_zeroed = { NULL, NULL };
91static list_node_pool_t list_node_pool = { NULL, 0, 1024 };
92
93
94typedef 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
103struct _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 */
134static 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
148static inline list_node_t *
149rect_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
166static 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
185static 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
199static 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
210static 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
222static 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
252static 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
315static 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
387enum
388{
389 SPLIT_FUZZY_ACTION_NONE,
390 SPLIT_FUZZY_ACTION_SPLIT,
391 SPLIT_FUZZY_ACTION_MERGE
392};
393
394static 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
471static 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
491static 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
507static 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
520static 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
525static 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
554static inline list_node_t *
555rect_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
577static 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
585static 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
601static 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
654static 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
724static list_node_t *
725rect_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
872static 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
909static 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
965static 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
987static inline void _splitter_new(Eina_Tiler *t)
988{
989 t->splitter.rects = list_zeroed;
990 t->splitter.need_merge = EINA_FALSE;
991}
992
993static inline void _splitter_del(Eina_Tiler *t)
994{
995 rect_list_clear(&t->splitter.rects);
996 rect_list_node_pool_flush();
997}
998
999static 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
1007static 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
1032static 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
1059static 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
1066static 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
1094static void *_iterator_get_container(Eina_Iterator_Tiler *it)
1095{
1096 EINA_MAGIC_CHECK_TILER_ITERATOR(it, NULL);
1097 return (void *)it->tiler;
1098}
1099
1100static 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
1114EAPI 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
1128EAPI void eina_tiler_free(Eina_Tiler *t)
1129{
1130 EINA_MAGIC_CHECK_TILER(t);
1131 _splitter_del(t);
1132 free(t);
1133}
1134
1135EAPI void eina_tiler_tile_size_set(Eina_Tiler *t, int w, int h)
1136{
1137 EINA_MAGIC_CHECK_TILER(t);
1138 if ((w <= 0) || (h <= 0))
1139 return;
1140
1141 t->tile.w = w;
1142 t->tile.h = h;
1143 _splitter_tile_size_set(t, w, h);
1144}
1145
1146EAPI Eina_Bool eina_tiler_rect_add(Eina_Tiler *t, const Eina_Rectangle *r)
1147{
1148 Eina_Rectangle tmp;
1149
1150 EINA_MAGIC_CHECK_TILER(t, EINA_FALSE);
1151 if ((r->w <= 0) || (r->h <= 0))
1152 return EINA_FALSE;
1153
1154 tmp = *r;
1155 if (eina_rectangle_intersection(&tmp, &t->area) == EINA_FALSE)
1156 return EINA_FALSE;
1157
1158 if ((tmp.w <= 0) || (tmp.h <= 0))
1159 return EINA_FALSE;
1160
1161 return _splitter_rect_add(t, &tmp);
1162}
1163
1164EAPI void eina_tiler_rect_del(Eina_Tiler *t, const Eina_Rectangle *r)
1165{
1166 Eina_Rectangle tmp;
1167
1168 EINA_MAGIC_CHECK_TILER(t);
1169 if ((r->w <= 0) || (r->h <= 0))
1170 return;
1171
1172 tmp = *r;
1173 if (eina_rectangle_intersection(&tmp, &t->area) == EINA_FALSE)
1174 return;
1175
1176 if ((tmp.w <= 0) || (tmp.h <= 0))
1177 return;
1178
1179 _splitter_rect_del(t, &tmp);
1180}
1181
1182EAPI void eina_tiler_clear(Eina_Tiler *t)
1183{
1184 EINA_MAGIC_CHECK_TILER(t);
1185 _splitter_clear(t);
1186}
1187
1188
1189EAPI Eina_Iterator *eina_tiler_iterator_new(const Eina_Tiler *t)
1190{
1191 Eina_Iterator_Tiler *it;
1192
1193 EINA_MAGIC_CHECK_TILER(t, NULL);
1194
1195 it = calloc(1, sizeof (Eina_Iterator_Tiler));
1196 if (!it)
1197 return NULL;
1198
1199 it->tiler = t;
1200
1201 if (t->splitter.need_merge == EINA_TRUE)
1202 {
1203 list_t to_merge;
1204 splitter_t *sp;
1205
1206 sp = (splitter_t *)&(t->splitter);
1207 to_merge = t->splitter.rects;
1208 sp->rects = list_zeroed;
1209 rect_list_merge_rects(&sp->rects, &to_merge, FUZZ * FUZZ);
1210 sp->need_merge = 0;
1211 }
1212
1213 it->curr = it->tiler->splitter.rects.head;
1214
1215 it->iterator.version = EINA_ITERATOR_VERSION;
1216 it->iterator.next = FUNC_ITERATOR_NEXT(_iterator_next);
1217 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1218 _iterator_get_container);
1219 it->iterator.free = FUNC_ITERATOR_FREE(_iterator_free);
1220
1221 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1222 EINA_MAGIC_SET(it, EINA_MAGIC_TILER_ITERATOR);
1223
1224 return &it->iterator;
1225}
1226
1227struct _Eina_Tile_Grid_Slicer_Iterator
1228{
1229 Eina_Iterator iterator;
1230 Eina_Tile_Grid_Slicer priv;
1231};
1232
1233typedef struct _Eina_Tile_Grid_Slicer_Iterator Eina_Tile_Grid_Slicer_Iterator;
1234
1235static void
1236eina_tile_grid_slicer_iterator_free(Eina_Tile_Grid_Slicer_Iterator *it)
1237{
1238 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_NONE);
1239 free(it);
1240}
1241
1242static Eina_Bool
1243eina_tile_grid_slicer_iterator_next(Eina_Tile_Grid_Slicer_Iterator *it,
1244 void **data)
1245{
1246 return eina_tile_grid_slicer_next
1247 (&it->priv, (const Eina_Tile_Grid_Info **)data);
1248}
1249
1250EAPI Eina_Iterator *
1251eina_tile_grid_slicer_iterator_new(int x,
1252 int y,
1253 int w,
1254 int h,
1255 int tile_w,
1256 int tile_h)
1257{
1258 Eina_Tile_Grid_Slicer_Iterator *it;
1259
1260 it = calloc(1, sizeof(*it));
1261 if (!it)
1262 {
1263 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1264 return NULL;
1265 }
1266
1267 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1268
1269 it->iterator.version = EINA_ITERATOR_VERSION;
1270 it->iterator.next = FUNC_ITERATOR_NEXT(eina_tile_grid_slicer_iterator_next);
1271 it->iterator.free = FUNC_ITERATOR_FREE(eina_tile_grid_slicer_iterator_free);
1272
1273 eina_tile_grid_slicer_setup(&it->priv, x, y, w, h, tile_w, tile_h);
1274
1275 return &it->iterator;
1276}
generated by cgit v1.1 at 2024-07-18 09:00:30 +0000