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 23 namespace android { 24 25 typedef int SimpleKey; 26 typedef const char* StringValue; 27 28 struct 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 54 ssize_t ComplexKey::instanceCount = 0; 55 56 template<> inline hash_t hash_type(const ComplexKey& value) { 57 return hash_type(value.k); 58 } 59 60 struct 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 78 ssize_t ComplexValue::instanceCount = 0; 79 80 typedef LruCache<ComplexKey, ComplexValue> ComplexCache; 81 82 class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> { 83 public: 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 96 class LruCacheTest : public testing::Test { 97 protected: 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 116 TEST_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 123 TEST_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 135 TEST_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 147 TEST_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 160 TEST_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 174 uint32_t hash_int(int x) { 175 return JenkinsHashWhiten(JenkinsHashMix(0, x)); 176 } 177 178 TEST_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], "%zu", 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 213 TEST_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 222 TEST_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 233 TEST_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 248 TEST_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 263 TEST_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 278 TEST_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
