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