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