BTree.hpp

Go to the documentation of this file.

#ifndef _BTREE_HPP_INCLUDED_
#define _BTREE_HPP_INCLUDED_

#include <cstdio>
#include <memory>

#include "Block.hpp"


template<typename T, std::size_t M, unsigned int BlockSize = BLOCK_SIZE>
class BTree {
public:
    typedef T ValueType;

    static constexpr auto Order = M;

    static constexpr auto BlockSizeInUse = BlockSize;


    BTree();
    

    ~BTree();
    

    bool create(const char* filepath);
    

    bool load(const char* filepath);
    

    void insert(const T& value);
    

    template <typename U>
    std::unique_ptr<T> seek(const U& key);
    
    struct Statistics {
        unsigned int blocksRead; 
        unsigned int blocksCreated; 
        unsigned int blocksInDisk; 
    };
    

    const Statistics& getStatistics(bool includeFileBlockCount = false) const;
    

    void resetStatistics();
    

    void finishInsertions();
    
private:
    struct FileHeader {
        long rootAddress;
        unsigned int blockCount;
    };

    typedef Block<FileHeader, BlockSize> FileHeaderBlock;
    
    struct BNode {

        long offset;
        bool isLeaf; 
        std::size_t size; 
        

        T values[2 * M + 1];
        

        long children[2 * M + 2];
        

        void initialize(bool isLeaf = true, int size = 0);
        

        bool isFull() const;
        

        template <typename U>
        std::unique_ptr<T> seek(const U& key, BTree& tree) const;
    };

    typedef Block<BNode, BlockSize> BNodeBlock;

    std::FILE *m_file; 
    BNodeBlock m_root; 
    mutable Statistics m_stats; 
    

    BNodeBlock readFromDisk(long offset);
    

    void writeToDisk(BNodeBlock& node);
    

    FileHeaderBlock readHeader() const;
    

    void writeHeader(const FileHeaderBlock& header);
    
    struct OverflowResult {
        T middle; 
        long rightNode; 
    };
    

    std::unique_ptr<OverflowResult> insert(BNodeBlock& node, T value, long rightNodeOffset = -1);
};

#include "BTree.inl"

#endif // _BTREE_HPP_INCLUDED_