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 <UniquePtr.h>
21#include <utils/BasicHashtable.h>
22
23namespace android {
24
25/**
26 * GenerationCache callback used when an item is removed
27 */
28template<typename EntryKey, typename EntryValue>
29class OnEntryRemoved {
30public:
31    virtual ~OnEntryRemoved() { };
32    virtual void operator()(EntryKey& key, EntryValue& value) = 0;
33}; // class OnEntryRemoved
34
35template <typename TKey, typename TValue>
36class LruCache {
37public:
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    const TValue& peekOldestValue();
52
53    class Iterator {
54    public:
55        Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
56        }
57
58        bool next() {
59            mIndex = mCache.mTable->next(mIndex);
60            return (ssize_t)mIndex != -1;
61        }
62
63        size_t index() const {
64            return mIndex;
65        }
66
67        const TValue& value() const {
68            return mCache.mTable->entryAt(mIndex).value;
69        }
70
71        const TKey& key() const {
72            return mCache.mTable->entryAt(mIndex).key;
73        }
74    private:
75        const LruCache<TKey, TValue>& mCache;
76        size_t mIndex;
77    };
78
79private:
80    LruCache(const LruCache& that);  // disallow copy constructor
81
82    struct Entry {
83        TKey key;
84        TValue value;
85        Entry* parent;
86        Entry* child;
87
88        Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
89        }
90        const TKey& getKey() const { return key; }
91    };
92
93    void attachToCache(Entry& entry);
94    void detachFromCache(Entry& entry);
95    void rehash(size_t newCapacity);
96
97    UniquePtr<BasicHashtable<TKey, Entry> > mTable;
98    OnEntryRemoved<TKey, TValue>* mListener;
99    Entry* mOldest;
100    Entry* mYoungest;
101    uint32_t mMaxCapacity;
102    TValue mNullValue;
103};
104
105// Implementation is here, because it's fully templated
106template <typename TKey, typename TValue>
107LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
108    : mTable(new BasicHashtable<TKey, Entry>)
109    , mListener(NULL)
110    , mOldest(NULL)
111    , mYoungest(NULL)
112    , mMaxCapacity(maxCapacity)
113    , mNullValue(NULL) {
114};
115
116template<typename K, typename V>
117void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
118    mListener = listener;
119}
120
121template <typename TKey, typename TValue>
122size_t LruCache<TKey, TValue>::size() const {
123    return mTable->size();
124}
125
126template <typename TKey, typename TValue>
127const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
128    hash_t hash = hash_type(key);
129    ssize_t index = mTable->find(-1, hash, key);
130    if (index == -1) {
131        return mNullValue;
132    }
133    Entry& entry = mTable->editEntryAt(index);
134    detachFromCache(entry);
135    attachToCache(entry);
136    return entry.value;
137}
138
139template <typename TKey, typename TValue>
140bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
141    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
142        removeOldest();
143    }
144
145    hash_t hash = hash_type(key);
146    ssize_t index = mTable->find(-1, hash, key);
147    if (index >= 0) {
148        return false;
149    }
150    if (!mTable->hasMoreRoom()) {
151        rehash(mTable->capacity() * 2);
152    }
153
154    // Would it be better to initialize a blank entry and assign key, value?
155    Entry initEntry(key, value);
156    index = mTable->add(hash, initEntry);
157    Entry& entry = mTable->editEntryAt(index);
158    attachToCache(entry);
159    return true;
160}
161
162template <typename TKey, typename TValue>
163bool LruCache<TKey, TValue>::remove(const TKey& key) {
164    hash_t hash = hash_type(key);
165    ssize_t index = mTable->find(-1, hash, key);
166    if (index < 0) {
167        return false;
168    }
169    Entry& entry = mTable->editEntryAt(index);
170    if (mListener) {
171        (*mListener)(entry.key, entry.value);
172    }
173    detachFromCache(entry);
174    mTable->removeAt(index);
175    return true;
176}
177
178template <typename TKey, typename TValue>
179bool LruCache<TKey, TValue>::removeOldest() {
180    if (mOldest != NULL) {
181        return remove(mOldest->key);
182        // TODO: should probably abort if false
183    }
184    return false;
185}
186
187template <typename TKey, typename TValue>
188const TValue& LruCache<TKey, TValue>::peekOldestValue() {
189    if (mOldest) {
190        return mOldest->value;
191    }
192    return mNullValue;
193}
194
195template <typename TKey, typename TValue>
196void LruCache<TKey, TValue>::clear() {
197    if (mListener) {
198        for (Entry* p = mOldest; p != NULL; p = p->child) {
199            (*mListener)(p->key, p->value);
200        }
201    }
202    mYoungest = NULL;
203    mOldest = NULL;
204    mTable->clear();
205}
206
207template <typename TKey, typename TValue>
208void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
209    if (mYoungest == NULL) {
210        mYoungest = mOldest = &entry;
211    } else {
212        entry.parent = mYoungest;
213        mYoungest->child = &entry;
214        mYoungest = &entry;
215    }
216}
217
218template <typename TKey, typename TValue>
219void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
220    if (entry.parent != NULL) {
221        entry.parent->child = entry.child;
222    } else {
223        mOldest = entry.child;
224    }
225    if (entry.child != NULL) {
226        entry.child->parent = entry.parent;
227    } else {
228        mYoungest = entry.parent;
229    }
230
231    entry.parent = NULL;
232    entry.child = NULL;
233}
234
235template <typename TKey, typename TValue>
236void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
237    UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
238    Entry* oldest = mOldest;
239
240    mOldest = NULL;
241    mYoungest = NULL;
242    mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
243    for (Entry* p = oldest; p != NULL; p = p->child) {
244        put(p->key, p->value);
245    }
246}
247
248}
249
250#endif // ANDROID_UTILS_LRU_CACHE_H
251