#include <Brie.h>

Collaboration diagram for souffle::Trie< Dim >:

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 Member Functions
iterator	begin () const
	Obtains an iterator referencing the first element stored within this trie. More...

void	clear ()
	Removes all entries within this trie. More...

bool	contains (const_entry_span_type tuple, op_context &ctxt) const

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

template<unsigned levels>
range< iterator >	getBoundaries (const entry_type &entry) const

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

template<unsigned levels>
range< iterator >	getBoundaries (const_entry_span_type entry) const

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

template<unsigned levels, typename... Values, typename = std::enable_if_t<(isRamType<Values> && ...)>>
range< iterator >	getBoundaries (Values... values) const

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 a new entry. More...

iterator	lower_bound (const_entry_span_type entry, op_context &) const
	Obtains an iterator to the first element not less than the given entry value. More...

std::vector< range< iterator > >	partition (unsigned chunks=500) const
	Computes a partition of an approximate number of chunks of the content of 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
	Obtains an iterator to the first element greater than the given entry value, or end if there is no such element. More...

	~Trie ()

Private Types
using	base = TrieBase< Dim, Trie< Dim > >

using	nested_trie_type = typename types::nested_trie_type

using	store_type = typename types::store_type

using	types = TrieTypes< Dim >

Private Attributes
store_type	store

Friends
template<unsigned N>
class	Trie

Detailed Description

template<unsigned Dim>
class souffle::Trie< Dim >

Definition at line 79 of file Brie.h.

Member Typedef Documentation

◆ base

template<unsigned Dim>

using souffle::Trie< Dim >::base = TrieBase<Dim, Trie<Dim> >

private

Definition at line 2659 of file Brie.h.

◆ const_entry_span_type

template<unsigned Dim>

using souffle::Trie< Dim >::const_entry_span_type = typename types::const_entry_span_type

Definition at line 2667 of file Brie.h.

◆ element_type

template<unsigned Dim>

using souffle::Trie< Dim >::element_type = entry_type

Definition at line 2675 of file Brie.h.

◆ entry_span_type

template<unsigned Dim>

using souffle::Trie< Dim >::entry_span_type = typename types::entry_span_type

Definition at line 2668 of file Brie.h.

◆ entry_type

template<unsigned Dim>

using souffle::Trie< Dim >::entry_type = typename types::entry_type

Definition at line 2669 of file Brie.h.

◆ iterator

template<unsigned Dim>

using souffle::Trie< Dim >::iterator = typename types::iterator

Definition at line 2670 of file Brie.h.

◆ iterator_core

template<unsigned Dim>

using souffle::Trie< Dim >::iterator_core = typename types::iterator_core

Definition at line 2671 of file Brie.h.

◆ nested_trie_type

template<unsigned Dim>

using souffle::Trie< Dim >::nested_trie_type = typename types::nested_trie_type

private

Definition at line 2661 of file Brie.h.

◆ op_context

template<unsigned Dim>

using souffle::Trie< Dim >::op_context = typename types::op_context

Definition at line 2672 of file Brie.h.

◆ operation_hints

template<unsigned Dim>

using souffle::Trie< Dim >::operation_hints = op_context

Definition at line 2674 of file Brie.h.

◆ store_type

template<unsigned Dim>

using souffle::Trie< Dim >::store_type = typename types::store_type

private

Definition at line 2662 of file Brie.h.

◆ types

template<unsigned Dim>

using souffle::Trie< Dim >::types = TrieTypes<Dim>

private

Definition at line 2660 of file Brie.h.

Constructor & Destructor Documentation

◆ ~Trie()

template<unsigned Dim>

souffle::Trie< Dim >::~Trie ( )

inline

Definition at line 2687 of file Brie.h.

Member Function Documentation

◆ begin()

template<unsigned Dim>

iterator souffle::detail::brie::TrieBase< Dim, Derived >::begin

inline

Obtains an iterator referencing the first element stored within this trie.

Definition at line 2082 of file Brie.h.

2094 {

Referenced by souffle::TEST().

◆ clear()

template<unsigned Dim>

void souffle::Trie< Dim >::clear ( )

inline

Removes all entries within this trie.

Definition at line 2718 of file Brie.h.

                                                                {
         using value_t = typename store_type::value_type;
         using atomic_value_t = typename store_type::atomic_value_type;
  
         // check context
         if (ctxt.lastNested && ctxt.lastQuery == tuple[0]) {
             base::hint_stats.inserts.addHit();

References souffle::detail::brie::tail().

Here is the call graph for this function:

◆ contains()

template<unsigned Dim>

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

inline

Definition at line 2778 of file Brie.h.

                               {};
         }
  
         // conduct recursive step
         return next && next->contains(tail(tuple), ctxt.nestedCtxt);
     }
  
     /**
      * 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.
      *
      * @tparam levels the length of the requested matching prefix
      * @param entry the entry to be looking for
      * @param ctxt the operation context to be utilized
      * @return the corresponding range of matching elements
      */
     template <unsigned levels>
     range<iterator> getBoundaries(const_entry_span_type entry, op_context& ctxt) const {
         // if nothing is bound => just use begin and end
         if constexpr (levels == 0) return make_range(begin(), end());
  

Referenced by souffle::TEST().

◆ empty()

template<unsigned Dim>

bool souffle::detail::brie::TrieBase< Dim, Derived >::empty

inline

Determines whether this trie is empty or not.

Definition at line 2075 of file Brie.h.

2078 {

◆ end()

template<unsigned Dim>

iterator souffle::detail::brie::TrieBase< Dim, Derived >::end

inline

Obtains an iterator referencing the position after the last element stored within this trie.

Definition at line 2090 of file Brie.h.

2094 {

Referenced by souffle::TEST().

◆ find()

template<unsigned Dim>

iterator souffle::detail::brie::TrieBase< Dim, Derived >::find

inline

Definition at line 2094 of file Brie.h.

                                                                      {
         op_context ctxt;
         return impl().template getBoundaries<levels>(entry, ctxt);
     }

◆ getBoundaries() [1/5]

template<unsigned Dim>

template<unsigned levels>

range<iterator> souffle::detail::brie::TrieBase< Dim, Derived >::getBoundaries ( unsigned levels )

inline

Definition at line 2121 of file Brie.h.

2123 { \

◆ getBoundaries() [2/5]

template<unsigned Dim>

template<unsigned levels>

range<iterator> souffle::detail::brie::TrieBase< Dim, Derived >::getBoundaries ( unsigned levels )

inline

Definition at line 2116 of file Brie.h.

                                                    {               \
         op_context ctxt;                                           \
         return impl().fn(entry, ctxt);                             \

◆ getBoundaries() [3/5]

template<unsigned Dim>

template<unsigned levels>

range<iterator> souffle::detail::brie::TrieBase< Dim, Derived >::getBoundaries ( unsigned levels )

inline

Definition at line 2110 of file Brie.h.

                                                           {
         return impl().template getBoundaries<levels>(entry_type{ramBitCast(values)...});
     }
  

◆ getBoundaries() [4/5]

template<unsigned Dim>

template<unsigned levels>

range<iterator> souffle::Trie< Dim >::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 2812 of file Brie.h.

                       {};
         iterator end{};
  
         // adapt them level by level
         auto found = fix_binding<levels, 0, Dim>()(store, begin, end, entry);
         if (!found) return make_range(iterator(), iterator());
  
         // update context
         static_assert(std::tuple_size_v<decltype(ctxt.lastBoundaryRequest)> == Dim);
         static_assert(std::tuple_size_v<decltype(entry)> == Dim);
         ctxt.lastBoundaryLevels = levels;
         std::copy_n(entry.begin(), Dim, ctxt.lastBoundaryRequest.begin());
         ctxt.lastBoundaries = make_range(begin, end);
  
         // use the result
         return ctxt.lastBoundaries;
     }
  
     /**
      * Obtains an iterator to the first element not less than the given entry value.
      *
      * @param entry the lower bound for this search
      * @param ctxt the operation context to be utilized
      * @return an iterator addressing the first element in this structure not less than the given value
      */
     iterator lower_bound(const_entry_span_type entry, op_context& /* ctxt */) const {
         // start with a default-initialized iterator
         iterator res;
  
         // adapt it level by level
         bool found = fix_lower_bound<Dim>()(store, res, entry);
  
         // use the result

◆ getBoundaries() [5/5]

template<unsigned Dim>

template<unsigned levels, typename... Values, typename = std::enable_if_t<(isRamType<Values> && ...)>>

range<iterator> souffle::detail::brie::TrieBase< Dim, Derived >::getBoundaries	(	unsigned	levels,
		typename...	Values,
		typename	= `std::enable_if_t<(isRamType<Values> && ...)>`
	)

inline

Definition at line 2126 of file Brie.h.

2138 {

◆ getMemoryUsage()

template<unsigned Dim>

std::size_t souffle::Trie< Dim >::getMemoryUsage ( ) const

inline

Computes the total memory usage of this data structure.

Definition at line 2706 of file Brie.h.

2720 {

◆ insert()

template<unsigned Dim>

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

inline

Inserts a new entry.

A operation context may be provided to exploit temporal locality.

Parameters

tuple	the entry to be added
ctxt	the operation context to be utilized

Returns: true if the same tuple hasn't been present before, false otherwise

Definition at line 2736 of file Brie.h.

                       {
             // create a sub-tree && register it atomically
             auto newNested = std::make_unique<nested_trie_type>();
             if (next.compare_exchange_weak(nextPtr, newNested.get())) {
                 nextPtr = newNested.release();  // worked, ownership is acquired by `store`
             }
             // otherwise some other thread was faster => use its version
         }
  
         // make sure a next has been established
         assert(nextPtr);
  
         // clear context if necessary
         if (nextPtr != ctxt.lastNested) {
             ctxt.lastQuery = tuple[0];
             ctxt.lastNested = nextPtr;
             ctxt.nestedCtxt = {};
         }
  
         // conduct recursive step
         return nextPtr->insert(tail(tuple), ctxt.nestedCtxt);
     }
  
     bool contains(const_entry_span_type tuple, op_context& ctxt) const {
         // check context
         if (ctxt.lastNested && ctxt.lastQuery == tuple[0]) {
             base::hint_stats.contains.addHit();
             return ctxt.lastNested->contains(tail(tuple), ctxt.nestedCtxt);
         }
  
         base::hint_stats.contains.addMiss();
  
         // lookup next step
         auto next = store.lookup(tuple[0], ctxt.local);
  
         // clear context if necessary
         if (next != ctxt.lastNested) {
             ctxt.lastQuery = tuple[0];

◆ lower_bound()

template<unsigned Dim>

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

inline

Obtains an iterator to the first element not less than the given entry value.

Parameters

entry	the lower bound for this search
ctxt	the operation context to be utilized

Returns: an iterator addressing the first element in this structure not less than the given value

Definition at line 2859 of file Brie.h.

                                                                            {
         // start with a default-initialized iterator
         iterator res;
  
         // adapt it level by level
         bool found = fix_upper_bound<Dim>()(store, res, entry);
  

◆ partition()

template<unsigned Dim>

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

inline

Computes a partition of an approximate number of chunks of the content of this trie.

Thus, the union of the resulting set of disjoint ranges is equivalent to the content of this trie.

Parameters

chunks the number of chunks requested

Returns: a list of sub-ranges forming a partition of the content of this trie

Definition at line 2897 of file Brie.h.

                : public TrieBase<1u, Trie<1u>> {
     using base = TrieBase<1u, Trie<1u>>;
     using types = TrieTypes<1u>;
     using store_type = typename types::store_type;
  
     using base::store;
  

◆ size()

template<unsigned Dim>

std::size_t souffle::Trie< Dim >::size ( ) const

inline

Determines the number of entries in this trie.

Definition at line 2694 of file Brie.h.

2702 {

◆ upper_bound()

template<unsigned Dim>

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

inline

Obtains an iterator to the first element greater than the given entry value, or end if there is no such element.

Parameters

entry	the upper bound for this search
ctxt	the operation context to be utilized

Returns: an iterator addressing the first element in this structure greater than the given value

Definition at line 2878 of file Brie.h.

                                                                       {
         std::vector<range<iterator>> res;
  
         // shortcut for empty trie
         if (this->empty()) return res;
  
         // use top-level elements for partitioning

Friends And Related Function Documentation

◆ Trie

template<unsigned Dim>

template<unsigned N>

friend class Trie

friend

Definition at line 2656 of file Brie.h.

Field Documentation

◆ store

template<unsigned Dim>

store_type souffle::detail::brie::TrieBase< Dim, Derived >::store

private

Definition at line 2044 of file Brie.h.

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

include/souffle/datastructure/Brie.h

Public Types

Public Member Functions

Private Types

Private Attributes

Friends

Detailed Description

template<unsigned Dim> class souffle::Trie< Dim >

Member Typedef Documentation

◆ base

◆ const_entry_span_type

◆ element_type

◆ entry_span_type

◆ entry_type

◆ iterator

◆ iterator_core

◆ nested_trie_type

◆ op_context

◆ operation_hints

◆ store_type

◆ types

Constructor & Destructor Documentation

◆ ~Trie()

Member Function Documentation

◆ begin()

◆ clear()

◆ contains()

◆ empty()

◆ end()

◆ find()

◆ getBoundaries() [1/5]

◆ getBoundaries() [2/5]

◆ getBoundaries() [3/5]

◆ getBoundaries() [4/5]

◆ getBoundaries() [5/5]

◆ getMemoryUsage()

◆ insert()

◆ lower_bound()

◆ partition()

◆ size()

◆ upper_bound()

Friends And Related Function Documentation

◆ Trie

Field Documentation

◆ store

template<unsigned Dim>
class souffle::Trie< Dim >