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 | } |
529 | |