OmniSciDB  dfae7c3b14
LruCache.hpp
Go to the documentation of this file.
1 /*
2  * File: lrucache.hpp
3  * Author: Alexander Ponomarev
4  *
5  * Created on June 20, 2013, 5:09 PM
6  */
7 
8 #ifndef STRINGDICTIONARY_LRUCACHE_HPP
9 #define STRINGDICTIONARY_LRUCACHE_HPP
10 
11 #include <cstddef>
12 #include <list>
13 #include <unordered_map>
14 
15 template <typename key_t, typename value_t, class hash_t = std::hash<key_t>>
16 class LruCache {
17  private:
18  using key_value_pair_t = typename std::pair<key_t, value_t>;
19  using cache_list_t = typename std::list<key_value_pair_t>;
20  using list_iterator_t = typename cache_list_t::iterator;
21  using map_t = typename std::unordered_map<key_t, list_iterator_t, hash_t>;
22  using map_t_iterator = typename map_t::iterator;
23 
24  public:
25  LruCache(const size_t max_size) : max_size_(max_size) {}
26 
27  void put(const key_t& key, value_t&& value) {
28  auto it = cache_items_map_.find(key);
29  cache_items_list_.emplace_front(key, std::forward<value_t&&>(value));
30  putCommon(it, key);
31  }
32 
33  void put(const key_t& key, const value_t& value) {
34  auto it = cache_items_map_.find(key);
35  cache_items_list_.emplace_front(key, std::forward<const value_t&&>(value));
36  putCommon(it, key);
37  }
38 
39  value_t* get(const key_t& key) {
40  auto it = cache_items_map_.find(key);
41  if (it == cache_items_map_.end()) {
42  return nullptr;
43  }
44  cache_items_list_.splice(cache_items_list_.begin(), cache_items_list_, it->second);
45  return &it->second->second;
46  }
47  using const_list_iterator_t = typename cache_list_t::const_iterator;
48 
49  const_list_iterator_t find(const key_t& key) const {
50  auto it = cache_items_map_.find(key);
51  if (it == cache_items_map_.end()) {
52  return cend();
53  } else {
54  return it->second;
55  }
56  }
57 
58  const_list_iterator_t cend() const { return (cache_items_list_.cend()); }
59 
60  void clear() {
61  cache_items_list_.clear();
62  cache_items_map_.clear();
63  }
64 
65  void evictFractionEntries(const float fraction) {
66  size_t entries_to_evict =
67  std::min(std::max(static_cast<size_t>(cache_items_map_.size() * fraction),
68  static_cast<size_t>(1)),
69  cache_items_map_.size());
70  evictCommon(entries_to_evict);
71  }
72 
73  void evictNEntries(const size_t n) {
74  size_t entries_to_evict = std::min(n, cache_items_map_.size());
75  evictCommon(entries_to_evict);
76  }
77 
78  private:
79  void putCommon(map_t_iterator& it, key_t const& key) {
80  if (it != cache_items_map_.end()) {
81  cache_items_list_.erase(it->second);
82  cache_items_map_.erase(it);
83  }
84  cache_items_map_[key] = cache_items_list_.begin();
85 
86  if (cache_items_map_.size() > max_size_) {
87  auto last = cache_items_list_.end();
88  last--;
89  cache_items_map_.erase(last->first);
90  cache_items_list_.pop_back();
91  }
92  }
93 
94  void evictCommon(const size_t entries_to_evict) {
95  auto last = cache_items_list_.end();
96  size_t entries_erased = 0;
97  while (entries_erased < entries_to_evict && last != cache_items_list_.begin()) {
98  last--;
99  cache_items_map_.erase(last->first);
100  last = cache_items_list_.erase(last);
101  entries_erased++;
102  }
103  }
104 
107  size_t max_size_;
108 };
109 
110 #endif // STRINGDICTIONARY_LRUCACHE_HPP
typename std::unordered_map< CodeCacheKey, list_iterator_t, boost::hash< CodeCacheKey > > map_t
Definition: LruCache.hpp:21
void clear()
Definition: LruCache.hpp:60
typename std::pair< CodeCacheKey, CodeCacheValWithModule > key_value_pair_t
Definition: LruCache.hpp:18
void put(const key_t &key, const value_t &value)
Definition: LruCache.hpp:33
const_list_iterator_t find(const key_t &key) const
Definition: LruCache.hpp:49
LruCache(const size_t max_size)
Definition: LruCache.hpp:25
const_list_iterator_t cend() const
Definition: LruCache.hpp:58
map_t cache_items_map_
Definition: LruCache.hpp:106
void evictCommon(const size_t entries_to_evict)
Definition: LruCache.hpp:94
cache_list_t cache_items_list_
Definition: LruCache.hpp:105
void evictFractionEntries(const float fraction)
Definition: LruCache.hpp:65
size_t max_size_
Definition: LruCache.hpp:107
void evictNEntries(const size_t n)
Definition: LruCache.hpp:73
void putCommon(map_t_iterator &it, key_t const &key)
Definition: LruCache.hpp:79
void put(const key_t &key, value_t &&value)
Definition: LruCache.hpp:27