stortree.cxx 14.3 KB
Newer Older
1
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
Michael Meeks's avatar
Michael Meeks committed
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * This file is part of the LibreOffice project.
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * This file incorporates work covered by the following license notice:
 *
 *   Licensed to the Apache Software Foundation (ASF) under one or more
 *   contributor license agreements. See the NOTICE file distributed
 *   with this work for additional information regarding copyright
 *   ownership. The ASF licenses this file to you under the Apache
 *   License, Version 2.0 (the "License"); you may not use this file
 *   except in compliance with the License. You may obtain a copy of
 *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
 */
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
19

20 21 22
#include <sal/config.h>

#include <memory>
23
#include <string.h>
24

25 26
#include "stortree.hxx"

27 28 29
#include <sal/types.h>
#include <sal/log.hxx>
#include <osl/diagnose.h>
30

31
#include <store/types.h>
32 33 34

#include "storbase.hxx"
#include "storbios.hxx"
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
35 36 37 38 39 40 41 42 43 44 45 46

using namespace store;

/*========================================================================
 *
 * OStoreBTreeNodeData implementation.
 *
 *======================================================================*/
/*
 * OStoreBTreeNodeData.
 */
OStoreBTreeNodeData::OStoreBTreeNodeData (sal_uInt16 nPageSize)
47
    : PageData (nPageSize)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
48
{
49 50 51
    base::m_aGuard.m_nMagic = store::htonl(self::theTypeId);
    base::m_aDescr.m_nUsed  = store::htons(self::thePageSize); // usageCount(0)
    self::m_aGuard.m_nMagic = store::htonl(0); // depth(0)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
52

53 54
    sal_uInt16 const n = capacityCount();
    T const          t;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
55

56
    for (sal_uInt16 i = 1; i < n; i++)
57 58
    {
        // cppcheck-suppress arrayIndexOutOfBounds
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
59
        m_pData[i] = t;
60
    }
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
61 62 63 64 65 66 67
}

/*
 * find.
 */
sal_uInt16 OStoreBTreeNodeData::find (const T& t) const
{
68 69
    sal_Int32 l = 0;
    sal_Int32 r = usageCount() - 1;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
70 71 72

    while (l < r)
    {
73
        sal_Int32 const m = ((l + r) >> 1);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
74 75

        if (t.m_aKey == m_pData[m].m_aKey)
76
            return static_cast<sal_uInt16>(m);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
77 78 79 80 81 82
        if (t.m_aKey < m_pData[m].m_aKey)
            r = m - 1;
        else
            l = m + 1;
    }

83
    sal_uInt16 const k = static_cast<sal_uInt16>(r);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
84
    if ((k < capacityCount()) && (t.m_aKey < m_pData[k].m_aKey))
85
        return k - 1;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
86
    else
87
        return k;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
88 89 90 91 92 93 94
}

/*
 * insert.
 */
void OStoreBTreeNodeData::insert (sal_uInt16 i, const T& t)
{
95 96
    sal_uInt16 const n = usageCount();
    sal_uInt16 const m = capacityCount();
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
97 98 99
    if ((n < m) && (i < m))
    {
        // shift right.
100
        memmove (&(m_pData[i + 1]), &(m_pData[i]), (n - i) * sizeof(T));
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
101 102 103

        // insert.
        m_pData[i] = t;
104
        usageCount (n + 1);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
105 106 107 108 109 110 111 112
    }
}

/*
 * remove.
 */
void OStoreBTreeNodeData::remove (sal_uInt16 i)
{
113
    sal_uInt16 const n = usageCount();
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
114 115 116
    if (i < n)
    {
        // shift left.
117
        memmove (&(m_pData[i]), &(m_pData[i + 1]), (n - i - 1) * sizeof(T));
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
118 119 120

        // truncate.
        m_pData[n - 1] = T();
121
        usageCount (n - 1);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
122 123 124 125
    }
}

/*
126
 * split (left half copied from right half of left page).
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
127 128 129
 */
void OStoreBTreeNodeData::split (const self& rPageL)
{
130 131
    sal_uInt16 const h = capacityCount() / 2;
    memcpy (&(m_pData[0]), &(rPageL.m_pData[h]), h * sizeof(T));
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
132 133 134 135 136 137 138 139
    truncate (h);
}

/*
 * truncate.
 */
void OStoreBTreeNodeData::truncate (sal_uInt16 n)
{
140 141
    sal_uInt16 const m = capacityCount();
    T const          t;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
142 143 144 145 146 147 148 149 150 151 152 153 154 155

    for (sal_uInt16 i = n; i < m; i++)
        m_pData[i] = t;
    usageCount (n);
}

/*========================================================================
 *
 * OStoreBTreeNodeObject implementation.
 *
 *======================================================================*/
/*
 * guard.
 */
156
storeError OStoreBTreeNodeObject::guard (sal_uInt32 nAddr)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
157
{
158
    return PageHolderObject< page >::guard (m_xPage, nAddr);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
159 160 161 162 163
}

/*
 * verify.
 */
164
storeError OStoreBTreeNodeObject::verify (sal_uInt32 nAddr) const
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
165
{
166
    return PageHolderObject< page >::verify (m_xPage, nAddr);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
167 168 169 170 171 172
}

/*
 * split.
 */
storeError OStoreBTreeNodeObject::split (
173 174 175
    sal_uInt16                 nIndexL,
    PageHolderObject< page > & rxPageL,
    OStorePageBIOS           & rBIOS)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
176
{
177 178 179 180 181 182 183 184
    PageHolderObject< page > xPage (m_xPage);
    if (!xPage.is())
        return store_E_InvalidAccess;

    // Check left page usage.
    if (!rxPageL.is())
        return store_E_InvalidAccess;
    if (!rxPageL->querySplit())
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
185 186
        return store_E_None;

187 188 189 190
    // Construct right page.
    PageHolderObject< page > xPageR;
    if (!xPageR.construct (rBIOS.allocator()))
        return store_E_OutOfMemory;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
191 192

    // Split right page off left page.
193 194
    xPageR->split (*rxPageL);
    xPageR->depth (rxPageL->depth());
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
195 196

    // Allocate right page.
197
    self aNodeR (xPageR.get());
198
    storeError eErrCode = rBIOS.allocate (aNodeR);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
199
    if (eErrCode != store_E_None)
200
        return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
201 202

    // Truncate left page.
203
    rxPageL->truncate (rxPageL->capacityCount() / 2);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
204 205

    // Save left page.
206 207
    self aNodeL (rxPageL.get());
    eErrCode = rBIOS.saveObjectAt (aNodeL, aNodeL.location());
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
208
    if (eErrCode != store_E_None)
209
        return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
210 211

    // Insert right page.
212 213
    OStorePageLink aLink (xPageR->location());
    xPage->insert (nIndexL + 1, T(xPageR->m_pData[0].m_aKey, aLink));
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
214

215 216
    // Save this page and leave.
    return rBIOS.saveObjectAt (*this, location());
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
217 218 219 220 221 222
}

/*
 * remove (down to leaf node, recursive).
 */
storeError OStoreBTreeNodeObject::remove (
223 224 225
    sal_uInt16         nIndexL,
    OStoreBTreeEntry & rEntryL,
    OStorePageBIOS &   rBIOS)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
226
{
227
    PageHolderObject< page > xImpl (m_xPage);
228
    page & rPage = *xImpl;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
229 230

    // Check depth.
231
    storeError eErrCode = store_E_None;
232
    if (rPage.depth())
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
233 234
    {
        // Check link entry.
235
        T const aEntryL (rPage.m_pData[nIndexL]);
236
        if (rEntryL.compare (aEntryL) != T::COMPARE_EQUAL)
237
            return store_E_InvalidAccess;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
238 239

        // Load link node.
240 241
        self aNodeL;
        eErrCode = rBIOS.loadObjectAt (aNodeL, aEntryL.m_aLink.location());
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
242
        if (eErrCode != store_E_None)
243
            return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
244

245 246
        // Recurse: remove from link node.
        eErrCode = aNodeL.remove (0, rEntryL, rBIOS);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
247
        if (eErrCode != store_E_None)
248
            return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
249

250 251 252
        // Check resulting link node usage.
        PageHolderObject< page > xPageL (aNodeL.get());
        if (xPageL->usageCount() == 0)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
253 254
        {
            // Free empty link node.
255
            eErrCode = rBIOS.free (xPageL->location());
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
256
            if (eErrCode != store_E_None)
257
                return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
258 259

            // Remove index.
260
            rPage.remove (nIndexL);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
261 262 263 264 265 266
            touch();
        }
        else
        {

            // Relink.
267
            rPage.m_pData[nIndexL].m_aKey = xPageL->m_pData[0].m_aKey;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
268 269 270 271 272 273
            touch();
        }
    }
    else
    {
        // Check leaf entry.
274
        if (rEntryL.compare (rPage.m_pData[nIndexL]) != T::COMPARE_EQUAL)
275
            return store_E_NotExists;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
276 277

        // Save leaf entry.
278
        rEntryL = rPage.m_pData[nIndexL];
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
279 280

        // Remove leaf index.
281
        rPage.remove (nIndexL);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
282 283 284 285 286 287 288
        touch();
    }

    // Check for modified node.
    if (dirty())
    {
        // Save this page.
289
        eErrCode = rBIOS.saveObjectAt (*this, location());
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
290 291
    }

292 293
    // Done.
    return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
294 295 296 297 298 299 300
}

/*========================================================================
 *
 * OStoreBTreeRootObject implementation.
 *
 *======================================================================*/
301 302 303 304
/*
 * testInvariant.
 * Precond: root node page loaded.
 */
305
void OStoreBTreeRootObject::testInvariant (char const * message) const
306
{
307
    OSL_PRECOND(m_xPage != nullptr, "OStoreBTreeRootObject::testInvariant(): Null pointer");
308
    SAL_WARN_IF( (m_xPage->location() - m_xPage->size()) != 0, "store", message);
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330
}

/*
 * loadOrCreate.
 */
storeError OStoreBTreeRootObject::loadOrCreate (
    sal_uInt32       nAddr,
    OStorePageBIOS & rBIOS)
{
    storeError eErrCode = rBIOS.loadObjectAt (*this, nAddr);
    if (eErrCode != store_E_NotExists)
        return eErrCode;

    eErrCode = construct<page>(rBIOS.allocator());
    if (eErrCode != store_E_None)
        return eErrCode;

    eErrCode = rBIOS.allocate (*this);
    if (eErrCode != store_E_None)
        return eErrCode;

    // Notify caller of the creation.
331
    testInvariant("OStoreBTreeRootObject::loadOrCreate(): leave");
332 333 334
    return store_E_Pending;
}

Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
335 336 337 338
/*
 * change.
 */
storeError OStoreBTreeRootObject::change (
339 340
    PageHolderObject< page > & rxPageL,
    OStorePageBIOS &           rBIOS)
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
341
{
342
    PageHolderObject< page > xPage (m_xPage);
343
    testInvariant("OStoreBTreeRootObject::change(): enter");
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
344

345 346
    // Save root location.
    sal_uInt32 const nRootAddr = xPage->location();
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
347

348 349 350
    // Construct new root.
    if (!rxPageL.construct (rBIOS.allocator()))
        return store_E_OutOfMemory;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
351

352
    // Save this as prev root.
353
    storeError eErrCode = rBIOS.allocate (*this);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
354
    if (eErrCode != store_E_None)
355
        return store_E_OutOfMemory;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
356

357 358 359 360 361
    // Setup new root.
    rxPageL->depth (xPage->depth() + 1);
    rxPageL->m_pData[0] = xPage->m_pData[0];
    rxPageL->m_pData[0].m_aLink = xPage->location();
    rxPageL->usageCount(1);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
362

363 364 365
    // Change root.
    rxPageL.swap (xPage);
    {
366
        std::shared_ptr<PageData> tmp (xPage.get());
367 368
        tmp.swap (m_xPage);
    }
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
369

370
    // Save this as new root and finish.
371
    eErrCode = rBIOS.saveObjectAt (*this, nRootAddr);
372
    testInvariant("OStoreBTreeRootObject::change(): leave");
373
    return eErrCode;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
374 375 376
}

/*
377 378
 * find_lookup (w/o split()).
 * Precond: root node page loaded.
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
379
 */
380 381 382 383
storeError OStoreBTreeRootObject::find_lookup (
    OStoreBTreeNodeObject & rNode,  // [out]
    sal_uInt16 &            rIndex, // [out]
    OStorePageKey const &   rKey,
384
    OStorePageBIOS &        rBIOS) const
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
385
{
386
    // Init node w/ root page.
387
    testInvariant("OStoreBTreeRootObject::find_lookup(): enter");
388
    {
389
        std::shared_ptr<PageData> tmp (m_xPage);
390 391
        tmp.swap (rNode.get());
    }
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
392

393 394
    // Setup BTree entry.
    T const entry (rKey);
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
395

396 397
    // Check current page.
    PageHolderObject< page > xPage (rNode.get());
398
    for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
399 400
    {
        // Find next page.
401
        page const & rPage = *xPage;
402 403
        sal_uInt16 const i = rPage.find(entry);
        sal_uInt16 const n = rPage.usageCount();
404
        if (i >= n)
405 406 407 408
        {
            // Path to entry not exists (Must not happen(?)).
            return store_E_NotExists;
        }
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
409

410 411 412 413 414 415 416
        // Check address.
        sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
        if (nAddr == STORE_PAGE_NULL)
        {
            // Path to entry not exists (Must not happen(?)).
            return store_E_NotExists;
        }
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
417

418 419 420 421 422 423 424
        // Load next page.
        storeError eErrCode = rBIOS.loadObjectAt (rNode, nAddr);
        if (eErrCode != store_E_None)
            return eErrCode;
    }

    // Find index.
425
    page const & rPage = *xPage;
426
    rIndex = rPage.find(entry);
427
    if (rIndex >= rPage.usageCount())
428 429 430 431 432
        return store_E_NotExists;

    // Compare entry.
    T::CompareResult eResult = entry.compare(rPage.m_pData[rIndex]);
    if (eResult == T::COMPARE_LESS)
433 434
    {
        SAL_WARN("store", "store::BTreeRoot::find_lookup(): sort error");
435
        return store_E_Unknown;
436
    }
437 438

    // Greater or Equal.
439
    testInvariant("OStoreBTreeRootObject::find_lookup(): leave");
440
    return store_E_None;
Jens-Heiner Rechtien's avatar
Jens-Heiner Rechtien committed
441 442
}

443 444 445 446 447 448 449 450 451 452
/*
 * find_insert (possibly with split()).
 * Precond: root node page loaded.
 */
storeError OStoreBTreeRootObject::find_insert (
    OStoreBTreeNodeObject & rNode,  // [out]
    sal_uInt16 &            rIndex, // [out]
    OStorePageKey const &   rKey,
    OStorePageBIOS &        rBIOS)
{
453
    testInvariant("OStoreBTreeRootObject::find_insert(): enter");
454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473

    // Check for RootNode split.
    PageHolderObject< page > xRoot (m_xPage);
    if (xRoot->querySplit())
    {
        PageHolderObject< page > xPageL;

        // Change root.
        storeError eErrCode = change (xPageL, rBIOS);
        if (eErrCode != store_E_None)
            return eErrCode;

        // Split left page (prev root).
        eErrCode = split (0, xPageL, rBIOS);
        if (eErrCode != store_E_None)
            return eErrCode;
    }

    // Init node w/ root page.
    {
474
        std::shared_ptr<PageData> tmp (m_xPage);
475 476 477 478 479 480 481 482
        tmp.swap (rNode.get());
    }

    // Setup BTree entry.
    T const entry (rKey);

    // Check current Page.
    PageHolderObject< page > xPage (rNode.get());
483
    for (; xPage->depth() > 0; xPage = rNode.makeHolder< page >())
484 485
    {
        // Find next page.
486
        page const & rPage = *xPage;
487 488
        sal_uInt16 const i = rPage.find (entry);
        sal_uInt16 const n = rPage.usageCount();
489
        if (i >= n)
490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522
        {
            // Path to entry not exists (Must not happen(?)).
            return store_E_NotExists;
        }

        // Check address.
        sal_uInt32 const nAddr = rPage.m_pData[i].m_aLink.location();
        if (nAddr == STORE_PAGE_NULL)
        {
            // Path to entry not exists (Must not happen(?)).
            return store_E_NotExists;
        }

        // Load next page.
        OStoreBTreeNodeObject aNext;
        storeError eErrCode = rBIOS.loadObjectAt (aNext, nAddr);
        if (eErrCode != store_E_None)
            return eErrCode;

        // Check for next node split.
        PageHolderObject< page > xNext (aNext.get());
        if (xNext->querySplit())
        {
            // Split next node.
            eErrCode = rNode.split (i, xNext, rBIOS);
            if (eErrCode != store_E_None)
                return eErrCode;

            // Restart.
            continue;
        }

        // Let next page be current.
523
        std::shared_ptr<PageData> tmp (aNext.get());
524 525 526 527
        tmp.swap (rNode.get());
    }

    // Find index.
528
    page const & rPage = *xPage;
529 530 531 532 533 534
    rIndex = rPage.find(entry);
    if (rIndex < rPage.usageCount())
    {
        // Compare entry.
        T::CompareResult result = entry.compare (rPage.m_pData[rIndex]);
        if (result == T::COMPARE_LESS)
535 536
        {
            SAL_WARN("store", "store::BTreeRoot::find_insert(): sort error");
537
            return store_E_Unknown;
538
        }
539 540 541 542 543 544

        if (result == T::COMPARE_EQUAL)
            return store_E_AlreadyExists;
    }

    // Greater or not (yet) existing.
545
    testInvariant("OStoreBTreeRootObject::find_insert(): leave");
546 547
    return store_E_None;
}
548 549

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */