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 <UniquePtr.h>
21 #include <utils/BasicHashtable.h>
22
23 namespace android {
24
25 /**
26 * GenerationCache callback used when an item is removed
27 */
28 template<typename EntryKey, typename EntryValue>
29 class OnEntryRemoved {
30 public:
~OnEntryRemoved()31 virtual ~OnEntryRemoved() { };
32 virtual void operator()(EntryKey& key, EntryValue& value) = 0;
33 }; // class OnEntryRemoved
34
35 template <typename TKey, typename TValue>
36 class LruCache {
37 public:
38 explicit LruCache(uint32_t maxCapacity);
39
40 enum Capacity {
41 kUnlimitedCapacity,
42 };
43
44 void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
45 size_t size() const;
46 const TValue& get(const TKey& key);
47 bool put(const TKey& key, const TValue& value);
48 bool remove(const TKey& key);
49 bool removeOldest();
50 void clear();
51 const TValue& peekOldestValue();
52
53 class Iterator {
54 public:
Iterator(const LruCache<TKey,TValue> & cache)55 Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
56 }
57
next()58 bool next() {
59 mIndex = mCache.mTable->next(mIndex);
60 return (ssize_t)mIndex != -1;
61 }
62
index()63 size_t index() const {
64 return mIndex;
65 }
66
value()67 const TValue& value() const {
68 return mCache.mTable->entryAt(mIndex).value;
69 }
70
key()71 const TKey& key() const {
72 return mCache.mTable->entryAt(mIndex).key;
73 }
74 private:
75 const LruCache<TKey, TValue>& mCache;
76 size_t mIndex;
77 };
78
79 private:
80 LruCache(const LruCache& that); // disallow copy constructor
81
82 struct Entry {
83 TKey key;
84 TValue value;
85 Entry* parent;
86 Entry* child;
87
EntryEntry88 Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
89 }
getKeyEntry90 const TKey& getKey() const { return key; }
91 };
92
93 void attachToCache(Entry& entry);
94 void detachFromCache(Entry& entry);
95 void rehash(size_t newCapacity);
96
97 UniquePtr<BasicHashtable<TKey, Entry> > mTable;
98 OnEntryRemoved<TKey, TValue>* mListener;
99 Entry* mOldest;
100 Entry* mYoungest;
101 uint32_t mMaxCapacity;
102 TValue mNullValue;
103 };
104
105 // Implementation is here, because it's fully templated
106 template <typename TKey, typename TValue>
LruCache(uint32_t maxCapacity)107 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
108 : mTable(new BasicHashtable<TKey, Entry>)
109 , mListener(NULL)
110 , mOldest(NULL)
111 , mYoungest(NULL)
112 , mMaxCapacity(maxCapacity)
113 , mNullValue(NULL) {
114 };
115
116 template<typename K, typename V>
setOnEntryRemovedListener(OnEntryRemoved<K,V> * listener)117 void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
118 mListener = listener;
119 }
120
121 template <typename TKey, typename TValue>
size()122 size_t LruCache<TKey, TValue>::size() const {
123 return mTable->size();
124 }
125
126 template <typename TKey, typename TValue>
get(const TKey & key)127 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
128 hash_t hash = hash_type(key);
129 ssize_t index = mTable->find(-1, hash, key);
130 if (index == -1) {
131 return mNullValue;
132 }
133 Entry& entry = mTable->editEntryAt(index);
134 detachFromCache(entry);
135 attachToCache(entry);
136 return entry.value;
137 }
138
139 template <typename TKey, typename TValue>
put(const TKey & key,const TValue & value)140 bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
141 if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
142 removeOldest();
143 }
144
145 hash_t hash = hash_type(key);
146 ssize_t index = mTable->find(-1, hash, key);
147 if (index >= 0) {
148 return false;
149 }
150 if (!mTable->hasMoreRoom()) {
151 rehash(mTable->capacity() * 2);
152 }
153
154 // Would it be better to initialize a blank entry and assign key, value?
155 Entry initEntry(key, value);
156 index = mTable->add(hash, initEntry);
157 Entry& entry = mTable->editEntryAt(index);
158 attachToCache(entry);
159 return true;
160 }
161
162 template <typename TKey, typename TValue>
remove(const TKey & key)163 bool LruCache<TKey, TValue>::remove(const TKey& key) {
164 hash_t hash = hash_type(key);
165 ssize_t index = mTable->find(-1, hash, key);
166 if (index < 0) {
167 return false;
168 }
169 Entry& entry = mTable->editEntryAt(index);
170 if (mListener) {
171 (*mListener)(entry.key, entry.value);
172 }
173 detachFromCache(entry);
174 mTable->removeAt(index);
175 return true;
176 }
177
178 template <typename TKey, typename TValue>
removeOldest()179 bool LruCache<TKey, TValue>::removeOldest() {
180 if (mOldest != NULL) {
181 return remove(mOldest->key);
182 // TODO: should probably abort if false
183 }
184 return false;
185 }
186
187 template <typename TKey, typename TValue>
peekOldestValue()188 const TValue& LruCache<TKey, TValue>::peekOldestValue() {
189 if (mOldest) {
190 return mOldest->value;
191 }
192 return mNullValue;
193 }
194
195 template <typename TKey, typename TValue>
clear()196 void LruCache<TKey, TValue>::clear() {
197 if (mListener) {
198 for (Entry* p = mOldest; p != NULL; p = p->child) {
199 (*mListener)(p->key, p->value);
200 }
201 }
202 mYoungest = NULL;
203 mOldest = NULL;
204 mTable->clear();
205 }
206
207 template <typename TKey, typename TValue>
attachToCache(Entry & entry)208 void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
209 if (mYoungest == NULL) {
210 mYoungest = mOldest = &entry;
211 } else {
212 entry.parent = mYoungest;
213 mYoungest->child = &entry;
214 mYoungest = &entry;
215 }
216 }
217
218 template <typename TKey, typename TValue>
detachFromCache(Entry & entry)219 void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
220 if (entry.parent != NULL) {
221 entry.parent->child = entry.child;
222 } else {
223 mOldest = entry.child;
224 }
225 if (entry.child != NULL) {
226 entry.child->parent = entry.parent;
227 } else {
228 mYoungest = entry.parent;
229 }
230
231 entry.parent = NULL;
232 entry.child = NULL;
233 }
234
235 template <typename TKey, typename TValue>
rehash(size_t newCapacity)236 void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
237 UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
238 Entry* oldest = mOldest;
239
240 mOldest = NULL;
241 mYoungest = NULL;
242 mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
243 for (Entry* p = oldest; p != NULL; p = p->child) {
244 put(p->key, p->value);
245 }
246 }
247
248 }
249
250 #endif // ANDROID_UTILS_LRU_CACHE_H
251