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 #include <stdlib.h>
18 #include <utils/JenkinsHash.h>
19 #include <utils/LruCache.h>
20 #include <cutils/log.h>
21 #include <gtest/gtest.h>
22
23 namespace {
24
25 typedef int SimpleKey;
26 typedef const char* StringValue;
27
28 struct ComplexKey {
29 int k;
30
ComplexKey__anon57a6895c0111::ComplexKey31 explicit ComplexKey(int k) : k(k) {
32 instanceCount += 1;
33 }
34
ComplexKey__anon57a6895c0111::ComplexKey35 ComplexKey(const ComplexKey& other) : k(other.k) {
36 instanceCount += 1;
37 }
38
~ComplexKey__anon57a6895c0111::ComplexKey39 ~ComplexKey() {
40 instanceCount -= 1;
41 }
42
operator ==__anon57a6895c0111::ComplexKey43 bool operator ==(const ComplexKey& other) const {
44 return k == other.k;
45 }
46
operator !=__anon57a6895c0111::ComplexKey47 bool operator !=(const ComplexKey& other) const {
48 return k != other.k;
49 }
50
51 static ssize_t instanceCount;
52 };
53
54 ssize_t ComplexKey::instanceCount = 0;
55
56 struct ComplexValue {
57 int v;
58
ComplexValue__anon57a6895c0111::ComplexValue59 explicit ComplexValue(int v) : v(v) {
60 instanceCount += 1;
61 }
62
ComplexValue__anon57a6895c0111::ComplexValue63 ComplexValue(const ComplexValue& other) : v(other.v) {
64 instanceCount += 1;
65 }
66
~ComplexValue__anon57a6895c0111::ComplexValue67 ~ComplexValue() {
68 instanceCount -= 1;
69 }
70
71 static ssize_t instanceCount;
72 };
73
74 ssize_t ComplexValue::instanceCount = 0;
75
76 struct KeyWithPointer {
77 int *ptr;
operator ==__anon57a6895c0111::KeyWithPointer78 bool operator ==(const KeyWithPointer& other) const {
79 return *ptr == *other.ptr;
80 }
81 };
82
83 } // namespace
84
85
86 namespace android {
87
88 typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
89
hash_type(const ComplexKey & value)90 template<> inline android::hash_t hash_type(const ComplexKey& value) {
91 return hash_type(value.k);
92 }
93
hash_type(const KeyWithPointer & value)94 template<> inline android::hash_t hash_type(const KeyWithPointer& value) {
95 return hash_type(*value.ptr);
96 }
97
98 class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
99 public:
EntryRemovedCallback()100 EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
~EntryRemovedCallback()101 ~EntryRemovedCallback() {}
operator ()(SimpleKey & k,StringValue & v)102 void operator()(SimpleKey& k, StringValue& v) {
103 callbackCount += 1;
104 lastKey = k;
105 lastValue = v;
106 }
107 ssize_t callbackCount;
108 SimpleKey lastKey;
109 StringValue lastValue;
110 };
111
112 class InvalidateKeyCallback : public OnEntryRemoved<KeyWithPointer, StringValue> {
113 public:
operator ()(KeyWithPointer & k,StringValue &)114 void operator()(KeyWithPointer& k, StringValue&) {
115 delete k.ptr;
116 k.ptr = nullptr;
117 }
118 };
119
120 class LruCacheTest : public testing::Test {
121 protected:
SetUp()122 virtual void SetUp() {
123 ComplexKey::instanceCount = 0;
124 ComplexValue::instanceCount = 0;
125 }
126
TearDown()127 virtual void TearDown() {
128 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
129 }
130
assertInstanceCount(ssize_t keys,ssize_t values)131 void assertInstanceCount(ssize_t keys, ssize_t values) {
132 if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
133 FAIL() << "Expected " << keys << " keys and " << values << " values "
134 "but there were actually " << ComplexKey::instanceCount << " keys and "
135 << ComplexValue::instanceCount << " values";
136 }
137 }
138 };
139
TEST_F(LruCacheTest,Empty)140 TEST_F(LruCacheTest, Empty) {
141 LruCache<SimpleKey, StringValue> cache(100);
142
143 EXPECT_EQ(NULL, cache.get(0));
144 EXPECT_EQ(0u, cache.size());
145 }
146
TEST_F(LruCacheTest,Simple)147 TEST_F(LruCacheTest, Simple) {
148 LruCache<SimpleKey, StringValue> cache(100);
149
150 cache.put(1, "one");
151 cache.put(2, "two");
152 cache.put(3, "three");
153 EXPECT_STREQ("one", cache.get(1));
154 EXPECT_STREQ("two", cache.get(2));
155 EXPECT_STREQ("three", cache.get(3));
156 EXPECT_EQ(3u, cache.size());
157 }
158
TEST_F(LruCacheTest,MaxCapacity)159 TEST_F(LruCacheTest, MaxCapacity) {
160 LruCache<SimpleKey, StringValue> cache(2);
161
162 cache.put(1, "one");
163 cache.put(2, "two");
164 cache.put(3, "three");
165 EXPECT_EQ(NULL, cache.get(1));
166 EXPECT_STREQ("two", cache.get(2));
167 EXPECT_STREQ("three", cache.get(3));
168 EXPECT_EQ(2u, cache.size());
169 }
170
TEST_F(LruCacheTest,RemoveLru)171 TEST_F(LruCacheTest, RemoveLru) {
172 LruCache<SimpleKey, StringValue> cache(100);
173
174 cache.put(1, "one");
175 cache.put(2, "two");
176 cache.put(3, "three");
177 cache.removeOldest();
178 EXPECT_EQ(NULL, cache.get(1));
179 EXPECT_STREQ("two", cache.get(2));
180 EXPECT_STREQ("three", cache.get(3));
181 EXPECT_EQ(2u, cache.size());
182 }
183
TEST_F(LruCacheTest,GetUpdatesLru)184 TEST_F(LruCacheTest, GetUpdatesLru) {
185 LruCache<SimpleKey, StringValue> cache(100);
186
187 cache.put(1, "one");
188 cache.put(2, "two");
189 cache.put(3, "three");
190 EXPECT_STREQ("one", cache.get(1));
191 cache.removeOldest();
192 EXPECT_STREQ("one", cache.get(1));
193 EXPECT_EQ(NULL, cache.get(2));
194 EXPECT_STREQ("three", cache.get(3));
195 EXPECT_EQ(2u, cache.size());
196 }
197
hash_int(int x)198 uint32_t hash_int(int x) {
199 return JenkinsHashWhiten(JenkinsHashMix(0, x));
200 }
201
TEST_F(LruCacheTest,StressTest)202 TEST_F(LruCacheTest, StressTest) {
203 const size_t kCacheSize = 512;
204 LruCache<SimpleKey, StringValue> cache(512);
205 const size_t kNumKeys = 16 * 1024;
206 const size_t kNumIters = 100000;
207 char* strings[kNumKeys];
208
209 for (size_t i = 0; i < kNumKeys; i++) {
210 strings[i] = (char *)malloc(16);
211 sprintf(strings[i], "%zu", i);
212 }
213
214 srandom(12345);
215 int hitCount = 0;
216 for (size_t i = 0; i < kNumIters; i++) {
217 int index = random() % kNumKeys;
218 uint32_t key = hash_int(index);
219 const char *val = cache.get(key);
220 if (val != NULL) {
221 EXPECT_EQ(strings[index], val);
222 hitCount++;
223 } else {
224 cache.put(key, strings[index]);
225 }
226 }
227 size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys;
228 EXPECT_LT(int(expectedHitCount * 0.9), hitCount);
229 EXPECT_GT(int(expectedHitCount * 1.1), hitCount);
230 EXPECT_EQ(kCacheSize, cache.size());
231
232 for (size_t i = 0; i < kNumKeys; i++) {
233 free((void *)strings[i]);
234 }
235 }
236
TEST_F(LruCacheTest,NoLeak)237 TEST_F(LruCacheTest, NoLeak) {
238 ComplexCache cache(100);
239
240 cache.put(ComplexKey(0), ComplexValue(0));
241 cache.put(ComplexKey(1), ComplexValue(1));
242 EXPECT_EQ(2U, cache.size());
243 assertInstanceCount(2, 3); // the member mNullValue counts as an instance
244 }
245
TEST_F(LruCacheTest,Clear)246 TEST_F(LruCacheTest, Clear) {
247 ComplexCache cache(100);
248
249 cache.put(ComplexKey(0), ComplexValue(0));
250 cache.put(ComplexKey(1), ComplexValue(1));
251 EXPECT_EQ(2U, cache.size());
252 assertInstanceCount(2, 3);
253 cache.clear();
254 assertInstanceCount(0, 1);
255 }
256
TEST_F(LruCacheTest,ClearNoDoubleFree)257 TEST_F(LruCacheTest, ClearNoDoubleFree) {
258 {
259 ComplexCache cache(100);
260
261 cache.put(ComplexKey(0), ComplexValue(0));
262 cache.put(ComplexKey(1), ComplexValue(1));
263 EXPECT_EQ(2U, cache.size());
264 assertInstanceCount(2, 3);
265 cache.removeOldest();
266 cache.clear();
267 assertInstanceCount(0, 1);
268 }
269 assertInstanceCount(0, 0);
270 }
271
TEST_F(LruCacheTest,ClearReuseOk)272 TEST_F(LruCacheTest, ClearReuseOk) {
273 ComplexCache cache(100);
274
275 cache.put(ComplexKey(0), ComplexValue(0));
276 cache.put(ComplexKey(1), ComplexValue(1));
277 EXPECT_EQ(2U, cache.size());
278 assertInstanceCount(2, 3);
279 cache.clear();
280 assertInstanceCount(0, 1);
281 cache.put(ComplexKey(0), ComplexValue(0));
282 cache.put(ComplexKey(1), ComplexValue(1));
283 EXPECT_EQ(2U, cache.size());
284 assertInstanceCount(2, 3);
285 }
286
TEST_F(LruCacheTest,Callback)287 TEST_F(LruCacheTest, Callback) {
288 LruCache<SimpleKey, StringValue> cache(100);
289 EntryRemovedCallback callback;
290 cache.setOnEntryRemovedListener(&callback);
291
292 cache.put(1, "one");
293 cache.put(2, "two");
294 cache.put(3, "three");
295 EXPECT_EQ(3U, cache.size());
296 cache.removeOldest();
297 EXPECT_EQ(1, callback.callbackCount);
298 EXPECT_EQ(1, callback.lastKey);
299 EXPECT_STREQ("one", callback.lastValue);
300 }
301
TEST_F(LruCacheTest,CallbackOnClear)302 TEST_F(LruCacheTest, CallbackOnClear) {
303 LruCache<SimpleKey, StringValue> cache(100);
304 EntryRemovedCallback callback;
305 cache.setOnEntryRemovedListener(&callback);
306
307 cache.put(1, "one");
308 cache.put(2, "two");
309 cache.put(3, "three");
310 EXPECT_EQ(3U, cache.size());
311 cache.clear();
312 EXPECT_EQ(3, callback.callbackCount);
313 }
314
TEST_F(LruCacheTest,CallbackRemovesKeyWorksOK)315 TEST_F(LruCacheTest, CallbackRemovesKeyWorksOK) {
316 LruCache<KeyWithPointer, StringValue> cache(1);
317 InvalidateKeyCallback callback;
318 cache.setOnEntryRemovedListener(&callback);
319 KeyWithPointer key1;
320 key1.ptr = new int(1);
321 KeyWithPointer key2;
322 key2.ptr = new int(2);
323
324 cache.put(key1, "one");
325 // As the size of the cache is 1, the put will call the callback.
326 // Make sure everything goes smoothly even if the callback invalidates
327 // the key (b/24785286)
328 cache.put(key2, "two");
329 EXPECT_EQ(1U, cache.size());
330 EXPECT_STREQ("two", cache.get(key2));
331 cache.clear();
332 }
333
TEST_F(LruCacheTest,IteratorCheck)334 TEST_F(LruCacheTest, IteratorCheck) {
335 LruCache<int, int> cache(100);
336
337 cache.put(1, 4);
338 cache.put(2, 5);
339 cache.put(3, 6);
340 EXPECT_EQ(3U, cache.size());
341
342 LruCache<int, int>::Iterator it(cache);
343 std::unordered_set<int> returnedValues;
344 while (it.next()) {
345 int v = it.value();
346 // Check we haven't seen the value before.
347 EXPECT_TRUE(returnedValues.find(v) == returnedValues.end());
348 returnedValues.insert(v);
349 }
350 EXPECT_EQ(std::unordered_set<int>({4, 5, 6}), returnedValues);
351 }
352
TEST_F(LruCacheTest,EmptyCacheIterator)353 TEST_F(LruCacheTest, EmptyCacheIterator) {
354 // Check that nothing crashes...
355 LruCache<int, int> cache(100);
356
357 LruCache<int, int>::Iterator it(cache);
358 std::unordered_set<int> returnedValues;
359 while (it.next()) {
360 returnedValues.insert(it.value());
361 }
362 EXPECT_EQ(std::unordered_set<int>(), returnedValues);
363 }
364
TEST_F(LruCacheTest,OneElementCacheIterator)365 TEST_F(LruCacheTest, OneElementCacheIterator) {
366 // Check that nothing crashes...
367 LruCache<int, int> cache(100);
368 cache.put(1, 2);
369
370 LruCache<int, int>::Iterator it(cache);
371 std::unordered_set<int> returnedValues;
372 while (it.next()) {
373 returnedValues.insert(it.value());
374 }
375 EXPECT_EQ(std::unordered_set<int>({ 2 }), returnedValues);
376 }
377
TEST_F(LruCacheTest,OneElementCacheRemove)378 TEST_F(LruCacheTest, OneElementCacheRemove) {
379 LruCache<int, int> cache(100);
380 cache.put(1, 2);
381
382 cache.remove(1);
383
384 LruCache<int, int>::Iterator it(cache);
385 std::unordered_set<int> returnedValues;
386 while (it.next()) {
387 returnedValues.insert(it.value());
388 }
389 EXPECT_EQ(std::unordered_set<int>({ }), returnedValues);
390 }
391
TEST_F(LruCacheTest,Remove)392 TEST_F(LruCacheTest, Remove) {
393 LruCache<int, int> cache(100);
394 cache.put(1, 4);
395 cache.put(2, 5);
396 cache.put(3, 6);
397
398 cache.remove(2);
399
400 LruCache<int, int>::Iterator it(cache);
401 std::unordered_set<int> returnedValues;
402 while (it.next()) {
403 returnedValues.insert(it.value());
404 }
405 EXPECT_EQ(std::unordered_set<int>({ 4, 6 }), returnedValues);
406 }
407
TEST_F(LruCacheTest,RemoveYoungest)408 TEST_F(LruCacheTest, RemoveYoungest) {
409 LruCache<int, int> cache(100);
410 cache.put(1, 4);
411 cache.put(2, 5);
412 cache.put(3, 6);
413
414 cache.remove(3);
415
416 LruCache<int, int>::Iterator it(cache);
417 std::unordered_set<int> returnedValues;
418 while (it.next()) {
419 returnedValues.insert(it.value());
420 }
421 EXPECT_EQ(std::unordered_set<int>({ 4, 5 }), returnedValues);
422 }
423
TEST_F(LruCacheTest,RemoveNonMember)424 TEST_F(LruCacheTest, RemoveNonMember) {
425 LruCache<int, int> cache(100);
426 cache.put(1, 4);
427 cache.put(2, 5);
428 cache.put(3, 6);
429
430 cache.remove(7);
431
432 LruCache<int, int>::Iterator it(cache);
433 std::unordered_set<int> returnedValues;
434 while (it.next()) {
435 returnedValues.insert(it.value());
436 }
437 EXPECT_EQ(std::unordered_set<int>({ 4, 5, 6 }), returnedValues);
438 }
439
440 }
441