btops.cpp

CBASE v1.01 采用Borland公司TC++编写的数据库管理源程序库

/*man---------------------------------------------------------------------------
NAME
     bt_free - free memory allocated for btree

SYNOPSIS
     #include "btree_.h"

     void bt_free(btp)
     btree_t *btp;

DESCRIPTION
     The bt_free function frees all memory allocated for btree btp.
     If btp is not a valid btree, no action is taken.

SEE ALSO
     bt_alloc.

------------------------------------------------------------------------------*/
void bt_free(btree_t *btp)
{
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp)) {
		BTEPRINT;
		return;
	}
#endif
	/* free memory */
	if (btp->fldv != NULL) free(btp->fldv);
	btp->fldv = NULL;
	if (btp->sp != NULL) free(btp->sp);
	btp->sp = NULL;
	bt_ndfree(btp->cbtnp);
	btp->cbtnp = NULL;

	return;
}

/*man---------------------------------------------------------------------------
NAME
     bt_fvalid - validate field definition list

SYNOPSIS
     #include "btree_.h"

     bool bt_fvalid(keysize, fldc, fldv)
     size_t keysize;
     int fldc;
     const btfield_t fldv[];

DESCRIPTION
     The bt_fvalid function determines if keysize, fldc, and fldv
     constitute a valid btree field definition list.  If valid, then
     TRUE is returned.  If not, then FALSE is returned.

------------------------------------------------------------------------------*/
bool bt_fvalid(size_t keysize, int fldc, const btfield_t fldv[])
{
	size_t end = 0;
	int i = 0;

	if (keysize < 1 || fldc < 1 || fldv == NULL) {
		return FALSE;
	}

	for (i = 0; i < fldc; ++i) {
		if (fldv[i].offset < end) {
			return FALSE;
		}
		if (fldv[i].len < 1) {
			return FALSE;
		}
		end = fldv[i].offset + fldv[i].len;
		if (end > keysize) {
			return FALSE;
		}
		if (fldv[i].cmp == NULL) {
			return FALSE;
		}
		if (fldv[i].flags & ~(BT_FFLAGS)) {
			return FALSE;
		}
	}

	return TRUE;
}

/*man---------------------------------------------------------------------------
NAME
     bt_grow - btree grow

SYNOPSIS
     #include "btree_.h"

     int bt_grow(btp, bttplp)
     btree_t *btp;
     const bttpl_t *bttplp;

DESCRIPTION
     The bt_grow function creates a new root for btree btp and inserts
     the (key, child) tuple pointed to by bttplp into the new root
     node.  This increases the tree height by one; it is the only way
     by which the height can increase.  If the tree was previously
     empty, the first and last key links in the in-core header are set
     to the new root.

     bt_grow will fail if one or more of the following is true:

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       bttplp is the NULL pointer.
     [BTENOPEN]     btp is not open.

SEE ALSO
     bt_shrink.

DIAGNOSTICS
     Upon successful completion, a value of 0 is returned.  Otherwise,
     a value of -1 is returned, and errno set to indicate the error.

------------------------------------------------------------------------------*/
int bt_grow(btree_t *btp, const bttpl_t *bttplp)
{
	btnode_t *	btnp	= NULL;
	bpos_t		oldroot	= NIL;
	bpos_t		newroot	= NIL;
	btpos_t	*	sp	= NULL;
	int		terrno	= 0;
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || bttplp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

	/* check if not open */
	if (!(btp->flags & BTOPEN)) {
		BTEPRINT;
		errno = BTENOPEN;
		return -1;
	}
#endif
	/* get node from free list */
	if (bflpop(btp->bp, &newroot) == -1) {
		BTEPRINT;
		return -1;
	}

	/* set root link in in-core header */
	oldroot = btp->bthdr.root;
	btp->bthdr.root = newroot;

	/* add element to search path */
	btp->sp[btp->bthdr.height].node = newroot;
	btp->sp[btp->bthdr.height].key = 1;
	++btp->bthdr.height;
	sp = (btpos_t *)realloc(btp->sp, (size_t)(btp->bthdr.height + 1) * sizeof(*sp));
	if (sp == NULL) {
		BTEPRINT;
		btp->bthdr.root = oldroot;
		--btp->bthdr.height;
		errno = ENOMEM;
		return -1;
	}
	btp->sp = sp;
	sp = NULL;
	btp->sp[btp->bthdr.height].node = NIL;
	btp->sp[btp->bthdr.height].key = 0;

	/* write new root to file */
	btnp = bt_ndalloc(btp);
	if (btnp == NULL) {
		BTEPRINT;
		terrno = errno;
		btp->bthdr.root = oldroot;
		--btp->bthdr.height;
		bflpush(btp->bp, &newroot);
		errno = terrno;
		return -1;
	}
	*bt_kychildp(btnp, 0) = oldroot;	/* link to old root */
	if (bt_ndinskey(btp, btnp, 1, bttplp) == -1) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		btp->bthdr.root = oldroot;
		--btp->bthdr.height;
		bflpush(btp->bp, &newroot);
		errno = terrno;
		return -1;
	}
	if (bt_ndput(btp, newroot, btnp) == -1) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		btp->bthdr.root = oldroot;
		--btp->bthdr.height;
		bflpush(btp->bp, &newroot);
		errno = terrno;
		return -1;
	}
	bt_ndfree(btnp);

	/* update first and last key links */
	if (oldroot == NIL) {
		btp->bthdr.first = btp->bthdr.last = newroot;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_search - search a btree

SYNOPSIS
     #include <btree.h>

     int bt_search(btp, buf)
     btree_t *btp;
     const void *buf;

DESCRIPTION
     The bt_search function searches the btree btp for the key pointed
     to by buf.  If it is found, the cursor is set to the location of
     the key and 1 is returned.  If it is not found, the cursor is set
     to the location at which it should be inserted and 0 is returned.
     Note that in the latter case the cursor may be positioned to an
     empty location.

     bt_search will fail if one or more of the following is true:

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       buf is the NULL pointer.

DIAGNOSTICS
     Upon successful completion, a value of 1 is returned if the key
     was found or a value of 0 if it was not found.  On failure, a
     value of -1 is returned, and errno set to indicate the error.

------------------------------------------------------------------------------*/
int bt_search(btree_t *btp, const void *buf)
{
	int		found	= 0;		/* found flag */
	bpos_t		node	= NIL;		/* node position */
	unsigned long	spi	= 0;		/* search path index */
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || buf == NULL) {
		errno = EINVAL;
		return -1;
	}
#endif
	/* initialize btree structure for search */
	btp->cbtpos.node = NIL;			/* init cursor */
	btp->cbtpos.key = 0;
	btp->sp[btp->bthdr.height].node = NIL;	/* init search path head */
	btp->sp[btp->bthdr.height].key = 0;

	/* loop from root to leaf node */
	/* Note: spi is unsigned, so spi >= 0 will not terminate loop */
	spi = btp->bthdr.height;
	for (node = btp->bthdr.root; node != NIL;
			node = *bt_kychildp(btp->cbtnp, btp->sp[spi].key - 1)) {
		btp->sp[--spi].node = node;
		if (bt_ndget(btp, node, btp->cbtnp) == -1) {
			BTEPRINT;
			return -1;
		}
		found = bt_ndsearch(btp, btp->cbtnp, buf, &btp->sp[spi].key);
		if (found == -1) {
			BTEPRINT;
			return -1;
		}
		if (found == 1) {
			btp->sp[spi].key++;	/* move forward one */
		}
		if (spi == 0) {			/* leaf node */
			break;
		}
	}
	if (spi != 0) {
		BTEPRINT;	/* height value probably incorrect */
		errno = BTEPANIC;
		return -1;
	}

	/* set cursor */
	btp->cbtpos.node = btp->sp[0].node;
	btp->cbtpos.key = btp->sp[0].key - ((found == 1) ? 1 : 0);

	errno = 0;
	return ((found == 1) ? 1: 0);
}

/*man---------------------------------------------------------------------------
NAME
     bt_shrink - btree shrink

SYNOPSIS
     #include "btree_.h"

     int bt_shrink(btp, newrootp)
     btree_t *btp;
     const bpos_t *newrootp;

DESCRIPTION
     The bt_shrink function makes *newrootp the new root for btree btp
     and returns the old root back to the free list.  This decreases
     the tree height by one; it is the only way in which the height
     can decrease.  If the old root node was also a leaf node, the
     first and last key links in the in-core header are set to NIL.

     bt_shrink will fail if one or more of the following is true:

     [EINVAL]       btp is not a valid btree pointer.
     [BTEPANIC]     btp is already empty.

SEE ALSO
     bt_grow.

DIAGNOSTICS
     Upon successful completion, a value of 0 is returned.  Otherwise,
     a value of -1 is returned, and errno set to indicate the error.

------------------------------------------------------------------------------*/
int bt_shrink(btree_t *btp, const bpos_t *newrootp)
{
	bpos_t		newroot	= NIL;
	bpos_t		oldroot	= NIL;
	btpos_t *	sp	= NULL;
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || newrootp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

	/* check if not open */
	if (!(btp->flags & BTOPEN)) {
		BTEPRINT;
		errno = BTENOPEN;
		return -1;
	}

	/* check if tree already empty */
	if (btp->bthdr.root == NIL) {
		BTEPRINT;
		errno = BTEPANIC;
		return -1;
	}
#endif
	/* set root link in in-core header */
	oldroot = btp->bthdr.root;
	btp->bthdr.root = newroot = *newrootp;

	/* remove element from search path */
	--btp->bthdr.height;
	sp = (btpos_t *)realloc(btp->sp, (size_t)(btp->bthdr.height + 1) * sizeof(*sp));
	if (sp == NULL) {
		BTEPRINT;
		btp->bthdr.root = oldroot;
		++btp->bthdr.height;
		errno = ENOMEM;
		return -1;
	}
	btp->sp = sp;
	sp = NULL;
	btp->sp[btp->bthdr.height].node = NIL;
	btp->sp[btp->bthdr.height].key = 0;

	/* push root back onto free list stack */
	if (bflpush(btp->bp, &oldroot) == -1) {
		BTEPRINT;
		btp->bthdr.root = oldroot;
		++btp->bthdr.height;
		return -1;
	}

	/* update first and last key links */
	if (newroot == NIL) {
		btp->bthdr.first = btp->bthdr.last = NIL;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_valid - validate btree pointer

SYNOPSIS
     #include "btree_.h"

     bool bt_valid(btp)
     btree_t *btp;

DESCRIPTION
     The bt_valid function determines if btp is a valid btree pointer.
     If valid, then TRUE is returned.  If not, then FALSE is returned.

------------------------------------------------------------------------------*/
bool bt_valid(btree_t *btp)
{
	if (btp < btb || btp > (btb + BTOPEN_MAX - 1)) {
		return FALSE;
	}
	if ((((char *)btp - (char *)btb)) % sizeof(*btb) != 0) {
		return FALSE;
	}

	return TRUE;
}