folly/experimental/test/StringKeyedTest.cpp

   1 /*
   2  * Copyright 2016 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 // Copyright 2013-present Facebook. All Rights Reserved.
  17
  18 #include <folly/experimental/StringKeyedMap.h>
  19 #include <folly/experimental/StringKeyedSet.h>
  20 #include <folly/experimental/StringKeyedUnorderedMap.h>
  21 #include <folly/experimental/StringKeyedUnorderedSet.h>
  22
  23 #include <list>
  24 #include <string>
  25
  26 #include <glog/logging.h>
  27 #include <gtest/gtest.h>
  28
  29 #include <folly/Range.h>
  30 #include <folly/portability/GFlags.h>
  31
  32 using folly::StringKeyedMap;
  33 using folly::StringKeyedSetBase;
  34 using folly::StringKeyedUnorderedMap;
  35 using folly::BasicStringKeyedUnorderedSet;
  36 using folly::StringPiece;
  37 using std::string;
  38
  39 static unsigned long long allocated = 0;
  40 static unsigned long long freed = 0;
  41
  42 template <typename Alloc>
  43 struct MemoryLeakCheckerAllocator {
  44   typedef typename Alloc::value_type value_type;
  45   typedef value_type *pointer;
  46   typedef value_type const *const_pointer;
  47   typedef value_type &reference;
  48   typedef value_type const *const_reference;
  49
  50   typedef std::ptrdiff_t difference_type;
  51   typedef std::size_t size_type;
  52
  53   explicit MemoryLeakCheckerAllocator() {
  54   }
  55
  56   explicit MemoryLeakCheckerAllocator(Alloc alloc)
  57       : alloc_(alloc) {
  58   }
  59
  60   template <class UAlloc>
  61   MemoryLeakCheckerAllocator(const MemoryLeakCheckerAllocator<UAlloc>& other)
  62       : alloc_(other.allocator()) {
  63   }
  64
  65   value_type* allocate(size_t n, const void* hint = nullptr) {
  66     auto p = alloc_.allocate(n, hint);
  67     allocated += n * sizeof(value_type);
  68     return p;
  69   }
  70
  71   void deallocate(value_type* p, size_t n) {
  72     alloc_.deallocate(p, n);
  73     freed += n * sizeof(value_type);
  74   }
  75
  76   size_t max_size() const {
  77     return alloc_.max_size();
  78   }
  79
  80   template <class... Args>
  81   void construct(value_type* p, Args&&... args) {
  82     alloc_.construct(p, std::forward<Args>(args)...);
  83   }
  84
  85   void destroy(value_type* p) {
  86     alloc_.destroy(p);
  87   }
  88
  89   template <class U>
  90   struct rebind {
  91     typedef MemoryLeakCheckerAllocator<
  92       typename std::allocator_traits<Alloc>::template rebind_alloc<U>
  93     > other;
  94   };
  95
  96   const Alloc& allocator() const {
  97     return alloc_;
  98   }
  99
 100   bool operator!=(const MemoryLeakCheckerAllocator& other) const {
 101     return alloc_ != other.alloc_;
 102   }
 103
 104   bool operator==(const MemoryLeakCheckerAllocator& other) const {
 105     return alloc_ == other.alloc_;
 106   }
 107
 108 private:
 109   Alloc alloc_;
 110 };
 111
 112 typedef MemoryLeakCheckerAllocator<std::allocator<char>> KeyLeakChecker;
 113 typedef MemoryLeakCheckerAllocator<
 114   std::allocator<std::pair<const StringPiece, int>>> ValueLeakChecker;
 115
 116 typedef StringKeyedUnorderedMap<int, folly::StringPieceHash,
 117                                 std::equal_to<StringPiece>, ValueLeakChecker>
 118   LeakCheckedUnorderedMap;
 119
 120 typedef StringKeyedSetBase<std::less<StringPiece>, ValueLeakChecker> LeakCheckedSet;
 121
 122 typedef StringKeyedMap<int, std::less<StringPiece>,
 123                        ValueLeakChecker> LeakCheckedMap;
 124
 125 using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet<
 126   folly::StringPieceHash,
 127   std::equal_to<folly::StringPiece>,
 128   ValueLeakChecker>;
 129
 130 TEST(StringKeyedUnorderedMapTest, sanity) {
 131   LeakCheckedUnorderedMap map;
 132   EXPECT_TRUE(map.empty());
 133   EXPECT_EQ(map.size(), 0);
 134
 135   {
 136     string s("hello");
 137     StringPiece piece(s, 3);
 138     map.insert({s, 1});
 139     EXPECT_FALSE(map.emplace(s, 2).second);
 140     EXPECT_TRUE(map.emplace(piece, 3).second);
 141   }
 142
 143   EXPECT_EQ(map.size(), 2);
 144
 145   map = map;
 146
 147   EXPECT_EQ(map.find("hello")->second, 1);
 148   EXPECT_EQ(map.find("lo")->second, 3);
 149
 150   map.erase(map.find("hello"));
 151
 152   EXPECT_EQ(map.size(), 1);
 153
 154   for (auto& it : map) {
 155     EXPECT_EQ(it.first, "lo");
 156   }
 157 }
 158
 159 TEST(StringKeyedUnorderedMapTest, constructors) {
 160   LeakCheckedUnorderedMap map {
 161     {"hello", 1},
 162     {"lo", 3}
 163   };
 164
 165   LeakCheckedUnorderedMap map2(map);
 166   EXPECT_EQ(map2.size(), 2);
 167   EXPECT_TRUE(map2 == map);
 168
 169   map2.erase("lo");
 170   for (auto& it : map2) {
 171     EXPECT_EQ(it.first, "hello");
 172   }
 173
 174   map2.clear();
 175
 176   EXPECT_TRUE(map2.empty());
 177
 178   map2.emplace("key1", 1);
 179
 180   LeakCheckedUnorderedMap map3(std::move(map2));
 181
 182   EXPECT_EQ(map3.size(), 1);
 183   EXPECT_EQ(map3["key1"], 1);
 184
 185   EXPECT_EQ(map3["key0"], 0);
 186   EXPECT_EQ(map3.size(), 2);
 187
 188   map3.reserve(1000);
 189
 190   EXPECT_EQ(map3.size(), 2);
 191
 192   LeakCheckedUnorderedMap map4 {
 193     {"key0", 0},
 194     {"key1", 1}
 195   };
 196
 197   EXPECT_EQ(map4.erase("key0"), 1);
 198   EXPECT_EQ(map4.size(), 1);
 199   EXPECT_EQ(map4.find("key0"), map4.end());
 200
 201   map3 = map4;
 202
 203   EXPECT_EQ(map3.size(), 1);
 204   EXPECT_EQ(map4.size(), 1);
 205   EXPECT_EQ(map4.max_size(), map3.max_size());
 206
 207   map4 = std::move(map3);
 208
 209   EXPECT_EQ(map4.size(), 1);
 210   EXPECT_EQ(map4.at("key1"), 1);
 211 }
 212
 213 TEST(StringKeyedSetTest, sanity) {
 214   LeakCheckedSet set;
 215   EXPECT_TRUE(set.empty());
 216   EXPECT_EQ(set.size(), 0);
 217
 218   {
 219     string s("hello");
 220     StringPiece piece(s, 3);
 221     set.insert(s);
 222     EXPECT_FALSE(set.emplace(s).second);
 223     EXPECT_TRUE(set.emplace(piece).second);
 224   }
 225
 226   EXPECT_EQ(set.size(), 2);
 227
 228   set = set;
 229
 230   EXPECT_NE(set.find(StringPiece("hello")), set.end());
 231   EXPECT_NE(set.find("lo"), set.end());
 232
 233   auto it = set.begin();
 234   EXPECT_EQ(*it, "hello");
 235   EXPECT_EQ(*(++it), "lo");
 236   EXPECT_EQ(++it, set.end());
 237
 238   set.erase(set.find("hello"));
 239
 240   EXPECT_EQ(set.size(), 1);
 241
 242   for (auto it : set) {
 243     EXPECT_EQ(it, "lo");
 244   }
 245 }
 246
 247 TEST(StringKeyedSetTest, constructors) {
 248   LeakCheckedSet set {
 249     "hello",
 250     "lo"
 251   };
 252   LeakCheckedSet set2(set);
 253
 254   EXPECT_EQ(set2.size(), 2);
 255
 256   set2.erase("lo");
 257   for (auto it : set2) {
 258     EXPECT_EQ(it, "hello");
 259   }
 260
 261   set2.clear();
 262
 263   EXPECT_TRUE(set2.empty());
 264
 265   set2.emplace("key1");
 266
 267   LeakCheckedSet set3(std::move(set2));
 268
 269   EXPECT_EQ(set3.size(), 1);
 270   EXPECT_EQ(set3.insert("key1").second, false);
 271
 272   EXPECT_EQ(set3.emplace("key0").second, true);
 273   EXPECT_EQ(set3.size(), 2);
 274
 275   EXPECT_EQ(set3.size(), 2);
 276
 277   LeakCheckedSet set4 {
 278     "key0",
 279     "key1"
 280   };
 281
 282   EXPECT_EQ(set4.erase("key0"), 1);
 283   EXPECT_EQ(set4.size(), 1);
 284   EXPECT_EQ(set4.find("key0"), set4.end());
 285
 286   set3 = set4;
 287
 288   EXPECT_EQ(set3.size(), 1);
 289   EXPECT_EQ(set4.size(), 1);
 290   EXPECT_EQ(set4.max_size(), set3.max_size());
 291
 292   set4 = std::move(set3);
 293
 294   EXPECT_EQ(set4.size(), 1);
 295   EXPECT_NE(set4.find("key1"), set4.end());
 296 }
 297
 298 TEST(StringKeyedUnorderedSetTest, sanity) {
 299   LeakCheckedUnorderedSet set;
 300   EXPECT_TRUE(set.empty());
 301   EXPECT_EQ(set.size(), 0);
 302
 303   {
 304     string s("hello");
 305     StringPiece piece(s, 3);
 306     set.insert(s);
 307     EXPECT_FALSE(set.emplace(s).second);
 308     EXPECT_TRUE(set.emplace(piece).second);
 309   }
 310
 311   EXPECT_EQ(set.size(), 2);
 312
 313   set = set;
 314
 315   EXPECT_NE(set.find("hello"), set.end());
 316   EXPECT_NE(set.find("lo"), set.end());
 317
 318   set.erase(set.find("hello"));
 319
 320   EXPECT_EQ(set.size(), 1);
 321
 322   for (auto it : set) {
 323     EXPECT_EQ(it, "lo");
 324   }
 325 }
 326
 327 TEST(StringKeyedUnorderedSetTest, constructors) {
 328   LeakCheckedUnorderedSet s1;
 329   EXPECT_TRUE(s1.empty());
 330
 331   LeakCheckedUnorderedSet s2(10);
 332   EXPECT_TRUE(s2.empty());
 333   EXPECT_GE(s2.bucket_count(), 10);
 334
 335   std::list<StringPiece> lst { "abc", "def" };
 336   LeakCheckedUnorderedSet s3(lst.begin(), lst.end());
 337   EXPECT_EQ(s3.size(), 2);
 338   EXPECT_NE(s3.find("abc"), s3.end());
 339   EXPECT_NE(s3.find("def"), s3.end());
 340   EXPECT_TRUE(s3 == (LeakCheckedUnorderedSet{"abc", "def"}));
 341
 342   LeakCheckedUnorderedSet s4(const_cast<LeakCheckedUnorderedSet&>(s3));
 343   EXPECT_TRUE(s4 == s3);
 344
 345   LeakCheckedUnorderedSet s5(const_cast<LeakCheckedUnorderedSet&>(s3),
 346                              ValueLeakChecker());
 347   EXPECT_TRUE(s5 == s3);
 348
 349   LeakCheckedUnorderedSet s6(std::move(s3));
 350   EXPECT_TRUE(s3.empty());
 351   EXPECT_TRUE(s6 == s5);
 352
 353   LeakCheckedUnorderedSet s7(std::move(s6), s6.get_allocator());
 354   EXPECT_TRUE(s6.empty());
 355   EXPECT_TRUE(s7 == s5);
 356
 357   LeakCheckedUnorderedSet s8 {
 358     "hello",
 359     "lo"
 360   };
 361   EXPECT_EQ(s8.size(), 2);
 362   EXPECT_NE(s8.find("hello"), s8.end());
 363   EXPECT_NE(s8.find("lo"), s8.end());
 364
 365   LeakCheckedUnorderedSet s9({
 366     "hello",
 367     "lo"
 368       }, 10);
 369   EXPECT_EQ(s9.size(), 2);
 370   EXPECT_NE(s9.find("hello"), s9.end());
 371   EXPECT_NE(s9.find("lo"), s9.end());
 372
 373   LeakCheckedUnorderedSet set2(s8);
 374   EXPECT_EQ(set2.size(), 2);
 375
 376   set2.erase("lo");
 377   for (auto it : set2) {
 378     EXPECT_EQ(it, "hello");
 379   }
 380
 381   set2.clear();
 382
 383   EXPECT_TRUE(set2.empty());
 384
 385   set2.emplace("key1");
 386
 387   LeakCheckedUnorderedSet set3(std::move(set2));
 388
 389   EXPECT_EQ(set3.size(), 1);
 390   EXPECT_EQ(set3.insert("key1").second, false);
 391
 392   EXPECT_EQ(set3.emplace("key0").second, true);
 393   EXPECT_EQ(set3.size(), 2);
 394
 395   set3.reserve(1000);
 396
 397   EXPECT_EQ(set3.size(), 2);
 398
 399   LeakCheckedUnorderedSet set4 {
 400     "key0",
 401     "key1"
 402   };
 403
 404   EXPECT_EQ(set4.erase("key0"), 1);
 405   EXPECT_EQ(set4.size(), 1);
 406   EXPECT_EQ(set4.find("key0"), set4.end());
 407
 408   set3 = set4;
 409
 410   EXPECT_EQ(set3.size(), 1);
 411   EXPECT_EQ(set4.size(), 1);
 412   EXPECT_EQ(set4.max_size(), set3.max_size());
 413
 414   set4 = std::move(set3);
 415
 416   EXPECT_EQ(set4.size(), 1);
 417   EXPECT_NE(set4.find("key1"), set4.end());
 418 }
 419
 420 TEST(StringKeyedMapTest, sanity) {
 421   LeakCheckedMap map;
 422   EXPECT_TRUE(map.empty());
 423   EXPECT_EQ(map.size(), 0);
 424
 425   {
 426     string s("hello");
 427     StringPiece piece(s, 3);
 428     map.insert({s, 1});
 429     EXPECT_FALSE(map.emplace(s, 2).second);
 430     EXPECT_TRUE(map.emplace(piece, 3).second);
 431   }
 432
 433   EXPECT_EQ(map.size(), 2);
 434
 435   map = map;
 436
 437   EXPECT_EQ(map.find("hello")->second, 1);
 438   EXPECT_EQ(map.find("lo")->second, 3);
 439
 440   auto it = map.begin();
 441   EXPECT_EQ(it->first, "hello");
 442   EXPECT_EQ((++it)->first, "lo");
 443   EXPECT_EQ(++it, map.end());
 444
 445   map.erase(map.find("hello"));
 446
 447   EXPECT_EQ(map.size(), 1);
 448
 449   for (auto& it : map) {
 450     EXPECT_EQ(it.first, "lo");
 451   }
 452 }
 453
 454 TEST(StringKeyedMapTest, constructors) {
 455   LeakCheckedMap map {
 456     {"hello", 1},
 457     {"lo", 3}
 458   };
 459   LeakCheckedMap map2(map);
 460
 461   EXPECT_EQ(map2.size(), 2);
 462
 463   map2.erase("lo");
 464   for (auto& it : map2) {
 465     EXPECT_EQ(it.first, "hello");
 466   }
 467
 468   map2.clear();
 469
 470   EXPECT_TRUE(map2.empty());
 471
 472   map2.emplace("key1", 1);
 473
 474   LeakCheckedMap map3(std::move(map2));
 475
 476   EXPECT_EQ(map3.size(), 1);
 477   EXPECT_EQ(map3["key1"], 1);
 478
 479   EXPECT_EQ(map3["key0"], 0);
 480   EXPECT_EQ(map3.size(), 2);
 481
 482   LeakCheckedMap map4 {
 483     {"key0", 0},
 484     {"key1", 1}
 485   };
 486
 487   EXPECT_EQ(map4.erase("key0"), 1);
 488   EXPECT_EQ(map4.size(), 1);
 489   EXPECT_EQ(map4.find("key0"), map4.end());
 490
 491   map3 = map4;
 492
 493   EXPECT_EQ(map3.size(), 1);
 494   EXPECT_EQ(map4.size(), 1);
 495   EXPECT_EQ(map4.max_size(), map3.max_size());
 496
 497   map4 = std::move(map3);
 498
 499   EXPECT_EQ(map4.size(), 1);
 500   EXPECT_EQ(map4.at("key1"), 1);
 501 }
 502
 503 int main(int argc, char **argv) {
 504   FLAGS_logtostderr = true;
 505   google::InitGoogleLogging(argv[0]);
 506   testing::InitGoogleTest(&argc, argv);
 507   gflags::ParseCommandLineFlags(&argc, &argv, true);
 508
 509   return RUN_ALL_TESTS();
 510 }
 511
 512 // This MUST be the LAST test.
 513 TEST(StringKeyed, memory_balance) {
 514   auto balance = allocated < freed
 515     ? freed - allocated
 516     : allocated - freed;
 517
 518   LOG(INFO) << "allocated: " << allocated
 519     << " freed: " << freed
 520     << " balance: " << balance
 521     << (
 522       allocated < freed
 523         ? " negative (huh?)"
 524         : freed < allocated
 525           ? " positive (leak)" : ""
 526     );
 527
 528   EXPECT_EQ(allocated, freed);
 529 }