Apollo 10.0
自动驾驶开放平台
lru_cache.h
浏览该文件的文档.
1/******************************************************************************
2 * Copyright 2017 The Apollo Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 *****************************************************************************/
16
17#pragma once
18
19#include <iostream>
20#include <map>
21#include <mutex>
22#include <utility>
23#include <vector>
24
25namespace apollo {
26namespace common {
27namespace util {
28
29template <class K, class V>
30struct Node {
31 K key;
32 V val;
35 Node() : prev(nullptr), next(nullptr) {}
36
37 template <typename VV>
38 Node(const K& key, VV&& val)
39 : key(key), val(std::forward<VV>(val)), prev(nullptr), next(nullptr) {}
40};
41
42template <class K, class V>
43class LRUCache {
44 public:
45 explicit LRUCache(const size_t capacity = kDefaultCapacity)
46 : capacity_(capacity), head_(), tail_() {
47 Init();
48 }
49
51
52 void GetCache(std::map<K, V>* cache) {
53 for (auto it = map_.begin(); it != map_.end(); ++it) {
54 cache->emplace(it->first, it->second.val);
55 }
56 }
57
58 V& operator[](const K& key) {
59 if (!Contains(key)) {
60 K obsolete;
61 GetObsolete(&obsolete);
62 }
63 return map_[key].val;
64 }
65
66 /*
67 * Silently get all as vector
68 */
69 void GetAllSilently(std::vector<V*>* ret) {
70 for (auto it = map_.begin(); it != map_.end(); ++it) {
71 ret->push_back(&it->second.val);
72 }
73 }
74
75 /*
76 * for both add & update purposes
77 */
78 template <typename VV>
79 bool Put(const K& key, VV&& val) {
80 K tmp;
81 return Update(key, std::forward<VV>(val), &tmp, false, false);
82 }
83
84 /*
85 * update existing elements only
86 */
87 template <typename VV>
88 bool Update(const K& key, VV&& val) {
89 if (!Contains(key)) {
90 return false;
91 }
92 K tmp;
93 return Update(key, std::forward<VV>(val), &tmp, true, false);
94 }
95
96 /*
97 * silently update existing elements only
98 */
99 template <typename VV>
100 bool UpdateSilently(const K& key, VV* val) {
101 if (!Contains(key)) {
102 return false;
103 }
104 K tmp;
105 return Update(key, std::forward<VV>(*val), &tmp, true, true);
106 }
107
108 /*
109 * add new elements only
110 */
111 template <typename VV>
112 bool Add(const K& key, VV* val) {
113 K tmp;
114 return Update(key, std::forward<VV>(*val), &tmp, true, false);
115 }
116
117 template <typename VV>
118 bool PutAndGetObsolete(const K& key, VV* val, K* obs) {
119 return Update(key, std::forward<VV>(*val), obs, false, false);
120 }
121
122 template <typename VV>
123 bool AddAndGetObsolete(const K& key, VV* val, K* obs) {
124 return Update(key, std::forward<VV>(*val), obs, true, false);
125 }
126
127 V* GetSilently(const K& key) { return Get(key, true); }
128
129 V* Get(const K& key) { return Get(key, false); }
130
131 bool GetCopySilently(const K& key, V* const val) {
132 return GetCopy(key, val, true);
133 }
134
135 bool GetCopy(const K& key, V* const val) { return GetCopy(key, val, false); }
136
137 size_t size() { return size_; }
138
139 bool Full() { return size() > 0 && size() >= capacity_; }
140
141 bool Empty() { return size() == 0; }
142
143 size_t capacity() { return capacity_; }
144
146 if (size()) {
147 return head_.next;
148 }
149 return nullptr;
150 }
151
153 if (size()) {
154 return tail_.prev;
155 }
156 return nullptr;
157 }
158
159 bool Contains(const K& key) { return map_.find(key) != map_.end(); }
160
161 bool Prioritize(const K& key) {
162 if (Contains(key)) {
163 auto* node = &map_[key];
164 Detach(node);
165 Attach(node);
166 return true;
167 }
168 return false;
169 }
170
171 void Clear() {
172 map_.clear();
173 Init();
174 }
175
176 bool Remove(const K& key) {
177 if (!Contains(key)) {
178 return false;
179 }
180 auto* node = &map_[key];
181 Detach(node);
182 return true;
183 }
184
185 bool ChangeCapacity(const size_t capacity) {
186 if (size() > capacity) {
187 return false;
188 }
189 capacity_ = capacity;
190 return true;
191 }
192
193 private:
194 static constexpr size_t kDefaultCapacity = 10;
195
196 const size_t capacity_;
197 size_t size_;
198 std::map<K, Node<K, V>> map_;
199 Node<K, V> head_;
200 Node<K, V> tail_;
201
202 void Init() {
203 head_.prev = nullptr;
204 head_.next = &tail_;
205 tail_.prev = &head_;
206 tail_.next = nullptr;
207 size_ = 0;
208 map_.clear();
209 }
210
211 void Detach(Node<K, V>* node) {
212 if (node->prev != nullptr) {
213 node->prev->next = node->next;
214 }
215 if (node->next != nullptr) {
216 node->next->prev = node->prev;
217 }
218 node->prev = nullptr;
219 node->next = nullptr;
220 --size_;
221 }
222
223 void Attach(Node<K, V>* node) {
224 node->prev = &head_;
225 node->next = head_.next;
226 head_.next = node;
227 if (node->next != nullptr) {
228 node->next->prev = node;
229 }
230 ++size_;
231 }
232
233 template <typename VV>
234 bool Update(const K& key, VV&& val, K* obs, bool add_only,
235 bool silent_update) {
236 if (obs == nullptr) {
237 return false;
238 }
239 if (Contains(key)) {
240 if (!add_only) {
241 map_[key].val = std::forward<VV>(val);
242 if (!silent_update) {
243 auto* node = &map_[key];
244 Detach(node);
245 Attach(node);
246 } else {
247 return false;
248 }
249 }
250 } else {
251 if (Full() && !GetObsolete(obs)) {
252 return false;
253 }
254
255 map_.emplace(key, Node<K, V>(key, std::forward<VV>(val)));
256 Attach(&map_[key]);
257 }
258 return true;
259 }
260
261 V* Get(const K& key, bool silent) {
262 if (Contains(key)) {
263 auto* node = &map_[key];
264 if (!silent) {
265 Detach(node);
266 Attach(node);
267 }
268 return &node->val;
269 }
270 return nullptr;
271 }
272
273 bool GetCopy(const K& key, V* const val, bool silent) {
274 if (Contains(key)) {
275 auto* node = &map_[key];
276 if (!silent) {
277 Detach(node);
278 Attach(node);
279 }
280 *val = node->val;
281 return true;
282 }
283 return false;
284 }
285
286 bool GetObsolete(K* key) {
287 if (Full()) {
288 auto* node = tail_.prev;
289 Detach(node);
290 *key = node->key;
291 map_.erase(node->key);
292 return true;
293 }
294 return false;
295 }
296};
297
298} // namespace util
299} // namespace common
300} // namespace apollo
Definition node.h:31
bool UpdateSilently(const K &key, VV *val)
Definition lru_cache.h:100
bool ChangeCapacity(const size_t capacity)
Definition lru_cache.h:185
bool Put(const K &key, VV &&val)
Definition lru_cache.h:79
V & operator[](const K &key)
Definition lru_cache.h:58
bool GetCopySilently(const K &key, V *const val)
Definition lru_cache.h:131
bool Add(const K &key, VV *val)
Definition lru_cache.h:112
bool GetCopy(const K &key, V *const val)
Definition lru_cache.h:135
void GetCache(std::map< K, V > *cache)
Definition lru_cache.h:52
bool AddAndGetObsolete(const K &key, VV *val, K *obs)
Definition lru_cache.h:123
bool Update(const K &key, VV &&val)
Definition lru_cache.h:88
void GetAllSilently(std::vector< V * > *ret)
Definition lru_cache.h:69
bool Contains(const K &key)
Definition lru_cache.h:159
bool Remove(const K &key)
Definition lru_cache.h:176
V * GetSilently(const K &key)
Definition lru_cache.h:127
bool Prioritize(const K &key)
Definition lru_cache.h:161
bool PutAndGetObsolete(const K &key, VV *val, K *obs)
Definition lru_cache.h:118
LRUCache(const size_t capacity=kDefaultCapacity)
Definition lru_cache.h:45
class register implement
Definition arena_queue.h:37
Definition future.h:29
Node(const K &key, VV &&val)
Definition lru_cache.h:38