src/modules/mp/fixed_bitmap/eina_fixed_bitmap.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2008 Cedric BAIL
   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 #ifndef _MSC_VER
  24 # include <stdint.h>
  25 #endif
  26 #include <string.h>
  27 #include <assert.h>
  28
  29 #ifdef HAVE_EVIL
  30 # include <Evil.h>
  31 #endif
  32
  33 #include "eina_inlist.h"
  34 #include "eina_rbtree.h"
  35 #include "eina_error.h"
  36
  37 #include "eina_mempool.h"
  38
  39 #include "eina_private.h"
  40
  41 typedef struct _Eina_Fixed_Bitmap Eina_Fixed_Bitmap;
  42 typedef struct _Eina_Fixed_Bitmap_Pool Eina_Fixed_Bitmap_Pool;
  43
  44 struct _Eina_Fixed_Bitmap
  45 {
  46    Eina_Rbtree *lookup;
  47    Eina_Inlist *head;
  48
  49    int item_size;
  50 };
  51
  52 struct _Eina_Fixed_Bitmap_Pool
  53 {
  54    EINA_RBTREE;
  55    EINA_INLIST;
  56
  57    uint32_t bitmask;
  58 };
  59
  60 static inline size_t
  61 _eina_rbtree_inlist_delta(void)
  62 {
  63    Eina_Fixed_Bitmap_Pool tmp;
  64    void *a = &tmp.__rbtree;
  65    void *b = &tmp.__in_list;
  66
  67    return (char *)a - (char *)b;
  68 }
  69
  70 static Eina_Rbtree_Direction
  71 _eina_fixed_cmp(const Eina_Rbtree *left,
  72                 const Eina_Rbtree *right,
  73                 __UNUSED__ void *data)
  74 {
  75    if (left - right < 0)
  76       return EINA_RBTREE_LEFT;
  77
  78    return EINA_RBTREE_RIGHT;
  79 }
  80
  81 static int
  82 _eina_fixed_cmp_key(const Eina_Rbtree *node,
  83                     const void *key,
  84                     __UNUSED__ int length,
  85                     Eina_Fixed_Bitmap *mp)
  86 {
  87    const void *a = node;
  88    const void *b = key;
  89    ssize_t delta;
  90    ssize_t limit;
  91
  92    limit = sizeof (Eina_Fixed_Bitmap_Pool) + mp->item_size * 32;
  93    delta = (char *)a - (char *)b;
  94
  95    if (delta > 0)
  96       return 1;
  97
  98    if (delta + limit < 0)
  99       return -1;
 100
 101    return 0;
 102 }
 103
 104 static void
 105 _eina_fixed_bitmap_pool_free(Eina_Fixed_Bitmap_Pool *pool,
 106                              __UNUSED__ void *data)
 107 {
 108    free(pool);
 109 }
 110
 111 static void *
 112 eina_fixed_bitmap_malloc(void *data, __UNUSED__ unsigned int size)
 113 {
 114    Eina_Fixed_Bitmap *mp = data;
 115    Eina_Fixed_Bitmap_Pool *pool = NULL;
 116    void *ptr;
 117    int idx;
 118
 119    if (mp->head)
 120      {
 121         pool =
 122            (Eina_Fixed_Bitmap_Pool *)((unsigned char *)mp->head +
 123                                       _eina_rbtree_inlist_delta());
 124
 125         if (pool->bitmask == 0)
 126            pool = NULL;
 127      }
 128
 129    if (!pool)
 130      {
 131              eina_error_set(0);
 132         pool = malloc(sizeof (Eina_Fixed_Bitmap_Pool) + mp->item_size * 32);
 133         if (!pool)
 134           {
 135              eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
 136              return NULL;
 137           }
 138
 139         pool->bitmask = 0xFFFFFFFF;
 140
 141         mp->head = eina_inlist_prepend(mp->head, EINA_INLIST_GET(pool));
 142         mp->lookup = eina_rbtree_inline_insert(mp->lookup, EINA_RBTREE_GET(
 143                                                   pool),
 144                                                EINA_RBTREE_CMP_NODE_CB(
 145                                                   _eina_fixed_cmp), NULL);
 146      }
 147
 148    idx = ffs(pool->bitmask) - 1;
 149    pool->bitmask &= ~(1 << idx);
 150    ptr = (unsigned char *)(pool + 1) + idx * mp->item_size;
 151
 152    if (pool->bitmask == 0)
 153       mp->head = eina_inlist_demote(mp->head, EINA_INLIST_GET(pool));
 154
 155    return ptr;
 156 }
 157
 158 static void
 159 eina_fixed_bitmap_free(void *data, void *ptr)
 160 {
 161    Eina_Fixed_Bitmap *mp = data;
 162    Eina_Fixed_Bitmap_Pool *pool;
 163    void *a;
 164    Eina_Bool push_front = EINA_FALSE;
 165    ssize_t delta;
 166
 167    pool = (Eina_Fixed_Bitmap_Pool *)eina_rbtree_inline_lookup(
 168          mp->lookup,
 169          ptr,
 170          0,
 171          EINA_RBTREE_CMP_KEY_CB(
 172             _eina_fixed_cmp_key),
 173          mp);
 174    if (!pool)
 175       return;
 176
 177    if (pool->bitmask != 0xFFFFFFFF)
 178       push_front = EINA_TRUE;
 179
 180    a = pool;
 181    delta =
 182       ((char *)ptr - (char *)a -
 183        sizeof (Eina_Fixed_Bitmap_Pool)) / mp->item_size;
 184
 185    assert(delta >= 0 && delta < 32);
 186
 187    pool->bitmask |= (1 << (delta & 0x1F));
 188
 189    if (pool->bitmask == 0xFFFFFFFF)
 190      {
 191         mp->head = eina_inlist_remove(mp->head, EINA_INLIST_GET(pool));
 192         mp->lookup = eina_rbtree_inline_remove(mp->lookup, EINA_RBTREE_GET(
 193                                                   pool),
 194                                                EINA_RBTREE_CMP_NODE_CB(
 195                                                   _eina_fixed_cmp), NULL);
 196         free(pool);
 197      }
 198    else if (push_front)
 199       mp->head = eina_inlist_promote(mp->head, EINA_INLIST_GET(pool));
 200 }
 201
 202 static void *
 203 eina_fixed_bitmap_realloc(__UNUSED__ void *data,
 204                           __UNUSED__ void *element,
 205                           __UNUSED__ unsigned int size)
 206 {
 207    return NULL;
 208 }
 209
 210 static void *
 211 eina_fixed_bitmap_init(__UNUSED__ const char *context,
 212                        __UNUSED__ const char *option,
 213                        va_list args)
 214 {
 215    Eina_Fixed_Bitmap *mp;
 216    int item_size;
 217
 218    mp = malloc(sizeof (Eina_Fixed_Bitmap));
 219    if (!mp)
 220       return NULL;
 221
 222    item_size = va_arg(args, int);
 223
 224    mp->item_size = eina_mempool_alignof(item_size);
 225
 226    mp->lookup = NULL;
 227    mp->head = NULL;
 228
 229    return mp;
 230 }
 231
 232 static void
 233 eina_fixed_bitmap_shutdown(void *data)
 234 {
 235    Eina_Fixed_Bitmap *mp = data;
 236
 237    eina_rbtree_delete(mp->lookup,
 238                       EINA_RBTREE_FREE_CB(_eina_fixed_bitmap_pool_free), NULL);
 239    free(mp);
 240 }
 241
 242 static Eina_Mempool_Backend _eina_fixed_bitmap_mp_backend = {
 243    "fixed_bitmap",
 244    &eina_fixed_bitmap_init,
 245    &eina_fixed_bitmap_free,
 246    &eina_fixed_bitmap_malloc,
 247    &eina_fixed_bitmap_realloc,
 248    NULL,
 249    NULL,
 250    &eina_fixed_bitmap_shutdown,
 251    NULL
 252 };
 253
 254 Eina_Bool fixed_bitmap_init(void)
 255 {
 256    return eina_mempool_register(&_eina_fixed_bitmap_mp_backend);
 257 }
 258
 259 void fixed_bitmap_shutdown(void)
 260 {
 261    eina_mempool_unregister(&_eina_fixed_bitmap_mp_backend);
 262 }
 263
 264 #ifndef EINA_STATIC_BUILD_FIXED_BITMAP
 265
 266 EINA_MODULE_INIT(fixed_bitmap_init);
 267 EINA_MODULE_SHUTDOWN(fixed_bitmap_shutdown);
 268
 269 #endif /* ! EINA_STATIC_BUILD_FIXED_BITMAP */
 270