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