A b-tree based set implementation. More...

#include <LambdaBTree.h>

Inheritance diagram for souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >:

Collaboration diagram for souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >:

Public Member Functions
	LambdaBTreeSet (const Comparator &comp=Comparator())
	A default constructor creating an empty set. More...

template<typename Iter >
	LambdaBTreeSet (const Iter &a, const Iter &b)
	A constructor creating a set based on the given range. More...

	LambdaBTreeSet (const LambdaBTreeSet &other)

	LambdaBTreeSet (LambdaBTreeSet &&other)

LambdaBTreeSet &	operator= (const LambdaBTreeSet &other)

Public Member Functions inherited from souffle::detail::LambdaBTree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename detail::default_strategy< Key >::type, true, Functor >
void	insert (const Iter &a, const Iter &b)
	Inserts the given range of elements into this tree. More...

Functor::result_type	insert (Key &k, const Functor &f)
	Inserts the given key into this tree. More...

Functor::result_type	insert (Key &k, typename parenttype::operation_hints &hints, const Functor &f)

	LambdaBTree (const detail::comparator< Key > &comp=detail::comparator< Key >(), const detail::comparator< Key > &weak_comp=detail::comparator< Key >())

bool	operator!= (const LambdaBTree &other) const

LambdaBTree &	operator= (const LambdaBTree &other)

bool	operator== (const LambdaBTree &other) const

void	swap (LambdaBTree &other)
	Swaps the content of this tree with the given tree. More...

Public Member Functions inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
iterator	begin () const

	btree (btree &&other)

	btree (const btree &set)

	btree (const Iter &a, const Iter &b)

	btree (detail::comparator< Key > comp=detail::comparator< Key >(), detail::comparator< Key > weak_comp=detail::comparator< Key >())

bool	check ()
	Checks the consistency of this tree. More...

void	clear ()
	Clears this tree. More...

bool	contains (const Key &k) const
	Determines whether the given element is a member of this tree. More...

bool	contains (const Key &k, operation_hints &hints) const
	Determines whether the given element is a member of this tree. More...

bool	empty () const

iterator	end () const

iterator	find (const Key &k) const
	Locates the given key within this tree and returns an iterator referencing its position. More...

iterator	find (const Key &k, operation_hints &hints) const
	Locates the given key within this tree and returns an iterator referencing its position. More...

std::vector< chunk >	getChunks (size_type num) const

size_type	getDepth () const

size_type	getMemoryUsage () const

size_type	getNumNodes () const

void	insert (const Iter &a, const Iter &b)
	Inserts the given range of elements into this tree. More...

bool	insert (const Key &k)
	Inserts the given key into this tree. More...

bool	insert (const Key &k, operation_hints &hints)
	Inserts the given key into this tree. More...

iterator	lower_bound (const Key &k) const
	Obtains a lower boundary for the given key – hence an iterator referencing the smallest value that is not less the given key. More...

iterator	lower_bound (const Key &k, operation_hints &hints) const
	Obtains a lower boundary for the given key – hence an iterator referencing the smallest value that is not less the given key. More...

bool	operator!= (const btree &other) const

btree &	operator= (const btree &other)

bool	operator== (const btree &other) const

std::vector< chunk >	partition (size_type num) const
	Partitions the full range of this set into up to a given number of chunks. More...

void	printStats (std::ostream &out=std::cout) const
	Prints a textual summary of statistical properties of this tree to the given output stream (for debugging and tuning). More...

void	printTree (std::ostream &out=std::cout) const

size_type	size () const

void	swap (btree &other)
	Swaps the content of this tree with the given tree. More...

iterator	upper_bound (const Key &k) const
	Obtains an upper boundary for the given key – hence an iterator referencing the first element that the given key is less than the referenced value. More...

iterator	upper_bound (const Key &k, operation_hints &hints) const
	Obtains an upper boundary for the given key – hence an iterator referencing the first element that the given key is less than the referenced value. More...

	~btree ()

Static Public Member Functions
template<typename Iter >
static LambdaBTreeSet	load (const Iter &a, const Iter &b)

Static Public Member Functions inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
static std::enable_if< std::is_same< typename std::iterator_traits< Iter >::iterator_category, std::random_access_iterator_tag >::value, R >::type	load (const Iter &a, const Iter &b)
	A static member enabling the bulk-load of ordered data into an empty tree. More...

Private Types
using	super = detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor >

Private Member Functions
template<typename s , typename n , typename l >
	LambdaBTreeSet (s size, n root, l leftmost)

Friends
class	detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor >

Additional Inherited Members
Public Types inherited from souffle::detail::LambdaBTree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename detail::default_strategy< Key >::type, true, Functor >
using	parenttype = btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >

Public Types inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
using	chunk = range< iterator >

using	const_iterator = iterator

using	element_type = Key

using	key_type = Key

using	operation_hints = btree_operation_hints< 1 >

Static Public Attributes inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
static constexpr size_t	max_keys_per_node

Protected Types inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
using	field_index_type = uint8_t

using	lock_type = OptimisticReadWriteLock

using	size_type = std::size_t

Protected Member Functions inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
	btree (size_type, node root, leaf_node leftmost)
	An internal constructor enabling the specific creation of a tree based on internal parameters. More...

bool	covers (const node *node, const Key &k) const
	Determines whether the range covered by the given node is also covering the given key value. More...

bool	equal (const Key &a, const Key &b) const

bool	less (const Key &a, const Key &b) const

void	update (Key &old_k, const Key &new_k)

bool	weak_covers (const node *node, const Key &k) const
	Determines whether the range covered by the given node is also covering the given key value. More...

bool	weak_equal (const Key &a, const Key &b) const

bool	weak_less (const Key &a, const Key &b) const

Protected Attributes inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
detail::comparator< Key >	comp

hint_statistics	hint_stats

leaf_node *	leftmost

node *	root

lock_type	root_lock

detail::updater< Key >	upd

detail::comparator< Key >	weak_comp

Static Protected Attributes inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >
const static typename detail::default_strategy< Key >::type	search

Detailed Description

template<typename Key, typename Functor, typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>
class souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >

A b-tree based set implementation.

Template Parameters

Key	.. the element type to be stored in this set
Functor	.. a std::function that is invoked on successful insert
Comparator	.. a class defining an order on the stored elements
Allocator	.. utilized for allocating memory for required nodes
blockSize	.. determines the number of bytes/block utilized by leaf nodes
SearchStrategy	.. enables switching between linear, binary or any other search strategy

Definition at line 584 of file LambdaBTree.h.

Member Typedef Documentation

◆ super

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

using souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::super = detail::LambdaBTree<Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor>

private

Definition at line 586 of file LambdaBTree.h.

Constructor & Destructor Documentation

◆ LambdaBTreeSet() [1/5]

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::LambdaBTreeSet ( const Comparator & comp = Comparator() )

inline

A default constructor creating an empty set.

Definition at line 594 of file LambdaBTree.h.

596 : super(other) {}

◆ LambdaBTreeSet() [2/5]

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

template<typename Iter >

souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::LambdaBTreeSet	(	const Iter &	a,
		const Iter &	b
	)

inline

A constructor creating a set based on the given range.

Definition at line 600 of file LambdaBTree.h.

601 :

602 // A constructor required by the bulk-load facility.

◆ LambdaBTreeSet() [3/5]

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::LambdaBTreeSet ( const LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy > & other )

inline

Definition at line 605 of file LambdaBTree.h.

606 :

607 // Support for the assignment operator.

◆ LambdaBTreeSet() [4/5]

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::LambdaBTreeSet ( LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy > && other )

inline

Definition at line 608 of file LambdaBTree.h.

608 {

◆ LambdaBTreeSet() [5/5]

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

template<typename s , typename n , typename l >

souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::LambdaBTreeSet	(	s	size,
		n *	root,
		l *	leftmost
	)

inlineprivate

Definition at line 613 of file LambdaBTree.h.

615 {

Member Function Documentation

◆ load()

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

template<typename Iter >

static LambdaBTreeSet souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::load	(	const Iter &	a,
		const Iter &	b
	)

inlinestatic

Definition at line 624 of file LambdaBTree.h.

◆ operator=()

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

LambdaBTreeSet& souffle::LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy >::operator= ( const LambdaBTreeSet< Key, Functor, Comparator, Allocator, blockSize, SearchStrategy > & other )

inline

Definition at line 617 of file LambdaBTree.h.

Friends And Related Function Documentation

◆ detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor >

template<typename Key , typename Functor , typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename detail::default_strategy<Key>::type>

friend class detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor >

friend

Definition at line 588 of file LambdaBTree.h.

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

include/souffle/datastructure/LambdaBTree.h

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ super

Constructor & Destructor Documentation

◆ LambdaBTreeSet() [1/5]

◆ LambdaBTreeSet() [2/5]

◆ LambdaBTreeSet() [3/5]

◆ LambdaBTreeSet() [4/5]

◆ LambdaBTreeSet() [5/5]

Member Function Documentation

◆ load()

◆ operator=()

Friends And Related Function Documentation

◆ detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor >