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