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