hpx/cache/lru_cache.hpp#

See Public API for a list of names and headers that are part of the public HPX API.

namespace hpx
namespace util
namespace cache
template<typename Key, typename Entry, typename Statistics = statistics::no_statistics>
class lru_cache#
#include <hpx/cache/lru_cache.hpp>

The lru_cache implements the basic functionality needed for a local (non-distributed) LRU cache.

Template Parameters

  • Key – The type of the keys to use to identify the entries stored in the cache

  • Entry – The type of the items to be held in the cache.

  • Statistics – A (optional) type allowing to collect some basic statistics about the operation of the cache instance. The type must conform to the CacheStatistics concept. The default value is the type statistics::no_statistics which does not collect any numbers, but provides empty stubs allowing the code to compile.

Public Types

using key_type = Key#
using entry_type = Entry#
using statistics_type = Statistics#
using entry_pair = std::pair<key_type, entry_type>#
using storage_type = std::list<entry_pair>#
using map_type = std::map<Key, typename storage_type::iterator>#
using size_type = std::size_t#

Public Functions

inline lru_cache(size_type max_size = 0)#

Construct an instance of a lru_cache.

Parameters

max_size – [in] The maximal size this cache is allowed to reach any time. The default is zero (no size limitation). The unit of this value is usually determined by the unit of the values returned by the entry’s get_size function.

lru_cache(lru_cache &&other) = default#
inline constexpr size_type size() const noexcept#

Return current size of the cache.

Returns

The current size of this cache instance.

inline constexpr size_type capacity() const noexcept#

Access the maximum size the cache is allowed to grow to.

Note

The unit of this value is usually determined by the unit of the return values of the entry’s function entry::get_size.

Returns

The maximum size this cache instance is currently allowed to reach. If this number is zero the cache has no limitation with regard to a maximum size.

inline void reserve(size_type max_size)#

Change the maximum size this cache can grow to.

Parameters

max_size – [in] The new maximum size this cache will be allowed to grow to.

inline bool holds_key(key_type const &key) const#

Check whether the cache currently holds an entry identified by the given key.

Note

This function does not call the entry’s function entry::touch. It just checks if the cache contains an entry corresponding to the given key.

Parameters

k – [in] The key for the entry which should be looked up in the cache.

Returns

This function returns true if the cache holds the referenced entry, otherwise it returns false.

inline bool get_entry(key_type const &key, key_type &realkey, entry_type &entry)#

Get a specific entry identified by the given key.

Note

The function will “touch” the entry and mark it as recently used if the key was found in the cache.

Parameters

  • key – [in] The key for the entry which should be retrieved from the cache.

  • entry – [out] If the entry indexed by the key is found in the cache this value on successful return will be a copy of the corresponding entry.

Returns

This function returns true if the cache holds the referenced entry, otherwise it returns false.

inline bool get_entry(key_type const &key, entry_type const &entry)#

Get a specific entry identified by the given key.

Note

The function will “touch” the entry and mark it as recently used if the key was found in the cache.

Parameters

  • key – [in] The key for the entry which should be retrieved from the cache.

  • entry – [out] If the entry indexed by the key is found in the cache this value on successful return will be a copy of the corresponding entry.

Returns

This function returns true if the cache holds the referenced entry, otherwise it returns false.

template<typename Entry_, typename = std::enable_if_t<std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
inline bool insert(key_type const &key, Entry_ &&entry)#

Insert a new entry into this cache.

Note

This function assumes that the entry is not in the cache already. Inserting an already existing entry is considered undefined behavior

Parameters

  • key – [in] The key for the entry which should be added to the cache.

  • entry – [in] The entry which should be added to the cache.

template<typename Entry_, typename = std::enable_if_t<std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
inline void update(key_type const &key, Entry_ &&entry)#

Update an existing element in this cache.

Note

The function will “touch” the entry and mark it as recently used if the key was found in the cache.

Note

The difference to the other overload of the insert function is that this overload replaces the cached value only, while the other overload replaces the whole cache entry, updating the cache entry properties.

Parameters

  • key – [in] The key for the value which should be updated in the cache.

  • entry – [in] The entry which should be used as a replacement for the existing value in the cache. Any existing cache entry is not changed except for its value.

template<typename F, typename Entry_, std::enable_if_t<std::is_convertible_v<std::decay_t<Entry_>, entry_type>, int> = 0>
inline bool update_if(key_type const &key, Entry_ &&entry, F &&f)#

Update an existing element in this cache.

Note

The function will “touch” the entry and mark it as recently used if the key was found in the cache.

Note

The difference to the other overload of the insert function is that this overload replaces the cached value only, while the other overload replaces the whole cache entry, updating the cache entry properties.

Parameters

  • key – [in] The key for the value which should be updated in the cache.

  • entry – [in] The value which should be used as a replacement for the existing value in the cache. Any existing cache entry is not changed except for its value.

  • f – [in] A callable taking two arguments, k and the key found in the cache (in that order). If f returns true, then the update will continue. If f returns false, then the update will not succeed.

Returns

This function returns true if the entry has been successfully updated, otherwise it returns false. If the entry currently is not held by the cache it is added and the return value reflects the outcome of the corresponding insert operation.

template<typename Func>
inline size_type erase(Func const &ep)#

Remove stored entries from the cache for which the supplied function object returns true.

Parameters

ep – [in] This parameter has to be a (unary) function object. It is invoked for each of the entries currently held in the cache. An entry is considered for removal from the cache whenever the value returned from this invocation is true.

Returns

This function returns the overall size of the removed entries (which is the sum of the values returned by the entry::get_size functions of the removed entries).

inline size_type erase()#

Remove all stored entries from the cache.

Returns

This function returns the overall size of the removed entries (which is the sum of the values returned by the entry::get_size functions of the removed entries).

inline size_type clear()#

Clear the cache.

Unconditionally removes all stored entries from the cache.

inline constexpr statistics_type const &get_statistics() const noexcept#

Allow to access the embedded statistics instance.

Returns

This function returns a reference to the statistics instance embedded inside this cache

inline statistics_type &get_statistics() noexcept#

Private Types

using update_on_exit = typename statistics_type::update_on_exit#

Private Functions

template<typename Entry_, typename = std::enable_if_t<std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
inline void insert_nonexist(key_type const &key, Entry_ &&entry)#
inline void touch(typename storage_type::iterator it)#
inline void evict()#

Private Members

size_type max_size_#
size_type current_size_ = 0#
storage_type storage_#
map_type map_#
statistics_type statistics_#