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