Least Recently Used Cache. More...

#include <vc/core/types/LRUCache.hpp>

Inheritance diagram for volcart::LRUCache< TKey, TValue, TMutex >:

Collaboration diagram for volcart::LRUCache< TKey, TValue, TMutex >:

Public Types
using	BaseClass = Cache< TKey, TValue >

using	TPair = std::pair< TKey, TValue >
	Templated Key/Value pair. More...

using	TListIterator = typename std::list< TPair >::iterator
	Templated Key/Value pair iterator. More...

using	Pointer = std::shared_ptr< LRUCache< TKey, TValue > >

Public Types inherited from volcart::Cache< TKey, TValue >
using	Pointer = std::shared_ptr< Cache >

Public Member Functions

void	setCapacity (std::size_t capacity) override
	Set the maximum number of elements in the cache. More...

auto	capacity () const -> std::size_t override
	Get the maximum number of elements in the cache. More...

auto	size () const -> std::size_t override
	Get the current number of elements in the cache. More...


auto	get (const TKey &k) -> TValue override
	Get an item from the cache by key. More...

void	put (const TKey &k, const TValue &v) override
	Put an item into the cache. More...

auto	contains (const TKey &k) -> bool override
	Check if an item is already in the cache. More...

void	onEvict (std::function< bool(TKey &, TValue &)> fn) override
	Set a callback function for validating if an item can be evicted. More...

void	resetOnEvict () override
	Remove the validation callback function. More...

void	evict () override
	Evict items following the cache policy. More...

void	purge () override
	Evict all items ignoring cache policy. More...

Public Member Functions inherited from volcart::Cache< TKey, TValue >
virtual	~Cache ()=default

Public Attributes
std::size_t	capacity_

Private Attributes
std::list< TPair >	items_

std::unordered_map< TKey, TListIterator >	lookup_

TMutex	cache_mutex_

	LRUCache ()
	Default constructor. More...

	LRUCache (std::size_t capacity)
	Constructor with cache capacity parameter. More...

static auto	New () -> Pointer

static auto	New (std::size_t capacity) -> Pointer

Additional Inherited Members
Protected Member Functions inherited from volcart::Cache< TKey, TValue >
	Cache ()=default

	Cache (const std::size_t capacity)

Protected Attributes inherited from volcart::Cache< TKey, TValue >
std::size_t	capacity_ {200}

std::function< bool(TKey &, TValue &)>	on_eject_

Detailed Description

template<typename TKey, typename TValue, class TMutex = std::shared_mutex>
class volcart::LRUCache< TKey, TValue, TMutex >

Least Recently Used Cache.

Author: Sean Karlage

A cache using a least recently used replacement policy. As elements are used, they are moved to the front of the cache. When the cache exceeds capacity, elements are popped from the end of the cache and replacement elements are added to the front.

Data elements are stored in a std::list, ordered from most to least recently used. A key-value map into this list is stored in a std::unordered_map.

If a function is provided to onEvict(), cache entries are only removed if the function returns true for the given entry. See the documentation of onEvict() for more details.

Design mostly taken from here.

Definition at line 44 of file LRUCache.hpp.

Member Typedef Documentation

◆ BaseClass

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

using volcart::LRUCache< TKey, TValue, TMutex >::BaseClass = Cache<TKey, TValue>

Definition at line 47 of file LRUCache.hpp.

◆ Pointer

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

using volcart::LRUCache< TKey, TValue, TMutex >::Pointer = std::shared_ptr<LRUCache<TKey, TValue> >

Shared pointer type

Definition at line 65 of file LRUCache.hpp.

◆ TListIterator

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

using volcart::LRUCache< TKey, TValue, TMutex >::TListIterator = typename std::list<TPair>::iterator

Templated Key/Value pair iterator.

Stored in the LRU map.

Definition at line 62 of file LRUCache.hpp.

◆ TPair

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

using volcart::LRUCache< TKey, TValue, TMutex >::TPair = std::pair<TKey, TValue>

Templated Key/Value pair.

Stored in the data list.

Definition at line 55 of file LRUCache.hpp.

Constructor & Destructor Documentation

◆ LRUCache() [1/2]

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

volcart::LRUCache< TKey, TValue, TMutex >::LRUCache ( )

inline

Default constructor.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 69 of file LRUCache.hpp.

◆ LRUCache() [2/2]

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

volcart::LRUCache< TKey, TValue, TMutex >::LRUCache ( std::size_t capacity )

inlineexplicit

Constructor with cache capacity parameter.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 72 of file LRUCache.hpp.

Member Function Documentation

◆ capacity()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

auto volcart::LRUCache< TKey, TValue, TMutex >::capacity ( ) const -> std::size_t

inlineoverridevirtual

Get the maximum number of elements in the cache.

Implements volcart::Cache< TKey, TValue >.

Definition at line 101 of file LRUCache.hpp.

◆ contains()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

auto volcart::LRUCache< TKey, TValue, TMutex >::contains ( const TKey & k ) -> bool

inlineoverridevirtual

Check if an item is already in the cache.

Implements volcart::Cache< TKey, TValue >.

Definition at line 142 of file LRUCache.hpp.

◆ evict()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

void volcart::LRUCache< TKey, TValue, TMutex >::evict ( )

inlineoverridevirtual

Evict items following the cache policy.

Automatically called whenever the cache size is expected to exceed the current capacity. Normally should not need to be called directly except when using onEvict() to conditionally keep items which would otherwise be evicted.

Implements volcart::Cache< TKey, TValue >.

Definition at line 181 of file LRUCache.hpp.

◆ get()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

auto volcart::LRUCache< TKey, TValue, TMutex >::get ( const TKey & k ) -> TValue

inlineoverridevirtual

Get an item from the cache by key.

Implements volcart::Cache< TKey, TValue >.

Definition at line 109 of file LRUCache.hpp.

◆ New() [1/2]

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

static auto volcart::LRUCache< TKey, TValue, TMutex >::New ( ) -> Pointer

inlinestatic

Definition at line 75 of file LRUCache.hpp.

◆ New() [2/2]

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

static auto volcart::LRUCache< TKey, TValue, TMutex >::New ( std::size_t capacity ) -> Pointer

inlinestatic

Definition at line 81 of file LRUCache.hpp.

◆ onEvict()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

void volcart::LRUCache< TKey, TValue, TMutex >::onEvict ( std::function< bool(TKey &, TValue &)> fn )

inlineoverridevirtual

Set a callback function for validating if an item can be evicted.

This optional function is called whenever a cache entry is about to be evicted. Minimally, it should return true if it is safe to remove the cache entry and false otherwise. Optionally, it may also perform cleanup operations for the stored item, such as manual deallocation. Entries are only tested for eviction when calling setCapacity(), put(), evict(), and purge().

Note: Depending upon the function provided, the cache may temporarily store more entries than the capacity suggests.

Implements volcart::Cache< TKey, TValue >.

Definition at line 161 of file LRUCache.hpp.

◆ purge()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

void volcart::LRUCache< TKey, TValue, TMutex >::purge ( )

inlineoverridevirtual

Evict all items ignoring cache policy.

Implements volcart::Cache< TKey, TValue >.

Definition at line 219 of file LRUCache.hpp.

◆ put()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

void volcart::LRUCache< TKey, TValue, TMutex >::put	(	const TKey &	k,
		const TValue &	v
	)

inlineoverridevirtual

Put an item into the cache.

Implements volcart::Cache< TKey, TValue >.

Definition at line 122 of file LRUCache.hpp.

◆ resetOnEvict()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

void volcart::LRUCache< TKey, TValue, TMutex >::resetOnEvict ( )

inlineoverridevirtual

Remove the validation callback function.

See also: onEvict()

Implements volcart::Cache< TKey, TValue >.

Definition at line 171 of file LRUCache.hpp.

◆ setCapacity()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

void volcart::LRUCache< TKey, TValue, TMutex >::setCapacity ( std::size_t capacity )

inlineoverridevirtual

Set the maximum number of elements in the cache.

Implements volcart::Cache< TKey, TValue >.

Definition at line 89 of file LRUCache.hpp.

◆ size()

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

auto volcart::LRUCache< TKey, TValue, TMutex >::size ( ) const -> std::size_t

inlineoverridevirtual

Get the current number of elements in the cache.

Implements volcart::Cache< TKey, TValue >.

Definition at line 104 of file LRUCache.hpp.

Member Data Documentation

◆ cache_mutex_

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

TMutex volcart::LRUCache< TKey, TValue, TMutex >::cache_mutex_

mutableprivate

Shared mutex for thread-safe access

Definition at line 249 of file LRUCache.hpp.

◆ capacity_

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

std::size_t volcart::Cache< TKey, TValue >::capacity_

Maximum number of elements in the cache

Definition at line 68 of file Cache.hpp.

◆ items_

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

std::list<TPair> volcart::LRUCache< TKey, TValue, TMutex >::items_

private

Cache data storage

Definition at line 245 of file LRUCache.hpp.

◆ lookup_

template<typename TKey , typename TValue , class TMutex = std::shared_mutex>

std::unordered_map<TKey, TListIterator> volcart::LRUCache< TKey, TValue, TMutex >::lookup_

private

Cache usage information

Definition at line 247 of file LRUCache.hpp.

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

vc/core/types/LRUCache.hpp

Public Types

Public Member Functions

Public Attributes

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ BaseClass

◆ Pointer

◆ TListIterator

◆ TPair

Constructor & Destructor Documentation

◆ LRUCache() [1/2]

◆ LRUCache() [2/2]

Member Function Documentation

◆ capacity()

◆ contains()

◆ evict()

◆ get()

◆ New() [1/2]

◆ New() [2/2]

◆ onEvict()

◆ purge()

◆ put()

◆ resetOnEvict()

◆ setCapacity()

◆ size()

Member Data Documentation

◆ cache_mutex_

◆ capacity_

◆ items_

◆ lookup_