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