store/source/stortree.cxx

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