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

Generated by: LCOV version 1.10