summaryrefslogtreecommitdiffstats
path: root/connectivity/source/drivers/dbase/dindexnode.cxx
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 09:06:44 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 09:06:44 +0000
commited5640d8b587fbcfed7dd7967f3de04b37a76f26 (patch)
tree7a5f7c6c9d02226d7471cb3cc8fbbf631b415303 /connectivity/source/drivers/dbase/dindexnode.cxx
parentInitial commit. (diff)
downloadlibreoffice-upstream.tar.xz
libreoffice-upstream.zip
Adding upstream version 4:7.4.7.upstream/4%7.4.7upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'connectivity/source/drivers/dbase/dindexnode.cxx')
-rw-r--r--connectivity/source/drivers/dbase/dindexnode.cxx1046
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: */