souffle::LRUCache< T, size > Class Template Reference

An Least-Recently-Used cache for arbitrary element types. More...

#include <CacheUtil.h>

Collaboration diagram for souffle::LRUCache< T, size >:

Public Member Functions
void	access (const T &val)
template<typename Op >
bool	any (const Op &op) const
void	clear (const T &val=T())
template<typename Op >
bool	forEachInOrder (const Op &op) const
	Iterates over the elements within this cache in LRU order. More...
	LRUCache (const T &val=T())

Private Attributes
std::array< T, size >	entries
std::size_t	first {0}
std::size_t	last {size - 1}
std::array< std::size_t, size >	post
std::array< std::size_t, size >	priv

Detailed Description

template<typename T, unsigned size = 1>
class souffle::LRUCache< T, size >

An Least-Recently-Used cache for arbitrary element types.

Elements can be signaled to be accessed and iterated through in their LRU order.

Definition at line 39 of file CacheUtil.h.

Constructor & Destructor Documentation

LRUCache()

template<typename T , unsigned size = 1>

souffle::LRUCache< T, size >::LRUCache ( const T &  val = T() )

inline

Definition at line 58 of file CacheUtil.h.

                       : entries) {
            cur = val;
        }
    }
 
    // registers an access to the given element
    void access(const T& val) {
        // test whether it is contained
        for (std::size_t i = 0; i < size; i++) {

Member Function Documentation

access()

template<typename T , unsigned size = 1>

void souffle::LRUCache< T, size >::access ( const T &  val )

inline

Definition at line 76 of file CacheUtil.h.

                           {
                auto tmp = last;
                last = priv[last];
                first = tmp;
                return;
            }
 
            // otherwise we need to update the linked list
 
            // remove from current position
            post[priv[i]] = post[i];
            priv[post[i]] = priv[i];
 
            // insert in first position
            post[i] = first;
            priv[i] = last;
            priv[first] = i;
            post[last] = i;
 
            // update first pointer
            first = i;
            return;
        }
        // not present => drop last, make it first
        entries[last] = val;
        auto tmp = last;
        last = priv[last];
        first = tmp;
    }
 
    /**
     * Iterates over the elements within this cache in LRU order.
     * The operator is applied on each element. If the operation
     * returns false, iteration is continued. If the operator return
     * true, iteration is stopped -- similar to the any operator.
     *
     * @param op the operator to be applied on every element
     * @return true if op returned true for any entry, false otherwise
     */
    template <typename Op>
    bool forEachInOrder(const Op& op) const {

any()

template<typename T , unsigned size = 1>

template<typename Op >

bool souffle::LRUCache< T, size >::any ( const Op &  op ) const

inline

Definition at line 142 of file CacheUtil.h.

                     {

clear()

template<typename T , unsigned size = 1>

void souffle::LRUCache< T, size >::clear ( const T &  val = T() )

inline

Definition at line 69 of file CacheUtil.h.

                            {

forEachInOrder()

template<typename T , unsigned size = 1>

template<typename Op >

bool souffle::LRUCache< T, size >::forEachInOrder ( const Op &  op ) const

inline

Iterates over the elements within this cache in LRU order.

The operator is applied on each element. If the operation returns false, iteration is continued. If the operator return true, iteration is stopped – similar to the any operator.

Parameters

op	the operator to be applied on every element

Returns

true if op returned true for any entry, false otherwise

Definition at line 131 of file CacheUtil.h.

                                                                        {
    bool first = true;
    cache.forEachInOrder([&](const T& val) {

Referenced by souffle::LRUCache< T, 1 >::forEachInOrder(), and souffle::LRUCache< T, 0 >::forEachInOrder().

Field Documentation

entries

template<typename T , unsigned size = 1>

std::array<T, size> souffle::LRUCache< T, size >::entries

private

Definition at line 47 of file CacheUtil.h.

first

template<typename T , unsigned size = 1>

std::size_t souffle::LRUCache< T, size >::first {0}

private

Definition at line 53 of file CacheUtil.h.

last

template<typename T , unsigned size = 1>

std::size_t souffle::LRUCache< T, size >::last {size - 1}

private

Definition at line 54 of file CacheUtil.h.

post

template<typename T , unsigned size = 1>

std::array<std::size_t, size> souffle::LRUCache< T, size >::post

private

Definition at line 51 of file CacheUtil.h.

priv

template<typename T , unsigned size = 1>

std::array<std::size_t, size> souffle::LRUCache< T, size >::priv

private

Definition at line 50 of file CacheUtil.h.

---

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

• include/souffle/utility/CacheUtil.h