bpTree_block.h

#ifndef BPTREE_BLOCK_H
#define BPTREE_BLOCK_H
 
#include "buffer/buffer_manager.h"
#include "share/config.h"
 
#include <cassert>
 
#define KEY_VALUE_T_DECLARE template<typename key_t, typename value_t>
#define MAPPING_T std::pair<key_t, value_t>
 
#define LEAF_HEADER_SIZE 24
#define INTERNAL_HEADER_SIZE 24
#define MAX_LEAF_SIZE ((BLOCKSIZE - LEAF_HEADER_SIZE) / sizeof(std::pair<key_t, value_t>) - 1)
#define MAX_INTERNAL_SIZE ((BLOCKSIZE - INTERNAL_HEADER_SIZE) / sizeof(std::pair<key_t, value_t>) - 1)
#define INVALID_BLOCK_ID -1
 
enum blockType_t{
    INVALID_BLOCK,
    LEAF_BLOCK,
    INTERNAL_BLOCK
};
 
struct bpTree_Block{
    void init(blockId_t myBId, blockId_t parentId){
        _blockType = INVALID_BLOCK;
        _parent_block_id = parentId;
        _block_id = myBId;
    }
 
    bool isLeaf() const{
        return _blockType == LEAF_BLOCK;
    }
 
    blockType_t _blockType;
    blockId_t _parent_block_id;
    blockId_t _block_id;
    db_size_t _size;
    db_size_t _max_size;
    blockId_t _next_block_id;
 
};
 
KEY_VALUE_T_DECLARE
struct bpTree_Leaf : public bpTree_Block{
    void init(blockId_t myBId, blockId_t parentId, blockId_t next_block_id){
        bpTree_Block::init(myBId, parentId);
        bpTree_Block::_blockType = LEAF_BLOCK;
        bpTree_Block::_next_block_id = next_block_id;
        bpTree_Block::_size = 0;
        bpTree_Block::_max_size = MAX_LEAF_SIZE;
    }
 
    db_size_t leaf_biSearch(const key_t key){
        int left = 0; // Every pair is used.
        if (_size == 0)
            return 0;
        int right = _size - 1;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if (_k_rowid_pair[mid].first < key){
                left = mid + 1;
            }
            else if (_k_rowid_pair[mid].first == key){
                return mid;
            }
            else{
                right = mid - 1;
            }
        }
        assert(left >= 0);
        return (db_size_t)left;
    }
 
    MAPPING_T _k_rowid_pair[MAX_LEAF_SIZE + 1]; 
};
 
KEY_VALUE_T_DECLARE
struct bpTree_Internal : public bpTree_Block{
public:
    void init(blockId_t myBId, blockId_t parentId){
        bpTree_Block::init(myBId, parentId);
        bpTree_Block::_blockType = INTERNAL_BLOCK;
 
        bpTree_Block::_size = 0;
        bpTree_Block::_max_size = MAX_INTERNAL_SIZE;
    }
 
    db_size_t internal_biSearch(const key_t key){
        db_size_t left = 1; // The first _k_child_pair doesn't contain a valid key.
        db_size_t right = _size - 1;
        db_size_t mid;
        while(left <= right){
            mid = (left + right + 1) / 2;
            if (_k_child_pair[mid].first < key){
                left = mid + 1;
            }
            else if (_k_child_pair[mid].first == key){
                return mid;
            }
            else{
                right = mid - 1;
            }
        }
        return right;
    }
 
    MAPPING_T _k_child_pair[MAX_INTERNAL_SIZE + 1]; 
};
 
 
 
#endif