OmniSciDB  04ee39c94c
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  typedef typename std::pair<key_t, value_t> key_value_pair_t;
19  using cache_list_t = typename std::list<key_value_pair_t>;
20  using list_iterator_t = typename cache_list_t::iterator;
21  typedef typename std::unordered_map<key_t, list_iterator_t, hash_t> map_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(key_t const& 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  private:
63  void putCommon(map_t_iterator& it, key_t const& key) {
64  if (it != cache_items_map_.end()) {
65  cache_items_list_.erase(it->second);
66  cache_items_map_.erase(it);
67  }
68  cache_items_map_[key] = cache_items_list_.begin();
69 
70  if (cache_items_map_.size() > max_size_) {
71  auto last = cache_items_list_.end();
72  last--;
73  cache_items_map_.erase(last->first);
74  cache_items_list_.pop_back();
75  }
76  }
77 
80  size_t max_size_;
81 };
82 
83 #endif // STRINGDICTIONARY_LRUCACHE_HPP
void clear()
Definition: LruCache.hpp:57
std::unordered_map< key_t, list_iterator_t, hash_t > map_t
Definition: LruCache.hpp:21
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:55
map_t cache_items_map_
Definition: LruCache.hpp:79
cache_list_t cache_items_list_
Definition: LruCache.hpp:78
size_t max_size_
Definition: LruCache.hpp:80
std::pair< key_t, value_t > key_value_pair_t
Definition: LruCache.hpp:18
void putCommon(map_t_iterator &it, key_t const &key)
Definition: LruCache.hpp:63
void put(key_t const &key, value_t &&value)
Definition: LruCache.hpp:27