#include <u.h>
#include <base.h>

#include "pool.h"

// -----------------------------------------------------------------------
// globals/macros

#define NOMAGIC        0xDEADFA11u
#define DEADMAGIC      0xDEADDEADu
#define TAILMAGIC0     0xBEu
#define TAILMAGIC1     0xEFu
#define FREEMAGIC      0xBA5EBA11u
#define USEDMAGIC      0x0A110C09u
#define UNUSEDMAGIC   (0xCAB00D1Eu+1)
#define COREMAGIC     (0xC0A1E5CEu+1)
#define CORETAILMAGIC (0xEC5E1A0Cu+1)
#define ALIGNMAGIC     0xA1F1D1C1u

#define POISON        ((void*)0xCAFEBABEu)

// -----------------------------------------------------------------------
// hunk maintenance

#define HUNKTAIL(h)  ((Tail*)((uchar*)(h)+(h)->size-sizeof(Tail)))

static uintptr
gethunksize(mem·Pool *pool, uintptr size)
{
    size += sizeof(Head) + sizeof(Tail);
    if(size < pool->minhunk)
        size = pool->minhunk;
    size = (size+pool->quantum) & ~(pool->quantum-1); // aligns to quantum
    return size;
}

static Head *
sethunksize(Head *h, uintptr size)
{
    Tail *t;

    assert(h->magic != FREEMAGIC);

    h->size = size;

    t = HUNKTAIL(h);
    t->size = size;
    t->magic0 = TAILMAGIC0;
    t->magic1 = TAILMAGIC1;

    return h;
}

static void
checkhunk(mem·Pool *p, Head *h)
{
    switch(h->magic){
        default:
            abort();
        case FREEMAGIC:
        case UNUSEDMAGIC:
        case DEADMAGIC:
        case COREMAGIC:
        case CORETAILMAGIC:
        case USEDMAGIC:
            ;
    }
}

// -----------------------------------------------------------------------
// core maintenance

#define COREHEAD(c)  ((Head*)((uchar*)(c)+(c)->len -sizeof(Head)))

static uintptr
getcoresize(mem·Pool *pool, uintptr size)
{
    size += sizeof(Core) + sizeof(Tail);
    if(size < pool->mincore)
        size = pool->mincore;
    size = (size+pool->quantum) & ~(pool->quantum-1);
    return size;
}

static Core *
setcoresize(Core *c, uintptr size)
{
    Head *h;

    c->len = size;

    h = COREHEAD(c);
    h->size  = 0;
    h->magic = CORETAILMAGIC;

    return c;
}

static void
newcore(mem·Pool *pool, uintptr size)
{
    Core *c;

    // XXX: check for size overflow
 
    if(!(c = pool->mem.alloc(pool->heap, 1, size)))
        return;

    pool->cursize += size;

    /* core header */
    c->magic = COREMAGIC;
    sethunksize((Head*)c, sizeof(Core));
    setcoresize(c, size);
    checkhunk(pool, (Head*)c);
}

// -----------------------------------------------------------------------
// free list maintenance

static Free *
findgreater(Free *root, uintptr size)
{
    Free *last;

    last = nil;
    for(;;){
        if(!root)
            return last;
        if(size == root->size)
            return root;
        if(size < root->size){
            last = root;
            root = root->left;
        }else
            root = root->right;
    }
}

// -----------------------------------------------------------------------
// exported functions

/* constructors / destructors */
mem·Pool*
mem·makepool(mem·Allocator mem, void *heap, char *name, int flags, intptr maxsize, intptr mincore)
{
    mem·Pool *pool = mem.alloc(heap, 1, sizeof(*pool));
    mem·set(pool, sizeof(*pool), 0);

    pool->mem     = mem;
    pool->heap    = heap;
    pool->name    = name;
    pool->flags   = flags;
    pool->mincore = mincore;
    pool->maxsize = maxsize;
 
    return pool;
}

void
mem·freepool(mem·Pool *pool)
{
    void *heap = pool->heap;
    mem·Allocator mem = pool->mem;

    mem.free(heap, pool);
}

/* base functions */

void *
mem·poolalloc(mem·Pool *pool, long n, uintptr eltsize)
{
    Free *node;
    uintptr size, bksz;

    if((size = n*eltsize) >= 0x80000000UL){
        errorf("allocation overflow");
        return nil;
    }

    bksz = gethunksize(pool, size);
    node = findgreater(pool->free, bksz);
    if(!node){
        newcore(pool, getcoresize(pool, bksz));
        if(!(node = findgreater(pool->free, bksz)))
            return nil;
    }



    return nil;
}