#include <advanced_structures.hpp>

Collaboration diagram for advanced_structures::ChunkLSMTree< T >:

Classes
struct	Level

Public Member Functions
	ChunkLSMTree (size_t memtable_limit=1024, size_t ratio=4)

void	force_flush ()

void	insert (const T &value)

bool	search (const T &value) const

Private Member Functions
void	compact_level (size_t level_idx)

void	flush_memtable ()

Private Attributes
std::vector< std::shared_ptr< Level > >	levels

std::vector< T >	memtable

size_t	memtable_size_limit

size_t	size_ratio

Detailed Description

template<typename T>
class advanced_structures::ChunkLSMTree< T >

Definition at line 664 of file advanced_structures.hpp.

Constructor & Destructor Documentation

◆ ChunkLSMTree()

template<typename T >

advanced_structures::ChunkLSMTree< T >::ChunkLSMTree	(	size_t	memtable_limit = `1024`,
		size_t	ratio = `4`
	)

inline

Definition at line 732 of file advanced_structures.hpp.

733 : memtable_size_limit(memtable_limit), size_ratio(ratio) {}

advanced_structures::ChunkLSMTree::size_ratio

size_t size_ratio

Definition advanced_structures.hpp:680

advanced_structures::ChunkLSMTree::memtable_size_limit

size_t memtable_size_limit

Definition advanced_structures.hpp:679

Member Function Documentation

◆ compact_level()

template<typename T >

void advanced_structures::ChunkLSMTree< T >::compact_level ( size_t level_idx )

inlineprivate

Definition at line 682 of file advanced_structures.hpp.

                                         {
        if (level_idx >= levels.size() - 1) {
            // Create new level if we're at the last one
            levels.push_back(std::make_shared<Level>(levels[level_idx]->size_limit * size_ratio));
        }
 
        auto& current_level = levels[level_idx]->data;
        auto& next_level = levels[level_idx + 1]->data;
 
        // Merge current level into next level
        std::vector<T> merged;
        std::merge(current_level.begin(), current_level.end(), next_level.begin(), next_level.end(),
                   std::back_inserter(merged));
 
        // Update levels
        current_level.clear();
        next_level = std::move(merged);
 
        // If next level is full, compact it too
        if (levels[level_idx + 1]->is_full()) {
            compact_level(level_idx + 1);
        }
    }

References advanced_structures::ChunkLSMTree< T >::compact_level(), advanced_structures::ChunkLSMTree< T >::levels, and advanced_structures::ChunkLSMTree< T >::size_ratio.

Referenced by advanced_structures::ChunkLSMTree< T >::compact_level(), and advanced_structures::ChunkLSMTree< T >::flush_memtable().

◆ flush_memtable()

template<typename T >

void advanced_structures::ChunkLSMTree< T >::flush_memtable ( )

inlineprivate

Definition at line 706 of file advanced_structures.hpp.

                          {
        if (memtable.empty())
            return;
 
        // Sort memtable before flushing
        std::sort(memtable.begin(), memtable.end());
 
        if (levels.empty()) {
            levels.push_back(std::make_shared<Level>(memtable_size_limit * size_ratio));
        }
 
        // Merge memtable with first level
        std::vector<T> merged;
        std::merge(memtable.begin(), memtable.end(), levels[0]->data.begin(), levels[0]->data.end(),
                   std::back_inserter(merged));
 
        levels[0]->data = std::move(merged);
        memtable.clear();
 
        // If level 0 is full, trigger compaction
        if (levels[0]->is_full()) {
            compact_level(0);
        }
    }

References advanced_structures::ChunkLSMTree< T >::compact_level(), advanced_structures::ChunkLSMTree< T >::levels, advanced_structures::ChunkLSMTree< T >::memtable, advanced_structures::ChunkLSMTree< T >::memtable_size_limit, and advanced_structures::ChunkLSMTree< T >::size_ratio.

Referenced by advanced_structures::ChunkLSMTree< T >::force_flush(), and advanced_structures::ChunkLSMTree< T >::insert().

◆ force_flush()

template<typename T >

void advanced_structures::ChunkLSMTree< T >::force_flush ( )

inline

Definition at line 758 of file advanced_structures.hpp.

                       {
        flush_memtable();
    }

References advanced_structures::ChunkLSMTree< T >::flush_memtable().

◆ insert()

template<typename T >

void advanced_structures::ChunkLSMTree< T >::insert ( const T & value )

inline

Definition at line 735 of file advanced_structures.hpp.

                                {
        memtable.push_back(value);
 
        if (memtable.size() >= memtable_size_limit) {
            flush_memtable();
        }
    }

References advanced_structures::ChunkLSMTree< T >::flush_memtable(), advanced_structures::ChunkLSMTree< T >::memtable, and advanced_structures::ChunkLSMTree< T >::memtable_size_limit.

◆ search()

template<typename T >

bool advanced_structures::ChunkLSMTree< T >::search ( const T & value ) const

inline

Definition at line 743 of file advanced_structures.hpp.

                                      {
        // Search memtable first
        if (std::binary_search(memtable.begin(), memtable.end(), value)) {
            return true;
        }
 
        // Search through all levels
        for (const auto& level : levels) {
            if (std::binary_search(level->data.begin(), level->data.end(), value)) {
                return true;
            }
        }
        return false;
    }