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 23namespace android { 24 25/** 26 * GenerationCache callback used when an item is removed 27 */ 28template<typename EntryKey, typename EntryValue> 29class OnEntryRemoved { 30public: 31 virtual ~OnEntryRemoved() { }; 32 virtual void operator()(EntryKey& key, EntryValue& value) = 0; 33}; // class OnEntryRemoved 34 35template<typename EntryKey, typename EntryValue> 36struct 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 */ 53template<typename K, typename V> 54class GenerationCache { 55public: 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 80private: 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 95template<typename K, typename V> 96GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity), 97 mListener(NULL), mNullValue(NULL) { 98}; 99 100template<typename K, typename V> 101GenerationCache<K, V>::~GenerationCache() { 102 clear(); 103}; 104 105template<typename K, typename V> 106uint32_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 */ 114template<typename K, typename V> 115void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) { 116 mListener = listener; 117} 118 119template<typename K, typename V> 120void 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 134template<typename K, typename V> 135bool GenerationCache<K, V>::contains(const K& key) const { 136 return mCache.indexOfKey(key) >= 0; 137} 138 139template<typename K, typename V> 140const K& GenerationCache<K, V>::getKeyAt(size_t index) const { 141 return mCache.keyAt(index); 142} 143 144template<typename K, typename V> 145const V& GenerationCache<K, V>::getValueAt(size_t index) const { 146 return mCache.valueAt(index)->value; 147} 148 149template<typename K, typename V> 150const 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 162template<typename K, typename V> 163bool 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 179template<typename K, typename V> 180bool 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 190template<typename K, typename V> 191void 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 200template<typename K, typename V> 201bool 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 216template<typename K, typename V> 217void 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 227template<typename K, typename V> 228void 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