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