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: 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> > { 37 Entry(const Entry<EntryKey, EntryValue>& e) : 38 key(e.key), value(e.value), 39 parent(e.parent), child(e.child) { } 40 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> 96 GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity), 97 mListener(NULL), mNullValue(NULL) { 98 }; 99 100 template<typename K, typename V> 101 GenerationCache<K, V>::~GenerationCache() { 102 clear(); 103 }; 104 105 template<typename K, typename V> 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> 115 void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) { 116 mListener = listener; 117 } 118 119 template<typename K, typename V> 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> 135 bool GenerationCache<K, V>::contains(const K& key) const { 136 return mCache.indexOfKey(key) >= 0; 137 } 138 139 template<typename K, typename V> 140 const K& GenerationCache<K, V>::getKeyAt(size_t index) const { 141 return mCache.keyAt(index); 142 } 143 144 template<typename K, typename V> 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> 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> 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> 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> 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> 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> 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> 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
