27 #ifndef INCLUDED_CACHE_ADT 28 #define INCLUDED_CACHE_ADT 33 #include <unordered_map> 115 float min_credit_density = FLT_MAX;
116 for(
typename Entries::const_iterator it = entries.begin(); it != entries.end(); ++it)
118 const float credit_density = Entries::entry_from_it(it).credit_density();
119 min_credit_density = std::min(min_credit_density, credit_density);
121 return min_credit_density;
131 template<
class Entry,
class Entries>
149 template<
class Entry,
class Entries>
165 min_credit_density = std::min(min_credit_density, entry.credit_density());
171 is_min_entry =
feq(min_credit_density, entry.credit_density());
181 min_credit_density = -1.0f;
193 return min_credit_density;
203 min_credit_density = FLT_MAX;
224 template<
typename Key,
typename Entry,
template<
class Entry_,
class Entries>
class McdCalc =
McdCalc_Cached>
236 (void)add_(key, entry);
241 MapCIt it = map.find(key);
244 *pentry = &it->second;
248 void remove(
const Key&
key)
260 mcd_calc.notify_impending_increase_or_remove(entry);
264 const float gain = 0.75f;
265 entry.credit = gain*entry.cost + (1.0f-gain)*entry.credit;
267 mcd_calc.notify_increased_or_removed(entry);
280 const float min_credit_density = mcd_calc(map);
281 ENSURE(min_credit_density > 0.0f);
283 for(
MapIt it = map.begin(); it != map.end();)
285 Entry& entry = it->second;
287 charge(entry, min_credit_density);
288 if(should_evict(entry))
290 entry_list.push_back(entry);
293 MapIt it_to_remove = it++;
294 map.erase(it_to_remove);
298 mcd_calc.notify_decreased(entry);
303 if(entry_list.empty())
308 class Map :
public std::unordered_map<Key, Entry>
314 typedef typename Map::iterator
MapIt;
315 typedef typename Map::const_iterator
MapCIt;
321 typedef std::pair<MapIt, bool> PairIB;
322 typename Map::value_type val = std::make_pair(key, entry);
323 PairIB ret = map.insert(val);
326 mcd_calc.notify_added(entry);
334 const Entry& entry = it->second;
335 mcd_calc.notify_impending_increase_or_remove(entry);
336 mcd_calc.notify_increased_or_removed(entry);
342 entry.credit -= delta * entry.size;
353 for(MapIt it = map.begin(); it != map.end(); ++it)
355 Entry& entry = it->second;
356 entry.credit -= delta * entry.size;
357 if(!should_evict(entry))
358 mcd_calc.notify_decreased(entry);
368 return entry.credit < 0.0001f;
384 template<
typename Key,
class Entry>
398 commit_pending_delta();
400 MapIt it = Parent::add_(key, entry);
404 void remove(
const Key&
key)
411 while(!pri_q.empty())
413 for(MapCIt it = this->map.begin(); it != this->map.end(); ++it)
419 Parent::on_access(entry);
423 pri_q.ensure_heap_order();
428 MapIt least_valuable_it = pri_q.top(); pri_q.pop();
429 Entry& entry = Map::entry_from_it(least_valuable_it);
431 entry_list.push_back(entry);
437 entry.credit -= pending_delta*entry.size;
438 const float credit_density = entry.credit_density();
439 ENSURE(credit_density > 0.0f);
440 pending_delta += credit_density;
442 Parent::remove_(least_valuable_it);
453 return Map::entry_from_it(it1).credit_density() >
454 Map::entry_from_it(it2).credit_density();
465 class PriQ:
public std::priority_queue<MapIt, std::vector<MapIt>, CD_greater>
475 std::make_heap(this->c.begin(), this->c.end(), this->comp);
486 if(pending_delta > 0.0f)
488 this->charge_all(pending_delta);
489 pending_delta = 0.0f;
515 return val / divisor;
535 template<
typename Key,
typename Entry>
554 *pentry = &it->entry;
558 void remove(
const Key&
key)
565 for(
It it = lru.begin(); it != lru.end(); ++it)
567 if(&entry == &it->entry)
569 add(it->key, it->entry);
579 entry_list.push_back(lru.front().entry);
596 typedef std::list<KeyAndEntry>
List;
597 typedef typename List::iterator
It;
598 typedef typename List::const_iterator
CIt;
621 : item(item_), divider((float)size_)
625 credit = (float)cost;
633 return divider(credit, (
float)size);
644 typename Key,
typename Item,
654 void add(
const Key&
key,
const Item& item,
size_t size,
size_t cost)
656 return mgr.add(key,
Entry(item, size, cost));
663 void remove(
const Key&
key)
675 bool retrieve(
const Key&
key, Item& item,
size_t* psize = 0,
bool refill_credit =
true)
678 if(!mgr.find(key, &entry))
683 *psize = entry->
size;
686 mgr.on_access((
Entry&)*entry);
691 bool peek(
const Key&
key, Item& item,
size_t* psize = 0)
693 return retrieve(key, item, psize,
false);
704 if(entries_awaiting_eviction.empty())
709 mgr.remove_least_valuable(entries_awaiting_eviction);
710 ENSURE(!entries_awaiting_eviction.empty());
713 const Entry& entry = entries_awaiting_eviction.front();
718 entries_awaiting_eviction.pop_front();
737 #endif // #ifndef INCLUDED_CACHE_ADT void notify_impending_increase_or_remove(const Entry &entry)
Definition: cache_adt.h:168
void commit_pending_delta()
Definition: cache_adt.h:484
const Status LOGIC
Definition: status.h:407
bool retrieve(const Key &key, Item &item, size_t *psize=0, bool refill_credit=true)
Definition: cache_adt.h:675
Definition: cache_adt.h:308
#define UNUSED(param)
mark a function parameter as unused and avoid the corresponding compiler warning. ...
Definition: code_annotation.h:38
void remove_(MapIt it)
Definition: cache_adt.h:332
Definition: cache_adt.h:606
float min_credit_density
Definition: cache_adt.h:208
McdCalc< Entry, Map > mcd_calc
Definition: cache_adt.h:372
bool operator()(MapIt it1, MapIt it2) const
Definition: cache_adt.h:451
CacheEntry()
Definition: cache_adt.h:616
Definition: cache_adt.h:377
void add(const Key &key, const Entry &entry)
Definition: cache_adt.h:233
float operator()(float val, float divisor) const
Definition: cache_adt.h:527
void notify_increased_or_removed(const Entry &entry)
Definition: cache_adt.h:174
Divider divider
Definition: cache_adt.h:613
Landlord_Naive< Key, Entry >::Map Map
Definition: cache_adt.h:387
Item item
Definition: cache_adt.h:608
bool operator==(const FCDJointWeightPair &a, const FCDJointWeightPair &b)
Definition: GeomReindex.cpp:59
bool remove_least_valuable(Item *pItem=0, size_t *pSize=0)
Definition: cache_adt.h:698
Divider_Naive()
Definition: cache_adt.h:511
float credit
Definition: cache_adt.h:611
void charge(Entry &entry, float delta)
Definition: cache_adt.h:340
bool should_evict(const Entry &entry)
Definition: cache_adt.h:363
bool find(const Key &key, const Entry **pentry) const
Definition: cache_adt.h:549
bool find(const Key &key, const Entry **pentry) const
Definition: cache_adt.h:239
void on_access(Entry &entry)
Definition: cache_adt.h:258
float credit_density() const
Definition: cache_adt.h:631
void add(const Key &key, const Item &item, size_t size, size_t cost)
Definition: cache_adt.h:654
void notify_decreased(const Entry &) const
Definition: cache_adt.h:136
Definition: cache_adt.h:150
bool operator==(const KeyAndEntry &rhs) const
Definition: cache_adt.h:589
static const Entry & entry_from_it(typename Map::const_iterator it)
Definition: cache_adt.h:312
Definition: cache_adt.h:584
KeyAndEntry(const Key &key, const Entry &entry)
Definition: cache_adt.h:587
void charge_all(float delta)
Definition: cache_adt.h:351
CacheEntry(const Item &item_, size_t size_, size_t cost_)
Definition: cache_adt.h:620
Definition: cache_adt.h:465
void add(const Key &key, const Entry &entry)
Definition: cache_adt.h:544
Entry entry
Definition: cache_adt.h:593
Manager< Key, Entry > mgr
Definition: cache_adt.h:734
Definition: cache_adt.h:649
Landlord_Naive< Key, Entry > Parent
Definition: cache_adt.h:446
float pending_delta
Definition: cache_adt.h:482
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:290
PriQ pri_q
Definition: cache_adt.h:478
size_t cost
Definition: cache_adt.h:610
Definition: cache_adt.h:536
bool peek(const Key &key, Item &item, size_t *psize=0)
Definition: cache_adt.h:691
List::const_iterator CIt
Definition: cache_adt.h:598
Map::const_iterator MapCIt
Definition: cache_adt.h:315
Map map
Definition: cache_adt.h:316
bool empty() const
Definition: cache_adt.h:723
void ensure_heap_order()
Definition: cache_adt.h:468
void remove_least_valuable(std::list< Entry > &entry_list)
Definition: cache_adt.h:426
Definition: cache_adt.h:449
void remove_least_valuable(std::list< Entry > &entry_list)
Definition: cache_adt.h:577
pthread_key_t key
Definition: wpthread.cpp:140
Definition: cache_adt.h:225
void on_access(Entry &entry)
Definition: cache_adt.h:417
List lru
Definition: cache_adt.h:599
size_t size
Definition: cache_adt.h:609
bool empty() const
Definition: cache_adt.h:539
uint32_t Entry
Definition: SilhouetteRenderer.cpp:138
Landlord_Naive< Key, Entry >::MapIt MapIt
Definition: cache_adt.h:388
bool operator!=(const KeyAndEntry &rhs) const
Definition: cache_adt.h:590
static Entry & entry_from_it(typename Map::iterator it)
Definition: cache_adt.h:311
Definition: cache_adt.h:508
void on_access(Entry &entry)
Definition: cache_adt.h:563
Key key
Definition: cache_adt.h:592
CacheEntry< Item, Divider > Entry
Definition: cache_adt.h:729
Cache()
Definition: cache_adt.h:652
Landlord_Lazy()
Definition: cache_adt.h:392
#define DEBUG_WARN_ERR(status)
display the error dialog with text corresponding to the given error code.
Definition: debug.h:339
McdCalc_Cached()
Definition: cache_adt.h:153
Divider_Recip()
Definition: cache_adt.h:525
Definition: cache_adt.h:385
Landlord_Naive< Key, Entry >::MapCIt MapCIt
Definition: cache_adt.h:389
void remove_least_valuable(std::list< Entry > &entry_list)
Definition: cache_adt.h:270
std::list< KeyAndEntry > List
Definition: cache_adt.h:596
bool empty() const
Definition: cache_adt.h:228
void notify_increased_or_removed(const Entry &) const
Definition: cache_adt.h:138
float recip
Definition: cache_adt.h:523
void add(const Key &key, const Entry &entry)
Definition: cache_adt.h:394
void notify_added(const Entry &) const
Definition: cache_adt.h:135
bool min_valid
Definition: cache_adt.h:209
Definition: cache_adt.h:132
bool feq(double d1, double d2, double epsilon=0.00001)
are the given floats nearly "equal"?
Definition: lib.h:88
float operator()(const Entries &entries) const
Definition: cache_adt.h:139
bool is_min_entry
Definition: cache_adt.h:212
std::list< Entry > entries_awaiting_eviction
Definition: cache_adt.h:732
Definition: cache_adt.h:378
float operator()(float val, float divisor) const
Definition: cache_adt.h:513
Map::iterator MapIt
Definition: cache_adt.h:314
List::iterator It
Definition: cache_adt.h:597
Divider_Naive(float x)
Definition: cache_adt.h:512
Divider_Recip(float x)
Definition: cache_adt.h:526
Definition: cache_adt.h:521
KeyAndEntry(const Key &key)
Definition: cache_adt.h:586
void notify_decreased(const Entry &entry)
Definition: cache_adt.h:163
void notify_impending_increase_or_remove(const Entry &) const
Definition: cache_adt.h:137
void notify_added(const Entry &entry)
Definition: cache_adt.h:155
MapIt add_(const Key &key, const Entry &entry)
Definition: cache_adt.h:319
float ll_calc_min_credit_density(const Entries &entries)
Definition: cache_adt.h:113
float operator()(const Entries &entries)
Definition: cache_adt.h:185