Detailed Description

template<typename Key, typename Value, typename KeyOfValue, typename Compare = std::less<Key>, typename Traits = btree_default_traits<Key, Value>, bool Duplicates = false, typename Allocator = std::allocator<Value>>
class tlx::BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >

Basic class implementing a B+ tree data structure in memory.

The base implementation of an in-memory B+ tree. It is based on the implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. Almost all STL-required function calls are implemented. The asymptotic time requirements of the STL are not always fulfilled in theory, however, in practice this B+ tree performs better than a red-black tree and almost always uses less memory. The insertion function splits the nodes on the recursion unroll. Erase is largely based on Jannink's ideas.

This class is specialized into btree_set, btree_multiset, btree_map and btree_multimap using default template parameters and facade functions.

Definition at line 124 of file btree.hpp.

Inheritance diagram for BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >:

Collaboration diagram for BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >:

#include <btree.hpp>

Classes
class	const_iterator

class	const_reverse_iterator

struct	InnerNode

class	iterator

struct	LeafNode

struct	node

struct	result_t

class	reverse_iterator

struct	tree_stats
	A small struct containing basic statistics about the B+ tree. More...

class	value_compare
	Function class to compare value_type objects. Required by the STL. More...

Public Types
Constructed Types
typedef BTree< key_type, value_type, key_of_value, key_compare, traits, allow_duplicates, allocator_type >	Self
	Typedef of our own type. More...

typedef size_t	size_type
	Size type used to count keys. More...

Public Member Functions
Constructors and Destructor
	BTree (const allocator_type &alloc=allocator_type())

	BTree (const key_compare &kcf, const allocator_type &alloc=allocator_type())

template<class InputIterator >
	BTree (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type())

template<class InputIterator >
	BTree (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type())

	~BTree ()
	Frees up all used B+ tree memory pages. More...

void	swap (BTree &from)
	Fast swapping of two identical B+ tree objects. More...

Key and Value Comparison Function Objects
key_compare	key_comp () const
	Constant access to the key comparison object sorting the B+ tree. More...

value_compare	value_comp () const

Allocators
allocator_type	get_allocator () const
	Return the base node allocator provided during construction. More...

STL Iterator Construction Functions
iterator	begin ()

iterator	end ()

const_iterator	begin () const

const_iterator	end () const

reverse_iterator	rbegin ()

reverse_iterator	rend ()

const_reverse_iterator	rbegin () const

const_reverse_iterator	rend () const

Access Functions to the Item Count
size_type	size () const
	Return the number of key/data pairs in the B+ tree. More...

bool	empty () const
	Returns true if there is at least one key/data pair in the B+ tree. More...

size_type	max_size () const

const struct tree_stats &	get_stats () const
	Return a const reference to the current statistics. More...

STL Access Functions Querying the Tree by Descending to a Leaf
bool	exists (const key_type &key) const

iterator	find (const key_type &key)

const_iterator	find (const key_type &key) const

size_type	count (const key_type &key) const

iterator	lower_bound (const key_type &key)

const_iterator	lower_bound (const key_type &key) const

iterator	upper_bound (const key_type &key)

const_iterator	upper_bound (const key_type &key) const

std::pair< iterator, iterator >	equal_range (const key_type &key)
	Searches the B+ tree and returns both lower_bound() and upper_bound(). More...

std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
	Searches the B+ tree and returns both lower_bound() and upper_bound(). More...

B+ Tree Object Comparison Functions
bool	operator== (const BTree &other) const

bool	operator!= (const BTree &other) const
	Inequality relation. Based on operator==. More...

bool	operator< (const BTree &other) const

bool	operator> (const BTree &other) const
	Greater relation. Based on operator<. More...

bool	operator<= (const BTree &other) const
	Less-equal relation. Based on operator<. More...

bool	operator>= (const BTree &other) const
	Greater-equal relation. Based on operator<. More...

Public Insertion Functions
std::pair< iterator, bool >	insert (const value_type &x)

iterator	insert (iterator, const value_type &x)

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)

Bulk Loader - Construct Tree from Sorted Sequence
template<typename Iterator >
void	bulk_load (Iterator ibegin, Iterator iend)

Public Erase Functions
bool	erase_one (const key_type &key)

size_type	erase (const key_type &key)

void	erase (iterator iter)
	Erase the key/data pair referenced by the iterator. More...

Static Public Attributes
Static Constant Options and Values of the B+ Tree
static const unsigned short	leaf_slotmax = traits::leaf_slots
	Base B+ tree parameter: The number of key/data slots in each leaf. More...

static const unsigned short	inner_slotmax = traits::inner_slots

static const unsigned short	leaf_slotmin = (leaf_slotmax / 2)

static const unsigned short	inner_slotmin = (inner_slotmax / 2)

static const bool	self_verify = traits::self_verify

static const bool	debug = traits::debug

Private Types
Support Class Encapsulating Deletion Results
enum	result_flags_t { btree_ok = 0, btree_not_found = 1, btree_update_lastkey = 2, btree_fixmerge = 4 }
	Result flags of recursive deletion. More...

Private Member Functions
Convenient Key Comparison Functions Generated From key_less
bool	key_less (const key_type &a, const key_type &b) const
	True if a < b ? "constructed" from key_less_() More...

bool	key_lessequal (const key_type &a, const key_type &b) const
	True if a <= b ? constructed from key_less() More...

bool	key_greater (const key_type &a, const key_type &b) const
	True if a > b ? constructed from key_less() More...

bool	key_greaterequal (const key_type &a, const key_type &b) const
	True if a >= b ? constructed from key_less() More...

bool	key_equal (const key_type &a, const key_type &b) const

Node Object Allocation and Deallocation Functions
LeafNode::alloc_type	leaf_node_allocator ()
	Return an allocator for LeafNode objects. More...

InnerNode::alloc_type	inner_node_allocator ()
	Return an allocator for InnerNode objects. More...

LeafNode *	allocate_leaf ()
	Allocate and initialize a leaf node. More...

InnerNode *	allocate_inner (unsigned short level)
	Allocate and initialize an inner node. More...

void	free_node (node *n)

B+ Tree Node Binary Search Functions
template<typename node_type >
unsigned short	find_lower (const node_type *n, const key_type &key) const

template<typename node_type >
unsigned short	find_upper (const node_type *n, const key_type &key) const

Private Insertion Functions
std::pair< iterator, bool >	insert_start (const key_type &key, const value_type &value)

std::pair< iterator, bool >	insert_descend (node n, const key_type &key, const value_type &value, key_type splitkey, node **splitnode)
	Insert an item into the B+ tree. More...

void	split_leaf_node (LeafNode leaf, key_type out_newkey, node **out_newleaf)

void	split_inner_node (InnerNode inner, key_type out_newkey, node **out_newinner, unsigned int addslot)

Private Attributes
Tree Object Data Members
node *	root_
	Pointer to the B+ tree's root node, either leaf or inner node. More...

LeafNode *	head_leaf_
	Pointer to first leaf in the double linked leaf chain. More...

LeafNode *	tail_leaf_
	Pointer to last leaf in the double linked leaf chain. More...

tree_stats	stats_
	Other small statistics about the B+ tree. More...

key_compare	key_less_

allocator_type	allocator_
	Memory allocator. More...

Template Parameter Types
typedef Key	key_type

typedef Value	value_type

typedef KeyOfValue	key_of_value
	Third template: key extractor class to pull key_type from value_type. More...

typedef Compare	key_compare
	Fourth template parameter: key_type comparison function object. More...

typedef Traits	traits

typedef Allocator	allocator_type
	Seventh template parameter: STL allocator for tree nodes. More...

static const bool	allow_duplicates = Duplicates

Fast Destruction of the B+ Tree
void	clear ()
	Frees all key/data pairs and all nodes of the tree. More...

void	clear_recursive (node *n)
	Recursively free up nodes. More...

Fast Copy: Assign Operator and Copy Constructors
BTree &	operator= (const BTree &other)
	Assignment operator. All the key/data pairs are copied. More...

	BTree (const BTree &other)

struct node *	copy_recursive (const node *n)
	Recursively copy nodes from another B+ tree object. More...

Private Erase Functions
result_t	erase_one_descend (const key_type &key, node curr, node left, node right, InnerNode left_parent, InnerNode right_parent, InnerNode parent, unsigned int parentslot)
	Erase one (the first) key/data pair in the B+ tree matching key. More...

result_t	erase_iter_descend (const iterator &iter, node curr, node left, node right, InnerNode left_parent, InnerNode right_parent, InnerNode parent, unsigned int parentslot)
	Erase one key/data pair referenced by an iterator in the B+ tree. More...

result_t	merge_leaves (LeafNode left, LeafNode right, InnerNode *parent)

static result_t	merge_inner (InnerNode left, InnerNode right, InnerNode *parent, unsigned int parentslot)

static result_t	shift_left_leaf (LeafNode left, LeafNode right, InnerNode *parent, unsigned int parentslot)

static void	shift_left_inner (InnerNode left, InnerNode right, InnerNode *parent, unsigned int parentslot)

static void	shift_right_leaf (LeafNode left, LeafNode right, InnerNode *parent, unsigned int parentslot)

static void	shift_right_inner (InnerNode left, InnerNode right, InnerNode *parent, unsigned int parentslot)

Verification of B+ Tree Invariants
void	verify () const

void	verify_node (const node n, key_type minkey, key_type *maxkey, tree_stats &vstats) const
	Recursively descend down the tree and verify each node. More...

void	verify_leaflinks () const
	Verify the double linked list of leaves. More...

Member Typedef Documentation

◆ allocator_type

typedef Allocator allocator_type

Seventh template parameter: STL allocator for tree nodes.

Definition at line 153 of file btree.hpp.

◆ key_compare

typedef Compare key_compare

Fourth template parameter: key_type comparison function object.

Definition at line 142 of file btree.hpp.

◆ key_of_value

typedef KeyOfValue key_of_value

Third template: key extractor class to pull key_type from value_type.

Definition at line 139 of file btree.hpp.

◆ key_type

typedef Key key_type

First template parameter: The key type of the B+ tree. This is stored in inner nodes.

Definition at line 132 of file btree.hpp.

◆ Self

typedef BTree<key_type, value_type, key_of_value, key_compare, traits, allow_duplicates, allocator_type> Self

Typedef of our own type.

Definition at line 168 of file btree.hpp.

◆ size_type

typedef size_t size_type

Size type used to count keys.

Definition at line 171 of file btree.hpp.

◆ traits

typedef Traits traits

Fifth template parameter: Traits object used to define more parameters of the B+ tree

Definition at line 146 of file btree.hpp.

◆ value_type

typedef Value value_type

Second template parameter: Composition pair of key and data types, or just the key for set containers. This data type is stored in the leaves.

Definition at line 136 of file btree.hpp.

Member Enumeration Documentation

◆ result_flags_t

enum result_flags_t

private

Result flags of recursive deletion.

Enumerator
btree_ok	Deletion successful and no fix-ups necessary.
btree_not_found	Deletion not successful because key was not found.
btree_update_lastkey	Deletion successful, the last key was updated so parent slotkeys need updates.
btree_fixmerge	Deletion successful, children nodes were merged and the parent needs to remove the empty node.

Definition at line 2307 of file btree.hpp.

Constructor & Destructor Documentation

◆ BTree() [1/5]

BTree ( const allocator_type & alloc = allocator_type() )

inlineexplicit

Default constructor initializing an empty B+ tree with the standard key comparison function.

Definition at line 1103 of file btree.hpp.

◆ BTree() [2/5]

BTree	(	const key_compare &	kcf,
		const allocator_type &	alloc = `allocator_type()`
	)

inlineexplicit

Constructor initializing an empty B+ tree with a special key comparison object.

Definition at line 1110 of file btree.hpp.

◆ BTree() [3/5]

BTree	(	InputIterator	first,
		InputIterator	last,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

Constructor initializing a B+ tree with the range [first,last). The range need not be sorted. To create a B+ tree from a sorted range, use bulk_load().

Definition at line 1120 of file btree.hpp.

◆ BTree() [4/5]

BTree	(	InputIterator	first,
		InputIterator	last,
		const key_compare &	kcf,
		const allocator_type &	alloc = `allocator_type()`
	)

inline

Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. The range need not be sorted. To create a B+ tree from a sorted range, use bulk_load().

Definition at line 1131 of file btree.hpp.

◆ ~BTree()

~BTree ( )

inline

Frees up all used B+ tree memory pages.

Definition at line 1139 of file btree.hpp.

◆ BTree() [5/5]

BTree ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other )

inline

Copy constructor. The newly initialized B+ tree object will contain a copy of all key/data pairs.

Definition at line 1779 of file btree.hpp.

Member Function Documentation

◆ allocate_inner()

InnerNode* allocate_inner ( unsigned short level )

inlineprivate

Allocate and initialize an inner node.

Definition at line 1261 of file btree.hpp.

◆ allocate_leaf()

LeafNode* allocate_leaf ( )

inlineprivate

Allocate and initialize a leaf node.

Definition at line 1253 of file btree.hpp.

◆ begin() [1/2]

iterator begin ( )

inline

Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree.

Definition at line 1341 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::begin(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::begin(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::begin(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::begin(), BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator<(), and BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator==().

◆ begin() [2/2]

const_iterator begin ( ) const

inline

Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree.

Definition at line 1353 of file btree.hpp.

◆ bulk_load()

void bulk_load	(	Iterator	ibegin,
		Iterator	iend
	)

inline

Bulk load a sorted range. Loads items into leaves and constructs a B-tree above them. The tree must be empty when calling this function.

Definition at line 2155 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::bulk_load(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::bulk_load(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::bulk_load(), and btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::bulk_load().

◆ clear()

void clear ( )

inline

Frees all key/data pairs and all nodes of the tree.

Definition at line 1294 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::clear(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::clear(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::clear(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::clear().

◆ clear_recursive()

void clear_recursive ( node * n )

inlineprivate

Recursively free up nodes.

Definition at line 1311 of file btree.hpp.

◆ copy_recursive()

struct node* copy_recursive ( const node * n )

inlineprivate

Recursively copy nodes from another B+ tree object.

Definition at line 1796 of file btree.hpp.

◆ count()

size_type count ( const key_type & key ) const

inline

Tries to locate a key in the B+ tree and returns the number of identical key entries found.

Definition at line 1584 of file btree.hpp.

Referenced by btree_multiset< Key_, Compare_, Traits_, Alloc_ >::count(), btree_set< Key_, Compare_, Traits_, Alloc_ >::count(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::count(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::count().

◆ empty()

bool empty ( ) const

inline

Returns true if there is at least one key/data pair in the B+ tree.

Definition at line 1499 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::empty(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::empty(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::empty(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::empty().

◆ end() [1/2]

iterator end ( )

inline

Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree.

Definition at line 1347 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::end(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::end(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::end(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::end(), and BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator<().

◆ end() [2/2]

const_iterator end ( ) const

inline

Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree.

Definition at line 1359 of file btree.hpp.

◆ equal_range() [1/2]

std::pair<iterator, iterator> equal_range ( const key_type & key )

inline

Searches the B+ tree and returns both lower_bound() and upper_bound().

Definition at line 1695 of file btree.hpp.

Referenced by btree_multiset< Key_, Compare_, Traits_, Alloc_ >::equal_range(), btree_set< Key_, Compare_, Traits_, Alloc_ >::equal_range(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::equal_range(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::equal_range().

◆ equal_range() [2/2]

std::pair<const_iterator, const_iterator> equal_range ( const key_type & key ) const

inline

Searches the B+ tree and returns both lower_bound() and upper_bound().

Definition at line 1702 of file btree.hpp.

◆ erase() [1/2]

size_type erase ( const key_type & key )

inline

Erases all the key/data pairs associated with the given key. This is implemented using erase_one().

Definition at line 2392 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::erase(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::erase(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::erase(), and btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::erase().

◆ erase() [2/2]

void erase ( iterator iter )

inline

Erase the key/data pair referenced by the iterator.

Definition at line 2405 of file btree.hpp.

◆ erase_iter_descend()

result_t erase_iter_descend	(	const iterator &	iter,
		node *	curr,
		node *	left,
		node *	right,
		InnerNode *	left_parent,
		InnerNode *	right_parent,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlineprivate

Erase one key/data pair referenced by an iterator in the B+ tree.

Descends down the tree in search of an iterator. During the descent the parent, left and right siblings and their parents are computed and passed down. The difficulty is that the iterator contains only a pointer to a LeafNode, which means that this function must do a recursive depth first search for that leaf node in the subtree containing all pairs of the same key. This subtree can be very large, even the whole tree, though in practice it would not make sense to have so many duplicate keys.

Once the referenced key/data pair is found, it is removed from the leaf and the same underflow cases are handled as in erase_one_descend.

Definition at line 2779 of file btree.hpp.

◆ erase_one()

bool erase_one ( const key_type & key )

inline

Erases one (the first) of the key/data pairs associated with the given key.

Definition at line 2368 of file btree.hpp.

Referenced by btree_multiset< Key_, Compare_, Traits_, Alloc_ >::erase_one(), btree_set< Key_, Compare_, Traits_, Alloc_ >::erase_one(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::erase_one(), and btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::erase_one().

◆ erase_one_descend()

result_t erase_one_descend	(	const key_type &	key,
		node *	curr,
		node *	left,
		node *	right,
		InnerNode *	left_parent,
		InnerNode *	right_parent,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlineprivate

Erase one (the first) key/data pair in the B+ tree matching key.

Descends down the tree in search of key. During the descent the parent, left and right siblings and their parents are computed and passed down. Once the key/data pair is found, it is removed from the leaf. If the leaf underflows 6 different cases are handled. These cases resolve the underflow by shifting key/data pairs from adjacent sibling nodes, merging two sibling nodes or trimming the tree.

Definition at line 2449 of file btree.hpp.

◆ exists()

bool exists ( const key_type & key ) const

inline

Non-STL function checking whether a key is in the B+ tree. The same as (find(k) != end()) or (count() != 0).

Definition at line 1522 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::exists(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::exists(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::exists(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::exists().

◆ find() [1/2]

iterator find ( const key_type & key )

inline

Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found. If unsuccessful it returns end().

Definition at line 1542 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::find(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::find(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::find(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::find().

◆ find() [2/2]

const_iterator find ( const key_type & key ) const

inline

Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found. If unsuccessful it returns end().

Definition at line 1563 of file btree.hpp.

◆ find_lower()

unsigned short find_lower	(	const node_type *	n,
		const key_type &	key
	)		const

inlineprivate

Searches for the first key in the node n greater or equal to key. Uses binary search with an optional linear self-verification. This is a template function, because the slotkey array is located at different places in LeafNode and InnerNode.

Definition at line 1398 of file btree.hpp.

◆ find_upper()

unsigned short find_upper	(	const node_type *	n,
		const key_type &	key
	)		const

inlineprivate

Searches for the first key in the node n greater than key. Uses binary search with an optional linear self-verification. This is a template function, because the slotkey array is located at different places in LeafNode and InnerNode.

Definition at line 1445 of file btree.hpp.

◆ free_node()

void free_node ( node * n )

inlineprivate

Correctly free either inner or leaf node, destructs all contained key and value objects.

Definition at line 1270 of file btree.hpp.

◆ get_allocator()

allocator_type get_allocator ( ) const

inline

Return the base node allocator provided during construction.

Definition at line 1232 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::get_allocator(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::get_allocator(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::get_allocator(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::get_allocator(), and BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator=().

◆ get_stats()

const struct tree_stats& get_stats ( ) const

inline

Return a const reference to the current statistics.

Definition at line 1510 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::get_stats(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::get_stats(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::get_stats(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::get_stats().

◆ inner_node_allocator()

InnerNode::alloc_type inner_node_allocator ( )

inlineprivate

Return an allocator for InnerNode objects.

Definition at line 1248 of file btree.hpp.

◆ insert() [1/3]

std::pair<iterator, bool> insert ( const value_type & x )

inline

Attempt to insert a key/data pair into the B+ tree. If the tree does not allow duplicate keys, then the insert may fail if it is already present.

Definition at line 1846 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::insert(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::insert(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::insert(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::insert(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::insert2(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::insert2().

◆ insert() [2/3]

iterator insert	(	iterator	,
		const value_type &	x
	)

inline

Attempt to insert a key/data pair into the B+ tree. The iterator hint is currently ignored by the B+ tree insertion routine.

Definition at line 1852 of file btree.hpp.

◆ insert() [3/3]

void insert	(	InputIterator	first,
		InputIterator	last
	)

inline

Attempt to insert the range [first,last) of value_type pairs into the B+ tree. Each key/data pair is inserted individually; to bulk load the tree, use a constructor with range.

Definition at line 1860 of file btree.hpp.

◆ insert_descend()

std::pair<iterator, bool> insert_descend	(	node *	n,
		const key_type &	key,
		const value_type &	value,
		key_type *	splitkey,
		node **	splitnode
	)

inlineprivate

Insert an item into the B+ tree.

Descend down the nodes to a leaf, insert the key/data pair in a free slot. If the node overflows, then it must be split and the new split node inserted into the parent. Unroll / this splitting up to the root.

Definition at line 1928 of file btree.hpp.

◆ insert_start()

std::pair<iterator, bool> insert_start	(	const key_type &	key,
		const value_type &	value
	)

inlineprivate

Start the insertion descent at the current root and handle root splits. Returns true if the item was inserted

Definition at line 1878 of file btree.hpp.

◆ key_comp()

key_compare key_comp ( ) const

inline

Constant access to the key comparison object sorting the B+ tree.

Definition at line 1183 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::key_comp(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::key_comp(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::key_comp(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::key_comp(), and BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator=().

◆ key_equal()

bool key_equal	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprivate

True if a == b ? constructed from key_less(). This requires the < relation to be a total order, otherwise the B+ tree cannot be sorted.

Definition at line 1221 of file btree.hpp.

◆ key_greater()

bool key_greater	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprivate

True if a > b ? constructed from key_less()

Definition at line 1210 of file btree.hpp.

◆ key_greaterequal()

bool key_greaterequal	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprivate

True if a >= b ? constructed from key_less()

Definition at line 1215 of file btree.hpp.

◆ key_less()

bool key_less	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprivate

True if a < b ? "constructed" from key_less_()

Definition at line 1200 of file btree.hpp.

◆ key_lessequal()

bool key_lessequal	(	const key_type &	a,
		const key_type &	b
	)		const

inlineprivate

True if a <= b ? constructed from key_less()

Definition at line 1205 of file btree.hpp.

◆ leaf_node_allocator()

LeafNode::alloc_type leaf_node_allocator ( )

inlineprivate

Return an allocator for LeafNode objects.

Definition at line 1243 of file btree.hpp.

◆ lower_bound() [1/2]

iterator lower_bound ( const key_type & key )

inline

Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller.

Definition at line 1616 of file btree.hpp.

Referenced by btree_multiset< Key_, Compare_, Traits_, Alloc_ >::lower_bound(), btree_set< Key_, Compare_, Traits_, Alloc_ >::lower_bound(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::lower_bound(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::lower_bound().

◆ lower_bound() [2/2]

const_iterator lower_bound ( const key_type & key ) const

inline

Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller.

Definition at line 1636 of file btree.hpp.

◆ max_size()

size_type max_size ( ) const

inline

Returns the largest possible size of the B+ Tree. This is just a function required by the STL standard, the B+ Tree can hold more items.

Definition at line 1505 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::max_size(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::max_size(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::max_size(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::max_size().

◆ merge_inner()

static result_t merge_inner	(	InnerNode *	left,
		InnerNode *	right,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlinestaticprivate

Merge two inner nodes. The function moves all key/childid pairs from right to left and sets right's slotuse to zero. The right slot is then removed by the calling parent node.

Definition at line 3169 of file btree.hpp.

◆ merge_leaves()

result_t merge_leaves	(	LeafNode *	left,
		LeafNode *	right,
		InnerNode *	parent
	)

inlineprivate

Merge two leaf nodes. The function moves all key/data pairs from right to left and sets right's slotuse to zero. The right slot is then removed by the calling parent node.

Definition at line 3139 of file btree.hpp.

◆ operator!=()

bool operator!= ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other ) const

inline

Inequality relation. Based on operator==.

Definition at line 1722 of file btree.hpp.

◆ operator<()

bool operator< ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other ) const

inline

Total ordering relation of B+ trees of the same type. It uses std::lexicographical_compare() for the actual comparison of elements.

Definition at line 1728 of file btree.hpp.

◆ operator<=()

bool operator<= ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other ) const

inline

Less-equal relation. Based on operator<.

Definition at line 1739 of file btree.hpp.

◆ operator=()

BTree& operator= ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other )

inline

Assignment operator. All the key/data pairs are copied.

Definition at line 1755 of file btree.hpp.

◆ operator==()

bool operator== ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other ) const

inline

Equality relation of B+ trees of the same type. B+ trees of the same size and equal elements (both key and data) are considered equal. Beware of the random ordering of duplicate keys.

Definition at line 1716 of file btree.hpp.

◆ operator>()

bool operator> ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other ) const

inline

Greater relation. Based on operator<.

Definition at line 1734 of file btree.hpp.

◆ operator>=()

bool operator>= ( const BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & other ) const

inline

Greater-equal relation. Based on operator<.

Definition at line 1744 of file btree.hpp.

◆ rbegin() [1/2]

reverse_iterator rbegin ( )

inline

Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. Uses STL magic.

Definition at line 1365 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::rbegin(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::rbegin(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::rbegin(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::rbegin().

◆ rbegin() [2/2]

const_reverse_iterator rbegin ( ) const

inline

Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. Uses STL magic.

Definition at line 1377 of file btree.hpp.

◆ rend() [1/2]

reverse_iterator rend ( )

inline

Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. Uses STL magic.

Definition at line 1371 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::rend(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::rend(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::rend(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::rend().

◆ rend() [2/2]

const_reverse_iterator rend ( ) const

inline

Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree. Uses STL magic.

Definition at line 1383 of file btree.hpp.

◆ shift_left_inner()

static void shift_left_inner	(	InnerNode *	left,
		InnerNode *	right,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlinestaticprivate

Balance two inner nodes. The function moves key/data pairs from right to left so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3264 of file btree.hpp.

◆ shift_left_leaf()

static result_t shift_left_leaf	(	LeafNode *	left,
		LeafNode *	right,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlinestaticprivate

Balance two leaf nodes. The function moves key/data pairs from right to left so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3215 of file btree.hpp.

◆ shift_right_inner()

static void shift_right_inner	(	InnerNode *	left,
		InnerNode *	right,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlinestaticprivate

Balance two inner nodes. The function moves key/data pairs from left to right so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3385 of file btree.hpp.

◆ shift_right_leaf()

static void shift_right_leaf	(	LeafNode *	left,
		LeafNode *	right,
		InnerNode *	parent,
		unsigned int	parentslot
	)

inlinestaticprivate

Balance two leaf nodes. The function moves key/data pairs from left to right so that both nodes are equally filled. The parent node is updated if possible.

Definition at line 3329 of file btree.hpp.

◆ size()

size_type size ( ) const

inline

Return the number of key/data pairs in the B+ tree.

Definition at line 1494 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator=(), BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator==(), btree_set< Key_, Compare_, Traits_, Alloc_ >::size(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::size(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::size(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::size().

◆ split_inner_node()

void split_inner_node	(	InnerNode *	inner,
		key_type *	out_newkey,
		node **	out_newinner,
		unsigned int	addslot
	)

inlineprivate

Split up an inner node into two equally-filled sibling nodes. Returns the new nodes and it's insertion key in the two parameters. Requires the slot of the item will be inserted, so the nodes will be the same size after the insert.

Definition at line 2110 of file btree.hpp.

◆ split_leaf_node()

void split_leaf_node	(	LeafNode *	leaf,
		key_type *	out_newkey,
		node **	out_newleaf
	)

inlineprivate

Split up a leaf node into two equally-filled sibling leaves. Returns the new nodes and it's insertion key in the two parameters.

Definition at line 2074 of file btree.hpp.

◆ swap()

void swap ( BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator > & from )

inline

Fast swapping of two identical B+ tree objects.

Definition at line 1144 of file btree.hpp.

◆ upper_bound() [1/2]

iterator upper_bound ( const key_type & key )

inline

Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal.

Definition at line 1656 of file btree.hpp.

Referenced by btree_multiset< Key_, Compare_, Traits_, Alloc_ >::upper_bound(), btree_set< Key_, Compare_, Traits_, Alloc_ >::upper_bound(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::upper_bound(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::upper_bound().

◆ upper_bound() [2/2]

const_iterator upper_bound ( const key_type & key ) const

inline

Searches the B+ tree and returns a constant iterator to the first pair greater than key, or end() if all keys are smaller or equal.

Definition at line 1676 of file btree.hpp.

◆ value_comp()

value_compare value_comp ( ) const

inline

Constant access to a constructed value_type comparison object. Required by the STL.

Definition at line 1189 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::value_comp(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::value_comp(), btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::value_comp(), and btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::value_comp().

◆ verify()

void verify ( ) const

inline

Run a thorough verification of all B+ tree invariants. The program aborts via tlx_die_unless() if something is wrong.

Definition at line 3541 of file btree.hpp.

Referenced by btree_set< Key_, Compare_, Traits_, Alloc_ >::verify(), btree_multiset< Key_, Compare_, Traits_, Alloc_ >::verify(), btree_multimap< Key_, Data_, Compare_, Traits_, Alloc_ >::verify(), and btree_map< Key_, Data_, Compare_, Traits_, Alloc_ >::verify().

◆ verify_leaflinks()

void verify_leaflinks ( ) const

inlineprivate

Verify the double linked list of leaves.

Definition at line 3653 of file btree.hpp.

◆ verify_node()

void verify_node	(	const node *	n,
		key_type *	minkey,
		key_type *	maxkey,
		tree_stats &	vstats
	)		const

inlineprivate

Recursively descend down the tree and verify each node.

Definition at line 3559 of file btree.hpp.

Member Data Documentation

◆ allocator_

allocator_type allocator_

private

Memory allocator.

Definition at line 1093 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::swap().

◆ allow_duplicates

const bool allow_duplicates = Duplicates

static

Sixth template parameter: Allow duplicate keys in the B+ tree. Used to implement multiset and multimap.

Definition at line 150 of file btree.hpp.

◆ debug

const bool debug = traits::debug

static

Debug parameter: Prints out lots of debug information about how the algorithms change the tree. Requires the header file to be compiled with TLX_BTREE_DEBUG and the key type must be std::ostream printable.

Definition at line 203 of file btree.hpp.

◆ head_leaf_

LeafNode* head_leaf_

private

Pointer to first leaf in the double linked leaf chain.

Definition at line 1080 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::swap().

◆ inner_slotmax

const unsigned short inner_slotmax = traits::inner_slots

static

Base B+ tree parameter: The number of key slots in each inner node, this can differ from slots in each leaf.

Definition at line 184 of file btree.hpp.

◆ inner_slotmin

const unsigned short inner_slotmin = (inner_slotmax / 2)

static

Computed B+ tree parameter: The minimum number of key slots used in an inner node. If fewer slots are used, the inner node will be merged or slots shifted from it's siblings.

Definition at line 194 of file btree.hpp.

◆ key_less_

key_compare key_less_

private

Key comparison object. More comparison functions are generated from this < relation.

Definition at line 1090 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::swap().

◆ leaf_slotmax

const unsigned short leaf_slotmax = traits::leaf_slots

static

Base B+ tree parameter: The number of key/data slots in each leaf.

Definition at line 180 of file btree.hpp.

◆ leaf_slotmin

const unsigned short leaf_slotmin = (leaf_slotmax / 2)

static

Computed B+ tree parameter: The minimum number of key/data slots used in a leaf. If fewer slots are used, the leaf will be merged or slots shifted from it's siblings.

Definition at line 189 of file btree.hpp.

◆ root_

node* root_

private

Pointer to the B+ tree's root node, either leaf or inner node.

Definition at line 1077 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::BTree(), BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator=(), and BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::swap().

◆ self_verify

const bool self_verify = traits::self_verify

static

Debug parameter: Enables expensive and thorough checking of the B+ tree invariants after each insert/erase operation.

Definition at line 198 of file btree.hpp.

◆ stats_

tree_stats stats_

private

Other small statistics about the B+ tree.

Definition at line 1086 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::operator=(), and BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::swap().

◆ tail_leaf_

LeafNode* tail_leaf_

private

Pointer to last leaf in the double linked leaf chain.

Definition at line 1083 of file btree.hpp.

Referenced by BTree< key_type, value_type, key_of_value, key_compare, traits, true, allocator_type >::swap().

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

extlib/tlx/tlx/container/btree.hpp

Detailed Description

template<typename Key, typename Value, typename KeyOfValue, typename Compare = std::less<Key>, typename Traits = btree_default_traits<Key, Value>, bool Duplicates = false, typename Allocator = std::allocator<Value>> class tlx::BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Template Parameter Types

Fast Destruction of the B+ Tree

Fast Copy: Assign Operator and Copy Constructors

Private Erase Functions

Verification of B+ Tree Invariants

Member Typedef Documentation

◆ allocator_type

◆ key_compare

◆ key_of_value

◆ key_type

◆ Self

◆ size_type

◆ traits

◆ value_type

Member Enumeration Documentation

◆ result_flags_t

Constructor & Destructor Documentation

◆ BTree() [1/5]

◆ BTree() [2/5]

◆ BTree() [3/5]

◆ BTree() [4/5]

◆ ~BTree()

◆ BTree() [5/5]

Member Function Documentation

◆ allocate_inner()

◆ allocate_leaf()

◆ begin() [1/2]

◆ begin() [2/2]

◆ bulk_load()

◆ clear()

◆ clear_recursive()

◆ copy_recursive()

◆ count()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ erase() [1/2]

◆ erase() [2/2]

◆ erase_iter_descend()

◆ erase_one()

◆ erase_one_descend()

◆ exists()

◆ find() [1/2]

◆ find() [2/2]

◆ find_lower()

◆ find_upper()

◆ free_node()

◆ get_allocator()

◆ get_stats()

◆ inner_node_allocator()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ insert_descend()

◆ insert_start()

◆ key_comp()

◆ key_equal()

◆ key_greater()

◆ key_greaterequal()

◆ key_less()

◆ key_lessequal()

◆ leaf_node_allocator()

◆ lower_bound() [1/2]

◆ lower_bound() [2/2]

◆ max_size()

◆ merge_inner()

◆ merge_leaves()

◆ operator!=()

◆ operator<()

template<typename Key, typename Value, typename KeyOfValue, typename Compare = std::less<Key>, typename Traits = btree_default_traits<Key, Value>, bool Duplicates = false, typename Allocator = std::allocator<Value>>
class tlx::BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >