ndops.cpp

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

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

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

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

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

/*man---------------------------------------------------------------------------
NAME
     bt_ndalloc - allocate memory for node

SYNOPSIS
     #include "btree_.h"

     btnode_t *bt_ndalloc(btp)
     btree_t *btp;

DESCRIPTION
     The bt_ndalloc function allocates an initialized in-core node for
     btree btp.  The address of the node created is returned.

     bt_ndalloc 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.
     [BTENOPEN]     btp is not open.

SEE ALSO
     bt_ndfree, bt_ndinit.

DIAGNOSTICS
     On failure, a NULL pointer is returned, and errno set to indicate
     the error.

------------------------------------------------------------------------------*/
btnode_t *bt_ndalloc(btree_t *btp)
{
	btnode_t *btnp = NULL;
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp)) {
		BTEPRINT;
		errno = EINVAL;
		return NULL;
	}

	/* check if not open */
	if (!(btp->flags & BTOPEN)) {
		BTEPRINT;
		errno = BTENOPEN;
		return NULL;
	}
#endif
	/* allocate storage for main node structure */
	/* (calloc is used throughout to automatically set all bits 0) */
	btnp = (btnode_t *)calloc((size_t)1, sizeof(btnode_t));
	if (btnp == NULL) {
		BTEPRINT;
		errno = ENOMEM;
		return NULL;
	}
	btnp->lsib = NIL;
	btnp->rsib = NIL;
	btnp->n = 0;
	/* key array [1..m] (extra slot is for overflow) */
	btnp->keyv = calloc((size_t)btp->bthdr.m, btp->bthdr.keysize);
	if (btnp->keyv == NULL) {
		BTEPRINT;
		free(btnp);
		errno = ENOMEM;
		return NULL;
	}
	/* child node file postion array [0..m] */
	btnp->childv = (bpos_t *)calloc((size_t)(btp->bthdr.m + 1), sizeof(*btnp->childv));
	if (btnp->childv == NULL) {
		BTEPRINT;
		free(btnp->keyv);
		free(btnp);
		errno = ENOMEM;
		return NULL;
	}

	errno = 0;
	return btnp;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndcopy - copy btree node

SYNOPSIS
     #include "btree_.h"

     int bt_ndcopy(btp, tbtnp, sbtnp)
     btree_t *btp;
     btnode_t *tbtnp;
     const btnode_t *sbtnp;

DESCRIPTION
     The bt_ndcopy function makes an exact copy of the in-core node
     pointed to by sbtnp to the in-core node pointed to by tbtnp.

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

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       tbtnp or sbtnp is the NULL pointer.

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_ndcopy(btree_t *btp, btnode_t *tbtnp, const btnode_t *sbtnp)
{
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || tbtnp == NULL || sbtnp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}
#endif
	/* copy node sbtnp into tbtnp */
	tbtnp->lsib = sbtnp->lsib;
	tbtnp->rsib = sbtnp->rsib;
	tbtnp->n = sbtnp->n;
	memcpy(bt_kykeyp(btp, tbtnp, 1), bt_kykeyp(btp, sbtnp, 1), (size_t)(btp->bthdr.m * btp->bthdr.keysize));
	memcpy(bt_kychildp(tbtnp, 0), bt_kychildp(sbtnp, 0), (size_t)((btp->bthdr.m + 1) * sizeof(*bt_kychildp(tbtnp, 0))));

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_nddelkey - delete key from btree node

SYNOPSIS
     #include "btree_.h"

     int bt_nddelkey(btp, btnp, kn)
     btree_t *btp;
     btnode_t *btnp;
     int kn;

DESCRIPTION
     The bt_nddelkey function deletes the tuple kn from the in-core
     node pointed to by btnp.

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

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

SEE ALSO
     bt_ndinskey, bt_ndsearch.

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_nddelkey(btree_t *btp, btnode_t *btnp, int kn)
{
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || btnp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}
#endif
	/* delete key kn */
	if (bt_kyshift(btp, btnp, kn + 1, -1) == -1) {
		BTEPRINT;
		return -1;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndfree - free in-core node

SYNOPSIS
     #include "btree_.h"

     void bt_ndfree(btnp)
     btnode_t *btnp;

DESCRIPTION
     The bt_ndfree function frees the in-core node pointed to by btnp.

SEE ALSO
     bt_ndalloc.

------------------------------------------------------------------------------*/
void bt_ndfree(btnode_t *btnp)
{
	if (btnp == NULL) {
		return;
	}
	if (btnp->keyv != NULL) free(btnp->keyv);
	btnp->keyv = NULL;
	if (btnp->childv != NULL) free(btnp->childv);
	btnp->childv = NULL;
	free(btnp);

	return;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndfuse - btree node fuse

SYNOPSIS
     #include "btree_.h"

     int bt_ndfuse(btp, lbtnp, rbtnp, pbtnp, pkn)
     btree_t *btp;
     btnode_t *lbtnp;
     btnode_t *rbtnp;
     btnode_t *pbtnp;
     int pkn;

DESCRIPTION
     The bt_ndfuse function fuses two nodes.  lbtnp and rbtnp point to
     in-core copies of nodes to be fused, the left and right sibling,
     respectively.  pbtnp points to an in-core copy of the parent
     node.  pkn is the number of the key in pbtnp whose left child is
     lbtnp and right child is rbtnp.

     On return, lbtnp contains the fused node and rbtnp is empty.
     Both the left and right nodes are written to the file.  pbtnp is
     modified during the fusion, but is not written to the file; the
     calling program must write pbtnp to the file.

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

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       btnp, rbtnp, or pbtnp is NULL.
     [EINVAL]       pkn is less than 1 or greater than pbtnp->n.
     [BTENOPEN]     btp is not open.
     [BTEPANIC]     The total number of keys in lbtnp and rbtnp is
                    too large to fuse into one node.

SEE ALSO
     bt_ndshift, 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_ndfuse(btree_t *btp, btnode_t *lbtnp, btnode_t *rbtnp, btnode_t *pbtnp, int pkn)
{
	bttpl_t	bttpl;			/* (key, child address) tuple */
	bool	leaf	= FALSE;	/* leaf node flag */
	bpos_t	lnode	= 0;		/* left node block number */
	bpos_t	rnode	= 0;		/* right node block number */

	/* 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 == NUL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}
	if (pkn < 1 || pkn > pbtnp->n) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

	/* check if too many keys for fusion */
	if (lbtnp->n + rbtnp->n > bt_ndmax(btp) - (leaf ? 0 : 1)) {
		BTEPRINT;
		errno = BTEPANIC;
		return -1;
	}
#endif
	/* check if leaf */
	if (bt_ndleaf(lbtnp)) {
		leaf = TRUE;
	}

	/* get block number of sibling nodes */
	lnode = rbtnp->lsib;
	rnode = lbtnp->rsib;

	/* 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 (bt_ndinskey(btp, lbtnp, lbtnp->n + 1, &bttpl) == -1) {
			BTEPRINT;
			free(bttpl.keyp);
			return -1;
		}
		free(bttpl.keyp);
		bttpl.keyp = NULL;
	}

	/* move keys from rbtnp to lbtnp */
	if (bt_kymvleft(btp, lbtnp, rbtnp, rbtnp->n) == -1) {
		BTEPRINT;
		return -1;
	}

	/* return right node to free list */
	if (bflpush(btp->bp, &rnode) == -1) {
		BTEPRINT;
		return -1;
	}

	/* fix sibling links */		/*L=left N=new right */
	lbtnp->rsib = rbtnp->rsib;	/* L -> N */
	if (lbtnp->rsib == NIL) {	/* L <- N */
		if (leaf) btp->bthdr.last = lnode;
	} else {
		if (bputbf(btp->bp, lbtnp->rsib, offsetof(btnode_t, lsib), &lnode, sizeof(lbtnp->lsib)) == -1) {
			BTEPRINT;
			return -1;
		}
	}

	/* initialize in-core copy of right sibling */
	bt_ndinit(btp, rbtnp);

	/* delete parent key of right sibling */
	if (bt_nddelkey(btp, pbtnp, pkn) == -1) {
		BTEPRINT;
		return -1;
	}

	/* write fused node */
	if (bt_ndput(btp, lnode, lbtnp) == -1) {
		BTEPRINT;
		return -1;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndget - get btree node from file

SYNOPSIS
     #include "btree_.h"

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

DESCRIPTION
     The bt_ndget function reads the contents of a node into the
     in-core node pointed to by btnp to the file.  node is the block
     number of the node in the file.

     bt_ndget 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_ndput.

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_ndget(btree_t *btp, bpos_t node, 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
	/* read node from file */
	buf = calloc((size_t)1, bt_blksize(btp));
	if (buf == NULL) {
		BTEPRINT;
		errno = ENOMEM;
		return -1;
	}
	if (bgetb(btp->bp, node, buf) == -1) {
		BTEPRINT;
		free(buf);
		return -1;
	}

	/* convert file node to in-core format */
	memcpy(btnp, buf, offsetof(btnode_t, keyv));
	memcpy(btnp->keyv,
		((char *)buf + offsetof(btnode_t, keyv)),
		((btp->bthdr.m - 1) * btp->bthdr.keysize));
	memcpy(btnp->childv,
		((char *)buf + offsetof(btnode_t, keyv) +
			((btp->bthdr.m - 1) * btp->bthdr.keysize)),
		(btp->bthdr.m * sizeof(*btnp->childv)));

	/* free buffer */
	free(buf);

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndinit - initialize in-core node

SYNOPSIS
     #include "btree_.h"

     void bt_ndinit(btp, btnp)
     btree_t *btp;
     btnode_t *btnp;

DESCRIPTION
     The bt_ndinit function initializes the in-core node btnp.

------------------------------------------------------------------------------*/
void bt_ndinit(btree_t *btp, btnode_t *btnp)
{
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || btnp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return;
	}
#endif
	/* initialize btnp */
	btnp->lsib = NIL;
	btnp->rsib = NIL;
	btnp->n = 0;
	memset(btnp->keyv, 0, (size_t)(btp->bthdr.m * btp->bthdr.keysize));
	memset(btnp->childv, 0, (size_t)((btp->bthdr.m + 1) * sizeof(*btnp->childv)));

	return;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndinskey - insert key into btree node

SYNOPSIS
     #include "btree_.h"

     int bt_ndinskey(btp, btnp, kn, bttplp)
     btree_t *btp;
     btnode_t *btnp;
     int kn;
     const bttpl_t *bttplp;

DESCRIPTION
     The bt_ndinskey function inserts bttplp into the knth slot in
     the in-core btree node btnp.  The node is not written to the
     file.

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

     [EINVAL]       btp is not a valid btree pointer.
     [EINVAL]       btnp is the NULL pointer.
     [EINVAL]       kn is less than 1 or greater than the number of
                    keys in btnp plus 1.

SEE ALSO
     bt_nddelkey, bt_ndsearch.

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_ndinskey(btree_t *btp, btnode_t *btnp, int kn, const bttpl_t *bttplp)
{
#ifdef DEBUG
	/* validate arguments */
	if (!bt_valid(btp) || btnp == NULL || bttplp == NULL) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}
	if (kn < 1 || kn > btnp->n + 1) {
		BTEPRINT;
		errno = EINVAL;
		return -1;
	}

	/* check if room to insert */
	if (btnp->n >= btp->bthdr.m) {
		BTEPRINT;
		errno = BTEPANIC;
		return -1;
	}
#endif
	/* make an empty slot */
	if (bt_kyshift(btp, btnp, kn, 1) == -1) {
		BTEPRINT;
		return -1;
	}

	/* put new key into empty slot */
	if (bt_kywrite(btp, btnp, kn, bttplp) == -1) {
		BTEPRINT;
		return -1;
	}

	errno = 0;
	return 0;
}

/*man---------------------------------------------------------------------------
NAME
     bt_ndleaf - is btree node leaf

SYNOPSIS
     #include "btree_.h"

     int bt_ndleaf(btnp)
     btnode_t *btnp;