A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
MruCache< Key, T > Class Template Reference

#include <genesis/utils/containers/mru_cache.hpp>

Detailed Description

template<typename Key, typename T>
class genesis::utils::MruCache< Key, T >

Most Recently Used Cache.

The class offers a cache that maps from unique keys of type Key to values of type T, automatically loading elements as needed using the load_function. The cache only keeps a certain number of elements. That is, the elements that were least recently used are removed to avoid exceeding the capacity().

The main functions are fetch() and fetch_copy(), which retrieve an element from the cache, potentially loading it first, and potentially removing old elements. During a fetch, it is possible that one more element is kept in memory than the capacity allows, before removing the oldest one. This is done in order to recover from a load that failed (with an exception) without altering the state of the cache.

In order to use this class, the functor load_function has to be set before calling fetch(), fetch_copy() or touch(). The functor needs to take a const reference to the key type Key and return a mapped type T by value.

Example:

// Path to some data.
std::string dir = "/path/to/data";
// Create a cache from file names to file contents, with a capacity of 5.
MruCache<std::string, std::string> cache{ 5 };
// Our load function is to read the file.
cache.load_function = [ &dir ]( std::string const& file ){
return file_read( dir + "/" + file );
};
// Access an element, that is, load a file into the cache.
auto const& content = cache.fetch( "test.txt" );

Lastly, a second functor release_function can be used to specify a function that is exectued before an element is removed from the cache. If this functor is not set, the element is simply removed without any prior call.

Thread safety: As fetch() returns by reference, it is not thread safe. A fetched element can be removed at any time when other threads invoke fetch() again, leaving to a dangling reference. Thus, for multi-threaded use, fetch_copy() can be used, which is guarded and returns a copy of the elment instead. See there for details.

Definition at line 96 of file mru_cache.hpp.

Public Member Functions

 MruCache ()=default
 Default constructor. Uses a capacity() of 0, that is, limitless. More...
 
 MruCache (size_t capacity)
 Construct a cache with a given capacity. More...
 
 MruCache (MruCache const &)=default
 
 MruCache (MruCache &&)=default
 
 ~MruCache ()
 
iterator begin ()
 Get an iterator to the begin of the cache, that is, the most recently used element. More...
 
const_iterator begin () const
 Get a const iterator to the begin of the cache, that is, the most recently used element. More...
 
size_type capacity () const
 Return the currently set capacity of the cache, i.e., its maximal size. More...
 
void capacity (size_t value)
 Set the capacity of the cache, i.e., its maximal size. More...
 
const_iterator cbegin ()
 Get a const iterator to the begin of the cache, that is, the most recently used element. More...
 
const_iterator cend ()
 Get a const iterator to past-the-end of the cache, that is, one element after the least recently used one. More...
 
void clear ()
 Clear the cache. More...
 
bool contains (key_type const &key)
 Return whether an element is currently in the cache. More...
 
bool empty () const
 Return whether the cache is currently empty, that is, has no elements loaded. More...
 
iterator end ()
 Get an iterator to past-the-end of the cache, that is, one element after the least recently used one. More...
 
const_iterator end () const
 Get a const iterator to past-the-end of the cache, that is, one element after the least recently used one. More...
 
mapped_typefetch (key_type const &key)
 Get an element. More...
 
mapped_type fetch_copy (key_type const &key)
 Get an element by copy. More...
 
MruCacheoperator= (MruCache const &)=default
 
MruCacheoperator= (MruCache &&)=default
 
size_type size () const
 Get the current count of elements being loaded in the cache. More...
 
void touch (key_type const &key)
 Bring an element to the front, and load it if needed. More...
 

Public Types

using const_iterator = typename std::list< value_type >::const_iterator
 
using iterator = typename std::list< value_type >::iterator
 
using key_type = Key
 
using mapped_type = T
 
using size_type = size_t
 
using value_type = std::pair< const key_type, mapped_type >
 

Public Attributes

std::function< mapped_type(key_type
const &)> 
load_function
 Function to load an element into the cache if it is being fetched but not there yet. More...
 
std::function< void(key_type
const &, mapped_type &)> 
release_function
 Function to be called when an element is removed from the cache. More...
 

Constructor & Destructor Documentation

MruCache ( )
default

Default constructor. Uses a capacity() of 0, that is, limitless.

A capacity of 0 means limitless, meaning that no elements are ever removed.

See Also
capacity( size_t value )
MruCache ( size_t  capacity)
inline

Construct a cache with a given capacity.

A capacity of 0 means limitless, meaning that no elements are ever removed.

See Also
capacity( size_t value )

Definition at line 131 of file mru_cache.hpp.

~MruCache ( )
inline

Definition at line 135 of file mru_cache.hpp.

MruCache ( MruCache< Key, T > const &  )
default
MruCache ( MruCache< Key, T > &&  )
default

Member Function Documentation

iterator begin ( )
inline

Get an iterator to the begin of the cache, that is, the most recently used element.

Definition at line 154 of file mru_cache.hpp.

const_iterator begin ( ) const
inline

Get a const iterator to the begin of the cache, that is, the most recently used element.

Definition at line 162 of file mru_cache.hpp.

size_type capacity ( ) const
inline

Return the currently set capacity of the cache, i.e., its maximal size.

A capacity of 0 means limitless, that is, no elements are ever removed.

Definition at line 219 of file mru_cache.hpp.

void capacity ( size_t  value)
inline

Set the capacity of the cache, i.e., its maximal size.

Setting the capacity to 0 means limitless, that is, no elements are ever removed.

Definition at line 413 of file mru_cache.hpp.

const_iterator cbegin ( )
inline

Get a const iterator to the begin of the cache, that is, the most recently used element.

Definition at line 188 of file mru_cache.hpp.

const_iterator cend ( )
inline

Get a const iterator to past-the-end of the cache, that is, one element after the least recently used one.

Definition at line 196 of file mru_cache.hpp.

void clear ( )
inline

Clear the cache.

Definition at line 428 of file mru_cache.hpp.

bool contains ( key_type const &  key)
inline

Return whether an element is currently in the cache.

Thread safety: Safe. But the element might be removed by other threads soon.

Definition at line 383 of file mru_cache.hpp.

bool empty ( ) const
inline

Return whether the cache is currently empty, that is, has no elements loaded.

Definition at line 228 of file mru_cache.hpp.

iterator end ( )
inline

Get an iterator to past-the-end of the cache, that is, one element after the least recently used one.

Definition at line 171 of file mru_cache.hpp.

const_iterator end ( ) const
inline

Get a const iterator to past-the-end of the cache, that is, one element after the least recently used one.

Definition at line 180 of file mru_cache.hpp.

mapped_type& fetch ( key_type const &  key)
inline

Get an element.

This is the main function of the class. It gets an element given its key, either by retrieving it from the cache, or loading it into the cache first, if needed.

If loading an element leads to the capacity of the cache begin exceeded, the least recently used element is removed. The removal is done after loading the new element. This means that the memory usage can be one more element than the capacity() allows. This is done to make sure that an exception thrown when loading the new element does not lead to the cache being altered.

Thread safety: Not thread safe, because it does not use a guard, and because it returns a reference, which can become dangling if other threads fetch new elements, leading to the referenced one being removed. For multi-threaded use, see fetch_copy().

Caveat: Even in single-thread use, a variable storing a reference obtained from fetch() can become dangling, if more new elements are fetched or touched than the capacity allows. Thus, the variable needs to go out of scope before this happens. For example, a loop over keys, fetching an element in the beginning of the loop body and keeping the reference only within the loop body without calling fetch() again, is fine.

Definition at line 259 of file mru_cache.hpp.

mapped_type fetch_copy ( key_type const &  key)
inline

Get an element by copy.

This works exactly the same as fetch(), but is thread safe and returns a copy. See fetch() for details.

Because the loading is not part of the mutex that makes this function thread safe, it is possible to parallely load elements in different threads. However, when two threads need to load an element at the same time, the loading may happen twice. Then, only the first thread that finishes loading stores the element in the cache, while the other one is discarded. This is done in order to allow parallel loading without the hassle of per-element locks.

If the cache is used in a multi-threaded environment and holds large elements, making actual copies might be too expensive. In that case, a neat trick is to store shared pointers to the elements instead:

// Path to some data.
std::string dir = "/path/to/data";
// Create a cache from file names to shared pointers of file contents.
MruCache<std::string, std::shared_ptr<std::string>> cache{ 5 };
// Load elements from file.
cache.load_function = [ &dir ]( std::string const& file ){
return std::make_shared<std::string>( file_read( dir + "/" + file ));
};
// Fetch an element, that is, load a file into the cache.
// Store it by copy, which just copies the shared pointer.
auto content = cache.fetch_copy( "fail2.jtest" );

As the control block of std::shared_ptr is thread safe, these shared pointer copies can stay alive in a thread that still needs the element, even if the element was removed from the cache by other threads in the meantime.

Definition at line 323 of file mru_cache.hpp.

MruCache& operator= ( MruCache< Key, T > const &  )
default
MruCache& operator= ( MruCache< Key, T > &&  )
default
size_type size ( ) const
inline

Get the current count of elements being loaded in the cache.

Definition at line 208 of file mru_cache.hpp.

void touch ( key_type const &  key)
inline

Bring an element to the front, and load it if needed.

The function behaves just like fetch_copy(), but without returning the element. Useful to pre-load the cache.

Be aware however that having touched an element in multi threaded used does not guarantee that it stays in the cache for long. Other threads might have fetched other elements, leading to the removal of the touched one. In that case, it has to be loaded again when fetched later.

Definition at line 399 of file mru_cache.hpp.

Member Typedef Documentation

using const_iterator = typename std::list< value_type >::const_iterator

Definition at line 109 of file mru_cache.hpp.

using iterator = typename std::list< value_type >::iterator

Definition at line 108 of file mru_cache.hpp.

using key_type = Key

Definition at line 104 of file mru_cache.hpp.

using mapped_type = T

Definition at line 105 of file mru_cache.hpp.

using size_type = size_t

Definition at line 111 of file mru_cache.hpp.

using value_type = std::pair<const key_type, mapped_type>

Definition at line 106 of file mru_cache.hpp.

Member Data Documentation

std::function< mapped_type( key_type const& )> load_function

Function to load an element into the cache if it is being fetched but not there yet.

Has to be set before calling fetch(), fetch_copy() or touch(), otherwise an exception is thrown.

Definition at line 509 of file mru_cache.hpp.

std::function< void( key_type const&, mapped_type& )> release_function

Function to be called when an element is removed from the cache.

This function is called whenever elements are removed from the cache, e.g., due to being the least recently used one, due to a call to clear(), or when the destructor is called.

Can be empty. In that case, nothing is called when elements are removed.

Definition at line 519 of file mru_cache.hpp.


The documentation for this class was generated from the following file: