| author | Michael Krelin <hacker@klever.net> | 2004-07-05 01:53:09 (UTC) |
|---|---|---|
| committer | Michael Krelin <hacker@klever.net> | 2004-07-05 01:53:09 (UTC) |
| commit | 9938ea772d372ba955b7bc1f1c48a062c3a36f8a (patch) (side-by-side diff) | |
| tree | a98185df944e3a763f9557aa74bc2837b343f048 /shared-code/BTreendex.h | |
| download | pumpkin-9938ea772d372ba955b7bc1f1c48a062c3a36f8a.zip pumpkin-9938ea772d372ba955b7bc1f1c48a062c3a36f8a.tar.gz pumpkin-9938ea772d372ba955b7bc1f1c48a062c3a36f8a.tar.bz2 | |
initial commit into svn repository
git-svn-id: http://svn.klever.net/kin/pumpkin/trunk@1 fe716a7a-6dde-0310-88d9-d003556173a8
| -rw-r--r-- | shared-code/BTreendex.h | 595 |
1 files changed, 595 insertions, 0 deletions
diff --git a/shared-code/BTreendex.h b/shared-code/BTreendex.h new file mode 100644 index 0000000..88109ab --- a/dev/null +++ b/shared-code/BTreendex.h @@ -0,0 +1,595 @@ +#ifndef __BTREENDEX_H
+#define __BTREENDEX_H
+
+#include "Dynamide.h"
+
+namespace Klever {
+
+template<class key,class value,int treeOrder,int cluster>
+class CBTreendex : public CObject {
+public:
+ typedef LONG CBTPageRef;
+ struct CBTRecordRef {
+ CBTPageRef m_Page;
+ INT m_Offset;
+ CBTRecordRef(CBTPageRef page=-1,INT offset=-1) : m_Page(page), m_Offset(offset) {}
+ };
+ class CBTRecord : public CObject {
+ public:
+ CBTPageRef m_ptrLeft;
+ CBTPageRef m_ptrRight;
+ key m_Key;
+ value m_Value;
+ CBTRecord() : m_ptrLeft(-1), m_ptrRight(-1) {}
+ CBTRecord(key& _key,value& _value,CBTPageRef left=-1,CBTPageRef right=-1) : m_Key(_key), m_Value(_value), m_ptrLeft(left), m_ptrRight(right) {}
+ CBTRecord(CBTRecord& r) : m_Key(r.m_Key), m_Value(r.m_Value), m_ptrLeft(r.m_ptrLeft), m_ptrRight(r.m_ptrRight) {}
+
+ CBTRecord& operator=(CBTRecord& r) {m_Key=r.m_Key, m_Value=r.m_Value, m_ptrLeft=r.m_ptrLeft, m_ptrRight=r.m_ptrRight;return *this;}
+
+ void Serialize(CArchive& ar) {
+ if(ar.IsStoring()){
+ ar << m_ptrLeft;
+ ar << m_ptrRight;
+ }else{
+ ar >> m_ptrLeft;
+ ar >> m_ptrRight;
+ }
+ SerializeElements(ar,&m_Key,1);
+ SerializeElements(ar,&m_Value,1);
+ }
+ };
+ class CBTPage : public CArray<CBTRecord,CBTRecord&> {
+ public:
+ void Serialize(CArchive& ar) {
+ int nCount = -1;
+ if(ar.IsStoring()){
+ nCount = GetSize();
+ ar << nCount;
+ }else{
+ nCount = 0;
+ ar >> nCount;
+ RemoveAll();
+ SetSize(nCount);
+ }
+ for(int tmp=0;tmp<nCount;tmp++)
+ ElementAt(tmp).Serialize(ar);
+ }
+ };
+ typedef CDynamide<256,cluster> CBTDyna;
+ typedef CBTDyna::CDynaFile CBTDynaFile;
+ typedef CArray<CBTRecordRef,CBTRecordRef&> CBTRStack;
+
+ CBTDyna m_BT;
+ struct _btCrap {
+ BOOL m_bRootSet;
+ CBTPageRef m_Root;
+ } *m_BTCrap;
+ BOOL m_bRO;
+ CBTRStack m_btStack;
+ CBTPage m_stackTop;
+
+ CBTreendex() {}
+ ~CBTreendex() { Close(); }
+ BOOL Attach(CFile* file,BOOL bAutodelete) {
+ m_bRO = FALSE;
+ if(!m_BT.Attach(file,bAutodelete))
+ return FALSE;
+ return Attach();
+ }
+ BOOL Open(LPCTSTR file,BOOL bReadOnly) {
+ if(!m_BT.Open(file,bReadOnly))
+ return FALSE;
+ m_bRO = bReadOnly;
+ return Attach();
+ }
+ BOOL Create(LPCTSTR file) {
+ try{
+ CFile* f = new CFile(file,CFile::modeCreate|CFile::modeReadWrite|CFile::shareDenyRead|CFile::shareDenyWrite|CFile::typeBinary);
+ ASSERT(f);
+ return Attach(f,TRUE);
+ }catch(CException* e){
+ e->Delete();
+ return FALSE;
+ }
+ }
+ BOOL Attach() {
+ ASSERT(m_BT.IsOpened());
+ m_BTCrap = (_btCrap*)m_BT.m_FB.crap;
+ if(!m_BTCrap->m_bRootSet){
+ m_BTCrap->m_Root = AllocatePage();
+ if(m_BTCrap->m_Root<0)
+ return FALSE;
+ m_BTCrap->m_bRootSet = TRUE;
+ m_BT.Write1stBlock();
+ }
+ return TRUE;
+ }
+ BOOL Close() {
+ m_BT.Close();
+ return TRUE;
+ }
+ BOOL IsOpened() {
+ return m_BT.IsOpened();
+ }
+
+ BOOL Lookup(key& _key,value& value) {
+ if(!IsOpened())
+ return FALSE;
+ ASSERT(m_BTCrap->m_bRootSet);
+ if(!SeekToPage(_key))
+ return FALSE;
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(rr.m_Offset<0)
+ return FALSE;
+ ASSERT(rr.m_Offset<m_stackTop.GetSize());
+ if(_key != m_stackTop[rr.m_Offset].m_Key)
+ return FALSE;
+ value = m_stackTop[rr.m_Offset].m_Value;
+ return TRUE;
+ }
+ BOOL Add(key& _key,value& _value) {
+ if(!IsOpened())
+ return FALSE;
+ ASSERT(m_BTCrap->m_bRootSet);
+ if(!SeekToPage(_key))
+ return FALSE;
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ CBTRecord nuRecord(_key,_value);
+ if(rr.m_Offset<0){
+ if(m_stackTop.GetSize())
+ nuRecord.m_ptrLeft = m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight;
+ }else if(rr.m_Offset==0){
+ nuRecord.m_ptrRight = m_stackTop[0].m_ptrLeft;
+ }else{
+ nuRecord.m_ptrLeft = m_stackTop[rr.m_Offset-1].m_ptrRight;
+ nuRecord.m_ptrRight = m_stackTop[rr.m_Offset].m_ptrLeft;
+ }
+// ASSERT(rr.m_Offset==0 || (m_stackTop[rr.m_Offset-1].m_Key<_key && m_stackTop[rr.m_Offset-1].m_ptrRight<0));
+// ASSERT(rr.m_Offset<0 || m_stackTop[rr.m_Offset].m_Key>=_key && m_stackTop[rr.m_Offset].m_ptrLeft<0);
+ if(rr.m_Offset>=0 && m_stackTop[rr.m_Offset].m_Key==_key){
+ // Exact match found - just replace.
+ m_stackTop[rr.m_Offset].m_Value = _value;
+ if(!SavePage(rr.m_Page,m_stackTop))
+ return FALSE;
+ return TRUE;
+ }
+ // Split the page and propagate the split if needed..
+ // Insert new element at rr.m_Offset..
+ BOOL nuisnew = TRUE;
+ for(int sp=m_btStack.GetUpperBound();sp>=0;sp--){
+ CBTPageRef opr = m_btStack[sp].m_Page;
+ int iAt = m_btStack[sp].m_Offset;
+ CBTPage op;
+ VERIFY(LoadPage(opr,op));
+ if(iAt<0)
+ iAt = op.GetSize();
+ else{
+ if(op[iAt].m_Key<nuRecord.m_Key)
+ iAt++;
+ ASSERT(iAt==op.GetSize() || op[iAt].m_Key > nuRecord.m_Key);
+ }
+ op.InsertAt(iAt,nuRecord);
+ if(iAt>0)
+ op[iAt-1].m_ptrRight=nuRecord.m_ptrLeft;
+ if(iAt<op.GetUpperBound())
+ op[iAt+1].m_ptrLeft=nuRecord.m_ptrRight;
+ if(op.GetSize()<=treeOrder*2){
+ // This isn't causing overflow
+ VERIFY(SavePage(opr,op));
+ return TRUE;
+ }
+ TRACE0("Split\n");
+ ASSERT(op.GetSize()==(treeOrder*2+1));
+ CBTPageRef npr = AllocatePage();
+ ASSERT(npr>=0);
+ CBTPage np;
+ ASSERT(LoadPage(npr,np));
+ ASSERT(!np.GetSize());
+ nuRecord = op[treeOrder];
+ if(iAt==treeOrder){
+ // We're inserting central element! - drop out the stack top if this is still new one
+ for(int tmp=0;tmp<treeOrder;tmp++)
+ np.InsertAt(tmp,op[tmp]);
+ op.RemoveAt(0,treeOrder+1);
+ nuRecord.m_ptrLeft = npr;
+ nuRecord.m_ptrRight = opr;
+ if(nuisnew)
+ m_btStack.RemoveAt(m_btStack.GetUpperBound());
+ }else{
+ if(iAt<treeOrder){
+ // We're inserting in the left subtree.
+ // Make newpage the right one and forget it.
+ for(int tmp=0;tmp<treeOrder;tmp++)
+ np.InsertAt(tmp,op[tmp+treeOrder+1]);
+ op.RemoveAt(treeOrder,treeOrder+1);
+ nuRecord.m_ptrLeft = opr;
+ nuRecord.m_ptrRight = npr;
+ }else{
+ // We're inserting in the right subtree.
+ // Make newpage the left one, forget it, but also adjust offset in the stack
+ for(int tmp=0;tmp<treeOrder;tmp++)
+ np.InsertAt(tmp,op[tmp]);
+ op.RemoveAt(0,treeOrder+1);
+ nuRecord.m_ptrLeft = npr;
+ nuRecord.m_ptrRight = opr;
+ m_btStack[sp].m_Offset-=treeOrder+1;
+ }
+ // Note that we're not inserting new element anymore.
+ nuisnew = FALSE;
+ }
+ // Do, excessive sanity checks and save pages
+ ASSERT(op.GetSize());
+ ASSERT(np.GetSize());
+ VERIFY(SavePage(opr,op));
+ VERIFY(SavePage(npr,np));
+ }
+ // Here we have root page overflow, which means that we're simply putting new
+ // record in this brand new root page and also inserting this page on the bottom of the stack
+ CBTPageRef nuroot = AllocatePage();
+ ASSERT(nuroot>=0);
+ CBTPage nurpa;
+ ASSERT(LoadPage(nuroot,nurpa));
+ ASSERT(!nurpa.GetSize());
+ nurpa.Add(nuRecord);
+ VERIFY(SavePage(nuroot,nurpa));
+ m_btStack.InsertAt(0,CBTRecordRef(nuroot,0));
+ m_BTCrap->m_Root = nuroot;
+ m_BT.Write1stBlock();
+ return TRUE;
+ }
+ BOOL Delete(key& _key) {
+ if(!IsOpened())
+ return FALSE;
+ ASSERT(m_BTCrap->m_bRootSet);
+ value _value;
+ if(!Lookup(_key,_value))
+ return FALSE;
+ // Found key, check if it's a leaf
+ {
+ CBTRecordRef* rr = &m_btStack[m_btStack.GetUpperBound()];
+ int rrIdx = m_btStack.GetUpperBound();
+ if(m_stackTop[rr->m_Offset].m_ptrLeft>=0){
+ ASSERT(m_stackTop[rr->m_Offset].m_ptrRight>=0);
+ // It isn't - scan for the _next_ key and do dirty deeds
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr->m_Offset].m_ptrRight,0));
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ if(m_stackTop[0].m_ptrLeft<0)
+ break;
+ m_btStack.Add(CBTRecordRef(m_stackTop[0].m_ptrLeft,0));
+ }
+ // We have a leaf node here, replace victim with the first element and kill it.
+ CBTPage uppage;
+ rr = &m_btStack[rrIdx];
+ if(!LoadPage(rr->m_Page,uppage))
+ return FALSE;
+ uppage[rr->m_Offset].m_Key=m_stackTop[0].m_Key; uppage[rr->m_Offset].m_Value=m_stackTop[0].m_Value;
+ m_stackTop.RemoveAt(0);
+ if(!(SavePage(rr->m_Page,uppage) && SavePage(m_btStack[m_btStack.GetUpperBound()].m_Page,m_stackTop)))
+ return FALSE;
+ }else{
+ ASSERT(m_stackTop[rr->m_Offset].m_ptrRight<0);
+ m_stackTop.RemoveAt(rr->m_Offset);
+ if(!SavePage(rr->m_Page,m_stackTop))
+ return FALSE;
+ }
+ }
+ // We have a page to check for underflow at the top of the stack now.
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ if(m_stackTop.GetSize()>=treeOrder || m_btStack.GetSize()==1)
+ return TRUE;
+ CBTRecordRef& rr1 = m_btStack[m_btStack.GetUpperBound()-1];
+ CBTPage daddy;
+ if(!LoadPage(rr1.m_Page,daddy))
+ return FALSE;
+ CBTPageRef nPage = daddy[rr1.m_Offset].m_ptrRight;
+ BOOL bRight=TRUE;
+ if(nPage<0 || nPage==rr.m_Page){
+ nPage = daddy[rr1.m_Offset].m_ptrLeft;
+ bRight = FALSE;
+ }
+ ASSERT(nPage>=0 && nPage!=rr.m_Page);
+ CBTPage neighbor;
+ if(!LoadPage(nPage,neighbor))
+ return FALSE;
+ // Here we have possibly two cases:
+ // 1. Neighboring page can share some data with use, then do share and leave
+ // 2. Neighboring page is of treeorder in size, then merge and propagate
+ if(neighbor.GetSize()>treeOrder){
+ TRACE0("Redistributing..\n");
+ // Borrow some data from there.
+ int toBorrow = neighbor.GetSize()-treeOrder;
+ toBorrow=toBorrow/2+1;
+ ASSERT(toBorrow);
+ if(bRight)
+ m_stackTop.Add(CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight,neighbor[0].m_ptrLeft));
+ else
+ m_stackTop.InsertAt(0,CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,neighbor[neighbor.GetUpperBound()].m_ptrRight,m_stackTop[0].m_ptrLeft));
+ for(toBorrow--;toBorrow;toBorrow--){
+ if(bRight){
+ m_stackTop.Add(neighbor[0]);
+ neighbor.RemoveAt(0);
+ }else{
+ m_stackTop.InsertAt(0,neighbor[neighbor.GetUpperBound()]);
+ neighbor.RemoveAt(neighbor.GetUpperBound());
+ }
+ }
+ daddy[rr1.m_Offset].m_Key = neighbor[bRight?0:neighbor.GetUpperBound()].m_Key; daddy[rr1.m_Offset].m_Value = neighbor[bRight?0:neighbor.GetUpperBound()].m_Value;
+ neighbor.RemoveAt(bRight?0:neighbor.GetUpperBound());
+ if(!(SavePage(rr1.m_Page,daddy) && SavePage(nPage,neighbor) && SavePage(rr.m_Page,m_stackTop)))
+ return FALSE;
+ rr.m_Offset = -1; // *** Point to the next??
+ return TRUE;
+ }
+ TRACE0("Merging..\n");
+ // We need to merge pages here..
+ // We will merge them at stacktop, then we'll discard neighbor guy..
+ if(bRight)
+ m_stackTop.Add(CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight,neighbor[0].m_ptrLeft));
+ else
+ m_stackTop.InsertAt(0,CBTRecord(daddy[rr1.m_Offset].m_Key,daddy[rr1.m_Offset].m_Value,neighbor[neighbor.GetUpperBound()].m_ptrRight,m_stackTop[0].m_ptrLeft));
+ if(bRight){
+ while(neighbor.GetSize()){
+ m_stackTop.Add(neighbor[0]);
+ neighbor.RemoveAt(0);
+ }
+ }else{
+ while(neighbor.GetSize()){
+ m_stackTop.InsertAt(0,neighbor[neighbor.GetUpperBound()]);
+ neighbor.RemoveAt(neighbor.GetUpperBound());
+ }
+ }
+ if(rr1.m_Offset>0)
+ daddy[rr1.m_Offset-1].m_ptrRight=rr.m_Page;
+ if(rr1.m_Offset<daddy.GetUpperBound())
+ daddy[rr1.m_Offset+1].m_ptrLeft=rr.m_Page;
+ daddy.RemoveAt(rr1.m_Offset);
+ if(!(SavePage(rr1.m_Page,daddy) && SavePage(rr.m_Page,m_stackTop)))
+ return FALSE;
+ VERIFY(DeallocatePage(nPage));
+ m_btStack.RemoveAt(m_btStack.GetUpperBound());
+ }
+ return FALSE;
+ }
+ BOOL GoFirst() {
+ if(!IsOpened())
+ return FALSE;
+ ASSERT(m_BTCrap->m_bRootSet);
+ m_btStack.RemoveAll();
+ m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1));
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ if(!m_stackTop.GetSize()){
+ ASSERT(m_btStack.GetSize()==1);
+ return FALSE;
+ }
+ rr.m_Offset = 0;
+ if(m_stackTop[rr.m_Offset].m_ptrLeft<0)
+ return TRUE;
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1));
+ }
+ }
+ BOOL GoLast() {
+ if(!IsOpened())
+ return FALSE;
+ ASSERT(m_BTCrap->m_bRootSet);
+ m_btStack.RemoveAll();
+ m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1));
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ if(!m_stackTop.GetSize()){
+ ASSERT(m_btStack.GetSize()==1);
+ return FALSE;
+ }
+ rr.m_Offset = m_stackTop.GetUpperBound();
+ if(m_stackTop[rr.m_Offset].m_ptrRight<0)
+ return TRUE;
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,-1));
+ }
+ }
+ BOOL GoNext() {
+ if(!IsOpened())
+ return FALSE;
+ if(!(m_btStack.GetSize() && m_btStack[m_btStack.GetUpperBound()].m_Offset>=0))
+ return FALSE;
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ ASSERT(rr.m_Offset<m_stackTop.GetSize());
+ if(m_stackTop[rr.m_Offset].m_ptrRight>=0){
+ // Advance pointer in this page and dive into subtree
+ // going left and left until we have nowhere to go.
+// TRACE1("Dive into page %lu",m_stackTop[rr.m_Offset].m_ptrRight);
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,0));
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ ASSERT(rr.m_Offset==0);
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ if(m_stackTop[rr.m_Offset].m_ptrLeft<0)
+ break;
+// TRACE1(", %lu",m_stackTop[rr.m_Offset].m_ptrLeft);
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,0));
+ }
+// TRACE0("\n");
+ return TRUE;
+ }else if(rr.m_Offset<m_stackTop.GetUpperBound()){
+ rr.m_Offset++;
+ return TRUE;
+ }
+ // We're at the end of page go up until we're done or we have data.
+ m_btStack.RemoveAt(m_btStack.GetUpperBound());
+// TRACE0("Go up");
+ while(m_btStack.GetSize()){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ if(rr.m_Offset<m_stackTop.GetSize()){
+// TRACE0("\n");
+ return TRUE;
+ }
+// TRACE0(", up");
+ m_btStack.RemoveAt(m_btStack.GetUpperBound());
+ }
+// TRACE0("\nBtree is done\n");
+ return FALSE;
+ }
+ BOOL GoPrev() {
+ if(!IsOpened())
+ return FALSE;
+ if(!(m_btStack.GetSize() && m_btStack[m_btStack.GetUpperBound()].m_Offset>=0))
+ return FALSE;
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ ASSERT(rr.m_Offset<m_stackTop.GetSize());
+ if(m_stackTop[rr.m_Offset].m_ptrLeft>=0){
+ // Dive in and go right and right from the rightmost until
+ // we have nowhere to go.
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1));
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ rr.m_Offset = m_stackTop.GetUpperBound();
+ if(m_stackTop[rr.m_Offset].m_ptrRight<0)
+ return TRUE;
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,-1));
+ }
+ return TRUE;
+ }else if(rr.m_Offset>0){
+ rr.m_Offset--;
+ return TRUE;
+ }
+ // We're at the leftmost element in page - go up and left until we're
+ // done or we have data.
+ m_btStack.RemoveAt(m_btStack.GetUpperBound());
+ while(m_btStack.GetSize()){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ rr.m_Offset--;
+ if(rr.m_Offset>=0)
+ return TRUE;
+ m_btStack.RemoveAt(m_btStack.GetUpperBound());
+ }
+ // No more data - we were at the first element in tree.
+ return FALSE;
+ }
+ BOOL GetThis(key& _key,value& _value) {
+ if(!IsOpened())
+ return FALSE;
+ // *** MORE CHECKING
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ _key = m_stackTop[rr.m_Offset].m_Key;
+ _value = m_stackTop[rr.m_Offset].m_Value;
+ return TRUE;
+ }
+
+ BOOL SeekToPage(const key& _key) {
+ ASSERT(IsOpened());
+ ASSERT(m_BTCrap->m_bRootSet);
+ m_btStack.RemoveAll();
+ m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1));
+ for(;;){
+ CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
+ if(!LoadPage(rr.m_Page,m_stackTop))
+ return FALSE;
+ ASSERT(m_stackTop.GetSize() || !m_btStack.GetUpperBound());
+ if(!m_stackTop.GetSize()){
+ rr.m_Offset=-1;
+ return TRUE;
+ }
+ for(rr.m_Offset=0;rr.m_Offset<m_stackTop.GetSize();rr.m_Offset++){
+ if(_key == m_stackTop[rr.m_Offset].m_Key)
+ return TRUE;
+ if(_key < m_stackTop[rr.m_Offset].m_Key){
+ ASSERT(rr.m_Offset==0 || m_stackTop[rr.m_Offset].m_ptrLeft==m_stackTop[rr.m_Offset-1].m_ptrRight);
+ if(m_stackTop[rr.m_Offset].m_ptrLeft<0)
+ return TRUE;
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1));
+ break;
+ }
+ if(rr.m_Offset==m_stackTop.GetUpperBound()){
+ if(m_stackTop[rr.m_Offset].m_ptrRight<0){
+ rr.m_Offset=-1;
+ return TRUE;
+ }
+ m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrRight,-1));
+ break;
+ }
+ }
+ }
+ }
+
+ BOOL LoadPage(CBTPageRef ref,CBTPage& page) {
+ CFile* pageFile = m_BT.OpenFile(ref);
+ if(!pageFile)
+ return FALSE;
+ BOOL rv = TRUE;
+ try{
+ CArchive ar(pageFile,CArchive::load);
+ page.Serialize(ar);
+ if(m_bRO)
+ page.FreeExtra(); // ** ???
+ ar.Close();
+ }catch(CException* e){
+ e->Delete();
+ rv = FALSE;
+ }
+ delete pageFile;
+ return rv;
+ }
+ BOOL SavePage(CBTPageRef ref,CBTPage& page) {
+ CFile* pageFile = m_BT.OpenFile(ref);
+ if(!pageFile)
+ return FALSE;
+ BOOL rv = TRUE;
+ try{
+ CArchive ar(pageFile,CArchive::store);
+ page.Serialize(ar);
+ ar.Close();
+ }catch(CException* e){
+ e->Delete();
+ rv = FALSE;
+ }
+ delete pageFile;
+ return rv;
+ }
+ CBTPageRef AllocatePage() {
+ CBTDynaFile* pageFile = m_BT.CreateFile();
+ if(!pageFile)
+ return -1;
+ CBTPage nothing;
+ CBTPageRef rv = pageFile->GetFile();
+ try{
+ CArchive ar(pageFile,CArchive::store);
+ nothing.Serialize(ar);
+ ar.Close();
+ }catch(CException* e){
+ e->Delete();
+ rv = -1;
+ }
+ delete pageFile;
+ return rv;
+ }
+ BOOL DeallocatePage(CBTPageRef ref) {
+ return m_BT.DeleteFile(ref);
+ }
+
+};
+
+};
+
+#endif // __BTREENDEX_H
|