Category : C Source Code
Archive   : BTREE3.ZIP
Filename : BTREE.C

/*
* btree.c - hacked by ...!gatech!kd4nc!n4hgf!wht
*
* Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
* $ Author: mjr
* $ Log: btree.c,v
* $ Revision 1.1 88/06/01 21:35:07 mjr Initial revision.
* The original code was placed in the public domain. This is not,
* since I wish to retain some control over it. No restrictions are placed on
* modification, or use of this code, as long as the copyrights are not
* removed. There are some areas that really could use improving (like
* handling free nodes better) and I hope that if someone makes improvements
* they will keep me up to date on them (e-mail please, I am not on usenet).
* Marcus J. Ranum, William Welch Medical Library, 1988 [email protected] ||
* uunet!mimsy!aplcen!osiris!welchvax!mjr
*
* Defined functions:
*
* _btlink(alpha1,node1,alpha2,node2) * btdelete(node_num,bt)
* _btnext(node_num,node,bt) * btfind(key,node_num,reckey,recno,bt)
* _btprevious(node_num,node,bt) * bthead(node_num,key,recno,bt)
* _btmove(node_num,node,bt, dir) * btinsert(argkey,recno,bt)
* _flush_cache_node(bt,cache_node) * btnext(node_num,key,recno,bt)
* _linknbr(alpha,node1,node_num) * btopen(path,flags,mode,keysize)
* _nbrlink(node_num,alpha,node1) * btperror(str)
* _nodebal(alpha,node1,node2,node3) * btprevious(node_num,key,recno,bt)
* _popl(bt) * btsetrec(node_num,newrec,bt)
* _popr(bt) * bttail(node_num,key,recno,bt)
* _pushl(bt,node_num)
* _pushr(bt,node_num)
* _rnode(node_num,npt,bt)
* _wnode(node_num,npt,bt)
* _wsuper(bt) btclose(bt)
* _btflush(bt)
*
* Modification History:
* 12-23-1989-17:29-mfl-re-wrote the cache memory allocation steps
* 12-23-1989-17:29-mfl-replaced _bthead &_bttail with _btmove
* 12-09-1989-17:29-wht-get working on SCO UNIX -- just #defines
* 12-17-1988-17:51-wht-write sblk only at close-writes were inefficient
* 12-17-1988-17:51-wht-cache now read-write... writes were inefficient
* 12-17-1988-12:09-wht-allow open of existing index to specify zero keysize
* 12-16-1988-20:38-wht-variable max key length
* 12-16-1988-17:15-wht-static procs no longer static, but with '_' prefix

/* #define DEBUG uncomment this for debugging output */
#include
#include
#include

#define MAIN /* enables btree declarations in 'btree.h' */
#include "btree.h"
#undef MAIN

/* write the btree superblock to disk */
int
_wsuper(bt)
struct btree *bt;
{
register int save_bterrno = bterrno;

if (bt->rdonly)
return (0);

#ifdef DEBUG
fprintf(stderr, "BTREE: write superblock fd=%d\n", bt->fd);
#endif

bterrno = BT_BAD_WSUPER;
if (lseek(bt->fd, 0L, 0) < 0)
return (BT_ERR);

if (write(bt->fd, (char *) & bt->sblk, BT_SSIZ) != BT_SSIZ)
return (BT_ERR);

bterrno = save_bterrno;
return (0);
}



/* dynamically allocate a control structure for an open btree */
struct btree *
btopen(path, flags, mode, keysize)
char *path;
register int flags;
register int mode;

register int keysize;
{
struct btree *bt;
struct btnode_m *cache, *cacheptr;
register int r;
extern char *malloc();

if (keysize) {
keysize++; /* allow for null at end of record */
if (keysize & 1)
keysize++; /* keep key size even */
}
if (keysize > BT_KSIZ) {
fprintf(stderr, "BTREE: key size for %s (%d) exceeds max of %d\n",
path, keysize, BT_KSIZ);
exit(1);
}

/* lets be dynamic, shall we ? */
if ((bt = (struct btree *) malloc(sizeof(struct btree ))) == (BTREE * ) 0) {
bterrno = BT_BAD_MEMORY;
return ((BTREE * ) 0);
}
if ((bt->fd = open(path, flags, mode)) > -1) {
#ifdef DEBUG
fprintf(stderr, "BTREE: %s opened via fd #%d\n", path, bt->fd);
#endif
r = read(bt->fd, (char *) & bt->sblk, BT_SSIZ);

/* if read nothing, must be a new guy, right ? */
if (r == 0) {
bt->sblk.magic = BT_MAGIC;
bt->sblk.free = 1;
bt->sblk.root = 0;
bt->sblk.list = 0;
if (keysize)
bt->sblk.keysize = keysize;
else {
fprintf(stderr, "BTREE: cannot create index with zero length key\n");
exit(1);
}

if (_wsuper(bt) == 0)
r = BT_SSIZ;
} else if (r == BT_SSIZ) {
bterrno = 0;
if (bt->sblk.magic != BT_MAGIC)
bterrno = BT_BAD_MAGIC;
else if (keysize && (keysize != bt->sblk.keysize))
bterrno = BT_BAD_KSIZ;
if (bterrno) {
close(bt->fd);
free((char *) bt);
return ((BTREE * ) 0);
}
}
/* cleverly check ret value from either read or write */
if (r != BT_SSIZ) {
bterrno = BT_BAD_SBLK;
close(bt->fd);
free((char *) bt);
return ((BTREE * ) 0);
}
} else {
/* couldnt even open the bloody file */
free((char *) bt);
return ((BTREE * ) 0);
}

#ifdef DEBUG
fprintf(stderr, "BTREE: initialize disk cache memory\n");
#endif
/* initialize the disk cache memory (allocate the whole thing) */
cache = (struct btnode_m *) malloc(sizeof(struct btnode_m)*BT_CSIZ);
if (cache == (struct btnode_m *) 0) {
fprintf(stderr, "BTREE: insufficient memory for disk cache\n");
exit(1);
}
cacheptr = cache; /* point to start of cache */
for (r = 0; r < BT_CSIZ; r++) {
bt->cache[r] = cacheptr++; /* point to cache block */
bt->cache[r]->node_num = -1; /* reset node number */
bt->cache[r]->dirty = 0; /* mark it clean */
}
bt->rdonly = ((flags & (O_WRONLY | O_RDWR)) == O_RDONLY);

return (bt);
}


/* close and deallocate the control structure */
btclose(bt)
struct btree *bt;
{
register int err = 0;

if (!bt->rdonly) {
if (err = _btflush(bt))
fprintf(stderr, "BTREE: index file close error\n");
}
close(bt->fd);
free((char *) bt->cache[0]); /* this should free all cache */
free((char *) bt);
return (err);
}


int
_flush_cache_node(bt, cache_node)
struct btree *bt;
register struct btnode_m *cache_node;
{
register int save_bterrno = bterrno;

if ((cache_node->node_num == -1) || (!cache_node->dirty))
return (0);
bterrno = BT_BAD_FLUSH;
if (lseek(bt->fd, (((long) cache_node->node_num * BT_NSIZ) + BT_SSIZ), 0) < 0)
return (BT_ERR);
if (write(bt->fd, (char *) & cache_node->n, BT_NSIZ) != BT_NSIZ)
return (BT_ERR);
cache_node->dirty = 0;
bterrno = save_bterrno;
return (0);
}


int
_btflush(bt)
struct btree *bt;
{
register int icache;
register struct btnode_m *cache_node;

for (icache = 0; icache < BT_CSIZ; icache++) {
cache_node = bt->cache[icache];
if (_flush_cache_node(bt, cache_node))
return (BT_ERR);
}
if (_wsuper(bt))
return (BT_ERR);
return (0);
}


/* write a node to cache */
int
_wnode(node_num, npt, bt)
register short node_num;
struct btnode_m *npt;
register struct btree *bt;
{
unsigned int hash = (unsigned int) node_num &(BT_CSIZ-1);
register struct btnode_m *cache_node = bt->cache[hash];
extern int errno;

if (!node_num)
return (0);

errno = 0;
if (bt->rdonly) {
errno = EPERM; /* would be reported later */
return (BT_ERR);
}
bterrno = BT_BAD_WNODE;
if (cache_node->node_num != node_num) {
if (_flush_cache_node(bt, cache_node))
return (BT_ERR);
}
/* update cache if the write succeeded */
(void) bcopy((char *) npt, (char *) cache_node, sizeof(struct btnode_m ));
cache_node->node_num = node_num;
cache_node->dirty = 1;
bterrno = 0;
return (0);
}


/* read a node from disk */
int
_rnode(node_num, npt, bt)
register short node_num;
register struct btnode_m *npt;
register struct btree *bt;
{
register rdcount;
register long readpos;
unsigned int hash = (unsigned int) node_num &(BT_CSIZ-1);
register struct btnode_m *cache_node = bt->cache[hash];
extern int errno;

if (!node_num) {
(void) bzero((char *) npt, sizeof(struct btnode_m ));
return (0);
}
errno = 0;
bterrno = BT_BAD_RNODE;
if (cache_node->node_num != node_num) {
/* if no cache hit, load from disk */
cache_no_hits++;
if (!bt->rdonly) {
if (_flush_cache_node(bt, cache_node))
return (BT_ERR);
}

if (lseek(bt->fd, (readpos = ((long) node_num * BT_NSIZ) + BT_SSIZ), 0) < 0)
return (BT_ERR);
if ((rdcount = read(bt->fd, (char *) & cache_node->n, BT_NSIZ)) != BT_NSIZ) {
#ifdef DEBUG
if (rdcount >= 0)
fprintf(stderr, "BTREE: rdcount for node %u was %u (should be %d) @ %ld\n",
node_num, rdcount, BT_NSIZ, readpos);
#endif
return (BT_ERR);
}
cache_node->node_num = node_num;
cache_node->dirty = 0;
} else
cache_hits++;

(void) bcopy((char *) cache_node, (char *) npt, sizeof(struct btnode_m ));

bterrno = 0;
return (0);
}


int
_pushl(bt, node_num)
struct btree *bt;
register short node_num;
{
if (++(bt->lstak.sptr) >= STACK_SIZ) {
bterrno = BT_BAD_STACK;
exit(0);
}
bt->lstak.ele[bt->lstak.sptr] = node_num;
bt->lstak.lev[bt->lstak.sptr] = ++bt->slev;
return;
}


int
_pushr(bt, node_num)
struct btree *bt;
register short node_num;
{
if (++(bt->rstak.sptr) >= STACK_SIZ) {
bterrno = BT_BAD_STACK;
exit(0);
}
bt->rstak.ele[bt->rstak.sptr] = node_num;
bt->rstak.lev[bt->rstak.sptr] = ++bt->slev;
return;
}



short
_popr(bt)
struct btree *bt;
{
bt->slev = bt->rstak.lev[bt->rstak.sptr];

while (bt->lstak.lev[bt->lstak.sptr] > bt->slev)
(bt->lstak.sptr)--;

if (bt->rstak.sptr == 0)
return (0);

bt->slev--;
return (bt->rstak.ele[(bt->rstak.sptr)--]);
}



short
_popl(bt)
struct btree *bt;
{
bt->slev = bt->lstak.lev[bt->lstak.sptr];

while (bt->rstak.lev[bt->rstak.sptr] > bt->slev)
(bt->rstak.sptr)--;

if (bt->lstak.sptr == 0)
return (0);

bt->slev--;
return (bt->lstak.ele[(bt->lstak.sptr)--]);
}


void
_btlink(alpha1, node1, alpha2, node2)
register int alpha1;
register int alpha2;
struct btnode *node1;
struct btnode *node2;
{
if (alpha1 == -1 && alpha2 == -1)
node1->lptr = node2->lptr;
else if (alpha1 == -1 && alpha2 == 1)
node1->lptr = node2->rptr;
else if (alpha1 == 1 && alpha2 == -1)
node1->rptr = node2->lptr;
else
node1->rptr = node2->rptr;
}



/* number a link according to alpha */
void
_nbrlink(node_num, alpha, node1)
short *node_num;
register int alpha;
struct btnode *node1;
{
*node_num = (alpha == 1) ? node1->rptr : node1->lptr;
}



/* set a link according to alpha */
void
_linknbr(alpha, node1, node_num)
register int alpha;
struct btnode *node1;
register short node_num;
{

if (alpha == 1)
node1->rptr = node_num;
else
node1->lptr = node_num;
}



void
_nodebal(alpha, node1, node2, node3)
register int alpha;
struct btnode *node1;
struct btnode *node2;
struct btnode *node3;
{
if (node1->balance == alpha) {
node2->balance = -alpha;
node3->balance = 0;
} else if (node1->balance == 0)
node2->balance = node3->balance = 0;
else {
node2->balance = 0;
node3->balance = alpha;
}
}



/* change the record number in a node */
btsetrec(node_num, newrec, bt)
register short node_num;
long newrec;
struct btree *bt;
{
struct btnode_m tnode;

if (_rnode(node_num, &tnode, bt))
return (BT_ERR);

tnode.n.recno = newrec;

if (_wnode(node_num, &tnode, bt))
return (BT_ERR);

return (0);
}


/* insert the node into the tree */
btinsert(argkey, recno, bt)
char *argkey;
long recno;
struct btree *bt;
{
register int compare;
short trec1;
short trec2;
short trec3;
short trec4;
short top;
struct btnode_m tnode1;
struct btnode_m tnode2;
struct btnode_m tnode3;
struct btnode_m tnode4;


/* the very first node gets inserted specially */
if (bt->sblk.root == 0) {
bt->sblk.root = 1;
tnode1.n.balance = tnode1.n.rptr = tnode1.n.lptr = 0;
tnode1.n.deleted = BT_ACTIVE;
tnode1.n.recno = recno;

strncpy(tnode1.key, argkey, bt->sblk.keysize - 1);
tnode1.key[bt->sblk.keysize - 1] = '\0';
if (_wnode(1, &tnode1, bt) < 0)
return (BT_ERR);

bt->sblk.free++;
bt->sblk.list++;
return (0);
}
top = -1;
trec1 = bt->sblk.root;
trec4 = bt->sblk.root;
while (1) {
if (_rnode(trec1, &tnode1, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec1(1) read error\n");
#endif
return (BT_ERR);
}
if ((compare = strcmp(argkey, tnode1.key)) < 0) {
/* (move left) */
trec2 = tnode1.n.lptr;

if (trec2 == 0) {
/* insert here */
trec2 = bt->sblk.free++;
tnode1.n.lptr = trec2;
break; /* loop exit */
} else {
/* look again from this node */
if (_rnode(trec2, &tnode2, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec2(1) read error\n");
#endif
return (BT_ERR);
}
if (tnode2.n.balance != 0) {
top = trec1;
trec4 = trec2;
}
}
trec1 = trec2;
} else {
/* (move right) */
trec2 = tnode1.n.rptr;

if (trec2 == 0) {
/* insert here */
trec2 = bt->sblk.free++;
tnode1.n.rptr = trec2;
break; /* loop exit */
} else {
/* look again from this node */
if (_rnode(trec2, &tnode2, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec2(2) read error\n");
#endif
return (BT_ERR);
}
if (tnode2.n.balance != 0) {
top = trec1;
trec4 = trec2;
}
trec1 = trec2;
}
}
}

/* Step 5 (insert key at tnode2) */
tnode2.n.lptr = tnode2.n.rptr = 0;
tnode2.n.balance = 0;
tnode2.n.deleted = BT_ACTIVE;
tnode2.n.recno = recno;
strncpy(tnode2.key, argkey, bt->sblk.keysize - 1);
tnode2.key[bt->sblk.keysize - 1] = '\0';

if (_wnode(trec2, &tnode2, bt))
return (BT_ERR);
if (_wnode(trec1, &tnode1, bt))
return (BT_ERR);
if (_rnode(trec4, &tnode4, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec4(1) read error\n");
#endif
return (BT_ERR);
}
/* (adjust balance factors) */
if (strcmp(argkey, tnode4.key) < 0)
trec3 = trec1 = tnode4.n.lptr;
else
trec3 = trec1 = tnode4.n.rptr;

while (trec1 != trec2) {
if (_rnode(trec1, &tnode1, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec1(2) read error\n");
#endif
return (BT_ERR);
}
if (strcmp(argkey, tnode1.key) < 0) {
tnode1.n.balance = -1;
if (_wnode(trec1, &tnode1, bt) < 0)
return (BT_ERR);
trec1 = tnode1.n.lptr;
} else {
tnode1.n.balance = 1;
if (_wnode(trec1, &tnode1, bt) < 0)
return (BT_ERR);
trec1 = tnode1.n.rptr;
}
}

compare = (strcmp(argkey, tnode4.key) < 0) ? -1 : 1;
if (tnode4.n.balance == 0) {
bt->sblk.list++;
tnode4.n.balance = compare;
if (_wnode(trec4, &tnode4, bt) < 0)
return (BT_ERR);
return (0);
} else if (tnode4.n.balance == -compare) {
bt->sblk.list++;
tnode4.n.balance = 0;
if (_wnode(trec4, &tnode4, bt) < 0)
return (BT_ERR);
return (0);
} else {
/* (tree out of balance) */
bt->sblk.list++;
if (_rnode(trec4, &tnode4, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec4(2) read error\n");
#endif
return (BT_ERR);
}
if (_rnode(trec3, &tnode3, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec3(1) read error\n");
#endif
return (BT_ERR);
}
if (tnode3.n.balance == compare) {
/* (single rotate) */
trec1 = trec3;
_btlink(compare, (BTNODE * ) & tnode4, -compare, (BTNODE * ) & tnode3);
_linknbr(-compare, (BTNODE * ) & tnode3, trec4);
tnode4.n.balance = tnode3.n.balance = 0;
} else {
/* (double rotate) */
_nbrlink(&trec1, -compare, (BTNODE * ) & tnode3);
if (_rnode(trec1, &tnode1, bt)) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: trec1(3) read error\n");
#endif
return (BT_ERR);
}
_btlink(-compare, (BTNODE * ) & tnode3, compare, (BTNODE * ) & tnode1);
_linknbr(compare, (BTNODE * ) & tnode1, trec3);
_btlink(compare, (BTNODE * ) & tnode4, -compare, (BTNODE * ) & tnode1);
_linknbr(-compare, (BTNODE * ) & tnode1, trec4);
_nodebal(compare, (BTNODE * ) & tnode1, (BTNODE * ) & tnode4, (BTNODE * ) & tnode3);
tnode1.n.balance = 0;
if (_wnode(trec1, &tnode1, bt))
return (BT_ERR);
}

if (top == -1)
bt->sblk.root = trec1;
else {
/* balanced at top of a sub-tree */
if (_rnode(top, &tnode2, bt) < 0) {
#ifdef DEBUG
fprintf(stderr, "BTREE: btinsert: top(1) read error\n");
#endif
return (BT_ERR);
}
if (trec4 == tnode2.n.rptr)
tnode2.n.rptr = trec1;
else
tnode2.n.lptr = trec1;
if (_wnode(top, &tnode2, bt))
return (BT_ERR);
}
if (_wnode(trec4, &tnode4, bt))
return (BT_ERR);
if (_wnode(trec3, &tnode3, bt))
return (BT_ERR);
return (0);
}
}


/* drop a node */
btdelete(node_num, bt)
register short node_num;
struct btree *bt;
{
struct btnode_m node;

if (node_num == 0) {
bterrno = BT_BAD_ROOT;
return (BT_ERR);
} else {
if (_rnode(node_num, &node, bt))
return (BT_ERR);
node.n.deleted = BT_DELETED;
if (_wnode(node_num, &node, bt))
return (BT_ERR);
else
bt->sblk.list--;
}
return (0);
}


/* find the next node */
btnext(node_num, key, recno, bt)
short *node_num;
char **key;
long *recno;
struct btree *bt;
{
static struct btnode_m node;
register int retn;
if (_rnode(*node_num, &node, bt))
return (BT_ERR);
retn = _btnext(node_num, &node, bt);
*key = node.key;
*recno = node.n.recno;
return (retn);

}


/* find the next node */
_btnext(node_num, node, bt)
short *node_num;
register struct btnode_m *node;
struct btree *bt;
{
short _popl();
short _popr();
short s_nod;

s_nod = *node_num;

if (*node_num == 0) {
/* undefined current node - wind to beginning of file */
return (_btmove(node_num, node, bt, BT_HEAD));
}

do {
if (node->n.rptr == 0) {
/* can't move right */
if (bt->lstak.sptr == 0) {
/* none in stack */
if (_rnode(*node_num, node, bt))
return (BT_ERR);
return (BT_EOF);
} else {
/* can't go right &stack full (pop stack) */
s_nod = _popl(bt);
if (_rnode(s_nod, node, bt) < 0)
return (BT_ERR);
}
} else {
/* move right */
_pushr(bt, s_nod);
s_nod = node->n.rptr;
if (_rnode(s_nod, node, bt))
return (BT_ERR);

while (node->n.lptr != 0) {
/* bottom left */
_pushl(bt, s_nod);
/* of this sub-tree */
s_nod = node->n.lptr;
if (_rnode(s_nod, node, bt))
return (BT_ERR);
}
}
} while (node->n.deleted == BT_DELETED);

*node_num = s_nod;
return (0);
}


/* go to the tail of the file */
bttail(node_num, key, recno, bt)
short *node_num;
char **key;
long *recno;
struct btree *bt;
{
static struct btnode_m node;
register int retn = _btmove(node_num, &node, bt, BT_TAIL);
*key = node.key;
*recno = node.n.recno;
return (retn);
}


/* go to the head of the file */
bthead(node_num, key, recno, bt)
short *node_num;
char **key;
long *recno;
struct btree *bt;
{
static struct btnode_m node;
register int retn = _btmove(node_num, &node, bt, BT_HEAD);
*key = node.key;
*recno = node.n.recno;
return (retn);
}


/* move to the head or tail of the file */
_btmove(node_num, node, bt, dir)
struct btree *bt;
short *node_num, dir;
register struct btnode_m *node;
{
short s_nod;
short t_nod;

bt->rstak.sptr = 0;
bt->lstak.sptr = 0;
bt->rstak.ele[0] = 0;
bt->lstak.ele[0] = 0;

/* begin at list head */
s_nod = bt->sblk.root;

if (_rnode(s_nod, node, bt))
return (BT_ERR);

while (1) {
/* decide on direction */
t_nod = ((dir == BT_TAIL) ? node->n.rptr : node->n.lptr);

if (t_nod != 0) {
if (dir == BT_TAIL) {
_pushr(bt, s_nod);
s_nod = node->n.rptr;
} else {
_pushl(bt, s_nod);
s_nod = node->n.lptr;
}
if (_rnode(s_nod, node, bt))
return (BT_ERR);
} else {
if (node->n.deleted == BT_DELETED) {
/* skip all deleted nodes */
while (node->n.deleted == BT_DELETED) {
if (dir == BT_TAIL) {
if (_btnext(&s_nod, node, bt) == BT_EOF) {
if (_btprevious(&s_nod, node, bt) < 0)
return (BT_ERR);
*node_num = s_nod;
return (0);
}
} else {
if (_btprevious(&s_nod, node, bt) == BT_EOF) {
if (_btnext(&s_nod, node, bt) < 0)
return (BT_ERR);
*node_num = s_nod;
return (0);
}
}
}
*node_num = s_nod;
return (0);
} else {
/* at end of a branch */

*node_num = s_nod;
return (0);
}
}
}
}



/* find a key */
btfind(key, node_num, reckey, recno, bt)
char *key;
short *node_num;
char **reckey;
long *recno;
struct btree *bt;
{
register int direction;
short s_nod;
static struct btnode_m node;

bt->rstak.sptr = 0;
bt->lstak.sptr = 0;
bt->rstak.ele[0] = 0;
bt->lstak.ele[0] = 0;

bt->slev = 0; /* tree level at start of search */

/* begin at list head */
s_nod = bt->sblk.root;

if (_rnode(s_nod, &node, bt))
return (BT_ERR);

bterrno = 0;

while (node.n.deleted == BT_DELETED || (direction = strcmp(key, node.key)) != 0) {

if (bterrno == BT_EOF) /* hit end of file */
break;

if (direction > 0) { /* search to right */
if (node.n.rptr != 0) {
_pushr(bt, s_nod);
s_nod = node.n.rptr;
if (_rnode(s_nod, &node, bt))
return (BT_ERR);
} else /* end of a branch */
bterrno = BT_EOF;
} else { /* search to left */
if (node.n.lptr != 0) {
_pushl(bt, s_nod);
s_nod = node.n.lptr;
if (_rnode(s_nod, &node, bt))
return (BT_ERR);
} else /* end of a branch */
bterrno = BT_EOF;
}

/* skip all deleted nodes */
while (node.n.deleted == BT_DELETED) {
if (_btnext(&s_nod, &node, bt) == BT_EOF) {
if (_btprevious(&s_nod, &node, bt) < 0)
return (BT_ERR);
bterrno = BT_EOF;
break;
}
}
}
*recno = node.n.recno;
*reckey = node.key;
*node_num = s_nod;
return (strcmp(key, node.key) == 0 ? 0 : BT_NREC);
}


/* find the previous node */
btprevious(node_num, key, recno, bt)
short *node_num;
char **key;
long *recno;
struct btree *bt;
{
static struct btnode_m node;
register int retn;
if (_rnode(*node_num, &node, bt))
return (BT_ERR);
retn = _btprevious(node_num, &node, bt);
*key = node.key;
*recno = node.n.recno;
return (retn);
}


/* get the previous node */
_btprevious(node_num, node, bt)
short *node_num;
register struct btnode_m *node;
struct btree *bt;
{
short _popr();
short _popl();
short s_nod;

s_nod = *node_num;

/* if we are called without a node, wind to the end of file */
if (*node_num == 0)
return (_btmove(node_num, node, bt, BT_TAIL));

do {
if (node->n.lptr == 0) {
/* can't move left */
if (bt->rstak.sptr == 0) {
/* none in stack */
if (_rnode(*node_num, node, bt))
return (BT_ERR);
return (BT_EOF);
/* don't reset node_num */
} else {
/* can't go left &stack full (pop stack) */
s_nod = _popr(bt);
if (_rnode(s_nod, node, bt))
return (BT_ERR);
}
} else {
/* left then to bottom right - is previous */
_pushl(bt, s_nod);
s_nod = node->n.lptr;
if (_rnode(s_nod, node, bt))
return (BT_ERR);
while (node->n.rptr != 0) {
/* bottom right */
_pushr(bt, s_nod);
/* of this sub-tree */
s_nod = node->n.rptr;
if (_rnode(s_nod, node, bt))
return (BT_ERR);
}
}
} while (node->n.deleted == BT_DELETED);

*node_num = s_nod;
return (0);
}


/* print the btree error message */
void
btperror(str)
char *str;
{
extern int errno;

/* is it ours ?? */
if (bterrno) {
fprintf(stderr, "BTREE: %s: %s\n", str, bterrs[bterrno]);
bterrno = 0;
}
if (errno) {
fprintf(stderr, "BTREE: (OS error) ");
perror(str);
errno = 0;
}
}