aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/lib/eina_rectangle.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/lib/eina_rectangle.c')
-rw-r--r--libraries/eina/src/lib/eina_rectangle.c568
1 files changed, 568 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_rectangle.c b/libraries/eina/src/lib/eina_rectangle.c
new file mode 100644
index 0000000..7f0a619
--- /dev/null
+++ b/libraries/eina/src/lib/eina_rectangle.c
@@ -0,0 +1,568 @@
1/* EINA - EFL data type library
2 * Copyright (C) 2007-2008 Cedric BAIL, Carsten Haitzler
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#ifdef HAVE_CONFIG_H
20# include "config.h"
21#endif
22
23#include <stdio.h>
24#include <stdlib.h>
25
26#ifdef HAVE_EVIL
27# include <Evil.h>
28#endif
29
30#include "eina_config.h"
31#include "eina_private.h"
32#include "eina_magic.h"
33#include "eina_inlist.h"
34#include "eina_mempool.h"
35#include "eina_list.h"
36#include "eina_trash.h"
37#include "eina_log.h"
38
39/* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
40#include "eina_safety_checks.h"
41#include "eina_rectangle.h"
42
43/*============================================================================*
44* Local *
45*============================================================================*/
46
47/**
48 * @cond LOCAL
49 */
50
51#define EINA_RECTANGLE_POOL_MAGIC 0x1578FCB0
52#define EINA_RECTANGLE_ALLOC_MAGIC 0x1578FCB1
53
54#define BUCKET_THRESHOLD 110
55
56typedef struct _Eina_Rectangle_Alloc Eina_Rectangle_Alloc;
57
58struct _Eina_Rectangle_Pool
59{
60 Eina_Inlist *head;
61 Eina_List *empty;
62 void *data;
63
64 Eina_Trash *bucket;
65 unsigned int bucket_count;
66
67 unsigned int references;
68 int w;
69 int h;
70
71 Eina_Bool sorted;
72 EINA_MAGIC
73};
74
75struct _Eina_Rectangle_Alloc
76{
77 EINA_INLIST;
78 Eina_Rectangle_Pool *pool;
79 EINA_MAGIC
80};
81
82#define EINA_MAGIC_CHECK_RECTANGLE_POOL(d) \
83 do { \
84 if (!EINA_MAGIC_CHECK((d), EINA_RECTANGLE_POOL_MAGIC)) { \
85 EINA_MAGIC_FAIL((d), EINA_RECTANGLE_POOL_MAGIC); } \
86 } while (0)
87
88#define EINA_MAGIC_CHECK_RECTANGLE_ALLOC(d) \
89 do { \
90 if (!EINA_MAGIC_CHECK((d), EINA_RECTANGLE_ALLOC_MAGIC)) { \
91 EINA_MAGIC_FAIL((d), EINA_RECTANGLE_ALLOC_MAGIC); } \
92 } while (0)
93
94static Eina_Mempool *_eina_rectangle_alloc_mp = NULL;
95static Eina_Mempool *_eina_rectangle_mp = NULL;
96
97static Eina_Trash *_eina_rectangles = NULL;
98static unsigned int _eina_rectangles_count = 0;
99static int _eina_rectangle_log_dom = -1;
100
101#ifdef ERR
102#undef ERR
103#endif
104#define ERR(...) EINA_LOG_DOM_ERR(_eina_rectangle_log_dom, __VA_ARGS__)
105
106#ifdef DBG
107#undef DBG
108#endif
109#define DBG(...) EINA_LOG_DOM_DBG(_eina_rectangle_log_dom, __VA_ARGS__)
110
111static int
112_eina_rectangle_cmp(const Eina_Rectangle *r1, const Eina_Rectangle *r2)
113{
114 return (r2->w * r2->h) - (r1->w * r1->h);
115}
116
117static Eina_List *
118_eina_rectangle_merge_list(Eina_List *empty, Eina_Rectangle *r)
119{
120 Eina_Rectangle *match;
121 Eina_List *l;
122 int xw;
123 int yh;
124
125 if (r->w == 0 || r->h == 0)
126 {
127 eina_rectangle_free(r);
128 return empty;
129 }
130
131start_again:
132 xw = r->x + r->w;
133 yh = r->y + r->h;
134
135 EINA_LIST_FOREACH(empty, l, match)
136 {
137 if (match->x == r->x && match->w == r->w
138 && (match->y == yh || r->y == match->y + match->h))
139 {
140 if (match->y > r->y)
141 match->y = r->y;
142
143 match->h += r->h;
144
145 eina_rectangle_free(r);
146
147 empty = eina_list_remove_list(empty, l);
148
149 r = match;
150
151 goto start_again;
152 }
153 else if (match->y == r->y && match->h == r->h
154 && (match->x == xw || r->x == match->x + match->w))
155 {
156 if (match->x > r->x)
157 match->x = r->x;
158
159 match->w += r->w;
160
161 eina_rectangle_free(r);
162
163 empty = eina_list_remove_list(empty, l);
164
165 r = match;
166
167 goto start_again;
168 }
169 }
170
171 return eina_list_append(empty, r);
172}
173
174static Eina_List *
175_eina_rectangle_empty_space_find(Eina_List *empty, int w, int h, int *x, int *y)
176{
177 Eina_Rectangle *r;
178 Eina_List *l;
179
180 EINA_LIST_FOREACH(empty, l, r)
181 {
182 if (r->w >= w && r->h >= h)
183 {
184 /* Remove l from empty */
185 empty = eina_list_remove_list(empty, l);
186 /* Remember x and y */
187 *x = r->x;
188 *y = r->y;
189 /* Split r in 2 rectangle if needed (only the empty one) and insert them */
190 if (r->w == w)
191 {
192 r->y += h;
193 r->h -= h;
194 }
195 else if (r->h == h)
196 {
197 r->x += w;
198 r->w -= w;
199 }
200 else
201 {
202 int rx1, ry1, rw1, rh1;
203 int x2, y2, w2, h2;
204
205 rx1 = r->x + w;
206 ry1 = r->y;
207 rw1 = r->w - w;
208 /* h1 could be h or r->h */
209 x2 = r->x;
210 y2 = r->y + h;
211 /* w2 could be w or r->w */
212 h2 = r->h - h;
213
214 if (rw1 * r->h > h2 * r->w)
215 {
216 rh1 = r->h;
217 w2 = w;
218 }
219 else
220 {
221 rh1 = h;
222 w2 = r->w;
223 }
224
225 EINA_RECTANGLE_SET(r, rx1, ry1, rw1, rh1);
226 empty = _eina_rectangle_merge_list(empty, r);
227
228 r = eina_rectangle_new(x2, y2, w2, h2);
229 }
230
231 if (r)
232 {
233 empty = _eina_rectangle_merge_list(empty, r); /* Return empty */
234
235 }
236
237 return empty;
238 }
239 }
240
241 *x = -1;
242 *y = -1;
243 return empty;
244}
245
246/**
247 * @endcond
248 */
249
250/*============================================================================*
251* Global *
252*============================================================================*/
253
254Eina_Bool
255eina_rectangle_init(void)
256{
257 const char *choice, *tmp;
258
259 _eina_rectangle_log_dom = eina_log_domain_register("eina_rectangle",
260 EINA_LOG_COLOR_DEFAULT);
261 if (_eina_rectangle_log_dom < 0)
262 {
263 EINA_LOG_ERR("Could not register log domain: eina_rectangle");
264 return EINA_FALSE;
265 }
266
267#ifdef EINA_DEFAULT_MEMPOOL
268 choice = "pass_through";
269#else
270 choice = "chained_mempool";
271#endif
272 tmp = getenv("EINA_MEMPOOL");
273 if (tmp && tmp[0])
274 choice = tmp;
275
276 _eina_rectangle_alloc_mp = eina_mempool_add
277 (choice, "rectangle-alloc", NULL,
278 sizeof(Eina_Rectangle_Alloc) + sizeof(Eina_Rectangle), 1024);
279 if (!_eina_rectangle_alloc_mp)
280 {
281 ERR("Mempool for rectangle cannot be allocated in rectangle init.");
282 goto init_error;
283 }
284
285 _eina_rectangle_mp = eina_mempool_add
286 (choice, "rectangle", NULL, sizeof(Eina_Rectangle), 256);
287 if (!_eina_rectangle_mp)
288 {
289 ERR("Mempool for rectangle cannot be allocated in rectangle init.");
290 goto init_error;
291 }
292
293 return EINA_TRUE;
294
295init_error:
296 eina_log_domain_unregister(_eina_rectangle_log_dom);
297 _eina_rectangle_log_dom = -1;
298
299 return EINA_FALSE;
300}
301
302Eina_Bool
303eina_rectangle_shutdown(void)
304{
305 Eina_Rectangle *del;
306
307 while ((del = eina_trash_pop(&_eina_rectangles)))
308 eina_mempool_free(_eina_rectangle_mp, del);
309 _eina_rectangles_count = 0;
310
311 eina_mempool_del(_eina_rectangle_alloc_mp);
312 eina_mempool_del(_eina_rectangle_mp);
313
314 eina_log_domain_unregister(_eina_rectangle_log_dom);
315 _eina_rectangle_log_dom = -1;
316
317 return EINA_TRUE;
318}
319
320/*============================================================================*
321* API *
322*============================================================================*/
323
324EAPI Eina_Rectangle *
325eina_rectangle_new(int x, int y, int w, int h)
326{
327 Eina_Rectangle *rect;
328
329 if (_eina_rectangles)
330 {
331 rect = eina_trash_pop(&_eina_rectangles);
332 _eina_rectangles_count--;
333 }
334 else
335 rect = eina_mempool_malloc(_eina_rectangle_mp, sizeof (Eina_Rectangle));
336
337 if (!rect)
338 return NULL;
339
340 EINA_RECTANGLE_SET(rect, x, y, w, h);
341
342 return rect;
343}
344
345EAPI void
346eina_rectangle_free(Eina_Rectangle *rect)
347{
348 EINA_SAFETY_ON_NULL_RETURN(rect);
349
350 if (_eina_rectangles_count > BUCKET_THRESHOLD)
351 eina_mempool_free(_eina_rectangle_mp, rect);
352 else
353 {
354 eina_trash_push(&_eina_rectangles, rect);
355 _eina_rectangles_count++;
356 }
357}
358
359EAPI Eina_Rectangle_Pool *
360eina_rectangle_pool_new(int w, int h)
361{
362 Eina_Rectangle_Pool *new;
363
364 new = malloc(sizeof (Eina_Rectangle_Pool));
365 if (!new)
366 return NULL;
367
368 new->head = NULL;
369 new->empty = eina_list_append(NULL, eina_rectangle_new(0, 0, w, h));
370 new->references = 0;
371 new->sorted = EINA_FALSE;
372 new->w = w;
373 new->h = h;
374 new->bucket = NULL;
375 new->bucket_count = 0;
376
377 EINA_MAGIC_SET(new, EINA_RECTANGLE_POOL_MAGIC);
378 DBG("pool=%p, size=(%d, %d)", new, w, h);
379
380 return new;
381}
382
383EAPI void
384eina_rectangle_pool_free(Eina_Rectangle_Pool *pool)
385{
386 Eina_Rectangle_Alloc *del;
387
388 EINA_SAFETY_ON_NULL_RETURN(pool);
389 DBG("pool=%p, size=(%d, %d), references=%u",
390 pool, pool->w, pool->h, pool->references);
391 while (pool->head)
392 {
393 del = (Eina_Rectangle_Alloc *)pool->head;
394
395 pool->head = (EINA_INLIST_GET(del))->next;
396
397 EINA_MAGIC_SET(del, EINA_MAGIC_NONE);
398 eina_mempool_free(_eina_rectangle_alloc_mp, del);
399 }
400
401 while (pool->bucket)
402 {
403 del = eina_trash_pop(&pool->bucket);
404 eina_mempool_free(_eina_rectangle_alloc_mp, del);
405 }
406
407 MAGIC_FREE(pool);
408}
409
410EAPI int
411eina_rectangle_pool_count(Eina_Rectangle_Pool *pool)
412{
413 EINA_SAFETY_ON_NULL_RETURN_VAL(pool, 0);
414 return pool->references;
415}
416
417EAPI Eina_Rectangle *
418eina_rectangle_pool_request(Eina_Rectangle_Pool *pool, int w, int h)
419{
420 Eina_Rectangle_Alloc *new;
421 Eina_Rectangle *rect;
422 int x;
423 int y;
424
425 EINA_SAFETY_ON_NULL_RETURN_VAL(pool, NULL);
426
427 DBG("pool=%p, size=(%d, %d), references=%u",
428 pool, pool->w, pool->h, pool->references);
429
430 if (w <= 0 || h <= 0)
431 return NULL;
432
433 if (w > pool->w || h > pool->h)
434 return NULL;
435
436 /* Sort empty if dirty */
437 if (pool->sorted)
438 {
439 pool->empty =
440 eina_list_sort(pool->empty, 0, EINA_COMPARE_CB(_eina_rectangle_cmp));
441 pool->sorted = EINA_TRUE;
442 }
443
444 pool->empty = _eina_rectangle_empty_space_find(pool->empty, w, h, &x, &y);
445 if (x == -1)
446 return NULL;
447
448 pool->sorted = EINA_FALSE;
449
450 if (pool->bucket_count > 0)
451 {
452 new = eina_trash_pop(&pool->bucket);
453 pool->bucket_count--;
454 }
455 else
456 new = eina_mempool_malloc(_eina_rectangle_alloc_mp,
457 sizeof (Eina_Rectangle_Alloc) +
458 sizeof (Eina_Rectangle));
459
460 if (!new)
461 return NULL;
462
463 rect = (Eina_Rectangle *)(new + 1);
464 eina_rectangle_coords_from(rect, x, y, w, h);
465
466 pool->head = eina_inlist_prepend(pool->head, EINA_INLIST_GET(new));
467 pool->references++;
468
469 new->pool = pool;
470
471 EINA_MAGIC_SET(new, EINA_RECTANGLE_ALLOC_MAGIC);
472 DBG("rect=%p pool=%p, size=(%d, %d), references=%u",
473 rect, pool, pool->w, pool->h, pool->references);
474
475 return rect;
476}
477
478EAPI void
479eina_rectangle_pool_release(Eina_Rectangle *rect)
480{
481 Eina_Rectangle_Alloc *era = ((Eina_Rectangle_Alloc *)rect) - 1;
482 Eina_Rectangle *r;
483
484 EINA_SAFETY_ON_NULL_RETURN(rect);
485
486 EINA_MAGIC_CHECK_RECTANGLE_ALLOC(era);
487 EINA_MAGIC_CHECK_RECTANGLE_POOL(era->pool);
488
489 DBG("rect=%p pool=%p, size=(%d, %d), references=%u",
490 rect, era->pool, era->pool->w, era->pool->h, era->pool->references);
491
492 era->pool->references--;
493 era->pool->head = eina_inlist_remove(era->pool->head, EINA_INLIST_GET(era));
494
495 r = eina_rectangle_new(rect->x, rect->y, rect->w, rect->h);
496 if (r)
497 {
498 era->pool->empty = _eina_rectangle_merge_list(era->pool->empty, r);
499 era->pool->sorted = EINA_FALSE;
500 }
501
502 if (era->pool->bucket_count < BUCKET_THRESHOLD)
503 {
504 Eina_Rectangle_Pool *pool;
505
506 pool = era->pool;
507
508 pool->bucket_count++;
509 eina_trash_push(&pool->bucket, era);
510 }
511 else
512 {
513 EINA_MAGIC_SET(era, EINA_MAGIC_NONE);
514 eina_mempool_free(_eina_rectangle_alloc_mp, era);
515 }
516}
517
518EAPI Eina_Rectangle_Pool *
519eina_rectangle_pool_get(Eina_Rectangle *rect)
520{
521 Eina_Rectangle_Alloc *era = ((Eina_Rectangle_Alloc *)rect) - 1;
522
523 EINA_SAFETY_ON_NULL_RETURN_VAL(rect, NULL);
524
525 EINA_MAGIC_CHECK_RECTANGLE_ALLOC(era);
526 EINA_MAGIC_CHECK_RECTANGLE_POOL(era->pool);
527
528 return era->pool;
529}
530
531EAPI void
532eina_rectangle_pool_data_set(Eina_Rectangle_Pool *pool, const void *data)
533{
534 EINA_MAGIC_CHECK_RECTANGLE_POOL(pool);
535 EINA_SAFETY_ON_NULL_RETURN(pool);
536
537 DBG("data=%p pool=%p, size=(%d, %d), references=%u",
538 data, pool, pool->w, pool->h, pool->references);
539
540 pool->data = (void *)data;
541}
542
543EAPI void *
544eina_rectangle_pool_data_get(Eina_Rectangle_Pool *pool)
545{
546 EINA_MAGIC_CHECK_RECTANGLE_POOL(pool);
547 EINA_SAFETY_ON_NULL_RETURN_VAL(pool, NULL);
548
549 return pool->data;
550}
551
552EAPI Eina_Bool
553eina_rectangle_pool_geometry_get(Eina_Rectangle_Pool *pool, int *w, int *h)
554{
555 if (!pool)
556 return EINA_FALSE;
557
558 EINA_MAGIC_CHECK_RECTANGLE_POOL(pool);
559 EINA_SAFETY_ON_NULL_RETURN_VAL(pool, EINA_FALSE);
560
561 if (w)
562 *w = pool->w;
563
564 if (h)
565 *h = pool->h;
566
567 return EINA_TRUE;
568}