LruCache.h revision b3176acd5fa7a35cee7b6722cd5869f13542afdd 
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/GenerationCache.h>
22#include <utils/UniquePtr.h>
23
24namespace android {
25
26// OnEntryRemoved is defined in GenerationCache.h, but maybe should move here.
27
28template <typename TKey, typename TValue>
29class LruCache {
30public:
31    explicit LruCache(uint32_t maxCapacity);
32
33    enum Capacity {
34        kUnlimitedCapacity,
35    };
36
37    void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
38    size_t size() const;
39    const TValue& get(const TKey& key);
40    bool put(const TKey& key, const TValue& value);
41    bool remove(const TKey& key);
42    bool removeOldest();
43    void clear();
44
45private:
46    LruCache(const LruCache& that);  // disallow copy constructor
47
48    struct Entry {
49        TKey key;
50        TValue value;
51        Entry* parent;
52        Entry* child;
53
54        Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
55        }
56        const TKey& getKey() const { return key; }
57    };
58
59    void attachToCache(Entry& entry);
60    void detachFromCache(Entry& entry);
61    void rehash(size_t newCapacity);
62
63    UniquePtr<BasicHashtable<TKey, Entry> > mTable;
64    OnEntryRemoved<TKey, TValue>* mListener;
65    Entry* mOldest;
66    Entry* mYoungest;
67    uint32_t mMaxCapacity;
68    TValue mNullValue;
69};
70
71// Implementation is here, because it's fully templated
72template <typename TKey, typename TValue>
73LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
74    mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
75    mListener(NULL) {
76};
77
78template<typename K, typename V>
79void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
80    mListener = listener;
81}
82
83template <typename TKey, typename TValue>
84size_t LruCache<TKey, TValue>::size() const {
85    return mTable->size();
86}
87
88template <typename TKey, typename TValue>
89const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
90    hash_t hash = hash_type(key);
91    ssize_t index = mTable->find(-1, hash, key);
92    if (index == -1) {
93        return mNullValue;
94    }
95    Entry& entry = mTable->editEntryAt(index);
96    detachFromCache(entry);
97    attachToCache(entry);
98    return entry.value;
99}
100
101template <typename TKey, typename TValue>
102bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
103    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
104        removeOldest();
105    }
106
107    hash_t hash = hash_type(key);
108    ssize_t index = mTable->find(-1, hash, key);
109    if (index >= 0) {
110        return false;
111    }
112    if (!mTable->hasMoreRoom()) {
113        rehash(mTable->capacity() * 2);
114    }
115
116    // Would it be better to initialize a blank entry and assign key, value?
117    Entry initEntry(key, value);
118    index = mTable->add(hash, initEntry);
119    Entry& entry = mTable->editEntryAt(index);
120    attachToCache(entry);
121    return true;
122}
123
124template <typename TKey, typename TValue>
125bool LruCache<TKey, TValue>::remove(const TKey& key) {
126    hash_t hash = hash_type(key);
127    ssize_t index = mTable->find(-1, hash, key);
128    if (index < 0) {
129        return false;
130    }
131    Entry& entry = mTable->editEntryAt(index);
132    if (mListener) {
133        (*mListener)(entry.key, entry.value);
134    }
135    detachFromCache(entry);
136    mTable->removeAt(index);
137    return true;
138}
139
140template <typename TKey, typename TValue>
141bool LruCache<TKey, TValue>::removeOldest() {
142    if (mOldest != NULL) {
143        return remove(mOldest->key);
144        // TODO: should probably abort if false
145    }
146    return false;
147}
148
149template <typename TKey, typename TValue>
150void LruCache<TKey, TValue>::clear() {
151    if (mListener) {
152        for (Entry* p = mOldest; p != NULL; p = p->child) {
153            (*mListener)(p->key, p->value);
154        }
155    }
156    mYoungest = NULL;
157    mOldest = NULL;
158    mTable->clear();
159}
160
161template <typename TKey, typename TValue>
162void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
163    if (mYoungest == NULL) {
164        mYoungest = mOldest = &entry;
165    } else {
166        entry.parent = mYoungest;
167        mYoungest->child = &entry;
168        mYoungest = &entry;
169    }
170}
171
172template <typename TKey, typename TValue>
173void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
174    if (entry.parent != NULL) {
175        entry.parent->child = entry.child;
176    } else {
177        mOldest = entry.child;
178    }
179    if (entry.child != NULL) {
180        entry.child->parent = entry.parent;
181    } else {
182        mYoungest = entry.parent;
183    }
184
185    entry.parent = NULL;
186    entry.child = NULL;
187}
188
189template <typename TKey, typename TValue>
190void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
191    UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
192    Entry* oldest = mOldest;
193
194    mOldest = NULL;
195    mYoungest = NULL;
196    mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
197    for (Entry* p = oldest; p != NULL; p = p->child) {
198        put(p->key, p->value);
199    }
200}
201
202}
203
204#endif // ANDROID_UTILS_LRU_CACHE_H
205