souffle  2.0.2-371-g6315b36
Public Member Functions | Static Public Member Functions | Private Types | Private Member Functions | Friends
souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater > Class Template Reference

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

#include <BTree.h>

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

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_setoperator= (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< chunkgetChunks (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
 
btreeoperator= (const btree &other)
 
bool operator== (const btree &other) const
 
std::vector< chunkpartition (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 ( 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.

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

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:
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 > >::leftmost
leaf_node * leftmost
Definition: BTree.h:1249
souffle::btree_set::super
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, true, WeakComparator, Updater > super
Definition: BTree.h:2244
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 > >::insert
bool insert(const Key &k)
Inserts the given key into this tree.
Definition: BTree.h:1328
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 > >::root
node * root
Definition: BTree.h:1242
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 > >::size
size_type size() const
Definition: BTree.h:1321
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15