btree_page.h

Go to the documentation of this file.

/*
 * (c) Copyright 2011-2014, Hewlett-Packard Development Company, LP
 */

#ifndef __BTREE_PAGE_H
#define __BTREE_PAGE_H

#include "fixable_page_h.h"
#include "vec_t.h"

class btree_page_data : public generic_page_header {
public:
    enum {
        hdr_sz = sizeof(generic_page_header) + 48,
        // 48 above must be kept in sync with size of headers below!
        // (checked by static asserts after class)

        data_sz = sizeof(generic_page) - hdr_sz,
    };

protected:
    // ======================================================================
    //   BEGIN: BTree but not item-specific headers
    // ======================================================================

    PageID btree_root;                         // +4 -> 4

    PageID btree_pid0;                         // +4 -> 8

    PageID btree_foster;                       // +4 -> 12

    int16_t btree_level;                        // +2 -> 14

    int16_t btree_fence_low_length;             // +2 -> 16

    int16_t btree_fence_high_length;            // +2 -> 18

    int16_t btree_chain_fence_high_length;      // +2 -> 20

    int16_t btree_prefix_length;                // +2 -> 22

    int16_t btree_consecutive_skewed_insertions; // +2 -> 24

    // ======================================================================
    //   END: BTree but not item-specific headers
    // ======================================================================


    // ======================================================================
    //   BEGIN: protected item interface
    // ======================================================================

    void init_items();

    // Remove the largest 'item_count' items from the storage area
    // It erases existing items from storage therefore use with caution
    // The function should only be called by full logging page rebalance
    // restart operation to recovery the source page
    // item_count - number of records to remove
    // high - the new high fence after record removal
    void remove_items(const int item_count, const w_keystr_t& high);

    int number_of_items() const {
        return nitems;
    }

    int number_of_ghosts() const {
        return nghosts;
    }

    bool is_ghost(int item) const;

    void set_ghost(int item);

    void unset_ghost(int item);

    typedef uint16_t poor_man_key;

    poor_man_key item_poor(int item) const;

    poor_man_key& item_poor(int item);

    PageID& item_child(int item);

    char* item_data(int item);

    size_t item_length(int item) const;

    bool insert_item(int item, bool ghost, poor_man_key poor, PageID child,
                     size_t data_length);

    bool insert_item(int item, bool ghost, poor_man_key poor, PageID child,
                     const cvec_t& data);

    bool resize_item(int item, size_t new_length, size_t keep_old);

    bool replace_item_data(int item, size_t offset, const cvec_t& new_data);

    void delete_item(int item);

    void delete_range(int from, int to);

    void truncate_all(size_t amount, size_t pos);

    size_t item_space(int item) const;

    size_t predict_item_space(size_t data_length) const;

    size_t usable_space() const;

    void compact();

    char* unused_part(size_t& length);

    static const size_t max_item_overhead;

    bool _items_are_consistent() const;

private:
// ======================================================================
//   BEGIN: private implementation details
// ======================================================================

    typedef uint16_t item_index_t;

    typedef uint16_t item_length_t;

    typedef int16_t body_offset_t;

    // ======================================================================
    //   BEGIN: item-specific headers
    // ======================================================================

    item_index_t nitems;                          // +2 -> 26

    item_index_t nghosts;                         // +2 -> 28

    body_offset_t first_used_body;                 // +2 -> 30

    uint16_t padding;                         // +2 -> 32

    // ======================================================================
    //   END: item-specific headers
    // ======================================================================

protected:
    // ======================================================================
    //   BEGIN: Single-Page-Recovery-related headers (placed at last so that frequently used
    //  headers like nitems are in the first 64 bytes (one cacheline).
    // ======================================================================
    lsn_t btree_pid0_emlsn;   // +8 -> 40

    lsn_t btree_foster_emlsn; // +8 -> 48
    // ======================================================================
    //   END: Single-Page-Recovery-related headers
    // ======================================================================

private:
    /*
     * The item space is organized as follows:
     *
     *   head_0 head_1 ... head_I  <possible gap> body_J body_J+1 ... body_N
     *
     * where head_i is a fixed sized value of type item_head that
     * contains the poor_man_key, the ghost bit, and a offset to a
     * starting item_body for item # i.  As items are added, space is
     * consumed on both sides of the gap: at the beginning for another
     * item_head and at the end for one or more item bodies to store
     * the remaining data, namely the variable-size data field and
     * (for interior nodes only) the child pointer.
     *
     * Here, I is nitems+1, J is first_used_body, and N is max_bodies-1.
     */

    typedef struct {
        body_offset_t offset;
        poor_man_key poor;
    } item_head;
    //static_assert(sizeof(item_head) == 4, "item_head has wrong length");
    BOOST_STATIC_ASSERT(sizeof(item_head) == 4);

    typedef struct {
        // item format depends on whether we are a leaf or not:
        union {
            struct {
                item_length_t item_len;
                char item_data[6];
            } leaf;
            struct {
                PageID child;
                item_length_t item_len;
                char item_data[2];
            } interior;
            int64_t _for_alignment_only;
        };
    } item_body;

    BOOST_STATIC_ASSERT(sizeof(item_body) == 8);

    BOOST_STATIC_ASSERT(data_sz % sizeof(item_body) == 0);
    enum {
        max_heads = data_sz / sizeof(item_head),
        max_bodies = data_sz / sizeof(item_body),
        leaf_overhead = sizeof(item_length_t),
        interior_overhead = sizeof(item_length_t) + sizeof(PageID),
    };

    union {
        item_head head[max_heads];
        item_body body[max_bodies];
    };
    // check field sizes are large enough:
    /*
     * #define here is a workaround for ebrowse cannot handle < in
     * marcos calls, numeric_limits::min() is not constant
     */
#define STATIC_LESS_THAN(x, y)  BOOST_STATIC_ASSERT((x) < (y))
    STATIC_LESS_THAN(data_sz, 1 << (sizeof(item_length_t) * 8));
    STATIC_LESS_THAN(max_heads, 1 << (sizeof(item_index_t) * 8));
    STATIC_LESS_THAN(max_bodies, 1 << (sizeof(body_offset_t) * 8 - 1)); // -1 for ghost bit


    bool is_leaf() const {
        return btree_level == 1;
    }

    static size_t _item_align(size_t i) {
        return (i + sizeof(item_body) - 1) & ~(sizeof(item_body) - 1);
    }

    size_t _item_body_overhead() const;

    item_length_t& _item_body_length(body_offset_t offset);

    item_length_t _item_body_length(body_offset_t offset) const;

    body_offset_t _item_bodies(body_offset_t offset) const;

public:
    friend std::ostream& operator<<(std::ostream&, btree_page_data&);

    bool eq(const btree_page_data&) const;
};

// forward references for friending test...
class ss_m;
class test_volume_t;

class btree_page : public btree_page_data {
    friend class btree_page_h;

    template<class T> friend class page_img_format_t; // for unused_part()
    friend class btree_split_log;

    // _ux_deadopt_foster_apply_foster_parent
    // _ux_adopt_foster_apply_child
    friend class btree_impl;
    friend class test_bf_tree;

    friend w_rc_t test_bf_fix_virgin_root(ss_m* /*ssm*/, test_volume_t* test_volume);

    // these are for access to headers from btree_page_headers:
    friend w_rc_t test_bf_fix_virgin_child(ss_m* /*ssm*/, test_volume_t* test_volume);

    friend w_rc_t test_bf_evict(ss_m* /*ssm*/, test_volume_t* test_volume);

    friend w_rc_t _test_bf_swizzle(ss_m* /*ssm*/, test_volume_t* test_volume, bool enable_swizzle);
};
//static_assert(sizeof(btree_page) == sizeof(generic_page),
//              "btree_page has wrong length");
BOOST_STATIC_ASSERT(sizeof(btree_page) == sizeof(generic_page));



/***************************************************************************/
/*                                                                         */
/* Rest of file is inlined method implementations                          */
/*                                                                         */
/***************************************************************************/

inline size_t btree_page_data::_item_body_overhead() const {
    if (is_leaf()) {
        return leaf_overhead;
    } else {
        return interior_overhead;
    }
}

inline btree_page_data::item_length_t& btree_page_data::_item_body_length(body_offset_t offset) {
    w_assert1(offset >= 0);
    if (is_leaf()) {
        return body[offset].leaf.item_len;
    } else {
        return body[offset].interior.item_len;
    }
}

inline btree_page_data::item_length_t btree_page_data::_item_body_length(body_offset_t offset) const {
    w_assert1(offset >= 0);
    if (is_leaf()) {
        return body[offset].leaf.item_len;
    } else {
        return body[offset].interior.item_len;
    }
}

inline btree_page_data::body_offset_t btree_page_data::_item_bodies(body_offset_t offset) const {
    w_assert1(offset >= 0);
    return _item_align(_item_body_length(offset)) / sizeof(item_body);
}

inline bool btree_page_data::is_ghost(int item) const {
    w_assert1(item >= 0 && item < nitems);
    return head[item].offset < 0;
}

inline btree_page_data::poor_man_key& btree_page_data::item_poor(int item) {
    w_assert1(item >= 0 && item < nitems);
    return head[item].poor;
}

inline btree_page_data::poor_man_key btree_page_data::item_poor(int item) const {
    w_assert1(item >= 0 && item < nitems);
    return head[item].poor;
}

inline PageID& btree_page_data::item_child(int item) {
    w_assert1(item >= 0 && item < nitems);
    w_assert1(!is_leaf());

    body_offset_t offset = head[item].offset;
    if (offset < 0) {
        offset = -offset;
    }
    return body[offset].interior.child;
}

inline char* btree_page_data::item_data(int item) {
    w_assert1(item >= 0 && item < nitems);
    body_offset_t offset = head[item].offset;
    if (offset < 0) {
        offset = -offset;
    }
    if (is_leaf()) {
        return body[offset].leaf.item_data;
    } else {
        return body[offset].interior.item_data;
    }
}

inline size_t btree_page_data::item_length(int item) const {
    w_assert1(item >= 0 && item < nitems);
    body_offset_t offset = head[item].offset;
    if (offset < 0) {
        offset = -offset;
    }

    int length;
    if (is_leaf()) {
        length = body[offset].leaf.item_len - leaf_overhead;
    } else {
        length = body[offset].interior.item_len - interior_overhead;
    }
    w_assert1(length >= 0);
    return length;
}

inline size_t btree_page_data::predict_item_space(size_t data_length) const {
    size_t body_length = data_length + _item_body_overhead();
    return _item_align(body_length) + sizeof(item_head);
}

inline size_t btree_page_data::item_space(int item) const {
    w_assert1(item >= 0 && item < nitems);
    body_offset_t offset = head[item].offset;
    if (offset < 0) {
        offset = -offset;
    }

    return _item_align(_item_body_length(offset)) + sizeof(item_head);
}

inline size_t btree_page_data::usable_space() const {
    w_assert1(first_used_body * sizeof(item_body) >= nitems * sizeof(item_head));
    return first_used_body * sizeof(item_body) - nitems * sizeof(item_head);
}

template<typename T>
inline T volatile& ACCESS_ONCE(T& t) {
    return static_cast<T volatile&>(t);
}

#endif // __BTREE_PAGE_H