1 /*
2  * Copyright (C) 2012 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef ANDROID_UTILS_LRU_CACHE_H
18 #define ANDROID_UTILS_LRU_CACHE_H
19 
20 #include <memory>
21 #include <unordered_set>
22 
23 #include "utils/TypeHelpers.h"  // hash_t
24 
25 namespace android {
26 
27 /**
28  * GenerationCache callback used when an item is removed
29  */
30 template<typename EntryKey, typename EntryValue>
31 class OnEntryRemoved {
32 public:
~OnEntryRemoved()33     virtual ~OnEntryRemoved() { };
34     virtual void operator()(EntryKey& key, EntryValue& value) = 0;
35 }; // class OnEntryRemoved
36 
37 template <typename TKey, typename TValue>
38 class LruCache {
39 public:
40     explicit LruCache(uint32_t maxCapacity);
41     virtual ~LruCache();
42 
43     enum Capacity {
44         kUnlimitedCapacity,
45     };
46 
47     void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
48     size_t size() const;
49     const TValue& get(const TKey& key);
50     bool put(const TKey& key, const TValue& value);
51     bool remove(const TKey& key);
52     bool removeOldest();
53     void clear();
54     const TValue& peekOldestValue();
55 
56 private:
57     LruCache(const LruCache& that);  // disallow copy constructor
58 
59     struct Entry {
60         TKey key;
61         TValue value;
62         Entry* parent;
63         Entry* child;
64 
EntryEntry65         Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
66         }
getKeyEntry67         const TKey& getKey() const { return key; }
68     };
69 
70     struct HashForEntry : public std::unary_function<Entry*, hash_t> {
operatorHashForEntry71         size_t operator() (const Entry* entry) const {
72             return hash_type(entry->key);
73         };
74     };
75 
76     struct EqualityForHashedEntries : public std::unary_function<Entry*, hash_t> {
operatorEqualityForHashedEntries77         bool operator() (const Entry* lhs, const Entry* rhs) const {
78             return lhs->key == rhs->key;
79         };
80     };
81 
82     typedef std::unordered_set<Entry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
83 
84     void attachToCache(Entry& entry);
85     void detachFromCache(Entry& entry);
86 
findByKey(const TKey & key)87     typename LruCacheSet::iterator findByKey(const TKey& key) {
88         Entry entryForSearch(key, mNullValue);
89         typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
90         return result;
91     }
92 
93     std::unique_ptr<LruCacheSet> mSet;
94     OnEntryRemoved<TKey, TValue>* mListener;
95     Entry* mOldest;
96     Entry* mYoungest;
97     uint32_t mMaxCapacity;
98     TValue mNullValue;
99 
100 public:
101     // To be used like:
102     // while (it.next()) {
103     //   it.value(); it.key();
104     // }
105     class Iterator {
106     public:
Iterator(const LruCache<TKey,TValue> & cache)107         Iterator(const LruCache<TKey, TValue>& cache):
108                 mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) {
109         }
110 
next()111         bool next() {
112             if (mIterator == mCache.mSet->end()) {
113                 return false;
114             }
115             if (!mBeginReturned) {
116                 // mIterator has been initialized to the beginning and
117                 // hasn't been returned. Do not advance:
118                 mBeginReturned = true;
119             } else {
120                 std::advance(mIterator, 1);
121             }
122             bool ret = (mIterator != mCache.mSet->end());
123             return ret;
124         }
125 
value()126         const TValue& value() const {
127             return (*mIterator)->value;
128         }
129 
key()130         const TKey& key() const {
131             return (*mIterator)->key;
132         }
133     private:
134         const LruCache<TKey, TValue>& mCache;
135         typename LruCacheSet::iterator mIterator;
136         bool mBeginReturned;
137     };
138 };
139 
140 // Implementation is here, because it's fully templated
141 template <typename TKey, typename TValue>
LruCache(uint32_t maxCapacity)142 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
143     : mSet(new LruCacheSet())
144     , mListener(NULL)
145     , mOldest(NULL)
146     , mYoungest(NULL)
147     , mMaxCapacity(maxCapacity)
148     , mNullValue(NULL) {
149     mSet->max_load_factor(1.0);
150 };
151 
152 template <typename TKey, typename TValue>
~LruCache()153 LruCache<TKey, TValue>::~LruCache() {
154     // Need to delete created entries.
155     clear();
156 };
157 
158 template<typename K, typename V>
setOnEntryRemovedListener(OnEntryRemoved<K,V> * listener)159 void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
160     mListener = listener;
161 }
162 
163 template <typename TKey, typename TValue>
size()164 size_t LruCache<TKey, TValue>::size() const {
165     return mSet->size();
166 }
167 
168 template <typename TKey, typename TValue>
get(const TKey & key)169 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
170     typename LruCacheSet::const_iterator find_result = findByKey(key);
171     if (find_result == mSet->end()) {
172         return mNullValue;
173     }
174     Entry *entry = *find_result;
175     detachFromCache(*entry);
176     attachToCache(*entry);
177     return entry->value;
178 }
179 
180 template <typename TKey, typename TValue>
put(const TKey & key,const TValue & value)181 bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
182     if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
183         removeOldest();
184     }
185 
186     if (findByKey(key) != mSet->end()) {
187         return false;
188     }
189 
190     Entry* newEntry = new Entry(key, value);
191     mSet->insert(newEntry);
192     attachToCache(*newEntry);
193     return true;
194 }
195 
196 template <typename TKey, typename TValue>
remove(const TKey & key)197 bool LruCache<TKey, TValue>::remove(const TKey& key) {
198     typename LruCacheSet::const_iterator find_result = findByKey(key);
199     if (find_result == mSet->end()) {
200         return false;
201     }
202     Entry* entry = *find_result;
203     mSet->erase(entry);
204     if (mListener) {
205         (*mListener)(entry->key, entry->value);
206     }
207     detachFromCache(*entry);
208     delete entry;
209     return true;
210 }
211 
212 template <typename TKey, typename TValue>
removeOldest()213 bool LruCache<TKey, TValue>::removeOldest() {
214     if (mOldest != NULL) {
215         return remove(mOldest->key);
216         // TODO: should probably abort if false
217     }
218     return false;
219 }
220 
221 template <typename TKey, typename TValue>
peekOldestValue()222 const TValue& LruCache<TKey, TValue>::peekOldestValue() {
223     if (mOldest) {
224         return mOldest->value;
225     }
226     return mNullValue;
227 }
228 
229 template <typename TKey, typename TValue>
clear()230 void LruCache<TKey, TValue>::clear() {
231     if (mListener) {
232         for (Entry* p = mOldest; p != NULL; p = p->child) {
233             (*mListener)(p->key, p->value);
234         }
235     }
236     mYoungest = NULL;
237     mOldest = NULL;
238     for (auto entry : *mSet.get()) {
239         delete entry;
240     }
241     mSet->clear();
242 }
243 
244 template <typename TKey, typename TValue>
attachToCache(Entry & entry)245 void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
246     if (mYoungest == NULL) {
247         mYoungest = mOldest = &entry;
248     } else {
249         entry.parent = mYoungest;
250         mYoungest->child = &entry;
251         mYoungest = &entry;
252     }
253 }
254 
255 template <typename TKey, typename TValue>
detachFromCache(Entry & entry)256 void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
257     if (entry.parent != NULL) {
258         entry.parent->child = entry.child;
259     } else {
260         mOldest = entry.child;
261     }
262     if (entry.child != NULL) {
263         entry.child->parent = entry.parent;
264     } else {
265         mYoungest = entry.parent;
266     }
267 
268     entry.parent = NULL;
269     entry.child = NULL;
270 }
271 
272 }
273 #endif // ANDROID_UTILS_LRU_CACHE_H
274