1 files changed, 291 insertions, 0 deletions
diff --git a/libutils/tests/LruCache_test.cpp b/libutils/tests/LruCache_test.cpp
new file mode 100644
index 0000000..e573952
--- /dev/null
+++ b/libutils/tests/LruCache_test.cpp
@@ -0,0 +1,291 @@
+/*
+ * 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);
+}
+
+}