BTreeInternal.h

Go to the documentation of this file.

#ifndef INDEX_BTREE_BTREEINTERNAL_H
#define INDEX_BTREE_BTREEINTERNAL_H
 
#include "tdb.h"
 
#include "index/btree/BTree.h"
#include "storage/Record.h"
#include "storage/VarlenDataPage.h"
 
namespace taco {
 
static const RecordId INFINITY_RECORDID = { RESERVED_PID, MaxSlotId };
 
struct BTreeMetaPageData {
    PageHeaderData  m_ph;
 
    PageNumber      m_root_pid;
 
    static void Initialize(char *btmeta_buf, PageNumber root_pid);
};
 
constexpr uint16_t BTREE_PAGE_ISROOT = 1u;
constexpr uint16_t BTREE_PAGE_ISLEAF = 2u;
 
struct BTreePageHeaderData {
 
    uint16_t        m_flags;
 
    FieldOffset     m_totrlen;
 
    PageNumber      m_prev_pid;
 
    PageNumber      m_next_pid;
 
    uint32_t        m_reserved;
 
    constexpr bool
    IsRootPage() const {
        return m_flags & BTREE_PAGE_ISROOT;
    }
 
    constexpr bool
    IsLeafPage() const {
        return m_flags & BTREE_PAGE_ISLEAF;
    }
 
    static void Initialize(char *pagebuf,
                           uint16_t flags,
                           PageNumber prev_pid,
                           PageNumber next_pid);
};
 
constexpr size_t BTreePageHeaderSize = sizeof(BTreePageHeaderData);
 
struct BTreeInternalRecordHeaderData {
    PageNumber      m_child_pid;
 
    uint32_t        m_reserved;
 
    RecordId        m_heap_recid;
 
    char*
    GetPayload() const {
        return const_cast<char*>(reinterpret_cast<const char*>(this)) +
            MAXALIGN(sizeof(BTreeInternalRecordHeaderData));
    }
};
 
constexpr size_t BTreeInternalRecordHeaderSize =
    MAXALIGN(sizeof(BTreeInternalRecordHeaderData));
 
struct BTreeLeafRecordHeaderData {
    RecordId        m_recid;
 
    char*
    GetPayload() const {
        return const_cast<char*>(reinterpret_cast<const char*>(this)) +
            MAXALIGN(sizeof(BTreeLeafRecordHeaderData));
    }
};
 
constexpr size_t BTreeLeafRecordHeaderSize =
    MAXALIGN(sizeof(BTreeLeafRecordHeaderData));
 
static inline char*
BTreeRecordGetPayload(char* recbuf, bool isleaf) {
    if (isleaf) {
        return ((BTreeLeafRecordHeaderData*) recbuf)->GetPayload();
    } else {
        return ((BTreeInternalRecordHeaderData*) recbuf)->GetPayload();
    }
}
 
static inline const char*
BTreeRecordGetPayload(const char* recbuf, bool isleaf) {
    return BTreeRecordGetPayload(const_cast<char*>(recbuf), isleaf);
}
 
static inline const RecordId&
BTreeRecordGetHeapRecordId(const char *recbuf, bool isleaf) {
    if (isleaf) {
        return ((const BTreeLeafRecordHeaderData*) recbuf)->m_recid;
    } else {
        return ((const BTreeInternalRecordHeaderData*) recbuf)->m_heap_recid;
    }
}
 
static inline FieldOffset
BTreeComputePageUsage(SlotId num_recs, FieldOffset totrlen) {
    return ((FieldOffset) PAGE_SIZE) -
        VarlenDataPage::ComputeFreeSpace(BTreePageHeaderSize,
            num_recs, totrlen);
}
 
// This should be enough for fitting at least 3 internal records on an internal
// pages, or 2 leaf records on a leaf page, for 4KB pages.
//
// XXX This is not computed from VarlenDataPage impl because it's inconvenient
// to mark VarlenDataPage::ComputeFreeSpace() as constexpr in C++11 where
// constexpr function can only have one return statement (plus a few
// declarations).
// This should be computed as VarlenDataPage::BTreeComputePageUsage(3, 3 *
// BTreeInternalRecordHeaderData::HeaderSize) / 2, if we switch to C++14 or
// later C++ standard. (Note we do not need to store the first key on an
// internal page, hence / 2).
constexpr FieldOffset BTREE_MAX_RECORD_SIZE = 2000;
 
constexpr FieldOffset BTREE_MIN_PAGE_USAGE = (FieldOffset) (PAGE_SIZE * 0.4);
 
}   // namespace taco
 
#endif      // INDEX_BTREE_BTREEINTERNAL_H