YSTest  PreAlpha_b500_20140530
The YSLib Test Project
 全部  命名空间 文件 函数 变量 类型定义 枚举 枚举值 友元 宏定义  
Cache.hpp
浏览该文件的文档.
1 /*
2  © 2013-2014 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 YSL_INC_Core_Cache_hpp_
29 #define YSL_INC_Core_Cache_hpp_ 1
30 
31 #include "YModules.h"
32 #include YFM_YSLib_Core_YShellDefinition
33 #include <ystdex/iterator.hpp> // for ystdex::is_undereferenceable;
34 #include YFM_YSLib_Adaptor_YContainer
35 
36 namespace YSLib
37 {
38 
45 template<typename _tKey, typename _tMapped, typename _fHash = std::hash<_tKey>,
46  typename _fEqual = std::equal_to<_tKey>,
47  class _tAlloc = std::allocator<pair<const _tKey, _tMapped>>>
48 class GMRUCache
49  : private unordered_map<_tKey, _tMapped, _fHash, _fEqual, _tAlloc>
50 {
51 public:
52  using Map = unordered_map<_tKey, _tMapped, _fHash, _fEqual, _tAlloc>;
53  using UseList = list<_tKey, _tAlloc>;
54  using UseCache = unordered_multimap<_tKey, typename UseList::iterator,
55  _fHash, _fEqual, _tAlloc>;
56  using typename Map::const_iterator;
57  using typename Map::iterator;
58  using typename Map::key_type;
59  using typename Map::size_type;
60 
61 private:
62  mutable UseList use_list;
65  size_type max_use;
66 
67 public:
68  explicit
69  GMRUCache(size_type s = 15U)
70  : Map(), use_list(), use_cache(), max_use(s)
71  {}
73 
74 private:
75  void
76  CheckMaxUse()
77  {
78  while(max_use < use_list.size())
79  {
80  YAssert(!use_list.empty(), "Invalid state of use list found.");
81  YAssert(!use_cache.empty(), "Invalid state of use cache found.");
82 
83  const auto& key(use_list.front());
84 
85  Map::erase(key),
86  use_cache.erase(key);
87  use_list.pop_front();
88  }
89  }
90 
91 public:
92  DefGetter(const ynothrow, size_type, MaxUse, max_use)
93 
94  void
95  SetMaxUse(size_type s)
96  {
97  if(s < 1)
98  s = 1;
99  CheckMaxUse();
100  }
101 
102  using Map::begin;
103 
104  void
106  {
107  Map::clear(),
108  use_list.clear(),
109  use_cache.clear();
110  }
111 
112  using Map::end;
113 
114  template<typename... _tParams>
115  pair<typename Map::iterator, bool>
116  emplace(_tParams&&... args)
117  {
118  CheckMaxUse();
119 
120  const auto pr(Map::emplace(yforward(args)...));
121 
122  if(pr.second)
123  {
125 
126  YAssert(!is_undereferenceable(pr.first), "Bad iterator found.");
127 
128  const auto& k(pr.first->first);
129  const auto i(use_list.insert(use_list.end(), k));
130 
131  try
132  {
133  use_cache.emplace(k, i);
134  }
135  catch(...)
136  {
137  YAssert(!use_list.empty(), "Invalid state of use list found.");
138  use_list.pop_back();
139  throw;
140  }
141  }
142  return pr;
143  }
144 
145  iterator
146  find(const key_type& k)
147  {
148  const auto i(use_cache.find(k));
149 
150  if(i != use_cache.end())
151  {
152  use_list.splice(use_list.end(), use_list, i->second);
153  return Map::find(k);
154  }
155  return Map::end();
156  }
157  const_iterator
158  find(const key_type& k) const
159  {
160  const auto i(use_cache.find(k));
161 
162  if(i != use_cache.end())
163  {
164  use_list.splice(use_list.end(), use_list, i->second);
165  return Map::find(k);
166  }
167  return Map::end();
168  }
169 
170  using Map::size;
171 };
172 
173 
180 template<class _tMap, typename _tKey, typename _fCallable, typename... _tParams>
181 auto
182 CacheLookup(_tMap& cache, const _tKey& key, _fCallable init,
183  _tParams&&... args) -> decltype((cache.begin()->second))
184 {
185  auto i(cache.find(key));
186 
187  if(i == cache.end())
188  {
189  const auto pr(cache.emplace(key, init(yforward(args)...)));
190 
191  if(YB_UNLIKELY(!pr.second))
192  throw LoggedEvent("Cache insertion failed.", Alert);
193  i = pr.first;
194  }
195  return i->second;
196 }
197 
198 } // namespace YSLib;
199 
200 #endif
201 
iterator find(const key_type &k)
Definition: Cache.hpp:146
yconstfn const string _tParams && args
Definition: Loader.h:111
DefDeMoveCtor(GMRUCache) private
Definition: Cache.hpp:72
unordered_multimap< YSLib::Drawing::Typeface::BitmapKey, typename UseList::iterator, YSLib::Drawing::Typeface::BitmapKeyHash, _fEqual, _tAlloc > UseCache
Definition: Cache.hpp:55
#define yforward(_expr)
根据参数类型使用 std::forward 传递对应参数。
Definition: ydef.h:722
GMRUCache(size_type s=15U)
Definition: Cache.hpp:69
#define YB_UNLIKELY(expr)
分支预测提示。
Definition: ydef.h:298
size_type max_use
保持可以再增加一个缓存项的最大容量。
Definition: Cache.hpp:65
#define ynothrow
YSLib 无异常抛出保证:若支持 noexcept 关键字, 指定特定的 noexcept 异常规范。
Definition: ydef.h:514
通用迭代器。
unordered_map< YSLib::Drawing::Typeface::BitmapKey, YSLib::Drawing::Typeface::SmallBitmapData, YSLib::Drawing::Typeface::BitmapKeyHash, _fEqual, _tAlloc > Map
Definition: Cache.hpp:52
const_iterator find(const key_type &k) const
Definition: Cache.hpp:158
UseCache use_cache
Definition: Cache.hpp:63
void clear() ynoexcept
Definition: Cache.hpp:105
DefGetter(const ynothrow, size_type, MaxUse, max_use) void SetMaxUse(size_type s)
Definition: Cache.hpp:92
auto CacheLookup(_tMap &cache, const _tKey &key, _fCallable init, _tParams &&...args) -> decltype((cache.begin() ->second))
以指定的关键字查找作为缓存的无序关联容器, 若没有找到使用指定的可调用对象和参数初始化内容。 ...
Definition: Cache.hpp:182
按最近最多使用策略刷新的缓存。
Definition: Cache.hpp:48
UseList use_list
Definition: Cache.hpp:62
pair< typename Map::iterator, bool > emplace(_tParams &&...args)
Definition: Cache.hpp:116
记录日志的异常事件类。
Definition: yexcept.h:58
bool is_undereferenceable(const any_input_iterator< _type, _tDifference, _tPointer, _tReference > &i)
#define ynoexcept(...)
YSLib 无异常抛出保证:指定特定的异常规范。
Definition: ydef.h:526
#define YAssert(_expr, _msg)
Definition: cassert.h:73