folly/test/EvictingCacheMapTest.cpp

   1 /*
   2  * Copyright 2015 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 <gtest/gtest.h>
  18
  19 #include <set>
  20
  21 #include <folly/EvictingCacheMap.h>
  22
  23 using namespace folly;
  24
  25 TEST(EvictingCacheMap, SanityTest) {
  26   EvictingCacheMap<int, int> map(0);
  27
  28   EXPECT_EQ(0, map.size());
  29   EXPECT_TRUE(map.empty());
  30   EXPECT_FALSE(map.exists(1));
  31   map.set(1, 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));
  36   map.set(1, 2);
  37   EXPECT_EQ(1, map.size());
  38   EXPECT_FALSE(map.empty());
  39   EXPECT_EQ(2, map.get(1));
  40   EXPECT_TRUE(map.exists(1));
  41   map.erase(1);
  42   EXPECT_EQ(0, map.size());
  43   EXPECT_TRUE(map.empty());
  44   EXPECT_FALSE(map.exists(1));
  45
  46   EXPECT_EQ(0, map.size());
  47   EXPECT_TRUE(map.empty());
  48   EXPECT_FALSE(map.exists(1));
  49   map.set(1, 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));
  54   map.set(1, 2);
  55   EXPECT_EQ(1, map.size());
  56   EXPECT_FALSE(map.empty());
  57   EXPECT_EQ(2, map.get(1));
  58   EXPECT_TRUE(map.exists(1));
  59
  60   EXPECT_FALSE(map.exists(2));
  61   map.set(2, 1);
  62   EXPECT_TRUE(map.exists(2));
  63   EXPECT_EQ(2, map.size());
  64   EXPECT_FALSE(map.empty());
  65   EXPECT_EQ(1, map.get(2));
  66   map.set(2, 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));
  71   map.erase(2);
  72   EXPECT_EQ(1, map.size());
  73   EXPECT_FALSE(map.empty());
  74   EXPECT_FALSE(map.exists(2));
  75   map.erase(1);
  76   EXPECT_EQ(0, map.size());
  77   EXPECT_TRUE(map.empty());
  78   EXPECT_FALSE(map.exists(1));
  79 }
  80
  81
  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));
  88   }
  89
  90   for (int i = 0; i < 100; i++) {
  91     map.set(i, 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));
  96   }
  97
  98   map.prune(1000000);
  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));
 103   }
 104
 105   for (int i = 0; i < 100; i++) {
 106     map.set(i, 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));
 111   }
 112
 113   map.prune(100);
 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));
 118   }
 119
 120   for (int i = 0; i < 100; i++) {
 121     map.set(i, 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));
 126   }
 127
 128   map.prune(99);
 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));
 133   }
 134   EXPECT_TRUE(map.exists(99));
 135   EXPECT_EQ(99, map.get(99));
 136
 137   map.prune(100);
 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));
 142   }
 143
 144   for (int i = 0; i < 100; i++) {
 145     map.set(i, 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));
 150   }
 151
 152   map.prune(90);
 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));
 157   }
 158   for (int i = 90; i < 100; i++) {
 159     EXPECT_TRUE(map.exists(i));
 160     EXPECT_EQ(i, map.get(i));
 161   }
 162 }
 163
 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));
 170   }
 171
 172   int sum = 0;
 173   auto pruneCb = [&](int&& k, int&& v) {
 174     EXPECT_EQ(k, v);
 175     sum += k;
 176   };
 177
 178   map.setPruneHook(pruneCb);
 179
 180   for (int i = 0; i < 100; i++) {
 181     map.set(i, 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));
 186   }
 187
 188   map.prune(1000000);
 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));
 193   }
 194   EXPECT_EQ((99 * 100) / 2, sum);
 195   sum = 0;
 196
 197   for (int i = 0; i < 100; i++) {
 198     map.set(i, 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));
 203   }
 204
 205   map.prune(100);
 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));
 210   }
 211   EXPECT_EQ((99 * 100) / 2, sum);
 212   sum = 0;
 213
 214   for (int i = 0; i < 100; i++) {
 215     map.set(i, 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));
 220   }
 221
 222   map.prune(99);
 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));
 227   }
 228   EXPECT_TRUE(map.exists(99));
 229   EXPECT_EQ(99, map.get(99));
 230
 231   EXPECT_EQ((98 * 99) / 2, sum);
 232   sum = 0;
 233
 234   map.prune(100);
 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));
 239   }
 240
 241   EXPECT_EQ(99, sum);
 242   sum = 0;
 243
 244   for (int i = 0; i < 100; i++) {
 245     map.set(i, 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));
 250   }
 251
 252   map.prune(90);
 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));
 257   }
 258   for (int i = 90; i < 100; i++) {
 259     EXPECT_TRUE(map.exists(i));
 260     EXPECT_EQ(i, map.get(i));
 261   }
 262   EXPECT_EQ((89 * 90) / 2, sum);
 263   sum = 0;
 264 }
 265
 266 TEST(EvictingCacheMap, SetMaxSize) {
 267   EvictingCacheMap<int, int> map(100, 20);
 268   for (int i = 0; i < 90; i++) {
 269     map.set(i, i);
 270     EXPECT_TRUE(map.exists(i));
 271   }
 272
 273   EXPECT_EQ(90, map.size());
 274   map.setMaxSize(50);
 275   EXPECT_EQ(map.size(), 50);
 276
 277   for (int i = 0; i < 90; i++) {
 278     map.set(i, i);
 279     EXPECT_TRUE(map.exists(i));
 280   }
 281   EXPECT_EQ(40, map.size());
 282   map.setMaxSize(0);
 283   EXPECT_EQ(40, map.size());
 284   map.setMaxSize(10);
 285   EXPECT_EQ(10, map.size());
 286 }
 287
 288 TEST(EvictingCacheMap, SetClearSize) {
 289   EvictingCacheMap<int, int> map(100, 20);
 290   for (int i = 0; i < 90; i++) {
 291     map.set(i, i);
 292     EXPECT_TRUE(map.exists(i));
 293   }
 294
 295   EXPECT_EQ(90, map.size());
 296   map.setClearSize(40);
 297   map.setMaxSize(50);
 298   EXPECT_EQ(map.size(), 50);
 299
 300   for (int i = 0; i < 90; i++) {
 301     map.set(i, i);
 302     EXPECT_TRUE(map.exists(i));
 303   }
 304   EXPECT_EQ(20, map.size());
 305   map.setMaxSize(0);
 306   EXPECT_EQ(20, map.size());
 307   map.setMaxSize(10);
 308   EXPECT_EQ(0, map.size());
 309 }
 310
 311 TEST(EvictingCacheMap, DestructorInvocationTest) {
 312   struct SumInt {
 313     SumInt(int val, int* ref) : val(val), ref(ref) { }
 314     ~SumInt() {
 315       *ref += val;
 316     }
 317     int val;
 318     int* ref;
 319   };
 320
 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));
 326   }
 327
 328   int sum;
 329
 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);
 336   }
 337
 338   sum = 0;
 339   map.prune(1000000);
 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));
 344   }
 345   EXPECT_EQ((99 * 100) / 2, sum);
 346
 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);
 353   }
 354
 355   sum = 0;
 356   map.prune(100);
 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));
 361   }
 362   EXPECT_EQ((99 * 100) / 2, sum);
 363
 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);
 370   }
 371
 372   sum = 0;
 373   map.prune(99);
 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));
 378   }
 379   EXPECT_TRUE(map.exists(99));
 380   EXPECT_EQ(99, map.get(99).val);
 381
 382   EXPECT_EQ((98 * 99) / 2, sum);
 383
 384   sum = 0;
 385   map.prune(100);
 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));
 390   }
 391
 392   EXPECT_EQ(99, sum);
 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);
 399   }
 400
 401   sum = 0;
 402   map.prune(90);
 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));
 407   }
 408   for (int i = 90; i < 100; i++) {
 409     EXPECT_TRUE(map.exists(i));
 410     EXPECT_EQ(i, map.get(i).val);
 411   }
 412   EXPECT_EQ((89 * 90) / 2, sum);
 413   sum = 0;
 414 }
 415
 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));
 422   }
 423
 424   for (int i = 0; i < 100; i++) {
 425     map.set(i, 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));
 430   }
 431
 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));
 436   }
 437   for (int i = 90; i < 100; i++) {
 438     EXPECT_TRUE(map.exists(i));
 439   }
 440 }
 441
 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));
 448   }
 449
 450   for (int i = 0; i < 100; i++) {
 451     map.set(i, 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));
 459     }
 460   }
 461
 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));
 466   }
 467   EXPECT_TRUE(map.exists(99));
 468   for (int i = 10; i < 99; i++) {
 469     EXPECT_FALSE(map.exists(i));
 470   }
 471 }
 472
 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));
 479   }
 480
 481   for (int i = 0; i < 100; i++) {
 482     map.set(i, 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++) {
 488       if (map.exists(j)) {
 489         EXPECT_EQ(j, map.getWithoutPromotion(j));
 490       }
 491     }
 492   }
 493
 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));
 498   }
 499   for (int i = 90; i < 100; i++) {
 500     EXPECT_TRUE(map.exists(i));
 501   }
 502 }
 503
 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));
 510     map.set(i, i * 2);
 511     EXPECT_TRUE(map.exists(i));
 512     EXPECT_EQ(i * 2, map.get(i));
 513   }
 514
 515   std::set<int> seen;
 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);
 520   }
 521   EXPECT_EQ(nItems, seen.size());
 522 }
 523
 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));
 531   }
 532   for (int i = 0; i < nItems * 2; i++) {
 533     if (i % 2 == 0) {
 534       auto it = map.find(i);
 535       EXPECT_FALSE(it == map.end());
 536       EXPECT_EQ(i, it->first);
 537       EXPECT_EQ(i, it->second);
 538     } else {
 539       EXPECT_TRUE( map.find(i) == map.end());
 540     }
 541   }
 542   for (int i = nItems * 2 - 1; i >= 0; i--) {
 543     if (i % 2 == 0) {
 544       auto it = map.find(i);
 545       EXPECT_FALSE(it == map.end());
 546       EXPECT_EQ(i, it->first);
 547       EXPECT_EQ(i, it->second);
 548     } else {
 549       EXPECT_TRUE(map.find(i) == map.end());
 550     }
 551   }
 552   EXPECT_EQ(0, map.begin()->first);
 553 }
 554
 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));
 562   }
 563   for (int i = nItems * 2 - 1; i >= 0; i--) {
 564     if (i % 2 == 0) {
 565       auto it = map.findWithoutPromotion(i);
 566       EXPECT_FALSE(it == map.end());
 567       EXPECT_EQ(i, it->first);
 568       EXPECT_EQ(i, it->second);
 569     } else {
 570       EXPECT_TRUE(map.findWithoutPromotion(i) == map.end());
 571     }
 572   }
 573   EXPECT_EQ((nItems - 1) * 2, map.begin()->first);
 574 }
 575
 576 TEST(EvictingCacheMap, IteratorOrderingTest) {
 577   const int nItems = 1000;
 578   EvictingCacheMap<int, int> map(nItems);
 579   for (int i = 0; i < nItems; i++) {
 580     map.set(i, i);
 581     EXPECT_TRUE(map.exists(i));
 582     EXPECT_EQ(i, map.get(i));
 583   }
 584
 585   int expected = nItems - 1;
 586   for (auto it = map.begin(); it != map.end(); ++it) {
 587     EXPECT_EQ(expected, it->first);
 588     expected--;
 589   }
 590
 591   expected = 0;
 592   for (auto it = map.rbegin(); it != map.rend(); ++it) {
 593     EXPECT_EQ(expected, it->first);
 594     expected++;
 595   }
 596
 597   {
 598     auto it = map.end();
 599     expected = 0;
 600     EXPECT_TRUE(it != map.begin());
 601     do {
 602       --it;
 603       EXPECT_EQ(expected, it->first);
 604       expected++;
 605     } while (it != map.begin());
 606     EXPECT_EQ(nItems, expected);
 607   }
 608
 609   {
 610     auto it = map.rend();
 611     expected = nItems - 1;
 612     do {
 613       --it;
 614       EXPECT_EQ(expected, it->first);
 615       expected--;
 616     } while (it != map.rbegin());
 617     EXPECT_EQ(-1, expected);
 618   }
 619 }