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 { EntryEntry22 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: SkLRUCache(int maxCount)33 explicit SkLRUCache(int maxCount) 34 : fMaxCount(maxCount) {} 35 ~SkLRUCache()36 ~SkLRUCache() { 37 Entry* node = fLRU.head(); 38 while (node) { 39 fLRU.remove(node); 40 delete node; 41 node = fLRU.head(); 42 } 43 } 44 find(const K & key)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 insert(const K & key,V value)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 count()68 int count() { 69 return fMap.count(); 70 } 71 72 template <typename Fn> // f(V*) foreach(Fn && fn)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 reset()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 { GetKeyTraits91 static const K& GetKey(Entry* e) { 92 return e->fKey; 93 } 94 HashTraits95 static uint32_t Hash(const K& k) { 96 return HashK()(k); 97 } 98 }; 99 remove(const K & key)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