home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Media Share 9
/
MEDIASHARE_09.ISO
/
cprog
/
ndx303.zip
/
NDX.CPP
< prev
next >
Wrap
C/C++ Source or Header
|
1993-02-13
|
14KB
|
538 lines
// NDX.CPP . . . BTree Index Handling Routines
// Copyright (C) 1987-89, 1992-93 by George H. Mealy
#pragma OPTION -w-pia
#include <stdlib.h>
#include <stdarg.h>
#include <io.h>
#include <fcntl.h>
#include <ctype.h>
#include <sys\stat.h>
#include "ndx.h"
#define MAJOR 3
#define MINOR 3
#define HDRSIZE 512
#define POP(a) a->pop(a)
#define PUSH(a, b) b->push(a)
CACHE Index::cache[NCACHE]; // The node cache
unsigned Index::cache_users; // User count
unsigned Index::hdrsize = FIELDOFFSET(Index, stacktop);
void fatal(char *format, ...);
char notice[] = "B-tree indexing routines copyright (C) 1987-89, 92-93 by "
"George H. Mealy.";
Index *ndx; /* Current index block */
char searcharg[maxkey];
int searchn;
Index::Index(char *name, int md, CFN compfn) // Create new Index
{
ndx = this;
handle = fopen(name, "w+b");
strcpy(filename, name);
if (!handle) fatal("Cannot open %s\n\a", name);
initcache();
stacktop = 0;
n = 0;
root = eof = HDRSIZE;
freelist = 0L;
major = MAJOR;
minor = MINOR;
mode = md;
newnode();
write(0L, &root, hdrsize); // Write virgin file header
write((DWORD)hdrsize, cache[0].node->keys, HDRSIZE - hdrsize);
// This is guaranteed to be cleared, since getnode did it!
if (compfn) cmpfn = compfn;
}
Index::Index(char *name, CFN compfn) // Open existing index file
{
ndx = this;
stacktop = 0;
handle = fopen(name, "r+b");
if(! handle) fatal("Index file %s unavailable\n\a", name);
initcache();
strcpy(filename, name);
read(0L, &root, hdrsize); // Read the index file header
if (compfn) cmpfn = compfn;
}
Index::~Index()
{
ndx = this;
cache_users--;
for (int i=0; i < NCACHE; i++)
if (cache[i].handle == handle) {
if (cache[i].dirty) write(cache[i].node->offset,
cache[i].node, nodesize);
if (!cache_users) delete cache[i].node;
else {
cache[i].node->offset = cache[i].dirty = 0;
cache[i].handle = NULL;
}
}
write(0L, &root, hdrsize);
fclose(handle);
}
// Cache handling routines
Index::initcache()
{
int i;
if (! cache_users++) {
for (i=0; i<NCACHE; i++) {
if (! (cache[i].node = new Node)) return 0;
memset(cache[i].node, 0, nodesize);
}
}
return 1;
}
Node *Index::newnode()
{
Node *slot = getnode(0L); // New slot in the cache
DWORD n;
cache[0].dirty++; // Mark it dirty
if (freelist) { /* If we can use an old node
-- that is, if the node freelist has an entry */
read(n = freelist, slot, nodesize);
freelist = slot->offset;
slot->offset = n;
}
else { // extend the file
slot->offset = eof;
eof += nodesize;
chsize(fileno(handle), eof);
}
memset(&slot->endkeys, 0, maxendkeys + sizeof(WORD)); // Zero the keys
return slot;
}
Node * Index::getnode(DWORD offset)
{
CACHE *c = cache, temp;
for (int i=0; i < NCACHE; i++, c++) /* It may be in the cache */
if (c->node->offset == offset && (c->handle == handle
|| !offset)) break;
if (i == NCACHE) { /* No luck */
/* Try to find an empty slot */
for (c=cache, i=0; i < NCACHE && c->node->offset ; c++, i++) ;
/* None ... empty the last one */
if (i == NCACHE) {
c--; i--;
write(c->node->offset, c->node, nodesize);
}
c->dirty = 0;
if (! offset) memset(c->node, 0, nodesize);
else read(offset, c->node, nodesize);
}
temp = *c; /* Promote it to the top */
temp.handle = handle;
memmove(cache + 1, cache, i*sizeof(CACHE));
*cache = temp;
return temp.node;
}
void Index::read(DWORD start, void *buffer, unsigned n)
{
if (fseek(handle, start, SEEK_SET) ||
n != fread(buffer, 1, n, handle))
fatal("Read failure on file %s\n", filename);
}
void Index::write(DWORD start, void *buffer, unsigned n)
{
if (fseek(handle, start, SEEK_SET) ||
n != fwrite(buffer, 1, n, handle))
fatal("Write failure on file %s\n", filename);
}
Index::isvalid()
{
if (!first() && !n) return 1;
for (unsigned i = 1 ; next(); i++);
return i == n;
}
Key::Key(const char *k, DWORD off)
{
if (strlen(k) >= maxkey) fatal("Key \"%s\" too long");
strcpy(data, k);
offset = off;
lson = 0L;
}
DWORD Index::insert(const char * key, DWORD offset)
{
Key k(key, offset);
long result;
ndx = this;
do {
stacktop = 0;
result = k.insert(root);
} while (result < 0);
ckey = k;
if (result) n++;
return result? k.offset: result;
}
DWORD Key::insert(DWORD root)
{
Node * node;
Key *k, *ik;
void *end;
int compare = -1, n;
if (! root) return 0;
node = ndx->getnode(root);
k = (Key *)node->keys;
end = (char *)k + node->endkeys;
while (k < end &&
(compare = strcmp(k->data, data)) < 0)
k = k->next();
if (! compare) { /* Found it */
ik = k;
if (ndx->mode == NODUPS)
{offset = k->offset; return 0; }
for (; k < end; k = k->next()) {
if ((compare = strcmp((char *)k->data, data)) != 0) break;
if (k->offset == offset) return k->offset;
}
if (ndx->mode == LIFO) k = ik;
}
if (k->lson) { /* Recurse */
PUSH(node, k);
return insert(k->lson);
}
if (node->endkeys + length() > maxendkeys) /* Node full, so split */
return node->split()? -1: 0;
node->shiftup(k, length());
PUSH(node, k->next());
k->keycpy(this);
ndx->cache[0].dirty = 1;
return k->offset;
}
DWORD Index::remove(const char *key, DWORD offset)
{
unsigned ttop, i;
Node *node;
Key *kp, *tkey;
// If key==NULL assume ckey is to be removed!
if (key && !findkeyrec(key, offset)) return 0;
ndx = this;
ttop = stacktop;
node = POP(kp);
if (! kp->lson) { // Key is simply deleted
node->shiftdn(kp, kp->length(), 0);
// If at end of node, up to next key
while (kp == (Key *)(node->keys + node->endkeys)) {
if (!stacktop)
{*ckey.data = 0; return ckey.offset = ckey.lson = 0L;}
node = POP(kp);
}
}
else {
stacktop++; // Retain node on stack
do { // Find lower rightmost key to pull up
node = getnode(kp->lson);
kp = (Key *)(node->keys + node->endkeys);
PUSH(node, kp);
} while (kp->lson);
node = POP(kp);
kp = kp->prev(node); // This is the key to go up
// need only the offset and key
tkey = (Key *)malloc(i = kp->length());
memcpy(tkey, kp, i);
node->shiftdn(kp, i, 1); // Leave the lson part untouched
stacktop = ttop;
node = POP(kp);
/* Preserve the original lson */
tkey->lson = kp->lson;
/* Substitute tkey for key being deleted */
node->endkeys++; // Avoid deletion of node!
node->shiftdn(kp, kp->length(), 0);
node->endkeys--;
node->shiftup(kp, i);
memcpy(kp, tkey, i);
free(tkey);
}
++stacktop; // Retain node on stack
while (kp->lson) { // Get lowest left son, if any
PUSH(node, kp);
node = getnode(kp->lson);
kp = (Key *)node->keys;
}
ckey = *kp; // The new current key
n--;
return ckey.offset;
}
DWORD Index::findkeyrec(const char *key, DWORD offset)
{
DWORD rcd;
rcd = find(key);
while (rcd && rcd != offset) rcd = next();
return rcd;
}
DWORD Index::find(const char *key)
{
ndx = this;
if (key) {
strcpy(searcharg, key);
searchn = strlen(key);
stacktop = 0;
return _find(key, root); /* Inner routine */
}
if (! next() ||
(ndx->cmpfn)(searcharg, ckey.data, searchn)) return NULL;
return ckey.offset;
}
DWORD Index::_find(const char * key, DWORD root)
{
Node *node = getnode(root);
Key * k = (Key *)node->keys;
DWORD rcd;
int compare, n = strlen(key);
for (; k < (Key *)(node->keys + node->endkeys); k = k->next()) {
/* Find right place in this level */
if (! (compare = (* ndx->cmpfn)(key, k->data, n))) {
if (k->lson) { /* Lower level keys -- recurse */
PUSH(node, k);
rcd = _find(key, k->lson);
if (rcd) return rcd;
node = POP(k);
}
/* We have the key */
PUSH(node, k); // Save it on the stack
ckey.keycpy(k); // and copy to current key
return ckey.offset;
}
if (compare < 0) break;
}
/* Ran into larger key or at end of this level */
PUSH(node, k); /* Update stack */
rcd = 0;
if (k->lson) /* More keys on right -- recurse */
rcd = _find(key, k->lson);
if (! rcd) POP(k);
return rcd;
}
DWORD Index::first(unsigned last)
{
Node *node = getnode(root);
DWORD lson;
Key *kp;
ndx = this;
if (! node->endkeys && ! ((Key *)(node->keys))->lson) return 0;
stacktop = 0;
/* Find lowermost leftmost key (or last) in the index, setting the stack */
while ((kp = (Key *)(node->keys + (last? node->endkeys: 0)))->lson) {
PUSH(node, kp);
node = getnode(kp->lson);
}
if (last) kp = kp->prev(node);
PUSH(node, kp);
ckey.keycpy(kp);
return ckey.offset;
}
DWORD Index::next()
{
Node *node;
Key *kp;
ndx = this;
/* The state at return is that left by find():
The top of the stack is the node in which a key was last found
and the offset is that of the key. */
node = POP(kp); //
kp = kp->next();
while (kp->lson) { // While left son, descend to lowest one
PUSH(node, kp);
node = getnode(kp->lson);
kp = (Key *)node->keys;
continue;
}
// While at end of current node, back up a level
while (kp == (Key *)(node->keys + node->endkeys)) {
if (stacktop == 0) return 0;
node = POP(kp);
}
PUSH(node, kp);
ckey.keycpy(kp);
return ckey.offset;
}
DWORD Index::prev()
{
Node *node;
Key *kp;
ndx = this;
node = POP(kp);
while (kp->lson) {
PUSH(node, kp);
node = getnode(kp->lson);
kp = (Key *)(node->keys + node->endkeys);
}
kp = kp->prev(node);
while (! kp) {
if (stacktop) {
node = POP(kp);
kp = kp->prev(node);
}
else return 0;
}
PUSH(node, kp);
ckey.keycpy(kp);
return kp->offset;
}
void Key::push(Node *node)
{
Frame *stk = (Frame *)&ndx->stack[ndx->stacktop++];
if (ndx->stacktop > stackdepth) fatal("Index stack overflow");
stk->node = node->offset;
stk->offset = (char *)this - (char *)node->keys;
}
Node * Key::pop(Key *&k)
{
Frame *stk = (Frame *)&ndx->stack[--ndx->stacktop];
Node *node = ndx->getnode(stk->node);
k = (Key *)(node->keys + stk->offset);
return node;
}
int Node:: split()
{
Node *parent, *added;
Key *kp, *kpop, *old, *pivot;
unsigned n, np;
/* Find entry to be moved up a level */
kp = (Key *)(keys + endkeys/2);
pivot = kp->prev(this);
np = pivot->length();
old = pivot->next();
n = (char *)old - keys; /* The entry goes to new node, for */
if (ndx->stacktop) { /* the moment */
/* If parent full, split it, then we will be back hopefully */
parent = kpop->pop(kpop);
if (pivot->length() + parent->endkeys >= maxendkeys)
return parent->split();
}
/* Copy first keys and pivot to new node */
added = ndx->newnode();
memcpy(added->keys, keys, n);
added->endkeys = n - np;
((Key *)(added->keys + n))->lson = 0;
/* Then move the remaining keys of the original node down */
endkeys -= n;
memmove(keys , old, endkeys + sizeof(DWORD));
ndx->cache[1].dirty = 1;
/* If it was the root, create a new one */
if (offset == ndx->root) {
parent = ndx->newnode();
kpop = (Key *)parent->keys ;
kpop->lson = offset;
ndx->root = parent->offset;
}
/* Put the pivot in the next higher level */
pivot = (Key *)((char *)added->keys + added->endkeys);
parent->shiftup(kpop, pivot->length());
kpop->keycpy(pivot);
kpop->lson = added->offset; /* Pivot may have a lson! */
return ndx->cache[0].dirty = 1;
}
void Node::shiftup(Key *kp, unsigned n)
{
int m = keys + endkeys - (char *)kp + sizeof(DWORD);
memmove((char *)kp + n, kp, m);
endkeys += n;
ndx->cache[0].dirty = 1;
}
void Node::shiftdn(Key *kp, unsigned n, unsigned leave)
{
int m = keys + endkeys - (char *)kp + sizeof(DWORD);
DWORD link;
if (! leave) memmove(kp, (char *)kp + n, m);
endkeys -= n;
ndx->cache[0].dirty = 1;
if (endkeys || kp->lson || ! ndx->stacktop) return;
link = offset; // Hook node into the freelist
offset = ndx->freelist;
ndx->freelist = link;
ndx->write(link, this, nodesize); // Have to do this here!
ndx->cache[0].dirty = 0;
POP(kp); // Back up to poppa
kp->lson = 0; // No son now
ndx->cache[0].dirty = 1;
ndx->stacktop++; // REALLY do this???
}
Key * Key::prev(Node *node)
{
Key *pk = (Key *)node->keys, *k = pk;
if (pk == this) return NULL;
while (k < this) {
pk = k;
k = k->next();
}
return pk;
}
void fatal(char *format, ...)
{
va_list argptr;
fprintf(stderr, "FATAL ERROR: ");
va_start(argptr, format);
vprintf(format, argptr);
va_end(argptr);
fputs("\n", stderr);
exit(-1);
}