GenerationCache.h revision b4293fe4081d899446cf0b782da041d4af55d2f9 
1/*
2 * Copyright (C) 2010 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_GENERATION_CACHE_H
18#define ANDROID_UTILS_GENERATION_CACHE_H
19
20#include <utils/KeyedVector.h>
21#include <utils/RefBase.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 EntryKey, typename EntryValue>
36struct Entry: public LightRefBase<Entry<EntryKey, EntryValue> > {
37    Entry(const Entry<EntryKey, EntryValue>& e) :
38            key(e.key), value(e.value),
39            parent(e.parent), child(e.child) { }
40    Entry(const EntryKey& key, const EntryValue& value) :
41            key(key), value(value) { }
42
43    EntryKey key;
44    EntryValue value;
45
46    sp<Entry<EntryKey, EntryValue> > parent; // next older entry
47    sp<Entry<EntryKey, EntryValue> > child;  // next younger entry
48}; // struct Entry
49
50/**
51 * A LRU type cache
52 */
53template<typename K, typename V>
54class GenerationCache {
55public:
56    GenerationCache(uint32_t maxCapacity);
57    virtual ~GenerationCache();
58
59    enum Capacity {
60        kUnlimitedCapacity,
61    };
62
63    void setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener);
64
65    size_t size() const;
66
67    void clear();
68
69    bool contains(const K& key) const;
70    const K& getKeyAt(size_t index) const;
71    const V& getValueAt(size_t index) const;
72
73    const V& get(const K& key);
74    bool put(const K& key, const V& value);
75
76    void removeAt(ssize_t index);
77    bool remove(const K& key);
78    bool removeOldest();
79
80private:
81    KeyedVector<K, sp<Entry<K, V> > > mCache;
82    uint32_t mMaxCapacity;
83
84    OnEntryRemoved<K, V>* mListener;
85
86    sp<Entry<K, V> > mOldest;
87    sp<Entry<K, V> > mYoungest;
88
89    void attachToCache(const sp<Entry<K, V> >& entry);
90    void detachFromCache(const sp<Entry<K, V> >& entry);
91}; // class GenerationCache
92
93template<typename K, typename V>
94GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
95    mListener(NULL) {
96};
97
98template<typename K, typename V>
99GenerationCache<K, V>::~GenerationCache() {
100    clear();
101};
102
103template<typename K, typename V>
104uint32_t GenerationCache<K, V>::size() const {
105    return mCache.size();
106}
107
108/**
109 * Should be set by the user of the Cache so that the callback is called whenever an item is
110 * removed from the cache
111 */
112template<typename K, typename V>
113void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
114    mListener = listener;
115}
116
117template<typename K, typename V>
118void GenerationCache<K, V>::clear() {
119    if (mListener) {
120        for (uint32_t i = 0; i < mCache.size(); i++) {
121            sp<Entry<K, V> > entry = mCache.valueAt(i);
122            if (mListener) {
123                (*mListener)(entry->key, entry->value);
124            }
125        }
126    }
127    mCache.clear();
128    mYoungest.clear();
129    mOldest.clear();
130}
131
132template<typename K, typename V>
133bool GenerationCache<K, V>::contains(const K& key) const {
134    return mCache.indexOfKey(key) >= 0;
135}
136
137template<typename K, typename V>
138const K& GenerationCache<K, V>::getKeyAt(size_t index) const {
139    return mCache.keyAt(index);
140}
141
142template<typename K, typename V>
143const V& GenerationCache<K, V>::getValueAt(size_t index) const {
144    return mCache.valueAt(index)->value;
145}
146
147template<typename K, typename V>
148const V& GenerationCache<K, V>::get(const K& key) {
149    ssize_t index = mCache.indexOfKey(key);
150    if (index >= 0) {
151        const sp<Entry<K, V> >& entry = mCache.valueAt(index);
152        detachFromCache(entry);
153        attachToCache(entry);
154        return entry->value;
155    }
156
157    return NULL;
158}
159
160template<typename K, typename V>
161bool GenerationCache<K, V>::put(const K& key, const V& value) {
162    if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) {
163        removeOldest();
164    }
165
166    ssize_t index = mCache.indexOfKey(key);
167    if (index < 0) {
168        sp<Entry<K, V> > entry = new Entry<K, V>(key, value);
169        mCache.add(key, entry);
170        attachToCache(entry);
171        return true;
172    }
173
174    return false;
175}
176
177template<typename K, typename V>
178bool GenerationCache<K, V>::remove(const K& key) {
179    ssize_t index = mCache.indexOfKey(key);
180    if (index >= 0) {
181        removeAt(index);
182        return true;
183    }
184
185    return false;
186}
187
188template<typename K, typename V>
189void GenerationCache<K, V>::removeAt(ssize_t index) {
190    sp<Entry<K, V> > entry = mCache.valueAt(index);
191    if (mListener) {
192        (*mListener)(entry->key, entry->value);
193    }
194    mCache.removeItemsAt(index, 1);
195    detachFromCache(entry);
196}
197
198template<typename K, typename V>
199bool GenerationCache<K, V>::removeOldest() {
200    if (mOldest.get()) {
201        ssize_t index = mCache.indexOfKey(mOldest->key);
202        if (index >= 0) {
203            removeAt(index);
204            return true;
205        }
206        LOGE("GenerationCache: removeOldest failed to find the item in the cache "
207                "with the given key, but we know it must be in there.  "
208                "Is the key comparator kaput?");
209    }
210
211    return false;
212}
213
214template<typename K, typename V>
215void GenerationCache<K, V>::attachToCache(const sp<Entry<K, V> >& entry) {
216    if (!mYoungest.get()) {
217        mYoungest = mOldest = entry;
218    } else {
219        entry->parent = mYoungest;
220        mYoungest->child = entry;
221        mYoungest = entry;
222    }
223}
224
225template<typename K, typename V>
226void GenerationCache<K, V>::detachFromCache(const sp<Entry<K, V> >& entry) {
227    if (entry->parent.get()) {
228        entry->parent->child = entry->child;
229    } else {
230        mOldest = entry->child;
231    }
232
233    if (entry->child.get()) {
234        entry->child->parent = entry->parent;
235    } else {
236        mYoungest = entry->parent;
237    }
238
239    entry->parent.clear();
240    entry->child.clear();
241}
242
243}; // namespace android
244
245#endif // ANDROID_UTILS_GENERATION_CACHE_H
246