store/source/stortree.cxx

   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
  30 #include "stortree.hxx"
  31
  32 #include "sal/types.h"
  33 #include "osl/diagnose.h"
  34
  35 #include "store/types.h"
  36
  37 #include "storbase.hxx"
  38 #include "storbios.hxx"
  39
  40 using namespace store;
  41
  42 /*========================================================================
  43  *
  44  * OStoreBTreeNodeData implementation.
  45  *
  46  *======================================================================*/
  47 /*
  48  * OStoreBTreeNodeData.
  49  */
  50 OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
  51     : OStorePageData (nPageSize)
  52 {
  53     base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
  54     base::m_aDescr.m_nUsed  = store::htons(self::thePageSize); // usageCount(0)
  55     self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
  56
  57     sal_uInt16 const n = capacityCount();
  58     T const          t;
  59
  60     for (sal_uInt16 i = 1; i < n; i++)
  61         m_pData[i] = t;
  62 }
  63
  64 /*
  65  * find.
  66  */
  67 sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
  68 {
  69     register sal_Int32 l = 0;
  70     register sal_Int32 r = usageCount() - 1;
  71
  72     while (l < r)
  73     {
  74         register sal_Int32 const m = ((l + r) >> 1);
  75
  76         if (t.m_aKey == m_pData[m].m_aKey)
  77             return ((sal_uInt16)(m));
  78         if (t.m_aKey < m_pData[m].m_aKey)
  79             r = m - 1;
  80         else
  81             l = m + 1;
  82     }
  83
  84     sal_uInt16 const k = ((sal_uInt16)(r));
  85     if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
  86         return(k - 1);
  87     else
  88         return(k);
  89 }
  90
  91 /*
  92  * insert.
  93  */
  94 void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
  95 {
  96     sal_uInt16 const n = usageCount();
  97     sal_uInt16 const m = capacityCount();
  98     if ((n < m) && (i < m))
  99     {
 100         // shift right.
 101         memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
 102
 103         // insert.
 104         m_pData[i] = t;
 105         usageCount (n + 1);
 106     }
 107 }
 108
 109 /*
 110  * remove.
 111  */
 112 void OStoreBTreeNodeData::remove (sal_uInt16 i)
 113 {
 114     sal_uInt16 const n = usageCount();
 115     if (i < n)
 116     {
 117         // shift left.
 118         memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));
 119
 120         // truncate.
 121         m_pData[n - 1] = T();
 122         usageCount (n - 1);
 123     }
 124 }
 125
 126 /*
 127  * split (left half copied from right half of left page).
 128  */
 129 void OStoreBTreeNodeData::split (const self& rPageL)
 130 {
 131     sal_uInt16 const h = capacityCount() / 2;
 132     memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
 133     truncate (h);
 134 }
 135
 136 /*
 137  * truncate.
 138  */
 139 void OStoreBTreeNodeData::truncate (sal_uInt16 n)
 140 {
 141     sal_uInt16 const m = capacityCount();
 142     T const          t;
 143
 144     for (sal_uInt16 i = n; i < m; i++)
 145         m_pData[i] = t;
 146     usageCount (n);
 147 }
 148
 149 /*========================================================================
 150  *
 151  * OStoreBTreeNodeObject implementation.
 152  *
 153  *======================================================================*/
 154 /*
 155  * guard.
 156  */
 157 storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
 158 {
 159     return PageHolderObject< page >::guard (m_xPage, nAddr);
 160 }
 161
 162 /*
 163  * verify.
 164  */
 165 storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
 166 {
 167     return PageHolderObject< page >::verify (m_xPage, nAddr);
 168 }
 169
 170 /*
 171  * split.
 172  */
 173 storeError OStoreBTreeNodeObject::split (
 174     sal_uInt16                 nIndexL,
 175     PageHolderObject< page > & rxPageL,
 176     OStorePageBIOS           & rBIOS)
 177 {
 178     PageHolderObject< page > xPage (m_xPage);
 179     if (!xPage.is())
 180         return store_E_InvalidAccess;
 181
 182     // Check left page usage.
 183     if (!rxPageL.is())
 184         return store_E_InvalidAccess;
 185     if (!rxPageL->querySplit())
 186         return store_E_None;
 187
 188     // Construct right page.
 189     PageHolderObject< page > xPageR;
 190     if (!xPageR.construct (rBIOS.allocator()))
 191         return store_E_OutOfMemory;
 192
 193     // Split right page off left page.
 194     xPageR->split (*rxPageL);
 195     xPageR->depth (rxPageL->depth());
 196
 197     // Allocate right page.
 198     self aNodeR (xPageR.get());
 199     storeError eErrCode = rBIOS.allocate (aNodeR);
 200     if (eErrCode != store_E_None)
 201         return eErrCode;
 202
 203     // Truncate left page.
 204     rxPageL->truncate (rxPageL->capacityCount() / 2);
 205
 206     // Save left page.
 207     self aNodeL (rxPageL.get());
 208     eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
 209     if (eErrCode != store_E_None)
 210         return eErrCode;
 211
 212     // Insert right page.
 213     OStorePageLink aLink (xPageR->location());
 214     xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
 215
 216     // Save this page and leave.
 217     return rBIOS.saveObjectAt (*this, location());
 218 }
 219
 220 /*
 221  * remove (down to leaf node, recursive).
 222  */
 223 storeError OStoreBTreeNodeObject::remove (
 224     sal_uInt16         nIndexL,
 225     OStoreBTreeEntry & rEntryL,
 226     OStorePageBIOS &   rBIOS)
 227 {
 228     PageHolderObject< page > xImpl (m_xPage);
 229     page & rPage = (*xImpl);
 230
 231     // Check depth.
 232     storeError eErrCode = store_E_None;
 233     if (rPage.depth())
 234     {
 235         // Check link entry.
 236         T const aEntryL (rPage.m_pData[nIndexL]);
 237         if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL))
 238             return store_E_InvalidAccess;
 239
 240         // Load link node.
 241         self aNodeL;
 242         eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
 243         if (eErrCode != store_E_None)
 244             return eErrCode;
 245
 246         // Recurse: remove from link node.
 247         eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
 248         if (eErrCode != store_E_None)
 249             return eErrCode;
 250
 251         // Check resulting link node usage.
 252         PageHolderObject< page > xPageL (aNodeL.get());
 253         if (xPageL->usageCount() == 0)
 254         {
 255             // Free empty link node.
 256             eErrCode = rBIOS.free (xPageL->location());
 257             if (eErrCode != store_E_None)
 258                 return eErrCode;
 259
 260             // Remove index.
 261             rPage.remove (nIndexL);
 262             touch();
 263         }
 264         else
 265         {
 266
 267             // Relink.
 268             rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
 269             touch();
 270         }
 271     }
 272     else
 273     {
 274         // Check leaf entry.
 275         if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
 276             return store_E_NotExists;
 277
 278         // Save leaf entry.
 279         rEntryL = rPage.m_pData[nIndexL];
 280
 281         // Remove leaf index.
 282         rPage.remove (nIndexL);
 283         touch();
 284     }
 285
 286     // Check for modified node.
 287     if (dirty())
 288     {
 289         // Save this page.
 290         eErrCode = rBIOS.saveObjectAt (*this, location());
 291     }
 292
 293     // Done.
 294     return eErrCode;
 295 }
 296
 297 /*========================================================================
 298  *
 299  * OStoreBTreeRootObject implementation.
 300  *
 301  *======================================================================*/
 302 /*
 303  * testInvariant.
 304  * Precond: root node page loaded.
 305  */
 306 bool OStoreBTreeRootObject::testInvariant (char const * message)
 307 {
 308     OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
 309     bool result = ((m_xPage->location() - m_xPage->size()) == 0);
 310     OSL_POSTCOND(result, message); (void) message;
 311     return result;
 312 }
 313
 314 /*
 315  * loadOrCreate.
 316  */
 317 storeError OStoreBTreeRootObject::loadOrCreate (
 318     sal_uInt32       nAddr,
 319     OStorePageBIOS & rBIOS)
 320 {
 321     storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
 322     if (eErrCode != store_E_NotExists)
 323         return eErrCode;
 324
 325     eErrCode = construct<page>(rBIOS.allocator());
 326     if (eErrCode != store_E_None)
 327         return eErrCode;
 328
 329     eErrCode = rBIOS.allocate (*this);
 330     if (eErrCode != store_E_None)
 331         return eErrCode;
 332
 333     // Notify caller of the creation.
 334     (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
 335     return store_E_Pending;
 336 }
 337
 338 /*
 339  * change.
 340  */
 341 storeError OStoreBTreeRootObject::change (
 342     PageHolderObject< page > & rxPageL,
 343     OStorePageBIOS &           rBIOS)
 344 {
 345     PageHolderObject< page > xPage (m_xPage);
 346     (void) testInvariant("OStoreBTreeRootObject::change(): enter");
 347
 348     // Save root location.
 349     sal_uInt32 const nRootAddr = xPage->location();
 350
 351     // Construct new root.
 352     if (!rxPageL.construct (rBIOS.allocator()))
 353         return store_E_OutOfMemory;
 354
 355     // Save this as prev root.
 356     storeError eErrCode = rBIOS.allocate (*this);
 357     if (eErrCode != store_E_None)
 358         return store_E_OutOfMemory;
 359
 360     // Setup new root.
 361     rxPageL->depth (xPage->depth() + 1);
 362     rxPageL->m_pData[0] = xPage->m_pData[0];
 363     rxPageL->m_pData[0].m_aLink = xPage->location();
 364     rxPageL->usageCount(1);
 365
 366     // Change root.
 367     rxPageL.swap (xPage);
 368     {
 369         PageHolder tmp (xPage.get());
 370         tmp.swap (m_xPage);
 371     }
 372
 373     // Save this as new root and finish.
 374     eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
 375     (void) testInvariant("OStoreBTreeRootObject::change(): leave");
 376     return eErrCode;
 377 }
 378
 379 /*
 380  * find_lookup (w/o split()).
 381  * Precond: root node page loaded.
 382  */
 383 storeError OStoreBTreeRootObject::find_lookup (
 384     OStoreBTreeNodeObject & rNode,  // [out]
 385     sal_uInt16 &            rIndex, // [out]
 386     OStorePageKey const &   rKey,
 387     OStorePageBIOS &        rBIOS)
 388 {
 389     // Init node w/ root page.
 390     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
 391     {
 392         PageHolder tmp (m_xPage);
 393         tmp.swap (rNode.get());
 394     }
 395
 396     // Setup BTree entry.
 397     T const entry (rKey);
 398
 399     // Check current page.
 400     PageHolderObject< page > xPage (rNode.get());
 401     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
 402     {
 403         // Find next page.
 404         page const & rPage = (*xPage);
 405         sal_uInt16 const i = rPage.find(entry);
 406         sal_uInt16 const n = rPage.usageCount();
 407         if (!(i < n))
 408         {
 409             // Path to entry not exists (Must not happen(?)).
 410             return store_E_NotExists;
 411         }
 412
 413         // Check address.
 414         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
 415         if (nAddr == STORE_PAGE_NULL)
 416         {
 417             // Path to entry not exists (Must not happen(?)).
 418             return store_E_NotExists;
 419         }
 420
 421         // Load next page.
 422         storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
 423         if (eErrCode != store_E_None)
 424             return eErrCode;
 425     }
 426
 427     // Find index.
 428     page const & rPage = (*xPage);
 429     rIndex = rPage.find(entry);
 430     if (!(rIndex < rPage.usageCount()))
 431         return store_E_NotExists;
 432
 433     // Compare entry.
 434     T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
 435     OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
 436     if (eResult == T::COMPARE_LESS)
 437         return store_E_Unknown;
 438
 439     // Greater or Equal.
 440     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
 441     return store_E_None;
 442 }
 443
 444 /*
 445  * find_insert (possibly with split()).
 446  * Precond: root node page loaded.
 447  */
 448 storeError OStoreBTreeRootObject::find_insert (
 449     OStoreBTreeNodeObject & rNode,  // [out]
 450     sal_uInt16 &            rIndex, // [out]
 451     OStorePageKey const &   rKey,
 452     OStorePageBIOS &        rBIOS)
 453 {
 454     (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");
 455
 456     // Check for RootNode split.
 457     PageHolderObject< page > xRoot (m_xPage);
 458     if (xRoot->querySplit())
 459     {
 460         PageHolderObject< page > xPageL;
 461
 462         // Change root.
 463         storeError eErrCode = change (xPageL, rBIOS);
 464         if (eErrCode != store_E_None)
 465             return eErrCode;
 466
 467         // Split left page (prev root).
 468         eErrCode = split (0, xPageL, rBIOS);
 469         if (eErrCode != store_E_None)
 470             return eErrCode;
 471     }
 472
 473     // Init node w/ root page.
 474     {
 475         PageHolder tmp (m_xPage);
 476         tmp.swap (rNode.get());
 477     }
 478
 479     // Setup BTree entry.
 480     T const entry (rKey);
 481
 482     // Check current Page.
 483     PageHolderObject< page > xPage (rNode.get());
 484     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
 485     {
 486         // Find next page.
 487         page const & rPage = (*xPage);
 488         sal_uInt16 const i = rPage.find (entry);
 489         sal_uInt16 const n = rPage.usageCount();
 490         if (!(i < n))
 491         {
 492             // Path to entry not exists (Must not happen(?)).
 493             return store_E_NotExists;
 494         }
 495
 496         // Check address.
 497         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
 498         if (nAddr == STORE_PAGE_NULL)
 499         {
 500             // Path to entry not exists (Must not happen(?)).
 501             return store_E_NotExists;
 502         }
 503
 504         // Load next page.
 505         OStoreBTreeNodeObject aNext;
 506         storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
 507         if (eErrCode != store_E_None)
 508             return eErrCode;
 509
 510         // Check for next node split.
 511         PageHolderObject< page > xNext (aNext.get());
 512         if (xNext->querySplit())
 513         {
 514             // Split next node.
 515             eErrCode = rNode.split (i, xNext, rBIOS);
 516             if (eErrCode != store_E_None)
 517                 return eErrCode;
 518
 519             // Restart.
 520             continue;
 521         }
 522
 523         // Let next page be current.
 524         PageHolder tmp (aNext.get());
 525         tmp.swap (rNode.get());
 526     }
 527
 528     // Find index.
 529     page const & rPage = (*xPage);
 530     rIndex = rPage.find(entry);
 531     if (rIndex < rPage.usageCount())
 532     {
 533         // Compare entry.
 534         T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
 535         OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
 536         if (result == T::COMPARE_LESS)
 537             return store_E_Unknown;
 538
 539         if (result == T::COMPARE_EQUAL)
 540             return store_E_AlreadyExists;
 541     }
 542
 543     // Greater or not (yet) existing.
 544     (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
 545     return store_E_None;
 546 }
 547
 548 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */