src/lib/eina_rectangle.c

   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
  56 typedef struct _Eina_Rectangle_Alloc Eina_Rectangle_Alloc;
  57
  58 struct _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
  75 struct _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
  94 static Eina_Mempool *_eina_rectangle_alloc_mp = NULL;
  95 static Eina_Mempool *_eina_rectangle_mp = NULL;
  96
  97 static Eina_Trash *_eina_rectangles = NULL;
  98 static unsigned int _eina_rectangles_count = 0;
  99 static 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
 111 static 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
 117 static 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
 131 start_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
 174 static 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
 254 Eina_Bool
 255 eina_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), 64);
 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), 32);
 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
 295 init_error:
 296    eina_log_domain_unregister(_eina_rectangle_log_dom);
 297    _eina_rectangle_log_dom = -1;
 298
 299    return EINA_FALSE;
 300 }
 301
 302 Eina_Bool
 303 eina_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
 324 EAPI Eina_Rectangle *
 325 eina_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
 345 EAPI void
 346 eina_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
 359 EAPI Eina_Rectangle_Pool *
 360 eina_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
 383 EAPI void
 384 eina_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
 410 EAPI int
 411 eina_rectangle_pool_count(Eina_Rectangle_Pool *pool)
 412 {
 413    EINA_SAFETY_ON_NULL_RETURN_VAL(pool, 0);
 414    return pool->references;
 415 }
 416
 417 EAPI Eina_Rectangle *
 418 eina_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
 478 EAPI void
 479 eina_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
 518 EAPI Eina_Rectangle_Pool *
 519 eina_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
 531 EAPI void
 532 eina_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
 543 EAPI void *
 544 eina_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
 552 EAPI Eina_Bool
 553 eina_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 }