#include	<btree.h>
#include	<ingres.h>
#include	<opsys.h>
#include	<sccs.h>

SCCSID(@(#)btree_util.c	8.2	1/31/86)

/*	Trace up to the root of the BTree, incrementing (or decrementing) all
**	key values.
**
**	Parameters :
**		tree - BTree filename (I)
**		block - starting node from which path is traced (I)
**		inc - either +1 or -1 (I)
*/

tracepath(rootpage, block, inc)

long rootpage;
register struct locator *block;
register int inc;
{
	struct locator 	p, child;

	if (block->pageno != rootpage)	/* if at root, no need for adjustment */
	{
		bmove(block, &child, sizeof(struct locator));

		/* trace up to root node */
		do
		{
			p.pageno = child.page.parent;
			parentkey(child.pageno, &p);
			p.page.node.intnode.key[p.offset] += inc;
			write_node(p.pageno, &p.page);
			bmove(&p, &child, sizeof(struct locator));
		} while (p.pageno != rootpage);
	}
}

/*	Determines which key/ptr pair is the parent of the given page
**
**	Parameters :
**		tree - BTree filename (I)
**		block - page number of child (I)
**		prt - information about the parent of the child (I, O)
**
*/

parentkey(block, prt)

long block;
register struct locator *prt;
{
	register int	i;

	get_node(prt->pageno, &prt->page);
	/* find pointer in parent which references desired block */
	for (i = 0; prt->page.node.intnode.ptr[i] != block && i < prt->page.nelmts; ++i)
		continue;

	if (i == prt->page.nelmts)
		syserr("parentkey: child = %ld", block);
	prt->offset = i;
	return(0);
}

/*	Retrieve a node from the BTree
**
**	Parameters :
**		tree - BTree filename (I)
**		pagenum - page number of page to be retrieved (I)
**		buffer - buffer into which page is retrieved (O)
*/

get_node(pagenum, buffer)

long pagenum;
register struct BTreeNode *buffer;
{
	extern int	Btree_fd;

	if ( lseek(Btree_fd, pagenum * PGSIZE, 0) == -1 )
		syserr("GET_NODE: seek to %ld failed",pagenum);
	if (read(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
		syserr("GET_NODE: read btree, page %ld", pagenum);
}

/*	Write a node into the BTree file name 
**
**	Parameters :
**		tree - BTree filename (I)
**		pagenum - page number of page to be written (I)
**		buffer - buffer containing page to be written (I)
*/

write_node(pagenum, buffer)

long pagenum;
register struct BTreeNode *buffer;
{
	extern int	Btree_fd;

	lseek(Btree_fd, pagenum * PGSIZE, 0);
	if (write(Btree_fd, buffer, sizeof *buffer) != sizeof *buffer)
		syserr("WRITE_NODE: write btree, page %ld", pagenum);
}

/*	Retrieves a new page from the BTree file.  If there is an empty page
**	in the file, that page is used.  Otherwise, a new page is added to
**	the end of the file.
**
**	Parameters :
**		tree - BTree filename (I)
**
**	Returns :
**		page number of new page
*/

long
new_page(tree)

char *tree;
{
	int 			i;
	long			freepage, newpage;
	struct BTreeNode 	page, root, garbage;
	struct stat		fileinfo;
	extern DESC		Btreesec;

	get_node(RT, &root);
	freepage = root.parent;
	if (freepage == 0)
	/* no free pages in file, add a new page to the end */
	{
		/* determine page number of page at very end of file */
		stat(tree, &fileinfo);
		newpage = fileinfo.st_size / PGSIZE;
		write_node(newpage, &page);
	}
	else
	/* use first free page, adjusting free page chain */
	{
		newpage = freepage;
		get_node(newpage, &garbage);
		root.parent = garbage.parent;
		write_node(RT, &root);
	}
	return(newpage);
}

/*	Returns an empty file to the empty file list.  The head of the list
**	is indicated through the parent of the root and linked together
**	through the parents of the empty pages.
**
**	Parameters :
**		tree - BTree filename (I)
**		pagenum - page number of empty page (I)
*/

return_page(pagenum)

long pagenum;
{
	struct BTreeNode	root, freepage;	

	/* indicate that page is free by inserting its page number at the
	** head of the free page list */
	get_node(RT, &root);
	get_node(pagenum, &freepage);
	freepage.parent = root.parent;
	freepage.depth = 0;
	write_node(pagenum, &freepage);
	root.parent = pagenum;
	write_node(RT, &root);
}

/*
**	Determine the lid that corresponds to a given position in the B-Tree.
**
**	Parameters :
**		tree - BTree name (I)
**		tidloc - location in BTree (I)
**
**	Returns :
**		lid value
*/
get_lid(tidloc, lid)

TID *tidloc;
long lid[];
{
	static struct locator	tid;
	register int		i, j;
	long			l, child;

	do
	{
		/* determine where in BTree to search */
		pluck_page(tidloc, &tid.pageno);
	
		get_node(tid.pageno, (char *) &tid.page);
		tid.offset = tid.page.node.leafnode.back_ptr[tidloc->line_id & I1MASK];

		if (tid.offset > tid.page.nelmts - 1)
			syserr("get_lid: bad tid location %ld, tid.offset=%d, tid.page.nelmts=%d", *tidloc, tid.offset,tid.page.nelmts);
	
		/* scan through leaf */
		for (l = 1, i = tid.offset; i > 0; ++l, --i)
			continue;
		/* trace up to root, adding keys */
		while (!tid.page.depth)
		{
			child = tid.pageno;
			tid.pageno = tid.page.parent;
			parentkey(child, &tid);
			for (i = tid.offset - 1; i >= 0; l += tid.page.node.intnode.key[i--])
				continue;
		}
		lid[tid.page.depth - 1] = l;
#		ifdef xATR1
			if (tTf(24,0))
				printf("lid=%ld\n", lid[tid.page.depth - 1]);
#		endif
		bmove(&tid.page.prttree, tidloc, LIDSIZE);
	} while (tid.page.depth > 1);
}

/*
**	Uses the secondary btree relation to find the btree tid corresponding 
**	to a given main relation tid
*/

search_btree(mtid, tidloc)

TID mtid; 
register TID *tidloc;
{
	char		key[2 * LIDSIZE], tup[2 * LIDSIZE];
	TID		tid;
	extern DESC	Btreesec;

#	ifdef xATR1
		if (tTf(24,0))
		{
			printf("In Search_btree: searching for tid %ld\n", mtid);
			printdesc(&Btreesec);
		}
#	endif
	clearkeys(&Btreesec);
	setkey(&Btreesec, key, &mtid, 1);
	if (!getequal(&Btreesec, key, tup, &tid))
		bmove(tup + LIDSIZE, tidloc, LIDSIZE);
	else
		syserr("search_btree:can't find mtid %ld in btree", mtid);
#	ifdef xATR1
		if (tTf(24,0))
			printup(&Btreesec, tup);
#	endif
}

/*
**	Linearly searches the leaves of the BTree for a desired tid
**
**	Parameters :
**		tree - BTree file name (I)
**		tid - desired tid value (I)
**		tidloc - location of the desired tid (O)
*/

lin_search(level, tid, tidloc, lid, tupcnt)

int level;
long tid;
TID *tidloc;
long lid[];
long tupcnt;
{
	struct locator	block;
	register int	i;
	long		page, t, next;
	int		found;
	long		nextpage, count;
	int		forward, first;

	page = RT;
	for (i = 0; i < level - 1; ++i)
	{
		t = get_tid(page, lid[i], &block);
		page = t;
	}

	found = 0;
	forward  = 0;
	first = 1;
	do
	{
		if (!forward)
		{
			get_node(page, &block.page);
			next = block.page.nexttree;
		}
		count = 0;

		/* start at leftmost leaf */
		do
		{
			get_node(page, &block.page);
			if (forward)
				nextpage = block.page.nexttree;
			else
				nextpage = block.page.prevtree;
			get_tid(page, 1, &block);
			for ( ; ; )
			{
				/* search through leaf */
				for (i = 0; i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] != tid; ++i)
				{
					if (!first)
						++count;
				}
				if (i < block.page.nelmts && block.page.node.leafnode.tid_pos[block.page.node.leafnode.tid_loc[i]] == tid)
				{
					found = 1;
					break;	/* tid found */
				}
				first = 0;
				if (!(block.pageno = block.page.node.leafnode.nextleaf) || count >= tupcnt)
					break;	/* all leaves exhausted */
				else
					/* try leaf to the right */
					get_node(block.pageno, &block.page);
			}
			if (found || count >= tupcnt)
				break;
		} while (page = nextpage);
		nextpage = next;
		forward = !forward;
	} while (forward != 0 && !found);
	if (!found)
		syserr("search_btree: tid not found %ld", tid);
	else
	{
		stuff_page(tidloc, &block.pageno);
		tidloc->line_id = block.page.node.leafnode.tid_loc[i];
	}
}

/*
**	Determines the value corresponding to the very last lid in the
**	BTree.
**
**	Parameters :
**		tree - BTree file name (I)
**
**	Returns :
**		value of last lid
*/
long
last_lid(rootpage)

long rootpage;

{
	register int 		i;
	long			lid;
	struct BTreeNode	root;

	lid = 0;
	get_node(rootpage, &root);
	if (root.nodetype == 'L')
		lid = root.nelmts;
	else
		for (i = 0; i < root.nelmts; ++i)
			lid += root.node.intnode.key[i];
	++lid;
	return(lid);
}

/*
**	Changes the tid value stored in the leaf of a BTree node
**
**	Parameters :
**		tree - BTree file name (I)
**		tid - new tid value (I)
**		tidloc - location of tid to be replaced (I)
*/

replace_btree(tid, tidloc)

long tid;
register TID *tidloc;

{
	long			pageno;
	struct BTreeNode	p;

	pluck_page(tidloc, &pageno);
	get_node(pageno, &p);
	p.node.leafnode.tid_pos[tidloc->line_id] = tid;
	write_node(pageno, &p);
}