diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/lib/eina_tiler.c | 1276 |
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 */ | ||
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 | EINA_MAGIC_CHECK_TILER(t); | ||
1131 | _splitter_del(t); | ||
1132 | free(t); | ||
1133 | } | ||
1134 | |||
1135 | EAPI 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 | |||
1146 | EAPI 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 | |||
1164 | EAPI 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 | |||
1182 | EAPI void eina_tiler_clear(Eina_Tiler *t) | ||
1183 | { | ||
1184 | EINA_MAGIC_CHECK_TILER(t); | ||
1185 | _splitter_clear(t); | ||
1186 | } | ||
1187 | |||
1188 | |||
1189 | EAPI 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 | |||
1227 | struct _Eina_Tile_Grid_Slicer_Iterator | ||
1228 | { | ||
1229 | Eina_Iterator iterator; | ||
1230 | Eina_Tile_Grid_Slicer priv; | ||
1231 | }; | ||
1232 | |||
1233 | typedef struct _Eina_Tile_Grid_Slicer_Iterator Eina_Tile_Grid_Slicer_Iterator; | ||
1234 | |||
1235 | static void | ||
1236 | eina_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 | |||
1242 | static Eina_Bool | ||
1243 | eina_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 | |||
1250 | EAPI Eina_Iterator * | ||
1251 | eina_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 | } | ||