#include <Eina.h>
#include "eina_blist.h"

//////////////////////////////////////////////////////////////////////////////
// common cache lines sizes are 64bytes. some are 128 byte. i have read that
// some ppc/power chips use 256 byte and ultrasparc and some power/ppc has
// used 512 byte before. some older x86's have used 128byte too. i believe
// some arms have used 128 byte as well. some older cpus used 32 byte and
// even 16 byte. today i would say the most common size is 64 byte with a
// few 128's around. if we make this too big we will waste tail blocks for
// short lists and some fragmented blocks inside before a recompress so
// there has to be a balance between size and over-allocation as well as
// the cost of shuffling elements up and down on inserts or removes, so
// i'm going with this below as a "best overall" size.
// 
// also as opposed to eina_list, a non-fragmented blist breaks even with eina
// list in terms of memory footprint at > 4 items or so (on 64bit with a 128
// siaed block). so anything smaller will waste more memory with blist
// as opposed to eina list.
// 
// keep in mind that we can always have blist dynamically restructure data
// internally to make up for a lot of this (also see below performance nums).
// we can have api's to tell blist if to prefer speed over size or walking
// over modification etc. and then have it adapt correctly more quickly or
// even instantly when needed. there is also a cost to the transform to some
// other internal representation, so only do it when it's really worth it and
// don't keep changing format as that'll just make everything worsae.
//
// how big is a cacheline for blist? this does not meant it matches the
// real system cacheline size, but it would be the most optimal size for
// the total size of a block (including count, next/prev ptrs). i've found
// that 128 seems to produce the best results imperically. try yourself from
// the below sizes. somethinb bigger can work, but will lose lots of
// prefetches as it's probably not worth it anymore. note at 1024/2048
// (32/64bit) our counters go up in size from 8 to 16 bit. then again at
// 262144/524288. The bigger a block, the more sasted space per list too,
// so the more it fragments too. so there has to be a balance on speed for
// small, medium and large lists, fragmentation etc. for a default size.
// 
// quick perf numbers on i7700k (lower == better):
// 
//         number of items in list...
// BLKSZ :      10    100     1k    10k   100k
// 64    :   0.975  0.954  0.980  2.198  2.109
// 128   :   0.871  0.779  0.788  1.540  1.096 * best overall
// 256   :   0.918  0.854  0.897  1.830  1.011
// 512   :   0.906  0.777  0.813  1.646  0.983
// 1024  :   0.874  0.780  0.804  1.447  0.824
// 2048  :   0.882  0.838  0.803  1.376  0.667 * best for long lists + overall
// 4096  :   0.903  0.812  0.893  1.391  0.648 
// 8192  :   0.899  0.835  1.041  1.539  0.641
// 16384 :   0.898  0.820  1.641  1.812  0.655
// 32768 :   0.914  0.829  1.643  2.344  0.712
// 65536 :   4.563  1.291  1.782  4.497  0.968
// 
// now numbers for eina list:
// list  :   1.632  1.794  2.116 12.587 12.521
// 
// on an ampere emag (aarch64):
// 
//         number of items in list...
// BLKSZ :      10    100     1k    10k   100k
// 64    :   2.593  2.034  2.032  5.141  3.685
// 128   :   2.007  1.764  1.825  4.295  7.717
// 256   :   1.781  1.695  1.786  4.567  3.662 * best overall
// 512   :   1.875  1.653  1.770  4.008  5.832
// 1024  :   1.865  1.674  1.827  3.998  4.259
// 2048  :   1.809  1.929  2.008  4.055  3.319
// 4096  :   1.912  1.947  2.406  4.374  2.969
// 8192  :   1.927  1.933  3.158  5.179  2.684
// 16384 :   1.872  1.943  6.301  6.652  2.693
// 32768 :   1.890  1.963  6.314  9.452  3.033
// 65536 :   9.025  2.900  6.492 17.781  3.971
// 
// now numbers for eina list:
// list  :   9.667  9.922 11.659 56.922 35.032
// 
// on a rk3399 (arm a72) (aarch64):
// 
//         number of items in list...
// BLKSZ :      10    100     1k    10k   100k
// 64    :   0.344  0.312  0.309  0.723  1.197
// 128   :   0.321  0.289  0.316  0.561  1.050
// 256   :   0.284  0.271  0.297  0.685  0.603
// 512   :   0.290  0.256  0.281  0.666  0.547
// 1024  :   0.288  0.267  0.292  0.658  0.529
// 2048  :   0.289  0.321  0.332  0.675  0.556
// 4096  :   0.308  0.331  0.407  0.736  0.425
// 8192  :   0.290  0.324  0.538  0.875  0.444
// 16384 :   0.286  0.315  1.104  1.223  0.481
// 32768 :   0.299  0.313  1.449  1.164  0.485
// 65536 :   1.408  0.429  1.171  3.294  0.869
// 
// now numbers for eina list:
// list  :   1.047  1.020  1.272  5.658  4.875
// 
// so blist wins over eina list for almost everything until its basically a
// almost a big single array (65k block size) where it has very few blocks
// to break it up. this shows that arrays are not always just a win and that
// somerhing in between with much smaller block sizes is the real win overall.
// 
// as for blist block sizes...
// 
// 8192 seems to favor larger lists for performance whilst still not being
// bad for small lists (but will waste a lot of memory). 128 seems the best
// perf for smaller lists, where lasrger are not that bad and has one of the
// lowest memory wastes. 64 of clourse is even less waste but is really
// measurably worse for longer lists. overall as a balance 128 seems like the
// perfect default, with perhaps 2048 for long lists. let's say long lists
// start at ~5-10k items.
// 
// this needs a lot more testing with various usage patterns as well as
// various amounts of cache dirtying duinrg and in between operations.

#define EINA_BLIST_CACHE_LINE_SIZE 128
// define if we want prefetches. prefetches seem to always be a win
// whenever i turn them on and off and measure them.
#define PREFETCH 1

// 64bit -> 14, 32bit -> 30 @ 128
#define EINA_BLIST_BLOCK_SIZE       ((EINA_BLIST_CACHE_LINE_SIZE - \
                                      (sizeof(void *) * 2)) / \
                                     sizeof(void *))
#if (EINA_BLIST_CACHE_LINE_SIZE <= 1024)
typedef unsigned char  Blist_Counter;
#elif (EINA_BLIST_CACHE_LINE_SIZE <= 262144)
typedef unsigned short Blist_Counter;
#else
typedef unsigned int   Blist_Counter;
#endif

#ifdef PREFETCH

# define PF(x) EINA_PREFETCH((x))
//# define PF(x) EINA_PREFETCH_WRITE((x))
//# define PF(x) EINA_PREFETCH_NOCACHE((x))
//# define PF(x) EINA_PREFETCH_NOCACHE_WRITE((x))

#define PF_COND(x) if (x)
//#define PF_COND(x) if (EINA_LIKELY((x) != 0))
//#define PF_COND(x)

#define PTR(x) ((unsigned char *)(x))

# if (EINA_BLIST_CACHE_LINE_SIZE == 256)
#  define PREFETCH_NEXT(_it) do { \
   PF_COND  ((_it)->next) { \
      PF(PTR((_it)->next)      ); \
      PF(PTR((_it)->next) +  64); \
      PF(PTR((_it)->next) + 128); \
      PF(PTR((_it)->next) + 192); \
   } } while (0)
#  define PREFETCH_PREV(_it) do { \
   PF_COND  ((_it)->prev) { \
      PF(PTR((_it)->prev) + 192); \
      PF(PTR((_it)->prev) + 128); \
      PF(PTR((_it)->prev) +  64); \
      PF(PTR((_it)->prev)      ); \
   } } while (0)
# elif (EINA_BLIST_CACHE_LINE_SIZE == 128)
#  define PREFETCH_NEXT(_it) do { \
   PF_COND  ((_it)->next) { \
      PF(PTR((_it)->next)     ); \
      PF(PTR((_it)->next) + 64); \
   } } while (0)
#  define PREFETCH_PREV(_it) do { \
   PF_COND  ((_it)->prev) { \
      PF(PTR((_it)->prev) + 64); \
      PF(PTR((_it)->prev)     ); \
   } } while (0)
# else
#  define PREFETCH_NEXT(_it) do { \
   PF_COND  ((_it)->next) { \
      PF(PTR((_it)->next)); \
   } } while (0)
#  define PREFETCH_PREV(_it) do { \
   PF_COND  ((_it)->prev) { \
      PF(PTR((_it)->prev)); \
   } } while (0)
# endif
#else
# define PREFETCH_NEXT(_it)
# define PREFETCH_PREV(_it)
#endif

struct _Eina_Blist
{
   Eina_Blist_Item *list;
   Eina_Blist_Item *last;
   unsigned int count;
   unsigned int frags;
   void (*free_func) (void *data);
};

struct _Eina_Blist_Item
{
   // special - mask off lower 7 bits in following to get count of
   // elements. since block size is at least 128 and we use a mempool for
   // blocks
   Eina_Blist_Item *prev; // lower 7 bits are element count in data array
   Eina_Blist_Item *next;
   void *data[EINA_BLIST_BLOCK_SIZE];
};

//////////////////////////////////////////////////////////////////////////////

static inline Eina_Blist_Item *
_ptr_get(Eina_Blist_Item *it)
{
   return (Eina_Blist_Item *)((uintptr_t)it & (~(uintptr_t)(EINA_BLIST_CACHE_LINE_SIZE - 1)));
}

static inline Blist_Counter
_count_get(Eina_Blist_Item *it)
{
   return (Blist_Counter)((uintptr_t)it & (EINA_BLIST_CACHE_LINE_SIZE - 1));
}

static inline Eina_Blist_Item *
_count_set(Eina_Blist_Item *it, Blist_Counter count)
{
   return (Eina_Blist_Item *)((uintptr_t)_ptr_get(it) | (uintptr_t)(count & (EINA_BLIST_CACHE_LINE_SIZE - 1)));
}

//////////////////////////////////////////////////////////////////////////////

#define POOL
#define POOL_MAX 256
#define POOL_ITEM_MAX 512

#ifdef POOL
typedef struct _Pool_Item Pool_Item;

struct _Pool_Item
{
   Pool_Item *next;
};

static unsigned int  _pool_usage = 0;
static unsigned int  _pool_item_usage = 0;
static Pool_Item    *_pool_list = NULL;
static Pool_Item    *_pool_list_item = NULL;
#endif

static Eina_Blist *
_list_alloc(void)
{
   Eina_Blist *li;

#ifdef POOL
   if (_pool_list)
     {
        li = (Eina_Blist *)_pool_list;
        _pool_list = _pool_list->next;
        memset(li, 0, sizeof(Eina_Blist));
        _pool_usage--;
        return li;
     }
#endif
   li = calloc(1, sizeof(Eina_Blist));
   if (li) return li;
   fprintf(stderr, "ERROR: Alloc of blist failed\n");
   abort();
   return NULL;
}

static void
_list_free(Eina_Blist *li)
{
#ifdef POOL
   if (_pool_usage < POOL_MAX)
     {
        Pool_Item *pi = (Pool_Item *)li;
        pi->next = _pool_list;
        _pool_list = pi;
        _pool_usage++;
     }
   else
#endif
     free(li);
}

static Eina_Blist_Item *
_item_alloc(void)
{
   void *ptr;
   Eina_Blist_Item *it;

#ifdef POOL
   if (_pool_list)
     {
        it = (Eina_Blist_Item *)_pool_list_item;
        _pool_list_item = _pool_list->next;
        _pool_item_usage--;
        return it;
     }
#endif
   if (posix_memalign(&(ptr), EINA_BLIST_CACHE_LINE_SIZE,
                      sizeof(Eina_Blist_Item)) == 0)
     {
        it = ptr;
        it->prev = it->next = NULL;
        return it;
     }
   fprintf(stderr, "ERROR: Alloc of blist item failed\n");
   abort();
   return NULL;
}

static void
_item_free(Eina_Blist_Item *it)
{
#ifdef POOL
   if (_pool_item_usage < POOL_ITEM_MAX)
     {
        Pool_Item *pi = (Pool_Item *)it;
        pi->next = _pool_list_item;
        _pool_list_item = pi;
        _pool_item_usage++;
     }
   else
#endif
     free(it);
}

//////////////////////////////////////////////////////////////////////////////

static void
_shuffle_up(Eina_Blist_Item *item, Blist_Counter from, Blist_Counter to)
{
   Blist_Counter i;

   for (i = to; i > from; i--) item->data[i] = item->data[i - 1];
}

static void
_shuffle_down(Eina_Blist_Item *item, Blist_Counter from, Blist_Counter to)
{
   Blist_Counter i;

   to--;
   for (i = from; i < to; i++) item->data[i] = item->data[i + 1];
}

//////////////////////////////////////////////////////////////////////////////

static void
_insert_at(Eina_Blist **blist, const void *data, Eina_Blist_Item *item, Blist_Counter at)
{
   Eina_Blist_Item *it;
   Blist_Counter count;

   (*blist)->count++;
   count = _count_get(item->prev);
   // fits in current item block
   if (count < EINA_BLIST_BLOCK_SIZE)
     {
        // shuffle up items to make room at "at"
        _shuffle_up(item, at, count);
        item->data[at] = (void *)data;
        item->prev = _count_set(item->prev, ++count);
        if (count == EINA_BLIST_BLOCK_SIZE) (*blist)->frags--;
        return;
     }
   // if there is a following item...
   it = item->next;
   if (it)
     {
        count = _count_get(it->prev);
        // if next block has space
        if (count < EINA_BLIST_BLOCK_SIZE)
          {
             // shuffle up items to make first item empty
             _shuffle_up(it, 0, EINA_BLIST_BLOCK_SIZE - 1);
             // move last item from "this" block to the next
             it->data[0] = item->data[EINA_BLIST_BLOCK_SIZE - 1];
             // shuffle up items in "this" block to make space
             _shuffle_up(item, at, EINA_BLIST_BLOCK_SIZE - 1);
             // insert item
             item->data[at] = (void *)data;
             it->prev = _count_set(it->prev, ++count);
             if (count == EINA_BLIST_BLOCK_SIZE) (*blist)->frags--;
             return;
          }
     }
   // we need to append a new item block after this to make room
   it = _item_alloc();
   it->next = item->next;
   item->next = it;
   if (!it->next)
     (*blist)->last = it;
   it->prev = _count_set(item, 1);
   (*blist)->frags++;
   it->next->prev = _count_set(it, _count_get(it->next->prev));

   // if the insert spot is within this block
   if (at < EINA_BLIST_BLOCK_SIZE)
     {
        // move last item from "this" block to the new one first slot
        it->data[0] = item->data[EINA_BLIST_BLOCK_SIZE - 1];
        // shuffle up items above slot
        _shuffle_up(item, at, EINA_BLIST_BLOCK_SIZE - 1);
        // insert item
        item->data[at] = (void *)data;
        return;
     }
   // just fill the new block with the only item
   it->data[0] = (void *)data;
}

static void
_clean(Eina_Blist **blist)
{
   Eina_Blist_Item *it, *l;
   unsigned int total = 0;
   Blist_Counter i, count;

   it = (*blist)->list;
   while (it)
     {
        PREFETCH_NEXT(it);
        count = _count_get(it->prev);
        total += count;
        // find first block that is not fully filled
        if ((count != EINA_BLIST_BLOCK_SIZE) && (it->next))
          {
             // cut off list at this block
             (*blist)->count = total;
             (*blist)->last = it;
             l = it->next;
             it->next = NULL;
             // now go over the rest of the blocks and append them
             while (l)
               {
                  count = _count_get(l->prev);
                  for (i = 0; i < count; i++)
                    eina_blist_append(blist, l->data[i]);
                  PREFETCH_NEXT(l);
                  it = l->next;
                  _item_free(l);
                  l = it;
                  goto done;
               }
          }
        it = it->next;
     }
done:
   if (_count_get((*blist)->last) != EINA_BLIST_BLOCK_SIZE)
     (*blist)->frags = 1;
   else
     (*blist)->frags = 0;
}

//////////////////////////////////////////////////////////////////////////////

Eina_Blist_Item *
eina_blist_item_find(Eina_Blist **blist, const void *data)
{
   Eina_Blist_Item *it;
   Blist_Counter i, count;

   if (!(*blist)) return NULL;
   it = (*blist)->list;
   while (it)
     {
        PREFETCH_NEXT(it);
        count = _count_get(it->prev);
        for (i = 0; i < count; i++)
          {
             if (it->data[i] == data)
               {
                  // the lower 6/7/8 bits are already 0 due to alignment
                  // it = _ptr_get(it);
                  // use the lower 6/78 bits of the item ptr as a element slot
                  // value so we know which data array slot in the item
                  // is the one we want
                  it = _count_set(it, i);
                  return it;
               }
          }
        it = it->next;
     }
   return NULL;
}

Eina_Blist_Item *
eina_blist_item_first(Eina_Blist **blist)
{
   if (!(*blist)) return NULL;
   return (*blist)->list;
}

Eina_Blist_Item *
eina_blist_item_last(Eina_Blist **blist)
{
   Eina_Blist_Item *last;

   if (!(*blist)) return NULL;
   last = (*blist)->last;
   return _count_set(last, _count_get(last->prev) - 1);
}

Eina_Blist_Item *
eina_blist_item_nth(Eina_Blist **blist, unsigned int n)
{
   Eina_Blist_Item *it;
   unsigned int total = 0;
   Blist_Counter i, count;

   if (!(*blist)) return NULL;
   it = (*blist)->list;
   while (it)
     {
        PREFETCH_NEXT(it);
        count = _count_get(it->prev);
        if ((total + count) > n)
          {
             // the lower 7 bits are already 0 due to alignment
             // it = _ptr_get(it);
             // use the lower 7 bits of the item ptr as a element slot
             // value so we know which data array slot in the item
             // is the one we want
             it = _count_set(it, n - total);
             return it;
          }
        total += count;
        it = it->next;
     }
   return NULL;
}

void
eina_blist_item_remove(Eina_Blist **blist, Eina_Blist_Item *item)
{
   Eina_Blist_Item *it, *prev;
   Blist_Counter n, count;
   void (*func) (void *data);

   if (!(*blist)) return;
   // drop global count for list
   func = (*blist)->free_func;
   (*blist)->count--;
   it = _ptr_get(item);
   n = _count_get(item);
   if (n == 1)
     {
        PREFETCH_PREV(it);
        PREFETCH_NEXT(it);
     }
   if (func) func(it->data[n]);
   count = _count_get(it->prev);
   if (count > 0) // shuffle down items above
     {
        _shuffle_down(it, n, count);
        it->prev = _count_set(it->prev, count - 1);
        if (count == EINA_BLIST_BLOCK_SIZE) (*blist)->frags++;
     }
   count = _count_get(it->prev);
   if (count == 0) // 0 element item - remove it
     {
        (*blist)->frags--;
        prev = _ptr_get(it->prev);
        if (prev) prev->next = it->next;
        else
          {
             if ((*blist)->list == it) (*blist)->list = it->next;
          }
        if (it->next)
          {
             n = _count_get(it->next->prev);
             it->next->prev = prev;
             it->next->prev = _count_set(it->next->prev, n);
          }
        _item_free(it);
     }
}

void
eina_blist_item_relative_append(Eina_Blist **blist, const void *data, Eina_Blist_Item *item)
{
   if (!(*blist)) return;
   _insert_at(blist, data, _ptr_get(item), _count_get(item) + 1);
}

void
eina_blist_item_relative_prepend(Eina_Blist **blist, const void *data, Eina_Blist_Item *item)
{
   if (!(*blist)) return;
   _insert_at(blist, data, _ptr_get(item), _count_get(item));
}

void
eina_blist_free(Eina_Blist **blist)
{
   Eina_Blist_Item *it, *itnext;
   Blist_Counter i, count;
   void (*func) (void *data) = NULL;

   if (!(*blist)) return;
   it = (*blist)->list;
   func = (*blist)->free_func;
   while (it)
     {
        PREFETCH_NEXT(it);
        if (func)
          {
             count = _count_get(it->prev);
             for (i = 0; i < count; i++)
               func(it->data[i]);
          }
        itnext = it->next;
        _item_free(it);
        it = itnext;
     }
   _list_free(*blist);
   *blist = NULL;
}

void
eina_blist_free_func_set(Eina_Blist **blist, void (*func) (void *data))
{
   if (!(*blist))
     {
        *blist = _list_alloc();
        if (!*blist) return;
     }
   (*blist)->free_func = func;
}


void
eina_blist_append(Eina_Blist **blist, const void *data)
{
   Eina_Blist_Item *it, *last;
   Blist_Counter count;

   if (*blist) // existing list - more common
     {
        // bump header counter up
        (*blist)->count++;
        // find last item
        it = (*blist)->last;
        count = _count_get(it->prev);
        // space in last item so append there
        if (count < EINA_BLIST_BLOCK_SIZE)
          {
             it->data[count] = (void *)data;
             it->prev = _count_set(it->prev, ++count);
             if (count == EINA_BLIST_BLOCK_SIZE) (*blist)->frags--;
             return;
          }
        last = it;
        // need new block
        it = _item_alloc();
        // link it in at the end
        last->next = it;
        it->prev = last;
        (*blist)->last = it;
        // fill new last item with 1 element
        it->prev = _count_set(it->prev, 1);
        (*blist)->frags++;
        it->data[0] = (void *)data;
        return;
     }
   else // empty - new list
     {
        *blist = _list_alloc();
        it = _item_alloc();
        (*blist)->list = (*blist)->last = it;
        it->prev = _count_set(it->prev, 1);
        (*blist)->frags++;
        it->data[0] = (void *)data;
        (*blist)->count = 1;
     }
}

void
eina_blist_prepend(Eina_Blist **blist, const void *data)
{
   Eina_Blist_Item *it, *first;
   Blist_Counter count;

   if (*blist) // existing list - more common
     {
        // bump header counter up
        (*blist)->count++;
        // find first item
        it = (*blist)->list;
        count = _count_get(it->prev);
        // space in last item so append there
        if (count < EINA_BLIST_BLOCK_SIZE)
          {
             // shuffle elements up to make room at the start
             _shuffle_up(it, 0, count);
             it->data[0] = (void *)data;
             it->prev = _count_set(it->prev, ++count);
             if (count == EINA_BLIST_BLOCK_SIZE) (*blist)->frags--;
             return;
          }
        first = it;
        // need new block
        it = _item_alloc();
        // link it in at the start
        count = _count_get(first->prev);
        first->prev = _count_set(it, count);
        it->next = first;
        (*blist)->list = it;
        // fill new first item with 1 element
        it->prev = _count_set(it->prev, 1);
        (*blist)->frags++;
        it->data[0] = (void *)data;
     }
   else eina_blist_append(blist, data);
}

void
eina_blist_relative_append(Eina_Blist **blist, const void *data, const void *rel)
{
   Eina_Blist_Item *it;

   if (!(*blist)) return;
   if (!data) return;
   if (!(it = eina_blist_item_find(blist, rel))) return;
   eina_blist_item_relative_append(blist, data, it);
}

void
eina_blist_relative_prepend(Eina_Blist **blist, const void *data, const void *rel)
{
   Eina_Blist_Item *it;

   if (!(*blist)) return;
   if (!data) return;
   if (!(it = eina_blist_item_find(blist, rel))) return;
   eina_blist_item_relative_prepend(blist, data, it);
}

void
eina_blist_remove(Eina_Blist **blist, const void *data)
{
   Eina_Blist_Item *it;

   if (!(*blist)) return;
   if (!data) return;
   if (!(it = eina_blist_item_find(blist, data))) return;
   eina_blist_item_remove(blist, it);
}

void *
eina_blist_first(Eina_Blist **blist)
{
   Eina_Blist_Item *it = eina_blist_item_first(blist);
   return eina_blist_item_data_get(it);
}

void *
eina_blist_last(Eina_Blist **blist)
{
   Eina_Blist_Item *it = eina_blist_item_last(blist);
   return eina_blist_item_data_get(it);
}

void *
eina_blist_nth(Eina_Blist **blist, unsigned int n)
{
   Eina_Blist_Item *it;

   if (!(it = eina_blist_item_nth(blist, n))) return NULL;
   return eina_blist_item_data_get(it);
}

unsigned int
eina_blist_count(Eina_Blist **blist)
{
   if (!(*blist)) return 0;
   return (*blist)->count;
}

void
eina_blist_clean(Eina_Blist **blist)
{
   unsigned int total = 0, frags, perc;
   if (!(*blist)) return;
   frags = (*blist)->frags;
   if (frags < 2) return;
   total = (*blist)->count;
   // avoid int overflow
   if ((*blist)->count >= 0x0fffffff)
     {
        frags /= 10;
        total /= 10;
     }
   perc = (frags * 10) / total;
   // if 1/10 or fewer blocks are fragmented (not filled) then don't bother
   if (perc <= 1) return;
   _clean(blist);
}

void
eina_blist_clean_force(Eina_Blist **blist)
{
   if (!(*blist)) return;
   _clean(blist);
}

unsigned int
eina_blist_frag_scan(Eina_Blist **blist)
{
   Eina_Blist_Item *it;
   unsigned int total = 0, frags = 0;
   Blist_Counter i, count;

   if (!(*blist)) return 0;
   it = (*blist)->list;
   while (it)
     {
        PREFETCH_NEXT(it);
        count = _count_get(it->prev);
        if (count != EINA_BLIST_BLOCK_SIZE) frags++;
        it = it->next;
     }
   return frags;
}

Eina_Blist_Item *
eina_blist_item_next(Eina_Blist_Item *item)
{
   Eina_Blist_Item *it;
   Blist_Counter n, count;

   it = _ptr_get(item);
   n = _count_get(item);
   count = _count_get(it->prev);
   if (n < (count - 1))
     return _count_set(it, n + 1);
   it = it->next;
   return it;
}

Eina_Blist_Item *
eina_blist_item_prev(Eina_Blist_Item *item)
{
   Eina_Blist_Item *it;
   Blist_Counter n, count;

   it = _ptr_get(item);
   n = _count_get(item);
   if (n > 0)
     return _count_set(it, n - 1);
   it = _ptr_get(it->prev);
   if (!it) return NULL;
   count = _count_get(it->prev);
   return _count_set(it, count - 1);
}

void *
eina_blist_item_data_get(Eina_Blist_Item *item)
{
   Eina_Blist_Item *it;
   Blist_Counter n;

   if (!item) return NULL;
   it = _ptr_get(item);
   n = _count_get(item);
   return it->data[n];
}

void
eina_blist_item_data_set(Eina_Blist_Item *item, const void *data)
{
   Eina_Blist_Item *it;
   Blist_Counter n;

   if (!item) return;
   it = _ptr_get(item);
   n = _count_get(item);
   it->data[n] = (void  *)data;
}