Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 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 | |
Romain Guy | b3176ac | 2012-11-28 12:59:40 -0800 | [diff] [blame] | 17 | #ifndef ANDROID_UTILS_LRU_CACHE_H |
| 18 | #define ANDROID_UTILS_LRU_CACHE_H |
| 19 | |
Kenny Root | 0ddfe11 | 2013-09-11 23:41:23 -0700 | [diff] [blame] | 20 | #include <UniquePtr.h> |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 21 | #include <utils/BasicHashtable.h> |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 22 | |
| 23 | namespace android { |
| 24 | |
Mathias Agopian | 9eb2a3b | 2013-05-06 20:20:50 -0700 | [diff] [blame] | 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 |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 34 | |
| 35 | template <typename TKey, typename TValue> |
| 36 | class LruCache { |
| 37 | public: |
| 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 | |
Romain Guy | 5ca402a | 2012-11-28 18:26:54 -0800 | [diff] [blame] | 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 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 78 | private: |
| 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 |
| 105 | template <typename TKey, typename TValue> |
| 106 | LruCache<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 | |
| 111 | template<typename K, typename V> |
| 112 | void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) { |
| 113 | mListener = listener; |
| 114 | } |
| 115 | |
| 116 | template <typename TKey, typename TValue> |
| 117 | size_t LruCache<TKey, TValue>::size() const { |
| 118 | return mTable->size(); |
| 119 | } |
| 120 | |
| 121 | template <typename TKey, typename TValue> |
| 122 | const 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 | |
| 134 | template <typename TKey, typename TValue> |
| 135 | bool 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 | |
| 157 | template <typename TKey, typename TValue> |
| 158 | bool 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 | |
| 173 | template <typename TKey, typename TValue> |
| 174 | bool 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 | |
| 182 | template <typename TKey, typename TValue> |
| 183 | void 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 | |
| 194 | template <typename TKey, typename TValue> |
| 195 | void 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 | |
| 205 | template <typename TKey, typename TValue> |
| 206 | void 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 | |
| 222 | template <typename TKey, typename TValue> |
| 223 | void 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 | } |
Romain Guy | b3176ac | 2012-11-28 12:59:40 -0800 | [diff] [blame] | 236 | |
| 237 | #endif // ANDROID_UTILS_LRU_CACHE_H |