A generic key-value LRU cache. More...

#include <LruCache.h>

Classes
class	const_iterator
	A constant iterator of the `LruCache` object. More...

class	ValueType
	A type of objects to be stored. More...

Public Types
using	EvictionFunction = std::function< void(const Key &, Value &&)>
	An alias for the eviction function.

using	CompareType = typename MapType::key_compare
	An alias for the key comparison function.

using	AllocType = typename MapType::allocator_type
	An alias for the cache allocator type.

Public Member Functions
	LruCache (const AllocType &alloc=AllocType())
	Creates an `LruCache` instance. More...

	LruCache (std::size_t maxSize, CacheCostFunc cacheCostFunc=CacheCostFunc(), const CompareType &compare=CompareType(), const AllocType &alloc=AllocType())
	Creates an `LruCache` instance. More...

	LruCache (const LruCache &)=delete
	The deleted copy constructor.

	LruCache (LruCache &&other) noexcept
	The default move constructor.

LruCache &	operator= (const LruCache &)=delete
	The deleted assignment operator.

LruCache &	operator= (LruCache &&other) noexcept
	The default move assignment operator.

template<typename _Key , typename _Value >
std::pair< const_iterator, bool >	Insert (_Key &&key, _Value &&value)
	Inserts a key-value pair in the cache. More...

template<typename _Value >
std::pair< const_iterator, bool >	InsertOrAssign (Key key, _Value &&value)
	Inserts a key-value pair in the cache or updates an existing key-value pair. More...

bool	Erase (const Key &key)
	Removes a key from the cache. More...

const_iterator	Erase (const_iterator &it)
	Removes a key from the cache. More...

std::size_t	Size () const
	Gets the current size of the cache. More...

std::size_t	GetMaxSize () const
	Gets the maximum size of the cache. More...

void	Resize (size_t maxSize)
	Sets the new maximum size of the cache. More...

const_iterator	Find (const Key &key)
	Finds a value in the cache. More...

const_iterator	FindNoPromote (const Key &key) const
	Finds a value in the cache. More...

const Value &	Find (const Key &key, const Value &nullValue)
	Finds a value in the cache. More...

const_iterator	begin () const
	Returns a constant iterator to the beginning.

const_iterator	end () const
	Returns a constant iterator to the end.

const_iterator	rbegin () const
	Returns a reverse constant iterator to the beginning.

const_iterator	rend () const
	Returns a reverse constant iterator to the end.

void	Clear ()
	Removes all items from the cache. More...

void	SetEvictionCallback (EvictionFunction func)
	Sets a function that is invoked when a value is evicted from the cache. More...

template<typename _Key , typename _Value >
auto	Insert (_Key &&key, _Value &&value) -> std::pair< const_iterator, bool >
	Inserts a key-value pair in the cache. More...

template<typename _Value >
auto	InsertOrAssign (Key key, _Value &&value) -> std::pair< const_iterator, bool >
	Inserts a key-value pair in the cache or updates an existing key-value pair. More...

Friends
struct	CacheLruChecker

Detailed Description

template<typename Key, typename Value, typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>
class olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >

A generic key-value LRU cache.

This cache stores elements in a map up to the specified maximum size. The cache eviction follows the LRU principle: the element that was accessed last is evicted last.

The specializations return a non-zero value for any given object.

Template Parameters

Key	The `LruCache` key type.
Value	The `LruCache` value type.
CacheCostFunc	The cache cost functor. The specializations should return a non-zero value for any given object. The default implementation returns "1" as the size for each object.
Compare	The comparison function to be used for sorting keys. The default value of `std::less` is used, which sorts the keys in ascending order.
Alloc	The allocator to be used for allocating internal data. The default value of `std::allocator` is used.

Constructor & Destructor Documentation

◆ LruCache() [1/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::LruCache ( const AllocType & alloc = AllocType() )

inlineexplicit

Creates an LruCache instance.

Creates an invalid LruCache with the maximum size of 0 that caches nothing.

Parameters

alloc The allocator for the cache.

◆ LruCache() [2/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::LruCache	(	std::size_t	maxSize,
		CacheCostFunc	cacheCostFunc = `CacheCostFunc()`,
		const CompareType &	compare = `CompareType()`,
		const AllocType &	alloc = `AllocType()`
	)

inline

Creates an LruCache instance.

Parameters

maxSize	The maximum size of values this cache can keep.
cacheCostFunc	The function this cache uses to compute the caching cost of each cached value.
compare	The function object for comparing keys.
alloc	The allocator for the cache.

Member Function Documentation

◆ Clear()

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

void olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Clear ( )

inline

Removes all items from the cache.

Removes all content but does not reset the eviction callback or maximum size.

◆ Erase() [1/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

bool olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Erase ( const Key & key )

inline

Removes a key from the cache.

Parameters

key	The key to remove.

Returns: True if the key exists and is removed from the cache; false otherwise.

◆ Erase() [2/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

const_iterator olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Erase ( const_iterator & it )

inline

Removes a key from the cache.

Parameters

it	The iterator of the key that should be removed.

Returns: A new iterator.

◆ Find() [1/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

const_iterator olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Find ( const Key & key )

inline

Finds a value in the cache.

Note: This function promotes the item pointed to by a key if found.

Parameters

key	The key to find.

Returns: If found, the iterator to the value; the iterator pointing to end() otherwise.

◆ Find() [2/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

const Value& olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Find	(	const Key &	key,
		const Value &	nullValue
	)

inline

Finds a value in the cache.

Note: This function promotes the item pointed to by a key if found.

Parameters

key	The key to find.
nullValue	The value to return if the key-value pair is not in the cache

Returns: If found, a constant reference to the value; nullValue otherwise.

◆ FindNoPromote()

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

const_iterator olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::FindNoPromote ( const Key & key ) const

inline

Finds a value in the cache.

Note: This function does NOT promote the item pointed to by a key if found.

Parameters

key	The key to find.

Returns: If found, the iterator to the value; the iterator pointing to end() otherwise.

◆ GetMaxSize()

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

std::size_t olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::GetMaxSize ( ) const

inline

Gets the maximum size of the cache.

Returns: The maximum cache size.

◆ Insert() [1/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

template<typename _Key , typename _Value >

std::pair<const_iterator, bool> olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Insert	(	_Key &&	key,
		_Value &&	value
	)

Inserts a key-value pair in the cache.

Note: If the key already exists in the cache, it is promoted in the LRU, but its value and cost are not updated. To update or insert existing values, use InsertOrAssign instead.

If the key or value is an rvalue reference, they are moved; copied otherwise.

Note: This function behaves analogously to std::map. Even if the insertion fails, the key and value can be moved. Do not access them further.

Parameters

key	The key to add.
value	The value to add.

Returns: A pair of bool and an iterator, analogously to std::map::insert(). If the bool is true, the item is inserted, and the iterator points to the newly inserted item. If the bool is false and the iterator points to end(), the item cannot be inserted. Otherwise, the bool is false, and the iterator points to the item that prevented the insertion.

◆ Insert() [2/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

template<typename _Key , typename _Value >

auto olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Insert	(	_Key &&	key,
		_Value &&	value
	)		-> std::pair<const_iterator, bool>

Inserts a key-value pair in the cache.

Note: If the key already exists in the cache, it is promoted in the LRU, but its value and cost are not updated. To update or insert existing values, use InsertOrAssign instead.

If the key or value is an rvalue reference, they are moved; copied otherwise.

Note: This function behaves analogously to std::map. Even if the insertion fails, the key and value can be moved. Do not access them further.

Parameters

key	The key to add.
value	The value to add.

Returns: A pair of bool and an iterator, analogously to std::map::insert(). If the bool is true, the item is inserted, and the iterator points to the newly inserted item. If the bool is false and the iterator points to end(), the item cannot be inserted. Otherwise, the bool is false, and the iterator points to the item that prevented the insertion.

◆ InsertOrAssign() [1/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

template<typename _Value >

std::pair<const_iterator, bool> olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::InsertOrAssign	(	Key	key,
		_Value &&	value
	)

Inserts a key-value pair in the cache or updates an existing key-value pair.

Note: If the key already exists in the cache, its value and cost are updated. Not to update the existing key-value pair, use Insert instead.

Parameters

key	The key to add.
value	The value to add.

Returns: A pair of bool and an iterator, analogously to std::map::insert_or_assign(). If the bool is true, the item is inserted, and the iterator points to the newly inserted item. If the bool is false and the iterator points to end(), the item cannot be inserted. Otherwise, the bool is false, and the iterator points to the item that is assigned.

◆ InsertOrAssign() [2/2]

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

template<typename _Value >

auto olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::InsertOrAssign	(	Key	key,
		_Value &&	value
	)		-> std::pair<const_iterator, bool>

Inserts a key-value pair in the cache or updates an existing key-value pair.

Note: If the key already exists in the cache, its value and cost are updated. Not to update existing key-value pairs, use Insert instead.

Parameters

key	The key to add.
value	The value to add.

Returns: A pair of bool and an iterator, analogously to std::map::insert_or_assign(). If the bool is true, the item is inserted, and the iterator points to the newly inserted item. If the bool is false and the iterator points to end(), the item cannot be inserted. Otherwise, the bool is false, and the iterator points to the item that is assigned.

◆ Resize()

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

void olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Resize ( size_t maxSize )

inline

Sets the new maximum size of the cache.

If the new maximum size is smaller than the current size, items are evicted until the cache shrinks to less than or equal to the new maximum size.

Parameters

maxSize The new maximum size of the cache.

◆ SetEvictionCallback()

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

void olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::SetEvictionCallback ( EvictionFunction func )

inline

Sets a function that is invoked when a value is evicted from the cache.

Note: The function must not modify the cache in the callback. The value can be safely moved. If not, it is destroyed when the function returns.

To reset the eviction callback, pass nullptr.

Parameters

func	The function to be called on eviction.

◆ Size()

template<typename Key , typename Value , typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>

std::size_t olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >::Size ( ) const

inline

Gets the current size of the cache.

Returns: The current cache size.

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

olp-cpp-sdk-core/include/olp/core/utils/LruCache.h

Classes

Public Types

Public Member Functions

Friends

Detailed Description

template<typename Key, typename Value, typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator> class olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >

Constructor & Destructor Documentation

◆ LruCache() [1/2]

◆ LruCache() [2/2]

Member Function Documentation

◆ Clear()

◆ Erase() [1/2]

◆ Erase() [2/2]

◆ Find() [1/2]

◆ Find() [2/2]

◆ FindNoPromote()

◆ GetMaxSize()

◆ Insert() [1/2]

◆ Insert() [2/2]

◆ InsertOrAssign() [1/2]

◆ InsertOrAssign() [2/2]

◆ Resize()

◆ SetEvictionCallback()

◆ Size()

template<typename Key, typename Value, typename CacheCostFunc = CacheCost<Value>, typename Compare = std::less<Key>, template< typename > class Alloc = std::allocator>
class olp::utils::LruCache< Key, Value, CacheCostFunc, Compare, Alloc >