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 "src/base/SkTInternalLList.h" 12 #include "src/core/SkChecksum.h" 13 #include "src/core/SkTHash.h" 14 15 struct SkNoOpPurge { 16 template <typename K, typename V> operatorSkNoOpPurge17 void operator()(const K& /* k */, const V* /* v */) const {} 18 }; 19 20 /** 21 * A generic LRU cache. 22 */ 23 template <typename K, typename V, typename HashK = SkGoodHash, typename PurgeCB = SkNoOpPurge> 24 class SkLRUCache { 25 private: 26 struct Entry { EntryEntry27 Entry(const K& key, V&& value) 28 : fKey(key) 29 , fValue(std::move(value)) {} 30 31 K fKey; 32 V fValue; 33 34 SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry); 35 }; 36 37 public: SkLRUCache(int maxCount)38 explicit SkLRUCache(int maxCount) : fMaxCount(maxCount) {} 39 SkLRUCache() = delete; 40 ~SkLRUCache()41 ~SkLRUCache() { 42 Entry* node = fLRU.head(); 43 while (node) { 44 fLRU.remove(node); 45 delete node; 46 node = fLRU.head(); 47 } 48 } 49 50 // Make noncopyable 51 SkLRUCache(const SkLRUCache&) = delete; 52 SkLRUCache& operator=(const SkLRUCache&) = delete; 53 find(const K & key)54 V* find(const K& key) { 55 Entry** value = fMap.find(key); 56 if (!value) { 57 return nullptr; 58 } 59 Entry* entry = *value; 60 if (entry != fLRU.head()) { 61 fLRU.remove(entry); 62 fLRU.addToHead(entry); 63 } // else it's already at head position, don't need to do anything 64 return &entry->fValue; 65 } 66 insert(const K & key,V value)67 V* insert(const K& key, V value) { 68 SkASSERT(!this->find(key)); 69 70 Entry* entry = new Entry(key, std::move(value)); 71 fMap.set(entry); 72 fLRU.addToHead(entry); 73 while (fMap.count() > fMaxCount) { 74 this->remove(fLRU.tail()->fKey); 75 } 76 return &entry->fValue; 77 } 78 insert_or_update(const K & key,V value)79 V* insert_or_update(const K& key, V value) { 80 if (V* found = this->find(key)) { 81 *found = std::move(value); 82 return found; 83 } else { 84 return this->insert(key, std::move(value)); 85 } 86 } 87 count()88 int count() const { 89 return fMap.count(); 90 } 91 92 template <typename Fn> // f(K*, V*) foreach(Fn && fn)93 void foreach(Fn&& fn) { 94 typename SkTInternalLList<Entry>::Iter iter; 95 for (Entry* e = iter.init(fLRU, SkTInternalLList<Entry>::Iter::kHead_IterStart); e; 96 e = iter.next()) { 97 fn(&e->fKey, &e->fValue); 98 } 99 } 100 reset()101 void reset() { 102 fMap.reset(); 103 for (Entry* e = fLRU.head(); e; e = fLRU.head()) { 104 fLRU.remove(e); 105 delete e; 106 } 107 } 108 remove(const K & key)109 void remove(const K& key) { 110 Entry** value = fMap.find(key); 111 SkASSERT(value); 112 Entry* entry = *value; 113 SkASSERT(key == entry->fKey); 114 PurgeCB()(key, &entry->fValue); 115 fMap.remove(key); 116 fLRU.remove(entry); 117 delete entry; 118 } 119 120 private: 121 struct Traits { GetKeyTraits122 static const K& GetKey(Entry* e) { 123 return e->fKey; 124 } 125 HashTraits126 static uint32_t Hash(const K& k) { 127 return HashK()(k); 128 } 129 }; 130 131 int fMaxCount; 132 skia_private::THashTable<Entry*, K, Traits> fMap; 133 SkTInternalLList<Entry> fLRU; 134 }; 135 136 #endif 137