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   LeakCheckedUnorderedSet s7(std::move(s6), s6.get_allocator());
 359   EXPECT_TRUE(s6.empty());
 360   EXPECT_TRUE(s7 == s5);
 361
 362   LeakCheckedUnorderedSet s8 {
 363     "hello",
 364     "lo"
 365   };
 366   EXPECT_EQ(s8.size(), 2);
 367   EXPECT_NE(s8.find("hello"), s8.end());
 368   EXPECT_NE(s8.find("lo"), s8.end());
 369
 370   LeakCheckedUnorderedSet s9({
 371     "hello",
 372     "lo"
 373       }, 10);
 374   EXPECT_EQ(s9.size(), 2);
 375   EXPECT_NE(s9.find("hello"), s9.end());
 376   EXPECT_NE(s9.find("lo"), s9.end());
 377
 378   LeakCheckedUnorderedSet set2(s8);
 379   EXPECT_EQ(set2.size(), 2);
 380
 381   set2.erase("lo");
 382   for (auto entry : set2) {
 383     EXPECT_EQ(entry, "hello");
 384   }
 385
 386   set2.clear();
 387
 388   EXPECT_TRUE(set2.empty());
 389
 390   set2.emplace("key1");
 391
 392   LeakCheckedUnorderedSet set3(std::move(set2));
 393
 394   EXPECT_EQ(set3.size(), 1);
 395   EXPECT_EQ(set3.insert("key1").second, false);
 396
 397   EXPECT_EQ(set3.emplace("key0").second, true);
 398   EXPECT_EQ(set3.size(), 2);
 399
 400   set3.reserve(1000);
 401
 402   EXPECT_EQ(set3.size(), 2);
 403
 404   LeakCheckedUnorderedSet set4 {
 405     "key0",
 406     "key1"
 407   };
 408
 409   EXPECT_EQ(set4.erase("key0"), 1);
 410   EXPECT_EQ(set4.size(), 1);
 411   EXPECT_EQ(set4.find("key0"), set4.end());
 412
 413   set3 = set4;
 414
 415   EXPECT_EQ(set3.size(), 1);
 416   EXPECT_EQ(set4.size(), 1);
 417   EXPECT_EQ(set4.max_size(), set3.max_size());
 418
 419   set4 = std::move(set3);
 420
 421   EXPECT_EQ(set4.size(), 1);
 422   EXPECT_NE(set4.find("key1"), set4.end());
 423 }
 424
 425 TEST(StringKeyedMapTest, sanity) {
 426   LeakCheckedMap map;
 427   EXPECT_TRUE(map.empty());
 428   EXPECT_EQ(map.size(), 0);
 429
 430   {
 431     string s("hello");
 432     StringPiece piece(s, 3);
 433     map.insert({s, 1});
 434     EXPECT_FALSE(map.emplace(s, 2).second);
 435     EXPECT_TRUE(map.emplace(piece, 3).second);
 436   }
 437
 438   EXPECT_EQ(map.size(), 2);
 439
 440   map = map;
 441
 442   EXPECT_EQ(map.find("hello")->second, 1);
 443   EXPECT_EQ(map.find("lo")->second, 3);
 444
 445   auto it = map.begin();
 446   EXPECT_EQ(it->first, "hello");
 447   EXPECT_EQ((++it)->first, "lo");
 448   EXPECT_EQ(++it, map.end());
 449
 450   map.erase(map.find("hello"));
 451
 452   EXPECT_EQ(map.size(), 1);
 453
 454   for (auto& entry : map) {
 455     EXPECT_EQ(entry.first, "lo");
 456   }
 457 }
 458
 459 TEST(StringKeyedMapTest, constructors) {
 460   LeakCheckedMap map {
 461     {"hello", 1},
 462     {"lo", 3}
 463   };
 464   LeakCheckedMap map2(map);
 465
 466   EXPECT_EQ(map2.size(), 2);
 467
 468   map2.erase("lo");
 469   for (auto& entry : map2) {
 470     EXPECT_EQ(entry.first, "hello");
 471   }
 472
 473   map2.clear();
 474
 475   EXPECT_TRUE(map2.empty());
 476
 477   map2.emplace("key1", 1);
 478
 479   LeakCheckedMap map3(std::move(map2));
 480
 481   EXPECT_EQ(map3.size(), 1);
 482   EXPECT_EQ(map3["key1"], 1);
 483
 484   EXPECT_EQ(map3["key0"], 0);
 485   EXPECT_EQ(map3.size(), 2);
 486
 487   LeakCheckedMap map4 {
 488     {"key0", 0},
 489     {"key1", 1}
 490   };
 491
 492   EXPECT_EQ(map4.erase("key0"), 1);
 493   EXPECT_EQ(map4.size(), 1);
 494   EXPECT_EQ(map4.find("key0"), map4.end());
 495
 496   map3 = map4;
 497
 498   EXPECT_EQ(map3.size(), 1);
 499   EXPECT_EQ(map4.size(), 1);
 500   EXPECT_EQ(map4.max_size(), map3.max_size());
 501
 502   map4 = std::move(map3);
 503
 504   EXPECT_EQ(map4.size(), 1);
 505   EXPECT_EQ(map4.at("key1"), 1);
 506 }
 507
 508 int main(int argc, char **argv) {
 509   FLAGS_logtostderr = true;
 510   google::InitGoogleLogging(argv[0]);
 511   testing::InitGoogleTest(&argc, argv);
 512   gflags::ParseCommandLineFlags(&argc, &argv, true);
 513
 514   return RUN_ALL_TESTS();
 515 }
 516
 517 // This MUST be the LAST test.
 518 TEST(StringKeyed, memory_balance) {
 519   auto balance = allocated < freed
 520     ? freed - allocated
 521     : allocated - freed;
 522
 523   LOG(INFO) << "allocated: " << allocated
 524     << " freed: " << freed
 525     << " balance: " << balance
 526     << (
 527       allocated < freed
 528         ? " negative (huh?)"
 529         : freed < allocated
 530           ? " positive (leak)" : ""
 531     );
 532
 533   EXPECT_EQ(allocated, freed);
 534 }