souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node Struct Reference

The actual, generic node implementation covering the operations for both, inner and leaf nodes. More...

#include <BTree.h>

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

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

Public Member Functions
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
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

Static Public Attributes
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...

Private Member Functions
void	grow_parent (node **root, lock_type &root_lock, node *sibling)
	Inserts a new sibling into the parent of this node utilizing the last key of this node as a separation key. More...
void	insert_inner (node **root, lock_type &root_lock, unsigned pos, node *predecessor, const Key &key, node *newNode)
	Inserts a new element into an inner node (for internal use only). 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 >::node

The actual, generic node implementation covering the operations for both, inner and leaf nodes.

Definition at line 380 of file BTree.h.

Constructor & Destructor Documentation

node()

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 >::node::node ( bool  inner )

inline

Definition at line 396 of file BTree.h.

{

References i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::keys.

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(), 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(), souffle::detail::btree< Key, detail::comparator< Key >, std::allocator< Key >, blockSize, typename detail::default_strategy< Key >::type, isSet, detail::comparator< Key >, detail::updater< Key > >::coversUpperBound(), 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(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::inner_node::~inner_node().

Member Function Documentation

asInnerNode() [1/2]

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

inner_node& souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::asInnerNode ( )

inline

A utility function providing a reference to this node as an inner node.

Definition at line 434 of file BTree.h.

                                   {

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getChild(), souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getDepth(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base::isLeaf().

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

Here is the call graph for this function:

asInnerNode() [2/2]

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

const inner_node& souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::asInnerNode ( ) const

inline

A utility function providing a reference to this node as a const inner node.

Definition at line 443 of file BTree.h.

                                     {

check()

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

template<typename Comp >

bool souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::check ( Comp &  comp, const node *  root  ) const

inline

A function to verify the consistency of this node.

Parameters

root	... a reference to the root of the enclosing tree.

Returns

true if valid, false otherwise

Definition at line 994 of file BTree.h.

                   {
                // check parent relation
                if (!this->parent) {
                    std::cout << "Invalid null-parent!\n";
                    valid = false;
                } else {
                    if (this->parent->getChildren()[this->position] != this) {
                        std::cout << "Parent reference invalid!\n";
                        std::cout << "   Node:     " << this << "\n";
                        std::cout << "   Parent:   " << this->parent << "\n";
                        std::cout << "   Position: " << ((int)this->position) << "\n";
                        valid = false;
                    }
 
                    // check parent key
                    if (valid && this->position != 0 &&
                            !(comp(this->parent->keys[this->position - 1], keys[0]) < ((isSet) ? 0 : 1))) {
                        std::cout << "Left parent key not lower bound!\n";
                        std::cout << "   Node:     " << this << "\n";
                        std::cout << "   Parent:   " << this->parent << "\n";
                        std::cout << "   Position: " << ((int)this->position) << "\n";
                        std::cout << "   Key:   " << (this->parent->keys[this->position]) << "\n";
                        std::cout << "   Lower: " << (keys[0]) << "\n";
                        valid = false;
                    }
 
                    // check parent key
                    if (valid && this->position != this->parent->numElements &&
                            !(comp(keys[this->numElements - 1], this->parent->keys[this->position]) <
                                    ((isSet) ? 0 : 1))) {
                        std::cout << "Right parent key not lower bound!\n";
                        std::cout << "   Node:     " << this << "\n";
                        std::cout << "   Parent:   " << this->parent << "\n";
                        std::cout << "   Position: " << ((int)this->position) << "\n";
                        std::cout << "   Key:   " << (this->parent->keys[this->position]) << "\n";
                        std::cout << "   Upper: " << (keys[0]) << "\n";
                        valid = false;
                    }
                }
            }
 
            // check element order
            if (this->numElements > 0) {
                for (unsigned i = 0; i < this->numElements - 1; i++) {
                    if (valid && !(comp(keys[i], keys[i + 1]) < ((isSet) ? 0 : 1))) {
                        std::cout << "Element order invalid!\n";
                        std::cout << " @" << this << " key " << i << " is " << keys[i] << " vs "
                                  << keys[i + 1] << "\n";
                        valid = false;
                    }
                }
            }
 
            // check state of sub-nodes
            if (this->inner) {
                for (unsigned i = 0; i <= this->numElements; i++) {
                    valid &= getChildren()[i]->check(comp, root);
                }
            }
 
            return valid;
        }
    };  // namespace detail
 
    /**
     * 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.
     */
    struct inner_node : public node {
        // references to child nodes owned by this node
        node* children[node::maxKeys + 1];
 
        // a simple default constructor initializing member fields
        inner_node() : node(true) {}
 

clone()

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 >::node::clone ( ) const

inline

A deep-copy operation creating a clone of this node.

Definition at line 401 of file BTree.h.

                                {
                return res;
            }
 
            // copy child nodes recursively
            auto* ires = (inner_node*)res;
            for (size_type i = 0; i <= this->numElements; ++i) {
                ires->children[i] = this->getChild(i)->clone();
                ires->children[i]->parent = res;
            }
 
            // that's it
            return res;
        }
 
        /**
         * A utility function providing a reference to this node as
         * an inner node.
         */
        inner_node& asInnerNode() {
            assert(this->inner && "Invalid cast!");
            return *static_cast<inner_node*>(this);
        }
 
        /**
         * A utility function providing a reference to this node as
         * a const inner node.
         */

collectChunks()

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 >::node::collectChunks ( std::vector< chunk > &  res, size_type  num, const iterator &  begin, const iterator &  end  ) const

inline

A function decomposing the sub-tree rooted by this node into approximately equally sized chunks.

To minimize computational overhead, no strict load balance nor limit on the number of actual chunks is given.

See also

btree::getChunks()

Parameters

res	.. the list of chunks to be extended
num	.. the number of chunks to be produced
begin	.. the iterator to start the first chunk with
end	.. the iterator to end the last chunk with

Returns

the handed in list of chunks extended by generated chunks

Definition at line 927 of file BTree.h.

                                                                 {
                auto step = this->numElements / num;
                if (step == 0) {
                    step = 1;
                }
 
                size_type i = 0;
 
                // the first chunk starts at the begin
                res.push_back(chunk(begin, iterator(this, static_cast<field_index_type>(step) - 1)));
 
                // split up the main part
                for (i = step - 1; i < this->numElements - step; i += step) {
                    res.push_back(chunk(iterator(this, static_cast<field_index_type>(i)),
                            iterator(this, static_cast<field_index_type>(i + step))));
                }
 
                // the last chunk runs to the end
                res.push_back(chunk(iterator(this, static_cast<field_index_type>(i)), end));
 
                // done
                return res;
            }
 
            // else: collect chunks of sub-set elements
 
            auto part = num / (this->numElements + 1);
            assert(part > 0);
            getChild(0)->collectChunks(res, part, begin, iterator(this, 0));
            for (size_type i = 1; i < this->numElements; i++) {
                getChild(i)->collectChunks(res, part, iterator(this, static_cast<field_index_type>(i - 1)),
                        iterator(this, static_cast<field_index_type>(i)));
            }
            getChild(this->numElements)
                    ->collectChunks(res, num - (part * this->numElements),
                            iterator(this, static_cast<field_index_type>(this->numElements) - 1), end);
 
            // done
            return res;
        }
 
        /**
         * A function to verify the consistency of this node.
         *
         * @param root ... a reference to the root of the enclosing tree.
         * @return true if valid, false otherwise
         */
        template <typename Comp>
        bool check(Comp& comp, const node* root) const {
            bool valid = true;
 
            // check fill-state
            if (this->numElements > maxKeys) {
                std::cout << "Node with " << this->numElements << "/" << maxKeys << " encountered!\n";

countEntries()

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 >::node::countEntries ( ) const

inline

Counts the number of entries contained in the sub-tree rooted by this node.

Definition at line 478 of file BTree.h.

                                         {
            if (this->isLeaf()) {
                return sizeof(leaf_node);
            }
            size_type res = sizeof(inner_node);
            for (unsigned i = 0; i <= this->numElements; ++i) {
                res += getChild(i)->getMemoryUsage();
            }
            return res;

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getChild(), souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getMemoryUsage(), i, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base::isLeaf(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base::numElements.

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::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::countNodes().

Here is the call graph for this function:

countNodes()

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 >::node::countNodes ( ) const

inline

Counts the number of nodes contained in the sub-tree rooted by this node.

Definition at line 463 of file BTree.h.

                                       {
            if (this->isLeaf()) {
                return this->numElements;
            }
            size_type sum = this->numElements;
            for (unsigned i = 0; i <= this->numElements; ++i) {
                sum += getChild(i)->countEntries();
            }
            return sum;

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::countEntries(), souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getChild(), i, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base::isLeaf(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base::numElements.

Here is the call graph for this function:

getChild()

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 >::node::getChild ( size_type  s ) const

inline

Obtains a reference to the child of the given index.

Definition at line 523 of file BTree.h.

                            {
            return this->numElements == maxKeys;
        }

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::maxKeys.

Referenced by souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::asInnerNode(), 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, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::countEntries(), souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::countNodes(), 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 > >::operator=().

getChildren() [1/2]

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 >::node::getChildren ( )

inline

Obtains a pointer to the array of child-pointers of this node – if it is an inner node.

Definition at line 508 of file BTree.h.

                                          {
            return asInnerNode().children[s];

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::asInnerNode(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::inner_node::children.

Referenced by souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::iterator::operator*(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::printTree().

Here is the call graph for this function:

getChildren() [2/2]

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

node* const* souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getChildren ( ) const

inline

Obtains a pointer to the array of const child-pointers of this node – if it is an inner node.

Definition at line 516 of file BTree.h.

                             {
            return this->numElements == 0;
        }

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 >::node::getDepth ( ) const

inline

Computes the number of nested levels of the tree rooted by this node.

Definition at line 452 of file BTree.h.

                                                              {
                sum += getChild(i)->countNodes();
            }
            return sum;

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

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 >::node::getMemoryUsage ( ) const

inline

Determines the amount of memory used by the sub-tree rooted by this node.

Definition at line 493 of file BTree.h.

                             {
            return asInnerNode().children;
        }
 
        /**
         * Obtains a pointer to the array of const child-pointers
         * of this node -- if it is an inner node.
         */
        node* const* getChildren() const {

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::asInnerNode(), and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::inner_node::children.

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

Here is the call graph for this function:

getSplitPoint()

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

int souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getSplitPoint ( int  )

inline

Obtains the point at which full nodes should be split.

Conventional b-trees always split in half. However, in cases where in-order insertions are frequent, a split assigning larger portions to the right fragment provide higher performance and a better node-filling rate.

Definition at line 548 of file BTree.h.

grow_parent()

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 >::node::grow_parent ( node **  root, lock_type &  root_lock, node *  sibling  )

inlineprivate

Inserts a new sibling into the parent of this node utilizing the last key of this node as a separation key.

(for internal use only)

Parameters

root	.. a pointer to the root-pointer of the containing tree
sibling	.. the new right-sibling to be add to the parent node

Definition at line 747 of file BTree.h.

                   {
                // insert new element in parent element
                auto parent = this->parent;
                auto pos = this->position;
 
#ifdef IS_PARALLEL
                parent->insert_inner(
                        root, root_lock, pos, this, keys[this->numElements], sibling, locked_nodes);
#else
                parent->insert_inner(root, root_lock, pos, this, keys[this->numElements], sibling);
#endif
            }
        }
 
        /**
         * Inserts a new element into an inner node (for internal use only).
         *
         * @param root .. a pointer to the root-pointer of the containing tree
         * @param pos  .. the position to insert the new key
         * @param key  .. the key to insert
         * @param newNode .. the new right-child of the inserted key
         */
#ifdef IS_PARALLEL
        void insert_inner(node** root, lock_type& root_lock, unsigned pos, node* predecessor, const Key& key,
                node* newNode, std::vector<node*>& locked_nodes) {
            assert(this->lock.is_write_locked());
            assert(souffle::contains(locked_nodes, this));

insert_inner()

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 >::node::insert_inner ( node **  root, lock_type &  root_lock, unsigned  pos, node *  predecessor, const Key &  key, node *  newNode  )

inlineprivate

Inserts a new element into an inner node (for internal use only).

Parameters

root	.. a pointer to the root-pointer of the containing tree
pos	.. the position to insert the new key
key	.. the key to insert
newNode	.. the new right-child of the inserted key

Definition at line 797 of file BTree.h.

                                             {
                    // correct position
                    pos = pos - static_cast<unsigned int>(this->numElements) - 1;
 
                    // get new sibling
                    auto other = this->parent->getChild(this->position + 1);
 
#ifdef IS_PARALLEL
                    // make sure other side is write locked
                    assert(other->lock.is_write_locked());
                    assert(souffle::contains(locked_nodes, other));
 
                    // search for new position (since other may have been altered in the meanwhile)
                    size_type i = 0;
                    for (; i <= other->numElements; ++i) {
                        if (other->getChild(i) == predecessor) {
                            break;
                        }
                    }
 
                    pos = (i > other->numElements) ? 0 : i;
                    other->insert_inner(root, root_lock, pos, predecessor, key, newNode, locked_nodes);
#else
                    other->insert_inner(root, root_lock, pos, predecessor, key, newNode);
#endif
                    return;
                }
            }
 
            // move bigger keys one forward
            for (int i = static_cast<int>(this->numElements) - 1; i >= (int)pos; --i) {
                keys[i + 1] = keys[i];
                getChildren()[i + 2] = getChildren()[i + 1];
                ++getChildren()[i + 2]->position;
            }
 
            // ensure proper position
            assert(getChild(pos) == predecessor);
 
            // insert new element
            keys[pos] = key;
            getChildren()[pos + 1] = newNode;
            newNode->parent = this;
            newNode->position = static_cast<field_index_type>(pos) + 1;
            ++this->numElements;
        }
 
    public:
        /**
         * Prints a textual representation of this tree to the given output stream.
         * This feature is mainly intended for debugging and tuning purposes.
         *
         * @see btree::printTree
         */
        void printTree(std::ostream& out, const std::string& prefix) const {
            // print the header
            out << prefix << "@" << this << "[" << ((int)(this->position)) << "] - "
                << (this->inner ? "i" : "") << "node : " << this->numElements << "/" << maxKeys << " [";
 
            // print the keys

isEmpty()

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 >::node::isEmpty ( ) const

inline

Checks whether this node is empty – can happen due to biased insertion.

Definition at line 530 of file BTree.h.

                                 {

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::maxKeys.

isFull()

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 >::node::isFull ( ) const

inline

Checks whether this node is full.

Definition at line 537 of file BTree.h.

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 >::node::printTree ( std::ostream &  out, const std::string &  prefix  ) const

inline

Prints a textual representation of this tree to the given output stream.

This feature is mainly intended for debugging and tuning purposes.

See also

btree::printTree

Definition at line 871 of file BTree.h.

                             {
                out << " - [";
                for (unsigned i = 0; i <= this->numElements; i++) {
                    out << getChildren()[i];
                    if (i != this->numElements) {
                        out << ",";
                    }
                }
                out << "]";
            }
 
#ifdef IS_PARALLEL
            // print the lock state
            if (this->lock.is_write_locked()) {
                std::cout << " locked";
            }
#endif
 
            out << "\n";
 
            // print the children recursively
            if (this->inner) {
                for (unsigned i = 0; i < this->numElements + 1; ++i) {
                    static_cast<const inner_node*>(this)->children[i]->printTree(out, prefix + "    ");
                }
            }
        }
 
        /**
         * A function decomposing the sub-tree rooted by this node into approximately equally
         * sized chunks. To minimize computational overhead, no strict load balance nor limit
         * on the number of actual chunks is given.
         *
         * @see btree::getChunks()
         *
         * @param res   .. the list of chunks to be extended
         * @param num   .. the number of chunks to be produced
         * @param begin .. the iterator to start the first chunk with
         * @param end   .. the iterator to end the last chunk with
         * @return the handed in list of chunks extended by generated chunks
         */

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::getChildren(), i, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::base::numElements.

Here is the call graph for this function:

rebalance_or_split()

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

int souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::rebalance_or_split ( node **  root, lock_type &  root_lock, int  idx  )

inline

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.

Returns the number of elements moved to the left side, 0 in case of a split. The number of moved elements will be <= the given idx.

Parameters

root	.. the root node of the b-tree being part of
idx	.. the position of the insert triggering this operation

Definition at line 632 of file BTree.h.

                                                   {
                    // left node is currently updated => skip balancing and split
                    split(root, root_lock, idx, locked_nodes);
                    return 0;
                }
#endif
 
                // compute number of elements to be movable to left
                //    space available in left vs. insertion index
                size_type num = static_cast<size_type>(
                        std::min<int>(static_cast<int>(maxKeys - left->numElements), idx));
 
                // if there are elements to move ..
                if (num > 0) {
                    Key* splitter = &(parent->keys[this->position - 1]);
 
                    // .. move keys to left node
                    left->keys[left->numElements] = *splitter;
                    for (size_type i = 0; i < num - 1; ++i) {
                        left->keys[left->numElements + 1 + i] = keys[i];
                    }
                    *splitter = keys[num - 1];
 
                    // shift keys in this node to the left
                    for (size_type i = 0; i < this->numElements - num; ++i) {
                        keys[i] = keys[i + num];
                    }
 
                    // .. and children if necessary
                    if (this->isInner()) {
                        auto* ileft = static_cast<inner_node*>(left);
                        auto* iright = static_cast<inner_node*>(this);
 
                        // move children
                        for (field_index_type i = 0; i < num; ++i) {
                            ileft->children[left->numElements + i + 1] = iright->children[i];
                        }
 
                        // update moved children
                        for (size_type i = 0; i < num; ++i) {
                            iright->children[i]->parent = ileft;
                            iright->children[i]->position =
                                    static_cast<field_index_type>(left->numElements + i) + 1;
                        }
 
                        // shift child-pointer to the left
                        for (size_type i = 0; i < this->numElements - num + 1; ++i) {
                            iright->children[i] = iright->children[i + num];
                        }
 
                        // update position of children
                        for (size_type i = 0; i < this->numElements - num + 1; ++i) {
                            iright->children[i]->position = static_cast<field_index_type>(i);
                        }
                    }
 
                    // update node sizes
                    left->numElements += num;
                    this->numElements -= num;
 
#ifdef IS_PARALLEL
                    left->lock.end_write();
#endif
 
                    // done
                    return static_cast<int>(num);
                }
 
#ifdef IS_PARALLEL
                left->lock.abort_write();
#endif
            }
 
            // Option B) split node
#ifdef IS_PARALLEL
            split(root, root_lock, idx, locked_nodes);
#else
            split(root, root_lock, idx);
#endif
            return 0;  // = no re-balancing
        }
 
    private:
        /**
         * Inserts a new sibling into the parent of this node utilizing
         * the last key of this node as a separation key. (for internal
         * use only)
         *
         * @param root .. a pointer to the root-pointer of the containing tree
         * @param sibling .. the new right-sibling to be add to the parent node
         */
#ifdef IS_PARALLEL
        void grow_parent(node** root, lock_type& root_lock, node* sibling, std::vector<node*>& locked_nodes) {
            assert(this->lock.is_write_locked());
            assert(!this->parent || this->parent->lock.is_write_locked());

References souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::root, souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::root_lock, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::split().

Here is the call graph for this function:

split()

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 >::node::split ( node **  root, lock_type &  root_lock, int  idx  )

inline

Splits this node.

Parameters

root	.. a pointer to the root-pointer of the enclosing b-tree (might have to be updated if the root-node needs to be split)
idx	.. the position of the insert causing the split

Definition at line 567 of file BTree.h.

                                                                             {
                sibling->keys[j] = keys[i];
            }
 
            // move child pointers
            if (this->inner) {
                // move pointers to sibling
                auto* other = static_cast<inner_node*>(sibling);
                for (unsigned i = split_point + 1, j = 0; i <= maxKeys; ++i, ++j) {
                    other->children[j] = getChildren()[i];
                    other->children[j]->parent = other;
                    other->children[j]->position = static_cast<field_index_type>(j);
                }
            }
 
            // update number of elements
            this->numElements = split_point;
            sibling->numElements = maxKeys - split_point - 1;
 
            // update parent
#ifdef IS_PARALLEL
            grow_parent(root, root_lock, sibling, locked_nodes);
#else
            grow_parent(root, root_lock, sibling);
#endif
        }
 
        /**
         * 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.
         *
         * Returns the number of elements moved to the left side, 0 in case
         * of a split. The number of moved elements will be <= the given idx.
         *
         * @param root .. the root node of the b-tree being part of
         * @param idx  .. the position of the insert triggering this operation
         */
        // TODO: remove root_lock ... no longer needed
#ifdef IS_PARALLEL

References i, j, and souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::keys.

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

Field Documentation

desiredNumKeys

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 >::node::desiredNumKeys

staticconstexpr

Initial value:

=
                ((blockSize > sizeof(base)) ? blockSize - sizeof(base) : 0) / sizeof(Key)

The number of keys/node desired by the user.

Definition at line 384 of file BTree.h.

keys

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

Key souffle::detail::btree< Key, Comparator, Allocator, blockSize, SearchStrategy, isSet, WeakComparator, Updater >::node::keys[maxKeys]

Definition at line 393 of file BTree.h.

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

maxKeys

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 >::node::maxKeys = (desiredNumKeys > 3) ? desiredNumKeys : 3

staticconstexpr

The actual number of keys/node corrected by functional requirements.

Definition at line 390 of file BTree.h.

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

---

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

• include/souffle/datastructure/BTree.h