home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
rtsi.com
/
2014.01.www.rtsi.com.tar
/
www.rtsi.com
/
OS9
/
OSK
/
APPS
/
hl10osrc.zoo
/
Lib
/
vBTree.cc
< prev
next >
Wrap
Text File
|
2009-11-06
|
27KB
|
950 lines
/* -*- Mode: C -*- */
/* vBTree.cc - (virtual) BTree implementation
* This code was heavily inspired by the BTree class
* described in chapter 10 of "C++, a guide for C programmers",
* by Sharam Hekmatpour, (c) 1990 by Prentice Hall of
* Australia Pty Ltd.
* Created by Robert Heller on Sat Dec 7 20:59:18 1991
*
* ------------------------------------------------------------------
* Home Libarian by Deepwoods Software
* Common Class library implementation code
* ------------------------------------------------------------------
* Modification History:
* ------------------------------------------------------------------
* Contents:
* ------------------------------------------------------------------
*
*
* Copyright (c) 1991,1992 by Robert heller (D/B/A Deepwoods Software)
* All Rights Reserved
*
*/
#include <stream.h>
#include <vBTree.h>
#include <ctype.h>
// This function is for debugging. It formats a page for inspection.
// (Needed since g++ for OSK does not generate any usefull debugging
// info for Microware's srcdbg.
static void DumpPage (Page* page)
{
cout << form("*** Page* at 0x%08x:\n",page);
cout << form(" ->size = %d\n",page->size);
cout << form(" ->left.record_address = %d\n",
page->left.record_address);
cout << form(" ->parent.record_address = %d\n",
page->parent.record_address);
cout << form(" ->parentidx = %d\n",page->parentidx);
for (int i = 0; i < page->size; i++) {
cout << form(" ->items[%d].key = %s\n",i,page->items[i].key);
cout << form(" ->items[%d].data = [%d:%d]\n",i,
page->items[i].data.record_size,
page->items[i].data.record_address);
cout << form(" ->items[%d].right.record_address = %d\n",i,
page->items[i].right.record_address);
}
}
static void dumphome(const HomeBlock* block,const char* message)
{
cerr << "\nHomeBlock (" << message << "):\n\n";
unsigned char* p = (unsigned char*) block;
cerr <<
" Addr 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 2 4 6 8 A C E\n" <<
"-------- ---- ---- ---- ---- ---- ---- ---- ---- ----------------\n";
for (int i = 0; i < sizeof(HomeBlock); i += 16, p += 16) {
cerr << form("%08x ",i);
for (int j = 0; j < 16; j += 2) {
cerr << form(" %02.2x%02.2x",p[j] & 0x0FF,
p[j+1] & 0x0FF);
}
cerr << " ";
for (j = 0; j < 16; j++) {
char c = p[j];
if (c >= ' ' && c <= '~') cerr << c;
else cerr << ".";
}
cerr << "\n";
}
}
// Basic constructor. Does not actually open the file, just sets things up.
vBTree::vBTree() {
LastSearchType = none;
homedirty = false;
buf = new Item[2*Order + 2];
}
// This constructor also opens the file.
vBTree::vBTree(char *filename,OpenMode mode,int nfree)
{
LastSearchType = none;
homedirty = false;
buf = new Item[2*Order + 2];
open(filename,mode,nfree);
}
// Open a vBTree file (library card catalog file)
OpenStatus vBTree::open(char *filename, OpenMode mode,int nfree)
{
// Figure type of access and whether we should try to create a
// new file, if the file does not exist.
if ((mode & ModeMask) == ReadWrite) {
openstat = PageFile::open(filename, inout, ReadWriteFlags,
ReadWriteMode,
((mode & Create) != 0) ? true :
false);
} else {
openstat = PageFile::open(filename, in, ReadFlags, ReadMode,
false);
}
// File might have been opened. Fan out based on how PageFile::open
// fared.
switch (openstat) {
case openold : // An existing file was opened.
// Read in the home block and
// set things up.
DiskRecord homerecord(sizeof(HomeBlock),0L);
if (PageFile::ReadRecord(homerecord,
(char *) &homeblock,
sizeof(HomeBlock)) <
sizeof(HomeBlock)) {
PageFile::close();
return(openstat = failure);
}
// Is it really a library file??
if (strncmp(homeblock.magic,homeblock.Magic,8) != 0) {
PageFile::close();
return(openstat = failure);
}
// Home block is fresh and clean
homedirty = false;
// All set.
return(openstat);
case opennew : // new file. Initialize the
// file with a specified
// number of free pages
// and a properly intialized
// home block.
if (nfree > MaxNumFree) nfree = MaxNumFree;
else if (nfree < 0) nfree = 0;
strncpy(homeblock.magic,homeblock.Magic,8);
homeblock.IdRoot = 0L;
homeblock.TitleRoot = 0L;
homeblock.AuthorRoot = 0L;
homeblock.SubjRoot = 0L;
homeblock.numfree = 0;
// pre-write home block (tie up first "sector"
// so it won't get used as a page).
PageFile::WriteRecord((char *) &homeblock,
sizeof(HomeBlock));
// get a bunch of free pages
for (int i = nfree-1; i >= 0; i--) {
homeblock.freepages[i] = PageFile::NewPage();
}
// note the number of available pages
homeblock.numfree = nfree;
// the home block is already dirty...
homedirty = true;
//dumphome(&homeblock,"open (new file)");
// all set.
return(openstat);
case failure: return(openstat); // PageFile::open() failed.
}
}
// Destructor. Close file and generally clean up
vBTree::~vBTree()
{
if (isopen) { // if file is open...
if (homedirty == true) { // home block needs writing??
//dumphome(&homeblock,"Closing, updating homeblock");
// yep. rewrite it.
DiskRecord homerecord(sizeof(HomeBlock),0L);
PageFile::ReWriteRecord(homerecord,
(char *) &homeblock,
sizeof(HomeBlock));
}
// Close file. (dirty pages will get written out)
PageFile::close();
//delete[2*Order + 2] buf; // this crashes under OSK...
}
}
// Free up a disk page.
void vBTree::FreePage (DiskPage dpage)
{
if (dpage != 0) {
if (homeblock.numfree == MaxNumFree) return;
for (int i = 0; i < homeblock.numfree; i++)
if (homeblock.freepages[i] == dpage) return;
homeblock.freepages[homeblock.numfree++] = dpage;
homedirty = true;
//dumphome(&homeblock,"FreePage");
}
}
// allocate a new disk page.
DiskPage vBTree::NewPage()
{
if (homeblock.numfree > 0) { // any reuseable pages??
homeblock.numfree--;
homedirty = true;
//dumphome(&homeblock,"NewPage");
return (homeblock.freepages[homeblock.numfree]);
} else return (PageFile::NewPage()); // nope, get a new one
}
// Main searching function. I've modified things to remember where we found
// match. My key compare function matches proper prefixes and I've added a
// search again function - allows the user to only give a prefix and find
// all matches.
Boolean vBTree::SearchAux(DiskPage dtree, Key key, register CoreItem* item)
{
int idx;
Page *tree;
if (dtree == 0) { // fell through on exact match
// maybe a prefix matched...
if (LastSearchIdx >= 0) {
// yep. save state and return match.
strncpy(LastSearchKey,key,KeySize);
tree = (*this)[LastSearchPage]; // page in page
// copy actual key
strcpy(item->key,tree->items[LastSearchIdx].key);
// allocate a buffer and read in the data record
item->data.NewBuffer(tree->items[LastSearchIdx].data.record_size);
int bytesread =
PageFile::ReadRecord(tree->items[LastSearchIdx].data,
item->data.buffer,item->data.size);
// I/O error? report error and return empty buffer
if (bytesread < 0) {
Error(sysErr,"PageFile::ReadRecord");
item->data.NewBuffer(0);
}
// success
return true;
} else { // nope. search over.
LastSearchType = none;
return false;
}
}
LastSearchPage = dtree; // remember where er are
tree = (*this)[dtree]; // page in page
if (BinarySearch(tree,key,&idx)) { // is key on this page??
// yep. return key and data
strcpy(item->key,tree->items[idx].key);
item->data.NewBuffer(tree->items[idx].data.record_size);
int bytesread =
PageFile::ReadRecord(tree->items[idx].data,
item->data.buffer,item->data.size);
if (bytesread < 0) {
Error(sysErr,"PageFile::ReadRecord");
item->data.NewBuffer(0);
}
// save state
strncpy(LastSearchKey,key,KeySize);
LastSearchIdx = idx;
// success
return true;
}
// not here. descend down the tree.
return SearchAux((idx < 0 ? tree->left
: tree->items[idx].right),key,item);
}
// Binary search function
Boolean vBTree::BinarySearch (Page *node, Key key, int *idx)
{
int low = 0;
int up = node->size - 1;
register int mid, comp;
register Boolean found, exact;
do { // binary chop
mid = (low + up) / 2;
comp = CompareKeys(key,node->items[mid].key);
exact = comp==0 && strlen(key) == strlen(node->items[mid].key);
if (comp==0) LastSearchIdx = mid; // state preservation
if (comp==0 && !exact) comp = -1; // make sure we get
// the leftmost match
if (comp <= 0) up = mid - 1; // restrict to lower half
if (comp >= 0) low = mid + 1; // restrict to upper half
} while (low <= up);
*idx = (found = low - up > 1) ? mid : up;
return (found);
}
// Key comparison function. Will return 0 if keypat is a proper prefix
// of key. Otherwise it behaves simularly to strcmp(), except it does
// a case insensitive comparison.
int vBTree::CompareKeys(Key keypat,Key key)
{
char *p = keypat, *k = key;
int ch, comp;
if (*p == '\0') return(0);
do {
ch = *p++;
if (isalpha(ch) && islower(ch)) ch = toupper(ch);
comp = ch - *k++;
} while (comp == 0 && *p != '\0');
return (comp);
}
// This function continues the search (prefix string matching)
Boolean vBTree::SearchAgain(register CoreItem* item)
{
Page *tree;
int comp;
int idx, tidx;
DiskPage tpage;
LSType ttype;
// remember place
//cerr << "*** Entering SearchAgain: LastSearchPage = " <<
// LastSearchPage.record_address <<
// "LastSearchIdx = " << LastSearchIdx << "\n";
tpage = LastSearchPage;
tidx = LastSearchIdx;
ttype = LastSearchType;
tree = (*this)[LastSearchPage]; // page in page
if (LastSearchIdx >= 0 && // a real index?
tree->items[LastSearchIdx].right != 0) { // a child??
// decend the tree to the right
LastSearchPage = tree->items[LastSearchIdx].right;
LastSearchIdx = -1; // left most node
// recurse...
if (SearchAgain(item)) return(true);
// failed. reset
LastSearchPage = tpage;
LastSearchIdx = tidx;
LastSearchType = ttype;
}
// next node to the right
idx = ++LastSearchIdx;
// nodes remaining??
if (idx < tree->size) {
// yep. does this node match??
comp = CompareKeys(LastSearchKey,tree->items[idx].key);
if (comp < 0) {
// nope. we are done...
LastSearchType = none;
return (false);
}
// yep. return it.
strcpy(item->key,tree->items[LastSearchIdx].key);
item->data.NewBuffer(tree->items[LastSearchIdx].data.record_size);
int bytesread =
PageFile::ReadRecord(tree->items[LastSearchIdx].data,
item->data.buffer,item->data.size);
if (bytesread < 0) {
Error(sysErr,"PageFile::ReadRecord");
item->data.NewBuffer(0);
}
// we are all set for next time
return (true);
} else { // no more items here. pop up and try next item
// in parent
if (tree->parent == 0) { // if any...
// no parent. end of the line..
LastSearchType = none;
return(false);
} else {
// up and to the right...
LastSearchPage = tree->parent;
LastSearchIdx = tree->parentidx+1;
return (SearchAgain(item));
}
}
}
// helper function for InsertXXX
// copy a key, converting to uppercase and truncating to fit.
static strucase(Key dest, Key source)
{
char ch, *a, *b;
int i;
for (a=source,b=dest,i=1; *a != '\0' && i < KeySize; a++,b++,i++) {
ch = *a;
if (isalpha(ch) && islower(ch)) ch = toupper(ch);
*b = ch;
}
*b = '\0';
}
// Insertion function for the Id tree
DiskRecord vBTree::InsertId (Key key,Record* newdata)
{
Item *receive, item;
Page *page, *root;
DiskPage dpage;
// copy the key
strucase(item.key,key);
// and write the data out
item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
item.right = 0;
if (homeblock.IdRoot == 0) { // empty tree
homeblock.IdRoot = NewPage();
homedirty = true;
root = (*this)[homeblock.IdRoot];
root->left = 0;
root->parent = 0;
root->parentidx = -1;
root->items[0] = item;
root->size = 1;
(*this)(homeblock.IdRoot).isdirty = true;
//dumphome(&homeblock,"InsertId (new tree)");
} else if ((receive = InsertAux(&item,homeblock.IdRoot)) != 0) {
dpage = NewPage(); // new root
page = (*this)[dpage];
page->size = 1;
page->left = homeblock.IdRoot;
page->parent = 0;
page->parentidx = -1;
page->items[0] = *receive;
AdjustParent(dpage); // fixup this node's offspring
// to point back.
(*this)(dpage).isdirty = true;
root = (*this)[homeblock.IdRoot];
root->parent = dpage;
root->parentidx = -1;
(*this)(homeblock.IdRoot).isdirty = true;
homeblock.IdRoot = dpage;
homedirty = true;
//dumphome(&homeblock,"InsertId (new root)");
}
return(item.data);
}
// Insertion for the Title tree
DiskRecord vBTree::InsertTitle (Key key,Record* newdata)
{
Item *receive, item;
Page *page, *root;
DiskPage dpage;
strucase(item.key,key);
item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
item.right = 0;
if (homeblock.TitleRoot == 0) {
homeblock.TitleRoot = NewPage();
homedirty = true;
root = (*this)[homeblock.TitleRoot];
root->left = 0;
root->parent = 0;
root->parentidx = -1;
root->items[0] = item;
root->size = 1;
(*this)(homeblock.TitleRoot).isdirty = true;
//dumphome(&homeblock,"InsertTitle (new tree)");
} else if ((receive = InsertAux(&item,homeblock.TitleRoot)) != 0) {
dpage = NewPage();
page = (*this)[dpage];
page->size = 1;
page->left = homeblock.TitleRoot;
page->parent = 0;
page->parentidx = -1;
page->items[0] = *receive;
AdjustParent(dpage);
(*this)(dpage).isdirty = true;
root = (*this)[homeblock.TitleRoot];
root->parent = dpage;
root->parentidx = -1;
(*this)(homeblock.TitleRoot).isdirty = true;
homeblock.TitleRoot = dpage;
homedirty = true;
//dumphome(&homeblock,"InsertTitle (new root)");
}
return(item.data);
}
// Insertion for the Author tree
DiskRecord vBTree::InsertAuthor (Key key,Record* newdata)
{
Item *receive, item;
Page *page, *root;
DiskPage dpage;
strucase(item.key,key);
item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
item.right = 0;
if (homeblock.AuthorRoot == 0) {
homeblock.AuthorRoot = NewPage();
homedirty = true;
root = (*this)[homeblock.AuthorRoot];
root->left = 0;
root->parent = 0;
root->parentidx = -1;
root->items[0] = item;
root->size = 1;
(*this)(homeblock.AuthorRoot).isdirty = true;
//dumphome(&homeblock,"InsertAuthor (new tree)");
} else if ((receive = InsertAux(&item,homeblock.AuthorRoot)) != 0) {
dpage = NewPage();
page = (*this)[dpage];
page->size = 1;
page->left = homeblock.AuthorRoot;
page->parent = 0;
page->parentidx = -1;
page->items[0] = *receive;
AdjustParent(dpage);
(*this)(dpage).isdirty = true;
root = (*this)[homeblock.AuthorRoot];
root->parent = dpage;
root->parentidx = -1;
(*this)(homeblock.AuthorRoot).isdirty = true;
homeblock.AuthorRoot = dpage;
homedirty = true;
//dumphome(&homeblock,"InsertAuthor (new root)");
}
return(item.data);
}
// Insertion for the Subject tree
DiskRecord vBTree::InsertSubj (Key key,Record* newdata)
{
Item *receive, item;
Page *page, *root;
DiskPage dpage;
strucase(item.key,key);
item.data = PageFile::WriteRecord(newdata->buffer,newdata->size);
item.right = 0;
if (homeblock.SubjRoot == 0) {
homeblock.SubjRoot = NewPage();
homedirty = true;
root = (*this)[homeblock.SubjRoot];
root->left = 0;
root->parent = 0;
root->parentidx = -1;
root->items[0] = item;
root->size = 1;
(*this)(homeblock.SubjRoot).isdirty = true;
//dumphome(&homeblock,"InsertSubj (new tree)");
} else if ((receive = InsertAux(&item,homeblock.SubjRoot)) != 0) {
dpage = NewPage();
page = (*this)[dpage];
page->size = 1;
page->left = homeblock.SubjRoot;
page->parent = 0;
page->parentidx = -1;
page->items[0] = *receive;
AdjustParent(dpage);
(*this)(dpage).isdirty = true;
root = (*this)[homeblock.SubjRoot];
root->parent = dpage;
root->parentidx = -1;
(*this)(homeblock.SubjRoot).isdirty = true;
homeblock.SubjRoot = dpage;
homedirty = true;
//dumphome(&homeblock,"InsertSubj (new root)");
}
return(item.data);
}
// Common helper function for Inserting
Item* vBTree::InsertAux (Item* item, DiskPage dnode)
{
register Page* node = (*this)[dnode];
int idx, size, half;
if (BinarySearch(node,item->key,&idx)) {
// Modified to allow replacement
node->items[idx].data = item->data;
(*this)(dnode).isdirty = true;
return(0); // already in tree
}
DiskPage dchild = (idx < 0 ? node->left : node->items[idx].right);
if (dchild != 0) item = InsertAux(item,dchild); // child is not e leaf
// node is a leaf or passed up
if (item != 0) {
node = (*this)[dnode];
if (node->size < 2*Order) { // insert in the node
node->size = InsertItem(item,node->items,idx+1,
node->size);
AdjustParent(dnode);
(*this)(dnode).isdirty = true;
} else { // node is full, split
DiskPage dpage = NewPage();
register Page* page;
node = (*this)[dnode];
size = CopyItems(node->items, buf, node->size);
size = InsertItem(item,buf,idx+1,size);
node->size = CopyItems(buf,node->items,half=size/2);
(*this)(dnode).isdirty = true;
page = (*this)[dpage];
page->size = CopyItems(buf+half+1,page->items,size-half-1);
page->left = buf[half].right;
(*this)(dpage).isdirty = true;
*item = buf[half]; // the mid item
item->right = dpage;
return(item);
}
}
return(0);
}
// Deletion for Id tree...
void vBTree::DeleteId (Key key)
{
Boolean underflow;
DiskPage dtemp;
if (homeblock.IdRoot == 0) return;
DeleteAux1(key,homeblock.IdRoot,&underflow);
Page *root = (*this)[homeblock.IdRoot];
if (underflow && root->size == 0) { // dispose root
dtemp = homeblock.IdRoot;
homeblock.IdRoot = root->left;
homedirty = true;
FreePage(dtemp);
//dumphome(&homeblock,"DeleteId (new root)");
if (homeblock.IdRoot == 0) return;
root = (*this)[homeblock.IdRoot];
root->parent = 0;
root->parentidx = 0;
(*this)(homeblock.IdRoot).isdirty = true;
}
}
// Deletion for Title tree
void vBTree::DeleteTitle (Key key)
{
Boolean underflow;
DiskPage dtemp;
if (homeblock.TitleRoot == 0) return;
DeleteAux1(key,homeblock.TitleRoot,&underflow);
Page *root = (*this)[homeblock.TitleRoot];
if (underflow && root->size == 0) { // dispose root
dtemp = homeblock.TitleRoot;
homeblock.TitleRoot = root->left;
homedirty = true;
FreePage(dtemp);
//dumphome(&homeblock,"DeleteTitle (new root)");
if (homeblock.TitleRoot == 0) return;
root = (*this)[homeblock.TitleRoot];
root->parent = 0;
root->parentidx = 0;
(*this)(homeblock.TitleRoot).isdirty = true;
}
}
// Deletion for Author tree...
void vBTree::DeleteAuthor (Key key)
{
Boolean underflow;
DiskPage dtemp;
if (homeblock.AuthorRoot == 0) return;
DeleteAux1(key,homeblock.AuthorRoot,&underflow);
Page *root = (*this)[homeblock.AuthorRoot];
if (underflow && root->size == 0) { // dispose root
dtemp = homeblock.AuthorRoot;
homeblock.AuthorRoot = root->left;
homedirty = true;
FreePage(dtemp);
//dumphome(&homeblock,"DeleteAuthor (new root)");
if (homeblock.AuthorRoot == 0) return;
root = (*this)[homeblock.AuthorRoot];
root->parent = 0;
root->parentidx = 0;
(*this)(homeblock.AuthorRoot).isdirty = true;
}
}
// Deletion for Subject tree
void vBTree::DeleteSubj (Key key)
{
Boolean underflow;
DiskPage dtemp;
if (homeblock.SubjRoot == 0) return;
DeleteAux1(key,homeblock.SubjRoot,&underflow);
Page *root = (*this)[homeblock.SubjRoot];
if (underflow && root->size == 0) { // dispose root
dtemp = homeblock.SubjRoot;
homeblock.SubjRoot = root->left;
homedirty = true;
FreePage(dtemp);
//dumphome(&homeblock,"DeleteSubj (new root)");
if (homeblock.SubjRoot == 0) return;
root = (*this)[homeblock.SubjRoot];
root->parent = 0;
root->parentidx = 0;
(*this)(homeblock.SubjRoot).isdirty = true;
}
}
// First helper function for deleting
void vBTree::DeleteAux1(Key key, DiskPage dnode, Boolean* underflow)
{
Page *node;
DiskPage dchild;
int idx;
*underflow = false;
if (dnode == 0) return;
node = (*this)[dnode];
if (BinarySearch(node,key,&idx)) {
dchild = (idx - 1 < 0 ? node->left
: node->items[idx-1].right);
if (dchild == 0) {
// node is a leaf
node->size = DeleteItem(node->items,idx,node->size);
(*this)(dnode).isdirty = true;
*underflow = node->size < Order;
} else { // node is a subtree
// delete from subtree
DeleteAux2(dnode,dchild,idx,underflow);
if (*underflow)
Underflow(dnode,dchild,idx-1,underflow);
}
} else { // is not in this node
dchild = (idx < 0 ? node->left : node->items[idx].right);
DeleteAux1(key,dchild,underflow); // should be in child
if (*underflow)
Underflow(dnode,dchild,idx,underflow);
}
}
// Second helper function, subtree deletion
void vBTree::DeleteAux2 (DiskPage dparent, DiskPage dnode, int idx, Boolean* underflow)
{
Page* node = (*this)[dnode];
DiskPage dchild;
Page* child;
dchild = node->items[node->size-1].right;
if (dchild != 0) { // node is not is leaf
child = (*this)[dchild];
// go another level down
DeleteAux2(dparent,dchild,idx,underflow);
node = (*this)[dnode];
if (*underflow)
Underflow(dnode,dchild,node->size-1,underflow);
} else { // node is a leaf
DiskPage dright;
Page* parent = (*this)[dparent];
node = (*this)[dnode];
dright = parent->items[idx].right;
parent->items[idx] = node->items[node->size-1];
parent->items[idx].right = dright;
(*this)(dparent).isdirty = true;
node->size = DeleteItem(node->items,node->size-1,node->size);
(*this)(dnode).isdirty = true;
*underflow = node->size < Order;
}
}
// Underflow handler...
void vBTree::Underflow (DiskPage dnode, DiskPage dchild,int idx,Boolean* underflow)
{
register Page* node = (*this)[dnode];
DiskPage dleft;
if (idx < ((node->size)-1))
dleft = dchild;
else {
if (idx == 0) dleft = node->left;
else {
int prev = idx-1;
//cout << "Taking prev = " << prev << "\n";
dleft = node->items[prev].right;
}
}
register Page* left;
DiskPage dright;
if (dleft == dchild) {
idx++;
node = (*this)[dnode];
dright = node->items[idx].right;
} else dright = dchild;
register Page* right;
register int size, half;
// copy contents of the left, parent, and right into buf
left = (*this)[dleft];
size = CopyItems(left->items,buf,left->size);
node = (*this)[dnode];
buf[size] = node->items[idx];
right = (*this)[dright];
buf[size++].right = right->left;
size += CopyItems(right->items,buf+size,right->size);
if (size > 2*Order) { // distribute buf between the left and right
left = (*this)[dleft];
left->size = CopyItems(buf,left->items,half = size/2);
AdjustParent(dleft);
(*this)(dleft).isdirty = true;
right = (*this)[dright];
right->size = CopyItems(buf+half+1,right->items,size-half-1);
right->left = buf[half].right;
AdjustParent(dright);
right = (*this)[dright];
right->parent = dnode;
right->parentidx = idx;
(*this)(dright).isdirty = true;
node = (*this)[dnode];
node->items[idx] = buf[half];
node->items[idx].right = dright;
(*this)(dnode).isdirty = true;
*underflow = false;
} else { // merge, and free the right page.
left = (*this)[dleft];
left->size = CopyItems(buf,left->items,size);
AdjustParent(dleft);
(*this)(dleft).isdirty = true;
node = (*this)[dnode];
node->size = DeleteItem(node->items,idx,node->size);
(*this)(dnode).isdirty = true;
FreePage(dright);
*underflow = node->size < Order;
}
}
// Parentage adjuster. Makes sure the parent pointers are correct.
void vBTree::AdjustParent (DiskPage dparent)
{
int idx;
DiskPage dnode;
Page *node, *parent = (*this)[dparent];
int psize = parent->size;
parent = (*this)[dparent];
dnode = parent->left;
if (dnode != 0) {
node = (*this)[dnode];
if (node->parent != dparent ||
node->parentidx != -1) {
node->parent = dparent;
node->parentidx = -1;
(*this)(dnode).isdirty = true;
}
}
for (idx=0; idx < psize; idx++) {
parent = (*this)[dparent];
dnode = parent->items[idx].right;
if (dnode != 0) {
node = (*this)[dnode];
if (node->parent !=
dparent ||
node->parentidx != idx) {
node->parent = dparent;
node->parentidx = idx;
(*this)(dnode).isdirty = true;
}
}
}
}
// Item hacking code - copy items, insert an item and delete an item
int vBTree::CopyItems (Item* src,Item* dest,int count)
{
for (int i = 0; i < count; ++i) // straight copy
dest[i] = src[i];
return count;
}
int vBTree::InsertItem (Item* item,Item* items,int idx,int size)
{
for (int i = size; i > idx; --i) // shift right
items[i] = items[i-1];
items[idx] = *item; // insert
return size + 1;
}
int vBTree::DeleteItem (Item* items,int idx,int size)
{
for (int i = idx; i < size; ++i) // shift left
items[i] = items[i+1];
return size - 1;
}
// Raw printing function. Much like in the book. The data is printed as
// the size and offset of the disk record.
void vBTree::PrintAux(DiskPage dnode, int margin)
{
char margBuf[128];
Page* node;
if (dnode != 0) {
node = (*this)[dnode];
for (int i = 0; i < margin; ++i) margBuf[i] = ' ';
margBuf[i] = 0;
int nsize = node->size;
PrintAux(node->left,margin+8);
for (i = 0; i < nsize; ++i) {
node = (*this)[dnode];
cout << form("%s(%s [%d:%d])\n",
margBuf,node->items[i].key,
node->items[i].data.record_size,
node->items[i].data.record_address);
PrintAux(node->items[i].right,margin+8);
}
}
}
// page counting function. Allows applications that need this info
// do things smart (preallocating the pages for a compact output file)
int vBTree::CountPagesAux(DiskPage dnode)
{
int count = 0;
Page* node;
if (dnode != 0) {
count++;
node = (*this)[dnode];
//cout << "*** dnode = " << dnode.record_address << "\n"; DumpPage(node);
count += CountPagesAux(node->left);
node = (*this)[dnode];
int nsize = node->size;
for (int i = 0; i < nsize; ++i) {
count += CountPagesAux(node->items[i].right);
node = (*this)[dnode];
}
}
return(count);
}
// Tree traversal function. Allows "sequential" access to a tree
void vBTree::TravAux(DiskPage dnode,TravFunc tfun,int level)
{
CoreItem item;
Page* node;
if (dnode != 0) {
node = (*this)[dnode];
TravAux(node->left,tfun,level+1);
node = (*this)[dnode];
int nsize = node->size;
for (int i = 0; i < nsize; ++i) {
strcpy(item.key,node->items[i].key);
item.data.NewBuffer(node->items[i].data.record_size);
int bytesread =
PageFile::ReadRecord(node->items[i].data,
item.data.buffer,
item.data.size);
if (bytesread < 0) {
Error(sysErr,"PageFile::ReadRecord");
item.data.NewBuffer(0);
}
(*tfun)(&item,level);
node = (*this)[dnode];
TravAux(node->items[i].right,tfun,level+1);
}
}
}
// Generic error handler
void vBTree::Error (ErrKind err,const char* msg)
{
if (errFun != 0) (*errFun)(err,msg);
else {
if (err == sysErr) {
int error = errno;
cerr << form("Error: %s %s\n",strerror(error),msg);
exit(error);
} else {
cerr << form("Error: %s %s\n",
(err == termErr ? "Terminal" : "Memory"),
msg);
exit(1);
}
}
}