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