The data type representing inner nodes of the b-tree. More...
#include <BTree.h>
Inheritance diagram for souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::inner_node:
Collaboration diagram for souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::inner_node:
Public Member Functions | |
| inner_node () | |
| ~inner_node () | |
 Public Member Functions inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node | |
| inner_node & | asInnerNode () |
| A utility function providing a reference to this node as an inner node. More... | |
| const inner_node & | asInnerNode () const |
| A utility function providing a reference to this node as a const inner node. More... | |
| template<typename Comp > | |
| bool | check (Comp &comp, const node *root) const |
| A function to verify the consistency of this node. More... | |
| node * | clone () const |
| A deep-copy operation creating a clone of this node. More... | |
| std::vector< chunk > & | collectChunks (std::vector< chunk > &res, size_type num, const iterator &begin, const iterator &end) const |
| A function decomposing the sub-tree rooted by this node into approximately equally sized chunks. More... | |
| size_type | countEntries () const |
| Counts the number of entries contained in the sub-tree rooted by this node. More... | |
| size_type | countNodes () const |
| Counts the number of nodes contained in the sub-tree rooted by this node. More... | |
| node * | getChild (size_type s) const |
| Obtains a reference to the child of the given index. More... | |
| node ** | getChildren () |
| Obtains a pointer to the array of child-pointers of this node – if it is an inner node. More... | |
| node *const * | getChildren () const |
| Obtains a pointer to the array of const child-pointers of this node – if it is an inner node. More... | |
| size_type | getDepth () const |
| Computes the number of nested levels of the tree rooted by this node. More... | |
| size_type | getMemoryUsage () const |
| Determines the amount of memory used by the sub-tree rooted by this node. More... | |
| int | getSplitPoint (int) |
| Obtains the point at which full nodes should be split. More... | |
| bool | isEmpty () const |
| Checks whether this node is empty – can happen due to biased insertion. More... | |
| bool | isFull () const |
| Checks whether this node is full. More... | |
| node (bool inner) | |
| void | printTree (std::ostream &out, const std::string &prefix) const |
| Prints a textual representation of this tree to the given output stream. More... | |
| 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 insertion of an element at position idx. More... | |
| void | split (node **root, lock_type &root_lock, int idx) |
| Splits this node. More... | |
| Public Member Functions inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base | |
| base (bool inner) | |
| A simple constructor for nodes. More... | |
| size_type | getNumElements () const |
| node * | getParent () const |
| field_index_type | getPositionInParent () const |
| bool | isInner () const |
| bool | isLeaf () const |
Data Fields | |
| node * | children [node::maxKeys+1] |
| Data Fields inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node | |
| Key | keys [maxKeys] |
| Data Fields inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base | |
| const bool | inner |
| size_type | numElements |
| node * | parent |
| field_index_type | position |
Additional Inherited Members | |
| Static Public Attributes inherited from souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node | |
| static constexpr size_t | desiredNumKeys |
| The number of keys/node desired by the user. More... | |
| static constexpr size_t | maxKeys = (desiredNumKeys > 3) ? desiredNumKeys : 3 |
| The actual number of keys/node corrected by functional requirements. More... | |
Detailed Description
template<typename Key, typename Comparator, typename Allocator, unsigned blockSize, typename SearchStrategy, bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
struct souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::inner_node
The data type representing inner nodes of the b-tree.
It extends the generic implementation of a node by the storage locations of child pointers.
Constructor & Destructor Documentation
◆ inner_node()
template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
|
inline |
◆ ~inner_node()
template<typename Key , typename Comparator , typename Allocator , unsigned blockSize, typename SearchStrategy , bool isSet, typename WeakComparator = Comparator, typename Updater = detail::updater<Key>>
|
inline |
Field Documentation
◆ children
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 >::inner_node::children[node::maxKeys+1] |
Definition at line 1080 of file BTree.h.
Referenced by souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getChildren(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getMemoryUsage().
The documentation for this struct was generated from the following file:
- include/souffle/datastructure/BTree.h
