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