1 /*
2 * Copyright (C) 2010 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_GENERATION_CACHE_H
18 #define ANDROID_UTILS_GENERATION_CACHE_H
19
20 #include <utils/KeyedVector.h>
21 #include <utils/RefBase.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 EntryKey, typename EntryValue>
36 struct Entry: public LightRefBase<Entry<EntryKey, EntryValue> > {
EntryEntry37 Entry(const Entry<EntryKey, EntryValue>& e) :
38 key(e.key), value(e.value),
39 parent(e.parent), child(e.child) { }
EntryEntry40 Entry(const EntryKey& key, const EntryValue& value) :
41 key(key), value(value) { }
42
43 EntryKey key;
44 EntryValue value;
45
46 sp<Entry<EntryKey, EntryValue> > parent; // next older entry
47 sp<Entry<EntryKey, EntryValue> > child; // next younger entry
48 }; // struct Entry
49
50 /**
51 * A LRU type cache
52 */
53 template<typename K, typename V>
54 class GenerationCache {
55 public:
56 GenerationCache(uint32_t maxCapacity);
57 virtual ~GenerationCache();
58
59 enum Capacity {
60 kUnlimitedCapacity,
61 };
62
63 void setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener);
64
65 size_t size() const;
66
67 void clear();
68
69 bool contains(const K& key) const;
70 const K& getKeyAt(size_t index) const;
71 const V& getValueAt(size_t index) const;
72
73 const V& get(const K& key);
74 bool put(const K& key, const V& value);
75
76 void removeAt(ssize_t index);
77 bool remove(const K& key);
78 bool removeOldest();
79
80 private:
81 KeyedVector<K, sp<Entry<K, V> > > mCache;
82 uint32_t mMaxCapacity;
83
84 OnEntryRemoved<K, V>* mListener;
85
86 sp<Entry<K, V> > mOldest;
87 sp<Entry<K, V> > mYoungest;
88
89 void attachToCache(const sp<Entry<K, V> >& entry);
90 void detachFromCache(const sp<Entry<K, V> >& entry);
91
92 const V mNullValue;
93 }; // class GenerationCache
94
95 template<typename K, typename V>
GenerationCache(uint32_t maxCapacity)96 GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
97 mListener(NULL), mNullValue(NULL) {
98 };
99
100 template<typename K, typename V>
~GenerationCache()101 GenerationCache<K, V>::~GenerationCache() {
102 clear();
103 };
104
105 template<typename K, typename V>
size()106 uint32_t GenerationCache<K, V>::size() const {
107 return mCache.size();
108 }
109
110 /**
111 * Should be set by the user of the Cache so that the callback is called whenever an item is
112 * removed from the cache
113 */
114 template<typename K, typename V>
setOnEntryRemovedListener(OnEntryRemoved<K,V> * listener)115 void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
116 mListener = listener;
117 }
118
119 template<typename K, typename V>
clear()120 void GenerationCache<K, V>::clear() {
121 if (mListener) {
122 for (uint32_t i = 0; i < mCache.size(); i++) {
123 sp<Entry<K, V> > entry = mCache.valueAt(i);
124 if (mListener) {
125 (*mListener)(entry->key, entry->value);
126 }
127 }
128 }
129 mCache.clear();
130 mYoungest.clear();
131 mOldest.clear();
132 }
133
134 template<typename K, typename V>
contains(const K & key)135 bool GenerationCache<K, V>::contains(const K& key) const {
136 return mCache.indexOfKey(key) >= 0;
137 }
138
139 template<typename K, typename V>
getKeyAt(size_t index)140 const K& GenerationCache<K, V>::getKeyAt(size_t index) const {
141 return mCache.keyAt(index);
142 }
143
144 template<typename K, typename V>
getValueAt(size_t index)145 const V& GenerationCache<K, V>::getValueAt(size_t index) const {
146 return mCache.valueAt(index)->value;
147 }
148
149 template<typename K, typename V>
get(const K & key)150 const V& GenerationCache<K, V>::get(const K& key) {
151 ssize_t index = mCache.indexOfKey(key);
152 if (index >= 0) {
153 const sp<Entry<K, V> >& entry = mCache.valueAt(index);
154 detachFromCache(entry);
155 attachToCache(entry);
156 return entry->value;
157 }
158
159 return mNullValue;
160 }
161
162 template<typename K, typename V>
put(const K & key,const V & value)163 bool GenerationCache<K, V>::put(const K& key, const V& value) {
164 if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) {
165 removeOldest();
166 }
167
168 ssize_t index = mCache.indexOfKey(key);
169 if (index < 0) {
170 sp<Entry<K, V> > entry = new Entry<K, V>(key, value);
171 mCache.add(key, entry);
172 attachToCache(entry);
173 return true;
174 }
175
176 return false;
177 }
178
179 template<typename K, typename V>
remove(const K & key)180 bool GenerationCache<K, V>::remove(const K& key) {
181 ssize_t index = mCache.indexOfKey(key);
182 if (index >= 0) {
183 removeAt(index);
184 return true;
185 }
186
187 return false;
188 }
189
190 template<typename K, typename V>
removeAt(ssize_t index)191 void GenerationCache<K, V>::removeAt(ssize_t index) {
192 sp<Entry<K, V> > entry = mCache.valueAt(index);
193 if (mListener) {
194 (*mListener)(entry->key, entry->value);
195 }
196 mCache.removeItemsAt(index, 1);
197 detachFromCache(entry);
198 }
199
200 template<typename K, typename V>
removeOldest()201 bool GenerationCache<K, V>::removeOldest() {
202 if (mOldest.get()) {
203 ssize_t index = mCache.indexOfKey(mOldest->key);
204 if (index >= 0) {
205 removeAt(index);
206 return true;
207 }
208 ALOGE("GenerationCache: removeOldest failed to find the item in the cache "
209 "with the given key, but we know it must be in there. "
210 "Is the key comparator kaput?");
211 }
212
213 return false;
214 }
215
216 template<typename K, typename V>
attachToCache(const sp<Entry<K,V>> & entry)217 void GenerationCache<K, V>::attachToCache(const sp<Entry<K, V> >& entry) {
218 if (!mYoungest.get()) {
219 mYoungest = mOldest = entry;
220 } else {
221 entry->parent = mYoungest;
222 mYoungest->child = entry;
223 mYoungest = entry;
224 }
225 }
226
227 template<typename K, typename V>
detachFromCache(const sp<Entry<K,V>> & entry)228 void GenerationCache<K, V>::detachFromCache(const sp<Entry<K, V> >& entry) {
229 if (entry->parent.get()) {
230 entry->parent->child = entry->child;
231 } else {
232 mOldest = entry->child;
233 }
234
235 if (entry->child.get()) {
236 entry->child->parent = entry->parent;
237 } else {
238 mYoungest = entry->parent;
239 }
240
241 entry->parent.clear();
242 entry->child.clear();
243 }
244
245 }; // namespace android
246
247 #endif // ANDROID_UTILS_GENERATION_CACHE_H
248