1 /*
2  * File:   lrucache.hpp
3  * Author: Alexander Ponomarev
4  *
5  * Created on June 20, 2013, 5:09 PM
6  */
7 
8 #ifndef _LRUCACHE_HPP_INCLUDED_
9 #define	_LRUCACHE_HPP_INCLUDED_
10 
11 #include <map>
12 #include <list>
13 #include <cstddef>
14 #include <stdexcept>
15 
16 #include "optional.hpp"
17 
18 namespace cache {
19 
20 template<typename key_t, typename value_t>
21 class lru_cache {
22 public:
23 	typedef typename std::pair<key_t, value_t> key_value_pair_t;
24 	typedef typename std::list<key_value_pair_t>::iterator list_iterator_t;
25 
lru_cache(size_t max_size)26 	lru_cache(size_t max_size) :
27 		_max_size(max_size) {
28 	}
29 
put(const key_t & key,const value_t & value)30 	void put(const key_t& key, const value_t& value) {
31 		auto it = _cache_items_map.find(key);
32 		_cache_items_list.push_front(key_value_pair_t(key, value));
33 		if (it != _cache_items_map.end()) {
34 			_cache_items_list.erase(it->second);
35 			_cache_items_map.erase(it);
36 		}
37 		_cache_items_map[key] = _cache_items_list.begin();
38 
39 		if (_cache_items_map.size() > _max_size) {
40 			auto last = _cache_items_list.end();
41 			last--;
42 			_cache_items_map.erase(last->first);
43 			_cache_items_list.pop_back();
44 		}
45 	}
46 
get(const key_t & key)47 	nonstd::optional<value_t> get(const key_t& key) {
48 		auto it = _cache_items_map.find(key);
49 		if (it == _cache_items_map.end()) {
50 			return nonstd::nullopt;
51 		}
52 
53 		_cache_items_list.splice(_cache_items_list.begin(), _cache_items_list, it->second);
54         return it->second->second;
55 	}
56 
exists(const key_t & key) const57 	bool exists(const key_t& key) const {
58 		return _cache_items_map.find(key) != _cache_items_map.end();
59 	}
60 
size() const61 	size_t size() const {
62 		return _cache_items_map.size();
63 	}
64 
set_max_size(size_t max_size)65 	void set_max_size(size_t max_size) {
66 	    this->_max_size = max_size;
67 	}
68 
clear()69 	void clear() {
70 	    this->_cache_items_map.clear();
71 	    this->_cache_items_list.clear();
72 	}
73 
74 private:
75 	std::list<key_value_pair_t> _cache_items_list;
76 	std::map<key_t, list_iterator_t> _cache_items_map;
77 	size_t _max_size;
78 };
79 
80 } // namespace cache
81 
82 #endif	/* _LRUCACHE_HPP_INCLUDED_ */
83 
84