jbayer@ispi.UUCP (Jonathan Bayer) (08/09/89)
In response to several requests, I am posting my replacement routines for
the btree functions in the CData database library. Please note that while
I am posting the bplus routines they are not mine. They are sharware which
I received over the net a while ago. They were written and copyrighted by:
Hunter and Associates
7050 NW Zinfandel Lane
Corvallis, Oregon 97330
(503) 745 - 7186
I am not distributing the documentation for the bplus program.
This does NOT do any locking on the files. Therefore, multi-user applications
are n/a.
#! /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 shell archive."
# Contents: wrap.c bplus.c bplus.h
# Wrapped by cdbms@ispi on Tue Aug 8 16:29:04 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'wrap.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'wrap.c'\"
else
echo shar: Extracting \"'wrap.c'\" \(4641 characters\)
sed "s/^X//" >'wrap.c' <<'END_OF_FILE'
X#include <stdio.h>
X#include "cdata.h"
X#include "bplus.h"
X#include <string.h>
X
X
X/************************************************************************
X * *
X * *
X * wrap.c V. 1.0 *
X * *
X * Written by: Jonathan Bayer *
X * *
X * This is the wrapper interface which interfaces between *
X * the BPLUS file indexing program and the standard cdata routines *
X * *
X * This is released to the public domain, 8/8/1989 *
X * *
X * Use at your own risk. *
X * *
X * *
X * Use: *
X * Compile and link the files bplus.c and wrap.c with your *
X * program in place of the btree.c file. *
X * *
X * *
X ************************************************************************/
X
Xstatic IX_DESC trees[MXINDEX];
Xstatic int opened[MXINDEX] = {0};
Xstatic ENTRY entry[MXINDEX];
Xint near_mode = FALSE;
X
Xstatic int k_error = 0;
X
Xvoid build_b(name, len, Case)
Xchar *name;
Xint len, Case;
X{
XIX_DESC t;
X
X /* have to implement the case flag */
X
X k_error = make_index(name, &t, 1);
X k_error = close_index(&t);
X
X} /* build_b */
X
X
X
Xint btree_init(ndx_name)
Xchar *ndx_name;
X{
Xint x;
X
X for (x = 0; x < MXINDEX; x++) {
X if (!opened[x]) {
X open_index(ndx_name, &trees[x], 1);
X opened[x]++;
X return x;
X }
X }
X return ERROR;
X
X} /* btree_init */
X
X
Xint btree_close(tree)
Xint tree;
X{
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X k_error = close_index(&trees[tree]);
X opened[tree] = 0;
X if (k_error == IX_OK) return OK;
X return ERROR;
X} /* btree_close */
X
X
X
Xchar *case_check(k, klen)
Xchar *k;
Xunsigned klen;
X{
Xchar *k1,*k2;
X
Xklen++;
X if (strlen(k) + 1 < klen) {
X k1 = (char *) malloc(klen);
X strcpy(k1,k);
X } else k1 = strdup(k);
X
X/* if (bheader[trx].Case) { */
X k2 = k1;
X while (*k2) {
X *k2 = toupper(*k2);
X k2++;
X }
X/* } */
X return k1;
X}
X
X
Xint insertkey(tree, key, ad, unique)
Xint tree;
Xchar *key;
XRPTR ad;
Xint unique;
X{
Xchar *key1;
X
X /* have to add code to implement the "unique" var */
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X
X key1 = case_check(key, strlen(key)); /* kludge for now */
X
X strcpy(entry[tree].key, key1);
X free(key1);
X entry[tree].recptr = ad;
X k_error = add_key(&entry[tree], &trees[tree]);
X
X if (k_error == IX_OK) return OK;
X return ERROR;
X
X} /* insertkey */
X
X
X
XRPTR locate(tree, key)
Xint tree;
Xchar *key;
X{
Xchar *key1;
X
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X
X key1 = case_check(key, strlen(key)); /* kludge for now */
X
X strcpy(entry[tree].key, key1);
X free(key1);
X k_error = locate_key(&entry[tree], &trees[tree]);
X if ((near_mode) && (k_error == IX_FAIL) ||
X (k_error == IX_OK) ) {
X near_mode = FALSE;
X return entry[tree].recptr;
X }
X near_mode = FALSE;
X return 0;
X} /* locate */
X
X
X
Xint deletekey(tree, key, ad)
Xint tree;
Xchar *key;
XRPTR ad;
X{
Xchar *key1;
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X
X key1 = case_check(key, strlen(key)); /* kludge for now */
X
X strcpy(entry[tree].key, key1);
X free(key1);
X entry[tree].recptr = ad;
X k_error = delete_key(&entry[tree], &trees[tree]);
X if (k_error == IX_OK) return OK;
X return ERROR;
X
X} /* deletekey */
X
X
X
XRPTR firstkey(tree)
Xint tree;
X{
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X k_error = first_key(&trees[tree]);
X k_error = next_key(&entry[tree], &trees[tree]);
X
X if (k_error == IX_OK) return entry[tree].recptr;
X return ERROR;
X
X} /* firstkey */
X
X
X
XRPTR lastkey(tree)
Xint tree;
X{
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X k_error = last_key(&trees[tree]);
X k_error = prev_key(&entry[tree], &trees[tree]);
X
X if (k_error == IX_OK) return entry[tree].recptr;
X return ERROR;
X
X} /* lastkey */
X
X
XRPTR nextkey(tree)
Xint tree;
X{
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X k_error = next_key(&entry[tree], &trees[tree]);
X if (k_error == IX_OK) return entry[tree].recptr;
X return (RPTR) 0;
X
X} /* nextkey */
X
X
XRPTR prevkey(tree)
Xint tree;
X{
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X k_error = prev_key(&entry[tree], &trees[tree]);
X if (k_error == IX_OK) return entry[tree].recptr;
X return ERROR;
X
X} /* prevkey */
X
X
XRPTR currkey(tree)
Xint tree;
X{
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0)
X return ERROR;
X if (k_error == IX_OK) return entry[tree].recptr;
X return ERROR;
X
X} /* currkey */
X
X
X
Xvoid keyval(tree, key)
Xint tree;
Xchar *key;
X{
X
X if (tree >= MXINDEX || tree < 0 || opened [tree] == 0) {
X *key = 0;
X return;
X }
X if (k_error == IX_OK) {
X strcpy(key, entry[tree].key);
X } else *key = '\0';
X
X} /* keyval */
END_OF_FILE
if test 4641 -ne `wc -c <'wrap.c'`; then
echo shar: \"'wrap.c'\" unpacked with wrong size!
fi
# end of 'wrap.c'
fi
if test -f 'bplus.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'bplus.c'\"
else
echo shar: Extracting \"'bplus.c'\" \(24536 characters\)
sed "s/^X//" >'bplus.c' <<'END_OF_FILE'
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#ifndef M_XENIX
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 <errno.h>
X#include <malloc.h>
X#include "bplus.h"
X
X#ifndef M_XENIX
X#include <stddef.h>
X#endif
X
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
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
Xvoid pascal error(int, long);
Xvoid pascal read_if(long, char *, int);
Xvoid pascal write_if(int, long, char *, int);
Xint pascal creat_if(char *);
Xint pascal open_if(char *);
Xvoid pascal close_if(int);
Xvoid pascal update_block(void);
Xvoid pascal init_cache(void);
Xint pascal find_cache(RECPOS);
Xint pascal new_cache(void);
Xvoid pascal load_cache(RECPOS);
Xvoid pascal get_cache(RECPOS);
Xvoid pascal retrieve_block(int, RECPOS);
Xint pascal prev_entry(int);
Xint pascal next_entry(int);
Xint pascal copy_entry(ENTRY *, ENTRY *);
Xint pascal scan_blk(int);
Xint pascal last_entry(void);
Xint pascal write_free( RECPOS, BLOCK *);
XRECPOS pascal get_free(void);
Xint pascal find_block(ENTRY *, int *);
Xvoid pascal movedown(BLOCK *, int, int);
Xvoid pascal moveup(BLOCK *, int, int);
Xvoid pascal ins_block(BLOCK *, ENTRY *, int);
Xvoid pascal del_block(BLOCK *, int);
Xint pascal split(int, ENTRY *, ENTRY *);
Xvoid pascal ins_level(int, ENTRY *);
Xint pascal insert_ix(ENTRY *, IX_DESC *);
Xint pascal find_ix(ENTRY *, IX_DESC *, int);
Xint pascal combineblk(RECPOS, int);
Xvoid pascal replace_entry(ENTRY *);
Xvoid print_blk(BLOCK *);
X
X#ifdef M_XENIX
Xlong lseek();
X
X
Xchar *memmove ( s1, s2, n)
Xchar *s1, *s2;
Xint n;
X{
Xchar *b = (char *)malloc(n);
X
X memcpy(b,s2,n);
X memcpy(s1,b,n);
X free(b);
X
X}
X#endif
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#define memcpy memmove
X
X
X/* file I/O for B-PLUS module */
X
Xstatic void pascal error(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 printf("\n %s - Record Number %ld\n", msg[j], l);
X if (l == 0) {
X printf("\nerrno: %d\n",errno);
X}
X exit(1);
X } /* error */
X
X
Xvoid pascal read_if(start, buf, nwrt)
X long 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
Xvoid pascal write_if(handle, start, buf, nwrt)
X int handle;
X long 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
Xint pascal creat_if(fn)
X char *fn;
X {
X int ret;
X ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE | S_IREAD);
X if (ret < 0) error(0,0L);
X return (ret);
X } /* creat_if */
X
X
Xint pascal open_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
Xvoid pascal close_if(handle)
X int handle;
X {
X if(close(handle) < 0) error(2,0L);
X } /* close_if */
X
X
Xint cdecl open_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 close_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 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 make_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
Xvoid pascal update_block()
X {
X if (block_ptr != &(pci->root))
X BUFDIRTY(cache_ptr) = 1;
X } /* update_block */
X
X
Xvoid pascal init_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
Xint pascal find_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
Xint pascal new_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
Xvoid pascal load_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
Xvoid pascal get_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
Xvoid pascal retrieve_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
Xint pascal prev_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
Xint pascal next_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
Xint pascal copy_entry(to, from)
X ENTRY *to;
X ENTRY *from;
X {
X int me;
X me = ENT_SIZE(from);
X memcpy(to, from, me);
X } /* copy_entry */
X
X
Xint pascal scan_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
Xint pascal last_entry()
X {
X return( scan_blk(block_ptr->bend) );
X } /* last_entry */
X
X
X/* maintain list of free index blocks */
X
Xint pascal write_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 *) pb, sizeof(BLOCK));
X pci->dx.ff = r;
X } /* write_free */
X
X
X#ifdef M_XENIX
Xlong filelength(f)
Xint f;
X{
Xstruct stat buf;
X
X fstat(f, &buf);
X return buf.st_size;
X}
X#endif
X
X
X
XRECPOS pascal get_free()
X {
X RECPOS r, rt;
X
X r = pci->dx.ff;
X if ( r != NULLREC )
X { read_if(r, (char *)&rt, 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
Xint pascal find_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
Xvoid pascal movedown(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
Xvoid pascal moveup(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
Xvoid pascal ins_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
Xvoid pascal del_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 first_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 last_key(pix)
X IX_DESC *pix;
X {
X long ads;
X
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 next_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X RECPOS address;
X
X pci = pix;
X retrieve_block(pci->level, CB(pci->level));
X if(CO(pci->level) == -1) address = block_ptr->p0;
X else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
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);
Xprev_key(pe, pix);
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 prev_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X RECPOS address;
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 address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
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
Xint pascal split(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
Xvoid pascal ins_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
Xint pascal insert_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
Xint pascal find_ix(pe, pix, find)
X ENTRY *pe;
X IX_DESC *pix;
X int find;
X {
X int level, off, ret;
X RECPOS ads;
X
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 find_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 add_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 locate_key(pe, pix)
X ENTRY *pe;
X IX_DESC *pix;
X {
X int ret;
X
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 find_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 delete_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
Xint pascal combineblk(ads, size)
X RECPOS ads;
X int size;
X {
X ENTRY e;
X RECPOS address;
X int esize, off, ret, saveoff, ibuff;
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 address = ENT_ADR(block_ptr, CO(pci->level))->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 address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
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
Xvoid pascal replace_entry(pe)
X ENTRY *pe;
X {
X retrieve_block(pci->level, CB(pci->level));
X pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
X del_block(block_ptr, CO(pci->level));
X prev_entry(CO(pci->level));
X insert_ix(pe, pci);
X } /* replace_entry */
X
END_OF_FILE
if test 24536 -ne `wc -c <'bplus.c'`; then
echo shar: \"'bplus.c'\" unpacked with wrong size!
fi
# end of 'bplus.c'
fi
if test -f 'bplus.h' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'bplus.h'\"
else
echo shar: Extracting \"'bplus.h'\" \(2838 characters\)
sed "s/^X//" >'bplus.h' <<'END_OF_FILE'
X
X/* bplus.h - data structures and constants */
X
X
X#define IX_OK 1
X#define IX_FAIL 0
X#define EOIX (-2)
X#define MAXKEY 100
X#define NUM_BUFS 8
X#define MAX_LEVELS 8
X#define IXB_SIZE 1024
X#define IXB_SPACE (IXB_SIZE - sizeof(int) - sizeof(long) * 2)
X
Xtypedef long RECPOS;
X
Xtypedef struct /* entry structure in index */
X { RECPOS idxptr; /* points to lower index level */
X RECPOS recptr; /* points to data record */
X char key[MAXKEY]; /* start of record key */
X } ENTRY;
X
Xtypedef struct /* index record format */
X { RECPOS brec; /* position in index file */
X /* or location of next free block */
X int bend; /* first unused block location */
X RECPOS p0; /* points to next level */
X char entries[IXB_SPACE]; /* here are the key entries */
X } BLOCK;
X
Xtypedef struct /* disk file info */
X { RECPOS ff; /* location of first free block */
X int nl; /* number of index levels */
X } IX_DISK;
X
Xtypedef struct /* memory buffer pool of indx blks */
X { int dirty; /* true if changed */
X int handle; /* index file handle */
X int count; /* number of times referenced */
X BLOCK mb;
X } MEMBLOCK;
X
Xtypedef struct
X { MEMBLOCK cache [ NUM_BUFS ];
X } IX_BUFFER;
X
Xtypedef struct /* in-memory index descriptor */
X { int ixfile;
X int level; /* level in btree */
X int duplicate; /* no duplicate keys if 0 */
X struct
X { RECPOS cblock; /* position in index file */
X int coffset; /* current offset within block */
X } pos [ MAX_LEVELS ];
X BLOCK root; /* root index record */
X IX_DISK dx;
X } IX_DESC;
X
X#if defined(M_XENIX) && !defined(M_I386)
X#define cdecl
X#endif
X
Xint cdecl open_index(char *,IX_DESC *, int);
Xint cdecl close_index(IX_DESC *);
Xint cdecl make_index(char *,IX_DESC *, int);
Xint cdecl first_key(IX_DESC *);
Xint cdecl last_key(IX_DESC *);
Xint cdecl next_key(ENTRY *, IX_DESC *);
Xint cdecl prev_key(ENTRY *, IX_DESC *);
Xint cdecl find_key(ENTRY *, IX_DESC *);
Xint cdecl add_key(ENTRY *, IX_DESC *);
Xint cdecl locate_key(ENTRY *, IX_DESC *);
Xint cdecl delete_key(ENTRY *, IX_DESC *);
Xint cdecl find_exact(ENTRY *, IX_DESC *);
X
X
X#ifdef M_XENIX
X
X#define SEEK_SET 0
X#define SEEK_END 2
X#define O_BINARY 0
X
X#endif
X
END_OF_FILE
if test 2838 -ne `wc -c <'bplus.h'`; then
echo shar: \"'bplus.h'\" unpacked with wrong size!
fi
# end of 'bplus.h'
fi
echo shar: End of shell archive.
exit 0
--
Jonathan Bayer Beware: The light at the end of the
Intelligent Software Products, Inc. tunnel may be an oncoming dragon
500 Oakwood Ave. ...uunet!ispi!root
Roselle Park, NJ 07204 (201) 245-5922 jbayer@ispi.UUCP