v17i039: bplus - B+ Tree Library, Part01/02
Bill Davidsen
davidsen at crdos1.crd.ge.com
Sat Mar 16 07:25:29 AEST 1991
Submitted-by: Bill Davidsen <davidsen at crdos1.crd.ge.com>
Posting-number: Volume 17, Issue 39
Archive-name: bplus/part01
This is a freely distributable shareware B+ tree library from Hunter and
Associates. I have corrected bugs, eliminated portability problems, and
made it UNIX compatible. See the read.me for details.
Bill
--------
#!/bin/sh
# shar: Shell Archiver (v1.29)
#
# This is part 1 of a multipart archive
# do not concatenate these parts, unpack them in order with /bin/sh
#
# Run the following text with /bin/sh to create:
# bplus.c
# find1stkey.c
# filelen.c
# memmove.c
# read.me
# bplus.doc
# bplus.h
# makefile
# ndb.c
# lookup.c
# names.c
#
if test -r s2_seq_.tmp
then echo "Must unpack archives in sequence!"
next=`cat s2_seq_.tmp`; echo "Please unpack part $next next"
exit 1; fi
echo "x - extracting bplus.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > bplus.c &&
X/********************************************************************/
X/* */
X/* BPLUS file indexing program - Version 1.1 */
X/* */
X/* A "shareware program" */
X/* */
X/* */
X/* Copyright (C) 1987 by */
X/* */
X/* Hunter and Associates */
X/* 7050 NW Zinfandel Lane */
X/* Corvallis, Oregon 97330 */
X/* (503) 745 - 7186 */
X/* */
X/********************************************************************/
X
X
X#include <stdio.h>
X#include <fcntl.h>
X#ifdef MSC
X#include <io.h>
X#endif
X#include <sys/types.h> /* delete this line for Turbo C */
X#include <sys/stat.h>
X#include <string.h>
X#include "bplus.h"
X
X
X/* macros, constants, data types */
X
X#define NULLREC (-1L)
X#define FREE_BLOCK (-2)
X
X#define ENT_ADR(pb,off) ((ENTRY*)((char*)((pb)->entries) + off))
X#define ENT_SIZE(pe) strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
X#define BUFDIRTY(j) (mci->cache[j].dirty)
X#define BUFHANDLE(j) (mci->cache[j].handle)
X#define BUFBLOCK(j) (mci->cache[j].mb)
X#define BUFCOUNT(j) (mci->cache[j].count)
X#define CB(j) (pci->pos[j].cblock)
X#define CO(j) (pci->pos[j].coffset)
X
X
X /* ATTENTION MICROSOFT USERS */
X /* Microsoft changed the memcpy */
X /* library routine in the C 5.0 */
X /* compiler. The following macro */
X /* must be used for Microsoft 5.0 */
X /* and the Quick C compiler. */
X
X#if 1
X#define memcpy (void) memmove
X#endif /* if not needed */
X
X/* declare some global variables */
X
XIX_DESC *pci;
XIX_BUFFER bt_buffer;
XIX_BUFFER *mci = &bt_buffer;
XBLOCK *block_ptr;
XBLOCK *spare_block;
Xint cache_ptr = 0;
Xint cache_init = 0;
Xint split_size = IXB_SPACE;
Xint comb_size = (IXB_SPACE/2);
X
X/* ================ internal procedures ================ */
Xstatic void pascal error Param((int, long));
Xstatic void pascal read_if Param((RECPOS, char *, int));
Xstatic void pascal write_if Param((int, RECPOS, char *, int));
Xstatic int pascal creat_if Param((char *));
Xstatic int pascal open_if Param((char *));
Xstatic void pascal close_if Param((int));
Xstatic void pascal update_block Param((void));
Xstatic void pascal init_cache Param((void));
Xstatic int pascal find_cache Param((RECPOS));
Xstatic int pascal new_cache Param((void));
Xstatic void pascal load_cache Param((RECPOS));
Xstatic void pascal get_cache Param((RECPOS));
Xstatic void pascal retrieve_block Param((int, RECPOS));
Xstatic int pascal prev_entry Param((int));
Xstatic int pascal next_entry Param((int));
Xstatic void pascal copy_entry Param((ENTRY *, ENTRY *));
Xstatic int pascal scan_blk Param((int));
Xstatic int pascal last_entry Param((void));
Xstatic void pascal write_free Param(( RECPOS, BLOCK *));
Xstatic RECPOS pascal get_free Param((void));
Xstatic int pascal find_block Param((ENTRY *, int *));
Xstatic void pascal movedown Param((BLOCK *, int, int));
Xstatic void pascal moveup Param((BLOCK *, int, int));
Xstatic void pascal ins_block Param((BLOCK *, ENTRY *, int));
Xstatic void pascal del_block Param((BLOCK *, int));
Xstatic void pascal split Param((int, ENTRY *, ENTRY *));
Xstatic void pascal ins_level Param((int, ENTRY *));
Xstatic int pascal insert_ix Param((ENTRY *, IX_DESC *));
Xstatic int pascal find_ix Param((ENTRY *, IX_DESC *, int));
Xstatic int pascal combineblk Param((RECPOS, int));
Xstatic void pascal replace_entry Param((ENTRY *));
Xstatic void print_blk Param((BLOCK *));
X
X
X/* file I/O for B-PLUS module */
X
Xstatic void pascal
Xerror(j, l)
X int j;
X long l;
X {
X static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
X "ERROR WHILE READING FILE",
X "ERROR WHILE WRITING FILE"};
X (void) printf("\n %s - Record Number %ld\n", msg[j], l);
X exit(1);
X } /* error */
X
X
Xstatic void pascal
Xread_if(start, buf, nwrt)
X RECPOS start;
X char *buf;
X int nwrt;
X {
X long err;
X err = start - lseek(pci->ixfile, start, SEEK_SET);
X if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
X if (err != 0) error(1, start);
X } /* read_if */
X
X
Xstatic void pascal
Xwrite_if(handle, start, buf, nwrt)
X int handle;
X RECPOS start;
X char *buf;
X int nwrt;
X {
X long err;
X err = start - lseek(handle, start, SEEK_SET);
X if (err == 0) err = nwrt - write(handle, buf, nwrt);
X if (err != 0) error(2, start);
X } /* write_if */
X
X
Xstatic int pascal
Xcreat_if(fn)
X char *fn;
X {
X int ret;
X ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IREAD|S_IWRITE);
X if (ret < 0) error(0,0L);
X return (ret);
X } /* creat_if */
X
X
Xstatic int pascal
Xopen_if(fn)
X char *fn;
X {
X int ret;
X ret = open(fn,O_RDWR|O_BINARY);
X if (ret < 1) error(0,0L);
X return (ret);
X } /* open_if */
X
X
Xstatic void pascal
Xclose_if(handle)
X int handle;
X {
X if(close(handle) < 0) error(2,0L);
X } /* close_if */
X
X
Xint cdecl
Xopen_index(name, pix, dup)
X char *name;
X IX_DESC *pix;
X int dup;
X {
X pci = pix;
X pci->ixfile = open_if(name);
X pci->duplicate = dup;
X read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
X if (!cache_init)
X {
X init_cache();
X cache_init = 1;
X }
X first_key(pix);
X return ( IX_OK );
X } /* open_index */
X
X
Xint cdecl
Xclose_index(pix)
X IX_DESC *pix;
X {
X int i;
X write_if(pix->ixfile, 0L,(char *)&(pix->root),
X (sizeof(BLOCK) + sizeof(IX_DISK)));
X for (i = 0; i < NUM_BUFS; i++)
X if (BUFHANDLE(i) == pix->ixfile)
X {
X if (BUFDIRTY(i))
X {
X write_if(BUFHANDLE(i),
X BUFBLOCK(i).brec,
X (char *) &BUFBLOCK(i),
X (int) sizeof(BLOCK));
X BUFDIRTY(i) = 0;
X }
X BUFBLOCK(i).brec = NULLREC;
X }
X close_if(pix->ixfile);
X return( IX_OK );
X } /* close_index */
X
X
Xint cdecl
Xmake_index(name, pix, dup)
X char *name;
X IX_DESC *pix;
X int dup;
X {
X pci = pix;
X pci->ixfile = creat_if(name);
X pci->duplicate = dup;
X pci->dx.nl = 1;
X pci->dx.ff = NULLREC;
X pci->level = 0;
X CO(0) = -1;
X CB(0) = 0L;
X pci->root.brec = 0L;
X pci->root.bend = 0;
X pci->root.p0 = NULLREC;
X write_if(pci->ixfile, 0L,(char *)&(pix->root),
X (sizeof(BLOCK) + sizeof(IX_DISK)));
X if (!cache_init)
X {
X init_cache();
X cache_init = 1;
X }
X first_key(pix);
X return ( IX_OK );
X } /* make_index */
X
X
X/* cache I/O for BPLUS */
X
Xstatic void pascal
Xupdate_block()
X {
X if (block_ptr != &(pci->root))
X BUFDIRTY(cache_ptr) = 1;
X } /* update_block */
X
X
Xstatic void pascal
Xinit_cache()
X {
X register int j;
X for (j = 0; j < NUM_BUFS; j++)
X { BUFDIRTY(j) = 0;
X BUFCOUNT(j) = 0;
X BUFBLOCK(j).brec = NULLREC;
X }
X } /* init_cache */
X
X
Xstatic int pascal
Xfind_cache(r)
X RECPOS r;
X {
X register int j;
X for (j = 0; j < NUM_BUFS; j++)
X {
X if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
X { cache_ptr = j;
X return (1);
X } }
X return (-1);
X } /* find_cache */
X
X
Xstatic int pascal
Xnew_cache()
X {
X register int i;
X i = (cache_ptr + 1) % NUM_BUFS;
X if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
X BUFBLOCK(i).brec,
X (char *) &BUFBLOCK(i),
X sizeof(BLOCK));
X BUFHANDLE(i) = pci->ixfile;
X BUFDIRTY(i) = 0;
X return (i);
X } /* new_cache */
X
X
Xstatic void pascal
Xload_cache(r)
X RECPOS r;
X {
X cache_ptr = new_cache();
X read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
X } /* load_cache */
X
X
Xstatic void pascal
Xget_cache(r)
X RECPOS r;
X {
X if (find_cache(r) < 0)
X load_cache(r);
X block_ptr = &BUFBLOCK(cache_ptr);
X } /* get_cache */
X
X
Xstatic void pascal
Xretrieve_block(j, r)
X int j;
X RECPOS r;
X {
X if (j == 0)
X block_ptr = &(pci->root);
X else get_cache(r);
X CB(j) = block_ptr->brec;
X } /* retrieve_block */
X
X
X/* low level functions of BPLUS */
X
Xstatic int pascal
Xprev_entry(off)
X int off;
X {
X if (off <= 0)
X {
X off = -1;
X CO(pci->level) = off;
X }
X else
X off = scan_blk(off);
X return(off);
X } /* prev_entry */
X
X
Xstatic int pascal
Xnext_entry(off)
X int off;
X {
X if (off == -1)
X off = 0;
X else
X {
X if (off < block_ptr->bend)
X off += ENT_SIZE(ENT_ADR(block_ptr,off));
X }
X CO(pci->level) = off;
X return (off);
X } /* next_entry */
X
X
Xstatic void pascal
Xcopy_entry(to, from)
X ENTRY *to;
X ENTRY *from;
X {
X int me;
X me = ENT_SIZE(from);
X (void) memcpy(to, from, me);
X } /* copy_entry */
X
X
Xstatic int pascal
Xscan_blk(n)
X int n;
X {
X register int off, last;
X off = 0;
X last = -1;
X while (off < n )
X { last = off;
X off += ENT_SIZE(ENT_ADR(block_ptr,off));
X }
X CO(pci->level) = last;
X return (last);
X } /* scan_blk */
X
X
Xstatic int pascal
Xlast_entry()
X {
X return( scan_blk(block_ptr->bend) );
X } /* last_entry */
X
X
X/* maintain list of free index blocks */
X
Xstatic void pascal
Xwrite_free(r, pb)
X RECPOS r;
X BLOCK *pb;
X {
X pb->p0 = FREE_BLOCK;
X pb->brec = pci->dx.ff;
X write_if(pci->ixfile, r, (char *) (char *) pb, sizeof(BLOCK));
X pci->dx.ff = r;
X } /* write_free */
X
X
Xstatic RECPOS pascal
Xget_free()
X {
X RECPOS r, rt;
X
X r = pci->dx.ff;
X if ( r != NULLREC )
X { read_if(r, (char *)&rt, (int) sizeof( RECPOS ));
X pci->dx.ff = rt;
X }
X else
X r = filelength (pci->ixfile);
X return (r);
X } /* get_free */
X
X
X/* general BPLUS block level functions */
X
Xstatic int pascal
Xfind_block(pe, poff)
X ENTRY *pe;
X int *poff;
X {
X register int pos, nextpos, ret;
X pos = -1;
X nextpos = 0;
X ret = 1;
X while ( nextpos < block_ptr->bend)
X {
X ret = strcmp((char *)(pe->key),
X (char *)(ENT_ADR(block_ptr, nextpos)->key));
X if (ret <= 0)
X {
X if (ret == 0) pos = nextpos;
X break;
X }
X pos = nextpos;
X nextpos = next_entry(pos);
X }
X CO(pci->level) = pos;
X *poff = pos;
X return (ret);
X } /* find_block */
X
X
Xstatic void pascal
Xmovedown(pb, off, n)
X BLOCK *pb;
X int off;
X int n;
X {
X memcpy(ENT_ADR(pb, off),
X ENT_ADR(pb, off + n),
X pb -> bend - (off + n));
X } /* movedown */
X
X
Xstatic void pascal
Xmoveup(pb, off, n)
X BLOCK *pb;
X int off;
X int n;
X {
X memcpy(ENT_ADR(pb, off + n),
X ENT_ADR(pb, off),
X pb->bend - off);
X } /* moveup */
X
X
Xstatic void pascal
Xins_block(pb, pe, off)
X BLOCK *pb;
X ENTRY *pe;
X int off;
X {
X int size;
X size = ENT_SIZE(pe);
X moveup(pb,off,size);
X copy_entry(ENT_ADR(pb,off),pe);
X pb->bend += size;
X } /* ins_block */
X
X
Xstatic void pascal
Xdel_block(pb, off)
X BLOCK *pb;
X int off;
X {
X int ne;
X ne = ENT_SIZE(ENT_ADR(pb, off));
X movedown(pb, off, ne);
X pb->bend -= ne;
X } /* del_block */
X
X
X/* position at start/end of index */
X
Xint cdecl
Xfirst_key(pix)
X IX_DESC *pix;
X {
X pci = pix;
X block_ptr = &(pci->root);
X CB(0) = 0L;
X CO(0) = -1;
X pci->level = 0;
X while(block_ptr->p0 != NULLREC)
X {
X retrieve_block(++(pci->level), block_ptr->p0);
X CO(pci->level) = -1;
X }
X return ( IX_OK );
X } /* first_key */
X
X
Xint cdecl
Xlast_key(pix)
X IX_DESC *pix;
X {
X long ads;
X pci = pix;
X block_ptr = &(pci->root);
X CB(0) = 0L;
X pci->level = 0;
X if(last_entry() >= 0)
X {
X while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
X retrieve_block(++(pci->level), ads);
X }
X CO(pci->level) = block_ptr->bend;
X return ( IX_OK );
X } /* last_key */
X
X
X/* get next, previous entries */
X
Xint cdecl
Xnext_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X RECPOS address;
X int MSCbug; /* attempt to bypass bug in Microsoft C */
X
X pci = pix;
X retrieve_block(pci->level, CB(pci->level));
X if(CO(pci->level) == -1) address = block_ptr->p0;
X else {
X MSCbug = CO(pci->level);
X address = ENT_ADR(block_ptr, MSCbug)->idxptr;
X }
X while (address != NULLREC)
X {
X retrieve_block(++(pci->level), address);
X CO(pci->level) = -1;
X address = block_ptr->p0;
X }
X next_entry(CO(pci->level));
X if (CO(pci->level) == block_ptr->bend)
X {
X do
X { if(pci->level == 0)
X {
X last_key(pci);
X return (EOIX);
X }
X --(pci->level);
X retrieve_block(pci->level, CB(pci->level));
X next_entry(CO(pci->level));
X } while (CO(pci->level) == block_ptr->bend);
X }
X copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
X return ( IX_OK );
X } /* next_key */
X
X
Xint cdecl
Xprev_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X RECPOS address;
X int MSCbug; /* get around bug in Microsoft C */
X
X pci = pix;
X retrieve_block(pci->level, CB(pci->level));
X prev_entry(CO(pci->level));
X if (CO(pci->level) == -1)
X address = block_ptr->p0;
X else {
X MSCbug = CO(pci->level);
X address = ENT_ADR(block_ptr, MSCbug)->idxptr;
X }
X if (address != NULLREC)
X { do
X {
X retrieve_block(++(pci->level), address);
X address = ENT_ADR(block_ptr, last_entry())->idxptr;
X } while (address != NULLREC);
X }
X if (CO(pci->level) == -1)
X { do
X {
X if(pci->level == 0)
X {
X first_key(pci);
X return (EOIX);
X }
X --(pci->level);
X } while (CO(pci->level) == -1);
X retrieve_block(pci->level, CB(pci->level));
X }
X copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
X return ( IX_OK );
X } /* prev_key */
X
X
X/* insert new entries into tree */
X
Xstatic void pascal
Xsplit(l, pe, e)
X int l;
X ENTRY *pe;
X ENTRY *e;
X {
X int half, ins_pos, size;
X ins_pos = CO(pci->level);
X half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
X if (half == ins_pos)
X *e = *pe;
X else
X {
X copy_entry(e, ENT_ADR(block_ptr, half));
X size = ENT_SIZE(e);
X movedown(block_ptr, half, size);
X block_ptr->bend -= size;
X }
X spare_block = &BUFBLOCK(new_cache());
X memcpy(spare_block->entries,
X ENT_ADR(block_ptr,half),
X block_ptr->bend - half);
X spare_block->brec = get_free();
X spare_block->bend = block_ptr->bend - half;
X spare_block->p0 = e->idxptr;
X block_ptr->bend = half;
X e->idxptr = spare_block->brec;
X if (ins_pos < half)
X ins_block(block_ptr,pe,ins_pos);
X else if (ins_pos > half)
X {
X ins_pos -= ENT_SIZE(e);
X ins_block(spare_block,pe,ins_pos - half);
X CB(l) = e->idxptr;
X CO(l) = CO(l) - half;
X }
X write_if(pci->ixfile, spare_block->brec,
X (char *) spare_block, sizeof(BLOCK));
X } /* split */
X
X
Xstatic void pascal
Xins_level(l, e)
X int l;
X ENTRY *e;
X {
X int i;
X if ( l < 0)
X { for (i = 1; i < MAX_LEVELS; i++)
X { CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
X CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
X }
X memcpy(spare_block, &(pci->root), sizeof(BLOCK));
X spare_block->brec = get_free();
X write_if(pci->ixfile, spare_block->brec,
X (char *) spare_block, sizeof(BLOCK));
X pci->root.p0 = spare_block->brec;
X copy_entry((ENTRY *) (pci->root.entries), e);
X pci->root.bend = ENT_SIZE(e);
X CO(0) = 0;
X pci->level = 0;
X (pci->dx.nl)++;
X }
X else ins_block(block_ptr,e,CO(l));
X } /* ins_level */
X
X
Xstatic int pascal
Xinsert_ix(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X ENTRY e, ee;
X int h;
X h = 0;
X pci = pix;
X ee = *pe;
X do
X {
X if(CO(pci->level) >= 0)
X CO(pci->level) +=
X ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
X else
X CO(pci->level) = 0;
X update_block();
X if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
X {
X ins_level(pci->level, &ee);
X break;
X }
X else
X {
X h = 1;
X split(pci->level,&ee, &e);
X ee = e;
X pci->level--;
X if (pci->level < 0)
X {
X ins_level(pci->level, &e);
X break;
X }
X retrieve_block(pci->level, CB(pci->level));
X }
X }
X while (1);
X if (h) find_ix(pe, pix, 0);
X return ( IX_OK );
X } /* insert_ix */
X
X
X/* BPLUS find and add key functions */
X
Xstatic int pascal
Xfind_ix(pe, pix, find)
X ENTRY *pe;
X IX_DESC *pix;
X int find;
X {
X int level, off, ret;
X RECPOS ads;
X ENTRY found;
X pci = pix;
X ads = 0L;
X level = ret = 0;
X while (ads != NULLREC)
X { pci->level = level;
X retrieve_block(level, ads);
X if (find_block(pe, &off) == 0) ret = 1;
X if (ret && find) break;
X if (off == -1)
X ads = block_ptr->p0;
X else
X ads = ENT_ADR(block_ptr, off)->idxptr;
X CO(level++) = off;
X }
X return ( ret );
X } /* find_ix */
X
X
Xint cdecl
Xfind_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X int ret;
X ret = find_ix(pe, pix, 1);
X if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
X return ( ret );
X } /* find_key */
X
X
Xint cdecl
Xadd_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X int ret;
X ret = find_ix(pe, pix, 0);
X if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
X pe->idxptr = NULLREC;
X return (insert_ix(pe, pix));
X } /* add_key */
X
X
Xint cdecl
Xlocate_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X int ret;
X ENTRY e;
X ret = find_ix(pe, pix, 1);
X if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
X else if (next_key(pe,pix) == EOIX) ret = EOIX;
X return ( ret );
X } /* locate_key */
X
X
Xint cdecl
Xfind_exact(pe, pix)
X ENTRY *pe;
X IX_DESC * pix;
X {
X int ret;
X ENTRY e;
X copy_entry(&e, pe);
X ret = find_key(&e, pix);
X if ( ret && pci->duplicate)
X {
X do
X {
X ret = (e.recptr == pe->recptr);
X if( !ret ) ret = next_key(&e, pci);
X if (ret) ret = (strcmp(e.key, pe->key) == 0);
X if ( !ret ) return ( 0 );
X } while ( !ret );
X }
X copy_entry(pe, &e);
X return ( ret );
X } /* find_exact */
X
X
X/* BPLUS delete key functions */
X
Xint cdecl
Xdelete_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X ENTRY e;
X RECPOS ads;
X int h, leveli, levelf;
X if (!find_exact(pe, pix)) return( IX_FAIL );
X h = 1;
X if ((ads = pe->idxptr) != NULLREC)
X {
X leveli = pci->level;
X do
X {
X retrieve_block(++(pci->level), ads);
X CO(pci->level) = -1;
X }
X while ((ads = block_ptr->p0) != NULLREC);
X CO(pci->level) = 0;
X copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
X levelf = pci->level;
X pci->level = leveli;
X replace_entry(&e);
X pci->level = levelf;
X }
X while ( h )
X {
X retrieve_block(pci->level, CB(pci->level));
X del_block(block_ptr, CO(pci->level));
X update_block();
X if ( (pci->level == 0) && (block_ptr->bend == 0))
X /* tree was reduced in height */
X {
X if (pci->root.p0 != NULLREC)
X {
X retrieve_block(++pci->level, pci->root.p0);
X memcpy(&(pci->root), block_ptr, sizeof(BLOCK));
X (pci->dx.nl)--;
X write_free(block_ptr->brec, block_ptr);
X BUFDIRTY(cache_ptr) = 0;
X BUFHANDLE(cache_ptr) = 0;
X }
X break;
X }
X h = (block_ptr->bend < comb_size) && (pci->level > 0);
X if ( h )
X h = combineblk(CB(pci->level), block_ptr->bend);
X }
X find_ix(pe,pix,0);
X return( IX_OK );
X } /* delete_key */
X
X
Xstatic int pascal
Xcombineblk(ads, size)
X RECPOS ads;
X int size;
X {
X ENTRY e;
X RECPOS address;
X int MSCbug; /* fix bug in Microsoft C */
X int esize, off, ret, saveoff, ibuff;
X
X ret = 0;
X saveoff = CO(--(pci->level));
X retrieve_block(pci->level, CB(pci->level));
X if ((off = next_entry( saveoff )) < block_ptr->bend)
X /* combine with page on right */
X {
X if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
X {
X copy_entry(&e, ENT_ADR(block_ptr, off));
X MSCbug =CO(pci->level);
X address = ENT_ADR(block_ptr, MSCbug)->idxptr;
X retrieve_block(++pci->level, address);
X ibuff = cache_ptr;
X spare_block = block_ptr;
X retrieve_block(pci->level, ads);
X esize = ENT_SIZE(&e);
X if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
X && (spare_block->bend <= block_ptr->bend + esize))
X return( ret );
X e.idxptr = spare_block->p0;
X ins_block(block_ptr, &e, block_ptr->bend);
X update_block();
X if ((block_ptr->bend + spare_block->bend) < split_size)
X /* combine the blocks */
X {
X memcpy(ENT_ADR(block_ptr, block_ptr->bend),
X ENT_ADR(spare_block, 0),
X spare_block->bend);
X block_ptr->bend += spare_block->bend;
X write_free(spare_block->brec, spare_block);
X BUFDIRTY(ibuff) = 0;
X BUFHANDLE(ibuff) = 0;
X --pci->level;
X ret = 1;
X }
X else
X /* move an entry up to replace the one moved */
X {
X copy_entry(&e, ENT_ADR(spare_block, 0));
X esize = ENT_SIZE(&e);
X movedown(spare_block, 0, esize);
X spare_block->bend -= esize;
X spare_block->p0 = e.idxptr;
X BUFDIRTY(ibuff) = 1;
X --(pci->level);
X replace_entry(&e);
X }
X }
X }
X else
X /* move from page on left */
X {
X if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
X < split_size)
X {
X copy_entry(&e, ENT_ADR(block_ptr, saveoff));
X off = prev_entry(saveoff);
X if (CO(pci->level) == -1) address = block_ptr->p0;
X else {
X MSCbug = CO(pci->level);
X address = ENT_ADR(block_ptr, MSCbug)->idxptr;
X }
X retrieve_block(++pci->level, address);
X off = last_entry();
X ibuff = cache_ptr;
X spare_block = block_ptr;
X retrieve_block(pci->level, ads);
X esize = ENT_SIZE(&e);
X if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
X && (spare_block->bend <= block_ptr->bend + esize))
X return( ret );
X BUFDIRTY(ibuff) = 1;
X CO(pci->level) = 0;
X e.idxptr = block_ptr->p0;
X ins_block(block_ptr, &e, 0);
X if ((block_ptr->bend + spare_block->bend) < split_size)
X /* combine the blocks */
X {
X memcpy(ENT_ADR(spare_block, spare_block->bend),
X ENT_ADR(block_ptr, 0),
X block_ptr->bend);
X spare_block->bend += block_ptr->bend;
X write_free(block_ptr->brec, block_ptr);
X BUFDIRTY(cache_ptr) = 0;
X BUFHANDLE(cache_ptr) = 0;
X CO(--(pci->level)) = saveoff;
X ret = 1;
X }
X else
X /* move an entry up to replace the one moved */
X {
X block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
X copy_entry(&e, ENT_ADR(spare_block, off));
X spare_block->bend = off;
X update_block();
X CO(--(pci->level)) = saveoff;
X replace_entry(&e);
X }
X }
X }
X return ( ret );
X } /* combineblk */
X
X
Xstatic void pascal
Xreplace_entry(pe)
X ENTRY *pe;
X {
X int MSCbug; /* fix bug in Microsoft C */
X retrieve_block(pci->level, CB(pci->level));
X MSCbug = CO(pci->level);
X pe->idxptr = ENT_ADR(block_ptr, MSCbug)->idxptr;
X del_block(block_ptr, CO(pci->level));
X prev_entry(CO(pci->level));
X insert_ix(pe, pci);
X } /* replace_entry */
X
X/*****************************************************************
X | clearkey - set a database key to zero before using
X |----------------------------------------------------------------
X | Arguments:
X | 1) address of the ENTRY
X | Returns: none
X ****************************************************************/
X
Xvoid
Xclearkey(eptr)
XENTRY *eptr;
X{
X register char *cptr;
X register int n;
X
X for (n = MAXKEY, cptr = eptr->key; n--; )
X *(cptr++) = 0;
X}
SHAR_EOF
chmod 0644 bplus.c || echo "restore of bplus.c fails"
echo "x - extracting find1stkey.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > find1stkey.c &&
X/*****************************************************************
X | find_1stkey - find first key matching
X |----------------------------------------------------------------
X | The find_key routine may not return a pointer to the first
X | matching key in terms of next_key order. To allow searching
X | of all matching keys, use get_1stkey and next_key.
X |----------------------------------------------------------------
X | Arguments:
X | 1) pointer to the ENTRY struct
X | 2) pointer to the IX_DESC struct
X ****************************************************************/
X
X#include "bplus.h"
X
Xint
Xfind_1stkey(wkptr, ixptr)
X ENTRY *wkptr;
X IX_DESC *ixptr;
X{
X ENTRY lastok; /* last matching entry */
X IX_DESC ixwk; /* last valid index value */
X int stat;
X
X if ((stat = find_key(wkptr, ixptr)) == IX_OK)
X {
X lastok = *wkptr;
X ixwk = *ixptr;
X
X while (prev_key(wkptr, ixptr) != EOIX &&
X strcmp(wkptr->key, lastok.key) == 0)
X {
X lastok = *wkptr;
X ixwk = *ixptr;
X }
X
X *wkptr = lastok;
X *ixptr = ixwk;
X }
X return stat;
X}
X
SHAR_EOF
chmod 0644 find1stkey.c || echo "restore of find1stkey.c fails"
echo "x - extracting filelen.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > filelen.c &&
X/*****************************************************************
X | filelength - returns the length of a file
X ****************************************************************/
X
Xlong filelength (fd)
X int fd;
X{
X#if 0 /* original version */
X long orig, last, lseek();
X
X orig = lseek (fd, 0L, 1); /* seek to the current position */
X last = lseek (fd, 0L, 2); /* seek to the end */
X lseek (fd, orig, 0); /* reset the pointer */
X
X return last;
X#else /* new network version */
X#include <fcntl.h>
X#include <sys/types.h>
X#include <sys/stat.h>
X
X struct stat sb;
X fstat(fd, &sb);
X return sb.st_size;
X#endif
X}
SHAR_EOF
chmod 0644 filelen.c || echo "restore of filelen.c fails"
echo "x - extracting memmove.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > memmove.c &&
X/*****************************************************************
X | memmove - move in memory with attention to order and overlap
X |----------------------------------------------------------------
X | Arguments:
X | 1) destination: char *
X | 2) source: char *
X | 3) length: int
X | Returns: none
X ****************************************************************/
X
Xvoid memmove (to, from, length)
X char *to, *from;
X int length;
X{
X register char *TO, *FROM;
X
X if (to < from) {
X /* move left to right */
X TO = to;
X FROM = from;
X while (length--)
X *(TO++) = *(FROM++);
X }
X else {
X /* move right to left */
X TO = to + length - 1;
X FROM = from + length - 1;
X while (length--)
X *(TO--) = *(FROM--);
X }
X}
SHAR_EOF
chmod 0644 memmove.c || echo "restore of memmove.c fails"
echo "x - extracting read.me (Text)"
sed 's/^X//' << 'SHAR_EOF' > read.me &&
XThis package represents a few changes I have made in the shareware
Xbplus package from Hunter and Associates to allow operation under UNIX.
XI have been able to run this on MS-DOS, Xenix/286, Xenix/386, SunOS,
XUltrix, Encore, Convex, Sequent, and Cray-2. In short, In short it's
Xnot just for DOS any more.
X
XI have added the routines memmove (not in all UNIX flavors), filelen
X(same), and find1stkey. Note that my version of memmove pays attention
Xto direction for overlapping moves.
X
XWhen using duplicate keys, bplus looks at all bytes in the key. When
Xusing strings you may get some unexpected results if you don't clear
Xthe key to zeros before adding the string. The clearkey() routine does
Xjust that.
X
XI have used this for seven large databases, running on a LOT of machine
Xtypes, and since I added my changes I have not had any problems.
X
XI have included a small index program as a demo, which indexes a text
Xfile containing names and phone numbers.
X
XHistorical note: I bought v1.0 some years ago, and it didn't work.
XRecently I got v1.1 and found it worked well enough to justify the
Xeffort to port it to UNIX. I hope this is useful. Any shareware fees
Xshould be sent to H&A with a note that you are using my changes.
X
X bill davidsen, 2/20/89
X uunet!crdgw1!sixhub!davidsen
SHAR_EOF
chmod 0644 read.me || echo "restore of read.me fails"
echo "x - extracting bplus.doc (Text)"
sed 's/^X//' << 'SHAR_EOF' > bplus.doc &&
X\033(s10H
X
X
X
X
X
X THE B-PLUS PROGRAM
X A B-TREE INDEXING FILE MODULE
X FOR C PROGRAMMERS
X by
X Hunter and Associates
X
X
X
X B-PLUS is a versatile, carefully designed module for C
X programmers who need a fast, efficient program for indexing
X data files. B-PLUS allows data records to be retrieved based
X on a key value without regard to their position in the data
X file. The data records can also be accessed in sequential
X order in either a forward and reverse direction.
X
X The B-PLUS Program Module is based on the famous and
X widely used b-tree algorithm and has a number of useful
X extensions which are not found in many programs of this type.
X Some of its features are the following:
X
X - Variable length keys are allowed
X
X - File size limited only by DOS or by disk space
X
X - All functions are non-recursive so very little stack
X space is required
X
X - The most recently used key values are stored in a
X cache buffer in main memory for fast access
X
X - Duplicate keys are allowed
X
X The B-PLUS program has been tested using the Microsoft C
X Compilers, Versions 4.0, 4.5 (OS2 Beta release), 5.0 and the
X Borland Turbo C Compiler Version 1.0. The compiled object
X file is less than 9.4K bytes in length for these compilers.
X See the instructions at the end of this user's guide for a
X special note regarding Microsoft C Version 5.0 and Quick C.
X
X Version 1.1 has several new features that were not in
X Version 1.0. The next_key and prev_key routines can now be
X called immediately after adding or deleting an index key. It
X is no longer necessary to "reset" the index file with a
X find_key or locate_key function call after adding or deleting
X keys. Several minor bugs that were discovered in Version 1.0
X have been corrected in Version 1.1.
X
X
X LICENSE AND REGISTRATION
X
X B-PLUS is distributed as a "share ware" program. Please
X help us get it known by giving unmodified copies of the
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X program and documentation to other programmers who may find
X B-PLUS useful.
X
X B-PLUS is copyright (C) 1987 by Hunter and Associates.
X It is not public domain or free software. Non-registered
X users are granted a limited license to use B-PLUS on a trial
X basis for determining whether or not it is suitable for their
X needs. Registration permits the use of B-PLUS on one CPU and
X allows the use of the compiled B-PLUS modules in programs for
X general sale and/or distribution.
X
X The registration fee is $25 or $35. Users who pay the
X $35 fee will be sent a disk containing a fully commented
X listing of the latest source code, the user documentation,
X and a number of useful sample programs. Users who pay the
X $25 fee are not sent a new disk but are included in the
X mailing list for announcements about both current and future
X products. Your prompt registration of your copy of the B-
X PLUS program is appreciated.
X
X A trial disk with supporting documentation is available
X directly from Hunter and Associates for $10.
X
X Register your usage of B-PLUS by sending the registra-
X tion fee to:
X
X Hunter and Associates
X 7050 NW Zinfandel Lane
X Corvallis, OR 97330
X Telephone: (503) 745-7186
X
X Your comments regarding the B-PLUS program or any suggestions
X you have for extensions or for other programs that would be
X useful to you are welcomed.
X
X Hunter and Associates makes no warranties whatsoever
X regarding the B-PLUS computer programs or the supporting
X documentation.
X
X
X USING B-PLUS IN YOUR PROGRAMS
X
X The B-PLUS File Indexing Module contains twelve
X functions that handle the retrieval of data records by key
X value. The keys that are used to locate records are null
X terminated strings. The data structures and constants that
X are used are defined in the header file bplus.h.
X
X If the data record field that you want to use as a key
X contains numeric data, you can use one of the library
X
X Page 2
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X conversion routines (fcvt, evct, sprintf) to convert the data
X to string format.
X
X The connection between a key and its reference is
X formalized as a structure of type ENTRY. This structure
X contains three elements:
X
X typedef struct
X {
X RECPOS idxptr; /* long pointer to next index
X level */
X RECPOS recptr; /* long pointer to the file
X position of data record */
X char key[MAXKEY]; /* with this key value */
X } ENTRY;
X
X The application program uses only the recptr and key[]
X fields. The idxptr is used and maintained by the B-PLUS
X modules.
X
X A variable of type IX_DESC is declared for each open
X index file. See the header file bplus.h if you are
X interested in the elements of this structure. ENTRY and
X IX_DESC are the only two data types that are normally used by
X application programs.
X
X Here is a sample program stub which calls the open_index
X and find_index subroutines.
X
X
X Example:
X
X #include "bplus.h"
X main()
X {
X ENTRY e;
X IX_DESC names;
X
X /* open index file called NAMES.IDX */
X
X open_index("NAMES.IDX", &names, 0);
X
X /* find an index record for John Smith */
X
X strcpy(e.key, "SMITH JOHN");
X if(find_key(&e, &names))
X printf("Data record address is %ld", e.recptr);
X else
X printf("Cannot find record for that key");
X }
X
X Page 3
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X Each of the twelve subroutines is now described.
X
X int cdecl open_index(name, pix, dup);
X
X char *name; File path name
X IX_DESC *pix; Pointer to index file variable
X int dup; 0 - no duplicate keys allowed
X 1 - allow duplicate keys
X
X Description: The open_index function is used to open
X and initialize an existing index file specified by name
X and prepares the file for subsequent reading or writing.
X The file structure variable pix is defined in the
X application program. Duplicate keys are allowed or not
X allowed depending on whether dup has the value of 0 or
X 1. The open_index function returns the value IX_OK (1)
X if the file is opened successfully. If the file cannot
X be opened, an error message is displayed and the program
X is aborted.
X
X
X
X int cdecl make_index(name, pix, dup);
X
X char *name; File path name
X IX_DESC *pix; Pointer to index file variable
X int dup; 0 - no duplicate keys allowed
X 1 - allow duplicate keys
X
X Description: The make_index function is used to create
X and initialize a new index file specified by name and to
X prepare the file for subsequent reading or writing. If
X a file of this name already exists, its contents are
X destroyed when the new file is created. The file
X structure variable pix is defined in the application
X program. Duplicate keys are allowed or not allowed
X depending on whether dup has the value of 0 or 1. The
X make_index function returns the value IX_OK (1) if the
X file is created successfully. If the file cannot be
X created, an error message is displayed and the program
X is aborted.
X
X
X
X int cdecl close_index(pix);
X
X IX_DESC *pix; Pointer to index file variable
X
X Description: The close_index file function clears the
X internal cache buffer and closes the specified index
X
X Page 4
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X file. It is very important that each index file be
X closed. Otherwise data that is stored in the internal
X
X cache buffer may be lost and the index file may not be
X properly updated. The close_index function returns the
X value IX_OK (1) if the file is successfully closed.
X
X
X
X int cdecl find_key(pe, pix);
X
X ENTRY *pe; Pointer to variable of type ENTRY
X IX_DESC *pix; Pointer to index file variable
X
X Description: The find_key function searches the index
X file for the key value contained in pe.key. If an exact
X match is found, the value IX_OK (1) is returned and the
X location of the data record with this key value is
X stored in pe.recptr. If an exact match is not found,
X the value IX_FAIL (0) is returned and pe.recptr is
X undefined. If the index file contains duplicate keys,
X the first key is always found.
X
X
X
X int cdecl locate_key(pe, pix);
X
X ENTRY *pe; Pointer to variable of type ENTRY
X IX_DESC *pix; Pointer to index file variable
X
X Description: The locate key function searches the index
X file for the first key value which is equal to or
X greater than that stored in pe.key. The location of the
X data record which is equal to or greater than pe.key is
X stored in pe.recptr. This function can be used to
X locate an entry in the index file when only part of the
X key value is known. If the index file contains
X duplicate keys, locate_key will locate the first key.
X The following values are returned by locate_key:
X
X IX_OK - the value (1) is returned if an exact
X match is found
X
X IX_FAIL - the value (0) is returned if an exact
X match is not found
X
X EOIX - the value (-2) is returned for end of
X index if the search key is greater than
X all keys in the index file and pe.recptr
X is undefined.
X
X Page 5
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X
X
X int cdecl add_key(pe, pix);
X
X ENTRY *pe; Pointer to variable of type ENTRY
X IX_DESC *pix; Pointer to index file variable
X
X Description: The add_key function adds new entries to
X the index file. The calling program stores the key
X value in pe.key and the data record address in
X pe.recptr. Add_key first looks to see if an entry with
X this key already exists in the index file. If no entry
X with this key exists, the new entry is added. If an
X entry with this key already exists, the new entry is
X added only if duplicate keys are allowed (as defined by
X the open_index function). If the entry is successfully
X added, IX_OK (1) is returned; otherwise IX_FAIL (0) is
X returned.
X
X
X
X int cdecl delete_key(pe, pix);
X
X ENTRY *pe; Pointer to variable of type ENTRY
X IX_DESC *pix; Pointer to index file variable
X
X Description: The delete_key function deletes entries
X in the index file. The key to be deleted is stored in
X pe.key. If duplicate records are allowed, the
X corresponding data record address must also be stored in
X pe.recptr. In this case, delete key needs the record
X number to distinguish entries. If there are not
X duplicate entries, this field is ignored. If the entry
X is successfully deleted, IX_OK (1) is returned;
X otherwise IX_FAIL (0) is returned. The space that was
X occupied by the entry is marked as free for reused by
X B_PLUS.
X
X
X
X int cdecl first_key(pix);
X
X IX_DESC *pix; Pointer to index file variable
X
X Description: The first_key function positions the index
X file pointer to the beginning of the index file. The
X function next_key can then be used to list the file in
X key order. The first_key function returns the value
X IX_OK (1).
X
X
X Page 6
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X int cdecl last_key(pix);
X
X IX_DESC *pix; Pointer to index file variable
X
X Description: The last_key function positions the index
X file pointer at the end of the index file. The function
X previous_key can then be used to list the file in
X reverse key order. The last_key function returns the
X value IX_OK (1).
X
X
X
X int cdecl next_key(pe, pix);
X
X ENTRY *pe; Pointer to variable of type ENTRY
X IX_DESC *pix; Pointer to index file variable
X
X Description: The next_key function returns the next
X entry in the index file. After deleting or adding keys,
X next_key returns the key immediately following the
X addition or deletion. Next_key can be used to locate
X the desired data record when duplicate keys are allowed.
X Next_key is used to process files sequential. Next_key
X returns the value IX_OK (1) if the next key is present
X and the value EOIX (-2) when the file pointer is at the
X end of the index file. The following program processes
X an indexed file sequentially:
X
X #include "bplus.h"
X main()
X {
X ENTRY e;
X IX_DESC names;
X
X /* open the index file */
X open_index("names.idx", &names);
X
X /* now process the file sequentially */
X first_key(&names);
X ret = next_key(&e, &names);
X while (ret == IX_OK)
X {
X /* the data record location is e.recptr */
X /* the program would retrieve and process it */
X ret = next_key(&e, &names);
X }
X
X /* remember to always close open files */
X close_index(&names);
X }
X
X Page 7
X
X
X HUNTER AND ASSOCIATES B-PLUS FILE INDEXING PROGRAM
X -------------------------------------------------------------
X
X
X int cdecl prev_key(pe, pix);
X
X ENTRY *pe; Pointer to variable of type ENTRY
X IX_DESC *pix; Pointer to index file variable
X
X Description: The prev_key function returns the previous
X entry in the index file. After deleting or adding keys,
X prev_key returns the key immediately preceeding the
X addition or deletion. Prev_key can be used to process
X files sequentially in reverse order. Prev_key returns
X the value IX_OK (1) if there is a previous key and the
X value EOIX (-2) when the file pointer is at the
X beginning of the index file.
SHAR_EOF
echo "End of part 1"
echo "File bplus.doc is continued in part 2"
echo "2" > s2_seq_.tmp
exit 0
exit 0 # Just in case...
--
Kent Landfield INTERNET: kent at sparky.IMD.Sterling.COM
Sterling Software, IMD UUCP: uunet!sparky!kent
Phone: (402) 291-8300 FAX: (402) 291-4362
Please send comp.sources.misc-related mail to kent at uunet.uu.net.
More information about the Comp.sources.misc
mailing list