#include	<sys/types.h>

#include	<stdio.h>
#include	"btconf.h"
#include	"btree.h"
#include	"btintern.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.

	$Log:	btpage1.c,v $
 * Revision 1.1  90/06/08  16:11:49  mjr
 *  
 * 
 * Revision 1.1  90/06/06  15:03:49  mjr
 *  
 * 
 * Revision 1.1  90/06/03  16:23:13  mjr
 *  
 * 
 * Revision 1.1  90/05/18  23:20:39  mjr
 *  
 * 
 * Revision 1.1  90/05/15  13:18:34  mjr
 * Initial revision
 * 
 * Revision 1.1  90/05/05  15:04:37  mjr
 * Initial revision
 * 
 * Revision 1.1  90/03/23  15:03:57  mjr
 * Initial revision
 * 
*/


#ifndef	lint
static char *rcsid = "$Header: /atreus/mjr/hacks/mud/btlib/RCS/btpage1.c,v 1.1 90/06/08 16:11:49 mjr Exp $";
#endif

bt_srchpg(k,kl,dtyp,cmpf,ptr,num,s)
bt_chrp	k;
int	kl;
int	dtyp;
FUNCP	cmpf;
off_t	*ptr;
int	*num;
bt_chrp	s;
{
	int	lo = 0, m, hi;		/* low, mid, high ptrs for binsrch */
	int	*ip;			/* offset/beginning of key index */
	off_t	*cl;			/* offset/beginning of child index */
	bt_chrp	cp;			/* offset/beginning of keys */
	REGISTER int	cmpval;		/* returned value of comparison */
	REGISTER bt_chrp	kp1;	/* tmp key pointer */
	REGISTER bt_chrp	kp2;
	REGISTER int	l1;		/* key lengths */
	REGISTER int	l2;

	/* this value is decremented by one to keep from */
	/* looking past the top of the key list */
	hi = KEYCNT(s) - 1;

	/* save effort if this is an empty page */
	/* also saves from binary search where hi < lo! */
	if(KEYCNT(s) == 0) {
		*num = 0;
		*ptr = HIPT(s);
		return(BT_NF);
	}

	/* beginning of key index */
	ip = (int *)KEYIND(s);

	/* beginning of key string */
	cp = KEYADR(s);

	/* beginning of the child pointers */
	cl = (off_t *)KEYCLD(s);

	/* hold onto your cerebellums, folks !! */
	while(lo <= hi) {

		/* if the first key is the one we want, its length */
		/* is not calculated using the subtracted offsets, */
		/* but is rather calculated by using the offset */
		/* to the beginning of key #2, which starts where */
		/* the first key ends, by definition */

		/* actual comparison is done over len bytes from */
		/* the offset that is extracted out of the index */

		/* set up pointers for the compare */
		kp1 = k;
		l1 = kl;
		if((m = (lo + hi) >> 1) == 0) {
			kp2 = cp;
			l2 = *ip;
		} else {
			kp2 = cp + *(ip + m - 1);
			l2 = (*(ip + m) - *(ip + (m - 1)));
		}

		/* do the compare based on data type */
		if(dtyp == BT_STRING) {
				while(l1 != 0 && l2 != 0) {
					if(*kp1 != *kp2) {
						cmpval = *kp1 - *kp2;
						goto endcmp;
					}
					kp1++;
					kp2++;
					l1--;
					l2--;
				}

				if(l1 != l2)
					cmpval = l1 - l2;
				else
					cmpval = 0;
		} else if(dtyp == BT_INT) {
				cmpval = *(int *)kp1 - *(int *)kp2;
		} else if(dtyp == BT_LONG) {
				cmpval = *(long *)kp1 - *(long *)kp2;
		} else if(dtyp == BT_FLOAT) {
				cmpval = 0;
				 if(*(float *)kp1 > *(float *)kp2)
					cmpval = 1;
				else
					if(*(float *)kp1 < *(float *)kp2)
						cmpval = -1;
		} else if(dtyp == BT_USRDEF) {
			if(cmpf == 0)
				return(BT_ERR);
			cmpval = (*cmpf)(kp1,l1,kp2,l2);
		} else
			return(BT_ERR);
endcmp:
		if(cmpval < 0) {
			hi = m - 1;
			*num = m;
		} else {
			if(cmpval > 0) {
				lo = m + 1;
				*num = m + 1;
			} else {
				/* return current key # in num */
				*num = m;
				*ptr = *(cl + m);
				return(BT_OK);
			}
		}
	}

	if(*num == KEYCNT(s))
		*ptr = HIPT(s);
	else
		*ptr = *(cl + *num);
	return(BT_NF);
}


void
bt_inspg(key,len,ptr,at,in,out)
bt_chrp	key;
int	len;
off_t	*ptr;
int	at;
bt_chrp	in;
bt_chrp	out;
{
	REGISTER int	*iin;		/* index/length ptr to old page */
	REGISTER int	*iout;		/* index/length ptr to new page */
	REGISTER off_t	*lin;		/* child ptr to old page */
	REGISTER off_t	*lout;		/* child ptr to new page */
	REGISTER bt_chrp	kin;		/* key ptr to old page */
	REGISTER bt_chrp	kout;		/* key ptr to new page */
	REGISTER int	t;		/* iterator */
	int	iky;			/* key number in old page */
	int	oky;			/* key number in new page */
	int	copied = 0;		/* used as flag AND shift of lengths */

	/* fix key count in new page */
	KEYCNT(out) = KEYCNT(in) + 1;

	/* fix key length in new page */
	KEYLEN(out) = KEYLEN(in) + len;

	/* left and right sibs */
	LSIB(out) = LSIB(in);
	RSIB(out) = RSIB(in);

	/* and high pointer */
	HIPT(out) = HIPT(in);

	/* set the key start pointers, index and child pointers */
	kin = KEYADR(in);
	kout = KEYADR(out);

	iin = (int *)KEYIND(in);
	iout = (int *)KEYIND(out);

	lin = (off_t *)KEYCLD(in);
	lout = (off_t *)KEYCLD(out);

	for(oky = iky = 0; oky < KEYCNT(out); oky++) {

		/* insert the key at this point in the page */
		/* copied is used later to calculate lenght offsets */
		if(at == iky && copied == 0) {

			/* copy the key into the key space */
			for(t = 0; t < len; t++)
				*kout++ = *key++;

			/* fix up index lengths if key is first out */
			if(oky == 0)
				*iout = len;
			else
				*iout = *(iout - 1) + len;

			iout++;

			/* offset any more index lengths by this much */
			copied = len;

			/* copy ptrs */
			*lout++ = *ptr;

		} else {
			if(iky == 0)
				for(t = 0; t < *iin; t++)
					*kout++ = *kin++;
			else
				for(t = 0; t < (*iin - *(iin - 1)); t++)
					*kout++ = *kin++;
			iky++;
			*iout++ = *iin + copied;
			iin++;
			*lout++ = *lin++;
		}
	}
	lout--;
}