Debian Codegraph @

modules/cloudpinyin/lrucache.h

raw
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_