← Back to branch summary

~xnox/ubuntu/trusty/gcc-arm-linux-androideabi/dima

« back to all changes in this revision

Viewing changes to android/frameworks/native/include/utils/GenerationCache.h

  • Committer: Package Import Robot
  • Author(s): Dmitrijs Ledkovs
  • Date: 2013-07-05 10:12:24 UTC
  • Revision ID: package-import@ubuntu.com-20130705101224-6qo3e8jbz8p31aa1
Tags: upstream-0.20130705.1
Import upstream version 0.20130705.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
android/frameworks/native/include/utils/GenerationCache.h
 
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
 
 
23
namespace android {
 
24
 
 
25
/**
 
26
 * GenerationCache callback used when an item is removed
 
27
 */
 
28
template<typename EntryKey, typename EntryValue>
 
29
class OnEntryRemoved {
 
30
public:
 
31
    virtual ~OnEntryRemoved() { };
 
32
    virtual void operator()(EntryKey& key, EntryValue& value) = 0;
 
33
}; // class OnEntryRemoved
 
34
 
 
35
template<typename EntryKey, typename EntryValue>
 
36
struct 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
 */
 
53
template<typename K, typename V>
 
54
class GenerationCache {
 
55
public:
 
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
 
 
80
private:
 
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
 
 
95
template<typename K, typename V>
 
96
GenerationCache<K, V>::GenerationCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
 
97
    mListener(NULL), mNullValue(NULL) {
 
98
};
 
99
 
 
100
template<typename K, typename V>
 
101
GenerationCache<K, V>::~GenerationCache() {
 
102
    clear();
 
103
};
 
104
 
 
105
template<typename K, typename V>
 
106
uint32_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
 */
 
114
template<typename K, typename V>
 
115
void GenerationCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
 
116
    mListener = listener;
 
117
}
 
118
 
 
119
template<typename K, typename V>
 
120
void 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
 
 
134
template<typename K, typename V>
 
135
bool GenerationCache<K, V>::contains(const K& key) const {
 
136
    return mCache.indexOfKey(key) >= 0;
 
137
}
 
138
 
 
139
template<typename K, typename V>
 
140
const K& GenerationCache<K, V>::getKeyAt(size_t index) const {
 
141
    return mCache.keyAt(index);
 
142
}
 
143
 
 
144
template<typename K, typename V>
 
145
const V& GenerationCache<K, V>::getValueAt(size_t index) const {
 
146
    return mCache.valueAt(index)->value;
 
147
}
 
148
 
 
149
template<typename K, typename V>
 
150
const 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
 
 
162
template<typename K, typename V>
 
163
bool 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
 
 
179
template<typename K, typename V>
 
180
bool 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
 
 
190
template<typename K, typename V>
 
191
void 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
 
 
200
template<typename K, typename V>
 
201
bool 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
 
 
216
template<typename K, typename V>
 
217
void 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
 
 
227
template<typename K, typename V>
 
228
void 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