1/*
2 * Copyright 2014-present Facebook, Inc.
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 <set>
18
19#include <folly/container/EvictingCacheMap.h>
20#include <folly/portability/GTest.h>
21
22using namespace folly;
23
24TEST(EvictingCacheMap, SanityTest) {
25 EvictingCacheMap<int, int> map(0);
26
27 EXPECT_EQ(0, map.size());
28 EXPECT_TRUE(map.empty());
29 EXPECT_FALSE(map.exists(1));
30 map.set(1, 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));
35 map.set(1, 2);
36 EXPECT_EQ(1, map.size());
37 EXPECT_FALSE(map.empty());
38 EXPECT_EQ(2, map.get(1));
39 EXPECT_TRUE(map.exists(1));
40 map.erase(1);
41 EXPECT_EQ(0, map.size());
42 EXPECT_TRUE(map.empty());
43 EXPECT_FALSE(map.exists(1));
44
45 EXPECT_EQ(0, map.size());
46 EXPECT_TRUE(map.empty());
47 EXPECT_FALSE(map.exists(1));
48 map.set(1, 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));
53 map.set(1, 2);
54 EXPECT_EQ(1, map.size());
55 EXPECT_FALSE(map.empty());
56 EXPECT_EQ(2, map.get(1));
57 EXPECT_TRUE(map.exists(1));
58
59 EXPECT_FALSE(map.exists(2));
60 map.set(2, 1);
61 EXPECT_TRUE(map.exists(2));
62 EXPECT_EQ(2, map.size());
63 EXPECT_FALSE(map.empty());
64 EXPECT_EQ(1, map.get(2));
65 map.set(2, 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));
70 map.erase(2);
71 EXPECT_EQ(1, map.size());
72 EXPECT_FALSE(map.empty());
73 EXPECT_FALSE(map.exists(2));
74 map.erase(1);
75 EXPECT_EQ(0, map.size());
76 EXPECT_TRUE(map.empty());
77 EXPECT_FALSE(map.exists(1));
78}
79
80TEST(EvictingCacheMap, PruneTest) {
81 EvictingCacheMap<int, int> map(0);
82 EXPECT_EQ(0, map.size());
83 EXPECT_TRUE(map.empty());
84 for (int i = 0; i < 100; i++) {
85 EXPECT_FALSE(map.exists(i));
86 }
87
88 for (int i = 0; i < 100; i++) {
89 map.set(i, i);
90 EXPECT_EQ(i + 1, map.size());
91 EXPECT_FALSE(map.empty());
92 EXPECT_TRUE(map.exists(i));
93 EXPECT_EQ(i, map.get(i));
94 }
95
96 map.prune(1000000);
97 EXPECT_EQ(0, map.size());
98 EXPECT_TRUE(map.empty());
99 for (int i = 0; i < 100; i++) {
100 EXPECT_FALSE(map.exists(i));
101 }
102
103 for (int i = 0; i < 100; i++) {
104 map.set(i, i);
105 EXPECT_EQ(i + 1, map.size());
106 EXPECT_FALSE(map.empty());
107 EXPECT_TRUE(map.exists(i));
108 EXPECT_EQ(i, map.get(i));
109 }
110
111 map.prune(100);
112 EXPECT_EQ(0, map.size());
113 EXPECT_TRUE(map.empty());
114 for (int i = 0; i < 100; i++) {
115 EXPECT_FALSE(map.exists(i));
116 }
117
118 for (int i = 0; i < 100; i++) {
119 map.set(i, i);
120 EXPECT_EQ(i + 1, map.size());
121 EXPECT_FALSE(map.empty());
122 EXPECT_TRUE(map.exists(i));
123 EXPECT_EQ(i, map.get(i));
124 }
125
126 map.prune(99);
127 EXPECT_EQ(1, map.size());
128 EXPECT_FALSE(map.empty());
129 for (int i = 0; i < 99; i++) {
130 EXPECT_FALSE(map.exists(i));
131 }
132 EXPECT_TRUE(map.exists(99));
133 EXPECT_EQ(99, map.get(99));
134
135 map.prune(100);
136 EXPECT_EQ(0, map.size());
137 EXPECT_TRUE(map.empty());
138 for (int i = 0; i < 100; i++) {
139 EXPECT_FALSE(map.exists(i));
140 }
141
142 for (int i = 0; i < 100; i++) {
143 map.set(i, i);
144 EXPECT_EQ(i + 1, map.size());
145 EXPECT_FALSE(map.empty());
146 EXPECT_TRUE(map.exists(i));
147 EXPECT_EQ(i, map.get(i));
148 }
149
150 map.prune(90);
151 EXPECT_EQ(10, map.size());
152 EXPECT_FALSE(map.empty());
153 for (int i = 0; i < 90; i++) {
154 EXPECT_FALSE(map.exists(i));
155 }
156 for (int i = 90; i < 100; i++) {
157 EXPECT_TRUE(map.exists(i));
158 EXPECT_EQ(i, map.get(i));
159 }
160}
161
162TEST(EvictingCacheMap, PruneHookTest) {
163 EvictingCacheMap<int, int> map(0);
164 EXPECT_EQ(0, map.size());
165 EXPECT_TRUE(map.empty());
166 for (int i = 0; i < 100; i++) {
167 EXPECT_FALSE(map.exists(i));
168 }
169
170 int sum = 0;
171 auto pruneCb = [&](int&& k, int&& v) {
172 EXPECT_EQ(k, v);
173 sum += k;
174 };
175
176 map.setPruneHook(pruneCb);
177
178 for (int i = 0; i < 100; i++) {
179 map.set(i, i);
180 EXPECT_EQ(i + 1, map.size());
181 EXPECT_FALSE(map.empty());
182 EXPECT_TRUE(map.exists(i));
183 EXPECT_EQ(i, map.get(i));
184 }
185
186 map.prune(1000000);
187 EXPECT_EQ(0, map.size());
188 EXPECT_TRUE(map.empty());
189 for (int i = 0; i < 100; i++) {
190 EXPECT_FALSE(map.exists(i));
191 }
192 EXPECT_EQ((99 * 100) / 2, sum);
193 sum = 0;
194
195 for (int i = 0; i < 100; i++) {
196 map.set(i, i);
197 EXPECT_EQ(i + 1, map.size());
198 EXPECT_FALSE(map.empty());
199 EXPECT_TRUE(map.exists(i));
200 EXPECT_EQ(i, map.get(i));
201 }
202
203 map.prune(100);
204 EXPECT_EQ(0, map.size());
205 EXPECT_TRUE(map.empty());
206 for (int i = 0; i < 100; i++) {
207 EXPECT_FALSE(map.exists(i));
208 }
209 EXPECT_EQ((99 * 100) / 2, sum);
210 sum = 0;
211
212 for (int i = 0; i < 100; i++) {
213 map.set(i, i);
214 EXPECT_EQ(i + 1, map.size());
215 EXPECT_FALSE(map.empty());
216 EXPECT_TRUE(map.exists(i));
217 EXPECT_EQ(i, map.get(i));
218 }
219
220 map.prune(99);
221 EXPECT_EQ(1, map.size());
222 EXPECT_FALSE(map.empty());
223 for (int i = 0; i < 99; i++) {
224 EXPECT_FALSE(map.exists(i));
225 }
226 EXPECT_TRUE(map.exists(99));
227 EXPECT_EQ(99, map.get(99));
228
229 EXPECT_EQ((98 * 99) / 2, sum);
230 sum = 0;
231
232 map.prune(100);
233 EXPECT_EQ(0, map.size());
234 EXPECT_TRUE(map.empty());
235 for (int i = 0; i < 100; i++) {
236 EXPECT_FALSE(map.exists(i));
237 }
238
239 EXPECT_EQ(99, sum);
240 sum = 0;
241
242 for (int i = 0; i < 100; i++) {
243 map.set(i, i);
244 EXPECT_EQ(i + 1, map.size());
245 EXPECT_FALSE(map.empty());
246 EXPECT_TRUE(map.exists(i));
247 EXPECT_EQ(i, map.get(i));
248 }
249
250 map.prune(90);
251 EXPECT_EQ(10, map.size());
252 EXPECT_FALSE(map.empty());
253 for (int i = 0; i < 90; i++) {
254 EXPECT_FALSE(map.exists(i));
255 }
256 for (int i = 90; i < 100; i++) {
257 EXPECT_TRUE(map.exists(i));
258 EXPECT_EQ(i, map.get(i));
259 }
260 EXPECT_EQ((89 * 90) / 2, sum);
261 sum = 0;
262}
263
264TEST(EvictingCacheMap, SetMaxSize) {
265 EvictingCacheMap<int, int> map(100, 20);
266 for (int i = 0; i < 90; i++) {
267 map.set(i, i);
268 EXPECT_TRUE(map.exists(i));
269 }
270
271 EXPECT_EQ(90, map.size());
272 map.setMaxSize(50);
273 EXPECT_EQ(map.size(), 50);
274
275 for (int i = 0; i < 90; i++) {
276 map.set(i, i);
277 EXPECT_TRUE(map.exists(i));
278 }
279 EXPECT_EQ(40, map.size());
280 map.setMaxSize(0);
281 EXPECT_EQ(40, map.size());
282 map.setMaxSize(10);
283 EXPECT_EQ(10, map.size());
284}
285
286TEST(EvictingCacheMap, SetClearSize) {
287 EvictingCacheMap<int, int> map(100, 20);
288 for (int i = 0; i < 90; i++) {
289 map.set(i, i);
290 EXPECT_TRUE(map.exists(i));
291 }
292
293 EXPECT_EQ(90, map.size());
294 map.setClearSize(40);
295 map.setMaxSize(50);
296 EXPECT_EQ(map.size(), 50);
297
298 for (int i = 0; i < 90; i++) {
299 map.set(i, i);
300 EXPECT_TRUE(map.exists(i));
301 }
302 EXPECT_EQ(20, map.size());
303 map.setMaxSize(0);
304 EXPECT_EQ(20, map.size());
305 map.setMaxSize(10);
306 EXPECT_EQ(0, map.size());
307}
308
309TEST(EvictingCacheMap, DestructorInvocationTest) {
310 struct SumInt {
311 SumInt(int val_, int* ref_) : val(val_), ref(ref_) {}
312 ~SumInt() {
313 *ref += val;
314 }
315 int val;
316 int* ref;
317 };
318
319 int sum;
320 EvictingCacheMap<int, SumInt> map(0);
321
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));
326 }
327
328 for (int i = 0; i < 100; i++) {
329 map.set(i, SumInt(i, &sum));
330 EXPECT_EQ(i + 1, map.size());
331 EXPECT_FALSE(map.empty());
332 EXPECT_TRUE(map.exists(i));
333 EXPECT_EQ(i, map.get(i).val);
334 }
335
336 sum = 0;
337 map.prune(1000000);
338 EXPECT_EQ(0, map.size());
339 EXPECT_TRUE(map.empty());
340 for (int i = 0; i < 100; i++) {
341 EXPECT_FALSE(map.exists(i));
342 }
343 EXPECT_EQ((99 * 100) / 2, sum);
344
345 for (int i = 0; i < 100; i++) {
346 map.set(i, SumInt(i, &sum));
347 EXPECT_EQ(i + 1, map.size());
348 EXPECT_FALSE(map.empty());
349 EXPECT_TRUE(map.exists(i));
350 EXPECT_EQ(i, map.get(i).val);
351 }
352
353 sum = 0;
354 map.prune(100);
355 EXPECT_EQ(0, map.size());
356 EXPECT_TRUE(map.empty());
357 for (int i = 0; i < 100; i++) {
358 EXPECT_FALSE(map.exists(i));
359 }
360 EXPECT_EQ((99 * 100) / 2, sum);
361
362 for (int i = 0; i < 100; i++) {
363 map.set(i, SumInt(i, &sum));
364 EXPECT_EQ(i + 1, map.size());
365 EXPECT_FALSE(map.empty());
366 EXPECT_TRUE(map.exists(i));
367 EXPECT_EQ(i, map.get(i).val);
368 }
369
370 sum = 0;
371 map.prune(99);
372 EXPECT_EQ(1, map.size());
373 EXPECT_FALSE(map.empty());
374 for (int i = 0; i < 99; i++) {
375 EXPECT_FALSE(map.exists(i));
376 }
377 EXPECT_TRUE(map.exists(99));
378 EXPECT_EQ(99, map.get(99).val);
379
380 EXPECT_EQ((98 * 99) / 2, sum);
381
382 sum = 0;
383 map.prune(100);
384 EXPECT_EQ(0, map.size());
385 EXPECT_TRUE(map.empty());
386 for (int i = 0; i < 100; i++) {
387 EXPECT_FALSE(map.exists(i));
388 }
389
390 EXPECT_EQ(99, sum);
391 for (int i = 0; i < 100; i++) {
392 map.set(i, SumInt(i, &sum));
393 EXPECT_EQ(i + 1, map.size());
394 EXPECT_FALSE(map.empty());
395 EXPECT_TRUE(map.exists(i));
396 EXPECT_EQ(i, map.get(i).val);
397 }
398
399 sum = 0;
400 map.prune(90);
401 EXPECT_EQ(10, map.size());
402 EXPECT_FALSE(map.empty());
403 for (int i = 0; i < 90; i++) {
404 EXPECT_FALSE(map.exists(i));
405 }
406 for (int i = 90; i < 100; i++) {
407 EXPECT_TRUE(map.exists(i));
408 EXPECT_EQ(i, map.get(i).val);
409 }
410 EXPECT_EQ((89 * 90) / 2, sum);
411 sum = 0;
412}
413
414TEST(EvictingCacheMap, LruSanityTest) {
415 EvictingCacheMap<int, int> map(10);
416 EXPECT_EQ(0, map.size());
417 EXPECT_TRUE(map.empty());
418 for (int i = 0; i < 100; i++) {
419 EXPECT_FALSE(map.exists(i));
420 }
421
422 for (int i = 0; i < 100; i++) {
423 map.set(i, i);
424 EXPECT_GE(10, map.size());
425 EXPECT_FALSE(map.empty());
426 EXPECT_TRUE(map.exists(i));
427 EXPECT_EQ(i, map.get(i));
428 }
429
430 EXPECT_EQ(10, map.size());
431 EXPECT_FALSE(map.empty());
432 for (int i = 0; i < 90; i++) {
433 EXPECT_FALSE(map.exists(i));
434 }
435 for (int i = 90; i < 100; i++) {
436 EXPECT_TRUE(map.exists(i));
437 }
438}
439
440TEST(EvictingCacheMap, LruPromotionTest) {
441 EvictingCacheMap<int, int> map(10);
442 EXPECT_EQ(0, map.size());
443 EXPECT_TRUE(map.empty());
444 for (int i = 0; i < 100; i++) {
445 EXPECT_FALSE(map.exists(i));
446 }
447
448 for (int i = 0; i < 100; i++) {
449 map.set(i, i);
450 EXPECT_GE(10, map.size());
451 EXPECT_FALSE(map.empty());
452 EXPECT_TRUE(map.exists(i));
453 EXPECT_EQ(i, map.get(i));
454 for (int j = 0; j < std::min(i + 1, 9); j++) {
455 EXPECT_TRUE(map.exists(j));
456 EXPECT_EQ(j, map.get(j));
457 }
458 }
459
460 EXPECT_EQ(10, map.size());
461 EXPECT_FALSE(map.empty());
462 for (int i = 0; i < 9; i++) {
463 EXPECT_TRUE(map.exists(i));
464 }
465 EXPECT_TRUE(map.exists(99));
466 for (int i = 10; i < 99; i++) {
467 EXPECT_FALSE(map.exists(i));
468 }
469}
470
471TEST(EvictingCacheMap, LruNoPromotionTest) {
472 EvictingCacheMap<int, int> map(10);
473 EXPECT_EQ(0, map.size());
474 EXPECT_TRUE(map.empty());
475 for (int i = 0; i < 100; i++) {
476 EXPECT_FALSE(map.exists(i));
477 }
478
479 for (int i = 0; i < 100; i++) {
480 map.set(i, i);
481 EXPECT_GE(10, map.size());
482 EXPECT_FALSE(map.empty());
483 EXPECT_TRUE(map.exists(i));
484 EXPECT_EQ(i, map.get(i));
485 for (int j = 0; j < std::min(i + 1, 9); j++) {
486 if (map.exists(j)) {
487 EXPECT_EQ(j, map.getWithoutPromotion(j));
488 }
489 }
490 }
491
492 EXPECT_EQ(10, map.size());
493 EXPECT_FALSE(map.empty());
494 for (int i = 0; i < 90; i++) {
495 EXPECT_FALSE(map.exists(i));
496 }
497 for (int i = 90; i < 100; i++) {
498 EXPECT_TRUE(map.exists(i));
499 }
500}
501
502TEST(EvictingCacheMap, IteratorSanityTest) {
503 const int nItems = 1000;
504 EvictingCacheMap<int, int> map(nItems);
505 EXPECT_TRUE(map.begin() == map.end());
506 for (int i = 0; i < nItems; i++) {
507 EXPECT_FALSE(map.exists(i));
508 map.set(i, i * 2);
509 EXPECT_TRUE(map.exists(i));
510 EXPECT_EQ(i * 2, map.get(i));
511 }
512
513 std::set<int> seen;
514 for (auto& it : map) {
515 EXPECT_EQ(0, seen.count(it.first));
516 seen.insert(it.first);
517 EXPECT_EQ(it.first * 2, it.second);
518 }
519 EXPECT_EQ(nItems, seen.size());
520}
521
522TEST(EvictingCacheMap, FindTest) {
523 const int nItems = 1000;
524 EvictingCacheMap<int, int> map(nItems);
525 for (int i = 0; i < nItems; i++) {
526 map.set(i * 2, i * 2);
527 EXPECT_TRUE(map.exists(i * 2));
528 EXPECT_EQ(i * 2, map.get(i * 2));
529 }
530 for (int i = 0; i < nItems * 2; i++) {
531 if (i % 2 == 0) {
532 auto it = map.find(i);
533 EXPECT_FALSE(it == map.end());
534 EXPECT_EQ(i, it->first);
535 EXPECT_EQ(i, it->second);
536 } else {
537 EXPECT_TRUE(map.find(i) == map.end());
538 }
539 }
540 for (int i = nItems * 2 - 1; i >= 0; i--) {
541 if (i % 2 == 0) {
542 auto it = map.find(i);
543 EXPECT_FALSE(it == map.end());
544 EXPECT_EQ(i, it->first);
545 EXPECT_EQ(i, it->second);
546 } else {
547 EXPECT_TRUE(map.find(i) == map.end());
548 }
549 }
550 EXPECT_EQ(0, map.begin()->first);
551}
552
553TEST(EvictingCacheMap, FindWithoutPromotionTest) {
554 const int nItems = 1000;
555 EvictingCacheMap<int, int> map(nItems);
556 for (int i = 0; i < nItems; i++) {
557 map.set(i * 2, i * 2);
558 EXPECT_TRUE(map.exists(i * 2));
559 EXPECT_EQ(i * 2, map.get(i * 2));
560 }
561 for (int i = nItems * 2 - 1; i >= 0; i--) {
562 if (i % 2 == 0) {
563 auto it = map.findWithoutPromotion(i);
564 EXPECT_FALSE(it == map.end());
565 EXPECT_EQ(i, it->first);
566 EXPECT_EQ(i, it->second);
567 } else {
568 EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
569 }
570 }
571 EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
572}
573
574TEST(EvictingCacheMap, IteratorOrderingTest) {
575 const int nItems = 1000;
576 EvictingCacheMap<int, int> map(nItems);
577 for (int i = 0; i < nItems; i++) {
578 map.set(i, i);
579 EXPECT_TRUE(map.exists(i));
580 EXPECT_EQ(i, map.get(i));
581 }
582
583 int expected = nItems - 1;
584 for (auto it = map.begin(); it != map.end(); ++it) {
585 EXPECT_EQ(expected, it->first);
586 expected--;
587 }
588
589 expected = 0;
590 for (auto it = map.rbegin(); it != map.rend(); ++it) {
591 EXPECT_EQ(expected, it->first);
592 expected++;
593 }
594
595 {
596 auto it = map.end();
597 expected = 0;
598 EXPECT_TRUE(it != map.begin());
599 do {
600 --it;
601 EXPECT_EQ(expected, it->first);
602 expected++;
603 } while (it != map.begin());
604 EXPECT_EQ(nItems, expected);
605 }
606
607 {
608 auto it = map.rend();
609 expected = nItems - 1;
610 do {
611 --it;
612 EXPECT_EQ(expected, it->first);
613 expected--;
614 } while (it != map.rbegin());
615 EXPECT_EQ(-1, expected);
616 }
617}
618
619TEST(EvictingCacheMap, MoveTest) {
620 const int nItems = 1000;
621 EvictingCacheMap<int, int> map(nItems);
622 for (int i = 0; i < nItems; i++) {
623 map.set(i, i);
624 EXPECT_TRUE(map.exists(i));
625 EXPECT_EQ(i, map.get(i));
626 }
627
628 EvictingCacheMap<int, int> map2 = std::move(map);
629 EXPECT_TRUE(map.empty());
630 for (int i = 0; i < nItems; i++) {
631 EXPECT_TRUE(map2.exists(i));
632 EXPECT_EQ(i, map2.get(i));
633 }
634}
635
636TEST(EvictingCacheMap, CustomKeyEqual) {
637 const int nItems = 100;
638 struct Eq {
639 bool operator()(const int& a, const int& b) const {
640 return (a % mod) == (b % mod);
641 }
642 int mod;
643 };
644 struct Hash {
645 size_t operator()(const int& a) const {
646 return std::hash<int>()(a % mod);
647 }
648 int mod;
649 };
650 EvictingCacheMap<int, int, Hash, Eq> map(
651 nItems, 1 /* clearSize */, Hash{nItems}, Eq{nItems});
652 for (int i = 0; i < nItems; i++) {
653 map.set(i, i);
654 EXPECT_TRUE(map.exists(i));
655 EXPECT_EQ(i, map.get(i));
656 EXPECT_TRUE(map.exists(i + nItems));
657 EXPECT_EQ(i, map.get(i + nItems));
658 }
659}
660