folly/test/EvictingCacheMapTest.cpp

   1 /*
   2  * Copyright 2017 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/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
  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));
  87   }
  88
  89   for (int i = 0; i < 100; i++) {
  90     map.set(i, 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));
  95   }
  96
  97   map.prune(1000000);
  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));
 102   }
 103
 104   for (int i = 0; i < 100; i++) {
 105     map.set(i, 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));
 110   }
 111
 112   map.prune(100);
 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));
 117   }
 118
 119   for (int i = 0; i < 100; i++) {
 120     map.set(i, 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));
 125   }
 126
 127   map.prune(99);
 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));
 132   }
 133   EXPECT_TRUE(map.exists(99));
 134   EXPECT_EQ(99, map.get(99));
 135
 136   map.prune(100);
 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));
 141   }
 142
 143   for (int i = 0; i < 100; i++) {
 144     map.set(i, 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));
 149   }
 150
 151   map.prune(90);
 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));
 156   }
 157   for (int i = 90; i < 100; i++) {
 158     EXPECT_TRUE(map.exists(i));
 159     EXPECT_EQ(i, map.get(i));
 160   }
 161 }
 162
 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));
 169   }
 170
 171   int sum = 0;
 172   auto pruneCb = [&](int&& k, int&& v) {
 173     EXPECT_EQ(k, v);
 174     sum += k;
 175   };
 176
 177   map.setPruneHook(pruneCb);
 178
 179   for (int i = 0; i < 100; i++) {
 180     map.set(i, 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));
 185   }
 186
 187   map.prune(1000000);
 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));
 192   }
 193   EXPECT_EQ((99 * 100) / 2, sum);
 194   sum = 0;
 195
 196   for (int i = 0; i < 100; i++) {
 197     map.set(i, 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));
 202   }
 203
 204   map.prune(100);
 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));
 209   }
 210   EXPECT_EQ((99 * 100) / 2, sum);
 211   sum = 0;
 212
 213   for (int i = 0; i < 100; i++) {
 214     map.set(i, 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));
 219   }
 220
 221   map.prune(99);
 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));
 226   }
 227   EXPECT_TRUE(map.exists(99));
 228   EXPECT_EQ(99, map.get(99));
 229
 230   EXPECT_EQ((98 * 99) / 2, sum);
 231   sum = 0;
 232
 233   map.prune(100);
 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));
 238   }
 239
 240   EXPECT_EQ(99, sum);
 241   sum = 0;
 242
 243   for (int i = 0; i < 100; i++) {
 244     map.set(i, 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));
 249   }
 250
 251   map.prune(90);
 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));
 256   }
 257   for (int i = 90; i < 100; i++) {
 258     EXPECT_TRUE(map.exists(i));
 259     EXPECT_EQ(i, map.get(i));
 260   }
 261   EXPECT_EQ((89 * 90) / 2, sum);
 262   sum = 0;
 263 }
 264
 265 TEST(EvictingCacheMap, SetMaxSize) {
 266   EvictingCacheMap<int, int> map(100, 20);
 267   for (int i = 0; i < 90; i++) {
 268     map.set(i, i);
 269     EXPECT_TRUE(map.exists(i));
 270   }
 271
 272   EXPECT_EQ(90, map.size());
 273   map.setMaxSize(50);
 274   EXPECT_EQ(map.size(), 50);
 275
 276   for (int i = 0; i < 90; i++) {
 277     map.set(i, i);
 278     EXPECT_TRUE(map.exists(i));
 279   }
 280   EXPECT_EQ(40, map.size());
 281   map.setMaxSize(0);
 282   EXPECT_EQ(40, map.size());
 283   map.setMaxSize(10);
 284   EXPECT_EQ(10, map.size());
 285 }
 286
 287 TEST(EvictingCacheMap, SetClearSize) {
 288   EvictingCacheMap<int, int> map(100, 20);
 289   for (int i = 0; i < 90; i++) {
 290     map.set(i, i);
 291     EXPECT_TRUE(map.exists(i));
 292   }
 293
 294   EXPECT_EQ(90, map.size());
 295   map.setClearSize(40);
 296   map.setMaxSize(50);
 297   EXPECT_EQ(map.size(), 50);
 298
 299   for (int i = 0; i < 90; i++) {
 300     map.set(i, i);
 301     EXPECT_TRUE(map.exists(i));
 302   }
 303   EXPECT_EQ(20, map.size());
 304   map.setMaxSize(0);
 305   EXPECT_EQ(20, map.size());
 306   map.setMaxSize(10);
 307   EXPECT_EQ(0, map.size());
 308 }
 309
 310 TEST(EvictingCacheMap, DestructorInvocationTest) {
 311   struct SumInt {
 312     SumInt(int val, int* ref) : val(val), ref(ref) { }
 313     ~SumInt() {
 314       *ref += val;
 315     }
 316     int val;
 317     int* ref;
 318   };
 319
 320   int sum;
 321   EvictingCacheMap<int, SumInt> map(0);
 322
 323   EXPECT_EQ(0, map.size());
 324   EXPECT_TRUE(map.empty());
 325   for (int i = 0; i < 100; i++) {
 326     EXPECT_FALSE(map.exists(i));
 327   }
 328
 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);
 335   }
 336
 337   sum = 0;
 338   map.prune(1000000);
 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));
 343   }
 344   EXPECT_EQ((99 * 100) / 2, sum);
 345
 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);
 352   }
 353
 354   sum = 0;
 355   map.prune(100);
 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));
 360   }
 361   EXPECT_EQ((99 * 100) / 2, sum);
 362
 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);
 369   }
 370
 371   sum = 0;
 372   map.prune(99);
 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));
 377   }
 378   EXPECT_TRUE(map.exists(99));
 379   EXPECT_EQ(99, map.get(99).val);
 380
 381   EXPECT_EQ((98 * 99) / 2, sum);
 382
 383   sum = 0;
 384   map.prune(100);
 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));
 389   }
 390
 391   EXPECT_EQ(99, sum);
 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);
 398   }
 399
 400   sum = 0;
 401   map.prune(90);
 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));
 406   }
 407   for (int i = 90; i < 100; i++) {
 408     EXPECT_TRUE(map.exists(i));
 409     EXPECT_EQ(i, map.get(i).val);
 410   }
 411   EXPECT_EQ((89 * 90) / 2, sum);
 412   sum = 0;
 413 }
 414
 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));
 421   }
 422
 423   for (int i = 0; i < 100; i++) {
 424     map.set(i, 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));
 429   }
 430
 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));
 435   }
 436   for (int i = 90; i < 100; i++) {
 437     EXPECT_TRUE(map.exists(i));
 438   }
 439 }
 440
 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));
 447   }
 448
 449   for (int i = 0; i < 100; i++) {
 450     map.set(i, 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));
 458     }
 459   }
 460
 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));
 465   }
 466   EXPECT_TRUE(map.exists(99));
 467   for (int i = 10; i < 99; i++) {
 468     EXPECT_FALSE(map.exists(i));
 469   }
 470 }
 471
 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));
 478   }
 479
 480   for (int i = 0; i < 100; i++) {
 481     map.set(i, 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++) {
 487       if (map.exists(j)) {
 488         EXPECT_EQ(j, map.getWithoutPromotion(j));
 489       }
 490     }
 491   }
 492
 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));
 497   }
 498   for (int i = 90; i < 100; i++) {
 499     EXPECT_TRUE(map.exists(i));
 500   }
 501 }
 502
 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));
 509     map.set(i, i * 2);
 510     EXPECT_TRUE(map.exists(i));
 511     EXPECT_EQ(i * 2, map.get(i));
 512   }
 513
 514   std::set<int> seen;
 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);
 519   }
 520   EXPECT_EQ(nItems, seen.size());
 521 }
 522
 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));
 530   }
 531   for (int i = 0; i < nItems * 2; i++) {
 532     if (i % 2 == 0) {
 533       auto it = map.find(i);
 534       EXPECT_FALSE(it == map.end());
 535       EXPECT_EQ(i, it->first);
 536       EXPECT_EQ(i, it->second);
 537     } else {
 538       EXPECT_TRUE( map.find(i) == map.end());
 539     }
 540   }
 541   for (int i = nItems * 2 - 1; i >= 0; i--) {
 542     if (i % 2 == 0) {
 543       auto it = map.find(i);
 544       EXPECT_FALSE(it == map.end());
 545       EXPECT_EQ(i, it->first);
 546       EXPECT_EQ(i, it->second);
 547     } else {
 548       EXPECT_TRUE(map.find(i) == map.end());
 549     }
 550   }
 551   EXPECT_EQ(0, map.begin()->first);
 552 }
 553
 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));
 561   }
 562   for (int i = nItems * 2 - 1; i >= 0; i--) {
 563     if (i % 2 == 0) {
 564       auto it = map.findWithoutPromotion(i);
 565       EXPECT_FALSE(it == map.end());
 566       EXPECT_EQ(i, it->first);
 567       EXPECT_EQ(i, it->second);
 568     } else {
 569       EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
 570     }
 571   }
 572   EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
 573 }
 574
 575 TEST(EvictingCacheMap, IteratorOrderingTest) {
 576   const int nItems = 1000;
 577   EvictingCacheMap<int, int> map(nItems);
 578   for (int i = 0; i < nItems; i++) {
 579     map.set(i, i);
 580     EXPECT_TRUE(map.exists(i));
 581     EXPECT_EQ(i, map.get(i));
 582   }
 583
 584   int expected = nItems - 1;
 585   for (auto it = map.begin(); it != map.end(); ++it) {
 586     EXPECT_EQ(expected, it->first);
 587     expected--;
 588   }
 589
 590   expected = 0;
 591   for (auto it = map.rbegin(); it != map.rend(); ++it) {
 592     EXPECT_EQ(expected, it->first);
 593     expected++;
 594   }
 595
 596   {
 597     auto it = map.end();
 598     expected = 0;
 599     EXPECT_TRUE(it != map.begin());
 600     do {
 601       --it;
 602       EXPECT_EQ(expected, it->first);
 603       expected++;
 604     } while (it != map.begin());
 605     EXPECT_EQ(nItems, expected);
 606   }
 607
 608   {
 609     auto it = map.rend();
 610     expected = nItems - 1;
 611     do {
 612       --it;
 613       EXPECT_EQ(expected, it->first);
 614       expected--;
 615     } while (it != map.rbegin());
 616     EXPECT_EQ(-1, expected);
 617   }
 618 }
 619
 620 TEST(EvictingCacheMap, MoveTest) {
 621   const int nItems = 1000;
 622   EvictingCacheMap<int, int> map(nItems);
 623   for (int i = 0; i < nItems; i++) {
 624     map.set(i, i);
 625     EXPECT_TRUE(map.exists(i));
 626     EXPECT_EQ(i, map.get(i));
 627   }
 628
 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));
 634   }
 635 }