Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 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> |
Mark Salyzyn | 66ce3e0 | 2016-09-28 10:07:20 -0700 | [diff] [blame] | 18 | |
| 19 | #include <android/log.h> |
| 20 | #include <gtest/gtest.h> |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 21 | #include <utils/JenkinsHash.h> |
| 22 | #include <utils/LruCache.h> |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 23 | |
Dan Albert | 27d166c | 2014-10-16 20:47:51 -0700 | [diff] [blame] | 24 | namespace { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 25 | |
| 26 | typedef int SimpleKey; |
| 27 | typedef const char* StringValue; |
| 28 | |
| 29 | struct ComplexKey { |
| 30 | int k; |
| 31 | |
| 32 | explicit ComplexKey(int k) : k(k) { |
| 33 | instanceCount += 1; |
| 34 | } |
| 35 | |
| 36 | ComplexKey(const ComplexKey& other) : k(other.k) { |
| 37 | instanceCount += 1; |
| 38 | } |
| 39 | |
| 40 | ~ComplexKey() { |
| 41 | instanceCount -= 1; |
| 42 | } |
| 43 | |
| 44 | bool operator ==(const ComplexKey& other) const { |
| 45 | return k == other.k; |
| 46 | } |
| 47 | |
| 48 | bool operator !=(const ComplexKey& other) const { |
| 49 | return k != other.k; |
| 50 | } |
| 51 | |
| 52 | static ssize_t instanceCount; |
| 53 | }; |
| 54 | |
| 55 | ssize_t ComplexKey::instanceCount = 0; |
| 56 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 57 | struct ComplexValue { |
| 58 | int v; |
| 59 | |
| 60 | explicit ComplexValue(int v) : v(v) { |
| 61 | instanceCount += 1; |
| 62 | } |
| 63 | |
| 64 | ComplexValue(const ComplexValue& other) : v(other.v) { |
| 65 | instanceCount += 1; |
| 66 | } |
| 67 | |
| 68 | ~ComplexValue() { |
| 69 | instanceCount -= 1; |
| 70 | } |
| 71 | |
| 72 | static ssize_t instanceCount; |
| 73 | }; |
| 74 | |
| 75 | ssize_t ComplexValue::instanceCount = 0; |
| 76 | |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 77 | struct KeyWithPointer { |
| 78 | int *ptr; |
| 79 | bool operator ==(const KeyWithPointer& other) const { |
| 80 | return *ptr == *other.ptr; |
| 81 | } |
| 82 | }; |
| 83 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 84 | struct KeyFailsOnCopy : public ComplexKey { |
| 85 | public: |
| 86 | KeyFailsOnCopy(const KeyFailsOnCopy& key) : ComplexKey(key) { |
| 87 | ADD_FAILURE(); |
| 88 | } |
| 89 | KeyFailsOnCopy(int key) : ComplexKey(key) { } |
| 90 | }; |
| 91 | |
Dan Albert | 27d166c | 2014-10-16 20:47:51 -0700 | [diff] [blame] | 92 | } // namespace |
| 93 | |
| 94 | |
| 95 | namespace android { |
| 96 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 97 | typedef LruCache<ComplexKey, ComplexValue> ComplexCache; |
| 98 | |
Dan Albert | 27d166c | 2014-10-16 20:47:51 -0700 | [diff] [blame] | 99 | template<> inline android::hash_t hash_type(const ComplexKey& value) { |
| 100 | return hash_type(value.k); |
| 101 | } |
| 102 | |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 103 | template<> inline android::hash_t hash_type(const KeyWithPointer& value) { |
| 104 | return hash_type(*value.ptr); |
| 105 | } |
| 106 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 107 | template<> inline android::hash_t hash_type(const KeyFailsOnCopy& value) { |
| 108 | return hash_type<ComplexKey>(value); |
| 109 | } |
| 110 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 111 | class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> { |
| 112 | public: |
Yi Kong | e1731a4 | 2018-07-16 18:11:34 -0700 | [diff] [blame] | 113 | EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(nullptr) { } |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 114 | ~EntryRemovedCallback() {} |
| 115 | void operator()(SimpleKey& k, StringValue& v) { |
| 116 | callbackCount += 1; |
| 117 | lastKey = k; |
| 118 | lastValue = v; |
| 119 | } |
| 120 | ssize_t callbackCount; |
| 121 | SimpleKey lastKey; |
| 122 | StringValue lastValue; |
| 123 | }; |
| 124 | |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 125 | class InvalidateKeyCallback : public OnEntryRemoved<KeyWithPointer, StringValue> { |
| 126 | public: |
| 127 | void operator()(KeyWithPointer& k, StringValue&) { |
| 128 | delete k.ptr; |
| 129 | k.ptr = nullptr; |
| 130 | } |
| 131 | }; |
| 132 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 133 | class LruCacheTest : public testing::Test { |
| 134 | protected: |
| 135 | virtual void SetUp() { |
| 136 | ComplexKey::instanceCount = 0; |
| 137 | ComplexValue::instanceCount = 0; |
| 138 | } |
| 139 | |
| 140 | virtual void TearDown() { |
| 141 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); |
| 142 | } |
| 143 | |
| 144 | void assertInstanceCount(ssize_t keys, ssize_t values) { |
| 145 | if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) { |
| 146 | FAIL() << "Expected " << keys << " keys and " << values << " values " |
| 147 | "but there were actually " << ComplexKey::instanceCount << " keys and " |
| 148 | << ComplexValue::instanceCount << " values"; |
| 149 | } |
| 150 | } |
| 151 | }; |
| 152 | |
| 153 | TEST_F(LruCacheTest, Empty) { |
| 154 | LruCache<SimpleKey, StringValue> cache(100); |
| 155 | |
Yi Kong | e1731a4 | 2018-07-16 18:11:34 -0700 | [diff] [blame] | 156 | EXPECT_EQ(nullptr, cache.get(0)); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 157 | EXPECT_EQ(0u, cache.size()); |
| 158 | } |
| 159 | |
| 160 | TEST_F(LruCacheTest, Simple) { |
| 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 | EXPECT_STREQ("two", cache.get(2)); |
| 168 | EXPECT_STREQ("three", cache.get(3)); |
| 169 | EXPECT_EQ(3u, cache.size()); |
| 170 | } |
| 171 | |
| 172 | TEST_F(LruCacheTest, MaxCapacity) { |
| 173 | LruCache<SimpleKey, StringValue> cache(2); |
| 174 | |
| 175 | cache.put(1, "one"); |
| 176 | cache.put(2, "two"); |
| 177 | cache.put(3, "three"); |
Yi Kong | e1731a4 | 2018-07-16 18:11:34 -0700 | [diff] [blame] | 178 | EXPECT_EQ(nullptr, cache.get(1)); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 179 | EXPECT_STREQ("two", cache.get(2)); |
| 180 | EXPECT_STREQ("three", cache.get(3)); |
| 181 | EXPECT_EQ(2u, cache.size()); |
| 182 | } |
| 183 | |
| 184 | TEST_F(LruCacheTest, RemoveLru) { |
| 185 | LruCache<SimpleKey, StringValue> cache(100); |
| 186 | |
| 187 | cache.put(1, "one"); |
| 188 | cache.put(2, "two"); |
| 189 | cache.put(3, "three"); |
| 190 | cache.removeOldest(); |
Yi Kong | e1731a4 | 2018-07-16 18:11:34 -0700 | [diff] [blame] | 191 | EXPECT_EQ(nullptr, cache.get(1)); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 192 | EXPECT_STREQ("two", cache.get(2)); |
| 193 | EXPECT_STREQ("three", cache.get(3)); |
| 194 | EXPECT_EQ(2u, cache.size()); |
| 195 | } |
| 196 | |
| 197 | TEST_F(LruCacheTest, GetUpdatesLru) { |
| 198 | LruCache<SimpleKey, StringValue> cache(100); |
| 199 | |
| 200 | cache.put(1, "one"); |
| 201 | cache.put(2, "two"); |
| 202 | cache.put(3, "three"); |
| 203 | EXPECT_STREQ("one", cache.get(1)); |
| 204 | cache.removeOldest(); |
| 205 | EXPECT_STREQ("one", cache.get(1)); |
Yi Kong | e1731a4 | 2018-07-16 18:11:34 -0700 | [diff] [blame] | 206 | EXPECT_EQ(nullptr, cache.get(2)); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 207 | EXPECT_STREQ("three", cache.get(3)); |
| 208 | EXPECT_EQ(2u, cache.size()); |
| 209 | } |
| 210 | |
| 211 | uint32_t hash_int(int x) { |
| 212 | return JenkinsHashWhiten(JenkinsHashMix(0, x)); |
| 213 | } |
| 214 | |
| 215 | TEST_F(LruCacheTest, StressTest) { |
| 216 | const size_t kCacheSize = 512; |
| 217 | LruCache<SimpleKey, StringValue> cache(512); |
| 218 | const size_t kNumKeys = 16 * 1024; |
| 219 | const size_t kNumIters = 100000; |
| 220 | char* strings[kNumKeys]; |
| 221 | |
| 222 | for (size_t i = 0; i < kNumKeys; i++) { |
| 223 | strings[i] = (char *)malloc(16); |
Sasha Levitskiy | cdc1cfb | 2014-04-10 17:10:21 -0700 | [diff] [blame] | 224 | sprintf(strings[i], "%zu", i); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 225 | } |
| 226 | |
| 227 | srandom(12345); |
| 228 | int hitCount = 0; |
| 229 | for (size_t i = 0; i < kNumIters; i++) { |
| 230 | int index = random() % kNumKeys; |
| 231 | uint32_t key = hash_int(index); |
| 232 | const char *val = cache.get(key); |
Yi Kong | e1731a4 | 2018-07-16 18:11:34 -0700 | [diff] [blame] | 233 | if (val != nullptr) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 234 | EXPECT_EQ(strings[index], val); |
| 235 | hitCount++; |
| 236 | } else { |
| 237 | cache.put(key, strings[index]); |
| 238 | } |
| 239 | } |
| 240 | size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys; |
| 241 | EXPECT_LT(int(expectedHitCount * 0.9), hitCount); |
| 242 | EXPECT_GT(int(expectedHitCount * 1.1), hitCount); |
| 243 | EXPECT_EQ(kCacheSize, cache.size()); |
| 244 | |
| 245 | for (size_t i = 0; i < kNumKeys; i++) { |
| 246 | free((void *)strings[i]); |
| 247 | } |
| 248 | } |
| 249 | |
| 250 | TEST_F(LruCacheTest, NoLeak) { |
| 251 | ComplexCache cache(100); |
| 252 | |
| 253 | cache.put(ComplexKey(0), ComplexValue(0)); |
| 254 | cache.put(ComplexKey(1), ComplexValue(1)); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 255 | EXPECT_EQ(2U, cache.size()); |
Sergio Giro | bb58cde | 2015-09-25 18:03:18 +0100 | [diff] [blame] | 256 | assertInstanceCount(2, 3); // the member mNullValue counts as an instance |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 257 | } |
| 258 | |
| 259 | TEST_F(LruCacheTest, Clear) { |
| 260 | ComplexCache cache(100); |
| 261 | |
| 262 | cache.put(ComplexKey(0), ComplexValue(0)); |
| 263 | cache.put(ComplexKey(1), ComplexValue(1)); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 264 | EXPECT_EQ(2U, cache.size()); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 265 | assertInstanceCount(2, 3); |
| 266 | cache.clear(); |
| 267 | assertInstanceCount(0, 1); |
| 268 | } |
| 269 | |
| 270 | TEST_F(LruCacheTest, ClearNoDoubleFree) { |
| 271 | { |
| 272 | ComplexCache cache(100); |
| 273 | |
| 274 | cache.put(ComplexKey(0), ComplexValue(0)); |
| 275 | cache.put(ComplexKey(1), ComplexValue(1)); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 276 | EXPECT_EQ(2U, cache.size()); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 277 | assertInstanceCount(2, 3); |
| 278 | cache.removeOldest(); |
| 279 | cache.clear(); |
| 280 | assertInstanceCount(0, 1); |
| 281 | } |
| 282 | assertInstanceCount(0, 0); |
| 283 | } |
| 284 | |
| 285 | TEST_F(LruCacheTest, ClearReuseOk) { |
| 286 | ComplexCache cache(100); |
| 287 | |
| 288 | cache.put(ComplexKey(0), ComplexValue(0)); |
| 289 | cache.put(ComplexKey(1), ComplexValue(1)); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 290 | EXPECT_EQ(2U, cache.size()); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 291 | assertInstanceCount(2, 3); |
| 292 | cache.clear(); |
| 293 | assertInstanceCount(0, 1); |
| 294 | cache.put(ComplexKey(0), ComplexValue(0)); |
| 295 | cache.put(ComplexKey(1), ComplexValue(1)); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 296 | EXPECT_EQ(2U, cache.size()); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 297 | assertInstanceCount(2, 3); |
| 298 | } |
| 299 | |
| 300 | TEST_F(LruCacheTest, Callback) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 301 | EntryRemovedCallback callback; |
Florian Mayer | e0240d3 | 2022-03-31 20:21:12 +0000 | [diff] [blame] | 302 | LruCache<SimpleKey, StringValue> cache(100); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 303 | cache.setOnEntryRemovedListener(&callback); |
| 304 | |
| 305 | cache.put(1, "one"); |
| 306 | cache.put(2, "two"); |
| 307 | cache.put(3, "three"); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 308 | EXPECT_EQ(3U, cache.size()); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 309 | cache.removeOldest(); |
| 310 | EXPECT_EQ(1, callback.callbackCount); |
| 311 | EXPECT_EQ(1, callback.lastKey); |
| 312 | EXPECT_STREQ("one", callback.lastValue); |
| 313 | } |
| 314 | |
| 315 | TEST_F(LruCacheTest, CallbackOnClear) { |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 316 | EntryRemovedCallback callback; |
Florian Mayer | e0240d3 | 2022-03-31 20:21:12 +0000 | [diff] [blame] | 317 | LruCache<SimpleKey, StringValue> cache(100); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 318 | cache.setOnEntryRemovedListener(&callback); |
| 319 | |
| 320 | cache.put(1, "one"); |
| 321 | cache.put(2, "two"); |
| 322 | cache.put(3, "three"); |
Nick Kralevich | 3e6c451 | 2015-08-17 18:26:13 -0700 | [diff] [blame] | 323 | EXPECT_EQ(3U, cache.size()); |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 324 | cache.clear(); |
| 325 | EXPECT_EQ(3, callback.callbackCount); |
| 326 | } |
| 327 | |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 328 | TEST_F(LruCacheTest, CallbackRemovesKeyWorksOK) { |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 329 | InvalidateKeyCallback callback; |
Florian Mayer | e0240d3 | 2022-03-31 20:21:12 +0000 | [diff] [blame] | 330 | LruCache<KeyWithPointer, StringValue> cache(1); |
Sergio Giro | b7170fe | 2015-11-17 11:52:05 +0000 | [diff] [blame] | 331 | cache.setOnEntryRemovedListener(&callback); |
| 332 | KeyWithPointer key1; |
| 333 | key1.ptr = new int(1); |
| 334 | KeyWithPointer key2; |
| 335 | key2.ptr = new int(2); |
| 336 | |
| 337 | cache.put(key1, "one"); |
| 338 | // As the size of the cache is 1, the put will call the callback. |
| 339 | // Make sure everything goes smoothly even if the callback invalidates |
| 340 | // the key (b/24785286) |
| 341 | cache.put(key2, "two"); |
| 342 | EXPECT_EQ(1U, cache.size()); |
| 343 | EXPECT_STREQ("two", cache.get(key2)); |
| 344 | cache.clear(); |
| 345 | } |
| 346 | |
Sergio Giro | 0cb59c0 | 2015-10-02 17:31:34 +0100 | [diff] [blame] | 347 | TEST_F(LruCacheTest, IteratorCheck) { |
| 348 | LruCache<int, int> cache(100); |
| 349 | |
| 350 | cache.put(1, 4); |
| 351 | cache.put(2, 5); |
| 352 | cache.put(3, 6); |
| 353 | EXPECT_EQ(3U, cache.size()); |
| 354 | |
| 355 | LruCache<int, int>::Iterator it(cache); |
| 356 | std::unordered_set<int> returnedValues; |
| 357 | while (it.next()) { |
| 358 | int v = it.value(); |
| 359 | // Check we haven't seen the value before. |
| 360 | EXPECT_TRUE(returnedValues.find(v) == returnedValues.end()); |
| 361 | returnedValues.insert(v); |
| 362 | } |
| 363 | EXPECT_EQ(std::unordered_set<int>({4, 5, 6}), returnedValues); |
| 364 | } |
| 365 | |
| 366 | TEST_F(LruCacheTest, EmptyCacheIterator) { |
| 367 | // Check that nothing crashes... |
| 368 | LruCache<int, int> cache(100); |
| 369 | |
| 370 | LruCache<int, int>::Iterator it(cache); |
| 371 | std::unordered_set<int> returnedValues; |
| 372 | while (it.next()) { |
| 373 | returnedValues.insert(it.value()); |
| 374 | } |
| 375 | EXPECT_EQ(std::unordered_set<int>(), returnedValues); |
| 376 | } |
| 377 | |
| 378 | TEST_F(LruCacheTest, OneElementCacheIterator) { |
| 379 | // Check that nothing crashes... |
| 380 | LruCache<int, int> cache(100); |
| 381 | cache.put(1, 2); |
| 382 | |
| 383 | LruCache<int, int>::Iterator it(cache); |
| 384 | std::unordered_set<int> returnedValues; |
| 385 | while (it.next()) { |
| 386 | returnedValues.insert(it.value()); |
| 387 | } |
| 388 | EXPECT_EQ(std::unordered_set<int>({ 2 }), returnedValues); |
| 389 | } |
| 390 | |
| 391 | TEST_F(LruCacheTest, OneElementCacheRemove) { |
| 392 | LruCache<int, int> cache(100); |
| 393 | cache.put(1, 2); |
| 394 | |
| 395 | cache.remove(1); |
| 396 | |
| 397 | LruCache<int, int>::Iterator it(cache); |
| 398 | std::unordered_set<int> returnedValues; |
| 399 | while (it.next()) { |
| 400 | returnedValues.insert(it.value()); |
| 401 | } |
| 402 | EXPECT_EQ(std::unordered_set<int>({ }), returnedValues); |
| 403 | } |
| 404 | |
| 405 | TEST_F(LruCacheTest, Remove) { |
| 406 | LruCache<int, int> cache(100); |
| 407 | cache.put(1, 4); |
| 408 | cache.put(2, 5); |
| 409 | cache.put(3, 6); |
| 410 | |
| 411 | cache.remove(2); |
| 412 | |
| 413 | LruCache<int, int>::Iterator it(cache); |
| 414 | std::unordered_set<int> returnedValues; |
| 415 | while (it.next()) { |
| 416 | returnedValues.insert(it.value()); |
| 417 | } |
| 418 | EXPECT_EQ(std::unordered_set<int>({ 4, 6 }), returnedValues); |
| 419 | } |
| 420 | |
| 421 | TEST_F(LruCacheTest, RemoveYoungest) { |
| 422 | LruCache<int, int> cache(100); |
| 423 | cache.put(1, 4); |
| 424 | cache.put(2, 5); |
| 425 | cache.put(3, 6); |
| 426 | |
| 427 | cache.remove(3); |
| 428 | |
| 429 | LruCache<int, int>::Iterator it(cache); |
| 430 | std::unordered_set<int> returnedValues; |
| 431 | while (it.next()) { |
| 432 | returnedValues.insert(it.value()); |
| 433 | } |
| 434 | EXPECT_EQ(std::unordered_set<int>({ 4, 5 }), returnedValues); |
| 435 | } |
| 436 | |
| 437 | TEST_F(LruCacheTest, RemoveNonMember) { |
| 438 | LruCache<int, int> cache(100); |
| 439 | cache.put(1, 4); |
| 440 | cache.put(2, 5); |
| 441 | cache.put(3, 6); |
| 442 | |
| 443 | cache.remove(7); |
| 444 | |
| 445 | LruCache<int, int>::Iterator it(cache); |
| 446 | std::unordered_set<int> returnedValues; |
| 447 | while (it.next()) { |
| 448 | returnedValues.insert(it.value()); |
| 449 | } |
| 450 | EXPECT_EQ(std::unordered_set<int>({ 4, 5, 6 }), returnedValues); |
| 451 | } |
| 452 | |
Sergio Giro | 4c56e0a | 2016-06-23 17:19:13 +0100 | [diff] [blame] | 453 | TEST_F(LruCacheTest, DontCopyKeyInGet) { |
| 454 | LruCache<KeyFailsOnCopy, KeyFailsOnCopy> cache(1); |
| 455 | // Check that get doesn't copy the key |
| 456 | cache.get(KeyFailsOnCopy(0)); |
| 457 | } |
| 458 | |
Raph Levien | b6ea175 | 2012-10-25 23:11:13 -0700 | [diff] [blame] | 459 | } |