1 /* Copyright (C) 2010 Wildfire Games.
2 *
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included
12 * in all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 /*
24 * Customizable cache data structure.
25 */
26
27 #ifndef INCLUDED_CACHE_ADT
28 #define INCLUDED_CACHE_ADT
29
30 #include <cfloat>
31
32 #include <list>
33 #include <map>
34 #include <queue> // std::priority_queue
35
36 #if CONFIG_ENABLE_BOOST
37 # include <boost/unordered_map.hpp>
38 # define MAP boost::unordered_map
39 #else
40 # define MAP stdext::hash_map
41 #endif
42
43 /*
44 Cache for items of variable size and value/"cost".
45 underlying displacement algorithm is pluggable; default is "Landlord".
46
47 template reference:
48 Entry provides size, cost, credit and credit_density().
49 rationale:
50 - made a template instead of exposing Cache::Entry because
51 that would drag a lot of stuff out of Cache.
52 - calculates its own density since that entails a Divider functor,
53 which requires storage inside Entry.
54 Entries is a collection with iterator and begin()/end() and
55 "static Entry& entry_from_it(iterator)".
56 rationale:
57 - STL map has pair<key, item> as its value_type, so this
58 function would return it->second. however, we want to support
59 other container types (where we'd just return *it).
60 Manager is a template parameterized on typename Key and class Entry.
61 its interface is as follows:
62
63 // is the cache empty?
64 bool empty() const;
65
66 // add (key, entry) to cache.
67 void add(const Key& key, const Entry& entry);
68
69 // if the entry identified by <key> is not in cache, return false;
70 // otherwise return true and pass back a pointer to it.
71 bool find(const Key& key, const Entry** pentry) const;
72
73 // remove an entry from cache, which is assumed to exist!
74 // this makes sense because callers will typically first use find() to
75 // return info about the entry; this also checks if present.
76 void remove(const Key& key);
77
78 // mark <entry> as just accessed for purpose of cache management.
79 // it will tend to be kept in cache longer.
80 void on_access(Entry& entry);
81
82 // caller's intent is to remove the least valuable entry.
83 // in implementing this, you have the latitude to "shake loose"
84 // several entries (e.g. because their 'value' is equal).
85 // they must all be push_back-ed into the list; Cache will dole
86 // them out one at a time in FIFO order to callers.
87 //
88 // rationale:
89 // - it is necessary for callers to receive a copy of the
90 // Entry being evicted - e.g. file_cache owns its items and
91 // they must be passed back to allocator when evicted.
92 // - e.g. Landlord can potentially see several entries become
93 // evictable in one call to remove_least_valuable. there are
94 // several ways to deal with this:
95 // 1) generator interface: we return one of { empty, nevermind,
96 // removed, remove-and-call-again }. this greatly complicates
97 // the call site.
98 // 2) return immediately after finding an item to evict.
99 // this changes cache behavior - entries stored at the
100 // beginning would be charged more often (unfair).
101 // resuming charging at the next entry doesn't work - this
102 // would have to be flushed when adding, at which time there
103 // is no provision for returning any items that may be evicted.
104 // 3) return list of all entries "shaken loose". this incurs
105 // frequent mem allocs, which can be alleviated via suballocator.
106 // note: an intrusive linked-list doesn't make sense because
107 // entries to be returned need to be copied anyway (they are
108 // removed from the manager's storage).
109 void remove_least_valuable(std::list<Entry>& entry_list)
110 */
111
112
113 //
114 // functors to calculate minimum credit density (MCD)
115 //
116
117 // MCD is required for the Landlord algorithm's evict logic.
118 // [Young02] calls it '\delta'.
119
120 // scan over all entries and return MCD.
ll_calc_min_credit_density(const Entries & entries)121 template<class Entries> float ll_calc_min_credit_density(const Entries& entries)
122 {
123 float min_credit_density = FLT_MAX;
124 for(typename Entries::const_iterator it = entries.begin(); it != entries.end(); ++it)
125 {
126 const float credit_density = Entries::entry_from_it(it).credit_density();
127 min_credit_density = std::min(min_credit_density, credit_density);
128 }
129 return min_credit_density;
130 }
131
132 // note: no warning is given that the MCD entry is being removed!
133 // (reduces overhead in remove_least_valuable)
134 // these functors must account for that themselves (e.g. by resetting
135 // their state directly after returning MCD).
136
137 // determine MCD by scanning over all entries.
138 // tradeoff: O(N) time complexity, but all notify* calls are no-ops.
139 template<class Entry, class Entries>
140 class McdCalc_Naive
141 {
142 public:
notify_added(const Entry &)143 void notify_added(const Entry&) const {}
notify_decreased(const Entry &)144 void notify_decreased(const Entry&) const {}
notify_impending_increase_or_remove(const Entry &)145 void notify_impending_increase_or_remove(const Entry&) const {}
notify_increased_or_removed(const Entry &)146 void notify_increased_or_removed(const Entry&) const {}
operator()147 float operator()(const Entries& entries) const
148 {
149 const float mcd = ll_calc_min_credit_density(entries);
150 return mcd;
151 }
152 };
153
154 // cache previous MCD and update it incrementally (when possible).
155 // tradeoff: amortized O(1) time complexity, but notify* calls must
156 // perform work whenever something in the cache changes.
157 template<class Entry, class Entries>
158 class McdCalc_Cached
159 {
160 public:
McdCalc_Cached()161 McdCalc_Cached() : min_credit_density(FLT_MAX), min_valid(false) {}
162
notify_added(const Entry & entry)163 void notify_added(const Entry& entry)
164 {
165 // when adding a new item, the minimum credit density can only
166 // decrease or remain the same; acting as if entry's credit had
167 // been decreased covers both cases.
168 notify_decreased(entry);
169 }
170
notify_decreased(const Entry & entry)171 void notify_decreased(const Entry& entry)
172 {
173 min_credit_density = std::min(min_credit_density, entry.credit_density());
174 }
175
notify_impending_increase_or_remove(const Entry & entry)176 void notify_impending_increase_or_remove(const Entry& entry)
177 {
178 // remember if this entry had the smallest density
179 is_min_entry = feq(min_credit_density, entry.credit_density());
180 }
181
notify_increased_or_removed(const Entry & UNUSED (entry))182 void notify_increased_or_removed(const Entry& UNUSED(entry))
183 {
184 // .. it did and was increased or removed. we must invalidate
185 // MCD and recalculate it next time.
186 if(is_min_entry)
187 {
188 min_valid = false;
189 min_credit_density = -1.0f;
190 }
191 }
192
operator()193 float operator()(const Entries& entries)
194 {
195 if(min_valid)
196 {
197 // the entry that has MCD will be removed anyway by caller;
198 // we need to invalidate here because they don't call
199 // notify_increased_or_removed.
200 min_valid = false;
201 return min_credit_density;
202 }
203
204 // this is somewhat counterintuitive. since we're calculating
205 // MCD directly, why not mark our cached version of it valid
206 // afterwards? reason is that our caller will remove the entry with
207 // MCD, so it'll be invalidated anyway.
208 // instead, our intent is to calculate MCD for the *next time*.
209 const float ret = ll_calc_min_credit_density(entries);
210 min_valid = true;
211 min_credit_density = FLT_MAX;
212 return ret;
213 }
214
215 private:
216 float min_credit_density;
217 bool min_valid;
218
219 // temporary flag set by notify_impending_increase_or_remove
220 bool is_min_entry;
221 };
222
223
224 //
225 // Landlord cache management policy: see [Young02].
226 //
227
228 // in short, each entry has credit initially set to cost. when wanting to
229 // remove an item, all are charged according to MCD and their size;
230 // entries are evicted if their credit is exhausted. accessing an entry
231 // restores "some" of its credit.
232 template<typename Key, typename Entry, template<class Entry_, class Entries> class McdCalc = McdCalc_Cached>
233 class Landlord
234 {
235 public:
empty()236 bool empty() const
237 {
238 return map.empty();
239 }
240
add(const Key & key,const Entry & entry)241 void add(const Key& key, const Entry& entry)
242 {
243 // adapter for add_ (which returns an iterator)
244 (void)add_(key, entry);
245 }
246
find(const Key & key,const Entry ** pentry)247 bool find(const Key& key, const Entry** pentry) const
248 {
249 MapCIt it = map.find(key);
250 if(it == map.end())
251 return false;
252 *pentry = &it->second;
253 return true;
254 }
255
remove(const Key & key)256 void remove(const Key& key)
257 {
258 MapIt it = map.find(key);
259 // note: don't complain if not in the cache: this happens after
260 // writing a file and invalidating its cache entry, which may
261 // or may not exist.
262 if(it != map.end())
263 remove_(it);
264 }
265
on_access(Entry & entry)266 void on_access(Entry& entry)
267 {
268 mcd_calc.notify_impending_increase_or_remove(entry);
269
270 // Landlord algorithm calls for credit to be reset to anything
271 // between its current value and the cost.
272 const float gain = 0.75f; // restore most credit
273 entry.credit = gain*entry.cost + (1.0f-gain)*entry.credit;
274
275 mcd_calc.notify_increased_or_removed(entry);
276 }
277
remove_least_valuable(std::list<Entry> & entry_list)278 void remove_least_valuable(std::list<Entry>& entry_list)
279 {
280 // we are required to evict at least one entry. one iteration
281 // ought to suffice, due to definition of min_credit_density and
282 // tolerance; however, we provide for repeating if necessary.
283 again:
284
285 // messing with this (e.g. raising if tiny) would result in
286 // different evictions than Landlord_Lazy, which is unacceptable.
287 // nor is doing so necessary: if mcd is tiny, so is credit.
288 const float min_credit_density = mcd_calc(map);
289 ENSURE(min_credit_density > 0.0f);
290
291 for(MapIt it = map.begin(); it != map.end();) // no ++it
292 {
293 Entry& entry = it->second;
294
295 charge(entry, min_credit_density);
296 if(should_evict(entry))
297 {
298 entry_list.push_back(entry);
299
300 // annoying: we have to increment <it> before erasing
301 MapIt it_to_remove = it++;
302 map.erase(it_to_remove);
303 }
304 else
305 {
306 mcd_calc.notify_decreased(entry);
307 ++it;
308 }
309 }
310
311 if(entry_list.empty())
312 goto again;
313 }
314
315 protected:
316 class Map : public MAP<Key, Entry>
317 {
318 public:
entry_from_it(typename Map::iterator it)319 static Entry& entry_from_it(typename Map::iterator it) { return it->second; }
entry_from_it(typename Map::const_iterator it)320 static const Entry& entry_from_it(typename Map::const_iterator it) { return it->second; }
321 };
322 typedef typename Map::iterator MapIt;
323 typedef typename Map::const_iterator MapCIt;
324 Map map;
325
326 // add entry and return iterator pointing to it.
add_(const Key & key,const Entry & entry)327 MapIt add_(const Key& key, const Entry& entry)
328 {
329 typedef std::pair<MapIt, bool> PairIB;
330 typename Map::value_type val = std::make_pair(key, entry);
331 PairIB ret = map.insert(val);
332 ENSURE(ret.second); // must not already be in map
333
334 mcd_calc.notify_added(entry);
335
336 return ret.first;
337 }
338
339 // remove entry (given by iterator) directly.
remove_(MapIt it)340 void remove_(MapIt it)
341 {
342 const Entry& entry = it->second;
343 mcd_calc.notify_impending_increase_or_remove(entry);
344 mcd_calc.notify_increased_or_removed(entry);
345 map.erase(it);
346 }
347
charge(Entry & entry,float delta)348 void charge(Entry& entry, float delta)
349 {
350 entry.credit -= delta * entry.size;
351
352 // don't worry about entry.size being 0 - if so, cost
353 // should also be 0, so credit will already be 0 anyway.
354 }
355
356 // for each entry, 'charge' it (i.e. reduce credit by) delta * its size.
357 // delta is typically MCD (see above); however, several such updates
358 // may be lumped together to save time. Landlord_Lazy does this.
charge_all(float delta)359 void charge_all(float delta)
360 {
361 for(MapIt it = map.begin(); it != map.end(); ++it)
362 {
363 Entry& entry = it->second;
364 entry.credit -= delta * entry.size;
365 if(!should_evict(entry))
366 mcd_calc.notify_decreased(entry);
367 }
368 }
369
370 // is entry's credit exhausted? if so, it should be evicted.
should_evict(const Entry & entry)371 bool should_evict(const Entry& entry)
372 {
373 // we need a bit of leeway because density calculations may not
374 // be exact. choose value carefully: must not be high enough to
375 // trigger false positives.
376 return entry.credit < 0.0001f;
377 }
378
379 private:
380 McdCalc<Entry, Map> mcd_calc;
381 };
382
383 // Cache manger policies. (these are partial specializations of Landlord,
384 // adapting it to the template params required by Cache)
385 template<class Key, class Entry> class Landlord_Naive : public Landlord<Key, Entry, McdCalc_Naive> {};
386 template<class Key, class Entry> class Landlord_Cached: public Landlord<Key, Entry, McdCalc_Cached> {};
387
388 // variant of Landlord that adds a priority queue to directly determine
389 // which entry to evict. this allows lumping several charge operations
390 // together and thus reduces iteration over all entries.
391 // tradeoff: O(logN) removal (instead of N), but additional O(N) storage.
392 template<typename Key, class Entry>
393 class Landlord_Lazy : public Landlord_Naive<Key, Entry>
394 {
395 typedef typename Landlord_Naive<Key, Entry>::Map Map;
396 typedef typename Landlord_Naive<Key, Entry>::MapIt MapIt;
397 typedef typename Landlord_Naive<Key, Entry>::MapCIt MapCIt;
398
399 public:
Landlord_Lazy()400 Landlord_Lazy() { pending_delta = 0.0f; }
401
add(const Key & key,const Entry & entry)402 void add(const Key& key, const Entry& entry)
403 {
404 // we must apply pending_delta now - otherwise, the existing delta
405 // would later be applied to this newly added item (incorrect).
406 commit_pending_delta();
407
408 MapIt it = Parent::add_(key, entry);
409 pri_q.push(it);
410 }
411
remove(const Key & key)412 void remove(const Key& key)
413 {
414 Parent::remove(key);
415
416 // reconstruct pri_q from current map. this is slow (N*logN) and
417 // could definitely be done better, but we don't bother since
418 // remove is a very rare operation (e.g. invalidating entries).
419 while(!pri_q.empty())
420 pri_q.pop();
421 for(MapCIt it = this->map.begin(); it != this->map.end(); ++it)
422 pri_q.push(it);
423 }
424
on_access(Entry & entry)425 void on_access(Entry& entry)
426 {
427 Parent::on_access(entry);
428
429 // entry's credit was changed. we now need to reshuffle the
430 // pri queue to reflect this.
431 pri_q.ensure_heap_order();
432 }
433
remove_least_valuable(std::list<Entry> & entry_list)434 void remove_least_valuable(std::list<Entry>& entry_list)
435 {
436 MapIt least_valuable_it = pri_q.top(); pri_q.pop();
437 Entry& entry = Map::entry_from_it(least_valuable_it);
438
439 entry_list.push_back(entry);
440
441 // add to pending_delta the MCD that would have resulted
442 // if removing least_valuable_it normally.
443 // first, calculate actual credit (i.e. apply pending_delta to
444 // this entry); then add the resulting density to pending_delta.
445 entry.credit -= pending_delta*entry.size;
446 const float credit_density = entry.credit_density();
447 ENSURE(credit_density > 0.0f);
448 pending_delta += credit_density;
449
450 Parent::remove_(least_valuable_it);
451 }
452
453 private:
454 typedef Landlord_Naive<Key, Entry> Parent;
455
456 // sort iterators by credit_density of the Entry they reference.
457 struct CD_greater
458 {
operatorCD_greater459 bool operator()(MapIt it1, MapIt it2) const
460 {
461 return Map::entry_from_it(it1).credit_density() >
462 Map::entry_from_it(it2).credit_density();
463 }
464 };
465 // wrapper on top of priority_queue that allows 'heap re-sift'
466 // (see on_access).
467 // notes:
468 // - greater comparator makes pri_q.top() the one with
469 // LEAST credit_density, which is what we want.
470 // - deriving from an STL container is a bit dirty, but we need this
471 // to get at the underlying data (priority_queue interface is not
472 // very capable).
473 class PriQ: public std::priority_queue<MapIt, std::vector<MapIt>, CD_greater>
474 {
475 public:
ensure_heap_order()476 void ensure_heap_order()
477 {
478 // TODO: this is actually N*logN - ouch! that explains high
479 // CPU cost in profile. this is called after only 1 item has
480 // changed, so a logN "sift" operation ought to suffice.
481 // that's not supported by the STL heap functions, so we'd
482 // need a better implementation. pending..
483 std::make_heap(this->c.begin(), this->c.end(), this->comp);
484 }
485 };
486 PriQ pri_q;
487
488 // delta values that have accumulated over several
489 // remove_least_valuable() calls. applied during add().
490 float pending_delta;
491
commit_pending_delta()492 void commit_pending_delta()
493 {
494 if(pending_delta > 0.0f)
495 {
496 this->charge_all(pending_delta);
497 pending_delta = 0.0f;
498
499 // we've changed entry credit, so the heap order *may* have been
500 // violated; reorder the pri queue. (I don't think so,
501 // due to definition of delta, but we'll play it safe)
502 pri_q.ensure_heap_order();
503 }
504 }
505 };
506
507
508 //
509 // functor that implements division of first arg by second
510 //
511
512 // this is used to calculate credit_density(); performance matters
513 // because this is called for each entry during each remove operation.
514
515 // floating-point division (fairly slow)
516 class Divider_Naive
517 {
518 public:
Divider_Naive()519 Divider_Naive() {} // needed for default CacheEntry ctor
Divider_Naive(float UNUSED (x))520 Divider_Naive(float UNUSED(x)) {}
operator()521 float operator()(float val, float divisor) const
522 {
523 return val / divisor;
524 }
525 };
526
527 // caches reciprocal of divisor and multiplies by that.
528 // tradeoff: only 4 clocks (instead of 20), but 4 bytes extra per entry.
529 class Divider_Recip
530 {
531 float recip;
532 public:
Divider_Recip()533 Divider_Recip() {} // needed for default CacheEntry ctor
Divider_Recip(float x)534 Divider_Recip(float x) { recip = 1.0f / x; }
operator()535 float operator()(float val, float UNUSED(divisor)) const
536 {
537 return val * recip;
538 }
539 };
540
541
542 // initial implementation for testing purposes; quite inefficient.
543 template<typename Key, typename Entry>
544 class LRU
545 {
546 public:
empty()547 bool empty() const
548 {
549 return lru.empty();
550 }
551
add(const Key & key,const Entry & entry)552 void add(const Key& key, const Entry& entry)
553 {
554 lru.push_back(KeyAndEntry(key, entry));
555 }
556
find(const Key & key,const Entry ** pentry)557 bool find(const Key& key, const Entry** pentry) const
558 {
559 CIt it = std::find(lru.begin(), lru.end(), KeyAndEntry(key));
560 if(it == lru.end())
561 return false;
562 *pentry = &it->entry;
563 return true;
564 }
565
remove(const Key & key)566 void remove(const Key& key)
567 {
568 lru.remove(KeyAndEntry(key));
569 }
570
on_access(Entry & entry)571 void on_access(Entry& entry)
572 {
573 for(It it = lru.begin(); it != lru.end(); ++it)
574 {
575 if(&entry == &it->entry)
576 {
577 add(it->key, it->entry);
578 lru.erase(it);
579 return;
580 }
581 }
582 DEBUG_WARN_ERR(ERR::LOGIC); // entry not found in list
583 }
584
remove_least_valuable(std::list<Entry> & entry_list)585 void remove_least_valuable(std::list<Entry>& entry_list)
586 {
587 entry_list.push_back(lru.front().entry);
588 lru.pop_front();
589 }
590
591 private:
592 struct KeyAndEntry
593 {
KeyAndEntryKeyAndEntry594 KeyAndEntry(const Key& key): key(key) {}
KeyAndEntryKeyAndEntry595 KeyAndEntry(const Key& key, const Entry& entry): key(key), entry(entry) {}
596
597 bool operator==(const KeyAndEntry& rhs) const { return key == rhs.key; }
598 bool operator!=(const KeyAndEntry& rhs) const { return !operator==(rhs); }
599
600 Key key;
601 Entry entry;
602 };
603
604 typedef std::list<KeyAndEntry> List;
605 typedef typename List::iterator It;
606 typedef typename List::const_iterator CIt;
607 List lru;
608 };
609
610
611 // this is applicable to all cache management policies and stores all
612 // required information. a Divider functor is used to implement
613 // division for credit_density.
614 template<class Item, class Divider> struct CacheEntry
615 {
616 Item item;
617 size_t size;
618 size_t cost;
619 float credit;
620
621 Divider divider;
622
623 // needed for mgr.remove_least_valuable's entry_copy
CacheEntryCacheEntry624 CacheEntry()
625 {
626 }
627
CacheEntryCacheEntry628 CacheEntry(const Item& item_, size_t size_, size_t cost_)
629 : item(item_), divider((float)size_)
630 {
631 size = size_;
632 cost = cost_;
633 credit = (float)cost;
634
635 // else divider will fail
636 ENSURE(size != 0);
637 }
638
credit_densityCacheEntry639 float credit_density() const
640 {
641 return divider(credit, (float)size);
642 }
643 };
644
645
646 //
647 // Cache
648 //
649
650 template
651 <
652 typename Key, typename Item,
653 // see documentation above for Manager's interface.
654 template<typename Key_, class Entry> class Manager = Landlord_Cached,
655 class Divider = Divider_Naive
656 >
657 class Cache
658 {
659 public:
Cache()660 Cache() : mgr() {}
661
add(const Key & key,const Item & item,size_t size,size_t cost)662 void add(const Key& key, const Item& item, size_t size, size_t cost)
663 {
664 return mgr.add(key, Entry(item, size, cost));
665 }
666
667 // remove the entry identified by <key>. expected usage is to check
668 // if present and determine size via retrieve(), so no need for
669 // error checking.
670 // useful for invalidating single cache entries.
remove(const Key & key)671 void remove(const Key& key)
672 {
673 mgr.remove(key);
674 }
675
676 // if there is no entry for <key> in the cache, return false.
677 // otherwise, return true and pass back item and (optionally) size.
678 //
679 // if refill_credit (default), the cache manager 'rewards' this entry,
680 // tending to keep it in cache longer. this parameter is not used in
681 // normal operation - it's only for special cases where we need to
682 // make an end run around the cache accounting (e.g. for cache simulator).
683 bool retrieve(const Key& key, Item& item, size_t* psize = 0, bool refill_credit = true)
684 {
685 const Entry* entry;
686 if(!mgr.find(key, &entry))
687 return false;
688
689 item = entry->item;
690 if(psize)
691 *psize = entry->size;
692
693 if(refill_credit)
694 mgr.on_access((Entry&)*entry);
695
696 return true;
697 }
698
699 bool peek(const Key& key, Item& item, size_t* psize = 0)
700 {
701 return retrieve(key, item, psize, false);
702 }
703
704 // toss out the least valuable entry. return false if cache is empty,
705 // otherwise true and (optionally) pass back its item and size.
706 bool remove_least_valuable(Item* pItem = 0, size_t* pSize = 0)
707 {
708 // as an artefact of the cache eviction policy, several entries
709 // may be "shaken loose" by one call to remove_least_valuable.
710 // we cache them in a list to disburden callers (they always get
711 // exactly one).
712 if(entries_awaiting_eviction.empty())
713 {
714 if(empty())
715 return false;
716
717 mgr.remove_least_valuable(entries_awaiting_eviction);
718 ENSURE(!entries_awaiting_eviction.empty());
719 }
720
721 const Entry& entry = entries_awaiting_eviction.front();
722 if(pItem)
723 *pItem = entry.item;
724 if(pSize)
725 *pSize = entry.size;
726 entries_awaiting_eviction.pop_front();
727
728 return true;
729 }
730
empty()731 bool empty() const
732 {
733 return mgr.empty();
734 }
735
736 private:
737 typedef CacheEntry<Item, Divider> Entry;
738
739 // see note in remove_least_valuable().
740 std::list<Entry> entries_awaiting_eviction;
741
742 Manager<Key, Entry> mgr;
743 };
744
745 #endif // #ifndef INCLUDED_CACHE_ADT
746