// Main.cc
// Copyright (C) 1997, 98 Mori Tetsuya
// 12/23/97
// 1/20/98 SortableFixedString, SimpleTree
#include "PersistentStorage.h"
#include <iostream.h>
#include <fstream.h>
#include <new.h>
#include <Regex.h>
#include <stdlib.h>
#include <time.h>
#define RAND(m) (rand() / (RAND_MAX / m))
//#define SILENT 1
// pseudo main()
#define STRSIZE 256
enum OID { OID_SampleObject, OID_SimpleTree };
class SampleObject: public PersistentObject {
PersistentPointer next;
char str[10];
public:
SampleObject(PersistentPointer &p,
const char *s = 0) :
PersistentObject(OID_SampleObject), next(p) {
if (s != 0) {
strcpy(str, s);
} else {
strcpy(str, "abc");
}
}
PersistentPointer &Next() {
return next;
}
char *Str() {
return str;
}
};
template<int size>
class SortableFixedString {
protected:
char str[size];
public:
SortableFixedString(char *s = 0) {
if (s == 0) {
str[0] = '\0';
} else {
strncpy(str, s, size);
str[size - 1] = '\0';
}
}
~SortableFixedString() {}
inline char *getValue() { return str; }
inline ComparisonType compare(char *s) {
return s != 0 ? strcmp(str, s) : GreaterThan;
}
inline ComparisonType compare(SortableFixedString &s) {
return strcmp(str, s.str);
}
inline SortableFixedString &operator = (char *s) {
if (s == 0) {
str[0] = '\0';
} else {
strncpy(str, s, size);
str[size - 1] = '\0';
}
return *this;
}
};
template<int size>
ostream &operator<<(ostream &os, SortableFixedString<size> &obj) {
return os << obj.getValue();
}
const EntryID SimpleTreeTopEID = 1;
class SimpleTree;
ostream &operator<<(ostream &os, SimpleTree &obj);
template <class Element, class Value, ObjectID oid>
class SimpleTree : public PersistentObject {
friend ostream &operator<<(ostream &os, SimpleTree &obj);
protected:
PersistentPointer left;
PersistentPointer right;
Element object;
public:
SimpleTree(Value value,
PersistentPointer l = PersistentPointer(),
PersistentPointer r = PersistentPointer()) :
PersistentObject(oid),
left(l), right(r), object(value) {
}
~SimpleTree() {}
inline PersistentPointer &Left() { return left; }
inline PersistentPointer &Right() { return right; }
inline Value getValue() { return object.getValue(); }
PersistentPointer insert(Value v, PersistentPointer This) {
ComparisonType cmp = object.compare(v);
if (cmp == 0) {
return This;
} else if (cmp < 0) {
if (Right() == 0) {
PointerPair pp = ps->allocate(sizeof(*this));
pp.grab();
if (P(pp) == 0)
return PersistentPointer();
new(pp) SimpleTree(v);
pp.release();
Right() = pp;
return pp;
} else {
PointerPair pp = Right();
pp.grabReadOnly();
PersistentPointer p;
if (P(pp) != 0 && P(pp)->getID() == oid)
p = ((SimpleTree *)P(pp))->insert(v, Right());
pp.releaseReadOnly();
return p;
}
} else {
if (Left() == 0) {
PointerPair pp = ps->allocate(sizeof(*this));
pp.grab();
if (P(pp) == 0)
return PersistentPointer();
new(pp) SimpleTree(v);
pp.release();
Left() = pp;
return pp;
} else {
PointerPair pp = Left();
pp.grabReadOnly();
PersistentPointer p;
if (P(pp) != 0 && P(pp)->getID() == oid)
p = ((SimpleTree *)P(pp))->insert(v, Left());
pp.releaseReadOnly();
return p;
}
}
}
PersistentPointer search(Value v, PersistentPointer This) {
ComparisonType cmp = object.compare(v);
if (cmp == 0) {
return This;
} else if (cmp < 0) {
if (Right() == 0) {
return PersistentPointer();
} else {
PointerPair pp = Right();
pp.grabReadOnly();
PersistentPointer p;
if (P(pp) != 0 && P(pp)->getID() == oid)
p = ((SimpleTree *)P(pp))->search(v, Right());
pp.releaseReadOnly();
return p;
}
} else {
if (Left() == 0) {
return PersistentPointer();
} else {
PointerPair pp = Left();
pp.grabReadOnly();
PersistentPointer p;
if (P(pp) != 0 && P(pp)->getID() == oid)
p = ((SimpleTree *)P(pp))->search(v, Left());
pp.releaseReadOnly();
return p;
}
}
}
PersistentPointer match(Value lower, Value upper) {
PointerPair pp = ps->allocate(sizeof(*this));
pp.grab();
new (pp) SimpleTree("");
doMatch(lower, upper, pp);
pp.release();
return pp;
}
PointerPair &doMatch(Value lower, Value upper,
PointerPair &top) {
ComparisonType cmpLower = object.compare(lower);
ComparisonType cmpUpper = object.compare(upper);
ComparisonType cmp;
if (cmpLower < 0) {
cmp = LessThan;
} else if (cmpUpper > 0) {
cmp = GreaterThan;
} else {
cmp = EqualTo;
}
if (cmp == 0) {
((SimpleTree *)P(top))->insert(object.getValue(), top);
}
if (cmp >= 0 && Left() != 0) {
PointerPair L = Left();
L.grabReadOnly();
if (P(L) != 0 && ((SimpleTree *)P(L))->getID() == oid)
((SimpleTree *)P(L))->doMatch(lower, upper, top);
L.releaseReadOnly();
}
if (cmp <= 0 && Right() != 0) {
PointerPair R = Right();
R.grabReadOnly();
if (P(R) != 0 && ((SimpleTree *)P(R))->getID() == oid)
((SimpleTree *)P(R))->doMatch(lower, upper, top);
R.releaseReadOnly();
}
return top;
}
void traverse(ostream &os) {
if (Left() != 0) {
PointerPair pp = Left();
pp.grabReadOnly();
if (P(pp) != 0 && P(pp)->getID() == oid)
((SimpleTree *)P(pp))->traverse(os);
pp.releaseReadOnly();
}
#ifndef SILENT
os << object << endl;
#endif
if (Right() != 0) {
PointerPair pp = Right();
pp.grabReadOnly();
if (P(pp) != 0 && P(pp)->getID() == oid)
((SimpleTree *)P(pp))->traverse(os);
pp.releaseReadOnly();
}
}
inline isLeaf() { return Left() == 0 && Right() == 0; }
BoolType destroy() {
#ifndef SILENT
cout << "destroy " << object << endl;
#endif
BoolType successR;
BoolType successL;
if (Left() != 0) {
PointerPair L = Left();
L.grab();
if (P(L) != 0 && P(L)->getID() == oid) {
successL = ((SimpleTree *)P(L))->destroy();
if (successL && ((SimpleTree *)P(L))->isLeaf()) {
successL = ps->destroy(L);
if (!successL)
successL = False;
else
Left() = 0;
} else {
successL = False;
}
if (!successL)
successL = L.release();
} else {
successL = False;
}
} else {
successL = True;
}
if (Right() != 0) {
PointerPair R = Right();
R.grab();
if (P(R) != 0 && P(R)->getID() == oid) {
successR = ((SimpleTree *)P(R))->destroy();
if (successR && ((SimpleTree *)P(R))->isLeaf()) {
successR = ps->destroy(R);
if (!successR)
successR = False;
else
Right() = 0;
} else {
successR = False;
}
if (!successR)
successR = R.release();
} else {
successR = False;
}
} else {
successR = True;
}
return successR && successL;
}
}; // SimpleTree
typedef SimpleTree<SortableFixedString<STRSIZE>, char *, OID_SimpleTree> ST;
typedef ST *PST;
int main(int argc, char *argv[]) {
new PersistentStorage(".");
char line[STRSIZE];
char *lower, *upper;
BoolType verbose = True;
ifstream fin;
istream *is;
if (argc >= 4) {
fin.open(argv[1]);
lower = argv[2];
upper = argv[3];
is = &fin;
} else if (argc == 3) {
verbose = False;
lower = argv[1];
upper = argv[2];
is = &cin;
} else {
cout << "Usage " << argv[0] << " [file] lower upper" << endl;
exit(1);
}
PointerPair pp = ps->getEntryPoint(SimpleTreeTopEID);
if (pp == 0) {
pp = ps->allocate(sizeof(ST));
new(pp.grab()) ST("");
ps->setEntryPoint(SimpleTreeTopEID, pp);
} else {
pp.grab();
}
if (P(pp)->getID() != OID_SimpleTree) {
cout << "ObjectID is not OID_SimpleTree" << endl;
exit(1);
}
do {
is->getline(line, STRSIZE);
PST(P(pp))->insert(line, pp);
#ifndef SILENT
if (verbose)
cout << "inserting " << line << endl;
#endif
} while (is->gcount() > 0);
if (verbose) {
fin.close();
fin.open(argv[1]);
is = &fin;
PointerPair p;
do {
is->getline(line, STRSIZE);
p = PST(P(pp))->search(line, pp);
#ifndef SILENT
if (p != 0) {
p.grabReadOnly();
if (P(p) != 0 && P(p)->getID() == OID_SimpleTree) {
cout << "found " << PST(P(p))->getValue() << endl;
}
p.releaseReadOnly();
} else {
cout << "not found " << line << endl;
}
#endif
} while (is->gcount() > 0);
}
if (verbose)
PST(P(pp))->traverse(cout);
if (argc >= 3) {
PointerPair matched;
matched = PST(P(pp))->match(lower, upper);
matched.grab();
if (P(matched) != 0 && P(matched)->getID() == OID_SimpleTree) {
cout << "#matched" << endl;
PST(P(matched))->traverse(cout);
cout << "#end matched" << endl;
PST(P(matched))->destroy();
}
if (matched.isGrabbed() != 0)
ps->destroy(matched);
}
pp.release();
#if 0
PointerPair p;
PersistentPointer plast;
PersistentPointer pnext;
SizeType index;
SizeType s;
for (index = 0; index < 100000; index++) {
plast = p;
p = ps->allocate(s = sizeof(SampleObject) + RAND(1024) +
(RAND(100) == 0) * RAND(10000));
if (p.isNull()) {
cout << "\nallocate failed " << index << " " << s << endl;
break;
}
if (p.grab() != 0) {
new(p) SampleObject(plast);
} else {
cout << "\ngrab failed " << index << " " << s << endl;
break;
}
memset(((SampleObject *)P(p))->Str(), (index % (127 - 32)) + 32, 10);
(((SampleObject *)P(p))->Str())[9] = '\0';
if (!p.release()) {
cout << "release failed" << endl;
break;
}
#ifndef SILENT
cout << index << "\r" << flush;
#endif
}
#ifndef SILENT
cout << "\nallocation " << index << endl;
#endif
plast = p;
index = 0;
while (!p.isNull()) {
p.grabReadOnly();
#ifndef SILENT
cout << index << "\r" << flush;
#endif
if (P(p) == 0)
break;
pnext = ((SampleObject *)P(p))->Next();
p.releaseReadOnly();
p = pnext;
index++;
}
#ifndef SILENT
cout << "\ngrabReadOnly " << index << endl;
#endif
srand(time(0));
p = plast;
index = 0;
while (!p.isNull()) {
p.grab();
if (P(p) == 0) {
#ifndef SILENT
cout << "\ngrab failed" << index << endl;
#endif
break;
}
pnext = ((SampleObject *)P(p))->Next();
if (RAND(10) == 0) {
if (ps->destroy(p)) {
#ifndef SILENT
cout << "d" << index << "\r" << flush;
#endif
} else {
#ifndef SILENT
cout << "\ndestroy failed " << index << endl;
#endif
}
} else {
if (p.release()) {
#ifndef SILENT
cout << "r" << index << "\r" << flush;
#endif
} else {
#ifndef SILENT
cout << "\nrelease failed " << index << endl;
#endif
}
}
p = pnext;
index++;
}
cout << "\ndestroy or release " << index << endl;
#endif
cout << "synchronization" << endl;
delete ps;
#ifndef SILENT
// ps->printStatus();
#endif
cout << "sizeof(SampleObject) " << sizeof(SampleObject) << endl;
cout << "sizeof(SimpleTree) " << sizeof(ST) << endl;
cout << "sizeof(PersistentObject) " << sizeof(PersistentObject) << endl;
exit(1);
}