store/source/stortree.hxx

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