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

Text File | 1990-01-19 | 51.8 KB | 2,040 lines

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

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

#! /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 3 (of 5)."
# Contents:  b+tree/btdbmlib/stfree.c b+tree/btlib/btinsert.c
#   b+tree/btlib/btintern.h b+tree/btlib/btio.c b+tree/btlib/btoopen.c
#   b+tree/btlib/btpage1.c b+tree/doc/btdbm.3 b+tree/utils/dbtest.c
# Wrapped by mjr@atreus on Fri Jan 19 10:34:58 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'b+tree/btdbmlib/stfree.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btdbmlib/stfree.c'\"
else
echo shar: Extracting \"'b+tree/btdbmlib/stfree.c'\" \(5404 characters\)
sed "s/^X//" >'b+tree/btdbmlib/stfree.c' <<'END_OF_FILE'
X#include    <sys/types.h>
X#include    "stoconf.h"
X#include    "store.h"
X#include    "stointern.h"
X
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/btdbmlib/RCS/stfree.c,v 1.1 89/10/24 10:09:14 mjr Rel $";
X#endif
X
X/*
X    free list management and creation. the free list is maintained as a
X    stored record using the library's own internal routines. when a
X    request is made to free something, the order of operations is:
X
X    1) if the record is the free list, refuse to free it !!!
X    2)if there is more than one reference to the record, just
X    decrement the reference count and return.
X    3) if there is not a currently defined free list:
X        a)one is allocated via store_alloc(), which can actually
X        be safely called because it will not look at the nonexistent
X        free list. if the free-list management is changed, this will
X        probably get very weird.
X        b)make a free list entry and paste it into the new free list
X        c)update the superblock
X        d)return - done.
X    4) if there WAS a free list,
X        a)if the whole allocated block of the free list is not in
X        currently marked as in-use, just paste the new free list entry
X        at the end of the free list block and return.
X    - or -
X        b)scan through the allocated block looking for an empty slot
X        and if one is found, paste it directly in. this operation is
X        less inefficient than it may seem because the scan is buffered
X        pretty intelligently.
X    - if 'b' fails -
X        c)we know we now have a full free list block with no empty
X        slots, so we bite the bullet, and allocate a bigger free
X        list block at the end of file, and copy the old one into
X        it. we then have enough free space to paste the new free
X        list entry directly at the end of the block, as in '3'
X        above. this should presumably happen fairly rarely. it
X        costs some, but the copy is pretty well buffered.
X*/
X
Xstore_free(r,rec)
XSTORE    *r;
Xsto_ptr        rec;
X{
X    struct    sto_freeent    fry;
X    struct    sto_freeent    *freep;
X    struct    sto_hdr    rbuf;
X    struct    sto_hdr    nbuf;
X    sto_ptr    newf;
X    int        fcnt;
X    int        junk;
X    int        byts;
X
X    /* may as well make sure everything is OK before we do work */
X    if(store_gethdr(r,rec,&rbuf) == STO_ERR)
X        return(STO_ERR);
X
X    /* sneaky dog ! */
X    if(rec == r->sblk.free) {
X        store_errno(r) = STO_NOREC;
X        return(STO_ERR);
X    }
X
X    /* if there are is than one reference to this record, just decrement */
X    /* it and we are happy-like, even though it could be bad */
X    if(--rbuf.refs > 0) {
X        return(store_puthdr(r,rec,&rbuf));
X    }
X
X    /* if it is linked to siblinks, unlink them */
X    if(rbuf.next != STO_NULL || rbuf.prev != STO_NULL) {
X        if(store_unlink(r,rec) == STO_ERR)
X            return(STO_ERR);
X
X        /* one flaw in the design: we have to re-read the header */
X        /* since the call to unlink changes pointers and all that */
X        if(store_gethdr(r,rec,&rbuf) == STO_ERR)
X            return(STO_ERR);
X    }
X
X    fry.addr = rec;
X    fry.size = rbuf.size;
X
X    /* if there is not existing free page, create one */
X    if(r->sblk.free == STO_NULL) {
X        r->sblk.free = store_alloc(r,STO_BUFSIZ);
X        if(r->sblk.free == STO_NULL)
X            return(STO_ERR);
X        STO_FREENXT(store_buffer(r)) = STO_NULL;
X        STO_FREECNT(store_buffer(r)) = 0;
X
X        if(store_write(r,r->sblk.free,0L,store_buffer(r),2 * sizeof(off_t)) != STO_OK ||
X            store_wsuper(r) != STO_OK)
X                return(STO_ERR);
X    }
X
X    /* now grab the free record header */
X    if(store_gethdr(r,r->sblk.free,&rbuf) == STO_ERR)
X        return(STO_ERR);
X
X    /* is there room for a simple insert, or do we need to get mean ? */
X    if(rbuf.used + STO_FSIZ < rbuf.size) {
X        if(store_write(r,r->sblk.free,(off_t)rbuf.used,(unsigned char *)&fry,STO_FSIZ) == STO_ERR)
X            return(STO_ERR);
X        return(STO_OK);
X    } else {
X        off_t    currof;
X
X        currof = (off_t)(2 * sizeof(off_t));
X        while(1) {
X            int    ismore;
X
X            ismore = store_read(r,r->sblk.free,currof,store_buffer(r),store_bufsiz(r),&byts);
X            if(ismore == STO_ERR)
X                return(STO_ERR);
X
X            if(currof == 0L) {
X                freep = STO_FREEBUF(store_buffer(r));
X                fcnt = ((byts - (2 * sizeof(off_t))) / STO_FSIZ);
X            } else {
X                freep = (struct sto_freeent *)store_buffer(r);
X                fcnt = byts / STO_FSIZ;
X            }
X
X            currof += (off_t)byts;
X
X            for(junk = 0; junk < fcnt; junk++) {
X                if(freep->addr == STO_NULL) {
X                    if(store_write(r,r->sblk.free,(off_t)(2 * sizeof(off_t) + (junk * STO_FSIZ)),(unsigned char *)&fry,sizeof(fry)) == STO_ERR)
X                        return(STO_ERR);
X                }
X                freep++;
X            }
X            if(ismore != STO_MORE)
X                break;
X        }
X    }
X
X    /* brutal but effective. Allocate a bigger free block at EOF */
X    nbuf.size = rbuf.size * 2;
X    newf = r->sblk.high;
X    r->sblk.high += nbuf.size + STO_HSIZ;
X    nbuf.magic = STO_DFLTMAGIC;
X    nbuf.used = rbuf.used;
X    nbuf.refs = 1;
X    nbuf.next = nbuf.prev = STO_NULL;
X
X    if(store_puthdr(r,newf,&nbuf) == STO_ERR)
X        return(STO_ERR);
X
X    if(store_copy(r,r->sblk.free,newf) == STO_ERR)
X        return(STO_ERR);
X
X    if(store_write(r,newf,(off_t)nbuf.used,(unsigned char *)&fry,sizeof(fry)) == STO_ERR)
X        return(STO_ERR);
X
X    /* kludge #2 - free the old free page */
X    fry.addr = r->sblk.free;
X    fry.size = rbuf.size;
X
X    if(store_write(r,newf,(off_t)nbuf.used,(unsigned char *)&fry,sizeof(fry)) == STO_ERR)
X        return(STO_ERR);
X
X    r->sblk.free = newf;
X
X    return(store_wsuper(r));
X}
END_OF_FILE
if test 5404 -ne `wc -c <'b+tree/btdbmlib/stfree.c'`; then
    echo shar: \"'b+tree/btdbmlib/stfree.c'\" unpacked with wrong size!
fi
# end of 'b+tree/btdbmlib/stfree.c'
fi
if test -f 'b+tree/btlib/btinsert.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btlib/btinsert.c'\"
else
echo shar: Extracting \"'b+tree/btlib/btinsert.c'\" \(7136 characters\)
sed "s/^X//" >'b+tree/btlib/btinsert.c' <<'END_OF_FILE'
X#include    <sys/types.h>
X#include    <stdio.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/btinsert.c,v 1.1 89/10/24 10:08:58 mjr Rel $";
X#endif
X
X
Xbt_insert(b,key,len,rrn,dupflg)
XBT_INDEX    *b;
Xbt_chrp        key;
Xint        len;
Xoff_t        rrn;
Xint        dupflg;
X{
X    struct    bt_cache *kp;    /* scratch buffer for promoted keys */
X    struct    bt_cache *op;    /* old page */
X    int    staklev;
X    off_t    ipag;        /* page to insert into */
X    off_t    ival;        /* index value to insert */
X    int    keyat;        /* key # at which to insert */
X    bt_chrp    kp1;        /* rotating key buffer pointers */
X    bt_chrp    kp2;
X    off_t    ptj;        /* junk */
X    int    sr;
X
X    if(len > BT_MAXK(b)) {
X        bt_errno(b) = BT_KTOOBIG;
X        return(BT_ERR);
X    }
X
X    if(len <= 0) {
X        bt_errno(b) = BT_ZEROKEY;
X        return(BT_ERR);
X    }
X
X    if(bt_seekdown(b,key,len) == BT_ERR)
X        return(BT_ERR);
X
X    /* set current stack level */
X    staklev = b->sblk.levs - 1;
X    ipag = b->stack[staklev].pg;
X
X    /* allocate a scratch buffer for the key and promoted key */
X    /* since all keys will be < pagesiz/2, "split" the buffer */
X    if((kp = bt_rpage(b,BT_NULL)) == NULL)
X        return(BT_ERR);
X
X    /* set promotion key ptrs */
X    kp1 = kp->p;
X    /* split buffers MUST be aligned! */
X    kp2 = kp->p + DOALIGN(bt_pagesiz(b) / 2);
X
X    /* *THIS* bullshit should not be necessary */
X#ifdef    USE_BCOPY
X    (void)bcopy((char *)key,(char *)kp1,len);
X#endif
X#ifdef    USE_MEMCPY
X    (void)memcpy((char *)key,(char *)kp1,len);
X#endif
X#ifdef    USE_MOVEMEM
X    (void)movemem((char *)key,(char *)kp1,len);
X#endif
X    ival = rrn;
X
X    /* invalidate current notion of where we are in the tree */
X    b->cpag = BT_NULL;
X
X    /* set up key location for first page insert */
X    if((op = bt_rpage(b,ipag)) == NULL)
X        goto bombout;
X
X    /* locate insert point, check if duplicate */
X    /* this has the side-effect of setting keyat for the first */
X    /* run of insert. after the first insert, subsequent key */
X    /* positions are gotten from the stack, rather than searching */
X    sr = bt_srchpg(kp1,len,bt_dtype(b),b->cmpfn,&ptj,&keyat,op->p);
X    if(sr == BT_ERR) {
X        bt_errno(b) = BT_PAGESRCH;
X        return(BT_ERR);
X    }
X
X    /* if the search returned OK, we have a duplicate key and */
X    /* check to see if dupflg is set - if so, we slam a new */
X    /* copy of the rrn in, and return immediately. */
X    if(sr == BT_OK && HIPT(op->p) == BT_NULL) {
X        /* handle dup keys */
X        if(dupflg == 0) {
X            bt_errno(b) = BT_DUPKEY;
X            goto bombout;
X        } else {
X            /* paste new data ptr in page */
X            /* and write it out again. */
X            off_t    *p;
X            p = (off_t *)KEYCLD(op->p);
X            *(p + keyat) = rrn;
X            op->flags = BT_CHE_DIRTY;
X            if(bt_wpage(b,op) == BT_ERR ||
X                bt_wpage(b,kp) == BT_ERR)
X                return(BT_ERR);
X
X            /* mark all as well with tree */
X            bt_clearerr(b);
X            return(BT_OK);
X        }
X    }
X
X
X    /* this loop should be comfortably repeated until we perform a */
X    /* simple insert without a split, which will clean everything up */
X    /* and return correctly. breaking out indicates a fatal problem */
X    while(1) {
X
X        /* here is where we figure out if we need to split, or */
X        /* if we can just perform a simple insert instead */
X        if((int)KEYUSE(op->p) + len + sizeof(int) + sizeof(off_t) < bt_pagesiz(b)) {
X            struct    bt_cache *tp;
X
X            if((tp = bt_rpage(b,BT_NULL)) == NULL)
X                goto bombout;
X;
X            bt_inspg(kp1,len,&ival,keyat,op->p,tp->p);
X            /* swap the page numbers, invalidate the old, */
X            /* mark the new as dirty to force a write */
X            tp->num = op->num;
X            tp->flags = BT_CHE_DIRTY;
X            op->num = BT_NULL;
X
X            if(bt_wpage(b,op) == BT_ERR ||
X                bt_wpage(b,tp) == BT_ERR ||
X                bt_wpage(b,kp) == BT_ERR)
X                return(BT_ERR);
X
X            /* mark all as well with tree */
X            bt_clearerr(b);
X            return(BT_OK);
X        } else {
X            struct    bt_cache *lp;    /* new page to hold low keys */
X            struct    bt_cache *hp;    /* new page to hold hi keys */
X            off_t    savlft;        /* saved left sib page # */
X            off_t    npag;        /* new page # */
X
X            /* allocate new page for low keys */
X            if((npag = bt_newpage(b)) == BT_NULL)
X                goto bombout;
X
X            /* allocate new scratch page for low keys */
X            if((lp = bt_rpage(b,BT_NULL)) == NULL)
X                goto bombout;
X            /* allocate new scratch page for low keys */
X            if((hp = bt_rpage(b,BT_NULL)) == NULL)
X                goto bombout;
X
X            /* and do the thing */
X            bt_splpg(kp1,len,&ival,keyat,bt_pagesiz(b)/2,op->p,lp->p,hp->p,kp2,&len);
X
X
X            /* patch sibs */
X            LSIB(hp->p) = npag;
X            RSIB(hp->p) = RSIB(op->p);
X            LSIB(lp->p) = LSIB(op->p);
X            savlft = LSIB(op->p);
X            RSIB(lp->p) = ipag;
X
X            /* mark newly split pages as real */
X            lp->num = npag;
X            lp->flags = BT_CHE_DIRTY;
X            hp->num = ipag;
X            hp->flags = BT_CHE_DIRTY;
X
X            op->num = BT_NULL;
X
X            if(bt_wpage(b,op) == BT_ERR ||
X                bt_wpage(b,lp) == BT_ERR ||
X                bt_wpage(b,hp) == BT_ERR)
X                goto bombout;
X
X            /* patch right sib ptr of low pages left sib */
X            if(savlft != BT_NULL) {
X                if((op = bt_rpage(b,savlft)) == NULL)
X                    goto bombout;
X                RSIB(op->p) = npag;
X                op->flags = BT_CHE_DIRTY;
X                if(bt_wpage(b,op) == BT_ERR)
X                    goto bombout;
X            }
X
X            /* since we are not done, the new value */
X            /* ptr to insert at the next level is that */
X            /* of the new page we just allocated */
X            ival = npag;
X
X
X            /* if current page was root, make new root */
X            if(ipag == b->sblk.root) {
X                off_t    nr;
X
X                /* get new page # */
X                if((nr = bt_newpage(b)) == BT_NULL)
X                    goto bombout;
X
X                /* two scratch pages */
X                if((op = bt_rpage(b,BT_NULL)) == NULL)
X                    goto bombout;
X                if((lp = bt_rpage(b,BT_NULL)) == NULL)
X                    goto bombout;
X
X                /* prime empty root page */
X                LSIB(op->p) = RSIB(op->p) = BT_NULL;
X                KEYCNT(op->p) = 0;
X                KEYLEN(op->p) = 0;
X                HIPT(op->p) = ipag;
X
X                /* we already know where to insert */
X                bt_inspg(kp2,len,&npag,0,op->p,lp->p);
X
X                /* fix cache stuff and requeue */
X                op->num = BT_NULL;
X                lp->flags = BT_CHE_DIRTY;
X                lp->num = nr;
X
X
X                if(bt_wpage(b,lp) == BT_ERR ||
X                    bt_wpage(b,kp) == BT_ERR ||
X                    bt_wpage(b,op) == BT_ERR)
X                    goto bombout;
X
X                /* finally, sync up root */
X                b->sblk.root = nr;
X                b->sblk.levs++;
X                b->dirt++;
X                if(bt_wsuper(b) == BT_ERR)
X                    goto bombout;
X
X                /* mark all as well with tree */
X                bt_clearerr(b);
X
X                /* return - we are done */
X                return(BT_OK);
X            }
X        }
X
X        /* still going, pop stack level */
X        staklev--;
X        keyat = b->stack[staklev].ky;
X
X        /* current insert page is read from stack */
X        ipag = b->stack[staklev].pg;
X
X        if((op = bt_rpage(b,ipag)) == NULL)
X            goto bombout;
X
X        /* flip key buffer ptrs */
X        if(kp1 != kp->p) {
X            kp1 = kp->p;
X            kp2 = kp->p + DOALIGN(bt_pagesiz(b) / 2);
X        } else {
X            kp1 = kp->p + DOALIGN(bt_pagesiz(b) / 2);
X            kp2 = kp->p;
X        }
X    }
X
Xbombout:
X    /* if we reach this point, some fatal error has doubtless occurred */
X    /* try to bail out, though the tree is almost certainly toast */
X    if(op != NULL)
X        (void)bt_wpage(b,op);
X    if(kp != NULL)
X        (void)bt_wpage(b,kp);
X    return(BT_ERR);
X}
END_OF_FILE
if test 7136 -ne `wc -c <'b+tree/btlib/btinsert.c'`; then
    echo shar: \"'b+tree/btlib/btinsert.c'\" unpacked with wrong size!
fi
# end of 'b+tree/btlib/btinsert.c'
fi
if test -f 'b+tree/btlib/btintern.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btlib/btintern.h'\"
else
echo shar: Extracting \"'b+tree/btlib/btintern.h'\" \(4753 characters\)
sed "s/^X//" >'b+tree/btlib/btintern.h' <<'END_OF_FILE'
X#ifndef    _DEF_BT_INTERN_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/*
X    $Header: /atreus/mjr/hacks/btree/btlib/RCS/btintern.h,v 1.1 89/10/24 10:09:08 mjr Rel $
X    THIS SHOULD NOT BE INCLUDED BY USER-LEVEL PROGRAMS
X*/
X
X#define    BT_NULL    ((off_t)-1L)
X#define    BT_FREE    ((off_t)-2L)
X
X/* make life easier with function pointers */
Xtypedef    int    (*FUNCP)();
X
X/* cache flags - not needed by user code */
X#define    BT_CHE_CLEAN    0
X#define    BT_CHE_DIRTY    1
X#define    BT_CHE_LOCKD    2
X
X/* forward decls for internal funcs only */
Xextern    struct bt_cache *bt_rpage();
Xextern    off_t        bt_newpage();
Xextern    void        bt_inspg();
Xextern    void        bt_splpg();
X
X#ifndef    NO_BT_DEBUG
Xextern    void        bt_dump();
X#endif
X
X/*
Xminumum allowable page cache. since page sizes are variable,
Xthe cache is also used to provide buffers for insertion and
Xdeletion, or splitting. if there are not enough, nothing works
Xthis value was determined from intimate knowledge of the code
X*/
X#define    BT_MINCACHE    4
X
X
X/*
X Macros used in manipulating btree pages.
X
X this stuff is the machine specific part - if these macros are
X not right, you are guaranteed to know about it right away when
X this code is run. If you know exact values, you can plug them
X in directly, otherwise, we guess. getting it wrong will waste
X some space, is all. note that the off_ts are clustered at the
X beginning of the page, so that there is less likely to be a
X problem with the ints following. this may cause trouble in some
X odd architectures, and if so, fix it, and let me know.
X
X debugging a page is hard to do, by its very nature, and it is
X equally hard to build consistency checks into the code to
X validate pages as they are read and written. there is some
X code in bt_rpage() and bt_wpage() that looks for glaringly hosed
X pages, but if something gets past them, serious problems are
X sure to follow.
X
X    Don't even *THINK* about running this past "lint -h" !!!!!
X
X    These macros wind up nesting ~5 layers deep and get pretty
X    hairy. If your c-preprocessor is not gutsy enough, have fun
X    with the cut and paste !
X
X    Makeup of a page:
X    a page is an unstructured mess stuffed into a character buffer
X    with all locations being determined via pointer arithmetic.
X    this structure is loosely based on Zoellic and Folk's text
X    "File Structures: a conceptual toolkit". further, there is
X    no distinction between internal pages and leaf pages except
X    that the value in the high pointer will be BT_NULL
X
X    fields are (in order)
X    - how many -- data type (size) ---------value/description-----
X    1    |    off_t    |    page left sibling
X    1    |    off_t    |    page right sibling
X    1    |    off_t    |    page "high" (overflow) ptr
X    1    |    int    |    count of keys in page - keycnt
X    1    |    int    |    total length of keys in page
X    keycnt    |    int    |    length index (one per key)
X    keycnt    |    off_t    |    child/data ptrs (one per key)
X
X    Ideally, pages should be flagged depending on type, and if
X    the page contains fixed-size objects (structs, or ints, etc)
X    the length index should be left out, saving sizeof(int)
X    bytes/key, which would be susbstantial improvement. This is
X    an enhancement considered for release 2.0 if ever, or is
X    left as an exercise for the reader.
X
X    --mjr();
X*/
X
X/* alignment boundary for off_ts */
X#define    ALIGN    sizeof(off_t)
X/*
X#define    ALIGN    (sizeof(off_t)/sizeof(char))
X*/
X
X/*
Xthe actual alignments - the bit with the u_long may break on
Xsome systems. Whatever, it needs to be a size that can give a valid
Xmodulo operator on an address (Suns don't like modulo of pointers)
X*/
X#define    DOALIGN(s)    (s + (ALIGN - ((u_long)s % ALIGN)))
X
X/* page siblings */
X#define    LSIB(p)        (*(off_t *)(p))
X#define    RSIB(p)        (*(off_t *)(p + sizeof(off_t)))
X#define    HIPT(p)        (*(off_t *)(p + (2 * sizeof(off_t))))
X
X/* count of keys in page, stored in first integer value */
X#define    KEYCNT(p)    (*(int *)(p + (3 * sizeof(off_t))))
X
X/* length of keys in page, stored in second integer value */
X#define    KEYLEN(p)    (*(int *)(p + sizeof(int) + (3 * sizeof(off_t))))
X
X/* address of key string (pointer to char) */
X#define    KEYADR(p)    (p + (2 * sizeof(int)) + (3 * sizeof(off_t)))
X
X/* address of first (int) key index value */
X#define    KEYIND(p)    DOALIGN((KEYADR(p) + KEYLEN(p)))
X
X/* address of first (off_t) child pointer value */
X#define    KEYCLD(p)    (KEYIND(p) + (KEYCNT(p) * sizeof(int)))
X
X/* # of bytes used by page pointers, sibs, etc */
X#define PTRUSE        ((2 * sizeof(int)) + (4 * sizeof(off_t)))
X
X/* # of bytes used out of a page */
X#define KEYUSE(p)    ((KEYCNT(p) * (sizeof(off_t) + sizeof(int))) + PTRUSE + KEYLEN(p))
X
X#define    _DEF_BT_INTERN_H
X#endif
END_OF_FILE
if test 4753 -ne `wc -c <'b+tree/btlib/btintern.h'`; then
    echo shar: \"'b+tree/btlib/btintern.h'\" unpacked with wrong size!
fi
# end of 'b+tree/btlib/btintern.h'
fi
if test -f 'b+tree/btlib/btio.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btlib/btio.c'\"
else
echo shar: Extracting \"'b+tree/btlib/btio.c'\" \(8052 characters\)
sed "s/^X//" >'b+tree/btlib/btio.c' <<'END_OF_FILE'
X#include    <sys/types.h>
X#include    <sys/file.h>
X#include    <stdio.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/btio.c,v 1.1 89/10/24 10:08:59 mjr Rel $";
X#endif
X
Xextern    off_t    lseek();
X
X/*
X    all read/write operations are in this file, as well as cache
X    management stuff. the only exception to this is in btopen,
X    where we write an initial page if creating a tree
X
X    how caching is done in the btree routines: in case you care.
X    ------------------------------------------------------------
X    the bt_rpage and bt_wpage functions do NOT fill a buffer for
X    other btree functions to call - they return a pointer to a
X    filled cache buffer, which can be operated on and then written
X    back out. if an internal function requests page #BT_NULL, that
X    tells bt_rpage to just get the least recently used page, OR
X    any other scratch pages it has hanging around. preference is
X    to re-use a scribbled-on page rather than having to flush a
X    real page to disk and (possibly) have to read it right back.
X    a flag is raised to mark scratch page buffers as in use, since
X    there can be more than one page #BT_NULL and they are always
X    maintained at the least-recently used end of the queue.
X    writing is done just the opposite: if the page is not BT_NULL
X    the page may be synced to disk (depending on cache flags)
X    and will be re-inserted at the most-recently used end of the
X    cache. if the page IS BT_NULL, any misc. flags get cleared
X    (such as the 'this scratch page is in use' flag) and the
X    buffer is re-enqueued at the least-recently used.
X    the goal of all this stuff is to allow a calling function
X    to grab a page in a buffer, request 2 scratch pages, split the
X    first into the two scratches, mark the first (original) as
X    junk (since the page is now invalidated) and to 'write' it as
X    BT_NULL, while 'write'ing the 2 former scratch buffers as real
X    pages. All without doing a damn thing but juggling pointers.
X*/
X
X
Xbt_wsuper(b)
XBT_INDEX    *b;
X{
X    /* write a superblock to disk if and only if it is dirty */
X    /* keeps files opened O_RDONLY from choking up blood */
X    if(b->dirt &&
X        lseek(bt_fileno(b),0L,SEEK_SET) != 0L ||
X        write(bt_fileno(b),(char *)&b->sblk,sizeof(struct bt_super)) != sizeof(struct bt_super))
X            return(BT_ERR);
X    b->dirt = 0;
X
X    return(BT_OK);
X}
X
X
Xbt_sync(b)
XBT_INDEX    *b;
X{
X    struct    bt_cache *p1;
X
X    /* flip through the cache and flush any pages marked dirty to disk */
X
X    for(p1 = b->lru; p1 != NULL;) {
X        if(p1->flags == BT_CHE_DIRTY && p1->num != BT_NULL) {
X            if(lseek(bt_fileno(b),p1->num,SEEK_SET) != p1->num ||
X                write(bt_fileno(b),(char *)p1->p,bt_pagesiz(b)) != bt_pagesiz(b))
X                return(BT_ERR);
X        }
X        p1 = p1->next;
X    }
X    return(BT_OK);
X}
X
X
Xstatic void
Xbt_requeue(b,p)
XBT_INDEX    *b;
Xstruct bt_cache    *p;
X{
X    /* re-assign the cache buffer to a new (or possibly the same) */
X    /* location in the queue. buffers that have been stolen for */
X    /* scrap will have a BT_NULL number, and should just go at the */
X    /* least-recently used part of the cache, since they are junk. */
X    /* buffers with legit values get moved to the most-recently. */
X    /* this could all be inlined where appropriate, but gimme a */
X    /* break! call it, uh, modular programming. this is still */
X    /* plenty quick, I expect. */
X
X    /* if the element is where it already belongs, waste no time */
X    if((p->num == BT_NULL && p == b->lru) ||
X        (p->num != BT_NULL && p == b->mru))
X            return;
X
X    /* unlink */
X    if(p->prev != NULL)
X        p->prev->next = p->next;
X    if(p->next != NULL)
X        p->next->prev = p->prev;
X    if(p == b->lru)
X        b->lru = p->next;
X    if(p == b->mru)
X        b->mru = p->prev;
X
X    /* relink depending on number of page this buffer contains */
X    if(p->num == BT_NULL) {
X        b->lru->prev = p;
X        p->next = b->lru;
X        p->prev = NULL;
X        b->lru = p;
X    } else {
X        b->mru->next = p;
X        p->prev = b->mru;
X        p->next = NULL;
X        b->mru = p;
X    }
X}
X
X
Xstruct bt_cache *
Xbt_rpage(b,num)
XBT_INDEX    *b;
Xoff_t        num;
X{
X    struct bt_cache    *p;
X
X    /* sanity check - only BT_NULL is allowed to be a page less */
X    /* than 0 and no pages are allowed to be read past EOF. */
X    if(num == 0L || num >= b->sblk.high || (num < 0L && num != BT_NULL) || (num != BT_NULL && (num % bt_pagesiz(b)) != 0)) {
X        bt_errno(b) = BT_PTRINVAL;
X        return(NULL);
X    }
X
X    /* scan the cache for the desired page. if it is not there, */
X    /* load the desired stuff into the lru. if the requested page */
X    /* is BT_NULL we could probably cheat by just using the lru, */
X    /* but keeping the code smaller and cleaner is probably nicer */
X    for(p = b->mru; p != NULL; p = p->prev) {
X
X        /* if the page number matches and the buffer is not */
X        /* marked as an allocated scratch buffer, return it */
X        if(num == p->num && p->flags != BT_CHE_LOCKD) {
X            /* if it is a scratch buffer, lock it */
X            if(p->num == BT_NULL)
X                p->flags = BT_CHE_LOCKD;
X
X            /* recache the page (moves it to mru) */
X            bt_requeue(b,p);
X            return(p);
X        }
X    }
X
X    /* obviously, we didnt find it, so flush the lru and read */
X    /* one complication is to make sure we dont clobber allocated */
X    /* scratch page buffers. we have to seek backwards until we */
X    /* get a page that is not locked */
X    for(p = b->lru; p != NULL; p = p->next)
X        if(p->flags != BT_CHE_LOCKD)
X            break;
X
X    /* sanity check */
X    if(p == NULL) {
X        bt_errno(b) = BT_NOBUFFERS;
X        return(NULL);
X    }
X
X    /* flush if the page is dirty and not a scratch buffer */
X    if(p->num != BT_NULL && p->flags == BT_CHE_DIRTY) {
X        if(lseek(bt_fileno(b),p->num,SEEK_SET) != p->num ||
X            write(bt_fileno(b),(char *)p->p,bt_pagesiz(b)) != bt_pagesiz(b))
X            return(NULL);
X    }
X
X    /* read new data if not a scratch buffer */
X    if(num != BT_NULL) {
X        int    ku;
X
X        if(lseek(bt_fileno(b),num,SEEK_SET) != num ||
X            read(bt_fileno(b),(char *)p->p,bt_pagesiz(b)) != bt_pagesiz(b))
X            return(NULL);
X        p->flags = BT_CHE_CLEAN;
X        p->num = num;
X
X        /* sanity check */
X        ku = KEYUSE(p->p);
X        if(ku > bt_pagesiz(b) || ku < 0 || KEYLEN(p->p) < 0) {
X            bt_errno(b) = BT_BADPAGE;
X            return(NULL);
X        }
X    } else {
X        p->flags = BT_CHE_LOCKD;
X        p->num = BT_NULL;
X    }
X
X    bt_requeue(b,p);
X    return(p);
X}
X
X
X
Xbt_wpage(b,p)
XBT_INDEX    *b;
Xstruct bt_cache    *p;
X{
X
X    if(p->num != BT_NULL) {
X        int    ku;
X
X        /* sanity check */
X        ku = KEYUSE(p->p);
X        if(ku > bt_pagesiz(b) || ku < 0 || KEYLEN(p->p) < 0) {
X            bt_errno(b) = BT_BADPAGE;
X            return(BT_ERR);
X        }
X
X        if(b->cflg != BT_RWCACHE && p->flags == BT_CHE_DIRTY) {
X            if(lseek(bt_fileno(b),p->num,SEEK_SET) != p->num ||
X                write(bt_fileno(b),(char *)p->p,bt_pagesiz(b)) != bt_pagesiz(b))
X                return(BT_ERR);
X            p->flags = BT_CHE_CLEAN;
X        }
X    } else {
X        /* unlock scratch buffer */
X        p->flags = BT_CHE_CLEAN;
X    }
X
X    bt_requeue(b,p);
X    return(BT_OK);
X}
X
X
X
Xbt_freepage(b,pag)
XBT_INDEX    *b;
Xoff_t        pag;
X{
X    /* simple free page management is done with a linked */
X    /* list linked to the left sibling of each page */
X    struct    bt_cache *p;
X
X    if((p = bt_rpage(b,pag)) == NULL)
X        return(BT_ERR);
X
X    LSIB(p->p) = b->sblk.free;
X
X    /* note - this value is SET but never checked. Why ? because the */
X    /* in-order insert can't be bothered to reset all the free pointers */
X    /* in the free list. this could be useful, however, if someone ever */
X    /* writes a tree-patcher program, or something like that. */
X    HIPT(p->p) = BT_FREE;
X
X    p->flags = BT_CHE_DIRTY;
X    if(bt_wpage(b,p) == BT_ERR)
X        return(BT_ERR);
X
X    b->sblk.free = pag;
X    b->dirt = 1;
X    return(bt_wsuper(b));
X}
X
X
Xoff_t
Xbt_newpage(b)
XBT_INDEX    *b;
X{
X    off_t    ret = BT_NULL;
X    struct    bt_cache *p;
X
X    if(b->sblk.free == BT_NULL) {
X        ret = b->sblk.high;
X        b->sblk.high += bt_pagesiz(b);
X    } else {
X        if((p = bt_rpage(b,b->sblk.free)) != NULL) {
X            ret = b->sblk.free;
X            b->sblk.free = LSIB(p->p);
X        } else {
X            return(BT_NULL);
X        }
X    }
X    b->dirt = 1;
X    if(bt_wsuper(b) == BT_ERR)
X        return(BT_ERR);
X    return(ret);
X}
END_OF_FILE
if test 8052 -ne `wc -c <'b+tree/btlib/btio.c'`; then
    echo shar: \"'b+tree/btlib/btio.c'\" unpacked with wrong size!
fi
# end of 'b+tree/btlib/btio.c'
fi
if test -f 'b+tree/btlib/btoopen.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btlib/btoopen.c'\"
else
echo shar: Extracting \"'b+tree/btlib/btoopen.c'\" \(4634 characters\)
sed "s/^X//" >'b+tree/btlib/btoopen.c' <<'END_OF_FILE'
X#include    <sys/types.h>
X#include    <sys/file.h>
X#include    <sys/stat.h>
X#include    <varargs.h>
X#include    <stdio.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/btoopen.c,v 1.1 89/10/24 10:09:01 mjr Rel $";
X#endif
X
X/*    this way of handling opening and configuration is probably    */
X/*    unnecessarily large and awkward, but I think it gives a pretty    */
X/*    high degree of #ifdefability to make it portable across OS     */
X/*    types, as well as giving a lot of flexibility for those who    */
X/*    never trust default options.                     */
X
Xextern    char    *malloc();
Xextern    off_t    lseek();
X
X
XBT_INDEX    *
Xbt_optopen(va_alist)
Xva_dcl
X{
X    va_list        ap;
X    BT_INDEX    *ret;
X    struct bt_cache *cp1;
X    struct bt_cache *cp2;
X    int        dtyp = BT_DFLTDTYPE;
X    int        csiz = BT_DFLTCACHE;
X    int        cflg = BT_DFLTCFLAG;
X    int        psiz = BT_DFLTPSIZ;
X    int        operm = S_IREAD|S_IWRITE;
X    int        omode = O_RDWR;
X    off_t        magic = BT_DFLTMAGIC;
X    bt_chrp        labp = NULL;
X    int        labl;
X    int        r;
X    char        *path = NULL;
X
X    if((ret = (BT_INDEX *)malloc(sizeof(BT_INDEX))) == NULL)
X        return(NULL);
X
X    /* clear error */
X    bt_errno(ret) = BT_NOERROR;
X
X    /* zero this just in case */
X    bt_cmpfn(ret) = 0;
X
X    va_start(ap);
X    while((r = va_arg(ap,int)) != 0) {
X        switch(r) {
X            case    BT_PATH:
X                path = va_arg(ap,char *);
X                break;
X
X            case    BT_PSIZE:
X                psiz = va_arg(ap,int);
X                if(psiz < sizeof(struct bt_super))
X                    psiz = sizeof(struct bt_super);
X                break;
X
X            case    BT_CACHE:
X                csiz = va_arg(ap,int);
X                if(csiz < 0)
X                    csiz = 0;
X                break;
X
X            case    BT_CFLAG:
X                cflg = va_arg(ap,int);
X                break;
X
X            case    BT_OMODE:
X                omode = va_arg(ap,int) | O_RDWR;
X                break;
X
X            case    BT_OPERM:
X                operm = va_arg(ap,int);
X                break;
X
X            case    BT_MAGIC:
X                magic = va_arg(ap,off_t);
X                break;
X
X            case    BT_LABEL:
X                labp = va_arg(ap,bt_chrp);
X                labl = va_arg(ap,int);
X                break;
X
X            case    BT_DTYPE:
X                dtyp = va_arg(ap,int);
X                /* next arg BETTER be a valid funcp ! */
X                if(dtyp == BT_USRDEF)
X                    bt_cmpfn(ret) = va_arg(ap,FUNCP);
X                break;
X
X            default:
X                goto bombout;
X        }
X    }
X
X    if(path == NULL || (bt_fileno(ret) = open(path,omode,operm)) < 0)
X        goto bombout;
X
X    r = read(bt_fileno(ret),(char *)&ret->sblk,sizeof(struct bt_super));
X
X    /* failure to read anything - initialize tree */
X    if(r == 0) {
X        char    *jnk;
X        if((jnk = malloc((unsigned)psiz)) != NULL) {
X            ret->sblk.magic = magic;
X            bt_pagesiz(ret) = psiz;
X            bt_dtype(ret) = dtyp;
X            ret->sblk.levs = 1;
X            ret->sblk.root = (off_t)psiz;
X            ret->sblk.free = BT_NULL;
X            ret->sblk.high = (off_t)(2 * psiz);
X
X            /* mark super block as dirty and sync */
X            ret->dirt = 1;
X
X            /* write and pretend we read a legit superblock */
X            if(bt_wsuper(ret) == BT_OK)
X                r = sizeof(struct bt_super);
X
X            /* now make jnk into an empty first page */
X            KEYCNT(jnk) = 0;
X            KEYLEN(jnk) = 0;
X            LSIB(jnk) = RSIB(jnk) = BT_NULL;
X            HIPT(jnk) = BT_NULL;
X
X            /* now, since the cache is not set up yet, we */
X            /* must directly write the page. */
X            if(lseek(bt_fileno(ret),(off_t)psiz,SEEK_SET) != (off_t)psiz ||
X                write(bt_fileno(ret),jnk,psiz) != psiz)
X                r = 0;
X            (void)free(jnk);
X        }
X    }
X
X    /* yet another sanity check */
X    if(r != sizeof(struct bt_super) || ret->sblk.magic != magic)
X        goto bombout;
X
X    /* label it if we are supposed to */
X    if(labp && bt_wlabel(ret,labp,labl) == BT_ERR)
X        goto bombout;
X
X    /* initialize locator stack */
X    ret->shih = ret->sblk.levs + 2;
X    ret->stack = (struct bt_stack *)malloc((unsigned)(ret->shih * sizeof(struct bt_stack)));
X    if(ret->stack == NULL)
X        goto bombout;
X
X    /* initialize cache */
X    cp2 = ret->lru = NULL;
X    csiz += BT_MINCACHE;
X
X    /* just in case some bonehead asks for tons of unused cache */
X    if(cflg == BT_NOCACHE)
X        csiz = BT_MINCACHE;
X
X    while(csiz--) {
X        cp1 = (struct bt_cache *)malloc(sizeof(struct bt_cache));
X        if(cp1 == NULL)
X            goto bombout;
X
X        if(ret->lru == NULL)
X            ret->lru = cp1;
X        cp1->prev = cp2;
X        cp1->num = BT_NULL;
X        cp1->next = NULL;
X        cp1->flags = BT_CHE_CLEAN;
X        if((cp1->p = (bt_chrp)malloc((unsigned)bt_pagesiz(ret))) == NULL)
X            goto bombout;
X        if(cp2 != NULL)
X            cp2->next = cp1;
X
X        cp2 = cp1;
X    }
X    ret->mru = cp1;
X
X    /* set cache type flag */
X    ret->cflg = cflg;
X
X    /* no valid current key */
X    ret->cpag = BT_NULL;
X
X    /* all is well */
X    return(ret);
X
Xbombout:
X    (void)bt_close(ret);
X    return(NULL);
X}
END_OF_FILE
if test 4634 -ne `wc -c <'b+tree/btlib/btoopen.c'`; then
    echo shar: \"'b+tree/btlib/btoopen.c'\" unpacked with wrong size!
fi
# end of 'b+tree/btlib/btoopen.c'
fi
if test -f 'b+tree/btlib/btpage1.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/btlib/btpage1.c'\"
else
echo shar: Extracting \"'b+tree/btlib/btpage1.c'\" \(5063 characters\)
sed "s/^X//" >'b+tree/btlib/btpage1.c' <<'END_OF_FILE'
X#include    <sys/types.h>
X
X#include    <stdio.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/b+tree/btlib/RCS/btpage1.c,v 1.1 89/10/24 10:09:02 mjr Rel $";
X#endif
X
Xbt_srchpg(k,kl,dtyp,cmpf,ptr,num,s)
Xbt_chrp    k;
Xint    kl;
Xint    dtyp;
XFUNCP    cmpf;
Xoff_t    *ptr;
Xint    *num;
Xbt_chrp    s;
X{
X    int    lo = 0, m, hi;        /* low, mid, high ptrs for binsrch */
X    int    *ip;            /* offset/beginning of key index */
X    off_t    *cl;            /* offset/beginning of child index */
X    bt_chrp    cp;            /* offset/beginning of keys */
X    REGISTER int    cmpval;        /* returned value of comparison */
X    REGISTER bt_chrp    kp1;    /* tmp key pointer */
X    REGISTER bt_chrp    kp2;
X    REGISTER int    l1;        /* key lengths */
X    REGISTER int    l2;
X
X    /* this value is decremented by one to keep from */
X    /* looking past the top of the key list */
X    hi = KEYCNT(s) - 1;
X
X    /* save effort if this is an empty page */
X    /* also saves from binary search where hi < lo! */
X    if(KEYCNT(s) == 0) {
X        *num = 0;
X        *ptr = HIPT(s);
X        return(BT_NF);
X    }
X
X    /* beginning of key index */
X    ip = (int *)KEYIND(s);
X
X    /* beginning of key string */
X    cp = KEYADR(s);
X
X    /* beginning of the child pointers */
X    cl = (off_t *)KEYCLD(s);
X
X    /* hold onto your cerebellums, folks !! */
X    while(lo <= hi) {
X
X        /* if the first key is the one we want, its length */
X        /* is not calculated using the subtracted offsets, */
X        /* but is rather calculated by using the offset */
X        /* to the beginning of key #2, which starts where */
X        /* the first key ends, by definition */
X
X        /* actual comparison is done over len bytes from */
X        /* the offset that is extracted out of the index */
X
X        /* set up pointers for the compare */
X        kp1 = k;
X        l1 = kl;
X        if((m = (lo + hi) >> 1) == 0) {
X            kp2 = cp;
X            l2 = *ip;
X        } else {
X            kp2 = cp + *(ip + m - 1);
X            l2 = (*(ip + m) - *(ip + (m - 1)));
X        }
X
X        /* do the compare based on data type */
X        if(dtyp == BT_STRING) {
X                while(l1 != 0 && l2 != 0) {
X                    if(*kp1 != *kp2) {
X                        cmpval = *kp1 - *kp2;
X                        goto endcmp;
X                    }
X                    kp1++;
X                    kp2++;
X                    l1--;
X                    l2--;
X                }
X
X                if(l1 != l2)
X                    cmpval = l1 - l2;
X                else
X                    cmpval = 0;
X        } else if(dtyp == BT_INT) {
X                cmpval = *(int *)kp1 - *(int *)kp2;
X        } else if(dtyp == BT_LONG) {
X                cmpval = *(long *)kp1 - *(long *)kp2;
X        } else if(dtyp == BT_FLOAT) {
X                cmpval = 0;
X                 if(*(float *)kp1 > *(float *)kp2)
X                    cmpval = 1;
X                else
X                    if(*(float *)kp1 < *(float *)kp2)
X                        cmpval = -1;
X        } else if(dtyp == BT_USRDEF) {
X            if(cmpf == 0)
X                return(BT_ERR);
X            cmpval = (*cmpf)(kp1,l1,kp2,l2);
X        } else
X            return(BT_ERR);
Xendcmp:
X        if(cmpval < 0) {
X            hi = m - 1;
X            *num = m;
X        } else {
X            if(cmpval > 0) {
X                lo = m + 1;
X                *num = m + 1;
X            } else {
X                /* return current key # in num */
X                *num = m;
X                *ptr = *(cl + m);
X                return(BT_OK);
X            }
X        }
X    }
X
X    if(*num == KEYCNT(s))
X        *ptr = HIPT(s);
X    else
X        *ptr = *(cl + *num);
X    return(BT_NF);
X}
X
X
Xvoid
Xbt_inspg(key,len,ptr,at,in,out)
Xbt_chrp    key;
Xint    len;
Xoff_t    *ptr;
Xint    at;
Xbt_chrp    in;
Xbt_chrp    out;
X{
X    REGISTER int    *iin;        /* index/length ptr to old page */
X    REGISTER int    *iout;        /* index/length ptr to new page */
X    REGISTER off_t    *lin;        /* child ptr to old page */
X    REGISTER off_t    *lout;        /* child ptr to new page */
X    REGISTER bt_chrp    kin;        /* key ptr to old page */
X    REGISTER bt_chrp    kout;        /* key ptr to new page */
X    REGISTER int    t;        /* iterator */
X    int    iky;            /* key number in old page */
X    int    oky;            /* key number in new page */
X    int    copied = 0;        /* used as flag AND shift of lengths */
X
X    /* fix key count in new page */
X    KEYCNT(out) = KEYCNT(in) + 1;
X
X    /* fix key length in new page */
X    KEYLEN(out) = KEYLEN(in) + len;
X
X    /* left and right sibs */
X    LSIB(out) = LSIB(in);
X    RSIB(out) = RSIB(in);
X
X    /* and high pointer */
X    HIPT(out) = HIPT(in);
X
X    /* set the key start pointers, index and child pointers */
X    kin = KEYADR(in);
X    kout = KEYADR(out);
X
X    iin = (int *)KEYIND(in);
X    iout = (int *)KEYIND(out);
X
X    lin = (off_t *)KEYCLD(in);
X    lout = (off_t *)KEYCLD(out);
X
X    for(oky = iky = 0; oky < KEYCNT(out); oky++) {
X
X        /* insert the key at this point in the page */
X        /* copied is used later to calculate lenght offsets */
X        if(at == iky && copied == 0) {
X
X            /* copy the key into the key space */
X            for(t = 0; t < len; t++)
X                *kout++ = *key++;
X
X            /* fix up index lengths if key is first out */
X            if(oky == 0)
X                *iout = len;
X            else
X                *iout = *(iout - 1) + len;
X
X            iout++;
X
X            /* offset any more index lengths by this much */
X            copied = len;
X
X            /* copy ptrs */
X            *lout++ = *ptr;
X
X        } else {
X            if(iky == 0)
X                for(t = 0; t < *iin; t++)
X                    *kout++ = *kin++;
X            else
X                for(t = 0; t < (*iin - *(iin - 1)); t++)
X                    *kout++ = *kin++;
X            iky++;
X            *iout++ = *iin + copied;
X            iin++;
X            *lout++ = *lin++;
X        }
X    }
X    lout--;
X}
END_OF_FILE
if test 5063 -ne `wc -c <'b+tree/btlib/btpage1.c'`; then
    echo shar: \"'b+tree/btlib/btpage1.c'\" unpacked with wrong size!
fi
# end of 'b+tree/btlib/btpage1.c'
fi
if test -f 'b+tree/doc/btdbm.3' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/doc/btdbm.3'\"
else
echo shar: Extracting \"'b+tree/doc/btdbm.3'\" \(5510 characters\)
sed "s/^X//" >'b+tree/doc/btdbm.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/btdbm.3,v 1.2 89/10/23 18:31:00 mjr Rel $
X.\"
X.TH BTDBM 3 "18 October 1989"
X.SH NAME
Xbtdbm \- ndbm-like library with a b+tree index
X.SH SYNOPSIS
X.B #include <sys/types.h>
X.br
X.B #include <btdbm.h>
X.sp
X.LP
X.B "int btdbm_close(db)"
X.br
X.B "BTDBM *db;"
X.LP
X.B "int btdbm_delete(db,key)"
X.br
X.B "BTDBM *db;"
X.br
X.B "btdatum key;"
X.LP
X.B "btdatum btdbm_fetch(db,key)"
X.br
X.B "BTDBM *db;"
X.br
X.B "btdatum key;"
X.LP
X.B "btdatum btdbm_firstkey(db)"
X.br
X.B "BTDBM *db;"
X.LP
X.B "btdatum btdbm_nextkey(db)"
X.br
X.B "BTDBM *db;"
X.LP
X.B "BTDBM *btdbm_open(path,type,flags,mode)"
X.br
X.B "char *path;"
X.br
X.B "int type; /* from btree.h b+tree types */"
X.br
X.B "int flags;"
X.br
X.B "int mode;"
X.LP
X.B "int btdbm_store(db,key,data,flag)"
X.br
X.B "BTDBM *db;"
X.br
X.B "btdatum key;"
X.br
X.B "btdatum data;"
X.br
X.B "int flag;"
X.SH DESCRIPTION
X.LP
XThe
X.B btdbm
Xlibrary is a rough emulation of the
X.B "ndbm(3)"
Xlibrary built on top of the
X.B "b+tree(3)"
Xand
X.B "store(3)"
Xlibraries. The functions are intended to be as close to plug-compatible as
Xpossible, except for the
X.B btdbm_open
Xfunction, which requires a data type flag to maintain order of the keys.
XUnlike the hash table library, the
X.B btdbm
Xallows ordered access of the data by key, however the performance of the
X.B btdbm
Xlibrary will be inferior to that of the
X.B "ndbm(3)"
Xlibrary, due to both the speed of hash tables, and the fact that the
X.B "store(3)"
Xlibrary is not optimized for speed. The typedef
X.B btdatum
Xis provided, which is analogous to the
X.B dbm
X.B datum
Xtypedef.
X.SH FUNCTIONS
X.LP
X.B "int btdbm_close(db)"
X.br
XThis function closes and deallocates a
X.B BTDBM
Xpointer, closing the storage file and b+tree index.
X.LP
X.B "int btdbm_delete(db,key)"
X.br
XThis function deletes the key from the database.
X.LP
X.B "btdatum btdbm_fetch(db,key)"
X.bt
XThis function looks up the datum stored under
X.B key
Xand returns the result in a
X.B btdatum.
XIf the key is not located in the tree, the value
X.B "btdatum.size"
Xof the returned datum will be zero.
X.LP
X.B "btdatum btdbm_firstkey(db)"
X.br
XThis function returns the first data record from the database, in sort
Xorder according to the type of data stored in the b+tree index.
X.LP
X.B "btdatum btdbm_nextkey(db)"
X.br
XThis function returns the next key in order from the database. The next
Xkey will be the key following either the key returned from the last call
Xto
X.B btdbm_firstkey,
Xor
X.B btdbm_fetch.
X.LP
X.B "BTDBM *btdbm_open(path,type,flags,mode)"
X.br
XThis function opens a database and index. The file name is specified
Xin
X.B path
Xwith the data file automatically having a \fB".dat"\fR extension added,
Xand the b+tree index having a \fB".ndx"\fR added. The value in
X.B type
Xis passed to the underlying b+tree to indicate the type of key used
Xfor sorting. It must be one of:
X.B BT_STRING,
X.B BT_INT,
X.B BT_LONG,
X.B BT_FLOAT.
XThe
X.B flags
Xargument is passed to
X.B "open(2)"
Xand the
X.B mode
Xargument is used as the creation mode for the file, if it does not
Xalready exist.
X.LP
X.B "int btdbm_store(db,key,data,flag)"
X.br
XThis function stores the data in
X.B data
Xkeyed with the datum in
X.B key.
XIf the value of
X.B flag
Xis
X.B BTDBM_INSERT
Xand the key already exists, and error is returned. If the value of
X.B flag
Xis
X.B BTDBM_REPLACE
Xany existing data stored under
X.B key
Xis overwritten with the new data.
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) btdbm_error(db)"
X.br
Xpoints to the error number associated with the database.
X.LP
X.B "(void) btdbm_clearerror(db)"
X.br
Xclears any error number associated with the database.
X.LP
X.B "(BT_INDEX *) btdbm_btree(db)"
X.br
XPoints to the underlying b+tree handle used to store the keys. See
X.B "b+tree(3)".
X.LP
X.B "(STORE *) btdbm_storefile(db)"
X.br
XPoints to the underlying store file handle used to store the data. See
X.B "store(3)".
X.SH "SEE ALSO"
X.LP
X.B "ndbm(3)"
X.br
X.B "b+tree(3)"
X.br
X.B "store(3)"
X.SH DIAGNOSTICS
X.LP
XThe value
X.B 0
Xis returned whenever a function is successful.
X.LP
XThe value
X.SM
X.B 1
Xis returned to indicate some form of failure in any operation.
XThere is no provision for a more complete means of returning
Xerror codes, however, the error values in the store file and
Xb+tree can be accessed through their respective pointers using
X.B btdbm_btree
Xand
X.B btdbm_storefile.
X.LP
XA failed call to
X.B btdbm_open
Xreturns NULL. Failed calls to the functions that return a
Xbtdatum return a btdatum with size value set equal to zero.
X.SH BUGS
X.SH LIMITATIONS
X.LP
XData stored under a key can be arbitrarily large, subject to the limits
Xof the underlying store file. Since the store file's internal buffer will
Xstretch to accomodate large data, reasonably large amounts of data can
Xbe successfully stored and retrieved fairly efficiently. Keys stored in
Xthe b+tree index are subject to limits in the b+tree library. An individual
Xkey cannot be longer than permitted by the underlying page size of the
Xb+tree (typically a fairly large value).
X.SH AUTHOR
X.LP
XMarcus J. Ranum
END_OF_FILE
if test 5510 -ne `wc -c <'b+tree/doc/btdbm.3'`; then
    echo shar: \"'b+tree/doc/btdbm.3'\" unpacked with wrong size!
fi
chmod +x 'b+tree/doc/btdbm.3'
# end of 'b+tree/doc/btdbm.3'
fi
if test -f 'b+tree/utils/dbtest.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'b+tree/utils/dbtest.c'\"
else
echo shar: Extracting \"'b+tree/utils/dbtest.c'\" \(5674 characters\)
sed "s/^X//" >'b+tree/utils/dbtest.c' <<'END_OF_FILE'
X#include    <stdio.h>
X#include    <ctype.h>
X#include    <sys/types.h>
X#include    <sys/file.h>
X#include    "btdbm.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/dbtest.c,v 1.1 89/10/24 10:09:28 mjr Rel $";
X#endif
X
X
XBTDBM    *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_store(), do_fetch(), do_delete(), do_first();
Xvoid do_next();
X
Xvoid    enargv();    /* function to parse user args into strings */
Xvoid    doit();        /* dispatch function */
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 = "btdbmtest-> ";
X
X/* command dispatch table */
Xstruct    cmd    cmds[] = {
X"close",    "close",            do_close,    1,    1,
X"delete",    "delete key",            do_delete,    2,    0,
X"fetch",    "fetch key",            do_fetch,    2,    0,
X"first",    "first",            do_first,    1,    0,
X"next",        "next",                do_next,    1,    0,
X"open",        "open database",        do_open,    2,    0,
X"quit",        "quit",                do_quit,    1,    0,
X"store",    "store key data",        do_store,    3,    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 = btdbm_open(globargv[1],BT_STRING,O_CREAT,0600);
X
X    if(globf == NULL) {
X        (void)printf("error opening database");
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(btdbm_close(globf)) {
X            (void)printf("error closing\n");
X        } else {
X            (void)printf("closed OK\n");
X            globf = NULL;
X        }
X    } else {
X        (void)printf("nothing open\n");
X    }
X}
X
X
Xvoid
Xdo_quit()
X{
X    if(globf != NULL) {
X        (void)printf("closing %s\n",globname);
X        if(btdbm_close(globf)) {
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_store()
X{
X    btdatum    key;
X    btdatum    data;
X
X    key.dptr = (bt_chrp)globargv[1];
X    key.dsize = strlen(globargv[1]);
X
X    data.dptr = (bt_chrp)globargv[2];
X    data.dsize = strlen(globargv[2]) + 1;
X
X    if(btdbm_store(globf,key,data,BTDBM_REPLACE))
X        printf("could not store\n");
X}
X
X
Xvoid
Xdo_fetch()
X{
X    btdatum    key;
X    btdatum    data;
X
X    key.dptr = (bt_chrp)globargv[1];
X    key.dsize = strlen(globargv[1]);
X
X    data = btdbm_fetch(globf,key);
X    if(data.dptr == 0)
X        printf("could not fetch\n");
X    else
X        printf("%s\n",data.dptr);
X}
X
X
Xvoid
Xdo_delete()
X{
X    btdatum    key;
X
X    key.dptr = (bt_chrp)globargv[1];
X    key.dsize = strlen(globargv[1]);
X
X    if(btdbm_delete(globf,key) != 0)
X        printf("could not delete\n");
X    else
X        printf("deleted.\n");
X}
X
X
Xvoid
Xdo_first()
X{
X    btdatum    key;
X
X    key = btdbm_firstkey(globf);
X    if(key.dsize == 0)
X        printf("no first key\n");
X    else
X        printf("%s\n",key.dptr);
X}
X
X
Xvoid
Xdo_next()
X{
X    btdatum    key;
X
X    key = btdbm_nextkey(globf);
X    if(key.dsize == 0)
X        printf("no next key\n");
X    else
X        printf("%s\n",key.dptr);
X}
END_OF_FILE
if test 5674 -ne `wc -c <'b+tree/utils/dbtest.c'`; then
    echo shar: \"'b+tree/utils/dbtest.c'\" unpacked with wrong size!
fi
# end of 'b+tree/utils/dbtest.c'
fi
echo shar: End of archive 3 \(of 5\).
cp /dev/null ark3isdone
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