OmniSciDB  06b3bd477c
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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  auto val = (it == cache_items_map_.end() ? cend() : it->second);
52  return (val);
53  }
54 
55  const_list_iterator_t cend() const { return (cache_items_list_.cend()); }
56 
57  void clear() {
58  cache_items_list_.clear();
59  cache_items_map_.clear();
60  }
61 
62  void evictFractionEntries(const float fraction) {
63  size_t entries_to_evict =
64  std::min(std::max(static_cast<size_t>(cache_items_map_.size() * fraction),
65  static_cast<size_t>(1)),
66  cache_items_map_.size());
67  evictCommon(entries_to_evict);
68  }
69 
70  void evictNEntries(const size_t n) {
71  size_t entries_to_evict = std::min(n, cache_items_map_.size());
72  evictCommon(entries_to_evict);
73  }
74 
75  private:
76  void putCommon(map_t_iterator& it, key_t const& key) {
77  if (it != cache_items_map_.end()) {
78  cache_items_list_.erase(it->second);
79  cache_items_map_.erase(it);
80  }
81  cache_items_map_[key] = cache_items_list_.begin();
82 
83  if (cache_items_map_.size() > max_size_) {
84  auto last = cache_items_list_.end();
85  last--;
86  cache_items_map_.erase(last->first);
87  cache_items_list_.pop_back();
88  }
89  }
90 
91  void evictCommon(const size_t entries_to_evict) {
92  auto last = cache_items_list_.end();
93  size_t entries_erased = 0;
94  while (entries_erased < entries_to_evict && last != cache_items_list_.begin()) {
95  last--;
96  cache_items_map_.erase(last->first);
97  last = cache_items_list_.erase(last);
98  entries_erased++;
99  }
100  }
101 
104  size_t max_size_;
105 };
106 
107 #endif // STRINGDICTIONARY_LRUCACHE_HPP
typename std::unordered_map< key_t, list_iterator_t, hash_t > map_t
Definition: LruCache.hpp:21
void clear()
Definition: LruCache.hpp:57
typename cache_list_t::iterator list_iterator_t
Definition: LruCache.hpp:20
typename std::pair< key_t, value_t > key_value_pair_t
Definition: LruCache.hpp:18
void put(const key_t &key, const value_t &value)
Definition: LruCache.hpp:33
LruCache(const size_t max_size)
Definition: LruCache.hpp:25
const_list_iterator_t cend() const
Definition: LruCache.hpp:55
map_t cache_items_map_
Definition: LruCache.hpp:103
void evictCommon(const size_t entries_to_evict)
Definition: LruCache.hpp:91
cache_list_t cache_items_list_
Definition: LruCache.hpp:102
void evictFractionEntries(const float fraction)
Definition: LruCache.hpp:62
size_t max_size_
Definition: LruCache.hpp:104
typename map_t::iterator map_t_iterator
Definition: LruCache.hpp:22
typename std::list< key_value_pair_t > cache_list_t
Definition: LruCache.hpp:19
void evictNEntries(const size_t n)
Definition: LruCache.hpp:70
void putCommon(map_t_iterator &it, key_t const &key)
Definition: LruCache.hpp:76
void put(const key_t &key, value_t &&value)
Definition: LruCache.hpp:27
const_list_iterator_t find(const key_t &key) const
Definition: LruCache.hpp:49
typename cache_list_t::const_iterator const_list_iterator_t
Definition: LruCache.hpp:47