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 | |
Dan Albert | f2d2509 | 2015-11-05 01:09:22 -0800 | [diff] [blame] | 20 | #include <memory> |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 21 | #include <unordered_set> |
| 22 | |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 23 | #include "utils/TypeHelpers.h" // hash_t |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 24 | |
| 25 | namespace android { |
| 26 | |
Mathias Agopian | 9eb2a3b | 2013-05-06 20:20:50 -0700 | [diff] [blame] | 27 | /** |
| 28 | * GenerationCache callback used when an item is removed |
| 29 | */ |
| 30 | template<typename EntryKey, typename EntryValue> |
| 31 | class OnEntryRemoved { |
| 32 | public: |
| 33 | virtual ~OnEntryRemoved() { }; |
| 34 | virtual void operator()(EntryKey& key, EntryValue& value) = 0; |
| 35 | }; // class OnEntryRemoved |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 36 | |
| 37 | template <typename TKey, typename TValue> |
| 38 | class LruCache { |
| 39 | public: |
| 40 | explicit LruCache(uint32_t maxCapacity); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 41 | virtual ~LruCache(); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 42 | |
| 43 | enum Capacity { |
| 44 | kUnlimitedCapacity, |
| 45 | }; |
| 46 | |
| 47 | void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener); |
| 48 | size_t size() const; |
| 49 | const TValue& get(const TKey& key); |
| 50 | bool put(const TKey& key, const TValue& value); |
| 51 | bool remove(const TKey& key); |
| 52 | bool removeOldest(); |
| 53 | void clear(); |
John Reck | 9d8707c | 2014-04-11 19:14:15 -0700 | [diff] [blame] | 54 | const TValue& peekOldestValue(); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 55 | |
| 56 | private: |
| 57 | LruCache(const LruCache& that); // disallow copy constructor |
| 58 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 59 | // Super class so that we can have entries having only a key reference, for searches. |
| 60 | class KeyedEntry { |
| 61 | public: |
| 62 | virtual const TKey& getKey() const = 0; |
| 63 | // Make sure the right destructor is executed so that keys and values are deleted. |
| 64 | virtual ~KeyedEntry() {} |
| 65 | }; |
| 66 | |
| 67 | class Entry final : public KeyedEntry { |
| 68 | public: |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 69 | TKey key; |
| 70 | TValue value; |
| 71 | Entry* parent; |
| 72 | Entry* child; |
| 73 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 74 | Entry(TKey _key, TValue _value) : key(_key), value(_value), parent(NULL), child(NULL) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 75 | } |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 76 | const TKey& getKey() const final { return key; } |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 77 | }; |
| 78 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 79 | class EntryForSearch : public KeyedEntry { |
| 80 | public: |
| 81 | const TKey& key; |
| 82 | EntryForSearch(const TKey& key_) : key(key_) { |
| 83 | } |
| 84 | const TKey& getKey() const final { return key; } |
| 85 | }; |
| 86 | |
| 87 | struct HashForEntry : public std::unary_function<KeyedEntry*, hash_t> { |
| 88 | size_t operator() (const KeyedEntry* entry) const { |
| 89 | return hash_type(entry->getKey()); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 90 | }; |
| 91 | }; |
| 92 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 93 | struct EqualityForHashedEntries : public std::unary_function<KeyedEntry*, hash_t> { |
| 94 | bool operator() (const KeyedEntry* lhs, const KeyedEntry* rhs) const { |
| 95 | return lhs->getKey() == rhs->getKey(); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 96 | }; |
| 97 | }; |
| 98 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 99 | // All entries in the set will be Entry*. Using the weaker KeyedEntry as to allow entries |
| 100 | // that have only a key reference, for searching. |
| 101 | typedef std::unordered_set<KeyedEntry*, HashForEntry, EqualityForHashedEntries> LruCacheSet; |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 102 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 103 | void attachToCache(Entry& entry); |
| 104 | void detachFromCache(Entry& entry); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 105 | |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 106 | typename LruCacheSet::iterator findByKey(const TKey& key) { |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 107 | EntryForSearch entryForSearch(key); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 108 | typename LruCacheSet::iterator result = mSet->find(&entryForSearch); |
| 109 | return result; |
| 110 | } |
| 111 | |
Dan Albert | f2d2509 | 2015-11-05 01:09:22 -0800 | [diff] [blame] | 112 | std::unique_ptr<LruCacheSet> mSet; |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 113 | OnEntryRemoved<TKey, TValue>* mListener; |
| 114 | Entry* mOldest; |
| 115 | Entry* mYoungest; |
| 116 | uint32_t mMaxCapacity; |
| 117 | TValue mNullValue; |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 118 | |
| 119 | public: |
Sergio Giro | 0cb59c0 | 2015-10-02 17:31:34 +0100 | [diff] [blame] | 120 | // To be used like: |
| 121 | // while (it.next()) { |
| 122 | // it.value(); it.key(); |
| 123 | // } |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 124 | class Iterator { |
| 125 | public: |
Sergio Giro | 0cb59c0 | 2015-10-02 17:31:34 +0100 | [diff] [blame] | 126 | Iterator(const LruCache<TKey, TValue>& cache): |
| 127 | mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) { |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 128 | } |
| 129 | |
| 130 | bool next() { |
| 131 | if (mIterator == mCache.mSet->end()) { |
| 132 | return false; |
| 133 | } |
Sergio Giro | 0cb59c0 | 2015-10-02 17:31:34 +0100 | [diff] [blame] | 134 | if (!mBeginReturned) { |
| 135 | // mIterator has been initialized to the beginning and |
| 136 | // hasn't been returned. Do not advance: |
| 137 | mBeginReturned = true; |
| 138 | } else { |
| 139 | std::advance(mIterator, 1); |
| 140 | } |
| 141 | bool ret = (mIterator != mCache.mSet->end()); |
| 142 | return ret; |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 143 | } |
| 144 | |
| 145 | const TValue& value() const { |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 146 | // All the elements in the set are of type Entry. See comment in the definition |
| 147 | // of LruCacheSet above. |
| 148 | return reinterpret_cast<Entry *>(*mIterator)->value; |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 149 | } |
| 150 | |
| 151 | const TKey& key() const { |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 152 | return (*mIterator)->getKey(); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 153 | } |
| 154 | private: |
| 155 | const LruCache<TKey, TValue>& mCache; |
| 156 | typename LruCacheSet::iterator mIterator; |
Sergio Giro | 0cb59c0 | 2015-10-02 17:31:34 +0100 | [diff] [blame] | 157 | bool mBeginReturned; |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 158 | }; |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 159 | }; |
| 160 | |
| 161 | // Implementation is here, because it's fully templated |
| 162 | template <typename TKey, typename TValue> |
Mark Salyzyn | 4887842 | 2014-05-22 16:08:52 -0700 | [diff] [blame] | 163 | LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity) |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 164 | : mSet(new LruCacheSet()) |
Mark Salyzyn | 4887842 | 2014-05-22 16:08:52 -0700 | [diff] [blame] | 165 | , mListener(NULL) |
| 166 | , mOldest(NULL) |
| 167 | , mYoungest(NULL) |
| 168 | , mMaxCapacity(maxCapacity) |
Colin Cross | 17b5b82 | 2016-09-15 18:15:37 -0700 | [diff] [blame] | 169 | , mNullValue(0) { |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 170 | mSet->max_load_factor(1.0); |
| 171 | }; |
| 172 | |
| 173 | template <typename TKey, typename TValue> |
| 174 | LruCache<TKey, TValue>::~LruCache() { |
| 175 | // Need to delete created entries. |
| 176 | clear(); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 177 | }; |
| 178 | |
| 179 | template<typename K, typename V> |
| 180 | void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) { |
| 181 | mListener = listener; |
| 182 | } |
| 183 | |
| 184 | template <typename TKey, typename TValue> |
| 185 | size_t LruCache<TKey, TValue>::size() const { |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 186 | return mSet->size(); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 187 | } |
| 188 | |
| 189 | template <typename TKey, typename TValue> |
| 190 | const TValue& LruCache<TKey, TValue>::get(const TKey& key) { |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 191 | typename LruCacheSet::const_iterator find_result = findByKey(key); |
| 192 | if (find_result == mSet->end()) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 193 | return mNullValue; |
| 194 | } |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 195 | // All the elements in the set are of type Entry. See comment in the definition |
| 196 | // of LruCacheSet above. |
| 197 | Entry *entry = reinterpret_cast<Entry*>(*find_result); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 198 | detachFromCache(*entry); |
| 199 | attachToCache(*entry); |
| 200 | return entry->value; |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 201 | } |
| 202 | |
| 203 | template <typename TKey, typename TValue> |
| 204 | bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) { |
| 205 | if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) { |
| 206 | removeOldest(); |
| 207 | } |
| 208 | |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 209 | if (findByKey(key) != mSet->end()) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 210 | return false; |
| 211 | } |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 212 | |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 213 | Entry* newEntry = new Entry(key, value); |
| 214 | mSet->insert(newEntry); |
| 215 | attachToCache(*newEntry); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 216 | return true; |
| 217 | } |
| 218 | |
| 219 | template <typename TKey, typename TValue> |
| 220 | bool LruCache<TKey, TValue>::remove(const TKey& key) { |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 221 | typename LruCacheSet::const_iterator find_result = findByKey(key); |
| 222 | if (find_result == mSet->end()) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 223 | return false; |
| 224 | } |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 225 | // All the elements in the set are of type Entry. See comment in the definition |
| 226 | // of LruCacheSet above. |
| 227 | Entry* entry = reinterpret_cast<Entry*>(*find_result); |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 228 | mSet->erase(entry); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 229 | if (mListener) { |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 230 | (*mListener)(entry->key, entry->value); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 231 | } |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 232 | detachFromCache(*entry); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 233 | delete entry; |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 234 | return true; |
| 235 | } |
| 236 | |
| 237 | template <typename TKey, typename TValue> |
| 238 | bool LruCache<TKey, TValue>::removeOldest() { |
| 239 | if (mOldest != NULL) { |
| 240 | return remove(mOldest->key); |
| 241 | // TODO: should probably abort if false |
| 242 | } |
| 243 | return false; |
| 244 | } |
| 245 | |
| 246 | template <typename TKey, typename TValue> |
John Reck | 9d8707c | 2014-04-11 19:14:15 -0700 | [diff] [blame] | 247 | const TValue& LruCache<TKey, TValue>::peekOldestValue() { |
| 248 | if (mOldest) { |
| 249 | return mOldest->value; |
| 250 | } |
| 251 | return mNullValue; |
| 252 | } |
| 253 | |
| 254 | template <typename TKey, typename TValue> |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 255 | void LruCache<TKey, TValue>::clear() { |
| 256 | if (mListener) { |
| 257 | for (Entry* p = mOldest; p != NULL; p = p->child) { |
| 258 | (*mListener)(p->key, p->value); |
| 259 | } |
| 260 | } |
| 261 | mYoungest = NULL; |
| 262 | mOldest = NULL; |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 263 | for (auto entry : *mSet.get()) { |
| 264 | delete entry; |
| 265 | } |
| 266 | mSet->clear(); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 267 | } |
| 268 | |
| 269 | template <typename TKey, typename TValue> |
| 270 | void LruCache<TKey, TValue>::attachToCache(Entry& entry) { |
| 271 | if (mYoungest == NULL) { |
| 272 | mYoungest = mOldest = &entry; |
| 273 | } else { |
| 274 | entry.parent = mYoungest; |
| 275 | mYoungest->child = &entry; |
| 276 | mYoungest = &entry; |
| 277 | } |
| 278 | } |
| 279 | |
| 280 | template <typename TKey, typename TValue> |
| 281 | void LruCache<TKey, TValue>::detachFromCache(Entry& entry) { |
| 282 | if (entry.parent != NULL) { |
| 283 | entry.parent->child = entry.child; |
| 284 | } else { |
| 285 | mOldest = entry.child; |
| 286 | } |
| 287 | if (entry.child != NULL) { |
| 288 | entry.child->parent = entry.parent; |
| 289 | } else { |
| 290 | mYoungest = entry.parent; |
| 291 | } |
| 292 | |
| 293 | entry.parent = NULL; |
| 294 | entry.child = NULL; |
| 295 | } |
| 296 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 297 | } |
Romain Guy | b3176ac | 2012-11-28 12:59:40 -0800 | [diff] [blame] | 298 | #endif // ANDROID_UTILS_LRU_CACHE_H |