Volume Cartographer 2.27.0
Public Types | Public Attributes | Private Attributes | List of all members
volcart::LRUCache< TKey, TValue, TMutex > Class Template Referencefinal

Least Recently Used Cache. More...

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

Inheritance diagram for volcart::LRUCache< TKey, TValue, TMutex >:
[legend]
Collaboration diagram for volcart::LRUCache< TKey, TValue, TMutex >:
[legend]

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< TPairitems_
 
std::unordered_map< TKey, TListIteratorlookup_
 
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: