/* * 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. */ #include <stdlib.h> #include <android/log.h> #include <gtest/gtest.h> #include <utils/JenkinsHash.h> #include <utils/LruCache.h> namespace { typedef int SimpleKey; typedef const char* StringValue; struct ComplexKey { int k; explicit ComplexKey(int k) : k(k) { instanceCount += 1; } ComplexKey(const ComplexKey& other) : k(other.k) { instanceCount += 1; } ~ComplexKey() { instanceCount -= 1; } bool operator ==(const ComplexKey& other) const { return k == other.k; } bool operator !=(const ComplexKey& other) const { return k != other.k; } static ssize_t instanceCount; }; ssize_t ComplexKey::instanceCount = 0; struct ComplexValue { int v; explicit ComplexValue(int v) : v(v) { instanceCount += 1; } ComplexValue(const ComplexValue& other) : v(other.v) { instanceCount += 1; } ~ComplexValue() { instanceCount -= 1; } static ssize_t instanceCount; }; ssize_t ComplexValue::instanceCount = 0; struct KeyWithPointer { int *ptr; bool operator ==(const KeyWithPointer& other) const { return *ptr == *other.ptr; } }; struct KeyFailsOnCopy : public ComplexKey { public: KeyFailsOnCopy(const KeyFailsOnCopy& key) : ComplexKey(key) { ADD_FAILURE(); } KeyFailsOnCopy(int key) : ComplexKey(key) { } }; } // namespace namespace android { typedef LruCache<ComplexKey, ComplexValue> ComplexCache; template<> inline android::hash_t hash_type(const ComplexKey& value) { return hash_type(value.k); } template<> inline android::hash_t hash_type(const KeyWithPointer& value) { return hash_type(*value.ptr); } template<> inline android::hash_t hash_type(const KeyFailsOnCopy& value) { return hash_type<ComplexKey>(value); } class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> { public: EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { } ~EntryRemovedCallback() {} void operator()(SimpleKey& k, StringValue& v) { callbackCount += 1; lastKey = k; lastValue = v; } ssize_t callbackCount; SimpleKey lastKey; StringValue lastValue; }; class InvalidateKeyCallback : public OnEntryRemoved<KeyWithPointer, StringValue> { public: void operator()(KeyWithPointer& k, StringValue&) { delete k.ptr; k.ptr = nullptr; } }; class LruCacheTest : public testing::Test { protected: virtual void SetUp() { ComplexKey::instanceCount = 0; ComplexValue::instanceCount = 0; } virtual void TearDown() { ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); } void assertInstanceCount(ssize_t keys, ssize_t values) { if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) { FAIL() << "Expected " << keys << " keys and " << values << " values " "but there were actually " << ComplexKey::instanceCount << " keys and " << ComplexValue::instanceCount << " values"; } } }; TEST_F(LruCacheTest, Empty) { LruCache<SimpleKey, StringValue> cache(100); EXPECT_EQ(NULL, cache.get(0)); EXPECT_EQ(0u, cache.size()); } TEST_F(LruCacheTest, Simple) { LruCache<SimpleKey, StringValue> cache(100); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); EXPECT_STREQ("one", cache.get(1)); EXPECT_STREQ("two", cache.get(2)); EXPECT_STREQ("three", cache.get(3)); EXPECT_EQ(3u, cache.size()); } TEST_F(LruCacheTest, MaxCapacity) { LruCache<SimpleKey, StringValue> cache(2); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); EXPECT_EQ(NULL, cache.get(1)); EXPECT_STREQ("two", cache.get(2)); EXPECT_STREQ("three", cache.get(3)); EXPECT_EQ(2u, cache.size()); } TEST_F(LruCacheTest, RemoveLru) { LruCache<SimpleKey, StringValue> cache(100); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); cache.removeOldest(); EXPECT_EQ(NULL, cache.get(1)); EXPECT_STREQ("two", cache.get(2)); EXPECT_STREQ("three", cache.get(3)); EXPECT_EQ(2u, cache.size()); } TEST_F(LruCacheTest, GetUpdatesLru) { LruCache<SimpleKey, StringValue> cache(100); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); EXPECT_STREQ("one", cache.get(1)); cache.removeOldest(); EXPECT_STREQ("one", cache.get(1)); EXPECT_EQ(NULL, cache.get(2)); EXPECT_STREQ("three", cache.get(3)); EXPECT_EQ(2u, cache.size()); } uint32_t hash_int(int x) { return JenkinsHashWhiten(JenkinsHashMix(0, x)); } TEST_F(LruCacheTest, StressTest) { const size_t kCacheSize = 512; LruCache<SimpleKey, StringValue> cache(512); const size_t kNumKeys = 16 * 1024; const size_t kNumIters = 100000; char* strings[kNumKeys]; for (size_t i = 0; i < kNumKeys; i++) { strings[i] = (char *)malloc(16); sprintf(strings[i], "%zu", i); } srandom(12345); int hitCount = 0; for (size_t i = 0; i < kNumIters; i++) { int index = random() % kNumKeys; uint32_t key = hash_int(index); const char *val = cache.get(key); if (val != NULL) { EXPECT_EQ(strings[index], val); hitCount++; } else { cache.put(key, strings[index]); } } size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys; EXPECT_LT(int(expectedHitCount * 0.9), hitCount); EXPECT_GT(int(expectedHitCount * 1.1), hitCount); EXPECT_EQ(kCacheSize, cache.size()); for (size_t i = 0; i < kNumKeys; i++) { free((void *)strings[i]); } } TEST_F(LruCacheTest, NoLeak) { ComplexCache cache(100); cache.put(ComplexKey(0), ComplexValue(0)); cache.put(ComplexKey(1), ComplexValue(1)); EXPECT_EQ(2U, cache.size()); assertInstanceCount(2, 3); // the member mNullValue counts as an instance } TEST_F(LruCacheTest, Clear) { ComplexCache cache(100); cache.put(ComplexKey(0), ComplexValue(0)); cache.put(ComplexKey(1), ComplexValue(1)); EXPECT_EQ(2U, cache.size()); assertInstanceCount(2, 3); cache.clear(); assertInstanceCount(0, 1); } TEST_F(LruCacheTest, ClearNoDoubleFree) { { ComplexCache cache(100); cache.put(ComplexKey(0), ComplexValue(0)); cache.put(ComplexKey(1), ComplexValue(1)); EXPECT_EQ(2U, cache.size()); assertInstanceCount(2, 3); cache.removeOldest(); cache.clear(); assertInstanceCount(0, 1); } assertInstanceCount(0, 0); } TEST_F(LruCacheTest, ClearReuseOk) { ComplexCache cache(100); cache.put(ComplexKey(0), ComplexValue(0)); cache.put(ComplexKey(1), ComplexValue(1)); EXPECT_EQ(2U, cache.size()); assertInstanceCount(2, 3); cache.clear(); assertInstanceCount(0, 1); cache.put(ComplexKey(0), ComplexValue(0)); cache.put(ComplexKey(1), ComplexValue(1)); EXPECT_EQ(2U, cache.size()); assertInstanceCount(2, 3); } TEST_F(LruCacheTest, Callback) { LruCache<SimpleKey, StringValue> cache(100); EntryRemovedCallback callback; cache.setOnEntryRemovedListener(&callback); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); EXPECT_EQ(3U, cache.size()); cache.removeOldest(); EXPECT_EQ(1, callback.callbackCount); EXPECT_EQ(1, callback.lastKey); EXPECT_STREQ("one", callback.lastValue); } TEST_F(LruCacheTest, CallbackOnClear) { LruCache<SimpleKey, StringValue> cache(100); EntryRemovedCallback callback; cache.setOnEntryRemovedListener(&callback); cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three"); EXPECT_EQ(3U, cache.size()); cache.clear(); EXPECT_EQ(3, callback.callbackCount); } TEST_F(LruCacheTest, CallbackRemovesKeyWorksOK) { LruCache<KeyWithPointer, StringValue> cache(1); InvalidateKeyCallback callback; cache.setOnEntryRemovedListener(&callback); KeyWithPointer key1; key1.ptr = new int(1); KeyWithPointer key2; key2.ptr = new int(2); cache.put(key1, "one"); // As the size of the cache is 1, the put will call the callback. // Make sure everything goes smoothly even if the callback invalidates // the key (b/24785286) cache.put(key2, "two"); EXPECT_EQ(1U, cache.size()); EXPECT_STREQ("two", cache.get(key2)); cache.clear(); } TEST_F(LruCacheTest, IteratorCheck) { LruCache<int, int> cache(100); cache.put(1, 4); cache.put(2, 5); cache.put(3, 6); EXPECT_EQ(3U, cache.size()); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { int v = it.value(); // Check we haven't seen the value before. EXPECT_TRUE(returnedValues.find(v) == returnedValues.end()); returnedValues.insert(v); } EXPECT_EQ(std::unordered_set<int>({4, 5, 6}), returnedValues); } TEST_F(LruCacheTest, EmptyCacheIterator) { // Check that nothing crashes... LruCache<int, int> cache(100); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { returnedValues.insert(it.value()); } EXPECT_EQ(std::unordered_set<int>(), returnedValues); } TEST_F(LruCacheTest, OneElementCacheIterator) { // Check that nothing crashes... LruCache<int, int> cache(100); cache.put(1, 2); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { returnedValues.insert(it.value()); } EXPECT_EQ(std::unordered_set<int>({ 2 }), returnedValues); } TEST_F(LruCacheTest, OneElementCacheRemove) { LruCache<int, int> cache(100); cache.put(1, 2); cache.remove(1); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { returnedValues.insert(it.value()); } EXPECT_EQ(std::unordered_set<int>({ }), returnedValues); } TEST_F(LruCacheTest, Remove) { LruCache<int, int> cache(100); cache.put(1, 4); cache.put(2, 5); cache.put(3, 6); cache.remove(2); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { returnedValues.insert(it.value()); } EXPECT_EQ(std::unordered_set<int>({ 4, 6 }), returnedValues); } TEST_F(LruCacheTest, RemoveYoungest) { LruCache<int, int> cache(100); cache.put(1, 4); cache.put(2, 5); cache.put(3, 6); cache.remove(3); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { returnedValues.insert(it.value()); } EXPECT_EQ(std::unordered_set<int>({ 4, 5 }), returnedValues); } TEST_F(LruCacheTest, RemoveNonMember) { LruCache<int, int> cache(100); cache.put(1, 4); cache.put(2, 5); cache.put(3, 6); cache.remove(7); LruCache<int, int>::Iterator it(cache); std::unordered_set<int> returnedValues; while (it.next()) { returnedValues.insert(it.value()); } EXPECT_EQ(std::unordered_set<int>({ 4, 5, 6 }), returnedValues); } TEST_F(LruCacheTest, DontCopyKeyInGet) { LruCache<KeyFailsOnCopy, KeyFailsOnCopy> cache(1); // Check that get doesn't copy the key cache.get(KeyFailsOnCopy(0)); } }