Line data    Source code

       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           0 :     struct Entry {
      22           0 :         Entry(const K& key, V&& value)
      23             :         : fKey(key)
      24           0 :         , fValue(std::move(value)) {}
      25             : 
      26             :         K fKey;
      27             :         V fValue;
      28             : 
      29             :         SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry);
      30             :     };
      31             : 
      32             : public:
      33           0 :     explicit SkLRUCache(int maxCount)
      34           0 :     : fMaxCount(maxCount) {}
      35             : 
      36           0 :     ~SkLRUCache() {
      37           0 :         Entry* node = fLRU.head();
      38           0 :         while (node) {
      39           0 :             fLRU.remove(node);
      40           0 :             delete node;
      41           0 :             node = fLRU.head();
      42             :         }
      43           0 :     }
      44             : 
      45           0 :     V* find(const K& key) {
      46           0 :         Entry** value = fMap.find(key);
      47           0 :         if (!value) {
      48           0 :             return nullptr;
      49             :         }
      50           0 :         Entry* entry = *value;
      51           0 :         if (entry != fLRU.head()) {
      52           0 :             fLRU.remove(entry);
      53           0 :             fLRU.addToHead(entry);
      54             :         } // else it's already at head position, don't need to do anything
      55           0 :         return &entry->fValue;
      56             :     }
      57             : 
      58           0 :     V* insert(const K& key, V value) {
      59           0 :         Entry* entry = new Entry(key, std::move(value));
      60           0 :         fMap.set(entry);
      61           0 :         fLRU.addToHead(entry);
      62           0 :         while (fMap.count() > fMaxCount) {
      63           0 :             this->remove(fLRU.tail()->fKey);
      64             :         }
      65           0 :         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           0 :         static const K& GetKey(Entry* e) {
      92           0 :             return e->fKey;
      93             :         }
      94             : 
      95           0 :         static uint32_t Hash(const K& k) {
      96           0 :             return HashK()(k);
      97             :         }
      98             :     };
      99             : 
     100           0 :     void remove(const K& key) {
     101           0 :         Entry** value = fMap.find(key);
     102           0 :         SkASSERT(value);
     103           0 :         Entry* entry = *value;
     104           0 :         SkASSERT(key == entry->fKey);
     105           0 :         fMap.remove(key);
     106           0 :         fLRU.remove(entry);
     107           0 :         delete entry;
     108           0 :     }
     109             : 
     110             :     int                             fMaxCount;
     111             :     SkTHashTable<Entry*, K, Traits> fMap;
     112             :     SkTInternalLList<Entry>         fLRU;
     113             : };
     114             : 
     115             : #endif