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