Cache< K, V > Class Template Reference

#include <src/cache.h>

Inheritance diagram for Cache< K, V >:

Public Types
using	kv_pair = std::pair<K,V>
using	iterator = typename std::list<kv_pair>::iterator
using	const_iterator = typename std::list<kv_pair>::const_iterator

Public Member Functions
	Cache (size_t capacity)
	creates a cache that can hold capacity elements
V *	insert (const K &key, V &&value)
	Inserts value under key in the cache.
V *	insert (const K &key, const V &value)
	Inserts value under key in the cache.
void	remove (const K &key)
V *	find (const K &key)
size_t	size () const
	Returns the number of values stored in the cache.
size_t	capacity () const
	Returns the maximum number of values that can be stored in the cache.
uint64_t	hits () const
	Returns how many of the find() calls did find a value in the cache.
uint64_t	misses () const
	Returns how many of the find() calls did not found a value in the cache.
void	clear ()
	Clears all values in the cache.
iterator	begin ()
iterator	end ()
const_iterator	begin () const
const_iterator	end () const

Private Member Functions
void	resize ()

Private Attributes
size_t	m_capacity
std::list< kv_pair >	m_cacheItemList
std::unordered_map< K, iterator >	m_cacheItemMap
uint64_t	m_hits =0
uint64_t	m_misses =0

Detailed Description

template<typename K, typename V>
class Cache< K, V >

Fixed size cache for value type V using keys of type K.

When the maximum capacity has reached, the least recently used value is removed from the cache (LRU strategy).

Definition at line 31 of file cache.h.

Member Typedef Documentation

const_iterator

template<typename K, typename V>

using Cache< K, V >::const_iterator = typename std::list<kv_pair>::const_iterator

Definition at line 36 of file cache.h.

iterator

template<typename K, typename V>

using Cache< K, V >::iterator = typename std::list<kv_pair>::iterator

Definition at line 35 of file cache.h.

kv_pair

template<typename K, typename V>

using Cache< K, V >::kv_pair = std::pair<K,V>

Definition at line 34 of file cache.h.

Constructor & Destructor Documentation

Cache()

template<typename K, typename V>

Cache< K, V >::Cache ( size_t capacity )

inline

creates a cache that can hold capacity elements

Definition at line 39 of file cache.h.

                           : m_capacity(capacity)
    {
    }

References capacity(), and m_capacity.

Member Function Documentation

begin() [1/2]

template<typename K, typename V>

iterator Cache< K, V >::begin ( )

inline

Definition at line 156 of file cache.h.

{ return m_cacheItemList.begin();  }

References m_cacheItemList.

begin() [2/2]

template<typename K, typename V>

const_iterator Cache< K, V >::begin ( ) const

inline

Definition at line 158 of file cache.h.

{ return m_cacheItemList.cbegin(); }

References m_cacheItemList.

capacity()

template<typename K, typename V>

size_t Cache< K, V >::capacity ( ) const

inline

Returns the maximum number of values that can be stored in the cache.

Definition at line 132 of file cache.h.

    {
      return m_capacity;
    }

References m_capacity.

Referenced by Cache().

clear()

template<typename K, typename V>

void Cache< K, V >::clear ( )

inline

Clears all values in the cache.

Definition at line 150 of file cache.h.

    {
      m_cacheItemMap.clear();
      m_cacheItemList.clear();
    }

References m_cacheItemList, and m_cacheItemMap.

end() [1/2]

template<typename K, typename V>

iterator Cache< K, V >::end ( )

inline

Definition at line 157 of file cache.h.

{ return m_cacheItemList.end();    }

References m_cacheItemList.

end() [2/2]

template<typename K, typename V>

const_iterator Cache< K, V >::end ( ) const

inline

Definition at line 159 of file cache.h.

{ return m_cacheItemList.cend();   }

References m_cacheItemList.

find()

template<typename K, typename V>

V * Cache< K, V >::find ( const K & key )

inline

Finds a value in the cache given the corresponding key.

Returns

a pointer to the value or nullptr if the key is not found in the cache

Note

The hit and miss counters are updated, see hits() and misses().

Definition at line 105 of file cache.h.

    {
      auto it = m_cacheItemMap.find(key);
      if (it != m_cacheItemMap.end())
      {
        // move the item to the front of the list
        m_cacheItemList.splice(m_cacheItemList.begin(),
                               m_cacheItemList,
                               it->second);
        m_hits++;
        // return the value
        return &it->second->second;
      }
      else
      {
        m_misses++;
      }
      return nullptr;
    }

References m_cacheItemList, m_cacheItemMap, m_hits, and m_misses.

hits()

template<typename K, typename V>

uint64_t Cache< K, V >::hits ( ) const

inline

Returns how many of the find() calls did find a value in the cache.

Definition at line 138 of file cache.h.

    {
      return m_hits;
    }

References m_hits.

insert() [1/2]

template<typename K, typename V>

V * Cache< K, V >::insert ( const K & key, const V & value )

inline

Inserts value under key in the cache.

Definition at line 67 of file cache.h.

    {
      // reuse item if it already exists
      auto it = m_cacheItemMap.find(key);
      if (it != m_cacheItemMap.end())
      {
        // move the item to the front of the list
        m_cacheItemList.splice(m_cacheItemList.begin(),
                               m_cacheItemList,
                               it->second);
        it->second->second = value;
        return &it->second->second;
      }
      // store new item
      m_cacheItemList.push_front(kv_pair(key,value));
      V *result = &m_cacheItemList.front().second;
      m_cacheItemMap[key] = m_cacheItemList.begin();
      // remove least recently used item if cache is full
      resize();
      return result;
    }

References m_cacheItemList, m_cacheItemMap, and resize().

insert() [2/2]

template<typename K, typename V>

V * Cache< K, V >::insert ( const K & key, V && value )

inline

Inserts value under key in the cache.

Definition at line 44 of file cache.h.

    {
      // reuse item if it already exists
      auto it = m_cacheItemMap.find(key);
      if (it != m_cacheItemMap.end())
      {
        // move the item to the front of the list
        m_cacheItemList.splice(m_cacheItemList.begin(),
                               m_cacheItemList,
                               it->second);
        std::exchange(it->second->second,value);
        return &it->second->second;
      }
      // create new item
      m_cacheItemList.push_front(kv_pair(key,std::move(value)));
      V *result = &m_cacheItemList.front().second;
      m_cacheItemMap[key] = m_cacheItemList.begin();
      // remove least recently used item if cache is full
      resize();
      return result;
    }

References m_cacheItemList, m_cacheItemMap, and resize().

misses()

template<typename K, typename V>

uint64_t Cache< K, V >::misses ( ) const

inline

Returns how many of the find() calls did not found a value in the cache.

Definition at line 144 of file cache.h.

    {
      return m_misses;
    }

References m_misses.

remove()

template<typename K, typename V>

void Cache< K, V >::remove ( const K & key )

inline

Removes entry key from the cache.

Note

this invalidates any iterators

Definition at line 91 of file cache.h.

    {
      // remove item if it already exists
      auto it = m_cacheItemMap.find(key);
      if (it != m_cacheItemMap.end())
      {
        m_cacheItemList.erase(it->second);
        m_cacheItemMap.erase(it);
      }
    }

References m_cacheItemList, and m_cacheItemMap.

resize()

template<typename K, typename V>

void Cache< K, V >::resize ( )

inlineprivate

Definition at line 163 of file cache.h.

    {
      if (m_cacheItemMap.size() > m_capacity)
      {
        auto last_it = m_cacheItemList.end();
        --last_it;
        m_cacheItemMap.erase(last_it->first);
        m_cacheItemList.pop_back();
      }
    }

References m_cacheItemList, m_cacheItemMap, and m_capacity.

Referenced by insert(), and insert().

size()

template<typename K, typename V>

size_t Cache< K, V >::size ( ) const

inline

Returns the number of values stored in the cache.

Definition at line 126 of file cache.h.

    {
      return m_cacheItemMap.size();
    }

References m_cacheItemMap.

Member Data Documentation

m_cacheItemList

template<typename K, typename V>

std::list<kv_pair> Cache< K, V >::m_cacheItemList

private

Definition at line 176 of file cache.h.

Referenced by begin(), begin(), clear(), end(), end(), find(), insert(), insert(), remove(), and resize().

m_cacheItemMap

template<typename K, typename V>

std::unordered_map<K,iterator> Cache< K, V >::m_cacheItemMap

private

Definition at line 178 of file cache.h.

Referenced by clear(), find(), insert(), insert(), remove(), resize(), and size().

m_capacity

template<typename K, typename V>

size_t Cache< K, V >::m_capacity

private

Definition at line 174 of file cache.h.

Referenced by Cache(), capacity(), and resize().

m_hits

template<typename K, typename V>

uint64_t Cache< K, V >::m_hits =0

private

Definition at line 179 of file cache.h.

Referenced by find(), and hits().

m_misses

template<typename K, typename V>

uint64_t Cache< K, V >::m_misses =0

private

Definition at line 180 of file cache.h.

Referenced by find(), and misses().

---

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

• src/cache.h