LCOV - code coverage report
Current view: top level - libreoffice/store/source - stortree.hxx (source / functions) Hit Total Coverage
Test: libreoffice_filtered.info Lines: 56 57 98.2 %
Date: 2012-12-27 Functions: 18 20 90.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             : #ifndef _STORE_STORTREE_HXX
      21             : #define _STORE_STORTREE_HXX
      22             : 
      23             : #include "sal/types.h"
      24             : 
      25             : #include "store/types.h"
      26             : 
      27             : #include "storbase.hxx"
      28             : 
      29             : namespace store
      30             : {
      31             : 
      32             : class OStorePageBIOS;
      33             : 
      34             : /*========================================================================
      35             :  *
      36             :  * OStoreBTreeEntry.
      37             :  *
      38             :  *======================================================================*/
      39             : struct OStoreBTreeEntry
      40             : {
      41             :     typedef OStorePageKey  K;
      42             :     typedef OStorePageLink L;
      43             : 
      44             :     /** Representation.
      45             :     */
      46             :     K          m_aKey;
      47             :     L          m_aLink;
      48             :     sal_uInt32 m_nAttrib;
      49             : 
      50             :     /** Construction.
      51             :     */
      52     2240555 :     explicit OStoreBTreeEntry (
      53             :         K const &  rKey    = K(),
      54             :         L const &  rLink   = L(),
      55             :         sal_uInt32 nAttrib = 0)
      56             :         : m_aKey    (rKey),
      57             :           m_aLink   (rLink),
      58     2240555 :           m_nAttrib (store::htonl(nAttrib))
      59     2240555 :     {}
      60             : 
      61     1597574 :     OStoreBTreeEntry (const OStoreBTreeEntry & rhs)
      62             :         : m_aKey    (rhs.m_aKey),
      63             :           m_aLink   (rhs.m_aLink),
      64     1597574 :           m_nAttrib (rhs.m_nAttrib)
      65     1597574 :     {}
      66             : 
      67      301789 :     OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs)
      68             :     {
      69      301789 :         m_aKey    = rhs.m_aKey;
      70      301789 :         m_aLink   = rhs.m_aLink;
      71      301789 :         m_nAttrib = rhs.m_nAttrib;
      72      301789 :         return *this;
      73             :     }
      74             : 
      75             :     /** Comparison.
      76             :     */
      77             :     enum CompareResult
      78             :     {
      79             :         COMPARE_LESS    = -1,
      80             :         COMPARE_EQUAL   =  0,
      81             :         COMPARE_GREATER =  1
      82             :     };
      83             : 
      84     2145013 :     CompareResult compare (const OStoreBTreeEntry& rOther) const
      85             :     {
      86     2145013 :         if (m_aKey < rOther.m_aKey)
      87      468272 :             return COMPARE_LESS;
      88     1676741 :         else if (m_aKey == rOther.m_aKey)
      89      895854 :             return COMPARE_EQUAL;
      90             :         else
      91      780887 :             return COMPARE_GREATER;
      92             :     }
      93             : };
      94             : 
      95             : /*========================================================================
      96             :  *
      97             :  * OStoreBTreeNodeData.
      98             :  *
      99             :  *======================================================================*/
     100             : #define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322)
     101             : 
     102             : struct OStoreBTreeNodeData : public store::OStorePageData
     103             : {
     104             :     typedef OStorePageData      base;
     105             :     typedef OStoreBTreeNodeData self;
     106             : 
     107             :     typedef OStorePageGuard     G;
     108             :     typedef OStoreBTreeEntry    T;
     109             : 
     110             :     /** Representation.
     111             :      */
     112             :     G m_aGuard;
     113             :     T m_pData[1];
     114             : 
     115             :     /** type.
     116             :      */
     117             :     static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE;
     118             : 
     119             :     /** theSize.
     120             :      */
     121             :     static const size_t     theSize     = sizeof(G);
     122             :     static const sal_uInt16 thePageSize = base::theSize + self::theSize;
     123             :     STORE_STATIC_ASSERT(STORE_MINIMUM_PAGESIZE >= self::thePageSize);
     124             : 
     125             :     /** capacity.
     126             :     */
     127     3059101 :     sal_uInt16 capacity (void) const
     128             :     {
     129     3059101 :         return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
     130             :     }
     131             : 
     132             :     /** capacityCount (must be even).
     133             :     */
     134     2951136 :     sal_uInt16 capacityCount (void) const
     135             :     {
     136     2951136 :         return sal_uInt16(capacity() / sizeof(T));
     137             :     }
     138             : 
     139             :     /** usage.
     140             :     */
     141     6186930 :     sal_uInt16 usage (void) const
     142             :     {
     143     6186930 :         return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
     144             :     }
     145             : 
     146             :     /** usageCount.
     147             :     */
     148     6186930 :     sal_uInt16 usageCount (void) const
     149             :     {
     150     6186930 :         return sal_uInt16(usage() / sizeof(T));
     151             :     }
     152       82750 :     void usageCount (sal_uInt16 nCount)
     153             :     {
     154       82750 :         size_t const nBytes = self::thePageSize + nCount * sizeof(T);
     155       82750 :         base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
     156       82750 :     }
     157             : 
     158             :     /** Construction.
     159             :     */
     160             :     explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize);
     161             : 
     162             :     /** guard (external representation).
     163             :     */
     164       93168 :     void guard()
     165             :     {
     166       93168 :         sal_uInt32 nCRC32 = 0;
     167       93168 :         nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
     168       93168 :         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
     169       93168 :         m_aGuard.m_nCRC32 = store::htonl(nCRC32);
     170       93168 :     }
     171             : 
     172             :     /** verify (external representation).
     173             :     */
     174       14797 :     storeError verify() const
     175             :     {
     176       14797 :         sal_uInt32 nCRC32 = 0;
     177       14797 :         nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
     178       14797 :         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
     179       14797 :         if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
     180           0 :             return store_E_InvalidChecksum;
     181             :         else
     182       14797 :             return store_E_None;
     183             :     }
     184             : 
     185             :     /** depth.
     186             :     */
     187     2993845 :     sal_uInt32 depth (void) const
     188             :     {
     189     2993845 :         return store::ntohl(self::m_aGuard.m_nMagic);
     190             :     }
     191        1209 :     void depth (sal_uInt32 nDepth)
     192             :     {
     193        1209 :         self::m_aGuard.m_nMagic = store::htonl(nDepth);
     194        1209 :     }
     195             : 
     196             :     /** queryMerge.
     197             :     */
     198             :     sal_Bool queryMerge (const self &rPageR) const
     199             :     {
     200             :         return ((usageCount() + rPageR.usageCount()) <= capacityCount());
     201             :     }
     202             : 
     203             :     /** querySplit.
     204             :     */
     205      121304 :     sal_Bool querySplit (void) const
     206             :     {
     207      121304 :         return (!(usageCount() < capacityCount()));
     208             :     }
     209             : 
     210             :     /** Operation.
     211             :     */
     212             :     sal_uInt16 find   (const T& t) const;
     213             :     void       insert (sal_uInt16 i, const T& t);
     214             :     void       remove (sal_uInt16 i);
     215             : 
     216             :     /** split (left half copied from right half of left page).
     217             :     */
     218             :     void split (const self& rPageL);
     219             : 
     220             :     /** truncate (to n elements).
     221             :     */
     222             :     void truncate (sal_uInt16 n);
     223             : };
     224             : 
     225             : /*========================================================================
     226             :  *
     227             :  * OStoreBTreeNodeObject.
     228             :  *
     229             :  *======================================================================*/
     230     1285198 : class OStoreBTreeNodeObject : public store::OStorePageObject
     231             : {
     232             :     typedef OStorePageObject      base;
     233             :     typedef OStoreBTreeNodeObject self;
     234             :     typedef OStoreBTreeNodeData   page;
     235             : 
     236             :     typedef OStoreBTreeEntry      T;
     237             : 
     238             : public:
     239             :     /** Construction.
     240             :     */
     241     1285461 :     explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder())
     242     1285461 :         : OStorePageObject (rxPage)
     243     1285461 :     {}
     244             : 
     245             :     /** External representation.
     246             :     */
     247             :     virtual storeError guard  (sal_uInt32 nAddr);
     248             :     virtual storeError verify (sal_uInt32 nAddr) const;
     249             : 
     250             :     /** split.
     251             :      *
     252             :      *  @param rxPageL [inout] left child to be split
     253             :      */
     254             :     storeError split (
     255             :         sal_uInt16                 nIndexL,
     256             :         PageHolderObject< page > & rxPageL,
     257             :         OStorePageBIOS &           rBIOS);
     258             : 
     259             :     /** remove (down to leaf node, recursive).
     260             :     */
     261             :     storeError remove (
     262             :         sal_uInt16         nIndexL,
     263             :         OStoreBTreeEntry & rEntryL,
     264             :         OStorePageBIOS &   rBIOS);
     265             : };
     266             : 
     267             : /*========================================================================
     268             :  *
     269             :  * OStoreBTreeRootObject.
     270             :  *
     271             :  *======================================================================*/
     272       10461 : class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject
     273             : {
     274             :     typedef OStoreBTreeNodeObject base;
     275             :     typedef OStoreBTreeNodeData   page;
     276             : 
     277             :     typedef OStoreBTreeEntry      T;
     278             : 
     279             : public:
     280             :     /** Construction.
     281             :      */
     282       10724 :     explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder())
     283       10724 :         : OStoreBTreeNodeObject (rxPage)
     284       10724 :     {}
     285             : 
     286             :     storeError loadOrCreate (
     287             :         sal_uInt32       nAddr,
     288             :         OStorePageBIOS & rBIOS);
     289             : 
     290             :     /** find_lookup (w/o split()).
     291             :      *  Precond: root node page loaded.
     292             :      */
     293             :     storeError find_lookup (
     294             :         OStoreBTreeNodeObject & rNode,  // [out]
     295             :         sal_uInt16 &            rIndex, // [out]
     296             :         OStorePageKey const &   rKey,
     297             :         OStorePageBIOS &        rBIOS);
     298             : 
     299             :     /** find_insert (possibly with split()).
     300             :      *  Precond: root node page loaded.
     301             :      */
     302             :     storeError find_insert (
     303             :         OStoreBTreeNodeObject & rNode,
     304             :         sal_uInt16 &            rIndex,
     305             :         OStorePageKey const &   rKey,
     306             :         OStorePageBIOS &        rBIOS);
     307             : 
     308             : private:
     309             :     /** testInvariant.
     310             :      *  Precond: root node page loaded.
     311             :      */
     312             :     bool testInvariant (char const * message);
     313             : 
     314             :     /** change (Root).
     315             :      *
     316             :      *  @param rxPageL [out] prev. root (needs split)
     317             :      */
     318             :     storeError change (
     319             :         PageHolderObject< page > & rxPageL,
     320             :         OStorePageBIOS &           rBIOS);
     321             : };
     322             : 
     323             : /*========================================================================
     324             :  *
     325             :  * The End.
     326             :  *
     327             :  *======================================================================*/
     328             : 
     329             : } // namespace store
     330             : 
     331             : #endif /* !_STORE_STORTREE_HXX */
     332             : 
     333             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10