/*
 * Copyright (c) 2005 Teodor Sigaev <teodor@sigaev.ru>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the author nor the names of any co-contributors
 *      may be used to endorse or promote products derived from this software
 *      without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY CONTRIBUTORS ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
 * IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef __TBTREE_H__
#define __TBTREE_H__


#include <sys/types.h>
#include "tools.h" 

#define HASHSIZE(LEN)	( (LEN)<<1 )
/* end utils */


typedef struct {
	union {
		struct {
			u_int16_t offset;
			u_int16_t length;
		} leaf;
		struct {
			u_int32_t link;
		} internal;
	} pointer;
	union {
		struct {
			u_int16_t	offset;
			u_int16_t	length;
		} varlen;
		struct {
			char key[1];
		} fixed;
	} key;
} TBTPointer;

#define TBTPOINTERHRDSZ 	(offsetof(TBTPointer, key.fixed.key))
#define TBTPOINTERSIZE(db)	PTRALIGN( (db->keylen) ? TBTPOINTERHRDSZ + db->keylen : sizeof(TBTPointer) )
#define ISINFPOINTER(db, page, ptr)  ( (page)->isleaf==0 && (page)->rightlink == 0 && (char*)(ptr) == (page)->data + ((page)->npointer-1) * TBTPOINTERSIZE(db) ) 

/* can changed up to 65536 */
#define TBTREEPAGESIZE	8192
#define TBTPAGEHDRSZ	(2*sizeof(u_int32_t))

typedef struct {
	u_int32_t	rightlink;
	u_int32_t	
		freespace:16, /* correlate to TBTREEPAGESIZE */
		npointer:15,
		isleaf:1;
	char	data[TBTREEPAGESIZE-TBTPAGEHDRSZ];	
} TBTPage;

typedef struct TBTMemPage {
	u_int32_t	pagenumber;
	u_int32_t
		issynced:1,
		iscached:1,
		islocked:1,
		unused:29;
	struct TBTMemPage *prev;
	struct TBTMemPage *next;
	struct TBTMemPage *link;
	TBTPage	page;
} TBTMemPage;

#define TBTMEMPAGEHDRSZ (sizeof(u_int32_t)*2 + sizeof(TBTMemPage*)*3 + TBTPAGEHDRSZ)
typedef struct {
	u_int16_t 	length;
	char 		*value;
} TBTValue;

#define TBT_STATEGY_HALF 	0
#define TBT_STATEGY_LEFTFILL 	1
#define TBT_STATEGY_RIGHTFILL 	2

typedef struct {
	int	fd;	/* file descriptor */

	int	(*cmpkey)(const TBTValue *, const TBTValue *); 	

	u_int32_t
		readonly:1,
		keylen:11,
		strategy:2,
		unused:2,
		pointersize:16;

	/* cache page subsystem */
	u_int32_t	npage;
	u_int32_t	curpage;
	TBTMemPage	**Cache;
	TBTMemPage	*TimeCache;
	TBTMemPage	*TimeCacheLast;
	u_int32_t	lastpagenumber;

	/* stat subsystem */
	u_int32_t	cachehits;
	u_int32_t	pageread; /* include cachehits */
	u_int32_t	pagewrite;
} TBTree;

#define TBT_OK 		0
#define TBT_ERROR 	1
#define TBT_HUGE 	2

#define TBTPAGEROOT	0

int TBTOpen(TBTree *db, char *file) ;
int TBTClose(TBTree *db) ;
int TBTSync(TBTree *db) ;
int TBTFind(TBTree *db, TBTValue *key, TBTValue *value);
int TBTInsert(TBTree *db, TBTValue *key, TBTValue *value);
int TBTDelete(TBTree *db, TBTValue *key);

/* debug function, assume key is int4 or string and values are strings */
void dumpTree(TBTree *db, u_int32_t pagenumber, int follow);

typedef struct {
	TBTMemPage	*page;
	TBTPointer	*ptr;
} TBTIterator;

int TBTInitIterator(TBTree *db, TBTIterator *iterator );
int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value );
void TBTFreeIterator(TBTree *db, TBTIterator *iterator);


int TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value);
int TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value);

#endif