LCOV - code coverage report
Current view: top level - connectivity/source/drivers/dbase - dindexnode.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 441 0.0 %
Date: 2014-04-14 Functions: 0 41 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : #include "dbase/dindexnode.hxx"
      21             : #include "connectivity/CommonTools.hxx"
      22             : #include <osl/thread.h>
      23             : #include "dbase/DIndex.hxx"
      24             : #include <tools/debug.hxx>
      25             : #include "diagnose_ex.h"
      26             : 
      27             : #include <algorithm>
      28             : #include <boost/scoped_array.hpp>
      29             : 
      30             : 
      31             : using namespace connectivity;
      32             : using namespace connectivity::dbase;
      33             : using namespace connectivity::file;
      34             : using namespace com::sun::star::sdbc;
      35             : 
      36           0 : ONDXKey::ONDXKey(sal_uInt32 nRec)
      37           0 :     :nRecord(nRec)
      38             : {
      39           0 : }
      40             : 
      41           0 : ONDXKey::ONDXKey(const ORowSetValue& rVal, sal_Int32 eType, sal_uInt32 nRec)
      42             :     : ONDXKey_BASE(eType)
      43             :     , nRecord(nRec)
      44           0 :     , xValue(rVal)
      45             : {
      46           0 : }
      47             : 
      48           0 : ONDXKey::ONDXKey(const OUString& aStr, sal_uInt32 nRec)
      49             :     : ONDXKey_BASE(::com::sun::star::sdbc::DataType::VARCHAR)
      50           0 :      ,nRecord(nRec)
      51             : {
      52           0 :     if (!aStr.isEmpty())
      53             :     {
      54           0 :         xValue = aStr;
      55           0 :         xValue.setBound(true);
      56             :     }
      57           0 : }
      58             : 
      59             : 
      60           0 : ONDXKey::ONDXKey(double aVal, sal_uInt32 nRec)
      61             :     : ONDXKey_BASE(::com::sun::star::sdbc::DataType::DOUBLE)
      62             :      ,nRecord(nRec)
      63           0 :      ,xValue(aVal)
      64             : {
      65           0 : }
      66             : 
      67             : 
      68             : 
      69             : // index page
      70             : 
      71           0 : ONDXPage::ONDXPage(ODbaseIndex& rInd, sal_uInt32 nPos, ONDXPage* pParent)
      72             :            :nPagePos(nPos)
      73             :            ,bModified(sal_False)
      74             :            ,nCount(0)
      75             :            ,aParent(pParent)
      76             :            ,rIndex(rInd)
      77           0 :            ,ppNodes(NULL)
      78             : {
      79           0 :     sal_uInt16 nT = rIndex.getHeader().db_maxkeys;
      80           0 :     ppNodes = new ONDXNode[nT];
      81           0 : }
      82             : 
      83             : 
      84           0 : ONDXPage::~ONDXPage()
      85             : {
      86           0 :     delete[] ppNodes;
      87           0 : }
      88             : 
      89           0 : void ONDXPage::QueryDelete()
      90             : {
      91             :     // Store in GarbageCollector
      92           0 :     if (IsModified() && rIndex.m_pFileStream)
      93           0 :         WriteONDXPage( *rIndex.m_pFileStream, *this );
      94             : 
      95           0 :     bModified = sal_False;
      96           0 :     if (rIndex.UseCollector())
      97             :     {
      98           0 :         if (aChild.Is())
      99           0 :             aChild->Release(sal_False);
     100             : 
     101           0 :         for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
     102             :         {
     103           0 :             if (ppNodes[i].GetChild().Is())
     104           0 :                 ppNodes[i].GetChild()->Release(sal_False);
     105             : 
     106           0 :             ppNodes[i] = ONDXNode();
     107             :         }
     108           0 :         RestoreNoDelete();
     109             : 
     110           0 :         nCount = 0;
     111           0 :         aParent.Clear();
     112           0 :         rIndex.Collect(this);
     113             :     }
     114             :     else
     115           0 :         SvRefBase::QueryDelete();
     116           0 : }
     117             : 
     118           0 : ONDXPagePtr& ONDXPage::GetChild(ODbaseIndex* pIndex)
     119             : {
     120           0 :     if (!aChild.Is() && pIndex)
     121             :     {
     122           0 :         aChild = rIndex.CreatePage(aChild.GetPagePos(),this,aChild.HasPage());
     123             :     }
     124           0 :     return aChild;
     125             : }
     126             : 
     127             : 
     128           0 : sal_uInt16 ONDXPage::FindPos(const ONDXKey& rKey) const
     129             : {
     130             :     // searches the position for the given key in a page
     131           0 :     sal_uInt16 i = 0;
     132           0 :     while (i < nCount && rKey > ((*this)[i]).GetKey())
     133           0 :            i++;
     134             : 
     135           0 :     return i;
     136             : }
     137             : 
     138             : 
     139           0 : sal_Bool ONDXPage::Find(const ONDXKey& rKey)
     140             : {
     141             :     // searches the given key
     142             :     // Speciality: At the end of the method
     143             :     // the actual page and the position of the node, fulfilling the '<=' condition, are saved
     144             :     // This is considered at insert.
     145           0 :     sal_uInt16 i = 0;
     146           0 :     while (i < nCount && rKey > ((*this)[i]).GetKey())
     147           0 :            i++;
     148             : 
     149           0 :     sal_Bool bResult = sal_False;
     150             : 
     151           0 :     if (!IsLeaf())
     152             :     {
     153             :         // descend further
     154           0 :         ONDXPagePtr aPage = (i==0) ? GetChild(&rIndex) : ((*this)[i-1]).GetChild(&rIndex, this);
     155           0 :         bResult = aPage.Is() && aPage->Find(rKey);
     156             :     }
     157           0 :     else if (i == nCount)
     158             :     {
     159           0 :         rIndex.m_aCurLeaf = this;
     160           0 :         rIndex.m_nCurNode = i - 1;
     161           0 :         bResult = sal_False;
     162             :     }
     163             :     else
     164             :     {
     165           0 :         bResult = rKey == ((*this)[i]).GetKey();
     166           0 :         rIndex.m_aCurLeaf = this;
     167           0 :         rIndex.m_nCurNode = bResult ? i : i - 1;
     168             :     }
     169           0 :     return bResult;
     170             : }
     171             : 
     172             : 
     173           0 : sal_Bool ONDXPage::Insert(ONDXNode& rNode, sal_uInt32 nRowsLeft)
     174             : {
     175             :     // When creating an index there can be multiple nodes added,
     176             :     // these are sorted ascending
     177           0 :     sal_Bool bAppend = nRowsLeft > 0;
     178           0 :     if (IsFull())
     179             :     {
     180           0 :         sal_Bool bResult = sal_True;
     181           0 :         ONDXNode aSplitNode;
     182           0 :         if (bAppend)
     183           0 :             aSplitNode = rNode;
     184             :         else
     185             :         {
     186             :             // Save the last node
     187           0 :             aSplitNode = (*this)[nCount-1];
     188           0 :             if(rNode.GetKey() <= aSplitNode.GetKey())
     189             :             {
     190             : 
     191             :                 // this practically reduces the number of nodes by 1
     192           0 :                 if (IsLeaf() && this == &rIndex.m_aCurLeaf)
     193             :                 {
     194             :                     // assumes, that the node, for which the condition (<=) holds, is stored in m_nCurNode
     195           0 :                     --nCount;   // (otherwise we might get Assertions and GPFs - 60593)
     196           0 :                     bResult = Insert(rIndex.m_nCurNode + 1, rNode);
     197             :                 }
     198             :                 else  // position unknown
     199             :                 {
     200           0 :                     sal_uInt16 nPos = NODE_NOTFOUND;
     201           0 :                     while (++nPos < nCount && rNode.GetKey() > ((*this)[nPos]).GetKey()) ;
     202             : 
     203           0 :                     --nCount;   // (otherwise we might get Assertions and GPFs - 60593)
     204           0 :                     bResult = Insert(nPos, rNode);
     205             :                 }
     206             : 
     207             :                 // can the new node be inserted
     208           0 :                 if (!bResult)
     209             :                 {
     210           0 :                     nCount++;
     211           0 :                     aSplitNode = rNode;
     212             :                 }
     213             :             }
     214             :             else
     215           0 :                 aSplitNode = rNode;
     216             :         }
     217             : 
     218           0 :         sal_uInt32 nNewPagePos = rIndex.GetPageCount();
     219           0 :         sal_uInt32 nNewPageCount = nNewPagePos + 1;
     220             : 
     221             :         // insert extracted node into parent node
     222           0 :         if (!HasParent())
     223             :         {
     224             :             // No parent, then new root
     225           0 :             ONDXPagePtr aNewRoot = rIndex.CreatePage(nNewPagePos + 1);
     226           0 :             aNewRoot->SetChild(this);
     227             : 
     228           0 :             rIndex.m_aRoot = aNewRoot;
     229           0 :             rIndex.SetRootPos(nNewPagePos + 1);
     230           0 :             rIndex.SetPageCount(++nNewPageCount);
     231             :         }
     232             : 
     233             :         // create new leaf and divide page
     234           0 :         ONDXPagePtr aNewPage = rIndex.CreatePage(nNewPagePos,aParent);
     235           0 :         rIndex.SetPageCount(nNewPageCount);
     236             : 
     237             :         // How many nodes are being inserted?
     238             :         // Enough, then we can fill the page to the brim
     239           0 :         ONDXNode aInnerNode;
     240           0 :         if (!IsLeaf() || nRowsLeft < (sal_uInt32)(rIndex.GetMaxNodes() / 2))
     241           0 :             aInnerNode = Split(*aNewPage);
     242             :         else
     243             :         {
     244           0 :             aInnerNode = (*this)[nCount - 1];
     245             : 
     246             :             // Node points to the new page
     247           0 :             aInnerNode.SetChild(aNewPage);
     248             : 
     249             :             // Inner nodes have no record number
     250           0 :             if (rIndex.isUnique())
     251           0 :                 aInnerNode.GetKey().ResetRecord();
     252             : 
     253             :             // new page points to the page of the extracted node
     254           0 :             if (!IsLeaf())
     255           0 :                 aNewPage->SetChild(aInnerNode.GetChild());
     256             :         }
     257             : 
     258           0 :         aNewPage->Append(aSplitNode);
     259           0 :         ONDXPagePtr aTempParent = aParent;
     260           0 :         if (IsLeaf())
     261             :         {
     262           0 :             rIndex.m_aCurLeaf = aNewPage;
     263           0 :             rIndex.m_nCurNode = rIndex.m_aCurLeaf->Count() - 1;
     264             : 
     265             :             // free not needed pages, there are no references to those on the page
     266             :             // afterwards 'this' can't be valid anymore!!!
     267           0 :             ReleaseFull();
     268             :         }
     269             : 
     270             :         // Insert extracted node
     271           0 :         return aTempParent->Insert(aInnerNode);
     272             :     }
     273             :     else // Fill the page up
     274             :     {
     275           0 :         if (bAppend)
     276             :         {
     277           0 :             if (IsLeaf())
     278           0 :                 rIndex.m_nCurNode = nCount - 1;
     279           0 :             return Append(rNode);
     280             :         }
     281             :         else
     282             :         {
     283           0 :             sal_uInt16 nNodePos = FindPos(rNode.GetKey());
     284           0 :             if (IsLeaf())
     285           0 :                 rIndex.m_nCurNode = nNodePos;
     286             : 
     287           0 :             return Insert(nNodePos, rNode);
     288             :         }
     289             :     }
     290             : }
     291             : 
     292             : 
     293           0 : sal_Bool ONDXPage::Insert(sal_uInt16 nPos, ONDXNode& rNode)
     294             : {
     295           0 :     sal_uInt16 nMaxCount = rIndex.getHeader().db_maxkeys;
     296           0 :     if (nPos >= nMaxCount)
     297           0 :         return sal_False;
     298             : 
     299           0 :     if (nCount)
     300             :     {
     301           0 :         ++nCount;
     302             :         // shift right
     303           0 :         for (sal_uInt16 i = std::min((sal_uInt16)(nMaxCount-1), (sal_uInt16)(nCount-1)); nPos < i; --i)
     304           0 :             (*this)[i] = (*this)[i-1];
     305             :     }
     306             :     else
     307           0 :         if (nCount < nMaxCount)
     308           0 :             nCount++;
     309             : 
     310             :     // insert at the position
     311           0 :     ONDXNode& rInsertNode = (*this)[nPos];
     312           0 :     rInsertNode = rNode;
     313           0 :     if (rInsertNode.GetChild().Is())
     314             :     {
     315           0 :         rInsertNode.GetChild()->SetParent(this);
     316           0 :         rNode.GetChild()->SetParent(this);
     317             :     }
     318             : 
     319           0 :     bModified = sal_True;
     320             : 
     321           0 :     return sal_True;
     322             : }
     323             : 
     324             : 
     325           0 : sal_Bool ONDXPage::Append(ONDXNode& rNode)
     326             : {
     327             :     DBG_ASSERT(!IsFull(), "kein Append moeglich");
     328           0 :     return Insert(nCount, rNode);
     329             : }
     330             : 
     331           0 : void ONDXPage::Release(sal_Bool bSave)
     332             : {
     333             :     // free pages
     334           0 :     if (aChild.Is())
     335           0 :         aChild->Release(bSave);
     336             : 
     337             :     // free pointer
     338           0 :     aChild.Clear();
     339             : 
     340           0 :     for (sal_uInt16 i = 0; i < rIndex.getHeader().db_maxkeys;i++)
     341             :     {
     342           0 :         if (ppNodes[i].GetChild())
     343           0 :             ppNodes[i].GetChild()->Release(bSave);
     344             : 
     345           0 :         ppNodes[i].GetChild().Clear();
     346             :     }
     347           0 :     aParent = NULL;
     348           0 : }
     349             : 
     350           0 : void ONDXPage::ReleaseFull(sal_Bool bSave)
     351             : {
     352           0 :     ONDXPagePtr aTempParent = aParent;
     353           0 :     Release(bSave);
     354             : 
     355           0 :     if (aTempParent.Is())
     356             :     {
     357             :         // Free pages not needed, there will be no reference anymore to the pages
     358             :         // afterwards 'this' can't be valid anymore!!!
     359           0 :         sal_uInt16 nParentPos = aTempParent->Search(this);
     360           0 :         if (nParentPos != NODE_NOTFOUND)
     361           0 :             (*aTempParent)[nParentPos].GetChild().Clear();
     362             :         else
     363           0 :             aTempParent->GetChild().Clear();
     364           0 :     }
     365           0 : }
     366             : 
     367           0 : sal_Bool ONDXPage::Delete(sal_uInt16 nNodePos)
     368             : {
     369           0 :     if (IsLeaf())
     370             :     {
     371             :         // The last element will not be deleted
     372           0 :         if (nNodePos == (nCount - 1))
     373             :         {
     374           0 :             ONDXNode aNode = (*this)[nNodePos];
     375             : 
     376             :             // parent's KeyValue has to be replaced
     377           0 :             if (HasParent())
     378           0 :                 aParent->SearchAndReplace(aNode.GetKey(),
     379           0 :                                           (*this)[nNodePos-1].GetKey());
     380             :         }
     381             :     }
     382             : 
     383             :     // Delete the node
     384           0 :     Remove(nNodePos);
     385             : 
     386             :     // Underflow
     387           0 :     if (HasParent() && nCount < (rIndex.GetMaxNodes() / 2))
     388             :     {
     389             :         // determine, which node points to the page
     390           0 :         sal_uInt16 nParentNodePos = aParent->Search(this);
     391             :         // last element on parent-page -> merge with secondlast page
     392           0 :         if (nParentNodePos == (aParent->Count() - 1))
     393             :         {
     394           0 :             if (!nParentNodePos)
     395             :             // merge with left neighbour
     396           0 :                 Merge(nParentNodePos,aParent->GetChild(&rIndex));
     397             :             else
     398           0 :                 Merge(nParentNodePos,(*aParent)[nParentNodePos-1].GetChild(&rIndex,aParent));
     399             :         }
     400             :         // otherwise merge page with next page
     401             :         else
     402             :         {
     403             :             // merge with right neighbour
     404           0 :             Merge(nParentNodePos + 1,((*aParent)[nParentNodePos + 1].GetChild(&rIndex,aParent)));
     405           0 :             nParentNodePos++;
     406             :         }
     407           0 :         if (HasParent() && !(*aParent)[nParentNodePos].HasChild())
     408           0 :             aParent->Delete(nParentNodePos);
     409             :     }
     410           0 :     else if (IsRoot())
     411             :         // make sure that the position of the root is kept
     412           0 :         rIndex.SetRootPos(nPagePos);
     413           0 :     return sal_True;
     414             : }
     415             : 
     416             : 
     417             : 
     418           0 : ONDXNode ONDXPage::Split(ONDXPage& rPage)
     419             : {
     420             :     DBG_ASSERT(IsFull(), "Falsches Splitting");
     421             :     /*  devide one page into two
     422             :         leaf:
     423             :             Page 1 is (n - (n/2))
     424             :             Page 2 is (n/2)
     425             :             Node n/2 will be duplicated
     426             :         inner node:
     427             :             Page 1 is (n+1)/2
     428             :             Page 2 is (n/2-1)
     429             :             Node ((n+1)/2 + 1) : will be taken out
     430             :     */
     431           0 :     ONDXNode aResultNode;
     432           0 :     if (IsLeaf())
     433             :     {
     434           0 :         for (sal_uInt16 i = (nCount - (nCount / 2)), j = 0 ; i < nCount; i++)
     435           0 :             rPage.Insert(j++,(*this)[i]);
     436             : 
     437             :         // this node contains a key that already exists in the tree and must be replaced
     438           0 :         ONDXNode aLastNode = (*this)[nCount - 1];
     439           0 :         nCount = nCount - (nCount / 2);
     440           0 :         aResultNode = (*this)[nCount - 1];
     441             : 
     442           0 :         if (HasParent())
     443           0 :             aParent->SearchAndReplace(aLastNode.GetKey(),
     444           0 :                                       aResultNode.GetKey());
     445             :     }
     446             :     else
     447             :     {
     448           0 :         for (sal_uInt16 i = (nCount + 1) / 2 + 1, j = 0 ; i < nCount; i++)
     449           0 :             rPage.Insert(j++,(*this)[i]);
     450             : 
     451           0 :         aResultNode = (*this)[(nCount + 1) / 2];
     452           0 :         nCount = (nCount + 1) / 2;
     453             : 
     454             :         // new page points to page with extraced node
     455           0 :         rPage.SetChild(aResultNode.GetChild());
     456             :     }
     457             :     // node points to new page
     458           0 :     aResultNode.SetChild(&rPage);
     459             : 
     460             :     // inner nodes have no record number
     461           0 :     if (rIndex.isUnique())
     462           0 :         aResultNode.GetKey().ResetRecord();
     463           0 :     bModified = sal_True;
     464           0 :     return aResultNode;
     465             : }
     466             : 
     467             : 
     468           0 : void ONDXPage::Merge(sal_uInt16 nParentNodePos, ONDXPagePtr xPage)
     469             : {
     470             :     DBG_ASSERT(HasParent(), "kein Vater vorhanden");
     471             :     DBG_ASSERT(nParentNodePos != NODE_NOTFOUND, "Falscher Indexaufbau");
     472             : 
     473             :     /*  Merge 2 pages   */
     474           0 :     ONDXNode aResultNode;
     475           0 :     sal_uInt16 nMaxNodes = rIndex.GetMaxNodes(),
     476           0 :            nMaxNodes_2 = nMaxNodes / 2;
     477             : 
     478             :     // Determine if page is right or left neighbour
     479           0 :     sal_Bool    bRight    = ((*xPage)[0].GetKey() > (*this)[0].GetKey()); // sal_True, whenn xPage the right side is
     480           0 :     sal_uInt16  nNewCount = (*xPage).Count() + Count();
     481             : 
     482           0 :     if (IsLeaf())
     483             :     {
     484             :         // Condition for merge
     485           0 :         if (nNewCount < (nMaxNodes_2 * 2))
     486             :         {
     487           0 :             sal_uInt16 nLastNode = bRight ? Count() - 1 : xPage->Count() - 1;
     488           0 :             if (bRight)
     489             :             {
     490             :                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
     491             :                 // shift all nodes from xPage to the left node (append)
     492           0 :                 while (xPage->Count())
     493             :                 {
     494           0 :                     Append((*xPage)[0]);
     495           0 :                     xPage->Remove(0);
     496             :                 }
     497             :             }
     498             :             else
     499             :             {
     500             :                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
     501             :                 // xPage is the left page and THIS the right one
     502           0 :                 while (xPage->Count())
     503             :                 {
     504           0 :                     Insert(0,(*xPage)[xPage->Count()-1]);
     505           0 :                     xPage->Remove(xPage->Count()-1);
     506             :                 }
     507             :                 // replace old position of xPage in parent with this
     508           0 :                 if (nParentNodePos)
     509           0 :                     (*aParent)[nParentNodePos-1].SetChild(this,aParent);
     510             :                 else // or set as right node
     511           0 :                     aParent->SetChild(this);
     512           0 :                 aParent->SetModified(sal_True);
     513             : 
     514             :             }
     515             : 
     516             :             // cancel Child-relationship at parent node
     517           0 :             (*aParent)[nParentNodePos].SetChild();
     518             :             // replace the Node-value, only if changed page is the left one, otherwise become
     519           0 :             if(aParent->IsRoot() && aParent->Count() == 1)
     520             :             {
     521           0 :                 (*aParent)[0].SetChild();
     522           0 :                 aParent->ReleaseFull();
     523           0 :                 aParent = NULL;
     524           0 :                 rIndex.SetRootPos(nPagePos);
     525           0 :                 rIndex.m_aRoot = this;
     526           0 :                 SetModified(sal_True);
     527             :             }
     528             :             else
     529           0 :                 aParent->SearchAndReplace((*this)[nLastNode].GetKey(),(*this)[nCount-1].GetKey());
     530             : 
     531           0 :             xPage->SetModified(sal_False);
     532           0 :             xPage->ReleaseFull(); // is not needed anymore
     533             :         }
     534             :         // balance the elements   nNewCount >= (nMaxNodes_2 * 2)
     535             :         else
     536             :         {
     537           0 :             if (bRight)
     538             :             {
     539             :                 // shift all nodes from xPage to the left node (append)
     540           0 :                 ONDXNode aReplaceNode = (*this)[nCount - 1];
     541           0 :                 while (nCount < nMaxNodes_2)
     542             :                 {
     543           0 :                     Append((*xPage)[0]);
     544           0 :                     xPage->Remove(0);
     545             :                 }
     546             :                 // Replace the node values: replace old last value by the last of xPage
     547           0 :                 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[nCount-1].GetKey());
     548             :             }
     549             :             else
     550             :             {
     551             :                 // insert all nodes from this in front of the xPage nodes
     552           0 :                 ONDXNode aReplaceNode = (*this)[nCount - 1];
     553           0 :                 while (xPage->Count() < nMaxNodes_2)
     554             :                 {
     555           0 :                     xPage->Insert(0,(*this)[nCount-1]);
     556           0 :                     Remove(nCount-1);
     557             :                 }
     558             :                 // Replace the node value
     559           0 :                 aParent->SearchAndReplace(aReplaceNode.GetKey(),(*this)[Count()-1].GetKey());
     560             :             }
     561             :         }
     562             :     }
     563             :     else // !IsLeaf()
     564             :     {
     565             :         // Condition for merge
     566           0 :         if (nNewCount < nMaxNodes_2 * 2)
     567             :         {
     568           0 :             if (bRight)
     569             :             {
     570             :                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
     571             :                 // Parent node will be integrated; is initialized with Child from xPage
     572           0 :                 (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
     573           0 :                 Append((*aParent)[nParentNodePos]);
     574           0 :                 for (sal_uInt16 i = 0 ; i < xPage->Count(); i++)
     575           0 :                     Append((*xPage)[i]);
     576             :             }
     577             :             else
     578             :             {
     579             :                 DBG_ASSERT(&xPage != this,"xPage und THIS duerfen nicht gleich sein: Endlosschleife");
     580             :                 // Parent-node will be integrated; is initialized with child
     581           0 :                 (*aParent)[nParentNodePos].SetChild(GetChild(),aParent); // Parent memorizes my child
     582           0 :                 Insert(0,(*aParent)[nParentNodePos]); // insert parent node into myself
     583           0 :                 while (xPage->Count())
     584             :                 {
     585           0 :                     Insert(0,(*xPage)[xPage->Count()-1]);
     586           0 :                     xPage->Remove(xPage->Count()-1);
     587             :                 }
     588           0 :                 SetChild(xPage->GetChild());
     589             : 
     590           0 :                 if (nParentNodePos)
     591           0 :                     (*aParent)[nParentNodePos-1].SetChild(this,aParent);
     592             :                 else
     593           0 :                     aParent->SetChild(this);
     594             :             }
     595             : 
     596             :             // afterwards parent node will be reset
     597           0 :             (*aParent)[nParentNodePos].SetChild();
     598           0 :             aParent->SetModified(sal_True);
     599             : 
     600           0 :             if(aParent->IsRoot() && aParent->Count() == 1)
     601             :             {
     602           0 :                 (*aParent).SetChild();
     603           0 :                 aParent->ReleaseFull();
     604           0 :                 aParent = NULL;
     605           0 :                 rIndex.SetRootPos(nPagePos);
     606           0 :                 rIndex.m_aRoot = this;
     607           0 :                 SetModified(sal_True);
     608             :             }
     609           0 :             else if(nParentNodePos)
     610             :                 // replace the node value
     611             :                 // for Append the range will be enlarged, for Insert the old node from xPage will reference to this
     612             :                 // thats why the node must be updated here
     613           0 :                 aParent->SearchAndReplace((*aParent)[nParentNodePos-1].GetKey(),(*aParent)[nParentNodePos].GetKey());
     614             : 
     615           0 :             xPage->SetModified(sal_False);
     616           0 :             xPage->ReleaseFull();
     617             :         }
     618             :         // balance the elements
     619             :         else
     620             :         {
     621           0 :             if (bRight)
     622             :             {
     623           0 :                 while (nCount < nMaxNodes_2)
     624             :                 {
     625           0 :                     (*aParent)[nParentNodePos].SetChild(xPage->GetChild(),aParent);
     626           0 :                     Append((*aParent)[nParentNodePos]);
     627           0 :                     (*aParent)[nParentNodePos] = (*xPage)[0];
     628           0 :                     xPage->Remove(0);
     629             :                 }
     630           0 :                 xPage->SetChild((*aParent)[nParentNodePos].GetChild());
     631           0 :                 (*aParent)[nParentNodePos].SetChild(xPage,aParent);
     632             :             }
     633             :             else
     634             :             {
     635           0 :                 while (nCount < nMaxNodes_2)
     636             :                 {
     637           0 :                     (*aParent)[nParentNodePos].SetChild(GetChild(),aParent);
     638           0 :                     Insert(0,(*aParent)[nParentNodePos]);
     639           0 :                     (*aParent)[nParentNodePos] = (*xPage)[xPage->Count()-1];
     640           0 :                     xPage->Remove(xPage->Count()-1);
     641             :                 }
     642           0 :                 SetChild((*aParent)[nParentNodePos].GetChild());
     643           0 :                 (*aParent)[nParentNodePos].SetChild(this,aParent);
     644             : 
     645             :             }
     646           0 :             aParent->SetModified(sal_True);
     647             :         }
     648           0 :     }
     649           0 : }
     650             : 
     651             : // ONDXNode
     652             : 
     653             : 
     654             : 
     655           0 : void ONDXNode::Read(SvStream &rStream, ODbaseIndex& rIndex)
     656             : {
     657           0 :     rStream.ReadUInt32( aKey.nRecord ); // key
     658             : 
     659           0 :     if (rIndex.getHeader().db_keytype)
     660             :     {
     661             :         double aDbl;
     662           0 :         rStream.ReadDouble( aDbl );
     663           0 :         aKey = ONDXKey(aDbl,aKey.nRecord);
     664             :     }
     665             :     else
     666             :     {
     667           0 :         sal_uInt16 nLen = rIndex.getHeader().db_keylen;
     668           0 :         OString aBuf = read_uInt8s_ToOString(rStream, nLen);
     669             :         //get length minus trailing whitespace
     670           0 :         sal_Int32 nContentLen = aBuf.getLength();
     671           0 :         while (nContentLen && aBuf[nContentLen-1] == ' ')
     672           0 :             --nContentLen;
     673           0 :         aKey = ONDXKey(OUString(aBuf.getStr(), nContentLen, rIndex.m_pTable->getConnection()->getTextEncoding()) ,aKey.nRecord);
     674             :     }
     675           0 :     rStream >> aChild;
     676           0 : }
     677             : 
     678             : 
     679           0 : void ONDXNode::Write(SvStream &rStream, const ONDXPage& rPage) const
     680             : {
     681           0 :     const ODbaseIndex& rIndex = rPage.GetIndex();
     682           0 :     if (!rIndex.isUnique() || rPage.IsLeaf())
     683           0 :         rStream.WriteUInt32( (sal_uInt32)aKey.nRecord ); // key
     684             :     else
     685           0 :         rStream.WriteUInt32( (sal_uInt32)0 );   // key
     686             : 
     687           0 :     if (rIndex.getHeader().db_keytype) // double
     688             :     {
     689           0 :         if (sizeof(double) != rIndex.getHeader().db_keylen)
     690             :         {
     691             :             OSL_TRACE("this key length cannot possibly be right?");
     692             :         }
     693           0 :         if (aKey.getValue().isNull())
     694             :         {
     695             :             sal_uInt8 buf[sizeof(double)];
     696           0 :             memset(&buf[0], 0, sizeof(double));
     697           0 :             rStream.Write(&buf[0], sizeof(double));
     698             :         }
     699             :         else
     700           0 :             rStream.WriteDouble( (double) aKey.getValue() );
     701             :     }
     702             :     else
     703             :     {
     704           0 :         sal_uInt16 const nLen(rIndex.getHeader().db_keylen);
     705           0 :         ::boost::scoped_array<sal_uInt8> pBuf(new sal_uInt8[nLen]);
     706           0 :         memset(&pBuf[0], 0x20, nLen);
     707           0 :         if (!aKey.getValue().isNull())
     708             :         {
     709           0 :             OUString sValue = aKey.getValue();
     710           0 :             OString aText(OUStringToOString(sValue, rIndex.m_pTable->getConnection()->getTextEncoding()));
     711           0 :             strncpy(reinterpret_cast<char *>(&pBuf[0]), aText.getStr(),
     712           0 :                 std::min<size_t>(nLen, aText.getLength()));
     713             :         }
     714           0 :         rStream.Write(&pBuf[0], nLen);
     715             :     }
     716           0 :     WriteONDXPagePtr( rStream, aChild );
     717           0 : }
     718             : 
     719             : 
     720             : 
     721           0 : ONDXPagePtr& ONDXNode::GetChild(ODbaseIndex* pIndex, ONDXPage* pParent)
     722             : {
     723           0 :     if (!aChild.Is() && pIndex)
     724             :     {
     725           0 :         aChild = pIndex->CreatePage(aChild.GetPagePos(),pParent,aChild.HasPage());
     726             :     }
     727           0 :     return aChild;
     728             : }
     729             : 
     730             : 
     731             : // ONDXKey
     732             : 
     733             : 
     734           0 : sal_Bool ONDXKey::IsText(sal_Int32 eType)
     735             : {
     736           0 :     return eType == DataType::VARCHAR || eType == DataType::CHAR;
     737             : }
     738             : 
     739             : 
     740           0 : int ONDXKey::Compare(const ONDXKey& rKey) const
     741             : {
     742             :     sal_Int32 nRes;
     743             : 
     744           0 :     if (getValue().isNull())
     745             :     {
     746           0 :         if (rKey.getValue().isNull() || (rKey.IsText(getDBType()) && rKey.getValue().getString().isEmpty()))
     747           0 :             nRes = 0;
     748             :         else
     749           0 :             nRes = -1;
     750             :     }
     751           0 :     else if (rKey.getValue().isNull())
     752             :     {
     753           0 :         if (getValue().isNull() || (IsText(getDBType()) && getValue().getString().isEmpty()))
     754           0 :             nRes = 0;
     755             :         else
     756           0 :             nRes = 1;
     757             :     }
     758           0 :     else if (IsText(getDBType()))
     759             :     {
     760           0 :         nRes = getValue().getString().compareTo(rKey.getValue());
     761             :     }
     762             :     else
     763             :     {
     764           0 :         double m = getValue();
     765           0 :         double n = rKey.getValue();
     766           0 :         nRes = (m > n) ? 1 : ( m < n) ? -1 : 0;
     767             :     }
     768             : 
     769             :     // compare record, if index !Unique
     770           0 :     if (nRes == 0 && nRecord && rKey.nRecord)
     771             :     {
     772           0 :         nRes = (nRecord > rKey.nRecord) ? 1 :
     773           0 :             (nRecord == rKey.nRecord) ? 0 : -1;
     774             :     }
     775           0 :     return nRes;
     776             : }
     777             : 
     778           0 : void ONDXKey::setValue(const ORowSetValue& _rVal)
     779             : {
     780           0 :     xValue = _rVal;
     781           0 : }
     782             : 
     783           0 : const ORowSetValue& ONDXKey::getValue() const
     784             : {
     785           0 :     return xValue;
     786             : }
     787             : 
     788           0 : SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPagePtr& rPage)
     789             : {
     790           0 :     rStream.ReadUInt32( rPage.nPagePos );
     791           0 :     return rStream;
     792             : }
     793             : 
     794           0 : SvStream& connectivity::dbase::WriteONDXPagePtr(SvStream &rStream, const ONDXPagePtr& rPage)
     795             : {
     796           0 :     rStream.WriteUInt32( rPage.nPagePos );
     797           0 :     return rStream;
     798             : }
     799             : 
     800             : 
     801             : // ONDXPagePtr
     802             : 
     803             : 
     804           0 : ONDXPagePtr::ONDXPagePtr(const ONDXPagePtr& rRef)
     805             :               :ONDXPageRef(rRef)
     806           0 :               ,nPagePos(rRef.nPagePos)
     807             : {
     808           0 : }
     809             : 
     810             : 
     811           0 : ONDXPagePtr::ONDXPagePtr(ONDXPage* pRefPage)
     812             :               :ONDXPageRef(pRefPage)
     813           0 :               ,nPagePos(0)
     814             : {
     815           0 :     if (pRefPage)
     816           0 :         nPagePos = pRefPage->GetPagePos();
     817           0 : }
     818             : 
     819           0 : ONDXPagePtr& ONDXPagePtr::operator=(const ONDXPagePtr& rRef)
     820             : {
     821           0 :     ONDXPageRef::operator=(rRef);
     822           0 :     nPagePos = rRef.nPagePos;
     823           0 :     return *this;
     824             : }
     825             : 
     826             : 
     827           0 : ONDXPagePtr& ONDXPagePtr::operator= (ONDXPage* pRef)
     828             : {
     829           0 :     ONDXPageRef::operator=(pRef);
     830           0 :     nPagePos = (pRef) ? pRef->GetPagePos() : 0;
     831           0 :     return *this;
     832             : }
     833             : 
     834             : static sal_uInt32 nValue;
     835             : 
     836           0 : SvStream& connectivity::dbase::operator >> (SvStream &rStream, ONDXPage& rPage)
     837             : {
     838           0 :     rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
     839           0 :     rStream.ReadUInt32( nValue ) >> rPage.aChild;
     840           0 :     rPage.nCount = sal_uInt16(nValue);
     841             : 
     842           0 :     for (sal_uInt16 i = 0; i < rPage.nCount; i++)
     843           0 :         rPage[i].Read(rStream, rPage.GetIndex());
     844           0 :     return rStream;
     845             : }
     846             : 
     847             : 
     848           0 : SvStream& connectivity::dbase::WriteONDXPage(SvStream &rStream, const ONDXPage& rPage)
     849             : {
     850             :     // Page doesn't exist yet
     851           0 :     sal_Size nSize = rPage.GetPagePos() + 1;
     852           0 :     nSize *= DINDEX_PAGE_SIZE;
     853           0 :     if (nSize > rStream.Seek(STREAM_SEEK_TO_END))
     854             :     {
     855           0 :         rStream.SetStreamSize(nSize);
     856           0 :         rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
     857             : 
     858             :         char aEmptyData[DINDEX_PAGE_SIZE];
     859           0 :         memset(aEmptyData,0x00,DINDEX_PAGE_SIZE);
     860           0 :         rStream.Write((sal_uInt8*)aEmptyData,DINDEX_PAGE_SIZE);
     861             :     }
     862           0 :     sal_Size nCurrentPos = rStream.Seek(rPage.GetPagePos() * DINDEX_PAGE_SIZE);
     863             :     OSL_UNUSED( nCurrentPos );
     864             : 
     865           0 :     nValue = rPage.nCount;
     866           0 :     rStream.WriteUInt32( nValue );
     867           0 :     WriteONDXPagePtr( rStream, rPage.aChild );
     868             : 
     869           0 :     sal_uInt16 i = 0;
     870           0 :     for (; i < rPage.nCount; i++)
     871           0 :         rPage[i].Write(rStream, rPage);
     872             : 
     873             :     // check if we have to fill the stream with '\0'
     874           0 :     if(i < rPage.rIndex.getHeader().db_maxkeys)
     875             :     {
     876           0 :         sal_Size nTell = rStream.Tell() % DINDEX_PAGE_SIZE;
     877           0 :         sal_uInt16 nBufferSize = rStream.GetBufferSize();
     878           0 :         sal_Size nRemainSize = nBufferSize - nTell;
     879           0 :         if ( nRemainSize <= nBufferSize )
     880             :         {
     881           0 :             char* pEmptyData = new char[nRemainSize];
     882           0 :             memset(pEmptyData,0x00,nRemainSize);
     883           0 :             rStream.Write((sal_uInt8*)pEmptyData,nRemainSize);
     884           0 :             rStream.Seek(nTell);
     885           0 :             delete [] pEmptyData;
     886             :         }
     887             :     }
     888           0 :     return rStream;
     889             : }
     890             : 
     891             : #if OSL_DEBUG_LEVEL > 1
     892             : 
     893             : void ONDXPage::PrintPage()
     894             : {
     895             :     OSL_TRACE("\nSDB: -----------Page: %d  Parent: %d  Count: %d  Child: %d-----",
     896             :         nPagePos, HasParent() ? aParent->GetPagePos() : 0 ,nCount, aChild.GetPagePos());
     897             : 
     898             :     for (sal_uInt16 i = 0; i < nCount; i++)
     899             :     {
     900             :         ONDXNode rNode = (*this)[i];
     901             :         ONDXKey&  rKey = rNode.GetKey();
     902             :         if (!IsLeaf())
     903             :             rNode.GetChild(&rIndex, this);
     904             : 
     905             :         if (rKey.getValue().isNull())
     906             :         {
     907             :             OSL_TRACE("SDB: [%d,NULL,%d]",rKey.GetRecord(), rNode.GetChild().GetPagePos());
     908             :         }
     909             :         else if (rIndex.getHeader().db_keytype)
     910             :         {
     911             :             OSL_TRACE("SDB: [%d,%f,%d]",rKey.GetRecord(), rKey.getValue().getDouble(),rNode.GetChild().GetPagePos());
     912             :         }
     913             :         else
     914             :         {
     915             :             OSL_TRACE("SDB: [%d,%s,%d]",rKey.GetRecord(), OUStringToOString(rKey.getValue().getString(), rIndex.m_pTable->getConnection()->getTextEncoding()).getStr(),rNode.GetChild().GetPagePos());
     916             :         }
     917             :     }
     918             :     OSL_TRACE("SDB: -----------------------------------------------");
     919             :     if (!IsLeaf())
     920             :     {
     921             : #if OSL_DEBUG_LEVEL > 1
     922             :         GetChild(&rIndex)->PrintPage();
     923             :         for (sal_uInt16 i = 0; i < nCount; i++)
     924             :         {
     925             :             ONDXNode rNode = (*this)[i];
     926             :             rNode.GetChild(&rIndex,this)->PrintPage();
     927             :         }
     928             : #endif
     929             :     }
     930             :     OSL_TRACE("SDB: ===============================================");
     931             : }
     932             : #endif
     933             : 
     934           0 : sal_Bool ONDXPage::IsFull() const
     935             : {
     936           0 :     return Count() == rIndex.getHeader().db_maxkeys;
     937             : }
     938             : 
     939             : 
     940           0 : sal_uInt16 ONDXPage::Search(const ONDXKey& rSearch)
     941             : {
     942             :     // binary search later
     943           0 :     sal_uInt16 i = NODE_NOTFOUND;
     944           0 :     while (++i < Count())
     945           0 :         if ((*this)[i].GetKey() == rSearch)
     946           0 :             break;
     947             : 
     948           0 :     return (i < Count()) ? i : NODE_NOTFOUND;
     949             : }
     950             : 
     951             : 
     952           0 : sal_uInt16 ONDXPage::Search(const ONDXPage* pPage)
     953             : {
     954           0 :     sal_uInt16 i = NODE_NOTFOUND;
     955           0 :     while (++i < Count())
     956           0 :         if (((*this)[i]).GetChild() == pPage)
     957           0 :             break;
     958             : 
     959             :     // if not found, then we assume, that the page itself points to the page
     960           0 :     return (i < Count()) ? i : NODE_NOTFOUND;
     961             : }
     962             : 
     963             : // runs recursively
     964           0 : void ONDXPage::SearchAndReplace(const ONDXKey& rSearch,
     965             :                                   ONDXKey& rReplace)
     966             : {
     967             :     OSL_ENSURE(rSearch != rReplace,"Invalid here:rSearch == rReplace");
     968           0 :     if (rSearch != rReplace)
     969             :     {
     970           0 :         sal_uInt16 nPos = NODE_NOTFOUND;
     971           0 :         ONDXPage* pPage = this;
     972             : 
     973           0 :         while (pPage && (nPos = pPage->Search(rSearch)) == NODE_NOTFOUND)
     974           0 :             pPage = pPage->aParent;
     975             : 
     976           0 :         if (pPage)
     977             :         {
     978           0 :             (*pPage)[nPos].GetKey() = rReplace;
     979           0 :             pPage->SetModified(sal_True);
     980             :         }
     981             :     }
     982           0 : }
     983             : 
     984           0 : ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos)
     985             : {
     986             :     DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
     987           0 :     return ppNodes[nPos];
     988             : }
     989             : 
     990             : 
     991           0 : const ONDXNode& ONDXPage::operator[] (sal_uInt16 nPos) const
     992             : {
     993             :     DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
     994           0 :     return ppNodes[nPos];
     995             : }
     996             : 
     997           0 : void ONDXPage::Remove(sal_uInt16 nPos)
     998             : {
     999             :     DBG_ASSERT(nCount > nPos, "falscher Indexzugriff");
    1000             : 
    1001           0 :     for (sal_uInt16 i = nPos; i < (nCount-1); i++)
    1002           0 :         (*this)[i] = (*this)[i+1];
    1003             : 
    1004           0 :     nCount--;
    1005           0 :     bModified = sal_True;
    1006           0 : }
    1007             : 
    1008             : 
    1009             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10