| 1 |
/* |
| 2 |
* SPDX-FileCopyrightText: 2017-2017 CSSlayer <[email protected]> |
| 3 |
* |
| 4 |
* SPDX-License-Identifier: LGPL-2.1-or-later |
| 5 |
* |
| 6 |
*/ |
| 7 |
#ifndef _FCITX_LIBIME_LRU_H_ |
| 8 |
#define _FCITX_LIBIME_LRU_H_ |
| 9 |
|
| 10 |
#include <list> |
| 11 |
#include <unordered_map> |
| 12 |
|
| 13 |
template <typename K, typename V> |
| 14 |
class LRUCache { |
| 15 |
using key_type = K; |
| 16 |
using value_type = V; |
| 17 |
using dict_type = |
| 18 |
std::unordered_map<K, std::pair<V, typename std::list<K>::iterator>>; |
| 19 |
|
| 20 |
public: |
| 21 |
LRUCache(size_t sz = 80) : sz_(sz) {} |
| 22 |
|
| 23 |
size_t size() const { return dict_.size(); } |
| 24 |
|
| 25 |
size_t capacity() const { return sz_; } |
| 26 |
|
| 27 |
bool empty() const { return dict_.empty(); } |
| 28 |
|
| 29 |
bool contains(const key_type &key) { |
| 30 |
return dict_.find(key) != dict_.end(); |
| 31 |
} |
| 32 |
|
| 33 |
template <typename... Args> |
| 34 |
value_type *insert(const key_type &key, Args &&...args) { |
| 35 |
auto iter = dict_.find(key); |
| 36 |
if (iter == dict_.end()) { |
| 37 |
if (size() >= sz_) { |
| 38 |
evict(); |
| 39 |
} |
| 40 |
|
| 41 |
order_.push_front(key); |
| 42 |
auto r = dict_.emplace( |
| 43 |
key, std::make_pair(value_type(std::forward<Args>(args)...), |
| 44 |
order_.begin())); |
| 45 |
return &r.first->second.first; |
| 46 |
} |
| 47 |
return nullptr; |
| 48 |
} |
| 49 |
|
| 50 |
void erase(const key_type &key) { |
| 51 |
auto i = dict_.find(key); |
| 52 |
if (i == dict_.end()) { |
| 53 |
return; |
| 54 |
} |
| 55 |
order_.erase(i->second.second); |
| 56 |
dict_.erase(i); |
| 57 |
} |
| 58 |
|
| 59 |
value_type *find(const key_type &key) { |
| 60 |
// lookup value in the cache |
| 61 |
auto i = dict_.find(key); |
| 62 |
return find_helper(i); |
| 63 |
} |
| 64 |
|
| 65 |
void clear() { |
| 66 |
dict_.clear(); |
| 67 |
order_.clear(); |
| 68 |
} |
| 69 |
|
| 70 |
private: |
| 71 |
void evict() { |
| 72 |
// evict item from the end of most recently used list |
| 73 |
auto i = std::prev(order_.end()); |
| 74 |
dict_.erase(*i); |
| 75 |
order_.erase(i); |
| 76 |
} |
| 77 |
|
| 78 |
value_type *find_helper(typename dict_type::iterator i) { |
| 79 |
if (i == dict_.end()) { |
| 80 |
// value not in cache |
| 81 |
return nullptr; |
| 82 |
} |
| 83 |
|
| 84 |
// return the value, but first update its place in the most |
| 85 |
// recently used list |
| 86 |
auto j = i->second.second; |
| 87 |
if (j != order_.begin()) { |
| 88 |
order_.splice(order_.begin(), order_, j, std::next(j)); |
| 89 |
j = order_.begin(); |
| 90 |
i->second.second = j; |
| 91 |
} |
| 92 |
return &i->second.first; |
| 93 |
} |
| 94 |
dict_type dict_; |
| 95 |
std::list<K> order_; |
| 96 |
size_t sz_; |
| 97 |
}; |
| 98 |
|
| 99 |
#endif // _FCITX_LIBIME_LRU_H_ |