#include <x/orderedcache.H> typedef x::ordered_cache_traits<int, std::string> cache_traits; x::ordered_cache<cache_traits> cache(100); cache.add(1, "alpha"); cache.add(2, "beta"); cache.remove(2); const std::string *valueptr=cache.find(1); if (valueptr) { std::cout << *valueptr << std::endl; }
The
x::ordered_cache
template implements a an algorithm for a basic cache: a container for
key/value tuples, that grows to some maximum size, then existing
tuples are removed to make room for new ones.
x::ordered_cache's required template parameter
is an instance of the
x::ordered_cache_traits
template which defines the cache properties.
x::ordered_cache_traits's required first and
second template
parameters specify the classes for the cache's keys and values.
This example caches std::string values, keyed by
ints.
add() adds a key and its value to the
cache.
Only one value can be in the cache given a particular key. If the key
already exists, add() replaces the value in the
cache for that key.
remove() removes a key. Nothing happens if
the key does not exist. find() returns a
nullptr if the cache does not contain a value with the
given key, or a pointer to the corresponding value.
The constructor's argument specifies the maximum cache size.
If add() finds the cache at its maximum size, one
of the existing entries in the cache gets removed, to make room for the
new key and value. The default implementation removes the oldest element
in the cache. The third optional template parameter specifies a class
that controls which element gets removed.
#include <x/orderedcache.H> struct cache_order { int operator()(const int key, const std::string &value) { return key; } }; typedef x::ordered_cache_traits<int, std::string, cache_order> cache_traits; x::ordered_cache<cache_traits> cache(2); cache.add(2, "beta"); cache.add(1, "alpha"); cache.add(3, "gamma");
x::ordered_cache_traits's third parameter is
optional, and defins the class that sets the cache order.
add() calls the ordering class's functor
once for each key and value. The ordering class's functor returns the
ordering value for that cache entry.
When the cache's size is its maximum size, cache entry with the smallest
ordering value gets removed.
This example limits the cache to two elements, and the functor sets the
cache order value to the value of the key. The third
add() removes the “alpha” from the
cache, because it was the one with the smallest cache order value.
The functor gets called to obtain the ordering value once, for each key and data added to the cache, and the ordering value gets saved (unless “most recently used” flag is set, see below). When its time to trim the cache, the entry with the smallest saved ordering value gets the boot.
When more than one key/value tuple in the cache has the same ordering value, it is unspecified which one of them gets removed from the cache, first.
auto orderer=[] (const int key, const std::string &value) { return key; }; typedef x::ordered_cache_traits<int, std::string, decltype(orderer)> cache_traits; x::ordered_cache<cache_traits> cache(2);
This is an equivalent example that uses a lambda.
x::ordered_cache_traits's
third template parameter defaults to
x::ordered_cache_fifo
that sets up the default behavior of removing the oldest element in the
cache by using a simple counter:
class x::ordered_cache_fifo { size_t counter=0; public: template<typename key_type, typename value_type> size_t operator()(const key_type &key, const value_type &value) { return ++counter; } };
The value returning by the ordering class functor does not have to be
an int or a size_t, but
can be any class that implements strict weak ordering.
x::ordered_cache_traits
has two more optional template parameters:
A key class comparator implementing strict weak ordering for the
key class, which defaults to
std::less<key_type>.
An ordering class comparator implementing strict weak ordering for the
return value from the ordering functor, which defaults to
std::less<return value type from the ordering functor>.
The parameters to x::orderedcache's
constructor are:
Maximum cache size. This is the only required parameter. All of the remaining parameters are optional, and get constructed by default using the default constructor of the corresponding class:
Orderer class instance.
Key type comparator class instance.
Ordering value comparator class instance.
x::orderedcache does not implement locking.
Use x::mpobj to implement a thread-safe
ordered cache.
x::ordered_cache<cache_traits, true> cache(100);
x::orderedcache's second template parameter is a
bool value, defaulting to
false. Setting it to true has the
effect of enabling “most recently used” caching logic.
Specifically: when find() and
add() locate an existing cache entry, the
ordering class's functor is called again to calculate the new
ordering value, and the key/value tuple gets repositioned in the ordered
cache according to its new ordering value.