xref: /system/core/libutils/tests/LruCache_test.cpp

/*
 * 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 {

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;
    }
};

} // 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);
}

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);
}

}