store/source/stortree.cxx

   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.cxx,v $
  10  * $Revision: 1.8 $
  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 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_store.hxx"
  33
  34 #include "stortree.hxx"
  35
  36 #include "sal/types.h"
  37 #include "osl/diagnose.h"
  38
  39 #include "store/types.h"
  40
  41 #include "storbase.hxx"
  42 #include "storbios.hxx"
  43
  44 using namespace store;
  45
  46 /*========================================================================
  47  *
  48  * OStoreBTreeNodeData implementation.
  49  *
  50  *======================================================================*/
  51 /*
  52  * OStoreBTreeNodeData.
  53  */
  54 OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
  55     : OStorePageData (nPageSize)
  56 {
  57     base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
  58     base::m_aDescr.m_nUsed  = store::htons(self::thePageSize); // usageCount(0)
  59     self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
  60
  61     sal_uInt16 const n = capacityCount();
  62     T const          t;
  63
  64     for (sal_uInt16 i = 1; i < n; i++)
  65         m_pData[i] = t;
  66 }
  67
  68 /*
  69  * find.
  70  */
  71 sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
  72 {
  73     register sal_Int32 l = 0;
  74     register sal_Int32 r = usageCount() - 1;
  75
  76     while (l < r)
  77     {
  78         register sal_Int32 const m = ((l + r) >> 1);
  79
  80         if (t.m_aKey == m_pData[m].m_aKey)
  81             return ((sal_uInt16)(m));
  82         if (t.m_aKey < m_pData[m].m_aKey)
  83             r = m - 1;
  84         else
  85             l = m + 1;
  86     }
  87
  88     sal_uInt16 const k = ((sal_uInt16)(r));
  89     if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
  90         return(k - 1);
  91     else
  92         return(k);
  93 }
  94
  95 /*
  96  * insert.
  97  */
  98 void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
  99 {
 100     sal_uInt16 const n = usageCount();
 101     sal_uInt16 const m = capacityCount();
 102     if ((n < m) && (i < m))
 103     {
 104         // shift right.
 105         memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
 106
 107         // insert.
 108         m_pData[i] = t;
 109         usageCount (n + 1);
 110     }
 111 }
 112
 113 /*
 114  * remove.
 115  */
 116 void OStoreBTreeNodeData::remove (sal_uInt16 i)
 117 {
 118     sal_uInt16 const n = usageCount();
 119     if (i < n)
 120     {
 121         // shift left.
 122         memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));
 123
 124         // truncate.
 125         m_pData[n - 1] = T();
 126         usageCount (n - 1);
 127     }
 128 }
 129
 130 #if 0  /* NYI */
 131 /*
 132  * merge (with right page).
 133  */
 134 void OStoreBTreeNodeData::merge (const self& rPageR)
 135 {
 136     sal_uInt16 const n = usageCount();
 137     sal_uInt16 const m = rPageR.usageCount();
 138     if ((n + m) <= capacityCount())
 139     {
 140         memcpy (&(m_pData[n]), &(rPageR.m_pData[0]), m * sizeof(T));
 141         usageCount (n + m);
 142     }
 143 }
 144 #endif
 145
 146 /*
 147  * split (left half copied from right half of left page).
 148  */
 149 void OStoreBTreeNodeData::split (const self& rPageL)
 150 {
 151     sal_uInt16 const h = capacityCount() / 2;
 152     memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
 153     truncate (h);
 154 }
 155
 156 /*
 157  * truncate.
 158  */
 159 void OStoreBTreeNodeData::truncate (sal_uInt16 n)
 160 {
 161     sal_uInt16 const m = capacityCount();
 162     T const          t;
 163
 164     for (sal_uInt16 i = n; i < m; i++)
 165         m_pData[i] = t;
 166     usageCount (n);
 167 }
 168
 169 /*========================================================================
 170  *
 171  * OStoreBTreeNodeObject implementation.
 172  *
 173  *======================================================================*/
 174 /*
 175  * guard.
 176  */
 177 storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
 178 {
 179     return PageHolderObject< page >::guard (m_xPage, nAddr);
 180 }
 181
 182 /*
 183  * verify.
 184  */
 185 storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
 186 {
 187     return store_E_None;
 188
 189     return PageHolderObject< page >::verify (m_xPage, nAddr);
 190 }
 191
 192 /*
 193  * split.
 194  */
 195 storeError OStoreBTreeNodeObject::split (
 196     sal_uInt16                 nIndexL,
 197     PageHolderObject< page > & rxPageL,
 198     OStorePageBIOS           & rBIOS)
 199 {
 200     PageHolderObject< page > xPage (m_xPage);
 201     if (!xPage.is())
 202         return store_E_InvalidAccess;
 203
 204     // Check left page usage.
 205     if (!rxPageL.is())
 206         return store_E_InvalidAccess;
 207     if (!rxPageL->querySplit())
 208         return store_E_None;
 209
 210     // Save PageDescriptor.
 211     OStorePageDescriptor aDescr (xPage->m_aDescr);
 212     aDescr.m_nAddr = store::ntohl(aDescr.m_nAddr);
 213     aDescr.m_nSize = store::ntohs(aDescr.m_nSize);
 214
 215     // Acquire Lock.
 216     storeError eErrCode = rBIOS.acquireLock (aDescr.m_nAddr, aDescr.m_nSize);
 217     if (eErrCode != store_E_None)
 218         return eErrCode;
 219
 220     // [Begin PageL Lock (NYI)]
 221
 222     // Construct right page.
 223     PageHolderObject< page > xPageR;
 224     if (!xPageR.construct (rBIOS.allocator()))
 225     {
 226         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 227         return store_E_OutOfMemory;
 228     }
 229
 230     // Split right page off left page.
 231     xPageR->split (*rxPageL);
 232     xPageR->depth (rxPageL->depth());
 233
 234     // Allocate right page.
 235     self aNodeR (xPageR.get());
 236     eErrCode = rBIOS.allocate (aNodeR);
 237     if (eErrCode != store_E_None)
 238     {
 239         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 240         return eErrCode;
 241     }
 242
 243     // Truncate left page.
 244     rxPageL->truncate (rxPageL->capacityCount() / 2);
 245
 246     // Save left page.
 247     self aNodeL (rxPageL.get());
 248     eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
 249     if (eErrCode != store_E_None)
 250     {
 251         // Must not happen.
 252         OSL_TRACE("OStoreBTreeNodeObject::split(): save() failed");
 253
 254         // Release Lock and Leave.
 255         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 256         return eErrCode;
 257     }
 258
 259     // [End PageL Lock (NYI)]
 260
 261     // Insert right page.
 262     OStorePageLink aLink (xPageR->location());
 263     xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
 264
 265     // Save this page.
 266     eErrCode = rBIOS.saveObjectAt (*this, location());
 267     if (eErrCode != store_E_None)
 268     {
 269         // Must not happen.
 270         OSL_TRACE("OStoreBTreeNodeObject::split(): save() failed");
 271
 272         // Release Lock and Leave.
 273         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 274         return eErrCode;
 275     }
 276
 277     // Release Lock and Leave.
 278     return rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 279 }
 280
 281 /*
 282  * remove (down to leaf node, recursive).
 283  */
 284 storeError OStoreBTreeNodeObject::remove (
 285     sal_uInt16         nIndexL,
 286     OStoreBTreeEntry & rEntryL,
 287     OStorePageBIOS &   rBIOS)
 288 {
 289     PageHolderObject< page > xImpl (m_xPage);
 290     page & rPage = (*xImpl);
 291
 292     // Save PageDescriptor.
 293     OStorePageDescriptor aDescr (rPage.m_aDescr);
 294     aDescr.m_nAddr = store::ntohl(aDescr.m_nAddr);
 295     aDescr.m_nSize = store::ntohs(aDescr.m_nSize);
 296
 297     // Acquire Lock.
 298     storeError eErrCode = rBIOS.acquireLock (aDescr.m_nAddr, aDescr.m_nSize);
 299     if (eErrCode != store_E_None)
 300         return eErrCode;
 301
 302     // Check depth.
 303     if (rPage.depth())
 304     {
 305         // Check link entry.
 306         T const aEntryL (rPage.m_pData[nIndexL]);
 307         if (!(rEntryL.compare (aEntryL) == T::COMPARE_EQUAL))
 308         {
 309             rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 310             return store_E_InvalidAccess;
 311         }
 312
 313         // Load link node.
 314         self aNodeL;
 315         eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
 316         if (eErrCode != store_E_None)
 317         {
 318             rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 319             return eErrCode;
 320         }
 321
 322         // Recurse: remove from link node.
 323         eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
 324         if (eErrCode != store_E_None)
 325         {
 326             rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 327             return eErrCode;
 328         }
 329
 330         // Check resulting link node usage.
 331         PageHolderObject< page > xPageL (aNodeL.get());
 332         if (xPageL->usageCount() == 0)
 333         {
 334             // Free empty link node.
 335             OStorePageData aPageHead;
 336             eErrCode = rBIOS.free (aPageHead, xPageL->location());
 337             if (eErrCode != store_E_None)
 338             {
 339                 rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 340                 return eErrCode;
 341             }
 342
 343             // Remove index.
 344             rPage.remove (nIndexL);
 345             touch();
 346         }
 347         else
 348         {
 349 #if 0   /* NYI */
 350             // Check for right sibling.
 351             sal_uInt16 const nIndexR = nIndexL + 1;
 352             if (nIndexR < rPage.usageCount())
 353             {
 354                 // Load right link node.
 355                 self aNodeR;
 356                 eErrCode = rBIOS.loadObjectAt (aNodeR, rPage.m_pData[nIndexR].m_aLink.location());
 357                 if (eErrCode == store_E_None)
 358                 {
 359                     if (rPageL.queryMerge (rPageR))
 360                     {
 361                         rPageL.merge (rPageR);
 362
 363                         eErrCode = rBIOS.free (aPageHead, rPageR.location());
 364                     }
 365                 }
 366             }
 367 #endif  /* NYI */
 368
 369             // Relink.
 370             rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
 371             touch();
 372         }
 373     }
 374     else
 375     {
 376         // Check leaf entry.
 377         if (!(rEntryL.compare (rPage.m_pData[nIndexL]) == T::COMPARE_EQUAL))
 378         {
 379             rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 380             return store_E_NotExists;
 381         }
 382
 383         // Save leaf entry.
 384         rEntryL = rPage.m_pData[nIndexL];
 385
 386         // Remove leaf index.
 387         rPage.remove (nIndexL);
 388         touch();
 389     }
 390
 391     // Check for modified node.
 392     if (dirty())
 393     {
 394         // Save this page.
 395         eErrCode = rBIOS.saveObjectAt (*this, location());
 396         if (eErrCode != store_E_None)
 397         {
 398             // Must not happen.
 399             OSL_TRACE("OStoreBTreeNodeObject::remove(): save() failed");
 400
 401             // Release Lock and Leave.
 402             rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 403             return eErrCode;
 404         }
 405     }
 406
 407     // Release Lock and Leave.
 408     return rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 409 }
 410
 411 /*========================================================================
 412  *
 413  * OStoreBTreeRootObject implementation.
 414  *
 415  *======================================================================*/
 416 /*
 417  * testInvariant.
 418  * Precond: root node page loaded.
 419  */
 420 bool OStoreBTreeRootObject::testInvariant (char const * message)
 421 {
 422     OSL_PRECOND(m_xPage.get() != 0, "OStoreBTreeRootObject::testInvariant(): Null pointer");
 423     bool result = ((m_xPage->location() - m_xPage->size()) == 0);
 424     OSL_POSTCOND(result, message); (void) message;
 425     return result;
 426 }
 427
 428 /*
 429  * loadOrCreate.
 430  */
 431 storeError OStoreBTreeRootObject::loadOrCreate (
 432     sal_uInt32       nAddr,
 433     OStorePageBIOS & rBIOS)
 434 {
 435     storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
 436     if (eErrCode != store_E_NotExists)
 437         return eErrCode;
 438
 439     eErrCode = construct<page>(rBIOS.allocator());
 440     if (eErrCode != store_E_None)
 441         return eErrCode;
 442
 443     eErrCode = rBIOS.allocate (*this);
 444     if (eErrCode != store_E_None)
 445         return eErrCode;
 446
 447     // Notify caller of the creation.
 448     (void) testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
 449     return store_E_Pending;
 450 }
 451
 452 /*
 453  * change.
 454  */
 455 storeError OStoreBTreeRootObject::change (
 456     PageHolderObject< page > & rxPageL,
 457     OStorePageBIOS &           rBIOS)
 458 {
 459     PageHolderObject< page > xPage (m_xPage);
 460     (void) testInvariant("OStoreBTreeRootObject::change(): enter");
 461
 462     // Save PageDescriptor.
 463     OStorePageDescriptor aDescr (xPage->m_aDescr);
 464     aDescr.m_nAddr = store::ntohl(aDescr.m_nAddr);
 465     aDescr.m_nSize = store::ntohs(aDescr.m_nSize);
 466
 467     // Save root location.
 468     sal_uInt32 const nRootAddr = xPage->location();
 469
 470     // Acquire Lock.
 471     storeError eErrCode = rBIOS.acquireLock (aDescr.m_nAddr, aDescr.m_nSize);
 472     if (eErrCode != store_E_None)
 473         return eErrCode;
 474
 475     // Construct new root.
 476     if (!rxPageL.construct (rBIOS.allocator()))
 477     {
 478         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 479         return store_E_OutOfMemory;
 480     }
 481
 482     // Save this as prev root.
 483     eErrCode = rBIOS.allocate (*this);
 484     if (eErrCode != store_E_None)
 485     {
 486         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 487         return store_E_OutOfMemory;
 488     }
 489
 490     // Setup new root.
 491     rxPageL->depth (xPage->depth() + 1);
 492     rxPageL->m_pData[0] = xPage->m_pData[0];
 493     rxPageL->m_pData[0].m_aLink = xPage->location();
 494     rxPageL->usageCount(1);
 495
 496     // Change root.
 497     rxPageL.swap (xPage);
 498     {
 499         PageHolder tmp (xPage.get());
 500         tmp.swap (m_xPage);
 501     }
 502
 503     // Save this as new root.
 504     eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
 505     if (eErrCode != store_E_None)
 506     {
 507         // Must not happen.
 508         OSL_TRACE("OStoreBTreeRootObject::change(): save() failed");
 509
 510         // Release Lock and Leave.
 511         rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 512         return eErrCode;
 513     }
 514
 515     // Flush for robustness.
 516     (void) rBIOS.flush();
 517
 518     // Done. Release Lock and Leave.
 519     (void) testInvariant("OStoreBTreeRootObject::change(): leave");
 520     return rBIOS.releaseLock (aDescr.m_nAddr, aDescr.m_nSize);
 521 }
 522
 523 /*
 524  * find_lookup (w/o split()).
 525  * Precond: root node page loaded.
 526  */
 527 storeError OStoreBTreeRootObject::find_lookup (
 528     OStoreBTreeNodeObject & rNode,  // [out]
 529     sal_uInt16 &            rIndex, // [out]
 530     OStorePageKey const &   rKey,
 531     OStorePageBIOS &        rBIOS)
 532 {
 533     // Init node w/ root page.
 534     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
 535     {
 536         PageHolder tmp (m_xPage);
 537         tmp.swap (rNode.get());
 538     }
 539
 540     // Setup BTree entry.
 541     T const entry (rKey);
 542
 543     // Check current page.
 544     PageHolderObject< page > xPage (rNode.get());
 545     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
 546     {
 547         // Find next page.
 548         page const & rPage = (*xPage);
 549         sal_uInt16 const i = rPage.find(entry);
 550         sal_uInt16 const n = rPage.usageCount();
 551         if (!(i < n))
 552         {
 553             // Path to entry not exists (Must not happen(?)).
 554             return store_E_NotExists;
 555         }
 556
 557         // Check address.
 558         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
 559         if (nAddr == STORE_PAGE_NULL)
 560         {
 561             // Path to entry not exists (Must not happen(?)).
 562             return store_E_NotExists;
 563         }
 564
 565         // Load next page.
 566         storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
 567         if (eErrCode != store_E_None)
 568             return eErrCode;
 569     }
 570
 571     // Find index.
 572     page const & rPage = (*xPage);
 573     rIndex = rPage.find(entry);
 574     if (!(rIndex < rPage.usageCount()))
 575         return store_E_NotExists;
 576
 577     // Compare entry.
 578     T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
 579     OSL_POSTCOND(eResult != T::COMPARE_LESS, "store::BTreeRoot::find_lookup(): sort error");
 580     if (eResult == T::COMPARE_LESS)
 581         return store_E_Unknown;
 582
 583     // Greater or Equal.
 584     (void) testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
 585     return store_E_None;
 586 }
 587
 588 /*
 589  * find_insert (possibly with split()).
 590  * Precond: root node page loaded.
 591  */
 592 storeError OStoreBTreeRootObject::find_insert (
 593     OStoreBTreeNodeObject & rNode,  // [out]
 594     sal_uInt16 &            rIndex, // [out]
 595     OStorePageKey const &   rKey,
 596     OStorePageBIOS &        rBIOS)
 597 {
 598     (void) testInvariant("OStoreBTreeRootObject::find_insert(): enter");
 599
 600     // Check for RootNode split.
 601     PageHolderObject< page > xRoot (m_xPage);
 602     if (xRoot->querySplit())
 603     {
 604         PageHolderObject< page > xPageL;
 605
 606         // Change root.
 607         storeError eErrCode = change (xPageL, rBIOS);
 608         if (eErrCode != store_E_None)
 609             return eErrCode;
 610
 611         // Split left page (prev root).
 612         eErrCode = split (0, xPageL, rBIOS);
 613         if (eErrCode != store_E_None)
 614             return eErrCode;
 615     }
 616
 617     // Init node w/ root page.
 618     {
 619         PageHolder tmp (m_xPage);
 620         tmp.swap (rNode.get());
 621     }
 622
 623     // Setup BTree entry.
 624     T const entry (rKey);
 625
 626     // Check current Page.
 627     PageHolderObject< page > xPage (rNode.get());
 628     for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
 629     {
 630         // Find next page.
 631         page const & rPage = (*xPage);
 632         sal_uInt16 const i = rPage.find (entry);
 633         sal_uInt16 const n = rPage.usageCount();
 634         if (!(i < n))
 635         {
 636             // Path to entry not exists (Must not happen(?)).
 637             return store_E_NotExists;
 638         }
 639
 640         // Check address.
 641         sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
 642         if (nAddr == STORE_PAGE_NULL)
 643         {
 644             // Path to entry not exists (Must not happen(?)).
 645             return store_E_NotExists;
 646         }
 647
 648         // Load next page.
 649         OStoreBTreeNodeObject aNext;
 650         storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
 651         if (eErrCode != store_E_None)
 652             return eErrCode;
 653
 654         // Check for next node split.
 655         PageHolderObject< page > xNext (aNext.get());
 656         if (xNext->querySplit())
 657         {
 658             // Split next node.
 659             eErrCode = rNode.split (i, xNext, rBIOS);
 660             if (eErrCode != store_E_None)
 661                 return eErrCode;
 662
 663             // Restart.
 664             continue;
 665         }
 666
 667         // Let next page be current.
 668         PageHolder tmp (aNext.get());
 669         tmp.swap (rNode.get());
 670     }
 671
 672     // Find index.
 673     page const & rPage = (*xPage);
 674     rIndex = rPage.find(entry);
 675     if (rIndex < rPage.usageCount())
 676     {
 677         // Compare entry.
 678         T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
 679         OSL_POSTCOND(result != T::COMPARE_LESS, "store::BTreeRoot::find_insert(): sort error");
 680         if (result == T::COMPARE_LESS)
 681             return store_E_Unknown;
 682
 683         if (result == T::COMPARE_EQUAL)
 684             return store_E_AlreadyExists;
 685     }
 686
 687     // Greater or not (yet) existing.
 688     (void) testInvariant("OStoreBTreeRootObject::find_insert(): leave");
 689     return store_E_None;
 690 }