LruCache< key_t, value_t, hash_t > Class Template Reference

#include <LruCache.h>

Public Types
using	const_list_iterator_t = typename cache_list_t::const_iterator

Public Member Functions
	LruCache (EvictionMetricType eviction_metric_type, const size_t max_size)
size_t	put (const key_t &key, value_t &&value)
size_t	put (const key_t &key, const value_t &value)
void	erase (const key_t &key)
value_t *	get (const key_t &key)
const_list_iterator_t	find (const key_t &key) const
const_list_iterator_t	cbegin () const
const_list_iterator_t	cend () const
void	clear ()
size_t	computeNumEntriesToEvict (const float fraction)
size_t	evictNEntries (const size_t n)
size_t	size () const

Private Types
using	key_value_pair_t = typename std::pair< key_t, value_t >
using	cache_list_t = typename std::list< key_value_pair_t >
using	list_iterator_t = typename cache_list_t::iterator
using	map_t = typename std::unordered_map< key_t, list_iterator_t, hash_t >
using	map_t_iterator = typename map_t::iterator

Private Member Functions
size_t	putCommon (map_t_iterator &it, key_t const &key)
size_t	evictCommon (const size_t entries_to_evict)
size_t	getValueSize (const value_t &value)
size_t	getValueSize (const list_iterator_t &it)

Private Attributes
cache_list_t	cache_items_list_
map_t	cache_items_map_
EvictionMetricType	eviction_metric_type_
size_t	max_size_
size_t	total_byte_size_

Detailed Description

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>
class LruCache< key_t, value_t, hash_t >

Definition at line 25 of file LruCache.h.

Member Typedef Documentation

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

using LruCache< key_t, value_t, hash_t >::cache_list_t = typename std::list<key_value_pair_t>

private

Definition at line 28 of file LruCache.h.

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

using LruCache< key_t, value_t, hash_t >::const_list_iterator_t = typename cache_list_t::const_iterator

Definition at line 70 of file LruCache.h.

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

using LruCache< key_t, value_t, hash_t >::key_value_pair_t = typename std::pair<key_t, value_t>

private

Definition at line 27 of file LruCache.h.

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

using LruCache< key_t, value_t, hash_t >::list_iterator_t = typename cache_list_t::iterator

private

Definition at line 29 of file LruCache.h.

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

using LruCache< key_t, value_t, hash_t >::map_t = typename std::unordered_map<key_t, list_iterator_t, hash_t>

private

Definition at line 30 of file LruCache.h.

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

using LruCache< key_t, value_t, hash_t >::map_t_iterator = typename map_t::iterator

private

Definition at line 31 of file LruCache.h.

Constructor & Destructor Documentation

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

LruCache< key_t, value_t, hash_t >::LruCache ( EvictionMetricType  eviction_metric_type, const size_t  max_size  )

inline

Definition at line 34 of file LruCache.h.

      : eviction_metric_type_(eviction_metric_type)
      , max_size_(max_size)
      , total_byte_size_(0) {}

Member Function Documentation

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

const_list_iterator_t LruCache< key_t, value_t, hash_t >::cbegin ( ) const

inline

Definition at line 81 of file LruCache.h.

{ return (cache_items_list_.cbegin()); }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

const_list_iterator_t LruCache< key_t, value_t, hash_t >::cend ( ) const

inline

Definition at line 83 of file LruCache.h.

Referenced by LruCache< CompilationContext >::find().

{ return (cache_items_list_.cend()); }

Here is the caller graph for this function:

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

void LruCache< key_t, value_t, hash_t >::clear ( )

inline

Definition at line 85 of file LruCache.h.

               {
    cache_items_list_.clear();
    cache_items_map_.clear();
    total_byte_size_ = 0;
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::computeNumEntriesToEvict ( const float  fraction )

inline

Definition at line 91 of file LruCache.h.

                                                        {
    return std::min(
        std::min(std::max(static_cast<size_t>(cache_items_map_.size() * fraction),
                          static_cast<size_t>(1)),
                 cache_items_map_.size()),
        cache_items_map_.size());
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

void LruCache< key_t, value_t, hash_t >::erase ( const key_t &  key )

inline

Definition at line 53 of file LruCache.h.

                               {
    auto it = cache_items_map_.find(key);
    if (it != cache_items_map_.end()) {
      total_byte_size_ -= getValueSize(it->second);
      cache_items_list_.erase(it->second);
      cache_items_map_.erase(it);
    }
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::evictCommon ( const size_t  entries_to_evict )

inlineprivate

Definition at line 133 of file LruCache.h.

Referenced by LruCache< CompilationContext >::evictNEntries().

                                                    {
    auto last = cache_items_list_.end();
    size_t entries_erased = 0;
    while (entries_erased < entries_to_evict && last != cache_items_list_.begin()) {
      last--;
      total_byte_size_ -= getValueSize(last->second);
      cache_items_map_.erase(last->first);
      last = cache_items_list_.erase(last);
      entries_erased++;
    }
    return entries_erased;
  }

Here is the caller graph for this function:

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::evictNEntries ( const size_t  n )

inline

Definition at line 99 of file LruCache.h.

{ return evictCommon(n); }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

const_list_iterator_t LruCache< key_t, value_t, hash_t >::find ( const key_t &  key ) const

inline

Definition at line 72 of file LruCache.h.

                                                     {
    auto it = cache_items_map_.find(key);
    if (it == cache_items_map_.end()) {
      return cend();
    } else {
      return it->second;
    }
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

value_t* LruCache< key_t, value_t, hash_t >::get ( const key_t &  key )

inline

Definition at line 62 of file LruCache.h.

                                 {
    auto it = cache_items_map_.find(key);
    if (it == cache_items_map_.end()) {
      return nullptr;
    }
    cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, it->second);
    return &it->second->second;
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::getValueSize ( const value_t &  value )

inlineprivate

Definition at line 146 of file LruCache.h.

Referenced by LruCache< CompilationContext >::erase(), LruCache< CompilationContext >::evictCommon(), LruCache< CompilationContext >::put(), and LruCache< CompilationContext >::putCommon().

                                            {
    if constexpr (std::is_pointer_v<value_t> || is_shared_ptr<value_t>::value) {
      // 'value == nullptr' represents a call from the `get_or_wait` function
      return value ? value->size() : 0;
    } else {
      return value.size();
    }
  }

Here is the caller graph for this function:

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::getValueSize ( const list_iterator_t &  it )

inlineprivate

Definition at line 155 of file LruCache.h.

Referenced by LruCache< CompilationContext >::getValueSize().

{ return getValueSize(it->second); }

Here is the caller graph for this function:

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::put ( const key_t &  key, value_t &&  value  )

inline

Definition at line 39 of file LruCache.h.

                                                {
    total_byte_size_ += getValueSize(value);
    auto it = cache_items_map_.find(key);
    cache_items_list_.emplace_front(key, std::forward<value_t&&>(value));
    return putCommon(it, key);
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::put ( const key_t &  key, const value_t &  value  )

inline

Definition at line 46 of file LruCache.h.

                                                     {
    total_byte_size_ += getValueSize(value);
    auto it = cache_items_map_.find(key);
    cache_items_list_.emplace_front(key, std::forward<const value_t&&>(value));
    return putCommon(it, key);
  }

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::putCommon ( map_t_iterator &  it, key_t const &  key  )

inlineprivate

Definition at line 108 of file LruCache.h.

Referenced by LruCache< CompilationContext >::put().

                                                         {
    size_t entries_erased = 0;
    if (it != cache_items_map_.end()) {
      total_byte_size_ -= getValueSize(it->second);
      cache_items_list_.erase(it->second);
      cache_items_map_.erase(it);
      entries_erased++;
    }
    cache_items_map_[key] = cache_items_list_.begin();

    while ((eviction_metric_type_ == EvictionMetricType::EntryCount &&
            cache_items_map_.size() > max_size_) ||
           (eviction_metric_type_ == EvictionMetricType::ByteSize &&
            total_byte_size_ > max_size_)) {
      auto last = cache_items_list_.end();
      last--;
      auto target_it = cache_items_map_.find(last->first);
      total_byte_size_ -= getValueSize(target_it->second);
      cache_items_map_.erase(target_it);
      cache_items_list_.pop_back();
      entries_erased++;
    }
    return entries_erased;
  }

Here is the caller graph for this function:

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::size ( ) const

inline

Definition at line 101 of file LruCache.h.

                      {
    return eviction_metric_type_ == EvictionMetricType::EntryCount
               ? cache_items_list_.size()
               : total_byte_size_;
  }

Member Data Documentation

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

cache_list_t LruCache< key_t, value_t, hash_t >::cache_items_list_

private

Definition at line 157 of file LruCache.h.

Referenced by LruCache< CompilationContext >::cbegin(), LruCache< CompilationContext >::cend(), LruCache< CompilationContext >::clear(), LruCache< CompilationContext >::erase(), LruCache< CompilationContext >::evictCommon(), LruCache< CompilationContext >::get(), LruCache< CompilationContext >::put(), LruCache< CompilationContext >::putCommon(), and LruCache< CompilationContext >::size().

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

map_t LruCache< key_t, value_t, hash_t >::cache_items_map_

private

Definition at line 158 of file LruCache.h.

Referenced by LruCache< CompilationContext >::clear(), LruCache< CompilationContext >::computeNumEntriesToEvict(), LruCache< CompilationContext >::erase(), LruCache< CompilationContext >::evictCommon(), LruCache< CompilationContext >::find(), LruCache< CompilationContext >::get(), LruCache< CompilationContext >::put(), and LruCache< CompilationContext >::putCommon().

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

EvictionMetricType LruCache< key_t, value_t, hash_t >::eviction_metric_type_

private

Definition at line 159 of file LruCache.h.

Referenced by LruCache< CompilationContext >::putCommon(), and LruCache< CompilationContext >::size().

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::max_size_

private

Definition at line 160 of file LruCache.h.

Referenced by LruCache< CompilationContext >::putCommon().

template<typename key_t, typename value_t, class hash_t = std::hash<key_t>>

size_t LruCache< key_t, value_t, hash_t >::total_byte_size_

private

Definition at line 161 of file LruCache.h.

Referenced by LruCache< CompilationContext >::clear(), LruCache< CompilationContext >::erase(), LruCache< CompilationContext >::evictCommon(), LruCache< CompilationContext >::put(), LruCache< CompilationContext >::putCommon(), and LruCache< CompilationContext >::size().

---

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

• /home/jenkins-slave/workspace/core-os-doxygen/Shared/LruCache.h