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 <memory>
     21 #include <unordered_set>
     22 
     23 #include "utils/TypeHelpers.h"  // hash_t
     24 
     25 namespace android {
     26 
     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
     36 
     37 template <typename TKey, typename TValue>
     38 class LruCache {
     39 public:
     40     explicit LruCache(uint32_t maxCapacity);
     41     virtual ~LruCache();
     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();
     54     const TValue& peekOldestValue();
     55 
     56 private:
     57     LruCache(const LruCache& that);  // disallow copy constructor
     58 
     59     struct Entry {
     60         TKey key;
     61         TValue value;
     62         Entry* parent;
     63         Entry* child;
     64 
     65         Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
     66         }
     67         const TKey& getKey() const { return key; }
     68     };
     69 
     70     struct HashForEntry : public std::unary_function<Entry*, hash_t> {
     71         size_t operator() (const Entry* entry) const {
     72             return hash_type(entry->key);
     73         };
     74     };
     75 
     76     struct EqualityForHashedEntries : public std::unary_function<Entry*, hash_t> {
     77         bool operator() (const Entry* lhs, const Entry* rhs) const {
     78             return lhs->key == rhs->key;
     79         };
     80     };
     81 
     82     typedef std::unordered_set<Entry*, HashForEntry, EqualityForHashedEntries> LruCacheSet;
     83 
     84     void attachToCache(Entry& entry);
     85     void detachFromCache(Entry& entry);
     86 
     87     typename LruCacheSet::iterator findByKey(const TKey& key) {
     88         Entry entryForSearch(key, mNullValue);
     89         typename LruCacheSet::iterator result = mSet->find(&entryForSearch);
     90         return result;
     91     }
     92 
     93     std::unique_ptr<LruCacheSet> mSet;
     94     OnEntryRemoved<TKey, TValue>* mListener;
     95     Entry* mOldest;
     96     Entry* mYoungest;
     97     uint32_t mMaxCapacity;
     98     TValue mNullValue;
     99 
    100 public:
    101     // To be used like:
    102     // while (it.next()) {
    103     //   it.value(); it.key();
    104     // }
    105     class Iterator {
    106     public:
    107         Iterator(const LruCache<TKey, TValue>& cache):
    108                 mCache(cache), mIterator(mCache.mSet->begin()), mBeginReturned(false) {
    109         }
    110 
    111         bool next() {
    112             if (mIterator == mCache.mSet->end()) {
    113                 return false;
    114             }
    115             if (!mBeginReturned) {
    116                 // mIterator has been initialized to the beginning and
    117                 // hasn't been returned. Do not advance:
    118                 mBeginReturned = true;
    119             } else {
    120                 std::advance(mIterator, 1);
    121             }
    122             bool ret = (mIterator != mCache.mSet->end());
    123             return ret;
    124         }
    125 
    126         const TValue& value() const {
    127             return (*mIterator)->value;
    128         }
    129 
    130         const TKey& key() const {
    131             return (*mIterator)->key;
    132         }
    133     private:
    134         const LruCache<TKey, TValue>& mCache;
    135         typename LruCacheSet::iterator mIterator;
    136         bool mBeginReturned;
    137     };
    138 };
    139 
    140 // Implementation is here, because it's fully templated
    141 template <typename TKey, typename TValue>
    142 LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
    143     : mSet(new LruCacheSet())
    144     , mListener(NULL)
    145     , mOldest(NULL)
    146     , mYoungest(NULL)
    147     , mMaxCapacity(maxCapacity)
    148     , mNullValue(NULL) {
    149     mSet->max_load_factor(1.0);
    150 };
    151 
    152 template <typename TKey, typename TValue>
    153 LruCache<TKey, TValue>::~LruCache() {
    154     // Need to delete created entries.
    155     clear();
    156 };
    157 
    158 template<typename K, typename V>
    159 void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
    160     mListener = listener;
    161 }
    162 
    163 template <typename TKey, typename TValue>
    164 size_t LruCache<TKey, TValue>::size() const {
    165     return mSet->size();
    166 }
    167 
    168 template <typename TKey, typename TValue>
    169 const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
    170     typename LruCacheSet::const_iterator find_result = findByKey(key);
    171     if (find_result == mSet->end()) {
    172         return mNullValue;
    173     }
    174     Entry *entry = *find_result;
    175     detachFromCache(*entry);
    176     attachToCache(*entry);
    177     return entry->value;
    178 }
    179 
    180 template <typename TKey, typename TValue>
    181 bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
    182     if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
    183         removeOldest();
    184     }
    185 
    186     if (findByKey(key) != mSet->end()) {
    187         return false;
    188     }
    189 
    190     Entry* newEntry = new Entry(key, value);
    191     mSet->insert(newEntry);
    192     attachToCache(*newEntry);
    193     return true;
    194 }
    195 
    196 template <typename TKey, typename TValue>
    197 bool LruCache<TKey, TValue>::remove(const TKey& key) {
    198     typename LruCacheSet::const_iterator find_result = findByKey(key);
    199     if (find_result == mSet->end()) {
    200         return false;
    201     }
    202     Entry* entry = *find_result;
    203     mSet->erase(entry);
    204     if (mListener) {
    205         (*mListener)(entry->key, entry->value);
    206     }
    207     detachFromCache(*entry);
    208     delete entry;
    209     return true;
    210 }
    211 
    212 template <typename TKey, typename TValue>
    213 bool LruCache<TKey, TValue>::removeOldest() {
    214     if (mOldest != NULL) {
    215         return remove(mOldest->key);
    216         // TODO: should probably abort if false
    217     }
    218     return false;
    219 }
    220 
    221 template <typename TKey, typename TValue>
    222 const TValue& LruCache<TKey, TValue>::peekOldestValue() {
    223     if (mOldest) {
    224         return mOldest->value;
    225     }
    226     return mNullValue;
    227 }
    228 
    229 template <typename TKey, typename TValue>
    230 void LruCache<TKey, TValue>::clear() {
    231     if (mListener) {
    232         for (Entry* p = mOldest; p != NULL; p = p->child) {
    233             (*mListener)(p->key, p->value);
    234         }
    235     }
    236     mYoungest = NULL;
    237     mOldest = NULL;
    238     for (auto entry : *mSet.get()) {
    239         delete entry;
    240     }
    241     mSet->clear();
    242 }
    243 
    244 template <typename TKey, typename TValue>
    245 void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
    246     if (mYoungest == NULL) {
    247         mYoungest = mOldest = &entry;
    248     } else {
    249         entry.parent = mYoungest;
    250         mYoungest->child = &entry;
    251         mYoungest = &entry;
    252     }
    253 }
    254 
    255 template <typename TKey, typename TValue>
    256 void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
    257     if (entry.parent != NULL) {
    258         entry.parent->child = entry.child;
    259     } else {
    260         mOldest = entry.child;
    261     }
    262     if (entry.child != NULL) {
    263         entry.child->parent = entry.parent;
    264     } else {
    265         mYoungest = entry.parent;
    266     }
    267 
    268     entry.parent = NULL;
    269     entry.child = NULL;
    270 }
    271 
    272 }
    273 #endif // ANDROID_UTILS_LRU_CACHE_H
    274