store/source/stortree.hxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*************************************************************************
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * Copyright 2000, 2010 Oracle and/or its affiliates.
   7  *
   8  * OpenOffice.org - a multi-platform office productivity suite
   9  *
  10  * This file is part of OpenOffice.org.
  11  *
  12  * OpenOffice.org is free software: you can redistribute it and/or modify
  13  * it under the terms of the GNU Lesser General Public License version 3
  14  * only, as published by the Free Software Foundation.
  15  *
  16  * OpenOffice.org is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  * GNU Lesser General Public License version 3 for more details
  20  * (a copy is included in the LICENSE file that accompanied this code).
  21  *
  22  * You should have received a copy of the GNU Lesser General Public License
  23  * version 3 along with OpenOffice.org.  If not, see
  24  * <http://www.openoffice.org/license.html>
  25  * for a copy of the LGPLv3 License.
  26  *
  27  ************************************************************************/
  28
  29 #ifndef _STORE_STORTREE_HXX
  30 #define _STORE_STORTREE_HXX
  31
  32 #include "sal/types.h"
  33
  34 #include "store/types.h"
  35
  36 #include "storbase.hxx"
  37
  38 namespace store
  39 {
  40
  41 class OStorePageBIOS;
  42
  43 /*========================================================================
  44  *
  45  * OStoreBTreeEntry.
  46  *
  47  *======================================================================*/
  48 struct OStoreBTreeEntry
  49 {
  50     typedef OStorePageKey  K;
  51     typedef OStorePageLink L;
  52
  53     /** Representation.
  54     */
  55     K          m_aKey;
  56     L          m_aLink;
  57     sal_uInt32 m_nAttrib;
  58
  59     /** Construction.
  60     */
  61     explicit OStoreBTreeEntry (
  62         K const &  rKey    = K(),
  63         L const &  rLink   = L(),
  64         sal_uInt32 nAttrib = 0)
  65         : m_aKey    (rKey),
  66           m_aLink   (rLink),
  67           m_nAttrib (store::htonl(nAttrib))
  68     {}
  69
  70     OStoreBTreeEntry (const OStoreBTreeEntry & rhs)
  71         : m_aKey    (rhs.m_aKey),
  72           m_aLink   (rhs.m_aLink),
  73           m_nAttrib (rhs.m_nAttrib)
  74     {}
  75
  76     OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs)
  77     {
  78         m_aKey    = rhs.m_aKey;
  79         m_aLink   = rhs.m_aLink;
  80         m_nAttrib = rhs.m_nAttrib;
  81         return *this;
  82     }
  83
  84     /** Comparison.
  85     */
  86     enum CompareResult
  87     {
  88         COMPARE_LESS    = -1,
  89         COMPARE_EQUAL   =  0,
  90         COMPARE_GREATER =  1
  91     };
  92
  93     CompareResult compare (const OStoreBTreeEntry& rOther) const
  94     {
  95         if (m_aKey < rOther.m_aKey)
  96             return COMPARE_LESS;
  97         else if (m_aKey == rOther.m_aKey)
  98             return COMPARE_EQUAL;
  99         else
 100             return COMPARE_GREATER;
 101     }
 102 };
 103
 104 /*========================================================================
 105  *
 106  * OStoreBTreeNodeData.
 107  *
 108  *======================================================================*/
 109 #define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322)
 110
 111 struct OStoreBTreeNodeData : public store::OStorePageData
 112 {
 113     typedef OStorePageData      base;
 114     typedef OStoreBTreeNodeData self;
 115
 116     typedef OStorePageGuard     G;
 117     typedef OStoreBTreeEntry    T;
 118
 119     /** Representation.
 120      */
 121     G m_aGuard;
 122     T m_pData[1];
 123
 124     /** type.
 125      */
 126     static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE;
 127
 128     /** theSize.
 129      */
 130     static const size_t     theSize     = sizeof(G);
 131     static const sal_uInt16 thePageSize = base::theSize + self::theSize;
 132     STORE_STATIC_ASSERT(STORE_MINIMUM_PAGESIZE >= self::thePageSize);
 133
 134     /** capacity.
 135     */
 136     sal_uInt16 capacity (void) const
 137     {
 138         return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
 139     }
 140
 141     /** capacityCount (must be even).
 142     */
 143     sal_uInt16 capacityCount (void) const
 144     {
 145         return sal_uInt16(capacity() / sizeof(T));
 146     }
 147
 148     /** usage.
 149     */
 150     sal_uInt16 usage (void) const
 151     {
 152         return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
 153     }
 154
 155     /** usageCount.
 156     */
 157     sal_uInt16 usageCount (void) const
 158     {
 159         return sal_uInt16(usage() / sizeof(T));
 160     }
 161     void usageCount (sal_uInt16 nCount)
 162     {
 163         size_t const nBytes = self::thePageSize + nCount * sizeof(T);
 164         base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
 165     }
 166
 167     /** Construction.
 168     */
 169     explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize);
 170
 171     /** guard (external representation).
 172     */
 173     void guard()
 174     {
 175         sal_uInt32 nCRC32 = 0;
 176         nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
 177         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
 178         m_aGuard.m_nCRC32 = store::htonl(nCRC32);
 179     }
 180
 181     /** verify (external representation).
 182     */
 183     storeError verify() const
 184     {
 185         sal_uInt32 nCRC32 = 0;
 186         nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
 187         nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
 188         if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
 189             return store_E_InvalidChecksum;
 190         else
 191             return store_E_None;
 192     }
 193
 194     /** depth.
 195     */
 196     sal_uInt32 depth (void) const
 197     {
 198         return store::ntohl(self::m_aGuard.m_nMagic);
 199     }
 200     void depth (sal_uInt32 nDepth)
 201     {
 202         self::m_aGuard.m_nMagic = store::htonl(nDepth);
 203     }
 204
 205     /** queryMerge.
 206     */
 207     sal_Bool queryMerge (const self &rPageR) const
 208     {
 209         return ((usageCount() + rPageR.usageCount()) <= capacityCount());
 210     }
 211
 212     /** querySplit.
 213     */
 214     sal_Bool querySplit (void) const
 215     {
 216         return (!(usageCount() < capacityCount()));
 217     }
 218
 219     /** Operation.
 220     */
 221     sal_uInt16 find   (const T& t) const;
 222     void       insert (sal_uInt16 i, const T& t);
 223     void       remove (sal_uInt16 i);
 224
 225     /** split (left half copied from right half of left page).
 226     */
 227     void split (const self& rPageL);
 228
 229     /** truncate (to n elements).
 230     */
 231     void truncate (sal_uInt16 n);
 232 };
 233
 234 /*========================================================================
 235  *
 236  * OStoreBTreeNodeObject.
 237  *
 238  *======================================================================*/
 239 class OStoreBTreeNodeObject : public store::OStorePageObject
 240 {
 241     typedef OStorePageObject      base;
 242     typedef OStoreBTreeNodeObject self;
 243     typedef OStoreBTreeNodeData   page;
 244
 245     typedef OStoreBTreeEntry      T;
 246
 247 public:
 248     /** Construction.
 249     */
 250     explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder())
 251         : OStorePageObject (rxPage)
 252     {}
 253
 254     /** External representation.
 255     */
 256     virtual storeError guard  (sal_uInt32 nAddr);
 257     virtual storeError verify (sal_uInt32 nAddr) const;
 258
 259     /** split.
 260      *
 261      *  @param rxPageL [inout] left child to be split
 262      */
 263     storeError split (
 264         sal_uInt16                 nIndexL,
 265         PageHolderObject< page > & rxPageL,
 266         OStorePageBIOS &           rBIOS);
 267
 268     /** remove (down to leaf node, recursive).
 269     */
 270     storeError remove (
 271         sal_uInt16         nIndexL,
 272         OStoreBTreeEntry & rEntryL,
 273         OStorePageBIOS &   rBIOS);
 274 };
 275
 276 /*========================================================================
 277  *
 278  * OStoreBTreeRootObject.
 279  *
 280  *======================================================================*/
 281 class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject
 282 {
 283     typedef OStoreBTreeNodeObject base;
 284     typedef OStoreBTreeNodeData   page;
 285
 286     typedef OStoreBTreeEntry      T;
 287
 288 public:
 289     /** Construction.
 290      */
 291     explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder())
 292         : OStoreBTreeNodeObject (rxPage)
 293     {}
 294
 295     storeError loadOrCreate (
 296         sal_uInt32       nAddr,
 297         OStorePageBIOS & rBIOS);
 298
 299     /** find_lookup (w/o split()).
 300      *  Precond: root node page loaded.
 301      */
 302     storeError find_lookup (
 303         OStoreBTreeNodeObject & rNode,  // [out]
 304         sal_uInt16 &            rIndex, // [out]
 305         OStorePageKey const &   rKey,
 306         OStorePageBIOS &        rBIOS);
 307
 308     /** find_insert (possibly with split()).
 309      *  Precond: root node page loaded.
 310      */
 311     storeError find_insert (
 312         OStoreBTreeNodeObject & rNode,
 313         sal_uInt16 &            rIndex,
 314         OStorePageKey const &   rKey,
 315         OStorePageBIOS &        rBIOS);
 316
 317 private:
 318     /** testInvariant.
 319      *  Precond: root node page loaded.
 320      */
 321     bool testInvariant (char const * message);
 322
 323     /** change (Root).
 324      *
 325      *  @param rxPageL [out] prev. root (needs split)
 326      */
 327     storeError change (
 328         PageHolderObject< page > & rxPageL,
 329         OStorePageBIOS &           rBIOS);
 330 };
 331
 332 /*========================================================================
 333  *
 334  * The End.
 335  *
 336  *======================================================================*/
 337
 338 } // namespace store
 339
 340 #endif /* !_STORE_STORTREE_HXX */
 341
 342 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */