YSTest: cache.hpp 源文件

YSTest PreAlpha_b800_20170810 The YSLib Test Project

- 首页
- 相关页面
- 模块
- 命名空间
- 类
- 文件

- 文件列表
- 文件成员

cache.hpp
浏览该文件的文档.
1 /*
2 © 2013-2016 FrankHB.
3
4 This file is part of the YSLib project, and may only be used,
5 modified, and distributed under the terms of the YSLib project
6 license, LICENSE.TXT. By continuing to use, modify, or distribute
7 this file you indicate that you have read the license and
8 understand and accept it fully.
9 */
10
28 #ifndef YB_INC_ystdex_cache_hpp_
29 #define YB_INC_ystdex_cache_hpp_ 1
30
31 #include "deref_op.hpp" // for std::pair, is_undereferenceable;
32 #include "cassert.h" // for yassume;
33 #include "type_op.hpp" // for are_same;
34 #include <list> // for std::list;
35 #include <unordered_map> // for std::unordered_map;
36 #include <map> // for std::map;
37 #include <stdexcept> // for std::runtime_error;
38
39 namespace ystdex
40 {
41
43
44
48 template<typename _tKey, typename _tMapped,
49 class _tAlloc = std::allocator<std::pair<const _tKey, _tMapped>>>
50 class recent_used_list : private std::list<std::pair<const _tKey, _tMapped>>
51 {
52 public:
53 using allocator_type = _tAlloc;
54 using value_type = std::pair<const _tKey, _tMapped>;
55 using list_type = std::list<value_type>;
56 using size_type = typename list_type::size_type;
57 using const_iterator = typename list_type::const_iterator;
58 using iterator = typename list_type::iterator;
59
60 using list_type::begin;
61
62 using list_type::cbegin;
63
64 using list_type::cend;
65
66 using list_type::clear;
67
68 template<typename... _tParams>
69 iterator
70 emplace(_tParams&&... args)
71 {
72 list_type::emplace_front(yforward(args)...);
73 return begin();
74 }
75
76 using list_type::empty;
77
78 using list_type::end;
79
80 using list_type::front;
81
82 iterator
83 refresh(iterator i) ynothrowv
84 {
85 list_type::splice(begin(), *this, i);
86 return i;
87 }
88
89 template<typename _tMap>
90 void
91 shrink(_tMap& m) ynothrowv
92 {
93 yassume(!empty());
94
95 auto& val(list_type::back());
96
97 m.erase(val.first);
98 list_type::pop_back();
99 }
100 template<typename _tMap, typename _func>
101 void
102 shrink(_tMap& m, _func f)
103 {
104 yassume(!empty());
105
106 auto& val(list_type::back());
107
108 if(f)
109 f(val);
110 m.erase(val.first);
111 list_type::pop_back();
112 }
113 template<typename _tMap, typename... _tParams>
114 void
115 shrink(_tMap& m, size_type max_use, _tParams&&... args)
116 {
117 while(max_use < size_type(m.size()))
118 {
119 yassume(!m.empty());
120
121 shrink(m, yforward(args)...);
122 }
123 }
124
125 void
126 undo_emplace() ynothrow
127 {
128 yassume(!empty());
129
130 list_type::pop_front();
131 }
132 };
133
134
136
137 template<typename _tKey, typename _tMapped, typename _fHash = std::hash<_tKey>,
138 class _tAlloc = std::allocator<std::pair<const _tKey, _tMapped>>,
139 class _tList = recent_used_list<_tKey, _tMapped, _tAlloc>>
140 struct used_list_cache_traits
141 {
142 using map_type = std::unordered_map<_tKey, _tMapped, _fHash,
143 std::equal_to<_tKey>, _tAlloc>;
144 using used_list_type = _tList;
145 using used_cache_type = std::unordered_map<_tKey, typename _tList::iterator,
146 _fHash, typename map_type::key_equal, typename _tAlloc::template
147 rebind<std::pair<const _tKey, typename _tList::iterator>>::other>;
148 };
149
150 template<typename _tKey, typename _tMapped, class _tAlloc, class _tList>
151 struct used_list_cache_traits<_tKey, _tMapped, void, _tAlloc, _tList>
152 {
153 using map_type = std::map<_tKey, _tMapped, std::less<_tKey>, _tAlloc>;
154 using used_list_type = _tList;
155 using used_cache_type = std::map<_tKey, typename _tList::iterator,
156 typename map_type::key_compare, typename _tAlloc::template
157 rebind<std::pair<const _tKey, typename _tList::iterator>>::other>;
158 };
160
161
168 template<typename _tKey, typename _tMapped, typename _fHash = void,
169 typename _tTraits = used_list_cache_traits<_tKey, _tMapped, _fHash>>
170 class used_list_cache
171 {
172 public:
174 using traits_type = _tTraits;
175 using map_type = typename traits_type::map_type;
176 using key_type = typename map_type::key_type;
178 using value_type = typename map_type::value_type;
179 using size_type = typename map_type::size_type;
180 using used_list_type = typename traits_type::used_list_type;
181 using used_cache_type = typename traits_type::used_cache_type;
182 using const_iterator = typename used_list_type::const_iterator;
183 using iterator = typename used_list_type::iterator;
185 static_assert(are_same<size_type, typename used_list_type::size_type,
186 typename used_cache_type::size_type>(), "Invalid size found.");
187
188 private:
194 mutable used_list_type used_list;
195 used_cache_type used_cache;
197 size_type max_use;
199
200 public:
202 std::function<void(value_type&)> flush{};
203
204 explicit
205 used_list_cache(size_type s = yimpl(15U))
206 : used_list(), used_cache(), max_use(s)
207 {}
208 used_list_cache(used_list_cache&&) = default;
209
210 private:
212 void
213 check_max_used() ynothrowv
214 {
215 used_list.shrink(used_cache, max_use, flush);
216 }
217
218 public:
219 size_type
220 get_max_use() const ynothrow
221 {
222 return max_use;
223 }
224
226 void
227 set_max_use(size_type s) ynothrowv
228 {
229 max_use = s < 1 ? 1 : s;
230 check_max_used();
231 }
232
234
235 iterator
236 begin()
237 {
238 return used_list.begin();
239 }
240 iterator
241 begin() const
242 {
243 return used_list.cbegin();
244 }
246
247 void
248 clear() ynothrow
249 {
250 used_list.clear(),
251 used_cache.clear();
252 }
253
254 template<typename... _tParams>
255 std::pair<iterator, bool>
256 emplace(const key_type& k, _tParams&&... args)
257 {
258 check_max_used();
259
260 const auto i_cache(used_cache.find(k));
261
262 if(i_cache == used_cache.end())
263 {
264 const auto i(used_list.emplace(k, yforward(args)...));
265
266 try
267 {
268 used_cache.emplace(k, i);
269 }
270 catch(...)
271 {
272 used_list.undo_emplace();
273 throw;
274 }
275 return {i, true};
276 }
277 else
278 return {i_cache->second, false};
279 }
280 template<typename... _tParams>
281 std::pair<iterator, bool>
282 emplace(_tParams&&... args)
283 {
284 check_max_used();
285
286 const auto i(used_list.emplace_front(yforward(args)...));
287
288 try
289 {
290 const auto pr(used_cache.emplace(i->first, i));
291
292 if(!pr.second)
293 {
294 used_list.undo_emplace();
295 return {pr.first, false};
296 }
297 }
298 catch(...)
299 {
300 used_list.undo_emplace();
301 throw;
302 }
303 return {i, true};
304 }
305
307
308 iterator
309 end()
310 {
311 return used_list.end();
312 }
313 iterator
314 end() const
315 {
316 return used_list.cend();
317 }
319
320 iterator
321 find(const key_type& k)
322 {
323 const auto i(used_cache.find(k));
324
325 return i != used_cache.end() ? used_list.refresh(i->second) : end();
326 }
327 const_iterator
328 find(const key_type& k) const
329 {
330 const auto i(used_cache.find(k));
331
332 return i != used_cache.end() ? used_list.refresh(i->second) : end();
333 }
334
336
337 const used_cache_type&
338 get() const ynothrow
339 {
340 return used_cache;
341 }
342
343 const used_list_type&
344 list() const ynothrow
345 {
346 return used_list;
347 }
349
351 size_type
352 size() const ynothrow
353 {
354 return used_cache.size();
355 }
356 };
358
359
367 template<class _tMap, typename _tKey, typename _func, typename... _tParams>
368 auto
369 cache_lookup(_tMap& cache, const _tKey& key, _func init, _tParams&&... args)
370 -> decltype((cache.begin()->second))
371 {
372 auto i(cache.find(key));
373
374 if(i == cache.end())
375 {
376 const auto pr(cache.emplace(key, init(yforward(args)...)));
377
378 if(YB_UNLIKELY(!pr.second))
379 throw std::runtime_error("Cache insertion failed.");
380 i = pr.first;
381 }
382 return i->second;
383 }
384
385 } // namespace ystdex;
386
387 #endif
388
ystdex::recent_used_list::value_type
std::pair< const _tKey, _tMapped > value_type
Definition: cache.hpp:54
ystdex::used_list_cache::end
iterator end()
Definition: cache.hpp:309
ystdex::fseq::pop_front
empty_base< _types... > pop_front(empty_base< _type, _types... >)
Definition: variadic.hpp:81
ystdex::recent_used_list::shrink
void shrink(_tMap &m, size_type max_use, _tParams &&...args)
Definition: cache.hpp:115
CHRLib::f
f(d, s)
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:262
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::key_type
typename map_type::key_type key_type
Definition: cache.hpp:176
deref_op.hpp
解引用操作。
ystdex::used_list_cache_traits< _tKey, _tMapped, void, _tAlloc, _tList >::used_cache_type
std::map< _tKey, typename _tList::iterator, typename map_type::key_compare, typename _tAlloc::template rebind< std::pair< const _tKey, typename _tList::iterator >>::other > used_cache_type
Definition: cache.hpp:157
YB_UNLIKELY
#define YB_UNLIKELY(_expr)
分支预测提示。
Definition: ydef.h:464
ystdex::used_list_cache::clear
void clear()
Definition: cache.hpp:248
ystdex::cpp2014::cend
auto cend(const _tRange &c) -> decltype(std::end(c))
Definition: range.hpp:87
CHRLib::args
_tParams && args
Definition: CharacterProcessing.h:538
ystdex::used_list_cache::list
const used_list_type & list() const
Definition: cache.hpp:344
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::used_cache_type
typename traits_type::used_cache_type used_cache_type
Definition: cache.hpp:181
ystdex::used_list_cache_traits::used_list_type
_tList used_list_type
Definition: cache.hpp:144
ystdex::used_list_cache::begin
iterator begin() const
Definition: cache.hpp:241
ystdex::cpp2011::end
_type * end(_type(&&array)[_vN])
Definition: range.hpp:54
ystdex::used_list_cache::get_max_use
size_type get_max_use() const
Definition: cache.hpp:220
ystdex::used_list_cache::flush
std::function< void(value_type &)> flush
Definition: cache.hpp:202
ystdex::used_list_cache_traits< _tKey, _tMapped, void, _tAlloc, _tList >::used_list_type
_tList used_list_type
Definition: cache.hpp:154
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::map_type
typename traits_type::map_type map_type
Definition: cache.hpp:175
ystdex::path_category::empty
ystdex::used_list_cache::emplace
std::pair< iterator, bool > emplace(_tParams &&...args)
Definition: cache.hpp:282
ystdex::used_list_cache::used_list_cache
used_list_cache(size_type s=15U)
Definition: cache.hpp:205
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::size_type
typename map_type::size_type size_type
Definition: cache.hpp:179
ystdex::used_list_cache_traits::used_cache_type
std::unordered_map< _tKey, typename _tList::iterator, _fHash, typename map_type::key_equal, typename _tAlloc::template rebind< std::pair< const _tKey, typename _tList::iterator >>::other > used_cache_type
Definition: cache.hpp:147
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:766
ystdex::used_list_cache::used_list
used_list_type used_list
Definition: cache.hpp:186
ystdex::used_list_cache
按最近使用策略刷新的缓存。
Definition: cache.hpp:170
ystdex::cache_lookup
auto cache_lookup(_tMap &cache, const _tKey &key, _func init, _tParams &&...args) -> decltype((cache.begin() ->second))
以指定的关键字查找作为缓存的无序关联容器， 若没有找到使用指定的可调用对象和参数初始化内容。 ...
Definition: cache.hpp:369
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::value_type
typename map_type::value_type value_type
Definition: cache.hpp:178
CHRLib::s
_tDst const _tSrc * s
Definition: CharacterProcessing.h:140
ystdex::cpp2014::cbegin
auto cbegin(const _tRange &c) -> decltype(std::begin(c))
Definition: range.hpp:79
ystdex
特性测试宏。
Definition: ydef.h:822
ystdex::recent_used_list::shrink
void shrink(_tMap &m, _func f)
Definition: cache.hpp:102
YSLib::i
return i
Definition: YCoreUtilities.h:176
ystdex::used_list_cache::find
const_iterator find(const key_type &k) const
Definition: cache.hpp:328
type_op.hpp
C++ 类型操作。
ystdex::recent_used_list::iterator
typename list_type::iterator iterator
Definition: cache.hpp:58
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::iterator
typename used_list_type::iterator iterator
Definition: cache.hpp:183
ystdex::recent_used_list::const_iterator
typename list_type::const_iterator const_iterator
Definition: cache.hpp:57
cassert.h
ISO C 断言/调试跟踪扩展。
ystdex::fseq::front
identity< _type > front(empty_base< _type, _types... >)
Definition: variadic.hpp:74
ystdex::used_list_cache::used_cache
used_cache_type used_cache
Definition: cache.hpp:195
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::const_iterator
typename used_list_type::const_iterator const_iterator
Definition: cache.hpp:182
ystdex::used_list_cache::size
size_type size() const
Definition: cache.hpp:352
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:786
CHRLib::CharSet::other
Definition: Encoding.h:65
ystdex::used_list_cache::max_use
size_type max_use
保持可以再增加一个缓存项的最大容量。
Definition: cache.hpp:198
ystdex::used_list_cache::emplace
std::pair< iterator, bool > emplace(const key_type &k, _tParams &&...args)
Definition: cache.hpp:256
ystdex::recent_used_list::size_type
typename list_type::size_type size_type
Definition: cache.hpp:56
ystdex::recent_used_list::refresh
iterator refresh(iterator i)
Definition: cache.hpp:83
ystdex::recent_used_list::allocator_type
_tAlloc allocator_type
Definition: cache.hpp:53
ystdex::used_list_cache_traits< _tKey, _tMapped, void, _tAlloc, _tList >::map_type
std::map< _tKey, _tMapped, std::less< _tKey >, _tAlloc > map_type
Definition: cache.hpp:153
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 传递对应参数。
Definition: ydef.h:995
ystdex::used_list_cache::end
iterator end() const
Definition: cache.hpp:314
yassume
#define yassume(_expr)
假定：环境语义。
Definition: cassert.h:105
ystdex::are_same
判断第一个参数和之后的参数指定的类型相同。
Definition: type_traits.hpp:972
ystdex::recent_used_list::emplace
iterator emplace(_tParams &&...args)
Definition: cache.hpp:70
ystdex::used_list_cache_traits
最近刷新策略的缓存特征。
Definition: cache.hpp:140
ystdex::cpp2011::begin
_type * begin(_type(&&array)[_vN])
Definition: range.hpp:46
ystdex::used_list_cache_traits::map_type
std::unordered_map< _tKey, _tMapped, _fHash, std::equal_to< _tKey >, _tAlloc > map_type
Definition: cache.hpp:143
ystdex::recent_used_list
使用双向链表实现的最近使用列表。
Definition: cache.hpp:50
ystdex::used_list_cache::check_max_used
void check_max_used()
Definition: cache.hpp:213
ystdex::used_list_cache::set_max_use
void set_max_use(size_type s)
Definition: cache.hpp:227
ystdex::used_list_cache::begin
iterator begin()
Definition: cache.hpp:236
ystdex::recent_used_list::shrink
void shrink(_tMap &m)
Definition: cache.hpp:91
ystdex::recent_used_list::list_type
std::list< value_type > list_type
Definition: cache.hpp:55
ystdex::used_list_cache::find
iterator find(const key_type &k)
Definition: cache.hpp:321
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::used_list_type
typename traits_type::used_list_type used_list_type
Definition: cache.hpp:180
ystdex::recent_used_list::undo_emplace
void undo_emplace()
Definition: cache.hpp:126