/********************************************************************/
/* */
/* BPLUS file indexing program - Version 1.1 */
/* */
/* A "shareware program" */
/* */
/* */
/* Copyright (C) 1987 by */
/* */
/* Hunter and Associates */
/* 7050 NW Zinfandel Lane */
/* Corvallis, Oregon 97330 */
/* (503) 745 - 7186 */
/* */
/********************************************************************/
#include <stdio.h>
#include <fcntl.h>
#include <io.h>
#include <sys\types.h> /* delete this line for Turbo C */
#include <sys\stat.h>
#include <string.h>
#include "bplus.h"
/* macros, constants, data types */
#define NULLREC (-1L) /* special value for RECPOS variable */
#define FREE_BLOCK (-2) /* designates a free block in index file */
/* the address of an entry in a block */
#define ENT_ADR(pb,off) ((ENTRY*)((char*)((pb)->entries) + off))
/* the size of an entry */
#define ENT_SIZE(pe) strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
/* the cache changed indicator */
#define BUFDIRTY(j) (mci->cache[j].dirty)
/* the index file handle for memblock j */
#define BUFHANDLE(j) (mci->cache[j].handle)
/* memory cache block j */
#define BUFBLOCK(j) (mci->cache[j].mb)
/* number of times cache blk j is referenced */
#define BUFCOUNT(j) (mci->cache[j].count)
/* address of current block for level j */
#define CB(j) (pci->pos[j].cblock)
/* offset of current block for level j */
#define CO(j) (pci->pos[j].coffset)
/* declare some global variables */
IX_DESC *pci; /* pointer to index descriptor */
IX_BUFFER bt_buffer; /* memory cache for index blocks */
IX_BUFFER *mci = &bt_buffer; /* pointer to cache index blocks */
BLOCK *block_ptr; /* pointer to index record block */
BLOCK *spare_block; /* pointer to spare index block */
int cache_ptr = 0; /* index to cache memory pool */
int cache_init = 0; /* 1 when cache is initilized */
int split_size = IXB_SPACE; /* split block when greater than */
int comb_size = (IXB_SPACE/2); /* combine blocks when less than */
/* #define memmove memcpy */ /* Use this macro for MicroSoft C 4.0 */
/* list all function prototypes */
void pascal error(int, long);
void pascal read_if(long, char *, int);
void pascal write_if(int, long, char *, int);
int pascal creat_if(char *);
int pascal open_if(char *);
void pascal close_if(int);
void pascal update_block(void);
void pascal init_cache(void);
int pascal find_cache(RECPOS);
int pascal new_cache(void);
void pascal load_cache(RECPOS);
void pascal get_cache(RECPOS);
void pascal retrieve_block(int, RECPOS);
int pascal prev_entry(int);
int pascal next_entry(int);
void pascal copy_entry(ENTRY *, ENTRY *);
int pascal scan_blk(int);
int pascal last_entry(void);
void pascal write_free( RECPOS, BLOCK *);
RECPOS pascal get_free(void);
int pascal find_block(ENTRY *, int *);
void pascal movedown(BLOCK *, int, int);
void pascal moveup(BLOCK *, int, int);
void pascal ins_block(BLOCK *, ENTRY *, int);
void pascal del_block(BLOCK *, int);
void pascal split(int, ENTRY *, ENTRY *);
void pascal ins_level(int, ENTRY *);
int pascal insert_ix(ENTRY *, IX_DESC *);
int pascal find_ix(ENTRY *, IX_DESC *, int);
int pascal combineblk(RECPOS, int);
void pascal replace_entry(ENTRY *);
void print_blk(BLOCK *);
/* file I/O for B-PLUS module */
void pascal error(j, l) /* print file error messages */
int j; /* error number */
long l; /* current file position */
{
static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
"ERROR WHILE READING FILE",
"ERROR WHILE WRITING FILE"};
printf("\n %s - Record Number %ld\n", msg[j], l);
exit(1); /* delete this line to not halt program */
/* and call your error handlng routine */
} /* error */
void pascal read_if(start, buf, nwrt) /* read pci index file */
long start; /* file read position */
char *buf; /* data holding buffer */
int nwrt; /* number bytes to read */
{
long err;
/* seek to read position in current index file */
err = start - lseek(pci->ixfile, start, SEEK_SET);
/* if no error read an index file block */
if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
/* call error routine if number bytes read != nwrt */
if (err != 0) error(1, start);
} /* read_if */
void pascal write_if(handle, start, buf, nwrt) /* write index record */
int handle; /* write to this file handle */
long start; /* write to this position in file */
char *buf; /* write data from this buffer */
int nwrt; /* write this many bytes of data */
{
long err;
/* seek to file write position */
err = start - lseek(handle, start, SEEK_SET);
/* if no error write index block block */
if (err == 0) err = nwrt - write(handle, buf, nwrt);
/* call error routine if number bytes written != nwrt */
if (err != 0) error(2, start);
} /* write_if */
int pascal creat_if(fn) /* make a new index file */
char *fn; /* name and path of file */
{
int ret;
ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
if (ret < 0) error(0,0L); /* there was an error if ret < 0 */
return (ret);
} /* creat_if */
int pascal open_if(fn) /* open an existing index file */
char *fn; /* path and name of index file */
{
int ret;
ret = open(fn,O_RDWR|O_BINARY);
if (ret < 1) error(0,0L); /* there was an error is ret < 1 */
return (ret);
} /* open_if */
void pascal close_if(handle) /* close an open index file */
int handle; /* with this file handle */
{
if(close(handle) < 0) error(2,0L);
} /* close_if */
int cdecl open_index(name, pix, dup) /* open and initilize index file */
char *name; /* path and name of index file */
IX_DESC *pix; /* pointer to index descriptor */
int dup; /* allow duplicate keys if != 0 */
{
pci = pix; /* pci is global index descriptor */
pci->ixfile = open_if(name); /* file handle */
pci->duplicate = dup; /* set duplicate keys flag */
/* read root descriptor for index */
read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
if (!cache_init) /* if cache not initilized */
{
init_cache(); /* initilize cache memory */
cache_init = 1; /* but only once */
}
first_key(pix); /* position to first index key */
return ( IX_OK );
} /* open_index */
int cdecl close_index(pix) /* close an open index file */
IX_DESC *pix;
{
int i;
/* write out the root block for the index descriptor */
write_if(pix->ixfile, 0L,(char *)&(pix->root),
(sizeof(BLOCK) + sizeof(IX_DISK)));
/* save all memory blocks for index that have been changed */
for (i = 0; i < NUM_BUFS; i++) /* check all of cache */
if (BUFHANDLE(i) == pix->ixfile)
{
if (BUFDIRTY(i))
{
write_if(BUFHANDLE(i), /* if changed, write to disk */
BUFBLOCK(i).brec,
(char *) &BUFBLOCK(i),
sizeof(BLOCK));
BUFDIRTY(i) = 0;
}
BUFBLOCK(i).brec = NULLREC; /* same handle can be used again */
}
close_if(pix->ixfile); /* close the index file */
return( IX_OK );
} /* close_index */
int cdecl make_index(name, pix, dup) /* create a new index file */
char *name; /* pointer to path and file name */
IX_DESC *pix; /* pointer to index descriptor */
int dup; /* duplicate keys allow is != 0 */
{
pci = pix; /* set global pci to this index descriptor */
pci->ixfile = creat_if(name);
pci->duplicate = dup;
pci->dx.nl = 1; /* the only block is the root */
pci->dx.ff = NULLREC; /* there are no free index blocks */
pci->level = 0; /* the root is level 0 */
CO(0) = -1; /* the current block offset is -1 */
CB(0) = 0L; /* the current block address 0L */
pci->root.brec = 0L; /* root block address is 0L */
pci->root.bend = 0; /* no entries yet so block end is 0 */
pci->root.p0 = NULLREC; /* p0 points to next index level */
/* write the root block of the index descriptor */
write_if(pci->ixfile, 0L,(char *)&(pix->root),
(sizeof(BLOCK) + sizeof(IX_DISK)));
if (!cache_init)
{ /* initiate memory cache but only once */
init_cache();
cache_init = 1;
}
first_key(pix); /* initialize to first key in index */
return ( IX_OK );
} /* make_index */
/* cache I/O for BPLUS */
void pascal update_block()
/* set flag that a memory block has changed */
/* no action necessary if current block is root */
{
if (block_ptr != &(pci->root))
BUFDIRTY(cache_ptr) = 1;
} /* update_block */
void pascal init_cache() /* initialize the cache memory buffers */
{
register int j;
for (j = 0; j < NUM_BUFS; j++)
{ BUFDIRTY(j) = 0; /* the buffer has not been changed */
BUFCOUNT(j) = 0; /* number of references is 0 */
BUFBLOCK(j).brec = NULLREC; /* each memory block is empty */
}
} /* init_cache */
int pascal find_cache(r) /* find a block in the cache memory */
RECPOS r;
{
register int j;
for (j = 0; j < NUM_BUFS; j++) /* repeat for each index buffer */
{
/* check handle and index address for a match */
if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
{ cache_ptr = j; /* if match, set cache_ptr */
return (1); /* and return true */
} }
return (-1); /* return false if not in cache memory */
} /* find_cache */
int pascal new_cache() /* assign a block in cache memory */
{
register int i;
i = (cache_ptr + 1) % NUM_BUFS; /* assign memory buffer */
/* if it has been changed, save it to disk */
if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
BUFBLOCK(i).brec,
(char *) &BUFBLOCK(i),
sizeof(BLOCK));
BUFHANDLE(i) = pci->ixfile; /* save index file handle */
BUFDIRTY(i) = 0; /* buffer change flag is false */
return (i); /* return memory buffer pointer */
} /* new_cache */
void pascal load_cache(r) /* load index block in cache memory */
RECPOS r;
{
cache_ptr = new_cache(); /* get a block in cache memory */
/* and then load the index block */
read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
} /* load_cache */
void pascal get_cache(r) /* load an index block into cache */
RECPOS r;
{
if (find_cache(r) < 0) /* if block is not in cache memory */
load_cache(r); /* load the block in memory */
/* and set block point to this block */
block_ptr = &BUFBLOCK(cache_ptr);
} /* get_cache */
void pascal retrieve_block(j, r) /* load an index block */
int j;
RECPOS r;
{
if (j == 0) /* if the block wanted is the root */
block_ptr = &(pci->root); /* then point to the root */
else get_cache(r); /* else get from cache memory */
CB(j) = block_ptr->brec; /* store index block address */
} /* retrieve_block */
/* low level functions of BPLUS */
int pascal prev_entry(off) /* back up one entry in current block */
int off;
{
if (off <= 0) /* if off <= can not back up */
{
off = -1; /* set to beginning of block */
CO(pci->level) = off;
}
else
off = scan_blk(off); /* find previous entry */
return(off);
} /* prev_entry */
int pascal next_entry(off) /* find next entry in current block */
int off;
{
if (off == -1) /* at beginning of the block */
off = 0;
else /* move to next entry if not at end */
{
if (off < block_ptr->bend)
off += ENT_SIZE(ENT_ADR(block_ptr,off));
}
CO(pci->level) = off; /* save the offset position in block */
return (off);
} /* next_entry */
void pascal copy_entry(to, from) /* copy an entry */
ENTRY *to; /* to here */
ENTRY *from; /* from here */
{
int me;
me = ENT_SIZE(from); /* get the entry's size */
memmove(to, from, me); /* and copy */
} /* copy_entry */
int pascal scan_blk(n) /* find the offset of last entry in */
int n; /* current block before postion n */
{
register int off, last;
off = 0;
last = -1;
while (off < n ) /* repeat until position >= n */
{ last = off;
off += ENT_SIZE(ENT_ADR(block_ptr,off));
}
CO(pci->level) = last; /* save new block offset positioon */
return (last);
} /* scan_blk */
int pascal last_entry() /* find offset of last entry in block */
{
return( scan_blk(block_ptr->bend) );
} /* last_entry */
/* maintain list of free index blocks */
void pascal write_free(r, pb) /* update list of free index blocks */
RECPOS r; /* free index position */
BLOCK *pb; /* free block */
{
pb->p0 = FREE_BLOCK; /* mark as free */
pb->brec = pci->dx.ff; /* keep old first free address */
write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
pci->dx.ff = r; /* set first free address to r */
} /* write_free */
RECPOS pascal get_free() /* get address of free index block */
{
RECPOS r, rt;
r = pci->dx.ff; /* use block address ff if free */
if ( r != NULLREC )
{ read_if(r, (char *)&rt, sizeof( RECPOS ));
pci->dx.ff = rt; /* save next free index block */
}
else /* else add to end of index file */
r = filelength (pci->ixfile);
return (r); /* return index block address */
} /* get_free */
/* general BPLUS block level functions */
int pascal find_block(pe, poff) /* find a key with current block */
ENTRY *pe; /* use this entry */
int *poff; /* return offset within block */
{
register int pos, nextpos, ret;
pos = -1;
nextpos = 0;
ret = 1;
while ( nextpos < block_ptr->bend) /* repeat until end of block */
{
ret = strcmp((char *)(pe->key),
(char *)(ENT_ADR(block_ptr, nextpos)->key));
if (ret <= 0) /* if the entry key >= search key */
{
if (ret == 0) pos = nextpos; /* move to matching key */
break; /* and break loop */
}
pos = nextpos; /* save current offset */
nextpos = next_entry(pos); /* get next entry position */
}
CO(pci->level) = pos; /* save offset within current block */
*poff = pos; /* store offset position */
return (ret);
} /* find_block */
void pascal movedown(pb, off, n) /* move part of block downward */
BLOCK *pb; /* block to move down */
int off; /* start move here */
int n; /* move this far */
{
memmove(ENT_ADR(pb, off),
ENT_ADR(pb, off + n),
pb -> bend - (off + n));
} /* movedown */
void pascal moveup(pb, off, n) /* move part of a block upward */
BLOCK *pb; /* the block */
int off; /* start move here */
int n; /* move up n bytes */
{
memmove(ENT_ADR(pb, off + n),
ENT_ADR(pb, off),
pb->bend - off);
} /* moveup */
void pascal ins_block(pb, pe, off) /* insert entry into a block */
BLOCK *pb; /* add to this block */
ENTRY *pe; /* add this entry */
int off; /* at this position */
{
int size;
size = ENT_SIZE(pe); /* size of new entry */
moveup(pb,off,size); /* move entries to make room */
copy_entry(ENT_ADR(pb,off),pe); /* copy new entry */
pb->bend += size; /* adjust block size */
} /* ins_block */
void pascal del_block(pb, off) /* delete entry in a block */
BLOCK *pb; /* this block */
int off; /* delete entry at this position */
{
int ne;
ne = ENT_SIZE(ENT_ADR(pb, off)); /* size of deleted entry */
movedown(pb, off, ne); /* move entries down */
pb->bend -= ne; /* adjust block size */
} /* del_block */
/* position at start/end of index */
int cdecl first_key(pix) /* position to first key */
IX_DESC *pix; /* in this index file */
{
pci = pix; /* set global index descriptor */
block_ptr = &(pci->root); /* start with the root */
CB(0) = 0L; /* root address is 0L */
CO(0) = -1; /* offset is -1 */
pci->level = 0; /* 0 level in index file */
while(block_ptr->p0 != NULLREC) /* repeat for all levels */
{ /* get index block for next level */
retrieve_block(++(pci->level), block_ptr->p0);
CO(pci->level) = -1; /* position to start of block */
}
return ( IX_OK );
} /* first_key */
int cdecl last_key(pix) /* position at last key */
IX_DESC *pix; /* in this index file */
{
long ads;
pci = pix;
block_ptr = &(pci->root); /* start with the root */
CB(0) = 0L;
pci->level = 0;
if(last_entry() >= 0) /* repeat for all levels */
{ /* get block for next level */
while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
retrieve_block(++(pci->level), ads);
}
CO(pci->level) = block_ptr->bend; /* set offset position to the end */
return ( IX_OK );
} /* last_key */
/* get next, previous entries */
int cdecl next_key(pe, pix) /* get next key */
ENTRY *pe; /* and put it here */
IX_DESC *pix; /* for this index */
{
RECPOS address;
pci = pix;
/* get block for current level */
retrieve_block(pci->level, CB(pci->level));
/* set address for next level */
if(CO(pci->level) == -1) address = block_ptr->p0;
else
{
if (CO(pci->level) == block_ptr->bend) address = NULLREC;
else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
}
while (address != NULLREC) /* repeat until at leaf level */
{
retrieve_block(++(pci->level), address);
CO(pci->level) = -1;
address = block_ptr->p0;
}
next_entry(CO(pci->level)); /* get next entry for leaf block */
if (CO(pci->level) == block_ptr->bend) /* check for end of block */
{
do
{ if(pci->level == 0) /* if this is the root block */
{
last_key(pci); /* go to end of root block */
return (EOIX); /* return end of index file */
}
--(pci->level); /* level of ancestor block */
retrieve_block(pci->level, CB(pci->level));
next_entry(CO(pci->level)); /* next entry for ancestor */
} while (CO(pci->level) == block_ptr->bend);
}
/* copy the next entry and return */
copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
return ( IX_OK );
} /* next_key */
int cdecl prev_key(pe, pix) /* get the previous key */
ENTRY *pe; /* put it here */
IX_DESC *pix; /* for this index */
{
RECPOS address;
pci = pix;
/* get block for current level */
retrieve_block(pci->level, CB(pci->level));
prev_entry(CO(pci->level)); /* previous entry in this block */
if (CO(pci->level) == -1)
address = block_ptr->p0;
else
address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
if (address != NULLREC) /* go to the leaf level of index */
{ do
{
retrieve_block(++(pci->level), address);
address = ENT_ADR(block_ptr, last_entry())->idxptr;
} while (address != NULLREC);
}
if (CO(pci->level) == -1) /* check if at beginning of block */
{ do
{
if(pci->level == 0) /* if this is the root block */
{
first_key(pci); /* get first key */
return (EOIX); /* and return end of index */
}
--(pci->level); /* level for ancestor block */
} while (CO(pci->level) == -1); /* repeat if beginning */
retrieve_block(pci->level, CB(pci->level)); /* get block */
}
/* copy entry and return */
copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
return ( IX_OK );
} /* prev_key */
/* insert new entries into tree */
void pascal split(l, pe, e) /* split an index block */
int l; /* level in tree */
ENTRY *pe; /* entry to insert */
ENTRY *e; /* entry to pass up to next level */
{
int half, ins_pos, size;
ins_pos = CO(pci->level); /* save current offset */
/* and divide block in half */
half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
if (half == ins_pos) /* if inserting at half */
*e = *pe; /* pass up entry pe */
else /* else copy entry at half */
{
copy_entry(e, ENT_ADR(block_ptr, half));
size = ENT_SIZE(e);
movedown(block_ptr, half, size); /* move block entries down */
block_ptr->bend -= size; /* and adjust the size */
}
spare_block = &BUFBLOCK(new_cache()); /* allocate a spare block */
memmove(spare_block->entries, /* and copy half the entries */
ENT_ADR(block_ptr,half),
block_ptr->bend - half);
spare_block->brec = get_free(); /* index address of new block */
spare_block->bend = block_ptr->bend - half; /* set size of block */
spare_block->p0 = e->idxptr; /* set all the pointers */
block_ptr->bend = half;
e->idxptr = spare_block->brec;
if (ins_pos < half) /* insert the new entry */
ins_block(block_ptr,pe,ins_pos); /* in current block */
else if (ins_pos > half) /* else insert the entry */
{ /* in the spare block */
ins_pos -= ENT_SIZE(e);
ins_block(spare_block,pe,ins_pos - half);
CB(l) = e->idxptr; /* set block address */
CO(l) = CO(l) - half; /* and offset */
}
write_if(pci->ixfile, spare_block->brec, /* write to disk */
(char *) spare_block, sizeof(BLOCK));
} /* split */
void pascal ins_level(l, e) /* insert an entry e */
int l; /* into block level l */
ENTRY *e;
{
int i;
if ( l < 0) /* tree height has increased */
{ for (i = 1; i < MAX_LEVELS; i++) /* save offset and addresses */
{ CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
}
/* copy old root to spare block */
memmove(spare_block, &(pci->root), sizeof(BLOCK));
/* get index address and write to disk */
spare_block->brec = get_free();
write_if(pci->ixfile, spare_block->brec,
(char *) spare_block, sizeof(BLOCK));
pci->root.p0 = spare_block->brec; /* set p0 pointer */
copy_entry((ENTRY *) (pci->root.entries), e); /* copy insert e */
pci->root.bend = ENT_SIZE(e); /* root contains only e */
CO(0) = 0; /* root offset is 0 */
pci->level = 0; /* set current level */
(pci->dx.nl)++; /* increment no. of levels */
}
else ins_block(block_ptr,e,CO(l)); /* insert in current block */
} /* ins_level */
int pascal insert_ix(pe, pix) /* insert at current level */
ENTRY *pe; /* insert entry pe */
IX_DESC *pix; /* into this index */
{
ENTRY e, ee;
int h;
h = 0;
pci = pix;
ee = *pe;
do
{
if(CO(pci->level) >= 0) /* set new offset */
CO(pci->level) +=
ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
else
CO(pci->level) = 0;
update_block(); /* we are going to change this block */
/* if new block size < split size */
if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
{
ins_level(pci->level, &ee); /* insert into current block */
break; /* and break */
}
else
{
h = 1; /* must reset index pointers */
split(pci->level,&ee, &e); /* split the current block */
ee = e; /* this entry is passed up */
pci->level--; /* to insert at this level */
if (pci->level < 0) /* increase tree height */
{
ins_level(pci->level, &e);
break;
}
/* get block for next level */
retrieve_block(pci->level, CB(pci->level));
}
}
while (1);
if (h) find_ix(pe, pix, 0); /* reset pointers if necessary */
return ( IX_OK );
} /* insert_ix */
/* BPLUS find and add key functions */
int pascal find_ix(pe, pix, find) /* search an index file */
ENTRY *pe; /* for this entry */
IX_DESC *pix; /* in this index */
int find; /* 1 to find_key, 0 to locate_key */
{
int level, off, ret;
RECPOS ads;
pci = pix;
ads = 0L; /* start at the root */
level = ret = 0;
while (ads != NULLREC) /* repeat until done */
{ pci->level = level; /* set level */
retrieve_block(level, ads); /* get index block */
/* and search for entry */
if (find_block(pe, &off) == 0) ret = 1; /* found? */
if (ret && find) break; /* done? */
if (off == -1) /* get next block address */
ads = block_ptr->p0;
else
ads = ENT_ADR(block_ptr, off)->idxptr;
CO(level++) = off; /* increment level */
}
return ( ret );
} /* find_ix */
int cdecl find_key(pe, pix) /* find a key */
ENTRY *pe; /* this entry */
IX_DESC *pix; /* in this index */
{
int ret;
ret = find_ix(pe, pix, 1); /* find_ix does all the work */
/* if found, copy the entry */
if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
return ( ret );
} /* find_key */
int cdecl add_key(pe, pix) /* add a new key */
ENTRY *pe; /* this entry */
IX_DESC *pix; /* this index file */
{
int ret;
ret = find_ix(pe, pix, 0); /* see if key is already in index */
/* if found, are dupicates are OK? */
if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
pe->idxptr = NULLREC; /* add new key on leaf level */
return (insert_ix(pe, pix)); /* insert_ix does the work */
} /* add_key */
int cdecl locate_key(pe, pix) /* locate first key */
ENTRY *pe; /* <= this entry */
IX_DESC *pix; /* in this index */
{
int ret;
ret = find_ix(pe, pix, 1); /* search index for entry */
/* if found, copy it to pe */
if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
/* else get the next key */
else if (next_key(pe,pix) == EOIX) ret = EOIX;
return ( ret );
} /* locate_key */
int cdecl find_exact(pe, pix) /* find an exact match */
ENTRY *pe; /* for this entry */
IX_DESC * pix; /* in this index */
{
int ret;
ENTRY e;
copy_entry(&e, pe); /* make a copy of the entry */
ret = find_key(&e, pix); /* is it in the index? */
if ( ret && pci->duplicate) /* if duplicate key are allowed */
{ /* then search for recptr match */
do
{
ret = (e.recptr == pe->recptr);
if( !ret ) ret = next_key(&e, pci);
if (ret) ret = (strcmp(e.key, pe->key) == 0);
if ( !ret ) return ( 0 ); /* no match was found */
} while ( !ret );
}
copy_entry(pe, &e); /* if found, data is contained in e */
return ( ret );
} /* find_exact */
/* BPLUS delete key functions */
int cdecl delete_key(pe, pix) /* delete a key */
ENTRY *pe; /* this entry */
IX_DESC *pix; /* in this index */
{
ENTRY e;
RECPOS ads;
int h, leveli, levelf;
/* search index for exact match */
if (!find_exact(pe, pix)) return( IX_FAIL );
h = 1;
if ((ads = pe->idxptr) != NULLREC) /* if not the leaf level */
{
leveli = pci->level; /* save current level */
do /* go to leaf level of index */
{
retrieve_block(++(pci->level), ads);
CO(pci->level) = -1;
}
while ((ads = block_ptr->p0) != NULLREC);
CO(pci->level) = 0;
copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
levelf = pci->level; /* save leaf level */
pci->level = leveli; /* reset starting level */
replace_entry(&e); /* replace with entry from leaf */
pci->level = levelf; /* leaf level */
}
while ( h )
{
/* get block and delete current entry */
retrieve_block(pci->level, CB(pci->level));
del_block(block_ptr, CO(pci->level));
update_block(); /* block has been changed */
if ( (pci->level == 0) && (block_ptr->bend == 0))
/* tree was reduced in height */
{
if (pci->root.p0 != NULLREC) /* replace root block */
{
retrieve_block(++pci->level, pci->root.p0);
memmove(&(pci->root), block_ptr, sizeof(BLOCK));
(pci->dx.nl)--; /* decrement number of levels */
write_free(block_ptr->brec, block_ptr); /* reuse space */
BUFDIRTY(cache_ptr) = 0; /* block saved on disk */
BUFHANDLE(cache_ptr) = 0;
}
break;
}
/* see if we can combine index blocks */
h = (block_ptr->bend < comb_size) && (pci->level > 0);
if ( h )
h = combineblk(CB(pci->level), block_ptr->bend);
}
find_ix(pe, pix, 0); /* restore CO and CB for each level */
return( IX_OK );
} /* delete_key */
int pascal combineblk(ads, size) /* combine index blocks */
RECPOS ads; /* block at this address */
int size; /* and is this size */
{
ENTRY e;
RECPOS address;
int esize, off, ret, saveoff, ibuff;
ret = 0;
/* ancestor level and save offset */
saveoff = CO(--(pci->level));
/* retrieve ancestor index block */
retrieve_block(pci->level, CB(pci->level));
if ((off = next_entry( saveoff )) < block_ptr->bend)
/* combine with page on right */
{
if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
/* okay to combine */
{
copy_entry(&e, ENT_ADR(block_ptr, off)); /* save entry */
address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
retrieve_block(++pci->level, address);
ibuff = cache_ptr; /* save cache pointer */
spare_block = block_ptr; /* use as spare block */
retrieve_block(pci->level, ads);
esize = ENT_SIZE(&e);
if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
&& (spare_block->bend <= block_ptr->bend + esize))
return( ret );
e.idxptr = spare_block->p0;
ins_block(block_ptr, &e, block_ptr->bend);
update_block();
if ((block_ptr->bend + spare_block->bend) < split_size)
/* combine the blocks */
{
memmove(ENT_ADR(block_ptr, block_ptr->bend),
ENT_ADR(spare_block, 0),
spare_block->bend);
/* set block length and free spare block space */
block_ptr->bend += spare_block->bend;
write_free(spare_block->brec, spare_block);
BUFDIRTY(ibuff) = 0;
BUFHANDLE(ibuff) = 0;
--pci->level;
ret = 1;
}
else
/* move an entry up to replace the one moved */
{
copy_entry(&e, ENT_ADR(spare_block, 0));
esize = ENT_SIZE(&e);
/* fixup spare block and pointers */
movedown(spare_block, 0, esize);
spare_block->bend -= esize;
spare_block->p0 = e.idxptr;
BUFDIRTY(ibuff) = 1;
--(pci->level);
replace_entry(&e);
}
}
}
else
/* move from page on left */
{
if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
< split_size)
/* okay to proceed */
{
copy_entry(&e, ENT_ADR(block_ptr, saveoff)); /* save entry */
/* get page which is on the left */
off = prev_entry(saveoff);
if (CO(pci->level) == -1) address = block_ptr->p0;
else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
retrieve_block(++pci->level, address);
off = last_entry();
ibuff = cache_ptr;
/* set spare block to left page */
spare_block = block_ptr;
/* get current block */
retrieve_block(pci->level, ads);
esize = ENT_SIZE(&e);
if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
&& (spare_block->bend <= block_ptr->bend + esize))
return( ret );
BUFDIRTY(ibuff) = 1; /* we have changed things */
CO(pci->level) = 0;
e.idxptr = block_ptr->p0;
ins_block(block_ptr, &e, 0);
if ((block_ptr->bend + spare_block->bend) < split_size)
/* combine the blocks */
{
memmove(ENT_ADR(spare_block, spare_block->bend),
ENT_ADR(block_ptr, 0),
block_ptr->bend);
/* set block length and freeup block */
spare_block->bend += block_ptr->bend;
write_free(block_ptr->brec, block_ptr);
BUFDIRTY(cache_ptr) = 0;
BUFHANDLE(cache_ptr) = 0;
CO(--(pci->level)) = saveoff;
ret = 1;
}
else
/* move an entry up to replace the one moved */
{
block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
copy_entry(&e, ENT_ADR(spare_block, off));
spare_block->bend = off;
update_block();
CO(--(pci->level)) = saveoff;
replace_entry(&e);
}
}
}
return ( ret );
} /* combineblk */
void pascal replace_entry(pe) /* replace entry at current position */
ENTRY *pe; /* with this entry */
{
retrieve_block(pci->level, CB(pci->level)); /* get current block */
/* set address for the replacement entry */
pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
del_block(block_ptr, CO(pci->level)); /* now delete the entry */
prev_entry(CO(pci->level)); /* backup one entry */
insert_ix(pe, pci); /* and insert new entry */
} /* replace_entry */
tundra