2 * Copyright 2014 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <gtest/gtest.h>
21 #include <folly/EvictingCacheMap.h>
23 using namespace folly;
25 TEST(EvictingCacheMap, SanityTest) {
26 EvictingCacheMap<int, int> map(0);
28 EXPECT_EQ(0, map.size());
29 EXPECT_TRUE(map.empty());
30 EXPECT_FALSE(map.exists(1));
32 EXPECT_EQ(1, map.size());
33 EXPECT_FALSE(map.empty());
34 EXPECT_EQ(1, map.get(1));
35 EXPECT_TRUE(map.exists(1));
37 EXPECT_EQ(1, map.size());
38 EXPECT_FALSE(map.empty());
39 EXPECT_EQ(2, map.get(1));
40 EXPECT_TRUE(map.exists(1));
42 EXPECT_EQ(0, map.size());
43 EXPECT_TRUE(map.empty());
44 EXPECT_FALSE(map.exists(1));
46 EXPECT_EQ(0, map.size());
47 EXPECT_TRUE(map.empty());
48 EXPECT_FALSE(map.exists(1));
50 EXPECT_EQ(1, map.size());
51 EXPECT_FALSE(map.empty());
52 EXPECT_EQ(1, map.get(1));
53 EXPECT_TRUE(map.exists(1));
55 EXPECT_EQ(1, map.size());
56 EXPECT_FALSE(map.empty());
57 EXPECT_EQ(2, map.get(1));
58 EXPECT_TRUE(map.exists(1));
60 EXPECT_FALSE(map.exists(2));
62 EXPECT_TRUE(map.exists(2));
63 EXPECT_EQ(2, map.size());
64 EXPECT_FALSE(map.empty());
65 EXPECT_EQ(1, map.get(2));
67 EXPECT_EQ(2, map.size());
68 EXPECT_FALSE(map.empty());
69 EXPECT_EQ(2, map.get(2));
70 EXPECT_TRUE(map.exists(2));
72 EXPECT_EQ(1, map.size());
73 EXPECT_FALSE(map.empty());
74 EXPECT_FALSE(map.exists(2));
76 EXPECT_EQ(0, map.size());
77 EXPECT_TRUE(map.empty());
78 EXPECT_FALSE(map.exists(1));
82 TEST(EvictingCacheMap, PruneTest) {
83 EvictingCacheMap<int, int> map(0);
84 EXPECT_EQ(0, map.size());
85 EXPECT_TRUE(map.empty());
86 for (int i = 0; i < 100; i++) {
87 EXPECT_FALSE(map.exists(i));
90 for (int i = 0; i < 100; i++) {
92 EXPECT_EQ(i + 1, map.size());
93 EXPECT_FALSE(map.empty());
94 EXPECT_TRUE(map.exists(i));
95 EXPECT_EQ(i, map.get(i));
99 EXPECT_EQ(0, map.size());
100 EXPECT_TRUE(map.empty());
101 for (int i = 0; i < 100; i++) {
102 EXPECT_FALSE(map.exists(i));
105 for (int i = 0; i < 100; i++) {
107 EXPECT_EQ(i + 1, map.size());
108 EXPECT_FALSE(map.empty());
109 EXPECT_TRUE(map.exists(i));
110 EXPECT_EQ(i, map.get(i));
114 EXPECT_EQ(0, map.size());
115 EXPECT_TRUE(map.empty());
116 for (int i = 0; i < 100; i++) {
117 EXPECT_FALSE(map.exists(i));
120 for (int i = 0; i < 100; i++) {
122 EXPECT_EQ(i + 1, map.size());
123 EXPECT_FALSE(map.empty());
124 EXPECT_TRUE(map.exists(i));
125 EXPECT_EQ(i, map.get(i));
129 EXPECT_EQ(1, map.size());
130 EXPECT_FALSE(map.empty());
131 for (int i = 0; i < 99; i++) {
132 EXPECT_FALSE(map.exists(i));
134 EXPECT_TRUE(map.exists(99));
135 EXPECT_EQ(99, map.get(99));
138 EXPECT_EQ(0, map.size());
139 EXPECT_TRUE(map.empty());
140 for (int i = 0; i < 100; i++) {
141 EXPECT_FALSE(map.exists(i));
144 for (int i = 0; i < 100; i++) {
146 EXPECT_EQ(i + 1, map.size());
147 EXPECT_FALSE(map.empty());
148 EXPECT_TRUE(map.exists(i));
149 EXPECT_EQ(i, map.get(i));
153 EXPECT_EQ(10, map.size());
154 EXPECT_FALSE(map.empty());
155 for (int i = 0; i < 90; i++) {
156 EXPECT_FALSE(map.exists(i));
158 for (int i = 90; i < 100; i++) {
159 EXPECT_TRUE(map.exists(i));
160 EXPECT_EQ(i, map.get(i));
164 TEST(EvictingCacheMap, PruneHookTest) {
165 EvictingCacheMap<int, int> map(0);
166 EXPECT_EQ(0, map.size());
167 EXPECT_TRUE(map.empty());
168 for (int i = 0; i < 100; i++) {
169 EXPECT_FALSE(map.exists(i));
173 auto pruneCb = [&](int&& k, int&& v) {
178 map.setPruneHook(pruneCb);
180 for (int i = 0; i < 100; i++) {
182 EXPECT_EQ(i + 1, map.size());
183 EXPECT_FALSE(map.empty());
184 EXPECT_TRUE(map.exists(i));
185 EXPECT_EQ(i, map.get(i));
189 EXPECT_EQ(0, map.size());
190 EXPECT_TRUE(map.empty());
191 for (int i = 0; i < 100; i++) {
192 EXPECT_FALSE(map.exists(i));
194 EXPECT_EQ((99 * 100) / 2, sum);
197 for (int i = 0; i < 100; i++) {
199 EXPECT_EQ(i + 1, map.size());
200 EXPECT_FALSE(map.empty());
201 EXPECT_TRUE(map.exists(i));
202 EXPECT_EQ(i, map.get(i));
206 EXPECT_EQ(0, map.size());
207 EXPECT_TRUE(map.empty());
208 for (int i = 0; i < 100; i++) {
209 EXPECT_FALSE(map.exists(i));
211 EXPECT_EQ((99 * 100) / 2, sum);
214 for (int i = 0; i < 100; i++) {
216 EXPECT_EQ(i + 1, map.size());
217 EXPECT_FALSE(map.empty());
218 EXPECT_TRUE(map.exists(i));
219 EXPECT_EQ(i, map.get(i));
223 EXPECT_EQ(1, map.size());
224 EXPECT_FALSE(map.empty());
225 for (int i = 0; i < 99; i++) {
226 EXPECT_FALSE(map.exists(i));
228 EXPECT_TRUE(map.exists(99));
229 EXPECT_EQ(99, map.get(99));
231 EXPECT_EQ((98 * 99) / 2, sum);
235 EXPECT_EQ(0, map.size());
236 EXPECT_TRUE(map.empty());
237 for (int i = 0; i < 100; i++) {
238 EXPECT_FALSE(map.exists(i));
244 for (int i = 0; i < 100; i++) {
246 EXPECT_EQ(i + 1, map.size());
247 EXPECT_FALSE(map.empty());
248 EXPECT_TRUE(map.exists(i));
249 EXPECT_EQ(i, map.get(i));
253 EXPECT_EQ(10, map.size());
254 EXPECT_FALSE(map.empty());
255 for (int i = 0; i < 90; i++) {
256 EXPECT_FALSE(map.exists(i));
258 for (int i = 90; i < 100; i++) {
259 EXPECT_TRUE(map.exists(i));
260 EXPECT_EQ(i, map.get(i));
262 EXPECT_EQ((89 * 90) / 2, sum);
266 TEST(EvictingCacheMap, SetMaxSize) {
267 EvictingCacheMap<int, int> map(100, 20);
268 for (int i = 0; i < 90; i++) {
270 EXPECT_TRUE(map.exists(i));
273 EXPECT_EQ(90, map.size());
275 EXPECT_EQ(map.size(), 50);
277 for (int i = 0; i < 90; i++) {
279 EXPECT_TRUE(map.exists(i));
281 EXPECT_EQ(40, map.size());
283 EXPECT_EQ(40, map.size());
285 EXPECT_EQ(10, map.size());
288 TEST(EvictingCacheMap, SetClearSize) {
289 EvictingCacheMap<int, int> map(100, 20);
290 for (int i = 0; i < 90; i++) {
292 EXPECT_TRUE(map.exists(i));
295 EXPECT_EQ(90, map.size());
296 map.setClearSize(40);
298 EXPECT_EQ(map.size(), 50);
300 for (int i = 0; i < 90; i++) {
302 EXPECT_TRUE(map.exists(i));
304 EXPECT_EQ(20, map.size());
306 EXPECT_EQ(20, map.size());
308 EXPECT_EQ(0, map.size());
311 TEST(EvictingCacheMap, DestructorInvocationTest) {
313 SumInt(int val, int* ref) : val(val), ref(ref) { }
321 EvictingCacheMap<int, SumInt> map(0);
322 EXPECT_EQ(0, map.size());
323 EXPECT_TRUE(map.empty());
324 for (int i = 0; i < 100; i++) {
325 EXPECT_FALSE(map.exists(i));
330 for (int i = 0; i < 100; i++) {
331 map.set(i, SumInt(i, &sum));
332 EXPECT_EQ(i + 1, map.size());
333 EXPECT_FALSE(map.empty());
334 EXPECT_TRUE(map.exists(i));
335 EXPECT_EQ(i, map.get(i).val);
340 EXPECT_EQ(0, map.size());
341 EXPECT_TRUE(map.empty());
342 for (int i = 0; i < 100; i++) {
343 EXPECT_FALSE(map.exists(i));
345 EXPECT_EQ((99 * 100) / 2, sum);
347 for (int i = 0; i < 100; i++) {
348 map.set(i, SumInt(i, &sum));
349 EXPECT_EQ(i + 1, map.size());
350 EXPECT_FALSE(map.empty());
351 EXPECT_TRUE(map.exists(i));
352 EXPECT_EQ(i, map.get(i).val);
357 EXPECT_EQ(0, map.size());
358 EXPECT_TRUE(map.empty());
359 for (int i = 0; i < 100; i++) {
360 EXPECT_FALSE(map.exists(i));
362 EXPECT_EQ((99 * 100) / 2, sum);
364 for (int i = 0; i < 100; i++) {
365 map.set(i, SumInt(i, &sum));
366 EXPECT_EQ(i + 1, map.size());
367 EXPECT_FALSE(map.empty());
368 EXPECT_TRUE(map.exists(i));
369 EXPECT_EQ(i, map.get(i).val);
374 EXPECT_EQ(1, map.size());
375 EXPECT_FALSE(map.empty());
376 for (int i = 0; i < 99; i++) {
377 EXPECT_FALSE(map.exists(i));
379 EXPECT_TRUE(map.exists(99));
380 EXPECT_EQ(99, map.get(99).val);
382 EXPECT_EQ((98 * 99) / 2, sum);
386 EXPECT_EQ(0, map.size());
387 EXPECT_TRUE(map.empty());
388 for (int i = 0; i < 100; i++) {
389 EXPECT_FALSE(map.exists(i));
393 for (int i = 0; i < 100; i++) {
394 map.set(i, SumInt(i, &sum));
395 EXPECT_EQ(i + 1, map.size());
396 EXPECT_FALSE(map.empty());
397 EXPECT_TRUE(map.exists(i));
398 EXPECT_EQ(i, map.get(i).val);
403 EXPECT_EQ(10, map.size());
404 EXPECT_FALSE(map.empty());
405 for (int i = 0; i < 90; i++) {
406 EXPECT_FALSE(map.exists(i));
408 for (int i = 90; i < 100; i++) {
409 EXPECT_TRUE(map.exists(i));
410 EXPECT_EQ(i, map.get(i).val);
412 EXPECT_EQ((89 * 90) / 2, sum);
416 TEST(EvictingCacheMap, LruSanityTest) {
417 EvictingCacheMap<int, int> map(10);
418 EXPECT_EQ(0, map.size());
419 EXPECT_TRUE(map.empty());
420 for (int i = 0; i < 100; i++) {
421 EXPECT_FALSE(map.exists(i));
424 for (int i = 0; i < 100; i++) {
426 EXPECT_GE(10, map.size());
427 EXPECT_FALSE(map.empty());
428 EXPECT_TRUE(map.exists(i));
429 EXPECT_EQ(i, map.get(i));
432 EXPECT_EQ(10, map.size());
433 EXPECT_FALSE(map.empty());
434 for (int i = 0; i < 90; i++) {
435 EXPECT_FALSE(map.exists(i));
437 for (int i = 90; i < 100; i++) {
438 EXPECT_TRUE(map.exists(i));
442 TEST(EvictingCacheMap, LruPromotionTest) {
443 EvictingCacheMap<int, int> map(10);
444 EXPECT_EQ(0, map.size());
445 EXPECT_TRUE(map.empty());
446 for (int i = 0; i < 100; i++) {
447 EXPECT_FALSE(map.exists(i));
450 for (int i = 0; i < 100; i++) {
452 EXPECT_GE(10, map.size());
453 EXPECT_FALSE(map.empty());
454 EXPECT_TRUE(map.exists(i));
455 EXPECT_EQ(i, map.get(i));
456 for (int j = 0; j < std::min(i + 1, 9); j++) {
457 EXPECT_TRUE(map.exists(j));
458 EXPECT_EQ(j, map.get(j));
462 EXPECT_EQ(10, map.size());
463 EXPECT_FALSE(map.empty());
464 for (int i = 0; i < 9; i++) {
465 EXPECT_TRUE(map.exists(i));
467 EXPECT_TRUE(map.exists(99));
468 for (int i = 10; i < 99; i++) {
469 EXPECT_FALSE(map.exists(i));
473 TEST(EvictingCacheMap, LruNoPromotionTest) {
474 EvictingCacheMap<int, int> map(10);
475 EXPECT_EQ(0, map.size());
476 EXPECT_TRUE(map.empty());
477 for (int i = 0; i < 100; i++) {
478 EXPECT_FALSE(map.exists(i));
481 for (int i = 0; i < 100; i++) {
483 EXPECT_GE(10, map.size());
484 EXPECT_FALSE(map.empty());
485 EXPECT_TRUE(map.exists(i));
486 EXPECT_EQ(i, map.get(i));
487 for (int j = 0; j < std::min(i + 1, 9); j++) {
489 EXPECT_EQ(j, map.getWithoutPromotion(j));
494 EXPECT_EQ(10, map.size());
495 EXPECT_FALSE(map.empty());
496 for (int i = 0; i < 90; i++) {
497 EXPECT_FALSE(map.exists(i));
499 for (int i = 90; i < 100; i++) {
500 EXPECT_TRUE(map.exists(i));
504 TEST(EvictingCacheMap, IteratorSanityTest) {
505 const int nItems = 1000;
506 EvictingCacheMap<int, int> map(nItems);
507 EXPECT_TRUE(map.begin() == map.end());
508 for (int i = 0; i < nItems; i++) {
509 EXPECT_FALSE(map.exists(i));
511 EXPECT_TRUE(map.exists(i));
512 EXPECT_EQ(i * 2, map.get(i));
516 for (auto& it : map) {
517 EXPECT_EQ(0, seen.count(it.first));
518 seen.insert(it.first);
519 EXPECT_EQ(it.first * 2, it.second);
521 EXPECT_EQ(nItems, seen.size());
524 TEST(EvictingCacheMap, FindTest) {
525 const int nItems = 1000;
526 EvictingCacheMap<int, int> map(nItems);
527 for (int i = 0; i < nItems; i++) {
528 map.set(i * 2, i * 2);
529 EXPECT_TRUE(map.exists(i * 2));
530 EXPECT_EQ(i * 2, map.get(i * 2));
532 for (int i = 0; i < nItems * 2; i++) {
534 auto it = map.find(i);
535 EXPECT_FALSE(it == map.end());
536 EXPECT_EQ(i, it->first);
537 EXPECT_EQ(i, it->second);
539 EXPECT_TRUE( map.find(i) == map.end());
542 for (int i = nItems * 2 - 1; i >= 0; i--) {
544 auto it = map.find(i);
545 EXPECT_FALSE(it == map.end());
546 EXPECT_EQ(i, it->first);
547 EXPECT_EQ(i, it->second);
549 EXPECT_TRUE(map.find(i) == map.end());
552 EXPECT_EQ(0, map.begin()->first);
555 TEST(EvictingCacheMap, FindWithoutPromotionTest) {
556 const int nItems = 1000;
557 EvictingCacheMap<int, int> map(nItems);
558 for (int i = 0; i < nItems; i++) {
559 map.set(i * 2, i * 2);
560 EXPECT_TRUE(map.exists(i * 2));
561 EXPECT_EQ(i * 2, map.get(i * 2));
563 for (int i = nItems * 2 - 1; i >= 0; i--) {
565 auto it = map.findWithoutPromotion(i);
566 EXPECT_FALSE(it == map.end());
567 EXPECT_EQ(i, it->first);
568 EXPECT_EQ(i, it->second);
570 EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
573 EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
576 TEST(EvictingCacheMap, IteratorOrderingTest) {
577 const int nItems = 1000;
578 EvictingCacheMap<int, int> map(nItems);
579 for (int i = 0; i < nItems; i++) {
581 EXPECT_TRUE(map.exists(i));
582 EXPECT_EQ(i, map.get(i));
585 int expected = nItems - 1;
586 for (auto it = map.begin(); it != map.end(); ++it) {
587 EXPECT_EQ(expected, it->first);
592 for (auto it = map.rbegin(); it != map.rend(); ++it) {
593 EXPECT_EQ(expected, it->first);
600 EXPECT_TRUE(it != map.begin());
603 EXPECT_EQ(expected, it->first);
605 } while (it != map.begin());
606 EXPECT_EQ(nItems, expected);
610 auto it = map.rend();
611 expected = nItems - 1;
614 EXPECT_EQ(expected, it->first);
616 } while (it != map.rbegin());
617 EXPECT_EQ(-1, expected);