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
92    const V mNullValue;
93}; // class GenerationCache
94
95template<typename K, typename V>
96GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
97    mListener(NULL), mNullValue(NULL) {
98};
99
100template<typename K, typename V>
101GenerationCache<K, V>::~GenerationCache() {
102    clear();
103};
104
105template<typename K, typename V>
106uint32_t GenerationCache<K, V>::size() const {
107    return mCache.size();
108}
109
110/**
111 * Should be set by the user of the Cache so that the callback is called whenever an item is
112 * removed from the cache
113 */
114template<typename K, typename V>
115void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
116    mListener = listener;
117}
118
119template<typename K, typename V>
120void GenerationCache<K, V>::clear() {
121    if (mListener) {
122        for (uint32_t i = 0; i < mCache.size(); i++) {
123            sp<Entry<K, V> > entry = mCache.valueAt(i);
124            if (mListener) {
125                (*mListener)(entry->key, entry->value);
126            }
127        }
128    }
129    mCache.clear();
130    mYoungest.clear();
131    mOldest.clear();
132}
133
134template<typename K, typename V>
135bool GenerationCache<K, V>::contains(const K& key) const {
136    return mCache.indexOfKey(key) >= 0;
137}
138
139template<typename K, typename V>
140const K& GenerationCache<K, V>::getKeyAt(size_t index) const {
141    return mCache.keyAt(index);
142}
143
144template<typename K, typename V>
145const V& GenerationCache<K, V>::getValueAt(size_t index) const {
146    return mCache.valueAt(index)->value;
147}
148
149template<typename K, typename V>
150const V& GenerationCache<K, V>::get(const K& key) {
151    ssize_t index = mCache.indexOfKey(key);
152    if (index >= 0) {
153        const sp<Entry<K, V> >& entry = mCache.valueAt(index);
154        detachFromCache(entry);
155        attachToCache(entry);
156        return entry->value;
157    }
158
159    return mNullValue;
160}
161
162template<typename K, typename V>
163bool GenerationCache<K, V>::put(const K& key, const V& value) {
164    if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) {
165        removeOldest();
166    }
167
168    ssize_t index = mCache.indexOfKey(key);
169    if (index < 0) {
170        sp<Entry<K, V> > entry = new Entry<K, V>(key, value);
171        mCache.add(key, entry);
172        attachToCache(entry);
173        return true;
174    }
175
176    return false;
177}
178
179template<typename K, typename V>
180bool GenerationCache<K, V>::remove(const K& key) {
181    ssize_t index = mCache.indexOfKey(key);
182    if (index >= 0) {
183        removeAt(index);
184        return true;
185    }
186
187    return false;
188}
189
190template<typename K, typename V>
191void GenerationCache<K, V>::removeAt(ssize_t index) {
192    sp<Entry<K, V> > entry = mCache.valueAt(index);
193    if (mListener) {
194        (*mListener)(entry->key, entry->value);
195    }
196    mCache.removeItemsAt(index, 1);
197    detachFromCache(entry);
198}
199
200template<typename K, typename V>
201bool GenerationCache<K, V>::removeOldest() {
202    if (mOldest.get()) {
203        ssize_t index = mCache.indexOfKey(mOldest->key);
204        if (index >= 0) {
205            removeAt(index);
206            return true;
207        }
208        ALOGE("GenerationCache: removeOldest failed to find the item in the cache "
209                "with the given key, but we know it must be in there.  "
210                "Is the key comparator kaput?");
211    }
212
213    return false;
214}
215
216template<typename K, typename V>
217void GenerationCache<K, V>::attachToCache(const sp<Entry<K, V> >& entry) {
218    if (!mYoungest.get()) {
219        mYoungest = mOldest = entry;
220    } else {
221        entry->parent = mYoungest;
222        mYoungest->child = entry;
223        mYoungest = entry;
224    }
225}
226
227template<typename K, typename V>
228void GenerationCache<K, V>::detachFromCache(const sp<Entry<K, V> >& entry) {
229    if (entry->parent.get()) {
230        entry->parent->child = entry->child;
231    } else {
232        mOldest = entry->child;
233    }
234
235    if (entry->child.get()) {
236        entry->child->parent = entry->parent;
237    } else {
238        mYoungest = entry->parent;
239    }
240
241    entry->parent.clear();
242    entry->child.clear();
243}
244
245}; // namespace android
246
247#endif // ANDROID_UTILS_GENERATION_CACHE_H
248