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

#include <BTree.h>

Inheritance diagram for souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >:

Collaboration diagram for souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >:

Public Member Functions
	btree_set (btree_set &&other)

	btree_set (const btree_set &other)

	btree_set (const Comparator &comp=Comparator(), const WeakComparator &weak_comp=WeakComparator())
	A default constructor creating an empty set. More...

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

btree_set &	operator= (const btree_set &other)

Public Member Functions inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::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 btree_set	load (const Iter &a, const Iter &b)

Static Public Member Functions inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::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 = souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater >

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

Friends
class	souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater >

Additional Inherited Members
Public Types inherited from souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::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 >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::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 >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::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 >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::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 >, 256, typename souffle::detail::default_strategy< Key >::type, true, detail::comparator< Key >, souffle::detail::updater< Key > >
detail::comparator< Key >	comp

hint_statistics	hint_stats

leaf_node *	leftmost

node *	root

lock_type	root_lock

souffle::detail::updater< Key >	upd

detail::comparator< Key >	weak_comp

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

Detailed Description

template<typename Key, typename Comparator = detail::comparator<Key>, typename Allocator = std::allocator<Key>, unsigned blockSize = 256, typename SearchStrategy = typename souffle::detail::default_strategy<Key>::type, typename WeakComparator = Comparator, typename Updater = souffle::detail::updater<Key>>
class souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >

A b-tree based set implementation.

Template Parameters

Key	.. the element type to be stored in this set
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 2241 of file BTree.h.

Member Typedef Documentation

◆ super

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

using souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::super = souffle::detail::btree<Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater>

private

Definition at line 2244 of file BTree.h.

Constructor & Destructor Documentation

◆ btree_set() [1/5]

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

souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_set	(	const Comparator &	comp = `Comparator()`,
		const WeakComparator &	weak_comp = `WeakComparator()`
	)

inline

A default constructor creating an empty set.

Definition at line 2253 of file BTree.h.

2253 {

2254 this->insert(a, b);

References b, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert().

Here is the call graph for this function:

◆ btree_set() [2/5]

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

template<typename Iter >

souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_set	(	const Iter &	a,
		const Iter &	b
	)

inline

A constructor creating a set based on the given range.

Definition at line 2260 of file BTree.h.

2261 : super(std::move(other)) {}

2262

◆ btree_set() [3/5]

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

souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_set ( const btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater > & other )

inline

Definition at line 2265 of file BTree.h.

2266 : super(size, root, leftmost) {}

◆ btree_set() [4/5]

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

souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_set ( btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater > && other )

inline

Definition at line 2268 of file BTree.h.

2268 :

2269 // Support for the assignment operator.

◆ btree_set() [5/5]

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

template<typename s , typename n , typename l >

souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_set	(	s	size,
		n *	root,
		l *	leftmost
	)

inlineprivate

Definition at line 2273 of file BTree.h.

2277 {

Member Function Documentation

◆ load()

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

template<typename Iter >

static btree_set souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::load	(	const Iter &	a,
		const Iter &	b
	)

inlinestatic

Definition at line 2284 of file BTree.h.

◆ operator=()

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

btree_set& souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::operator= ( const btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater > & other )

inline

Definition at line 2277 of file BTree.h.

                                                         {
         return super::template load<btree_set>(a, b);
     }
 };

References b.

Friends And Related Function Documentation

◆ souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater >

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

friend class souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater >

friend

Definition at line 2247 of file BTree.h.

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

include/souffle/datastructure/BTree.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

◆ btree_set() [1/5]

◆ btree_set() [2/5]

◆ btree_set() [3/5]

◆ btree_set() [4/5]

◆ btree_set() [5/5]

Member Function Documentation

◆ load()

◆ operator=()

Friends And Related Function Documentation

◆ souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater >