store/source/stortree.hxx

   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/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     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           m_nAttrib (store::htonl(nAttrib))
  62     {}
  63
  64     OStoreBTreeEntry (const OStoreBTreeEntry & rhs)
  65         : m_aKey    (rhs.m_aKey),
  66           m_aLink   (rhs.m_aLink),
  67           m_nAttrib (rhs.m_nAttrib)
  68     {}
  69
  70     OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs)
  71     {
  72         m_aKey    = rhs.m_aKey;
  73         m_aLink   = rhs.m_aLink;
  74         m_nAttrib = rhs.m_nAttrib;
  75         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     CompareResult compare (const OStoreBTreeEntry& rOther) const
  88     {
  89         if (m_aKey < rOther.m_aKey)
  90             return COMPARE_LESS;
  91         else if (m_aKey == rOther.m_aKey)
  92             return COMPARE_EQUAL;
  93         else
  94             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     sal_uInt16 capacity (void) const
 131     {
 132         return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
 133     }
 134
 135     /** capacityCount (must be even).
 136     */
 137     sal_uInt16 capacityCount (void) const
 138     {
 139         return sal_uInt16(capacity() / sizeof(T));
 140     }
 141
 142     /** usage.
 143     */
 144     sal_uInt16 usage (void) const
 145     {
 146         return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
 147     }
 148
 149     /** usageCount.
 150     */
 151     sal_uInt16 usageCount (void) const
 152     {
 153         return sal_uInt16(usage() / sizeof(T));
 154     }
 155     void usageCount (sal_uInt16 nCount)
 156     {
 157         size_t const nBytes = self::thePageSize + nCount * sizeof(T);
 158         base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
 159     }
 160
 161     /** Construction.
 162     */
 163     explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize);
 164
 165     /** guard (external representation).
 166     */
 167     void guard()
 168     {
 169         sal_uInt32 nCRC32 = 0;
 170         nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
 171         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
 172         m_aGuard.m_nCRC32 = store::htonl(nCRC32);
 173     }
 174
 175     /** verify (external representation).
 176     */
 177     storeError verify() const
 178     {
 179         sal_uInt32 nCRC32 = 0;
 180         nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
 181         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
 182         if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
 183             return store_E_InvalidChecksum;
 184         else
 185             return store_E_None;
 186     }
 187
 188     /** depth.
 189     */
 190     sal_uInt32 depth (void) const
 191     {
 192         return store::ntohl(self::m_aGuard.m_nMagic);
 193     }
 194     void depth (sal_uInt32 nDepth)
 195     {
 196         self::m_aGuard.m_nMagic = store::htonl(nDepth);
 197     }
 198
 199     /** queryMerge.
 200     */
 201     sal_Bool queryMerge (const self &rPageR) const
 202     {
 203         return ((usageCount() + rPageR.usageCount()) <= capacityCount());
 204     }
 205
 206     /** querySplit.
 207     */
 208     sal_Bool querySplit (void) const
 209     {
 210         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 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     explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder())
 245         : OStorePageObject (rxPage)
 246     {}
 247
 248     /** External representation.
 249     */
 250     virtual storeError guard  (sal_uInt32 nAddr);
 251     virtual storeError verify (sal_uInt32 nAddr) const;
 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 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     explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder())
 286         : OStoreBTreeNodeObject (rxPage)
 287     {}
 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     bool 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 /* !_STORE_STORTREE_HXX */
 335
 336 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */