proxygen
StringKeyedTest.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2015-present 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::BasicStringKeyedUnorderedSet;
34 using folly::StringKeyedMap;
35 using folly::StringKeyedSetBase;
36 using folly::StringKeyedUnorderedMap;
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  explicit MemoryLeakCheckerAllocator(Alloc alloc) : alloc_(alloc) {}
57 
58  template <class UAlloc>
59  MemoryLeakCheckerAllocator(const MemoryLeakCheckerAllocator<UAlloc>& other)
60  : alloc_(other.allocator()) {}
61 
62  value_type* allocate(size_t n, const void* hint = nullptr) {
63  auto p = alloc_.allocate(n, hint);
64  allocated += n * sizeof(value_type);
65  return p;
66  }
67 
68  void deallocate(value_type* p, size_t n) {
69  alloc_.deallocate(p, n);
70  freed += n * sizeof(value_type);
71  }
72 
73  size_t max_size() const {
74  return alloc_.max_size();
75  }
76 
77  template <class... Args>
78  void construct(value_type* p, Args&&... args) {
79  alloc_.construct(p, std::forward<Args>(args)...);
80  }
81 
82  void destroy(value_type* p) {
83  alloc_.destroy(p);
84  }
85 
86  template <class U>
87  struct rebind {
88  typedef MemoryLeakCheckerAllocator<
89  typename std::allocator_traits<Alloc>::template rebind_alloc<U>>
90  other;
91  };
92 
93  const Alloc& allocator() const {
94  return alloc_;
95  }
96 
97  bool operator!=(const MemoryLeakCheckerAllocator& other) const {
98  return alloc_ != other.alloc_;
99  }
100 
101  bool operator==(const MemoryLeakCheckerAllocator& other) const {
102  return alloc_ == other.alloc_;
103  }
104 
105  private:
106  Alloc alloc_;
107 };
108 
109 using KeyValuePairLeakChecker = MemoryLeakCheckerAllocator<
110  std::allocator<std::pair<const StringPiece, int>>>;
111 using ValueLeakChecker =
112  MemoryLeakCheckerAllocator<std::allocator<StringPiece>>;
113 
114 using LeakCheckedUnorderedMap = StringKeyedUnorderedMap<
115  int,
116  folly::transparent<folly::hasher<StringPiece>>,
117  folly::transparent<std::equal_to<StringPiece>>,
118  MemoryLeakCheckerAllocator<
119  std::allocator<std::pair<const std::string, int>>>>;
120 
121 typedef StringKeyedSetBase<std::less<StringPiece>, ValueLeakChecker>
122  LeakCheckedSet;
123 
124 typedef StringKeyedMap<int, std::less<StringPiece>, KeyValuePairLeakChecker>
125  LeakCheckedMap;
126 
127 using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet<
128  folly::transparent<folly::hasher<StringPiece>>,
129  folly::transparent<std::equal_to<folly::StringPiece>>,
130  MemoryLeakCheckerAllocator<std::allocator<std::string>>>;
131 
132 TEST(StringKeyedUnorderedMapTest, sanity) {
133  LeakCheckedUnorderedMap map;
134  EXPECT_TRUE(map.empty());
135  EXPECT_EQ(map.size(), 0);
136 
137  {
138  string s("hello");
139  StringPiece piece(s, 3);
140  map.insert({s, 1});
141  EXPECT_FALSE(map.emplace(s, 2).second);
142  EXPECT_TRUE(map.emplace(piece, 3).second);
143  }
144 
145  EXPECT_EQ(map.size(), 2);
146 
147  map = static_cast<decltype(map)&>(map); // suppress self-assign warning
148 
149  EXPECT_EQ(map.find("hello")->second, 1);
150  EXPECT_EQ(map.find("lo")->second, 3);
151 
152  map.erase(map.find("hello"));
153 
154  EXPECT_EQ(map.size(), 1);
155 
156  for (auto& it : map) {
157  EXPECT_EQ(it.first, "lo");
158  }
159 }
160 
161 TEST(StringKeyedUnorderedMapTest, constructors) {
162  LeakCheckedUnorderedMap map{
163  {"hello", 1},
164  {"lo", 3},
165  };
166 
167  LeakCheckedUnorderedMap map2(map);
168  EXPECT_EQ(map2.size(), 2);
169  EXPECT_TRUE(map2 == map);
170 
171  map2.erase("lo");
172  for (auto& it : map2) {
173  EXPECT_EQ(it.first, "hello");
174  }
175 
176  map2.clear();
177 
178  EXPECT_TRUE(map2.empty());
179 
180  map2.emplace("key1", 1);
181 
182  LeakCheckedUnorderedMap map3(std::move(map2));
183 
184  EXPECT_EQ(map3.size(), 1);
185  EXPECT_EQ(map3["key1"], 1);
186 
187  EXPECT_EQ(map3["key0"], 0);
188  EXPECT_EQ(map3.size(), 2);
189 
190  map3.reserve(1000);
191 
192  EXPECT_EQ(map3.size(), 2);
193 
194  LeakCheckedUnorderedMap map4{
195  {"key0", 0},
196  {"key1", 1},
197  };
198 
199  EXPECT_EQ(map4.erase("key0"), 1);
200  EXPECT_EQ(map4.size(), 1);
201  EXPECT_EQ(map4.find("key0"), map4.end());
202 
203  map3 = map4;
204 
205  EXPECT_EQ(map3.size(), 1);
206  EXPECT_EQ(map4.size(), 1);
207  EXPECT_EQ(map4.max_size(), map3.max_size());
208 
209  map4 = std::move(map3);
210 
211  EXPECT_EQ(map4.size(), 1);
212  EXPECT_EQ(map4.at("key1"), 1);
213 }
214 
215 TEST(StringKeyedSetTest, sanity) {
216  LeakCheckedSet set;
217  EXPECT_TRUE(set.empty());
218  EXPECT_EQ(set.size(), 0);
219 
220  {
221  string s("hello");
222  StringPiece piece(s, 3);
223  set.insert(s);
224  EXPECT_FALSE(set.emplace(s).second);
225  EXPECT_TRUE(set.emplace(piece).second);
226  }
227 
228  EXPECT_EQ(set.size(), 2);
229 
230  set = static_cast<decltype(set)&>(set); // suppress self-assign warning
231 
232  EXPECT_NE(set.find(StringPiece("hello")), set.end());
233  EXPECT_NE(set.find("lo"), set.end());
234 
235  auto it = set.begin();
236  EXPECT_EQ(*it, "hello");
237  EXPECT_EQ(*(++it), "lo");
238  EXPECT_EQ(++it, set.end());
239 
240  set.erase(set.find("hello"));
241 
242  EXPECT_EQ(set.size(), 1);
243 
244  for (auto entry : set) {
245  EXPECT_EQ(entry, "lo");
246  }
247 }
248 
249 TEST(StringKeyedSetTest, constructors) {
250  LeakCheckedSet set{
251  "hello",
252  "lo",
253  };
254  LeakCheckedSet set2(set);
255 
256  EXPECT_EQ(set2.size(), 2);
257 
258  set2.erase("lo");
259  for (auto it : set2) {
260  EXPECT_EQ(it, "hello");
261  }
262 
263  set2.clear();
264 
265  EXPECT_TRUE(set2.empty());
266 
267  set2.emplace("key1");
268 
269  LeakCheckedSet set3(std::move(set2));
270 
271  EXPECT_EQ(set3.size(), 1);
272  EXPECT_EQ(set3.insert("key1").second, false);
273 
274  EXPECT_EQ(set3.emplace("key0").second, true);
275  EXPECT_EQ(set3.size(), 2);
276 
277  EXPECT_EQ(set3.size(), 2);
278 
279  LeakCheckedSet set4{
280  "key0",
281  "key1",
282  };
283 
284  EXPECT_EQ(set4.erase("key0"), 1);
285  EXPECT_EQ(set4.size(), 1);
286  EXPECT_EQ(set4.find("key0"), set4.end());
287 
288  set3 = set4;
289 
290  EXPECT_EQ(set3.size(), 1);
291  EXPECT_EQ(set4.size(), 1);
292  EXPECT_EQ(set4.max_size(), set3.max_size());
293 
294  set4 = std::move(set3);
295 
296  EXPECT_EQ(set4.size(), 1);
297  EXPECT_NE(set4.find("key1"), set4.end());
298 }
299 
300 TEST(StringKeyedUnorderedSetTest, sanity) {
301  LeakCheckedUnorderedSet set;
302  EXPECT_TRUE(set.empty());
303  EXPECT_EQ(set.size(), 0);
304 
305  {
306  string s("hello");
307  StringPiece piece(s, 3);
308  set.insert(s);
309  EXPECT_FALSE(set.emplace(s).second);
310  EXPECT_TRUE(set.emplace(piece).second);
311  }
312 
313  EXPECT_EQ(set.size(), 2);
314 
315  set = static_cast<decltype(set)&>(set); // suppress self-assign warning
316 
317  EXPECT_NE(set.find("hello"), set.end());
318  EXPECT_NE(set.find("lo"), set.end());
319 
320  set.erase(set.find("hello"));
321 
322  EXPECT_EQ(set.size(), 1);
323 
324  for (auto entry : set) {
325  EXPECT_EQ(entry, "lo");
326  }
327 }
328 
329 TEST(StringKeyedUnorderedSetTest, constructors) {
330  LeakCheckedUnorderedSet s1;
331  EXPECT_TRUE(s1.empty());
332 
333  LeakCheckedUnorderedSet s2(10);
334  EXPECT_TRUE(s2.empty());
335  EXPECT_GE(s2.bucket_count(), 10);
336 
337  std::list<StringPiece> lst{"abc", "def"};
338  LeakCheckedUnorderedSet s3(lst.begin(), lst.end());
339  EXPECT_EQ(s3.size(), 2);
340  EXPECT_NE(s3.find("abc"), s3.end());
341  EXPECT_NE(s3.find("def"), s3.end());
342  EXPECT_TRUE(s3 == (LeakCheckedUnorderedSet{"abc", "def"}));
343 
344  LeakCheckedUnorderedSet s4(const_cast<LeakCheckedUnorderedSet&>(s3));
345  EXPECT_TRUE(s4 == s3);
346 
347  LeakCheckedUnorderedSet s5(
348  const_cast<LeakCheckedUnorderedSet&>(s3), ValueLeakChecker());
349  EXPECT_TRUE(s5 == s3);
350 
351  LeakCheckedUnorderedSet s6(std::move(s3));
352  EXPECT_TRUE(s3.empty());
353  EXPECT_TRUE(s6 == s5);
354 
355  auto s6_allocator = s6.get_allocator();
356  LeakCheckedUnorderedSet s7(std::move(s6), s6_allocator);
357  EXPECT_TRUE(s6.empty());
358  EXPECT_TRUE(s7 == s5);
359 
360  LeakCheckedUnorderedSet s8{
361  "hello",
362  "lo",
363  };
364  EXPECT_EQ(s8.size(), 2);
365  EXPECT_NE(s8.find("hello"), s8.end());
366  EXPECT_NE(s8.find("lo"), s8.end());
367 
368  LeakCheckedUnorderedSet s9(
369  {
370  "hello",
371  "lo",
372  },
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 = static_cast<decltype(map)&>(map); // suppress self-assign warning
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 ? freed - allocated : allocated - freed;
520 
521  LOG(INFO) << "allocated: " << allocated << " freed: " << freed
522  << " balance: " << balance
523  << (allocated < freed
524  ? " negative (huh?)"
525  : freed < allocated ? " positive (leak)" : "");
526 
527  EXPECT_EQ(allocated, freed);
528 }
MemoryLeakCheckerAllocator::destroy
void destroy(value_type *p)
Definition: StringKeyedTest.cpp:82
folly::StringKeyedUnorderedMap::insert
std::pair< typename Super::iterator, bool > insert(std::pair< StringPiece, Mapped > const &p)
Definition: StringKeyedUnorderedMap.h:44
TEST
TEST(StringKeyedUnorderedMapTest, sanity)
Definition: StringKeyedTest.cpp:132
folly::StringKeyedSetBase::insert
std::pair< iterator, bool > insert(value_type val)
Definition: StringKeyedSet.h:146
freed
static unsigned long long freed
Definition: StringKeyedTest.cpp:41
MemoryLeakCheckerAllocator::operator!=
bool operator!=(const MemoryLeakCheckerAllocator &other) const
Definition: StringKeyedTest.cpp:97
MemoryLeakCheckerAllocator::MemoryLeakCheckerAllocator
MemoryLeakCheckerAllocator(Alloc alloc)
Definition: StringKeyedTest.cpp:56
Alloc::allocate
pointer allocate(size_type n)
Definition: StlVectorTest.cpp:677
RUN_ALL_TESTS
int RUN_ALL_TESTS() GTEST_MUST_USE_RESULT_
Definition: gtest.h:2232
folly::StringKeyedSetBase::erase
iterator erase(const_iterator position)
Definition: StringKeyedSet.h:154
EXPECT_EQ
#define EXPECT_EQ(val1, val2)
Definition: gtest.h:1922
folly::gen::move
constexpr detail::Map< Move > move
Definition: Base-inl.h:2567
LeakCheckedMap
StringKeyedMap< int, std::less< StringPiece >, KeyValuePairLeakChecker > LeakCheckedMap
Definition: StringKeyedTest.cpp:125
Alloc::value_type
std::allocator< T >::value_type value_type
Definition: StlVectorTest.cpp:655
LeakCheckedUnorderedSet
BasicStringKeyedUnorderedSet< folly::transparent< folly::hasher< StringPiece >>, folly::transparent< std::equal_to< folly::StringPiece >>, MemoryLeakCheckerAllocator< std::allocator< std::string >>> LeakCheckedUnorderedSet
Definition: StringKeyedTest.cpp:130
testing::Args
internal::ArgsMatcher< InnerMatcher > Args(const InnerMatcher &matcher)
Definition: gmock-generated-matchers.h:481
Alloc::construct
void construct(U *p, Args &&...args)
Definition: StlVectorTest.cpp:716
main
int main(int argc, char **argv)
Definition: StringKeyedTest.cpp:508
EXPECT_GE
#define EXPECT_GE(val1, val2)
Definition: gtest.h:1932
folly::StringKeyedMap::emplace
std::pair< iterator, bool > emplace(StringPiece key, Args &&...args)
Definition: StringKeyedMap.h:153
ValueLeakChecker
MemoryLeakCheckerAllocator< std::allocator< StringPiece >> ValueLeakChecker
Definition: StringKeyedTest.cpp:112
MemoryLeakCheckerAllocator::operator==
bool operator==(const MemoryLeakCheckerAllocator &other) const
Definition: StringKeyedTest.cpp:101
argv
char ** argv
Definition: SmallLocksBenchmark.cpp:430
folly::size
constexpr auto size(C const &c) -> decltype(c.size())
Definition: Access.h:45
MemoryLeakCheckerAllocator::const_reference
value_type const * const_reference
Definition: StringKeyedTest.cpp:49
folly::empty
constexpr auto empty(C const &c) -> decltype(c.empty())
Definition: Access.h:55
MemoryLeakCheckerAllocator::MemoryLeakCheckerAllocator
MemoryLeakCheckerAllocator(const MemoryLeakCheckerAllocator< UAlloc > &other)
Definition: StringKeyedTest.cpp:59
MemoryLeakCheckerAllocator::construct
void construct(value_type *p, Args &&...args)
Definition: StringKeyedTest.cpp:78
folly::StringKeyedSetBase::emplace
std::pair< iterator, bool > emplace(Args &&...args)
Definition: StringKeyedSet.h:137
folly::test::end
auto end(TestAdlIterable &instance)
Definition: ForeachTest.cpp:62
MemoryLeakCheckerAllocator::allocator
const Alloc & allocator() const
Definition: StringKeyedTest.cpp:93
map
static Map map(mapCap)
map
Definition: Traits.h:594
MemoryLeakCheckerAllocator::rebind::other
MemoryLeakCheckerAllocator< typename std::allocator_traits< Alloc >::template rebind_alloc< U > > other
Definition: StringKeyedTest.cpp:90
Alloc::deallocate
void deallocate(pointer p, size_type n)
Definition: StlVectorTest.cpp:689
folly::StringKeyedMap::insert
std::pair< iterator, bool > insert(value_type val)
Definition: StringKeyedMap.h:162
folly::BasicStringKeyedUnorderedSet
F14NodeSet< std::string, Hash, Eq, Alloc > BasicStringKeyedUnorderedSet
Definition: StringKeyedUnorderedSet.h:27
EXPECT_TRUE
#define EXPECT_TRUE(condition)
Definition: gtest.h:1859
MemoryLeakCheckerAllocator::allocate
value_type * allocate(size_t n, const void *hint=nullptr)
Definition: StringKeyedTest.cpp:62
string
const char * string
Definition: Conv.cpp:212
Alloc::destroy
void destroy(U *p)
Definition: StlVectorTest.cpp:723
MemoryLeakCheckerAllocator::value_type
Alloc::value_type value_type
Definition: StringKeyedTest.cpp:45
EXPECT_NE
#define EXPECT_NE(val1, val2)
Definition: gtest.h:1926
s
static set< string > s
Definition: StringKeyedBenchmark.cpp:48
allocated
static unsigned long long allocated
Definition: StringKeyedTest.cpp:40
testing::InitGoogleTest
GTEST_API_ void InitGoogleTest(int *argc, char **argv)
Definition: gtest.cc:5370
MemoryLeakCheckerAllocator::deallocate
void deallocate(value_type *p, size_t n)
Definition: StringKeyedTest.cpp:68
EXPECT_FALSE
#define EXPECT_FALSE(condition)
Definition: gtest.h:1862
folly::StringPiece
Range< const char * > StringPiece
Definition: ScopedEventBaseThread.h:29
folly::StringKeyedMap::erase
iterator erase(const_iterator position)
Definition: StringKeyedMap.h:171
set
Definition: Traits.h:592
LeakCheckedSet
StringKeyedSetBase< std::less< StringPiece >, ValueLeakChecker > LeakCheckedSet
Definition: StringKeyedTest.cpp:122
MemoryLeakCheckerAllocator::const_pointer
value_type const * const_pointer
Definition: StringKeyedTest.cpp:47
folly::gen::first
constexpr detail::First first
Definition: Base-inl.h:2553