The actual implementation of a b-tree data structure. More...

#include <LambdaBTree.h>

Inheritance diagram for souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >:

Collaboration diagram for souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >:

Public Types
using	parenttype = btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >

Public Types inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, 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 >

Public Member Functions
template<typename Iter >
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 Comparator &comp=Comparator(), const WeakComparator &weak_comp=WeakComparator())

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, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, detail::updater< Key > >
iterator	begin () const

	btree (btree &&other)

	btree (Comparator comp=Comparator(), Comparator weak_comp=Comparator())

	btree (const btree &set)

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

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 ()

Additional Inherited Members
Static Public Member Functions inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, 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...

Static Public Attributes inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, detail::updater< Key > >
static constexpr size_t	max_keys_per_node

Protected Types inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, 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, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, 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, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, detail::updater< Key > >
Comparator	comp

hint_statistics	hint_stats

leaf_node *	leftmost

node *	root

lock_type	root_lock

detail::updater< Key >	upd

Comparator	weak_comp

Static Protected Attributes inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Comparator, detail::updater< Key > >
const static SearchStrategy	search

Detailed Description

template<typename Key, typename Comparator, typename Allocator, unsigned blockSize, typename SearchStrategy, bool isSet, typename Functor, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
class souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >

The actual implementation of a b-tree data structure.

Template Parameters

Key	.. the element type to be stored in this tree
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
isSet	.. true = set, false = multiset
Functor	.. a std::function that is called on successful (new) insert

Definition at line 66 of file LambdaBTree.h.

Member Typedef Documentation

◆ parenttype

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

using souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::parenttype = btree<Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater>

Definition at line 79 of file LambdaBTree.h.

Constructor & Destructor Documentation

◆ LambdaBTree()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

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

inline

Definition at line 81 of file LambdaBTree.h.

Member Function Documentation

◆ insert() [1/3]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

template<typename Iter >

void souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::insert	(	const Iter &	a,
		const Iter &	b
	)

inline

Inserts the given range of elements into this tree.

Definition at line 509 of file LambdaBTree.h.

                            {
             return *this;
         }
  
         // clone content (deep copy)
         this->root = other.root->clone();

◆ insert() [2/3]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

Functor::result_type souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::insert	(	Key &	k,
		const Functor &	f
	)

inline

Inserts the given key into this tree.

Definition at line 87 of file LambdaBTree.h.

◆ insert() [3/3]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

Functor::result_type souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::insert	(	Key &	k,
		typename parenttype::operation_hints &	hints,
		const Functor &	f
	)

inline

Definition at line 93 of file LambdaBTree.h.

                                                                    {
             // ignore null pointer
             if (!last_insert) return false;
             // get a read lease on indicated node
             auto hint_lease = last_insert->lock.start_read();
             // check whether it covers the key
             if (!this->weak_covers(last_insert, k)) return false;
             // and if there was no concurrent modification
             if (!last_insert->lock.validate(hint_lease)) return false;
             // use hinted location
             cur = last_insert;
             // and keep lease
             cur_lease = hint_lease;
             // we found a hit
             return true;
         };
  
         if (hints.last_insert.any(checkHint)) {
             // register this as a hit
             this->hint_stats.inserts.addHit();
         } else {
             // register this as a miss
             this->hint_stats.inserts.addMiss();
         }
  
         // if there is no valid hint ..
         if (!cur) {
             do {
                 // get root - access lock
                 auto root_lease = this->root_lock.start_read();
  
                 // start with root
                 cur = this->root;
  
                 // get lease of the next node to be accessed
                 cur_lease = cur->lock.start_read();
  
                 // check validity of root pointer
                 if (this->root_lock.end_read(root_lease)) {
                     break;
                 }
  
             } while (true);
         }
  
         while (true) {
             // handle inner nodes
             if (cur->inner) {
                 auto a = &(cur->keys[0]);
                 auto b = &(cur->keys[cur->numElements]);
  
                 auto pos = this->search.lower_bound(k, a, b, this->weak_comp);
                 auto idx = pos - a;
  
                 // early exit for sets
                 if (isSet && pos != b && this->weak_equal(*pos, k)) {
                     // validate results
                     if (!cur->lock.validate(cur_lease)) {
                         // start over again
                         return insert(k, hints, f);
                     }
  
                     // update provenance information
                     if (typeid(Comparator) != typeid(WeakComparator) && this->less(k, *pos)) {
                         if (!cur->lock.try_upgrade_to_write(cur_lease)) {
                             // start again
                             return insert(k, hints, f);
                         }
                         this->update(*pos, k);
  
                         // get result before releasing lock
                         auto res = (*pos).second;
  
                         cur->lock.end_write();
                         return res;
                     }
  
                     // get the result before releasing lock
                     auto res = (*pos).second;
  
                     // check validity
                     if (!cur->lock.validate(cur_lease)) {
                         // start over again
                         return insert(k, hints, f);
                     }
  
                     // we found the element => return the result
                     return res;
                 }
  
                 // get next pointer
                 auto next = cur->getChild(idx);
  
                 // get lease on next level
                 auto next_lease = next->lock.start_read();
  
                 // check whether there was a write
                 if (!cur->lock.end_read(cur_lease)) {
                     // start over
                     return insert(k, hints, f);
                 }
  
                 // go to next
                 cur = next;
  
                 // move on lease
                 cur_lease = next_lease;
  
                 continue;
             }
  
             // the rest is for leaf nodes
             assert(!cur->inner);
  
             // -- insert node in leaf node --
  
             auto a = &(cur->keys[0]);
             auto b = &(cur->keys[cur->numElements]);
  
             auto pos = this->search.upper_bound(k, a, b, this->weak_comp);
             auto idx = pos - a;
  
             // early exit for sets
             if (isSet && pos != a && this->weak_equal(*(pos - 1), k)) {
                 // validate result
                 if (!cur->lock.validate(cur_lease)) {
                     // start over again
                     return insert(k, hints, f);
                 }
  
                 // TODO (pnappa): remove provenance from LambdaBTree - no use for it
                 // update provenance information
                 if (typeid(Comparator) != typeid(WeakComparator) && this->less(k, *(pos - 1))) {
                     if (!cur->lock.try_upgrade_to_write(cur_lease)) {
                         // start again
                         return insert(k, hints, f);
                     }
                     this->update(*(pos - 1), k);
  
                     // retrieve result before releasing lock
                     auto res = (*(pos - 1)).second;
  
                     cur->lock.end_write();
                     return res;
                 }
  
                 // read result (atomic) -- just as a proof of concept, this is actually not valid!!
                 std::atomic<typename Functor::result_type>& loc =
                         *reinterpret_cast<std::atomic<typename Functor::result_type>*>(&(*(pos - 1)).second);
                 auto res = loc.load(std::memory_order_relaxed);
  
                 // check validity
                 if (!cur->lock.validate(cur_lease)) {
                     // start over again
                     return insert(k, hints, f);
                 }
  
                 // we found the element => done
                 return res;
             }
  
             // upgrade to write-permission
             if (!cur->lock.try_upgrade_to_write(cur_lease)) {
                 // something has changed => restart
                 hints.last_insert.access(cur);
                 return insert(k, hints, f);
             }
  
             if (cur->numElements >= parenttype::node::maxKeys) {
                 // -- lock parents --
                 auto priv = cur;
                 auto parent = priv->parent;
                 std::vector<typename parenttype::node*> parents;
                 do {
                     if (parent) {
                         parent->lock.start_write();
                         while (true) {
                             // check whether parent is correct
                             if (parent == priv->parent) {
                                 break;
                             }
                             // switch parent
                             parent->lock.abort_write();
                             parent = priv->parent;
                             parent->lock.start_write();
                         }
                     } else {
                         // lock root lock => since cur is root
                         this->root_lock.start_write();
                     }
  
                     // record locked node
                     parents.push_back(parent);
  
                     // stop at "sphere of influence"
                     if (!parent || !parent->isFull()) {
                         break;
                     }
  
                     // go one step higher
                     priv = parent;
                     parent = parent->parent;
  
                 } while (true);
  
                 // split this node
                 auto old_root = this->root;
                 idx -= cur->rebalance_or_split(
                         const_cast<typename parenttype::node**>(&this->root), this->root_lock, idx, parents);
  
                 // release parent lock
                 for (auto it = parents.rbegin(); it != parents.rend(); ++it) {
                     auto parent = *it;
  
                     // release this lock
                     if (parent) {
                         parent->lock.end_write();
                     } else {
                         if (old_root != this->root) {
                             this->root_lock.end_write();
                         } else {
                             this->root_lock.abort_write();
                         }
                     }
                 }
  
                 // insert element in right fragment
                 if (((typename parenttype::size_type)idx) > cur->numElements) {
                     // release current lock
                     cur->lock.end_write();
  
                     // insert in sibling
                     return insert(k, hints, f);
                 }
             }
  
             // ok - no split necessary
             assert(cur->numElements < parenttype::node::maxKeys && "Split required!");
  
             // move keys
             for (int j = cur->numElements; j > idx; --j) {
                 cur->keys[j] = cur->keys[j - 1];
             }
  
             // insert new element
             typename Functor::result_type res = f(k);
             cur->keys[idx] = k;
             cur->numElements++;
  
             // release lock on current node
             cur->lock.end_write();
  
             // remember last insertion position
             hints.last_insert.access(cur);
             return res;
         }
  
 #else
         // special handling for inserting first element
         if (this->empty()) {
             // create new node
             this->leftmost = new typename parenttype::leaf_node();
             this->leftmost->numElements = 1;
             // call the functor as we've successfully inserted
             typename Functor::result_type res = f(k);
             this->leftmost->keys[0] = k;
             this->root = this->leftmost;
  
             hints.last_insert.access(this->leftmost);
  
             return res;
         }
  
         // insert using iterative implementation
         typename parenttype::node* cur = this->root;
  
         auto checkHints = [&](typename parenttype::node* last_insert) {
             if (!last_insert) return false;
             if (!this->weak_covers(last_insert, k)) return false;
             cur = last_insert;
             return true;
         };
  
         // test last insert
         if (hints.last_insert.any(checkHints)) {
             this->hint_stats.inserts.addHit();
         } else {
             this->hint_stats.inserts.addMiss();
         }
  
         while (true) {
             // handle inner nodes
             if (cur->inner) {
                 auto a = &(cur->keys[0]);
                 auto b = &(cur->keys[cur->numElements]);
  
                 auto pos = this->search.lower_bound(k, a, b, this->weak_comp);
                 auto idx = pos - a;
  
                 // early exit for sets
                 if (isSet && pos != b && this->weak_equal(*pos, k)) {
                     // update provenance information
                     if (typeid(Comparator) != typeid(WeakComparator) && this->less(k, *pos)) {
                         this->update(*pos, k);
                         return (*pos).second;
                     }
  
                     return (*pos).second;
                 }
  
                 cur = cur->getChild(idx);
                 continue;
             }
  
             // the rest is for leaf nodes
             assert(!cur->inner);
  
             // -- insert node in leaf node --
  
             auto a = &(cur->keys[0]);
             auto b = &(cur->keys[cur->numElements]);
  
             auto pos = this->search.upper_bound(k, a, b, this->weak_comp);
             auto idx = pos - a;
  
             // early exit for sets
             if (isSet && pos != a && this->weak_equal(*(pos - 1), k)) {
                 // update provenance information
                 if (typeid(Comparator) != typeid(WeakComparator) && this->less(k, *(pos - 1))) {
                     this->update(*(pos - 1), k);
                     return (*(pos - 1)).second;
                 }
  
                 return (*(pos - 1)).second;
             }
  
             if (cur->numElements >= parenttype::node::maxKeys) {
                 // split this node
                 idx -= cur->rebalance_or_split(
                         const_cast<typename parenttype::node**>(&this->root), this->root_lock, idx);
  
                 // insert element in right fragment
                 if (((typename parenttype::size_type)idx) > cur->numElements) {
                     idx -= cur->numElements + 1;
                     cur = cur->parent->getChild(cur->position + 1);
                 }
             }
  
             // ok - no split necessary
             assert(cur->numElements < parenttype::node::maxKeys && "Split required!");
  
             // move keys
             for (int j = cur->numElements; j > idx; --j) {
                 cur->keys[j] = cur->keys[j - 1];
             }
  
             // call the functor as we've successfully inserted
             typename Functor::result_type res = f(k);
             // insert new element
             cur->keys[idx] = k;
             cur->numElements++;
  
             // remember last insertion position
             hints.last_insert.access(cur);
             return res;
         }
 #endif
     }
  
     /**
      * Inserts the given range of elements into this tree.
      */
     template <typename Iter>
     void insert(const Iter& a, const Iter& b) {
         // TODO: improve this beyond a naive insert
         typename parenttype::operation_hints hints;
         // a naive insert so far .. seems to work fine
         for (auto it = a; it != b; ++it) {
             // use insert with hint
             insert(*it, hints);
         }
     }
  
     /**
      * Swaps the content of this tree with the given tree. This
      * is a much more efficient operation than creating a copy and
      * realizing the swap utilizing assignment operations.
      */
     void swap(LambdaBTree& other) {
         // swap the content
         std::swap(this->root, other.root);
         std::swap(this->leftmost, other.leftmost);
     }
  
     // Implementation of the assignment operation for trees.

◆ operator!=()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

bool souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::operator!= ( const LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater > & other ) const

inline

Definition at line 582 of file LambdaBTree.h.

585 : super(comp) {}

◆ operator=()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

LambdaBTree& souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::operator= ( const LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater > & other )

inline

Definition at line 531 of file LambdaBTree.h.

                                                     {
         // check identity
         if (this == &other) {
             return true;
         }
  
         // check size
         if (this->size() != other.size()) {
             return false;
         }
         if (this->size() < other.size()) {
             return other == *this;
         }
  
         // check content
         for (const auto& key : other) {
             if (!contains(key)) {
                 return false;
             }
         }
         return true;
     }
  
     // Implementation of an inequality operation for trees.
     bool operator!=(const LambdaBTree& other) const {

Referenced by souffle::LambdaBTreeSet< StorePair, std::function< StatesBucket(StorePair &)>, souffle::EqrelMapComparator< StorePair > >::LambdaBTreeSet().

◆ operator==()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

bool souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::operator== ( const LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater > & other ) const

inline

Definition at line 558 of file LambdaBTree.h.

         : public detail::LambdaBTree<Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor> {
     using super = detail::LambdaBTree<Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor>;
  
     friend class detail::LambdaBTree<Key, Comparator, Allocator, blockSize, SearchStrategy, true, Functor>;

◆ swap()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename Functor , typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>

void souffle::detail::LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater >::swap ( LambdaBTree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, Functor, WeakComparator, Updater > & other )

inline

Swaps the content of this tree with the given tree.

This is a much more efficient operation than creating a copy and realizing the swap utilizing assignment operations.

Definition at line 524 of file LambdaBTree.h.

531 {

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

include/souffle/datastructure/LambdaBTree.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ parenttype

Constructor & Destructor Documentation

◆ LambdaBTree()

Member Function Documentation

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ operator!=()

◆ operator=()

◆ operator==()

◆ swap()