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