ndops.cpp

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

DESCRIPTION
     bt_ndleaf returns a true value if btnp is a leaf node or a false
     value if it is not.  If btnp does not point to a valid in-core
     btree node, the results are undefined.  bt_ndleaf is a macro.

SEE ALSO
     bt_ndmax, bt_ndmin.

------------------------------------------------------------------------------*/
/* bt_ndleaf is defined in btree_.h. */

/*man---------------------------------------------------------------------------
NAME
     bt_ndmax - maximum keys per node

SYNOPSIS
     #include "btree_.h"

     int bt_ndmax(btp)
     btree_t *btp;

DESCRIPTION
     bt_ndmin returns the maximum number of keys allowable in a node
     of btree btp.  If btp does not point to a valid open btree, the
     results are undefined.  bt_ndmax is a macro.

SEE ALSO
     bt_ndleaf, bt_ndmin.

------------------------------------------------------------------------------*/
/* bt_ndmax is defined in btree_.h. */

/*man---------------------------------------------------------------------------
NAME
     bt_ndmin - minimum keys per node

SYNOPSIS
     #include "btree_.h"

     int bt_ndmin(btp)
     btree_t *btp;

DESCRIPTION
     bt_ndmin returns the minimum number of keys allowable in a node
     of btree btp.  If btp does not point to a valid open btree, the
     results are undefined.  bt_ndmin is a macro.

SEE ALSO
     bt_ndleaf, bt_ndmax.

------------------------------------------------------------------------------*/
/* bt_ndmin is defined in btree_.h. */

/*man---------------------------------------------------------------------------
NAME
     bt_ndput - put btree node to file

SYNOPSIS
     #include "btree_.h"

     int bt_ndput(btp, node, btnp)
     btree_t *btp;
     bpos_t node;
     const btnode_t *btnp;

DESCRIPTION
     The bt_ndput function writes the contents of the in-core node
     pointed to by btnp to the file.  node is the block number of the
     node in the file.

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

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       btnp is NULL.
     [EINVAL]       node is NIL.
     [EINVAL]       btnp is NULL.
     [BTENOPEN]     btp is not open.

SEE ALSO
     bt_ndget.

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_ndput(btree_t *btp, bpos_t node, const btnode_t *btnp)
{
	void *buf = NULL;
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || node == NIL || btnp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

	/* check if not open */
	if (!(btp->flags & BTOPEN)) {
		BTEPRINT;
		errno = BTENOPEN;
		return -1;
	}
#endif
	/* convert in-core node to file format */
	buf = calloc((size_t)1, bt_blksize(btp));
	if (buf == NULL) {
		BTEPRINT;
		errno = ENOMEM;
		return -1;
	}
	memcpy(buf, btnp, offsetof(btnode_t, keyv));
	memcpy(((char *)buf + offsetof(btnode_t, keyv)),
		btnp->keyv,
		((btp->bthdr.m - 1) * btp->bthdr.keysize));
	memcpy(((char *)buf + offsetof(btnode_t, keyv) +
			((btp->bthdr.m - 1) * btp->bthdr.keysize)),
		btnp->childv,
		(btp->bthdr.m * sizeof(*btnp->childv)));

	/* write node to file */
	if (bputb(btp->bp, node, buf) == -1) {
		BTEPRINT;
		free(buf);
		return -1;
	}

	/* free buffer */
	free(buf);

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndsearch - search btree node

SYNOPSIS
     #include "btree_.h"

     int bt_ndsearch(btp, btnp, buf, knp)
     btree_t *btp;
     const btnode_t *btnp;
     const void *buf;
     int *knp;

DESCRIPTION
     Function searches the in-core node btnp for the key pointed to by
     buf.  On return, the location of the smallest key >= that pointed
     to by buf is in the location pointed to by knp.

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

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

SEE ALSO
     bt_nddelkey, bt_ndinskey.

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

------------------------------------------------------------------------------*/
int bt_ndsearch(btree_t *btp, const btnode_t *btnp, const void *buf, int *knp)
{
	int	cmp	= 0;		/* result of key comparison */
	int	fld	= 0;		/* field number */
	bool	found	= FALSE;	/* key found flag */
	int	kn	= 0;		/* key number */
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || btnp == NULL || buf == NULL || knp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}
#endif
	/* initialize */
	*knp = 0;

	/* locate key */
	for (kn = 1; kn <= btnp->n; ++kn) {
		for (fld = 0; fld < btp->fldc; ++fld) {
			cmp = (*btp->fldv[fld].cmp)(bt_kykfp(btp, btnp, kn, fld),
					(char *)buf + btp->fldv[fld].offset,
					btp->fldv[fld].len);
			if (cmp != 0) {
				break;
			}
		}
		if (cmp == 0) {
			found = TRUE;
			break;
		}
		if (btp->fldv[fld].flags & BT_FDSC) {
			if (cmp < 0) break;	/* descending order */
		} else {
			if (cmp > 0) break;	/* ascending order */
		}
	}
	*knp = kn;

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

/*man---------------------------------------------------------------------------
NAME
     bt_ndshift - node shift

SYNOPSIS
     #include "btree_.h"

     int bt_ndshift(btp, lbtnp, rbtnp, pbtnp, pkn, pnode)
     btree_t *btp;
     btnode_t *lbtnp;
     btnode_t *rbtnp;
     btnode_t *pbtnp;
     int pkn;
     bpos_t pnode;

DESCRIPTION
     The bt_ndshift function shifts keys between two sibling nodes to
     give them both the same number of keys (+/- 1).  lbtnp and rbtnp
     are in-core copies of the two siblings.  pbtnp is an in-core copy
     of the parent node of the two siblings.  pkn is the number of the
     key in pbtnp whose left child is lbtnp and right child is rbtnp.

     The left, right, and parent nodes are written to the file.

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

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       lbtnp, rbtnp, or pbtnp is NULL.
     [EINVAL]       pkn is less than 1 or greater than pbtnp->n.
     [BTENOPEN]     btp is not open.
     [BTEPANIC]     Not enough keys in lbtnp and rbtnp to achieve
                    the minimum number in both nodes.

SEE ALSO
     bt_ndfuse, bt_ndsplit.

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_ndshift(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp, btnode_t *pbtnp, int pkn, bpos_t pnode)
{
	bttpl_t	bttpl;			/* (key, child address) tuple */
	bool	leaf	= FALSE;	/* leaf node flag */
	bool	right	= FALSE;	/* shift direction flag */
	int	ns	= 0;		/* number keys to shift */

	/* initialize automatic aggregates */
	memset(&bttpl, 0, sizeof(bttpl));
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp)) {
		BTEPRINT;
		errno = EINVAL;
		return NULL;
	}
	if (lbtnp == NULL || rbtnp == NULL || pbtnp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}
	if (pkn < 1 || pkn > pbtnp->n) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

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

	/* check if enough keys to shift */
if (lbtnp->n + rbtnp->n < 2 * bt_ndmin(btp)) {
		errno = BTEPANIC;
		return -1;
	}

	/* check if too many keys to shift */
	if (lbtnp->n + rbtnp->n > 2 * bt_ndmax(btp)) {
		errno = BTEPANIC;
		return -1;
	}
#endif
/*printf("IN NDSHIFT: pkn = %d, pnode = %lu.\n", pkn, pnode);*/
	/* set leaf and direction flags */
	if (bt_ndleaf(lbtnp)) {
		leaf = TRUE;
	}
	if (lbtnp->n > rbtnp->n) {
		right = TRUE;
	} else {
		right = FALSE;
	}

	/* if internal node, bring down parent key pkn */
	if (!leaf) {
		bttpl.keyp = calloc((size_t)1, btp->bthdr.keysize);
		if (bttpl.keyp == NULL) {
			BTEPRINT;
			errno = ENOMEM;
			return -1;
		}
		if (bt_kyread(btp, pbtnp, pkn, &bttpl) == -1) {
			BTEPRINT;
			free(bttpl.keyp);
			return -1;
		}
		bttpl.child = *bt_kychildp(rbtnp, 0);
		if (right) {
			if (bt_ndinskey(btp, rbtnp, 1, &bttpl) == -1) {
				BTEPRINT;
				free(bttpl.keyp);
				return -1;
			}
			*bt_kychildp(rbtnp, 0) = *bt_kychildp(lbtnp, lbtnp->n);
		} else {
			if (bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttpl) == -1) {
				BTEPRINT;
				free(bttpl.keyp);
				return -1;
			}
			*bt_kychildp(lbtnp, lbtnp->n) = *bt_kychildp(rbtnp, 0);
		}
		free(bttpl.keyp);
		bttpl.keyp = NULL;
	}

	/* calculate number of keys to shift (+ -> shift to right) */
	ns = (lbtnp->n - rbtnp->n) / 2;
	if (ns < 0) ns = -ns;

/*printf("NODES BEFORE SHIFT:\n");
puts("Left:");
bt_dgnode(btp, lbtnp, stdout);
puts("Right:");
bt_dgnode(btp, rbtnp, stdout);*/
	/* shift keys */
	if (right) {
		if (bt_kymvright(btp, lbtnp, rbtnp, ns) == -1) {
			BTEPRINT;
			return -1;
		}
	} else {
		if (bt_kymvleft(btp, lbtnp, rbtnp, ns) == -1) {
			BTEPRINT;
			return -1;
		}
	}
/*printf("NODES AFTER SHIFT BUT BEFORE EXTRACT PARENT KEY:\n");
puts("Left:");
bt_dgnode(btp, lbtnp, stdout);
puts("Right:");
bt_dgnode(btp, rbtnp, stdout);*/

	/* bring up new parent key (child of pkn remains right node) */
	if (!leaf) {
		if (lbtnp->n > rbtnp->n) {
			memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, lbtnp, lbtnp->n), btp->bthdr.keysize);
			if (bt_nddelkey(btp, lbtnp, lbtnp->n) == -1) {
				BTEPRINT;
				return -1;
			}
		} else {
			memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, rbtnp, 1), btp->bthdr.keysize);
			*bt_kychildp(rbtnp, 0) = *bt_kychildp(rbtnp, 1);
			if (bt_nddelkey(btp, rbtnp, 1) == -1) {
				BTEPRINT;
				return -1;
			}
		}
	} else {
		memcpy(bt_kykeyp(btp, pbtnp, pkn), bt_kykeyp(btp, rbtnp, 1), btp->bthdr.keysize);
	}
/*printf("NODES AFTER EXTRACT PARENT KEY:\n");
puts("Left:");
bt_dgnode(btp, lbtnp, stdout);
puts("Right:");
bt_dgnode(btp, rbtnp, stdout);*/

	/* write lbtnp, rbtnp, and pbtnp to file */
	if (bt_ndput(btp, *bt_kychildp(pbtnp, pkn - 1), lbtnp) == -1) {
		BTEPRINT;
		return -1;
	}
	if (bt_ndput(btp, *bt_kychildp(pbtnp, pkn), rbtnp) == -1) {
		BTEPRINT;
		return -1;
	}
	if (bt_ndput(btp, pnode, pbtnp) == -1) {
		BTEPRINT;
		return -1;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndsplit - btree node split

SYNOPSIS
     #include "btree_.h"

     int bt_ndsplit(btp, node, btnp, rbtnp, bttplp)
     btree_t *btp;
     bpos_t node;
     btnode_t *btnp;
     btnode_t *rbtnp;
     bttpl_t *bttplp;

DESCRIPTION
     The bt_ndsplit function splits a btree node.  btnp points to an
     in-core copy of the node to be split.  node is the block number
     of this node in the file.  The splitting will produce a new right
     sibling for this node.  Both the modified and the new node are
     written to the file.  If btnp had a right sibling prior to the
     split, the lsib link field in that node is updated, also.

     On return, btnp and rbtnp contain copies of the split node and
     its new right sibling, respectively, and the tuple pointed to by
     bttplp contains the (key, child address) tuple to be inserted in
     the parent of the split node; bttplp->child contains the block
     number of the new right sibling node.

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

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       btnp, rbtnp, or bttplp is NULL.
     [BTENOPEN]     btp is not open.
     [BTEPANIC]     The number of keys in btnp is not equal to m.

SEE ALSO
     bt_ndfuse, bt_ndshift.

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_ndsplit(btree_t *btp, bpos_t node, btnode_t *btnp, btnode_t *rbtnp, bttpl_t *bttplp)
{
	bool	leaf	= FALSE;	/* leaf node flag */
	int	midkn	= 0;		/* middle key number */
	bpos_t	rnode	= 0;		/* right node block number */
	int	terrno	= 0;		/* tmp errno */
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp)) {
		BTEPRINT;
		errno = EINVAL;
		return NULL;
	}
	if (btnp == NULL || rbtnp == NULL || bttplp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

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

	/* check if node not one over full */
	if (btnp->n != bt_ndmax(btp) + 1) {
		BTEPRINT;
		errno = BTEPANIC;
		return -1;
	}
#endif
	/* initialize */
	bt_ndinit(btp, rbtnp);

	/* check if leaf node */
	if (bt_ndleaf(btnp)) {
		leaf = TRUE;
	}

	/* get new block for right sibling node */
	if (bflpop(btp->bp, &rnode) == -1) {
		BTEPRINT;
		return -1;
	}

	/* fix sibling links */		/*L=left R=right O=old right */
	rbtnp->rsib = btnp->rsib;	/* L    R -> O */
	btnp->rsib = rnode;		/* L -> R    O */
	rbtnp->lsib = node;		/* L <- R    O */
	if (rbtnp->rsib == NIL) {	/* L    R <- O */
		if (leaf) btp->bthdr.last = rnode;
	} else {
		if (bputbf(btp->bp, rbtnp->rsib, offsetof(btnode_t, lsib),
					&rnode, sizeof(rbtnp->lsib)) == -1) {
			BTEPRINT;
			terrno = errno;
			bflpush(btp->bp, &rnode);
			errno = terrno;
			return -1;
		}
	}

	/* calculate middle key number */
	midkn = btnp->n / 2 + 1;

	/* get middle (key, child) tuple into bttplp */
	if (bt_kyread(btp, btnp, midkn, bttplp) == -1) {
		BTEPRINT;
		terrno = errno;
		bflpush(btp->bp, &rnode);
		errno = terrno;
		return -1;
	}
	bttplp->child = rnode;

	/* shift keys from left sibling */
	if (leaf) {
		/* move midkn thru n to right sibling */
		if (bt_kymvright(btp, btnp, rbtnp, btnp->n - midkn + 1) == -1) {
			BTEPRINT;
			return -1;
		}
	} else {
		/* move midkn + 1 thru n to right sibling */
		if (bt_kymvright(btp, btnp, rbtnp, btnp->n - midkn) == -1) {
			BTEPRINT;
			return -1;
		}
		/* delete midkn */
		if (bt_nddelkey(btp, btnp, midkn) == -1) {
			BTEPRINT;
			return -1;
		}
	}

	/* write split nodes */
	if (bt_ndput(btp, node, btnp) == -1) {
		BTEPRINT;
		return -1;
	}
	if (bt_ndput(btp, rnode, rbtnp) == -1) {
		BTEPRINT;
		return -1;
	}

	errno = 0;
	return 0;
}