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

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

Public Functions

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)
constexpr size_type size() const

Return current size of the cache.

Return

The current size of this cache instance.

constexpr size_type capacity() const

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.

Return

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.

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.

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.

Return

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

Parameters

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

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.

Return

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

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.

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.

Return

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

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.

template<typename Entry_, typename = std::enable_if_t<std::is_convertible_v<std::decay_t<Entry_>, entry_type>>>
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>>>
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>
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.

Return

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.

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.

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

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

Return

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).

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.

size_type erase()

Remove all stored entries from the cache.

Return

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).

size_type clear()

Clear the cache.

Unconditionally removes all stored entries from the cache.

constexpr statistics_type const &get_statistics() const

Allow to access the embedded statistics instance.

Return

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

statistics_type &get_statistics()

Private Types

template<>
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>>>
void insert_nonexist(key_type const &key, Entry_ &&entry)
void touch(typename storage_type::iterator it)
void evict()

Private Members

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