Page MenuHomePhabricator

eina_blist.c

File Metadata

Author
raster
Created
Dec 17 2018, 7:39 AM

eina_blist.c

#include <Eina.h>
#include "eina_blist.h"
//////////////////////////////////////////////////////////////////////////////
// common cache lines sizes are 64bytes. someare 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 coler 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 i 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
#define EINA_BLIST_CACHE_LINE_SIZE 128
// 64bit -> 14, 32bit -> 30
#define EINA_BLIST_BLOCK_SIZE ((EINA_BLIST_CACHE_LINE_SIZE - \
(sizeof(void *) * 2)) / \
sizeof(void *))
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 unsigned int _pool_usage = 0;
static unsigned int _pool_item_usage = 0;
//////////////////////////////////////////////////////////////////////////////
static inline Eina_Blist_Item *
_ptr_get(Eina_Blist_Item *it)
{
return (Eina_Blist_Item *)((uintptr_t)it & (~(uintptr_t)(0x7f)));
}
static inline unsigned char
_count_get(Eina_Blist_Item *it)
{
return (unsigned char)((uintptr_t)it & 0x7f);
}
static inline Eina_Blist_Item *
_count_set(Eina_Blist_Item *it, unsigned char count)
{
return (Eina_Blist_Item *)((uintptr_t)_ptr_get(it) | (uintptr_t)(count & 0x7f));
}
//////////////////////////////////////////////////////////////////////////////
static void
_pool_use(void)
{
_pool_usage++;
if (_pool_usage > 1) return;
if (_pool_usage == 0) goto overflow;
if (_pool_usage == 1)
{
// possible pool inits here
return;
}
overflow:
fprintf(stderr, "ERROR: Overflow of blist usage\n");
abort();
}
static void
_pool_unuse(void)
{
_pool_usage--;
if (_pool_usage > 0) return;
// possible pool cleanups here
}
static void
_pool_item_use(void)
{
_pool_item_usage++;
if (_pool_item_usage > 1) return;
if (_pool_item_usage == 0) goto overflow;
if (_pool_item_usage == 1)
{
// possible pool inits here
return;
}
overflow:
fprintf(stderr, "ERROR: Overflow of blist usage\n");
abort();
}
static void
_pool_item_unuse(void)
{
_pool_item_usage--;
if (_pool_item_usage > 0) return;
// possible pool cleanups here
}
static Eina_Blist *
_list_alloc(void)
{
Eina_Blist *li;
_pool_use();
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)
{
free(li);
_pool_unuse();
}
static Eina_Blist_Item *
_item_alloc(void)
{
void *ptr;
Eina_Blist_Item *it;
_pool_item_use();
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)
{
free(it);
_pool_item_unuse();
}
static void
_shuffle_up(Eina_Blist_Item *item, unsigned char from, unsigned char to)
{
unsigned char i;
for (i = to; i > from; i--) item->data[i] = item->data[i - 1];
}
static void
_shuffle_down(Eina_Blist_Item *item, unsigned char from, unsigned char to)
{
unsigned char 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, unsigned char at)
{
Eina_Blist_Item *it, *prev;
unsigned char 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;
unsigned char i, count;
it = (*blist)->list;
while (it)
{
// XXX: prefetch it->next
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;
// XXX: prefetch it->next
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]);
// XXX: prefetch l->next
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;
unsigned char i, count;
if (!(*blist)) return NULL;
it = (*blist)->list;
while (it)
{
// XXX: prefetch it->next
count = _count_get(it->prev);
for (i = 0; i < count; i++)
{
if (it->data[i] == data)
{
// 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, 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;
unsigned char i, count;
if (!(*blist)) return NULL;
it = (*blist)->list;
while (it)
{
// XXX: prefetch it->next
count = _count_get(it->prev);
for (i = 0; i < count; i++)
{
if (total == 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, i);
return it;
}
total++;
}
it = it->next;
}
return NULL;
}
void
eina_blist_item_remove(Eina_Blist **blist, Eina_Blist_Item *item)
{
Eina_Blist_Item *it, *prev;
unsigned char 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 (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);
prev->next = 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;
unsigned char i, count;
void (*func) (void *data) = NULL;
if (!(*blist)) return;
it = (*blist)->list;
func = (*blist)->free_func;
while (it)
{
// XXX: prefetch it->next
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;
unsigned char 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;
}
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;
unsigned char 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;
unsigned char i, count;
if (!(*blist)) return 0;
it = (*blist)->list;
while (it)
{
// XXX: prefetch it->next
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;
unsigned char 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;
unsigned char 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;
unsigned char 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;
unsigned char n;
if (!item) return;
it = _ptr_get(item);
n = _count_get(item);
it->data[n] = (void *)data;
}