A general purpose LRU evicting cache designed to support constant time set/get/insert/erase ops. The only required configuration parameter is the maxSize, which is the maximum number of entries held by the cache, which is also dynamically changeable. Insertion will evict (and destroy with ~TKey and ~TValue) existing entries in LRU order as needed to keep number of entries less than maxSize. When automatic eviction is triggered, the minimum number of evictions is clearSize, which is configurable with a default of 1. If a callback is specified with setPruneHook, it is invoked for each eviction. However, the prune hook cannot manage object lifetimes because it is not invoked on erase nor cache destruction.
Declared in <folly/container/EvictingCacheMap.h>
template<
class TKey,
class TValue,
class THash = HeterogeneousAccessHash<TKey>,
class TKeyEqual = HeterogeneousAccessEqualTo<TKey>>
class EvictingCacheMap;This is NOT a thread-safe implementation.
Iterators and references are only invalidated when the referenced entry might have been removed (pruned or erased), like std::map.
NOTE: maxSize==0 is a special case that disables automatic evictions. prune() can be used for manually trimming down the number of entries.
Implementation: Maintains a doubly linked list (lru_) of entry nodes in LRU order, which are also connected to hash table index (index_). The access order is maintained on the list by moving an element to the front of list on a get, and adding to the front on insert. Assuming quality hashing, set/get are both constant time operations.
NOTE: Previous versions of this structure used a hash table size that was fixed at creation time, but that limitation is no longer present.
| Name | Description |
|---|---|
iterator_base | Iterator base that returns TPair on dereference. |
| Name | Description |
|---|---|
PruneHookCall | Callback type invoked on eviction with the key and value. |
const_iterator | Const iterator over key-value pairs in LRU order. |
const_reverse_iterator | Const reverse iterator over key-value pairs in LRU order. |
hasher | The hash function type. |
iterator | Iterator over key-value pairs in LRU order. |
key_type | The key type. |
mapped_type | The mapped value type. |
reverse_iterator | Reverse iterator over key-value pairs in LRU order. |
| Name | Description |
|---|---|
EvictingCacheMap [constructor] | Constructors |
~EvictingCacheMap [destructor] | Destroys the cache map. |
operator= | Assignment operators |
begin | begin overloads |
cbegin | Returns a const iterator to the most recently used entry. |
cend | Returns a const iterator past the least recently used entry. |
clear | Remove all entries (as if all evicted) |
crbegin | Returns a const reverse iterator to the least recently used entry. |
crend | Returns a const reverse iterator past the most recently used entry. |
emplaceWithPruneHook | Emplace a new key-value pair in the dictionary if no element exists for key |
empty | Typical empty function |
end | end overloads |
erase | erase overloads |
exists | exists overloads |
find | find overloads |
findWithoutPromotion | findWithoutPromotion overloads |
get | get overloads |
getMaxSize | Returns the maximum size of the cache map. |
getPruneHook | Returns the currently configured prune hook. |
getWithoutPromotion | getWithoutPromotion overloads |
insert | insert overloads |
prune | Prune the minimum of pruneSize and size() from the back of the LRU. Will throw if pruneHook throws. |
rbegin | rbegin overloads |
rend | rend overloads |
set | set overloads |
setClearSize | Set the number of elements to evict at a time on automatic eviction. |
setMaxSize | Adjust the max size of EvictingCacheMap, evicting as needed to ensure the new max is not exceeded. |
setPruneHook | Set the prune hook, which is the function invoked on the key and value on each eviction. An operation will throw if the pruneHook throws. Note that this prune hook is not automatically called on entries explicitly erase()ed nor on remaining entries at destruction time. |
size | Get the number of elements in the dictionary |
try_emplace | Emplace a new key-value pair in the dictionary if no element exists for key, utilizing the configured prunehook |
| Name | Description |
|---|---|
kApproximateEntryMemUsage | Approximate size of memory used by each entry added to the cache, including the shallow bits (sizeof) of TKey and TValue, but not the deep bits. Using 128 (bytes per chunk) / 10 (avg entries per chunk) as approximate F14 index entry size. |