A template specialization for tries representing a set. More...

#include <Brie.h>

Inheritance diagram for souffle::Trie< 1u >:

Collaboration diagram for souffle::Trie< 1u >:

Public Types
using	const_entry_span_type = typename types::const_entry_span_type

using	element_type = entry_type

using	entry_span_type = typename types::entry_span_type

using	entry_type = typename types::entry_type

using	iterator = typename types::iterator

using	iterator_core = typename types::iterator_core

using	op_context = typename types::op_context

using	operation_hints = op_context

Public Types inherited from souffle::detail::brie::TrieBase< 1u, Trie< 1u > >
using	const_entry_span_type = typename types::const_entry_span_type

using	entry_span_type = typename types::entry_span_type

using	entry_type = typename types::entry_type

using	iterator = typename types::iterator

using	iterator_core = typename types::iterator_core

using	op_context = typename types::op_context

Public Member Functions
void	clear ()
	Removes all elements form this trie. More...

bool	contains (const_entry_span_type tuple, op_context &ctxt) const
	Determines whether the given tuple is present in this trie or not. More...

template<unsigned levels>
range< iterator >	getBoundaries (const_entry_span_type entry, op_context &ctxt) const
	Obtains a range of elements matching the prefix of the given entry up to levels elements. More...

std::size_t	getMemoryUsage () const
	Computes the total memory usage of this data structure. More...

bool	insert (const_entry_span_type tuple, op_context &ctxt)
	Inserts the given tuple into this trie. More...

iterator	lower_bound (const_entry_span_type entry, op_context &) const

std::vector< range< iterator > >	partition (unsigned chunks=500) const
	Obtains a partition of this tire such that the resulting list of ranges cover disjoint subsets of the elements stored in this trie. More...

std::size_t	size () const
	Determines the number of entries in this trie. More...

iterator	upper_bound (const_entry_span_type entry, op_context &) const

Public Member Functions inherited from souffle::detail::brie::TrieBase< 1u, Trie< 1u > >
iterator	begin () const
	Obtains an iterator referencing the first element stored within this trie. More...

bool	empty () const
	Determines whether this trie is empty or not. More...

iterator	end () const
	Obtains an iterator referencing the position after the last element stored within this trie. More...

iterator	find (const_entry_span_type entry, op_context &ctxt) const

range< iterator >	getBoundaries (const entry_type &entry) const

range< iterator >	getBoundaries (const entry_type &entry, op_context &ctxt) const

range< iterator >	getBoundaries (const_entry_span_type entry) const

range< iterator >	getBoundaries (Values... values) const

const store_type &	getStore () const
	Provides protected access to the internally maintained store. More...

void	insertAll (const TrieBase &other)
	Inserts all tuples stored within the given trie into this trie. More...

void	printStats (std::ostream &out) const

Private Types
using	base = TrieBase< 1u, Trie< 1u > >

using	store_type = typename types::store_type

using	types = TrieTypes< 1u >

Additional Inherited Members
Protected Types inherited from souffle::detail::brie::TrieBase< 1u, Trie< 1u > >
using	store_type = typename types::store_type

using	types = TrieTypes< Dim >

Protected Attributes inherited from souffle::detail::brie::TrieBase< 1u, Trie< 1u > >
hint_statistics	hint_stats

store_type	store

Detailed Description

A template specialization for tries representing a set.

For improved memory efficiency, this level is the leaf-node level of all tries exhibiting an arity >= 1. Internally, values are stored utilizing sparse bit maps.

Definition at line 2929 of file Brie.h.

Member Typedef Documentation

◆ base

using souffle::Trie< 1u >::base = TrieBase<1u, Trie<1u> >

private

Definition at line 2930 of file Brie.h.

◆ const_entry_span_type

using souffle::Trie< 1u >::const_entry_span_type = typename types::const_entry_span_type

Definition at line 2937 of file Brie.h.

◆ element_type

using souffle::Trie< 1u >::element_type = entry_type

Definition at line 2945 of file Brie.h.

◆ entry_span_type

using souffle::Trie< 1u >::entry_span_type = typename types::entry_span_type

Definition at line 2938 of file Brie.h.

◆ entry_type

using souffle::Trie< 1u >::entry_type = typename types::entry_type

Definition at line 2939 of file Brie.h.

◆ iterator

using souffle::Trie< 1u >::iterator = typename types::iterator

Definition at line 2940 of file Brie.h.

◆ iterator_core

using souffle::Trie< 1u >::iterator_core = typename types::iterator_core

Definition at line 2941 of file Brie.h.

◆ op_context

using souffle::Trie< 1u >::op_context = typename types::op_context

Definition at line 2942 of file Brie.h.

◆ operation_hints

using souffle::Trie< 1u >::operation_hints = op_context

Definition at line 2944 of file Brie.h.

◆ store_type

using souffle::Trie< 1u >::store_type = typename types::store_type

private

Definition at line 2932 of file Brie.h.

◆ types

using souffle::Trie< 1u >::types = TrieTypes<1u>

private

Definition at line 2931 of file Brie.h.

Member Function Documentation

◆ clear()

void souffle::Trie< 1u >::clear ( )

inline

Removes all elements form this trie.

Definition at line 2975 of file Brie.h.

2983 {

◆ contains()

bool souffle::Trie< 1u >::contains	(	const_entry_span_type	tuple,
		op_context &	ctxt
	)		const

inline

Determines whether the given tuple is present in this trie or not.

An operation context can be provided to exploit temporal locality.

Parameters

tuple	the tuple to be tested
ctxt	an operation context for exploiting temporal locality

Returns: true if present, false otherwise

Definition at line 2999 of file Brie.h.

◆ getBoundaries()

template<unsigned levels>

range<iterator> souffle::Trie< 1u >::getBoundaries	(	const_entry_span_type	entry,
		op_context &	ctxt
	)		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 3047 of file Brie.h.

               {
  
 using namespace ::souffle::detail::brie;

◆ getMemoryUsage()

std::size_t souffle::Trie< 1u >::getMemoryUsage ( ) const

inline

Computes the total memory usage of this data structure.

Definition at line 2967 of file Brie.h.

2971 {

◆ insert()

bool souffle::Trie< 1u >::insert	(	const_entry_span_type	tuple,
		op_context &	ctxt
	)

inline

Inserts the given tuple into this trie.

An operation context can be provided to exploit temporal locality.

Parameters

tuple	the tuple to be inserted
ctxt	an operation context for exploiting temporal locality

Returns: true if the tuple has not been present before, false otherwise

Definition at line 2987 of file Brie.h.

◆ lower_bound()

iterator souffle::Trie< 1u >::lower_bound	(	const_entry_span_type	entry,
		op_context &
	)		const

inline

Definition at line 3058 of file Brie.h.

3059 : forward_non_output_iterator_traits<typename SparseArrayIter<A>::value_type> {};

3060

◆ partition()

std::vector<range<iterator> > souffle::Trie< 1u >::partition ( unsigned chunks = 500 ) const

inline

Obtains a partition of this tire such that the resulting list of ranges cover disjoint subsets of the elements stored in this trie.

Their union is equivalent to the content of this trie.

Definition at line 3012 of file Brie.h.

                                                                                        {
         // for levels = 0
         if (levels == 0) return make_range(begin(), end());
         // for levels = 1

◆ size()

std::size_t souffle::Trie< 1u >::size ( ) const

inline

Determines the number of entries in this trie.

Definition at line 2960 of file Brie.h.

2971 {

◆ upper_bound()

iterator souffle::Trie< 1u >::upper_bound	(	const_entry_span_type	entry,
		op_context &
	)		const

inline

Definition at line 3062 of file Brie.h.

3063 : forward_non_output_iterator_traits<typename SparseBitMapIter<A>::value_type> {};

3064

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

include/souffle/datastructure/Brie.h

Public Types

Public Member Functions

Private Types

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ base

◆ const_entry_span_type

◆ element_type

◆ entry_span_type

◆ entry_type

◆ iterator

◆ iterator_core

◆ op_context

◆ operation_hints

◆ store_type

◆ types

Member Function Documentation

◆ clear()

◆ contains()

◆ getBoundaries()

◆ getMemoryUsage()

◆ insert()

◆ lower_bound()

◆ partition()

◆ size()

◆ upper_bound()