1b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien/* 2b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * Copyright (C) 2012 The Android Open Source Project 3b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * 4b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * Licensed under the Apache License, Version 2.0 (the "License"); 5b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * you may not use this file except in compliance with the License. 6b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * You may obtain a copy of the License at 7b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * 8b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * http://www.apache.org/licenses/LICENSE-2.0 9b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * 10b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * Unless required by applicable law or agreed to in writing, software 11b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * distributed under the License is distributed on an "AS IS" BASIS, 12b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * See the License for the specific language governing permissions and 14b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien * limitations under the License. 15b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien */ 16b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 17b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien#include <stdlib.h> 18b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien#include <utils/JenkinsHash.h> 19b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien#include <utils/LruCache.h> 20b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien#include <cutils/log.h> 21b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien#include <gtest/gtest.h> 22b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 23b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Leviennamespace android { 24b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 25b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levientypedef int SimpleKey; 26b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levientypedef const char* StringValue; 27b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 28b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienstruct ComplexKey { 29b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien int k; 30b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 31b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien explicit ComplexKey(int k) : k(k) { 32b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien instanceCount += 1; 33b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 34b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 35b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexKey(const ComplexKey& other) : k(other.k) { 36b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien instanceCount += 1; 37b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 38b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 39b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ~ComplexKey() { 40b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien instanceCount -= 1; 41b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 42b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 43b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien bool operator ==(const ComplexKey& other) const { 44b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return k == other.k; 45b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 46b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 47b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien bool operator !=(const ComplexKey& other) const { 48b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return k != other.k; 49b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 50b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 51b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien static ssize_t instanceCount; 52b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien}; 53b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 54b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienssize_t ComplexKey::instanceCount = 0; 55b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 56b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levientemplate<> inline hash_t hash_type(const ComplexKey& value) { 57b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return hash_type(value.k); 58b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 59b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 60b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienstruct ComplexValue { 61b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien int v; 62b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 63b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien explicit ComplexValue(int v) : v(v) { 64b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien instanceCount += 1; 65b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 66b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 67b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexValue(const ComplexValue& other) : v(other.v) { 68b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien instanceCount += 1; 69b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 70b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 71b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ~ComplexValue() { 72b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien instanceCount -= 1; 73b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 74b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 75b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien static ssize_t instanceCount; 76b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien}; 77b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 78b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienssize_t ComplexValue::instanceCount = 0; 79b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 80b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levientypedef LruCache<ComplexKey, ComplexValue> ComplexCache; 81b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 82b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienclass EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> { 83b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienpublic: 84b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { } 85b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ~EntryRemovedCallback() {} 86b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien void operator()(SimpleKey& k, StringValue& v) { 87b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien callbackCount += 1; 88b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien lastKey = k; 89b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien lastValue = v; 90b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 91b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ssize_t callbackCount; 92b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien SimpleKey lastKey; 93b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien StringValue lastValue; 94b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien}; 95b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 96b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienclass LruCacheTest : public testing::Test { 97b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienprotected: 98b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien virtual void SetUp() { 99b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexKey::instanceCount = 0; 100b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexValue::instanceCount = 0; 101b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 102b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 103b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien virtual void TearDown() { 104b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); 105b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 106b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 107b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien void assertInstanceCount(ssize_t keys, ssize_t values) { 108b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) { 109b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien FAIL() << "Expected " << keys << " keys and " << values << " values " 110b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien "but there were actually " << ComplexKey::instanceCount << " keys and " 111b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien << ComplexValue::instanceCount << " values"; 112b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 113b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 114b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien}; 115b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 116b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, Empty) { 117b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(100); 118b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 119b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(NULL, cache.get(0)); 120b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(0u, cache.size()); 121b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 122b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 123b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, Simple) { 124b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(100); 125b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 126b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(1, "one"); 127b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(2, "two"); 128b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(3, "three"); 129b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("one", cache.get(1)); 130b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("two", cache.get(2)); 131b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("three", cache.get(3)); 132b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(3u, cache.size()); 133b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 134b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 135b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, MaxCapacity) { 136b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(2); 137b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 138b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(1, "one"); 139b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(2, "two"); 140b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(3, "three"); 141b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(NULL, cache.get(1)); 142b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("two", cache.get(2)); 143b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("three", cache.get(3)); 144b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2u, cache.size()); 145b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 146b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 147b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, RemoveLru) { 148b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(100); 149b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 150b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(1, "one"); 151b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(2, "two"); 152b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(3, "three"); 153b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.removeOldest(); 154b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(NULL, cache.get(1)); 155b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("two", cache.get(2)); 156b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("three", cache.get(3)); 157b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2u, cache.size()); 158b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 159b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 160b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, GetUpdatesLru) { 161b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(100); 162b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 163b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(1, "one"); 164b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(2, "two"); 165b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(3, "three"); 166b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("one", cache.get(1)); 167b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.removeOldest(); 168b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("one", cache.get(1)); 169b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(NULL, cache.get(2)); 170b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("three", cache.get(3)); 171b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2u, cache.size()); 172b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 173b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 174b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levienuint32_t hash_int(int x) { 175b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien return JenkinsHashWhiten(JenkinsHashMix(0, x)); 176b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 177b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 178b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, StressTest) { 179b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien const size_t kCacheSize = 512; 180b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(512); 181b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien const size_t kNumKeys = 16 * 1024; 182b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien const size_t kNumIters = 100000; 183b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien char* strings[kNumKeys]; 184b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 185b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien for (size_t i = 0; i < kNumKeys; i++) { 186b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien strings[i] = (char *)malloc(16); 187b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien sprintf(strings[i], "%d", i); 188b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 189b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 190b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien srandom(12345); 191b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien int hitCount = 0; 192b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien for (size_t i = 0; i < kNumIters; i++) { 193b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien int index = random() % kNumKeys; 194b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien uint32_t key = hash_int(index); 195b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien const char *val = cache.get(key); 196b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien if (val != NULL) { 197b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(strings[index], val); 198b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien hitCount++; 199b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } else { 200b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(key, strings[index]); 201b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 202b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 203b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys; 204b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_LT(int(expectedHitCount * 0.9), hitCount); 205b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_GT(int(expectedHitCount * 1.1), hitCount); 206b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(kCacheSize, cache.size()); 207b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 208b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien for (size_t i = 0; i < kNumKeys; i++) { 209b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien free((void *)strings[i]); 210b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 211b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 212b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 213b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, NoLeak) { 214b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexCache cache(100); 215b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 216b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(0), ComplexValue(0)); 217b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(1), ComplexValue(1)); 218b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2, cache.size()); 219b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(2, 3); // the null value counts as an instance 220b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 221b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 222b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, Clear) { 223b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexCache cache(100); 224b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 225b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(0), ComplexValue(0)); 226b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(1), ComplexValue(1)); 227b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2, cache.size()); 228b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(2, 3); 229b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.clear(); 230b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(0, 1); 231b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 232b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 233b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, ClearNoDoubleFree) { 234b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien { 235b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexCache cache(100); 236b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 237b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(0), ComplexValue(0)); 238b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(1), ComplexValue(1)); 239b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2, cache.size()); 240b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(2, 3); 241b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.removeOldest(); 242b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.clear(); 243b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(0, 1); 244b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien } 245b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(0, 0); 246b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 247b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 248b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, ClearReuseOk) { 249b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien ComplexCache cache(100); 250b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 251b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(0), ComplexValue(0)); 252b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(1), ComplexValue(1)); 253b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2, cache.size()); 254b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(2, 3); 255b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.clear(); 256b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(0, 1); 257b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(0), ComplexValue(0)); 258b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(ComplexKey(1), ComplexValue(1)); 259b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(2, cache.size()); 260b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien assertInstanceCount(2, 3); 261b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 262b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 263b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, Callback) { 264b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(100); 265b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EntryRemovedCallback callback; 266b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.setOnEntryRemovedListener(&callback); 267b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 268b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(1, "one"); 269b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(2, "two"); 270b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(3, "three"); 271b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(3, cache.size()); 272b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.removeOldest(); 273b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(1, callback.callbackCount); 274b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(1, callback.lastKey); 275b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_STREQ("one", callback.lastValue); 276b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 277b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 278b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph LevienTEST_F(LruCacheTest, CallbackOnClear) { 279b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien LruCache<SimpleKey, StringValue> cache(100); 280b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EntryRemovedCallback callback; 281b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.setOnEntryRemovedListener(&callback); 282b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 283b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(1, "one"); 284b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(2, "two"); 285b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.put(3, "three"); 286b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(3, cache.size()); 287b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien cache.clear(); 288b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien EXPECT_EQ(3, callback.callbackCount); 289b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 290b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien 291b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien} 292