<![CDATA[
#ifndef DSKBTREEMUL_H
#define DSKBTREEMUL_H
/*
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 <stdlib.h>
#include <sys/stat.h>
#include <string.h>
#include <fstream.h>
#include <iostream.h>
#include <string>
#include <slist>
#include <stack>
#include <vector>
#include "POBException.h"
// Binary Tree node
class BTnode {
friend ostream& operator<<(ostream&, BTnode&);
public:
enum { MAXKEYS=3, MID=MAXKEYS/2 };
typedef struct BTnodeStruct {
short keycount;
short numtrees;
unsigned long key[MAXKEYS];
streampos data[MAXKEYS];
streampos child[MAXKEYS+1];
};
BTnode();
BTnode(const BTnode&);
BTnode& operator=(const BTnode&);
short numtrees() { return node.numtrees; }
short numkeys() { return node.keycount; }
BTnodeStruct& data() { return node; }
void clear();
private:
BTnodeStruct node;
};
// Reuseable Binary Tree nodes
class BTnodeAvl {
public:
BTnodeAvl();
BTnodeAvl(const char*);
~BTnodeAvl();
void open_avl(const char*) throw (BTreeException*);
bool isEmpty();
streampos getAvl() throw (BTreeException*);
void addAvl(streampos);
size_t size();
private:
void updateDskAvl() throw (BTreeException*);
private:
fstream _iof;
streampos _markp, _markg;
string _name;
stack<streampos> _avl;
};
// Disk Manager Binary tree
class DskMBTree {
public:
typedef pair<streampos, int> NODEINDEX;
typedef pair<BTnode, NODEINDEX> PATHNODE;
DskMBTree(const char*);
DskMBTree();
~DskMBTree();
void open_root(const char*) throw (BTreeException*);
bool get_root(BTnode&) throw (BTreeException*);
void makeroot(const long, streampos) throw (BTreeException*);
void insert(slist<PATHNODE>&, long, streampos);
bool find(int&, slist<PATHNODE>&, const unsigned long)
throw (BTreeException*);
bool find(int&, BTnode&, slist<PATHNODE>&, const unsigned long)
throw (BTreeException*);
bool deleten(long, slist<PATHNODE>&);
int delete_leafval(int, long, BTnode&) throw (BTreeException*); //return number of key left after delete
int delete_nodeval(int, long, BTnode&) throw (BTreeException*); //return number of key left after delete
void find_smallest(const streampos, long&, streampos&, slist<PATHNODE>&);
bool child(streampos, BTnode&) throw (BTreeException*);
void updatenode(streampos, const BTnode&) throw (BTreeException*);
streampos makenode(const BTnode&) throw (BTreeException*);
void traverse(BTnode&);
private:
void insertnode(BTnode&, int, const long, streampos, streampos);
void addpath(slist<PATHNODE>&, BTnode, streampos, int);
void split(streampos, int, BTnode&, BTnode&, const long, streampos,
long&, streampos&, streampos&);
void maketree(BTnode&, const streampos, const streampos)
throw (BTreeException*);
int nodesearch(BTnode&, const unsigned long);
int binsrch(const unsigned long [], const unsigned long, int);
private:
fstream _iof;
streampos _markp, _markg;
BTnodeAvl _avlnd;
};
#endif //DSKBTREEMUL_H
]]>