souffle::SparseArray< T, BITS, merge_op, copy_op > Class Template Reference

A sparse array simulates an array associating to every element of uint32_t an element of a generic type T. More...

#include <Brie.h>

Collaboration diagram for souffle::SparseArray< T, BITS, merge_op, copy_op >:

Data Structures
union	Cell
	The value stored in a single cell of a inner or leaf node. More...
struct	FirstInfoSnapshot
	A struct summarizing the state of the first node reference. More...
struct	Node
	The node type of the internally maintained tree. More...
struct	op_context
	A struct to be utilized as a local, temporal context by client code to speed up the execution of various operations (optional parameter). More...
struct	RootInfo
	A struct describing all the information required by the container class to manage the wrapped up tree. More...
struct	RootInfoSnapshot
	A struct to cover a snapshot of the root node state. More...

Public Types
using	atomic_value_type = std::atomic< value_type >
using	index_type = key_type
using	iterator = SparseArrayIter< this_t >
using	value_type = T

Public Member Functions
void	addAll (const SparseArray &other)
	Adds all the values stored in the given array to this array. More...
iterator	begin () const
	Obtains an iterator referencing the first non-default element or end in case there are no such elements. More...
void	clear ()
	Resets the content of this array to default values for each contained element. More...
void	dump (bool detail=false, std::ostream &out=std::cout) const
	A debug utility printing the internal structure of this sparse array to the given output stream. More...
bool	empty () const
	Tests whether this sparse array is empty, thus it only contains default-values, or not. More...
iterator	end () const
	An iterator referencing the position after the last non-default element. More...
iterator	find (index_type i) const
	An operation to obtain an iterator referencing an element addressed by the given index. More...
iterator	find (index_type i, op_context &ctxt) const
	An operation to obtain an iterator referencing an element addressed by the given index. More...
value_type &	get (index_type i)
	Obtains a mutable reference to the value addressed by the given index. More...
value_type &	get (index_type i, op_context &ctxt)
	Obtains a mutable reference to the value addressed by the given index. More...
atomic_value_type &	getAtomic (index_type i)
	Obtains a mutable reference to the atomic value addressed by the given index. More...
atomic_value_type &	getAtomic (index_type i, op_context &ctxt)
	Obtains a mutable reference to the atomic value addressed by the given index. More...
std::size_t	getMemoryUsage () const
	Computes the total memory usage of this data structure. More...
value_type	lookup (index_type i) const
	Obtains the value associated to index i – which might be the default value of the covered type if the value hasn't been defined previously. More...
value_type	lookup (index_type i, op_context &ctxt) const
	Obtains the value associated to index i – which might be the default value of the covered type if the value hasn't been defined previously. More...
iterator	lowerBound (index_type i) const
	An operation obtaining the smallest non-default element such that it's index is >= the given index. More...
iterator	lowerBound (index_type i, op_context &) const
	An operation obtaining the smallest non-default element such that it's index is >= the given index. More...
SparseArray &	operator= (const SparseArray &other)
	An assignment creating a deep copy of the handed in array structure (utilizing the copy functor provided as a template parameter). More...
SparseArray &	operator= (SparseArray &&other)
	An assignment operation taking over ownership from a r-value reference to a sparse array. More...
value_type	operator[] (index_type i) const
	Obtains the value associated to index i – which might be the default value of the covered type if the value hasn't been defined previously. More...
std::size_t	size () const
	Computes the number of non-empty elements within this sparse array. More...
	SparseArray ()
	A default constructor creating an empty sparse array. More...
	SparseArray (const SparseArray &other)
	A copy constructor for sparse arrays. More...
	SparseArray (SparseArray &&other)
	A r-value based copy constructor for sparse arrays. More...
void	update (index_type i, const value_type &val)
	Updates the value stored in cell i by the given value. More...
void	update (index_type i, const value_type &val, op_context &ctxt)
	Updates the value stored in cell i by the given value. More...
iterator	upperBound (index_type i) const
	An operation obtaining the smallest non-default element such that it's index is greater the given index. More...
iterator	upperBound (index_type i, op_context &ctxt) const
	An operation obtaining the smallest non-default element such that it's index is greater the given index. More...
	~SparseArray ()
	A destructor for sparse arrays clearing up the internally maintained data structure. More...

Private Types
using	key_type = uint64_t
using	this_t = SparseArray< T, BITS, merge_op, copy_op >

Private Member Functions
void	clean ()
	Conducts a cleanup of the internal tree structure. More...
void	dump (bool detailed, std::ostream &out, const Node &node, int level, index_type offset, int indent=0) const
	An internal debug utility printing the internal structure of this sparse array to the given output stream. More...
FirstInfoSnapshot	getFirstInfo () const
	Obtains a snapshot of the current first-node information. More...
uint64_t	getFirstVersion () const
	Obtains the current version number of the first node information. More...
Cell &	getLeaf (index_type i, op_context &ctxt)
	An internal function capable of navigating to a given leaf node entry. More...
RootInfoSnapshot	getRootInfo () const
	Obtains a snapshot of the current root information. More...
uint64_t	getRootVersion () const
	Obtains the current version of the root. More...
bool	inBoundaries (index_type a) const
	Tests whether the given index is covered by the boundaries defined by the hight and offset of the internally maintained tree. More...
void	raiseLevel ()
	Raises the level of this tree by one level. More...
void	raiseLevel (RootInfoSnapshot &info)
	Attempts to raise the height of this tree based on the given root node information and updates the root-info snapshot correspondingly. More...
bool	tryUpdateFirstInfo (const FirstInfoSnapshot &info)
	Updates the information stored regarding the first node in a concurrent setting utilizing a optimistic locking approach. More...
bool	tryUpdateRootInfo (const RootInfoSnapshot &info)
	Updates the current root information based on the handed in modified snapshot instance if the version number of the snapshot still corresponds to the current version. More...

Static Private Member Functions
static Node *	clone (const Node *node, int level)
	Clones the given node and all its sub-nodes. More...
static Node *	findFirst (Node *node, int level)
	Obtains the left-most leaf-node of the tree rooted by the given node with the given level. More...
static void	freeNodes (Node *node, int level)
	Destroys a node and all its sub-nodes recursively. More...
static index_type	getIndex (brie_element_type a, unsigned level)
	Obtains the index within the arrays of cells of a given index on a given level of the internally maintained tree. More...
static index_type	getLevelMask (unsigned level)
	Computes the bit-mask to be applicable to obtain the offset of a node on a given tree level. More...
static std::size_t	getMemoryUsage (const Node *node, int level)
	Computes the memory usage of the given sub-tree. More...
static bool	inBoundaries (index_type a, uint32_t levels, index_type offset)
	Tests whether the given index is within the boundaries defined by the given tree hight and offset. More...
static void	merge (const Node *parent, Node *&trg, const Node *src, int levels)
	A static operation utilized internally for merging sub-trees recursively. More...
static Node *	newNode ()
	Creates new nodes and initializes them with 0. More...

Private Attributes
union {
volatile RootInfo   synced
RootInfo   unsynced
};

Static Private Attributes
static constexpr int	BIT_PER_STEP = BITS
static constexpr key_type	INDEX_MASK = NUM_CELLS - 1
static constexpr int	NUM_CELLS = 1 << BIT_PER_STEP

Friends
template<typename A >
struct	detail::brie::SparseArrayIter

Detailed Description

template<typename T, unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>
class souffle::SparseArray< T, BITS, merge_op, copy_op >

A sparse array simulates an array associating to every element of uint32_t an element of a generic type T.

Any non-defined element will be default-initialized utilizing the detail::brie::default_factory functor.

Internally the array is organized as a balanced tree. The leaf level of the tree corresponds to the elements of the represented array. Inner nodes utilize individual bits of the indices to reference sub-trees. For efficiency reasons, only the minimal sub-tree required to cover all non-null / non-default values stored in the array is maintained. Furthermore, several levels of nodes are aggreated in a B-tree like fashion to inprove cache utilization and reduce the number of steps required for lookup and insert operations.

Template Parameters

T	the type of the stored elements
BITS	the number of bits consumed per node-level e.g. if it is set to 3, the resulting tree will be of a degree of 2^3=8, and thus 8 child-pointers will be stored in each inner node and as many values will be stored in each leaf node.
merge_op	the functor to be utilized when merging the content of two instances of this type.
copy_op	a functor to be applied to each stored value when copying an instance of this array. For instance, this is utilized by the trie implementation to create a clone of each sub-tree instead of preserving the original pointer.

Definition at line 339 of file Brie.h.

Member Typedef Documentation

atomic_value_type

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

using souffle::SparseArray< T, BITS, merge_op, copy_op >::atomic_value_type = std::atomic<value_type>

Definition at line 359 of file Brie.h.

index_type

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

using souffle::SparseArray< T, BITS, merge_op, copy_op >::index_type = key_type

Definition at line 353 of file Brie.h.

iterator

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

using souffle::SparseArray< T, BITS, merge_op, copy_op >::iterator = SparseArrayIter<this_t>

Definition at line 1096 of file Brie.h.

key_type

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

using souffle::SparseArray< T, BITS, merge_op, copy_op >::key_type = uint64_t

private

Definition at line 344 of file Brie.h.

this_t

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

using souffle::SparseArray< T, BITS, merge_op, copy_op >::this_t = SparseArray<T, BITS, merge_op, copy_op>

private

Definition at line 343 of file Brie.h.

value_type

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

using souffle::SparseArray< T, BITS, merge_op, copy_op >::value_type = T

Definition at line 356 of file Brie.h.

Constructor & Destructor Documentation

SparseArray() [1/3]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

souffle::SparseArray< T, BITS, merge_op, copy_op >::SparseArray ( )

inline

A default constructor creating an empty sparse array.

Definition at line 419 of file Brie.h.

: unsynced(RootInfo{other.unsynced.root, other.unsynced.levels, other.unsynced.offset,

SparseArray() [2/3]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

souffle::SparseArray< T, BITS, merge_op, copy_op >::SparseArray ( const SparseArray< T, BITS, merge_op, copy_op > &  other )

inline

A copy constructor for sparse arrays.

It creates a deep copy of the data structure maintained by the handed in array instance.

Definition at line 426 of file Brie.h.

                                                                         {
        other.unsynced.root = nullptr;
        other.unsynced.levels = 0;
        other.unsynced.first = nullptr;
    }
 
    /**
     * A destructor for sparse arrays clearing up the internally

SparseArray() [3/3]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

souffle::SparseArray< T, BITS, merge_op, copy_op >::SparseArray ( SparseArray< T, BITS, merge_op, copy_op > &&  other )

inline

A r-value based copy constructor for sparse arrays.

It takes over ownership of the structure maintained by the handed in array.

Definition at line 440 of file Brie.h.

                                                     {
        if (this == &other) return *this;

~SparseArray()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

souffle::SparseArray< T, BITS, merge_op, copy_op >::~SparseArray ( )

inline

A destructor for sparse arrays clearing up the internally maintained data structure.

Definition at line 452 of file Brie.h.

                           {

Member Function Documentation

addAll()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::addAll ( const SparseArray< T, BITS, merge_op, copy_op > &  other )

inline

Adds all the values stored in the given array to this array.

Definition at line 1042 of file Brie.h.

                                              {
            // get X coordinate
            auto x = getIndex(brie_element_type(other.unsynced.offset), level);
 
            // decrease level counter
            --level;
 
            // check next node
            Node*& next = (*node)->cell[x].ptr;
            if (!next) {
                // create new sub-tree
                next = newNode();
                next->parent = *node;
            }
 
            // continue one level below
            node = &next;
        }
 
        // merge sub-branches from here
        merge((*node)->parent, *node, other.unsynced.root, level);
 
        // update first
        if (unsynced.firstOffset > other.unsynced.firstOffset) {
            unsynced.first = findFirst(*node, level);
            unsynced.firstOffset = other.unsynced.firstOffset;
        }
    }
 
    // ---------------------------------------------------------------------
    //                           Iterator
    // ---------------------------------------------------------------------
 
    using iterator = SparseArrayIter<this_t>;
 
    /**
     * Obtains an iterator referencing the first non-default element or end in
     * case there are no such elements.
     */
    iterator begin() const {
        return iterator(unsynced.first, unsynced.firstOffset);
    }
 
    /**

Referenced by souffle::SparseBitMap< BITS >::size().

begin()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::begin ( ) const

inline

Obtains an iterator referencing the first non-default element or end in case there are no such elements.

Definition at line 1102 of file Brie.h.

                                      {
        op_context ctxt;
        return find(i, ctxt);

Referenced by souffle::SparseBitMap< BITS >::addAll().

clean()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::clean ( )

inlineprivate

Conducts a cleanup of the internal tree structure.

Definition at line 1352 of file Brie.h.

                        {
            copy_op copy;

clear()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::clear ( )

inline

Resets the content of this array to default values for each contained element.

Definition at line 572 of file Brie.h.

       :
    // ---------------------------------------------------------------------
    //              Optimistic Locking of Root-Level Infos
    // ---------------------------------------------------------------------
 

clone()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static Node* souffle::SparseArray< T, BITS, merge_op, copy_op >::clone ( const Node *  node, int  level  )

inlinestaticprivate

Clones the given node and all its sub-nodes.

Definition at line 1361 of file Brie.h.

                                            {
            auto cur = clone(node->cell[i].ptr, level - 1);
            if (cur != nullptr) {
                cur->parent = res;
            }
            res->cell[i].ptr = cur;
        }
 
        // done
        return res;
    }
 
    /**
     * Obtains the left-most leaf-node of the tree rooted by the given node
     * with the given level.
     */
    static Node* findFirst(Node* node, int level) {
        while (level > 0) {
            bool found = false;
            for (int i = 0; i < NUM_CELLS; i++) {
                Node* cur = node->cell[i].ptr;
                if (cur) {
                    node = cur;
                    --level;
                    found = true;
                    break;
                }

dump() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::dump ( bool  detail = false, std::ostream &  out = std::cout  ) const

inline

A debug utility printing the internal structure of this sparse array to the given output stream.

Definition at line 1312 of file Brie.h.

                           {
        return new Node();
    }
 
    /**
     * Destroys a node and all its sub-nodes recursively.
     */

dump() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::dump ( bool  detailed, std::ostream &  out, const Node &  node, int  level, index_type  offset, int  indent = 0  ) const

inlineprivate

An internal debug utility printing the internal structure of this sparse array to the given output stream.

Definition at line 1279 of file Brie.h.

                                      {
                    dump(detailed, out, *node.cell[i].ptr, level - 1,
                            offset + (i * (index_type(1) << (level * BIT_PER_STEP))), indent + 1);
                } else if (detailed) {
                    auto low = offset + (i * (1 << (level * BIT_PER_STEP)));
                    auto hig = low + ~getLevelMask(level);
                    out << times("\t", indent + 1) << i << ": empty range " << low << " - " << hig << "\n";
                }
            }
        }
        out << "\n";
    }
 
public:
    /**
     * A debug utility printing the internal structure of this sparse array to the given output stream.
     */
    void dump(bool detail = false, std::ostream& out = std::cout) const {
        if (!unsynced.root) {
            out << " - empty - \n";
            return;
        }
        out << "root:  " << unsynced.root << "\n";
        out << "offset: " << unsynced.offset << "\n";
        out << "first: " << unsynced.first << "\n";
        out << "fist offset: " << unsynced.firstOffset << "\n";
        dump(detail, out, *unsynced.root, unsynced.levels, unsynced.offset);
    }

empty()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

bool souffle::SparseArray< T, BITS, merge_op, copy_op >::empty ( ) const

inline

Tests whether this sparse array is empty, thus it only contains default-values, or not.

Definition at line 509 of file Brie.h.

       :
    /**

end()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::end ( ) const

inline

An iterator referencing the position after the last non-default element.

Definition at line 1109 of file Brie.h.

                                                        {

find() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::find ( index_type  i ) const

inline

An operation to obtain an iterator referencing an element addressed by the given index.

If the corresponding element is a non-default value, a corresponding iterator will be returned. Otherwise end() will be returned.

Definition at line 1118 of file Brie.h.

                                                                  {

Referenced by souffle::SparseBitMap< BITS >::end().

find() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::find ( index_type  i, op_context &  ctxt  ) const

inline

An operation to obtain an iterator referencing an element addressed by the given index.

If the corresponding element is a non-default value, a corresponding iterator will be returned. Otherwise end() will be returned. A operation context can be provided for exploiting temporal locality.

Definition at line 1129 of file Brie.h.

                           {
            // get X coordinate
            auto x = getIndex(i, level);
 
            // decrease level counter
            --level;
 
            // check next node
            Node* next = node->cell[x].ptr;
 
            // check next step
            if (!next) return end();
 
            // continue one level below
            node = next;
        }
 
        // register in context
        ctxt.lastNode = node;
        ctxt.lastIndex = (i & ~INDEX_MASK);
 
        // check whether there is a proper entry
        value_type value = node->cell[i & INDEX_MASK].value;
        if (value == value_type{}) {
            return end();
        }
 
        // return iterator pointing to cell
        return iterator(node, std::make_pair(i, value));
    }
 
    /**
     * An operation obtaining the smallest non-default element such that it's index is >=
     * the given index.
     */
    iterator lowerBound(index_type i) const {
        op_context ctxt;
        return lowerBound(i, ctxt);
    }
 
    /**
     * An operation obtaining the smallest non-default element such that it's index is >=
     * the given index. A operation context can be provided for exploiting temporal locality.
     */
    iterator lowerBound(index_type i, op_context&) const {
        // check whether it is empty

findFirst()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static Node* souffle::SparseArray< T, BITS, merge_op, copy_op >::findFirst ( Node *  node, int  level  )

inlinestaticprivate

Obtains the left-most leaf-node of the tree rooted by the given node with the given level.

Definition at line 1396 of file Brie.h.

                      {
        // something went wrong when we pass that line
        assert(unsynced.levels < (sizeof(index_type) * 8 / BITS) + 1);
 
        // create new root
        Node* node = newNode();
        node->parent = nullptr;
 
        // insert existing root as child
        auto x = getIndex(brie_element_type(unsynced.offset), unsynced.levels + 1);
        node->cell[x].ptr = unsynced.root;

freeNodes()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static void souffle::SparseArray< T, BITS, merge_op, copy_op >::freeNodes ( Node *  node, int  level  )

inlinestaticprivate

Destroys a node and all its sub-nodes recursively.

Definition at line 1339 of file Brie.h.

                                                    {
        // support null-pointers
        if (node == nullptr) {

get() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

value_type& souffle::SparseArray< T, BITS, merge_op, copy_op >::get ( index_type  i )

inline

Obtains a mutable reference to the value addressed by the given index.

Parameters

i	the index of the element to be addressed

Returns

a mutable reference to the corresponding element

Definition at line 744 of file Brie.h.

                                               {

get() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

value_type& souffle::SparseArray< T, BITS, merge_op, copy_op >::get ( index_type  i, op_context &  ctxt  )

inline

Obtains a mutable reference to the value addressed by the given index.

Parameters

i	the index of the element to be addressed
ctxt	a operation context to exploit state-less temporal locality

Returns

a mutable reference to the corresponding element

Definition at line 756 of file Brie.h.

                                                                 {

getAtomic() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

atomic_value_type& souffle::SparseArray< T, BITS, merge_op, copy_op >::getAtomic ( index_type  i )

inline

Obtains a mutable reference to the atomic value addressed by the given index.

Parameters

i	the index of the element to be addressed

Returns

a mutable reference to the corresponding element

Definition at line 766 of file Brie.h.

       :
    /**
     * An internal function capable of navigating to a given leaf node entry.
     * If the cell does not exist yet it will be created as a side-effect.

Referenced by souffle::SparseBitMap< BITS >::empty().

getAtomic() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

atomic_value_type& souffle::SparseArray< T, BITS, merge_op, copy_op >::getAtomic ( index_type  i, op_context &  ctxt  )

inline

Obtains a mutable reference to the atomic value addressed by the given index.

Parameters

i	the index of the element to be addressed
ctxt	a operation context to exploit state-less temporal locality

Returns

a mutable reference to the corresponding element

Definition at line 778 of file Brie.h.

                                  {

getFirstInfo()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

FirstInfoSnapshot souffle::SparseArray< T, BITS, merge_op, copy_op >::getFirstInfo ( ) const

inlineprivate

Obtains a snapshot of the current first-node information.

Definition at line 694 of file Brie.h.

                                                           {
        // check mod counter
        uintptr_t version = info.version;
 
        // temporary update first pointer to point to uneven value (lock-out)
        if (!__sync_bool_compare_and_swap(&synced.first, (Node*)version, (Node*)(version + 1))) {
            return false;
        }
 
        // conduct update

getFirstVersion()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

uint64_t souffle::SparseArray< T, BITS, merge_op, copy_op >::getFirstVersion ( ) const

inlineprivate

Obtains the current version number of the first node information.

Definition at line 686 of file Brie.h.

                                                           {

getIndex()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static index_type souffle::SparseArray< T, BITS, merge_op, copy_op >::getIndex ( brie_element_type  a, unsigned  level  )

inlinestaticprivate

Obtains the index within the arrays of cells of a given index on a given level of the internally maintained tree.

Definition at line 1498 of file Brie.h.

                       {

getLeaf()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

Cell& souffle::SparseArray< T, BITS, merge_op, copy_op >::getLeaf ( index_type  i, op_context &  ctxt  )

inlineprivate

An internal function capable of navigating to a given leaf node entry.

If the cell does not exist yet it will be created as a side-effect.

Parameters

i	the index of the requested cell
ctxt	a operation context to exploit state-less temporal locality

Returns

a reference to the requested cell

Definition at line 791 of file Brie.h.

                                         {
                // success -- finish get call
 
                // update first
                auto firstInfo = getFirstInfo();
                while (info.offset < firstInfo.offset) {
                    firstInfo.node = info.root;
                    firstInfo.offset = info.offset;
                    if (!tryUpdateFirstInfo(firstInfo)) {
                        // there was some concurrent update => check again
                        firstInfo = getFirstInfo();
                    }
                }
 
                // return reference to proper cell
                return info.root->cell[i & INDEX_MASK];
            }
 
            // somebody else was faster => use standard insertion procedure
            delete info.root;
 
            // retrieve new root info
            info = getRootInfo();
 
            // make sure there is a root
            assert(info.root);
        }
 
        // for all other inserts
        //   - check boundary
        //   - navigate to node
        //   - insert value
 
        // check boundaries
        while (!inBoundaries(i, info.levels, info.offset)) {
            // boundaries need to be expanded by growing upwards
            raiseLevel(info);  // try raising level unless someone else did already
            // update root info
            info = getRootInfo();
        }
 
        // navigate to node
        Node* node = info.root;
        unsigned level = info.levels;
        while (level != 0) {
            // get X coordinate
            auto x = getIndex(brie_element_type(i), level);
 
            // decrease level counter
            --level;
 
            // check next node
            std::atomic<Node*>& aNext = node->cell[x].aptr;
            Node* next = aNext;
            if (!next) {
                // create new sub-tree
                Node* newNext = newNode();
                newNext->parent = node;
 
                // try to update next
                if (!aNext.compare_exchange_strong(next, newNext)) {
                    // some other thread was faster => use updated next
                    delete newNext;
                } else {
                    // the locally created next is the new next
                    next = newNext;
 
                    // update first
                    if (level == 0) {
                        // compute offset of this node
                        auto off = i & ~INDEX_MASK;
 
                        // fast over-approximation of whether a update is necessary
                        if (off < unsynced.firstOffset) {
                            // update first reference if this one is the smallest
                            auto first_info = getFirstInfo();
                            while (off < first_info.offset) {
                                first_info.node = next;
                                first_info.offset = off;
                                if (!tryUpdateFirstInfo(first_info)) {
                                    // there was some concurrent update => check again
                                    first_info = getFirstInfo();
                                }
                            }
                        }
                    }
                }
 
                // now next should be defined
                assert(next);
            }
 
            // continue one level below
            node = next;
        }
 
        // update context
        ctxt.lastIndex = (i & ~INDEX_MASK);
        ctxt.lastNode = node;
 
        // return reference to cell
        return node->cell[i & INDEX_MASK];
    }
 
public:
    /**
     * Updates the value stored in cell i by the given value.
     */
    void update(index_type i, const value_type& val) {
        op_context ctxt;
        update(i, val, ctxt);
    }
 
    /**
     * Updates the value stored in cell i by the given value. A operation
     * context can be provided for exploiting temporal locality.
     */
    void update(index_type i, const value_type& val, op_context& ctxt) {
        get(i, ctxt) = val;

getLevelMask()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static index_type souffle::SparseArray< T, BITS, merge_op, copy_op >::getLevelMask ( unsigned  level )

inlinestaticprivate

Computes the bit-mask to be applicable to obtain the offset of a node on a given tree level.

Definition at line 1506 of file Brie.h.

                    {};

getMemoryUsage() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

std::size_t souffle::SparseArray< T, BITS, merge_op, copy_op >::getMemoryUsage ( ) const

inline

Computes the total memory usage of this data structure.

Definition at line 555 of file Brie.h.

                 {
        clean();
        unsynced.root = nullptr;
        unsynced.levels = 0;
        unsynced.first = nullptr;
        unsynced.firstOffset = std::numeric_limits<index_type>::max();
    }
 
    /**
     * A struct to be utilized as a local, temporal context by client code
     * to speed up the execution of various operations (optional parameter).

getMemoryUsage() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static std::size_t souffle::SparseArray< T, BITS, merge_op, copy_op >::getMemoryUsage ( const Node *  node, int  level  )

inlinestaticprivate

Computes the memory usage of the given sub-tree.

Definition at line 533 of file Brie.h.

      :
    /**
     * Computes the total memory usage of this data structure.
     */
    std::size_t getMemoryUsage() const {
        // the memory of the wrapper class
        std::size_t res = sizeof(*this);
 
        // add nodes
        if (unsynced.root) {
            res += getMemoryUsage(unsynced.root, unsynced.levels);
        }
 
        // done
        return res;

Referenced by souffle::SparseBitMap< BITS >::clear().

getRootInfo()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

RootInfoSnapshot souffle::SparseArray< T, BITS, merge_op, copy_op >::getRootInfo ( ) const

inlineprivate

Obtains a snapshot of the current root information.

Definition at line 620 of file Brie.h.

                                                         {
        // check mod counter
        uintptr_t version = info.version;
 
        // update root to invalid pointer (ending with 1)
        if (!__sync_bool_compare_and_swap(&synced.root, (Node*)version, (Node*)(version + 1))) {

getRootVersion()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

uint64_t souffle::SparseArray< T, BITS, merge_op, copy_op >::getRootVersion ( ) const

inlineprivate

Obtains the current version of the root.

Definition at line 612 of file Brie.h.

                                                         {

inBoundaries() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

bool souffle::SparseArray< T, BITS, merge_op, copy_op >::inBoundaries ( index_type  a ) const

inlineprivate

Tests whether the given index is covered by the boundaries defined by the hight and offset of the internally maintained tree.

Definition at line 1481 of file Brie.h.

                                                                    {
        return (a & (INDEX_MASK << (level * BIT_PER_STEP))) >> (level * BIT_PER_STEP);

inBoundaries() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static bool souffle::SparseArray< T, BITS, merge_op, copy_op >::inBoundaries ( index_type  a, uint32_t  levels, index_type  offset  )

inlinestaticprivate

Tests whether the given index is within the boundaries defined by the given tree hight and offset.

Definition at line 1489 of file Brie.h.

                                                   {
        if (level > (sizeof(index_type) * 8 / BITS)) return 0;
        return (~(index_type(0)) << (level * BIT_PER_STEP));

lookup() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

value_type souffle::SparseArray< T, BITS, merge_op, copy_op >::lookup ( index_type  i ) const

inline

Obtains the value associated to index i – which might be the default value of the covered type if the value hasn't been defined previously.

Definition at line 946 of file Brie.h.

                                                                  {

lookup() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

value_type souffle::SparseArray< T, BITS, merge_op, copy_op >::lookup ( index_type  i, op_context &  ctxt  ) const

inline

Obtains the value associated to index i – which might be the default value of the covered type if the value hasn't been defined previously.

A operation context can be provided for exploiting temporal locality.

Definition at line 957 of file Brie.h.

       :
    /**
     * A static operation utilized internally for merging sub-trees recursively.
     *
     * @param parent the parent node of the current merge operation
     * @param trg a reference to the pointer the cloned node should be stored to
     * @param src the node to be cloned
     * @param levels the height of the cloned node
     */
    static void merge(const Node* parent, Node*& trg, const Node* src, int levels) {
        // if other side is null => done
        if (src == nullptr) {
            return;
        }
 

lowerBound() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::lowerBound ( index_type  i ) const

inline

An operation obtaining the smallest non-default element such that it's index is >= the given index.

Definition at line 1187 of file Brie.h.

                                     {
                const auto& value = unsynced.first->cell[0].value;
                auto res = iterator(unsynced.first, std::make_pair(unsynced.offset, value));
                if (value == value_type()) {

Referenced by souffle::SparseBitMap< BITS >::find().

lowerBound() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::lowerBound ( index_type  i, op_context &    ) const

inline

An operation obtaining the smallest non-default element such that it's index is >= the given index.

A operation context can be provided for exploiting temporal locality.

Definition at line 1196 of file Brie.h.

                     {
            // get X coordinate
            auto x = getIndex(brie_element_type(i), level);
 
            // check next node
            Node* next = node->cell[x].ptr;
 
            // check next step
            if (!next) {
                if (x == NUM_CELLS - 1) {
                    ++level;
                    node = const_cast<Node*>(node->parent);
                    if (!node) return end();
                }
 
                // continue search
                i = i & getLevelMask(level);
 
                // find next higher value
                i += 1ull << (BITS * level);
 
            } else {
                if (level == 0) {
                    // found boundary
                    return iterator(node, std::make_pair(i, node->cell[x].value));
                }
 
                // decrease level counter
                --level;
 
                // continue one level below
                node = next;
            }
        }
    }
 
    /**
     * An operation obtaining the smallest non-default element such that it's index is greater
     * the given index.
     */
    iterator upperBound(index_type i) const {
        op_context ctxt;
        return upperBound(i, ctxt);
    }
 
    /**
     * An operation obtaining the smallest non-default element such that it's index is greater
     * the given index. A operation context can be provided for exploiting temporal locality.
     */
    iterator upperBound(index_type i, op_context& ctxt) const {
        if (i == std::numeric_limits<index_type>::max()) {

merge()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static void souffle::SparseArray< T, BITS, merge_op, copy_op >::merge ( const Node *  parent, Node *&  trg, const Node *  src, int  levels  )

inlinestaticprivate

A static operation utilized internally for merging sub-trees recursively.

Parameters

parent	the parent node of the current merge operation
trg	a reference to the pointer the cloned node should be stored to
src	the node to be cloned
levels	the height of the cloned node

Definition at line 1006 of file Brie.h.

                         {
            merge_op merg;
            for (int i = 0; i < NUM_CELLS; ++i) {
                trg->cell[i].value = merg(trg->cell[i].value, src->cell[i].value);
            }
            return;
        }
 
        // the recursive step
        for (int i = 0; i < NUM_CELLS; ++i) {
            merge(trg, trg->cell[i].ptr, src->cell[i].ptr, levels - 1);
        }
    }
 
public:
    /**
     * Adds all the values stored in the given array to this array.
     */
    void addAll(const SparseArray& other) {
        // skip if other is empty
        if (other.empty()) {
            return;
        }
 
        // special case: emptiness
        if (empty()) {
            // use assignment operator
            *this = other;
            return;

newNode()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

static Node* souffle::SparseArray< T, BITS, merge_op, copy_op >::newNode ( )

inlinestaticprivate

Creates new nodes and initializes them with 0.

Definition at line 1332 of file Brie.h.

                 {

operator=() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

SparseArray& souffle::SparseArray< T, BITS, merge_op, copy_op >::operator= ( const SparseArray< T, BITS, merge_op, copy_op > &  other )

inline

An assignment creating a deep copy of the handed in array structure (utilizing the copy functor provided as a template parameter).

Definition at line 461 of file Brie.h.

                                                {
        // clean this one
        clean();
 
        // harvest content
        unsynced.root = other.unsynced.root;
        unsynced.levels = other.unsynced.levels;
        unsynced.offset = other.unsynced.offset;
        unsynced.first = other.unsynced.first;
        unsynced.firstOffset = other.unsynced.firstOffset;
 

operator=() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

SparseArray& souffle::SparseArray< T, BITS, merge_op, copy_op >::operator= ( SparseArray< T, BITS, merge_op, copy_op > &&  other )

inline

An assignment operation taking over ownership from a r-value reference to a sparse array.

Definition at line 485 of file Brie.h.

                       {
        return unsynced.root == nullptr;
    }
 
    /**
     * Computes the number of non-empty elements within this
     * sparse array.
     */
    std::size_t size() const {
        // quick one for the empty map
        if (empty()) return 0;

operator[]()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

value_type souffle::SparseArray< T, BITS, merge_op, copy_op >::operator[] ( index_type  i ) const

inline

Obtains the value associated to index i – which might be the default value of the covered type if the value hasn't been defined previously.

Definition at line 937 of file Brie.h.

                                                            {

raiseLevel() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::raiseLevel ( )

inlineprivate

Raises the level of this tree by one level.

It does so by introducing a new root node and inserting the current root node as a child node.

Definition at line 1418 of file Brie.h.

                                            {
        // something went wrong when we pass that line
        assert(info.levels < (sizeof(index_type) * 8 / BITS) + 1);
 
        // create new root
        Node* newRoot = newNode();
        newRoot->parent = nullptr;
 
        // insert existing root as child
        auto x = getIndex(brie_element_type(info.offset), info.levels + 1);
        newRoot->cell[x].ptr = info.root;

raiseLevel() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::raiseLevel ( RootInfoSnapshot &  info )

inlineprivate

Attempts to raise the height of this tree based on the given root node information and updates the root-info snapshot correspondingly.

Definition at line 1445 of file Brie.h.

                                     {
            // success => final step, update parent of old root
            oldRoot->parent = info.root;
        } else {
            // throw away temporary new node
            delete newRoot;
        }
    }
 
    /**
     * Tests whether the given index is covered by the boundaries defined
     * by the hight and offset of the internally maintained tree.
     */
    bool inBoundaries(index_type a) const {
        return inBoundaries(a, unsynced.levels, unsynced.offset);
    }
 
    /**
     * Tests whether the given index is within the boundaries defined by the
     * given tree hight and offset.
     */
    static bool inBoundaries(index_type a, uint32_t levels, index_type offset) {
        auto mask = getLevelMask(levels + 1);
        return (a & mask) == offset;

size()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

std::size_t souffle::SparseArray< T, BITS, merge_op, copy_op >::size ( ) const

inline

Computes the number of non-empty elements within this sparse array.

Definition at line 517 of file Brie.h.

                                                                 {
        // support null-nodes
        if (!node) return 0;
 
        // add size of current node
        std::size_t res = sizeof(Node);
 
        // sum up memory usage of child nodes
        if (level > 0) {
            for (int i = 0; i < NUM_CELLS; i++) {
                res += getMemoryUsage(node->cell[i].ptr, level - 1);

tryUpdateFirstInfo()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

bool souffle::SparseArray< T, BITS, merge_op, copy_op >::tryUpdateFirstInfo ( const FirstInfoSnapshot &  info )

inlineprivate

Updates the information stored regarding the first node in a concurrent setting utilizing a optimistic locking approach.

This is identical to the approach utilized for the root info.

Definition at line 717 of file Brie.h.

      :
    /**
     * Obtains a mutable reference to the value addressed by the given index.
     *
     * @param i the index of the element to be addressed
     * @return a mutable reference to the corresponding element
     */
    value_type& get(index_type i) {
        op_context ctxt;
        return get(i, ctxt);
    }
 
    /**
     * Obtains a mutable reference to the value addressed by the given index.
     *

tryUpdateRootInfo()

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

bool souffle::SparseArray< T, BITS, merge_op, copy_op >::tryUpdateRootInfo ( const RootInfoSnapshot &  info )

inlineprivate

Updates the current root information based on the handed in modified snapshot instance if the version number of the snapshot still corresponds to the current version.

Otherwise a concurrent update took place and the operation is aborted.

Parameters

info	the updated information to be assigned to the active root-info data

Returns

true if successfully updated, false if aborted

Definition at line 650 of file Brie.h.

                             {
        // the pointer to the first node
        Node* node;
        // the offset of the first node
        index_type offset;
        // the version number of the first node (for the optimistic locking)
        uintptr_t version;
    };
 
    /**
     * Obtains the current version number of the first node information.
     */

update() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::update ( index_type  i, const value_type &  val  )

inline

Updates the value stored in cell i by the given value.

Definition at line 919 of file Brie.h.

                                              {
        return lookup(i);

update() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

void souffle::SparseArray< T, BITS, merge_op, copy_op >::update ( index_type  i, const value_type &  val, op_context &  ctxt  )

inline

Updates the value stored in cell i by the given value.

A operation context can be provided for exploiting temporal locality.

Definition at line 928 of file Brie.h.

                                          {

upperBound() [1/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::upperBound ( index_type  i ) const

inline

An operation obtaining the smallest non-default element such that it's index is greater the given index.

Definition at line 1258 of file Brie.h.

       :
    /**
     * An internal debug utility printing the internal structure of this sparse array to the given output
     * stream.

upperBound() [2/2]

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

iterator souffle::SparseArray< T, BITS, merge_op, copy_op >::upperBound ( index_type  i, op_context &  ctxt  ) const

inline

An operation obtaining the smallest non-default element such that it's index is greater the given index.

A operation context can be provided for exploiting temporal locality.

Definition at line 1267 of file Brie.h.

                       : " << node.parent << " -- range: " << offset << " - "
            << (offset + ~getLevelMask(level + 1)) << "\n";
 
        if (level == 0) {
            for (int i = 0; i < NUM_CELLS; i++) {
                if (detailed || node.cell[i].value != value_type()) {

Friends And Related Function Documentation

detail::brie::SparseArrayIter

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

template<typename A >

friend struct detail::brie::SparseArrayIter

friend

Definition at line 341 of file Brie.h.

Field Documentation

@1

union { ... }

BIT_PER_STEP

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

constexpr int souffle::SparseArray< T, BITS, merge_op, copy_op >::BIT_PER_STEP = BITS

staticconstexprprivate

Definition at line 347 of file Brie.h.

INDEX_MASK

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

constexpr key_type souffle::SparseArray< T, BITS, merge_op, copy_op >::INDEX_MASK = NUM_CELLS - 1

staticconstexprprivate

Definition at line 349 of file Brie.h.

NUM_CELLS

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

constexpr int souffle::SparseArray< T, BITS, merge_op, copy_op >::NUM_CELLS = 1 << BIT_PER_STEP

staticconstexprprivate

Definition at line 348 of file Brie.h.

synced

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

volatile RootInfo souffle::SparseArray< T, BITS, merge_op, copy_op >::synced

Definition at line 412 of file Brie.h.

unsynced

template<typename T , unsigned BITS = 6, typename merge_op = default_merge<T>, typename copy_op = identity<T>>

RootInfo souffle::SparseArray< T, BITS, merge_op, copy_op >::unsynced

Definition at line 411 of file Brie.h.

---

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

• include/souffle/datastructure/Brie.h