Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2016 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #ifndef SkLRUCache_DEFINED
      9 #define SkLRUCache_DEFINED
     10 
     11 #include "SkChecksum.h"
     12 #include "SkTHash.h"
     13 #include "SkTInternalLList.h"
     14 
     15 /**
     16  * A generic LRU cache.
     17  */
     18 template <typename K, typename V, typename HashK = SkGoodHash>
     19 class SkLRUCache : public SkNoncopyable {
     20 private:
     21     struct Entry {
     22         Entry(const K& key, V&& value)
     23         : fKey(key)
     24         , fValue(std::move(value)) {}
     25 
     26         K fKey;
     27         V fValue;
     28 
     29         SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry);
     30     };
     31 
     32 public:
     33     explicit SkLRUCache(int maxCount)
     34     : fMaxCount(maxCount) {}
     35 
     36     ~SkLRUCache() {
     37         Entry* node = fLRU.head();
     38         while (node) {
     39             fLRU.remove(node);
     40             delete node;
     41             node = fLRU.head();
     42         }
     43     }
     44 
     45     V* find(const K& key) {
     46         Entry** value = fMap.find(key);
     47         if (!value) {
     48             return nullptr;
     49         }
     50         Entry* entry = *value;
     51         if (entry != fLRU.head()) {
     52             fLRU.remove(entry);
     53             fLRU.addToHead(entry);
     54         } // else it's already at head position, don't need to do anything
     55         return &entry->fValue;
     56     }
     57 
     58     V* insert(const K& key, V value) {
     59         Entry* entry = new Entry(key, std::move(value));
     60         fMap.set(entry);
     61         fLRU.addToHead(entry);
     62         while (fMap.count() > fMaxCount) {
     63             this->remove(fLRU.tail()->fKey);
     64         }
     65         return &entry->fValue;
     66     }
     67 
     68     int count() {
     69         return fMap.count();
     70     }
     71 
     72     template <typename Fn>  // f(V*)
     73     void foreach(Fn&& fn) {
     74         typename SkTInternalLList<Entry>::Iter iter;
     75         for (Entry* e = iter.init(fLRU, SkTInternalLList<Entry>::Iter::kHead_IterStart); e;
     76              e = iter.next()) {
     77             fn(&e->fValue);
     78         }
     79     }
     80 
     81     void reset() {
     82         fMap.reset();
     83         for (Entry* e = fLRU.head(); e; e = fLRU.head()) {
     84             fLRU.remove(e);
     85             delete e;
     86         }
     87     }
     88 
     89 private:
     90     struct Traits {
     91         static const K& GetKey(Entry* e) {
     92             return e->fKey;
     93         }
     94 
     95         static uint32_t Hash(const K& k) {
     96             return HashK()(k);
     97         }
     98     };
     99 
    100     void remove(const K& key) {
    101         Entry** value = fMap.find(key);
    102         SkASSERT(value);
    103         Entry* entry = *value;
    104         SkASSERT(key == entry->fKey);
    105         fMap.remove(key);
    106         fLRU.remove(entry);
    107         delete entry;
    108     }
    109 
    110     int                             fMaxCount;
    111     SkTHashTable<Entry*, K, Traits> fMap;
    112     SkTInternalLList<Entry>         fLRU;
    113 };
    114 
    115 #endif
    116