blob: e573952c0739ffc10a8d9f86f20e3455d0c40f7f [file] [log] [blame]
/*
* 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 <utils/JenkinsHash.h>
#include <utils/LruCache.h>
#include <cutils/log.h>
#include <gtest/gtest.h>
namespace android {
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;
template<> inline hash_t hash_type(const ComplexKey& value) {
return hash_type(value.k);
}
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;
typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
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 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], "%d", 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(2, cache.size());
assertInstanceCount(2, 3); // the null value 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(2, 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(2, 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(2, cache.size());
assertInstanceCount(2, 3);
cache.clear();
assertInstanceCount(0, 1);
cache.put(ComplexKey(0), ComplexValue(0));
cache.put(ComplexKey(1), ComplexValue(1));
EXPECT_EQ(2, 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(3, 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(3, cache.size());
cache.clear();
EXPECT_EQ(3, callback.callbackCount);
}
}