2 * Copyright 2015 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 <gflags/gflags.h>
19 #include <glog/logging.h>
20 #include <gtest/gtest.h>
25 #include <folly/Range.h>
26 #include <folly/experimental/StringKeyedMap.h>
27 #include <folly/experimental/StringKeyedSet.h>
28 #include <folly/experimental/StringKeyedUnorderedMap.h>
29 #include <folly/experimental/StringKeyedUnorderedSet.h>
31 using folly::StringKeyedMap;
32 using folly::StringKeyedSetBase;
33 using folly::StringKeyedUnorderedMap;
34 using folly::BasicStringKeyedUnorderedSet;
35 using folly::StringPiece;
38 static unsigned long long allocated = 0;
39 static unsigned long long freed = 0;
41 template <typename Alloc>
42 struct MemoryLeakCheckerAllocator {
43 typedef typename Alloc::value_type value_type;
44 typedef value_type *pointer;
45 typedef value_type const *const_pointer;
46 typedef value_type &reference;
47 typedef value_type const *const_reference;
49 typedef std::ptrdiff_t difference_type;
50 typedef std::size_t size_type;
52 explicit MemoryLeakCheckerAllocator() {
55 explicit MemoryLeakCheckerAllocator(Alloc alloc)
59 template <class UAlloc>
60 MemoryLeakCheckerAllocator(const MemoryLeakCheckerAllocator<UAlloc>& other)
61 : alloc_(other.allocator()) {
64 value_type* allocate(size_t n, const void* hint = nullptr) {
65 auto p = alloc_.allocate(n, hint);
66 allocated += n * sizeof(value_type);
70 void deallocate(value_type* p, size_t n) {
71 alloc_.deallocate(p, n);
72 freed += n * sizeof(value_type);
75 size_t max_size() const {
76 return alloc_.max_size();
79 template <class... Args>
80 void construct(value_type* p, Args&&... args) {
81 alloc_.construct(p, std::forward<Args>(args)...);
84 void destroy(value_type* p) {
90 typedef MemoryLeakCheckerAllocator<
91 typename std::allocator_traits<Alloc>::template rebind_alloc<U>
95 const Alloc& allocator() const {
99 bool operator!=(const MemoryLeakCheckerAllocator& other) const {
100 return alloc_ != other.alloc_;
103 bool operator==(const MemoryLeakCheckerAllocator& other) const {
104 return alloc_ == other.alloc_;
111 typedef MemoryLeakCheckerAllocator<std::allocator<char>> KeyLeakChecker;
112 typedef MemoryLeakCheckerAllocator<
113 std::allocator<std::pair<const StringPiece, int>>> ValueLeakChecker;
115 typedef StringKeyedUnorderedMap<int, folly::StringPieceHash,
116 std::equal_to<StringPiece>, ValueLeakChecker>
117 LeakCheckedUnorderedMap;
119 typedef StringKeyedSetBase<std::less<StringPiece>, ValueLeakChecker> LeakCheckedSet;
121 typedef StringKeyedMap<int, std::less<StringPiece>,
122 ValueLeakChecker> LeakCheckedMap;
124 using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet<
125 folly::StringPieceHash,
126 std::equal_to<folly::StringPiece>,
129 TEST(StringKeyedUnorderedMapTest, sanity) {
130 LeakCheckedUnorderedMap map;
131 EXPECT_TRUE(map.empty());
132 EXPECT_EQ(map.size(), 0);
136 StringPiece piece(s, 3);
138 EXPECT_FALSE(map.emplace(s, 2).second);
139 EXPECT_TRUE(map.emplace(piece, 3).second);
142 EXPECT_EQ(map.size(), 2);
146 EXPECT_EQ(map.find("hello")->second, 1);
147 EXPECT_EQ(map.find("lo")->second, 3);
149 map.erase(map.find("hello"));
151 EXPECT_EQ(map.size(), 1);
153 for (auto& it : map) {
154 EXPECT_EQ(it.first, "lo");
158 TEST(StringKeyedUnorderedMapTest, constructors) {
159 LeakCheckedUnorderedMap map {
164 LeakCheckedUnorderedMap map2(map);
165 EXPECT_EQ(map2.size(), 2);
166 EXPECT_TRUE(map2 == map);
169 for (auto& it : map2) {
170 EXPECT_EQ(it.first, "hello");
175 EXPECT_TRUE(map2.empty());
177 map2.emplace("key1", 1);
179 LeakCheckedUnorderedMap map3(move(map2));
181 EXPECT_EQ(map3.size(), 1);
182 EXPECT_EQ(map3["key1"], 1);
184 EXPECT_EQ(map3["key0"], 0);
185 EXPECT_EQ(map3.size(), 2);
189 EXPECT_EQ(map3.size(), 2);
191 LeakCheckedUnorderedMap map4 {
196 EXPECT_EQ(map4.erase("key0"), 1);
197 EXPECT_EQ(map4.size(), 1);
198 EXPECT_EQ(map4.find("key0"), map4.end());
202 EXPECT_EQ(map3.size(), 1);
203 EXPECT_EQ(map4.size(), 1);
204 EXPECT_EQ(map4.max_size(), map3.max_size());
206 map4 = std::move(map3);
208 EXPECT_EQ(map4.size(), 1);
209 EXPECT_EQ(map4.at("key1"), 1);
212 TEST(StringKeyedSetTest, sanity) {
214 EXPECT_TRUE(set.empty());
215 EXPECT_EQ(set.size(), 0);
219 StringPiece piece(s, 3);
221 EXPECT_FALSE(set.emplace(s).second);
222 EXPECT_TRUE(set.emplace(piece).second);
225 EXPECT_EQ(set.size(), 2);
229 EXPECT_NE(set.find(StringPiece("hello")), set.end());
230 EXPECT_NE(set.find("lo"), set.end());
232 auto it = set.begin();
233 EXPECT_EQ(*it, "hello");
234 EXPECT_EQ(*(++it), "lo");
235 EXPECT_EQ(++it, set.end());
237 set.erase(set.find("hello"));
239 EXPECT_EQ(set.size(), 1);
241 for (auto it : set) {
246 TEST(StringKeyedSetTest, constructors) {
251 LeakCheckedSet set2(set);
253 EXPECT_EQ(set2.size(), 2);
256 for (auto it : set2) {
257 EXPECT_EQ(it, "hello");
262 EXPECT_TRUE(set2.empty());
264 set2.emplace("key1");
266 LeakCheckedSet set3(move(set2));
268 EXPECT_EQ(set3.size(), 1);
269 EXPECT_EQ(set3.insert("key1").second, false);
271 EXPECT_EQ(set3.emplace("key0").second, true);
272 EXPECT_EQ(set3.size(), 2);
274 EXPECT_EQ(set3.size(), 2);
276 LeakCheckedSet set4 {
281 EXPECT_EQ(set4.erase("key0"), 1);
282 EXPECT_EQ(set4.size(), 1);
283 EXPECT_EQ(set4.find("key0"), set4.end());
287 EXPECT_EQ(set3.size(), 1);
288 EXPECT_EQ(set4.size(), 1);
289 EXPECT_EQ(set4.max_size(), set3.max_size());
291 set4 = std::move(set3);
293 EXPECT_EQ(set4.size(), 1);
294 EXPECT_NE(set4.find("key1"), set4.end());
297 TEST(StringKeyedUnorderedSetTest, sanity) {
298 LeakCheckedUnorderedSet set;
299 EXPECT_TRUE(set.empty());
300 EXPECT_EQ(set.size(), 0);
304 StringPiece piece(s, 3);
306 EXPECT_FALSE(set.emplace(s).second);
307 EXPECT_TRUE(set.emplace(piece).second);
310 EXPECT_EQ(set.size(), 2);
314 EXPECT_NE(set.find("hello"), set.end());
315 EXPECT_NE(set.find("lo"), set.end());
317 set.erase(set.find("hello"));
319 EXPECT_EQ(set.size(), 1);
321 for (auto it : set) {
326 TEST(StringKeyedUnorderedSetTest, constructors) {
327 LeakCheckedUnorderedSet s1;
328 EXPECT_TRUE(s1.empty());
330 LeakCheckedUnorderedSet s2(10);
331 EXPECT_TRUE(s2.empty());
332 EXPECT_GE(s2.bucket_count(), 10);
334 std::list<StringPiece> lst { "abc", "def" };
335 LeakCheckedUnorderedSet s3(lst.begin(), lst.end());
336 EXPECT_EQ(s3.size(), 2);
337 EXPECT_NE(s3.find("abc"), s3.end());
338 EXPECT_NE(s3.find("def"), s3.end());
339 EXPECT_TRUE(s3 == (LeakCheckedUnorderedSet{"abc", "def"}));
341 LeakCheckedUnorderedSet s4(const_cast<LeakCheckedUnorderedSet&>(s3));
342 EXPECT_TRUE(s4 == s3);
344 LeakCheckedUnorderedSet s5(const_cast<LeakCheckedUnorderedSet&>(s3),
346 EXPECT_TRUE(s5 == s3);
348 LeakCheckedUnorderedSet s6(std::move(s3));
349 EXPECT_TRUE(s3.empty());
350 EXPECT_TRUE(s6 == s5);
352 LeakCheckedUnorderedSet s7(std::move(s6), s6.get_allocator());
353 EXPECT_TRUE(s6.empty());
354 EXPECT_TRUE(s7 == s5);
356 LeakCheckedUnorderedSet s8 {
360 EXPECT_EQ(s8.size(), 2);
361 EXPECT_NE(s8.find("hello"), s8.end());
362 EXPECT_NE(s8.find("lo"), s8.end());
364 LeakCheckedUnorderedSet s9({
368 EXPECT_EQ(s9.size(), 2);
369 EXPECT_NE(s9.find("hello"), s9.end());
370 EXPECT_NE(s9.find("lo"), s9.end());
372 LeakCheckedUnorderedSet set2(s8);
373 EXPECT_EQ(set2.size(), 2);
376 for (auto it : set2) {
377 EXPECT_EQ(it, "hello");
382 EXPECT_TRUE(set2.empty());
384 set2.emplace("key1");
386 LeakCheckedUnorderedSet set3(move(set2));
388 EXPECT_EQ(set3.size(), 1);
389 EXPECT_EQ(set3.insert("key1").second, false);
391 EXPECT_EQ(set3.emplace("key0").second, true);
392 EXPECT_EQ(set3.size(), 2);
396 EXPECT_EQ(set3.size(), 2);
398 LeakCheckedUnorderedSet set4 {
403 EXPECT_EQ(set4.erase("key0"), 1);
404 EXPECT_EQ(set4.size(), 1);
405 EXPECT_EQ(set4.find("key0"), set4.end());
409 EXPECT_EQ(set3.size(), 1);
410 EXPECT_EQ(set4.size(), 1);
411 EXPECT_EQ(set4.max_size(), set3.max_size());
413 set4 = std::move(set3);
415 EXPECT_EQ(set4.size(), 1);
416 EXPECT_NE(set4.find("key1"), set4.end());
419 TEST(StringKeyedMapTest, sanity) {
421 EXPECT_TRUE(map.empty());
422 EXPECT_EQ(map.size(), 0);
426 StringPiece piece(s, 3);
428 EXPECT_FALSE(map.emplace(s, 2).second);
429 EXPECT_TRUE(map.emplace(piece, 3).second);
432 EXPECT_EQ(map.size(), 2);
436 EXPECT_EQ(map.find("hello")->second, 1);
437 EXPECT_EQ(map.find("lo")->second, 3);
439 auto it = map.begin();
440 EXPECT_EQ(it->first, "hello");
441 EXPECT_EQ((++it)->first, "lo");
442 EXPECT_EQ(++it, map.end());
444 map.erase(map.find("hello"));
446 EXPECT_EQ(map.size(), 1);
448 for (auto& it : map) {
449 EXPECT_EQ(it.first, "lo");
453 TEST(StringKeyedMapTest, constructors) {
458 LeakCheckedMap map2(map);
460 EXPECT_EQ(map2.size(), 2);
463 for (auto& it : map2) {
464 EXPECT_EQ(it.first, "hello");
469 EXPECT_TRUE(map2.empty());
471 map2.emplace("key1", 1);
473 LeakCheckedMap map3(move(map2));
475 EXPECT_EQ(map3.size(), 1);
476 EXPECT_EQ(map3["key1"], 1);
478 EXPECT_EQ(map3["key0"], 0);
479 EXPECT_EQ(map3.size(), 2);
481 LeakCheckedMap map4 {
486 EXPECT_EQ(map4.erase("key0"), 1);
487 EXPECT_EQ(map4.size(), 1);
488 EXPECT_EQ(map4.find("key0"), map4.end());
492 EXPECT_EQ(map3.size(), 1);
493 EXPECT_EQ(map4.size(), 1);
494 EXPECT_EQ(map4.max_size(), map3.max_size());
496 map4 = std::move(map3);
498 EXPECT_EQ(map4.size(), 1);
499 EXPECT_EQ(map4.at("key1"), 1);
502 int main(int argc, char **argv) {
503 FLAGS_logtostderr = true;
504 google::InitGoogleLogging(argv[0]);
505 testing::InitGoogleTest(&argc, argv);
506 gflags::ParseCommandLineFlags(&argc, &argv, true);
508 return RUN_ALL_TESTS();
511 // This MUST be the LAST test.
512 TEST(StringKeyed, memory_balance) {
513 auto balance = allocated < freed
517 LOG(INFO) << "allocated: " << allocated
518 << " freed: " << freed
519 << " balance: " << balance
524 ? " positive (leak)" : ""
527 EXPECT_EQ(allocated, freed);