1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
|
/*
* Copyright (C) 2012 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ANDROID_UTILS_LRU_CACHE_H
#define ANDROID_UTILS_LRU_CACHE_H
#include <utils/BasicHashtable.h>
#include <utils/UniquePtr.h>
namespace android {
/**
* GenerationCache callback used when an item is removed
*/
template<typename EntryKey, typename EntryValue>
class OnEntryRemoved {
public:
virtual ~OnEntryRemoved() { };
virtual void operator()(EntryKey& key, EntryValue& value) = 0;
}; // class OnEntryRemoved
template <typename TKey, typename TValue>
class LruCache {
public:
explicit LruCache(uint32_t maxCapacity);
enum Capacity {
kUnlimitedCapacity,
};
void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
size_t size() const;
const TValue& get(const TKey& key);
bool put(const TKey& key, const TValue& value);
bool remove(const TKey& key);
bool removeOldest();
void clear();
class Iterator {
public:
Iterator(const LruCache<TKey, TValue>& cache): mCache(cache), mIndex(-1) {
}
bool next() {
mIndex = mCache.mTable->next(mIndex);
return mIndex != -1;
}
size_t index() const {
return mIndex;
}
const TValue& value() const {
return mCache.mTable->entryAt(mIndex).value;
}
const TKey& key() const {
return mCache.mTable->entryAt(mIndex).key;
}
private:
const LruCache<TKey, TValue>& mCache;
size_t mIndex;
};
private:
LruCache(const LruCache& that); // disallow copy constructor
struct Entry {
TKey key;
TValue value;
Entry* parent;
Entry* child;
Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
}
const TKey& getKey() const { return key; }
};
void attachToCache(Entry& entry);
void detachFromCache(Entry& entry);
void rehash(size_t newCapacity);
UniquePtr<BasicHashtable<TKey, Entry> > mTable;
OnEntryRemoved<TKey, TValue>* mListener;
Entry* mOldest;
Entry* mYoungest;
uint32_t mMaxCapacity;
TValue mNullValue;
};
// Implementation is here, because it's fully templated
template <typename TKey, typename TValue>
LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
mListener(NULL) {
};
template<typename K, typename V>
void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
mListener = listener;
}
template <typename TKey, typename TValue>
size_t LruCache<TKey, TValue>::size() const {
return mTable->size();
}
template <typename TKey, typename TValue>
const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
hash_t hash = hash_type(key);
ssize_t index = mTable->find(-1, hash, key);
if (index == -1) {
return mNullValue;
}
Entry& entry = mTable->editEntryAt(index);
detachFromCache(entry);
attachToCache(entry);
return entry.value;
}
template <typename TKey, typename TValue>
bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
removeOldest();
}
hash_t hash = hash_type(key);
ssize_t index = mTable->find(-1, hash, key);
if (index >= 0) {
return false;
}
if (!mTable->hasMoreRoom()) {
rehash(mTable->capacity() * 2);
}
// Would it be better to initialize a blank entry and assign key, value?
Entry initEntry(key, value);
index = mTable->add(hash, initEntry);
Entry& entry = mTable->editEntryAt(index);
attachToCache(entry);
return true;
}
template <typename TKey, typename TValue>
bool LruCache<TKey, TValue>::remove(const TKey& key) {
hash_t hash = hash_type(key);
ssize_t index = mTable->find(-1, hash, key);
if (index < 0) {
return false;
}
Entry& entry = mTable->editEntryAt(index);
if (mListener) {
(*mListener)(entry.key, entry.value);
}
detachFromCache(entry);
mTable->removeAt(index);
return true;
}
template <typename TKey, typename TValue>
bool LruCache<TKey, TValue>::removeOldest() {
if (mOldest != NULL) {
return remove(mOldest->key);
// TODO: should probably abort if false
}
return false;
}
template <typename TKey, typename TValue>
void LruCache<TKey, TValue>::clear() {
if (mListener) {
for (Entry* p = mOldest; p != NULL; p = p->child) {
(*mListener)(p->key, p->value);
}
}
mYoungest = NULL;
mOldest = NULL;
mTable->clear();
}
template <typename TKey, typename TValue>
void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
if (mYoungest == NULL) {
mYoungest = mOldest = &entry;
} else {
entry.parent = mYoungest;
mYoungest->child = &entry;
mYoungest = &entry;
}
}
template <typename TKey, typename TValue>
void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
if (entry.parent != NULL) {
entry.parent->child = entry.child;
} else {
mOldest = entry.child;
}
if (entry.child != NULL) {
entry.child->parent = entry.parent;
} else {
mYoungest = entry.parent;
}
entry.parent = NULL;
entry.child = NULL;
}
template <typename TKey, typename TValue>
void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
Entry* oldest = mOldest;
mOldest = NULL;
mYoungest = NULL;
mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
for (Entry* p = oldest; p != NULL; p = p->child) {
put(p->key, p->value);
}
}
}
#endif // ANDROID_UTILS_LRU_CACHE_H
|
