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
25namespace android {
26
27/**
28 * GenerationCache callback used when an item is removed
29 */
30template<typename EntryKey, typename EntryValue>
31class OnEntryRemoved {
32public:
33    virtual ~OnEntryRemoved() { };
34    virtual void operator()(EntryKey& key, EntryValue& value) = 0;
35}; // class OnEntryRemoved
36
37template <typename TKey, typename TValue>
38class LruCache {
39public:
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
56private:
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
100public:
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
141template <typename TKey, typename TValue>
142LruCache<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
152template <typename TKey, typename TValue>
153LruCache<TKey, TValue>::~LruCache() {
154    // Need to delete created entries.
155    clear();
156};
157
158template<typename K, typename V>
159void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
160    mListener = listener;
161}
162
163template <typename TKey, typename TValue>
164size_t LruCache<TKey, TValue>::size() const {
165    return mSet->size();
166}
167
168template <typename TKey, typename TValue>
169const 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
180template <typename TKey, typename TValue>
181bool 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
196template <typename TKey, typename TValue>
197bool 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
212template <typename TKey, typename TValue>
213bool 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
221template <typename TKey, typename TValue>
222const TValue& LruCache<TKey, TValue>::peekOldestValue() {
223    if (mOldest) {
224        return mOldest->value;
225    }
226    return mNullValue;
227}
228
229template <typename TKey, typename TValue>
230void 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
244template <typename TKey, typename TValue>
245void 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
255template <typename TKey, typename TValue>
256void 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