#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)
    {
    }

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.

156{ return m_cacheItemList.begin(); }

Cache::m_cacheItemList

std::list< kv_pair > m_cacheItemList

Definition cache.h:176

◆ begin() [2/2]

template<typename K, typename V>

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

inline

Definition at line 158 of file cache.h.

158{ return m_cacheItemList.cbegin(); }

◆ 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;
    }

Referenced by mergeStatistics().

◆ 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();
    }

◆ end() [1/2]

template<typename K, typename V>

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

inline

Definition at line 157 of file cache.h.

157{ return m_cacheItemList.end(); }

◆ end() [2/2]

template<typename K, typename V>

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

inline

Definition at line 159 of file cache.h.

159{ return m_cacheItemList.cend(); }

◆ 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;
    }

Referenced by SymbolResolver::Private::getResolvedSymbolRec(), and SymbolResolver::Private::getResolvedTypeRec().

◆ 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;
    }

Referenced by mergeStatistics().

◆ 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;
    }

◆ 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;
    }

Referenced by SymbolResolver::Private::getResolvedSymbolRec(), and SymbolResolver::Private::getResolvedTypeRec().

◆ 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;
    }

Referenced by mergeStatistics().

◆ 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);
      }
    }

◆ 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();
      }
    }

Referenced by Cache< std::string, LookupInfo >::insert(), and Cache< std::string, LookupInfo >::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();
    }

Referenced by mergeStatistics().

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.

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

◆ m_capacity

template<typename K, typename V>

size_t Cache< K, V >::m_capacity

private

Definition at line 174 of file cache.h.

◆ m_hits

template<typename K, typename V>

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

private

Definition at line 179 of file cache.h.

◆ m_misses

template<typename K, typename V>

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

private

Definition at line 180 of file cache.h.

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

src/cache.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ kv_pair

Constructor & Destructor Documentation

◆ Cache()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ capacity()

◆ clear()

◆ end() [1/2]

◆ end() [2/2]

◆ find()

◆ hits()

◆ insert() [1/2]

◆ insert() [2/2]

◆ misses()

◆ remove()

◆ resize()

◆ size()

Member Data Documentation

◆ m_cacheItemList

◆ m_cacheItemMap

◆ m_capacity

◆ m_hits

◆ m_misses