include/utils/LruCache.h

   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/UniquePtr.h>
  22
  23 namespace android {
  24
  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
  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
  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
  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 }
 236
 237 #endif // ANDROID_UTILS_LRU_CACHE_H