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

Generated by: LCOV version 1.10