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

#include "mdb.h"
#include "impl.h"

void*
mdb_calloc(MDB *db, ulong nel, ulong elsize)
{
	void *p;

	do {
		p = calloc(nel, elsize);
	} while(p == nil && mdb_error_oom(db) == 0);

	if(p == nil)
		abort();

	return p;
}

/* put page id into free list */
void
mdb_deallocate(MDB *db, u32int id)
{
	u32int newpid;
	Page *p;
	Freelist *fl;

	p = mdb_readpage(db, db->meta.freelist, T_FREELIST);
	fl = &p->free;

	if(fl->count == FREESIZE){
		mdb_putpage(db, p);

		newpid = mdb_allocate(db);

		p = mdb_getpage(db);
		p->id = newpid;
		p->type = T_FREELIST;
		p->free.next = db->meta.freelist;
		db->meta.freelist = p->id;

		fl = &p->free;
	}

	fl->ids[fl->count++] = id;

	mdb_writepage(db, p);
}

static void
mdb_grow(MDB *db, u32int pgs)
{
	int n, rv;
	Dir d;

	/* no need to grow */
	if(pgs <= db->size)
		return;

	/* expand file */
	nulldir(&d);
	d.length = pgs * BLOCK;
	do {
		rv = dirfwstat(db->fd, &d);
	} while(rv < 0 && mdb_error_io(db) == 0);

	if(rv < 0)
		abort();

	/* insert blocks into free list */
	n = pgs - db->size;

	while(n-- > 0)
		mdb_deallocate(db, db->meta.pgid++);

	db->size = pgs;

	mdb_syncmeta(db);
}

static int
mdb_pidcmp(void *a, void *b)
{
	u32int ua, ub;

	ua = *(u32int*)a;
	ub = *(u32int*)b;

	if(ua < ub)
		return -1;
	if(ua > ub)
		return 1;
	return 0;
}

/* get a free block from a freelist */
static u32int
mdb_allocate_from(Freelist *fl)
{
	u32int pid;

	if(fl->count == 0)
		return NOPAGE;

	/* keep the current list sorted, and take pages off the front. */

	pid = fl->ids[0];

	if(fl->count > 0){
		memmove(&fl->ids[0], &fl->ids[1], (fl->count-1) * sizeof(fl->ids[0]));
		fl->ids[fl->count-1] = 0;
		qsort(fl->ids, fl->count-1, sizeof(fl->ids[0]), mdb_pidcmp);
	} else
		fl->ids[0] = 0;

	fl->count--;

	return pid;
}

enum {
	/* grow a quarter freelist at a time */
	EXPAND	= FREESIZE/4,
};

#define MORE(x) (((x+EXPAND)/EXPAND)*EXPAND)

/* allocate a page. resize db if no unused pages. */
u32int
mdb_allocate(MDB *db)
{
	u32int pid;
	Page *p;
	Freelist *fl;

	/* check current free list */
checkfree:
	p = mdb_readpage(db, db->meta.freelist, T_FREELIST);
	fl = &p->free;

	pid = mdb_allocate_from(fl);
	if(pid != NOPAGE){
		mdb_writepage(db, p);
		return pid;
	}

	if(fl->next != 0){
		/* deallocate this freelist and move to previous one */

		db->meta.freelist = fl->next;
		pid = mdb_allocate(db);

		mdb_deallocate(db, p->id);

		mdb_syncmeta(db);

		mdb_putpage(db, p);

		return pid;
	}

	/* nothing in free list, need to grow. */
	mdb_putpage(db, p);

	mdb_grow(db, MORE(db->size));

	goto checkfree;
}