/*
Copyright (c) 2007-2013, John Ryland
*/


// malloc implementation

int index(int size)
{
    int b = 0;
    if (!size)
		return 0;
    size--;
    while (size) {
		size >>= 1;
		b++;
    }
    return b;
}


unsigned *free_lists[32] = {0,0,...};


void *malloc(int size)
{
    int free_list_idx = index(size + 4);
    size = 1 << free_list_idx;
    unsigned *mem = free_lists[free_list_idx];
    if (!mem) {
		int next_free_index = free_list_idx;
		while (!mem && next_free_index != 32) {
			mem = free_lists[next_free_index];
			next_free_index++;
		}
		if (!mem) {
			// mem = ...  // need mem from OS
		} else {
			free_lists[next_free_index] = (unsigned *)*mem;
			next_free_index--;
		}
		while (next_free_index >= 3) {
			size = 1 << next_free_index;
			mem[size >> 2] = 0;
			free_lists[next_free_index] = &mem[size >> 2];
			next_free_index--;
		}
		mem = free_lists[free_list_idx];
    }
    free_lists[free_list_idx] = (unsigned *)*mem;
    *mem = free_list_idx;
    return (void *)(mem + 1);
}

void free(void *mem)
{
    unsigned *m = mem;
    m = m - 1;
    unsigned index = *m;
    *m = (unsigned)free_lists[index];
    free_lists[index] = m;
}


// ref counting


// Not very efficient atomic
#define ATOMIC(x) \
    {\
		init_mutex();\
		x\
		done_mutex();\
    }


#define COPY(p,q) \
    if (q) \
		ATOMIC(++(q->refcount);) \
    if (p) { \
		size_t new_count; \
		ATOMIC(new_count = --(p->refcount);) \
		if (!new_count) \
			free(p); \
	} \
    p = q;