2 * Copyright 2017 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.
19 #include <folly/EvictingCacheMap.h>
20 #include <folly/portability/GTest.h>
22 using namespace folly;
24 TEST(EvictingCacheMap, SanityTest) {
25 EvictingCacheMap<int, int> map(0);
27 EXPECT_EQ(0, map.size());
28 EXPECT_TRUE(map.empty());
29 EXPECT_FALSE(map.exists(1));
31 EXPECT_EQ(1, map.size());
32 EXPECT_FALSE(map.empty());
33 EXPECT_EQ(1, map.get(1));
34 EXPECT_TRUE(map.exists(1));
36 EXPECT_EQ(1, map.size());
37 EXPECT_FALSE(map.empty());
38 EXPECT_EQ(2, map.get(1));
39 EXPECT_TRUE(map.exists(1));
41 EXPECT_EQ(0, map.size());
42 EXPECT_TRUE(map.empty());
43 EXPECT_FALSE(map.exists(1));
45 EXPECT_EQ(0, map.size());
46 EXPECT_TRUE(map.empty());
47 EXPECT_FALSE(map.exists(1));
49 EXPECT_EQ(1, map.size());
50 EXPECT_FALSE(map.empty());
51 EXPECT_EQ(1, map.get(1));
52 EXPECT_TRUE(map.exists(1));
54 EXPECT_EQ(1, map.size());
55 EXPECT_FALSE(map.empty());
56 EXPECT_EQ(2, map.get(1));
57 EXPECT_TRUE(map.exists(1));
59 EXPECT_FALSE(map.exists(2));
61 EXPECT_TRUE(map.exists(2));
62 EXPECT_EQ(2, map.size());
63 EXPECT_FALSE(map.empty());
64 EXPECT_EQ(1, map.get(2));
66 EXPECT_EQ(2, map.size());
67 EXPECT_FALSE(map.empty());
68 EXPECT_EQ(2, map.get(2));
69 EXPECT_TRUE(map.exists(2));
71 EXPECT_EQ(1, map.size());
72 EXPECT_FALSE(map.empty());
73 EXPECT_FALSE(map.exists(2));
75 EXPECT_EQ(0, map.size());
76 EXPECT_TRUE(map.empty());
77 EXPECT_FALSE(map.exists(1));
81 TEST(EvictingCacheMap, PruneTest) {
82 EvictingCacheMap<int, int> map(0);
83 EXPECT_EQ(0, map.size());
84 EXPECT_TRUE(map.empty());
85 for (int i = 0; i < 100; i++) {
86 EXPECT_FALSE(map.exists(i));
89 for (int i = 0; i < 100; i++) {
91 EXPECT_EQ(i + 1, map.size());
92 EXPECT_FALSE(map.empty());
93 EXPECT_TRUE(map.exists(i));
94 EXPECT_EQ(i, map.get(i));
98 EXPECT_EQ(0, map.size());
99 EXPECT_TRUE(map.empty());
100 for (int i = 0; i < 100; i++) {
101 EXPECT_FALSE(map.exists(i));
104 for (int i = 0; i < 100; i++) {
106 EXPECT_EQ(i + 1, map.size());
107 EXPECT_FALSE(map.empty());
108 EXPECT_TRUE(map.exists(i));
109 EXPECT_EQ(i, map.get(i));
113 EXPECT_EQ(0, map.size());
114 EXPECT_TRUE(map.empty());
115 for (int i = 0; i < 100; i++) {
116 EXPECT_FALSE(map.exists(i));
119 for (int i = 0; i < 100; i++) {
121 EXPECT_EQ(i + 1, map.size());
122 EXPECT_FALSE(map.empty());
123 EXPECT_TRUE(map.exists(i));
124 EXPECT_EQ(i, map.get(i));
128 EXPECT_EQ(1, map.size());
129 EXPECT_FALSE(map.empty());
130 for (int i = 0; i < 99; i++) {
131 EXPECT_FALSE(map.exists(i));
133 EXPECT_TRUE(map.exists(99));
134 EXPECT_EQ(99, map.get(99));
137 EXPECT_EQ(0, map.size());
138 EXPECT_TRUE(map.empty());
139 for (int i = 0; i < 100; i++) {
140 EXPECT_FALSE(map.exists(i));
143 for (int i = 0; i < 100; i++) {
145 EXPECT_EQ(i + 1, map.size());
146 EXPECT_FALSE(map.empty());
147 EXPECT_TRUE(map.exists(i));
148 EXPECT_EQ(i, map.get(i));
152 EXPECT_EQ(10, map.size());
153 EXPECT_FALSE(map.empty());
154 for (int i = 0; i < 90; i++) {
155 EXPECT_FALSE(map.exists(i));
157 for (int i = 90; i < 100; i++) {
158 EXPECT_TRUE(map.exists(i));
159 EXPECT_EQ(i, map.get(i));
163 TEST(EvictingCacheMap, PruneHookTest) {
164 EvictingCacheMap<int, int> map(0);
165 EXPECT_EQ(0, map.size());
166 EXPECT_TRUE(map.empty());
167 for (int i = 0; i < 100; i++) {
168 EXPECT_FALSE(map.exists(i));
172 auto pruneCb = [&](int&& k, int&& v) {
177 map.setPruneHook(pruneCb);
179 for (int i = 0; i < 100; i++) {
181 EXPECT_EQ(i + 1, map.size());
182 EXPECT_FALSE(map.empty());
183 EXPECT_TRUE(map.exists(i));
184 EXPECT_EQ(i, map.get(i));
188 EXPECT_EQ(0, map.size());
189 EXPECT_TRUE(map.empty());
190 for (int i = 0; i < 100; i++) {
191 EXPECT_FALSE(map.exists(i));
193 EXPECT_EQ((99 * 100) / 2, sum);
196 for (int i = 0; i < 100; i++) {
198 EXPECT_EQ(i + 1, map.size());
199 EXPECT_FALSE(map.empty());
200 EXPECT_TRUE(map.exists(i));
201 EXPECT_EQ(i, map.get(i));
205 EXPECT_EQ(0, map.size());
206 EXPECT_TRUE(map.empty());
207 for (int i = 0; i < 100; i++) {
208 EXPECT_FALSE(map.exists(i));
210 EXPECT_EQ((99 * 100) / 2, sum);
213 for (int i = 0; i < 100; i++) {
215 EXPECT_EQ(i + 1, map.size());
216 EXPECT_FALSE(map.empty());
217 EXPECT_TRUE(map.exists(i));
218 EXPECT_EQ(i, map.get(i));
222 EXPECT_EQ(1, map.size());
223 EXPECT_FALSE(map.empty());
224 for (int i = 0; i < 99; i++) {
225 EXPECT_FALSE(map.exists(i));
227 EXPECT_TRUE(map.exists(99));
228 EXPECT_EQ(99, map.get(99));
230 EXPECT_EQ((98 * 99) / 2, sum);
234 EXPECT_EQ(0, map.size());
235 EXPECT_TRUE(map.empty());
236 for (int i = 0; i < 100; i++) {
237 EXPECT_FALSE(map.exists(i));
243 for (int i = 0; i < 100; i++) {
245 EXPECT_EQ(i + 1, map.size());
246 EXPECT_FALSE(map.empty());
247 EXPECT_TRUE(map.exists(i));
248 EXPECT_EQ(i, map.get(i));
252 EXPECT_EQ(10, map.size());
253 EXPECT_FALSE(map.empty());
254 for (int i = 0; i < 90; i++) {
255 EXPECT_FALSE(map.exists(i));
257 for (int i = 90; i < 100; i++) {
258 EXPECT_TRUE(map.exists(i));
259 EXPECT_EQ(i, map.get(i));
261 EXPECT_EQ((89 * 90) / 2, sum);
265 TEST(EvictingCacheMap, SetMaxSize) {
266 EvictingCacheMap<int, int> map(100, 20);
267 for (int i = 0; i < 90; i++) {
269 EXPECT_TRUE(map.exists(i));
272 EXPECT_EQ(90, map.size());
274 EXPECT_EQ(map.size(), 50);
276 for (int i = 0; i < 90; i++) {
278 EXPECT_TRUE(map.exists(i));
280 EXPECT_EQ(40, map.size());
282 EXPECT_EQ(40, map.size());
284 EXPECT_EQ(10, map.size());
287 TEST(EvictingCacheMap, SetClearSize) {
288 EvictingCacheMap<int, int> map(100, 20);
289 for (int i = 0; i < 90; i++) {
291 EXPECT_TRUE(map.exists(i));
294 EXPECT_EQ(90, map.size());
295 map.setClearSize(40);
297 EXPECT_EQ(map.size(), 50);
299 for (int i = 0; i < 90; i++) {
301 EXPECT_TRUE(map.exists(i));
303 EXPECT_EQ(20, map.size());
305 EXPECT_EQ(20, map.size());
307 EXPECT_EQ(0, map.size());
310 TEST(EvictingCacheMap, DestructorInvocationTest) {
312 SumInt(int val, int* ref) : val(val), ref(ref) { }
320 EvictingCacheMap<int, SumInt> map(0);
321 EXPECT_EQ(0, map.size());
322 EXPECT_TRUE(map.empty());
323 for (int i = 0; i < 100; i++) {
324 EXPECT_FALSE(map.exists(i));
329 for (int i = 0; i < 100; i++) {
330 map.set(i, SumInt(i, &sum));
331 EXPECT_EQ(i + 1, map.size());
332 EXPECT_FALSE(map.empty());
333 EXPECT_TRUE(map.exists(i));
334 EXPECT_EQ(i, map.get(i).val);
339 EXPECT_EQ(0, map.size());
340 EXPECT_TRUE(map.empty());
341 for (int i = 0; i < 100; i++) {
342 EXPECT_FALSE(map.exists(i));
344 EXPECT_EQ((99 * 100) / 2, sum);
346 for (int i = 0; i < 100; i++) {
347 map.set(i, SumInt(i, &sum));
348 EXPECT_EQ(i + 1, map.size());
349 EXPECT_FALSE(map.empty());
350 EXPECT_TRUE(map.exists(i));
351 EXPECT_EQ(i, map.get(i).val);
356 EXPECT_EQ(0, map.size());
357 EXPECT_TRUE(map.empty());
358 for (int i = 0; i < 100; i++) {
359 EXPECT_FALSE(map.exists(i));
361 EXPECT_EQ((99 * 100) / 2, sum);
363 for (int i = 0; i < 100; i++) {
364 map.set(i, SumInt(i, &sum));
365 EXPECT_EQ(i + 1, map.size());
366 EXPECT_FALSE(map.empty());
367 EXPECT_TRUE(map.exists(i));
368 EXPECT_EQ(i, map.get(i).val);
373 EXPECT_EQ(1, map.size());
374 EXPECT_FALSE(map.empty());
375 for (int i = 0; i < 99; i++) {
376 EXPECT_FALSE(map.exists(i));
378 EXPECT_TRUE(map.exists(99));
379 EXPECT_EQ(99, map.get(99).val);
381 EXPECT_EQ((98 * 99) / 2, sum);
385 EXPECT_EQ(0, map.size());
386 EXPECT_TRUE(map.empty());
387 for (int i = 0; i < 100; i++) {
388 EXPECT_FALSE(map.exists(i));
392 for (int i = 0; i < 100; i++) {
393 map.set(i, SumInt(i, &sum));
394 EXPECT_EQ(i + 1, map.size());
395 EXPECT_FALSE(map.empty());
396 EXPECT_TRUE(map.exists(i));
397 EXPECT_EQ(i, map.get(i).val);
402 EXPECT_EQ(10, map.size());
403 EXPECT_FALSE(map.empty());
404 for (int i = 0; i < 90; i++) {
405 EXPECT_FALSE(map.exists(i));
407 for (int i = 90; i < 100; i++) {
408 EXPECT_TRUE(map.exists(i));
409 EXPECT_EQ(i, map.get(i).val);
411 EXPECT_EQ((89 * 90) / 2, sum);
415 TEST(EvictingCacheMap, LruSanityTest) {
416 EvictingCacheMap<int, int> map(10);
417 EXPECT_EQ(0, map.size());
418 EXPECT_TRUE(map.empty());
419 for (int i = 0; i < 100; i++) {
420 EXPECT_FALSE(map.exists(i));
423 for (int i = 0; i < 100; i++) {
425 EXPECT_GE(10, map.size());
426 EXPECT_FALSE(map.empty());
427 EXPECT_TRUE(map.exists(i));
428 EXPECT_EQ(i, map.get(i));
431 EXPECT_EQ(10, map.size());
432 EXPECT_FALSE(map.empty());
433 for (int i = 0; i < 90; i++) {
434 EXPECT_FALSE(map.exists(i));
436 for (int i = 90; i < 100; i++) {
437 EXPECT_TRUE(map.exists(i));
441 TEST(EvictingCacheMap, LruPromotionTest) {
442 EvictingCacheMap<int, int> map(10);
443 EXPECT_EQ(0, map.size());
444 EXPECT_TRUE(map.empty());
445 for (int i = 0; i < 100; i++) {
446 EXPECT_FALSE(map.exists(i));
449 for (int i = 0; i < 100; i++) {
451 EXPECT_GE(10, map.size());
452 EXPECT_FALSE(map.empty());
453 EXPECT_TRUE(map.exists(i));
454 EXPECT_EQ(i, map.get(i));
455 for (int j = 0; j < std::min(i + 1, 9); j++) {
456 EXPECT_TRUE(map.exists(j));
457 EXPECT_EQ(j, map.get(j));
461 EXPECT_EQ(10, map.size());
462 EXPECT_FALSE(map.empty());
463 for (int i = 0; i < 9; i++) {
464 EXPECT_TRUE(map.exists(i));
466 EXPECT_TRUE(map.exists(99));
467 for (int i = 10; i < 99; i++) {
468 EXPECT_FALSE(map.exists(i));
472 TEST(EvictingCacheMap, LruNoPromotionTest) {
473 EvictingCacheMap<int, int> map(10);
474 EXPECT_EQ(0, map.size());
475 EXPECT_TRUE(map.empty());
476 for (int i = 0; i < 100; i++) {
477 EXPECT_FALSE(map.exists(i));
480 for (int i = 0; i < 100; i++) {
482 EXPECT_GE(10, map.size());
483 EXPECT_FALSE(map.empty());
484 EXPECT_TRUE(map.exists(i));
485 EXPECT_EQ(i, map.get(i));
486 for (int j = 0; j < std::min(i + 1, 9); j++) {
488 EXPECT_EQ(j, map.getWithoutPromotion(j));
493 EXPECT_EQ(10, map.size());
494 EXPECT_FALSE(map.empty());
495 for (int i = 0; i < 90; i++) {
496 EXPECT_FALSE(map.exists(i));
498 for (int i = 90; i < 100; i++) {
499 EXPECT_TRUE(map.exists(i));
503 TEST(EvictingCacheMap, IteratorSanityTest) {
504 const int nItems = 1000;
505 EvictingCacheMap<int, int> map(nItems);
506 EXPECT_TRUE(map.begin() == map.end());
507 for (int i = 0; i < nItems; i++) {
508 EXPECT_FALSE(map.exists(i));
510 EXPECT_TRUE(map.exists(i));
511 EXPECT_EQ(i * 2, map.get(i));
515 for (auto& it : map) {
516 EXPECT_EQ(0, seen.count(it.first));
517 seen.insert(it.first);
518 EXPECT_EQ(it.first * 2, it.second);
520 EXPECT_EQ(nItems, seen.size());
523 TEST(EvictingCacheMap, FindTest) {
524 const int nItems = 1000;
525 EvictingCacheMap<int, int> map(nItems);
526 for (int i = 0; i < nItems; i++) {
527 map.set(i * 2, i * 2);
528 EXPECT_TRUE(map.exists(i * 2));
529 EXPECT_EQ(i * 2, map.get(i * 2));
531 for (int i = 0; i < nItems * 2; i++) {
533 auto it = map.find(i);
534 EXPECT_FALSE(it == map.end());
535 EXPECT_EQ(i, it->first);
536 EXPECT_EQ(i, it->second);
538 EXPECT_TRUE( map.find(i) == map.end());
541 for (int i = nItems * 2 - 1; i >= 0; i--) {
543 auto it = map.find(i);
544 EXPECT_FALSE(it == map.end());
545 EXPECT_EQ(i, it->first);
546 EXPECT_EQ(i, it->second);
548 EXPECT_TRUE(map.find(i) == map.end());
551 EXPECT_EQ(0, map.begin()->first);
554 TEST(EvictingCacheMap, FindWithoutPromotionTest) {
555 const int nItems = 1000;
556 EvictingCacheMap<int, int> map(nItems);
557 for (int i = 0; i < nItems; i++) {
558 map.set(i * 2, i * 2);
559 EXPECT_TRUE(map.exists(i * 2));
560 EXPECT_EQ(i * 2, map.get(i * 2));
562 for (int i = nItems * 2 - 1; i >= 0; i--) {
564 auto it = map.findWithoutPromotion(i);
565 EXPECT_FALSE(it == map.end());
566 EXPECT_EQ(i, it->first);
567 EXPECT_EQ(i, it->second);
569 EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
572 EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
575 TEST(EvictingCacheMap, IteratorOrderingTest) {
576 const int nItems = 1000;
577 EvictingCacheMap<int, int> map(nItems);
578 for (int i = 0; i < nItems; i++) {
580 EXPECT_TRUE(map.exists(i));
581 EXPECT_EQ(i, map.get(i));
584 int expected = nItems - 1;
585 for (auto it = map.begin(); it != map.end(); ++it) {
586 EXPECT_EQ(expected, it->first);
591 for (auto it = map.rbegin(); it != map.rend(); ++it) {
592 EXPECT_EQ(expected, it->first);
599 EXPECT_TRUE(it != map.begin());
602 EXPECT_EQ(expected, it->first);
604 } while (it != map.begin());
605 EXPECT_EQ(nItems, expected);
609 auto it = map.rend();
610 expected = nItems - 1;
613 EXPECT_EQ(expected, it->first);
615 } while (it != map.rbegin());
616 EXPECT_EQ(-1, expected);
620 TEST(EvictingCacheMap, MoveTest) {
621 const int nItems = 1000;
622 EvictingCacheMap<int, int> map(nItems);
623 for (int i = 0; i < nItems; i++) {
625 EXPECT_TRUE(map.exists(i));
626 EXPECT_EQ(i, map.get(i));
629 EvictingCacheMap<int, int> map2 = std::move(map);
630 EXPECT_TRUE(map.empty());
631 for (int i = 0; i < nItems; i++) {
632 EXPECT_TRUE(map2.exists(i));
633 EXPECT_EQ(i, map2.get(i));