LCOV - code coverage report
Current view: top level - source/lib/adts - cache_adt.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 10 10 100.0 %
Date: 2023-01-19 00:18:29 Functions: 46 46 100.0 %

          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

Generated by: LCOV version 1.13