-
Notifications
You must be signed in to change notification settings - Fork 4
/
lru.hpp
135 lines (113 loc) · 4.07 KB
/
lru.hpp
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
// A lightweight LRU cache structure for list<T> and map<K,V> containers. Written in C++11
// - rlyeh, zlib/libpng licensed.
#pragma once
#include <map>
#include <list>
#include <typeinfo>
// why list container? ~deque container, where only:
// erase, pop_front, pop_back, clear
// will invalidate the iterators and references to the erased elements.
// @todo:
// split cache class into lru::list and lru::map different classes eventually.
namespace lru {
template<typename K,typename V = K>
class cache : public std::list< std::pair<K,V> > {
const bool equivalent = ( typeid(K).hash_code() == typeid(V).hash_code() );
using list_t = std::list< std::pair<K,V> >;
std::map<K,typename list_t::iterator> map;
size_t limit;
public:
using key_type = K;
using value_type = V;
explicit
cache( const std::initializer_list<K> &&list = {} ) : list_t(), limit( list.size() ) {
std::list<K> inv( list );
for( auto it = inv.rbegin(), end = inv.rend(); it != end; ++it ) { // @todo: std::rbegin(list) (c++14)
insert( *it );
}
}
cache( const std::initializer_list<std::pair<K,V>> &&list ) : list_t(), limit( list.size() ) {
std::list<std::pair<K,V>> inv( list );
for( auto it = inv.rbegin(), end = inv.rend(); it != end; ++it ) { // @todo: std::rbegin(list) (c++14)
insert( it->first, it->second );
}
}
void resize( size_t nth ) {
list_t &list = *this;
limit = nth;
while( list.size() > limit ) {
map.erase( list.back().first );
list.pop_back();
}
}
typename list_t::iterator find( const K &k ) {
// if not found return end() list iterator
auto found = map.find( k );
if( found == map.end() ) {
return this->end();
}
// if found reinsert (promote to top) and return it
auto copy = found->second->second;
insert( k, copy );
return this->begin();
}
typename list_t::iterator insert( const K &k, const V &v ) {
list_t &list = *this;
auto found = map.find(k);
if( found == map.end() ) {
list.push_front({k,v});
map.insert( {k,list.begin()} );
found = map.find(k);
if( list.size() > limit ) {
map.erase( list.back().first );
list.pop_back();
}
} else {
list.erase(found->second);
list.push_front({k,v});
found->second = list.begin();
}
return found->second;
}
typename list_t::iterator insert( const V &v ) {
return insert( K(v), v );
}
void erase( const K &k ) {
list_t &list = *this;
auto found = map.find(k);
if( found != map.end() ) {
list.erase(found->second);
map.erase(found);
}
}
V &operator[]( const K &k ) {
// if found, return it (~promoted), else insert it
auto found = find(k);
if( found == this->end() ) {
return insert(k)->second;
} else {
return found->second;
}
}
const V &operator[]( const K &k ) const {
return find(k)->second;
}
template<typename ostream>
friend inline ostream &operator <<( ostream &os, const cache &self ) {
if( self.equivalent ) {
for( auto &in : self ) {
os << in.first << " ";
}
} else {
for( auto &in : self ) {
os << in.first << ":" << in.second << " ";
}
}
return os;
}
};
template<typename T>
using list = cache<T>;
template<typename K, typename V>
using map = cache<K, V>;
}