1/* 2 * Copyright (C) 2012 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_LRU_CACHE_H 18#define ANDROID_UTILS_LRU_CACHE_H 19 20#include <UniquePtr.h> 21#include <utils/BasicHashtable.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 TKey, typename TValue> 36class LruCache { 37public: 38 explicit LruCache(uint32_t maxCapacity); 39 40 enum Capacity { 41 kUnlimitedCapacity, 42 }; 43 44 void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener); 45 size_t size() const; 46 const TValue& get(const TKey& key); 47 bool put(const TKey& key, const TValue& value); 48 bool remove(const TKey& key); 49 bool removeOldest(); 50 void clear(); 51 const TValue& peekOldestValue(); 52 53 class Iterator { 54 public: 55 Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) { 56 } 57 58 bool next() { 59 mIndex = mCache.mTable->next(mIndex); 60 return (ssize_t)mIndex != -1; 61 } 62 63 size_t index() const { 64 return mIndex; 65 } 66 67 const TValue& value() const { 68 return mCache.mTable->entryAt(mIndex).value; 69 } 70 71 const TKey& key() const { 72 return mCache.mTable->entryAt(mIndex).key; 73 } 74 private: 75 const LruCache<TKey, TValue>& mCache; 76 size_t mIndex; 77 }; 78 79private: 80 LruCache(const LruCache& that); // disallow copy constructor 81 82 struct Entry { 83 TKey key; 84 TValue value; 85 Entry* parent; 86 Entry* child; 87 88 Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) { 89 } 90 const TKey& getKey() const { return key; } 91 }; 92 93 void attachToCache(Entry& entry); 94 void detachFromCache(Entry& entry); 95 void rehash(size_t newCapacity); 96 97 UniquePtr<BasicHashtable<TKey, Entry> > mTable; 98 OnEntryRemoved<TKey, TValue>* mListener; 99 Entry* mOldest; 100 Entry* mYoungest; 101 uint32_t mMaxCapacity; 102 TValue mNullValue; 103}; 104 105// Implementation is here, because it's fully templated 106template <typename TKey, typename TValue> 107LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity) 108 : mTable(new BasicHashtable<TKey, Entry>) 109 , mListener(NULL) 110 , mOldest(NULL) 111 , mYoungest(NULL) 112 , mMaxCapacity(maxCapacity) 113 , mNullValue(NULL) { 114}; 115 116template<typename K, typename V> 117void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) { 118 mListener = listener; 119} 120 121template <typename TKey, typename TValue> 122size_t LruCache<TKey, TValue>::size() const { 123 return mTable->size(); 124} 125 126template <typename TKey, typename TValue> 127const TValue& LruCache<TKey, TValue>::get(const TKey& key) { 128 hash_t hash = hash_type(key); 129 ssize_t index = mTable->find(-1, hash, key); 130 if (index == -1) { 131 return mNullValue; 132 } 133 Entry& entry = mTable->editEntryAt(index); 134 detachFromCache(entry); 135 attachToCache(entry); 136 return entry.value; 137} 138 139template <typename TKey, typename TValue> 140bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) { 141 if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) { 142 removeOldest(); 143 } 144 145 hash_t hash = hash_type(key); 146 ssize_t index = mTable->find(-1, hash, key); 147 if (index >= 0) { 148 return false; 149 } 150 if (!mTable->hasMoreRoom()) { 151 rehash(mTable->capacity() * 2); 152 } 153 154 // Would it be better to initialize a blank entry and assign key, value? 155 Entry initEntry(key, value); 156 index = mTable->add(hash, initEntry); 157 Entry& entry = mTable->editEntryAt(index); 158 attachToCache(entry); 159 return true; 160} 161 162template <typename TKey, typename TValue> 163bool LruCache<TKey, TValue>::remove(const TKey& key) { 164 hash_t hash = hash_type(key); 165 ssize_t index = mTable->find(-1, hash, key); 166 if (index < 0) { 167 return false; 168 } 169 Entry& entry = mTable->editEntryAt(index); 170 if (mListener) { 171 (*mListener)(entry.key, entry.value); 172 } 173 detachFromCache(entry); 174 mTable->removeAt(index); 175 return true; 176} 177 178template <typename TKey, typename TValue> 179bool LruCache<TKey, TValue>::removeOldest() { 180 if (mOldest != NULL) { 181 return remove(mOldest->key); 182 // TODO: should probably abort if false 183 } 184 return false; 185} 186 187template <typename TKey, typename TValue> 188const TValue& LruCache<TKey, TValue>::peekOldestValue() { 189 if (mOldest) { 190 return mOldest->value; 191 } 192 return mNullValue; 193} 194 195template <typename TKey, typename TValue> 196void LruCache<TKey, TValue>::clear() { 197 if (mListener) { 198 for (Entry* p = mOldest; p != NULL; p = p->child) { 199 (*mListener)(p->key, p->value); 200 } 201 } 202 mYoungest = NULL; 203 mOldest = NULL; 204 mTable->clear(); 205} 206 207template <typename TKey, typename TValue> 208void LruCache<TKey, TValue>::attachToCache(Entry& entry) { 209 if (mYoungest == NULL) { 210 mYoungest = mOldest = &entry; 211 } else { 212 entry.parent = mYoungest; 213 mYoungest->child = &entry; 214 mYoungest = &entry; 215 } 216} 217 218template <typename TKey, typename TValue> 219void LruCache<TKey, TValue>::detachFromCache(Entry& entry) { 220 if (entry.parent != NULL) { 221 entry.parent->child = entry.child; 222 } else { 223 mOldest = entry.child; 224 } 225 if (entry.child != NULL) { 226 entry.child->parent = entry.parent; 227 } else { 228 mYoungest = entry.parent; 229 } 230 231 entry.parent = NULL; 232 entry.child = NULL; 233} 234 235template <typename TKey, typename TValue> 236void LruCache<TKey, TValue>::rehash(size_t newCapacity) { 237 UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release()); 238 Entry* oldest = mOldest; 239 240 mOldest = NULL; 241 mYoungest = NULL; 242 mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity)); 243 for (Entry* p = oldest; p != NULL; p = p->child) { 244 put(p->key, p->value); 245 } 246} 247 248} 249 250#endif // ANDROID_UTILS_LRU_CACHE_H 251