LruCache.h revision 4887842c925f304dc862bdd5810f27cdd2eaedcb 
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
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
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 (ssize_t)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
78private:
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
105template <typename TKey, typename TValue>
106LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity)
107    : mTable(new BasicHashtable<TKey, Entry>)
108    , mListener(NULL)
109    , mOldest(NULL)
110    , mYoungest(NULL)
111    , mMaxCapacity(maxCapacity)
112    , mNullValue(NULL) {
113};
114
115template<typename K, typename V>
116void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
117    mListener = listener;
118}
119
120template <typename TKey, typename TValue>
121size_t LruCache<TKey, TValue>::size() const {
122    return mTable->size();
123}
124
125template <typename TKey, typename TValue>
126const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
127    hash_t hash = hash_type(key);
128    ssize_t index = mTable->find(-1, hash, key);
129    if (index == -1) {
130        return mNullValue;
131    }
132    Entry& entry = mTable->editEntryAt(index);
133    detachFromCache(entry);
134    attachToCache(entry);
135    return entry.value;
136}
137
138template <typename TKey, typename TValue>
139bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
140    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
141        removeOldest();
142    }
143
144    hash_t hash = hash_type(key);
145    ssize_t index = mTable->find(-1, hash, key);
146    if (index >= 0) {
147        return false;
148    }
149    if (!mTable->hasMoreRoom()) {
150        rehash(mTable->capacity() * 2);
151    }
152
153    // Would it be better to initialize a blank entry and assign key, value?
154    Entry initEntry(key, value);
155    index = mTable->add(hash, initEntry);
156    Entry& entry = mTable->editEntryAt(index);
157    attachToCache(entry);
158    return true;
159}
160
161template <typename TKey, typename TValue>
162bool LruCache<TKey, TValue>::remove(const TKey& key) {
163    hash_t hash = hash_type(key);
164    ssize_t index = mTable->find(-1, hash, key);
165    if (index < 0) {
166        return false;
167    }
168    Entry& entry = mTable->editEntryAt(index);
169    if (mListener) {
170        (*mListener)(entry.key, entry.value);
171    }
172    detachFromCache(entry);
173    mTable->removeAt(index);
174    return true;
175}
176
177template <typename TKey, typename TValue>
178bool LruCache<TKey, TValue>::removeOldest() {
179    if (mOldest != NULL) {
180        return remove(mOldest->key);
181        // TODO: should probably abort if false
182    }
183    return false;
184}
185
186template <typename TKey, typename TValue>
187void LruCache<TKey, TValue>::clear() {
188    if (mListener) {
189        for (Entry* p = mOldest; p != NULL; p = p->child) {
190            (*mListener)(p->key, p->value);
191        }
192    }
193    mYoungest = NULL;
194    mOldest = NULL;
195    mTable->clear();
196}
197
198template <typename TKey, typename TValue>
199void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
200    if (mYoungest == NULL) {
201        mYoungest = mOldest = &entry;
202    } else {
203        entry.parent = mYoungest;
204        mYoungest->child = &entry;
205        mYoungest = &entry;
206    }
207}
208
209template <typename TKey, typename TValue>
210void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
211    if (entry.parent != NULL) {
212        entry.parent->child = entry.child;
213    } else {
214        mOldest = entry.child;
215    }
216    if (entry.child != NULL) {
217        entry.child->parent = entry.parent;
218    } else {
219        mYoungest = entry.parent;
220    }
221
222    entry.parent = NULL;
223    entry.child = NULL;
224}
225
226template <typename TKey, typename TValue>
227void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
228    UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
229    Entry* oldest = mOldest;
230
231    mOldest = NULL;
232    mYoungest = NULL;
233    mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
234    for (Entry* p = oldest; p != NULL; p = p->child) {
235        put(p->key, p->value);
236    }
237}
238
239}
240
241#endif // ANDROID_UTILS_LRU_CACHE_H
242