/* database file */
#define BIDB_FILE "boris.bidb"

#define BIDB_DEFAULT_MAX_RECORDS 131072
#define BIDB_MAX_BLOCKS 4194304
#define BIDB_GROW_BLOCKS 256 /* number of blocks to grow by */

/*=* Linked list macros *=*/
#define LIST_ENTRY(type) struct { type *_next, **_prev; }
#define LIST_HEAD(headname, type) headname { type *_head; }
#define LIST_INIT(head) ((head)->_head=NULL)
#define LIST_ENTRY_INIT(elm, name) do { (elm)->name._next=NULL; (elm)->name._prev=NULL; } while(0)
#define LIST_TOP(head) ((head)._head)
#define LIST_NEXT(elm, name) ((elm)->name._next)
#define LIST_PREVPTR(elm, name) ((elm)->name._prev)
#define LIST_INSERT_ATPTR(prevptr, elm, name) do { \
	(elm)->name._prev=(prevptr); \
	if(((elm)->name._next=*(prevptr))!=NULL) \
		(elm)->name._next->name._prev=&(elm)->name._next; \
	*(prevptr)=(elm); \
	} while(0)
#define LIST_INSERT_AFTER(where, elm, name) do { \
		(elm)->name._prev=&(where)->name._next; \
		if(((elm)->name._next=(where)->name._next)!=NULL) \
			(where)->name._next->name._prev=&(elm)->name._next; \
		*(elm)->name._prev=(elm); \
	} while(0)
#define LIST_INSERT_HEAD(head, elm, name) do { \
		(elm)->name._prev=&(head)->_head; \
		if(((elm)->name._next=(head)->_head)!=NULL) \
			(head)->_head->name._prev=&(elm)->name._next; \
		(head)->_head=(elm); \
	} while(0)
#define LIST_REMOVE(elm, name) do { \
		if((elm)->name._next!=NULL) \
			(elm)->name._next->name._prev=(elm)->name._prev; \
		if((elm)->name._prev) \
			*(elm)->name._prev=(elm)->name._next; \
	} while(0)

typedef long bidb_blockofs_t;

struct bidb_extent {
	unsigned length, offset; /* both are in block-sized units */
};

/******************************************************************************
 * Freelist
 ******************************************************************************/

/* bucket number to use for overflows */
#define FREELIST_OVERFLOW_BUCKET(flp) (NR((flp)->buckets)-1)

struct freelist_entry {
	LIST_ENTRY(struct freelist_entry) global; /* global list */
	LIST_ENTRY(struct freelist_entry) bucket; /* bucket list */
	struct bidb_extent extent;
};

LIST_HEAD(struct freelist_listhead, struct freelist_entry);

struct freelist {
	/* single list ordered by offset to find adjacent chunks. */
	struct freelist_listhead global;
	/* buckets for each size, last entry is a catch-all for huge chunks */
	unsigned nr_buckets;
	struct freelist_listhead *buckets;
};

static unsigned freelist_ll_bucketnr(struct freelist *fl, unsigned count) {
	unsigned ret;
	ret=count/(fl->nr_buckets-1);
	if(ret>=fl->nr_buckets) {
		ret=FREELIST_OVERFLOW_BUCKET(fl);
	}
	return ret;
}

static void freelist_ll_bucketize(struct freelist *fl, struct freelist_entry *e) {
	unsigned bucket_nr;

	assert(e!=NULL);

	bucket_nr=freelist_ll_bucketnr(fl, e->extent.length);

	/* detach the entry */
	LIST_REMOVE(e, bucket);

	/* push entry on the top of the bucket */
	LIST_INSERT_HEAD(&fl->buckets[bucket_nr], e, bucket);
}

/* lowlevel - detach and free an entry */
static void freelist_ll_free(struct freelist_entry *e) {
	assert(e!=NULL);
	assert(e->global._prev!=NULL);
	assert(e->global._prev!=(void*)0x99999999);
	assert(e->bucket._prev!=NULL);
	LIST_REMOVE(e, global);
	LIST_REMOVE(e, bucket);
#ifndef NDEBUG
	memset(e, 0x99, sizeof *e); /* fill with fake data before freeing */
#endif
	free(e);
}

/* lowlevel - append an extra to the global list at prev */
static struct freelist_entry *freelist_ll_new(struct freelist_entry **prev, unsigned ofs, unsigned count) {
	struct freelist_entry *new;
	assert(prev!=NULL);
	assert(prev!=(void*)0x99999999);
	new=malloc(sizeof *new);
	assert(new!=NULL);
	if(!new) {
		perror("malloc()");
		return 0;
	}
	new->extent.offset=ofs;
	new->extent.length=count;
	LIST_ENTRY_INIT(new, bucket);
	LIST_INSERT_ATPTR(prev, new, global);
	return new;
}

/* returns true if a bridge is detected */
static int freelist_ll_isbridge(struct bidb_extent *prev_ext, unsigned ofs, unsigned count, struct bidb_extent *next_ext) {
	/*
	DEBUG("testing for bridge:\n"
			"  last:%6d+%d curr:%6d+%d ofs:%6d+%d\n",
			prev_ext->offset, prev_ext->length, next_ext->offset, next_ext->length,
			ofs, count
	);
	*/
	return prev_ext->offset+prev_ext->length==ofs && next_ext->offset==ofs+count;
}

EXPORT void freelist_init(struct freelist *fl, unsigned nr_buckets) {
	fl->nr_buckets=nr_buckets+1; /* add one for the overflow bucket */
	fl->buckets=calloc(fl->nr_buckets, sizeof *fl->buckets);
	LIST_INIT(&fl->global);
}

EXPORT void freelist_free(struct freelist *fl) {
	while(LIST_TOP(fl->global)) {
		freelist_ll_free(LIST_TOP(fl->global));
	}
	assert(LIST_TOP(fl->global)==NULL);

#ifndef NDEBUG
	{
		unsigned i;
		for(i=0;i<fl->nr_buckets;i++) {
			assert(LIST_TOP(fl->buckets[i])==NULL);
		}
	}
#endif
}

/* allocate memory from the pool
 * returns offset of the allocation
 * return -1 on failure */
EXPORT long freelist_alloc(struct freelist *fl, unsigned count) {
	unsigned bucketnr, ofs;
	struct freelist_entry **bucketptr, *curr;

	assert(count!=0);

	bucketnr=freelist_ll_bucketnr(fl, count);
	bucketptr=&LIST_TOP(fl->buckets[bucketnr]);
	/* TODO: prioritize the order of the check. 1. exact size, 2. double size 3. ? */
	for(;bucketnr<=FREELIST_OVERFLOW_BUCKET(fl);bucketnr++) {
		assert(bucketnr<=FREELIST_OVERFLOW_BUCKET(fl));
		assert(bucketptr!=NULL);

		if(*bucketptr) { /* found an entry*/
			curr=*bucketptr;
			DEBUG("curr->extent.length:%u count:%u\n", curr->extent.length, count);
			assert(curr->extent.length>=count);
			ofs=curr->extent.offset;
			curr->extent.offset+=count;
			curr->extent.length-=count;
			if(curr->extent.length==0) {
				freelist_ll_free(curr);
			} else {
				/* place in a new bucket */
				freelist_ll_bucketize(fl, curr);
			}
			return ofs;
		}
	}
	return -1;
}

/* adds a piece to the freelist pool
 *
 * . allocated
 * _ empty
 * X new entry
 *
 * |.....|_XXX_|......|		normal
 * |.....|_XXX|.......|		grow-next
 * |......|XXX_|......|		grow-prev
 * |......|XXX|.......|		bridge
 *
 * WARNING: passing bad parameters will result in strange data in the list
 * */
EXPORT void freelist_pool(struct freelist *fl, unsigned ofs, unsigned count) {
	struct freelist_entry *new, *curr, *last;

	TRACE_ENTER();

	assert(count!=0);

	last=NULL;
	new=NULL;
	for(curr=LIST_TOP(fl->global);curr;curr=LIST_NEXT(curr, global)) {
		assert(curr!=last);
		assert(curr!=(void*)0x99999999);
		if(last) {
			assert(LIST_NEXT(last, global)==curr); /* sanity check */
		}
		/*
		printf(
			"c.ofs:%6d c.len:%6d l.ofs:%6d l.len:%6d ofs:%6d len:%6d\n",
			curr->extent.offset, curr->extent.length,
			last ? last->extent.offset : -1, last ? last->extent.length : -1,
			ofs, count
		);
		*/

		if(ofs==curr->extent.offset) {
			fprintf(stderr, "overlap detected in freelist %p at %u+%u!\n", (void*)fl, ofs, count);
			abort(); /* TODO: make something out of this */
		} else if(last && freelist_ll_isbridge(&last->extent, ofs, count, &curr->extent)) {
			/* |......|XXX|.......|		bridge */
			DEBUG("|......|XXX|.......|		bridge. last=%u+%u curr=%u+%u new=%u+%u\n", last->extent.length, last->extent.offset, curr->extent.offset, curr->extent.length, ofs, count);
			/* we are dealing with 3 entries, the last, the new and the current */
			/* merge the 3 entries into the last entry */
			last->extent.length+=curr->extent.length+count;
			assert(LIST_PREVPTR(curr, global)==&LIST_NEXT(last, global));
			freelist_ll_free(curr);
			assert(LIST_TOP(fl->global)!=curr);
			assert(LIST_NEXT(last, global)!=(void*)0x99999999);
			assert(LIST_NEXT(last, global)!=curr); /* deleting it must take it off the list */
			new=curr=last;
			break;
		} else if(curr->extent.offset==ofs+count) {
			/* |.....|_XXX|.......|		grow-next */
			DEBUG("|.....|_XXX|.......|		grow-next. curr=%u+%u new=%u+%u\n", curr->extent.offset, curr->extent.length, ofs, count);
			/* merge new entry into a following entry */
			curr->extent.offset=ofs;
			curr->extent.length+=count;
			new=curr;
			break;
		} else if(last && curr->extent.offset+curr->extent.length==ofs) {
			/* |......|XXX_|......|		grow-prev */
			DEBUG("|......|XXX_|......|		grow-prev. curr=%u+%u new=%u+%u\n", curr->extent.offset, curr->extent.length, ofs, count);
			/* merge the new entry into the end of the previous entry */
			curr->extent.length+=count;
			new=curr;
			break;
		} else if(ofs<curr->extent.offset) {
			if(ofs+count>curr->extent.offset) {
				fprintf(stderr, "overlap detected in freelist %p at %u+%u!\n", (void*)fl, ofs, count);
				abort(); /* TODO: make something out of this */
			}
			DEBUG("|.....|_XXX_|......|		normal new=%u+%u\n", ofs, count);
			/* create a new entry */
			new=freelist_ll_new(LIST_PREVPTR(curr, global), ofs, count);
			break;
		}

		last=curr; /* save this for finding a bridge */
	}
	if(!curr) {
		if(last) {
			if(last->extent.offset+last->extent.length==ofs) {
				DEBUG("|......|XXX_|......|		grow-prev. last=%u+%u new=%u+%u\n", last->extent.offset, last->extent.length, ofs, count);
				last->extent.length+=count;
				new=last;
			} else {
				DEBUG("|............|XXX  |		end. new=%u+%u\n", ofs, count);
				new=freelist_ll_new(&LIST_NEXT(last, global), ofs, count);
			}
		} else {
			DEBUG("|XXX               |		initial. new=%u+%u\n", ofs, count);
			new=freelist_ll_new(&LIST_TOP(fl->global), ofs, count);
		}
	}

	/* push entry into bucket */
	if(new) {
		freelist_ll_bucketize(fl, new);
	}
}

#ifndef NDEBUG
EXPORT void freelist_dump(struct freelist *fl) {
	struct freelist_entry *curr;
	unsigned n;
	fprintf(stderr, "::: Dumping freelist :::\n");
	for(curr=LIST_TOP(fl->global),n=0;curr;curr=LIST_NEXT(curr, global),n++) {
		printf("[%05u] ofs: %6d len: %6d\n", n, curr->extent.offset, curr->extent.length);
	}
}

EXPORT void freelist_test(void) {
	struct freelist fl;
	unsigned n;
	freelist_init(&fl, 1024);
	fprintf(stderr, "::: Making some fragments :::\n");
	for(n=0;n<60;n+=12) {
		freelist_pool(&fl, n, 6);
	}
	fprintf(stderr, "::: Filling in gaps :::\n");
	for(n=0;n<60;n+=12) {
		freelist_pool(&fl, n+6, 6);
	}
	fprintf(stderr, "::: Walking backwards :::\n");
	for(n=120;n>60;) {
		n-=6;
		freelist_pool(&fl, n, 6);
	}

	freelist_dump(&fl);

	/* test freelist_alloc() */
	fprintf(stderr, "::: Allocating :::\n");
	for(n=0;n<60;n+=6) {
		long ofs;
		ofs=freelist_alloc(&fl, 6);
		TRACE("alloc: %lu+%u\n", ofs, 6);
	}

	freelist_dump(&fl);

	fprintf(stderr, "::: Allocating :::\n");
	for(n=0;n<60;n+=6) {
		long ofs;
		ofs=freelist_alloc(&fl, 6);
		TRACE("alloc: %lu+%u\n", ofs, 6);
	}

	freelist_dump(&fl);

	freelist_free(&fl);
}
#endif

/******************************************************************************
 * Bitmap API
 ******************************************************************************/

#define BITMAP_BITSIZE (sizeof(unsigned)*CHAR_BIT)

struct bitmap {
	unsigned *bitmap;
	size_t bitmap_allocbits;
};

EXPORT void bitmap_init(struct bitmap *bitmap) {
	assert(bitmap!=NULL);
	bitmap->bitmap=0;
	bitmap->bitmap_allocbits=0;
}

EXPORT void bitmap_free(struct bitmap *bitmap) {
	assert(bitmap!=NULL); /* catch when calling free on NULL */
	if(bitmap) {
		free(bitmap->bitmap);
		bitmap_init(bitmap);
	}
}

/* newbits is in bits (not bytes) */
EXPORT int bitmap_resize(struct bitmap *bitmap, size_t newbits) {
	unsigned *tmp;

	newbits=ROUNDUP(newbits, BITMAP_BITSIZE);
	DEBUG("%s():Allocating %zd bytes\n", __func__, newbits/CHAR_BIT);
	tmp=realloc(bitmap->bitmap, newbits/CHAR_BIT);
	if(!tmp) {
		perror("realloc()");
		return 0; /* failure */
	}
	if(bitmap->bitmap_allocbits<newbits) {
		/* clear out the new bits */
		size_t len;
		len=(newbits-bitmap->bitmap_allocbits)/CHAR_BIT;
		DEBUG("%s():Clearing %zd bytes (ofs %zd)\n", __func__, len, bitmap->bitmap_allocbits/BITMAP_BITSIZE);
		memset(tmp+bitmap->bitmap_allocbits/BITMAP_BITSIZE, 0, len);
	}

	bitmap->bitmap=tmp;
	bitmap->bitmap_allocbits=newbits;
	return 1; /* success */
}

EXPORT void bitmap_clear(struct bitmap *bitmap, unsigned ofs, unsigned len) {
	unsigned *p, mask;
	unsigned head_ofs, head_len;

	/* allocate more */
	if(ofs+len>bitmap->bitmap_allocbits) {
		bitmap_resize(bitmap, ofs+len);
	}

	p=bitmap->bitmap+ofs/BITMAP_BITSIZE; /* point to the first word */

	head_ofs=ofs%BITMAP_BITSIZE;
	head_len=len>BITMAP_BITSIZE-ofs ? BITMAP_BITSIZE-ofs : len;

	/* head */
	if(head_len<BITMAP_BITSIZE) {
		len-=head_len;
		mask=~(~((~0U)<<head_len)<<head_ofs);
		*p++&=mask;
	}

	for(;len>=BITMAP_BITSIZE;len-=BITMAP_BITSIZE) {
		*p++=0U;
	}

	if(len>0) {
		/* tail */
		mask=~((~0U)>>(BITMAP_BITSIZE-len));
		mask=(~0U)>>len;
		*p&=mask;
	}
}

EXPORT void bitmap_set(struct bitmap *bitmap, unsigned ofs, unsigned len) {
	unsigned *p, mask;
	unsigned head_ofs, head_len;

	/* allocate more */
	if(ofs+len>bitmap->bitmap_allocbits) {
		bitmap_resize(bitmap, ofs+len);
	}

	p=bitmap->bitmap+ofs/BITMAP_BITSIZE; /* point to the first word */

	head_ofs=ofs%BITMAP_BITSIZE;
	head_len=len>BITMAP_BITSIZE-ofs ? BITMAP_BITSIZE-ofs : len;

	/* head */
	if(head_len<BITMAP_BITSIZE) {
		len-=head_len;
		mask=(~((~0U)<<head_len))<<head_ofs;
		*p++|=mask;
	}

	for(;len>=BITMAP_BITSIZE;len-=BITMAP_BITSIZE) {
		*p++=~0U;
	}

	if(len>0) {
		/* tail */
		mask=(~0U)>>(BITMAP_BITSIZE-len);
		*p|=mask;
	}
}

/* gets a single bit */
EXPORT int bitmap_get(struct bitmap *bitmap, unsigned ofs) {
	if(ofs<bitmap->bitmap_allocbits) {
		return (bitmap->bitmap[ofs/BITMAP_BITSIZE]>>(ofs%BITMAP_BITSIZE))&1;
	} else {
		return 0; /* outside of the range, the bits are cleared */
	}
}

/* return the position of the next set bit
 * -1 if the end of the bits was reached */
EXPORT int bitmap_next_set(struct bitmap *bitmap, unsigned ofs) {
	unsigned i, len, bofs;
	assert(bitmap != NULL);
	len=bitmap->bitmap_allocbits/BITMAP_BITSIZE;
	/* TODO: check the head */
	for(i=ofs/BITMAP_BITSIZE;i<len;i++) {
		if(bitmap->bitmap[i]!=0) {
			/* found a set bit - scan the word to find the position */
			for(bofs=0;((bitmap->bitmap[i]>>bofs)&1)==0;bofs++) ;
			return i*BITMAP_BITSIZE+bofs;
		}
	}
	/* TODO: check the tail */
	return -1; /* outside of the range */
}

/* return the position of the next set bit
 * -1 if the end of the bits was reached */
EXPORT int bitmap_next_clear(struct bitmap *bitmap, unsigned ofs) {
	unsigned i, len, bofs;
	assert(bitmap != NULL);
	len=bitmap->bitmap_allocbits/BITMAP_BITSIZE;
	/* TODO: check the head */
	for(i=ofs/BITMAP_BITSIZE;i<len;i++) {
		if(bitmap->bitmap[i]!=~0U) {
			/* found a set bit - scan the word to find the position */
			for(bofs=0;((bitmap->bitmap[i]>>bofs)&1)==1;bofs++) ;
			return i*BITMAP_BITSIZE+bofs;
		}
	}
	/* TODO: check the tail */
	return -1; /* outside of the range */
}

/* loads a chunk of memory into the bitmap buffer
 * erases previous bitmap buffer
 * len is in bytes */
EXPORT void bitmap_loadmem(struct bitmap *bitmap, unsigned char *d, size_t len) {
	unsigned *p, word_count, i;

	/* resize if too small */
	if((len*CHAR_BIT)>bitmap->bitmap_allocbits) {
		bitmap_resize(bitmap, len*CHAR_BIT);
	}

	p=bitmap->bitmap;
	word_count=len/sizeof *p; /* number of words in d */

	/* first do the words */
	while(word_count>0) {
		i=sizeof *p-1;
		*p=0;
		do {
			*p|=*d<<(i*CHAR_BIT);
			d++;
		} while(--i);
		p++;
		word_count--;
		len-=sizeof *p;
	}

	/* finish the remaining */
	i=sizeof *p-1;
	while(len>0) {
		*p&=0xff<<(i*CHAR_BIT);
		*p|=*d<<(i*CHAR_BIT);
		i--;
		d++;
		len--;
	}
}

/* returns the length in bytes of the entire bitmap table */
EXPORT unsigned bitmap_length(struct bitmap *bitmap) {
	return bitmap ? ROUNDUP(bitmap->bitmap_allocbits, CHAR_BIT)/CHAR_BIT : 0;
}

#ifndef NDEBUG
EXPORT void bitmap_test(void) {
	int i;
	struct bitmap bitmap;

	bitmap_init(&bitmap);
	bitmap_resize(&bitmap, 1024);
	/* fill in with a test pattern */
	for(i=0;i<5;i++) {
		bitmap.bitmap[i]=0x12345678;
	}

	bitmap_set(&bitmap, 7, 1);
	/* display the test pattern */
	printf("bitmap_set():\n");
	for(i=0;i<5;i++) {
		printf("0x%08x %s\n", bitmap.bitmap[i], convert_number(bitmap.bitmap[i], 2, 32));
	}

	bitmap_set(&bitmap, 12, 64);
	/* display the test pattern */
	printf("bitmap_set():\n");
	for(i=0;i<5;i++) {
		printf("0x%08x %s\n", bitmap.bitmap[i], convert_number(bitmap.bitmap[i], 2, 32));
	}

	bitmap_clear(&bitmap, 7, 1);
	/* display the test pattern */
	printf("bitmap_clear():\n");
	for(i=0;i<5;i++) {
		printf("0x%08x %s\n", bitmap.bitmap[i], convert_number(bitmap.bitmap[i], 2, 32));
	}

	bitmap_clear(&bitmap, 12, 64);
	/* display the test pattern */
	printf("bitmap_clear():\n");
	for(i=0;i<5;i++) {
		printf("0x%08x %s\n", bitmap.bitmap[i], convert_number(bitmap.bitmap[i], 2, 32));
	}

	bitmap_set(&bitmap, 0, BITMAP_BITSIZE*5);
	/* display the test pattern */
	printf("bitmap_set():\n");
	for(i=0;i<5;i++) {
		printf("0x%08x %s\n", bitmap.bitmap[i], convert_number(bitmap.bitmap[i], 2, 32));
	}

	bitmap_clear(&bitmap, 0, BITMAP_BITSIZE*5);
	bitmap_set(&bitmap, 101, 1);
	printf("word at bit 101 = 0x%08x\n", bitmap.bitmap[101/BITMAP_BITSIZE]);
	printf("next set starting at 9 = %d\n", bitmap_next_set(&bitmap, 9));
	bitmap_clear(&bitmap, 101, 1);

	bitmap_set(&bitmap, 0, 101);
	printf("next clear starting at 9 = %d\n", bitmap_next_clear(&bitmap, 9));
	bitmap_clear(&bitmap, 0, 101);

	bitmap_clear(&bitmap, 0, BITMAP_BITSIZE*5);
	printf("next set should return -1 = %d\n", bitmap_next_set(&bitmap, 0));

	bitmap_free(&bitmap);
}
#endif

/******************************************************************************
 * Binary Database
 ******************************************************************************/

/*
 * Binary database
 * ===============
 * block size=1024. everything is in multiples of a block
 *
 * extents are 32-bits values. 22-bit offset, 10-bit length
 *
 * extent length is 1 to 1024. (0 is not a valid encoding)
 *
 * [ON-DISK]
 *
 * superblock
 * 	magic
 * 	record table extents [16]
 *
 * record table
 * 	record extent [n]
 *
 * [IN-MEMORY]
 *
 * max records
 * record table extents
 * hash table for id to extent
 * freelist
 * block bitmap
 *
 * [TYPES OF RECORDS]
 *
 * object_base/object_mob/object_item/object_room
 * sparse integer to record number table
 * string to record number table
 * sparse record number to string table
 *
 */

#define BIDB_BLOCK_SZ 1024
#define BIDB_SUPERBLOCK_SZ	1 /* size in blocks */

/* macros for manipulating extent descriptors */
#define BIDB_EXTENT_LENGTH_BITS 10U
#define BIDB_EXTENT_OFFSET_BITS (32U-BIDB_EXTENT_LENGTH_BITS)
#define BIDB_EXTENT(o,l) (((o)<<BIDB_EXTENT_LENGTH_BITS)|((l)-1))
#define BIDB_EXTENT_NONE 0U		/* this value means at block 0 you must be at least 2 blocks long */
#define BIDB_EXTENT_LENGTH(e)	(((e)&((1<<BIDB_EXTENT_LENGTH_BITS)-1))+1)
#define BIDB_EXTENT_OFFSET(e)	((uint_least32_t)(e)>>BIDB_EXTENT_LENGTH_BITS)
/* an extent is a 32 bit value */
#define BIDB_EXTENTPTR_SZ (32/CHAR_BIT)
/* size of a record pointer (1 extent) */
#define BIDB_RECPTR_SZ BIDB_EXTENTPTR_SZ
#define BIDB_RECORDS_PER_BLOCK (BIDB_BLOCK_SZ/BIDB_RECPTR_SZ)
#define BIDB_RECORDS_PER_EXTENT (BIDB_RECORDS_PER_BLOCK<<BIDB_EXTENT_LENGTH_BITS)

static struct {
	struct bidb_extent record_extents[16];
	unsigned record_dirty_blocks[BITFIELD(16<<BIDB_EXTENT_LENGTH_BITS,unsigned)]; /* one bit per block - 2Kbyte of bits total */
	unsigned record_max, block_max;
	struct bidb_stats {
		unsigned records_used;
	} stats;
	struct freelist freelist;
	FILE *file;
	char *filename;
} bidb_superblock;

EXPORT void bidb_close(void) {
#ifndef NDEBUG
	freelist_dump(&bidb_superblock.freelist);
#endif
	freelist_free(&bidb_superblock.freelist);
	if(bidb_superblock.file) {
		fclose(bidb_superblock.file);
		bidb_superblock.file=0;
	}
	free(bidb_superblock.filename);
	bidb_superblock.filename=0;
}

/* block_offset starts AFTER superblock */
static int bidb_read_blocks(unsigned char *data, bidb_blockofs_t block_offset, unsigned block_count) {
	size_t res;
	if(fseek(bidb_superblock.file, (block_offset+BIDB_SUPERBLOCK_SZ)*BIDB_BLOCK_SZ, SEEK_SET)) {
		perror(bidb_superblock.filename);
		return 0; /* failure */
	}
	res=fread(data, BIDB_BLOCK_SZ, block_count, bidb_superblock.file);
	if(res!=block_count) {
		if(ferror(bidb_superblock.file)) {
			perror(bidb_superblock.filename);
		}
		return 0; /* failure */
	}
	return 1; /* success */
}

/* block_offset starts AFTER superblock */
static int bidb_write_blocks(const unsigned char *data, bidb_blockofs_t block_offset, unsigned block_count) {
	size_t res;

	if(fseek(bidb_superblock.file, (block_offset+BIDB_SUPERBLOCK_SZ)*BIDB_BLOCK_SZ, SEEK_SET)) {
		perror(bidb_superblock.filename);
		return 0; /* failure */
	}
	res=fwrite(data, BIDB_BLOCK_SZ, block_count, bidb_superblock.file);
	if(res!=block_count) {
		if(ferror(bidb_superblock.file)) {
			perror(bidb_superblock.filename);
		}
		return 0; /* failure */
	}
	return 1; /* success */
}

static struct bidb_extent bidb_allocblocks(unsigned nr_blocks) {
	struct bidb_extent ret;
	long ofs;
	unsigned newlen;

	assert(nr_blocks>0);
	ofs=freelist_alloc(&bidb_superblock.freelist, nr_blocks);
	if(ofs==-1) {
		/* grow */
		if(BIDB_GROW_BLOCKS<nr_blocks) {
			newlen=bidb_superblock.block_max+nr_blocks+BIDB_GROW_BLOCKS;
		} else {
			newlen=bidb_superblock.block_max+BIDB_GROW_BLOCKS;
		}
		fprintf(stderr, "%s:growing file to %u blocks from %u blocks maximum.\n", bidb_superblock.filename, newlen, bidb_superblock.block_max);
		freelist_pool(&bidb_superblock.freelist, bidb_superblock.block_max, newlen-bidb_superblock.block_max);
		bidb_superblock.block_max=newlen;
		ofs=freelist_alloc(&bidb_superblock.freelist, nr_blocks);
		assert(ofs!=-1);
	}
	ret.offset=ofs;
	ret.length=nr_blocks;
	return ret;
}

/* check extent to see if it is in range of nr_blocks */
static int bidb_check_extent(struct bidb_extent *e, unsigned nr_blocks) {
	unsigned end;
	assert(e!=NULL);
	if(!e)
		return 1; /* ignore */
	if(e->length==0) {
		return 1; /* zero length extents don't exist */
	}
	end=(e->length+e->offset); /* end is last+1 */
	DEBUG("end:%u blocks:%u\n", end, nr_blocks);
	return (end<=nr_blocks);
}

static int bidb_load_superblock(void) {
	unsigned char data[BIDB_BLOCK_SZ*BIDB_SUPERBLOCK_SZ];
	uint_least32_t tmp;
	unsigned i, total_record_length;
	long filesize;
	int empty_fl;

	/* get the file size and check it */
	fseek(bidb_superblock.file, 0, SEEK_END);
	filesize=ftell(bidb_superblock.file);
	if((filesize%BIDB_BLOCK_SZ)!=0) {
		fprintf(stderr, "%s:database file is not a multiple of %u bytes\n", bidb_superblock.filename, BIDB_BLOCK_SZ);
		return 0;
	}
	bidb_superblock.block_max=filesize/BIDB_BLOCK_SZ;
	if(bidb_superblock.block_max>0) {
		bidb_superblock.block_max--; /* do not count the superblock */
	}

	if(bidb_read_blocks(data, -BIDB_SUPERBLOCK_SZ, BIDB_SUPERBLOCK_SZ)) {
		if(memcmp("BiDB", data, 4)) {
			fprintf(stderr, "%s:not a data file\n", bidb_superblock.filename);
			return 0; /* failure : invalid magic */
		}
		bidb_superblock.stats.records_used=0;

		memset(&bidb_superblock.record_dirty_blocks, 0, sizeof bidb_superblock.record_dirty_blocks);

		for(i=0,total_record_length=0;i<NR(bidb_superblock.record_extents);i++) {
			tmp=RD_BE32(data, 4+4*i);

			if(tmp==BIDB_EXTENT_NONE) { /* empty extent */
				bidb_superblock.record_extents[i].offset=0;
				bidb_superblock.record_extents[i].length=0;
			} else {
				bidb_superblock.record_extents[i].offset=BIDB_EXTENT_OFFSET(tmp);
				bidb_superblock.record_extents[i].length=BIDB_EXTENT_LENGTH(tmp);
			}
			total_record_length+=bidb_superblock.record_extents[i].length;
		}
		bidb_superblock.record_max=BIDB_BLOCK_SZ/BIDB_RECPTR_SZ*total_record_length;

		/** sanity checks **/

		for(i=0, empty_fl=0;i<NR(bidb_superblock.record_extents);i++) {
			if(bidb_superblock.record_extents[i].length==0) { /* empty extent */
				empty_fl=1;
			} else if(empty_fl) {
				fprintf(stderr, "%s:record table extent list has holes in it\n", bidb_superblock.filename);
				return 0;
			}
		}

		for(i=0;i<NR(bidb_superblock.record_extents);i++) {
			if(!bidb_check_extent(&bidb_superblock.record_extents[i], filesize/(unsigned)BIDB_BLOCK_SZ-BIDB_SUPERBLOCK_SZ)) {
				fprintf(stderr, "%s:record table %u extent exceeds file size\n", bidb_superblock.filename, i);
				return 0;
			}
		}

		return 1; /* success */
	}
	fprintf(stderr, "%s:could not load superblock\n", bidb_superblock.filename);
	return 0; /* failure : could not read superblock */
}

static int bidb_save_superblock(void) {
	unsigned char data[BIDB_BLOCK_SZ];
	uint_least32_t tmp;
	unsigned i;

	fprintf(stderr, "%s:saving superblock\n", bidb_superblock.filename);

	memset(data, 0, sizeof data);
	memcpy(data, "BiDB", 4);

	for(i=0;i<NR(bidb_superblock.record_extents);i++) {
		if(bidb_superblock.record_extents[i].length==0) { /* empty extent */
			tmp=BIDB_EXTENT_NONE;
		} else {
			tmp=BIDB_EXTENT(bidb_superblock.record_extents[i].offset, bidb_superblock.record_extents[i].length);
		}
		WR_BE32(data, 4+4*i, tmp);
	}

	if(!bidb_write_blocks(data, -BIDB_SUPERBLOCK_SZ, 1)) {
		fprintf(stderr, "%s:could not write superblock\n", bidb_superblock.filename);
		return 0; /* failure */
	}
	return 1; /* success */
}

static int bidb_save_record_table(void) {
	unsigned char data[BIDB_BLOCK_SZ];
	unsigned i, j, ofs;
	fprintf(stderr, "Saving record table\n");
	/* uses bitarray to save only blocks with dirty entries */
	for(i=0,ofs=0;i<NR(bidb_superblock.record_extents);i++) {
		for(j=0;j<bidb_superblock.record_extents[i].length;j++,ofs++) {
			if(BITTEST(bidb_superblock.record_dirty_blocks, ofs)) {
				/*
				DEBUG("%s:writing record block %d\n", bidb_superblock.filename, ofs);
				*/
				BITCLR(bidb_superblock.record_dirty_blocks, ofs);
				memset(data, 0, sizeof data); /* TODO: fill with record data */
				if(!bidb_write_blocks(data, (signed)(bidb_superblock.record_extents[i].offset+j), 1)) {
					DEBUG("%s:could not write record table\n", bidb_superblock.filename);
					return 0; /* failure */
				}
			}
		}
	}
	return 1;
}

static int bidb_create_record_table(void) {
	unsigned i, total, extentblks;
	assert(bidb_superblock.record_extents[0].offset==0); /* only safe to call if we have no table */

	/* create the record table on disk */
	fprintf(stderr, "Creating new record table\n");

	bidb_superblock.record_max=BIDB_DEFAULT_MAX_RECORDS;

	/* create all the extents necessary */
	for(i=0,total=0;i<NR(bidb_superblock.record_extents) && total<bidb_superblock.record_max;i++, total++) {
		extentblks=ROUNDUP((bidb_superblock.record_max-total)*BIDB_RECPTR_SZ, BIDB_BLOCK_SZ)/BIDB_BLOCK_SZ;
		if(extentblks>1U<<(BIDB_EXTENT_LENGTH_BITS)) {
			extentblks=1<<BIDB_EXTENT_LENGTH_BITS;
		}

		bidb_superblock.record_extents[i]=bidb_allocblocks(extentblks);

		DEBUG("%s:Record table allocating extent #%u @ %u+%u\n", bidb_superblock.filename, i, bidb_superblock.record_extents[i].offset, bidb_superblock.record_extents[i].length);

		total+=extentblks*BIDB_RECORDS_PER_BLOCK;
	}

	/* mark all the blocks for these new extents as dirty */
	for(i=0;i<bidb_superblock.record_max/BIDB_RECORDS_PER_BLOCK;i++) {
		BITSET(bidb_superblock.record_dirty_blocks, i);
	}

	bidb_save_record_table();

	/* updated the superblock with the record table */
	if(!bidb_save_superblock()) {
		bidb_close();
		return 0; /* failure */
	}

	return 1; /* success */
}

/* load a record table form disk */
static int bidb_load_record_table(void) {
	if(!recordcache_init(bidb_superblock.record_max)) {
		fprintf(stderr, "%s:could not initialize record table\n", bidb_superblock.filename);
		return 0;
	}
	if(bidb_superblock.record_extents[0].length==0) { /* no record table found .. create it */
		if(!bidb_create_record_table()) {
			return 0;
		}
	} else {
		/* TODO: read in record table entries */
		/* TODO: reserve entries */
	}
	return 1; /* */
}

/* mark a record as dirty due to modification */
EXPORT void bidb_record_dirty(unsigned record_number) {
	unsigned blknum;

	blknum=record_number/BIDB_RECORDS_PER_BLOCK;

	if(!BITRANGE(bidb_superblock.record_dirty_blocks, blknum)) {
		fprintf(stderr, "%s:Dirty block %u not in range!\n", bidb_superblock.filename, blknum);
		return;
	}

	DEBUG("%s:Dirty block %u\n", bidb_superblock.filename, blknum);
	BITSET(bidb_superblock.record_dirty_blocks, blknum);
}

/* create_fl will create if the superblock does not exist */
EXPORT int bidb_open(const char *filename) {
	int create_fl=0;
	if(bidb_superblock.file)
		bidb_close();
	bidb_superblock.file=fopen(filename, "r+b");
	if(!bidb_superblock.file) {
		fprintf(stderr, "%s:creating a new file\n", filename);
		bidb_superblock.file=fopen(filename, "w+b");
		if(!bidb_superblock.file) {
			perror(filename);
			return 0; /* failure */
		}
		create_fl=1;
	}
	bidb_superblock.filename=strdup(filename);

	if(create_fl) {
		fprintf(stderr, "%s:creating new superblock\n", bidb_superblock.filename);
		bidb_superblock.stats.records_used=0;
		bidb_superblock.record_max=0;
		bidb_superblock.block_max=0;
		if(!bidb_save_superblock()) {
			bidb_close();
			return 0; /* failure */
		}
	}

	if(!bidb_load_superblock()) {
		bidb_close();
		return 0; /* failure */
	}

	freelist_init(&bidb_superblock.freelist, 1<<BIDB_EXTENT_LENGTH_BITS);
	if(bidb_superblock.block_max>0) {
		freelist_pool(&bidb_superblock.freelist, 0, bidb_superblock.block_max);
	}

	if(!bidb_load_record_table()) {
		fprintf(stderr, "%s:could not load record table\n", bidb_superblock.filename);
		bidb_close();
		return 0; /* failure */
	}
	return 1; /* success */
}

EXPORT void bidb_show_info(void) {
#define BIDB_HIGHEST_RECORD
#define BIDB_HIGHEST_BLOCK
	const uint_least32_t
		max_extent_size=(BIDB_BLOCK_SZ<<BIDB_EXTENT_LENGTH_BITS)-1U,
		records_per_block=BIDB_BLOCK_SZ/BIDB_RECPTR_SZ,
		records_per_extent=records_per_block<<BIDB_EXTENT_LENGTH_BITS,
		max_records=NR(bidb_superblock.record_extents)*records_per_extent;

	printf(
		"BiDB configuration info:\n"
		"  block size: %u bytes\n"
		"  max extent size: %u blocks (%" PRIu32 " bytes)\n"
		"  records per block: %" PRIu32 " records\n"
		"  records per extent: %" PRIu32 " records\n"
		"  number of record extents: %zu extents\n"
		"  max number of record: %" PRIu32 " records\n"
		"  max total size for all records: %" PRIu64 " bytes\n"
		"  max blocks: %lu blocks (%" PRIu64 " bytes)\n",
		BIDB_BLOCK_SZ,
		1<<BIDB_EXTENT_LENGTH_BITS,
		max_extent_size,
		records_per_block,
		records_per_extent,
		NR(bidb_superblock.record_extents),
		max_records,
		(uint_least64_t)max_records<<BIDB_EXTENT_LENGTH_BITS,
		1L<<BIDB_EXTENT_OFFSET_BITS,
		(uint_least64_t)BIDB_BLOCK_SZ<<BIDB_EXTENT_OFFSET_BITS
	);
	printf(
		"  memory bytes for dirty records bitmap: %zu\n",
		sizeof bidb_superblock.record_dirty_blocks
	);
}

int main(void) {
	bidb_show_info();
	if(!bidb_open(BIDB_FILE)) {
		printf("Failed\n");
		return EXIT_FAILURE;
	}
	atexit(bidb_close);

}