souffle::EquivalenceRelation< TupleType > Class Template Reference

#include <EquivalenceRelation.h>

Collaboration diagram for souffle::EquivalenceRelation< TupleType >:

Data Structures
class	iterator
struct	operation_hints
	A collection of operation hints speeding up some of the involved operations by exploiting temporal locality. More...

Public Types
using	element_type = TupleType

Public Member Functions
iterator	anteriorIt (value_type anteriorVal) const
	Creates an iterator that generates all pairs (A, X) for a given A, and X are elements within A's disjoint set. More...
iterator	antpostit (value_type anteriorVal, value_type posteriorVal) const
	Creates an iterator that generates the pair (A, B) for a given A and B. More...
iterator	begin () const
	iterator pointing to the beginning of the tuples, with no restrictions More...
void	clear ()
	Empty the relation. More...
iterator	closure (value_type rep) const
	Begin an iterator over all pairs within a single disjoint set - This is used for partition(). More...
bool	contains (const TupleType &tuple) const
bool	contains (const TupleType &tuple, operation_hints &) const
	Returns whether there exists given tuple. More...
bool	contains (value_type x, value_type y) const
	Returns whether there exists a pair with these two nodes. More...
bool	empty () const
	Check emptiness. More...
void	emptyPartition () const
iterator	end () const
	iterator pointing to the end of the tuples More...
	EquivalenceRelation ()
void	extend (const EquivalenceRelation< TupleType > &other)
	Extend this relation with another relation, expanding this equivalence relation The supplied relation is the old knowledge, whilst this relation only contains explicitly new knowledge. More...
iterator	find (const TupleType &, operation_hints &) const
iterator	find (const TupleType &t) const
template<unsigned levels>
range< iterator >	getBoundaries (const TupleType &entry) const
	Obtains a range of elements matching the prefix of the given entry up to levels elements. More...
template<unsigned levels>
range< iterator >	getBoundaries (const TupleType &entry, operation_hints &) const
	Obtains a range of elements matching the prefix of the given entry up to levels elements. More...
bool	insert (const TupleType &tuple)
	Insert the tuple symbolically. More...
bool	insert (value_type x, value_type y)
	Insert the two values symbolically as a binary relation. More...
bool	insert (value_type x, value_type y, operation_hints)
	Insert the two values symbolically as a binary relation. More...
void	insertAll (const EquivalenceRelation< TupleType > &other)
	inserts all nodes from the other relation into this one More...
iterator	lower_bound (const TupleType &entry) const
iterator	lower_bound (const TupleType &entry, operation_hints &) const
	Act similar to getBoundaries. More...
std::vector< souffle::range< iterator > >	partition (size_t chunks) const
	Generate an approximate number of iterators for parallel iteration The iterators returned are not necessarily equal in size, but in practise are approximately similarly sized Depending on the structure of the data, there can be more or less partitions returned than requested. More...
size_t	size () const
	Size of relation. More...
iterator	upper_bound (const TupleType &, operation_hints &) const
	This function is only here in order to unify interfaces in InterpreterIndex. More...
iterator	upper_bound (const TupleType &entry) const
	~EquivalenceRelation ()

Protected Member Functions
bool	containsElement (value_type e) const

Private Types
using	StatesBucket = StatesList *
using	StatesList = souffle::PiggyList< value_type >
using	StatesMap = souffle::LambdaBTreeSet< StorePair, std::function< StatesBucket(StorePair &)>, souffle::EqrelMapComparator< StorePair > >
using	StorePair = std::pair< value_type, StatesBucket >
using	value_type = typename TupleType::value_type

Private Member Functions
void	genAllDisjointSetLists () const
	Generate a cache of the sets such that they can be iterated over efficiently. More...

Private Attributes
StatesMap	equivalencePartition
souffle::SparseDisjointSet< value_type >	sds
std::shared_mutex	statesLock
std::atomic< bool >	statesMapStale

Detailed Description

template<typename TupleType>
class souffle::EquivalenceRelation< TupleType >

Definition at line 50 of file EquivalenceRelation.h.

Member Typedef Documentation

element_type

template<typename TupleType >

using souffle::EquivalenceRelation< TupleType >::element_type = TupleType

Definition at line 70 of file EquivalenceRelation.h.

StatesBucket

template<typename TupleType >

using souffle::EquivalenceRelation< TupleType >::StatesBucket = StatesList*

private

Definition at line 64 of file EquivalenceRelation.h.

StatesList

template<typename TupleType >

using souffle::EquivalenceRelation< TupleType >::StatesList = souffle::PiggyList<value_type>

private

Definition at line 63 of file EquivalenceRelation.h.

StatesMap

template<typename TupleType >

using souffle::EquivalenceRelation< TupleType >::StatesMap = souffle::LambdaBTreeSet<StorePair, std::function<StatesBucket(StorePair&)>, souffle::EqrelMapComparator<StorePair> >

private

Definition at line 67 of file EquivalenceRelation.h.

StorePair

template<typename TupleType >

using souffle::EquivalenceRelation< TupleType >::StorePair = std::pair<value_type, StatesBucket>

private

Definition at line 65 of file EquivalenceRelation.h.

value_type

template<typename TupleType >

using souffle::EquivalenceRelation< TupleType >::value_type = typename TupleType::value_type

private

Definition at line 59 of file EquivalenceRelation.h.

Constructor & Destructor Documentation

EquivalenceRelation()

template<typename TupleType >

souffle::EquivalenceRelation< TupleType >::EquivalenceRelation ( )

inline

Definition at line 72 of file EquivalenceRelation.h.

{

~EquivalenceRelation()

template<typename TupleType >

souffle::EquivalenceRelation< TupleType >::~EquivalenceRelation ( )

inline

Definition at line 73 of file EquivalenceRelation.h.

                                            {

Member Function Documentation

anteriorIt()

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::anteriorIt ( value_type  anteriorVal ) const

inline

Creates an iterator that generates all pairs (A, X) for a given A, and X are elements within A's disjoint set.

Parameters

anteriorVal

The first value of the tuple to be generated for

Returns

the iterator representing this.

Definition at line 619 of file EquivalenceRelation.h.

                          : the B value of the tuple
     * @return the iterator representing this
     */
    iterator antpostit(value_type anteriorVal, value_type posteriorVal) const {
        // obv if they're in diff sets, then iteration for this pair just ends.
        if (!sds.sameSet(anteriorVal, posteriorVal)) return end();
 
        genAllDisjointSetLists();
 
        // locate the blocklist that the val resides in

Referenced by souffle::EquivalenceRelation< Arity >::getBoundaries(), and souffle::EquivalenceRelation< Arity >::partition().

antpostit()

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::antpostit ( value_type  anteriorVal, value_type  posteriorVal  ) const

inline

Creates an iterator that generates the pair (A, B) for a given A and B.

If A and B don't exist, or aren't in the same set, then the end() iterator is returned.

Parameters

anteriorVal	the A value of the tuple
posteriorVal	the B value of the tuple

Returns

the iterator representing this

Definition at line 638 of file EquivalenceRelation.h.

                                           {
        genAllDisjointSetLists();
 
        // locate the blocklist that the val resides in
        auto found = equivalencePartition.find({sds.findNode(rep), nullptr});
        return iterator(this, (*found).second);
    }
 
    /**
     * Generate an approximate number of iterators for parallel iteration

begin()

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::begin ( ) const

inline

iterator pointing to the beginning of the tuples, with no restrictions

Returns

the iterator that corresponds to the beginning of the binary relation

Definition at line 480 of file EquivalenceRelation.h.

                                                                {

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

clear()

template<typename TupleType >

void souffle::EquivalenceRelation< TupleType >::clear ( )

inline

Empty the relation.

Definition at line 229 of file EquivalenceRelation.h.

                     : this->equivalencePartition) {
            const size_t s = e.second->size();
            retVal += s * s;
        }
 

closure()

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::closure ( value_type  rep ) const

inline

Begin an iterator over all pairs within a single disjoint set - This is used for partition().

Parameters

rep	the representative of (or element within) a disjoint set of which to generate all pairs

Returns

an iterator that will generate all pairs within the disjoint set

Definition at line 656 of file EquivalenceRelation.h.

                                                                     {
        // generate all reps
        genAllDisjointSetLists();
 
        size_t numPairs = this->size();
        if (numPairs == 0) return {};
        if (numPairs == 1 || chunks <= 1) return {souffle::make_range(begin(), end())};

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

contains() [1/3]

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::contains ( const TupleType &  tuple ) const

inline

Definition at line 211 of file EquivalenceRelation.h.

                 {

contains() [2/3]

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::contains ( const TupleType &  tuple, operation_hints &    ) const

inline

Returns whether there exists given tuple.

Parameters

tuple

The tuple to search for.

Definition at line 207 of file EquivalenceRelation.h.

                 {

contains() [3/3]

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::contains ( value_type  x, value_type  y  ) const

inline

Returns whether there exists a pair with these two nodes.

Parameters

x	front of pair
y	back of pair

Definition at line 199 of file EquivalenceRelation.h.

                                {
        // delete the beautiful values inside (they're raw ptrs, so they need to be.)
        for (auto& pair : equivalencePartition) {

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

containsElement()

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::containsElement ( value_type  e ) const

inlineprotected

Definition at line 718 of file EquivalenceRelation.h.

                                        {

empty()

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::empty ( ) const

inline

Check emptiness.

Definition at line 609 of file EquivalenceRelation.h.

                                                                              {

emptyPartition()

template<typename TupleType >

void souffle::EquivalenceRelation< TupleType >::emptyPartition ( ) const

inline

Definition at line 215 of file EquivalenceRelation.h.

                        {

end()

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::end ( ) const

inline

iterator pointing to the end of the tuples

Returns

the iterator which represents the end of the binary rel

Definition at line 489 of file EquivalenceRelation.h.

                                                                                  {

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::EquivalenceRelation< Arity >::closure(), souffle::EquivalenceRelation< Arity >::getBoundaries(), souffle::EquivalenceRelation< Arity >::lower_bound(), and souffle::EquivalenceRelation< Arity >::partition().

extend()

template<typename TupleType >

void souffle::EquivalenceRelation< TupleType >::extend ( const EquivalenceRelation< TupleType > &  other )

inline

Extend this relation with another relation, expanding this equivalence relation The supplied relation is the old knowledge, whilst this relation only contains explicitly new knowledge.

After this operation the "implicitly new tuples" are now explicitly inserted this relation.

Definition at line 152 of file EquivalenceRelation.h.

                                               {
                    value_type rep = other.sds.findNode(el);
                    if (repsCovered.count(rep) == 0) {
                        repsCovered.emplace(rep);
                    }
                }
            }
        }
 
        // add the intersecting dj sets into this one
        {
            value_type el;
            value_type rep;
            auto it = other.sds.sparseToDenseMap.begin();
            auto end = other.sds.sparseToDenseMap.end();
            for (; it != end; ++it) {
                std::tie(el, std::ignore) = *it;
                rep = other.sds.findNode(el);
                if (repsCovered.count(rep) != 0) {
                    this->insert(el, rep);
                }
            }
        }
    }
 
    /**
     * Returns whether there exists a pair with these two nodes
     * @param x front of pair
     * @param y back of pair
     */
    bool contains(value_type x, value_type y) const {
        return sds.contains(x, y);
    }
 
    /**
     * Returns whether there exists given tuple.
     * @param tuple The tuple to search for.
     */
    bool contains(const TupleType& tuple, operation_hints&) const {
        return contains(tuple[0], tuple[1]);

find() [1/2]

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::find ( const TupleType &  , operation_hints &    ) const

inline

Definition at line 707 of file EquivalenceRelation.h.

find() [2/2]

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::find ( const TupleType &  t ) const

inline

Definition at line 712 of file EquivalenceRelation.h.

genAllDisjointSetLists()

template<typename TupleType >

void souffle::EquivalenceRelation< TupleType >::genAllDisjointSetLists ( ) const

inlineprivate

Generate a cache of the sets such that they can be iterated over efficiently.

Each set is partitioned into a PiggyList.

Definition at line 738 of file EquivalenceRelation.h.

                          {static_cast<value_type>(rep), nullptr};
            StatesList* mapList = equivalencePartition.insert(p, [&](StorePair& sp) {
                auto* r = new StatesList(1);
                sp.second = r;
                return r;
            });
            mapList->append(sparseVal);
        }
 
        statesMapStale.store(false, std::memory_order_release);
        statesLock.unlock();
    }
};
}  // namespace souffle

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::EquivalenceRelation< Arity >::antpostit(), souffle::EquivalenceRelation< Arity >::closure(), and souffle::EquivalenceRelation< Arity >::upper_bound().

getBoundaries() [1/2]

template<typename TupleType >

template<unsigned levels>

range<iterator> souffle::EquivalenceRelation< TupleType >::getBoundaries ( const TupleType &  entry ) const

inline

Obtains a range of elements matching the prefix of the given entry up to levels elements.

Template Parameters

levels

the length of the requested matching prefix

Parameters

entry

the entry to be looking for

Returns

the corresponding range of matching elements

Definition at line 502 of file EquivalenceRelation.h.

                                                                                  {
        // if nothing is bound => just use begin and end
        if (levels == 0) return make_range(begin(), end());
 

getBoundaries() [2/2]

template<typename TupleType >

template<unsigned levels>

range<iterator> souffle::EquivalenceRelation< TupleType >::getBoundaries ( const TupleType &  entry, operation_hints &    ) const

inline

Obtains a range of elements matching the prefix of the given entry up to levels elements.

A operation context may be provided to exploit temporal locality.

Template Parameters

levels

the length of the requested matching prefix

Parameters

entry	the entry to be looking for
ctxt	the operation context to be utilized

Returns

the corresponding range of matching elements

Definition at line 518 of file EquivalenceRelation.h.

                                                                         {
        if (entry[0] == MIN_RAM_SIGNED && entry[1] == MIN_RAM_SIGNED) {
            // Return an iterator over all tuples.
            return begin();
        }
 

insert() [1/3]

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::insert ( const TupleType &  tuple )

inline

Insert the tuple symbolically.

Parameters

tuple

The tuple to be inserted

Returns

true if the tuple is new to the data structure

Definition at line 104 of file EquivalenceRelation.h.

                                                                {

insert() [2/3]

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::insert ( value_type  x, value_type  y  )

inline

Insert the two values symbolically as a binary relation.

Parameters

x	node to be added/paired
y	node to be added/paired

Returns

true if the pair is new to the data structure

Definition at line 94 of file EquivalenceRelation.h.

                                                             {

Referenced by souffle::EquivalenceRelation< TupleType >::operation_hints::clear(), souffle::test::TEST(), and souffle::EquivalenceRelation< Arity >::~EquivalenceRelation().

insert() [3/3]

template<typename TupleType >

bool souffle::EquivalenceRelation< TupleType >::insert ( value_type  x, value_type  y, operation_hints    )

inline

Insert the two values symbolically as a binary relation.

Parameters

x	node to be added/paired
y	node to be added/paired
z	the hints to where the pair should be inserted (not applicable atm)

Returns

true if the pair is new to the data structure

Definition at line 116 of file EquivalenceRelation.h.

                                        : other.equivalencePartition.getChunks(MAX_THREADS)) {
            for (auto& p : it) {
                value_type rep = p.first;
                StatesList& pl = *p.second;
                const size_t ksize = pl.size();
                for (size_t i = 0; i < ksize; ++i) {
                    this->sds.unionNodes(rep, pl.get(i));

insertAll()

template<typename TupleType >

void souffle::EquivalenceRelation< TupleType >::insertAll ( const EquivalenceRelation< TupleType > &  other )

inline

inserts all nodes from the other relation into this one

Parameters

other

the binary relation from which to add elements from

Definition at line 128 of file EquivalenceRelation.h.

                                                             {
        // nothing to extend if there's no new/original knowledge
        if (other.size() == 0 || this->size() == 0) return;
 
        this->genAllDisjointSetLists();
        other.genAllDisjointSetLists();
 
        std::set<value_type> repsCovered;
 

lower_bound() [1/2]

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::lower_bound ( const TupleType &  entry ) const

inline

Definition at line 584 of file EquivalenceRelation.h.

                                                       {
        operation_hints hints;
        return upper_bound(entry, hints);

lower_bound() [2/2]

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::lower_bound ( const TupleType &  entry, operation_hints &    ) const

inline

Act similar to getBoundaries.

But non-static. This function should be used ONLY by interpreter, and its behavior is tightly coupling with InterpreterIndex. Do Not rely on this interface outside the interpreter.

Parameters

entry

the entry to be looking for

Returns

the corresponding range of matching elements

Definition at line 557 of file EquivalenceRelation.h.

                                                   {
                return end();
            }
            return antpostit(entry[0], entry[1]);
        }
 
        return end();
    }
 
    iterator lower_bound(const TupleType& entry) const {
        operation_hints hints;
        return lower_bound(entry, hints);
    }
 
    /**
     * This function is only here in order to unify interfaces in InterpreterIndex.
     * Unlike the name suggestes, it omit the arguments and simply return the end
     * iterator of the relation.
     *
     * @param omitted
     * @return the end iterator.
     */
    iterator upper_bound(const TupleType&, operation_hints&) const {
        return end();

partition()

template<typename TupleType >

std::vector<souffle::range<iterator> > souffle::EquivalenceRelation< TupleType >::partition ( size_t  chunks ) const

inline

Generate an approximate number of iterators for parallel iteration The iterators returned are not necessarily equal in size, but in practise are approximately similarly sized Depending on the structure of the data, there can be more or less partitions returned than requested.

Parameters

chunks

the number of requested partitions

Returns

a list of the iterators as ranges

Definition at line 672 of file EquivalenceRelation.h.

                             : equivalencePartition) {
            const size_t s = itp.second->size();
            if (s * s > perchunk) {
                for (const auto& i : *itp.second) {
                    ret.push_back(souffle::make_range(anteriorIt(i), end()));
                }
            } else {
                ret.push_back(souffle::make_range(closure(itp.first), end()));
            }
        }
 
        return ret;
    }
 
    iterator find(const TupleType&, operation_hints&) const {
        throw std::runtime_error("error: find() is not compatible with equivalence relations");
        return begin();
    }
 
    iterator find(const TupleType& t) const {
        operation_hints context;
        return find(t, context);
    }
 
protected:
    bool containsElement(value_type e) const {
        return this->sds.nodeExists(e);
    }
 

size()

template<typename TupleType >

size_t souffle::EquivalenceRelation< TupleType >::size ( ) const

inline

Size of relation.

Returns

the sum of the number of pairs per disjoint set

Definition at line 242 of file EquivalenceRelation.h.

                   {
    public:
        typedef std::forward_iterator_tag iterator_category;
        using value_type = TupleType;
        using difference_type = ptrdiff_t;
        using pointer = value_type*;
        using reference = value_type&;
 
        // one iterator for signalling the end (simplifies)
        explicit iterator(const EquivalenceRelation* br, bool /* signalIsEndIterator */)
                : br(br), isEndVal(true){};

Referenced by souffle::EquivalenceRelation< Arity >::closure(), and souffle::test::TEST().

upper_bound() [1/2]

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::upper_bound ( const TupleType &  , operation_hints &    ) const

inline

This function is only here in order to unify interfaces in InterpreterIndex.

Unlike the name suggestes, it omit the arguments and simply return the end iterator of the relation.

Parameters

omitted

Returns

the end iterator.

Definition at line 597 of file EquivalenceRelation.h.

                                                      {

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

upper_bound() [2/2]

template<typename TupleType >

iterator souffle::EquivalenceRelation< TupleType >::upper_bound ( const TupleType &  entry ) const

inline

Definition at line 601 of file EquivalenceRelation.h.

                                                      {
        genAllDisjointSetLists();

Field Documentation

equivalencePartition

template<typename TupleType >

StatesMap souffle::EquivalenceRelation< TupleType >::equivalencePartition

mutableprivate

Definition at line 730 of file EquivalenceRelation.h.

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::EquivalenceRelation< Arity >::antpostit(), souffle::EquivalenceRelation< Arity >::closure(), souffle::EquivalenceRelation< Arity >::contains(), souffle::EquivalenceRelation< Arity >::size(), and souffle::EquivalenceRelation< Arity >::upper_bound().

sds

template<typename TupleType >

souffle::SparseDisjointSet<value_type> souffle::EquivalenceRelation< TupleType >::sds

mutableprivate

Definition at line 725 of file EquivalenceRelation.h.

Referenced by souffle::EquivalenceRelation< Arity >::anteriorIt(), souffle::EquivalenceRelation< Arity >::antpostit(), souffle::EquivalenceRelation< Arity >::getBoundaries(), souffle::EquivalenceRelation< Arity >::insert(), and souffle::EquivalenceRelation< Arity >::upper_bound().

statesLock

template<typename TupleType >

std::shared_mutex souffle::EquivalenceRelation< TupleType >::statesLock

mutableprivate

Definition at line 728 of file EquivalenceRelation.h.

Referenced by souffle::EquivalenceRelation< Arity >::contains(), and souffle::EquivalenceRelation< Arity >::containsElement().

statesMapStale

template<typename TupleType >

std::atomic<bool> souffle::EquivalenceRelation< TupleType >::statesMapStale

mutableprivate

Definition at line 732 of file EquivalenceRelation.h.

Referenced by souffle::EquivalenceRelation< Arity >::contains(), and souffle::EquivalenceRelation< Arity >::insert().

---

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

• include/souffle/datastructure/EquivalenceRelation.h