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