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