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 "include/private/SkTHash.h" 13 #include "src/core/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 SkASSERT(!this->find(key)); 60 61 Entry* entry = new Entry(key, std::move(value)); 62 fMap.set(entry); 63 fLRU.addToHead(entry); 64 while (fMap.count() > fMaxCount) { 65 this->remove(fLRU.tail()->fKey); 66 } 67 return &entry->fValue; 68 } 69 insert_or_update(const K & key,V value)70 V* insert_or_update(const K& key, V value) { 71 if (V* found = this->find(key)) { 72 *found = std::move(value); 73 return found; 74 } else { 75 return this->insert(key, std::move(value)); 76 } 77 } 78 count()79 int count() { 80 return fMap.count(); 81 } 82 83 template <typename Fn> // f(K*, V*) foreach(Fn && fn)84 void foreach(Fn&& fn) { 85 typename SkTInternalLList<Entry>::Iter iter; 86 for (Entry* e = iter.init(fLRU, SkTInternalLList<Entry>::Iter::kHead_IterStart); e; 87 e = iter.next()) { 88 fn(&e->fKey, &e->fValue); 89 } 90 } 91 reset()92 void reset() { 93 fMap.reset(); 94 for (Entry* e = fLRU.head(); e; e = fLRU.head()) { 95 fLRU.remove(e); 96 delete e; 97 } 98 } 99 100 private: 101 struct Traits { GetKeyTraits102 static const K& GetKey(Entry* e) { 103 return e->fKey; 104 } 105 HashTraits106 static uint32_t Hash(const K& k) { 107 return HashK()(k); 108 } 109 }; 110 remove(const K & key)111 void remove(const K& key) { 112 Entry** value = fMap.find(key); 113 SkASSERT(value); 114 Entry* entry = *value; 115 SkASSERT(key == entry->fKey); 116 fMap.remove(key); 117 fLRU.remove(entry); 118 delete entry; 119 } 120 121 int fMaxCount; 122 SkTHashTable<Entry*, K, Traits> fMap; 123 SkTInternalLList<Entry> fLRU; 124 }; 125 126 #endif 127