<![CDATA[
/*
Copyright (c) 1999, Gary Yihsiang Hsiao. All Rights Reserved.
bugs report to: ghsiao@rbcds.com or ghsiao@netzero.net
Permission to use, copy, modify, and distribute this software
for NON-COMMERCIAL purposes and without fee
is hereby granted provided that this copyright notice
appears in all copies. This software is distributed on an 'as is'
basis without warranty.
Release: 1.0 15-Sept-1999
*/
#include <stdio.h>
#include <sys/stat.h>
#include <memory.h>
#include "DskMBTree.h"
#include <strings.h>
// Show a BTnode
ostream&
operator<<(ostream& os, BTnode& nd)
{
os << "keycount=" << nd.data().keycount << " numtrees=" << nd.data().numtrees << endl;
cout << "keys= ";
for(int i=0; i < BTnode::MAXKEYS ; i++)
os << nd.data().key[i] << " " ;
os << endl;
cout << "data= "http://www.geocities.com/leapingfrog/cpp/persist/;%20%20%20%20for(int%20i=0;%20i%20<%20BTnode::MAXKEYS%20;%20i++)%20%20%20%20%20%20%20%20os%20<<%20nd.data().data[i]%20<<" " ;
os << endl;
cout << "childs= ";
for(int i=0; i < BTnode::MAXKEYS+1 ; i++)
os << nd.data().child[i] << " " ;
os << endl;
}
BTnode::BTnode()
{
bzero((char*)(&node), sizeof(BTnode::BTnodeStruct));
}
BTnode::BTnode(const BTnode& nd)
{
this->operator=(nd);
}
BTnode& BTnode::operator=(const BTnode& nd)
{
memcpy((char*)(&node), (char*)(&(nd.node)), sizeof(BTnode::BTnodeStruct));
}
void BTnode::clear()
{
bzero((char*)(&node), sizeof(BTnode::BTnodeStruct));
}
//===============================================================
BTnodeAvl::BTnodeAvl()
{
}
BTnodeAvl::BTnodeAvl(const char* fname)
{
try{
open_avl(fname);
} catch(BTreeException* e) {
cout << *e << endl;
exit(-1);
}
}
BTnodeAvl::~BTnodeAvl()
{
updateDskAvl();
}
void BTnodeAvl::open_avl(const char* fname) throw (BTreeException*)
{
_iof.open(fname, ios::in|ios::out|ios::binary);
if(!_iof)
throw new BTreeException(BTreeException::FILE_OPEN_ERROR, "BTnodeAvl::open_avl");
int ret;
struct stat result;
if(!(ret=fstat(_iof.rdbuf()->fd(), &result))) {
if(result.st_size) {
const int num = result.st_size/sizeof(streampos);
streampos ploc[num];
_iof.read((char*)(ploc), num*sizeof(streampos));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_READ_ERROR, "BTnodeAvl::open_avl");
for(int i = 0; i < num; i++) {
_avl.push(ploc[i]);
}
}
}
_name = fname;
_iof.seekp(0L, ios::end);
_markp = _iof.tellp();
}
bool BTnodeAvl::isEmpty()
{
return _avl.empty();
}
streampos BTnodeAvl::getAvl() throw (BTreeException*)
{
if(!_avl.size()) return -1;
streampos loc = _avl.top();
_avl.pop();
streampos dkpos;
_iof.seekg(_markp-sizeof(streampos), ios::beg);
_iof.read((char*)(&dkpos), sizeof(streampos));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_READ_ERROR, "BTnodeAvl::getAvl");
if(loc != dkpos) {
cout << "Error: file offset not matched" << endl;
throw new BTreeException(BTreeException::OBJ_POSITION_NOT_MATCH, "BTnodeAvl::getAvl");
}
dkpos = 0;
_iof.seekp(_markp-sizeof(streampos), ios::beg);
_iof.write((char*)(&dkpos), sizeof(streampos));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "BTnodeAvl::getAvl");
_iof.seekp(_markp-sizeof(streampos), ios::beg);
_markp = _iof.tellp();
return loc;
}
void BTnodeAvl::addAvl(streampos loc)
{
_avl.push(loc);
_iof.write((char*)(&loc), sizeof(streampos));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "BTnodeAvl::addAvl");
_markp = _iof.tellp();
}
void BTnodeAvl::updateDskAvl() throw (BTreeException*)
{
const int size = _avl.size();
streampos ploc[size];
int ks, sz = _avl.size();
ks = sz;
for(; sz > 0 ;) {
ploc[--sz] = _avl.top();
_avl.pop();
}
_iof.close();
remove(_name.c_str());
_iof.open(_name.c_str(), ios::in|ios::out|ios::binary);
if(!_iof)
throw new BTreeException(BTreeException::FILE_OPEN_ERROR, "BTnodeAvl::updataDskAvl");
_iof.write((char*)(ploc), sizeof(streampos)*ks);
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "BTnodeAvl::updateDskAvl");
_iof.close();
}
size_t BTnodeAvl::size()
{
return _avl.size();
}
//===============================================================
DskMBTree::DskMBTree(const char* fname)
{
try{
open_root(fname);
} catch(BTreeException* e) {
cout << *e << endl;
exit(-1);
}
}
DskMBTree::DskMBTree()
{
}
DskMBTree::~DskMBTree()
{
}
void DskMBTree::open_root(const char* fname)
throw (BTreeException*)
{
_iof.open(fname, ios::in|ios::out|ios::binary);
if(!_iof)
throw new BTreeException(BTreeException::FILE_OPEN_ERROR, "DskMBTree::open_root");
_iof.seekp(0L, ios::end);
_markp = _iof.tellp();
string avlname;
if(!strchr(fname, '.')) {
avlname = fname; avlname += ".avl";
}
else {
string str = fname;
int i = str.find('.');
str.erase(i);
avlname = str + ".avl";
}
_avlnd.open_avl(avlname.c_str());
}
bool DskMBTree::get_root(BTnode& root)
throw (BTreeException*)
{
_iof.seekg(0L, ios::beg);
int ret;
struct stat result;
if(!(ret=fstat(_iof.rdbuf()->fd(), &result))) {
if(!result.st_size) return false;
}
else
throw new BTreeException(BTreeException::FILE_DATA_READ_ERROR, "DskMBTree::get_root");
_iof.read((char*)(&(root.data())), sizeof(BTnode::BTnodeStruct));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_READ_ERROR, "DskMBTree::get_root");
return true;
}
void DskMBTree::makeroot(const long k, streampos dat)
throw (BTreeException*)
{
BTnode nd;
nd.data().keycount = 1;
nd.data().numtrees = 2;
nd.data().key[0] = k;
nd.data().data[0] = dat;
_iof.seekg(0L, ios::beg);
_iof.seekp(0L, ios::beg);
_iof.write((char*)(&(nd.data())), sizeof(BTnode::BTnodeStruct));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "DskMBTree::makeroot");
_markp = _iof.tellp();
}
void DskMBTree::insert(slist<PATHNODE>& path,
long k, streampos dat)
{
int pos;
BTnode nd, nnd;
streampos newnodeloc = 0;
slist<PATHNODE>::iterator itr = path.begin();
while(itr != path.end()) {
nd = (*itr).first;
streampos loc = ((*itr).second).first;
pos = ((*itr++).second).second;
long midkey;
streampos middat;
nnd.clear();
if(nd.data().numtrees == BTnode::MAXKEYS+1) {
split(loc, pos, nd, nnd, k, dat, midkey, middat, newnodeloc);
k = midkey;
dat = middat;
}
else if(nd.data().numtrees < BTnode::MAXKEYS+1) {
insertnode(nd, pos, k, dat, newnodeloc);
updatenode(loc, nd);
return;
}
}
//*
//* make new tree
//*
BTnode nroot;
nroot.data().keycount = 1;
nroot.data().numtrees = 2;
nroot.data().key[0] = k;
nroot.data().data[0] = dat;
maketree(nroot, makenode(nd), newnodeloc);
}
bool DskMBTree::deleten(long key, slist<PATHNODE>& path)
{
int pos;
long delkey = key;
if(!find(pos, path, key)) return false;
else {
PATHNODE path_node = path.front();
BTnode del_nd = path_node.first;
bool isleaf = true;
for(int i = 1; i < del_nd.data().numtrees; ++i)
if(del_nd.data().child[i-1] != del_nd.data().child[i]) {
isleaf = false;
break;
}
long skey;
streampos sdata;
if(!isleaf) {
streampos loc = path_node.second.first;
path.clear();
addpath(path, del_nd, loc, pos+1);
PATHNODE& rfpath = path.front();
//* go to the right sibling
find_smallest(del_nd.data().child[pos+1], skey, sdata, path);
//*
//* delete a none-leaf node's value
//*
del_nd.data().key[pos] = skey;
del_nd.data().data[pos] = sdata;
updatenode(loc, del_nd);
rfpath.first = del_nd; //update path node
delkey = skey;
path_node = path.front();
del_nd = path_node.first;
pos = path_node.second.second;
}
//* It is a leaf node
//* (*)
if(del_nd.data().keycount > 1) {
delete_leafval(pos, delkey, del_nd);
updatenode(path_node.second.first, del_nd);
}
else {
slist<DskMBTree::PATHNODE>::iterator itr = path.begin();
streampos del_loc = (*itr++).second.first;
PATHNODE pn = *itr;
BTnode nd = pn.first;
int ppos = pn.second.second;
long keycount = nd.data().keycount;
if(keycount > 1 ) {
if(ppos == nd.data().numtrees - 1) {
//*
//* No right child
//* (*)
_avlnd.addAvl(del_loc);
long mkey = nd.data().key[ppos-1];
streampos mdat = nd.data().data[ppos-1];
delete_nodeval(ppos-1, mkey, nd);
updatenode(pn.second.first, nd);
BTnode lnd;
child(nd.data().child[ppos-1], lnd);
path.pop_front(); //* remove delete node from path
addpath(path, lnd, nd.data().child[ppos-1], lnd.data().keycount);
insert(path, mkey, mdat);
return true;
}
else if(ppos == 0) {
//*
//* No left child
//* (*)
_avlnd.addAvl(del_loc);
long mkey = nd.data().key[ppos];
streampos mdat = nd.data().data[ppos];
delete_nodeval(ppos, mkey, nd);
updatenode(pn.second.first, nd);
BTnode rnd;
child(nd.data().child[ppos], rnd);
path.pop_front(); //* remove delete node from path
addpath(path, rnd, nd.data().child[ppos], 0);
insert(path, mkey, mdat);
return true;
}
else {
//(*)
BTnode rnd;
child(nd.data().child[ppos+1], rnd);
streampos rloc = nd.data().child[ppos+1];
if(rnd.data().keycount > 1) {
long mkey = nd.data().key[ppos];
streampos mdat = nd.data().data[ppos];
nd.data().key[ppos] = rnd.data().key[0];
nd.data().data[ppos] = rnd.data().data[0];
delete_leafval(0, rnd.data().key[0], rnd);
updatenode(pn.second.first, nd);
updatenode(nd.data().child[ppos+1], rnd);
del_nd.data().key[0] = mkey;
del_nd.data().data[0] = mdat;
updatenode(path_node.second.first, del_nd);
return true;
}
//(*)
BTnode lnd;
child(nd.data().child[ppos-1], lnd);
if(lnd.data().keycount > 1) {
long mkey = nd.data().key[ppos-1];
streampos mdat = nd.data().data[ppos-1];
nd.data().key[ppos-1] = lnd.data().key[lnd.data().keycount-1];
nd.data().data[ppos-1] = lnd.data().data[lnd.data().keycount-1];
delete_leafval(lnd.data().keycount-1, lnd.data().key[lnd.data().keycount-1], lnd);
updatenode(pn.second.first, nd);
updatenode(nd.data().child[ppos-1], lnd);
del_nd.data().key[0] = mkey;
del_nd.data().data[0] = mdat;
updatenode(path_node.second.first, del_nd);
return true;
}
//* midd:with no naighbour has more than 1 key
//(*)
long mkey = nd.data().key[ppos];
streampos mdat = nd.data().data[ppos];
delete_nodeval(ppos, mkey, nd);
updatenode(pn.second.first, nd);
path.pop_front(); //* remove del_nd node from path
addpath(path, rnd, rloc, 0);
insert(path, mkey, mdat);
_avlnd.addAvl(del_loc);
}
}
else {
slist<DskMBTree::PATHNODE>::iterator itr = path.begin();
PATHNODE pn = *++itr;
streampos nd_loc = pn.second.first;
BTnode nd = pn.first;
BTnode rnd, lnd;
streampos lnd_loc, rnd_loc;
lnd_loc = nd.data().child[0];
rnd_loc = nd.data().child[1];
child(lnd_loc, lnd);
child(rnd_loc, rnd);
int ppos = pn.second.second;
if(ppos == 0) {
if(rnd.data().keycount > 1) {
lnd.data().key[0] = nd.data().key[0];
lnd.data().data[0] = nd.data().data[0];
updatenode(lnd_loc, lnd);
nd.data().key[0] = rnd.data().key[0];
nd.data().data[0] = rnd.data().data[0];
updatenode(nd_loc, nd);
delete_leafval(0, rnd.data().key[0], rnd);
updatenode(rnd_loc, rnd);
}
else {
//* free l-node, and concate with r-node
nd.data().child[0] = 0;
nd.data().child[1] = 0;
nd.data().key[1] = rnd.data().key[0];
nd.data().data[1] = rnd.data().data[0];
nd.data().keycount = 2;
nd.data().numtrees = 3;
updatenode(nd_loc, nd);
_avlnd.addAvl(lnd_loc);
_avlnd.addAvl(rnd_loc);
//* free r/l-node
}
}
else {
if(lnd.data().keycount > 1) {
rnd.data().key[0] = nd.data().key[0];
rnd.data().data[0] = nd.data().data[0];
updatenode(rnd_loc, rnd);
nd.data().key[0] = lnd.data().key[lnd.data().keycount-1];
nd.data().data[0] = lnd.data().data[lnd.data().keycount-1];
updatenode(nd_loc, nd);
delete_leafval(lnd.data().keycount-1, lnd.data().key[lnd.data().keycount-1], lnd);
updatenode(lnd_loc, lnd);
}
else {
//* free r-node, and concate with l-node
nd.data().child[0] = 0;
nd.data().child[1] = 0;
nd.data().key[1] = nd.data().key[0];
nd.data().data[1] = nd.data().data[0];
nd.data().key[0] = lnd.data().key[0];
nd.data().data[0] = lnd.data().data[0];
nd.data().keycount = 2;
nd.data().numtrees = 3;
updatenode(nd_loc, nd);
_avlnd.addAvl(rnd_loc);
_avlnd.addAvl(lnd_loc);
//* free l/r-node
}
}
}
}
}
}
void DskMBTree::find_smallest(streampos loc, long& skey, streampos& sdata, slist<PATHNODE>& path)
{
BTnode nd;
if(loc) {
child(loc, nd); //* get child from location loc
addpath(path, nd, loc, 0);
}
else return ;
while ( (loc = nd.data().child[0]) ) {
child(loc, nd);
addpath(path, nd, loc, 0);
}
skey = nd.data().key[0];
sdata = nd.data().data[0];
}
int DskMBTree::delete_nodeval(int kpos, long dkey, BTnode& nd)
throw (BTreeException*)
{
unsigned long bf[BTnode::MAXKEYS+1];
bzero((char*)(&bf), sizeof(long));
int keycount = nd.data().keycount;
if(dkey != nd.data().key[kpos]) {
cout << "delete_nodeval(" << kpos << ")::key not matched" << endl;
throw new BTreeException(BTreeException::NODE_KEY_NOT_MATCH, "DskMBTree::delete_nodeval");
}
if(keycount == 1) {
cout << "Error keycount:" << keycount << endl;
throw new BTreeException(BTreeException::INVALID_KEY_COUNT, "DskMBTree::delete_nodeval");
}
if(kpos == 0) {
memcpy(bf, &(nd.data().key[1]), (keycount-1)*sizeof(long));
memcpy(nd.data().key, bf, (keycount-1)*sizeof(long));
memcpy(bf, &(nd.data().data[1]), (keycount-1)*sizeof(long));
memcpy(nd.data().data, bf, (keycount-1)*sizeof(long));
memcpy(bf, &(nd.data().child[1]), keycount*sizeof(long));
memcpy(nd.data().child, bf, keycount*sizeof(long));
}
else if(kpos > 0 && kpos < keycount - 1) {
memcpy(bf, &(nd.data().key[kpos+1]), ((keycount-kpos)-1)*sizeof(long));
memcpy(&(nd.data().key[kpos]), bf, ((keycount-kpos)-1)*sizeof(long));
memcpy(bf, &(nd.data().data[kpos+1]), ((keycount-kpos)-1)*sizeof(long));
memcpy(&(nd.data().data[kpos]), bf, ((keycount-kpos)-1)*sizeof(long));
memcpy(bf, &(nd.data().child[kpos+1]), (keycount-kpos)*sizeof(long));
memcpy(&(nd.data().child[kpos]), bf, (keycount-kpos)*sizeof(long));
}
else {
//* nd.data().child[keycount-1] = nd.data().child[keycount];
}
nd.data().key[keycount-1] = 0;
nd.data().data[keycount-1] = 0;
nd.data().child[keycount] = 0;
--nd.data().keycount;
--nd.data().numtrees;
return nd.data().keycount;
}
int DskMBTree::delete_leafval(int kpos, long dkey, BTnode& nd)
throw (BTreeException*)
{
unsigned long bf[BTnode::MAXKEYS+1];
bzero((char*)(&bf), sizeof(long));
int keycount = nd.data().keycount;
if(dkey != nd.data().key[kpos]) {
cout << "delete_leafval(" << kpos << ")::key not matched" << endl;
throw new BTreeException(BTreeException::NODE_KEY_NOT_MATCH, "DskMBTree::delete_leafval");
}
if(keycount == 1) {
nd.data().key[kpos] = 0;
nd.data().data[kpos] = 0;
nd.data().keycount = 0;
nd.data().numtrees = 0;
return 0;
}
if(kpos == 0) {
memcpy(bf, &(nd.data().key[1]), (keycount-1)*sizeof(long));
memcpy(nd.data().key, bf, (keycount-1)*sizeof(long));
memcpy(bf, &(nd.data().data[1]), (keycount-1)*sizeof(long));
memcpy(nd.data().data, bf, (keycount-1)*sizeof(long));
}
else if(kpos > 0 && kpos < keycount - 1) {
memcpy(bf, &(nd.data().key[kpos+1]), ((keycount-kpos)-1)*sizeof(long));
memcpy(&(nd.data().key[kpos]), bf, ((keycount-kpos)-1)*sizeof(long));
memcpy(bf, &(nd.data().data[kpos+1]), ((keycount-kpos)-1)*sizeof(long));
memcpy(&(nd.data().data[kpos]), bf, ((keycount-kpos)-1)*sizeof(long));
}
nd.data().key[keycount-1] = 0;
nd.data().data[keycount-1] = 0;
--nd.data().keycount;
--nd.data().numtrees;
return nd.data().keycount;
}
//* Change root node
void DskMBTree::maketree(BTnode& nd,
const streampos left, const streampos right)
throw (BTreeException*)
{
nd.data().child[0] = left;
nd.data().child[1] = right;
_iof.seekp(0L, ios::beg);
_iof.write((char*)(&(nd.data())), sizeof(BTnode::BTnodeStruct));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "DskMBTree::maketree");
}
void DskMBTree::split(streampos loc, int pos, BTnode& nd, BTnode& nnd,
const long k, streampos dat,
long& mk, streampos& md, streampos& son)
{
if(pos > BTnode::MID) {
mk = nd.data().key[BTnode::MID];
md = nd.data().data[BTnode::MID];
memcpy(nnd.data().key, &(nd.data().key[BTnode::MID+1]), (BTnode::MID)*sizeof(long));
memcpy(nnd.data().data, &(nd.data().data[BTnode::MID+1]), (BTnode::MID)*sizeof(streampos));
memcpy(nnd.data().child, &(nd.data().child[BTnode::MID+1]), (BTnode::MID+1)*sizeof(streampos));
bzero((char *) &(nd.data().key[BTnode::MID]), (BTnode::MID+1)*sizeof(long));
bzero((char *) &(nd.data().data[BTnode::MID]), (BTnode::MID+1)*sizeof(streampos));
bzero((char *) &(nd.data().child[BTnode::MID+1]), (BTnode::MID+1)*sizeof(streampos));
nd.data().keycount = BTnode::MID;
nd.data().numtrees = BTnode::MID + 1;
nnd.data().keycount = BTnode::MID;
nnd.data().numtrees = BTnode::MID + 1;
updatenode(loc, nd);
insertnode(nnd, pos-(BTnode::MID)-1, k, dat, son);
son = makenode(nnd);
}
else if(pos == BTnode::MID) {
mk = k;
md = dat;
memcpy(nnd.data().key, &(nd.data().key[BTnode::MID]), (BTnode::MID+1)*sizeof(long));
memcpy(nnd.data().data, &(nd.data().data[BTnode::MID]), (BTnode::MID+1)*sizeof(streampos));
memcpy(&nnd.data().child[1], &(nd.data().child[BTnode::MID+1]), (BTnode::MID+1)*sizeof(streampos));
nnd.data().child[0] = son;
bzero((char *) &(nd.data().key[BTnode::MID]), (BTnode::MID+1)*sizeof(long));
bzero((char *) &(nd.data().data[BTnode::MID]), (BTnode::MID+1)*sizeof(streampos));
bzero((char *) &(nd.data().child[BTnode::MID+1]), (BTnode::MID+1)*sizeof(streampos));
nd.data().keycount = BTnode::MID;
nd.data().numtrees = BTnode::MID + 1;
nnd.data().keycount = BTnode::MID + 1;
nnd.data().numtrees = BTnode::MID + 2;
updatenode(loc, nd);
son = makenode(nnd);
}
else {
mk = nd.data().key[BTnode::MID];
md = nd.data().data[BTnode::MID];
memcpy(nnd.data().key, &(nd.data().key[BTnode::MID+1]), (BTnode::MID)*sizeof(long));
memcpy(nnd.data().data, &(nd.data().data[BTnode::MID+1]), (BTnode::MID)*sizeof(streampos));
memcpy(nnd.data().child, &(nd.data().child[BTnode::MID+1]), (BTnode::MID+1)*sizeof(streampos));
bzero((char *) &(nd.data().key[BTnode::MID]), (BTnode::MID+1)*sizeof(long));
bzero((char *) &(nd.data().data[BTnode::MID]), (BTnode::MID+1)*sizeof(streampos));
bzero((char *) &(nd.data().child[BTnode::MID+1]), (BTnode::MID+1)*sizeof(streampos));
nd.data().keycount = BTnode::MID;
nd.data().numtrees = BTnode::MID + 1;
nnd.data().keycount = BTnode::MID;
nnd.data().numtrees = BTnode::MID + 1;
insertnode(nd, pos, k, dat, son);
updatenode(loc, nd);
son = makenode(nnd);
}
}
void DskMBTree::insertnode(BTnode& nd, int pos,
const long k, streampos dat, streampos son)
{
if(pos > nd.data().numtrees - 1) {
cout << "insertnode::overflow" << endl;
return;
}
if(pos >= nd.data().keycount) {
nd.data().key[nd.data().keycount] = k;
nd.data().data[nd.data().keycount++] = dat;
nd.data().child[pos+1] = son;
++nd.data().numtrees;
}
else {
unsigned long buf[BTnode::MAXKEYS];
memcpy(buf, &(nd.data().key[pos]),
(nd.data().keycount - pos)*sizeof(const long) );
memcpy(&(nd.data().key[pos+1]), buf,
(nd.data().keycount - pos)*sizeof(const long) );
memcpy(buf, &(nd.data().data[pos]),
(nd.data().keycount - pos)*sizeof(const long) );
memcpy(&(nd.data().data[pos+1]), buf,
(nd.data().keycount - pos)*sizeof(const long) );
memcpy(buf, &(nd.data().child[pos+1]),
(nd.data().numtrees - (pos+1))*sizeof(const long) );
memcpy(&(nd.data().child[pos+2]), buf,
(nd.data().numtrees - (pos+1))*sizeof(const long) );
nd.data().key[pos] = k;
nd.data().data[pos] = dat;
nd.data().child[pos+1] = son;
++nd.data().keycount;
++nd.data().numtrees;
}
}
void DskMBTree::updatenode(streampos loc, const BTnode& nd)
throw (BTreeException*)
{
_iof.seekp(loc, ios::beg);
BTnode& rnd = const_cast<BTnode&>(nd);
_iof.write((char*)(&(rnd.data())), sizeof(BTnode::BTnodeStruct));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "DskMBTree::updatenode");
_iof.seekp(_markp, ios::beg);
}
streampos DskMBTree::makenode(const BTnode& nd)
throw (BTreeException*)
{
bool new_loc = true;
streampos loc;
if(_avlnd.isEmpty()) {
loc = _markp;
_iof.seekp(_markp, ios::beg);
}
else {
new_loc = false;
loc = _avlnd.getAvl();
_iof.seekp(loc, ios::beg);
}
BTnode& rnd = const_cast<BTnode&>(nd);
_iof.write((char*)(&(rnd.data())), sizeof(BTnode::BTnodeStruct));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_WRITE_ERROR, "makenode");
if(new_loc)
_markp = _iof.tellp();
return loc;
}
int DskMBTree::nodesearch(BTnode& nd, const unsigned long key)
{
unsigned long *p = nd.data().key;
int max = nd.data().keycount;
return binsrch(p, key, max);
}
int DskMBTree::binsrch(const unsigned long a[],
const unsigned long key, int max)
{
int mid, lower = 0, upper = max - 1;
if(key > a[upper]) return max;
if(key < a[lower]) return lower;
while(lower < upper) {
mid = (lower+upper)/2;
if(key == a[mid]) return mid;
else if(key > a[mid]) lower = mid + 1;
else {
upper = mid - 1;
if(key > a[upper]) return mid;
}
}
return upper;
}
bool DskMBTree::find(int& pos, BTnode& root, slist<PATHNODE>& path,
const unsigned long k)
throw (BTreeException*)
{
int i = 0;
BTnode nd;
pos = -1;
streampos loc = 0;
if(root.data().keycount > 0) {
do {
if(loc) child(loc, nd);
i = nodesearch(nd, k);
if( i < (nd.data().numtrees - 1) && k == nd.data().key[i] ) {
pos = i;
addpath(path, nd, loc, pos);
return true;
}
pos = i;
addpath(path, nd, loc, pos);
loc = nd.data().child[i];
}while(loc);
}
return false;
}
bool DskMBTree::find(int& pos, slist<PATHNODE>& path,
const unsigned long k)
throw (BTreeException*)
{
int i = 0;
BTnode nd;
pos = -1;
streampos loc = 0;
if(get_root(nd) && nd.data().keycount > 0) {
do {
if(loc) child(loc, nd);
i = nodesearch(nd, k);
if( i < (nd.data().numtrees - 1) && k == nd.data().key[i] ) {
pos = i;
addpath(path, nd, loc, pos);
return true;
}
pos = i;
addpath(path, nd, loc, pos);
loc = nd.data().child[i];
}while(loc);
}
return false;
}
void DskMBTree::addpath(slist<PATHNODE>& path, BTnode nd,
streampos loc, int pos)
{
NODEINDEX idx(loc, pos);
PATHNODE pnode(nd, idx);
path.push_front(pnode);
}
bool DskMBTree::child(streampos loc, BTnode& nd)
throw (BTreeException*)
{
_iof.seekg(loc, ios::beg);
_iof.read((char*)(&(nd.data())), sizeof(BTnode::BTnodeStruct));
if(!_iof)
throw new BTreeException(BTreeException::FILE_DATA_READ_ERROR, "DskMBTree::child");
}
void DskMBTree::traverse(BTnode& nd)
{
int nt = nd.data().numtrees;
cout << "(" ;
for(int i = 0; i < nt - 1; i ++) {
if(nd.data().child[i]) {
BTnode cnd;
child(nd.data().child[i], cnd);
traverse(cnd);
}
cout << " " << nd.data().data[i] << " ";
}
if(nd.data().child[nt - 1]) {
BTnode lnd;
child(nd.data().child[nt - 1], lnd);
traverse(lnd);
}
cout << ")" ;
}
]]>