dns_cache/lru_cache.h at master · ilnarb/dns_cache · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#ifndef __LRU_CACHE_H__
#define __LRU_CACHE_H__

#include <list>
#include <unordered_map>

template<
	typename Key,
	typename Value,
	// lets allow to change hasher and equal predicate
	typename Hash = std::hash<Key>,
	typename Pred = std::equal_to<Key>
>
class lru_cache_t
{
public:
	typedef Key key_type;
	typedef Value value_type;
	typedef Hash hasher_type;
	typedef Pred predicate_type;
	typedef typename std::pair<key_type, value_type> pair_type;
	typedef typename std::list<pair_type>::iterator iterator;
	typedef typename std::list<pair_type>::const_iterator const_iterator;
	//
	lru_cache_t(size_t max_size): _max_size(max_size)
	{
	}
	void set(const key_type &key, const value_type &value)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			auto lit = (*it).second;
			// move to the head
			_elements.splice(_elements.begin(), _elements, lit);
			// set new value
			(*lit).second = value;
		}
		else
		{
			displace_if();
			//
			_elements.emplace_front(key, value);
			auto lit = _elements.begin();
			_mapper.insert(std::make_pair(key, lit));
		}
	}
	value_type& operator[](const key_type &key)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			auto lit = (*it).second;
			// move to the head
			_elements.splice(_elements.begin(), _elements, lit);
			//
			return (*lit).second;
		}
		else
		{
			displace_if();
			//
			_elements.emplace_front(key, value_type());
			auto lit = _elements.begin();
			_mapper.insert(std::make_pair(key, lit));
			return (*lit).second;
		}
	}
	bool get(const key_type &key, value_type &value)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			auto lit = (*it).second;
			// move to the head
			_elements.splice(_elements.begin(), _elements, lit);
			value = (*lit).second;
			return true;
		}
		return false;
	}
	bool get(const key_type &key, value_type &value) const
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			auto lit = (*it).second;
			value = (*lit).second;
			return true;
		}
		return false;
	}
	void erase(const key_type &key)
	{
		auto it = _mapper.find(key);
		if (it != _mapper.end())
		{
			auto lit = (*it).second;
			_elements.erase(lit);
			_mapper.erase(it);
		}
	}
	// iterators
	iterator begin()
	{
		return _elements.begin();
	}
	iterator end()
	{
		return _elements.end();
	}
	const_iterator begin() const
	{
		return _elements.begin();
	}
	const_iterator end() const
	{
		return _elements.end();
	}
	//
	size_t size() const
	{
		return _elements.size();
	}
	size_t max_size() const
	{
		return _max_size;
	}
	size_t empty() const
	{
		return _elements.empty();
	}

private:
	bool displace_if()
	{
		if (_elements.size() >= _max_size)
		{
			auto &pair = _elements.back();
			_mapper.erase(pair.first);
			_elements.pop_back();
			return true;
		}
		return false;
	}

private:
	size_t _max_size;
	std::list<pair_type> _elements;
	std::unordered_map<key_type, iterator, hasher_type, predicate_type> _mapper;
};

#endif // __LRU_CACHE_H__