Home | History | Annotate | Download | only in utils 
      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
    238