LCOV - code coverage report
Current view: top level - store/source - stortree.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 221 0.0 %
Date: 2014-04-14 Functions: 0 15 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 "stortree.hxx"
      21             : 
      22             : #include "sal/types.h"
      23             : #include "osl/diagnose.h"
      24             : 
      25             : #include "store/types.h"
      26             : 
      27             : #include "storbase.hxx"
      28             : #include "storbios.hxx"
      29             : 
      30             : using namespace store;
      31             : 
      32             : /*========================================================================
      33             :  *
      34             :  * OStoreBTreeNodeData implementation.
      35             :  *
      36             :  *======================================================================*/
      37             : /*
      38             :  * OStoreBTreeNodeData.
      39             :  */
      40           0 : OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
      41           0 :     : OStorePageData (nPageSize)
      42             : {
      43           0 :     base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
      44           0 :     base::m_aDescr.m_nUsed  = store::htons(self::thePageSize); // usageCount(0)
      45           0 :     self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
      46             : 
      47           0 :     sal_uInt16 const n = capacityCount();
      48           0 :     T const          t;
      49             : 
      50           0 :     for (sal_uInt16 i = 1; i < n; i++)
      51           0 :         m_pData[i] = t;
      52           0 : }
      53             : 
      54             : /*
      55             :  * find.
      56             :  */
      57           0 : sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
      58             : {
      59           0 :     sal_Int32 l = 0;
      60           0 :     sal_Int32 r = usageCount() - 1;
      61             : 
      62           0 :     while (l < r)
      63             :     {
      64           0 :         sal_Int32 const m = ((l + r) >> 1);
      65             : 
      66           0 :         if (t.m_aKey == m_pData[m].m_aKey)
      67           0 :             return ((sal_uInt16)(m));
      68           0 :         if (t.m_aKey < m_pData[m].m_aKey)
      69           0 :             r = m - 1;
      70             :         else
      71           0 :             l = m + 1;
      72             :     }
      73             : 
      74           0 :     sal_uInt16 const k = ((sal_uInt16)(r));
      75           0 :     if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
      76           0 :         return(k - 1);
      77             :     else
      78           0 :         return(k);
      79             : }
      80             : 
      81             : /*
      82             :  * insert.
      83             :  */
      84           0 : void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
      85             : {
      86           0 :     sal_uInt16 const n = usageCount();
      87           0 :     sal_uInt16 const m = capacityCount();
      88           0 :     if ((n < m) && (i < m))
      89             :     {
      90             :         // shift right.
      91           0 :         memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
      92             : 
      93             :         // insert.
      94           0 :         m_pData[i] = t;
      95           0 :         usageCount (n + 1);
      96             :     }
      97           0 : }
      98             : 
      99             : /*
     100             :  * remove.
     101             :  */
     102           0 : void OStoreBTreeNodeData::remove (sal_uInt16 i)
     103             : {
     104           0 :     sal_uInt16 const n = usageCount();
     105           0 :     if (i < n)
     106             :     {
     107             :         // shift left.
     108           0 :         memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));
     109             : 
     110             :         // truncate.
     111           0 :         m_pData[n - 1] = T();
     112           0 :         usageCount (n - 1);
     113             :     }
     114           0 : }
     115             : 
     116             : /*
     117             :  * split (left half copied from right half of left page).
     118             :  */
     119           0 : void OStoreBTreeNodeData::split (const self& rPageL)
     120             : {
     121           0 :     sal_uInt16 const h = capacityCount() / 2;
     122           0 :     memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
     123           0 :     truncate (h);
     124           0 : }
     125             : 
     126             : /*
     127             :  * truncate.
     128             :  */
     129           0 : void OStoreBTreeNodeData::truncate (sal_uInt16 n)
     130             : {
     131           0 :     sal_uInt16 const m = capacityCount();
     132           0 :     T const          t;
     133             : 
     134           0 :     for (sal_uInt16 i = n; i < m; i++)
     135           0 :         m_pData[i] = t;
     136           0 :     usageCount (n);
     137           0 : }
     138             : 
     139             : /*========================================================================
     140             :  *
     141             :  * OStoreBTreeNodeObject implementation.
     142             :  *
     143             :  *======================================================================*/
     144             : /*
     145             :  * guard.
     146             :  */
     147           0 : storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
     148             : {
     149           0 :     return PageHolderObject< page >::guard (m_xPage, nAddr);
     150             : }
     151             : 
     152             : /*
     153             :  * verify.
     154             :  */
     155           0 : storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
     156             : {
     157           0 :     return PageHolderObject< page >::verify (m_xPage, nAddr);
     158             : }
     159             : 
     160             : /*
     161             :  * split.
     162             :  */
     163           0 : storeError OStoreBTreeNodeObject::split (
     164             :     sal_uInt16                 nIndexL,
     165             :     PageHolderObject< page > & rxPageL,
     166             :     OStorePageBIOS           & rBIOS)
     167             : {
     168           0 :     PageHolderObject< page > xPage (m_xPage);
     169           0 :     if (!xPage.is())
     170           0 :         return store_E_InvalidAccess;
     171             : 
     172             :     // Check left page usage.
     173           0 :     if (!rxPageL.is())
     174           0 :         return store_E_InvalidAccess;
     175           0 :     if (!rxPageL->querySplit())
     176           0 :         return store_E_None;
     177             : 
     178             :     // Construct right page.
     179           0 :     PageHolderObject< page > xPageR;
     180           0 :     if (!xPageR.construct (rBIOS.allocator()))
     181           0 :         return store_E_OutOfMemory;
     182             : 
     183             :     // Split right page off left page.
     184           0 :     xPageR->split (*rxPageL);
     185           0 :     xPageR->depth (rxPageL->depth());
     186             : 
     187             :     // Allocate right page.
     188           0 :     self aNodeR (xPageR.get());
     189           0 :     storeError eErrCode = rBIOS.allocate (aNodeR);
     190           0 :     if (eErrCode != store_E_None)
     191           0 :         return eErrCode;
     192             : 
     193             :     // Truncate left page.
     194           0 :     rxPageL->truncate (rxPageL->capacityCount() / 2);
     195             : 
     196             :     // Save left page.
     197           0 :     self aNodeL (rxPageL.get());
     198           0 :     eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
     199           0 :     if (eErrCode != store_E_None)
     200           0 :         return eErrCode;
     201             : 
     202             :     // Insert right page.
     203           0 :     OStorePageLink aLink (xPageR->location());
     204           0 :     xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
     205             : 
     206             :     // Save this page and leave.
     207           0 :     return rBIOS.saveObjectAt (*this, location());
     208             : }
     209             : 
     210             : /*
     211             :  * remove (down to leaf node, recursive).
     212             :  */
     213           0 : storeError OStoreBTreeNodeObject::remove (
     214             :     sal_uInt16         nIndexL,
     215             :     OStoreBTreeEntry & rEntryL,
     216             :     OStorePageBIOS &   rBIOS)
     217             : {
     218           0 :     PageHolderObject< page > xImpl (m_xPage);
     219           0 :     page & rPage = (*xImpl);
     220             : 
     221             :     // Check depth.
     222           0 :     storeError eErrCode = store_E_None;
     223           0 :     if (rPage.depth())
     224             :     {
     225             :         // Check link entry.
     226           0 :         T const aEntryL (rPage.m_pData[nIndexL]);
     227           0 :         if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL))
     228           0 :             return store_E_InvalidAccess;
     229             : 
     230             :         // Load link node.
     231           0 :         self aNodeL;
     232           0 :         eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
     233           0 :         if (eErrCode != store_E_None)
     234           0 :             return eErrCode;
     235             : 
     236             :         // Recurse: remove from link node.
     237           0 :         eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
     238           0 :         if (eErrCode != store_E_None)
     239           0 :             return eErrCode;
     240             : 
     241             :         // Check resulting link node usage.
     242           0 :         PageHolderObject< page > xPageL (aNodeL.get());
     243           0 :         if (xPageL->usageCount() == 0)
     244             :         {
     245             :             // Free empty link node.
     246           0 :             eErrCode = rBIOS.free (xPageL->location());
     247           0 :             if (eErrCode != store_E_None)
     248           0 :                 return eErrCode;
     249             : 
     250             :             // Remove index.
     251           0 :             rPage.remove (nIndexL);
     252           0 :             touch();
     253             :         }
     254             :         else
     255             :         {
     256             : 
     257             :             // Relink.
     258           0 :             rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
     259           0 :             touch();
     260           0 :         }
     261             :     }
     262             :     else
     263             :     {
     264             :         // Check leaf entry.
     265           0 :         if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
     266           0 :             return store_E_NotExists;
     267             : 
     268             :         // Save leaf entry.
     269           0 :         rEntryL = rPage.m_pData[nIndexL];
     270             : 
     271             :         // Remove leaf index.
     272           0 :         rPage.remove (nIndexL);
     273           0 :         touch();
     274             :     }
     275             : 
     276             :     // Check for modified node.
     277           0 :     if (dirty())
     278             :     {
     279             :         // Save this page.
     280           0 :         eErrCode = rBIOS.saveObjectAt (*this, location());
     281             :     }
     282             : 
     283             :     // Done.
     284           0 :     return eErrCode;
     285             : }
     286             : 
     287             : /*========================================================================
     288             :  *
     289             :  * OStoreBTreeRootObject implementation.
     290             :  *
     291             :  *======================================================================*/
     292             : /*
     293             :  * testInvariant.
     294             :  * Precond: root node page loaded.
     295             :  */
     296           0 : bool OStoreBTreeRootObject::testInvariant (char const * message)
     297             : {
     298             :     OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
     299           0 :     bool result = ((m_xPage->location() - m_xPage->size()) == 0);
     300             :     OSL_POSTCOND(result, message); (void) message;
     301           0 :     return result;
     302             : }
     303             : 
     304             : /*
     305             :  * loadOrCreate.
     306             :  */
     307           0 : storeError OStoreBTreeRootObject::loadOrCreate (
     308             :     sal_uInt32       nAddr,
     309             :     OStorePageBIOS & rBIOS)
     310             : {
     311           0 :     storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
     312           0 :     if (eErrCode != store_E_NotExists)
     313           0 :         return eErrCode;
     314             : 
     315           0 :     eErrCode = construct<page>(rBIOS.allocator());
     316           0 :     if (eErrCode != store_E_None)
     317           0 :         return eErrCode;
     318             : 
     319           0 :     eErrCode = rBIOS.allocate (*this);
     320           0 :     if (eErrCode != store_E_None)
     321           0 :         return eErrCode;
     322             : 
     323             :     // Notify caller of the creation.
     324           0 :     (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
     325           0 :     return store_E_Pending;
     326             : }
     327             : 
     328             : /*
     329             :  * change.
     330             :  */
     331           0 : storeError OStoreBTreeRootObject::change (
     332             :     PageHolderObject< page > & rxPageL,
     333             :     OStorePageBIOS &           rBIOS)
     334             : {
     335           0 :     PageHolderObject< page > xPage (m_xPage);
     336           0 :     (void) testInvariant("OStoreBTreeRootObject::change(): enter");
     337             : 
     338             :     // Save root location.
     339           0 :     sal_uInt32 const nRootAddr = xPage->location();
     340             : 
     341             :     // Construct new root.
     342           0 :     if (!rxPageL.construct (rBIOS.allocator()))
     343           0 :         return store_E_OutOfMemory;
     344             : 
     345             :     // Save this as prev root.
     346           0 :     storeError eErrCode = rBIOS.allocate (*this);
     347           0 :     if (eErrCode != store_E_None)
     348           0 :         return store_E_OutOfMemory;
     349             : 
     350             :     // Setup new root.
     351           0 :     rxPageL->depth (xPage->depth() + 1);
     352           0 :     rxPageL->m_pData[0] = xPage->m_pData[0];
     353           0 :     rxPageL->m_pData[0].m_aLink = xPage->location();
     354           0 :     rxPageL->usageCount(1);
     355             : 
     356             :     // Change root.
     357           0 :     rxPageL.swap (xPage);
     358             :     {
     359           0 :         PageHolder tmp (xPage.get());
     360           0 :         tmp.swap (m_xPage);
     361             :     }
     362             : 
     363             :     // Save this as new root and finish.
     364           0 :     eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
     365           0 :     (void) testInvariant("OStoreBTreeRootObject::change(): leave");
     366           0 :     return eErrCode;
     367             : }
     368             : 
     369             : /*
     370             :  * find_lookup (w/o split()).
     371             :  * Precond: root node page loaded.
     372             :  */
     373           0 : storeError OStoreBTreeRootObject::find_lookup (
     374             :     OStoreBTreeNodeObject & rNode,  // [out]
     375             :     sal_uInt16 &            rIndex, // [out]
     376             :     OStorePageKey const &   rKey,
     377             :     OStorePageBIOS &        rBIOS)
     378             : {
     379             :     // Init node w/ root page.
     380           0 :     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
     381             :     {
     382           0 :         PageHolder tmp (m_xPage);
     383           0 :         tmp.swap (rNode.get());
     384             :     }
     385             : 
     386             :     // Setup BTree entry.
     387           0 :     T const entry (rKey);
     388             : 
     389             :     // Check current page.
     390           0 :     PageHolderObject< page > xPage (rNode.get());
     391           0 :     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
     392             :     {
     393             :         // Find next page.
     394           0 :         page const & rPage = (*xPage);
     395           0 :         sal_uInt16 const i = rPage.find(entry);
     396           0 :         sal_uInt16 const n = rPage.usageCount();
     397           0 :         if (!(i < n))
     398             :         {
     399             :             // Path to entry not exists (Must not happen(?)).
     400           0 :             return store_E_NotExists;
     401             :         }
     402             : 
     403             :         // Check address.
     404           0 :         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
     405           0 :         if (nAddr == STORE_PAGE_NULL)
     406             :         {
     407             :             // Path to entry not exists (Must not happen(?)).
     408           0 :             return store_E_NotExists;
     409             :         }
     410             : 
     411             :         // Load next page.
     412           0 :         storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
     413           0 :         if (eErrCode != store_E_None)
     414           0 :             return eErrCode;
     415             :     }
     416             : 
     417             :     // Find index.
     418           0 :     page const & rPage = (*xPage);
     419           0 :     rIndex = rPage.find(entry);
     420           0 :     if (!(rIndex < rPage.usageCount()))
     421           0 :         return store_E_NotExists;
     422             : 
     423             :     // Compare entry.
     424           0 :     T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
     425             :     OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
     426           0 :     if (eResult == T::COMPARE_LESS)
     427           0 :         return store_E_Unknown;
     428             : 
     429             :     // Greater or Equal.
     430           0 :     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
     431           0 :     return store_E_None;
     432             : }
     433             : 
     434             : /*
     435             :  * find_insert (possibly with split()).
     436             :  * Precond: root node page loaded.
     437             :  */
     438           0 : storeError OStoreBTreeRootObject::find_insert (
     439             :     OStoreBTreeNodeObject & rNode,  // [out]
     440             :     sal_uInt16 &            rIndex, // [out]
     441             :     OStorePageKey const &   rKey,
     442             :     OStorePageBIOS &        rBIOS)
     443             : {
     444           0 :     (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");
     445             : 
     446             :     // Check for RootNode split.
     447           0 :     PageHolderObject< page > xRoot (m_xPage);
     448           0 :     if (xRoot->querySplit())
     449             :     {
     450           0 :         PageHolderObject< page > xPageL;
     451             : 
     452             :         // Change root.
     453           0 :         storeError eErrCode = change (xPageL, rBIOS);
     454           0 :         if (eErrCode != store_E_None)
     455           0 :             return eErrCode;
     456             : 
     457             :         // Split left page (prev root).
     458           0 :         eErrCode = split (0, xPageL, rBIOS);
     459           0 :         if (eErrCode != store_E_None)
     460           0 :             return eErrCode;
     461             :     }
     462             : 
     463             :     // Init node w/ root page.
     464             :     {
     465           0 :         PageHolder tmp (m_xPage);
     466           0 :         tmp.swap (rNode.get());
     467             :     }
     468             : 
     469             :     // Setup BTree entry.
     470           0 :     T const entry (rKey);
     471             : 
     472             :     // Check current Page.
     473           0 :     PageHolderObject< page > xPage (rNode.get());
     474           0 :     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
     475             :     {
     476             :         // Find next page.
     477           0 :         page const & rPage = (*xPage);
     478           0 :         sal_uInt16 const i = rPage.find (entry);
     479           0 :         sal_uInt16 const n = rPage.usageCount();
     480           0 :         if (!(i < n))
     481             :         {
     482             :             // Path to entry not exists (Must not happen(?)).
     483           0 :             return store_E_NotExists;
     484             :         }
     485             : 
     486             :         // Check address.
     487           0 :         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
     488           0 :         if (nAddr == STORE_PAGE_NULL)
     489             :         {
     490             :             // Path to entry not exists (Must not happen(?)).
     491           0 :             return store_E_NotExists;
     492             :         }
     493             : 
     494             :         // Load next page.
     495           0 :         OStoreBTreeNodeObject aNext;
     496           0 :         storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
     497           0 :         if (eErrCode != store_E_None)
     498           0 :             return eErrCode;
     499             : 
     500             :         // Check for next node split.
     501           0 :         PageHolderObject< page > xNext (aNext.get());
     502           0 :         if (xNext->querySplit())
     503             :         {
     504             :             // Split next node.
     505           0 :             eErrCode = rNode.split (i, xNext, rBIOS);
     506           0 :             if (eErrCode != store_E_None)
     507           0 :                 return eErrCode;
     508             : 
     509             :             // Restart.
     510           0 :             continue;
     511             :         }
     512             : 
     513             :         // Let next page be current.
     514           0 :         PageHolder tmp (aNext.get());
     515           0 :         tmp.swap (rNode.get());
     516           0 :     }
     517             : 
     518             :     // Find index.
     519           0 :     page const & rPage = (*xPage);
     520           0 :     rIndex = rPage.find(entry);
     521           0 :     if (rIndex < rPage.usageCount())
     522             :     {
     523             :         // Compare entry.
     524           0 :         T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
     525             :         OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
     526           0 :         if (result == T::COMPARE_LESS)
     527           0 :             return store_E_Unknown;
     528             : 
     529           0 :         if (result == T::COMPARE_EQUAL)
     530           0 :             return store_E_AlreadyExists;
     531             :     }
     532             : 
     533             :     // Greater or not (yet) existing.
     534           0 :     (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
     535           0 :     return store_E_None;
     536             : }
     537             : 
     538             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10