souffle  2.0.2-371-g6315b36
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Protected Types | Protected Member Functions | Protected Attributes | Static Protected Attributes | Private Member Functions | Static Private Member Functions
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater > Class Template Reference

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

#include <BTree.h>

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

Data Structures

struct  base
 The base type of all node types containing essential book-keeping information. More...
 
struct  btree_operation_hints
 A collection of operation hints speeding up some of the involved operations by exploiting temporal locality. More...
 
struct  hint_statistics
 
struct  inner_node
 The data type representing inner nodes of the b-tree. More...
 
class  iterator
 The iterator type to be utilized for scanning through btree instances. More...
 
struct  leaf_node
 The data type representing leaf nodes of the b-tree. More...
 
struct  node
 The actual, generic node implementation covering the operations for both, inner and leaf nodes. More...
 

Public Types

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

iterator begin () const
 
 btree (btree &&other)
 
 btree (Comparator comp=Comparator(), WeakComparator weak_comp=WeakComparator())
 
 btree (const btree &set)
 
template<typename Iter >
 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
 
template<typename Iter >
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 R , typename Iter >
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

static constexpr size_t max_keys_per_node = node::maxKeys
 

Protected Types

using field_index_type = uint8_t
 
using lock_type = OptimisticReadWriteLock
 
using size_type = std::size_t
 

Protected Member Functions

 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

Comparator comp
 
hint_statistics hint_stats
 
leaf_node * leftmost
 
node * root
 
lock_type root_lock
 
Updater upd
 
WeakComparator weak_comp
 

Static Protected Attributes

const static SearchStrategy search
 

Private Member Functions

bool coversUpperBound (const node *node, const Key &k) const
 Determines whether the range covered by this node covers the upper bound of the given key. More...
 

Static Private Member Functions

template<typename Iter >
static node * buildSubTree (const Iter &a, const Iter &b)
 

Detailed Description

template<typename Key, typename Comparator, typename Allocator, unsigned blockSize, typename SearchStrategy, bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
class souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, 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

Definition at line 265 of file BTree.h.

Member Typedef Documentation

◆ chunk

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::chunk = range<iterator>

Definition at line 272 of file BTree.h.

◆ const_iterator

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::const_iterator = iterator

Definition at line 268 of file BTree.h.

◆ element_type

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::element_type = Key

Definition at line 271 of file BTree.h.

◆ field_index_type

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::field_index_type = uint8_t
protected

Definition at line 311 of file BTree.h.

◆ key_type

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::key_type = Key

Definition at line 270 of file BTree.h.

◆ lock_type

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::lock_type = OptimisticReadWriteLock
protected

Definition at line 312 of file BTree.h.

◆ operation_hints

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::operation_hints = btree_operation_hints<1>

Definition at line 1231 of file BTree.h.

◆ size_type

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
using souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::size_type = std::size_t
protected

Definition at line 310 of file BTree.h.

Constructor & Destructor Documentation

◆ btree() [1/5]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::btree ( Comparator  comp = Comparator(),
WeakComparator  weak_comp = WeakComparator() 
)
inline

Definition at line 1278 of file BTree.h.

1281  : comp(set.comp), weak_comp(set.weak_comp), root(nullptr), leftmost(nullptr) {

◆ btree() [2/5]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
template<typename Iter >
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::btree ( const Iter &  a,
const Iter &  b 
)
inline

Definition at line 1283 of file BTree.h.

1286  :
1287  /**

◆ btree() [3/5]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::btree ( btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater > &&  other)
inline

Definition at line 1288 of file BTree.h.

1291  : root(root), leftmost(leftmost) {}
1292 

◆ btree() [4/5]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::btree ( const btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater > &  set)
inline

Definition at line 1295 of file BTree.h.

1295  {
1296  clear();
1297  }
1298 

◆ btree() [5/5]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::btree ( size_type  ,
node *  root,
leaf_node *  leftmost 
)
inlineprotected

An internal constructor enabling the specific creation of a tree based on internal parameters.

Definition at line 1305 of file BTree.h.

1307 {

◆ ~btree()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::~btree ( )
inline

Definition at line 1309 of file BTree.h.

1314  {

Member Function Documentation

◆ begin()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::begin ( ) const
inline

Definition at line 1724 of file BTree.h.

Referenced by souffle::EquivalenceRelation< Arity >::size().

◆ buildSubTree()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
template<typename Iter >
static node* souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::buildSubTree ( const Iter &  a,
const Iter &  b 
)
inlinestaticprivate

Definition at line 2169 of file BTree.h.

2178  {
2179  numKeys--;
2180  step = ((length - numKeys) / (numKeys + 1));
2181  }
2182 
2183  // create inner node
2184  node* res = new inner_node();
2185  res->numElements = numKeys;
2186 
2187  Iter c = a;
2188  for (int i = 0; i < numKeys; i++) {
2189  // get dividing key
2190  res->keys[i] = c[step];
2191 
2192  // get sub-tree
2193  auto child = buildSubTree(c, c + (step - 1));
2194  child->parent = res;
2195  child->position = i;
2196  res->getChildren()[i] = child;
2197 
2198  c = c + (step + 1);
2199  }
2200 
2201  // and the remaining part
2202  auto child = buildSubTree(c, b);
2203  child->parent = res;
2204  child->position = numKeys;
2205  res->getChildren()[numKeys] = child;
2206 
2207  // done
2208  return res;
2209  }
2210 }; // namespace souffle
2211 
2212 // Instantiation of static member search.
2213 template <typename Key, typename Comparator, typename Allocator, unsigned blockSize, typename SearchStrategy,
2214  bool isSet, typename WeakComparator, typename Updater>
2215 const SearchStrategy
2216  btree<Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater>::search;
2217 
2218 } // end namespace detail
2219 
2220 /**
2221  * A b-tree based set implementation.
2222  *
2223  * @tparam Key .. the element type to be stored in this set

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::check().

◆ check()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::check ( )
inline

Checks the consistency of this tree.

Definition at line 2089 of file BTree.h.

2095  {

◆ clear()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
void souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::clear ( )
inline

Clears this tree.

Definition at line 1948 of file BTree.h.

1951  {
1952  // swap the content
1953  std::swap(root, other.root);
1954  std::swap(leftmost, other.leftmost);
1955  }
1956 
1957  // Implementation of the assignment operation for trees.
1958  btree& operator=(const btree& other) {

Referenced by 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(), and souffle::SparseDisjointSet< value_type >::size().

◆ contains() [1/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::contains ( const Key &  k) const
inline

Determines whether the given element is a member of this tree.

Definition at line 1756 of file BTree.h.

1758  {
1759  operation_hints hints;

Referenced by souffle::SparseDisjointSet< value_type >::makeNode(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::operator==(), and souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::partition().

◆ contains() [2/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::contains ( const Key &  k,
operation_hints &  hints 
) const
inline

Determines whether the given element is a member of this tree.

Definition at line 1764 of file BTree.h.

1767  {

◆ covers()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::covers ( const node *  node,
const Key &  k 
) const
inlineprotected

Determines whether the range covered by the given node is also covering the given key value.

Definition at line 2133 of file BTree.h.

2133  {
2134  // in sets we can include the ends as covered elements
2135  return !node->isEmpty() && !weak_less(k, node->keys[0]) &&
2136  !weak_less(node->keys[node->numElements - 1], k);
2137  }
2138  // in multi-sets the ends may not be completely covered
2139  return !node->isEmpty() && weak_less(node->keys[0], k) &&
2140  weak_less(k, node->keys[node->numElements - 1]);

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::find(), and souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::lower_bound().

◆ coversUpperBound()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::coversUpperBound ( const node *  node,
const Key &  k 
) const
inlineprivate

Determines whether the range covered by this node covers the upper bound of the given key.

Definition at line 2162 of file BTree.h.

2162  {
2163  // create a leaf node
2164  node* res = new leaf_node();
2165  res->numElements = length;

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::upper_bound().

◆ empty()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::empty ( ) const
inline

Definition at line 1316 of file BTree.h.

1322  {

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::contains().

◆ end()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::end ( ) const
inline

Definition at line 1729 of file BTree.h.

1731  {

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::contains(), souffle::EquivalenceRelation< Arity >::size(), and souffle::EquivalenceRelation< Arity >::upper_bound().

◆ equal()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::equal ( const Key &  a,
const Key &  b 
) const
inlineprotected

Definition at line 287 of file BTree.h.

290  {

◆ find() [1/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::find ( const Key &  k) const
inline

Locates the given key within this tree and returns an iterator referencing its position.

If not found, an end-iterator will be returned.

Definition at line 1772 of file BTree.h.

1774  {
1775  if (!last_find_end) return false;

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::EquivalenceRelation< Arity >::antpostit(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::contains(), and souffle::EquivalenceRelation< Arity >::upper_bound().

◆ find() [2/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::find ( const Key &  k,
operation_hints &  hints 
) const
inline

Locates the given key within this tree and returns an iterator referencing its position.

If not found, an end-iterator will be returned.

Definition at line 1781 of file BTree.h.

1782  {
1783  // register it as a hit
1784  hint_stats.contains.addHit();
1785  } else {
1786  // register it as a miss
1787  hint_stats.contains.addMiss();
1788  }
1789 
1790  // an iterative implementation (since 2/7 faster than recursive)
1791 
1792  while (true) {
1793  auto a = &(cur->keys[0]);
1794  auto b = &(cur->keys[cur->numElements]);
1795 
1796  auto pos = search(k, a, b, comp);
1797 
1798  if (pos < b && equal(*pos, k)) {
1799  hints.last_find_end.access(cur);
1800  return iterator(cur, static_cast<field_index_type>(pos - a));
1801  }
1802 
1803  if (!cur->inner) {
1804  hints.last_find_end.access(cur);
1805  return end();
1806  }
1807 
1808  // continue search in child node
1809  cur = cur->getChild(pos - a);
1810  }
1811  }
1812 
1813  /**
1814  * Obtains a lower boundary for the given key -- hence an iterator referencing
1815  * the smallest value that is not less the given key. If there is no such element,
1816  * an end-iterator will be returned.
1817  */
1818  iterator lower_bound(const Key& k) const {
1819  operation_hints hints;
1820  return lower_bound(k, hints);
1821  }
1822 
1823  /**
1824  * Obtains a lower boundary for the given key -- hence an iterator referencing
1825  * the smallest value that is not less the given key. If there is no such element,

◆ getChunks()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
std::vector<chunk> souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::getChunks ( size_type  num) const
inline

Definition at line 1745 of file BTree.h.

1750  {
1751  return find(k, hints) != end();

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::begin().

◆ getDepth()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
size_type souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::getDepth ( ) const
inline

Definition at line 2030 of file BTree.h.

◆ getMemoryUsage()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
size_type souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::getMemoryUsage ( ) const
inline

Definition at line 2040 of file BTree.h.

◆ getNumNodes()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
size_type souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::getNumNodes ( ) const
inline

Definition at line 2035 of file BTree.h.

2035  :\n";
2036  if (empty()) {
2037  out << " - empty - \n";

◆ insert() [1/3]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
template<typename Iter >
void souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert ( const Iter &  a,
const Iter &  b 
)
inline

Inserts the given range of elements into this tree.

Definition at line 1713 of file BTree.h.

1715  {
1716  return iterator();
1717  }
1718 
1719  /**
1720  * Partitions the full range of this set into up to a given number of chunks.
1721  * The chunks will cover approximately the same number of elements. Also, the

◆ insert() [2/3]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert ( const Key &  k)
inline

Inserts the given key into this tree.

Definition at line 1328 of file BTree.h.

1328  {
1329  // somebody else was faster => re-check
1330  continue;
1331  }

Referenced by souffle::btree_multiset< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_multiset(), souffle::btree_set< Key, Comparator, Allocator, blockSize, SearchStrategy, WeakComparator, Updater >::btree_set(), and souffle::test::TEST().

◆ insert() [3/3]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::insert ( const Key &  k,
operation_hints &  hints 
)
inline

Inserts the given key into this tree.

Definition at line 1336 of file BTree.h.

1361  {
1362  // ignore null pointer
1363  if (!last_insert) return false;
1364  // get a read lease on indicated node
1365  auto hint_lease = last_insert->lock.start_read();
1366  // check whether it covers the key
1367  if (!weak_covers(last_insert, k)) return false;
1368  // and if there was no concurrent modification
1369  if (!last_insert->lock.validate(hint_lease)) return false;
1370  // use hinted location
1371  cur = last_insert;
1372  // and keep lease
1373  cur_lease = hint_lease;
1374  // we found a hit
1375  return true;
1376  };
1377 
1378  if (hints.last_insert.any(checkHint)) {
1379  // register this as a hit
1380  hint_stats.inserts.addHit();
1381  } else {
1382  // register this as a miss
1383  hint_stats.inserts.addMiss();
1384  }
1385 
1386  // if there is no valid hint ..
1387  if (!cur) {
1388  do {
1389  // get root - access lock
1390  auto root_lease = root_lock.start_read();
1391 
1392  // start with root
1393  cur = root;
1394 
1395  // get lease of the next node to be accessed
1396  cur_lease = cur->lock.start_read();
1397 
1398  // check validity of root pointer
1399  if (root_lock.end_read(root_lease)) {
1400  break;
1401  }
1402 
1403  } while (true);
1404  }
1405 
1406  while (true) {
1407  // handle inner nodes
1408  if (cur->inner) {
1409  auto a = &(cur->keys[0]);
1410  auto b = &(cur->keys[cur->numElements]);
1411 
1412  auto pos = search.lower_bound(k, a, b, weak_comp);
1413  auto idx = pos - a;
1414 
1415  // early exit for sets
1416  if (isSet && pos != b && weak_equal(*pos, k)) {
1417  // validate results
1418  if (!cur->lock.validate(cur_lease)) {
1419  // start over again
1420  return insert(k, hints);
1421  }
1422 
1423  // update provenance information
1424  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *pos)) {
1425  if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1426  // start again
1427  return insert(k, hints);
1428  }
1429  update(*pos, k);
1430  cur->lock.end_write();
1431  return true;
1432  }
1433 
1434  // we found the element => no check of lock necessary
1435  return false;
1436  }
1437 
1438  // get next pointer
1439  auto next = cur->getChild(idx);
1440 
1441  // get lease on next level
1442  auto next_lease = next->lock.start_read();
1443 
1444  // check whether there was a write
1445  if (!cur->lock.end_read(cur_lease)) {
1446  // start over
1447  return insert(k, hints);
1448  }
1449 
1450  // go to next
1451  cur = next;
1452 
1453  // move on lease
1454  cur_lease = next_lease;
1455 
1456  continue;
1457  }
1458 
1459  // the rest is for leaf nodes
1460  assert(!cur->inner);
1461 
1462  // -- insert node in leaf node --
1463 
1464  auto a = &(cur->keys[0]);
1465  auto b = &(cur->keys[cur->numElements]);
1466 
1467  auto pos = search.upper_bound(k, a, b, weak_comp);
1468  auto idx = pos - a;
1469 
1470  // early exit for sets
1471  if (isSet && pos != a && weak_equal(*(pos - 1), k)) {
1472  // validate result
1473  if (!cur->lock.validate(cur_lease)) {
1474  // start over again
1475  return insert(k, hints);
1476  }
1477 
1478  // update provenance information
1479  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *(pos - 1))) {
1480  if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1481  // start again
1482  return insert(k, hints);
1483  }
1484  update(*(pos - 1), k);
1485  cur->lock.end_write();
1486  return true;
1487  }
1488 
1489  // we found the element => done
1490  return false;
1491  }
1492 
1493  // upgrade to write-permission
1494  if (!cur->lock.try_upgrade_to_write(cur_lease)) {
1495  // something has changed => restart
1496  hints.last_insert.access(cur);
1497  return insert(k, hints);
1498  }
1499 
1500  if (cur->numElements >= node::maxKeys) {
1501  // -- lock parents --
1502  auto priv = cur;
1503  auto parent = priv->parent;
1504  std::vector<node*> parents;
1505  do {
1506  if (parent) {
1507  parent->lock.start_write();
1508  while (true) {
1509  // check whether parent is correct
1510  if (parent == priv->parent) {
1511  break;
1512  }
1513  // switch parent
1514  parent->lock.abort_write();
1515  parent = priv->parent;
1516  parent->lock.start_write();
1517  }
1518  } else {
1519  // lock root lock => since cur is root
1520  root_lock.start_write();
1521  }
1522 
1523  // record locked node
1524  parents.push_back(parent);
1525 
1526  // stop at "sphere of influence"
1527  if (!parent || !parent->isFull()) {
1528  break;
1529  }
1530 
1531  // go one step higher
1532  priv = parent;
1533  parent = parent->parent;
1534 
1535  } while (true);
1536 
1537  // split this node
1538  auto old_root = root;
1539  idx -= cur->rebalance_or_split(const_cast<node**>(&root), root_lock, idx, parents);
1540 
1541  // release parent lock
1542  for (auto it = parents.rbegin(); it != parents.rend(); ++it) {
1543  auto parent = *it;
1544 
1545  // release this lock
1546  if (parent) {
1547  parent->lock.end_write();
1548  } else {
1549  if (old_root != root) {
1550  root_lock.end_write();
1551  } else {
1552  root_lock.abort_write();
1553  }
1554  }
1555  }
1556 
1557  // insert element in right fragment
1558  if (((size_type)idx) > cur->numElements) {
1559  // release current lock
1560  cur->lock.end_write();
1561 
1562  // insert in sibling
1563  return insert(k, hints);
1564  }
1565  }
1566 
1567  // ok - no split necessary
1568  assert(cur->numElements < node::maxKeys && "Split required!");
1569 
1570  // move keys
1571  for (int j = cur->numElements; j > idx; --j) {
1572  cur->keys[j] = cur->keys[j - 1];
1573  }
1574 
1575  // insert new element
1576  cur->keys[idx] = k;
1577  cur->numElements++;
1578 
1579  // release lock on current node
1580  cur->lock.end_write();
1581 
1582  // remember last insertion position
1583  hints.last_insert.access(cur);
1584  return true;
1585  }
1586 
1587 #else
1588  // special handling for inserting first element
1589  if (empty()) {
1590  // create new node
1591  leftmost = new leaf_node();
1592  leftmost->numElements = 1;
1593  leftmost->keys[0] = k;
1594  root = leftmost;
1595 
1596  hints.last_insert.access(leftmost);
1597 
1598  return true;
1599  }
1600 
1601  // insert using iterative implementation
1602  node* cur = root;
1603 
1604  auto checkHints = [&](node* last_insert) {
1605  if (!last_insert) return false;
1606  if (!weak_covers(last_insert, k)) return false;
1607  cur = last_insert;
1608  return true;
1609  };
1610 
1611  // test last insert
1612  if (hints.last_insert.any(checkHints)) {
1613  hint_stats.inserts.addHit();
1614  } else {
1615  hint_stats.inserts.addMiss();
1616  }
1617 
1618  while (true) {
1619  // handle inner nodes
1620  if (cur->inner) {
1621  auto a = &(cur->keys[0]);
1622  auto b = &(cur->keys[cur->numElements]);
1623 
1624  auto pos = search.lower_bound(k, a, b, weak_comp);
1625  auto idx = pos - a;
1626 
1627  // early exit for sets
1628  if (isSet && pos != b && weak_equal(*pos, k)) {
1629  // update provenance information
1630  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *pos)) {
1631  update(*pos, k);
1632  return true;
1633  }
1634 
1635  return false;
1636  }
1637 
1638  cur = cur->getChild(idx);
1639  continue;
1640  }
1641 
1642  // the rest is for leaf nodes
1643  assert(!cur->inner);
1644 
1645  // -- insert node in leaf node --
1646 
1647  auto a = &(cur->keys[0]);
1648  auto b = &(cur->keys[cur->numElements]);
1649 
1650  auto pos = search.upper_bound(k, a, b, weak_comp);
1651  auto idx = pos - a;
1652 
1653  // early exit for sets
1654  if (isSet && pos != a && weak_equal(*(pos - 1), k)) {
1655  // update provenance information
1656  if (typeid(Comparator) != typeid(WeakComparator) && less(k, *(pos - 1))) {
1657  update(*(pos - 1), k);
1658  return true;
1659  }
1660 
1661  return false;
1662  }
1663 
1664  if (cur->numElements >= node::maxKeys) {
1665  // split this node
1666  idx -= cur->rebalance_or_split(&root, root_lock, static_cast<int>(idx));
1667 
1668  // insert element in right fragment
1669  if (((size_type)idx) > cur->numElements) {
1670  idx -= cur->numElements + 1;
1671  cur = cur->parent->getChild(cur->position + 1);
1672  }
1673  }
1674 
1675  // ok - no split necessary
1676  assert(cur->numElements < node::maxKeys && "Split required!");
1677 
1678  // move keys
1679  for (int j = static_cast<int>(cur->numElements); j > idx; --j) {
1680  cur->keys[j] = cur->keys[j - 1];
1681  }
1682 
1683  // insert new element
1684  cur->keys[idx] = k;
1685  cur->numElements++;
1686 
1687  // remember last insertion position
1688  hints.last_insert.access(cur);
1689 
1690  return true;
1691  }
1692 #endif
1693  }
1694 
1695  /**
1696  * Inserts the given range of elements into this tree.
1697  */
1698  template <typename Iter>
1699  void insert(const Iter& a, const Iter& b) {
1700  // TODO: improve this beyond a naive insert
1701  operation_hints hints;
1702  // a naive insert so far .. seems to work fine
1703  for (auto it = a; it != b; ++it) {
1704  // use insert with hint
1705  insert(*it, hints);
1706  }
1707  }

◆ less()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::less ( const Key &  a,
const Key &  b 
) const
inlineprotected

Definition at line 283 of file BTree.h.

283  {
284  return weak_comp.equal(a, b);
285  }

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::weak_covers().

◆ load()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
template<typename R , typename Iter >
static std::enable_if<std::is_same<typename std::iterator_traits<Iter>::iterator_category, std::random_access_iterator_tag>::value, R>::type souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::load ( const Iter &  a,
const Iter &  b 
)
inlinestatic

A static member enabling the bulk-load of ordered data into an empty tree.

This function is much more efficient in creating a index over an ordered set of elements than an iterative insertion of values.

Template Parameters
Iter.. the type of iterator specifying the range it must be a random-access iterator

Definition at line 2109 of file BTree.h.

2114  :
2115  /**
2116  * Determines whether the range covered by the given node is also
2117  * covering the given key value.
2118  */
2119  bool covers(const node* node, const Key& k) const {
2120  if (isSet) {
2121  // in sets we can include the ends as covered elements
2122  return !node->isEmpty() && !less(k, node->keys[0]) && !less(node->keys[node->numElements - 1], k);
2123  }
2124  // in multi-sets the ends may not be completely covered
2125  return !node->isEmpty() && less(node->keys[0], k) && less(k, node->keys[node->numElements - 1]);
2126  }

◆ lower_bound() [1/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::lower_bound ( const Key &  k) const
inline

Obtains a lower boundary for the given key – hence an iterator referencing the smallest value that is not less the given key.

If there is no such element, an end-iterator will be returned.

Definition at line 1832 of file BTree.h.

1835  {

◆ lower_bound() [2/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::lower_bound ( const Key &  k,
operation_hints &  hints 
) const
inline

Obtains a lower boundary for the given key – hence an iterator referencing the smallest value that is not less the given key.

If there is no such element, an end-iterator will be returned.

Definition at line 1842 of file BTree.h.

1843  {
1844  hint_stats.lower_bound.addHit();
1845  } else {
1846  hint_stats.lower_bound.addMiss();
1847  }
1848 
1849  iterator res = end();
1850  while (true) {
1851  auto a = &(cur->keys[0]);
1852  auto b = &(cur->keys[cur->numElements]);
1853 
1854  auto pos = search.lower_bound(k, a, b, comp);
1855  auto idx = static_cast<field_index_type>(pos - a);
1856 
1857  if (!cur->inner) {
1858  hints.last_lower_bound_end.access(cur);
1859  return (pos != b) ? iterator(cur, idx) : res;
1860  }
1861 
1862  if (isSet && pos != b && equal(*pos, k)) {
1863  return iterator(cur, idx);
1864  }
1865 
1866  if (pos != b) {
1867  res = iterator(cur, idx);
1868  }
1869 
1870  cur = cur->getChild(idx);
1871  }
1872  }
1873 
1874  /**
1875  * Obtains an upper boundary for the given key -- hence an iterator referencing
1876  * the first element that the given key is less than the referenced value. If
1877  * there is no such element, an end-iterator will be returned.
1878  */
1879  iterator upper_bound(const Key& k) const {
1880  operation_hints hints;
1881  return upper_bound(k, hints);
1882  }
1883 
1884  /**
1885  * Obtains an upper boundary for the given key -- hence an iterator referencing
1886  * the first element that the given key is less than the referenced value. If

◆ operator!=()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::operator!= ( const btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater > &  other) const
inline

Definition at line 2023 of file BTree.h.

2026  {

◆ operator=()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
btree& souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::operator= ( const btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater > &  other)
inline

Definition at line 1972 of file BTree.h.

1975  {
1976  tmp = tmp->getChild(0);
1977  }
1978  leftmost = static_cast<leaf_node*>(tmp);
1979 
1980  // done
1981  return *this;
1982  }
1983 
1984  // Implementation of an equality operation for trees.
1985  bool operator==(const btree& other) const {
1986  // check identity
1987  if (this == &other) {
1988  return true;
1989  }
1990 
1991  // check size
1992  if (size() != other.size()) {
1993  return false;
1994  }
1995  if (size() < other.size()) {
1996  return other == *this;

◆ operator==()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::operator== ( const btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater > &  other) const
inline

Definition at line 1999 of file BTree.h.

2000  : other) {
2001  if (!contains(key)) {
2002  return false;
2003  }
2004  }
2005  return true;
2006  }
2007 
2008  // Implementation of an inequality operation for trees.
2009  bool operator!=(const btree& other) const {
2010  return !(*this == other);
2011  }
2012 
2013  // -- for debugging --
2014 
2015  // Determines the number of levels contained in this tree.
2016  size_type getDepth() const {
2017  return (empty()) ? 0 : root->getDepth();
2018  }
2019 
2020  // Determines the number of nodes contained in this tree.

◆ partition()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
std::vector<chunk> souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::partition ( size_type  num) const
inline

Partitions the full range of this set into up to a given number of chunks.

The chunks will cover approximately the same number of elements. Also, the number of chunks will only approximate the desired number of chunks.

Parameters
num.. the number of chunks requested
Returns
a list of chunks partitioning this tree

Definition at line 1741 of file BTree.h.

1742  {
1743  operation_hints hints;

◆ printStats()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
void souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::printStats ( std::ostream &  out = std::cout) const
inline

Prints a textual summary of statistical properties of this tree to the given output stream (for debugging and tuning).

Definition at line 2061 of file BTree.h.

2061  : " << hint_stats.inserts.getHits() << "/"
2062  << hint_stats.inserts.getMisses() << "/" << hint_stats.inserts.getAccesses() << "\n";
2063  out << " contains-hint(hits/misses/total):" << hint_stats.contains.getHits() << "/"
2064  << hint_stats.contains.getMisses() << "/" << hint_stats.contains.getAccesses() << "\n";
2065  out << " lower-bound-hint (hits/misses/total):" << hint_stats.lower_bound.getHits() << "/"
2066  << hint_stats.lower_bound.getMisses() << "/" << hint_stats.lower_bound.getAccesses() << "\n";
2067  out << " upper-bound-hint (hits/misses/total):" << hint_stats.upper_bound.getHits() << "/"
2068  << hint_stats.upper_bound.getMisses() << "/" << hint_stats.upper_bound.getAccesses() << "\n";
2069  out << " ---------------------------------\n";
2070  }
2071 
2072  /**
2073  * Checks the consistency of this tree.
2074  */
2075  bool check() {
2076  auto ok = empty() || root->check(comp, root);
2077  if (!ok) {
2078  printTree();
2079  }
2080  return ok;
2081  }
2082 
2083  /**
2084  * A static member enabling the bulk-load of ordered data into an empty

◆ printTree()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
void souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::printTree ( std::ostream &  out = std::cout) const
inline

Definition at line 2048 of file BTree.h.

2050  : " << size() << "\n";
2051  out << " Depth: " << (empty() ? 0 : root->getDepth()) << "\n";
2052  out << " Nodes: " << nodes << "\n";
2053  out << " ---------------------------------\n";
2054  out << " Size of inner node: " << sizeof(inner_node) << "\n";
2055  out << " Size of leaf node: " << sizeof(leaf_node) << "\n";

◆ size()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
size_type souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::size ( ) const
inline

Definition at line 1321 of file BTree.h.

1322  {
1323 #ifdef IS_PARALLEL

Referenced by souffle::EquivalenceRelation< Arity >::closure().

◆ swap()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
void souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::swap ( btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, 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 1965 of file BTree.h.

1966  {
1967  return *this;
1968  }
1969 

◆ update()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
void souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::update ( Key &  old_k,
const Key &  new_k 
)
inlineprotected

Definition at line 304 of file BTree.h.

306  {

◆ upper_bound() [1/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::upper_bound ( const Key &  k) const
inline

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.

If there is no such element, an end-iterator will be returned.

Definition at line 1893 of file BTree.h.

1896  {

◆ upper_bound() [2/2]

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
iterator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::upper_bound ( const Key &  k,
operation_hints &  hints 
) const
inline

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.

If there is no such element, an end-iterator will be returned.

Definition at line 1903 of file BTree.h.

1904  {
1905  hint_stats.upper_bound.addHit();
1906  } else {
1907  hint_stats.upper_bound.addMiss();
1908  }
1909 
1910  iterator res = end();
1911  while (true) {
1912  auto a = &(cur->keys[0]);
1913  auto b = &(cur->keys[cur->numElements]);
1914 
1915  auto pos = search.upper_bound(k, a, b, comp);
1916  auto idx = static_cast<field_index_type>(pos - a);
1917 
1918  if (!cur->inner) {
1919  hints.last_upper_bound_end.access(cur);
1920  return (pos != b) ? iterator(cur, idx) : res;
1921  }
1922 
1923  if (pos != b) {
1924  res = iterator(cur, idx);
1925  }
1926 
1927  cur = cur->getChild(idx);
1928  }
1929  }
1930 
1931  /**
1932  * Clears this tree.
1933  */
1934  void clear() {
1935  if (root != nullptr) {
1936  if (root->isLeaf()) {
1937  delete static_cast<leaf_node*>(root);
1938  } else {
1939  delete static_cast<inner_node*>(root);
1940  }
1941  }
1942  root = nullptr;
1943  leftmost = nullptr;

◆ weak_covers()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::weak_covers ( const node *  node,
const Key &  k 
) const
inlineprotected

Determines whether the range covered by the given node is also covering the given key value.

Definition at line 2146 of file BTree.h.

2148  {
2149  // ignore edges
2150  return !node->isEmpty() && !less(k, node->keys[0]) && less(k, node->keys[node->numElements - 1]);
2151  }
2152 
2153  // Utility function for the load operation above.
2154  template <typename Iter>
2155  static node* buildSubTree(const Iter& a, const Iter& b) {

◆ weak_equal()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::weak_equal ( const Key &  a,
const Key &  b 
) const
inlineprotected

Definition at line 297 of file BTree.h.

306  {

◆ weak_less()

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::weak_less ( const Key &  a,
const Key &  b 
) const
inlineprotected

Definition at line 293 of file BTree.h.

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::covers().

Field Documentation

◆ comp

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
Comparator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::comp
mutableprotected

Definition at line 281 of file BTree.h.

◆ hint_stats

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
hint_statistics souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::hint_stats
mutableprotected

Definition at line 1269 of file BTree.h.

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::find(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::lower_bound(), and souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::upper_bound().

◆ leftmost

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
leaf_node* souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::leftmost
protected

Definition at line 1249 of file BTree.h.

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::check(), and souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::clear().

◆ max_keys_per_node

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
constexpr size_t souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::max_keys_per_node = node::maxKeys
staticconstexpr

Definition at line 1273 of file BTree.h.

◆ root

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
node* souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::root
protected

Definition at line 1242 of file BTree.h.

Referenced by 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(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::check(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::clear(), souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::rebalance_or_split(), and souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::size().

◆ root_lock

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
lock_type souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::root_lock
protected

Definition at line 1245 of file BTree.h.

Referenced by souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::rebalance_or_split().

◆ search

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator , typename Updater >
const SearchStrategy souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::search
staticprotected

Definition at line 277 of file BTree.h.

Referenced by souffle::detail::updater< StorePair >::update().

◆ upd

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
Updater souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::upd
mutableprotected

Definition at line 303 of file BTree.h.

◆ weak_comp

template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
WeakComparator souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::weak_comp
mutableprotected

Definition at line 291 of file BTree.h.

Referenced by souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::less().

The documentation for this class was generated from the following file:
souffle::detail::btree::root_lock
lock_type root_lock
Definition: BTree.h:1245
souffle::detail::btree::empty
bool empty() const
Definition: BTree.h:1316
souffle::detail::btree::weak_less
bool weak_less(const Key &a, const Key &b) const
Definition: BTree.h:293
souffle::detail::btree::search
const static SearchStrategy search
Definition: BTree.h:277
souffle::CacheAccessCounter::addMiss
void addMiss()
Definition: CacheUtil.h:283
souffle::detail::btree::node::rebalance_or_split
int rebalance_or_split(node **root, lock_type &root_lock, int idx)
Moves keys from this node to one of its siblings or splits this node to make some space for the inser...
Definition: BTree.h:632
souffle::detail::btree::clear
void clear()
Clears this tree.
Definition: BTree.h:1948
souffle::detail::btree::update
void update(Key &old_k, const Key &new_k)
Definition: BTree.h:304
souffle::detail::btree::hint_statistics::upper_bound
CacheAccessCounter upper_bound
Definition: BTree.h:1265
souffle::detail::btree::leftmost
leaf_node * leftmost
Definition: BTree.h:1249
souffle::detail::btree::equal
bool equal(const Key &a, const Key &b) const
Definition: BTree.h:287
souffle::detail::btree::end
iterator end() const
Definition: BTree.h:1729
souffle::OptimisticReadWriteLock::start_read
Lease start_read()
Definition: ParallelUtil.h:532
souffle::detail::btree::weak_comp
WeakComparator weak_comp
Definition: BTree.h:291
souffle::detail::btree::field_index_type
uint8_t field_index_type
Definition: BTree.h:311
Comparator
souffle::detail::btree::btree
btree(Comparator comp=Comparator(), WeakComparator weak_comp=WeakComparator())
Definition: BTree.h:1278
souffle::detail::btree::less
bool less(const Key &a, const Key &b) const
Definition: BTree.h:283
souffle::detail::btree::comp
Comparator comp
Definition: BTree.h:281
souffle::detail::btree::size_type
std::size_t size_type
Definition: BTree.h:310
souffle::detail::btree::operator!=
bool operator!=(const btree &other) const
Definition: BTree.h:2023
n
var n
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::operator==
bool operator==(const btree &other) const
Definition: BTree.h:1999
j
var j
Definition: htmlJsChartistMin.h:15
souffle::OptimisticReadWriteLock::abort_write
void abort_write()
Definition: ParallelUtil.h:554
souffle::ram::Nodes
MinIndexSelection::SearchSet Nodes
Definition: matching_test.cpp:42
souffle::detail::btree::insert
bool insert(const Key &k)
Inserts the given key into this tree.
Definition: BTree.h:1328
souffle::detail::btree::weak_equal
bool weak_equal(const Key &a, const Key &b) const
Definition: BTree.h:297
souffle::detail::btree::buildSubTree
static node * buildSubTree(const Iter &a, const Iter &b)
Definition: BTree.h:2169
souffle::detail::btree::node::keys
Key keys[maxKeys]
Definition: BTree.h:393
souffle::detail::btree::weak_covers
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.
Definition: BTree.h:2146
i
size_t i
Definition: json11.h:663
souffle::detail::btree::base::numElements
size_type numElements
Definition: BTree.h:339
souffle::detail::btree::hint_statistics::inserts
CacheAccessCounter inserts
Definition: BTree.h:1256
souffle::detail::btree::root
node * root
Definition: BTree.h:1242
souffle::OptimisticReadWriteLock::start_write
void start_write()
Definition: ParallelUtil.h:544
souffle::detail::btree::hint_stats
hint_statistics hint_stats
Definition: BTree.h:1269
souffle::detail::btree::size
size_type size() const
Definition: BTree.h:1321
souffle::detail::btree::node::getDepth
size_type getDepth() const
Computes the number of nested levels of the tree rooted by this node.
Definition: BTree.h:452
souffle::CacheAccessCounter::addHit
void addHit()
Definition: CacheUtil.h:282
k
var k
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::find
iterator find(const Key &k) const
Locates the given key within this tree and returns an iterator referencing its position.
Definition: BTree.h:1772
souffle::detail::btree::base::isLeaf
bool isLeaf() const
Definition: BTree.h:353
souffle::OptimisticReadWriteLock::end_write
void end_write()
Definition: ParallelUtil.h:556
souffle::detail::btree::covers
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.
Definition: BTree.h:2133
souffle::detail::btree::getDepth
size_type getDepth() const
Definition: BTree.h:2030
b
l j a showGridBackground &&c b raw series this eventEmitter b
Definition: htmlJsChartistMin.h:15
souffle::detail::btree::operator=
btree & operator=(const btree &other)
Definition: BTree.h:1972
souffle::OptimisticReadWriteLock::end_read
bool end_read(const Lease &)
Definition: ParallelUtil.h:540
souffle::detail::btree::upper_bound
iterator upper_bound(const Key &k) const
Obtains an upper boundary for the given key – hence an iterator referencing the first element that th...
Definition: BTree.h:1893
souffle::detail::btree::contains
bool contains(const Key &k) const
Determines whether the given element is a member of this tree.
Definition: BTree.h:1756
souffle::detail::btree::hint_statistics::contains
CacheAccessCounter contains
Definition: BTree.h:1259
souffle::detail::btree::lower_bound
iterator lower_bound(const Key &k) const
Obtains a lower boundary for the given key – hence an iterator referencing the smallest value that is...
Definition: BTree.h:1832
souffle::detail::btree::operation_hints
btree_operation_hints< 1 > operation_hints
Definition: BTree.h:1231
souffle::detail::btree::hint_statistics::lower_bound
CacheAccessCounter lower_bound
Definition: BTree.h:1262
souffle::detail::btree::node::maxKeys
static constexpr size_t maxKeys
The actual number of keys/node corrected by functional requirements.
Definition: BTree.h:390
Generated by   doxygen 1.8.17