Adding upstream version 4:7.4.7.upstream/4%7.4.7upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1046 insertions, 0 deletions

diff --git a/connectivity/source/drivers/dbase/dindexnode.cxx b/connectivity/source/drivers/dbase/dindexnode.cxx
new file mode 100644
index 000000000..3ac8b8064
--- /dev/null
+++ b/connectivity/source/drivers/dbase/dindexnode.cxx
@@ -0,0 +1,1046 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ *   Licensed to the Apache Software Foundation (ASF) under one or more
+ *   contributor license agreements. See the NOTICE file distributed
+ *   with this work for additional information regarding copyright
+ *   ownership. The ASF licenses this file to you under the Apache
+ *   License, Version 2.0 (the "License"); you may not use this file
+ *   except in compliance with the License. You may obtain a copy of
+ *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#include <dbase/dindexnode.hxx>
+#include <dbase/DIndex.hxx>
+#include <o3tl/safeint.hxx>
+#include <tools/debug.hxx>
+#include <tools/stream.hxx>
+#include <sal/log.hxx>
+
+#include <algorithm>
+#include <memory>
+
+
+using namespace connectivity;
+using namespace connectivity::dbase;
+using namespace connectivity::file;
+using namespace com::sun::star::sdbc;
+
+ONDXKey::ONDXKey()
+    :nRecord(0)
+{
+}
+
+ONDXKey::ONDXKey(const ORowSetValue& rVal, sal_Int32 eType, sal_uInt32 nRec)
+    : ONDXKey_BASE(eType)
+    , nRecord(nRec)
+    , xValue(rVal)
+{
+}
+
+ONDXKey::ONDXKey(const OUString& aStr, sal_uInt32 nRec)
+    : ONDXKey_BASE(css::sdbc::DataType::VARCHAR)
+     ,nRecord(nRec)
+{
+    if (!aStr.isEmpty())
+    {
+        xValue = aStr;
+        xValue.setBound(true);
+    }
+}
+
+ONDXKey::ONDXKey(double aVal, sal_uInt32 nRec)
+    : ONDXKey_BASE(css::sdbc::DataType::DOUBLE)
+     ,nRecord(nRec)
+     ,xValue(aVal)
+{
+}
+
+// index page
+ONDXPage::ONDXPage(ODbaseIndex& rInd, sal_uInt32 nPos, ONDXPage* pParent)
+    : nRefCount(0)
+    , bNoDelete(1)
+    , nPagePos(nPos)
+    , bModified(false)
+    , nCount(0)
+    , aParent(pParent)
+    , rIndex(rInd)
+{
+    sal_uInt16 nT = rIndex.getHeader().db_maxkeys;
+    ppNodes.reset( new ONDXNode[nT] );
+}
+
+ONDXPage::~ONDXPage()
+{
+}
+
+void ONDXPage::ReleaseRef()
+{
+    assert( nRefCount >= 1);
+    if(--nRefCount == 0 && !bNoDelete)
+    {
+        QueryDelete();
+    }
+}
+
+void ONDXPage::QueryDelete()
+{
+    // Store in GarbageCollector
+    if (IsModified() && rIndex.m_pFileStream)
+        WriteONDXPage( *rIndex.m_pFileStream, *this );
+
+    bModified = false;
+    if (rIndex.UseCollector())
+    {
+        if (aChild.Is())
+            aChild->Release(false);
+
+        for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
+        {
+            if (ppNodes[i].GetChild().Is())
+                ppNodes[i].GetChild()->Release(false);
+
+            ppNodes[i] = ONDXNode();
+        }
+        bNoDelete = 1;
+
+        nCount = 0;
+        aParent.Clear();
+        rIndex.Collect(this);
+    }
+    else
+    {
+        // I'm not sure about the original purpose of this line, but right now
+        // it serves the purpose that anything that attempts to do an AddFirstRef()
+        // after an object is deleted will trip an assert.
+        nRefCount = 1 << 30;
+        delete this;
+    }
+}
+
+ONDXPagePtr& ONDXPage::GetChild(ODbaseIndex const * pIndex)
+{
+    if (!aChild.Is() && pIndex)
+    {
+        aChild = rIndex.CreatePage(aChild.GetPagePos(),this,aChild.HasPage());
+    }
+    return aChild;
+}
+
+
+sal_uInt16 ONDXPage::FindPos(const ONDXKey& rKey) const
+{
+    // searches the position for the given key in a page
+    sal_uInt16 i = 0;
+    while (i < nCount && rKey > ((*this)[i]).GetKey())
+           i++;
+
+    return i;
+}
+
+
+bool ONDXPage::Find(const ONDXKey& rKey)
+{
+    // searches the given key
+    // Speciality: At the end of the method
+    // the actual page and the position of the node, fulfilling the '<=' condition, are saved
+    // This is considered at insert.
+    sal_uInt16 i = 0;
+    while (i < nCount && rKey > ((*this)[i]).GetKey())
+           i++;
+
+    bool bResult = false;
+
+    if (!IsLeaf())
+    {
+        // descend further
+        ONDXPagePtr aPage = (i==0) ? GetChild(&rIndex) : ((*this)[i-1]).GetChild(&rIndex, this);
+        bResult = aPage.Is() && aPage->Find(rKey);
+    }
+    else if (i == nCount)
+    {
+        rIndex.m_aCurLeaf = this;
+        rIndex.m_nCurNode = i - 1;
+        bResult = false;
+    }
+    else
+    {
+        bResult = rKey == ((*this)[i]).GetKey();
+        rIndex.m_aCurLeaf = this;
+        rIndex.m_nCurNode = bResult ? i : i - 1;
+    }
+    return bResult;
+}
+
+
+bool ONDXPage::Insert(ONDXNode& rNode, sal_uInt32 nRowsLeft)
+{
+    // When creating an index there can be multiple nodes added,
+    // these are sorted ascending
+    bool bAppend = nRowsLeft > 0;
+    if (IsFull())
+    {
+        ONDXNode aSplitNode;
+        if (bAppend)
+            aSplitNode = rNode;
+        else
+        {
+            // Save the last node
+            aSplitNode = (*this)[nCount-1];
+            if(rNode.GetKey() <= aSplitNode.GetKey())
+            {
+                bool bResult = true;
+                // this practically reduces the number of nodes by 1
+                if (IsLeaf() && this == rIndex.m_aCurLeaf)
+                {
+                    // assumes, that the node, for which the condition (<=) holds, is stored in m_nCurNode
+                    --nCount;   // (otherwise we might get Assertions and GPFs - 60593)
+                    bResult = Insert(rIndex.m_nCurNode + 1, rNode);
+                }
+                else  // position unknown
+                {
+                    sal_uInt16 nPos = NODE_NOTFOUND;
+                    while (++nPos < nCount && rNode.GetKey() > ((*this)[nPos]).GetKey()) ;
+
+                    --nCount;   // (otherwise we might get Assertions and GPFs - 60593)
+                    bResult = Insert(nPos, rNode);
+                }
+
+                // can the new node be inserted
+                if (!bResult)
+                {
+                    nCount++;
+                    aSplitNode = rNode;
+                }
+            }
+            else
+                aSplitNode = rNode;
+        }
+
+        sal_uInt32 nNewPagePos = rIndex.GetPageCount();
+        sal_uInt32 nNewPageCount = nNewPagePos + 1;
+
+        // insert extracted node into parent node
+        if (!HasParent())
+        {
+            // No parent, then new root
+            ONDXPagePtr aNewRoot = rIndex.CreatePage(nNewPagePos + 1);
+            aNewRoot->SetChild(this);
+
+            rIndex.m_aRoot = aNewRoot;
+            rIndex.SetRootPos(nNewPagePos + 1);
+            rIndex.SetPageCount(++nNewPageCount);
+        }
+
+        // create new leaf and divide page
+        ONDXPagePtr aNewPage = rIndex.CreatePage(nNewPagePos,aParent);
+        rIndex.SetPageCount(nNewPageCount);
+
+        // How many nodes are being inserted?
+        // Enough, then we can fill the page to the brim
+        ONDXNode aInnerNode;
+        if (!IsLeaf() || nRowsLeft < o3tl::make_unsigned(rIndex.GetMaxNodes() / 2))
+            aInnerNode = Split(*aNewPage);
+        else
+        {
+            aInnerNode = (*this)[nCount - 1];
+
+            // Node points to the new page
+            aInnerNode.SetChild(aNewPage);
+
+            // Inner nodes have no record number
+            if (rIndex.isUnique())
+                aInnerNode.GetKey().ResetRecord();
+
+            // new page points to the page of the extracted node
+            if (!IsLeaf())
+                aNewPage->SetChild(aInnerNode.GetChild());
+        }
+
+        aNewPage->Append(aSplitNode);
+        ONDXPagePtr aTempParent = aParent;
+        if (IsLeaf())
+        {
+            rIndex.m_aCurLeaf = aNewPage;
+            rIndex.m_nCurNode = rIndex.m_aCurLeaf->Count() - 1;
+
+            // free not needed pages, there are no references to those on the page
+            // afterwards 'this' can't be valid anymore!!!
+            ReleaseFull();
+        }
+
+        // Insert extracted node
+        return aTempParent->Insert(aInnerNode);
+    }
+    else // Fill the page up
+    {
+        if (bAppend)
+        {
+            if (IsLeaf())
+                rIndex.m_nCurNode = nCount - 1;
+            return Append(rNode);
+        }
+        else
+        {
+            sal_uInt16 nNodePos = FindPos(rNode.GetKey());
+            if (IsLeaf())
+                rIndex.m_nCurNode = nNodePos;
+
+            return Insert(nNodePos, rNode);
+        }
+    }
+}
+
+
+bool ONDXPage::Insert(sal_uInt16 nPos, ONDXNode& rNode)
+{
+    sal_uInt16 nMaxCount = rIndex.getHeader().db_maxkeys;
+    if (nPos >= nMaxCount)
+        return false;
+
+    if (nCount)
+    {
+        ++nCount;
+        // shift right
+        for (sal_uInt16 i = std::min(static_cast<sal_uInt16>(nMaxCount-1), static_cast<sal_uInt16>(nCount-1)); nPos < i; --i)
+            (*this)[i] = (*this)[i-1];
+    }
+    else
+        if (nCount < nMaxCount)
+            nCount++;
+
+    // insert at the position
+    ONDXNode& rInsertNode = (*this)[nPos];
+    rInsertNode = rNode;
+    if (rInsertNode.GetChild().Is())
+    {
+        rInsertNode.GetChild()->SetParent(this);
+        rNode.GetChild()->SetParent(this);
+    }
+
+    bModified = true;
+
+    return true;
+}
+
+
+bool ONDXPage::Append(ONDXNode& rNode)
+{
+    DBG_ASSERT(!IsFull(), "no Append possible");
+    return Insert(nCount, rNode);
+}
+
+void ONDXPage::Release(bool bSave)
+{
+    // free pages
+    if (aChild.Is())
+        aChild->Release(bSave);
+
+    // free pointer
+    aChild.Clear();
+
+    for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
+    {
+        if (ppNodes[i].GetChild())
+            ppNodes[i].GetChild()->Release(bSave);
+
+        ppNodes[i].GetChild().Clear();
+    }
+    aParent.Clear();
+}
+
+void ONDXPage::ReleaseFull()
+{
+    ONDXPagePtr aTempParent = aParent;
+    Release();
+
+    if (aTempParent.Is())
+    {
+        // Free pages not needed, there will be no reference anymore to the pages
+        // afterwards 'this' can't be valid anymore!!!
+        sal_uInt16 nParentPos = aTempParent->Search(this);
+        if (nParentPos != NODE_NOTFOUND)
+            (*aTempParent)[nParentPos].GetChild().Clear();
+        else
+            aTempParent->GetChild().Clear();
+    }
+}
+
+void ONDXPage::Delete(sal_uInt16 nNodePos)
+{
+    if (IsLeaf())
+    {
+        // The last element will not be deleted
+        if (nNodePos == (nCount - 1))
+        {
+            ONDXNode aNode = (*this)[nNodePos];
+
+            // parent's KeyValue has to be replaced
+            if (HasParent())
+                aParent->SearchAndReplace(aNode.GetKey(),
+                                          (*this)[nNodePos-1].GetKey());
+        }
+    }
+
+    // Delete the node
+    Remove(nNodePos);
+
+    // Underflow
+    if (HasParent() && nCount < (rIndex.GetMaxNodes() / 2))
+    {
+        // determine, which node points to the page
+        sal_uInt16 nParentNodePos = aParent->Search(this);
+        // last element on parent-page -> merge with secondlast page
+        if (nParentNodePos == (aParent->Count() - 1))
+        {
+            if (!nParentNodePos)
+            // merge with left neighbour
+                Merge(nParentNodePos,aParent->GetChild(&rIndex));
+            else
+                Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent));
+        }
+        // otherwise merge page with next page
+        else
+        {
+            // merge with right neighbour
+            Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent)));
+            nParentNodePos++;
+        }
+        if (HasParent() && !(*aParent)[nParentNodePos].HasChild())
+            aParent->Delete(nParentNodePos);
+    }
+    else if (IsRoot())
+        // make sure that the position of the root is kept
+        rIndex.SetRootPos(nPagePos);
+}
+
+
+ONDXNode ONDXPage::Split(ONDXPage& rPage)
+{
+    DBG_ASSERT(IsFull(), "Incorrect Splitting");
+    /*  divide one page into two
+        leaf:
+            Page 1 is (n - (n/2))
+            Page 2 is (n/2)
+            Node n/2 will be duplicated
+        inner node:
+            Page 1 is (n+1)/2
+            Page 2 is (n/2-1)
+            Node ((n+1)/2 + 1) : will be taken out
+    */
+    ONDXNode aResultNode;
+    if (IsLeaf())
+    {
+        for (sal_uInt16 i = nCount - (nCount / 2), j = 0 ; i < nCount; i++)
+            rPage.Insert(j++,(*this)[i]);
+
+        // this node contains a key that already exists in the tree and must be replaced
+        ONDXNode aLastNode = (*this)[nCount - 1];
+        nCount = nCount - (nCount / 2);
+        aResultNode = (*this)[nCount - 1];
+
+        if (HasParent())
+            aParent->SearchAndReplace(aLastNode.GetKey(),
+                                      aResultNode.GetKey());
+    }
+    else
+    {
+        for (sal_uInt16 i = (nCount + 1) / 2 + 1, j = 0 ; i < nCount; i++)
+            rPage.Insert(j++,(*this)[i]);
+
+        aResultNode = (*this)[(nCount + 1) / 2];
+        nCount = (nCount + 1) / 2;
+
+        // new page points to page with extracted node
+        rPage.SetChild(aResultNode.GetChild());
+    }
+    // node points to new page
+    aResultNode.SetChild(&rPage);
+
+    // inner nodes have no record number
+    if (rIndex.isUnique())
+        aResultNode.GetKey().ResetRecord();
+    bModified = true;
+    return aResultNode;
+}
+
+
+void ONDXPage::Merge(sal_uInt16 nParentNodePos, const ONDXPagePtr& xPage)
+{
+    DBG_ASSERT(HasParent(), "no parent existing");
+    DBG_ASSERT(nParentNodePos != NODE_NOTFOUND, "Wrong index setup");
+
+    /*  Merge 2 pages   */
+    sal_uInt16 nMaxNodes = rIndex.GetMaxNodes(),
+           nMaxNodes_2 = nMaxNodes / 2;
+
+    // Determine if page is right or left neighbour
+    bool    bRight    = ((*xPage)[0].GetKey() > (*this)[0].GetKey()); // true when xPage is at the right side
+    sal_uInt16  nNewCount = (*xPage).Count() + Count();
+
+    if (IsLeaf())
+    {
+        // Condition for merge
+        if (nNewCount < (nMaxNodes_2 * 2))
+        {
+            sal_uInt16 nLastNode = bRight ? Count() - 1 : xPage->Count() - 1;
+            if (bRight)
+            {
+                DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
+                // shift all nodes from xPage to the left node (append)
+                while (xPage->Count())
+                {
+                    Append((*xPage)[0]);
+                    xPage->Remove(0);
+                }
+            }
+            else
+            {
+                DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
+                // xPage is the left page and THIS the right one
+                while (xPage->Count())
+                {
+                    Insert(0,(*xPage)[xPage->Count()-1]);
+                    xPage->Remove(xPage->Count()-1);
+                }
+                // replace old position of xPage in parent with this
+                if (nParentNodePos)
+                    (*aParent)[nParentNodePos-1].SetChild(this,aParent);
+                else // or set as right node
+                    aParent->SetChild(this);
+                aParent->SetModified(true);
+
+            }
+
+            // cancel Child-relationship at parent node
+            (*aParent)[nParentNodePos].SetChild();
+            // replace the Node-value, only if changed page is the left one, otherwise become
+            if(aParent->IsRoot() && aParent->Count() == 1)
+            {
+                (*aParent)[0].SetChild();
+                aParent->ReleaseFull();
+                aParent.Clear();
+                rIndex.SetRootPos(nPagePos);
+                rIndex.m_aRoot = this;
+                SetModified(true);
+            }
+            else
+                aParent->SearchAndReplace((*this)[nLastNode].GetKey(),(*this)[nCount-1].GetKey());
+
+            xPage->SetModified(false);
+            xPage->ReleaseFull(); // is not needed anymore
+        }
+        // balance the elements   nNewCount >= (nMaxNodes_2 * 2)
+        else
+        {
+            if (bRight)
+            {
+                // shift all nodes from xPage to the left node (append)
+                ONDXNode aReplaceNode = (*this)[nCount - 1];
+                while (nCount < nMaxNodes_2)
+                {
+                    Append((*xPage)[0]);
+                    xPage->Remove(0);
+                }
+                // Replace the node values: replace old last value by the last of xPage
+                aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[nCount-1].GetKey());
+            }
+            else
+            {
+                // insert all nodes from this in front of the xPage nodes
+                ONDXNode aReplaceNode = (*this)[nCount - 1];
+                while (xPage->Count() < nMaxNodes_2)
+                {
+                    xPage->Insert(0,(*this)[nCount-1]);
+                    Remove(nCount-1);
+                }
+                // Replace the node value
+                aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[Count()-1].GetKey());
+            }
+        }
+    }
+    else // !IsLeaf()
+    {
+        // Condition for merge
+        if (nNewCount < nMaxNodes_2 * 2)
+        {
+            if (bRight)
+            {
+                DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
+                // Parent node will be integrated; is initialized with Child from xPage
+                (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
+                Append((*aParent)[nParentNodePos]);
+                for (sal_uInt16 i = 0 ; i < xPage->Count(); i++)
+                    Append((*xPage)[i]);
+            }
+            else
+            {
+                DBG_ASSERT(xPage != this,"xPage and THIS must not be the same: infinite loop");
+                // Parent-node will be integrated; is initialized with child
+                (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); // Parent memorizes my child
+                Insert(0,(*aParent)[nParentNodePos]); // insert parent node into myself
+                while (xPage->Count())
+                {
+                    Insert(0,(*xPage)[xPage->Count()-1]);
+                    xPage->Remove(xPage->Count()-1);
+                }
+                SetChild(xPage->GetChild());
+
+                if (nParentNodePos)
+                    (*aParent)[nParentNodePos-1].SetChild(this,aParent);
+                else
+                    aParent->SetChild(this);
+            }
+
+            // afterwards parent node will be reset
+            (*aParent)[nParentNodePos].SetChild();
+            aParent->SetModified(true);
+
+            if(aParent->IsRoot() && aParent->Count() == 1)
+            {
+                (*aParent).SetChild();
+                aParent->ReleaseFull();
+                aParent.Clear();
+                rIndex.SetRootPos(nPagePos);
+                rIndex.m_aRoot = this;
+                SetModified(true);
+            }
+            else if(nParentNodePos)
+                // replace the node value
+                // for Append the range will be enlarged, for Insert the old node from xPage will reference to this
+                // that's why the node must be updated here
+                aParent->SearchAndReplace((*aParent)[nParentNodePos-1].GetKey(),(*aParent)[nParentNodePos].GetKey());
+
+            xPage->SetModified(false);
+            xPage->ReleaseFull();
+        }
+        // balance the elements
+        else
+        {
+            if (bRight)
+            {
+                while (nCount < nMaxNodes_2)
+                {
+                    (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
+                    Append((*aParent)[nParentNodePos]);
+                    (*aParent)[nParentNodePos] = (*xPage)[0];
+                    xPage->Remove(0);
+                }
+                xPage->SetChild((*aParent)[nParentNodePos].GetChild());
+                (*aParent)[nParentNodePos].SetChild(xPage,aParent);
+            }
+            else
+            {
+                while (nCount < nMaxNodes_2)
+                {
+                    (*aParent)[nParentNodePos].SetChild(GetChild(),aParent);
+                    Insert(0,(*aParent)[nParentNodePos]);
+                    (*aParent)[nParentNodePos] = (*xPage)[xPage->Count()-1];
+                    xPage->Remove(xPage->Count()-1);
+                }
+                SetChild((*aParent)[nParentNodePos].GetChild());
+                (*aParent)[nParentNodePos].SetChild(this,aParent);
+
+            }
+            aParent->SetModified(true);
+        }
+    }
+}
+
+// ONDXNode
+
+
+void ONDXNode::Read(SvStream &rStream, ODbaseIndex const & rIndex)
+{
+    rStream.ReadUInt32( aKey.nRecord ); // key
+
+    if (rIndex.getHeader().db_keytype)
+    {
+        double aDbl;
+        rStream.ReadDouble( aDbl );
+        aKey = ONDXKey(aDbl,aKey.nRecord);
+    }
+    else
+    {
+        sal_uInt16 nLen = rIndex.getHeader().db_keylen;
+        OString aBuf = read_uInt8s_ToOString(rStream, nLen);
+        //get length minus trailing whitespace
+        sal_Int32 nContentLen = aBuf.getLength();
+        while (nContentLen && aBuf[nContentLen-1] == ' ')
+            --nContentLen;
+        aKey = ONDXKey(OUString(aBuf.getStr(), nContentLen, rIndex.m_pTable->getConnection()->getTextEncoding()) ,aKey.nRecord);
+    }
+    rStream >> aChild;
+}
+
+
+void ONDXNode::Write(SvStream &rStream, const ONDXPage& rPage) const
+{
+    const ODbaseIndex& rIndex = rPage.GetIndex();
+    if (!rIndex.isUnique() || rPage.IsLeaf())
+        rStream.WriteUInt32( aKey.nRecord ); // key
+    else
+        rStream.WriteUInt32( 0 );   // key
+
+    if (rIndex.getHeader().db_keytype) // double
+    {
+        if (sizeof(double) != rIndex.getHeader().db_keylen)
+        {
+            SAL_WARN("connectivity.dbase", "this key length cannot possibly be right?");
+        }
+        if (aKey.getValue().isNull())
+        {
+            sal_uInt8 buf[sizeof(double)] = {};
+            rStream.WriteBytes(&buf[0], sizeof(double));
+        }
+        else
+            rStream.WriteDouble( aKey.getValue().getDouble() );
+    }
+    else
+    {
+        sal_uInt16 const nLen(rIndex.getHeader().db_keylen);
+        std::unique_ptr<sal_uInt8[]> pBuf(new sal_uInt8[nLen]);
+        memset(&pBuf[0], 0x20, nLen);
+        if (!aKey.getValue().isNull())
+        {
+            OUString sValue = aKey.getValue().getString();
+            OString aText(OUStringToOString(sValue, rIndex.m_pTable->getConnection()->getTextEncoding()));
+            strncpy(reinterpret_cast<char *>(&pBuf[0]), aText.getStr(),
+                std::min<size_t>(nLen, aText.getLength()));
+        }
+        rStream.WriteBytes(&pBuf[0], nLen);
+    }
+    WriteONDXPagePtr( rStream, aChild );
+}
+
+
+ONDXPagePtr& ONDXNode::GetChild(ODbaseIndex* pIndex, ONDXPage* pParent)
+{
+    if (!aChild.Is() && pIndex)
+    {
+        aChild = pIndex->CreatePage(aChild.GetPagePos(),pParent,aChild.HasPage());
+    }
+    return aChild;
+}
+
+
+// ONDXKey
+
+
+bool ONDXKey::IsText(sal_Int32 eType)
+{
+    return eType == DataType::VARCHAR || eType == DataType::CHAR;
+}
+
+
+int ONDXKey::Compare(const ONDXKey& rKey) const
+{
+    sal_Int32 nRes;
+
+    if (getValue().isNull())
+    {
+        if (rKey.getValue().isNull() || (IsText(getDBType()) && rKey.getValue().getString().isEmpty()))
+            nRes = 0;
+        else
+            nRes = -1;
+    }
+    else if (rKey.getValue().isNull())
+    {
+        if (getValue().isNull() || (IsText(getDBType()) && getValue().getString().isEmpty()))
+            nRes = 0;
+        else
+            nRes = 1;
+    }
+    else if (IsText(getDBType()))
+    {
+        nRes = getValue().getString().compareTo(rKey.getValue().getString());
+    }
+    else
+    {
+        double m = getValue().getDouble();
+        double n = rKey.getValue().getDouble();
+        nRes = (m > n) ? 1 : ( m < n) ? -1 : 0;
+    }
+
+    // compare record, if index !Unique
+    if (nRes == 0 && nRecord && rKey.nRecord)
+    {
+        nRes = (nRecord > rKey.nRecord) ? 1 :
+            (nRecord == rKey.nRecord) ? 0 : -1;
+    }
+    return nRes;
+}
+
+void ONDXKey::setValue(const ORowSetValue& _rVal)
+{
+    xValue = _rVal;
+}
+
+const ORowSetValue& ONDXKey::getValue() const
+{
+    return xValue;
+}
+
+SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPagePtr& rPage)
+{
+    rStream.ReadUInt32( rPage.nPagePos );
+    return rStream;
+}
+
+SvStream& connectivity::dbase::WriteONDXPagePtr(SvStream &rStream, const ONDXPagePtr& rPage)
+{
+    rStream.WriteUInt32( rPage.nPagePos );
+    return rStream;
+}
+
+// ONDXPagePtr
+ONDXPagePtr::ONDXPagePtr()
+    : mpPage(nullptr)
+    , nPagePos(0)
+{
+}
+
+ONDXPagePtr::ONDXPagePtr(ONDXPagePtr&& rRef) noexcept
+{
+    mpPage = rRef.mpPage;
+    rRef.mpPage = nullptr;
+    nPagePos = rRef.nPagePos;
+}
+
+ONDXPagePtr::ONDXPagePtr(ONDXPagePtr const & rRef)
+    : mpPage(rRef.mpPage)
+    , nPagePos(rRef.nPagePos)
+{
+    if (mpPage != nullptr)
+        mpPage->AddNextRef();
+}
+
+ONDXPagePtr::ONDXPagePtr(ONDXPage* pRefPage)
+    : mpPage(pRefPage)
+    , nPagePos(0)
+{
+    if (mpPage != nullptr)
+        mpPage->AddFirstRef();
+    if (pRefPage)
+        nPagePos = pRefPage->GetPagePos();
+}
+
+ONDXPagePtr::~ONDXPagePtr()
+{
+    if (mpPage != nullptr) mpPage->ReleaseRef();
+}
+
+void ONDXPagePtr::Clear()
+{
+    if (mpPage != nullptr) {
+        ONDXPage * pRefObj = mpPage;
+        mpPage = nullptr;
+        pRefObj->ReleaseRef();
+    }
+}
+
+ONDXPagePtr& ONDXPagePtr::operator=(ONDXPagePtr const & rOther)
+{
+    ONDXPagePtr aTemp(rOther);
+    *this = std::move(aTemp);
+    return *this;
+}
+
+ONDXPagePtr& ONDXPagePtr::operator=(ONDXPagePtr && rOther)
+{
+    if (mpPage != nullptr) {
+        mpPage->ReleaseRef();
+    }
+    mpPage = rOther.mpPage;
+    nPagePos = rOther.nPagePos;
+    rOther.mpPage = nullptr;
+    return *this;
+}
+
+static sal_uInt32 nValue;
+
+SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPage& rPage)
+{
+    rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
+    rStream.ReadUInt32( nValue ) >> rPage.aChild;
+    rPage.nCount = sal_uInt16(nValue);
+
+    for (sal_uInt16 i = 0; i < rPage.nCount; i++)
+        rPage[i].Read(rStream, rPage.GetIndex());
+    return rStream;
+}
+
+
+SvStream& connectivity::dbase::WriteONDXPage(SvStream &rStream, const ONDXPage& rPage)
+{
+    // Page doesn't exist yet
+    std::size_t nSize = rPage.GetPagePos() + 1;
+    nSize *= DINDEX_PAGE_SIZE;
+    if (nSize > rStream.TellEnd())
+    {
+        rStream.SetStreamSize(nSize);
+        rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
+
+        char aEmptyData[DINDEX_PAGE_SIZE] = {};
+        rStream.WriteBytes(aEmptyData, DINDEX_PAGE_SIZE);
+    }
+    rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
+
+    nValue = rPage.nCount;
+    rStream.WriteUInt32( nValue );
+    WriteONDXPagePtr( rStream, rPage.aChild );
+
+    sal_uInt16 i = 0;
+    for (; i < rPage.nCount; i++)
+        rPage[i].Write(rStream, rPage);
+
+    // check if we have to fill the stream with '\0'
+    if(i < rPage.rIndex.getHeader().db_maxkeys)
+    {
+        std::size_t nTell = rStream.Tell() % DINDEX_PAGE_SIZE;
+        sal_uInt16 nBufferSize = rStream.GetBufferSize();
+        std::size_t nRemainSize = nBufferSize - nTell;
+        if ( nRemainSize <= nBufferSize )
+        {
+            std::unique_ptr<char[]> pEmptyData( new char[nRemainSize] );
+            memset(pEmptyData.get(), 0x00, nRemainSize);
+            rStream.WriteBytes(pEmptyData.get(), nRemainSize);
+            rStream.Seek(nTell);
+        }
+    }
+    return rStream;
+}
+
+#if OSL_DEBUG_LEVEL > 1
+
+void ONDXPage::PrintPage()
+{
+    SAL_WARN("connectivity.dbase", "SDB: -----------Page: " << nPagePos << "  Parent: " << (HasParent() ? aParent->GetPagePos() : 0)
+              << "  Count: " << nCount << "  Child: " << aChild.GetPagePos() << "-----");
+
+    for (sal_uInt16 i = 0; i < nCount; i++)
+    {
+        ONDXNode rNode = (*this)[i];
+        ONDXKey&  rKey = rNode.GetKey();
+        if (!IsLeaf())
+            rNode.GetChild(&rIndex, this);
+
+        if (rKey.getValue().isNull())
+        {
+            SAL_WARN("connectivity.dbase", "SDB: [" << rKey.GetRecord() << ",NULL," << rNode.GetChild().GetPagePos() << "]");
+        }
+        else if (rIndex.getHeader().db_keytype)
+        {
+            SAL_WARN("connectivity.dbase", "SDB: [" << rKey.GetRecord() << "," << rKey.getValue().getDouble()
+                                           << "," << rNode.GetChild().GetPagePos() << "]");
+        }
+        else
+        {
+            SAL_WARN("connectivity.dbase", "SDB: [" << rKey.GetRecord() << "," << rKey.getValue().getString()
+                                           << "," << rNode.GetChild().GetPagePos() << "]" );
+        }
+    }
+    SAL_WARN("connectivity.dbase", "SDB: -----------------------------------------------");
+    if (!IsLeaf())
+    {
+#if OSL_DEBUG_LEVEL > 1
+        GetChild(&rIndex)->PrintPage();
+        for (sal_uInt16 i = 0; i < nCount; i++)
+        {
+            ONDXNode rNode = (*this)[i];
+            rNode.GetChild(&rIndex,this)->PrintPage();
+        }
+#endif
+    }
+    SAL_WARN("connectivity.dbase", "SDB: ===============================================");
+}
+#endif
+
+bool ONDXPage::IsFull() const
+{
+    return Count() == rIndex.getHeader().db_maxkeys;
+}
+
+
+sal_uInt16 ONDXPage::Search(const ONDXKey& rSearch)
+{
+    // binary search later
+    sal_uInt16 i = NODE_NOTFOUND;
+    while (++i < Count())
+        if ((*this)[i].GetKey() == rSearch)
+            break;
+
+    return (i < Count()) ? i : NODE_NOTFOUND;
+}
+
+
+sal_uInt16 ONDXPage::Search(const ONDXPage* pPage)
+{
+    sal_uInt16 i = NODE_NOTFOUND;
+    while (++i < Count())
+        if (((*this)[i]).GetChild() == pPage)
+            break;
+
+    // if not found, then we assume, that the page itself points to the page
+    return (i < Count()) ? i : NODE_NOTFOUND;
+}
+
+// runs recursively
+void ONDXPage::SearchAndReplace(const ONDXKey& rSearch,
+                                  ONDXKey const & rReplace)
+{
+    OSL_ENSURE(rSearch != rReplace,"Invalid here:rSearch == rReplace");
+    if (rSearch == rReplace)
+        return;
+
+    sal_uInt16 nPos = NODE_NOTFOUND;
+    ONDXPage* pPage = this;
+
+    while (pPage)
+    {
+        nPos = pPage->Search(rSearch);
+        if (nPos != NODE_NOTFOUND)
+            break;
+        pPage = pPage->aParent;
+    }
+
+    if (pPage)
+    {
+        (*pPage)[nPos].GetKey() = rReplace;
+        pPage->SetModified(true);
+    }
+}
+
+ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos)
+{
+    DBG_ASSERT(nCount > nPos, "incorrect index access");
+    return ppNodes[nPos];
+}
+
+
+const ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) const
+{
+    DBG_ASSERT(nCount > nPos, "incorrect index access");
+    return ppNodes[nPos];
+}
+
+void ONDXPage::Remove(sal_uInt16 nPos)
+{
+    DBG_ASSERT(nCount > nPos, "incorrect index access");
+
+    for (sal_uInt16 i = nPos; i < (nCount-1); i++)
+        (*this)[i] = (*this)[i+1];
+
+    nCount--;
+    bModified = true;
+}
+
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */