8 #ifndef IMPBASE_CACHE_H
9 #define IMPBASE_CACHE_H
11 #include <IMP/base/base_config.h>
12 #include "internal/cache.h"
17 #include <boost/multi_index_container.hpp>
18 #include <boost/multi_index/sequenced_index.hpp>
19 #include <boost/multi_index/hashed_index.hpp>
20 #include <boost/multi_index/global_fun.hpp>
28 IMPBASE_BEGIN_NAMESPACE
39 template <
class Generator,
40 class Checker=std::equal_to<typename Generator::result_type> >
44 mutable bool has_result_;
45 mutable typename Generator::result_type result_;
46 mutable int num_misses_;
47 mutable int num_stats_;
49 typedef typename Generator::result_type Value;
50 typedef typename Generator::argument_type Key;
52 const Checker &checker=Checker()): gen_(gen),
57 Generator &access_generator() {
return gen_;}
58 const Generator &get_generator()
const {
return gen_;}
63 const Value &
get()
const {
72 "Wrong result returned from generator");
76 void set(
const Value &v)
const {
78 "Wrong result passed on set");
82 double get_hit_rate()
const {
83 return 1.0-
static_cast<double>(num_misses_)/num_stats_;
91 template <
class Generator,
class Checker>
94 typedef typename Generator::argument_type::value_type Key;
95 typedef typename Generator::result_type::value_type Entry;
101 static Key get_0( Entry e) {
return e[0];}
102 static Key get_1( Entry e) {
return e[1];}
105 typedef boost::multi_index::global_fun<Entry,
107 &This::get_0 > P0Member;
108 typedef boost::multi_index::global_fun<Entry,
110 &This::get_1 > P1Member;
111 typedef boost::multi_index::hashed_non_unique<P0Member> Hash0Index;
112 typedef boost::multi_index::hashed_non_unique<P1Member> Hash1Index;
113 typedef boost::multi_index::indexed_by<Hash0Index,
114 Hash1Index > IndexBy;
115 typedef boost::multi_index_container<Entry,
117 typedef typename boost::multi_index::nth_index<Cache, 0>
118 ::type::const_iterator Hash0Iterator;
119 typedef typename boost::multi_index::nth_index<Cache, 1>
120 ::type::const_iterator Hash1Iterator;
126 EntryEqual(Key t0, Key t1):
129 bool operator()(
const O &o)
const {
130 return v[0]==o[0] && v[1] == o[1];
134 Hash0Iterator
get(Key t0, Key t1)
const {
136 boost::tie(b,e)=cache_.template get<0>().equal_range(t0);
139 Hash0Iterator f= std::find_if(b,e, EntryEqual(t0, t1));
141 if (f==e)
return cache_.template get<0>().end();
145 void check_it()
const {
146 #if IMP_HAS_CHECKS >= IMP_INTERNAL
149 "Cached and newly computed don't match: "
150 << cur <<
" vs " << gen_(domain_,
this)
151 <<
" and cleared is " << cleared_);
152 for (Hash0Iterator c= cache_.template get<0>().begin();
153 c != cache_.template get<0>().end(); ++c) {
155 == cache_.template get<0>().end(),
156 "Both an entry and its flip are in the table: "
157 << *c <<
": " << cur);
163 for (
unsigned int i=0; i< cleared_.size(); ++i) {
166 boost::tie(b,e)=cache_.template get<0>().equal_range(cleared_[i]);
168 <<
" was not cleared.");
172 boost::tie(b,e)=cache_.template get<1>().equal_range(cleared_[i]);
174 <<
" was not cleared.");
180 IMP_LOG_VERBOSE(
"Inserting " << nv <<
" into pair memoizer" << std::endl);
182 for (
unsigned int i=0; i< nv.size(); ++i) {
187 "An entry and its flip are already in list: "
192 cache_.insert(nv.begin(), nv.end());
195 <<
typename Generator::result_type(cache_.begin(),
200 template <
class F,
class It>
201 F do_apply( It b, It e, F f)
const {
202 for (It c=b; c!= e; ++c) {
209 const Generator &gen= Generator(),
210 const Checker &check= Checker()):
215 IMP_LOG_TERSE(
"Domain for memoizer is " << domain << std::endl);
220 if (!cleared_.empty()) fill_it();
222 return do_apply(cache_.begin(), cache_.end(), f);
228 return do_apply(cache_.begin(), cache_.end(), f);
232 void remove(
const Key &a) {
233 if (std::find(cleared_.begin(), cleared_.end(), a) != cleared_.end()) {
237 cleared_.push_back(a);
240 boost::tie(b,e)=cache_.template get<0>().equal_range(a);
241 cache_.template get<0>().erase(b,e);
245 boost::tie(b,e)=cache_.template get<1>().equal_range(a);
246 cache_.template get<1>().erase(b,e);
249 void insert(
const Entry &e) {
256 const Generator &get_generator()
const {
return gen_;}
257 Generator &access_generator()
const {
return gen_;}
268 template <
class Generator,
269 class Checker=std::equal_to<typename Generator::result_type> >
272 typedef typename Generator::result_type Value;
273 typedef typename Generator::argument_type Key;
277 unsigned int max_size_;
278 mutable int num_stats_;
279 mutable int num_misses_;
283 KVP(
const Key &k,
const Value &v): key(k), value(v){}
285 typedef boost::multi_index::member<KVP,
287 &KVP::key > KeyMember;
288 typedef boost::multi_index::hashed_unique<KeyMember> HashIndex;
289 typedef boost::multi_index::sequenced< > Sequenced;
290 typedef boost::multi_index_container<KVP,
291 boost::multi_index::indexed_by<HashIndex,
294 typedef typename boost::multi_index::template nth_index<Map, 0>
295 ::type::const_iterator LookupIterator;
296 typedef typename boost::multi_index::template nth_index<Map, 1>
297 ::type::const_iterator OrderIterator;
298 Value add_value(
const Key &k)
const {
299 Value v= gen_(k, *
this);
300 map_.template get<1>().push_front(KVP(k, v));
301 while (map_.size() > max_size_) {
303 map_.template get<1>().pop_back();
308 LRUCache(
const Generator &gen,
unsigned int size,
309 const Checker checker=Checker()): gen_(gen),
314 Value
get(
const Key &k)
const {
315 LookupIterator it=map_.template get<0>().find(k);
317 if (it == map_.template get<0>().end()) {
320 Value v=add_value(k);
322 != map_.template get<0>().end(),
323 "Failed to insert into cache");
326 map_.template get<1>().relocate(map_.template project<1>(it),
327 map_.template get<1>().begin());
334 != map_.template get<0>().end(),
335 "Gone, gone I tell you");
340 double get_hit_rate()
const {
341 return 1.0-
static_cast<double>(num_misses_)/num_stats_;
345 for (OrderIterator it= map_.template get<1>().begin();
346 it != map_.template get<1>().end(); ++it) {
347 ret.push_back(it->key);
351 typedef OrderIterator ContentIterator;
352 ContentIterator contents_begin()
const {
353 return map_.template get<1>().begin();
355 ContentIterator contents_end()
const {
356 return map_.template get<1>().end();
358 void insert(Key k, Value v) {
359 LookupIterator it=map_.template get<0>().find(k);
360 if (it == map_.template get<0>().end()) {
361 map_.template get<1>().push_front(KVP(k, v));
362 while (map_.size() > max_size_) {
363 map_.template get<1>().pop_back();
367 unsigned int size()
const {
370 Generator &access_generator() {
373 const Generator &get_generator()
const {
379 IMPBASE_END_NAMESPACE