enum {
	BLOCK	= 4*1024,
	RBLOCK	= BLOCK - sizeof(u32int),
	MAGIC	= 0xdb53494d,

	/* number of page ids in each freelist */
	FREESIZE	= (RBLOCK - (3*4)) / 4,

	/* max key size */
	KEYSIZE		= 246,

	/* numbers of keys per Branch */
//	KEYSPERBRANCH	= (RBLOCK-4-4) / (1+KEYSIZE+4),
	KEYSPERBRANCH	= 16,

	/* number of leaves in Leaf */
//	KEYSPERLEAF	= (RBLOCK-4-4) / (1+KEYSIZE+4+4),
	KEYSPERLEAF	= 15,

	/* number of bytes per data page */
	DATASIZE	= RBLOCK-4-2,

	/* block types */
	T_UNALLOC	= 0,
	T_META		= 1,
	T_FREELIST	= 2,
	T_BRANCH	= 3,
	T_LEAF		= 4,
	T_DATA		= 5,
	T_MAX		= 6,
	T_ANY		= ~0U,

	NOPAGE		= ~0U,
};

typedef struct Meta Meta;
struct Meta {
	u32int	magic;
	u32int	freelist;
	u32int	root;
	u32int	pgid;
};

typedef struct Freelist Freelist;
struct Freelist {
	u32int	next;
	u32int	count;
	u32int	ids[FREESIZE];
};

typedef struct Key Key;
struct Key {
	u8int	len;
	u8int	data[KEYSIZE];
};

typedef struct Branch Branch;
struct Branch {
	u32int	n;
	Key		keys[KEYSPERBRANCH];
	u32int	child[KEYSPERBRANCH+1];
};

typedef struct KeyPair KeyPair;
struct KeyPair {
	Key		key;					/* associated key */
	u32int	pid;					/* first page of value */
	u32int	length;					/* value length in bytes */
};

typedef struct Leaf Leaf;
struct Leaf {
	u32int	n;						/* number of keys in this leaf */
	u32int	next;					/* next linked leaf page */
	KeyPair	keypairs[KEYSPERLEAF];	/* keys+value pages */
};

typedef struct Data Data;
struct Data {
	u32int	next;					/* next data page */
	u16int	length;					/* # bytes in this block */
	u8int	value[DATASIZE];		/* value block */
};

typedef struct Page Page;
struct Page {
	Page	*next;

	u32int	id;
	u16int	type;
	u16int	pad;

	union {
		Meta		meta;
		Freelist	free;
		Branch		branch;
		Leaf		leaf;
		Data		data;
	};
};

struct MDB {
	int		fd;
	u32int	size;		/* # of blocks in db */

	Page	*pool;
	int 	npool;

//	Page	*cache[127];
	Page	*cache[5];
	int		ncache;

	Meta meta;			/* cached meta */
};

/* compile time constants check. */
struct __sizecheck {
	char keysperleaf_must_be_odd[(!(KEYSPERLEAF%2)) * -2 + 1];
	char keysperleaf_gt_3[(!(KEYSPERLEAF >= 3)) * -2 + 1];

	char keysperbranch_must_be_odd[(!(KEYSPERBRANCH)) * -2 + 1];
	char keysperbranch_gt_3[(!(KEYSPERBRANCH >= 3)) * -2 + 1];
};

/* alloc.c */
void* mdb_calloc(MDB *db, ulong nel, ulong elsize);
void mdb_deallocate(MDB *db, u32int id);
u32int mdb_allocate(MDB *db);

/* mdb.c */
int mdb_keycmp(void *a, void *b);
void mdb_syncmeta(MDB *db);
KeyPair* mdb_search_leaf(Leaf *leaf, Key *key);
uchar *mdb_get(MDB *db, uchar *key, int keylen, int *rlen);
int mdb_put(MDB *db, uchar *key, int klen, uchar *value, int vlen);

/* conv.c */
int mdb_unpack(MDB *db, Page *page, uchar b[BLOCK]);
int mdb_pack(MDB *db, Page *page, uchar b[BLOCK]);

/* error.c */
int mdb_error_oom(MDB *db);
int mdb_error_io(MDB *db);
void mdb_error_corrupt(MDB *db);

/* page.c */
int mdb_initpool(MDB *db);
Page *mdb_getpage(MDB *db);
void mdb_putpage(MDB *db, Page *p);
Page *mdb_readpage(MDB *db, u32int id, u32int type);
void mdb_writepage(MDB *db, Page *p);
int mdb_sync(MDB *db);

/* tree.c */
void mdb_tree_insert_leaf_nonfull(Leaf *leaf, KeyPair *keypair);
int mdb_tree_search(MDB *db, KeyPair *search);
int mdb_tree_insert(MDB *db, KeyPair *keypair);

/* value.c */
void mdb_value_delete(MDB *db, u32int headpid);
void mdb_value_read(MDB *db, u32int headpid, u8int *buf, int size);
u32int mdb_value_write(MDB *db, u8int *value, int vlen);