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 | |
22 | using namespace folly; |
23 | |
24 | TEST(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 | |
80 | TEST(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 | |
162 | TEST(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 | |
264 | TEST(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 | |
286 | TEST(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 | |
309 | TEST(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 | |
414 | TEST(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 | |
440 | TEST(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 | |
471 | TEST(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 | |
502 | TEST(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 | |
522 | TEST(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 | |
553 | TEST(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 | |
574 | TEST(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 | |
619 | TEST(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 | |
636 | TEST(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 | |