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 #pragma once
  21
  22 #include <sal/config.h>
  23
  24 #include <memory>
  25
  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 struct OStoreBTreeEntry
  38 {
  39     typedef OStorePageKey  K;
  40     typedef OStorePageLink L;
  41
  42     K          m_aKey;
  43     L          m_aLink;
  44     sal_uInt32 m_nAttrib;
  45
  46     explicit OStoreBTreeEntry (
  47         K const &  rKey    = K(),
  48         L const &  rLink   = L())
  49         : m_aKey    (rKey),
  50           m_aLink   (rLink),
  51           m_nAttrib (store::htonl(0))
  52     {}
  53
  54     enum CompareResult
  55     {
  56         COMPARE_LESS    = -1,
  57         COMPARE_EQUAL   =  0,
  58         COMPARE_GREATER =  1
  59     };
  60
  61     CompareResult compare (const OStoreBTreeEntry& rOther) const
  62     {
  63         if (m_aKey < rOther.m_aKey)
  64             return COMPARE_LESS;
  65         else if (m_aKey == rOther.m_aKey)
  66             return COMPARE_EQUAL;
  67         else
  68             return COMPARE_GREATER;
  69     }
  70 };
  71
  72 #define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322)
  73
  74 struct OStoreBTreeNodeData : public store::PageData
  75 {
  76     typedef PageData      base;
  77     typedef OStoreBTreeNodeData self;
  78
  79     typedef OStorePageGuard     G;
  80     typedef OStoreBTreeEntry    T;
  81
  82     G m_aGuard;
  83     T m_pData[1];
  84
  85     static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE;
  86
  87     static const size_t     theSize     = sizeof(G);
  88     static const sal_uInt16 thePageSize = base::theSize + self::theSize;
  89     static_assert(STORE_MINIMUM_PAGESIZE >= self::thePageSize, "got to be at least equal in size");
  90
  91     sal_uInt16 capacity() const
  92     {
  93         return static_cast<sal_uInt16>(store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
  94     }
  95
  96     /** capacityCount (must be even).
  97     */
  98     sal_uInt16 capacityCount() const
  99     {
 100         return sal_uInt16(capacity() / sizeof(T));
 101     }
 102
 103     sal_uInt16 usage() const
 104     {
 105         return static_cast<sal_uInt16>(store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
 106     }
 107
 108     sal_uInt16 usageCount() const
 109     {
 110         return sal_uInt16(usage() / sizeof(T));
 111     }
 112     void usageCount (sal_uInt16 nCount)
 113     {
 114         size_t const nBytes = self::thePageSize + nCount * sizeof(T);
 115         base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
 116     }
 117
 118     explicit OStoreBTreeNodeData (sal_uInt16 nPageSize);
 119
 120     void guard()
 121     {
 122         sal_uInt32 nCRC32 = rtl_crc32 (0, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
 123         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
 124         m_aGuard.m_nCRC32 = store::htonl(nCRC32);
 125     }
 126
 127     storeError verify() const
 128     {
 129         sal_uInt32 nCRC32 = rtl_crc32 (0, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
 130         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
 131         if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
 132             return store_E_InvalidChecksum;
 133         else
 134             return store_E_None;
 135     }
 136
 137     sal_uInt32 depth() const
 138     {
 139         return store::ntohl(self::m_aGuard.m_nMagic);
 140     }
 141     void depth (sal_uInt32 nDepth)
 142     {
 143         self::m_aGuard.m_nMagic = store::htonl(nDepth);
 144     }
 145
 146     bool querySplit() const
 147     {
 148         return usageCount() >= capacityCount();
 149     }
 150
 151     sal_uInt16 find   (const T& t) const;
 152     void       insert (sal_uInt16 i, const T& t);
 153     void       remove (sal_uInt16 i);
 154
 155     /** split (left half copied from right half of left page).
 156     */
 157     void split (const self& rPageL);
 158
 159     /** truncate (to n elements).
 160     */
 161     void truncate (sal_uInt16 n);
 162 };
 163
 164 class OStoreBTreeNodeObject : public store::OStorePageObject
 165 {
 166     typedef OStorePageObject      base;
 167     typedef OStoreBTreeNodeObject self;
 168     typedef OStoreBTreeNodeData   page;
 169
 170     typedef OStoreBTreeEntry      T;
 171
 172 public:
 173     explicit OStoreBTreeNodeObject (std::shared_ptr<PageData> const & rxPage = std::shared_ptr<PageData>())
 174         : OStorePageObject (rxPage)
 175     {}
 176
 177     virtual storeError guard  (sal_uInt32 nAddr) override;
 178     virtual storeError verify (sal_uInt32 nAddr) const override;
 179
 180     /** split.
 181      *
 182      *  @param rxPageL [inout] left child to be split
 183      */
 184     storeError split (
 185         sal_uInt16                 nIndexL,
 186         PageHolderObject< page > & rxPageL,
 187         OStorePageBIOS &           rBIOS);
 188
 189     /** remove (down to leaf node, recursive).
 190     */
 191     storeError remove (
 192         sal_uInt16         nIndexL,
 193         OStoreBTreeEntry & rEntryL,
 194         OStorePageBIOS &   rBIOS);
 195 };
 196
 197 class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject
 198 {
 199     typedef OStoreBTreeNodeObject base;
 200     typedef OStoreBTreeNodeData   page;
 201
 202     typedef OStoreBTreeEntry      T;
 203
 204 public:
 205     explicit OStoreBTreeRootObject (std::shared_ptr<PageData> const & rxPage = std::shared_ptr<PageData>())
 206         : OStoreBTreeNodeObject (rxPage)
 207     {}
 208
 209     storeError loadOrCreate (
 210         sal_uInt32       nAddr,
 211         OStorePageBIOS & rBIOS);
 212
 213     /** find_lookup (w/o split()).
 214      *  Precond: root node page loaded.
 215      */
 216     storeError find_lookup (
 217         OStoreBTreeNodeObject & rNode,  // [out]
 218         sal_uInt16 &            rIndex, // [out]
 219         OStorePageKey const &   rKey,
 220         OStorePageBIOS &        rBIOS) const;
 221
 222     /** find_insert (possibly with split()).
 223      *  Precond: root node page loaded.
 224      */
 225     storeError find_insert (
 226         OStoreBTreeNodeObject & rNode,
 227         sal_uInt16 &            rIndex,
 228         OStorePageKey const &   rKey,
 229         OStorePageBIOS &        rBIOS);
 230
 231 private:
 232     /** testInvariant.
 233      *  Precond: root node page loaded.
 234      */
 235     void testInvariant (char const * message) const;
 236
 237     /** change (Root).
 238      *
 239      *  @param rxPageL [out] prev. root (needs split)
 240      */
 241     storeError change (
 242         PageHolderObject< page > & rxPageL,
 243         OStorePageBIOS &           rBIOS);
 244 };
 245
 246 } // namespace store
 247
 248 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */