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() { }
EntryEntry38 Entry(const Entry<EntryKey, EntryValue>& e):
39 key(e.key), value(e.value), parent(e.parent), child(e.child) { }
EntryEntry40 Entry(sp<Entry<EntryKey, EntryValue> > e):
41 key(e->key), value(e->value), parent(e->parent), child(e->child) { }
42
43 EntryKey key;
44 EntryValue value;
45
46 sp<Entry<EntryKey, EntryValue> > parent;
47 sp<Entry<EntryKey, EntryValue> > child;
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 void clear();
66
67 bool contains(K key) const;
68 V get(K key);
69 K getKeyAt(uint32_t index) const;
70 bool put(K key, V value);
71 V remove(K key);
72 V removeOldest();
73 V getValueAt(uint32_t index) const;
74
75 uint32_t size() const;
76
77 void addToCache(sp<Entry<K, V> > entry, K key, V value);
78 void attachToCache(sp<Entry<K, V> > entry);
79 void detachFromCache(sp<Entry<K, V> > entry);
80
81 V removeAt(ssize_t index);
82
83 private:
84 KeyedVector<K, sp<Entry<K, V> > > mCache;
85 uint32_t mMaxCapacity;
86
87 OnEntryRemoved<K, V>* mListener;
88
89 sp<Entry<K, V> > mOldest;
90 sp<Entry<K, V> > mYoungest;
91 }; // class GenerationCache
92
93 template<typename K, typename V>
GenerationCache(uint32_t maxCapacity)94 GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
95 mListener(NULL) {
96 };
97
98 template<typename K, typename V>
~GenerationCache()99 GenerationCache<K, V>::~GenerationCache() {
100 clear();
101 };
102
103 template<typename K, typename V>
size()104 uint32_t GenerationCache<K, V>::size() const {
105 return mCache.size();
106 }
107
108 /**
109 * Should be set by the user of the Cache so that the callback is called whenever an item is
110 * removed from the cache
111 */
112 template<typename K, typename V>
setOnEntryRemovedListener(OnEntryRemoved<K,V> * listener)113 void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
114 mListener = listener;
115 }
116
117 template<typename K, typename V>
clear()118 void GenerationCache<K, V>::clear() {
119 if (mListener) {
120 for (uint32_t i = 0; i < mCache.size(); i++) {
121 sp<Entry<K, V> > entry = mCache.valueAt(i);
122 if (mListener) {
123 (*mListener)(entry->key, entry->value);
124 }
125 }
126 }
127 mCache.clear();
128 mYoungest.clear();
129 mOldest.clear();
130 }
131
132 template<typename K, typename V>
contains(K key)133 bool GenerationCache<K, V>::contains(K key) const {
134 return mCache.indexOfKey(key) >= 0;
135 }
136
137 template<typename K, typename V>
getKeyAt(uint32_t index)138 K GenerationCache<K, V>::getKeyAt(uint32_t index) const {
139 return mCache.keyAt(index);
140 }
141
142 template<typename K, typename V>
getValueAt(uint32_t index)143 V GenerationCache<K, V>::getValueAt(uint32_t index) const {
144 return mCache.valueAt(index)->value;
145 }
146
147 template<typename K, typename V>
get(K key)148 V GenerationCache<K, V>::get(K key) {
149 ssize_t index = mCache.indexOfKey(key);
150 if (index >= 0) {
151 sp<Entry<K, V> > entry = mCache.valueAt(index);
152 if (entry.get()) {
153 detachFromCache(entry);
154 attachToCache(entry);
155 return entry->value;
156 }
157 }
158
159 return NULL;
160 }
161
162 template<typename K, typename V>
put(K key,V value)163 bool GenerationCache<K, V>::put(K key, 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>;
171 addToCache(entry, key, value);
172 return true;
173 }
174
175 return false;
176 }
177
178 template<typename K, typename V>
addToCache(sp<Entry<K,V>> entry,K key,V value)179 void GenerationCache<K, V>::addToCache(sp<Entry<K, V> > entry, K key, V value) {
180 entry->key = key;
181 entry->value = value;
182 mCache.add(key, entry);
183 attachToCache(entry);
184 }
185
186 template<typename K, typename V>
remove(K key)187 V GenerationCache<K, V>::remove(K key) {
188 ssize_t index = mCache.indexOfKey(key);
189 if (index >= 0) {
190 return removeAt(index);
191 }
192
193 return NULL;
194 }
195
196 template<typename K, typename V>
removeAt(ssize_t index)197 V GenerationCache<K, V>::removeAt(ssize_t index) {
198 sp<Entry<K, V> > entry = mCache.valueAt(index);
199 if (mListener) {
200 (*mListener)(entry->key, entry->value);
201 }
202 mCache.removeItemsAt(index, 1);
203 detachFromCache(entry);
204
205 return entry->value;
206 }
207
208 template<typename K, typename V>
removeOldest()209 V GenerationCache<K, V>::removeOldest() {
210 if (mOldest.get()) {
211 ssize_t index = mCache.indexOfKey(mOldest->key);
212 if (index >= 0) {
213 return removeAt(index);
214 }
215 }
216
217 return NULL;
218 }
219
220 template<typename K, typename V>
attachToCache(sp<Entry<K,V>> entry)221 void GenerationCache<K, V>::attachToCache(sp<Entry<K, V> > entry) {
222 if (!mYoungest.get()) {
223 mYoungest = mOldest = entry;
224 } else {
225 entry->parent = mYoungest;
226 mYoungest->child = entry;
227 mYoungest = entry;
228 }
229 }
230
231 template<typename K, typename V>
detachFromCache(sp<Entry<K,V>> entry)232 void GenerationCache<K, V>::detachFromCache(sp<Entry<K, V> > entry) {
233 if (entry->parent.get()) {
234 entry->parent->child = entry->child;
235 }
236
237 if (entry->child.get()) {
238 entry->child->parent = entry->parent;
239 }
240
241 if (mOldest == entry) {
242 mOldest = entry->child;
243 }
244
245 if (mYoungest == entry) {
246 mYoungest = entry->parent;
247 }
248
249 entry->parent.clear();
250 entry->child.clear();
251 }
252
253 }; // namespace android
254
255 #endif // ANDROID_UTILS_GENERATION_CACHE_H
256