2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 // Copyright 2013-present Facebook. All Rights Reserved.
18 #include <folly/experimental/StringKeyedMap.h>
19 #include <folly/experimental/StringKeyedSet.h>
20 #include <folly/experimental/StringKeyedUnorderedMap.h>
21 #include <folly/experimental/StringKeyedUnorderedSet.h>
26 #include <glog/logging.h>
28 #include <folly/Hash.h>
29 #include <folly/Range.h>
30 #include <folly/portability/GFlags.h>
31 #include <folly/portability/GTest.h>
33 using folly::StringKeyedMap;
34 using folly::StringKeyedSetBase;
35 using folly::StringKeyedUnorderedMap;
36 using folly::BasicStringKeyedUnorderedSet;
37 using folly::StringPiece;
40 static unsigned long long allocated = 0;
41 static unsigned long long freed = 0;
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;
51 typedef std::ptrdiff_t difference_type;
52 typedef std::size_t size_type;
54 explicit MemoryLeakCheckerAllocator() {
57 explicit MemoryLeakCheckerAllocator(Alloc alloc)
61 template <class UAlloc>
62 MemoryLeakCheckerAllocator(const MemoryLeakCheckerAllocator<UAlloc>& other)
63 : alloc_(other.allocator()) {
66 value_type* allocate(size_t n, const void* hint = nullptr) {
67 auto p = alloc_.allocate(n, hint);
68 allocated += n * sizeof(value_type);
72 void deallocate(value_type* p, size_t n) {
73 alloc_.deallocate(p, n);
74 freed += n * sizeof(value_type);
77 size_t max_size() const {
78 return alloc_.max_size();
81 template <class... Args>
82 void construct(value_type* p, Args&&... args) {
83 alloc_.construct(p, std::forward<Args>(args)...);
86 void destroy(value_type* p) {
92 typedef MemoryLeakCheckerAllocator<
93 typename std::allocator_traits<Alloc>::template rebind_alloc<U>
97 const Alloc& allocator() const {
101 bool operator!=(const MemoryLeakCheckerAllocator& other) const {
102 return alloc_ != other.alloc_;
105 bool operator==(const MemoryLeakCheckerAllocator& other) const {
106 return alloc_ == other.alloc_;
113 using KeyValuePairLeakChecker = MemoryLeakCheckerAllocator<
114 std::allocator<std::pair<const StringPiece, int>>>;
115 using ValueLeakChecker =
116 MemoryLeakCheckerAllocator<std::allocator<StringPiece>>;
118 typedef StringKeyedUnorderedMap<
121 std::equal_to<StringPiece>,
122 KeyValuePairLeakChecker>
123 LeakCheckedUnorderedMap;
125 typedef StringKeyedSetBase<std::less<StringPiece>, ValueLeakChecker>
128 typedef StringKeyedMap<int, std::less<StringPiece>, KeyValuePairLeakChecker>
131 using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet<
133 std::equal_to<folly::StringPiece>,
136 TEST(StringKeyedUnorderedMapTest, sanity) {
137 LeakCheckedUnorderedMap map;
138 EXPECT_TRUE(map.empty());
139 EXPECT_EQ(map.size(), 0);
143 StringPiece piece(s, 3);
145 EXPECT_FALSE(map.emplace(s, 2).second);
146 EXPECT_TRUE(map.emplace(piece, 3).second);
149 EXPECT_EQ(map.size(), 2);
153 EXPECT_EQ(map.find("hello")->second, 1);
154 EXPECT_EQ(map.find("lo")->second, 3);
156 map.erase(map.find("hello"));
158 EXPECT_EQ(map.size(), 1);
160 for (auto& it : map) {
161 EXPECT_EQ(it.first, "lo");
165 TEST(StringKeyedUnorderedMapTest, constructors) {
166 LeakCheckedUnorderedMap map {
171 LeakCheckedUnorderedMap map2(map);
172 EXPECT_EQ(map2.size(), 2);
173 EXPECT_TRUE(map2 == map);
176 for (auto& it : map2) {
177 EXPECT_EQ(it.first, "hello");
182 EXPECT_TRUE(map2.empty());
184 map2.emplace("key1", 1);
186 LeakCheckedUnorderedMap map3(std::move(map2));
188 EXPECT_EQ(map3.size(), 1);
189 EXPECT_EQ(map3["key1"], 1);
191 EXPECT_EQ(map3["key0"], 0);
192 EXPECT_EQ(map3.size(), 2);
196 EXPECT_EQ(map3.size(), 2);
198 LeakCheckedUnorderedMap map4 {
203 EXPECT_EQ(map4.erase("key0"), 1);
204 EXPECT_EQ(map4.size(), 1);
205 EXPECT_EQ(map4.find("key0"), map4.end());
209 EXPECT_EQ(map3.size(), 1);
210 EXPECT_EQ(map4.size(), 1);
211 EXPECT_EQ(map4.max_size(), map3.max_size());
213 map4 = std::move(map3);
215 EXPECT_EQ(map4.size(), 1);
216 EXPECT_EQ(map4.at("key1"), 1);
219 TEST(StringKeyedSetTest, sanity) {
221 EXPECT_TRUE(set.empty());
222 EXPECT_EQ(set.size(), 0);
226 StringPiece piece(s, 3);
228 EXPECT_FALSE(set.emplace(s).second);
229 EXPECT_TRUE(set.emplace(piece).second);
232 EXPECT_EQ(set.size(), 2);
236 EXPECT_NE(set.find(StringPiece("hello")), set.end());
237 EXPECT_NE(set.find("lo"), set.end());
239 auto it = set.begin();
240 EXPECT_EQ(*it, "hello");
241 EXPECT_EQ(*(++it), "lo");
242 EXPECT_EQ(++it, set.end());
244 set.erase(set.find("hello"));
246 EXPECT_EQ(set.size(), 1);
248 for (auto entry : set) {
249 EXPECT_EQ(entry, "lo");
253 TEST(StringKeyedSetTest, constructors) {
258 LeakCheckedSet set2(set);
260 EXPECT_EQ(set2.size(), 2);
263 for (auto it : set2) {
264 EXPECT_EQ(it, "hello");
269 EXPECT_TRUE(set2.empty());
271 set2.emplace("key1");
273 LeakCheckedSet set3(std::move(set2));
275 EXPECT_EQ(set3.size(), 1);
276 EXPECT_EQ(set3.insert("key1").second, false);
278 EXPECT_EQ(set3.emplace("key0").second, true);
279 EXPECT_EQ(set3.size(), 2);
281 EXPECT_EQ(set3.size(), 2);
283 LeakCheckedSet set4 {
288 EXPECT_EQ(set4.erase("key0"), 1);
289 EXPECT_EQ(set4.size(), 1);
290 EXPECT_EQ(set4.find("key0"), set4.end());
294 EXPECT_EQ(set3.size(), 1);
295 EXPECT_EQ(set4.size(), 1);
296 EXPECT_EQ(set4.max_size(), set3.max_size());
298 set4 = std::move(set3);
300 EXPECT_EQ(set4.size(), 1);
301 EXPECT_NE(set4.find("key1"), set4.end());
304 TEST(StringKeyedUnorderedSetTest, sanity) {
305 LeakCheckedUnorderedSet set;
306 EXPECT_TRUE(set.empty());
307 EXPECT_EQ(set.size(), 0);
311 StringPiece piece(s, 3);
313 EXPECT_FALSE(set.emplace(s).second);
314 EXPECT_TRUE(set.emplace(piece).second);
317 EXPECT_EQ(set.size(), 2);
321 EXPECT_NE(set.find("hello"), set.end());
322 EXPECT_NE(set.find("lo"), set.end());
324 set.erase(set.find("hello"));
326 EXPECT_EQ(set.size(), 1);
328 for (auto entry : set) {
329 EXPECT_EQ(entry, "lo");
333 TEST(StringKeyedUnorderedSetTest, constructors) {
334 LeakCheckedUnorderedSet s1;
335 EXPECT_TRUE(s1.empty());
337 LeakCheckedUnorderedSet s2(10);
338 EXPECT_TRUE(s2.empty());
339 EXPECT_GE(s2.bucket_count(), 10);
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"}));
348 LeakCheckedUnorderedSet s4(const_cast<LeakCheckedUnorderedSet&>(s3));
349 EXPECT_TRUE(s4 == s3);
351 LeakCheckedUnorderedSet s5(const_cast<LeakCheckedUnorderedSet&>(s3),
353 EXPECT_TRUE(s5 == s3);
355 LeakCheckedUnorderedSet s6(std::move(s3));
356 EXPECT_TRUE(s3.empty());
357 EXPECT_TRUE(s6 == s5);
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);
364 LeakCheckedUnorderedSet s8 {
368 EXPECT_EQ(s8.size(), 2);
369 EXPECT_NE(s8.find("hello"), s8.end());
370 EXPECT_NE(s8.find("lo"), s8.end());
372 LeakCheckedUnorderedSet s9({
376 EXPECT_EQ(s9.size(), 2);
377 EXPECT_NE(s9.find("hello"), s9.end());
378 EXPECT_NE(s9.find("lo"), s9.end());
380 LeakCheckedUnorderedSet set2(s8);
381 EXPECT_EQ(set2.size(), 2);
384 for (auto entry : set2) {
385 EXPECT_EQ(entry, "hello");
390 EXPECT_TRUE(set2.empty());
392 set2.emplace("key1");
394 LeakCheckedUnorderedSet set3(std::move(set2));
396 EXPECT_EQ(set3.size(), 1);
397 EXPECT_EQ(set3.insert("key1").second, false);
399 EXPECT_EQ(set3.emplace("key0").second, true);
400 EXPECT_EQ(set3.size(), 2);
404 EXPECT_EQ(set3.size(), 2);
406 LeakCheckedUnorderedSet set4 {
411 EXPECT_EQ(set4.erase("key0"), 1);
412 EXPECT_EQ(set4.size(), 1);
413 EXPECT_EQ(set4.find("key0"), set4.end());
417 EXPECT_EQ(set3.size(), 1);
418 EXPECT_EQ(set4.size(), 1);
419 EXPECT_EQ(set4.max_size(), set3.max_size());
421 set4 = std::move(set3);
423 EXPECT_EQ(set4.size(), 1);
424 EXPECT_NE(set4.find("key1"), set4.end());
427 TEST(StringKeyedMapTest, sanity) {
429 EXPECT_TRUE(map.empty());
430 EXPECT_EQ(map.size(), 0);
434 StringPiece piece(s, 3);
436 EXPECT_FALSE(map.emplace(s, 2).second);
437 EXPECT_TRUE(map.emplace(piece, 3).second);
440 EXPECT_EQ(map.size(), 2);
444 EXPECT_EQ(map.find("hello")->second, 1);
445 EXPECT_EQ(map.find("lo")->second, 3);
447 auto it = map.begin();
448 EXPECT_EQ(it->first, "hello");
449 EXPECT_EQ((++it)->first, "lo");
450 EXPECT_EQ(++it, map.end());
452 map.erase(map.find("hello"));
454 EXPECT_EQ(map.size(), 1);
456 for (auto& entry : map) {
457 EXPECT_EQ(entry.first, "lo");
461 TEST(StringKeyedMapTest, constructors) {
466 LeakCheckedMap map2(map);
468 EXPECT_EQ(map2.size(), 2);
471 for (auto& entry : map2) {
472 EXPECT_EQ(entry.first, "hello");
477 EXPECT_TRUE(map2.empty());
479 map2.emplace("key1", 1);
481 LeakCheckedMap map3(std::move(map2));
483 EXPECT_EQ(map3.size(), 1);
484 EXPECT_EQ(map3["key1"], 1);
486 EXPECT_EQ(map3["key0"], 0);
487 EXPECT_EQ(map3.size(), 2);
489 LeakCheckedMap map4 {
494 EXPECT_EQ(map4.erase("key0"), 1);
495 EXPECT_EQ(map4.size(), 1);
496 EXPECT_EQ(map4.find("key0"), map4.end());
500 EXPECT_EQ(map3.size(), 1);
501 EXPECT_EQ(map4.size(), 1);
502 EXPECT_EQ(map4.max_size(), map3.max_size());
504 map4 = std::move(map3);
506 EXPECT_EQ(map4.size(), 1);
507 EXPECT_EQ(map4.at("key1"), 1);
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);
516 return RUN_ALL_TESTS();
519 // This MUST be the LAST test.
520 TEST(StringKeyed, memory_balance) {
521 auto balance = allocated < freed
525 LOG(INFO) << "allocated: " << allocated
526 << " freed: " << freed
527 << " balance: " << balance
532 ? " positive (leak)" : ""
535 EXPECT_EQ(allocated, freed);