#include <u.h>
#include <libc.h>

enum {
        MUsed = (1 << 15),
        MSize = (~(1<<15)),
};

#define Mused MUsed
#define Msize MSize
#define USED(x) ((x & Mused)>>15)
#define SIZE(x) (x & Msize)

typedef struct Memblock Memblock;

struct Memblock {
        u16int st; // [15] used bit, [14:0] len + sizeof(Memblock)
        Memblock *next;
};

/*
memory block layout:;
        struct {
                Memblock header;
                byte data[SIZE(header->st)];
        };
*/

Memblock *memstart;
u16int memused;
u16int memfree;
u8int frees;

Memblock*
nextfree(u16int sz)
{
        Memblock *cur;

        cur = memstart;
        while(cur != nil){
                if((USED(cur->st) == 0) && (SIZE(cur->st) >= sz))
                        return cur;
                cur = cur->next;
        }
        return nil;
}

int
coalesce(Memblock *a, Memblock *b)
{
        u16int asize;

        if(a->next != b)
                return -1;
        if(USED(a->st) || USED(b->st))
                return -1;
        asize = SIZE(a->st) + SIZE(b->st);
        a->next = b->next;
        a->st = asize & Msize;
        return 0;
}

void    // not a real garbage collector ;)
rungc(void)
{
        Memblock *cur, *next;

        cur = memstart;
        next = memstart->next;
        while(next != nil){
                if(!USED(cur->st) && !USED(next->st))
                        coalesce(cur, next);
                cur = cur->next;
                if(cur == nil)
                        break;
                next = cur->next;
        }
        frees = 0;      // if this gets done outside of free, free doesn't need
                                // to do it as well.
}

int  // block to split, new size of block + sizeof(Memblock)
splitblock(Memblock *a, u16int sz)
{
        char *cb;
        void *anext;
        Memblock *mb;
        u16int blen;

        if((SIZE(a->st) - sz > SIZE(a->st)) || (SIZE(a->st) - sz == 0))
                return -1;
        if(USED(a->st))
                return -2;
        if(sz & MUsed)
                return -3;
        cb = a;
        anext = a->next;
        cb += sz;
        mb = (void*)cb;
        mb->st = SIZE(a->st) - sz;
        mb->next = anext;
        a->st = mb;
        a->next = mb;
        return 0;
}

int
allocinit(void *heap, u16int len)
{
        Memblock *mst, *mnext;
        char *cb;
        u16int sza = 0, szb = 0;

        mst = heap;
        if(len < sizeof(Memblock))
                return -1;
        if(USED(len)){
                sza = ~(1<<15);
                szb = len - sza;
                if(szb > (~(1<<15)))
                        return -2;
        } else
                sza = len;
        mst->st = sza;
        mst->next = nil;
        if(szb != 0){
                cb = (void*)mst;
                cb += sza;
                mnext = cb;
                mst->next = mnext;
                mnext->st = szb;
                mnext->next = nil;
        }
        memstart = mst;
        memused = 0;
        memfree = len;
        frees = 0;
        return 0;
}


void*
kalloc(u16int sz)
{
        Memblock *blk;
        char *cb;

        sz += sizeof(Memblock);
        if(!(blk = nextfree(sz))){
                rungc();
                if(!(blk = nextfree(sz)))
                        return nil;
        }
        if(SIZE(blk->st) > sz)
                if(!splitblock(blk, sz))
                        return nil;
        blk->st |= MUsed;
        cb = (void*)blk;
        cb += sizeof(Memblock);
        memfree -= sz;
        memused += sz;
        return (void*)cb;
}

void*
kallocz(u16int sz)
{
        void *ptr;

        if(!(ptr = kalloc(sz)))
                return nil;
        memset(ptr, 0, sz);
        return ptr;
}

int
kfree(void *ptr)
{
        Memblock *blk;
        char *cb;
        u16int sz;

        cb = ptr;
        cb -= sizeof(Memblock);
        blk = (void*)cb;
        if(USED(blk->st))       // check for a double free
                return -1;
        blk->st &= ~MUsed;
        sz = SIZE(blk->st);
        memfree += sz;
        memused -= sz;
        frees++;
        if(frees > FREES2GC)
                rungc();
        return 0;
}

int
memstats(Memstats *stats)
{
        u16int blks = 0, ublks = 0, fnd = 0;
        Memblock *cur;

        cur = memstart;
        stats->total = memused+memfree;
        stats->used = memused;
        stats->free = memfree;
        stats->sincegc = frees;
        while(cur != nil){
                blks++;
                fnd += SIZE(cur->st);
                if(USED(cur->st))
                        ublks++;
                cur = cur->next;
        }
        stats->ublocks = ublks;
        stats->blocks = blks;
        stats->found = fnd;
        return 0;
}