store/source/stortree.hxx

/**************************************************************
 *
 * 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
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *************************************************************/


#ifndef _STORE_STORTREE_HXX
#define _STORE_STORTREE_HXX "$Revision: 1.6.8.2 $"

#include "sal/types.h"

#include "store/types.h"

#include "storbase.hxx"

namespace store
{

class OStorePageBIOS;

/*========================================================================
 *
 * OStoreBTreeEntry.
 *
 *======================================================================*/
struct OStoreBTreeEntry
{
    typedef OStorePageKey  K;
    typedef OStorePageLink L;

    /** Representation.
    */
    K          m_aKey;
    L          m_aLink;
    sal_uInt32 m_nAttrib;

    /** Construction.
    */
    explicit OStoreBTreeEntry (
        K const &  rKey    = K(),
        L const &  rLink   = L(),
        sal_uInt32 nAttrib = 0)
        : m_aKey    (rKey),
          m_aLink   (rLink),
          m_nAttrib (store::htonl(nAttrib))
    {}

    OStoreBTreeEntry (const OStoreBTreeEntry & rhs)
        : m_aKey    (rhs.m_aKey),
          m_aLink   (rhs.m_aLink),
          m_nAttrib (rhs.m_nAttrib)
    {}

    OStoreBTreeEntry& operator= (const OStoreBTreeEntry & rhs)
    {
        m_aKey    = rhs.m_aKey;
        m_aLink   = rhs.m_aLink;
        m_nAttrib = rhs.m_nAttrib;
        return *this;
    }

    /** Comparison.
    */
    enum CompareResult
    {
        COMPARE_LESS    = -1,
        COMPARE_EQUAL   =  0,
        COMPARE_GREATER =  1
    };

    CompareResult compare (const OStoreBTreeEntry& rOther) const
    {
        if (m_aKey < rOther.m_aKey)
            return COMPARE_LESS;
        else if (m_aKey == rOther.m_aKey)
            return COMPARE_EQUAL;
        else
            return COMPARE_GREATER;
    }
};

/*========================================================================
 *
 * OStoreBTreeNodeData.
 *
 *======================================================================*/
#define STORE_MAGIC_BTREENODE sal_uInt32(0x58190322)

struct OStoreBTreeNodeData : public store::OStorePageData
{
    typedef OStorePageData      base;
    typedef OStoreBTreeNodeData self;

    typedef OStorePageGuard     G;
    typedef OStoreBTreeEntry    T;

    /** Representation.
     */
    G m_aGuard;
    T m_pData[1];

    /** type.
     */
    static const sal_uInt32 theTypeId = STORE_MAGIC_BTREENODE;

    /** theSize.
     */
    static const size_t     theSize     = sizeof(G);
    static const sal_uInt16 thePageSize = base::theSize + self::theSize;
    STORE_STATIC_ASSERT(STORE_MINIMUM_PAGESIZE >= self::thePageSize);

    /** capacity.
    */
    sal_uInt16 capacity (void) const
    {
        return (store::ntohs(base::m_aDescr.m_nSize) - self::thePageSize);
    }

    /** capacityCount (must be even).
    */
    sal_uInt16 capacityCount (void) const
    {
        return sal_uInt16(capacity() / sizeof(T));
    }

    /** usage.
    */
    sal_uInt16 usage (void) const
    {
        return (store::ntohs(base::m_aDescr.m_nUsed) - self::thePageSize);
    }

    /** usageCount.
    */
    sal_uInt16 usageCount (void) const
    {
        return sal_uInt16(usage() / sizeof(T));
    }
    void usageCount (sal_uInt16 nCount)
    {
        size_t const nBytes = self::thePageSize + nCount * sizeof(T);
        base::m_aDescr.m_nUsed = store::htons(sal::static_int_cast< sal_uInt16 >(nBytes));
    }

    /** Construction.
    */
    explicit OStoreBTreeNodeData (sal_uInt16 nPageSize = self::thePageSize);

    /** guard (external representation).
    */
    void guard()
    {
        sal_uInt32 nCRC32 = 0;
        nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
        nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
        m_aGuard.m_nCRC32 = store::htonl(nCRC32);
    }

    /** verify (external representation).
    */
    storeError verify() const
    {
        sal_uInt32 nCRC32 = 0;
        nCRC32 = rtl_crc32 (nCRC32, &m_aGuard.m_nMagic, sizeof(sal_uInt32));
        nCRC32 = rtl_crc32 (nCRC32, m_pData, capacity());
        if (m_aGuard.m_nCRC32 != store::htonl(nCRC32))
            return store_E_InvalidChecksum;
        else
            return store_E_None;
    }

    /** depth.
    */
    sal_uInt32 depth (void) const
    {
        return store::ntohl(self::m_aGuard.m_nMagic);
    }
    void depth (sal_uInt32 nDepth)
    {
        self::m_aGuard.m_nMagic = store::htonl(nDepth);
    }

    /** queryMerge.
    */
    sal_Bool queryMerge (const self &rPageR) const
    {
        return ((usageCount() + rPageR.usageCount()) <= capacityCount());
    }

    /** querySplit.
    */
    sal_Bool querySplit (void) const
    {
        return (!(usageCount() < capacityCount()));
    }

    /** Operation.
    */
    sal_uInt16 find   (const T& t) const;
    void       insert (sal_uInt16 i, const T& t);
    void       remove (sal_uInt16 i);

#if 0  /* NYI */
    /** merge (with right page).
     */
    void merge (const self& rPageR);
#endif

    /** split (left half copied from right half of left page).
    */
    void split (const self& rPageL);

    /** truncate (to n elements).
    */
    void truncate (sal_uInt16 n);
};

/*========================================================================
 *
 * OStoreBTreeNodeObject.
 *
 *======================================================================*/
class OStoreBTreeNodeObject : public store::OStorePageObject
{
    typedef OStorePageObject      base;
    typedef OStoreBTreeNodeObject self;
    typedef OStoreBTreeNodeData   page;

    typedef OStoreBTreeEntry      T;

public:
    /** Construction.
    */
    explicit OStoreBTreeNodeObject (PageHolder const & rxPage = PageHolder())
        : OStorePageObject (rxPage)
    {}

    /** External representation.
    */
    virtual storeError guard  (sal_uInt32 nAddr);
    virtual storeError verify (sal_uInt32 nAddr) const;

    /** split.
     *
     *  @param rxPageL [inout] left child to be split
     */
    storeError split (
        sal_uInt16                 nIndexL,
        PageHolderObject< page > & rxPageL,
        OStorePageBIOS &           rBIOS);

    /** remove (down to leaf node, recursive).
    */
    storeError remove (
        sal_uInt16         nIndexL,
        OStoreBTreeEntry & rEntryL,
        OStorePageBIOS &   rBIOS);
};

/*========================================================================
 *
 * OStoreBTreeRootObject.
 *
 *======================================================================*/
class OStoreBTreeRootObject : public store::OStoreBTreeNodeObject
{
    typedef OStoreBTreeNodeObject base;
    typedef OStoreBTreeNodeData   page;

    typedef OStoreBTreeEntry      T;

public:
    /** Construction.
     */
    explicit OStoreBTreeRootObject (PageHolder const & rxPage = PageHolder())
        : OStoreBTreeNodeObject (rxPage)
    {}

    storeError loadOrCreate (
        sal_uInt32       nAddr,
        OStorePageBIOS & rBIOS);

    /** find_lookup (w/o split()).
     *  Precond: root node page loaded.
     */
    storeError find_lookup (
        OStoreBTreeNodeObject & rNode,  // [out]
        sal_uInt16 &            rIndex, // [out]
        OStorePageKey const &   rKey,
        OStorePageBIOS &        rBIOS);

    /** find_insert (possibly with split()).
     *  Precond: root node page loaded.
     */
    storeError find_insert (
        OStoreBTreeNodeObject & rNode,
        sal_uInt16 &            rIndex,
        OStorePageKey const &   rKey,
        OStorePageBIOS &        rBIOS);

private:
    /** testInvariant.
     *  Precond: root node page loaded.
     */
    bool testInvariant (char const * message);

    /** change (Root).
     *
     *  @param rxPageL [out] prev. root (needs split)
     */
    storeError change (
        PageHolderObject< page > & rxPageL,
        OStorePageBIOS &           rBIOS);
};

/*========================================================================
 *
 * The End.
 *
 *======================================================================*/

} // namespace store

#endif /* !_STORE_STORTREE_HXX */