2 * Copyright 2016 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 typedef MemoryLeakCheckerAllocator<std::allocator<char>> KeyLeakChecker;
114 typedef MemoryLeakCheckerAllocator<
115 std::allocator<std::pair<const StringPiece, int>>> ValueLeakChecker;
117 typedef StringKeyedUnorderedMap<
120 std::equal_to<StringPiece>,
122 LeakCheckedUnorderedMap;
124 typedef StringKeyedSetBase<std::less<StringPiece>, ValueLeakChecker>
127 typedef StringKeyedMap<int, std::less<StringPiece>, ValueLeakChecker>
130 using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet<
132 std::equal_to<folly::StringPiece>,
135 TEST(StringKeyedUnorderedMapTest, sanity) {
136 LeakCheckedUnorderedMap map;
137 EXPECT_TRUE(map.empty());
138 EXPECT_EQ(map.size(), 0);
142 StringPiece piece(s, 3);
144 EXPECT_FALSE(map.emplace(s, 2).second);
145 EXPECT_TRUE(map.emplace(piece, 3).second);
148 EXPECT_EQ(map.size(), 2);
152 EXPECT_EQ(map.find("hello")->second, 1);
153 EXPECT_EQ(map.find("lo")->second, 3);
155 map.erase(map.find("hello"));
157 EXPECT_EQ(map.size(), 1);
159 for (auto& it : map) {
160 EXPECT_EQ(it.first, "lo");
164 TEST(StringKeyedUnorderedMapTest, constructors) {
165 LeakCheckedUnorderedMap map {
170 LeakCheckedUnorderedMap map2(map);
171 EXPECT_EQ(map2.size(), 2);
172 EXPECT_TRUE(map2 == map);
175 for (auto& it : map2) {
176 EXPECT_EQ(it.first, "hello");
181 EXPECT_TRUE(map2.empty());
183 map2.emplace("key1", 1);
185 LeakCheckedUnorderedMap map3(std::move(map2));
187 EXPECT_EQ(map3.size(), 1);
188 EXPECT_EQ(map3["key1"], 1);
190 EXPECT_EQ(map3["key0"], 0);
191 EXPECT_EQ(map3.size(), 2);
195 EXPECT_EQ(map3.size(), 2);
197 LeakCheckedUnorderedMap map4 {
202 EXPECT_EQ(map4.erase("key0"), 1);
203 EXPECT_EQ(map4.size(), 1);
204 EXPECT_EQ(map4.find("key0"), map4.end());
208 EXPECT_EQ(map3.size(), 1);
209 EXPECT_EQ(map4.size(), 1);
210 EXPECT_EQ(map4.max_size(), map3.max_size());
212 map4 = std::move(map3);
214 EXPECT_EQ(map4.size(), 1);
215 EXPECT_EQ(map4.at("key1"), 1);
218 TEST(StringKeyedSetTest, sanity) {
220 EXPECT_TRUE(set.empty());
221 EXPECT_EQ(set.size(), 0);
225 StringPiece piece(s, 3);
227 EXPECT_FALSE(set.emplace(s).second);
228 EXPECT_TRUE(set.emplace(piece).second);
231 EXPECT_EQ(set.size(), 2);
235 EXPECT_NE(set.find(StringPiece("hello")), set.end());
236 EXPECT_NE(set.find("lo"), set.end());
238 auto it = set.begin();
239 EXPECT_EQ(*it, "hello");
240 EXPECT_EQ(*(++it), "lo");
241 EXPECT_EQ(++it, set.end());
243 set.erase(set.find("hello"));
245 EXPECT_EQ(set.size(), 1);
247 for (auto it : set) {
252 TEST(StringKeyedSetTest, constructors) {
257 LeakCheckedSet set2(set);
259 EXPECT_EQ(set2.size(), 2);
262 for (auto it : set2) {
263 EXPECT_EQ(it, "hello");
268 EXPECT_TRUE(set2.empty());
270 set2.emplace("key1");
272 LeakCheckedSet set3(std::move(set2));
274 EXPECT_EQ(set3.size(), 1);
275 EXPECT_EQ(set3.insert("key1").second, false);
277 EXPECT_EQ(set3.emplace("key0").second, true);
278 EXPECT_EQ(set3.size(), 2);
280 EXPECT_EQ(set3.size(), 2);
282 LeakCheckedSet set4 {
287 EXPECT_EQ(set4.erase("key0"), 1);
288 EXPECT_EQ(set4.size(), 1);
289 EXPECT_EQ(set4.find("key0"), set4.end());
293 EXPECT_EQ(set3.size(), 1);
294 EXPECT_EQ(set4.size(), 1);
295 EXPECT_EQ(set4.max_size(), set3.max_size());
297 set4 = std::move(set3);
299 EXPECT_EQ(set4.size(), 1);
300 EXPECT_NE(set4.find("key1"), set4.end());
303 TEST(StringKeyedUnorderedSetTest, sanity) {
304 LeakCheckedUnorderedSet set;
305 EXPECT_TRUE(set.empty());
306 EXPECT_EQ(set.size(), 0);
310 StringPiece piece(s, 3);
312 EXPECT_FALSE(set.emplace(s).second);
313 EXPECT_TRUE(set.emplace(piece).second);
316 EXPECT_EQ(set.size(), 2);
320 EXPECT_NE(set.find("hello"), set.end());
321 EXPECT_NE(set.find("lo"), set.end());
323 set.erase(set.find("hello"));
325 EXPECT_EQ(set.size(), 1);
327 for (auto it : set) {
332 TEST(StringKeyedUnorderedSetTest, constructors) {
333 LeakCheckedUnorderedSet s1;
334 EXPECT_TRUE(s1.empty());
336 LeakCheckedUnorderedSet s2(10);
337 EXPECT_TRUE(s2.empty());
338 EXPECT_GE(s2.bucket_count(), 10);
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"}));
347 LeakCheckedUnorderedSet s4(const_cast<LeakCheckedUnorderedSet&>(s3));
348 EXPECT_TRUE(s4 == s3);
350 LeakCheckedUnorderedSet s5(const_cast<LeakCheckedUnorderedSet&>(s3),
352 EXPECT_TRUE(s5 == s3);
354 LeakCheckedUnorderedSet s6(std::move(s3));
355 EXPECT_TRUE(s3.empty());
356 EXPECT_TRUE(s6 == s5);
358 LeakCheckedUnorderedSet s7(std::move(s6), s6.get_allocator());
359 EXPECT_TRUE(s6.empty());
360 EXPECT_TRUE(s7 == s5);
362 LeakCheckedUnorderedSet s8 {
366 EXPECT_EQ(s8.size(), 2);
367 EXPECT_NE(s8.find("hello"), s8.end());
368 EXPECT_NE(s8.find("lo"), s8.end());
370 LeakCheckedUnorderedSet s9({
374 EXPECT_EQ(s9.size(), 2);
375 EXPECT_NE(s9.find("hello"), s9.end());
376 EXPECT_NE(s9.find("lo"), s9.end());
378 LeakCheckedUnorderedSet set2(s8);
379 EXPECT_EQ(set2.size(), 2);
382 for (auto it : set2) {
383 EXPECT_EQ(it, "hello");
388 EXPECT_TRUE(set2.empty());
390 set2.emplace("key1");
392 LeakCheckedUnorderedSet set3(std::move(set2));
394 EXPECT_EQ(set3.size(), 1);
395 EXPECT_EQ(set3.insert("key1").second, false);
397 EXPECT_EQ(set3.emplace("key0").second, true);
398 EXPECT_EQ(set3.size(), 2);
402 EXPECT_EQ(set3.size(), 2);
404 LeakCheckedUnorderedSet set4 {
409 EXPECT_EQ(set4.erase("key0"), 1);
410 EXPECT_EQ(set4.size(), 1);
411 EXPECT_EQ(set4.find("key0"), set4.end());
415 EXPECT_EQ(set3.size(), 1);
416 EXPECT_EQ(set4.size(), 1);
417 EXPECT_EQ(set4.max_size(), set3.max_size());
419 set4 = std::move(set3);
421 EXPECT_EQ(set4.size(), 1);
422 EXPECT_NE(set4.find("key1"), set4.end());
425 TEST(StringKeyedMapTest, sanity) {
427 EXPECT_TRUE(map.empty());
428 EXPECT_EQ(map.size(), 0);
432 StringPiece piece(s, 3);
434 EXPECT_FALSE(map.emplace(s, 2).second);
435 EXPECT_TRUE(map.emplace(piece, 3).second);
438 EXPECT_EQ(map.size(), 2);
442 EXPECT_EQ(map.find("hello")->second, 1);
443 EXPECT_EQ(map.find("lo")->second, 3);
445 auto it = map.begin();
446 EXPECT_EQ(it->first, "hello");
447 EXPECT_EQ((++it)->first, "lo");
448 EXPECT_EQ(++it, map.end());
450 map.erase(map.find("hello"));
452 EXPECT_EQ(map.size(), 1);
454 for (auto& it : map) {
455 EXPECT_EQ(it.first, "lo");
459 TEST(StringKeyedMapTest, constructors) {
464 LeakCheckedMap map2(map);
466 EXPECT_EQ(map2.size(), 2);
469 for (auto& it : map2) {
470 EXPECT_EQ(it.first, "hello");
475 EXPECT_TRUE(map2.empty());
477 map2.emplace("key1", 1);
479 LeakCheckedMap map3(std::move(map2));
481 EXPECT_EQ(map3.size(), 1);
482 EXPECT_EQ(map3["key1"], 1);
484 EXPECT_EQ(map3["key0"], 0);
485 EXPECT_EQ(map3.size(), 2);
487 LeakCheckedMap map4 {
492 EXPECT_EQ(map4.erase("key0"), 1);
493 EXPECT_EQ(map4.size(), 1);
494 EXPECT_EQ(map4.find("key0"), map4.end());
498 EXPECT_EQ(map3.size(), 1);
499 EXPECT_EQ(map4.size(), 1);
500 EXPECT_EQ(map4.max_size(), map3.max_size());
502 map4 = std::move(map3);
504 EXPECT_EQ(map4.size(), 1);
505 EXPECT_EQ(map4.at("key1"), 1);
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);
514 return RUN_ALL_TESTS();
517 // This MUST be the LAST test.
518 TEST(StringKeyed, memory_balance) {
519 auto balance = allocated < freed
523 LOG(INFO) << "allocated: " << allocated
524 << " freed: " << freed
525 << " balance: " << balance
530 ? " positive (leak)" : ""
533 EXPECT_EQ(allocated, freed);