OmniSciDB  72c90bc290
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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.

35  : eviction_metric_type_(eviction_metric_type)
36  , max_size_(max_size)
37  , total_byte_size_(0) {}
EvictionMetricType eviction_metric_type_
Definition: LruCache.h:159
size_t max_size_
Definition: LruCache.h:160
size_t total_byte_size_
Definition: LruCache.h:161

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.

81 { return (cache_items_list_.cbegin()); }
cache_list_t cache_items_list_
Definition: LruCache.h:157
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().

83 { return (cache_items_list_.cend()); }
cache_list_t cache_items_list_
Definition: LruCache.h:157

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

85  {
86  cache_items_list_.clear();
87  cache_items_map_.clear();
88  total_byte_size_ = 0;
89  }
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
size_t total_byte_size_
Definition: LruCache.h:161
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.

91  {
92  return std::min(
93  std::min(std::max(static_cast<size_t>(cache_items_map_.size() * fraction),
94  static_cast<size_t>(1)),
95  cache_items_map_.size()),
96  cache_items_map_.size());
97  }
map_t cache_items_map_
Definition: LruCache.h:158
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.

53  {
54  auto it = cache_items_map_.find(key);
55  if (it != cache_items_map_.end()) {
56  total_byte_size_ -= getValueSize(it->second);
57  cache_items_list_.erase(it->second);
58  cache_items_map_.erase(it);
59  }
60  }
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
size_t total_byte_size_
Definition: LruCache.h:161
size_t getValueSize(const value_t &value)
Definition: LruCache.h:146
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().

133  {
134  auto last = cache_items_list_.end();
135  size_t entries_erased = 0;
136  while (entries_erased < entries_to_evict && last != cache_items_list_.begin()) {
137  last--;
138  total_byte_size_ -= getValueSize(last->second);
139  cache_items_map_.erase(last->first);
140  last = cache_items_list_.erase(last);
141  entries_erased++;
142  }
143  return entries_erased;
144  }
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
size_t total_byte_size_
Definition: LruCache.h:161
size_t getValueSize(const value_t &value)
Definition: LruCache.h:146

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

99 { return evictCommon(n); }
size_t evictCommon(const size_t entries_to_evict)
Definition: LruCache.h:133
constexpr double n
Definition: Utm.h:38
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.

72  {
73  auto it = cache_items_map_.find(key);
74  if (it == cache_items_map_.end()) {
75  return cend();
76  } else {
77  return it->second;
78  }
79  }
const_list_iterator_t cend() const
Definition: LruCache.h:83
map_t cache_items_map_
Definition: LruCache.h:158
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.

62  {
63  auto it = cache_items_map_.find(key);
64  if (it == cache_items_map_.end()) {
65  return nullptr;
66  }
67  cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, it->second);
68  return &it->second->second;
69  }
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
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().

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

+ 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().

155 { return getValueSize(it->second); }
size_t getValueSize(const value_t &value)
Definition: LruCache.h:146

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

39  {
41  auto it = cache_items_map_.find(key);
42  cache_items_list_.emplace_front(key, std::forward<value_t&&>(value));
43  return putCommon(it, key);
44  }
size_t putCommon(map_t_iterator &it, key_t const &key)
Definition: LruCache.h:108
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
size_t total_byte_size_
Definition: LruCache.h:161
size_t getValueSize(const value_t &value)
Definition: LruCache.h:146
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.

46  {
48  auto it = cache_items_map_.find(key);
49  cache_items_list_.emplace_front(key, std::forward<const value_t&&>(value));
50  return putCommon(it, key);
51  }
size_t putCommon(map_t_iterator &it, key_t const &key)
Definition: LruCache.h:108
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
size_t total_byte_size_
Definition: LruCache.h:161
size_t getValueSize(const value_t &value)
Definition: LruCache.h:146
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().

108  {
109  size_t entries_erased = 0;
110  if (it != cache_items_map_.end()) {
111  total_byte_size_ -= getValueSize(it->second);
112  cache_items_list_.erase(it->second);
113  cache_items_map_.erase(it);
114  entries_erased++;
115  }
116  cache_items_map_[key] = cache_items_list_.begin();
117 
119  cache_items_map_.size() > max_size_) ||
122  auto last = cache_items_list_.end();
123  last--;
124  auto target_it = cache_items_map_.find(last->first);
125  total_byte_size_ -= getValueSize(target_it->second);
126  cache_items_map_.erase(target_it);
127  cache_items_list_.pop_back();
128  entries_erased++;
129  }
130  return entries_erased;
131  }
map_t cache_items_map_
Definition: LruCache.h:158
cache_list_t cache_items_list_
Definition: LruCache.h:157
EvictionMetricType eviction_metric_type_
Definition: LruCache.h:159
size_t max_size_
Definition: LruCache.h:160
size_t total_byte_size_
Definition: LruCache.h:161
size_t getValueSize(const value_t &value)
Definition: LruCache.h:146

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

101  {
103  ? cache_items_list_.size()
105  }
cache_list_t cache_items_list_
Definition: LruCache.h:157
EvictionMetricType eviction_metric_type_
Definition: LruCache.h:159
size_t total_byte_size_
Definition: LruCache.h:161

Member Data Documentation

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

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