initial commit into svn repository

git-svn-id: http://svn.klever.net/kin/kinsole/trunk@1 fe716a7a-6dde-0310-88d9-d003556173a8
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: 885f8cc426a8840ae61023b75f3f0e4a1e268082 (patch) (unidiff)
tree: 5e942d450c97ca0bf0f9cfb80aa0fefb486535d9 /shared-code/BTreendex.h
download: kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.zip
kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.tar.gz
kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.tar.bz2
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
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	885f8cc426a8840ae61023b75f3f0e4a1e268082 (patch) (unidiff)
tree	5e942d450c97ca0bf0f9cfb80aa0fefb486535d9 /shared-code/BTreendex.h
download	kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.zip kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.tar.gz kinsole-885f8cc426a8840ae61023b75f3f0e4a1e268082.tar.bz2

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 @@
	1	#ifndef__BTREENDEX_H
	2	#define__BTREENDEX_H
	3
	4	#include "Dynamide.h"
	5
	6	namespace Klever {
	7
	8	template<class key,class value,int treeOrder,int cluster>
	9	class CBTreendex : public CObject{
	10	public:
	11	typedef LONG CBTPageRef;
	12	struct CBTRecordRef {
	13	CBTPageRef m_Page;
	14	INT m_Offset;
	15	CBTRecordRef(CBTPageRef page=-1,INT offset=-1) : m_Page(page), m_Offset(offset) {}
	16	};
	17	class CBTRecord : public CObject {
	18	public:
	19	CBTPageRef m_ptrLeft;
	20	CBTPageRef m_ptrRight;
	21	key m_Key;
	22	value m_Value;
	23	CBTRecord() : m_ptrLeft(-1), m_ptrRight(-1) {}
	24	CBTRecord(key& _key,value& _value,CBTPageRef left=-1,CBTPageRef right=-1) : m_Key(_key), m_Value(_value), m_ptrLeft(left), m_ptrRight(right) {}
	25	CBTRecord(CBTRecord& r) : m_Key(r.m_Key), m_Value(r.m_Value), m_ptrLeft(r.m_ptrLeft), m_ptrRight(r.m_ptrRight) {}
	26
	27	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;}
	28
	29	void Serialize(CArchive& ar) {
	30	if(ar.IsStoring()){
	31	ar << m_ptrLeft;
	32	ar << m_ptrRight;
	33	}else{
	34	ar >> m_ptrLeft;
	35	ar >> m_ptrRight;
	36	}
	37	SerializeElements(ar,&m_Key,1);
	38	SerializeElements(ar,&m_Value,1);
	39	}
	40	};
	41	class CBTPage : public CArray<CBTRecord,CBTRecord&> {
	42	public:
	43	void Serialize(CArchive& ar) {
	44	int nCount = -1;
	45	if(ar.IsStoring()){
	46	nCount = GetSize();
	47	ar << nCount;
	48	}else{
	49	nCount = 0;
	50	ar >> nCount;
	51	RemoveAll();
	52	SetSize(nCount);
	53	}
	54	for(int tmp=0;tmp<nCount;tmp++)
	55	ElementAt(tmp).Serialize(ar);
	56	}
	57	};
	58	typedef CDynamide<256,cluster> CBTDyna;
	59	typedef CBTDyna::CDynaFile CBTDynaFile;
	60	typedef CArray<CBTRecordRef,CBTRecordRef&> CBTRStack;
	61
	62	CBTDyna m_BT;
	63	struct_btCrap {
	64	BOOL m_bRootSet;
	65	CBTPageRef m_Root;
	66	} *m_BTCrap;
	67	BOOL m_bRO;
	68	CBTRStack m_btStack;
	69	CBTPage m_stackTop;
	70
	71	CBTreendex() {}
	72	~CBTreendex() { Close(); }
	73	BOOL Attach(CFile* file,BOOL bAutodelete) {
	74	m_bRO = FALSE;
	75	if(!m_BT.Attach(file,bAutodelete))
	76	return FALSE;
	77	return Attach();
	78	}
	79	BOOL Open(LPCTSTR file,BOOL bReadOnly) {
	80	if(!m_BT.Open(file,bReadOnly))
	81	return FALSE;
	82	m_bRO = bReadOnly;
	83	return Attach();
	84	}
	85	BOOL Create(LPCTSTR file) {
	86	try{
	87	CFile* f = new CFile(file,CFile::modeCreate\|CFile::modeReadWrite\|CFile::shareDenyRead\|CFile::shareDenyWrite\|CFile::typeBinary);
	88	ASSERT(f);
	89	return Attach(f,TRUE);
	90	}catch(CException* e){
	91	e->Delete();
	92	return FALSE;
	93	}
	94	}
	95	BOOL Attach() {
	96	ASSERT(m_BT.IsOpened());
	97	m_BTCrap = (_btCrap*)m_BT.m_FB.crap;
	98	if(!m_BTCrap->m_bRootSet){
	99	m_BTCrap->m_Root = AllocatePage();
	100	if(m_BTCrap->m_Root<0)
	101	return FALSE;
	102	m_BTCrap->m_bRootSet = TRUE;
	103	m_BT.Write1stBlock();
	104	}
	105	return TRUE;
	106	}
	107	BOOL Close() {
	108	m_BT.Close();
	109	return TRUE;
	110	}
	111	BOOL IsOpened() {
	112	return m_BT.IsOpened();
	113	}
	114
	115	BOOL Lookup(key& _key,value& value) {
	116	if(!IsOpened())
	117	return FALSE;
	118	ASSERT(m_BTCrap->m_bRootSet);
	119	if(!SeekToPage(_key))
	120	return FALSE;
	121	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	122	if(rr.m_Offset<0)
	123	return FALSE;
	124	ASSERT(rr.m_Offset<m_stackTop.GetSize());
	125	if(_key != m_stackTop[rr.m_Offset].m_Key)
	126	return FALSE;
	127	value = m_stackTop[rr.m_Offset].m_Value;
	128	return TRUE;
	129	}
	130	BOOL Add(key& _key,value& _value) {
	131	if(!IsOpened())
	132	return FALSE;
	133	ASSERT(m_BTCrap->m_bRootSet);
	134	if(!SeekToPage(_key))
	135	return FALSE;
	136	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	137	CBTRecord nuRecord(_key,_value);
	138	if(rr.m_Offset<0){
	139	if(m_stackTop.GetSize())
	140	nuRecord.m_ptrLeft = m_stackTop[m_stackTop.GetUpperBound()].m_ptrRight;
	141	}else if(rr.m_Offset==0){
	142	nuRecord.m_ptrRight = m_stackTop[0].m_ptrLeft;
	143	}else{
	144	nuRecord.m_ptrLeft = m_stackTop[rr.m_Offset-1].m_ptrRight;
	145	nuRecord.m_ptrRight = m_stackTop[rr.m_Offset].m_ptrLeft;
	146	}
	147	// ASSERT(rr.m_Offset==0 \|\| (m_stackTop[rr.m_Offset-1].m_Key<_key && m_stackTop[rr.m_Offset-1].m_ptrRight<0));
	148	// ASSERT(rr.m_Offset<0 \|\| m_stackTop[rr.m_Offset].m_Key>=_key && m_stackTop[rr.m_Offset].m_ptrLeft<0);
	149	if(rr.m_Offset>=0 && m_stackTop[rr.m_Offset].m_Key==_key){
	150	// Exact match found - just replace.
	151	m_stackTop[rr.m_Offset].m_Value = _value;
	152	if(!SavePage(rr.m_Page,m_stackTop))
	153	return FALSE;
	154	return TRUE;
	155	}
	156	// Split the page and propagate the split if needed..
	157	// Insert new element at rr.m_Offset..
	158	BOOL nuisnew = TRUE;
	159	for(int sp=m_btStack.GetUpperBound();sp>=0;sp--){
	160	CBTPageRef opr = m_btStack[sp].m_Page;
	161	int iAt = m_btStack[sp].m_Offset;
	162	CBTPage op;
	163	VERIFY(LoadPage(opr,op));
	164	if(iAt<0)
	165	iAt = op.GetSize();
	166	else{
	167	if(op[iAt].m_Key<nuRecord.m_Key)
	168	iAt++;
	169	ASSERT(iAt==op.GetSize() \|\| op[iAt].m_Key > nuRecord.m_Key);
	170	}
	171	op.InsertAt(iAt,nuRecord);
	172	if(iAt>0)
	173	op[iAt-1].m_ptrRight=nuRecord.m_ptrLeft;
	174	if(iAt<op.GetUpperBound())
	175	op[iAt+1].m_ptrLeft=nuRecord.m_ptrRight;
	176	if(op.GetSize()<=treeOrder*2){
	177	// This isn't causing overflow
	178	VERIFY(SavePage(opr,op));
	179	return TRUE;
	180	}
	181	TRACE0("Split\n");
	182	ASSERT(op.GetSize()==(treeOrder*2+1));
	183	CBTPageRef npr = AllocatePage();
	184	ASSERT(npr>=0);
	185	CBTPage np;
	186	ASSERT(LoadPage(npr,np));
	187	ASSERT(!np.GetSize());
	188	nuRecord = op[treeOrder];
	189	if(iAt==treeOrder){
	190	// We're inserting central element! - drop out the stack top if this is still new one
	191	for(int tmp=0;tmp<treeOrder;tmp++)
	192	np.InsertAt(tmp,op[tmp]);
	193	op.RemoveAt(0,treeOrder+1);
	194	nuRecord.m_ptrLeft = npr;
	195	nuRecord.m_ptrRight = opr;
	196	if(nuisnew)
	197	m_btStack.RemoveAt(m_btStack.GetUpperBound());
	198	}else{
	199	if(iAt<treeOrder){
	200	// We're inserting in the left subtree.
	201	// Make newpage the right one and forget it.
	202	for(int tmp=0;tmp<treeOrder;tmp++)
	203	np.InsertAt(tmp,op[tmp+treeOrder+1]);
	204	op.RemoveAt(treeOrder,treeOrder+1);
	205	nuRecord.m_ptrLeft = opr;
	206	nuRecord.m_ptrRight = npr;
	207	}else{
	208	// We're inserting in the right subtree.
	209	// Make newpage the left one, forget it, but also adjust offset in the stack
	210	for(int tmp=0;tmp<treeOrder;tmp++)
	211	np.InsertAt(tmp,op[tmp]);
	212	op.RemoveAt(0,treeOrder+1);
	213	nuRecord.m_ptrLeft = npr;
	214	nuRecord.m_ptrRight = opr;
	215	m_btStack[sp].m_Offset-=treeOrder+1;
	216	}
	217	// Note that we're not inserting new element anymore.
	218	nuisnew = FALSE;
	219	}
	220	// Do, excessive sanity checks and save pages
	221	ASSERT(op.GetSize());
	222	ASSERT(np.GetSize());
	223	VERIFY(SavePage(opr,op));
	224	VERIFY(SavePage(npr,np));
	225	}
	226	// Here we have root page overflow, which means that we're simply putting new
	227	// record in this brand new root page and also inserting this page on the bottom of the stack
	228	CBTPageRef nuroot = AllocatePage();
	229	ASSERT(nuroot>=0);
	230	CBTPage nurpa;
	231	ASSERT(LoadPage(nuroot,nurpa));
	232	ASSERT(!nurpa.GetSize());
	233	nurpa.Add(nuRecord);
	234	VERIFY(SavePage(nuroot,nurpa));
	235	m_btStack.InsertAt(0,CBTRecordRef(nuroot,0));
	236	m_BTCrap->m_Root = nuroot;
	237	m_BT.Write1stBlock();
	238	return TRUE;
	239	}
	240	BOOL Delete(key& _key) {
	241	if(!IsOpened())
	242	return FALSE;
	243	ASSERT(m_BTCrap->m_bRootSet);
	244	value _value;
	245	if(!Lookup(_key,_value))
	246	return FALSE;
	247	// Found key, check if it's a leaf
	248	{
	249	CBTRecordRef* rr = &m_btStack[m_btStack.GetUpperBound()];
	250	int rrIdx = m_btStack.GetUpperBound();
	251	if(m_stackTop[rr->m_Offset].m_ptrLeft>=0){
	252	ASSERT(m_stackTop[rr->m_Offset].m_ptrRight>=0);
	253	// It isn't - scan for the _next_ key and do dirty deeds
	254	m_btStack.Add(CBTRecordRef(m_stackTop[rr->m_Offset].m_ptrRight,0));
	255	for(;;){
	256	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	257	if(!LoadPage(rr.m_Page,m_stackTop))
	258	return FALSE;
	259	if(m_stackTop[0].m_ptrLeft<0)
	260	break;
	261	m_btStack.Add(CBTRecordRef(m_stackTop[0].m_ptrLeft,0));
	262	}
	263	// We have a leaf node here, replace victim with the first element and kill it.
	264	CBTPage uppage;
	265	rr = &m_btStack[rrIdx];
	266	if(!LoadPage(rr->m_Page,uppage))
	267	return FALSE;
	268	uppage[rr->m_Offset].m_Key=m_stackTop[0].m_Key; uppage[rr->m_Offset].m_Value=m_stackTop[0].m_Value;
	269	m_stackTop.RemoveAt(0);
	270	if(!(SavePage(rr->m_Page,uppage) && SavePage(m_btStack[m_btStack.GetUpperBound()].m_Page,m_stackTop)))
	271	return FALSE;
	272	}else{
	273	ASSERT(m_stackTop[rr->m_Offset].m_ptrRight<0);
	274	m_stackTop.RemoveAt(rr->m_Offset);
	275	if(!SavePage(rr->m_Page,m_stackTop))
	276	return FALSE;
	277	}
	278	}
	279	// We have a page to check for underflow at the top of the stack now.
	280	for(;;){
	281	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	282	if(!LoadPage(rr.m_Page,m_stackTop))
	283	return FALSE;
	284	if(m_stackTop.GetSize()>=treeOrder \|\| m_btStack.GetSize()==1)
	285	return TRUE;
	286	CBTRecordRef& rr1 = m_btStack[m_btStack.GetUpperBound()-1];
	287	CBTPage daddy;
	288	if(!LoadPage(rr1.m_Page,daddy))
	289	return FALSE;
	290	CBTPageRef nPage = daddy[rr1.m_Offset].m_ptrRight;
	291	BOOL bRight=TRUE;
	292	if(nPage<0 \|\| nPage==rr.m_Page){
	293	nPage = daddy[rr1.m_Offset].m_ptrLeft;
	294	bRight = FALSE;
	295	}
	296	ASSERT(nPage>=0 && nPage!=rr.m_Page);
	297	CBTPage neighbor;
	298	if(!LoadPage(nPage,neighbor))
	299	return FALSE;
	300	// Here we have possibly two cases:
	301	// 1. Neighboring page can share some data with use, then do share and leave
	302	// 2. Neighboring page is of treeorder in size, then merge and propagate
	303	if(neighbor.GetSize()>treeOrder){
	304	TRACE0("Redistributing..\n");
	305	// Borrow some data from there.
	306	int toBorrow = neighbor.GetSize()-treeOrder;
	307	toBorrow=toBorrow/2+1;
	308	ASSERT(toBorrow);
	309	if(bRight)
	310	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));
	311	else
	312	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));
	313	for(toBorrow--;toBorrow;toBorrow--){
	314	if(bRight){
	315	m_stackTop.Add(neighbor[0]);
	316	neighbor.RemoveAt(0);
	317	}else{
	318	m_stackTop.InsertAt(0,neighbor[neighbor.GetUpperBound()]);
	319	neighbor.RemoveAt(neighbor.GetUpperBound());
	320	}
	321	}
	322	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;
	323	neighbor.RemoveAt(bRight?0:neighbor.GetUpperBound());
	324	if(!(SavePage(rr1.m_Page,daddy) && SavePage(nPage,neighbor) && SavePage(rr.m_Page,m_stackTop)))
	325	return FALSE;
	326	rr.m_Offset = -1;// *** Point to the next??
	327	return TRUE;
	328	}
	329	TRACE0("Merging..\n");
	330	// We need to merge pages here..
	331	// We will merge them at stacktop, then we'll discard neighbor guy..
	332	if(bRight)
	333	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));
	334	else
	335	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));
	336	if(bRight){
	337	while(neighbor.GetSize()){
	338	m_stackTop.Add(neighbor[0]);
	339	neighbor.RemoveAt(0);
	340	}
	341	}else{
	342	while(neighbor.GetSize()){
	343	m_stackTop.InsertAt(0,neighbor[neighbor.GetUpperBound()]);
	344	neighbor.RemoveAt(neighbor.GetUpperBound());
	345	}
	346	}
	347	if(rr1.m_Offset>0)
	348	daddy[rr1.m_Offset-1].m_ptrRight=rr.m_Page;
	349	if(rr1.m_Offset<daddy.GetUpperBound())
	350	daddy[rr1.m_Offset+1].m_ptrLeft=rr.m_Page;
	351	daddy.RemoveAt(rr1.m_Offset);
	352	if(!(SavePage(rr1.m_Page,daddy) && SavePage(rr.m_Page,m_stackTop)))
	353	return FALSE;
	354	VERIFY(DeallocatePage(nPage));
	355	m_btStack.RemoveAt(m_btStack.GetUpperBound());
	356	}
	357	return FALSE;
	358	}
	359	BOOL GoFirst() {
	360	if(!IsOpened())
	361	return FALSE;
	362	ASSERT(m_BTCrap->m_bRootSet);
	363	m_btStack.RemoveAll();
	364	m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1));
	365	for(;;){
	366	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	367	if(!LoadPage(rr.m_Page,m_stackTop))
	368	return FALSE;
	369	if(!m_stackTop.GetSize()){
	370	ASSERT(m_btStack.GetSize()==1);
	371	return FALSE;
	372	}
	373	rr.m_Offset = 0;
	374	if(m_stackTop[rr.m_Offset].m_ptrLeft<0)
	375	return TRUE;
	376	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1));
	377	}
	378	}
	379	BOOL GoLast() {
	380	if(!IsOpened())
	381	return FALSE;
	382	ASSERT(m_BTCrap->m_bRootSet);
	383	m_btStack.RemoveAll();
	384	m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1));
	385	for(;;){
	386	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	387	if(!LoadPage(rr.m_Page,m_stackTop))
	388	return FALSE;
	389	if(!m_stackTop.GetSize()){
	390	ASSERT(m_btStack.GetSize()==1);
	391	return FALSE;
	392	}
	393	rr.m_Offset = m_stackTop.GetUpperBound();
	394	if(m_stackTop[rr.m_Offset].m_ptrRight<0)
	395	return TRUE;
	396	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,-1));
	397	}
	398	}
	399	BOOL GoNext() {
	400	if(!IsOpened())
	401	return FALSE;
	402	if(!(m_btStack.GetSize() && m_btStack[m_btStack.GetUpperBound()].m_Offset>=0))
	403	return FALSE;
	404	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	405	if(!LoadPage(rr.m_Page,m_stackTop))
	406	return FALSE;
	407	ASSERT(rr.m_Offset<m_stackTop.GetSize());
	408	if(m_stackTop[rr.m_Offset].m_ptrRight>=0){
	409	// Advance pointer in this page and dive into subtree
	410	// going left and left until we have nowhere to go.
	411	// TRACE1("Dive into page %lu",m_stackTop[rr.m_Offset].m_ptrRight);
	412	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,0));
	413	for(;;){
	414	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	415	ASSERT(rr.m_Offset==0);
	416	if(!LoadPage(rr.m_Page,m_stackTop))
	417	return FALSE;
	418	if(m_stackTop[rr.m_Offset].m_ptrLeft<0)
	419	break;
	420	// TRACE1(", %lu",m_stackTop[rr.m_Offset].m_ptrLeft);
	421	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,0));
	422	}
	423	// TRACE0("\n");
	424	return TRUE;
	425	}else if(rr.m_Offset<m_stackTop.GetUpperBound()){
	426	rr.m_Offset++;
	427	return TRUE;
	428	}
	429	// We're at the end of page go up until we're done or we have data.
	430	m_btStack.RemoveAt(m_btStack.GetUpperBound());
	431	// TRACE0("Go up");
	432	while(m_btStack.GetSize()){
	433	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	434	if(!LoadPage(rr.m_Page,m_stackTop))
	435	return FALSE;
	436	if(rr.m_Offset<m_stackTop.GetSize()){
	437	// TRACE0("\n");
	438	return TRUE;
	439	}
	440	// TRACE0(", up");
	441	m_btStack.RemoveAt(m_btStack.GetUpperBound());
	442	}
	443	// TRACE0("\nBtree is done\n");
	444	return FALSE;
	445	}
	446	BOOL GoPrev() {
	447	if(!IsOpened())
	448	return FALSE;
	449	if(!(m_btStack.GetSize() && m_btStack[m_btStack.GetUpperBound()].m_Offset>=0))
	450	return FALSE;
	451	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	452	if(!LoadPage(rr.m_Page,m_stackTop))
	453	return FALSE;
	454	ASSERT(rr.m_Offset<m_stackTop.GetSize());
	455	if(m_stackTop[rr.m_Offset].m_ptrLeft>=0){
	456	// Dive in and go right and right from the rightmost until
	457	// we have nowhere to go.
	458	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1));
	459	for(;;){
	460	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	461	if(!LoadPage(rr.m_Page,m_stackTop))
	462	return FALSE;
	463	rr.m_Offset = m_stackTop.GetUpperBound();
	464	if(m_stackTop[rr.m_Offset].m_ptrRight<0)
	465	return TRUE;
	466	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset++].m_ptrRight,-1));
	467	}
	468	return TRUE;
	469	}else if(rr.m_Offset>0){
	470	rr.m_Offset--;
	471	return TRUE;
	472	}
	473	// We're at the leftmost element in page - go up and left until we're
	474	// done or we have data.
	475	m_btStack.RemoveAt(m_btStack.GetUpperBound());
	476	while(m_btStack.GetSize()){
	477	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	478	if(!LoadPage(rr.m_Page,m_stackTop))
	479	return FALSE;
	480	rr.m_Offset--;
	481	if(rr.m_Offset>=0)
	482	return TRUE;
	483	m_btStack.RemoveAt(m_btStack.GetUpperBound());
	484	}
	485	// No more data - we were at the first element in tree.
	486	return FALSE;
	487	}
	488	BOOL GetThis(key& _key,value& _value) {
	489	if(!IsOpened())
	490	return FALSE;
	491	// *** MORE CHECKING
	492	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	493	if(!LoadPage(rr.m_Page,m_stackTop))
	494	return FALSE;
	495	_key = m_stackTop[rr.m_Offset].m_Key;
	496	_value = m_stackTop[rr.m_Offset].m_Value;
	497	return TRUE;
	498	}
	499
	500	BOOL SeekToPage(const key& _key) {
	501	ASSERT(IsOpened());
	502	ASSERT(m_BTCrap->m_bRootSet);
	503	m_btStack.RemoveAll();
	504	m_btStack.Add(CBTRecordRef(m_BTCrap->m_Root,-1));
	505	for(;;){
	506	CBTRecordRef& rr = m_btStack[m_btStack.GetUpperBound()];
	507	if(!LoadPage(rr.m_Page,m_stackTop))
	508	return FALSE;
	509	ASSERT(m_stackTop.GetSize() \|\| !m_btStack.GetUpperBound());
	510	if(!m_stackTop.GetSize()){
	511	rr.m_Offset=-1;
	512	return TRUE;
	513	}
	514	for(rr.m_Offset=0;rr.m_Offset<m_stackTop.GetSize();rr.m_Offset++){
	515	if(_key == m_stackTop[rr.m_Offset].m_Key)
	516	return TRUE;
	517	if(_key < m_stackTop[rr.m_Offset].m_Key){
	518	ASSERT(rr.m_Offset==0 \|\| m_stackTop[rr.m_Offset].m_ptrLeft==m_stackTop[rr.m_Offset-1].m_ptrRight);
	519	if(m_stackTop[rr.m_Offset].m_ptrLeft<0)
	520	return TRUE;
	521	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrLeft,-1));
	522	break;
	523	}
	524	if(rr.m_Offset==m_stackTop.GetUpperBound()){
	525	if(m_stackTop[rr.m_Offset].m_ptrRight<0){
	526	rr.m_Offset=-1;
	527	return TRUE;
	528	}
	529	m_btStack.Add(CBTRecordRef(m_stackTop[rr.m_Offset].m_ptrRight,-1));
	530	break;
	531	}
	532	}
	533	}
	534	}
	535
	536	BOOL LoadPage(CBTPageRef ref,CBTPage& page) {
	537	CFile* pageFile = m_BT.OpenFile(ref);
	538	if(!pageFile)
	539	return FALSE;
	540	BOOL rv = TRUE;
	541	try{
	542	CArchive ar(pageFile,CArchive::load);
	543	page.Serialize(ar);
	544	if(m_bRO)
	545	page.FreeExtra();// ** ???
	546	ar.Close();
	547	}catch(CException* e){
	548	e->Delete();
	549	rv = FALSE;
	550	}
	551	delete pageFile;
	552	return rv;
	553	}
	554	BOOL SavePage(CBTPageRef ref,CBTPage& page) {
	555	CFile* pageFile = m_BT.OpenFile(ref);
	556	if(!pageFile)
	557	return FALSE;
	558	BOOL rv = TRUE;
	559	try{
	560	CArchive ar(pageFile,CArchive::store);
	561	page.Serialize(ar);
	562	ar.Close();
	563	}catch(CException* e){
	564	e->Delete();
	565	rv = FALSE;
	566	}
	567	delete pageFile;
	568	return rv;
	569	}
	570	CBTPageRef AllocatePage() {
	571	CBTDynaFile* pageFile = m_BT.CreateFile();
	572	if(!pageFile)
	573	return -1;
	574	CBTPage nothing;
	575	CBTPageRef rv = pageFile->GetFile();
	576	try{
	577	CArchive ar(pageFile,CArchive::store);
	578	nothing.Serialize(ar);
	579	ar.Close();
	580	}catch(CException* e){
	581	e->Delete();
	582	rv = -1;
	583	}
	584	delete pageFile;
	585	return rv;
	586	}
	587	BOOL DeallocatePage(CBTPageRef ref) {
	588	return m_BT.DeleteFile(ref);
	589	}
	590
	591	};
	592
	593	};
	594
	595	#endif// __BTREENDEX_H