home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Frostbyte's 1980s DOS Shareware Collection
/
floppyshareware.zip
/
floppyshareware
/
DOOG
/
CBASE09.ZIP
/
BTREE.ZIP
/
KYOPS.C
< prev
next >
Wrap
Text File
|
1989-08-31
|
14KB
|
493 lines
/* Copyright (c) 1989 Citadel */
/* All Rights Reserved */
/* #ident "kyops.c 1.1 - 89/07/03" */
#include <blkio.h>
#include <errno.h>
#include "btree_.h"
/*man---------------------------------------------------------------------------
NAME
bt_kychild_p - btree node child
SYNOPSIS
#include "btree_.h"
bpos_t *bt_kychild_p(btnp, kn)
btnode_t *btnp;
size_t kn;
DESCRIPTION
bt_kychild_p returns a pointer to the knth child in node btnp. If btnp
is not a valid btree node or if kn < 0 or kn > btnp->n the results
are undefined. bt_kychild_p is a macro.
SEE ALSO
bt_kykey_p.
------------------------------------------------------------------------------*/
/* bt_kychild_p is #defined in btree.h. */
/*man---------------------------------------------------------------------------
NAME
bt_kykey_p - btree node key
SYNOPSIS
#include "btree_.h"
void *bt_kykey_p(btnp, kn)
btnode_t *btnp;
size_t kn;
DESCRIPTION
bt_kykey_p returns a pointer to the knth key in node btnp. If btnp
is not a valid btree node or if kn < 0 or kn > btnp->n the results
are undefined. bt_kychild_p is a macro.
SEE ALSO
bt_kychild_p.
------------------------------------------------------------------------------*/
/* bt_kykey_p is #defined in btree.h. */
/*man---------------------------------------------------------------------------
NAME
bt_kymvleft - move keys left
SYNOPSIS
#include "btree_.h"
int bt_kymvleft(btp, lbtnp, rbtnp, nm)
btree_t *btp;
btnode_t *lbtnp;
btnode_t *rbtnp;
size_t nm;
DESCRIPTION
Function moves the leftmost nm tuples and child 0 (keys 1..nm and children
0..nm) from node rbtnp to lbtnp. They are appended after the last key in
lbtnp, its rightmost child being overwritten. The key count in each node
is corrected for the shift. No other changes are made.
bt_kymvleft will fail if one or more of the following is true:
[EINVAL] btp, lbtnp, or rbtnp is NULL.
[EINVAL] lbtnp and rbtnp are same node.
[EINVAL] rbtnp does not have nm keys.
[EINVAL] lbtnp does not have room for nm keys.
SEE ALSO
bt_kymvright, bt_kyshift.
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_kymvleft(btp, lbtnp, rbtnp, nm)
btree_t *btp; /* --> */
btnode_t *lbtnp; /* <-> */
btnode_t *rbtnp; /* <-> */
size_t nm; /* --> */
{
int rs = 0;
size_t ks = 0; /* first key to copy */
size_t ke = 0; /* last key to copy */
size_t kt = 0; /* target key */
void * ps = NULL; /* pointer to copy source */
void * pe = NULL; /* pointer to copy source end */
void * pt = NULL; /* pointer to copy target */
errno = 0;
#ifdef DEBUG
/* validate arguments */
if ((btp == NULL) || (lbtnp == NULL) || (rbtnp == NULL) || (lbtnp == rbtnp)) {
BTEPRINT;
errno = EINVAL;
return -1;
}
if ((nm > rbtnp->n) || ((nm + lbtnp->n) > bt_ndmax(btp))) {
BTEPRINT;
errno = EINVAL;
return -1;
}
#endif
/* move bttuples */
ks = 1;
ke = nm;
kt = lbtnp->n + 1;
ps = bt_kykey_p(btp, rbtnp, ks);
pe = bt_kykey_p(btp, rbtnp, ke + 1);
pt = bt_kykey_p(btp, lbtnp, kt);
memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
ps = (void *)bt_kychild_p(rbtnp, ks - 1);
pe = (void *)bt_kychild_p(rbtnp, ke + 1);
pt = (void *)bt_kychild_p(lbtnp, kt - 1);
memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
/* adjust key count of left node */
lbtnp->n += nm;
/* delete keys from rbtnp */
ks = nm + 1;
ke = rbtnp->n;
kt = 1;
ps = bt_kykey_p(btp, rbtnp, ks);
pe = bt_kykey_p(btp, rbtnp, ke + 1);
pt = bt_kykey_p(btp, rbtnp, kt);
memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
ps = (void *)bt_kychild_p(rbtnp, ks - 1);
pe = (void *)bt_kychild_p(rbtnp, ke + 1);
pt = (void *)bt_kychild_p(rbtnp, kt - 1);
memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
/* adjust key count of right node */
rbtnp->n -= nm;
errno = 0;
return 0;
}
/*man---------------------------------------------------------------------------
NAME
bt_kymvright - move keys right
SYNOPSIS
#include "btree_.h"
int bt_kymvright(btp, lbtnp, rbtnp, nm)
btree_t *btp;
btnode_t *lbtnp;
btnode_t *rbtnp;
size_t nm;
DESCRIPTION
Function moves the rightmost nm bttuples and the child preceding them
(keys (n + 1 - nm)..n and children (n - nm)..n) from node lbtnp to
rbtnp. They are inserted before the first key in rbtnp, its leftmost
child being overwritten. The key count in each node is corrected for
the shift. No other changes are made.
bt_kymvright will fail if one or more of the following is true:
[EINVAL] btp, lbtnp, or rbtnp is NULL.
[EINVAL] lbtnp and rbtnp are same node.
[EINVAL] rbtnp does not have nm keys.
[EINVAL] lbtnp does not have room for nm keys.
SEE ALSO
bt_kymvleft, bt_kyshift.
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_kymvright(btp, lbtnp, rbtnp, nm)
btree_t *btp; /* --> */
btnode_t *lbtnp; /* <-> */
btnode_t *rbtnp; /* <-> */
size_t nm; /* --> */
{
int rs = 0;
size_t ks = 0; /* first key to copy */
size_t ke = 0; /* last key to copy */
size_t kt = 0; /* target key */
void * ps = NULL; /* pointer to copy source */
void * pe = NULL; /* pointer to copy source end */
void * pt = NULL; /* pointer to copy target */
errno = 0;
#ifdef DEBUG
/* validate arguments */
if ((btp == NULL) || (lbtnp == NULL) || (rbtnp == NULL) || (lbtnp == rbtnp)) {
BTEPRINT;
errno = EINVAL;
return -1;
}
if ((nm > lbtnp->n) || ((nm + rbtnp->n) > bt_ndmax(btp))) {
BTEPRINT;
errno = EINVAL;
return -1;
}
#endif
/* make room in right node */
ks = 1;
ke = rbtnp->n;
kt = nm + 1;
ps = bt_kykey_p(btp, rbtnp, ks);
pe = bt_kykey_p(btp, rbtnp, ke + 1);
pt = bt_kykey_p(btp, rbtnp, kt);
memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
ps = (void *)bt_kychild_p(rbtnp, ks - 1);
pe = (void *)bt_kychild_p(rbtnp, ke + 1);
pt = (void *)bt_kychild_p(rbtnp, kt - 1);
memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
/* adjust key count of right node */
rbtnp->n += nm;
/* move bttuples */
ks = lbtnp->n - nm + 1;
ke = lbtnp->n;
kt = 1;
ps = bt_kykey_p(btp, lbtnp, ks);
pe = bt_kykey_p(btp, lbtnp, ke + 1);
pt = bt_kykey_p(btp, rbtnp, kt);
memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
memset(ps, 0, (size_t)((char *)pe - (char *)ps));
ps = (void *)bt_kychild_p(lbtnp, ks - 1);
pe = (void *)bt_kychild_p(lbtnp, ke + 1);
pt = (void *)bt_kychild_p(rbtnp, kt - 1);
memcpy(pt, ps, (size_t)((char *)pe - (char *)ps));
memset(ps, 0, (size_t)((char *)pe - (char *)ps));
/* adjust key count of left node */
lbtnp->n -= nm;
errno = 0;
return 0;
}
/*man---------------------------------------------------------------------------
NAME
bt_kyread - read key
SYNOPSIS
#include "btree_.h"
int bt_kyread(btp, btnp, kn, bttuple_p)
btree_t *btp;
btnode_t *btnp;
size_t kn;
bttuple_t *bttuple_p;
DESCRIPTION
Function reads the (key, child) bttuple in slot kn of node btnp. The
results are returned in bttuple_p. If kn is zero, then the key field
of bttuple_p is cleared and child 0 is written in the child field.
bt_kyread will fail if one or more of the following is true:
[EINVAL] btp, btnp, or bttuple_p is NULL.
[EINVAL] btnp contains fewer than kn keys.
SEE ALSO
bt_kywrite.
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_kyread(btp, btnp, kn, bttuple_p)
btree_t *btp; /* --> */
btnode_t *btnp; /* --> */
size_t kn; /* --> */
bttuple_t *bttuple_p; /* <-- */
{
errno = 0;
#ifdef DEBUG
/* validate arguments */
if ((btp == NULL) || (btnp == NULL) || (bttuple_p == NULL)) {
BTEPRINT;
errno = EINVAL;
return -1;
}
if (kn > btnp->n) {
BTEPRINT;
errno = EINVAL;
return -1;
}
#endif
if (kn == 0) {
memset(bttuple_p->key_p, 0, sizeof(bttuple_p->key_p));
} else {
memcpy(bttuple_p->key_p, bt_kykey_p(btp, btnp, kn), btp->bthdr.keysize);
}
memcpy((void *)&bttuple_p->child, (void *)bt_kychild_p(btnp, kn), sizeof(bttuple_p->child));
errno = 0;
return 0;
}
/*man---------------------------------------------------------------------------
NAME
bt_kymvleft - move keys left
SYNOPSIS
#include "btree_.h"
int bt_kyshift(btp, btnp, kn, ns)
btree_t *btp;
btnode_t *btnp;
size_t kn;
int ns;
DESCRIPTION
Function shifts bttuples kn and above in node btnp by ns slots. If
ns > 0, the keys are shifted up. If ns < 0, they are shifted down.
The key count in is corrected for the shift. No other changes are
made.
bt_kymvleft will fail if one or more of the following is true:
[EINVAL] btp or lbtnp is NULL.
SEE ALSO
bt_kymvleft, bt_kymvright.
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_kyshift(btp, btnp, kn, ns)
btree_t *btp; /* --> */
btnode_t *btnp; /* <-> */
size_t kn; /* --> */
int ns; /* --> */
{
size_t ks = 0; /* first key to copy */
size_t ke = 0; /* last key to copy */
size_t kt = 0; /* target key */
void * ps = NULL; /* pointer to copy source */
void * pe = NULL; /* pointer to copy source end */
void * pt = NULL; /* pointer to copy target */
errno = 0;
#ifdef DEBUG
/* validate arguments */
if ((btp == NULL) || (btnp == NULL)) {
BTEPRINT;
errno = EINVAL;
return -1;
}
if ((kn == 0) || (kn > (btnp->n + 1))) {
BTEPRINT;
errno = EINVAL;
return -1;
}
#endif
if (((int)btnp->n + ns) > (int)btp->bthdr.m) {/* keys shifted out top */
BTEPRINT;
errno = BTEPANIC;
return -1;
}
if (-ns >= (int)kn) { /* keys shifted out bottom */
BTEPRINT;
errno = BTEPANIC;
return -1;
}
/* shift keys */
ks = kn;
ke = btnp->n;
kt = kn + ns;
ps = bt_kykey_p(btp, btnp, ks);
pe = bt_kykey_p(btp, btnp, ke + 1);
pt = bt_kykey_p(btp, btnp, kt);
memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
ps = (void *)bt_kychild_p(btnp, ks);
pe = (void *)bt_kychild_p(btnp, ke + 1);
pt = (void *)bt_kychild_p(btnp, kt);
memmove(pt, ps, (size_t)((char *)pe - (char *)ps));
/* adjust number of keys */
btnp->n = (int)btnp->n + ns;
/* clear memory above last key */
if (ns < 0) {
ps = bt_kykey_p(btp, btnp, btnp->n + 1);
pe = bt_kykey_p(btp, btnp, btp->bthdr.m + 1);
memset(ps, 0, (size_t)((char *)pe - (char *)ps));
ps = (void *)bt_kychild_p(btnp, btnp->n + 1);
pe = (void *)bt_kychild_p(btnp, btp->bthdr.m + 1);
memset(ps, 0, (size_t)((char *)pe - (char *)ps));
}
errno = 0;
return 0;
}
/*man---------------------------------------------------------------------------
NAME
bt_kywrite - write key
SYNOPSIS
#include "btree_.h"
int bt_kywrite(btp, btnp, kn, bttuple_p)
btree_t *btp;
btnode_t *btnp;
size_t kn;
bttuple_t *bttuple_p;
DESCRIPTION
Function writes the (key, child) bttuple contained in bttuple_p in slot
kn of node btnp. If kn is zero, then the contents of the key field
of bttuple_p are ignored and the contents of the child field are written
to child 0 of btnp. If bttuple_p is NULL, the slot is cleared.
bt_kywrite will fail if one or more of the following is true:
[EINVAL] btp or btnp is NULL.
[EINVAL] btnp contains fewer than kn keys.
SEE ALSO
bt_kywrite.
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_kywrite(btp, btnp, kn, bttuple_p)
btree_t * btp;
btnode_t * btnp;
size_t kn;
bttuple_t * bttuple_p;
{
errno = 0;
#ifdef DEBUG
/* validate arguments */
if ((!bt_valid(btp)) || (btnp == NULL)) {
BTEPRINT;
errno = EINVAL;
return -1;
}
if (kn > btnp->n) {
BTEPRINT;
errno = EINVAL;
return -1;
}
#endif
if (bttuple_p == NULL) {
if (kn != 0) {
memset(bt_kykey_p(btp, btnp, kn), 0, btp->bthdr.keysize);
}
memset((void *)bt_kychild_p(btnp, kn), 0, sizeof(bttuple_p->child));
} else {
if (kn != 0) {
memcpy(bt_kykey_p(btp, btnp, kn), bttuple_p->key_p, btp->bthdr.keysize);
}
memcpy((void *)bt_kychild_p(btnp, kn), (void *)&bttuple_p->child, sizeof(bttuple_p->child));
}
errno = 0;
return 0;
}