btops.cpp

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

/*	Copyright (c) 1989 Citadel	*/
/*	   All Rights Reserved    	*/

/* #ident	"@(#)btops.c	1.4 - 90/06/20" */

#include <blkio.h>
#include <bool.h>
#include <errno.h>
/*#include <stddef.h*/
/*#include <stdlib.h>*/
/*#include <string.h>*/

/* local headers */
#include "btree_.h"

/*man---------------------------------------------------------------------------
NAME
     bt_alloc - allocate memory for btree

SYNOPSIS
     #include "btree_.h"

     int bt_alloc(btp);
     btree_t *btp;

DESCRIPTION
     The bt_alloc function allocates the memory needed by btp.  The
     memory is is initialized to all zeros.

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

     [EINVAL]       btp is not a valid btree pointer.
     [ENOMEM]       Not enough memory is available for allocation by
                    the calling process.

SEE ALSO
     bt_free.

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_alloc(btree_t *btp)
{
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp)) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

	/* check for memory leak */
	if (btp->fldv != NULL || btp->sp != NULL || btp->cbtnp != NULL) {
		BTEPRINT;
		errno = BTEPANIC;
		return -1;
	}
#endif
	/* field definition array */
	btp->fldv = (btfield_t *)calloc((size_t)btp->fldc, sizeof(*btp->fldv));
	if (btp->fldv == NULL) {
		BTEPRINT;
		errno = ENOMEM;
		return -1;
	}

	/* search path (one extra element for when root splits) */
	btp->sp = (btpos_t *)calloc((size_t)(btp->bthdr.height + 1), sizeof(*btp->sp));
	if (btp->sp == NULL) {
		BTEPRINT;
		free(btp->fldv);
		errno = ENOMEM;
		return -1;
	}

	/* current node */
	btp->cbtnp = bt_ndalloc(btp);
	if (btp->cbtnp == NULL) {
		BTEPRINT;
		free(btp->fldv);
		free(btp->sp);
		return -1;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_blksize - btree block size

SYNOPSIS
     #include <btree.h>

     size_t bt_blksize(btp)
     btree_t *btp;

DESCRIPTION
     bt_blksize returns the size of the blocks in btree file btp.  If
     btp is not a valid open btree, the results are undefined.
     bt_blksize is a macro.

------------------------------------------------------------------------------*/
/* bt_blksize defined in btree_.h. */

/*man---------------------------------------------------------------------------
NAME
     bt_delete - delete btree key

SYNOPSIS
     #include <btree.h>

     int bt_delete(btp)
     btree_t *btp;

DESCRIPTION
     The bt_delete function deletes the current key from btree btp.
     The search path must be generated prior to calling bt_delete.
     The cursor is positioned to null.

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

     [EINVAL]       btp is not a valid btree pointer.
     [BTELOCK]      btree btp is not write locked.
     [BTENKEY]      The cursor is null.
     [BTENOPEN]     btree btp is not open.

SEE ALSO
     btdelete, btinsert, btsearch.

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_delete(btree_t *btp)
{
	btnode_t *	btnp	= NULL;		/* node receiving new key */
	bool		err	= FALSE;	/* error flag */
	btnode_t *	lbtnp	= NULL;		/* left sibling node */
	bpos_t		lsib	= NIL;		/* lsib location */
	/*bpos_t	node	= NIL;		/* node location */
	btnode_t *	pbtnp	= NULL;		/* parent node */
	int		pkn	= 0;		/* parent key number */
	bpos_t		pnode	= 0;		/* parent node location */
	btnode_t *	rbtnp	= NULL;		/* right sibling node */
	bpos_t		rsib	= NIL;		/* rsib location */
	unsigned long	spi	= 0;		/* search path index */
	int		terrno	= 0;		/* tmp errno */
	int		total	= 0;		/* total keys in node and sib */
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp)) {
		errno = EINVAL;
		return -1;
	}

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

	/* check lock */
	if (!(btp->flags & BTWRLCK)) {
		errno = BTELOCK;
		return -1;
	}

	/* check if cursor is null */
	if (btcursor(btp) == NULL) {
		errno = BTENKEY;
		return -1;
	}
#endif
	/* initialize working nodes */
	btnp = bt_ndalloc(btp);
	if (btnp == NULL) {
		BTEPRINT;
		return -1;
	}
	lbtnp = bt_ndalloc(btp);	/* left sibling */
	if (lbtnp == NULL) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		errno = terrno;
		return -1;
	}
	rbtnp = bt_ndalloc(btp);	/* right sibling */
	if (rbtnp == NULL) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		errno = terrno;
		return -1;
	}
	pbtnp = bt_ndalloc(btp);	/* parent */
	if (pbtnp == NULL) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		bt_ndfree(rbtnp);
		errno = terrno;
		return -1;
	}

	/* initialize btnp with current node */
	if (bt_ndcopy(btp, btnp, btp->cbtnp) == -1) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		bt_ndfree(rbtnp);
		bt_ndfree(pbtnp);
		errno = terrno;
		return -1;
	}

	/* delete key from node */
	if (bt_nddelkey(btp, btnp, btp->cbtpos.key) == -1) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		bt_ndfree(rbtnp);
		bt_ndfree(pbtnp);
		errno = terrno;
		return -1;
	}

	/* set modify bit in in-core header and write to file */
	btp->bthdr.flags |= BTHMOD;
	if (bputhf(btp->bp, sizeof(bpos_t),
				(char *)&btp->bthdr + sizeof(bpos_t),
				sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		bt_ndfree(rbtnp);
		bt_ndfree(pbtnp);
		errno = terrno;
		return -1;
	}
	if (bsync(btp->bp) == -1) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		bt_ndfree(rbtnp);
		bt_ndfree(pbtnp);
		errno = terrno;
		return -1;
	}

	/* loop from leaf node to root */
	for (spi = 0; spi < btp->bthdr.height; ++spi) {
		/* write to disk if node not too small */
/*??*/		if (btnp->n >= bt_ndmin(btp) || spi == btp->bthdr.height - 1 && btnp->n != 0) {
			if (bt_ndput(btp, btp->sp[spi].node, btnp) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			break;
		}
		if (spi == btp->bthdr.height - 1) {		/* empty root */
			if (bt_shrink(btp, bt_kychildp(btnp, 0)) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			break;
		}

		/* node needs more keys */
		/* try to shift keys with siblings */
		/* read in parent node */
		if (bt_ndget(btp, btp->sp[spi + 1].node, pbtnp) == -1) {
			BTEPRINT;
			err = TRUE;
			break;
		}
		/* get locations of nodes */
		/*node = btp->sp[spi].node;*/
		pnode = btp->sp[spi + 1].node;
		pkn = btp->sp[spi + 1].key - 1;
		if (pkn == 0) {
			lsib = NIL;
		} else {
			lsib = btnp->lsib;
		}
		if (pkn == pbtnp->n) {
			rsib = NIL;
		} else {
			rsib = btnp->rsib;
		}

		/* try shifting keys with right sibling */
		if (rsib != NIL) {
			if (bt_ndget(btp, rsib, rbtnp) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			total = btnp->n + rbtnp->n;
			if (total >= 2 * bt_ndmin(btp)) {
				if (bt_ndshift(btp, btnp, rbtnp, pbtnp, pkn + 1, pnode) == -1) {
					BTEPRINT;
					err = TRUE;
					break;
				}
				break;
			}
		}

		/* try shifting keys with left sibling */
		if (lsib != NIL) {
			if (bt_ndget(btp, lsib, lbtnp) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			total = lbtnp->n + btnp->n;
			if (total >= 2 * bt_ndmin(btp)) {
				btp->sp[spi].key = lbtnp->n + btp->sp[spi].key;
				if (bt_ndshift(btp, lbtnp, btnp, pbtnp, pkn, pnode) == -1) {
					BTEPRINT;
					err = TRUE;
					break;
				}
				break;
			}
		}

		/* try fusing with right sibling */
		if (rsib != NIL) {
			if (bt_ndfuse(btp, btnp, rbtnp, pbtnp, pkn + 1) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			if (bt_ndcopy(btp, btnp, pbtnp) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			continue;
		}

		/* try fusing with left sibling */
		if (lsib != NIL) {
			if (bt_ndfuse(btp, lbtnp, btnp, pbtnp, pkn) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			if (bt_ndcopy(btp, btnp, pbtnp) == -1) {
				BTEPRINT;
				err = TRUE;
				break;
			}
			continue;
		}

		BTEPRINT;
		errno = BEPANIC;
		err = TRUE;
		break;
	}
	if (err) {
		BTEPRINT;
		terrno = errno;
		bt_ndfree(btnp);
		bt_ndfree(lbtnp);
		bt_ndfree(rbtnp);
		bt_ndfree(pbtnp);
		errno = terrno;
		return -1;
	}

	bt_ndfree(btnp);
	bt_ndfree(lbtnp);
	bt_ndfree(rbtnp);
	bt_ndfree(pbtnp);

	/* decrement key count in header */
	btp->bthdr.keycnt--;

	/* clear modify bit in in-core header and write to file */
	btp->bthdr.flags &= ~BTHMOD;
	if (bputhf(btp->bp, sizeof(bpos_t),
				(char *)&btp->bthdr + sizeof(bpos_t),
				sizeof(bthdr_t) - sizeof(bpos_t)) == -1) {
		BTEPRINT;
		return -1;
	}
	if (bsync(btp->bp) == -1) {
		BTEPRINT;
		return -1;
	}

	/* set cursor to null */
	btp->cbtpos.node = NIL;
	btp->cbtpos.key = 0;
	bt_ndinit(btp, btp->cbtnp);

	errno = 0;
	return 0;
}