eina: add multiple logic for allocating rectangle from a pool.devs/cedric/pool

Some part in Evas does need a efficient way to allocate rectangle out
of a fixed size pool, like Evas GL texture allocation. The more rectangle
you can get out of the same atlas, the better the performance will be.
Until now we were using a simple guillotine descending algorithm.
  This patch add the support to other algorithm to give us a chance to
choose the best algorithm depending on the situation. We did identify
that both guillotine ascending or guillotine skyline are better than our
previous implementation.
  There is possibility to still improve skyline and a following patch
may just do so. The next improvement would be to make Evas GL engine
to use Eina rectangle pool.

Signed-off-by: Cedric BAIL <cedric.bail@samsung.com>

4 files changed, 189 insertions, 31 deletions

diff --git a/src/benchmarks/eina/eina_bench_rectangle_pool.c b/src/benchmarks/eina/eina_bench_rectangle_pool.c
index 96d4b1bf0a..2468e5918e 100644
--- a/src/benchmarks/eina/eina_bench_rectangle_pool.c
+++ b/src/benchmarks/eina/eina_bench_rectangle_pool.c
@@ -23,18 +23,24 @@
 #include "eina_bench.h"
 #include "Eina.h"
 
+#define W 1024
+#define H 512
+#define RW 64
+#define RH 64
+
 static void
-eina_bench_eina_rectangle_pool(int request)
+eina_bench_generic_packing_efficiency(int request, Eina_Rectangle_Packing type)
 {
    Eina_Rectangle_Pool *pool;
    Eina_Rectangle *rect;
-   Eina_List *list = NULL;
+   Eina_List *list = NULL, *list1 = NULL;
+   int current_descending=0;
+   int count = 0;
    int i;
 
-   eina_init();
-   eina_init();
+   pool = eina_rectangle_pool_new(W, H);
+   eina_rectangle_pool_packing_set(pool, type);
 
-   pool = eina_rectangle_pool_new(2048, 2048);
    if (!pool)
       return;
 
@@ -44,33 +50,54 @@ eina_bench_eina_rectangle_pool(int request)
 
         while (!rect)
           {
-             rect = eina_rectangle_pool_request(pool, i & 0xFF, 256 - (i & 0xFF));
+             rect = eina_rectangle_pool_request(pool, rand() % RW + 1, rand() % RH + 1);
              if (!rect)
                {
-                  rect = eina_list_data_get(list);
-                  list = eina_list_remove_list(list, list);
+                  list1 = eina_list_last(list);
+                  rect = eina_list_data_get(list1);
+                  list = eina_list_remove_list(list, list1);
                   if (rect)
-                     eina_rectangle_pool_release(rect);
+                    {
+                       count = 1;
+                       eina_rectangle_pool_release(rect);
+                    }
                }
-             else
-                list = eina_list_append(list, rect);
-
-             if (!(i & 0xFF))
-                break;
+            else
+              {
+                 if (!count)
+                   current_descending++;
+                 list = eina_list_append(list, rect);
+              }
           }
      }
 
    eina_rectangle_pool_free(pool);
    eina_list_free(list);
-
-   eina_shutdown();
 }
 
+#define EINA_BENCH_PACKING(Name)                                        \
+  static void                                                           \
+  eina_bench_packing_#Name(int request)                                 \
+  {                                                                     \
+     eina_bench_generic_packing_efficiency(request, Eina_Packing_#Name); \
+  }
+
+EINA_BENCH_PACKING(Descending);
+EINA_BENCH_PACKING(Ascending);
+EINA_BENCH_PACKING(Bottom_Left);
+EINA_BENCH_PACKING(Bottom_Left_Skyline);
+
 void eina_bench_rectangle_pool(Eina_Benchmark *bench)
 {
-   eina_benchmark_register(bench, "eina",
-                           EINA_BENCHMARK(
-                              eina_bench_eina_rectangle_pool), 10, 4000, 100);
+#define EINA_BENCH_REGISTER(Name)                                       \
+   eina_benchmark_register(bench, "eina - "##Name,                      \
+                           EINA_BENCHMARK(eina_bench_packing_#Name),    \
+                           10, 4000, 100);
+
+   EINA_BENCH_REGISTER(Descending);
+   EINA_BENCH_REGISTER(Ascending);
+   EINA_BENCH_REGISTER(Bottom_Left);
+   EINA_BENCH_REGISTER(Bottom_Left_Skyline);
 }
 
 
diff --git a/src/lib/eina/eina_rectangle.c b/src/lib/eina/eina_rectangle.c
index 5ae680b7df..6242ef7018 100644
--- a/src/lib/eina/eina_rectangle.c
+++ b/src/lib/eina/eina_rectangle.c
@@ -61,9 +61,13 @@ struct _Eina_Rectangle_Pool
    Eina_List *empty;
    void *data;
 
+   Eina_Compare_Cb eina_rectangle_compare_func;
+
    Eina_Trash *bucket;
    unsigned int bucket_count;
 
+   Eina_Rectangle_Packing type;
+
    unsigned int references;
    int w;
    int h;
@@ -109,18 +113,40 @@ static int _eina_rectangle_log_dom = -1;
 #define DBG(...) EINA_LOG_DOM_DBG(_eina_rectangle_log_dom, __VA_ARGS__)
 
 static int
-_eina_rectangle_cmp(const Eina_Rectangle *r1, const Eina_Rectangle *r2)
+_eina_rectangle_cmp(const void *data1, const void *data2)
 {
+   Eina_Rectangle *r1 = (Eina_Rectangle *) data1;
+   Eina_Rectangle *r2 = (Eina_Rectangle *) data2;
    return (r2->w * r2->h) - (r1->w * r1->h);
 }
 
+static int
+_eina_rectangle_cmp_asc(const void *data1, const void *data2)
+{
+   Eina_Rectangle *r1 = (Eina_Rectangle *) data1;
+   Eina_Rectangle *r2 = (Eina_Rectangle *) data2;
+   return (r1->w * r1->h) - (r2->w * r2->h);
+}
+
+static int
+_eina_rectangle_cmp_bl(const void *data1, const void *data2)
+{
+   Eina_Rectangle *r1 = (Eina_Rectangle *) data1;
+   Eina_Rectangle *r2 = (Eina_Rectangle *) data2;
+   if (r1->y != r2->y)
+     return (r1->y) - (r2->y);
+   else
+     return (r1->x) - (r2->x);
+}
+
 static Eina_List *
-_eina_rectangle_merge_list(Eina_List *empty, Eina_Rectangle *r)
+_eina_rectangle_merge_list(Eina_List *empty, Eina_Rectangle_Packing type, Eina_Rectangle *r)
 {
-   Eina_Rectangle *match;
+   Eina_Rectangle *match, *r1;
    Eina_List *l;
    int xw;
    int yh;
+   int x2 ,y2 ,w2 ,h2;
 
    if (r->w == 0 || r->h == 0)
      {
@@ -166,13 +192,41 @@ start_again:
 
            goto start_again;
         }
+      else if (match->y > r->y && type == Eina_Packing_Bottom_Left_Skyline
+               && (match->y + match->h == r->y + r->h) &&
+              (match->x + match->w == r->x || r->x + r->w == match->x))
+        {
+
+           if (r->x < match->x)
+              match->x = r->x;
+
+           match->w += r->w;
+
+           x2 = r->x;
+           y2 = r->y;
+           w2 = r->w;
+           h2 = match->y - r->y;
+
+           eina_rectangle_free(r);
+
+           r1 = eina_rectangle_new(x2, y2, w2, h2);
+
+           empty = eina_list_remove_list(empty, l);
+
+           if (r1)
+              empty = eina_list_append(empty, r1);
+
+           r = match;
+
+           goto start_again;
+        }
    }
 
    return eina_list_append(empty, r);
 }
 
 static Eina_List *
-_eina_rectangle_empty_space_find(Eina_List *empty, int w, int h, int *x, int *y)
+_eina_rectangle_empty_space_find(Eina_List *empty, Eina_Rectangle_Packing type, int w, int h, int *x, int *y)
 {
    Eina_Rectangle *r;
    Eina_List *l;
@@ -211,7 +265,7 @@ _eina_rectangle_empty_space_find(Eina_List *empty, int w, int h, int *x, int *y)
                 /* w2 could be w or r->w */
                 h2 = r->h - h;
 
-                if (rw1 * r->h > h2 * r->w)
+                if ((rw1 * r->h > h2 * r->w) || type == Eina_Packing_Bottom_Left || type == Eina_Packing_Bottom_Left_Skyline)
                   {
                      rh1 = r->h;
                      w2 = w;
@@ -223,14 +277,14 @@ _eina_rectangle_empty_space_find(Eina_List *empty, int w, int h, int *x, int *y)
                   }
 
                 EINA_RECTANGLE_SET(r, rx1, ry1, rw1, rh1);
-                empty = _eina_rectangle_merge_list(empty, r);
+                empty = _eina_rectangle_merge_list(empty, type, r);
 
                 r = eina_rectangle_new(x2, y2, w2, h2);
              }
 
            if (r)
              {
-                empty = _eina_rectangle_merge_list(empty, r); /* Return empty */
+                empty = _eina_rectangle_merge_list(empty, type, r); /* Return empty */
 
              }
 
@@ -376,6 +430,8 @@ eina_rectangle_pool_new(int w, int h)
    new->h = h;
    new->bucket = NULL;
    new->bucket_count = 0;
+   new->eina_rectangle_compare_func = _eina_rectangle_cmp;
+   new->type = Eina_Packing_Descending;
 
    EINA_MAGIC_SET(new, EINA_RECTANGLE_POOL_MAGIC);
    DBG("pool=%p, size=(%d, %d)", new, w, h);
@@ -440,11 +496,11 @@ eina_rectangle_pool_request(Eina_Rectangle_Pool *pool, int w, int h)
    if (!pool->sorted)
      {
         pool->empty =
-           eina_list_sort(pool->empty, 0, EINA_COMPARE_CB(_eina_rectangle_cmp));
+           eina_list_sort(pool->empty, 0, pool->eina_rectangle_compare_func);
         pool->sorted = EINA_TRUE;
      }
 
-   pool->empty = _eina_rectangle_empty_space_find(pool->empty, w, h, &x, &y);
+   pool->empty = _eina_rectangle_empty_space_find(pool->empty, pool->type, w, h, &x, &y);
    if (x == -1)
       return NULL;
 
@@ -498,7 +554,7 @@ eina_rectangle_pool_release(Eina_Rectangle *rect)
    r = eina_rectangle_new(rect->x, rect->y, rect->w, rect->h);
    if (r)
      {
-        era->pool->empty = _eina_rectangle_merge_list(era->pool->empty, r);
+        era->pool->empty = _eina_rectangle_merge_list(era->pool->empty, era->pool->type, r);
         era->pool->sorted = EINA_FALSE;
      }
 
@@ -532,6 +588,29 @@ eina_rectangle_pool_get(Eina_Rectangle *rect)
 }
 
 EAPI void
+eina_rectangle_pool_packing_set(Eina_Rectangle_Pool *pool, Eina_Rectangle_Packing type)
+{
+   EINA_MAGIC_CHECK_RECTANGLE_POOL(pool);
+   EINA_SAFETY_ON_NULL_RETURN(pool);
+
+   DBG("type=%d  pool=%p, size=(%d, %d), references=%u",
+       type, pool, pool->w, pool->h, pool->references);
+   pool->type =type;
+
+   switch (type)
+     {
+      case Eina_Packing_Ascending:
+         pool->eina_rectangle_compare_func = _eina_rectangle_cmp_asc;
+         break;
+      case Eina_Packing_Descending:
+         pool->eina_rectangle_compare_func = _eina_rectangle_cmp;
+         break;
+      default:
+         pool->eina_rectangle_compare_func = _eina_rectangle_cmp_bl;
+     }
+}
+
+EAPI void
 eina_rectangle_pool_data_set(Eina_Rectangle_Pool *pool, const void *data)
 {
    EINA_MAGIC_CHECK_RECTANGLE_POOL(pool);
diff --git a/src/lib/eina/eina_rectangle.h b/src/lib/eina/eina_rectangle.h
index d3e2443a95..fff4b3bb6a 100644
--- a/src/lib/eina/eina_rectangle.h
+++ b/src/lib/eina/eina_rectangle.h
@@ -61,6 +61,18 @@ typedef struct _Eina_Rectangle
  */
 typedef struct _Eina_Rectangle_Pool Eina_Rectangle_Pool;
 
+/**
+ * @typedef Eina_Rectangle_Pool_Type
+ * Type for an Eina Pool based on packing algorithm.
+ * @since 1.10
+ */
+typedef enum {
+  Eina_Packing_Descending,            /**< Current */
+  Eina_Packing_Ascending,             /**< sorting in assending order */
+  Eina_Packing_Bottom_Left,           /**< sorting in bottemleft fasion */
+  Eina_Packing_Bottom_Left_Skyline    /**< bottemleft skyline  */
+} Eina_Rectangle_Packing;
+
 static inline int         eina_spans_intersect(int c1, int l1, int c2, int l2) EINA_WARN_UNUSED_RESULT;
 static inline Eina_Bool   eina_rectangle_is_empty(const Eina_Rectangle *r) EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT;
 static inline void        eina_rectangle_coords_from(Eina_Rectangle *r, int x, int y, int w, int h) EINA_ARG_NONNULL(1);
@@ -238,6 +250,17 @@ EAPI Eina_Rectangle *eina_rectangle_new(int x, int y, int w, int h) EINA_MALLOC
  */
 EAPI void            eina_rectangle_free(Eina_Rectangle *rect) EINA_ARG_NONNULL(1);
 
+/**
+ * @brief Sets the type of given rectangle pool.
+ *
+ * @param pool The rectangle pool for which type is to be set.
+ *
+ * This function sets @p type of @p pool.
+ * @see Eina_Rectangle_Packing
+ * @since 1.10
+ */
+EAPI void            eina_rectangle_pool_packing_set(Eina_Rectangle_Pool *pool,Eina_Rectangle_Packing type) EINA_ARG_NONNULL(1);
+
 #include "eina_inline_rectangle.x"
 
 /**
diff --git a/src/tests/eina/eina_test_rectangle.c b/src/tests/eina/eina_test_rectangle.c
index e5a211fd0f..a8a214d3fd 100644
--- a/src/tests/eina/eina_test_rectangle.c
+++ b/src/tests/eina/eina_test_rectangle.c
@@ -25,7 +25,8 @@
 #include "eina_suite.h"
 #include "Eina.h"
 
-START_TEST(eina_rectangle_pool)
+static void
+eina_test_generic_rectangle_pool(Eina_Rectangle_Packing type)
 {
    Eina_Rectangle_Pool *pool;
    Eina_Rectangle *rects[8][8];
@@ -39,6 +40,8 @@ START_TEST(eina_rectangle_pool)
    pool = eina_rectangle_pool_new(256, 256);
    fail_if(pool == NULL);
 
+   eina_rectangle_pool_packing_set(pool, type);
+
    eina_rectangle_pool_data_set(pool, rects);
    fail_if(eina_rectangle_pool_data_get(pool) != rects);
 
@@ -70,6 +73,29 @@ START_TEST(eina_rectangle_pool)
 
    eina_shutdown();
 }
+
+START_TEST(eina_rectangle_pool_descending)
+{
+   eina_test_generic_rectangle_pool(Eina_Packing_Descending);
+}
+END_TEST
+
+START_TEST(eina_rectangle_pool_ascending)
+{
+   eina_test_generic_rectangle_pool(Eina_Packing_Ascending);
+}
+END_TEST
+
+START_TEST(eina_rectangle_pool_bottom_left)
+{
+   eina_test_generic_rectangle_pool(Eina_Packing_Bottom_Left);
+}
+END_TEST
+
+START_TEST(eina_rectangle_pool_bottom_left_skyline)
+{
+   eina_test_generic_rectangle_pool(Eina_Packing_Bottom_Left_Skyline);
+}
 END_TEST
 
 START_TEST(eina_rectangle_intersect)
@@ -109,7 +135,10 @@ END_TEST
 void
 eina_test_rectangle(TCase *tc)
 {
-   tcase_add_test(tc, eina_rectangle_pool);
+   tcase_add_test(tc, eina_rectangle_pool_descending);
+   tcase_add_test(tc, eina_rectangle_pool_ascending);
+   tcase_add_test(tc, eina_rectangle_pool_bottom_left);
+   tcase_add_test(tc, eina_rectangle_pool_bottom_left_skyline);
    tcase_add_test(tc, eina_rectangle_intersect);
 }