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
33using folly::BasicStringKeyedUnorderedSet;
34using folly::StringKeyedMap;
35using folly::StringKeyedSetBase;
36using folly::StringKeyedUnorderedMap;
37using folly::StringPiece;
38using std::string;
39
40static unsigned long long allocated = 0;
41static unsigned long long freed = 0;
42
43template <typename Alloc>
44struct 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
109using KeyValuePairLeakChecker = MemoryLeakCheckerAllocator<
110 std::allocator<std::pair<const StringPiece, int>>>;
111using ValueLeakChecker =
112 MemoryLeakCheckerAllocator<std::allocator<StringPiece>>;
113
114using 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
121typedef StringKeyedSetBase<std::less<StringPiece>, ValueLeakChecker>
122 LeakCheckedSet;
123
124typedef StringKeyedMap<int, std::less<StringPiece>, KeyValuePairLeakChecker>
125 LeakCheckedMap;
126
127using LeakCheckedUnorderedSet = BasicStringKeyedUnorderedSet<
128 folly::transparent<folly::hasher<StringPiece>>,
129 folly::transparent<std::equal_to<folly::StringPiece>>,
130 MemoryLeakCheckerAllocator<std::allocator<std::string>>>;
131
132TEST(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
161TEST(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
215TEST(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
249TEST(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
300TEST(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
329TEST(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
425TEST(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
459TEST(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
508int 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.
518TEST(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}
529