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