An implementation of B+-tree. More...

#include <bp_tree.hpp>

Public Types
using	NodePointer = BPNodePointer< LEAF_CONTAINER, VALUE, MAX_DEGREE >

using	Node = BPInternalNode< LEAF_CONTAINER, VALUE, MAX_DEGREE >

using	PostorderIterator = BPPostorderIterator< LEAF_CONTAINER, VALUE, MAX_DEGREE >

using	ValueForwardIterator = BPValueForwardIterator< LEAF_CONTAINER, VALUE, MAX_DEGREE >

using	LeafForwardIterator = BPLeafForwardIterator< LEAF_CONTAINER, VALUE, MAX_DEGREE >

using	BPFunctions = BPInternalNodeFunctions< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE >

Public Member Functions
	BPTree (const BPTree &)=delete

	BPTree (BPTree &&other) noexcept

BPTree &	operator= (BPTree &&other) noexcept

Initializers
void	initialize ()
	Initializes the B+ tree with specified maximum degrees for internal nodes and leaf nodes.

void	swap (BPTree &_tree, bool swap_linked_tree)
	Swaps the contents of this B+ tree with another B+ tree.

void	swap (BPTree &_tree)
	Swaps the contents of this B+ tree with another B+ tree.

void	clear ()
	Clears all contents of the B+ tree and resets it to an empty state.

Properties
The properties of this class.
const std::vector< NodePointer > &	get_temporary_path () const
	Returns the temporary path used during tree operations.

uint64_t	get_max_degree_of_internal_node () const
	Return the max degree of this tree. The number of children of every internal node does not exceed the max degree.

uint64_t	get_split_process_counter () const

uint64_t	capacity () const

double	get_value_density () const

uint64_t	get_max_count_of_values_in_leaf () const
	Returns the maximum number of values that can be stored in a leaf node.

uint64_t	height () const
	Return the height of this tree.

uint64_t	size () const
	Return the number of values stored in this tree.

uint64_t	get_leaf_count () const
	Return the number of leaves in this tree.

uint64_t	get_leaf_container_vector_size () const
	Return the size of the vector that stores leaf containers.

Convertion functions
Convertion functions
std::vector< VALUE >	to_value_vector () const
	Converts the B+ tree to a vector of values.

Const print and verification functions
Const print functions
bool	verify_sub () const

void	verify_sum_deque (Node *node) const

bool	verify () const
	Verifies the integrity of the B+ tree.

void	print_tree () const
	Prints the B+ tree in a tree-like format.

void	print_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints detailed information about the B+ tree.

void	print_leaves () const
	Prints the leaves of the B+ tree.

void	print_internal_nodes () const

void	print_leaf_containers () const
	Prints the leaf containers of the B+ tree.

uint64_t	size_in_bytes () const
	Returns the total memory size of the B+ tree.

uint64_t	compute_internal_node_count () const
	Returns the number of internal nodes in the B+ tree.

uint64_t	compute_leaf_container_count () const
	Returns the number of leaf containers in the B+ tree.

uint64_t	get_internal_node_memory () const
	Returns the memory size of the internal nodes in the B+ tree.

uint64_t	get_unused_leaf_container_vector_memory () const
	Returns the memory size of the unused leaf container vector in the B+ tree.

uint64_t	get_leaf_container_vector_memory () const
	Returns the memory size of the leaf container vector in the B+ tree.

uint64_t	get_leaf_container_memory () const
	Returns the memory size of the leaf containers in the B+ tree.

uint64_t	get_leaf_container_unused_memory () const

uint64_t	get_unused_node_pointers_memory () const
	Returns the memory size of the unused node pointers in the B+ tree.

uint64_t	get_parent_vector_memory () const
	Returns the memory size of the parent vector in the B+ tree.

std::vector< std::string >	get_memory_usage_info (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Returns a vector of strings containing memory usage information about the B+ tree.

void	print_memory_usage (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints the memory usage information of the B+ tree.

Const private functions
Const private functions
void	get_path_from_root_to_first_leaf (std::vector< NodePointer > &output_path) const
	Returns a vector of NodePointer objects representing the path from the root to the first leaf.

void	get_path_from_root_to_last_leaf (std::vector< NodePointer > &output_path) const
	Returns a vector of NodePointer objects representing the path from the root to the last leaf.

int64_t	compute_path_from_root_to_leaf (uint64_t i) const
	Computes the path from the root to the leaf at position i.

int64_t	compute_path_from_root_to_leaf (uint64_t i, std::vector< NodePointer > &output_path) const
	Computes the path from root to leaf containing position i and returns leaf position.

Public standard functions
Public standard functions
static uint64_t	time_count = 0

PostorderIterator	get_postorder_iterator_begin () const
	Returns an iterator pointing to the first node in postorder traversal.

PostorderIterator	get_postorder_iterator_end () const
	Returns an iterator pointing to the end of postorder traversal.

ValueForwardIterator	get_value_forward_iterator_begin () const
	Returns an iterator pointing to the first value in forward traversal.

ValueForwardIterator	get_value_forward_iterator_end () const
	Returns an iterator pointing to the end of forward value traversal.

LeafForwardIterator	get_leaf_forward_iterator_begin () const
	Returns an iterator pointing to the first leaf in forward traversal.

LeafForwardIterator	get_leaf_forward_iterator_end () const
	Returns an iterator pointing to the end of forward leaf traversal.

bool	empty () const
	Checks if the B+ tree is empty.

uint64_t	psum () const
	Returns the prefix sum of the B+ tree.

uint64_t	psum (uint64_t i) const
	Returns the prefix sum of the B+ tree at position i.

int64_t	select0 (uint64_t i) const
	Returns the position of the i-th 0 in the B+ tree.

int64_t	search (uint64_t sum) const
	Returns the position of the sum in the B+ tree.

VALUE	at (uint64_t pos) const
	Returns the value at position pos in the B+ tree.

uint64_t	get_value_index (uint64_t leaf_index, uint64_t position_in_leaf_container) const
	Returns the value index at position pos in the B+ tree.

const LEAF_CONTAINER &	get_leaf_container (uint64_t leaf_index) const
	Returns the leaf container at position leaf_index.

LEAF_CONTAINER &	get_leaf_container (uint64_t leaf_index)
	Returns a reference to the leaf container at position leaf_index.

Non-const public functions
Non-const public functions
void	push_back (VALUE value)
	Pushes a single value to the B+ tree.

void	push_front (VALUE value)
	Inserts a value at the front of the B+ tree.

void	push_many (std::vector< LEAF_CONTAINER > &containers)
	Pushes multiple leaf containers into the B+ tree.

void	push_many (const std::vector< VALUE > &values)
	Pushes multiple values into the B+ tree.

uint64_t	remove_using_path (const std::vector< NodePointer > &path, uint64_t position_in_leaf_container)
	Removes a value at a specific position using a path to the leaf.

void	remove (uint64_t pos)
	Removes a value at a specific position in the B+ tree.

void	insert (uint64_t pos, VALUE value, uint64_t sum_delta)
	Inserts a value at a specific position in the B+ tree.

void	resize (uint64_t _size, VALUE default_value)
	Resizes the B+ tree to contain a specified number of elements.

void	set_linked_tree (BPTree *_tree)
	Sets the linked B+ tree.

BPTree *	get_linked_tree () const
	Gets the linked B+ tree.

Non-const private functions for updating nodes
Non-const private functions for updating nodes
void	move_values_right (Node left_node, Node right_node, uint64_t len, bool is_leaf, Node *parent, int64_t parent_edge_index_of_left_node)
	Moves values from a left node to a right node in the B+ tree.

void	move_values_left (Node left_node, Node right_node, uint64_t len, bool is_leaf, Node *parent, int64_t parent_edge_index_of_right_node)
	Moves values from a right node to a left node in the B+ tree.

void	split_node (Node left_node, Node right_node, bool is_leaf, Node parent, int64_t parent_edge_index_of_left_node, std::vector< Node > &parent_vec)
	Splits a node into two nodes in the B+ tree.

void	increment (uint64_t i, int64_t delta)
	Increments a value at a given position in the B+ tree.

bool	check_if_leaf_container_vec_is_sorted () const
	Checks if the leaf containers in the B+ tree are sorted.

void	print_debug_info () const

void	sort_leaf_containers ()
	Sorts the leaf containers in the B+ tree.

std::vector< Node * >	build_from_leaf_containers_sub2 (std::vector< Node * > &nodes, uint64_t current_height)
	Builds a layer of internal nodes from a vector of child nodes.

std::vector< Node * >	build_from_leaf_containers_sub1 ()
	Creates the first layer of internal nodes from leaf containers.

void	build_sub (const std::vector< VALUE > &_values)
	Creates leaf containers from a vector of values.

void	build (const std::vector< VALUE > &_values)
	Builds a complete B+ tree from a vector of values.

void	build_from_leaf_containers (std::vector< LEAF_CONTAINER > &_leaf_containers)
	Builds a B+ tree from a vector of leaf containers.

void	save (std::vector< uint8_t > &output, uint64_t &pos)
	Saves the B+ tree structure to a byte vector.

void	save (std::ofstream &os)
	Saves the B+ tree structure to a file stream.

void	build_from_data (const std::vector< uint8_t > &data, uint64_t &pos)
	Builds a B+ tree from serialized data in a byte vector.

void	build_from_data (std::ifstream &ifs)
	Builds a B+ tree from serialized data in a file stream.

void	print_information_about_performance (int message_paragraph=stool::Message::SHOW_MESSAGE) const

void	print_statistics (int message_paragraph=stool::Message::SHOW_MESSAGE) const
	Prints statistical information about the B+ tree.

Detailed Description

template<typename LEAF_CONTAINER, typename VALUE, bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>
class stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >

An implementation of B+-tree.

Member Function Documentation

◆ at()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

VALUE stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::at ( uint64_t pos ) const

inline

Returns the value at position pos in the B+ tree.

Parameters

pos	The position in the B+ tree

Returns: The value at position pos in the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build ( const std::vector< VALUE > & _values )

inline

Builds a complete B+ tree from a vector of values.

Parameters

_values Vector of values to build the tree from

This function constructs a complete B+ tree by:

Clearing any existing tree structure
Creating leaf containers from input values
Building internal node layers bottom-up
Setting root and updating tree properties

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build_from_data() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build_from_data	(	const std::vector< uint8_t > &	data,
		uint64_t &	pos
	)

inline

Builds a B+ tree from serialized data in a byte vector.

Parameters

data	Vector containing the serialized tree data
pos	Starting position in the data vector

This function reconstructs the tree by:

Clearing any existing tree structure
Reading tree parameters
Loading leaf containers
Rebuilding the tree structure

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build_from_data() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build_from_data ( std::ifstream & ifs )

inline

Builds a B+ tree from serialized data in a file stream.

Parameters

ifs	Input file stream to read from

This function reconstructs the tree by:

Clearing any existing tree structure
Reading tree parameters
Loading leaf containers from the file
Rebuilding the tree structure

Here is the call graph for this function:

◆ build_from_leaf_containers()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build_from_leaf_containers ( std::vector< LEAF_CONTAINER > & _leaf_containers )

inline

Builds a B+ tree from a vector of leaf containers.

Parameters

_leaf_containers Vector of leaf containers to build the tree from

This function constructs a B+ tree by:

Clearing any existing tree structure
Swapping the input leaf containers into the tree
Building internal node layers bottom-up
Setting root and updating tree properties

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build_from_leaf_containers_sub1()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

std::vector< Node * > stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build_from_leaf_containers_sub1 ( )

inline

Creates the first layer of internal nodes from leaf containers.

Returns: Vector of newly created internal nodes

This function builds the first layer of internal nodes by:

Handling empty tree case
Handling single leaf case
Creating parent nodes for multiple leaves Updates parent pointers and node counts/sums as needed.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ build_from_leaf_containers_sub2()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

std::vector< Node * > stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build_from_leaf_containers_sub2	(	std::vector< Node * > &	nodes,
		uint64_t	current_height
	)

inline

Builds a layer of internal nodes from a vector of child nodes.

Parameters

nodes	Vector of child nodes to build from
current_height	Current height of the tree being built

Returns: Vector of newly created parent nodes

This function creates a new layer of internal nodes by:

If only one child node, sets it as root
If children fit in one node, creates single parent node
Otherwise distributes children across multiple parent nodes Updates parent pointers and node counts/sums as needed.

Here is the caller graph for this function:

◆ build_sub()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::build_sub ( const std::vector< VALUE > & _values )

inline

Creates leaf containers from a vector of values.

Parameters

_values Vector of values to build leaf containers from

This function distributes values across leaf containers by:

Handling empty input case
Creating single leaf for small number of values
Distributing values across multiple leaves for larger inputs Maintains balanced leaf sizes according to tree parameters.

Here is the caller graph for this function:

◆ check_if_leaf_container_vec_is_sorted()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

bool stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::check_if_leaf_container_vec_is_sorted ( ) const

inline

Checks if the leaf containers in the B+ tree are sorted.

Returns: true if leaf containers are in sorted order, false otherwise

This function verifies that the leaf container indices are in sequential order by:

Iterating through all leaf containers using forward iterator
Checking that each container index is exactly one more than previous
Returns false if any gap in sequence is found

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::clear ( )

inline

Clears all contents of the B+ tree and resets it to an empty state.

This function:

Deletes all nodes in the tree using a stack-based traversal
Clears the root pointer and resets root state flags
Deletes any unused node pointers that were cached
Clears the leaf container and parent vectors
Empties the unused leaf container index queue
Resets the tree height to 0 After calling clear(), the tree will be in an empty state ready for new insertions.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_internal_node_count()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::compute_internal_node_count ( ) const

inline

Returns the number of internal nodes in the B+ tree.

Returns: The number of internal nodes in the B+ tree

Here is the call graph for this function:

◆ compute_leaf_container_count()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::compute_leaf_container_count ( ) const

inline

Returns the number of leaf containers in the B+ tree.

Returns: The number of leaf containers in the B+ tree

Here is the call graph for this function:

◆ compute_path_from_root_to_leaf() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::compute_path_from_root_to_leaf ( uint64_t i ) const

inline

Computes the path from the root to the leaf at position i.

Parameters

i	The position of the leaf

Returns: The position of the leaf in the path

This function computes the path from the root to the leaf at position i in the B+ tree. If the tree is empty, it returns -1.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ compute_path_from_root_to_leaf() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::compute_path_from_root_to_leaf	(	uint64_t	i,
		std::vector< NodePointer > &	output_path
	)		const

inline

Computes the path from root to leaf containing position i and returns leaf position.

Parameters

i	The position in the B+ tree to find the path to
output_path	Vector to store the path from root to leaf

Returns: The position within the leaf node, or -1 if tree is empty

This function computes the path from the root to the leaf node containing position i in the B+ tree. The path is stored in output_path as a sequence of NodePointers. Each NodePointer contains either an internal node or leaf pointer along with its parent edge index. The function returns the position within the final leaf node where value i is located.

Here is the call graph for this function:

◆ empty()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

bool stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::empty ( ) const

inline

Checks if the B+ tree is empty.

Returns: true if the tree is empty, false otherwise

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_internal_node_memory()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_internal_node_memory ( ) const

inline

Returns the memory size of the internal nodes in the B+ tree.

Returns: The memory size of the internal nodes in the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_leaf_container() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

LEAF_CONTAINER & stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_leaf_container ( uint64_t leaf_index )

inline

Returns a reference to the leaf container at position leaf_index.

Parameters

leaf_index The position of the leaf container

Returns: A reference to the leaf container at position leaf_index

Here is the call graph for this function:

◆ get_leaf_container() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

const LEAF_CONTAINER & stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_leaf_container ( uint64_t leaf_index ) const

inline

Returns the leaf container at position leaf_index.

Parameters

leaf_index The position of the leaf container

Returns: The leaf container at position leaf_index

◆ get_leaf_container_memory()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_leaf_container_memory ( ) const

inline

Returns the memory size of the leaf containers in the B+ tree.

Returns: The memory size of the leaf containers in the B+ tree

Here is the caller graph for this function:

◆ get_leaf_container_vector_memory()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_leaf_container_vector_memory ( ) const

inline

Returns the memory size of the leaf container vector in the B+ tree.

Returns: The memory size of the leaf container vector in the B+ tree

Here is the caller graph for this function:

◆ get_leaf_forward_iterator_begin()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

LeafForwardIterator stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_leaf_forward_iterator_begin ( ) const

inline

Returns an iterator pointing to the first leaf in forward traversal.

This function returns a LeafForwardIterator that points to the first leaf when traversing the tree in forward order. If the tree is empty, returns an iterator pointing to nullptr. Otherwise returns an iterator pointing to the root.

Returns: LeafForwardIterator pointing to the first leaf

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_leaf_forward_iterator_end()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

LeafForwardIterator stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_leaf_forward_iterator_end ( ) const

inline

Returns an iterator pointing to the end of forward leaf traversal.

This function returns a LeafForwardIterator that represents the end of the forward leaf traversal sequence (nullptr)

Returns: LeafForwardIterator pointing to nullptr

Here is the caller graph for this function:

◆ get_linked_tree()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

BPTree * stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_linked_tree ( ) const

inline

Gets the linked B+ tree.

Returns: Pointer to the linked B+ tree

Returns the pointer to the B+ tree that was previously linked using set_linked_tree()

◆ get_max_count_of_values_in_leaf()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_max_count_of_values_in_leaf ( ) const

inline

Returns the maximum number of values that can be stored in a leaf node.

Returns: The maximum number of values that can be stored in a leaf node

Here is the caller graph for this function:

◆ get_memory_usage_info()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

std::vector< std::string > stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_memory_usage_info ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Returns a vector of strings containing memory usage information about the B+ tree.

Parameters

message_paragraph The paragraph number for the message

Returns: A vector of strings containing memory usage information

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_parent_vector_memory()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_parent_vector_memory ( ) const

inline

Returns the memory size of the parent vector in the B+ tree.

Returns: The memory size of the parent vector in the B+ tree

Here is the caller graph for this function:

◆ get_path_from_root_to_first_leaf()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_path_from_root_to_first_leaf ( std::vector< NodePointer > & output_path ) const

inline

Returns a vector of NodePointer objects representing the path from the root to the first leaf.

Parameters

output_path The vector to store the path

This function constructs a path from the root to the first leaf in the B+ tree. If the tree is empty, the output path remains empty.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_path_from_root_to_last_leaf()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_path_from_root_to_last_leaf ( std::vector< NodePointer > & output_path ) const

inline

Returns a vector of NodePointer objects representing the path from the root to the last leaf.

Parameters

output_path The vector to store the path

This function constructs a path from the root to the last leaf in the B+ tree. If the tree is empty, the output path remains empty.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_postorder_iterator_begin()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

PostorderIterator stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_postorder_iterator_begin ( ) const

inline

Returns an iterator pointing to the first node in postorder traversal.

This function returns a PostorderIterator that points to the first node when traversing the tree in postorder (left-right-root). If the tree is empty, returns an iterator pointing to nullptr. If the root is a leaf, returns an iterator pointing to the root leaf container index. Otherwise returns an iterator pointing to the root node.

Returns: PostorderIterator pointing to the first node in postorder traversal

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_postorder_iterator_end()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

PostorderIterator stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_postorder_iterator_end ( ) const

inline

Returns an iterator pointing to the end of postorder traversal.

This function returns a PostorderIterator that represents the end of the postorder traversal sequence (nullptr)

Returns: PostorderIterator pointing to nullptr

Here is the caller graph for this function:

◆ get_temporary_path()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

const std::vector< NodePointer > & stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_temporary_path ( ) const

inline

Returns the temporary path used during tree operations.

Returns: A reference to the vector containing temporary path nodes

◆ get_unused_leaf_container_vector_memory()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_unused_leaf_container_vector_memory ( ) const

inline

Returns the memory size of the unused leaf container vector in the B+ tree.

Returns: The memory size of the unused leaf container vector in the B+ tree

Here is the caller graph for this function:

◆ get_unused_node_pointers_memory()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_unused_node_pointers_memory ( ) const

inline

Returns the memory size of the unused node pointers in the B+ tree.

Returns: The memory size of the unused node pointers in the B+ tree

Here is the caller graph for this function:

◆ get_value_forward_iterator_begin()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

ValueForwardIterator stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_value_forward_iterator_begin ( ) const

inline

Returns an iterator pointing to the first value in forward traversal.

This function returns a ValueForwardIterator that points to the first value when traversing the tree in forward order. If the tree is empty, returns an iterator pointing to nullptr. Otherwise returns an iterator initialized with the first node in postorder and the leaf container vector.

Returns: ValueForwardIterator pointing to the first value

Here is the call graph for this function:

Here is the caller graph for this function:

◆ get_value_forward_iterator_end()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

ValueForwardIterator stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_value_forward_iterator_end ( ) const

inline

Returns an iterator pointing to the end of forward value traversal.

This function returns a ValueForwardIterator that represents the end of the forward value traversal sequence (nullptr)

Returns: ValueForwardIterator pointing to nullptr

Here is the caller graph for this function:

◆ get_value_index()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::get_value_index	(	uint64_t	leaf_index,
		uint64_t	position_in_leaf_container
	)		const

inline

Returns the value index at position pos in the B+ tree.

Parameters

pos	The position in the B+ tree

Returns: The value index at position pos in the B+ tree

◆ increment()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::increment	(	uint64_t	i,
		int64_t	delta
	)

inline

Increments a value at a given position in the B+ tree.

Parameters

i	The position in the B+ tree where the value should be incremented
delta	The amount to increment the value by

This function:

Computes the path to the leaf containing position i
Increments the value in the leaf container
Updates prefix sums in all parent nodes along the path The increment operation maintains the tree's prefix sum property.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ initialize()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::initialize ( )

inline

Initializes the B+ tree with specified maximum degrees for internal nodes and leaf nodes.

Exceptions

std::runtime_error if either parameter is less than 4

This function initializes a new empty B+ tree with the given parameters. Both parameters must be at least 4 to maintain B+ tree properties. The function clears any existing data before initialization.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ insert()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::insert	(	uint64_t	pos,
		VALUE	value,
		uint64_t	sum_delta
	)

inline

Inserts a value at a specific position in the B+ tree.

Parameters

pos	Position to insert value
value	Value to insert
sum_delta	Change in prefix sum for parent updates

This function:

Handles insertion at any valid position
Creates root leaf if tree is empty
Updates prefix sums and counts in parent nodes
Rebalances tree if needed
Appends value if position equals tree size

Here is the call graph for this function:

Here is the caller graph for this function:

◆ move_values_left()

void stool::___PermutationTree::move_values_left	(	Node *	left_node,
		Node *	right_node,
		uint64_t	len,
		bool	is_leaf,
		Node *	parent,
		int64_t	parent_edge_index_of_right_node
	)

inline

Moves values from a right node to a left node in the B+ tree.

Parameters

left_node	Pointer to the left node
right_node	Pointer to the right node
len	Number of values to move
is_leaf	True if nodes are leaves, false if internal nodes
parent	Pointer to the parent node
parent_edge_index_of_right_node	Index of right node in parent's children

This function moves len values from right_node to left_node. For leaf nodes, it moves values between leaf containers and updates parent prefix sums and counts. For internal nodes, it delegates to BPFunctions::move_left().

◆ move_values_right()

void stool::___PermutationTree::move_values_right	(	Node *	left_node,
		Node *	right_node,
		uint64_t	len,
		bool	is_leaf,
		Node *	parent,
		int64_t	parent_edge_index_of_left_node
	)

inline

Moves values from a left node to a right node in the B+ tree.

Parameters

left_node	Pointer to the left node
right_node	Pointer to the right node
len	Number of values to move
is_leaf	True if nodes are leaves, false if internal nodes
parent	Pointer to the parent node
parent_edge_index_of_left_node	Index of left node in parent's children

This function moves len values from left_node to right_node. For leaf nodes, it moves values between leaf containers and updates parent prefix sums and counts. For internal nodes, it delegates to BPFunctions::move_right().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print_info()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_info ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Prints detailed information about the B+ tree.

This function prints the height of the tree, the number of internal nodes, and the number of leaf containers. It also prints the contents of each leaf container and the parent vector if USE_PARENT_FIELD is true.

Here is the call graph for this function:

◆ print_leaf_containers()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_leaf_containers ( ) const

inline

Prints the leaf containers of the B+ tree.

This function prints the leaf containers of the B+ tree, where each leaf container is represented by its index and its contents. If the tree is empty, it prints an empty string.

◆ print_leaves()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_leaves ( ) const

inline

Prints the leaves of the B+ tree.

This function prints the leaves of the B+ tree, where each leaf is represented by its index and its contents. If the tree is empty, it prints an empty string.

Here is the call graph for this function:

◆ print_memory_usage()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_memory_usage ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Prints the memory usage information of the B+ tree.

Parameters

message_paragraph The paragraph number for the message

This function prints the memory usage information of the B+ tree, where each line is printed with the specified message paragraph number.

Here is the call graph for this function:

◆ print_statistics()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_statistics ( int message_paragraph = stool::Message::SHOW_MESSAGE ) const

inline

Prints statistical information about the B+ tree.

Parameters

message_paragraph Indentation level for output messages (default: stool::Message::SHOW_MESSAGE)

This function prints detailed statistics about the B+ tree structure including:

Number of internal nodes and leaf containers
Tree height and total number of stored values
Maximum and average degrees of internal nodes
Maximum and average number of values in leaf nodes
Number of unused nodes and leaf containers
Number of parent pointers stored
Estimated memory usage in bytes The statistics are printed with proper indentation based on message_paragraph parameter.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ print_tree()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::print_tree ( ) const

inline

Prints the B+ tree in a tree-like format.

This function prints the B+ tree in a tree-like format, where each internal node is represented by its value and its children are printed on the next line. If the tree is empty, it prints an empty string.

Here is the call graph for this function:

◆ psum() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::psum ( ) const

inline

Returns the prefix sum of the B+ tree.

Returns: The prefix sum of the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ psum() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::psum ( uint64_t i ) const

inline

Returns the prefix sum of the B+ tree at position i.

Parameters

i	The position in the B+ tree

Returns: The prefix sum of the B+ tree at position i

Here is the call graph for this function:

◆ push_back()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_back ( VALUE value )

inline

Pushes a single value to the B+ tree.

Parameters

value The value to be pushed

This function pushes a single value to the B+ tree by creating a vector with the value and calling push_many() with the vector.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_front()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_front ( VALUE value )

inline

Inserts a value at the front of the B+ tree.

Parameters

value The value to be inserted at the front

This function inserts a value at the beginning of the B+ tree by:

Finding the path to the first leaf node
Inserting the value at the front of that leaf
Updating parent node counts and prefix sums
Rebalancing the tree if needed If the tree is empty, creates a new root leaf node with the value.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push_many() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_many ( const std::vector< VALUE > & values )

inline

Pushes multiple values into the B+ tree.

Parameters

values Vector of values to insert

This function iteratively:

Gets path to last leaf node
If path exists, pushes values to leaf node
If tree is empty, creates root leaf with first value
Continues until all values are inserted

Here is the call graph for this function:

◆ push_many() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::push_many ( std::vector< LEAF_CONTAINER > & containers )

inline

Pushes multiple leaf containers into the B+ tree.

Parameters

containers Vector of leaf containers to insert

This function iteratively:

Gets path to last leaf node
If path length > 1, creates new container and appends to internal node
If path length = 1, converts container to values and pushes individually
Continues until all containers are inserted

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::remove ( uint64_t pos )

inline

Removes a value at a specific position in the B+ tree.

Parameters

pos	Position of value to remove

Exceptions

std::invalid_argument if tree is empty

This function:

Computes path to leaf containing position
Removes value using computed path
Throws exception if tree is empty

Here is the call graph for this function:

Here is the caller graph for this function:

◆ remove_using_path()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::remove_using_path	(	const std::vector< NodePointer > &	path,
		uint64_t	position_in_leaf_container
	)

inline

Removes a value at a specific position using a path to the leaf.

Parameters

path	Vector of NodePointers representing path from root to leaf
position_in_leaf_container	Position in leaf container to remove

This function:

Removes value from leaf container
Updates prefix sums and counts in parent nodes
Rebalances tree if needed
Handles special case of removing last element in root leaf

Here is the call graph for this function:

Here is the caller graph for this function:

◆ resize()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::resize	(	uint64_t	_size,
		VALUE	default_value
	)

inline

Resizes the B+ tree to contain a specified number of elements.

Parameters

_size	The new size of the B+ tree
default_value	The value to initialize new elements with if expanding

If the new size is larger than the current size, this function:

Adds new elements initialized with default_value until reaching target size
Maintains B+ tree properties by balancing nodes and updating paths If the new size is smaller, removes elements from the end until reaching target size

Here is the call graph for this function:

Here is the caller graph for this function:

◆ save() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::save ( std::ofstream & os )

inline

Saves the B+ tree structure to a file stream.

Parameters

os	Output file stream to write to

This function serializes the tree by:

Sorting leaf containers if needed
Writing tree parameters (max degrees)
Saving leaf container data to the file

Here is the call graph for this function:

◆ save() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::save	(	std::vector< uint8_t > &	output,
		uint64_t &	pos
	)

inline

Saves the B+ tree structure to a byte vector.

Parameters

output	Vector to store the serialized tree data
pos	Starting position in the output vector

This function serializes the tree by:

Sorting leaf containers if needed
Writing tree parameters (max degrees)
Saving leaf container data The output vector is resized if needed to accommodate the data

Here is the call graph for this function:

Here is the caller graph for this function:

◆ search()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::search ( uint64_t sum ) const

inline

Returns the position of the sum in the B+ tree.

Parameters

sum	The sum in the B+ tree

Returns: The position of the sum in the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ select0()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

int64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::select0 ( uint64_t i ) const

inline

Returns the position of the i-th 0 in the B+ tree.

Parameters

i	The position of the 0 in the B+ tree

Returns: The position of the i-th 0 in the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ set_linked_tree()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::set_linked_tree ( BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE > * _tree )

inline

Sets the linked B+ tree.

Parameters

_tree Pointer to the B+ tree to be linked

Associates another B+ tree with this one by storing a pointer to it

◆ size_in_bytes()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

uint64_t stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::size_in_bytes ( ) const

inline

Returns the total memory size of the B+ tree.

Returns: The total memory size of the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ sort_leaf_containers()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::sort_leaf_containers ( )

inline

Sorts the leaf containers in the B+ tree.

This function sorts and reorganizes the leaf containers in the B+ tree by:

Initializing parent pointers if not using parent field tracking
Traversing the tree in postorder and exchanging leaf containers to sort them
Removing any excess leaf containers and unused indexes
Cleaning up temporary parent vector if not using parent field tracking
Updating root pointer if tree is a single leaf

The function does nothing if:

The tree is empty
The root is a leaf node

After sorting, the leaf containers will be arranged in sequential order matching their positions in the tree traversal.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ split_node()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::split_node	(	Node *	left_node,
		Node *	right_node,
		bool	is_leaf,
		Node *	parent,
		int64_t	parent_edge_index_of_left_node,
		std::vector< Node * > &	parent_vec
	)

inline

Splits a node into two nodes in the B+ tree.

Parameters

left_node	Pointer to the node being split (original node)
right_node	Pointer to the new node that will receive half the values
is_leaf	True if nodes are leaves, false if internal nodes
parent	Pointer to the parent node
parent_edge_index_of_left_node	Index of left node in parent's children
parent_vec	Vector of parent pointers (unused parameter)

This function splits a node that has reached maximum capacity into two nodes. For leaf nodes, it splits the leaf container. For internal nodes, it splits the children array. The split is roughly even, with the right node receiving slightly more values if the total is odd. Updates parent relationships and maintains tree invariants.

Here is the call graph for this function:

◆ swap() [1/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::swap ( BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE > & _tree )

inline

Swaps the contents of this B+ tree with another B+ tree.

Parameters

_tree The B+ tree to swap contents with

This is a convenience overload that calls swap() with swap_linked_tree set to true

Here is the call graph for this function:

◆ swap() [2/2]

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

void stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::swap	(	BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE > &	_tree,
		bool	swap_linked_tree
	)

inline

Swaps the contents of this B+ tree with another B+ tree.

Parameters

_tree	The B+ tree to swap contents with
swap_linked_tree	Whether to also swap the linked tree pointer

This function swaps all internal data structures between this tree and the given tree, including leaf containers, parent vectors, unused node pointers, tree parameters, and tree properties. The swap_linked_tree parameter controls whether the linked tree pointer should also be swapped.

Here is the caller graph for this function:

◆ to_value_vector()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

std::vector< VALUE > stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::to_value_vector ( ) const

inline

Converts the B+ tree to a vector of values.

Returns: A vector of values representing the B+ tree

Here is the call graph for this function:

Here is the caller graph for this function:

◆ verify()

template<typename LEAF_CONTAINER , typename VALUE , bool USE_PARENT_FIELD, bool USE_PSUM, uint64_t MAX_DEGREE, uint64_t LEAF_CONTAINER_MAX_SIZE>

bool stool::bptree::BPTree< LEAF_CONTAINER, VALUE, USE_PARENT_FIELD, USE_PSUM, MAX_DEGREE, LEAF_CONTAINER_MAX_SIZE >::verify ( ) const

inline

Verifies the integrity of the B+ tree.

Returns: true if the tree is valid, false otherwise

Here is the call graph for this function:

Here is the caller graph for this function:

The documentation for this class was generated from the following files:

include/bp_tree/bp_tree.hpp
include/permutation/bp_tree_template.hpp

Public Types

Public Member Functions

Public standard functions

Non-const public functions

Non-const private functions for updating nodes

Detailed Description

Member Function Documentation

◆ at()

◆ build()

◆ build_from_data() [1/2]

◆ build_from_data() [2/2]

◆ build_from_leaf_containers()

◆ build_from_leaf_containers_sub1()

◆ build_from_leaf_containers_sub2()

◆ build_sub()

◆ check_if_leaf_container_vec_is_sorted()

◆ clear()

◆ compute_internal_node_count()

◆ compute_leaf_container_count()

◆ compute_path_from_root_to_leaf() [1/2]

◆ compute_path_from_root_to_leaf() [2/2]

◆ empty()

◆ get_internal_node_memory()

◆ get_leaf_container() [1/2]

◆ get_leaf_container() [2/2]

◆ get_leaf_container_memory()

◆ get_leaf_container_vector_memory()

◆ get_leaf_forward_iterator_begin()

◆ get_leaf_forward_iterator_end()

◆ get_linked_tree()

◆ get_max_count_of_values_in_leaf()

◆ get_memory_usage_info()

◆ get_parent_vector_memory()

◆ get_path_from_root_to_first_leaf()

◆ get_path_from_root_to_last_leaf()

◆ get_postorder_iterator_begin()

◆ get_postorder_iterator_end()

◆ get_temporary_path()

◆ get_unused_leaf_container_vector_memory()

◆ get_unused_node_pointers_memory()

◆ get_value_forward_iterator_begin()

◆ get_value_forward_iterator_end()

◆ get_value_index()

◆ increment()

◆ initialize()

◆ insert()

◆ move_values_left()

◆ move_values_right()

◆ print_info()

◆ print_leaf_containers()

◆ print_leaves()

◆ print_memory_usage()

◆ print_statistics()

◆ print_tree()

◆ psum() [1/2]

◆ psum() [2/2]

◆ push_back()

◆ push_front()

◆ push_many() [1/2]

◆ push_many() [2/2]

◆ remove()

◆ remove_using_path()

◆ resize()

◆ save() [1/2]

◆ save() [2/2]

◆ search()

◆ select0()

◆ set_linked_tree()

◆ size_in_bytes()

◆ sort_leaf_containers()

◆ split_node()

◆ swap() [1/2]

◆ swap() [2/2]

◆ to_value_vector()

◆ verify()