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