/*
   Time-stamp: <99/05/12 21:34:10 yusuf>

   $Id: mtree.c,v 1.19.4.2 1999/05/12 13:34:42 yusuf Exp $	

*/

#ifndef lint
static char vcid[] = "$Id: mtree.c,v 1.19.4.2 1999/05/12 13:34:42 yusuf Exp $";
#endif /* lint */



/* multi-way Tree 

	Implemented in C from a pseudoalgorithm in
	the book:

	Horowitz, E. & Sahni, S.	"Fundamentals of Data Structures"
		Computer Science Press (1983); pp 496ff.

	NOTE: When the algorithm calls for an expression [m/2], 
		  have interpreted the square brackets to mean that
		  the value is to be rounded UP, not down. Only then
		  does the algorithm work properly.


	This C implementation plus linked list addition
	was written by Yusuf Nagree.

*/



/* Implementation notes:

		This routine does NOT make use of recursion so that it
		can be easily translated into languages that do not
		support recursion (eg. BASIC). Therefore, a stack is maintained.
		The stack actually holds a full node to limit disk accesses. If
		memory is a problem, then modify the stack, mnsearch, ndeleteb and
		ninsertb so that only the disk block numbers are stored on
		the stack, and the actual nodes are read in when required.

		The symbol m is used to determine the order of the tree.

*/


/* index_f = which index_f to use : 0 = suread_info_key, 1 = ?  */

#include "taper.h"

PUBLIC node stackb[MAXSTACK][MAXSTACK_ITEMS];	 /* the stack of path down to node - nodes */
PUBLIC dskblk stackn[MAXSTACK][MAXSTACK_ITEMS];	 /*                                 node # */
PUBLIC int stackptr[MAXSTACK];

_errstat read_info_keynode(int index_f, _s32 rec, node *i_key)
{
/* Reads i_key in the index_f inf file

   Returns -1 if error, 0 otherwise
 */
    node i_key1;

    lseek(info_index[index_f+1], (long) ((rec+1)*sizeof(*i_key)), SEEK_SET);
    if (read(info_index[index_f+1], &i_key1, sizeof(*i_key)) == -1) return -1;
    ifk_node_endianize2mach(&i_key1, i_key);
    return 0;
}


_errstat write_info_keynode(int index_f, _s32 rec, node *i_key)
{
/* Reads i_key in the index_f inf file

   Returns -1 if error, 0 otherwise
 */

    node i_key1;
    
    lseek(info_index[index_f+1], (long) ((rec+1)*sizeof(*i_key)), SEEK_SET);
    ifk_node_endianize2little(i_key, &i_key1);
    if (write(info_index[index_f+1], &i_key1, sizeof(*i_key)) == -1) return -1;
    return 0;
}

PRIVATE void clrstack(int stackno)
{
    stackptr[stackno] = 0;
}


PRIVATE _errstat push(int stackno, dskblk n, node blk)
{
	if (stackptr[stackno] == MAXSTACK_ITEMS) return do_exit(ERROR_STACKOVER);
	stackn[stackno][stackptr[stackno]] = n;
	stackb[stackno][stackptr[stackno]] = blk;
	stackptr[stackno]++;
	return  0;
}


PRIVATE void pop(int stackno, dskblk *n, node *blk)
{
	if (stackptr[stackno] == 0)			/* If there is a stack underflow */
		*n = 0;					/* return 0 */
	else {
		stackptr[stackno]--;
		*n = stackn[stackno][stackptr[stackno]];
		*blk = stackb[stackno][stackptr[stackno]];
    }
}


PRIVATE dskblk makenode(int index_f)		 /* returns the block # of a new disk block */
{
    node blk;
    dskblk a;

    if (ifd.free[index_f] == 0)
        a = ++ifd.end[index_f];
    else {
         read_info_keynode(index_f, ifd.free[index_f], &blk);
         a = ifd.free[index_f];
         ifd.free[index_f] = blk.n;
    }
    return(a);
}


PRIVATE void freenode(dskblk rec, int index_f)			 /* frees a block */
{
		node blk;

        read_info_keynode(index_f, rec, &blk);
        blk.n = ifd.free[index_f];
        write_info_keynode(index_f, rec, &blk);
        ifd.free[index_f] = rec;
}

int compare(keytype *x1, keytype *x2, int index_f)
{
    /* Compares two info_file_datas and returns:
         0 = if equal,
	 -1 if x1 < x2
	 +1 if x1 > x2

	 if index_f == 0, sorting on name
	            1, sorting on mtime
    */
    int x;
    
    switch(index_f) {
    case INFO_NAME:
	x = strcmp(get_fn1(x1->fname_pos), get_fn2(x2->fname_pos));			 /* compare on name first */
	if (x) return x;			  
	if (x1->mtime < x2->mtime) return -1; /* then backup time */
	if (x1->mtime > x2->mtime) return 1;
	if (x1->volume < x2->volume) return -1; /* then volume */
	if (x1->volume > x2->volume) return 1;
	return 0;				 /* assume equal */
    }
    return 0;
}
    

PRIVATE int wherein(keytype *x, node blk, int index_f) /* Returns i such that Ki < x Ki+1 */
{						 /*  (ie. where in the node does x go */
	int	i;				/* counter */

	if (compare(x, &blk.keys[blk.n], index_f) >= 0)
		i = blk.n;
	else
		if (compare(x, &blk.keys[1], index_f) < 0)
			i = 0;
		else
			for (i=1; i < blk.n; i++)
				if ((compare(x, &blk.keys[i], index_f) >= 0) &&
					(compare(x, &blk.keys[i+1], index_f) <0))
					break;
	return(i);
}


PRIVATE int mnsearch(int stackno, keytype *x, dskblk *p, node *pblk, int *i, int index_f) 	/* returns 1 if x found, 0 if not*/
				/* What we are searching for */
	/* return codes */
			/* Which disk block where we found x
					         or, if not found, where x can go */
				/* The node p */
					/* The entry in p where x is */
{
	dskblk q=0;			/* parent of P */
	dskblk d;			/* dummies to use to pull p */
	node d1;			/*  off the stack */

	clrstack(stackno);
	*p = ifd.root[index_f];			/* line 1 of alg */
	while (*p != 0) {				/* line 2 */
		read_info_keynode(index_f, *p, pblk);			/* line 3 */
		if (pblk->n == 0)	{		/*   Check for completely empty tree */
			*i = 0;
			return(0);
		}
		*i = wherein(x, *pblk, index_f);		/* line 5, 6 */
		if (*i)
		    if (compare(x, &pblk->keys[*i], index_f) == 0)	/* line 7 */
			return(1);				/*   found the entry */
		push(stackno,*p, *pblk);			/*   add to stack */
 		q = *p;						/* line 8*/
		*p = pblk->a[*i];
	}
	*p = q;		   					/* line 10 */
	read_info_keynode(index_f, *p, pblk);
	pop(stackno, &d, &d1);					/*   remove 0 entry from stack */
	return(0);						/*   x not found */
}


PUBLIC int nsearch(int stackno, keytype *x, int index_f)				/* Searchs the tree for x.skey */
/* Returns 1 if found, 0 if not */
{
    node p1;		/* All these are not used, but are required in the */
	dskblk p;		/* call to msearch */
	int i;

	if (mnsearch(stackno, x, &p, &p1, &i, index_f)) {
        *x = p1.keys[i];			/* Get the whole of the found key */
		return(1);					/* including the index_f & chain value */
	}
	else
		return(0);
}


PUBLIC int insertb(int stackno, keytype *x, int index_f)				 /* Insert item x into t */
	 				 /* Item to be inserted */

/* Return codes = 0 - succesfully in - root block unchanged
				  2 - successfully in - root block changed
				  3 - new tree made
*/

{
	dskblk p;			/* block number */
	node blk;			/* node */
	dskblk p_;			/* second block number used when splitting */
	node blk_;			/* second node used when splitting */
	dskblk a;
	keytype k;			/* key */
	int  i;				/* position in node where key can be put */
	int	 c;				/* counter used for moving */
	dskblk t;			/* root block */

	a = 0;							/* line 1 */
	k = *x;
	t = ifd.root[index_f];
	if (t == 0)	{					/* New tree */
	    memset(&blk, 0, sizeof(blk));
		blk.n = 1;
		blk.a[0] = 0;
		blk.keys[1] = *x;
		blk.a[1] = 0;
		blk.a[2] = 0;
		t = makenode(index_f);
        ifd.root[index_f] = t;
		write_info_keynode(index_f, t, &blk);
		return(3);
	}
	mnsearch(stackno, x, &p, &blk, &i, index_f);
	while (p != 0) {				/* line 4 */
		i = wherein(&k, blk, index_f);	 /* line 5 : find where to insert it */
		for (c=blk.n+1;c>i;c--)		/*  now insert it */
			if (c < TREEORD) {
				blk.keys[c+1] = blk.keys[c];
				blk.a[c+1] = blk.a[c];
			}
		blk.keys[i+1] = k;
		blk.a[i+1] = a;
		blk.n++;
        if (blk.n < TREEORD) {				/* line 6 */
			write_info_keynode(index_f, p, &blk);
			return(0);

		}
		k = blk.keys[MB2];			/* part of line 9 */
		p_ = makenode(index_f);			/* line 7 */
		blk_.n = TREEORD - (MB2);
		blk.n = (MB2) - 1;
		blk_.a[0] = blk.a[MB2];
		for (c=MB2+1; c<=TREEORD; c++) {		/*   split the node */
			blk_.keys[c-(MB2)] = blk.keys[c];
			blk_.a[c-(MB2)] = blk.a[c];
		}
		blk.a[blk.n+1] = 0;
		blk_.a[blk_.n+1] = 0;
		write_info_keynode(index_f, p_, &blk_);				/* line 8 */
		write_info_keynode(index_f, p, &blk);
		a = p_;							/* rest of line 9 */
		pop(stackno,&p, &blk);
	}         							/* line 10 */
    blk.n = 1;                          /* line 11 */
	blk.a[0] = t;
	blk.keys[1] = k;
	blk.a[1] = a;
	blk.a[2] = 0;
	t = makenode(index_f);						/* line 12 */
	ifd.root[index_f] = t;
	write_info_keynode(index_f, t, &blk);
	return(2);
}


PUBLIC int ndeleteb(int stackno, keytype *x, int index_f)				/* Removes item from tree */
/* Return codes - 0 succesfully removed by shifting
				  1 item does not exist
				  2  item removed by merging
				  3  item removed by merging and root changed
                  4  item removed from chain
*/
{
	dskblk p;
	dskblk q;
	node pblk;
	node qblk;
	dskblk y,z;
	node yblk, zblk, tblk;
	int i, c, j;
	int tsp;				/* temp stack pointer */
	dskblk t=0;				/* Root */

    clrstack(stackno);
	t = ifd.root[index_f];
	if (mnsearch(stackno, x, &p, &pblk, &i, index_f) != 1)	/* line 1 */
		return(1);							/* line 2 */
	if (pblk.a[0] != 0)	{					/* line 4 */
		q = pblk.a[i];						/* line 5 */
		tsp = stackptr[stackno];						/*  Save stackptr so can change */
											/*   this entry later */
		push(stackno,p, pblk);						/*  Save this leaf */
		for (;;) {                          /* line 6 */
			read_info_keynode(index_f, q, &qblk);				/* line 7 */
			if (qblk.a[0] == 0) 			/* line 8 */
				break;
			push(stackno,q, qblk);
            q = qblk.a[0];					/* line 9 */
        }
		pblk.keys[i] = qblk.keys[i];		/* line 11 */
		write_info_keynode(index_f, p, &pblk);
		stackb[stackno][tsp] = pblk;					/*  Change value on stack */
		p = q;								/* line 12 */
		pblk = qblk;
		i = 1;
	}
	for (c=i; c<pblk.n; c++)	{				/* line 14 */
		pblk.keys[c] = pblk.keys[c+1];
		pblk.a[c] = pblk.a[c+1];
	}
	pblk.n--;
	while ((pblk.n < MB2 - 1) && (p != t)) {	/* line 15 */
		pop(stackno,&z, &zblk);      	                /* line 18 */
		for (c=0; c<=zblk.n; c++)	 			/* line 17 */
			if (zblk.a[c] == p)					/*  try and find nearest right */
				break;
		if ((zblk.a[c+1] != 0) &&
		   (c != zblk.n)) {				/* does have a right sibling */
		   	j = c + 1;					/* line 19 */
			y = zblk.a[j];
			read_info_keynode(index_f, y, &yblk);
			if (yblk.n >= MB2) {				/* line 20 */
				pblk.a[pblk.n+1] = yblk.a[0];	/* line 21 */
				pblk.keys[pblk.n+1] = zblk.keys[j];
				pblk.n++;
				zblk.keys[j] = yblk.keys[1];	/* line 22 */
				yblk.a[0] = yblk.a[1];				/* line 23 */
    	        for (c=1; c<yblk.n; c++) {
					yblk.a[c] = yblk.a[c+1];
					yblk.keys[c] = yblk.keys[c+1];
				}
				yblk.n--;
				write_info_keynode(index_f, p, &pblk);			/* line 24 */
				write_info_keynode(index_f, y, &yblk);
				write_info_keynode(index_f, z, &zblk);
				return(0);                      /* line 25 */
	        }
			pblk.a[pblk.n+1] = yblk.a[0];		/* line 27 */
			pblk.keys[pblk.n+1] = zblk.keys[j];
			for (c=1; c <= yblk.n; c++) {
				pblk.a[pblk.n+1+c] = yblk.a[c];
				pblk.keys[pblk.n+1+c] = yblk.keys[c];
			}
			pblk.n = 2*MB2-2;						/* line 26 */
			write_info_keynode(index_f, p, &pblk);
			p=z;									/* line 28, 29 */
			pblk = zblk;
			pblk.n--;
			for (c=j; c<=pblk.n; c++) {
				pblk.a[c] = pblk.a[c+1];
				pblk.keys[c] = pblk.keys[c+1];
			}
			freenode(y, index_f);
		}
		else {  					/* P must have a left sibling */
									/*  is symmetrical to the above */
		   	j = c;						/* line 19 */
			y = zblk.a[j-1];
			read_info_keynode(index_f, y, &yblk);
			if (yblk.n >= MB2) {				/* line 20 */
				pblk.a[pblk.n+1] = yblk.a[0];	/* line 21 */
				pblk.keys[pblk.n+1] = zblk.keys[j];
				pblk.n++;
				zblk.keys[j] = yblk.keys[1];	/* line 22 */
				yblk.a[0] = yblk.a[1];				/* line 23 */
    	        for (c=1; c<yblk.n; c++) {
					yblk.a[c] = yblk.a[c+1];
					yblk.keys[c] = yblk.keys[c+1];
				}
				yblk.n--;
				write_info_keynode(index_f, p, &pblk);			/* line 24 */
				write_info_keynode(index_f, y, &yblk);
				write_info_keynode(index_f, z, &zblk);
				return(0);                      /* line 25 */
	        }
			i=1;
			tblk.a[0] = yblk.a[0];
			for (c=yblk.n;c >=1; c--) {
				tblk.a[i] = yblk.a[c];
				tblk.keys[i] = yblk.keys[c];
				i++;
			}
			tblk.keys[i] = zblk.keys[j];
			tblk.a[i] = pblk.a[0];
			i++;
			for (c=1; c<=pblk.n; c++) {
				tblk.a[i] = pblk.a[c];
				tblk.keys[i] = pblk.keys[c];
				i++;
			}
			tblk.n = 2*MB2-2;						/* line 26 */
			write_info_keynode(index_f, p, &tblk);
			p=z;									/* line 28, 29 */
			pblk = zblk;
			pblk.n--;
			for (c=j-1; c<=pblk.n; c++)
				pblk.a[c] = pblk.a[c+1];
			freenode(y, index_f);
		}
    }
	if (pblk.n != 0) {
		write_info_keynode(index_f, p, &pblk);
		return(2);
	}
	else {
    	if (pblk.a[0] == 0)
        	freenode(t, index_f);			/* Free the old root */
		t = pblk.a[0];
		ifd.root[index_f] = t;
		return(3);
	}
}


PUBLIC int ntraverse(int stackno, keytype *start, keytype *end,
		 dskblk *rec, char command, int index_f)	/* Traverse the tree */
{							/* Returns 0 - OK                   */
    /* If end == NULL, then continues going until end */
	static int i[MAXSTACK];           /*         1 - finished             */
	static dskblk p[MAXSTACK];        /*         2 - error somewhere      */
	static node pblk[MAXSTACK];
	dskblk q=0, d;
	node d1;
	char goneup;
	keytype k;

	if (command != TRAVERSE_CONTINUE) {
	    clrstack(stackno);
	    k=*start;
	    p[stackno] = ifd.root[index_f];
	    if (p[stackno] == 0) {		 /* empty tree */
		*rec = 0;
		memset(start, 0, sizeof(*start));
		return 1;
	    }
	    while (p[stackno]) {
		read_info_keynode(index_f, p[stackno], &(pblk[stackno]));
		if (!pblk[stackno].n) {
		    *rec = 0;
		    memset(start, 0, sizeof(*start));
		    return 1;
		}
		if (command == TRAVERSE_TOP) i[stackno] = 0;
		if (command == TRAVERSE_BOTTOM) i[stackno] = pblk[stackno].n;
		if (command == TRAVERSE_SEARCH) {
		    i[stackno] = wherein(&k, pblk[stackno], index_f);
		    if (i[stackno])		 /* if i=0, can't equal */
			switch (index_f) {
			case INFO_NAME:
			    if (!strcmp(get_fn1(start->fname_pos), get_fn2(pblk[stackno].keys[i[stackno]].fname_pos))) {
				*rec = pblk[stackno].keys[i[stackno]].recnum;
				*start = pblk[stackno].keys[i[stackno]];
				return 0;
			    }
			    break;
			}
		}
		push(stackno,p[stackno], pblk[stackno]);
		q = p[stackno];
		p[stackno] = pblk[stackno].a[i[stackno]];
	    }
	    p[stackno] = q;
	    read_info_keynode(index_f, p[stackno], &(pblk[stackno]));
	    pop(stackno,&d, &d1);
	}
	
	/* Get next */
	while (1) {
		if (pblk[stackno].a[i[stackno]]) {		/* There are children */
			push(stackno,p[stackno], pblk[stackno]);
			p[stackno] = pblk[stackno].a[i[stackno]];
			while (p[stackno]) {
				read_info_keynode(index_f, p[stackno], &(pblk[stackno]));
				push(stackno,p[stackno], pblk[stackno]);
				q = p[stackno];
				p[stackno] = pblk[stackno].a[0];
			}
			p[stackno] = q;
			read_info_keynode(index_f, p[stackno], &(pblk[stackno]));
			pop(stackno,&d, &d1);
			i[stackno] = 0;
		}

		i[stackno]++;
		goneup=FALSE;
		while (i[stackno] > pblk[stackno].n) {
			q = p[stackno];
			pop(stackno,&p[stackno], &(pblk[stackno]));
			if (!p[stackno])
				return(1);			/* End of tree */
			for (i[stackno]=0;;i[stackno]++)
				if (pblk[stackno].a[i[stackno]] == q)
					break;
			i[stackno]++;
			goneup = TRUE;
		}
		if ((goneup) || (!pblk[stackno].a[i[stackno]])) {
			*rec = pblk[stackno].keys[i[stackno]].recnum;
			*start = pblk[stackno].keys[i[stackno]];
			if (end == NULL) return 0; /* keep on going */
			if (compare(&(pblk[stackno].keys[i[stackno]]), end, index_f) <= 0)
				return(0);
			else
				return(1);
		}
	}
}