YSTest: cache.hpp 源文件

YSTest PreAlpha_b900_20201012 The YSLib Test Project

cache.hpp
浏览该文件的文档.
1 /*
2 © 2013-2016, 2018-2020 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 "allocator.hpp" // for std::pair, yassume, allocator_traits, are_same,
32 // rebind_alloc_t;
33 #include <list> // for std::list;
34 #include <unordered_map> // for std::unordered_map;
35 #include <map> // for std::map;
36 #include "function.hpp" // for function;
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:
57 using allocator_type = _tAlloc;
58 using value_type = std::pair<const _tKey, _tMapped>;
59 using list_type = std::list<value_type>;
60 using size_type = typename list_type::size_type;
61 using const_iterator = typename list_type::const_iterator;
62 using iterator = typename list_type::iterator;
63
64 using list_type::begin;
65
66 using list_type::cbegin;
67
68 using list_type::cend;
69
70 using list_type::clear;
71
72 template<typename... _tParams>
73 iterator
74 emplace(_tParams&&... args)
75 {
76 list_type::emplace_front(yforward(args)...);
77 return begin();
78 }
79
80 using list_type::empty;
81
82 using list_type::end;
83
84 using list_type::front;
85
86 iterator
87 refresh(iterator i) ynothrowv
88 {
89 list_type::splice(begin(), *this, i);
90 return i;
91 }
92
93 template<typename _tMap>
94 void
95 shrink(_tMap& m) ynothrowv
96 {
97 yassume(!empty());
98
99 auto& val(list_type::back());
100
101 m.erase(val.first);
102 list_type::pop_back();
103 }
104 template<typename _tMap, typename _func>
105 void
106 shrink(_tMap& m, _func f)
107 {
108 yassume(!empty());
109
110 auto& val(list_type::back());
111
112 if(f)
113 f(val);
114 m.erase(val.first);
115 list_type::pop_back();
116 }
117 template<typename _tMap, typename... _tParams>
118 void
119 shrink(_tMap& m, size_type max_use, _tParams&&... args)
120 {
121 while(max_use < size_type(m.size()))
122 {
123 yassume(!m.empty());
124
125 shrink(m, yforward(args)...);
126 }
127 }
128
129 void
130 undo_emplace() ynothrow
131 {
132 yassume(!empty());
133
134 list_type::pop_front();
135 }
136 };
137
138
140
141 template<typename _tKey, typename _tMapped, typename _fHash = std::hash<_tKey>,
142 class _tAlloc = std::allocator<std::pair<const _tKey, _tMapped>>,
143 class _tList = recent_used_list<_tKey, _tMapped, _tAlloc>>
144 struct used_list_cache_traits
145 {
146 using map_type = std::unordered_map<_tKey, _tMapped, _fHash,
147 std::equal_to<_tKey>, _tAlloc>;
148 using used_list_type = _tList;
149 using used_cache_type = std::unordered_map<_tKey, typename _tList::iterator,
150 _fHash, typename map_type::key_equal, rebind_alloc_t<_tAlloc,
151 std::pair<const _tKey, typename _tList::iterator>>>;
152 };
153
154 template<typename _tKey, typename _tMapped, class _tAlloc, class _tList>
155 struct used_list_cache_traits<_tKey, _tMapped, void, _tAlloc, _tList>
156 {
157 using map_type = std::map<_tKey, _tMapped, std::less<_tKey>, _tAlloc>;
158 using used_list_type = _tList;
159 using used_cache_type = std::map<_tKey, typename _tList::iterator,
160 typename map_type::key_compare, rebind_alloc_t<_tAlloc,
161 std::pair<const _tKey, typename _tList::iterator>>>;
162 };
164
165
172 template<typename _tKey, typename _tMapped, typename _fHash = void,
173 typename _tTraits = used_list_cache_traits<_tKey, _tMapped, _fHash>>
174 class used_list_cache
175 {
176 public:
178 using traits_type = _tTraits;
179 using map_type = typename traits_type::map_type;
180 using key_type = typename map_type::key_type;
182 using value_type = typename map_type::value_type;
183 using size_type = typename map_type::size_type;
184 using used_list_type = typename traits_type::used_list_type;
185 using used_cache_type = typename traits_type::used_cache_type;
186 using const_iterator = typename used_list_type::const_iterator;
187 using iterator = typename used_list_type::iterator;
189 static_assert(are_same<size_type, typename used_list_type::size_type,
190 typename used_cache_type::size_type>(), "Invalid size found.");
191
192 private:
198 mutable used_list_type used_list;
199 used_cache_type used_cache;
201 size_type max_use;
203
204 public:
206 function<void(value_type&)> flush{};
207
208 explicit
209 used_list_cache(size_type s = yimpl(15U))
210 : used_list(), used_cache(), max_use(s)
211 {}
213
214 used_list_cache(used_list_cache&&) = default;
215
217 used_list_cache&
218 operator=(used_list_cache&&) = default;
220
221 private:
223 void
224 check_max_used() ynothrowv
225 {
226 used_list.shrink(used_cache, max_use, flush);
227 }
228
229 public:
230 size_type
231 get_max_use() const ynothrow
232 {
233 return max_use;
234 }
235
237 void
238 set_max_use(size_type s) ynothrowv
239 {
240 max_use = s < 1 ? 1 : s;
241 check_max_used();
242 }
243
245
246 iterator
247 begin()
248 {
249 return used_list.begin();
250 }
251 iterator
252 begin() const
253 {
254 return used_list.cbegin();
255 }
257
258 void
259 clear() ynothrow
260 {
261 used_list.clear(),
262 used_cache.clear();
263 }
264
265 template<typename... _tParams>
266 std::pair<iterator, bool>
267 emplace(const key_type& k, _tParams&&... args)
268 {
269 check_max_used();
270
271 const auto i_cache(used_cache.find(k));
272
273 if(i_cache == used_cache.end())
274 {
275 const auto i(used_list.emplace(k, yforward(args)...));
276
277 try
278 {
279 used_cache.emplace(k, i);
280 }
281 catch(...)
282 {
283 used_list.undo_emplace();
284 throw;
285 }
286 return {i, true};
287 }
288 else
289 return {i_cache->second, false};
290 }
291 template<typename... _tParams>
292 std::pair<iterator, bool>
293 emplace(_tParams&&... args)
294 {
295 check_max_used();
296
297 const auto i(used_list.emplace_front(yforward(args)...));
298
299 try
300 {
301 const auto pr(used_cache.emplace(i->first, i));
302
303 if(!pr.second)
304 {
305 used_list.undo_emplace();
306 return {pr.first, false};
307 }
308 }
309 catch(...)
310 {
311 used_list.undo_emplace();
312 throw;
313 }
314 return {i, true};
315 }
316
318
319 iterator
320 end()
321 {
322 return used_list.end();
323 }
324 iterator
325 end() const
326 {
327 return used_list.cend();
328 }
330
331 iterator
332 find(const key_type& k)
333 {
334 const auto i(used_cache.find(k));
335
336 return i != used_cache.end() ? used_list.refresh(i->second) : end();
337 }
338 const_iterator
339 find(const key_type& k) const
340 {
341 const auto i(used_cache.find(k));
342
343 return i != used_cache.end() ? used_list.refresh(i->second) : end();
344 }
345
347
348 const used_cache_type&
349 get() const ynothrow
350 {
351 return used_cache;
352 }
353
354 const used_list_type&
355 list() const ynothrow
356 {
357 return used_list;
358 }
360
362 size_type
363 size() const ynothrow
364 {
365 return used_cache.size();
366 }
367 };
369
370
378 template<class _tMap, typename _tKey, typename _func, typename... _tParams>
379 auto
380 cache_lookup(_tMap& cache, const _tKey& key, _func init, _tParams&&... args)
381 -> decltype((cache.begin()->second))
382 {
383 auto i(cache.find(key));
384
385 if(i == cache.end())
386 {
387 const auto pr(cache.emplace(key, init(yforward(args)...)));
388
389 if(YB_UNLIKELY(!pr.second))
390 throw std::runtime_error("Cache insertion failed.");
391 i = pr.first;
392 }
393 return i->second;
394 }
395
396 } // namespace ystdex;
397
398 #endif
399
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::size_type
typename map_type::size_type size_type
Definition: cache.hpp:183
ystdex::used_list_cache::used_list_cache
used_list_cache(size_type s=15U)
Definition: cache.hpp:209
ystdex::fseq::front
identity< _type > front(empty_base< _type, _types... >)
Definition: variadic.hpp:74
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::map_type
typename traits_type::map_type map_type
Definition: cache.hpp:179
platform::containers::map
ystdex::map< _tKey, _tMapped, _fComp, _tAlloc > map
Definition: Container.h:113
ystdex::used_list_cache::end
iterator end()
Definition: cache.hpp:320
platform::containers::list
ystdex::list< _type, _tAlloc > list
Definition: Container.h:99
ystdex::recent_used_list::list_type
std::list< value_type > list_type
Definition: cache.hpp:59
ystdex::used_list_cache::check_max_used
void check_max_used()
Definition: cache.hpp:224
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:157
YSLib::IO::_tTraits
const string &path const String &path class class _tTraits
Definition: YSLib/Service/FileSystem.h:582
ystdex::used_list_cache::set_max_use
void set_max_use(size_type s)
Definition: cache.hpp:238
ystdex::used_list_cache::list
const used_list_type & list() const
Definition: cache.hpp:355
ystdex::used_list_cache_traits
最近刷新策略的缓存特征。
Definition: cache.hpp:145
ystdex::used_list_cache::max_use
size_type max_use
保持可以再增加一个缓存项的最大容量。
Definition: cache.hpp:202
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::iterator
typename used_list_type::iterator iterator
Definition: cache.hpp:187
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::used_cache_type
typename traits_type::used_cache_type used_cache_type
Definition: cache.hpp:185
ystdex::recent_used_list::undo_emplace
void undo_emplace()
Definition: cache.hpp:130
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::value_type
typename map_type::value_type value_type
Definition: cache.hpp:182
ystdex::recent_used_list::const_iterator
typename list_type::const_iterator const_iterator
Definition: cache.hpp:61
ystdex::used_list_cache::get
const used_cache_type & get() const
Definition: cache.hpp:349
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::const_iterator
typename used_list_type::const_iterator const_iterator
Definition: cache.hpp:186
ystdex::recent_used_list::iterator
typename list_type::iterator iterator
Definition: cache.hpp:62
CHRLib::f
f(d, s)
ystdex::used_list_cache::flush
function< void(value_type &)> flush
Definition: cache.hpp:206
ystdex::used_list_cache
按最近使用策略刷新的缓存。
Definition: cache.hpp:175
allocator.hpp
分配器接口。
ystdex::cpp2014::cbegin
auto cbegin(const _tRange &c) -> decltype(ystdex::begin(c))
Definition: range.hpp:418
ystdex::are_same
判断第一参数和之后的参数指定的类型相同。
Definition: meta.hpp:768
CHRLib::args
YB_ATTR_nodiscard _tParams && args
Definition: CharacterProcessing.h:649
ystdex::cpp2014::cend
auto cend(const _tRange &c) -> decltype(ystdex::end(c))
Definition: range.hpp:427
yassume
#define yassume(_expr)
假定：环境语义。
Definition: cassert.h:96
ystdex::used_list_cache::size
size_type size() const
Definition: cache.hpp:363
function.hpp
函数基本操作和调用包装对象。
ystdex::used_list_cache::used_list
used_list_type used_list
Definition: cache.hpp:190
ystdex::recent_used_list::shrink
void shrink(_tMap &m, size_type max_use, _tParams &&... args)
Definition: cache.hpp:119
yforward
#define yforward(_expr)
根据参数类型使用 std::forward 转发对应参数。
Definition: ydef.h:1508
ystdex::recent_used_list::refresh
iterator refresh(iterator i)
Definition: cache.hpp:87
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::used_list_type
typename traits_type::used_list_type used_list_type
Definition: cache.hpp:184
ystdex::used_list_cache_traits< _tKey, _tMapped, void, _tAlloc, _tList >::used_list_type
_tList used_list_type
Definition: cache.hpp:158
ystdex::cpp2017::end
auto end(_tRange &c) -> decltype(c.end())
Definition: range.hpp:345
platform::containers::unordered_map
std::unordered_map< _tKey, _tMapped, _fHash, _fEqual, _tAlloc > unordered_map
Definition: Container.h:133
ystdex::recent_used_list::size_type
typename list_type::size_type size_type
Definition: cache.hpp:60
YSLib::i
return i
Definition: YCoreUtilities.h:177
ystdex::used_list_cache::begin
iterator begin()
Definition: cache.hpp:247
ystdex::recent_used_list::shrink
void shrink(_tMap &m, _func f)
Definition: cache.hpp:106
ystdex::rebind_alloc_t
typename allocator_traits< _tAlloc >::template rebind_alloc< _type > rebind_alloc_t
Definition: allocator.hpp:423
ystdex::used_list_cache::get_max_use
size_type get_max_use() const
Definition: cache.hpp:231
ystdex::used_list_cache< CacheKey, shared_ptr< Image >, CacheHash >::key_type
typename map_type::key_type key_type
Definition: cache.hpp:180
ystdex::cpp2017::empty
auto empty(const _tRange &c) -> decltype(c.empty())
Definition: range.hpp:562
CHRLib::s
_tDst const _tSrc * s
Definition: CharacterProcessing.h:143
ystdex::cache_lookup
auto cache_lookup(_tMap &cache, const _tKey &key, _func init, _tParams &&... args) -> decltype((cache.begin() ->second))
以指定的关键字查找作为缓存的无序关联容器， 若没有找到使用指定的可调用对象和参数初始化内容。
Definition: cache.hpp:380
ystdex::used_list_cache::used_cache
used_cache_type used_cache
Definition: cache.hpp:199
ystdex::recent_used_list
使用双向链表实现的最近使用列表。
Definition: cache.hpp:51
ystdex::used_list_cache::clear
void clear()
Definition: cache.hpp:259
ystdex::used_list_cache_traits< _tKey, _tMapped, void, _tAlloc, _tList >::used_cache_type
std::map< _tKey, typename _tList::iterator, typename map_type::key_compare, rebind_alloc_t< _tAlloc, std::pair< const _tKey, typename _tList::iterator > >> used_cache_type
Definition: cache.hpp:161
ystdex::recent_used_list::value_type
std::pair< const _tKey, _tMapped > value_type
Definition: cache.hpp:58
ynothrowv
#define ynothrowv
YSLib 无异常抛出保证验证：有条件地使用无异常抛出规范。
Definition: ydef.h:1219
ystdex
<memory> 特性测试宏。
Definition: ydef.h:1262
YSLib::_tParams
YB_ATTR_nodiscard YB_PURE typename _tParams
Definition: ValueNode.h:1294
ystdex::used_list_cache::end
iterator end() const
Definition: cache.hpp:325
ystdex::recent_used_list::allocator_type
_tAlloc allocator_type
分配器类型。
Definition: cache.hpp:57
ystdex::used_list_cache::operator=
used_list_cache & operator=(used_list_cache &&)=default
ystdex::used_list_cache::emplace
std::pair< iterator, bool > emplace(const key_type &k, _tParams &&... args)
Definition: cache.hpp:267
ystdex::used_list_cache_traits::map_type
std::unordered_map< _tKey, _tMapped, _fHash, std::equal_to< _tKey >, _tAlloc > map_type
Definition: cache.hpp:147
ystdex::used_list_cache_traits::used_list_type
_tList used_list_type
Definition: cache.hpp:148
ystdex::used_list_cache::find
iterator find(const key_type &k)
Definition: cache.hpp:332
YB_UNLIKELY
#define YB_UNLIKELY(_expr)
分支预测提示。
Definition: ydef.h:828
ystdex::used_list_cache::begin
iterator begin() const
Definition: cache.hpp:252
ystdex::recent_used_list::emplace
iterator emplace(_tParams &&... args)
Definition: cache.hpp:74
const
const Decapsulate const Decapsulate &y ynothrow ContextNode &ctx const
Definition: NPLA1Forms.cpp:1629
yimpl
#define yimpl(...)
实现标签。
Definition: ydef.h:413
ystdex::used_list_cache::emplace
std::pair< iterator, bool > emplace(_tParams &&... args)
Definition: cache.hpp:293
ynothrow
#define ynothrow
YSLib 无异常抛出保证：若支持 noexcept 关键字， 指定特定的 noexcept 异常规范。
Definition: ydef.h:1199
ystdex::used_list_cache_traits::used_cache_type
std::unordered_map< _tKey, typename _tList::iterator, _fHash, typename map_type::key_equal, rebind_alloc_t< _tAlloc, std::pair< const _tKey, typename _tList::iterator > >> used_cache_type
Definition: cache.hpp:151
ystdex::fseq::pop_front
integer_sequence< _tInt, _vSeq... > pop_front(integer_sequence< _tInt, _vInt, _vSeq... >)
Definition: integer_sequence.hpp:91
ystdex::used_list_cache::find
const_iterator find(const key_type &k) const
Definition: cache.hpp:339
ystdex::cpp2017::begin
auto begin(_tRange &c) -> decltype(c.begin())
Definition: range.hpp:323
ystdex::recent_used_list::shrink
void shrink(_tMap &m)
Definition: cache.hpp:95
ystdex::used_list_cache::used_list_cache
used_list_cache(used_list_cache &&)=default