Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume10/b+tree_mjr/part04

Text File | 1990-01-19 | 48KB | 1,946 lines

Newsgroups: comp.sources.misc
subject: v10i030: B+tree library, part04 of 5
from: [e-mail] (Marcus J. Ranum)
Sender: [e-mail] (Brandon S. Allbery - comp.sources.misc)

Posting-number: Volume 10, Issue 30
Submitted-by: [e-mail] (Marcus J. Ranum)
Archive-name: b+tree_mjr/part04

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 4 (of 5)."
# Contents:  b+tree/btlib/btpage2.c b+tree/doc/store.3
#   b+tree/utils/rectest.c b+tree/utils/testrack.c
# Wrapped by mjr@atreus on Fri Jan 19 10:34:59 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'b+tree/btlib/btpage2.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btlib/btpage2.c'\"
else
echo shar: Extracting \"'b+tree/btlib/btpage2.c'\" \(9448 characters\)
sed "s/^X//" >'b+tree/btlib/btpage2.c' <<'END_OF_FILE'
X#include    <sys/types.h>
X#include    "btconf.h"
X#include    "btree.h"
X#include    "btintern.h"
X
X/*
X         (C) Copyright, 1988, 1989 Marcus J. Ranum
X                    All rights reserved
X
X
X          This software, its documentation,  and  supporting
X          files  are  copyrighted  material  and may only be
X          distributed in accordance with the terms listed in
X          the COPYRIGHT document.
X*/
X
X
X#ifndef    lint
Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/btlib/RCS/btpage2.c,v 1.1 89/10/24 10:09:05 mjr Rel $";
X#endif
X
X
Xbt_delpg(at,in,out)
Xint    at;
Xbt_chrp    in;
Xbt_chrp    out;
X{
X    int    iky;            /* key iterator */
X    REGISTER bt_chrp    icp;    /* old key pointer */
X    REGISTER bt_chrp    ocp;    /* new key pointer */
X    REGISTER int    *iin;        /* old index/length pointer */
X    REGISTER int    *iout;        /* new index/length pointer */
X    REGISTER off_t    *lin;        /* old child ptr */
X    REGISTER off_t    *lout;        /* new child ptr */
X    REGISTER int    t;        /* iterator */
X    int    dropd = 0;        /* flag AND count of dropped bytes */
X    int    shif = 0;        /* length index shift after drop */
X
X    /* delete a key from a page. very similar to insert in page */
X    /* except we do it in 2 steps, like a split because we are not */
X    /* sure how long the key being dropped is until we get there. */
X    /* since we don't know how long it is, we can't set up the */
X    /* index and child ptrs, and have to do that in a second pass */
X
X    /* fix key count in new page */
X    KEYCNT(out) = KEYCNT(in) - 1;
X
X    /* fix left and right sibs */
X    LSIB(out) = LSIB(in);
X    RSIB(out) = RSIB(in);
X
X    /* fix high pointer (may change later) */
X    HIPT(out) = HIPT(in);
X
X    /* init various pointers */
X    ocp = KEYADR(out);
X    icp = KEYADR(in);
X    iin = (int *)KEYIND(in);
X
X    /* start copy/drop of keys */
X    for(iky = 0; iky < KEYCNT(in); iky++) {
X        if(at == iky) {
X            if(iky == 0)
X                for(t = 0; t < *iin; t++)
X                    icp++;
X            else
X                for(t = 0; t < (*iin - *(iin - 1)); t++)
X                    icp++;
X            dropd = t;
X        } else {
X            if(iky == 0)
X                for(t = 0; t < *iin; t++)
X                    *ocp++ = *icp++;
X            else
X                for(t = 0; t < (*iin - *(iin - 1)); t++)
X                    *ocp++ = *icp++;
X        }
X        iin++;
X    }
X
X    /* fix key count length new page */
X    if(at == KEYCNT(in) && HIPT(in) != BT_NULL) {
X        /* if we are dropping last key from an index page, */
X        /* drop the last key (effectively) by decrementing */
X        /* the length. kind of a kludgey way to do it... */
X        KEYLEN(out) = KEYLEN(in) - t;
X    } else {
X        /* key length of the new page is length of old minus */
X        /* the length of the key that we already dropped */
X        KEYLEN(out) = KEYLEN(in) - dropd;
X    }
X
X    /* reset pointers in prep for ptr/index copy/drop */
X    iin = (int *)KEYIND(in);
X    iout = (int *)KEYIND(out);
X    lin = (off_t *)KEYCLD(in);
X    lout = (off_t *)KEYCLD(out);
X
X    /* start copy/drop of ptrs */
X    for(iky = 0; iky < KEYCNT(in); iky++) {
X        if(at == iky) {
X            shif = dropd;
X        } else {
X            if(iky == KEYCNT(in) - 1 && HIPT(in) != BT_NULL && at == KEYCNT(in)) {
X                HIPT(out) = *lin;
X            } else {
X                *iout++ = *iin - shif;
X                *lout++ = *lin;
X            }
X        }
X        iin++;
X        lin++;
X    }
X}
X
X
Xbt_keyof(n,p,dbuf,dlen,dptr,max)
Xint    n;
Xbt_chrp    p;
Xbt_chrp    dbuf;
Xint    *dlen;
Xoff_t    *dptr;
Xint    max;
X{
X
X    /* clip the numbered key out of the page and return it in */
X    /* kbuf. the key length and rrv are also returned as well */
X    int    *ip;
X    bt_chrp    cp;
X
X    if(KEYCNT(p) == 0) {
X        *dlen = 0;
X        *dptr = BT_NULL;
X        return(BT_OK);
X    }
X
X    cp = KEYADR(p);
X    ip = (int *)KEYIND(p);
X
X    if(n == 0) {
X        *dlen = *ip;
X    } else {
X        *dlen = *(ip + n) - *(ip + (n - 1));
X        cp += *(ip + (n - 1));
X    }
X
X    if(*dlen > max)
X        return(BT_ERR);
X
X    *dptr = *((off_t *)KEYCLD(p) + n);
X#ifdef    USE_BCOPY
X    (void)bcopy((char *)cp,(char *)dbuf,*dlen);
X#endif
X#ifdef    USE_MEMCPY
X    (void)memcpy((char *)cp,(char *)dbuf,*dlen);
X#endif
X#ifdef    USE_MOVEMEM
X    (void)movemem((char *)cp,(char *)dbuf,*dlen);
X#endif
X    return(BT_OK);
X}
X
Xvoid
Xbt_splpg(key,len,ptr,at,siz,old,lo,hi,new,nlen)
Xbt_chrp    key;
Xint    len;
Xoff_t    *ptr;
Xint    at;
Xint    siz;
Xbt_chrp    old;
Xbt_chrp    lo;
Xbt_chrp    hi;
Xbt_chrp    new;
Xint    *nlen;
X{
X    int    oky;            /* key iterator */
X    int    iky;            /* key iterator */
X    int    byt = 0;        /* key byte cnt for low page */
X    REGISTER bt_chrp    icp;    /* old key pointer */
X    REGISTER bt_chrp    ocp;    /* new key pointer */
X    REGISTER int    *iin;        /* old index/length pointer */
X    REGISTER int    *iout;        /* new index/length pointer */
X    REGISTER off_t    *lin;        /* old child ptr */
X    REGISTER off_t    *lout;        /* new child ptr */
X    REGISTER int    t;        /* iterator */
X    char    copied = 0;        /* flag */
X    int    shif = 0;        /* length index shift after insert */
X    int    dropbyt = 0;        /* bytes dropped in index split */
X    int    splitat;        /* key # where we did the split */
X
X    /* this is somewhat different from a simple page insert, since */
X    /* we don't yet know HOW long each key block will be, and as a */
X    /* result we can't copy the pointers until the keys have been */
X    /* done. first we copy the keys, fix up the length and count */
X    /* values, which allows us to correctly get the addresses of */
X    /* the various pointer offsets, and then we copy the keys/ptrs */
X    /* there are, as you would expect, tons of special cases and */
X    /* so on, in this function. The MAIN special cases are: the */
X    /* last key in the low page is the one that needs to be sent */
X    /* up to the calling function for insertion in the parent page */
X    /* after the split. This is done with a little kludgery stuck */
X    /* in the logic where we switch pages during the key copy. The */
X    /* second special case is when we are splitting an index page, */
X    /* the low child ptr has to become "meaningful" so what needs */
X    /* to happen is that the lowest key in the high page needs to */
X    /* get dropped onto the floor, rather than copied. *THEN* the */
X    /* pointers need to be adjusted during the pointer copy. Ick ! */
X
X    /* set pointers to keys prior to copy. low key first. */
X    icp = KEYADR(old);
X    ocp = KEYADR(lo);
X
X
X    /* set the child ptr pointer here - it is used to tell */
X    /* if this is an index page when we do the key copy */
X    lin = (off_t *)KEYCLD(old);
X
X    /* warning! used as a temp var to tell if we have switched pages. */
X    KEYLEN(lo) = 0;
X
X    /* set pointer to old index - output indices are unknown still */
X    iin = (int *)KEYIND(old);
X
X    /* copy one more key than was in the old page */
X    for(iky = oky = 0; oky < KEYCNT(old) + 1; oky++) {
X
X        /* if we are at insertion point, insert key here */
X        if(at == iky && copied == 0) {
X            for(t = 0; t < len; t++)
X                *ocp++ = *key++;
X            byt += len;
X            copied++;
X        } else {
X            /* the usual nonsense with key #0 length */
X            if(iky == 0) {
X                for(t = 0; t < *iin; t++)
X                    *ocp++ = *icp++;
X                byt += *iin;
X            } else {
X                for(t = 0; t < *iin - *(iin - 1); t++)
X                    *ocp++ = *icp++;
X                byt += *iin - *(iin - 1);
X            }
X            iky++;
X            iin++;
X        }
X
X        /* when the first page is full, start on the second */
X        if(KEYLEN(lo) == 0 && (PTRUSE + byt + (oky * (sizeof(int) + sizeof(off_t)))) > siz) {
X
X            /* set length and count for low page */
X            KEYLEN(lo) = byt;
X            KEYCNT(lo) = oky + 1;
X
X            /* remember the # of the key where we split */
X            splitat = oky;
X
X            /* set high pointer for low page */
X            /* if this is an interior page, drop the */
X            /* last key and turn the last ptr into */
X            /* the high pointer (done below) */
X            if(HIPT(old) != BT_NULL) {
X                KEYCNT(lo) = oky;
X
X                /* keep track of how many bytes we just */
X                /* lost so we can fix key lengths later */
X                dropbyt = t;
X
X                /* adjust length of low key */
X                KEYLEN(lo) = byt - dropbyt;
X            }
X
X            /* return the dropped or otherwise high key */
X            /* in new, and set nlen, if applicable */
X             if(new != (bt_chrp)0) {
X                bt_chrp    tmpp;
X
X                 *nlen = t;
X                 tmpp = new + (t - 1);
X                 /* do the copy */
X                 while(t--)
X                     *tmpp-- = *(--ocp);
X            }
X
X            /* now set the out pointer to point to next page */
X            ocp = KEYADR(hi);
X
X        }
X    }
X
X    /* set key counts - if we split an index, we dropped one */
X    if(HIPT(old) == BT_NULL) {
X        KEYCNT(hi) = oky - KEYCNT(lo);
X    } else {
X        KEYCNT(hi) = (oky - KEYCNT(lo)) - 1;
X    }
X
X    /* set key lengths - if we split an index, adjust high value */
X    KEYLEN(hi) = byt - KEYLEN(lo) - dropbyt;
X
X    /* set the locations of the ptrs */
X    iout = (int *)KEYIND(lo);
X    iin = (int *)KEYIND(old);
X    lout = (off_t *)KEYCLD(lo);
X
X    /* copy ptrs and insert new ptr at specified location */
X    copied = 0;
X
X    for(iky = oky = 0; oky < KEYCNT(old) + 1; oky++) {
X
X        if(at == iky && copied == 0) {
X            copied++;
X            if(oky == splitat && HIPT(old) != BT_NULL) {
X                HIPT(lo) = *ptr;
X
X                /* since we did this, dropped bytes */
X                /* dont count. ignore them */
X                dropbyt = 0;
X            } else {
X                *lout = *ptr;
X
X                /* set up length/index ptrs */
X                /* do not do this if the ptr was */
X                /* inserted at a dropped location */
X                if(iky == 0 || oky == splitat + 1)
X                    *iout = len;
X                else
X                    *iout = *(iout - 1) + len;
X
X                /* length values now shift due to insert */
X                shif += len;
X            }
X        } else {
X            if(oky == splitat && HIPT(old) != BT_NULL) {
X                /* normal ptr insert at boundary */
X                HIPT(lo) = *lin++;
X                iin++;
X            } else {
X                *lout = *lin++;
X
X                *iout = *iin + shif;
X                iin++;
X            }
X
X            iky++;
X        }
X        iout++;
X        lout++;
X
X        if(oky == splitat) {
X
X            lout = (off_t *)KEYCLD(hi);
X            iout = (int *)KEYIND(hi);
X
X            /* index/length values now shift due to split */
X            shif -= (KEYLEN(lo) + dropbyt);
X
X            if(HIPT(old) == BT_NULL)
X                HIPT(lo) = BT_NULL;
X        }
X
X    }
X
X    /* the high pointer of the high page will be that of the */
X    /* original page. the low pages high pointer should have */
X    /* already been fixed up properly somewhere in code above */
X    HIPT(hi) = HIPT(old);
X}
END_OF_FILE
if test 9448 -ne `wc -c <'b+tree/btlib/btpage2.c'`; then
    echo shar: \"'b+tree/btlib/btpage2.c'\" unpacked with wrong size!
fi
# end of 'b+tree/btlib/btpage2.c'
fi
if test -f 'b+tree/doc/store.3' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/doc/store.3'\"
else
echo shar: Extracting \"'b+tree/doc/store.3'\" \(12752 characters\)
sed "s/^X//" >'b+tree/doc/store.3' <<'END_OF_FILE'
X.\"
X.\"         (C) Copyright, 1988, 1989 Marcus J. Ranum
X.\"                    All rights reserved
X.\"
X.\"
X.\"          This software, its documentation,  and  supporting
X.\"          files  are  copyrighted  material  and may only be
X.\"          distributed in accordance with the terms listed in
X.\"          the COPYRIGHT document.
X.\"
X.\" $Header: /atreus/mjr/hacks/btree/doc/RCS/store.3,v 1.2 89/10/23 16:06:04 mjr Rel $
X.\"
X.TH STORE 3 "18 October 1989"
X.SH NAME
Xstore \- variable length record storage and management routines
X.SH SYNOPSIS
X.B #include <sys/types.h>
X.br
X.B #include <store.h>
X.sp
X.LP
X.B "sto_ptr store_alloc(st,bytes)"
X.br
X.B "STORE *st;"
X.br
X.B "int bytes;"
X.LP
X.B "int store_close(st)"
X.br
X.B "STORE *st;"
X.LP
X.B "int store_copy(st,record1,record2)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record1;"
X.br
X.B "sto_ptr record2;"
X.LP
X.B "int store_decrefcnt(st,record)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.LP
X.B "int store_free(st,record)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.LP
X.B "int store_gethdr(st,record,hdr)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "struct sto_hdr hdr;"
X.LP
X.B "int store_increfcnt(st,record)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.LP
X.B "int store_linkafter(st,record,predecessor)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "sto_ptr predecessor;"
X.LP
X.B "int store_linkbefore(st,record,next)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "sto_ptr next;"
X.LP
X.B "STORE *store_open(file,flags,mode)"
X.br
X.B "char *file;"
X.br
X.B "int flags;"
X.br
X.B "int mode;"
X.LP
X.B "void store_perror(st,string)"
X.br
X.B "STORE *st;"
X.br
X.B "char *string;"
X.LP
X.B "int store_puthdr(st,record,hdr)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "struct sto_hdr hdr;"
X.LP
X.B "int store_read(st,record,offset,buf,siz,rsiz)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "off_t offset;"
X.br
X.B "unsigned char *buf;"
X.br
X.B "int siz;"
X.br
X.B "int *rsiz;"
X.LP
X.B "int store_realloc(st,record,newbytes)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "int newbytes;"
X.LP
X.B "sto_ptr store_reallocbuf(st,newsize)"
X.br
X.B "STORE *st;"
X.br
X.B "int newsize;"
X.LP
X.B "int store_unlink(st,record)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.LP
X.B "int store_write(st,record,offset,buf,bytes)"
X.br
X.B "STORE *st;"
X.br
X.B "sto_ptr record;"
X.br
X.B "off_t offset;"
X.br
X.B "unsigned char *buf;"
X.br
X.B "int bytes;"
X.SH DESCRIPTION
X.LP
XThe record storage library is intended to provide a reasonably simple
Xlow-level record allocation and manipulation package. Functions are
Xprovided for allocating, deallocating, reallocating, copying, and linking
Xrecords into lists. Basic functions are also provided for performing
XI/O to records with the ability to update complete or partial records.
XFree space management is based on first fit without garbage collection.
X.LP
XThe interface to the library is intended to somewhat evoke
X.B "malloc()"
Xet. al., with a typedef'd data type
X.B sto_ptr
Xbeing the "address" of a storage record (in this case, the offset of
Xthe record header in the disk file). The library is constructed in
Xseveral layers, the lowest handling accessing and modifying the record
Xheaders, stored data, and storage allocation. Another layer is built
Xupon the basic routines, managing copying data, reallocation and resizing
Xof records, and linked list management. The library is constructed so
Xthat a minimal price is paid for features not used, so programmers can
Xwork at whatever level suits their needs.
X.LP
XWith each record, an internal count is kept of the number of bytes in
Xuse within the record (the record's size) and the actual allocated size
Xof the record (the record's allocation). Reads and writes may adjust the
Xrecord's size, but only allocation or reallocation can affect the
Xrecord's allocation.
X.SH FUNCTIONS
X.LP
X.B "sto_ptr store_alloc(store,bytes)"
X.br
XThe
X.B store_alloc
Xfunction allocates a record space of
X.B bytes
Xsize and returns the address of the record, or
X.B STO_NULL
Xif the allocation failed.
X.LP
X.B "store_close(store)"
X.br
XThis function closes a store file.
X.LP
X.B "store_copy(store,rec1,rec2)"
X.br
XThis function copies the data in record
X.B rec1
Xinto
X.B rec2,
Xwhich must have been previously allocated, and must be large enough to
Xcontain the contents of
X.B rec1.
XIf
X.B rec2
Xhas data already allocated in it, and
X.B rec1
Xdoes not completely over-write
X.B rec2
Xthe size of the record remains whatever size
X.B rec2
Xalready held. This allows a record to be "overlaid" on another, similarly
Xto
X.B "bcopy(3)"
Xand its effect on memory. If
X.B rec2
Xhad not actually had any data written into it, the size of the record's
Xcontents will be set as that of
X.B rec1.
X.LP
X.B "store_decrefcnt(store,record)"
X.br
XThis function decrements the reference counter of the record by one.
XThe reference count can go below zero. Reference counts do not currently
Xhave much effect on records, however
X.B "store_free()"
Xwill not free a record with a reference count greater than zero, though
Xit will decrement it automatically, and return as if the operation had
Xcompleted correctly.
X.LP
X.B "store_gethdr(store,record,hdr)"
X.br
XThis function reads the header of the record specified in
X.B record,
Xand places the results in
X.B hdr.
XThis function performs some additional checks to try to ensure that
Xthe record is a valid one, including checking a magic number stored
Xin the header.
X.LP
X.B "store_increfcnt(store,record)"
X.br
XThis function increments the reference counter of the record by one.
X.LP
X.B "store_linkafter(store,record,predecessor)"
X.br
XThis function places the record
X.B record
Xinto a linked list after the record
X.B predecessor
Xand adjusts and links that may have already existed between
X.B predecessor
Xand any other records linked after it.
XIf
X.B record
Xis already linked into a list, those links are \fBnot\fR broken before
Xthe link-in is performed. This permits appending two chains together,
Xbut also makes it possible to destroy a chain by inserting a record
Xwithout unlinking it from its siblings. Careful management of the
Xlinked lists is the user's responsibility. If a call is made to
X.B store_free
Xor
X.B store_realloc
Xthe links are unlinked, or adjusted appropriately, if they exist.
X.LP
X.B "store_linkbefore(store,record,next)"
X.br
XThis function links the record before the record specified as
X.B next.
X.LP
X.B "STORE *store_open(file,flags,mode)"
X.br
XThis function allocates a new store file handle, with the pathname
Xspecified by
X.B file.
XThe flags specified in
X.B flags
Xand the mode specified in
X.B mode
Xare passed to
X.B "open(2)".
X.LP
X.B "void store_perror(store,string)"
X.br
XThis function prints an error string
X.B string
Xassociated with store file
X.B store
Xon the standard error, if there is an error flag set for that store
Xfile. If there is no error flag set, and a system error number is
Xset in
X.B errno
Xthe library call
X.B "perror(3)"
Xis called instead.
X.LP
X.B "int store_puthdr(store,record,hdr)"
X.br
XThis function writes the header stored in
X.B hdr
Xinto the record header for
X.B record.
X.LP
X.B "int store_read(store,record,offset,buf,size,rsiz)"
X.br
XThis function reads the data stored in record
X.B record,
Xstarting from offset
X.B offset
Xrelative to the beginning of the record. The returned data is
Xplaced in
X.B buf,
Xup to a maximum of
X.B size,
Xand the number of bytes read is returned in
X.B rsiz.
XIf there was more data in the record than could fit in
X.B buf,
X.B size
Xbytes is read into
X.B buf,
Xand
X.B store_read
Xreturns the constant
X.B STO_MORE
Xto indicate that there is more data to read.
X.LP
X.B "sto_ptr store_realloc(store,record,newbytes)"
X.bt
XThis function allocates a new record of size
X.B newbytes
Xand copies the contents of
X.B record
Xinto it, returning the new record pointer, or
X.B STO_NULL
Xin the event of a failure.
X.LP
X.B "int store_reallocbuf(store,newsize)"
X.br
XThis function is used to manipulate the size of the internal
Xbuffer used by the record store, to allocate more memory for it
Xif needed. This is used in the
X.B btdbm
Xlibrary to stretch the buffer to adapt to user data.
X.LP
X.B "int store_unlink(store,record)"
X.br
XThis function breaks any linked list pointers for
X.B record
Xand re-connects them as necessary to fill the record's gap.
X.LP
X.B "int store_write(store,record,offset,buf,bytes)"
X.br
XThis function will write
X.B bytes
Xfrom
X.B buf
Xinto record
X.B record
Xstarting at offset
X.B offset
Xrelative to the beginning of the record. If the write cannot fit into
Xthe space allocated for the record,
X.B STO_ERR
Xis returned. If the write places more of the record's allocated space
Xinto use, the record header will be adjusted appropriately. This function
Xcan be used to over-write parts of a record, as well as entire records,
Xso that each record can be treated somewhat like a small file in its
Xown right.
X.SH "MACROS"
X.LP
XSince these values are all macros, they should be used only with
Xcaution, to avoid side-effects. Mostly these should not be used by
Xuser-level code, but providing a common interface seemed better
Xthan the alternative.
X.LP
X.B "(int) store_errno(store)"
X.br
Xpoints to the error number associated with the storage file.
X.LP
X.B "(void) store_clearerr(store)"
X.br
Xclears the error number associated with the storage file.
X.LP
X.B "(int) store_fileno(store)"
X.br
Xpoints to the file descriptor of the storage file.
X.LP
X.B "(unsigned char *) store_buffer(store)"
X.br
Xpoints to the internal buffer of the storage file. This can be used
X(wisely) as a buffer in which to store record data temporarily, but
Xit may be changed without warning by any of the store library or
Xbtdbm library functions.
X.LP
X.B "(int) store_bufsiz(store)"
X.br
Xpoints to an integer value that is the current maximum size of the
Xinternal buffer.
X.LP
X.B "(sto_ptr) store_currec(store)"
X.br
Xpoints to a temporary area in which the current record can be stored.
XAny calls to the btdbm library or the store library may change this
Xvalue. (NOT USED CURRENTLY).
X.LP
X.B "(sto_ptr) store_label(store)"
X.br
Xpoints to a special record value that can be used to store data file
Xspecific information. Currently neither the store or btdbm libraries
Xuse this value. It is initially not allocated, and must be allocated
Xand set before using. In all other ways, it is treated just like any
Xother record. The intent is to allow a place to store static schema
Xinformation, etc.
X.SH EXAMPLES
X.nf
X.na
X.ft C
X    STORE    *p;
X    struct    froozum    stuff;
X    sto_ptr    rec;
X    int    i;
X
X    p = store_open("foo.dat",O_CREAT,0600);
X
X    if(p != NULL) {
X        rec = store_alloc(p,sizeof(struct froozum));
X        if(rec == STO_NULL) {
X            store_perror(p,"cannot allocate record");
X            exit(1);
X        }
X
X        i = store_write(p,rec,0L,(unsigned char *)&stuff,sizeof(stuff))
X        if(i != STO_OK) {
X            store_perror(p,"cannot store stuff");
X            exit(1);
X        }
X    }
X.ft R
X.fi
X.ad
X.LP
XThe above would open \fIfoo.dat\fR with mode 0600, and would create
Xthe file if it did not already exist. A record is allocated with enough
Xroom to fit a data structure, which is then stored.
X.SH "SEE ALSO"
X.SH "INTERNAL FUNCTIONS"
X.LP
XThe following functions are internal functions used by the store library.
XCare should be taken to avoid declaring functions with names that clash:
X.B store_wsuper
X.LP
XIn general, all the store library functions and macros are prefixed with
X.B store_...
Xand constants with
X.B STO_...
X.SH DIAGNOSTICS
X.LP
XThe value
X.B STO_OK
Xis returned whenever a function is successful.
X.LP
XThe value
X.SM
X.B STO_ERR
Xis returned to indicate some form of failure in any operation performed on
Xa valid
X.B STORE.
XAll valid storage file handles contain their own error number that is set to
Xindicate the cause of a failure, and can be accessed with the macro
X.B "store_errno(store)"
X(where
X.B store
Xis a valid store file). A function
X.B "store_perror(store,string)"
X(where
X.B string
Xis a character pointer and
X.B store
Xis a valid store file) is provided, which prints an appropriate error
Xmessage on the standard error.
XAdditionally, access to the error strings is available through the
Xexternal array
X.B "store_errs[]".
XConstant value codes for each error are defined in
X.B store.h
Xfor symbolic reference.
X.LP
XThe value
X.SM
X.B NULL
Xis returned to indicate that a
X.SM
X.B STORE
Xpointer has not been initialized properly.
X.SH BUGS
X.LP
XThe facilities for managing linked lists is very primitive. Ideally, more
Xwork should be done behind the scenes by the library, rather than forcing
Xthe user to handle link consistency.
X.LP
XA lot is left to the user's discretion.
X.SH LIMITATIONS
X.LP
XA record can be arbitrarily large, though it will take longer to copy
Xand reallocate longer records. The way in which the
X.B store_read
Xand
X.B store_write
Xfunctions are implemented allows reasonably flexible manipulation of even
Xlarge amounts of storage in a record.
X.SH AUTHOR
X.LP
XMarcus J. Ranum
END_OF_FILE
if test 12752 -ne `wc -c <'b+tree/doc/store.3'`; then
    echo shar: \"'b+tree/doc/store.3'\" unpacked with wrong size!
fi
chmod +x 'b+tree/doc/store.3'
# end of 'b+tree/doc/store.3'
fi
if test -f 'b+tree/utils/rectest.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/utils/rectest.c'\"
else
echo shar: Extracting \"'b+tree/utils/rectest.c'\" \(9925 characters\)
sed "s/^X//" >'b+tree/utils/rectest.c' <<'END_OF_FILE'
X#include    <stdio.h>
X#include    <ctype.h>
X#include    <sys/types.h>
X#include    <sys/file.h>
X#include    "store.h"
X
X/*
X         (C) Copyright, 1988, 1989 Marcus J. Ranum
X                    All rights reserved
X
X
X          This software, its documentation,  and  supporting
X          files  are  copyrighted  material  and may only be
X          distributed in accordance with the terms listed in
X          the COPYRIGHT document.
X*/
X
X/*
X    Test rack program for the record storage library. This allows some
X    minimal interaction with record stores. All records are identified
X    with the header of their offset. The only way to get a valid header
X    is by alloc'ing a new record. Good luck. This is not worth documenting.
X*/
X
X
X#ifndef    lint
Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/utils/RCS/rectest.c,v 1.1 89/10/24 10:09:27 mjr Rel $";
X#endif
X
X
XSTORE    *globf = NULL;
X
X#define    MAXARG    40
Xchar    *globargv[MAXARG];        /* args for commands */
Xint    globargc;
Xchar    globname[500];
X
Xextern    char    *strcpy();
Xextern    char    *malloc();
Xextern    char    *rindex();
Xextern    long    atol();
Xextern    float    atof();
X
Xvoid do_open(), do_close(), do_quit(), do_help();
Xvoid do_read(), do_write(), do_alloc(), do_pheader();
Xvoid do_increc(), do_decrec(), do_free(), do_copy();
Xvoid do_realloc(), do_linkrec(), do_unlink();
X
Xvoid    enargv();    /* function to parse user args into strings */
Xvoid    doit();        /* dispatch function */
X
Xstatic    char    *grokmsg = "Cannot interpret \"%s\" as a record number\n";
X
X
Xstruct    cmd {
X    char    *name;
X    char    *usage;
X    void    (*func)();
X    int    narg;        /* # of args req'd */
X    int    op;        /* needs an open index to call */
X};
X
Xstatic    char    *prompt = "rectest-> ";
X
X/* command dispatch table */
Xstruct    cmd    cmds[] = {
X"alloc",    "alloc nbytes",            do_alloc,    1,    1,
X"close",    "close",            do_close,    1,    1,
X"copy",        "copy fromrec# torec#",        do_copy,    2,    1,
X"decrement",    "decrement rec# (ref count)",    do_decrec,    2,    1,
X"free",        "free rec#",            do_free,    2,    1,
X"increment",    "increment rec# (ref count)",    do_increc,    2,    1,
X"link",        "link rec# after|before recd#",    do_linkrec,    3,    1,
X"open",        "open database",        do_open,    2,    0,
X"printheader",    "printheader rec#",        do_pheader,    2,    1,
X"quit",        "quit",                do_quit,    1,    0,
X"read",        "read rec#",            do_read,    2,    1,
X"realloc",    "realloc rec# size",        do_realloc,    3,    1,
X"unlink",    "unlink rec#",            do_unlink,    2,    1,
X"write",    "write rec#",            do_write,    2,    1,
X"?",        "?",                do_help,    1,    0,
X0,        0,                0,        0,    0
X};
X
X
Xmain(ac,av)
Xint    ac;
Xchar    **av;
X{
X    int    x;
X    char    buf[BUFSIZ];
X
X    /* enargv() makes a string look like an arg. vector. */
X    /* doit dispatches the stuff, calls functions, etc */
X    /* functions must have at least the given # of args */
X    /* last flag in a command if not zero means an index */
X    /* must be open in order to call that function */
X
X    if(ac > 1) {
X        char    **gap = globargv;
X
X        globargc = ac - 1;
X        while(*++av)
X            *gap++ = *av;
X        doit();
X    } else {
X        (void)printf(prompt);
X        while(gets(buf)) {
X            enargv(buf);
X            if(globargv[0] != NULL)
X                doit();
X
X            for(x = 0; x < globargc; x++)
X                (void)free(globargv[x]);
X
X            (void)printf(prompt);
X        }
X        (void)printf("EOF.\n");
X    }
X    do_quit();
X}
X
X
Xvoid
Xdoit()
X{
X    struct    cmd    *c = cmds;
X
X    /* main dispatcher */
X    while(c->name != 0) {
X        if(strncmp(c->name,globargv[0],strlen(globargv[0])) == 0) {
X            if(globargc < c->narg) {
X                (void)printf("usage:\"%s\"\n",c->usage);
X                return;
X            } else {
X                if(c->op != 0 && globf == NULL) {
X                    (void)printf("no store file open.\n");
X                    return;
X                }
X                (*c->func)();
X                return;
X            }
X        }
X        c++;
X    }
X    (void)printf("unknown command: \"%s\"\n",globargv[0]);
X    return;
X}
X
X
Xchar *
Xwordparse(line,word,delim)
Xchar    *line,    *word;
Xint    delim;
X{
X    int    quot =0;
X
X    /* parse a word, or quoted string into a buffer. */
X    while (*line && (isspace(*line) || *line == delim))
X        line++;
X
X    if(*line == '\n')
X        line++;
X
X    if (!*line) {
X        *word = '\0';
X        return(0);
X    }
X
X    while (*line)
X    {
X        if(!quot && (*line == '\"' || *line == '\''))
X            quot = *line++;
X
X        if((isspace(*line) || *line == delim) && !quot) {
X            break;
X        } else {
X            if(quot && *line == quot) {
X                quot = 0;
X                line++;
X            } else {
X                *word++ = *line++;
X            }
X        }
X    }
X    *word = '\0';
X    return(line);
X}
X
X
Xvoid
Xenargv(buf)
Xchar    *buf;
X{
X    char    *bufptr;
X    char    pbuf[BUFSIZ];
X
X    globargc =0;
X    bufptr = buf;
X
X    /* this is kinda gross, but the easiest way to handle */
X    /* quoted strings, since I already had wordparse() written */
X    while(bufptr = wordparse(bufptr,pbuf,0)) {
X        globargv[globargc] = malloc((unsigned)(strlen(pbuf) + 1));
X        (void)strcpy(globargv[globargc++],pbuf);
X    }
X    globargv[globargc] = NULL;
X}
X
Xvoid
Xdo_open()
X{
X    if(globf != NULL) {
X        (void)printf("try closing %s first, ok ?\n",globname);
X        return;
X    }
X
X    globf = store_open(globargv[1],O_CREAT,0600);
X
X    if(globf == NULL) {
X        (void)printf("error opening store file ");
X        perror(globargv[1]);
X    } else {
X        (void)printf("opened %s\n",globargv[1]);
X        (void)strcpy(globname,globargv[1]);
X    }
X}
X
X
Xvoid
Xdo_close()
X{
X    if(globf != NULL) {
X        if(store_close(globf) == STO_OK) {
X            (void)printf("closed OK\n");
X            globf = NULL;
X        } else
X            (void)printf("error closing\n");
X    } else {
X        (void)printf("nothing open\n");
X    }
X}
X
X
Xvoid
Xdo_alloc()
X{
X    int    siz;
X    sto_ptr    ret;
X
X    if((siz = atoi(globargv[1])) == 0) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    ret = store_alloc(globf,siz);
X    if(ret != STO_NULL) {
X        (void)printf("allocated record #%ld\n",ret);
X    } else {
X        store_perror(globf,"cannot allocate record");
X    }
X}
X
X
Xvoid
Xdo_quit()
X{
X    if(globf != NULL) {
X        (void)printf("closing %s\n",globname);
X        if(store_close(globf) != STO_OK) {
X            (void)printf("problems closing %s\n",globname);
X            exit(1);
X        }
X    }
X    exit(0);
X}
X
X
Xvoid
Xdo_help()
X{
X    struct    cmd    *c = cmds;
X    (void)printf("short list of commands::\n------------------------\n");
X    while(c->name != 0) {
X        (void)printf("%s\n",c->usage);
X        c++;
X    }
X}
X
X
Xvoid
Xdo_read()
X{
X    char    buf[BUFSIZ];
X    int    rv;
X    int    byts;
X    off_t    offset =0L;
X    sto_ptr    r;
X
X    if((r = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(globargc > 2) {
X        if((offset = atol(globargv[2])) == 0L) {
X            (void)printf(grokmsg,globargv[1]);
X            return;
X        } else {
X            (void)printf("offset is %ld\n",offset);
X        }
X    }
X
X    while(1) {
X        rv = store_read(globf,r,offset,(unsigned char *)buf,sizeof(buf),&byts);
X        switch(rv) {
X            case STO_OK:
X                (void)printf("got %d bytes:\n",byts);
X                buf[byts] = '\0';
X                (void)printf("%s\n",buf);
X                return;
X
X            case STO_MORE:
X                (void)printf("got %d bytes:\n",byts);
X                buf[byts] = '\0';
X                (void)printf("%s\n---(press return for more)---",buf);
X                (void)gets(buf);
X
X            case STO_ERR:
X                store_perror(globf,"cannot read record");
X                return;
X        }
X    }
X}
X
X
Xvoid
Xdo_write()
X{
X    char    buf[BUFSIZ];
X    int    rv;
X    off_t    offset =0L;
X    sto_ptr    r;
X
X    if((r = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(globargc > 2) {
X        if((offset = atol(globargv[2])) == 0L) {
X            (void)printf(grokmsg,globargv[1]);
X            return;
X        } else {
X            (void)printf("offset is %ld\n",offset);
X        }
X    }
X
X    (void)printf("\tinput-> ");
X    if(fgets(buf,BUFSIZ,stdin) != NULL) {
X        rv = store_write(globf,r,offset,(unsigned char *)buf,strlen(buf));
X        if(rv != STO_OK) {
X            store_perror(globf,"cannot store record");
X        }
X    }
X}
X
Xvoid
Xdo_pheader()
X{
X    struct    sto_hdr    rbuf;
X    sto_ptr    r;
X
X    if((r = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(store_gethdr(globf,r,&rbuf) == STO_ERR) {
X        store_perror(globf,"cannot get record header");
X        return;
X    }
X    (void)printf("struct\tsto_hdr {\n\toff_t\tmagic = %ld\n",rbuf.magic);
X    (void)printf("\tint\tsize = %d\n\tint\tused = %d\n",rbuf.size,rbuf.used);
X    (void)printf("\tint\trefs = %d\n\tsto_ptr\tnext = %d\n",rbuf.refs,rbuf.next);
X    (void)printf("\tsto_ptr\tprev = %d\n};\n",rbuf.prev);
X}
X
X
Xvoid
Xdo_increc()
X{
X    sto_ptr    r;
X
X    if((r = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(store_increfcnt(globf,r) == STO_ERR) {
X        store_perror(globf,"cannot increment record header");
X        return;
X    }
X}
X
X
Xvoid
Xdo_decrec()
X{
X    sto_ptr    r;
X
X    if((r = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(store_decrefcnt(globf,r) == STO_ERR) {
X        store_perror(globf,"cannot decrement record header");
X        return;
X    }
X}
X
X
Xvoid
Xdo_free()
X{
X    sto_ptr    r;
X
X    if((r = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(store_free(globf,r) == STO_ERR) {
X        store_perror(globf,"cannot free record");
X        return;
X    }
X}
X
X
Xvoid
Xdo_copy()
X{
X    sto_ptr    r1;
X    sto_ptr    r2;
X
X    if((r1 = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X    if((r2 = atol(globargv[2])) == 0L) {
X        (void)printf(grokmsg,globargv[2]);
X        return;
X    }
X
X    if(store_copy(globf,r1,r2) == STO_ERR) {
X        store_perror(globf,"cannot copy record");
X        return;
X    }
X}
X
X
Xvoid
Xdo_realloc()
X{
X    sto_ptr    rec;
X    int    nsize;
X
X    if((rec = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X    if((nsize = atoi(globargv[2])) == 0L) {
X        (void)printf(grokmsg,globargv[2]);
X        return;
X    }
X    if((rec = store_realloc(globf,rec,nsize)) == STO_NULL) {
X        store_perror(globf,"realloc failed");
X        return;
X    }
X    (void)printf("new record is %ld\n",rec);
X}
X
X
Xvoid
Xdo_linkrec()
X{
X    sto_ptr    rec;
X    sto_ptr    rec2;
X    int    after = 1;
X    int    ret;
X
X    if((rec = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X    if(strncmp(globargv[2],"after",strlen(globargv[2])))
X        if(strncmp(globargv[2],"before",strlen(globargv[2]))) {
X            (void)printf("specify \"before\" or \"after\"\n");
X            return;
X        } else
X            after = 0;
X
X    if((rec2 = atol(globargv[3])) == 0L) {
X        (void)printf(grokmsg,globargv[3]);
X        return;
X    }
X
X    if(after)
X        ret = store_linkafter(globf,rec,rec2);
X    else
X        ret = store_linkbefore(globf,rec,rec2);
X    if(ret == STO_ERR) {
X        store_perror(globf,"relink failed");
X        return;
X    }
X}
X
X
Xvoid
Xdo_unlink()
X{
X    sto_ptr    rec;
X
X    if((rec = atol(globargv[1])) == 0L) {
X        (void)printf(grokmsg,globargv[1]);
X        return;
X    }
X
X
X    if(store_unlink(globf,rec) == STO_ERR) {
X        store_perror(globf,"unlink failed");
X        return;
X    }
X}
END_OF_FILE
if test 9925 -ne `wc -c <'b+tree/utils/rectest.c'`; then
    echo shar: \"'b+tree/utils/rectest.c'\" unpacked with wrong size!
fi
# end of 'b+tree/utils/rectest.c'
fi
if test -f 'b+tree/utils/testrack.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/utils/testrack.c'\"
else
echo shar: Extracting \"'b+tree/utils/testrack.c'\" \(11151 characters\)
sed "s/^X//" >'b+tree/utils/testrack.c' <<'END_OF_FILE'
X#include    <stdio.h>
X#include    <sys/file.h>
X#include    <sys/types.h>
X#include    "btree.h"
X
X/*
X         (C) Copyright, 1988, 1989 Marcus J. Ranum
X                    All rights reserved
X
X
X          This software, its documentation,  and  supporting
X          files  are  copyrighted  material  and may only be
X          distributed in accordance with the terms listed in
X          the COPYRIGHT document.
X*/
X
X
X#ifndef    lint
Xstatic char *rcsid = "$Header: /atreus/mjr/hacks/btree/utils/RCS/testrack.c,v 1.1 89/10/24 10:09:25 mjr Rel $";
X#endif
X
Xextern    char    *index();
X
X/*
X    about this program:
X    This program slams the btree index routines repeatedly on thier
X    heads in an attempt to break them, or detect problems. rather
X    than make the checks rely on information about the internal
X    structures of the tree itself, these checks verify the BEHAVIOUR
X    of the library. that is to say, if 1000 keys are inserted, it
X    should be possible to find them all. if 1000 keys are deleted,
X    there should be no more keys left, etc. really, the only aspect
X    of the functions that is not given a pretty harsh going-over is
X    the reverse traversing function. this is mainly because I cant
X    think of a nice way to scan an ascii file a line at a time in
X    reverse, and didn't want to have another sorted input file.
X
X    before this code has been released, this testrack has been
X    allowed to run on a reasonable variety of page sizes for a
X    reasonable number of keys (say, 10,000) for, say, a day or
X    two, on a Sun4. if you make changes to the library internals
X    this suite can come in pretty handy, though it offers zero
X    help for debugging.
X*/
X
Xstatic    void
Xdie(b1,b2,val)
XBT_INDEX    *b1;
XBT_INDEX    *b2;
Xint        val;
X{
X    /* die is called with a sequentially higher value from each */
X    /* possible point of failure. this allows quick location of */
X    /* which check may have produced he fatal error condition */
X    if(b1 != NULL)
X        (void)bt_close(b1);
X    if(b2 != NULL)
X        (void)bt_close(b2);
X    (void)fprintf(stderr,"tests FAILED at error point %d\n",val);
X    exit(val);
X}
X
Xmain(ac, av)
Xint     ac;
Xchar   *av[];
X{
X    char           buf[BUFSIZ];
X    char           buf2[BUFSIZ];
X    FILE        *input;
X    FILE        *sorted;
X    BT_INDEX    *b = NULL;    /* main test index */
X    BT_INDEX    *d = NULL;    /* index to store deleted keys */
X    char        *p;
X    off_t          rrv = 0L;
X    int        ret;
X    int        keycnt = 0;    /* # of keys inserted */
X    int        psiz = BUFSIZ;
X    int        retlen;
X    int        junk;
X
X    /* boo ! Sun buffers stderr ! */
X    (void)setbuf(stderr,0);
X
X    if(ac < 3) {
X        (void)fprintf(stderr,"usage: %s input sorted_input [psiz]\n",av[0]);
X        die(b,d,1);
X    }
X
X    if(ac > 3) {
X        if((psiz = atoi(av[3])) == 0) {
X            (void)fprintf(stderr,"cannot grok %s as a page size\n",av[3]);
X            die(b,d,2);
X        }
X    }
X
X    if((input = fopen(av[1],"r")) == NULL) {
X        perror(av[1]);
X        die(b,d,3);
X    }
X
X    if((sorted = fopen(av[2],"r")) == NULL) {
X        perror(av[2]);
X        die(b,d,4);
X    }
X
X#ifdef    BTOPEN
X    b = bt_open("test.dat",O_CREAT|O_TRUNC,0600);
X#else
X    b = bt_optopen(BT_PATH,    "test.dat",
X            BT_OMODE,    O_CREAT|O_TRUNC,    /* clobber */
X            BT_CACHE,    2,
X            BT_PSIZE,    psiz,
X    0);
X#endif
X
X    if(b == NULL) {
X        perror("test.dat");
X        die(b,d,5);
X    }
X
X#ifdef    DEBUG
X    (void)fprintf(stderr,"Start: opened all trees OK.\n");
X#endif
X
X    /* PHASE I - insert everything from our random-ordered file */
X    /* into our newly created tree. This should return all BT_OK */
X    while(fgets(buf,BUFSIZ,input) != NULL) {
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        /* stuff it */
X        ret = bt_insert(b,buf,strlen(buf),++rrv,1);
X        if(ret != BT_OK) {
X            (void)fprintf(stderr,"insert \"%s\" failed: ",buf);
X            bt_perror(b,NULL);
X            die(b,d,6);
X        }
X        keycnt++;
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase I, inserted %d keys OK.\n",keycnt);
X#endif
X
X
X    /* PHASE II - rewind to the beginning of the input file and */
X    /* search for each key again, to make sure we can find it. */
X    if(fseek(input,0L,0)) {
X        perror("rewind random ordered input file");
X        die(b,d,7);
X    }
X    keycnt = 0;
X    while(fgets(buf,BUFSIZ,input) != NULL) {
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        /* find it */
X        ret = bt_find(b,buf,strlen(buf),&rrv);
X        if(ret != BT_OK) {
X            (void)fprintf(stderr,"find \"%s\" failed: ",buf);
X            bt_perror(b,NULL);
X            die(b,d,8);
X        }
X        keycnt++;
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase II, located %d keys OK.\n",keycnt);
X#endif
X
X
X    /* PHASE III - go to the beginning of the tree, and read each */
X    /* key in order. as we read it, compare it to the matching key */
X    /* read out of the sorted input file. they should all match */
X
X    if(fseek(sorted,0L,0)) {
X        perror("rewind ordered input file");
X        die(b,d,9);
X    }
X
X    /* goto head of tree */
X    if(bt_goto(b,BT_BOF) == BT_ERR) {
X        bt_perror(b,"rewind btree to BOF");
X        die(b,d,10);
X    }
X
X    while(fgets(buf,BUFSIZ,sorted) != NULL) {
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        ret = bt_traverse(b,BT_EOF,buf2,BUFSIZ,&retlen,&rrv);
X        if(ret != BT_OK) {
X            (void)fprintf(stderr,"read of next key failed.\n");
X            die(b,d,11);
X        }
X
X        /* NULL terminate buf2 */
X        buf2[retlen] = '\0';
X
X        if(strcmp(buf2,buf)) {
X            (void)fprintf(stderr,"read-back of \"%s\" and \"%s\" - do not match.\n",buf,buf2);
X            die(b,d,12);
X        }
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase III, ordered read-back of keys.\n");
X#endif
X
X
X    /* PHASE IV - delete half the keys from the index */
X
X    /* rewind input file */
X    if(fseek(input,0L,0)) {
X        perror("rewind input file");
X        die(b,d,13);
X    }
X
X    /* open a second index to store deleted keys */
X#ifdef    BTOPEN
X    d = bt_open("test2.dat",O_CREAT|O_TRUNC,0600);
X#else
X    d = bt_optopen(BT_PATH,    "test2.dat",
X            BT_OMODE,    O_CREAT|O_TRUNC,    /* clobber */
X            BT_CACHE,    2,
X            BT_PSIZE,    psiz,
X    0);
X#endif
X    if(d == NULL) {
X        perror("test2.dat");
X        die(b,d,14);
X    }
X    for(junk = 0; junk < keycnt/2; junk++) {
X        if(fgets(buf,BUFSIZ,input) == NULL) {
X            (void)fprintf(stderr,"EOF in read-back of initial input\n");
X            die(b,d,15);
X        }
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        /* see if the key is a duplicate that was already deleted */
X        /* and if so, do not try to re-delete it */
X        ret = bt_find(d,buf,strlen(buf),&rrv);
X        if(ret == BT_NF) {
X
X            /* not in the deleted index, so delete it and add it */
X            /* step 1: delete from real index */
X            if(bt_delete(b,buf,strlen(buf)) != BT_OK) {
X                bt_perror(b,"delete failed\n");
X                die(b,d,16);
X            }
X            /* step 2: add it to the deleted index */
X            if(bt_insert(d,buf,strlen(buf),-1L,1) != BT_OK) {
X                bt_perror(d,"insert in deleted failed\n");
X                die(b,d,17);
X            }
X        } else {
X            if(ret != BT_OK) {
X                bt_perror(d,"search for deleted failed\n");
X                die(b,d,18);
X            }
X        }
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase IV, delete half of keys.\n");
X#endif
X
X
X    /* PHASE V - go to the beginning of the tree, and read each */
X    /* key in order. as we read it, compare it to the matching key */
X    /* read out of the sorted input file. they should all match */
X    /* OR it should be in the deleted index, its an error */
X
X    if(fseek(sorted,0L,0)) {
X        perror("rewind ordered input file");
X        die(b,d,19);
X    }
X
X    /* goto head of tree */
X    if(bt_goto(b,BT_BOF) == BT_ERR) {
X        bt_perror(b,"rewind btree to BOF");
X        die(b,d,20);
X    }
X
X    while(fgets(buf,BUFSIZ,sorted) != NULL) {
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        ret = bt_find(d,buf,strlen(buf),&rrv);
X        if(ret == BT_NF) {
X            ret = bt_traverse(b,BT_EOF,buf2,BUFSIZ,&retlen,&rrv);
X
X            /* NULL terminate buf2 */
X            buf2[retlen] = '\0';
X
X
X            if(strcmp(buf2,buf)) {
X                (void)fprintf(stderr,"read-back of \"%s\" and \"%s\" - do not match.\n",buf,buf2);
X                die(b,d,21);
X            }
X        } else {
X            if(ret != BT_OK) {
X                (void)fprintf(stderr,"search deleted for \"%s\":",buf);
X                bt_perror(d,NULL);
X                die(b,d,22);
X            }
X        }
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase V, ordered read-back of keys.\n");
X#endif
X
X
X    /* PHASE VI - delete the rest of the keys in the input file */
X
X    /* at this point the FILE pointer should still be where we left */
X    /* it when we were done deleteing the first half of the keys in */
X    /* the index. */
X    while(fgets(buf,BUFSIZ,input) != NULL) {
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        /* see if the key is a duplicate that was already deleted */
X        /* and if so, do not try to re-delete it */
X        ret = bt_find(d,buf,strlen(buf),&rrv);
X        if(ret == BT_NF) {
X
X            /* not in the deleted index, so delete it and add it */
X            /* step 1: delete from real index */
X            if(bt_delete(b,buf,strlen(buf)) != BT_OK) {
X                bt_perror(b,"delete failed\n");
X                die(b,d,23);
X            }
X            /* step 2: add it to the deleted index */
X            if(bt_insert(d,buf,strlen(buf),-1L,1) != BT_OK) {
X                bt_perror(d,"insert in deleted failed\n");
X                die(b,d,24);
X            }
X        } else {
X            if(ret != BT_OK) {
X                bt_perror(d,"search for deleted failed\n");
X                die(b,d,25);
X            }
X        }
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase VI, delete rest of keys.\n");
X#endif
X
X    /* PHASE VII - make sure there are no more keys in original index */
X    /* seek to beginning of index and try to traverse. it should give */
X    /* an EOF immediately. any other result is an error */
X    /* goto head of tree */
X    if(bt_goto(b,BT_BOF) == BT_ERR) {
X        bt_perror(b,"rewind btree to BOF");
X        die(b,d,26);
X    }
X    ret = bt_traverse(b,BT_EOF,buf2,BUFSIZ,&retlen,&rrv);
X    if(ret != BT_EOF) {
X        if(ret == BT_ERR) {
X            bt_perror(b,"traverse to EOF");
X            die(b,d,27);
X        }
X        (void)fprintf(stderr,"expected EOF, but didn't get it\n");
X        die(b,d,28);
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase VII, tree is empty!\n");
X#endif
X
X    /* PHASE VIII - do an optimal reverse load of the deleted tree */
X    /* back into the original tree */
X    if(bt_goto(d,BT_EOF) == BT_ERR) {
X        bt_perror(b,"rewind deleted btree to EOF");
X        die(b,d,29);
X    }
X
X    /* inform the old tree we are going to bt_load it */
X    if(bt_load(b,0,0,0L,BT_BOF)== BT_ERR) {
X        bt_perror(b,"initialize load");
X        die(b,d,30);
X    }
X
X    while((ret = bt_traverse(d,BT_BOF,buf,BUFSIZ,&retlen,&rrv)) == BT_OK) {
X        if(bt_load(b,buf,retlen,rrv,BT_OK)== BT_ERR) {
X            bt_perror(b,"bt_load failed!");
X            die(b,d,31);
X        }
X    }
X
X    if(ret != BT_BOF) {
X        (void)fprintf(stderr,"deleted tree traverse did not complete at BOF!\n");
X        die(b,d,32);
X    }
X
X    /* a final call to bt_load with BT_EOF tells it to stop */
X    if(bt_load(b,0,0,0L,BT_EOF) == BT_ERR) {
X        bt_perror(b,"shut down bt_load");
X        die(b,d,33);
X    }
X
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase VIII, optimal load\n");
X#endif
X
X    /* PHASE IX - rewind to the beginning of the input file and */
X    /* search for each key again, to make sure we can find it. */
X    if(fseek(input,0L,0)) {
X        perror("rewind random ordered input file");
X        die(b,d,34);
X    }
X    keycnt = 0;
X    while(fgets(buf,BUFSIZ,input) != NULL) {
X
X        /* drop newline */
X        if((p = index(buf,'\n')) != NULL)
X            *p = '\0';
X
X        /* find it */
X        ret = bt_find(b,buf,strlen(buf),&rrv);
X        if(ret != BT_OK) {
X            (void)fprintf(stderr,"find \"%s\" failed: ",buf);
X            bt_perror(b,NULL);
X            die(b,d,35);
X        }
X        keycnt++;
X    }
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed phase IX, located %d keys OK.\n",keycnt);
X#endif
X
X    (void)bt_close(b);
X    (void)bt_close(d);
X#ifdef    DEBUG
X    (void)fprintf(stderr,"passed all tests OK.\n");
X#endif
X    exit(0);
X}
END_OF_FILE
if test 11151 -ne `wc -c <'b+tree/utils/testrack.c'`; then
    echo shar: \"'b+tree/utils/testrack.c'\" unpacked with wrong size!
fi
# end of 'b+tree/utils/testrack.c'
fi
echo shar: End of archive 4 \(of 5\).
cp /dev/null ark4isdone
MISSING=""
for I in 1 2 3 4 5 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 5 archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0