An index is an abstraction of a data structure. More...

#include <Index.h>

Collaboration diagram for souffle::interpreter::Index< _Arity, Structure >:

Data Structures
class	View
	A view on a relation caching local access patterns (not thread safe!). More...

Public Types
using	Data = Structure< Arity >

using	Hints = typename Data::operation_hints

using	iterator = typename Data::iterator

using	Tuple = typename souffle::Tuple< RamDomain, Arity >

Public Member Functions
iterator	begin () const

void	clear ()
	Clears the content of this index, turning it empty. More...

bool	contains (const Tuple &low, const Tuple &high) const
	Tests whether this index contains any tuple within the given bounds. More...

bool	contains (const Tuple &tuple) const
	Tests whether the given tuple is present in this index or not. More...

View	createView ()
	Requests the creation of a view on this index. More...

bool	empty () const
	Tests whether this index is empty or not. More...

iterator	end () const

Order	getOrder () const
	Obtains the lex order of this index. More...

	Index (Order order)

void	insert (const Index< Arity, Structure > &src)
	Inserts all elements of the given index. More...

bool	insert (const Tuple &tuple)
	Inserts a tuple into this index. More...

std::vector< souffle::range< iterator > >	partitionRange (const Tuple &low, const Tuple &high, int partitionCount) const
	Returns a partitioned list of iterators coving elements in range [low, high]. More...

std::vector< souffle::range< iterator > >	partitionScan (int partitionCount) const
	Retruns a partitioned list of iterators for parallel computation. More...

souffle::range< iterator >	range (const Tuple &low, const Tuple &high) const
	Returns a pair of iterators covering elements in the range [low,high) More...

souffle::range< iterator >	scan () const
	Returns a pair of iterators covering the entire index content. More...

size_t	size () const
	Obtains the number of elements stored in this index. More...

Static Public Attributes
static constexpr size_t	Arity = _Arity

Protected Attributes
Data	data

Order	order

Detailed Description

template<size_t _Arity, template< size_t > typename Structure>
class souffle::interpreter::Index< _Arity, Structure >

An index is an abstraction of a data structure.

Definition at line 152 of file Index.h.

Member Typedef Documentation

◆ Data

template<size_t _Arity, template< size_t > typename Structure>

using souffle::interpreter::Index< _Arity, Structure >::Data = Structure<Arity>

Definition at line 155 of file Index.h.

◆ Hints

template<size_t _Arity, template< size_t > typename Structure>

using souffle::interpreter::Index< _Arity, Structure >::Hints = typename Data::operation_hints

Definition at line 158 of file Index.h.

◆ iterator

template<size_t _Arity, template< size_t > typename Structure>

using souffle::interpreter::Index< _Arity, Structure >::iterator = typename Data::iterator

Definition at line 157 of file Index.h.

◆ Tuple

template<size_t _Arity, template< size_t > typename Structure>

using souffle::interpreter::Index< _Arity, Structure >::Tuple = typename souffle::Tuple<RamDomain, Arity>

Definition at line 156 of file Index.h.

Constructor & Destructor Documentation

◆ Index()

template<size_t _Arity, template< size_t > typename Structure>

souffle::interpreter::Index< _Arity, Structure >::Index ( Order order )

inline

Definition at line 160 of file Index.h.

160 :

161 /**

Member Function Documentation

◆ begin()

template<size_t _Arity, template< size_t > typename Structure>

iterator souffle::interpreter::Index< _Arity, Structure >::begin ( ) const

inline

Definition at line 203 of file Index.h.

208 {

◆ clear()

template<size_t _Arity, template< size_t > typename Structure>

void souffle::interpreter::Index< _Arity, Structure >::clear ( )

inline

Clears the content of this index, turning it empty.

Definition at line 307 of file Index.h.

311 {

◆ contains() [1/2]

template<size_t _Arity, template< size_t > typename Structure>

bool souffle::interpreter::Index< _Arity, Structure >::contains	(	const Tuple &	low,
		const Tuple &	high
	)		const

inline

Tests whether this index contains any tuple within the given bounds.

Definition at line 258 of file Index.h.

259 {

260 return {data.begin(), data.end()};

◆ contains() [2/2]

template<size_t _Arity, template< size_t > typename Structure>

bool souffle::interpreter::Index< _Arity, Structure >::contains ( const Tuple & tuple ) const

inline

Tests whether the given tuple is present in this index or not.

Definition at line 251 of file Index.h.

252 {

253 return !range(low, high).empty();

Referenced by souffle::interpreter::Relation< 2, Eqrel >::__purge(), and souffle::interpreter::Relation< 2, Eqrel >::insert().

◆ createView()

template<size_t _Arity, template< size_t > typename Structure>

View souffle::interpreter::Index< _Arity, Structure >::createView ( )

inline

Requests the creation of a view on this index.

Definition at line 199 of file Index.h.

201 {

◆ empty()

template<size_t _Arity, template< size_t > typename Structure>

bool souffle::interpreter::Index< _Arity, Structure >::empty ( ) const

inline

Tests whether this index is empty or not.

Definition at line 221 of file Index.h.

222 {

223 return data.size();

Referenced by souffle::interpreter::Relation< 2, Eqrel >::__size().

◆ end()

template<size_t _Arity, template< size_t > typename Structure>

iterator souffle::interpreter::Index< _Arity, Structure >::end ( ) const

inline

Definition at line 207 of file Index.h.

208 {

209 return order;

◆ getOrder()

template<size_t _Arity, template< size_t > typename Structure>

Order souffle::interpreter::Index< _Arity, Structure >::getOrder ( ) const

inline

Obtains the lex order of this index.

Definition at line 214 of file Index.h.

215 {

216 return data.empty();

◆ insert() [1/2]

template<size_t _Arity, template< size_t > typename Structure>

void souffle::interpreter::Index< _Arity, Structure >::insert ( const Index< Arity, Structure > & src )

inline

Inserts all elements of the given index.

Definition at line 242 of file Index.h.

245 {

246 return data.contains(tuple);

◆ insert() [2/2]

template<size_t _Arity, template< size_t > typename Structure>

bool souffle::interpreter::Index< _Arity, Structure >::insert ( const Tuple & tuple )

inline

Inserts a tuple into this index.

Definition at line 235 of file Index.h.

236 {

237 for (const auto& tuple : src) {

Referenced by souffle::interpreter::Relation< 2, Eqrel >::end(), and souffle::interpreter::Index< 2, Eqrel >::insert().

◆ partitionRange()

template<size_t _Arity, template< size_t > typename Structure>

std::vector<souffle::range<iterator> > souffle::interpreter::Index< _Arity, Structure >::partitionRange	(	const Tuple &	low,
		const Tuple &	high,
		int	partitionCount
	)		const

inline

Returns a partitioned list of iterators coving elements in range [low, high].

Definition at line 292 of file Index.h.

                              : chunks) {
             res.push_back({cur.begin(), cur.end()});
         }
         return res;
     }
  
     /**
      * Clears the content of this index, turning it empty.
      */
     void clear() {
         data.clear();

◆ partitionScan()

template<size_t _Arity, template< size_t > typename Structure>

std::vector<souffle::range<iterator> > souffle::interpreter::Index< _Arity, Structure >::partitionScan ( int partitionCount ) const

inline

Retruns a partitioned list of iterators for parallel computation.

Definition at line 279 of file Index.h.

287 {

Referenced by souffle::interpreter::Index< 0, Structure >::partitionScan(), and souffle::interpreter::Relation< 2, Eqrel >::scan().

◆ range()

template<size_t _Arity, template< size_t > typename Structure>

souffle::range<iterator> souffle::interpreter::Index< _Arity, Structure >::range	(	const Tuple &	low,
		const Tuple &	high
	)		const

inline

Returns a pair of iterators covering elements in the range [low,high)

Definition at line 272 of file Index.h.

273 {

274 auto chunks = data.partition(partitionCount);

Referenced by souffle::interpreter::Index< 2, Eqrel >::contains().

◆ scan()

template<size_t _Arity, template< size_t > typename Structure>

souffle::range<iterator> souffle::interpreter::Index< _Arity, Structure >::scan ( ) const

inline

Returns a pair of iterators covering the entire index content.

Definition at line 265 of file Index.h.

266 {

267 return {data.lower_bound(low), data.upper_bound(high)};

Referenced by souffle::interpreter::Relation< 2, Eqrel >::contains().

◆ size()

template<size_t _Arity, template< size_t > typename Structure>

size_t souffle::interpreter::Index< _Arity, Structure >::size ( ) const

inline

Obtains the number of elements stored in this index.

Definition at line 228 of file Index.h.

229 {

230 return data.insert(order.encode(tuple));

Referenced by souffle::interpreter::Relation< 2, Eqrel >::swap().

Field Documentation

◆ Arity

template<size_t _Arity, template< size_t > typename Structure>

constexpr size_t souffle::interpreter::Index< _Arity, Structure >::Arity = _Arity

staticconstexpr

Definition at line 154 of file Index.h.

Referenced by souffle::interpreter::Index< 2, Eqrel >::clear().

◆ data

template<size_t _Arity, template< size_t > typename Structure>

Data souffle::interpreter::Index< _Arity, Structure >::data

protected

Definition at line 164 of file Index.h.

Referenced by souffle::interpreter::Index< 2, Eqrel >::contains(), souffle::interpreter::Index< 2, Eqrel >::empty(), souffle::interpreter::Index< 2, Eqrel >::getOrder(), souffle::interpreter::Index< 2, Eqrel >::insert(), souffle::interpreter::Index< 2, Eqrel >::range(), souffle::interpreter::Index< 2, Eqrel >::scan(), and souffle::interpreter::Index< 2, Eqrel >::size().

◆ order

template<size_t _Arity, template< size_t > typename Structure>

Order souffle::interpreter::Index< _Arity, Structure >::order

protected

Definition at line 163 of file Index.h.

Referenced by souffle::interpreter::Index< 2, Eqrel >::end(), and souffle::interpreter::Index< 2, Eqrel >::size().

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

interpreter/Index.h

Data Structures

Public Types

Public Member Functions

Static Public Attributes

Protected Attributes

Detailed Description

template<size_t _Arity, template< size_t > typename Structure> class souffle::interpreter::Index< _Arity, Structure >

Member Typedef Documentation

◆ Data

◆ Hints

◆ iterator

◆ Tuple

Constructor & Destructor Documentation

◆ Index()

Member Function Documentation

◆ begin()

◆ clear()

◆ contains() [1/2]

◆ contains() [2/2]

◆ createView()

◆ empty()

◆ end()

◆ getOrder()

◆ insert() [1/2]

◆ insert() [2/2]

◆ partitionRange()

◆ partitionScan()

◆ range()

◆ scan()

◆ size()

Field Documentation

◆ Arity

◆ data

◆ order

template<size_t _Arity, template< size_t > typename Structure>
class souffle::interpreter::Index< _Arity, Structure >