Chapter 45. An ordered cache

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

Note

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.

Note

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:

The parameters to x::orderedcache's constructor are:

  1. 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:

  2. Orderer class instance.

  3. Key type comparator class instance.

  4. Ordering value comparator class instance.

Note

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.