#ifndef	_DEF_BT_INTERN_H

/*
         (C) Copyright, 1988, 1989 Marcus J. Ranum
                    All rights reserved


          This software, its documentation,  and  supporting
          files  are  copyrighted  material  and may only be
          distributed in accordance with the terms listed in
          the COPYRIGHT document.
*/


/*
	$Header: /atreus/mjr/hacks/mud/btlib/RCS/btintern.h,v 1.1 90/06/08 16:11:53 mjr Exp $
	THIS SHOULD NOT BE INCLUDED BY USER-LEVEL PROGRAMS
*/

#define	BT_NULL	((off_t)-1L)
#define	BT_FREE	((off_t)-2L)

/* make life easier with function pointers */
typedef	int	(*FUNCP)();

/* cache flags - not needed by user code */
#define	BT_CHE_CLEAN	0
#define	BT_CHE_DIRTY	1
#define	BT_CHE_LOCKD	2

/* forward decls for internal funcs only */
extern	struct bt_cache *bt_rpage();
extern	off_t		bt_newpage();
extern	void		bt_inspg();
extern	void		bt_splpg();

#ifndef	NO_BT_DEBUG
extern	void		bt_dump();
#endif

/*
minumum allowable page cache. since page sizes are variable,
the cache is also used to provide buffers for insertion and
deletion, or splitting. if there are not enough, nothing works
this value was determined from intimate knowledge of the code
*/
#define	BT_MINCACHE	4


/*
 Macros used in manipulating btree pages.

 this stuff is the machine specific part - if these macros are
 not right, you are guaranteed to know about it right away when
 this code is run. If you know exact values, you can plug them
 in directly, otherwise, we guess. getting it wrong will waste
 some space, is all. note that the off_ts are clustered at the
 beginning of the page, so that there is less likely to be a
 problem with the ints following. this may cause trouble in some
 odd architectures, and if so, fix it, and let me know.

 debugging a page is hard to do, by its very nature, and it is
 equally hard to build consistency checks into the code to
 validate pages as they are read and written. there is some
 code in bt_rpage() and bt_wpage() that looks for glaringly hosed
 pages, but if something gets past them, serious problems are
 sure to follow.

	Don't even *THINK* about running this past "lint -h" !!!!!

	These macros wind up nesting ~5 layers deep and get pretty
	hairy. If your c-preprocessor is not gutsy enough, have fun
	with the cut and paste !

	Makeup of a page:
	a page is an unstructured mess stuffed into a character buffer
	with all locations being determined via pointer arithmetic.
	this structure is loosely based on Zoellic and Folk's text
	"File Structures: a conceptual toolkit". further, there is
	no distinction between internal pages and leaf pages except
	that the value in the high pointer will be BT_NULL

	fields are (in order)
	- how many -- data type (size) ---------value/description-----
	1	|	off_t	|	page left sibling
	1	|	off_t	|	page right sibling
	1	|	off_t	|	page "high" (overflow) ptr
	1	|	int	|	count of keys in page - keycnt
	1	|	int	|	total length of keys in page
	keycnt	|	int	|	length index (one per key)
	keycnt	|	off_t	|	child/data ptrs (one per key)

	Ideally, pages should be flagged depending on type, and if
	the page contains fixed-size objects (structs, or ints, etc)
	the length index should be left out, saving sizeof(int) 
	bytes/key, which would be susbstantial improvement. This is
	an enhancement considered for release 2.0 if ever, or is
	left as an exercise for the reader.

	--mjr();
*/

/* alignment boundary for off_ts */
#define	ALIGN	sizeof(off_t)
/*
#define	ALIGN	(sizeof(off_t)/sizeof(char))
*/

/*
the actual alignments - the bit with the u_long may break on
some systems. Whatever, it needs to be a size that can give a valid
modulo operator on an address (Suns don't like modulo of pointers)
*/
#define	DOALIGN(s)	(s + (ALIGN - ((u_long)s % ALIGN)))

/* page siblings */
#define	LSIB(p)		(*(off_t *)(p))
#define	RSIB(p)		(*(off_t *)(p + sizeof(off_t)))
#define	HIPT(p)		(*(off_t *)(p + (2 * sizeof(off_t))))

/* count of keys in page, stored in first integer value */
#define	KEYCNT(p)	(*(int *)(p + (3 * sizeof(off_t))))

/* length of keys in page, stored in second integer value */
#define	KEYLEN(p)	(*(int *)(p + sizeof(int) + (3 * sizeof(off_t))))

/* address of key string (pointer to char) */
#define	KEYADR(p)	(p + (2 * sizeof(int)) + (3 * sizeof(off_t)))

/* address of first (int) key index value */
#define	KEYIND(p)	DOALIGN((KEYADR(p) + KEYLEN(p)))

/* address of first (off_t) child pointer value */
#define	KEYCLD(p)	(KEYIND(p) + (KEYCNT(p) * sizeof(int)))

/* # of bytes used by page pointers, sibs, etc */
#define PTRUSE		((2 * sizeof(int)) + (4 * sizeof(off_t)))

/* # of bytes used out of a page */
#define KEYUSE(p)	((KEYCNT(p) * (sizeof(off_t) + sizeof(int))) + PTRUSE + KEYLEN(p))

#define	_DEF_BT_INTERN_H
#endif