mjr@welchsun2.UUCP (Marcus J. Ranum) (06/02/88)
comp.sources.misc: Volume 3, Issue 49
Submitted-By: "Marcus J. Ranum" <mjr@welchsun2.UUCP>
Archive-Name: btree
Poor Man's Btree Library
This is a library that maintains a simple balanced btree index. Nothing
more is provided than routines to insert, set, find (specific, next,
and previous), and delete keys. Each key, however, has a spare long
value that can be used to contain an offset to a data file. A library
to handle fixed-length records based on these pointers should be
trivial. (Can you say 'dBASEIII'?) Another failing of this library is
its total inability to cope with having several programs modifying
indices at the same time. (it *CAN*, but I won't vouch for the result)
The good solutions to that particular problem are OS dependent,
unfortunately, and I am not a database guru anyhow.
---mangle------mangle------mangle------mangle------mangle------mangle---
#!/bin/sh
# This is a shell archive.
# run the file through sh.
# shar: Shell Archiver
# Run the following text with /bin/sh to create:
# README
# Makefile
# btree.c
# btree.h
# btree.3
# bench.c
# loadtree.c
# treedump.c
# sizes.c
# example.c
# This archive created: Wed Jun 1 22:09:41 1988
echo shar: extracting README '(3153 characters)'
sed 's/^XX//' << \SHAR_EOF > README
XXPoor Man's Btree Library
XX
XXThis is a library that maintains a simple balanced btree index. Nothing
XXmore is provided than routines to insert, set, find (specific, next,
XXand previous), and delete keys. Each key, however, has a spare long
XXvalue that can be used to contain an offset to a data file. A library
XXto handle fixed-length records based on these pointers should be
XXtrivial. (Can you say 'dBASEIII'?) Another failing of this library is
XXits total inability to cope with having several programs modifying
XXindices at the same time. (it *CAN*, but I won't vouch for the result)
XXThe good solutions to that particular problem are OS dependent,
XXunfortunately, and I am not a database guru anyhow.
XX
XXThe code originally came from a Public Domain package written by Ray
XXSwartz in 1983. I have almost totally re-written it; a proverbial 'no
XXline remains untouched' job that included removal of globals,
XXrearranging most of the data structures, and use of read/write for file
XXI/O instead of stdio. I also made sure that return values are all
XXchecked properly, so they can be properly ignored in the user code :-)
XXAnother addition is a simple cache, which boosted performance a great
XXdeal. The cache is maintained through a sort of a hash. I had a fairly
XXnifty LRU cache set up, originally, but it turned out to be marginally
XXslower, according to gprof, time, and anything else I could bring to
XXbear on the problem. If a real database guru takes a look at this,
XXperhaps they can come up with a better way of doing things.
XX
XXSome aspects of this package are a bit primitive - mostly those that
XXdeal with deleting nodes. Deleted nodes are simply flagged as such, and
XXare ignored when searching for data. This effectively means that the
XXindex will continue to grow. Fixing this is left as an exercise,
XXetc... :-) (actually, keeping the stuff around has its uses, too.)
XXThere is a hook in the super block structure designed to allow a
XX'free-list' to be implemented, but no hooks in the btdelete() code for
XXjoining nodes, etc, etc.
XX
XXThe original code was placed in the public domain. This is not, since I
XXwish to retain some control over it. No restrictions are placed on
XXmodification, or use of this code, as long as the copyrights are not
XXremoved. There are some areas that really could use improving (like
XXhandling free nodes better) and I hope that if someone makes
XXimprovements they will keep me up to date on them (e-mail please, I am
XXnot on usenet).
XX
XXByte-order and portability: There are #ifdefs for BYTEORDER, which make
XXthe program store data in network byte order (at least the data
XXstructures that drive the library - user data is the user's problem.)
XXThere are several unsolved problems with this approach. It works fine
XXbetween my Sun and my VAX, but the way the structures are written to
XXdisk is also going to depend on your compiler. The BYTEORDER code is
XXnot guaranteed to work, and if it doesn't, your best bet is to look at
XXthe output of sizes.c and to check to see if your compiler assembles
XXthe structures in the same ORDER.
XX
XX Marcus J. Ranum, William Welch Medical Library, 1988
XX mjr@jhuigf.BITNET || uunet!mimsy!aplcen!osiris!welchvax!mjr
SHAR_EOF
if test 3153 -ne "`wc -c README`"
then
echo shar: error transmitting README '(should have been 3153 characters)'
fi
echo shar: extracting Makefile '(1880 characters)'
sed 's/^XX//' << \SHAR_EOF > Makefile
XX# Makefile for btree library
XX# Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX#
XX#
XX# $Header: Makefile,v 1.1 88/06/01 21:36:05 mjr Rel $: Makefile
XX#
XX# $Log: Makefile,v $
XX# Revision 1.1 88/06/01 21:36:05 mjr
XX# Initial revision
XX#
XX#
XX#
XX
XX# define SYSV or BSD (only for purposes of test code) - btree.c doesn't care.
XX#
XX# define BYTEORDER to store the
XX# data files in network byte order. On systems that are already in the
XX# right byteorder, defining this will waste a few cycles here and there,
XX# but the slowdown is I/O anyway.
XXCFLAGS=-O -DBSD -DBYTEORDER
XXLFLAGS=-s
XXLINTFLAGS=-h -x -u -DBSD -DBYTEORDER
XX
XXLIB= libbtree.a
XXLIBDIR= /usr/local/lib
XXHDR= btree.h
XXHDRDIR= /usr/include/local
XXMAN= btree.3
XXMANDIR= /usr/man/manl
XX
XXall: example loadtree treedump bench sizes
XX
XX$(LIB): btree.o
XX ar rc $(LIB) btree.o
XX ranlib $(LIB)
XX
XXexample: $(LIB) example.o
XX cc $(LFLAGS) -o example example.o $(LIB)
XX
XXloadtree: $(LIB) loadtree.o
XX cc $(LFLAGS) -o loadtree loadtree.o $(LIB)
XX
XXtreedump: $(LIB) treedump.o
XX cc $(LFLAGS) -o treedump treedump.o $(LIB)
XX
XXbench: $(LIB) bench.o
XX cc $(LFLAGS) -o bench bench.o $(LIB)
XX
XXsizes: sizes.o
XX cc $(LFLAGS) -o sizes sizes.o
XX @sizes
XX
XXbtree.o: $(HDR) Makefile
XXexample.o: $(HDR) Makefile
XXloadtree.o: $(HDR) Makefile
XXtreedump.o: $(HDR) Makefile
XXbench.o: $(HDR) Makefile
XXsizes.o: $(HDR) Makefile
XX
XXinstall: $(LIB) $(MAN)
XX cp $(LIB) $(LIBDIR)/$(LIB)
XX chmod 644 $(LIBDIR)/$(LIB)
XX cp $(HDR) $(HDRDIR)/$(HDR)
XX chmod 644 $(HDRDIR)/$(HDR)
XX ranlib $(LIBDIR)/$(LIB)
XX cp $(MAN) $(MANDIR)/$(MAN)
XX chmod 644 $(MANDIR)/$(MAN)
XX
XXclean:
XX rm -f $(LIB) *.o example bench loadtree treedump core mon.out \
XX sizes llib-lbtree.ln btr.shar
XX
XXlint:
XX lint $(LINTFLAGS) btree.c
XX
XXdiction:
XX style $(MAN)
XX diction $(MAN)
XX
XXlintlib:
XX lint -Cbtree btree.c
XX
XXshar:
XX shar -a README Makefile btree.c $(HDR) $(MAN) bench.c \
XX loadtree.c treedump.c sizes.c example.c > btr.shar
SHAR_EOF
if test 1880 -ne "`wc -c Makefile`"
then
echo shar: error transmitting Makefile '(should have been 1880 characters)'
fi
echo shar: extracting btree.c '(17883 characters)'
sed 's/^XX//' << \SHAR_EOF > btree.c
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX */
XX
XX#ifndef lint
XXstatic char *RCSid="$Header: btree.c,v 1.1 88/06/01 21:35:07 mjr Rel $: btree.c";
XX#endif
XX
XX/*
XX * $Log: btree.c,v $
XX * Revision 1.1 88/06/01 21:35:07 mjr
XX * Initial revision
XX *
XX */
XX
XX#include <stdio.h>
XX#include "btree.h"
XX
XX/* if we wish to store our disk data in network byte order */
XX#ifdef BYTEORDER
XX#include <sys/types.h>
XX#include <netinet/in.h>
XX#endif
XX
XX#define BT_NSIZ (sizeof(struct btnode))
XX#define BT_SSIZ (sizeof(struct btsuper))
XX
XX
XX/* the errno for btree problems. we use negative # - */
XX/* so btperror can use the real UNIX errno */
XXint bterrno = 0;
XXchar *bterrs[] = {
XX "No btree error",
XX "Bad index magic number",
XX "History stack overflow",
XX "Cannot delete node zero",
XX 0
XX};
XX
XX#ifdef vax
XXextern void bcopy();
XXextern void free();
XXextern void exit();
XXextern void perror();
XX#endif
XX
XX
XX/* write the btree superblock to disk */
XXstatic int
XXwsuper(bt)
XXstruct btree *bt;
XX{
XX#ifdef BYTEORDER
XX struct btsuper boge;
XX#endif
XX extern long lseek();
XX
XX if (lseek(bt->fd, 0L, 0) < 0)
XX return (-1);
XX
XX#ifdef BYTEORDER
XX boge.magic = htonl(bt->sblk.magic);
XX boge.free = htonl(bt->sblk.free);
XX boge.root = htonl(bt->sblk.root);
XX boge.list = htonl(bt->sblk.list);
XX
XX if (write(bt->fd, (char *) &boge, BT_SSIZ) != BT_SSIZ)
XX return (-1);
XX#else
XX if (write(bt->fd, (char *) &bt->sblk, BT_SSIZ) != BT_SSIZ)
XX return (-1);
XX#endif
XX
XX return (0);
XX}
XX
XX
XX
XX/* dynamically allocate a control structure for an open btree */
XXstruct btree *
XXbtopen(path, flags, mode)
XXchar *path;
XXint flags;
XXint mode;
XX{
XX struct btree *bt;
XX int r;
XX extern char *malloc();
XX
XX /* lets be dynamic, shall we ? */
XX#ifndef lint
XX /* this to avoid the possible pointer alignment lint message */
XX if ((bt = (struct btree *) malloc(sizeof(struct btree))) == NULL)
XX return (NULL);
XX#else
XX bt = (struct btree *)0;
XX#endif
XX
XX if ((bt->fd = open(path, flags, mode)) > -1) {
XX
XX r = read(bt->fd, (char *) &bt->sblk, BT_SSIZ);
XX
XX /* if read nothing, must be a new guy, right ? */
XX if (r == 0) {
XX bt->sblk.magic = BT_MAGIC;
XX bt->sblk.free = 1L;
XX bt->sblk.root = 0L;
XX bt->sblk.list = 0L;
XX
XX if (wsuper(bt) == 0)
XX r = BT_SSIZ;
XX }
XX#ifdef BYTEORDER
XX else {
XX /* read something, decode the numbers */
XX bt->sblk.magic = ntohl(bt->sblk.magic);
XX bt->sblk.free = ntohl(bt->sblk.free);
XX bt->sblk.root = ntohl(bt->sblk.root);
XX bt->sblk.list = ntohl(bt->sblk.list);
XX }
XX#endif
XX
XX /* cleverly check ret value from either read or write */
XX if (r != BT_SSIZ) {
XX (void) close(bt->fd);
XX (void) free((char *) bt);
XX return (NULL);
XX }
XX
XX /* check that ole magic number */
XX if (bt->sblk.magic != BT_MAGIC) {
XX bterrno = BT_BAD_MAGIC;
XX (void) close(bt->fd);
XX (void) free((char *) bt);
XX return (NULL);
XX }
XX } else {
XX /* couldnt even open the bloody file */
XX (void) free((char *) bt);
XX return (NULL);
XX }
XX
XX /* zero the cache - record numbers will never be -1, */
XX /* so the cache will load as activity takes place */
XX for(r = 0; r < BT_CSIZ; r++)
XX bt->cache[r].recno = -1L;
XX
XX return (bt);
XX}
XX
XX
XX
XX/* close and deallocate the control structure */
XXbtclose(bt)
XXstruct btree *bt;
XX{
XX int t;
XX
XX t = wsuper(bt);
XX (void) close(bt->fd);
XX (void) free((char *) bt);
XX return (t);
XX}
XX
XX
XX
XX/* write a node to disk */
XXstatic int
XXwnode(nbr, npt, bt)
XXlong nbr;
XXstruct btnode *npt;
XXstruct btree *bt;
XX{
XX extern long lseek();
XX extern char *strncpy();
XX#ifdef BYTEORDER
XX struct btnode boge;
XX#endif
XX
XX if (lseek(bt->fd, (long) ((nbr * BT_NSIZ) + BT_SSIZ), 0) == -1)
XX return (-1);
XX
XX
XX#ifdef BYTEORDER
XX boge.recno = htonl(npt->recno);
XX boge.lptr = htonl(npt->lptr);
XX boge.rptr = htonl(npt->rptr);
XX boge.deleted = htons(npt->deleted);
XX boge.balance = htons(npt->balance);
XX (void) strncpy(boge.key, npt->key, BT_KSIZ - 1);
XX if (write(bt->fd, (char *) &boge, BT_NSIZ) != BT_NSIZ)
XX return (-1);
XX#else
XX if (write(bt->fd, (char *) npt, BT_NSIZ) != BT_NSIZ)
XX return (-1);
XX#endif
XX
XX /* update cache - if the write succeeded */
XX (void)bcopy((char *)npt,(char *)&bt->cache[(int)nbr % BT_CSIZ],BT_NSIZ);
XX return (0);
XX}
XX
XX
XX
XX/* read a node from disk */
XXstatic int
XXrnode(nbr, npt, bt)
XXlong nbr;
XXstruct btnode *npt;
XXstruct btree *bt;
XX{
XX extern long lseek();
XX extern char *strncpy();
XX int hash;
XX#ifdef BYTEORDER
XX struct btnode boge;
XX#endif
XX hash = (int)nbr % BT_CSIZ;
XX
XX /* check for cache hit - simple hash - braindead, really */
XX if(bt->cache[hash].recno != nbr) {
XX
XX /* if no cache hit, load from disk */
XX if (lseek(bt->fd, (long) ((nbr * BT_NSIZ) + BT_SSIZ), 0) == -1)
XX return (-1);
XX#ifndef BYTEORDER
XX if (read(bt->fd, (char *) &bt->cache[hash], BT_NSIZ) != BT_NSIZ)
XX return (-1);
XX#else
XX if (read(bt->fd, (char *) &boge, BT_NSIZ) != BT_NSIZ)
XX return (-1);
XX
XX bt->cache[hash].recno = ntohl(boge.recno);
XX bt->cache[hash].lptr = ntohl(boge.lptr);
XX bt->cache[hash].rptr = ntohl(boge.rptr);
XX bt->cache[hash].deleted = ntohs(boge.deleted);
XX bt->cache[hash].balance = ntohs(boge.balance);
XX (void) strncpy(bt->cache[hash].key, boge.key, BT_KSIZ - 1);
XX#endif
XX }
XX
XX /* loaded OK, now copy the updated cached data to the target */
XX (void)bcopy((char *) &bt->cache[hash],(char *)npt,BT_NSIZ);
XX
XX return (0);
XX}
XX
XX
XX
XXstatic int
XXpushl(bt, nbr)
XXstruct btree *bt;
XXlong nbr;
XX{
XX if (++(bt->lstak.sptr) >= STACK_LENGTH) {
XX bterrno = BT_BAD_STACK;
XX exit(0);
XX }
XX bt->lstak.ele[bt->lstak.sptr] = nbr;
XX bt->lstak.lev[bt->lstak.sptr] = ++bt->slev;
XX return;
XX}
XX
XX
XXstatic int
XXpushr(bt, nbr)
XXstruct btree *bt;
XXlong nbr;
XX{
XX if (++(bt->rstak.sptr) >= STACK_LENGTH) {
XX bterrno = BT_BAD_STACK;
XX exit(0);
XX }
XX bt->rstak.ele[bt->rstak.sptr] = nbr;
XX bt->rstak.lev[bt->rstak.sptr] = ++bt->slev;
XX return;
XX}
XX
XX
XX
XXstatic long
XXpopr(bt)
XXstruct btree *bt;
XX{
XX
XX bt->slev = bt->rstak.lev[bt->rstak.sptr];
XX
XX while (bt->lstak.lev[bt->lstak.sptr] > bt->slev)
XX (bt->lstak.sptr)--;
XX
XX if (bt->rstak.sptr == 0)
XX return (0);
XX
XX bt->slev--;
XX return (bt->rstak.ele[(bt->rstak.sptr)--]);
XX}
XX
XX
XX
XXstatic long
XXpopl(bt)
XXstruct btree *bt;
XX{
XX
XX bt->slev = bt->lstak.lev[bt->lstak.sptr];
XX
XX while (bt->rstak.lev[bt->rstak.sptr] > bt->slev)
XX (bt->rstak.sptr)--;
XX
XX if (bt->lstak.sptr == 0)
XX return (0);
XX
XX bt->slev--;
XX return (bt->lstak.ele[(bt->lstak.sptr)--]);
XX}
XX
XX
XX
XXstatic void
XXbt_link(alpha1, node1, alpha2, node2)
XXint alpha1;
XXint alpha2;
XXstruct btnode *node1;
XXstruct btnode *node2;
XX{
XX if (alpha1 == -1 && alpha2 == -1)
XX node1->lptr = node2->lptr;
XX else if (alpha1 == -1 && alpha2 == 1)
XX node1->lptr = node2->rptr;
XX else if (alpha1 == 1 && alpha2 == -1)
XX node1->rptr = node2->lptr;
XX else
XX node1->rptr = node2->rptr;
XX}
XX
XX
XX
XX/* number a link according to alpha */
XXstatic void
XXnbr_link(nbr, alpha, node1)
XXlong *nbr;
XXint alpha;
XXstruct btnode *node1;
XX{
XX *nbr = (alpha == 1) ? node1->rptr : node1->lptr;
XX}
XX
XX
XX
XX/* set a link according to alpha */
XXstatic void
XXlink_nbr(alpha, node1, nbr)
XXint alpha;
XXstruct btnode *node1;
XXlong nbr;
XX{
XX
XX if (alpha == 1)
XX node1->rptr = nbr;
XX else
XX node1->lptr = nbr;
XX}
XX
XX
XX
XXstatic void
XXnode_bal(alpha, node1, node2, node3)
XXint alpha;
XXstruct btnode *node1;
XXstruct btnode *node2;
XXstruct btnode *node3;
XX{
XX
XX if (node1->balance == alpha) {
XX node2->balance = -alpha;
XX node3->balance = 0;
XX } else if (node1->balance == 0)
XX node2->balance = node3->balance = 0;
XX else {
XX node2->balance = 0;
XX node3->balance = alpha;
XX }
XX}
XX
XX
XX
XX/* change the record number in a node */
XXbtsetrec(nbr, newrec, bt)
XXlong nbr;
XXlong newrec;
XXstruct btree *bt;
XX{
XX struct btnode tmpnode;
XX
XX if(rnode(nbr, &tmpnode, bt) <0)
XX return(-1);
XX
XX tmpnode.recno = newrec;
XX
XX if(wnode(nbr, &tmpnode, bt) <0)
XX return(-1);
XX
XX
XX return(0);
XX}
XX
XX
XX
XX/* insert the node into the tree */
XXbtinsert(argkey, recnbr, bt)
XXchar *argkey;
XXlong recnbr;
XXstruct btree *bt;
XX{
XX long top;
XX long p_rec;
XX long s_rec;
XX long q_rec;
XX long r_rec;
XX struct btnode q_node;
XX struct btnode s_node;
XX struct btnode r_node;
XX struct btnode p_node;
XX int compare;
XX extern char *strncpy();
XX
XX
XX /* the very first node gets inserted specially */
XX if (bt->sblk.root == 0) {
XX bt->sblk.root = 1;
XX p_node.balance = p_node.rptr = p_node.lptr = 0;
XX p_node.deleted = BT_ACTIVE;
XX p_node.recno = recnbr;
XX
XX (void) strncpy(p_node.key, argkey, BT_KSIZ - 1);
XX p_node.key[BT_KSIZ - 1] = '\0';
XX if(wnode(1L, &p_node, bt) < 0)
XX return(-1);
XX
XX bt->sblk.free++;
XX bt->sblk.list++;
XX if(wsuper(bt) <0)
XX return(-1);
XX return (0);
XX }
XX top = -1;
XX p_rec = bt->sblk.root;
XX s_rec = bt->sblk.root;
XX while (1) {
XX if(rnode(p_rec, &p_node, bt) <0)
XX return(-1);
XX if ((compare = strcmp(argkey, p_node.key)) < 0) {
XX
XX /* (move left) */
XX q_rec = p_node.lptr;
XX
XX if (q_rec == 0) {
XX /* insert here */
XX q_rec = bt->sblk.free++;
XX p_node.lptr = q_rec;
XX break; /* loop exit */
XX } else {
XX /* look again from this node */
XX if(rnode(q_rec, &q_node, bt) <0)
XX return(-1);
XX if (q_node.balance != 0) {
XX top = p_rec;
XX s_rec = q_rec;
XX }
XX }
XX p_rec = q_rec;
XX
XX } else {
XX /* (move right) */
XX q_rec = p_node.rptr;
XX
XX if (q_rec == 0) {
XX /* insert here */
XX q_rec = bt->sblk.free++;
XX p_node.rptr = q_rec;
XX break; /* loop exit */
XX } else {
XX /* look again from this node */
XX if(rnode(q_rec, &q_node, bt) <0)
XX return(-1);
XX if (q_node.balance != 0) {
XX top = p_rec;
XX s_rec = q_rec;
XX }
XX p_rec = q_rec;
XX }
XX }
XX }
XX
XX /* Step 5 (insert key at q_node) */
XX q_node.lptr = q_node.rptr = 0;
XX q_node.balance = 0;
XX q_node.deleted = BT_ACTIVE;
XX q_node.recno = recnbr;
XX (void) strncpy(q_node.key, argkey, BT_KSIZ);
XX q_node.key[BT_KSIZ - 1] = '\0';
XX
XX if (wnode(q_rec, &q_node, bt) == -1)
XX return (-1);
XX
XX if(wnode(p_rec, &p_node, bt) <0)
XX return(-1);
XX if(rnode(s_rec, &s_node, bt) <0)
XX return(-1);
XX if(wsuper(bt) <0)
XX return(-1);
XX
XX /* (adjust balance factors) */
XX if (strcmp(argkey, s_node.key) < 0) {
XX r_rec = p_rec = s_node.lptr;
XX } else {
XX r_rec = p_rec = s_node.rptr;
XX }
XX
XX while (p_rec != q_rec) {
XX if(rnode(p_rec, &p_node, bt) <0)
XX return(-1);
XX if (strcmp(argkey, p_node.key) < 0) {
XX p_node.balance = -1;
XX if(wnode(p_rec, &p_node, bt) < 0)
XX return(-1);
XX p_rec = p_node.lptr;
XX } else {
XX p_node.balance = 1;
XX if(wnode(p_rec, &p_node, bt) < 0)
XX return(-1);
XX p_rec = p_node.rptr;
XX }
XX }
XX
XX compare = (strcmp(argkey, s_node.key) < 0) ? -1 : 1;
XX if (s_node.balance == 0) {
XX bt->sblk.list++;
XX s_node.balance = compare;
XX if(wnode(s_rec, &s_node, bt) < 0)
XX return(-1);
XX if(wsuper(bt) <0)
XX return(-1);
XX return (0);
XX } else if (s_node.balance == -compare) {
XX bt->sblk.list++;
XX s_node.balance = 0;
XX if(wnode(s_rec, &s_node, bt) < 0)
XX return(-1);
XX if(wsuper(bt) <0)
XX return(-1);
XX return (0);
XX } else {
XX /* (tree out of balance) */
XX bt->sblk.list++;
XX if(rnode(s_rec, &s_node, bt) <0)
XX return(-1);
XX if(rnode(r_rec, &r_node, bt) <0)
XX return(-1);
XX if (r_node.balance == compare) {
XX /* (single rotate) */
XX p_rec = r_rec;
XX bt_link(compare, &s_node, -compare, &r_node);
XX link_nbr(-compare, &r_node, s_rec);
XX s_node.balance = r_node.balance = 0;
XX } else {
XX /* (double rotate) */
XX nbr_link(&p_rec, -compare, &r_node);
XX if(rnode(p_rec, &p_node, bt) <0)
XX return(-1);
XX bt_link(-compare, &r_node, compare, &p_node);
XX link_nbr(compare, &p_node, r_rec);
XX bt_link(compare, &s_node, -compare, &p_node);
XX link_nbr(-compare, &p_node, s_rec);
XX node_bal(compare, &p_node, &s_node, &r_node);
XX p_node.balance = 0;
XX if(wnode(p_rec, &p_node, bt) <0)
XX return(-1);
XX }
XX
XX if (top == -1) {
XX bt->sblk.root = p_rec;
XX } else {
XX /* balanced at top of a sub-tree */
XX if(rnode(top, &q_node, bt) < 0)
XX return(-1);
XX if (s_rec == q_node.rptr)
XX q_node.rptr = p_rec;
XX else
XX q_node.lptr = p_rec;
XX if(wnode(top, &q_node, bt) <0)
XX return(-1);
XX }
XX if(wnode(s_rec, &s_node, bt) <0)
XX return(-1);
XX if(wnode(r_rec, &r_node, bt) <0)
XX return(-1);
XX if(wsuper(bt) <0)
XX return(-1);
XX return (0);
XX }
XX}
XX
XX
XX
XX/* drop a node */
XXbtdelete(node_nbr, bt)
XXlong node_nbr;
XXstruct btree *bt;
XX{
XX struct btnode cno;
XX
XX if (node_nbr == 0) {
XX bterrno = BT_BAD_ROOT;
XX return (-1);
XX } else {
XX if (rnode(node_nbr, &cno, bt) == -1)
XX return(-1);
XX cno.deleted = BT_DELETED;
XX if (wnode(node_nbr, &cno, bt) == -1) {
XX return (-1);
XX } else {
XX bt->sblk.list--;
XX if(wsuper(bt) <0)
XX return(-1);
XX }
XX }
XX return (0);
XX}
XX
XX
XX
XX/* find the next node */
XXbtnext(node_nbr, cno, bt)
XXlong *node_nbr;
XXstruct btnode *cno;
XXstruct btree *bt;
XX{
XX long popl();
XX long popr();
XX long s_nod;
XX
XX s_nod = *node_nbr;
XX
XX if (*node_nbr == 0) {
XX /* undefined current node - wind to beginning of file */
XX return (bthead(node_nbr,cno,bt));
XX }
XX do {
XX if (cno->rptr == 0) {
XX /* can't move right */
XX if (bt->lstak.sptr == 0) {
XX /* none in stack */
XX if(rnode(*node_nbr, cno, bt) <0)
XX return(-1);
XX return (BT_EOF);
XX } else {
XX /* can't go right & stack full (pop stack) */
XX s_nod = popl(bt);
XX if(rnode(s_nod, cno, bt) < 0)
XX return(-1);
XX }
XX } else {
XX /* move right */
XX pushr(bt, s_nod);
XX s_nod = cno->rptr;
XX if(rnode(s_nod, cno, bt) <0 )
XX return(-1);
XX
XX while (cno->lptr != 0) {
XX /* bottom left */
XX pushl(bt, s_nod);
XX /* of this sub-tree */
XX s_nod = cno->lptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX }
XX }
XX } while (cno->deleted == BT_DELETED);
XX
XX *node_nbr = s_nod;
XX return (0);
XX}
XX
XX
XX
XX/* go to the tail of the file */
XXbttail(node_nbr, cno, bt)
XXstruct btree *bt;
XXlong *node_nbr;
XXstruct btnode *cno;
XX{
XX long s_nod;
XX
XX bt->rstak.sptr = 0;
XX bt->lstak.sptr = 0;
XX bt->rstak.ele[0] = 0;
XX bt->lstak.ele[0] = 0;
XX
XX /* begin at list head */
XX s_nod = bt->sblk.root;
XX
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX while (1) {
XX /* search to right */
XX if (cno->rptr != 0) {
XX pushr(bt, s_nod);
XX s_nod = cno->rptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX } else {
XX if (cno->deleted == BT_DELETED) {
XX /* skip all deleted nodes */
XX while (cno->deleted == BT_DELETED) {
XX if (btnext(&s_nod, cno, bt) == BT_EOF) {
XX if(btprevious(&s_nod, cno, bt)<0)
XX return(-1);
XX *node_nbr = s_nod;
XX return (0);
XX }
XX }
XX *node_nbr = s_nod;
XX return (0);
XX } else {
XX /* at end of a branch */
XX *node_nbr = s_nod;
XX return (0);
XX }
XX }
XX }
XX}
XX
XX
XX/* go to the head of the file */
XXbthead(node_nbr, cno, bt)
XXstruct btree *bt;
XXlong *node_nbr;
XXstruct btnode *cno;
XX{
XX long s_nod;
XX
XX bt->rstak.sptr = 0;
XX bt->lstak.sptr = 0;
XX bt->rstak.ele[0] = 0;
XX bt->lstak.ele[0] = 0;
XX
XX /* begin at list head */
XX s_nod = bt->sblk.root;
XX
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX while (1) {
XX /* search to left */
XX if (cno->lptr != 0) {
XX pushl(bt, s_nod);
XX s_nod = cno->lptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX } else {
XX if (cno->deleted == BT_DELETED) {
XX /* skip all deleted nodes */
XX while (cno->deleted == BT_DELETED) {
XX if (btprevious(&s_nod, cno, bt) == BT_EOF) {
XX if(btnext(&s_nod, cno, bt)<0)
XX return(-1);
XX *node_nbr = s_nod;
XX return (0);
XX }
XX }
XX *node_nbr = s_nod;
XX return (0);
XX } else {
XX /* at end of a branch */
XX *node_nbr = s_nod;
XX return (0);
XX }
XX }
XX }
XX}
XX
XX
XX
XX/* find a key */
XXbtfind(key1, node_nbr, cno, bt)
XXchar *key1;
XXstruct btree *bt;
XXlong *node_nbr;
XXstruct btnode *cno;
XX{
XX int direction;
XX long s_nod;
XX
XX bt->rstak.sptr = 0;
XX bt->lstak.sptr = 0;
XX bt->rstak.ele[0] = 0;
XX bt->lstak.ele[0] = 0;
XX
XX bt->slev = 0; /* tree level at start of search */
XX
XX /* begin at list head */
XX s_nod = bt->sblk.root;
XX
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX while ((direction = strcmp(key1, cno->key)) != 0 ||
XX cno->deleted == BT_DELETED) {
XX
XX if (direction > 0) {
XX /* search to right */
XX if (cno->rptr != 0) {
XX pushr(bt, s_nod);
XX s_nod = cno->rptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX } else if (cno->deleted == BT_DELETED) {
XX /* skip all deleted nodes */
XX while (cno->deleted == BT_DELETED) {
XX if (btnext(&s_nod, cno, bt) == BT_EOF) {
XX if(btprevious(&s_nod, cno, bt)<0)
XX return(-1);
XX *node_nbr = s_nod;
XX return (BT_NREC);
XX }
XX }
XX *node_nbr = s_nod;
XX return (BT_NREC);
XX } else {
XX /* at end of a branch */
XX *node_nbr = s_nod;
XX return (BT_NREC);
XX }
XX } else {
XX /* search to left */
XX if (cno->lptr != 0) {
XX pushl(bt, s_nod);
XX s_nod = cno->lptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX } else if (cno->deleted == BT_DELETED) {
XX while (cno->deleted == BT_DELETED) {
XX if (btnext(&s_nod, cno, bt) == BT_EOF) {
XX if(btprevious(&s_nod, cno, bt)< 0)
XX return(-1);
XX *node_nbr = s_nod;
XX return (BT_NREC);
XX }
XX }
XX *node_nbr = s_nod;
XX return (BT_NREC);
XX } else {
XX *node_nbr = s_nod;
XX return (BT_NREC);
XX }
XX }
XX }
XX *node_nbr = s_nod;
XX return (0);
XX}
XX
XX
XX
XX/* get the previous node */
XXbtprevious(node_nbr, cno, bt)
XXlong *node_nbr;
XXstruct btnode *cno;
XXstruct btree *bt;
XX{
XX long popr();
XX long popl();
XX long s_nod;
XX
XX s_nod = *node_nbr;
XX
XX /* if we are called without a node, wind to the end of file */
XX if (*node_nbr == 0) {
XX return (bttail(node_nbr,cno,bt));
XX }
XX
XX
XX do {
XX if (cno->lptr == 0) {
XX /* can't move left */
XX if (bt->rstak.sptr == 0) {
XX /* none in stack */
XX if(rnode(*node_nbr, cno, bt) <0)
XX return(-1);
XX return (BT_EOF);
XX /* don't reset node_nbr */
XX } else {
XX /* can't go left & stack full (pop stack) */
XX s_nod = popr(bt);
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX }
XX } else {
XX /* left then to bottom right - is previous */
XX pushl(bt, s_nod);
XX s_nod = cno->lptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX while (cno->rptr != 0) {
XX /* bottom right */
XX pushr(bt, s_nod);
XX /* of this sub-tree */
XX s_nod = cno->rptr;
XX if(rnode(s_nod, cno, bt) <0)
XX return(-1);
XX }
XX }
XX } while (cno->deleted == BT_DELETED);
XX
XX *node_nbr = s_nod;
XX return (0);
XX}
XX
XX
XX
XX/* print the btree error message */
XXvoid
XXbtperror(str)
XXchar *str;
XX{
XX extern int errno;
XX
XX /* is it ours ?? */
XX if (errno == 0) {
XX if (str[strlen(str) - 1] != ':')
XX (void) fprintf(stderr, "%s: %s\n", str, bterrs[bterrno]);
XX else
XX (void) fprintf(stderr, "%s %s\n", str, bterrs[bterrno]);
XX bterrno = 0;
XX } else {
XX perror(str);
XX }
XX}
SHAR_EOF
if test 17883 -ne "`wc -c btree.c`"
then
echo shar: error transmitting btree.c '(should have been 17883 characters)'
fi
echo shar: extracting btree.h '(2161 characters)'
sed 's/^XX//' << \SHAR_EOF > btree.h
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX *
XX * $Header: btree.h,v 1.1 88/06/01 21:35:55 mjr Rel $: btree.h
XX *
XX * $Log: btree.h,v $
XX * Revision 1.1 88/06/01 21:35:55 mjr
XX * Initial revision
XX *
XX */
XX
XX#ifndef _INCL_BTREE_H
XX
XX#define BT_NREC 1 /* no such record */
XX#define BT_EOF 2 /* end of the tree (either end) */
XX#define BT_ERR -1 /* something went wrong */
XX
XX#define BT_KSIZ 40 /* size of keys to store (or trunc) */
XX#define BT_CSIZ 30 /* # of nodes to cache readonly */
XX /* current cache alg gives ~59% hits */
XX
XX/* this indicates a node deleted */
XX#define BT_DELETED 1
XX#define BT_ACTIVE 0
XX
XX#define BT_MAGIC 0x72251
XX
XX/* btree stack */
XX#define STACK_LENGTH 30 /* length of history stacks */
XX
XXstruct btstack {
XX long ele[STACK_LENGTH]; /* stack elements */
XX int lev[STACK_LENGTH]; /* stack levels */
XX int sptr; /* stack pointer */
XX};
XX
XX/* a disk resident btree super block */
XXstruct btsuper {
XX long magic; /* generic magic number */
XX long free; /* pointer to next free (basically, EOF) */
XX long root; /* pointer to root node */
XX long list; /* number of active records */
XX};
XX
XXstruct btnode {
XX long recno; /* index to external file, or whatever */
XX long lptr; /* left-pointer */
XX long rptr; /* right-pointer */
XX char key[BT_KSIZ]; /* datum */
XX short deleted; /* deleted flag */
XX short balance; /* balance flag */
XX};
XX#define BTNODE struct btnode
XX
XX/* a memory resident btree super block */
XX/* including room to hold a disk super block */
XXstruct btree {
XX int fd; /* file descriptor */
XX int slev; /* history stack level */
XX struct btsuper sblk; /* copy of superblock */
XX struct btstack rstak; /* history stack */
XX struct btstack lstak; /* history stack */
XX struct btnode cache[BT_CSIZ]; /* read-only cache */
XX};
XX#define BTREE struct btree
XX
XXBTREE *btopen();
XXvoid btperror();
XX
XXextern int bterrno; /* btree error number/flag */
XXextern char *bterrs[]; /* error message list */
XX/* error codes - match bterrs */
XX#define BT_BAD_MAGIC 1 /* bad index file magic number */
XX#define BT_BAD_STACK 2 /* history stack overflow */
XX#define BT_BAD_ROOT 3 /* failed attempt to delete node 0 */
XX
XX#define _INCL_BTREE_H
XX#endif
SHAR_EOF
if test 2161 -ne "`wc -c btree.h`"
then
echo shar: error transmitting btree.h '(should have been 2161 characters)'
fi
echo shar: extracting btree.3 '(7582 characters)'
sed 's/^XX//' << \SHAR_EOF > btree.3
XX.\" btree.3l (C)1988 Marcus J. Ranum, Welch Medical Library
XX.\" $Header: btree.3,v 1.1 88/06/01 21:36:01 mjr Rel $
XX.TH BTREE 3l
XX.SH NAME
XXbtopen, btclose, btfind, btinsert, btdelete, bthead, bttail,
XXbtnext, btprevious, btsetrec, btperror
XX.br
XX\- the poor man's b-tree index library
XX.SH SYNTAX
XX.B #include <local/btree.h>
XX.PP
XX.B BTREE *btopen(path,flags,mode)
XX.br
XX.SM
XX.B char *path;
XX.br
XX.B int flags, mode;
XX.PP
XX.B int btclose(btree)
XX.br
XX.SM
XX.B BTREE *btree;
XX.PP
XX.B int btfind(key,node_num,nodebuf,btree)
XX.br
XX.SM
XX.B char *key;
XX.br
XX.B long *node_num;
XX.br
XX.B BTNODE *nodebuf;
XX.br
XX.B BTREE btree;
XX.PP
XX.B int btinsert(key,recno,btree)
XX.br
XX.SM
XX.B char *key;
XX.br
XX.B long recno;
XX.br
XX.B BTREE btree;
XX.PP
XX.B int btdelete(number,btree)
XX.br
XX.SM
XX.B long number;
XX.br
XX.B BTREE btree;
XX.PP
XX.B int bthead(node_num,nodebuf,btree)
XX.br
XX.SM
XX.B long *node_num;
XX.br
XX.B BTNODE *nodebuf;
XX.br
XX.B BTREE *btree;
XX.PP
XX.B int bttail(node_num,nodebuf,btree)
XX.br
XX.SM
XX.B long *node_num;
XX.br
XX.B BTNODE *nodebuf;
XX.br
XX.B BTREE *btree;
XX.PP
XX.B int btnext(node_num,nodebuf,btree)
XX.br
XX.SM
XX.B long *node_num;
XX.br
XX.B BTNODE *nodebuf;
XX.br
XX.B BTREE *btree;
XX.PP
XX.B int btprevious(node_num,nodebuf,btree)
XX.br
XX.SM
XX.B long *node_num;
XX.br
XX.B BTNODE *nodebuf;
XX.br
XX.B BTREE *btree;
XX.PP
XX.B int btsetrec(number,newrec,btree)
XX.br
XX.SM
XX.B long number, newrec;
XX.br
XX.B BTREE *btree;
XX.PP
XX.B void btperror(message)
XX.br
XX.SM
XX.B char *message;
XX.SH DESCRIPTION
XX.PP
XXThe poor man's btree library is a set of routines to manage a balanced
XXbtree index file. No provisions are made for storing any data other
XXthan the key in the btree nodes, except for a single long int that
XXcan be used as a pointer to storage elsewhere. No provisions are made
XXfor multi-user access. Currently, deleted keys are not handled
XXelegantly. They are marked as deleted, but are not re-used, which will
XXcause an index file to grow constantly, which can waste
XXdisk space if the data is frequently modified. A read cache is
XXmaintained, but write requests are not cached. Multiple entries for
XXthe same key are permitted, so it is the user's responsibility to specify
XXthe node number to delete. Keys are fixed-length, defined
XXin
XX.B btree.h
XXand overlong keys are silently truncated during inserts.
XXAll functions return -1 on error, 0 for success, but occasionally
XXother codes defined in
XX.B btree.h
XXfor special conditions (no record found, end of tree, etc).
XX.PP
XXThe
XX.B btopen
XXsubroutine allocates a btree control structure, using the path name
XXprovided in
XX.B path.
XXThe
XX.B flags
XXand
XX.B mode
XXarguments are passed to open(2) to control creation and permissions.
XXIf the data file is successfully opened with 0 size (either through
XXopen(2) flags O_TRUNC or O_CREAT on a nonexistent file) a new btree
XXis initialized automatically.
XX.B Btopen
XXchecks a magic number stored in the index superblock, and will fail
XXunless the magic number is correct, to prevent accidentally using a
XXdamaged file, or a non-index file. If
XX.B btopen
XXcannot open the requested file, or encounters other problems,
XXit returns NULL.
XX.PP
XXThe
XX.B btclose
XXsubroutine closes an opened btree, and deallocates the memory that
XXwas allocated in btopen.
XX.PP
XXThe
XX.B btfind
XXsubroutine searches for a key within the index. The argument
XX.B key
XXis
XXsearched for, and the results of the search are placed in
XX.B nodebuf.
XXThe number of the "found" node is placed in
XX.B node_num.
XX.B Btree
XXis expected to be an open, valid, btree index.
XX.B Btfind
XXreturns 0 if the requested key is located, -1 for error, or BT_NREC if
XXthe requested key was not found. If the requested key is not found,
XXthe contents of
XX.B nodebuf
XXand
XX.b node_num
XXwill be loaded with the node that held the place in the tree directly
XXbefore where the requested node would have been. This gives
XX.B btfind
XXa limited ability for finding the nearest "like" node (though it is a
XXtoss-up whether the preceding node is "closer" than the
XXfollowing one).
XX.PP
XXThe
XX.B btinsert
XXsubroutine creates a new node for the given
XX.B key
XXand numbers it with the requested
XX.B recno,
XXwhich can be used to link the index to additional data elsewhere.
XXIf
XX.B btinsert
XXfails, it returns -1, otherwise it returns 0.
XX.PP
XXThe
XX.B btdelete
XXsubroutine marks node number
XX.B number
XXas deleted, which causes it to become "invisible" during future searches.
XXThe disk space is not reclaimed.
XX.B Btdelete
XXreturns 0 on success, -1 on failure. Since the node to delete is
XXreferenced only by node number,
XX.B btdelete
XXis typically used with something like
XX.B btfind
XXthat provides the node number.
XX.PP
XXThe
XX.B bthead
XXsubroutine searches to the first entry in the btree, returning the entry's
XXnode number in
XX.B node_num
XXand its data in
XX.B nodebuf.
XX.B Bthead
XXreturns 0 on success, -1 on failure.
XX.PP
XXThe
XX.B bttail
XXsubroutine searches to the last entry in the btree, but is otherwise
XXexactly the same as
XX.B bthead.
XX.PP
XXThe
XX.B btnext
XXsubroutine finds the next node in the tree after
XX.B node_nbr
XXand places its data in
XX.B nodebuf.
XX.B Btnext
XXreturns 0 on success, -1 on failure, ande
XX.B BT_EOF
XXif it cannot search any further because it has hit the end of the tree.
XXNote that
XX.B BT_EOF
XXis a positive value, so tests like:
XX.sp
XX.ti 1i
XXwhile(btnext(&node_nbr,&nodebuf,bt) >= 0);
XX.sp
XXwill loop forever. Something like:
XX.sp
XX.ti 1i
XXwhile(btnext(&node_nbr,&nodebuf,bt) == 0);
XX.sp
XXshould be used instead. If
XX.B node_nbr
XXis 0L (undefined)
XX.B btnext
XXwill automatically search to the beginning of the index file, rather
XXthan starting at a random location.
XX.PP
XXThe
XX.B btprevious
XXsubroutine finds the next node in the tree before
XX.B node_nbr
XXbut is otherwise exactly the same as
XX.B bthead. If invoked with
XX.B node_nbr
XX0,
XX.B btprevious
XXautomatically searches to to the end of the index file.
XX.PP
XXThe
XX.B btsetrec
XXsubroutine allows the user to modify node number
XX.B node_nbr
XXrecord number, for whatever reason. Typically
XX.B recno
XXis used for linking the index to additional data elsewhere.
XX.PP
XXThe
XX.B btperror
XXsubroutine will print any applicable btree error messages, similarly to
XX.B perror.
XXIf the btree error number
XX.B bterrno
XXis 0, and the UNIX
XX.B errno
XXis set, perror is called instead, to print the UNIX error. The btree
XXerror messages are accessible to the user, as an array of strings
XX.B bterrs.
XXA call to
XX.B btperror
XXresets
XX.B bterrno
XXautomatically.
XX.SH EXAMPLES
XX.PP
XXThe following routine inputs strings into an index:
XX.nf
XX.na
XX.ft C
XX#include <local/btree.h>
XX
XXmain(ac,av)
XXint ac;
XXchar *av[];
XX{
XX BTREE *bt;
XX char buf[BUFSIZ];
XX long recno =0L;
XX
XX if((bt = btopen(av[1],O_CREAT,0600)) ==NULL) {
XX btperror(av[1]);
XX exit(1);
XX }
XX
XX while(gets(buf)) {
XX if(btinsert(buf,++recno,bt)< 0) {
XX btperror("insert");
XX (void)btclose(bt);
XX exit(1);
XX }
XX }
XX exit(btclose(bt));
XX}
XX.ft P
XX.sp
XX.PP
XXThe following example dumps an index:
XX.ft C
XX#include <local/btree.h>
XX
XXmain(ac,av)
XXint ac;
XXchar *av[];
XX{
XX
XX BTREE *bt;
XX BTNODE cnode;
XX long nbr =0L;
XX
XX if((bt = btopen(av[1],O_RDWR,0600)) == NULL) {
XX btperror(av[1]);
XX exit(1);
XX }
XX
XX while((btnext(&nbr, &cnode, bt) == 0) {
XX (void)printf("%s\\n",cnode.key);
XX }
XX exit(btclose(bt));
XX}
XX.ft P
XX.ad
XX.SH RESTRICTIONS
XX.PP
XXFiles can get large unless copied out occasionally.
XX.PP
XXIt is not permitted to delete node number 0.
XX.PP
XX.SH DIAGNOSTICS
XXThese functions return -1 on error, 0 on success, and occasionally other
XXvalues that can signal end of file or failure to find a record.
XX.SH AUTHOR
XX.PP
XXThe original code was from a PD library for IBM PCs written by Ray Swartz.
XX90% of the code was totally re-written and restructured to make it into
XXa usable library.
XX.PP
XXMarcus J. Ranum, Welch Medical Library.
XX.br
XX.ti 1i
XXuunet!aplcen!osiris!welchvax!mjr
XX.br
XX.ti 1i
XXmjr@jhuigf.BITNET
XX.SH SEE ALSO
SHAR_EOF
if test 7582 -ne "`wc -c btree.3`"
then
echo shar: error transmitting btree.3 '(should have been 7582 characters)'
fi
echo shar: extracting bench.c '(2003 characters)'
sed 's/^XX//' << \SHAR_EOF > bench.c
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX */
XX
XX#ifndef lint
XXstatic char *RCSid="$Header: bench.c,v 1.1 88/06/01 21:34:55 mjr Rel $: bench.c";
XX#endif
XX
XX/*
XX * $Log: bench.c,v $
XX * Revision 1.1 88/06/01 21:34:55 mjr
XX * Initial revision
XX *
XX */
XX
XX
XX/* grosso hack to load a database and perform a bunch of */
XX/* operations on it - a sort of benchmark, but not in any */
XX/* real sense of the word */
XX
XX#ifdef BSD
XX#include <sys/file.h>
XX#endif
XX#ifdef SYSV
XX#include <sys/fcntl.h>
XX#endif
XX#include <stdio.h>
XX#include "btree.h"
XX
XXmain(ac,av)
XXint ac;
XXchar *av[];
XX{
XX BTREE *bt;
XX BTNODE cnod;
XX int fo;
XX int xo;
XX long nbr;
XX long time();
XX long random();
XX long start;
XX long end;
XX char buf[120];
XX
XX if(ac < 2) {
XX (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
XX exit(1);
XX }
XX
XX (void)srandom(getpid());
XX if((bt = btopen(av[1],O_CREAT|O_TRUNC,0600)) == NULL) {
XX btperror(av[1]);
XX exit(1);
XX }
XX
XX (void)time(&start);
XX
XX (void)fprintf(stderr,"insert 5000\n");
XX /* insert 5000 random records */
XX for(fo = 0; fo < 5000; fo++) {
XX for(xo = 0; xo < ((int)random()%15)+1; xo++)
XX buf[xo] = (int)((random()%25)+97);
XX buf[xo] = '\0';
XX if(btinsert(buf, bt->sblk.free, bt)<0) {
XX btperror("insert");
XX exit(1);
XX }
XX }
XX
XX (void)fprintf(stderr,"find 5000\n");
XX /* find 5000 random records */
XX for(fo = 0; fo < 5000; fo++) {
XX for(xo = 0; xo < ((int)random()%15)+1; xo++)
XX buf[xo] = (int)((random()%25)+97);
XX buf[xo] = '\0';
XX if(btfind(buf, &nbr, &cnod, bt)<0) {
XX btperror("find");
XX exit(1);
XX }
XX }
XX
XX (void)fprintf(stderr,"delete 500\n");
XX for(fo = 0; fo < 500; fo++) {
XX for(xo = 0; xo < ((int)random()%15)+1; xo++)
XX buf[xo] = (int)(random()%25)+97;
XX buf[xo] = '\0';
XX if(btfind(buf, &nbr, &cnod, bt)<0) {
XX btperror("find");
XX exit(1);
XX }
XX if(nbr != 0L && btdelete(nbr, bt)<0) {
XX btperror("delete");
XX (void)fprintf(stderr,"node=%d\n",nbr);
XX exit(1);
XX }
XX }
XX
XX (void)btclose(bt);
XX (void)time(&end);
XX (void)fprintf(stderr,"total secs:%ld\n",end-start);
XX exit(0);
XX}
SHAR_EOF
if test 2003 -ne "`wc -c bench.c`"
then
echo shar: error transmitting bench.c '(should have been 2003 characters)'
fi
echo shar: extracting loadtree.c '(1264 characters)'
sed 's/^XX//' << \SHAR_EOF > loadtree.c
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX */
XX
XX#ifndef lint
XXstatic char *RCSid="$Header: loadtree.c,v 1.1 88/06/01 21:35:24 mjr Rel $: loadtree.c";
XX#endif
XX
XX/*
XX * $Log: loadtree.c,v $
XX * Revision 1.1 88/06/01 21:35:24 mjr
XX * Initial revision
XX *
XX */
XX
XX
XX/* used to load a tree with data from the standard input - */
XX/* primarily for testing purposes - to load a file with some */
XX/* "known" data, which can then be dumped and checked, etc */
XX
XX#ifdef BSD
XX#include <sys/file.h>
XX#endif
XX#ifdef SYSV
XX#include <sys/fcntl.h>
XX#endif
XX#include <stdio.h>
XX#include "btree.h"
XX
XXmain(ac,av)
XXint ac;
XXchar *av[];
XX{
XX BTREE *bt;
XX long time();
XX long start;
XX long end;
XX long lded = 0L;
XX char buf[BUFSIZ];
XX
XX if(ac < 2) {
XX (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
XX exit(1);
XX }
XX
XX (void)srandom(getpid());
XX
XX if((bt = btopen(av[1],O_CREAT,0600)) ==NULL) {
XX btperror(av[1]);
XX exit(1);
XX }
XX
XX (void)time(&start);
XX
XX while(gets(buf)) {
XX /* note - btinsert() truncates overlong keys */
XX if(btinsert(buf, bt->sblk.free, bt)< 0) {
XX btperror("insert");
XX (void)btclose(bt);
XX exit(1);
XX } else
XX lded++;
XX }
XX (void)btclose(bt);
XX (void)time(&end);
XX (void)fprintf(stderr,"total secs:%ld - %ld records\n",end-start,lded);
XX exit(0);
XX}
SHAR_EOF
if test 1264 -ne "`wc -c loadtree.c`"
then
echo shar: error transmitting loadtree.c '(should have been 1264 characters)'
fi
echo shar: extracting treedump.c '(1064 characters)'
sed 's/^XX//' << \SHAR_EOF > treedump.c
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX */
XX
XX#ifndef lint
XXstatic char *RCSid="$Header: treedump.c,v 1.1 88/06/01 21:35:46 mjr Rel $: treedump.c";
XX#endif
XX
XX/*
XX * $Log: treedump.c,v $
XX * Revision 1.1 88/06/01 21:35:46 mjr
XX * Initial revision
XX *
XX */
XX
XX
XX/* dump a tree to the standard output */
XX
XX#ifdef BSD
XX#include <sys/file.h>
XX#endif
XX#ifdef SYSV
XX#include <sys/fcntl.h>
XX#endif
XX#include <stdio.h>
XX#include "btree.h"
XX
XXmain(ac,av)
XXint ac;
XXchar *av[];
XX{
XX
XX BTREE *bt;
XX BTNODE cnode;
XX long nbr =0L;
XX
XX if(ac < 2) {
XX (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
XX exit(1);
XX }
XX
XX if((bt = btopen(av[1],O_RDWR,0600)) == NULL) {
XX btperror(av[1]);
XX exit(1);
XX }
XX
XX /* if btnext is called with nbr = 0, it automatically winds to the */
XX /* front of the file - as in this example */
XX while (1) {
XX switch (btnext(&nbr, &cnode, bt)) {
XX case (-1):
XX btperror("btnext");
XX (void)btclose(bt);
XX exit(1);
XX
XX case (0):
XX (void)printf("%s\n",cnode.key);
XX break;
XX
XX case (BT_EOF):
XX (void)btclose(bt);
XX exit(0);
XX }
XX }
XX}
SHAR_EOF
if test 1064 -ne "`wc -c treedump.c`"
then
echo shar: error transmitting treedump.c '(should have been 1064 characters)'
fi
echo shar: extracting sizes.c '(592 characters)'
sed 's/^XX//' << \SHAR_EOF > sizes.c
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX */
XX
XX#ifndef lint
XXstatic char *RCSid="$Header: sizes.c,v 1.1 88/06/01 21:35:34 mjr Rel $: sizes.c";
XX#endif
XX
XX/*
XX * $Log: sizes.c,v $
XX * Revision 1.1 88/06/01 21:35:34 mjr
XX * Initial revision
XX *
XX */
XX
XX
XX/* provides some minimally useful info about how big your */
XX/* data structures are */
XX
XX#include "btree.h"
XX
XXmain()
XX{
XX (void)printf("a btree control structure is %d bytes",sizeof(BTREE));
XX (void)printf(" (cache of %d nodes)\n",BT_CSIZ);
XX (void)printf("a btree node is %d bytes\n",sizeof(BTNODE));
XX}
SHAR_EOF
if test 592 -ne "`wc -c sizes.c`"
then
echo shar: error transmitting sizes.c '(should have been 592 characters)'
fi
echo shar: extracting example.c '(3261 characters)'
sed 's/^XX//' << \SHAR_EOF > example.c
XX/*
XX * Copyright (C) 1988, Marcus J. Ranum, William Welch Medical Library
XX * $Author: mjr $
XX */
XX
XX#ifndef lint
XXstatic char *RCSid="$Header: example.c,v 1.1 88/06/01 21:35:15 mjr Rel $: example.c";
XX#endif
XX
XX/*
XX * $Log: example.c,v $
XX * Revision 1.1 88/06/01 21:35:15 mjr
XX * Initial revision
XX *
XX */
XX
XX
XX/* nobody ever writes nice test programs. in fact, this one is pretty gross */
XX/* basically, this allows exercising all the various functions of the btree */
XX/* library */
XX
XX#ifdef BSD
XX#include <sys/file.h>
XX#endif
XX#ifdef SYSV
XX#include <sys/fcntl.h>
XX#endif
XX#include <stdio.h>
XX#include "btree.h"
XX
XXextern char *strncpy();
XXextern char *strcpy();
XX
XXmain(ac,av)
XXint ac;
XXchar *av[];
XX{
XX BTREE *h1;
XX BTNODE cnode;
XX char instr[BUFSIZ];
XX long node_nbr;
XX
XX if(ac < 2) {
XX (void)fprintf(stderr,"usage: %s <file>\n",av[0]);
XX exit(1);
XX }
XX
XX if((h1 = btopen(av[1],O_CREAT|O_RDWR,0600)) ==NULL) {
XX btperror(av[1]);
XX exit(1);
XX }
XX
XX
XX while (1) {
XX (void)printf("Find Next Tail Head Prev Insrt Del Quit:");
XX if(gets(instr) == NULL)
XX exit(btclose(h1));
XX
XX switch (*instr) {
XX
XX case 'f':
XX case 'F':
XX (void)printf("\nKey to Find: ");
XX (void)gets(instr);
XX (void)strncpy(instr, instr, BT_KSIZ - 1);
XX instr[BT_KSIZ - 1] = '\0';
XX switch(btfind(instr, &node_nbr, &cnode, h1)) {
XX case BT_NREC:
XX (void)printf("not found: closest before=%s\n",cnode.key);
XX break;
XX case -1:
XX btperror("find");
XX break;
XX default:
XX (void)printf("current=%s\n", cnode.key);
XX break;
XX }
XX break;
XX
XX case 'h':
XX case 'H':
XX switch(bthead(&node_nbr, &cnode, h1)) {
XX case (-1):
XX btperror("bthead() returns -1");
XX continue;
XX break;
XX default:
XX (void)printf("current=%s\n", cnode.key);
XX }
XX break;
XX
XX case 't':
XX case 'T':
XX switch(bttail(&node_nbr, &cnode, h1)) {
XX case (-1):
XX btperror("bttail() returns -1");
XX continue;
XX break;
XX default:
XX (void)printf("current=%s\n", cnode.key);
XX }
XX break;
XX
XX case 'd':
XX case 'D':
XX if(btdelete(node_nbr, h1) < 0) {
XX btperror("delete failed");
XX } else {
XX (void)printf("...deleted\n");
XX }
XX break;
XX
XX case 'n':
XX case 'N':
XX switch (btnext(&node_nbr, &cnode, h1)) {
XX case (-1):
XX btperror("btnext() returns -1");
XX continue;
XX break;
XX
XX case (0):
XX (void)printf("current=%s\n", cnode.key);
XX break;
XX
XX case (BT_EOF):
XX (void)printf("end of file: current=%s\n",cnode.key);
XX break;
XX }
XX break;
XX
XX case 'p':
XX case 'P':
XX switch (btprevious(&node_nbr, &cnode, h1)) {
XX case (-1):
XX btperror("btprevious() returns -1");
XX continue;
XX break;
XX case (0):
XX (void)printf("current=%s\n", cnode.key);
XX break;
XX case (BT_EOF):
XX (void)printf("start of file: current=%s\n",cnode.key);
XX }
XX break;
XX
XX case 'i':
XX case 'I':
XX (void)printf("Enter a key: ");
XX (void)gets(instr);
XX (void)strncpy(cnode.key, instr, BT_KSIZ);
XX cnode.key[BT_KSIZ - 1] = '\0';
XX
XX /* h1->sblk.free is used here as arbitrary record # */
XX /* typical use would be to set this to the recno */
XX /* for whatever it is that is being indexed into */
XX if(btinsert(cnode.key, h1->sblk.free, h1) < 0)
XX btperror("insert failed");
XX else
XX (void)printf("...inserted\n");
XX break;
XX
XX case 'q':
XX case 'Q':
XX exit(btclose(h1));
XX
XX default:
XX (void)printf("huh?\n");
XX }
XX }
XX}
SHAR_EOF
if test 3261 -ne "`wc -c example.c`"
then
echo shar: error transmitting example.c '(should have been 3261 characters)'
fi
# End of shell archive
exit 0