Debian Codegraph @

tests/btree_test.cc

raw
1 // ---------------------------------------------------------------------------
2 // Copyright (c) 2019, Gregory Popovitch - [email protected]
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 // https://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 // Includes work from abseil-cpp (https://github.com/abseil/abseil-cpp)
17 // with modifications.
18 //
19 // Copyright 2018 The Abseil Authors.
20 //
21 // Licensed under the Apache License, Version 2.0 (the "License");
22 // you may not use this file except in compliance with the License.
23 // You may obtain a copy of the License at
24 //
25 // https://www.apache.org/licenses/LICENSE-2.0
26 //
27 // Unless required by applicable law or agreed to in writing, software
28 // distributed under the License is distributed on an "AS IS" BASIS,
29 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
30 // See the License for the specific language governing permissions and
31 // limitations under the License.
32 // ---------------------------------------------------------------------------
33
34 #include <numeric>
35 #include "btree_test.h"
36
37 #ifdef _MSC_VER
38 #pragma warning(disable: 4244 4100 4389)
39 #endif
40
41 namespace phmap {
42 namespace test_internal {
43 size_t BaseCountedInstance::num_instances_ = 0;
44 size_t BaseCountedInstance::num_live_instances_ = 0;
45 size_t BaseCountedInstance::num_moves_ = 0;
46 size_t BaseCountedInstance::num_copies_ = 0;
47 size_t BaseCountedInstance::num_swaps_ = 0;
48 size_t BaseCountedInstance::num_comparisons_ = 0;
49
50 } // namespace test_internal
51 } // namespace phmap
52
53
54 static const size_t test_values = 10000;
55
56 namespace phmap {
57 namespace priv {
58 namespace {
59
60 using ::phmap::test_internal::CopyableMovableInstance;
61 using ::phmap::test_internal::InstanceTracker;
62 using ::phmap::test_internal::MovableOnlyInstance;
63 using ::testing::ElementsAre;
64 using ::testing::ElementsAreArray;
65 using ::testing::IsEmpty;
66 using ::testing::Pair;
67
68 #define PHMAP_INTERNAL_CHECK(condition, message) \
69 if (!(condition)) assert(0)
70
71 template <typename T, typename U>
72 void CheckPairEquals(const T &x, const U &y) {
73 PHMAP_INTERNAL_CHECK(x == y, "Values are unequal.");
74 }
75
76 template <typename T, typename U, typename V, typename W>
77 void CheckPairEquals(const std::pair<T, U> &x, const std::pair<V, W> &y) {
78 CheckPairEquals(x.first, y.first);
79 CheckPairEquals(x.second, y.second);
80 }
81 } // namespace
82
83 // The base class for a sorted associative container checker. TreeType is the
84 // container type to check and CheckerType is the container type to check
85 // against. TreeType is expected to be btree_{set,map,multiset,multimap} and
86 // CheckerType is expected to be {set,map,multiset,multimap}.
87 template <typename TreeType, typename CheckerType>
88 class base_checker {
89 public:
90 using key_type = typename TreeType::key_type;
91 using value_type = typename TreeType::value_type;
92 using key_compare = typename TreeType::key_compare;
93 using pointer = typename TreeType::pointer;
94 using const_pointer = typename TreeType::const_pointer;
95 using reference = typename TreeType::reference;
96 using const_reference = typename TreeType::const_reference;
97 using size_type = typename TreeType::size_type;
98 using difference_type = typename TreeType::difference_type;
99 using iterator = typename TreeType::iterator;
100 using const_iterator = typename TreeType::const_iterator;
101 using reverse_iterator = typename TreeType::reverse_iterator;
102 using const_reverse_iterator = typename TreeType::const_reverse_iterator;
103
104 public:
105 base_checker() : const_tree_(tree_) {}
106 base_checker(const base_checker &x)
107 : tree_(x.tree_), const_tree_(tree_), checker_(x.checker_) {}
108 template <typename InputIterator>
109 base_checker(InputIterator b, InputIterator e)
110 : tree_(b, e), const_tree_(tree_), checker_(b, e) {}
111
112 iterator begin() { return tree_.begin(); }
113 const_iterator begin() const { return tree_.begin(); }
114 iterator end() { return tree_.end(); }
115 const_iterator end() const { return tree_.end(); }
116 reverse_iterator rbegin() { return tree_.rbegin(); }
117 const_reverse_iterator rbegin() const { return tree_.rbegin(); }
118 reverse_iterator rend() { return tree_.rend(); }
119 const_reverse_iterator rend() const { return tree_.rend(); }
120
121 template <typename IterType, typename CheckerIterType>
122 IterType iter_check(IterType tree_iter, CheckerIterType checker_iter) const {
123 if (tree_iter == tree_.end()) {
124 PHMAP_INTERNAL_CHECK(checker_iter == checker_.end(),
125 "Checker iterator not at end.");
126 } else {
127 CheckPairEquals(*tree_iter, *checker_iter);
128 }
129 return tree_iter;
130 }
131 template <typename IterType, typename CheckerIterType>
132 IterType riter_check(IterType tree_iter, CheckerIterType checker_iter) const {
133 if (tree_iter == tree_.rend()) {
134 PHMAP_INTERNAL_CHECK(checker_iter == checker_.rend(),
135 "Checker iterator not at rend.");
136 } else {
137 CheckPairEquals(*tree_iter, *checker_iter);
138 }
139 return tree_iter;
140 }
141 void value_check(const value_type &x) {
142 typename KeyOfValue<typename TreeType::key_type,
143 typename TreeType::value_type>::type key_of_value;
144 const key_type &key = key_of_value(x);
145 CheckPairEquals(*find(key), x);
146 lower_bound(key);
147 upper_bound(key);
148 equal_range(key);
149 contains(key);
150 count(key);
151 }
152 void erase_check(const key_type &key) {
153 EXPECT_FALSE(tree_.contains(key));
154 EXPECT_EQ(tree_.find(key), const_tree_.end());
155 EXPECT_FALSE(const_tree_.contains(key));
156 EXPECT_EQ(const_tree_.find(key), tree_.end());
157 EXPECT_EQ(tree_.equal_range(key).first,
158 const_tree_.equal_range(key).second);
159 }
160
161 iterator lower_bound(const key_type &key) {
162 return iter_check(tree_.lower_bound(key), checker_.lower_bound(key));
163 }
164 const_iterator lower_bound(const key_type &key) const {
165 return iter_check(tree_.lower_bound(key), checker_.lower_bound(key));
166 }
167 iterator upper_bound(const key_type &key) {
168 return iter_check(tree_.upper_bound(key), checker_.upper_bound(key));
169 }
170 const_iterator upper_bound(const key_type &key) const {
171 return iter_check(tree_.upper_bound(key), checker_.upper_bound(key));
172 }
173 std::pair<iterator, iterator> equal_range(const key_type &key) {
174 std::pair<typename CheckerType::iterator, typename CheckerType::iterator>
175 checker_res = checker_.equal_range(key);
176 std::pair<iterator, iterator> tree_res = tree_.equal_range(key);
177 iter_check(tree_res.first, checker_res.first);
178 iter_check(tree_res.second, checker_res.second);
179 return tree_res;
180 }
181 std::pair<const_iterator, const_iterator> equal_range(
182 const key_type &key) const {
183 std::pair<typename CheckerType::const_iterator,
184 typename CheckerType::const_iterator>
185 checker_res = checker_.equal_range(key);
186 std::pair<const_iterator, const_iterator> tree_res = tree_.equal_range(key);
187 iter_check(tree_res.first, checker_res.first);
188 iter_check(tree_res.second, checker_res.second);
189 return tree_res;
190 }
191 iterator find(const key_type &key) {
192 return iter_check(tree_.find(key), checker_.find(key));
193 }
194 const_iterator find(const key_type &key) const {
195 return iter_check(tree_.find(key), checker_.find(key));
196 }
197 bool contains(const key_type &key) const {
198 return find(key) != end();
199 }
200 size_type count(const key_type &key) const {
201 size_type res = checker_.count(key);
202 EXPECT_EQ(res, tree_.count(key));
203 return res;
204 }
205
206 base_checker &operator=(const base_checker &x) {
207 tree_ = x.tree_;
208 checker_ = x.checker_;
209 return *this;
210 }
211
212 int erase(const key_type &key) {
213 size_t size = tree_.size();
214 int res = (int)checker_.erase(key);
215 EXPECT_EQ(res, tree_.count(key));
216 EXPECT_EQ(res, tree_.erase(key));
217 EXPECT_EQ(tree_.count(key), 0);
218 EXPECT_EQ(tree_.size(), size - res);
219 erase_check(key);
220 return res;
221 }
222 iterator erase(iterator iter) {
223 key_type key = iter.key();
224 size_t size = tree_.size();
225 size_t count = tree_.count(key);
226 auto checker_iter = checker_.lower_bound(key);
227 for (iterator tmp(tree_.lower_bound(key)); tmp != iter; ++tmp) {
228 ++checker_iter;
229 }
230 auto checker_next = checker_iter;
231 ++checker_next;
232 checker_.erase(checker_iter);
233 iter = tree_.erase(iter);
234 EXPECT_EQ(tree_.size(), (size_t)checker_.size());
235 EXPECT_EQ(tree_.size(), size - 1);
236 EXPECT_EQ(tree_.count(key), count - 1);
237 if (count == 1) {
238 erase_check(key);
239 }
240 return iter_check(iter, checker_next);
241 }
242
243 void erase(iterator begin, iterator end) {
244 size_t size = tree_.size();
245 int count = std::distance(begin, end);
246 auto checker_begin = checker_.lower_bound(begin.key());
247 for (iterator tmp(tree_.lower_bound(begin.key())); tmp != begin; ++tmp) {
248 ++checker_begin;
249 }
250 auto checker_end =
251 end == tree_.end() ? checker_.end() : checker_.lower_bound(end.key());
252 if (end != tree_.end()) {
253 for (iterator tmp(tree_.lower_bound(end.key())); tmp != end; ++tmp) {
254 ++checker_end;
255 }
256 }
257 checker_.erase(checker_begin, checker_end);
258 tree_.erase(begin, end);
259 EXPECT_EQ(tree_.size(), checker_.size());
260 EXPECT_EQ(tree_.size(), size - count);
261 }
262
263 void clear() {
264 tree_.clear();
265 checker_.clear();
266 }
267 void swap(base_checker &x) {
268 tree_.swap(x.tree_);
269 checker_.swap(x.checker_);
270 }
271
272 void verify() const {
273 tree_.verify();
274 EXPECT_EQ(tree_.size(), checker_.size());
275
276 // Move through the forward iterators using increment.
277 auto checker_iter = checker_.begin();
278 const_iterator tree_iter(tree_.begin());
279 for (; tree_iter != tree_.end(); ++tree_iter, ++checker_iter) {
280 CheckPairEquals(*tree_iter, *checker_iter);
281 }
282
283 // Move through the forward iterators using decrement.
284 for (int n = (int)tree_.size() - 1; n >= 0; --n) {
285 iter_check(tree_iter, checker_iter);
286 --tree_iter;
287 --checker_iter;
288 }
289 EXPECT_EQ(tree_iter, tree_.begin());
290 EXPECT_EQ(checker_iter, checker_.begin());
291
292 // Move through the reverse iterators using increment.
293 auto checker_riter = checker_.rbegin();
294 const_reverse_iterator tree_riter(tree_.rbegin());
295 for (; tree_riter != tree_.rend(); ++tree_riter, ++checker_riter) {
296 CheckPairEquals(*tree_riter, *checker_riter);
297 }
298
299 // Move through the reverse iterators using decrement.
300 for (int n = (int)tree_.size() - 1; n >= 0; --n) {
301 riter_check(tree_riter, checker_riter);
302 --tree_riter;
303 --checker_riter;
304 }
305 EXPECT_EQ(tree_riter, tree_.rbegin());
306 EXPECT_EQ(checker_riter, checker_.rbegin());
307 }
308
309 const TreeType &tree() const { return tree_; }
310
311 size_type size() const {
312 EXPECT_EQ(tree_.size(), checker_.size());
313 return tree_.size();
314 }
315 size_type max_size() const { return tree_.max_size(); }
316 bool empty() const {
317 EXPECT_EQ(tree_.empty(), checker_.empty());
318 return tree_.empty();
319 }
320
321 protected:
322 TreeType tree_;
323 const TreeType &const_tree_;
324 CheckerType checker_;
325 };
326
327 namespace {
328 // A checker for unique sorted associative containers. TreeType is expected to
329 // be btree_{set,map} and CheckerType is expected to be {set,map}.
330 template <typename TreeType, typename CheckerType>
331 class unique_checker : public base_checker<TreeType, CheckerType> {
332 using super_type = base_checker<TreeType, CheckerType>;
333
334 public:
335 using iterator = typename super_type::iterator;
336 using value_type = typename super_type::value_type;
337
338 public:
339 unique_checker() : super_type() {}
340 unique_checker(const unique_checker &x) : super_type(x) {}
341 template <class InputIterator>
342 unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
343 unique_checker& operator=(const unique_checker&) = default;
344
345 // Insertion routines.
346 std::pair<iterator, bool> insert(const value_type &x) {
347 size_t size = this->tree_.size();
348 std::pair<typename CheckerType::iterator, bool> checker_res =
349 this->checker_.insert(x);
350 std::pair<iterator, bool> tree_res = this->tree_.insert(x);
351 CheckPairEquals(*tree_res.first, *checker_res.first);
352 EXPECT_EQ(tree_res.second, checker_res.second);
353 EXPECT_EQ(this->tree_.size(), this->checker_.size());
354 EXPECT_EQ(this->tree_.size(), size + tree_res.second);
355 return tree_res;
356 }
357 iterator insert(iterator position, const value_type &x) {
358 size_t size = this->tree_.size();
359 std::pair<typename CheckerType::iterator, bool> checker_res =
360 this->checker_.insert(x);
361 iterator tree_res = this->tree_.insert(position, x);
362 CheckPairEquals(*tree_res, *checker_res.first);
363 EXPECT_EQ(this->tree_.size(), this->checker_.size());
364 EXPECT_EQ(this->tree_.size(), size + checker_res.second);
365 return tree_res;
366 }
367 template <typename InputIterator>
368 void insert(InputIterator b, InputIterator e) {
369 for (; b != e; ++b) {
370 insert(*b);
371 }
372 }
373 };
374
375 // A checker for multiple sorted associative containers. TreeType is expected
376 // to be btree_{multiset,multimap} and CheckerType is expected to be
377 // {multiset,multimap}.
378 template <typename TreeType, typename CheckerType>
379 class multi_checker : public base_checker<TreeType, CheckerType> {
380 using super_type = base_checker<TreeType, CheckerType>;
381
382 public:
383 using iterator = typename super_type::iterator;
384 using value_type = typename super_type::value_type;
385
386 public:
387 multi_checker() : super_type() {}
388 multi_checker(const multi_checker &x) : super_type(x) {}
389 template <class InputIterator>
390 multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {}
391 multi_checker& operator=(const multi_checker&) = default;
392
393 // Insertion routines.
394 iterator insert(const value_type &x) {
395 size_t size = this->tree_.size();
396 auto checker_res = this->checker_.insert(x);
397 iterator tree_res = this->tree_.insert(x);
398 CheckPairEquals(*tree_res, *checker_res);
399 EXPECT_EQ(this->tree_.size(), this->checker_.size());
400 EXPECT_EQ(this->tree_.size(), size + 1);
401 return tree_res;
402 }
403 iterator insert(iterator position, const value_type &x) {
404 size_t size = this->tree_.size();
405 auto checker_res = this->checker_.insert(x);
406 iterator tree_res = this->tree_.insert(position, x);
407 CheckPairEquals(*tree_res, *checker_res);
408 EXPECT_EQ(this->tree_.size(), this->checker_.size());
409 EXPECT_EQ(this->tree_.size(), size + 1);
410 return tree_res;
411 }
412 template <typename InputIterator>
413 void insert(InputIterator b, InputIterator e) {
414 for (; b != e; ++b) {
415 insert(*b);
416 }
417 }
418 };
419
420 template <typename T, typename V>
421 void DoTest(const char *, T *b, const std::vector<V> &values) {
422 typename KeyOfValue<typename T::key_type, V>::type key_of_value;
423
424 T &mutable_b = *b;
425 const T &const_b = *b;
426
427 // Test insert.
428 for (size_t i = 0; i < values.size(); ++i) {
429 mutable_b.insert(values[i]);
430 mutable_b.value_check(values[i]);
431 }
432 ASSERT_EQ(mutable_b.size(), values.size());
433
434 const_b.verify();
435
436 // Test copy constructor.
437 T b_copy(const_b);
438 EXPECT_EQ(b_copy.size(), const_b.size());
439 for (size_t i = 0; i < values.size(); ++i) {
440 CheckPairEquals(*b_copy.find(key_of_value(values[i])), values[i]);
441 }
442
443 // Test range constructor.
444 T b_range(const_b.begin(), const_b.end());
445 EXPECT_EQ(b_range.size(), const_b.size());
446 for (size_t i = 0; i < values.size(); ++i) {
447 CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
448 }
449
450 // Test range insertion for values that already exist.
451 b_range.insert(b_copy.begin(), b_copy.end());
452 b_range.verify();
453
454 // Test range insertion for new values.
455 b_range.clear();
456 b_range.insert(b_copy.begin(), b_copy.end());
457 EXPECT_EQ(b_range.size(), b_copy.size());
458 for (size_t i = 0; i < values.size(); ++i) {
459 CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
460 }
461
462 // Test assignment to self. Nothing should change.
463 b_range.operator=(b_range);
464 EXPECT_EQ(b_range.size(), b_copy.size());
465
466 // Test assignment of new values.
467 b_range.clear();
468 b_range = b_copy;
469 EXPECT_EQ(b_range.size(), b_copy.size());
470
471 // Test swap.
472 b_range.clear();
473 b_range.swap(b_copy);
474 EXPECT_EQ(b_copy.size(), 0);
475 EXPECT_EQ(b_range.size(), const_b.size());
476 for (size_t i = 0; i < values.size(); ++i) {
477 CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
478 }
479 b_range.swap(b_copy);
480
481 // Test non-member function swap.
482 swap(b_range, b_copy);
483 EXPECT_EQ(b_copy.size(), 0);
484 EXPECT_EQ(b_range.size(), const_b.size());
485 for (size_t i = 0; i < values.size(); ++i) {
486 CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]);
487 }
488 swap(b_range, b_copy);
489
490 // Test erase via values.
491 for (size_t i = 0; i < values.size(); ++i) {
492 mutable_b.erase(key_of_value(values[i]));
493 // Erasing a non-existent key should have no effect.
494 ASSERT_EQ(mutable_b.erase(key_of_value(values[i])), 0);
495 }
496
497 const_b.verify();
498 EXPECT_EQ(const_b.size(), 0);
499
500 // Test erase via iterators.
501 mutable_b = b_copy;
502 for (size_t i = 0; i < values.size(); ++i) {
503 mutable_b.erase(mutable_b.find(key_of_value(values[i])));
504 }
505
506 const_b.verify();
507 EXPECT_EQ(const_b.size(), 0);
508
509 // Test insert with hint.
510 for (size_t i = 0; i < values.size(); i++) {
511 mutable_b.insert(mutable_b.upper_bound(key_of_value(values[i])), values[i]);
512 }
513
514 const_b.verify();
515
516 // Test range erase.
517 mutable_b.erase(mutable_b.begin(), mutable_b.end());
518 EXPECT_EQ(mutable_b.size(), 0);
519 const_b.verify();
520
521 // First half.
522 mutable_b = b_copy;
523 typename T::iterator mutable_iter_end = mutable_b.begin();
524 for (size_t i = 0; i < values.size() / 2; ++i) ++mutable_iter_end;
525 mutable_b.erase(mutable_b.begin(), mutable_iter_end);
526 EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 2);
527 const_b.verify();
528
529 // Second half.
530 mutable_b = b_copy;
531 typename T::iterator mutable_iter_begin = mutable_b.begin();
532 for (size_t i = 0; i < values.size() / 2; ++i) ++mutable_iter_begin;
533 mutable_b.erase(mutable_iter_begin, mutable_b.end());
534 EXPECT_EQ(mutable_b.size(), values.size() / 2);
535 const_b.verify();
536
537 // Second quarter.
538 mutable_b = b_copy;
539 mutable_iter_begin = mutable_b.begin();
540 for (size_t i = 0; i < values.size() / 4; ++i) ++mutable_iter_begin;
541 mutable_iter_end = mutable_iter_begin;
542 for (size_t i = 0; i < values.size() / 4; ++i) ++mutable_iter_end;
543 mutable_b.erase(mutable_iter_begin, mutable_iter_end);
544 EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 4);
545 const_b.verify();
546
547 mutable_b.clear();
548 }
549
550 template <typename T>
551 void ConstTest() {
552 using value_type = typename T::value_type;
553 typename KeyOfValue<typename T::key_type, value_type>::type key_of_value;
554
555 T mutable_b;
556 const T &const_b = mutable_b;
557
558 // Insert a single value into the container and test looking it up.
559 value_type value = Generator<value_type>(2)(2);
560 mutable_b.insert(value);
561 EXPECT_TRUE(mutable_b.contains(key_of_value(value)));
562 EXPECT_NE(mutable_b.find(key_of_value(value)), const_b.end());
563 EXPECT_TRUE(const_b.contains(key_of_value(value)));
564 EXPECT_NE(const_b.find(key_of_value(value)), mutable_b.end());
565 EXPECT_EQ(*const_b.lower_bound(key_of_value(value)), value);
566 EXPECT_EQ(const_b.upper_bound(key_of_value(value)), const_b.end());
567 EXPECT_EQ(*const_b.equal_range(key_of_value(value)).first, value);
568
569 // We can only create a non-const iterator from a non-const container.
570 typename T::iterator mutable_iter(mutable_b.begin());
571 EXPECT_EQ(mutable_iter, const_b.begin());
572 EXPECT_NE(mutable_iter, const_b.end());
573 EXPECT_EQ(const_b.begin(), mutable_iter);
574 EXPECT_NE(const_b.end(), mutable_iter);
575 typename T::reverse_iterator mutable_riter(mutable_b.rbegin());
576 EXPECT_EQ(mutable_riter, const_b.rbegin());
577 EXPECT_NE(mutable_riter, const_b.rend());
578 EXPECT_EQ(const_b.rbegin(), mutable_riter);
579 EXPECT_NE(const_b.rend(), mutable_riter);
580
581 // We can create a const iterator from a non-const iterator.
582 typename T::const_iterator const_iter(mutable_iter);
583 EXPECT_EQ(const_iter, mutable_b.begin());
584 EXPECT_NE(const_iter, mutable_b.end());
585 EXPECT_EQ(mutable_b.begin(), const_iter);
586 EXPECT_NE(mutable_b.end(), const_iter);
587 typename T::const_reverse_iterator const_riter(mutable_riter);
588 EXPECT_EQ(const_riter, mutable_b.rbegin());
589 EXPECT_NE(const_riter, mutable_b.rend());
590 EXPECT_EQ(mutable_b.rbegin(), const_riter);
591 EXPECT_NE(mutable_b.rend(), const_riter);
592
593 // Make sure various methods can be invoked on a const container.
594 const_b.verify();
595 ASSERT_TRUE(!const_b.empty());
596 EXPECT_EQ(const_b.size(), 1);
597 EXPECT_GT(const_b.max_size(), 0);
598 EXPECT_TRUE(const_b.contains(key_of_value(value)));
599 EXPECT_EQ(const_b.count(key_of_value(value)), 1);
600 }
601
602 template <typename T, typename C>
603 void BtreeTest() {
604 ConstTest<T>();
605
606 using V = typename remove_pair_const<typename T::value_type>::type;
607 const std::vector<V> random_values = GenerateValuesWithSeed<V>(
608 test_values, 4 * test_values,
609 GTEST_FLAG_GET(random_seed));
610
611 unique_checker<T, C> container;
612
613 // Test key insertion/deletion in sorted order.
614 std::vector<V> sorted_values(random_values);
615 std::sort(sorted_values.begin(), sorted_values.end());
616 DoTest("sorted: ", &container, sorted_values);
617
618 // Test key insertion/deletion in reverse sorted order.
619 std::reverse(sorted_values.begin(), sorted_values.end());
620 DoTest("rsorted: ", &container, sorted_values);
621
622 // Test key insertion/deletion in random order.
623 DoTest("random: ", &container, random_values);
624 }
625
626 template <typename T, typename C>
627 void BtreeMultiTest() {
628 ConstTest<T>();
629
630 using V = typename remove_pair_const<typename T::value_type>::type;
631 const std::vector<V> random_values = GenerateValuesWithSeed<V>(
632 test_values, 4 * test_values,
633 GTEST_FLAG_GET(random_seed));
634
635 multi_checker<T, C> container;
636
637 // Test keys in sorted order.
638 std::vector<V> sorted_values(random_values);
639 std::sort(sorted_values.begin(), sorted_values.end());
640 DoTest("sorted: ", &container, sorted_values);
641
642 // Test keys in reverse sorted order.
643 std::reverse(sorted_values.begin(), sorted_values.end());
644 DoTest("rsorted: ", &container, sorted_values);
645
646 // Test keys in random order.
647 DoTest("random: ", &container, random_values);
648
649 // Test keys in random order w/ duplicates.
650 std::vector<V> duplicate_values(random_values);
651 duplicate_values.insert(duplicate_values.end(), random_values.begin(),
652 random_values.end());
653 DoTest("duplicates:", &container, duplicate_values);
654
655 // Test all identical keys.
656 std::vector<V> identical_values(100);
657 std::fill(identical_values.begin(), identical_values.end(),
658 Generator<V>(2)(2));
659 DoTest("identical: ", &container, identical_values);
660 }
661
662 template <typename T>
663 struct PropagatingCountingAlloc : public CountingAllocator<T> {
664 using propagate_on_container_copy_assignment = std::true_type;
665 using propagate_on_container_move_assignment = std::true_type;
666 using propagate_on_container_swap = std::true_type;
667
668 using Base = CountingAllocator<T>;
669 using Base::Base;
670
671 template <typename U>
672 explicit PropagatingCountingAlloc(const PropagatingCountingAlloc<U> &other)
673 : Base(other.bytes_used_) {}
674
675 template <typename U>
676 struct rebind {
677 using other = PropagatingCountingAlloc<U>;
678 };
679 };
680
681 template <typename T>
682 void BtreeAllocatorTest() {
683 using value_type = typename T::value_type;
684
685 int64_t bytes1 = 0, bytes2 = 0;
686 PropagatingCountingAlloc<T> allocator1(&bytes1);
687 PropagatingCountingAlloc<T> allocator2(&bytes2);
688 Generator<value_type> generator(1000);
689
690 // Test that we allocate properly aligned memory. If we don't, then Layout
691 // will assert fail.
692 auto unused1 = allocator1.allocate(1);
693 auto unused2 = allocator2.allocate(1);
694
695 // Test copy assignment
696 {
697 T b1(typename T::key_compare(), allocator1);
698 T b2(typename T::key_compare(), allocator2);
699
700 int64_t original_bytes1 = bytes1;
701 b1.insert(generator(0));
702 EXPECT_GT(bytes1, original_bytes1);
703
704 // This should propagate the allocator.
705 b1 = b2;
706 EXPECT_EQ(b1.size(), 0);
707 EXPECT_EQ(b2.size(), 0);
708 EXPECT_EQ(bytes1, original_bytes1);
709
710 for (int i = 1; i < 1000; i++) {
711 b1.insert(generator(i));
712 }
713
714 // We should have allocated out of allocator2.
715 EXPECT_GT(bytes2, bytes1);
716 }
717
718 // Test move assignment
719 {
720 T b1(typename T::key_compare(), allocator1);
721 T b2(typename T::key_compare(), allocator2);
722
723 int64_t original_bytes1 = bytes1;
724 b1.insert(generator(0));
725 EXPECT_GT(bytes1, original_bytes1);
726
727 // This should propagate the allocator.
728 b1 = std::move(b2);
729 EXPECT_EQ(b1.size(), 0);
730 EXPECT_EQ(bytes1, original_bytes1);
731
732 for (int i = 1; i < 1000; i++) {
733 b1.insert(generator(i));
734 }
735
736 // We should have allocated out of allocator2.
737 EXPECT_GT(bytes2, bytes1);
738 }
739
740 // Test swap
741 {
742 T b1(typename T::key_compare(), allocator1);
743 T b2(typename T::key_compare(), allocator2);
744
745 int64_t original_bytes1 = bytes1;
746 b1.insert(generator(0));
747 EXPECT_GT(bytes1, original_bytes1);
748
749 // This should swap the allocators.
750 swap(b1, b2);
751 EXPECT_EQ(b1.size(), 0);
752 EXPECT_EQ(b2.size(), 1);
753 EXPECT_GT(bytes1, original_bytes1);
754
755 for (int i = 1; i < 1000; i++) {
756 b1.insert(generator(i));
757 }
758
759 // We should have allocated out of allocator2.
760 EXPECT_GT(bytes2, bytes1);
761 }
762
763 allocator1.deallocate(unused1, 1);
764 allocator2.deallocate(unused2, 1);
765 }
766
767 template <typename T>
768 void BtreeMapTest() {
769 using value_type = typename T::value_type;
770 using mapped_type = typename T::mapped_type;
771
772 mapped_type m = Generator<mapped_type>(0)(0);
773 (void)m;
774
775 T b;
776
777 // Verify we can insert using operator[].
778 for (int i = 0; i < 1000; i++) {
779 value_type v = Generator<value_type>(1000)(i);
780 b[v.first] = v.second;
781 }
782 EXPECT_EQ(b.size(), 1000);
783
784 // Test whether we can use the "->" operator on iterators and
785 // reverse_iterators. This stresses the btree_map_params::pair_pointer
786 // mechanism.
787 EXPECT_EQ(b.begin()->first, Generator<value_type>(1000)(0).first);
788 EXPECT_EQ(b.begin()->second, Generator<value_type>(1000)(0).second);
789 EXPECT_EQ(b.rbegin()->first, Generator<value_type>(1000)(999).first);
790 EXPECT_EQ(b.rbegin()->second, Generator<value_type>(1000)(999).second);
791 }
792
793 template <typename T>
794 void BtreeMultiMapTest() {
795 using mapped_type = typename T::mapped_type;
796 mapped_type m = Generator<mapped_type>(0)(0);
797 (void)m;
798 }
799
800 template <typename K, int N = 256>
801 void SetTest() {
802 using BtreeSet = phmap::btree_set<K>;
803 using CountingBtreeSet =
804 phmap::btree_set<K, std::less<K>, PropagatingCountingAlloc<K>>;
805 BtreeTest<BtreeSet, std::set<K>>();
806 BtreeAllocatorTest<CountingBtreeSet>();
807 }
808
809 template <typename K, int N = 256>
810 void MapTest() {
811 using BtreeMap = phmap::btree_map<K, K>;
812 using CountingBtreeMap =
813 phmap::btree_map<K, K, std::less<K>,
814 PropagatingCountingAlloc<std::pair<const K, K>>>;
815 BtreeTest<BtreeMap, std::map<K, K>>();
816 BtreeAllocatorTest<CountingBtreeMap>();
817 BtreeMapTest<BtreeMap>();
818 }
819
820 TEST(Btree, set_int32) { SetTest<int32_t>(); }
821 TEST(Btree, set_int64) { SetTest<int64_t>(); }
822 TEST(Btree, set_string) { SetTest<std::string>(); }
823 TEST(Btree, set_pair) { SetTest<std::pair<int, int>>(); }
824 TEST(Btree, map_int32) { MapTest<int32_t>(); }
825 TEST(Btree, map_int64) { MapTest<int64_t>(); }
826 TEST(Btree, map_string) { MapTest<std::string>(); }
827 TEST(Btree, map_pair) { MapTest<std::pair<int, int>>(); }
828
829 template <typename K, int N = 256>
830 void MultiSetTest() {
831 using BtreeMSet = phmap::btree_multiset<K>;
832 using CountingBtreeMSet =
833 phmap::btree_multiset<K, std::less<K>, PropagatingCountingAlloc<K>>;
834 BtreeMultiTest<BtreeMSet, std::multiset<K>>();
835 BtreeAllocatorTest<CountingBtreeMSet>();
836 }
837
838 template <typename K, int N = 256>
839 void MultiMapTest() {
840 using BtreeMMap = phmap::btree_multimap<K, K>;
841 using CountingBtreeMMap =
842 phmap::btree_multimap<K, K, std::less<K>,
843 PropagatingCountingAlloc<std::pair<const K, K>>>;
844 BtreeMultiTest<BtreeMMap, std::multimap<K, K>>();
845 BtreeMultiMapTest<BtreeMMap>();
846 BtreeAllocatorTest<CountingBtreeMMap>();
847 }
848
849 TEST(Btree, multiset_int32) { MultiSetTest<int32_t>(); }
850 TEST(Btree, multiset_int64) { MultiSetTest<int64_t>(); }
851 TEST(Btree, multiset_string) { MultiSetTest<std::string>(); }
852 TEST(Btree, multiset_pair) { MultiSetTest<std::pair<int, int>>(); }
853 TEST(Btree, multimap_int32) { MultiMapTest<int32_t>(); }
854 TEST(Btree, multimap_int64) { MultiMapTest<int64_t>(); }
855 TEST(Btree, multimap_string) { MultiMapTest<std::string>(); }
856 TEST(Btree, multimap_pair) { MultiMapTest<std::pair<int, int>>(); }
857
858 struct CompareIntToString {
859 bool operator()(const std::string &a, const std::string &b) const {
860 return a < b;
861 }
862 bool operator()(const std::string &a, int b) const {
863 return a < std::to_string(b);
864 }
865 bool operator()(int a, const std::string &b) const {
866 return std::to_string(a) < b;
867 }
868 using is_transparent = void;
869 };
870
871 struct NonTransparentCompare {
872 template <typename T, typename U>
873 bool operator()(const T& t, const U& u) const {
874 // Treating all comparators as transparent can cause inefficiencies (see
875 // N3657 C++ proposal). Test that for comparators without 'is_transparent'
876 // alias (like this one), we do not attempt heterogeneous lookup.
877 EXPECT_TRUE((std::is_same<T, U>()));
878 return t < u;
879 }
880 };
881
882 template <typename T>
883 bool CanEraseWithEmptyBrace(T t, decltype(t.erase({})) *) {
884 return true;
885 }
886
887 template <typename T>
888 bool CanEraseWithEmptyBrace(T, ...) {
889 return false;
890 }
891
892 template <typename T>
893 void TestHeterogeneous(T table) {
894 auto lb = table.lower_bound("3");
895 EXPECT_EQ(lb, table.lower_bound(3));
896 EXPECT_NE(lb, table.lower_bound(4));
897 EXPECT_EQ(lb, table.lower_bound({"3"}));
898 EXPECT_NE(lb, table.lower_bound({}));
899
900 auto ub = table.upper_bound("3");
901 EXPECT_EQ(ub, table.upper_bound(3));
902 EXPECT_NE(ub, table.upper_bound(5));
903 EXPECT_EQ(ub, table.upper_bound({"3"}));
904 EXPECT_NE(ub, table.upper_bound({}));
905
906 auto er = table.equal_range("3");
907 EXPECT_EQ(er, table.equal_range(3));
908 EXPECT_NE(er, table.equal_range(4));
909 EXPECT_EQ(er, table.equal_range({"3"}));
910 EXPECT_NE(er, table.equal_range({}));
911
912 auto it = table.find("3");
913 EXPECT_EQ(it, table.find(3));
914 EXPECT_NE(it, table.find(4));
915 EXPECT_EQ(it, table.find({"3"}));
916 EXPECT_NE(it, table.find({}));
917
918 EXPECT_TRUE(table.contains(3));
919 EXPECT_FALSE(table.contains(4));
920 EXPECT_TRUE(table.count({"3"}));
921 EXPECT_FALSE(table.contains({}));
922
923 EXPECT_EQ(1, table.count(3));
924 EXPECT_EQ(0, table.count(4));
925 EXPECT_EQ(1, table.count({"3"}));
926 EXPECT_EQ(0, table.count({}));
927
928 auto copy = table;
929 copy.erase(3);
930 EXPECT_EQ(table.size() - 1, copy.size());
931 copy.erase(4);
932 EXPECT_EQ(table.size() - 1, copy.size());
933 copy.erase({"5"});
934 EXPECT_EQ(table.size() - 2, copy.size());
935 EXPECT_FALSE(CanEraseWithEmptyBrace(table, nullptr));
936
937 // Also run it with const T&.
938 if (std::is_class<T>()) TestHeterogeneous<const T &>(table);
939 }
940
941 TEST(Btree, HeterogeneousLookup) {
942 TestHeterogeneous(btree_set<std::string, CompareIntToString>{"1", "3", "5"});
943 TestHeterogeneous(btree_map<std::string, int, CompareIntToString>{
944 {"1", 1}, {"3", 3}, {"5", 5}});
945 TestHeterogeneous(
946 btree_multiset<std::string, CompareIntToString>{"1", "3", "5"});
947 TestHeterogeneous(btree_multimap<std::string, int, CompareIntToString>{
948 {"1", 1}, {"3", 3}, {"5", 5}});
949
950 // Only maps have .at()
951 btree_map<std::string, int, CompareIntToString> map{
952 {"", -1}, {"1", 1}, {"3", 3}, {"5", 5}};
953 EXPECT_EQ(1, map.at(1));
954 EXPECT_EQ(3, map.at({"3"}));
955 EXPECT_EQ(-1, map.at({}));
956 const auto &cmap = map;
957 EXPECT_EQ(1, cmap.at(1));
958 EXPECT_EQ(3, cmap.at({"3"}));
959 EXPECT_EQ(-1, cmap.at({}));
960 }
961
962 TEST(Btree, NoHeterogeneousLookupWithoutAlias) {
963 using StringSet = phmap::btree_set<std::string, NonTransparentCompare>;
964 StringSet s;
965 ASSERT_TRUE(s.insert("hello").second);
966 ASSERT_TRUE(s.insert("world").second);
967 EXPECT_TRUE(s.end() == s.find("blah"));
968 EXPECT_TRUE(s.begin() == s.lower_bound("hello"));
969 EXPECT_EQ(1, s.count("world"));
970 EXPECT_TRUE(s.contains("hello"));
971 EXPECT_TRUE(s.contains("world"));
972 EXPECT_FALSE(s.contains("blah"));
973
974 using StringMultiSet =
975 phmap::btree_multiset<std::string, NonTransparentCompare>;
976 StringMultiSet ms;
977 ms.insert("hello");
978 ms.insert("world");
979 ms.insert("world");
980 EXPECT_TRUE(ms.end() == ms.find("blah"));
981 EXPECT_TRUE(ms.begin() == ms.lower_bound("hello"));
982 EXPECT_EQ(2, ms.count("world"));
983 EXPECT_TRUE(ms.contains("hello"));
984 EXPECT_TRUE(ms.contains("world"));
985 EXPECT_FALSE(ms.contains("blah"));
986 }
987
988 TEST(Btree, DefaultTransparent) {
989 {
990 // `int` does not have a default transparent comparator.
991 // The input value is converted to key_type.
992 btree_set<int> s = {1};
993 double d = 1.1;
994 EXPECT_EQ(s.begin(), s.find(d));
995 EXPECT_TRUE(s.contains(d));
996 }
997
998 {
999 // `std::string` has heterogeneous support.
1000 btree_set<std::string> s = {"A"};
1001 #if PHMAP_HAVE_STD_STRING_VIEW
1002 EXPECT_EQ(s.begin(), s.find(std::string_view("A")));
1003 EXPECT_TRUE(s.contains(std::string_view("A")));
1004 #endif
1005 }
1006 }
1007
1008 class StringLike {
1009 public:
1010 StringLike() = default;
1011
1012 StringLike(const char* s) : s_(s) { // NOLINT
1013 ++constructor_calls_;
1014 }
1015
1016 bool operator<(const StringLike& a) const {
1017 return s_ < a.s_;
1018 }
1019
1020 static void clear_constructor_call_count() {
1021 constructor_calls_ = 0;
1022 }
1023
1024 static int constructor_calls() {
1025 return constructor_calls_;
1026 }
1027
1028 private:
1029 static int constructor_calls_;
1030 std::string s_;
1031 };
1032
1033 int StringLike::constructor_calls_ = 0;
1034
1035 TEST(Btree, HeterogeneousLookupDoesntDegradePerformance) {
1036 using StringSet = phmap::btree_set<StringLike>;
1037 StringSet s;
1038 for (int i = 0; i < 100; ++i) {
1039 ASSERT_TRUE(s.insert(std::to_string(i).c_str()).second);
1040 }
1041 StringLike::clear_constructor_call_count();
1042 s.find("50");
1043 ASSERT_EQ(1, StringLike::constructor_calls());
1044
1045 StringLike::clear_constructor_call_count();
1046 s.contains("50");
1047 ASSERT_EQ(1, StringLike::constructor_calls());
1048
1049 StringLike::clear_constructor_call_count();
1050 s.count("50");
1051 ASSERT_EQ(1, StringLike::constructor_calls());
1052
1053 StringLike::clear_constructor_call_count();
1054 s.lower_bound("50");
1055 ASSERT_EQ(1, StringLike::constructor_calls());
1056
1057 StringLike::clear_constructor_call_count();
1058 s.upper_bound("50");
1059 ASSERT_EQ(1, StringLike::constructor_calls());
1060
1061 StringLike::clear_constructor_call_count();
1062 s.equal_range("50");
1063 ASSERT_EQ(1, StringLike::constructor_calls());
1064
1065 StringLike::clear_constructor_call_count();
1066 s.erase("50");
1067 ASSERT_EQ(1, StringLike::constructor_calls());
1068 }
1069
1070 // Verify that swapping btrees swaps the key comparison functors and that we can
1071 // use non-default constructible comparators.
1072 struct SubstringLess {
1073 SubstringLess() = delete;
1074 explicit SubstringLess(int length) : n(length) {}
1075 bool operator()(const std::string &a, const std::string &b) const {
1076 #if PHMAP_HAVE_STD_STRING_VIEW
1077 return std::string_view(a).substr(0, n) <
1078 std::string_view(b).substr(0, n);
1079 #else
1080 return a.substr(0, n) < b.substr(0, n);
1081 #endif
1082 }
1083 int n;
1084 };
1085
1086 TEST(Btree, SwapKeyCompare) {
1087 using SubstringSet = phmap::btree_set<std::string, SubstringLess>;
1088 SubstringSet s1(SubstringLess(1), SubstringSet::allocator_type());
1089 SubstringSet s2(SubstringLess(2), SubstringSet::allocator_type());
1090
1091 ASSERT_TRUE(s1.insert("a").second);
1092 ASSERT_FALSE(s1.insert("aa").second);
1093
1094 ASSERT_TRUE(s2.insert("a").second);
1095 ASSERT_TRUE(s2.insert("aa").second);
1096 ASSERT_FALSE(s2.insert("aaa").second);
1097
1098 swap(s1, s2);
1099
1100 ASSERT_TRUE(s1.insert("b").second);
1101 ASSERT_TRUE(s1.insert("bb").second);
1102 ASSERT_FALSE(s1.insert("bbb").second);
1103
1104 ASSERT_TRUE(s2.insert("b").second);
1105 ASSERT_FALSE(s2.insert("bb").second);
1106 }
1107
1108 TEST(Btree, UpperBoundRegression) {
1109 // Regress a bug where upper_bound would default-construct a new key_compare
1110 // instead of copying the existing one.
1111 using SubstringSet = phmap::btree_set<std::string, SubstringLess>;
1112 SubstringSet my_set(SubstringLess(3));
1113 my_set.insert("aab");
1114 my_set.insert("abb");
1115 // We call upper_bound("aaa"). If this correctly uses the length 3
1116 // comparator, aaa < aab < abb, so we should get aab as the result.
1117 // If it instead uses the default-constructed length 2 comparator,
1118 // aa == aa < ab, so we'll get abb as our result.
1119 SubstringSet::iterator it = my_set.upper_bound("aaa");
1120 ASSERT_TRUE(it != my_set.end());
1121 EXPECT_EQ("aab", *it);
1122 }
1123
1124 TEST(Btree, Comparison) {
1125 const int kSetSize = 1201;
1126 phmap::btree_set<int64_t> my_set;
1127 for (int i = 0; i < kSetSize; ++i) {
1128 my_set.insert(i);
1129 }
1130 phmap::btree_set<int64_t> my_set_copy(my_set);
1131 EXPECT_TRUE(my_set_copy == my_set);
1132 EXPECT_TRUE(my_set == my_set_copy);
1133 EXPECT_FALSE(my_set_copy != my_set);
1134 EXPECT_FALSE(my_set != my_set_copy);
1135
1136 my_set.insert(kSetSize);
1137 EXPECT_FALSE(my_set_copy == my_set);
1138 EXPECT_FALSE(my_set == my_set_copy);
1139 EXPECT_TRUE(my_set_copy != my_set);
1140 EXPECT_TRUE(my_set != my_set_copy);
1141
1142 my_set.erase(kSetSize - 1);
1143 EXPECT_FALSE(my_set_copy == my_set);
1144 EXPECT_FALSE(my_set == my_set_copy);
1145 EXPECT_TRUE(my_set_copy != my_set);
1146 EXPECT_TRUE(my_set != my_set_copy);
1147
1148 phmap::btree_map<std::string, int64_t> my_map;
1149 for (int i = 0; i < kSetSize; ++i) {
1150 my_map[std::string(i, 'a')] = i;
1151 }
1152 phmap::btree_map<std::string, int64_t> my_map_copy(my_map);
1153 EXPECT_TRUE(my_map_copy == my_map);
1154 EXPECT_TRUE(my_map == my_map_copy);
1155 EXPECT_FALSE(my_map_copy != my_map);
1156 EXPECT_FALSE(my_map != my_map_copy);
1157
1158 ++my_map_copy[std::string(7, 'a')];
1159 EXPECT_FALSE(my_map_copy == my_map);
1160 EXPECT_FALSE(my_map == my_map_copy);
1161 EXPECT_TRUE(my_map_copy != my_map);
1162 EXPECT_TRUE(my_map != my_map_copy);
1163
1164 my_map_copy = my_map;
1165 my_map["hello"] = kSetSize;
1166 EXPECT_FALSE(my_map_copy == my_map);
1167 EXPECT_FALSE(my_map == my_map_copy);
1168 EXPECT_TRUE(my_map_copy != my_map);
1169 EXPECT_TRUE(my_map != my_map_copy);
1170
1171 my_map.erase(std::string(kSetSize - 1, 'a'));
1172 EXPECT_FALSE(my_map_copy == my_map);
1173 EXPECT_FALSE(my_map == my_map_copy);
1174 EXPECT_TRUE(my_map_copy != my_map);
1175 EXPECT_TRUE(my_map != my_map_copy);
1176 }
1177
1178 TEST(Btree, RangeCtorSanity) {
1179 std::vector<int> ivec;
1180 ivec.push_back(1);
1181 std::map<int, int> imap;
1182 imap.insert(std::make_pair(1, 2));
1183 phmap::btree_multiset<int> tmset(ivec.begin(), ivec.end());
1184 phmap::btree_multimap<int, int> tmmap(imap.begin(), imap.end());
1185 phmap::btree_set<int> tset(ivec.begin(), ivec.end());
1186 phmap::btree_map<int, int> tmap(imap.begin(), imap.end());
1187 EXPECT_EQ(1, tmset.size());
1188 EXPECT_EQ(1, tmmap.size());
1189 EXPECT_EQ(1, tset.size());
1190 EXPECT_EQ(1, tmap.size());
1191 }
1192
1193 TEST(Btree, BtreeMapCanHoldMoveOnlyTypes) {
1194 phmap::btree_map<std::string, std::unique_ptr<std::string>> m;
1195
1196 std::unique_ptr<std::string> &v = m["A"];
1197 EXPECT_TRUE(v == nullptr);
1198 v.reset(new std::string("X"));
1199
1200 auto iter = m.find("A");
1201 EXPECT_EQ("X", *iter->second);
1202 }
1203
1204 TEST(Btree, InitializerListConstructor) {
1205 phmap::btree_set<std::string> set({"a", "b"});
1206 EXPECT_EQ(set.count("a"), 1);
1207 EXPECT_EQ(set.count("b"), 1);
1208
1209 phmap::btree_multiset<int> mset({1, 1, 4});
1210 EXPECT_EQ(mset.count(1), 2);
1211 EXPECT_EQ(mset.count(4), 1);
1212
1213 phmap::btree_map<int, int> map({{1, 5}, {2, 10}});
1214 EXPECT_EQ(map[1], 5);
1215 EXPECT_EQ(map[2], 10);
1216
1217 phmap::btree_multimap<int, int> mmap({{1, 5}, {1, 10}});
1218 auto range = mmap.equal_range(1);
1219 auto it = range.first;
1220 ASSERT_NE(it, range.second);
1221 EXPECT_EQ(it->second, 5);
1222 ASSERT_NE(++it, range.second);
1223 EXPECT_EQ(it->second, 10);
1224 EXPECT_EQ(++it, range.second);
1225 }
1226
1227 TEST(Btree, InitializerListInsert) {
1228 phmap::btree_set<std::string> set;
1229 set.insert({"a", "b"});
1230 EXPECT_EQ(set.count("a"), 1);
1231 EXPECT_EQ(set.count("b"), 1);
1232
1233 phmap::btree_multiset<int> mset;
1234 mset.insert({1, 1, 4});
1235 EXPECT_EQ(mset.count(1), 2);
1236 EXPECT_EQ(mset.count(4), 1);
1237
1238 phmap::btree_map<int, int> map;
1239 map.insert({{1, 5}, {2, 10}});
1240 // Test that inserting one element using an initializer list also works.
1241 map.insert({3, 15});
1242 EXPECT_EQ(map[1], 5);
1243 EXPECT_EQ(map[2], 10);
1244 EXPECT_EQ(map[3], 15);
1245
1246 phmap::btree_multimap<int, int> mmap;
1247 mmap.insert({{1, 5}, {1, 10}});
1248 auto range = mmap.equal_range(1);
1249 auto it = range.first;
1250 ASSERT_NE(it, range.second);
1251 EXPECT_EQ(it->second, 5);
1252 ASSERT_NE(++it, range.second);
1253 EXPECT_EQ(it->second, 10);
1254 EXPECT_EQ(++it, range.second);
1255 }
1256
1257 template <typename Compare, typename K>
1258 void AssertKeyCompareToAdapted() {
1259 using Adapted = typename key_compare_to_adapter<Compare>::type;
1260 static_assert(!std::is_same<Adapted, Compare>::value,
1261 "key_compare_to_adapter should have adapted this comparator.");
1262 static_assert(
1263 std::is_same<phmap::weak_ordering,
1264 phmap::invoke_result_t<Adapted, const K &, const K &>>::value,
1265 "Adapted comparator should be a key-compare-to comparator.");
1266 }
1267 template <typename Compare, typename K>
1268 void AssertKeyCompareToNotAdapted() {
1269 using Unadapted = typename key_compare_to_adapter<Compare>::type;
1270 static_assert(
1271 std::is_same<Unadapted, Compare>::value,
1272 "key_compare_to_adapter shouldn't have adapted this comparator.");
1273 static_assert(
1274 std::is_same<bool,
1275 phmap::invoke_result_t<Unadapted, const K &, const K &>>::value,
1276 "Un-adapted comparator should return bool.");
1277 }
1278
1279 TEST(Btree, KeyCompareToAdapter) {
1280 AssertKeyCompareToAdapted<std::less<std::string>, std::string>();
1281 AssertKeyCompareToAdapted<std::greater<std::string>, std::string>();
1282 #if PHMAP_HAVE_STD_STRING_VIEW
1283 AssertKeyCompareToAdapted<std::less<std::string_view>, std::string_view>();
1284 AssertKeyCompareToAdapted<std::greater<std::string_view>,
1285 std::string_view>();
1286 #endif
1287 AssertKeyCompareToNotAdapted<std::less<int>, int>();
1288 AssertKeyCompareToNotAdapted<std::greater<int>, int>();
1289 }
1290
1291 TEST(Btree, RValueInsert) {
1292 InstanceTracker tracker;
1293
1294 phmap::btree_set<MovableOnlyInstance> set;
1295 set.insert(MovableOnlyInstance(1));
1296 set.insert(MovableOnlyInstance(3));
1297 MovableOnlyInstance two(2);
1298 set.insert(set.find(MovableOnlyInstance(3)), std::move(two));
1299 auto it = set.find(MovableOnlyInstance(2));
1300 ASSERT_NE(it, set.end());
1301 ASSERT_NE(++it, set.end());
1302 EXPECT_EQ(it->value(), 3);
1303
1304 phmap::btree_multiset<MovableOnlyInstance> mset;
1305 MovableOnlyInstance zero(0);
1306 MovableOnlyInstance zero2(0);
1307 mset.insert(std::move(zero));
1308 mset.insert(mset.find(MovableOnlyInstance(0)), std::move(zero2));
1309 EXPECT_EQ(mset.count(MovableOnlyInstance(0)), 2);
1310
1311 phmap::btree_map<int, MovableOnlyInstance> map;
1312 std::pair<const int, MovableOnlyInstance> p1 = {1, MovableOnlyInstance(5)};
1313 std::pair<const int, MovableOnlyInstance> p2 = {2, MovableOnlyInstance(10)};
1314 std::pair<const int, MovableOnlyInstance> p3 = {3, MovableOnlyInstance(15)};
1315 map.insert(std::move(p1));
1316 map.insert(std::move(p3));
1317 map.insert(map.find(3), std::move(p2));
1318 ASSERT_NE(map.find(2), map.end());
1319 EXPECT_EQ(map.find(2)->second.value(), 10);
1320
1321 phmap::btree_multimap<int, MovableOnlyInstance> mmap;
1322 std::pair<const int, MovableOnlyInstance> p4 = {1, MovableOnlyInstance(5)};
1323 std::pair<const int, MovableOnlyInstance> p5 = {1, MovableOnlyInstance(10)};
1324 mmap.insert(std::move(p4));
1325 mmap.insert(mmap.find(1), std::move(p5));
1326 auto range = mmap.equal_range(1);
1327 auto it1 = range.first;
1328 ASSERT_NE(it1, range.second);
1329 EXPECT_EQ(it1->second.value(), 10);
1330 ASSERT_NE(++it1, range.second);
1331 EXPECT_EQ(it1->second.value(), 5);
1332 EXPECT_EQ(++it1, range.second);
1333
1334 EXPECT_EQ(tracker.copies(), 0);
1335 EXPECT_EQ(tracker.swaps(), 0);
1336 }
1337
1338 } // namespace
1339
1340 class BtreeNodePeer {
1341 public:
1342 // Yields the size of a leaf node with a specific number of values.
1343 template <typename ValueType>
1344 constexpr static size_t GetTargetNodeSize(size_t target_values_per_node) {
1345 return btree_node<
1346 set_params<ValueType, std::less<ValueType>, std::allocator<ValueType>,
1347 /*TargetNodeSize=*/256, // This parameter isn't used here.
1348 /*Multi=*/false>>::SizeWithNValues(target_values_per_node);
1349 }
1350
1351 // Yields the number of values in a (non-root) leaf node for this set.
1352 template <typename Set>
1353 constexpr static size_t GetNumValuesPerNode() {
1354 return btree_node<typename Set::params_type>::kNodeValues;
1355 }
1356 };
1357
1358 namespace {
1359
1360 // A btree set with a specific number of values per node.
1361 template <typename Key, int TargetValuesPerNode, typename Cmp = std::less<Key>>
1362 class SizedBtreeSet
1363 : public btree_set_container<btree<
1364 set_params<Key, Cmp, std::allocator<Key>,
1365 BtreeNodePeer::GetTargetNodeSize<Key>(TargetValuesPerNode),
1366 /*Multi=*/false>>> {
1367 using Base = typename SizedBtreeSet::btree_set_container;
1368
1369 public:
1370 SizedBtreeSet() {}
1371 using Base::Base;
1372 };
1373
1374 template <typename Set>
1375 void ExpectOperationCounts(const int expected_moves,
1376 const int expected_comparisons,
1377 const std::vector<int> &values,
1378 InstanceTracker *tracker, Set *set) {
1379 for (const int v : values) set->insert(MovableOnlyInstance(v));
1380 set->clear();
1381 EXPECT_EQ(tracker->moves(), expected_moves);
1382 EXPECT_EQ(tracker->comparisons(), expected_comparisons);
1383 EXPECT_EQ(tracker->copies(), 0);
1384 EXPECT_EQ(tracker->swaps(), 0);
1385 tracker->ResetCopiesMovesSwaps();
1386 }
1387
1388 // Note: when the values in this test change, it is expected to have an impact
1389 // on performance.
1390 TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
1391 InstanceTracker tracker;
1392 // Note: this is minimum number of values per node.
1393 SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/3> set3;
1394 // Note: this is the default number of values per node for a set of int32s
1395 // (with 64-bit pointers).
1396 SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/61> set61;
1397 SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/100> set100;
1398
1399 // Don't depend on flags for random values because then the expectations will
1400 // fail if the flags change.
1401 std::vector<int> values =
1402 GenerateValuesWithSeed<int>(10000, 1 << 22, /*seed=*/23);
1403
1404 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<decltype(set3)>(), 3);
1405 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<decltype(set61)>(), 61);
1406 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<decltype(set100)>(), 100);
1407 PHMAP_IF_CONSTEXPR (sizeof(void *) == 8) {
1408 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<phmap::btree_set<int32_t>>(),
1409 BtreeNodePeer::GetNumValuesPerNode<decltype(set61)>());
1410 }
1411
1412 // Test key insertion/deletion in random order.
1413 ExpectOperationCounts(45281, 132551, values, &tracker, &set3);
1414 ExpectOperationCounts(386718, 129807, values, &tracker, &set61);
1415 ExpectOperationCounts(586761, 130310, values, &tracker, &set100);
1416
1417 // Test key insertion/deletion in sorted order.
1418 std::sort(values.begin(), values.end());
1419 ExpectOperationCounts(26638, 92134, values, &tracker, &set3);
1420 ExpectOperationCounts(20208, 87757, values, &tracker, &set61);
1421 ExpectOperationCounts(20124, 96583, values, &tracker, &set100);
1422
1423 // Test key insertion/deletion in reverse sorted order.
1424 std::reverse(values.begin(), values.end());
1425 ExpectOperationCounts(49951, 119325, values, &tracker, &set3);
1426 ExpectOperationCounts(338813, 118266, values, &tracker, &set61);
1427 ExpectOperationCounts(534529, 125279, values, &tracker, &set100);
1428 }
1429
1430 struct MovableOnlyInstanceThreeWayCompare {
1431 phmap::weak_ordering operator()(const MovableOnlyInstance &a,
1432 const MovableOnlyInstance &b) const {
1433 return a.compare(b);
1434 }
1435 };
1436
1437 // Note: when the values in this test change, it is expected to have an impact
1438 // on performance.
1439 TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
1440 InstanceTracker tracker;
1441 // Note: this is minimum number of values per node.
1442 SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/3,
1443 MovableOnlyInstanceThreeWayCompare>
1444 set3;
1445 // Note: this is the default number of values per node for a set of int32s
1446 // (with 64-bit pointers).
1447 SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/61,
1448 MovableOnlyInstanceThreeWayCompare>
1449 set61;
1450 SizedBtreeSet<MovableOnlyInstance, /*TargetValuesPerNode=*/100,
1451 MovableOnlyInstanceThreeWayCompare>
1452 set100;
1453
1454 // Don't depend on flags for random values because then the expectations will
1455 // fail if the flags change.
1456 std::vector<int> values =
1457 GenerateValuesWithSeed<int>(10000, 1 << 22, /*seed=*/23);
1458
1459 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<decltype(set3)>(), 3);
1460 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<decltype(set61)>(), 61);
1461 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<decltype(set100)>(), 100);
1462 PHMAP_IF_CONSTEXPR (sizeof(void *) == 8) {
1463 EXPECT_EQ(BtreeNodePeer::GetNumValuesPerNode<phmap::btree_set<int32_t>>(),
1464 BtreeNodePeer::GetNumValuesPerNode<decltype(set61)>());
1465 }
1466
1467 // Test key insertion/deletion in random order.
1468 ExpectOperationCounts(45281, 122560, values, &tracker, &set3);
1469 ExpectOperationCounts(386718, 119816, values, &tracker, &set61);
1470 ExpectOperationCounts(586761, 120319, values, &tracker, &set100);
1471
1472 // Test key insertion/deletion in sorted order.
1473 std::sort(values.begin(), values.end());
1474 ExpectOperationCounts(26638, 92134, values, &tracker, &set3);
1475 ExpectOperationCounts(20208, 87757, values, &tracker, &set61);
1476 ExpectOperationCounts(20124, 96583, values, &tracker, &set100);
1477
1478 // Test key insertion/deletion in reverse sorted order.
1479 std::reverse(values.begin(), values.end());
1480 ExpectOperationCounts(49951, 109326, values, &tracker, &set3);
1481 ExpectOperationCounts(338813, 108267, values, &tracker, &set61);
1482 ExpectOperationCounts(534529, 115280, values, &tracker, &set100);
1483 }
1484
1485 struct NoDefaultCtor {
1486 int num;
1487 explicit NoDefaultCtor(int i) : num(i) {}
1488
1489 friend bool operator<(const NoDefaultCtor& a, const NoDefaultCtor& b) {
1490 return a.num < b.num;
1491 }
1492 };
1493
1494 TEST(Btree, BtreeMapCanHoldNoDefaultCtorTypes) {
1495 phmap::btree_map<NoDefaultCtor, NoDefaultCtor> m;
1496
1497 for (int i = 1; i <= 99; ++i) {
1498 SCOPED_TRACE(i);
1499 EXPECT_TRUE(m.emplace(NoDefaultCtor(i), NoDefaultCtor(100 - i)).second);
1500 }
1501 EXPECT_FALSE(m.emplace(NoDefaultCtor(78), NoDefaultCtor(0)).second);
1502
1503 auto iter99 = m.find(NoDefaultCtor(99));
1504 ASSERT_NE(iter99, m.end());
1505 EXPECT_EQ(iter99->second.num, 1);
1506
1507 auto iter1 = m.find(NoDefaultCtor(1));
1508 ASSERT_NE(iter1, m.end());
1509 EXPECT_EQ(iter1->second.num, 99);
1510
1511 auto iter50 = m.find(NoDefaultCtor(50));
1512 ASSERT_NE(iter50, m.end());
1513 EXPECT_EQ(iter50->second.num, 50);
1514
1515 auto iter25 = m.find(NoDefaultCtor(25));
1516 ASSERT_NE(iter25, m.end());
1517 EXPECT_EQ(iter25->second.num, 75);
1518 }
1519
1520 TEST(Btree, BtreeMultimapCanHoldNoDefaultCtorTypes) {
1521 phmap::btree_multimap<NoDefaultCtor, NoDefaultCtor> m;
1522
1523 for (int i = 1; i <= 99; ++i) {
1524 SCOPED_TRACE(i);
1525 m.emplace(NoDefaultCtor(i), NoDefaultCtor(100 - i));
1526 }
1527
1528 auto iter99 = m.find(NoDefaultCtor(99));
1529 ASSERT_NE(iter99, m.end());
1530 EXPECT_EQ(iter99->second.num, 1);
1531
1532 auto iter1 = m.find(NoDefaultCtor(1));
1533 ASSERT_NE(iter1, m.end());
1534 EXPECT_EQ(iter1->second.num, 99);
1535
1536 auto iter50 = m.find(NoDefaultCtor(50));
1537 ASSERT_NE(iter50, m.end());
1538 EXPECT_EQ(iter50->second.num, 50);
1539
1540 auto iter25 = m.find(NoDefaultCtor(25));
1541 ASSERT_NE(iter25, m.end());
1542 EXPECT_EQ(iter25->second.num, 75);
1543 }
1544
1545 TEST(Btree, MapAt) {
1546 phmap::btree_map<int, int> map = {{1, 2}, {2, 4}};
1547 EXPECT_EQ(map.at(1), 2);
1548 EXPECT_EQ(map.at(2), 4);
1549 map.at(2) = 8;
1550 const phmap::btree_map<int, int> &const_map = map;
1551 EXPECT_EQ(const_map.at(1), 2);
1552 EXPECT_EQ(const_map.at(2), 8);
1553 #ifdef PHMAP_HAVE_EXCEPTIONS
1554 EXPECT_THROW(map.at(3), std::out_of_range);
1555 #else
1556 EXPECT_DEATH(map.at(3), "phmap::btree_map::at");
1557 #endif
1558 }
1559
1560 TEST(Btree, BtreeMultisetEmplace) {
1561 const int value_to_insert = 123456;
1562 phmap::btree_multiset<int> s;
1563 auto iter = s.emplace(value_to_insert);
1564 ASSERT_NE(iter, s.end());
1565 EXPECT_EQ(*iter, value_to_insert);
1566 auto iter2 = s.emplace(value_to_insert);
1567 EXPECT_NE(iter2, iter);
1568 ASSERT_NE(iter2, s.end());
1569 EXPECT_EQ(*iter2, value_to_insert);
1570 auto result = s.equal_range(value_to_insert);
1571 EXPECT_EQ(std::distance(result.first, result.second), 2);
1572 }
1573
1574 TEST(Btree, BtreeMultisetEmplaceHint) {
1575 const int value_to_insert = 123456;
1576 phmap::btree_multiset<int> s;
1577 auto iter = s.emplace(value_to_insert);
1578 ASSERT_NE(iter, s.end());
1579 EXPECT_EQ(*iter, value_to_insert);
1580 auto emplace_iter = s.emplace_hint(iter, value_to_insert);
1581 EXPECT_NE(emplace_iter, iter);
1582 ASSERT_NE(emplace_iter, s.end());
1583 EXPECT_EQ(*emplace_iter, value_to_insert);
1584 }
1585
1586 TEST(Btree, BtreeMultimapEmplace) {
1587 const int key_to_insert = 123456;
1588 const char value0[] = "a";
1589 phmap::btree_multimap<int, std::string> s;
1590 auto iter = s.emplace(key_to_insert, value0);
1591 ASSERT_NE(iter, s.end());
1592 EXPECT_EQ(iter->first, key_to_insert);
1593 EXPECT_EQ(iter->second, value0);
1594 const char value1[] = "b";
1595 auto iter2 = s.emplace(key_to_insert, value1);
1596 EXPECT_NE(iter2, iter);
1597 ASSERT_NE(iter2, s.end());
1598 EXPECT_EQ(iter2->first, key_to_insert);
1599 EXPECT_EQ(iter2->second, value1);
1600 auto result = s.equal_range(key_to_insert);
1601 EXPECT_EQ(std::distance(result.first, result.second), 2);
1602 }
1603
1604 TEST(Btree, BtreeMultimapEmplaceHint) {
1605 const int key_to_insert = 123456;
1606 const char value0[] = "a";
1607 phmap::btree_multimap<int, std::string> s;
1608 auto iter = s.emplace(key_to_insert, value0);
1609 ASSERT_NE(iter, s.end());
1610 EXPECT_EQ(iter->first, key_to_insert);
1611 EXPECT_EQ(iter->second, value0);
1612 const char value1[] = "b";
1613 auto emplace_iter = s.emplace_hint(iter, key_to_insert, value1);
1614 EXPECT_NE(emplace_iter, iter);
1615 ASSERT_NE(emplace_iter, s.end());
1616 EXPECT_EQ(emplace_iter->first, key_to_insert);
1617 EXPECT_EQ(emplace_iter->second, value1);
1618 }
1619
1620 TEST(Btree, ConstIteratorAccessors) {
1621 phmap::btree_set<int> set;
1622 for (int i = 0; i < 100; ++i) {
1623 set.insert(i);
1624 }
1625
1626 auto it = set.cbegin();
1627 auto r_it = set.crbegin();
1628 for (int i = 0; i < 100; ++i, ++it, ++r_it) {
1629 ASSERT_EQ(*it, i);
1630 ASSERT_EQ(*r_it, 99 - i);
1631 }
1632 EXPECT_EQ(it, set.cend());
1633 EXPECT_EQ(r_it, set.crend());
1634 }
1635
1636 #if 0
1637 TEST(Btree, StrSplitCompatible) {
1638 const phmap::btree_set<std::string> split_set = phmap::StrSplit("a,b,c", ',');
1639 const phmap::btree_set<std::string> expected_set = {"a", "b", "c"};
1640
1641 EXPECT_EQ(split_set, expected_set);
1642 }
1643 #endif
1644
1645 // We can't use EXPECT_EQ/etc. to compare phmap::weak_ordering because they
1646 // convert literal 0 to int and phmap::weak_ordering can only be compared with
1647 // literal 0. Defining this function allows for avoiding ClangTidy warnings.
1648 bool Identity(const bool b) { return b; }
1649
1650 TEST(Btree, ValueComp) {
1651 phmap::btree_set<int> s;
1652 EXPECT_TRUE(s.value_comp()(1, 2));
1653 EXPECT_FALSE(s.value_comp()(2, 2));
1654 EXPECT_FALSE(s.value_comp()(2, 1));
1655
1656 phmap::btree_map<int, int> m1;
1657 EXPECT_TRUE(m1.value_comp()(std::make_pair(1, 0), std::make_pair(2, 0)));
1658 EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(2, 0)));
1659 EXPECT_FALSE(m1.value_comp()(std::make_pair(2, 0), std::make_pair(1, 0)));
1660
1661 phmap::btree_map<std::string, int> m2;
1662 EXPECT_TRUE(Identity(
1663 m2.value_comp()(std::make_pair("a", 0), std::make_pair("b", 0)) < 0));
1664 EXPECT_TRUE(Identity(
1665 m2.value_comp()(std::make_pair("b", 0), std::make_pair("b", 0)) == 0));
1666 EXPECT_TRUE(Identity(
1667 m2.value_comp()(std::make_pair("b", 0), std::make_pair("a", 0)) > 0));
1668 }
1669
1670 TEST(Btree, DefaultConstruction) {
1671 phmap::btree_set<int> s;
1672 phmap::btree_map<int, int> m;
1673 phmap::btree_multiset<int> ms;
1674 phmap::btree_multimap<int, int> mm;
1675
1676 EXPECT_TRUE(s.empty());
1677 EXPECT_TRUE(m.empty());
1678 EXPECT_TRUE(ms.empty());
1679 EXPECT_TRUE(mm.empty());
1680 }
1681
1682 #if 0
1683 TEST(Btree, SwissTableHashable) {
1684 static constexpr int kValues = 10000;
1685 std::vector<int> values(kValues);
1686 std::iota(values.begin(), values.end(), 0);
1687 std::vector<std::pair<int, int>> map_values;
1688 for (int v : values) map_values.emplace_back(v, -v);
1689
1690 using set = phmap::btree_set<int>;
1691 EXPECT_TRUE(phmap::VerifyTypeImplementsPhmapHashCorrectly({
1692 set{},
1693 set{1},
1694 set{2},
1695 set{1, 2},
1696 set{2, 1},
1697 set(values.begin(), values.end()),
1698 set(values.rbegin(), values.rend()),
1699 }));
1700
1701 using mset = phmap::btree_multiset<int>;
1702 EXPECT_TRUE(phmap::VerifyTypeImplementsPhmapHashCorrectly({
1703 mset{},
1704 mset{1},
1705 mset{1, 1},
1706 mset{2},
1707 mset{2, 2},
1708 mset{1, 2},
1709 mset{1, 1, 2},
1710 mset{1, 2, 2},
1711 mset{1, 1, 2, 2},
1712 mset(values.begin(), values.end()),
1713 mset(values.rbegin(), values.rend()),
1714 }));
1715
1716 using map = phmap::btree_map<int, int>;
1717 EXPECT_TRUE(phmap::VerifyTypeImplementsPhmapHashCorrectly({
1718 map{},
1719 map{{1, 0}},
1720 map{{1, 1}},
1721 map{{2, 0}},
1722 map{{2, 2}},
1723 map{{1, 0}, {2, 1}},
1724 map(map_values.begin(), map_values.end()),
1725 map(map_values.rbegin(), map_values.rend()),
1726 }));
1727
1728 using mmap = phmap::btree_multimap<int, int>;
1729 EXPECT_TRUE(phmap::VerifyTypeImplementsPhmapHashCorrectly({
1730 mmap{},
1731 mmap{{1, 0}},
1732 mmap{{1, 1}},
1733 mmap{{1, 0}, {1, 1}},
1734 mmap{{1, 1}, {1, 0}},
1735 mmap{{2, 0}},
1736 mmap{{2, 2}},
1737 mmap{{1, 0}, {2, 1}},
1738 mmap(map_values.begin(), map_values.end()),
1739 mmap(map_values.rbegin(), map_values.rend()),
1740 }));
1741 }
1742 #endif
1743
1744 TEST(Btree, ComparableSet) {
1745 phmap::btree_set<int> s1 = {1, 2};
1746 phmap::btree_set<int> s2 = {2, 3};
1747 EXPECT_LT(s1, s2);
1748 EXPECT_LE(s1, s2);
1749 EXPECT_LE(s1, s1);
1750 EXPECT_GT(s2, s1);
1751 EXPECT_GE(s2, s1);
1752 EXPECT_GE(s1, s1);
1753 }
1754
1755 TEST(Btree, ComparableSetsDifferentLength) {
1756 phmap::btree_set<int> s1 = {1, 2};
1757 phmap::btree_set<int> s2 = {1, 2, 3};
1758 EXPECT_LT(s1, s2);
1759 EXPECT_LE(s1, s2);
1760 EXPECT_GT(s2, s1);
1761 EXPECT_GE(s2, s1);
1762 }
1763
1764 TEST(Btree, ComparableMultiset) {
1765 phmap::btree_multiset<int> s1 = {1, 2};
1766 phmap::btree_multiset<int> s2 = {2, 3};
1767 EXPECT_LT(s1, s2);
1768 EXPECT_LE(s1, s2);
1769 EXPECT_LE(s1, s1);
1770 EXPECT_GT(s2, s1);
1771 EXPECT_GE(s2, s1);
1772 EXPECT_GE(s1, s1);
1773 }
1774
1775 TEST(Btree, ComparableMap) {
1776 phmap::btree_map<int, int> s1 = {{1, 2}};
1777 phmap::btree_map<int, int> s2 = {{2, 3}};
1778 EXPECT_LT(s1, s2);
1779 EXPECT_LE(s1, s2);
1780 EXPECT_LE(s1, s1);
1781 EXPECT_GT(s2, s1);
1782 EXPECT_GE(s2, s1);
1783 EXPECT_GE(s1, s1);
1784 }
1785
1786 TEST(Btree, ComparableMultimap) {
1787 phmap::btree_multimap<int, int> s1 = {{1, 2}};
1788 phmap::btree_multimap<int, int> s2 = {{2, 3}};
1789 EXPECT_LT(s1, s2);
1790 EXPECT_LE(s1, s2);
1791 EXPECT_LE(s1, s1);
1792 EXPECT_GT(s2, s1);
1793 EXPECT_GE(s2, s1);
1794 EXPECT_GE(s1, s1);
1795 }
1796
1797 TEST(Btree, ComparableSetWithCustomComparator) {
1798 // As specified by
1799 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf section
1800 // [container.requirements.general].12, ordering associative containers always
1801 // uses default '<' operator
1802 // - even if otherwise the container uses custom functor.
1803 phmap::btree_set<int, std::greater<int>> s1 = {1, 2};
1804 phmap::btree_set<int, std::greater<int>> s2 = {2, 3};
1805 EXPECT_LT(s1, s2);
1806 EXPECT_LE(s1, s2);
1807 EXPECT_LE(s1, s1);
1808 EXPECT_GT(s2, s1);
1809 EXPECT_GE(s2, s1);
1810 EXPECT_GE(s1, s1);
1811 }
1812
1813 TEST(Btree, EraseReturnsIterator) {
1814 phmap::btree_set<int> set = {1, 2, 3, 4, 5};
1815 auto result_it = set.erase(set.begin(), set.find(3));
1816 EXPECT_EQ(result_it, set.find(3));
1817 result_it = set.erase(set.find(5));
1818 EXPECT_EQ(result_it, set.end());
1819 }
1820
1821 TEST(Btree, ExtractAndInsertNodeHandleSet) {
1822 phmap::btree_set<int> src1 = {1, 2, 3, 4, 5};
1823 auto nh = src1.extract(src1.find(3));
1824 EXPECT_THAT(src1, ElementsAre(1, 2, 4, 5));
1825 phmap::btree_set<int> other;
1826 phmap::btree_set<int>::insert_return_type res = other.insert(std::move(nh));
1827 EXPECT_THAT(other, ElementsAre(3));
1828 EXPECT_EQ(res.position, other.find(3));
1829 EXPECT_TRUE(res.inserted);
1830 EXPECT_TRUE(res.node.empty());
1831
1832 phmap::btree_set<int> src2 = {3, 4};
1833 nh = src2.extract(src2.find(3));
1834 EXPECT_THAT(src2, ElementsAre(4));
1835 res = other.insert(std::move(nh));
1836 EXPECT_THAT(other, ElementsAre(3));
1837 EXPECT_EQ(res.position, other.find(3));
1838 EXPECT_FALSE(res.inserted);
1839 ASSERT_FALSE(res.node.empty());
1840 EXPECT_EQ(res.node.value(), 3);
1841 }
1842
1843 template <typename Set>
1844 void TestExtractWithTrackingForSet() {
1845 InstanceTracker tracker;
1846 {
1847 Set s;
1848 // Add enough elements to make sure we test internal nodes too.
1849 const size_t kSize = 1000;
1850 while (s.size() < kSize) {
1851 s.insert(MovableOnlyInstance(s.size()));
1852 }
1853 for (size_t i = 0; i < kSize; ++i) {
1854 // Extract with key
1855 auto nh = s.extract(MovableOnlyInstance(i));
1856 EXPECT_EQ(s.size(), kSize - 1);
1857 EXPECT_EQ(nh.value().value(), i);
1858 // Insert with node
1859 s.insert(std::move(nh));
1860 EXPECT_EQ(s.size(), kSize);
1861
1862 // Extract with iterator
1863 auto it = s.find(MovableOnlyInstance(i));
1864 nh = s.extract(it);
1865 EXPECT_EQ(s.size(), kSize - 1);
1866 EXPECT_EQ(nh.value().value(), i);
1867 // Insert with node and hint
1868 s.insert(s.begin(), std::move(nh));
1869 EXPECT_EQ(s.size(), kSize);
1870 }
1871 }
1872 EXPECT_EQ(0, tracker.instances());
1873 }
1874
1875 template <typename Map>
1876 void TestExtractWithTrackingForMap() {
1877 InstanceTracker tracker;
1878 {
1879 Map m;
1880 // Add enough elements to make sure we test internal nodes too.
1881 const size_t kSize = 1000;
1882 while (m.size() < kSize) {
1883 m.insert(
1884 {CopyableMovableInstance(m.size()), MovableOnlyInstance(m.size())});
1885 }
1886 for (size_t i = 0; i < kSize; ++i) {
1887 // Extract with key
1888 auto nh = m.extract(CopyableMovableInstance(i));
1889 EXPECT_EQ(m.size(), kSize - 1);
1890 EXPECT_EQ(nh.key().value(), i);
1891 EXPECT_EQ(nh.mapped().value(), i);
1892 // Insert with node
1893 m.insert(std::move(nh));
1894 EXPECT_EQ(m.size(), kSize);
1895
1896 // Extract with iterator
1897 auto it = m.find(CopyableMovableInstance(i));
1898 nh = m.extract(it);
1899 EXPECT_EQ(m.size(), kSize - 1);
1900 EXPECT_EQ(nh.key().value(), i);
1901 EXPECT_EQ(nh.mapped().value(), i);
1902 // Insert with node and hint
1903 m.insert(m.begin(), std::move(nh));
1904 EXPECT_EQ(m.size(), kSize);
1905 }
1906 }
1907 EXPECT_EQ(0, tracker.instances());
1908 }
1909
1910 TEST(Btree, ExtractTracking) {
1911 TestExtractWithTrackingForSet<phmap::btree_set<MovableOnlyInstance>>();
1912 TestExtractWithTrackingForSet<phmap::btree_multiset<MovableOnlyInstance>>();
1913 TestExtractWithTrackingForMap<
1914 phmap::btree_map<CopyableMovableInstance, MovableOnlyInstance>>();
1915 TestExtractWithTrackingForMap<
1916 phmap::btree_multimap<CopyableMovableInstance, MovableOnlyInstance>>();
1917 }
1918
1919 TEST(Btree, ExtractAndInsertNodeHandleMultiSet) {
1920 phmap::btree_multiset<int> src1 = {1, 2, 3, 3, 4, 5};
1921 auto nh = src1.extract(src1.find(3));
1922 EXPECT_THAT(src1, ElementsAre(1, 2, 3, 4, 5));
1923 phmap::btree_multiset<int> other;
1924 auto res = other.insert(std::move(nh));
1925 EXPECT_THAT(other, ElementsAre(3));
1926 EXPECT_EQ(res, other.find(3));
1927
1928 phmap::btree_multiset<int> src2 = {3, 4};
1929 nh = src2.extract(src2.find(3));
1930 EXPECT_THAT(src2, ElementsAre(4));
1931 res = other.insert(std::move(nh));
1932 EXPECT_THAT(other, ElementsAre(3, 3));
1933 EXPECT_EQ(res, ++other.find(3));
1934 }
1935
1936 TEST(Btree, ExtractAndInsertNodeHandleMap) {
1937 phmap::btree_map<int, int> src1 = {{1, 2}, {3, 4}, {5, 6}};
1938 auto nh = src1.extract(src1.find(3));
1939 EXPECT_THAT(src1, ElementsAre(Pair(1, 2), Pair(5, 6)));
1940 phmap::btree_map<int, int> other;
1941 phmap::btree_map<int, int>::insert_return_type res =
1942 other.insert(std::move(nh));
1943 EXPECT_THAT(other, ElementsAre(Pair(3, 4)));
1944 EXPECT_EQ(res.position, other.find(3));
1945 EXPECT_TRUE(res.inserted);
1946 EXPECT_TRUE(res.node.empty());
1947
1948 phmap::btree_map<int, int> src2 = {{3, 6}};
1949 nh = src2.extract(src2.find(3));
1950 EXPECT_TRUE(src2.empty());
1951 res = other.insert(std::move(nh));
1952 EXPECT_THAT(other, ElementsAre(Pair(3, 4)));
1953 EXPECT_EQ(res.position, other.find(3));
1954 EXPECT_FALSE(res.inserted);
1955 ASSERT_FALSE(res.node.empty());
1956 EXPECT_EQ(res.node.key(), 3);
1957 EXPECT_EQ(res.node.mapped(), 6);
1958 }
1959
1960 TEST(Btree, ExtractAndInsertNodeHandleMultiMap) {
1961 phmap::btree_multimap<int, int> src1 = {{1, 2}, {3, 4}, {5, 6}};
1962 auto nh = src1.extract(src1.find(3));
1963 EXPECT_THAT(src1, ElementsAre(Pair(1, 2), Pair(5, 6)));
1964 phmap::btree_multimap<int, int> other;
1965 auto res = other.insert(std::move(nh));
1966 EXPECT_THAT(other, ElementsAre(Pair(3, 4)));
1967 EXPECT_EQ(res, other.find(3));
1968
1969 phmap::btree_multimap<int, int> src2 = {{3, 6}};
1970 nh = src2.extract(src2.find(3));
1971 EXPECT_TRUE(src2.empty());
1972 res = other.insert(std::move(nh));
1973 EXPECT_THAT(other, ElementsAre(Pair(3, 4), Pair(3, 6)));
1974 EXPECT_EQ(res, ++other.begin());
1975 }
1976
1977 // For multisets, insert with hint also affects correctness because we need to
1978 // insert immediately before the hint if possible.
1979 struct InsertMultiHintData {
1980 int key;
1981 int not_key;
1982 bool operator==(const InsertMultiHintData other) const {
1983 return key == other.key && not_key == other.not_key;
1984 }
1985 };
1986
1987 struct InsertMultiHintDataKeyCompare {
1988 using is_transparent = void;
1989 bool operator()(const InsertMultiHintData a,
1990 const InsertMultiHintData b) const {
1991 return a.key < b.key;
1992 }
1993 bool operator()(const int a, const InsertMultiHintData b) const {
1994 return a < b.key;
1995 }
1996 bool operator()(const InsertMultiHintData a, const int b) const {
1997 return a.key < b;
1998 }
1999 };
2000
2001 TEST(Btree, InsertHintNodeHandle) {
2002 // For unique sets, insert with hint is just a performance optimization.
2003 // Test that insert works correctly when the hint is right or wrong.
2004 {
2005 phmap::btree_set<int> src = {1, 2, 3, 4, 5};
2006 auto nh = src.extract(src.find(3));
2007 EXPECT_THAT(src, ElementsAre(1, 2, 4, 5));
2008 phmap::btree_set<int> other = {0, 100};
2009 // Test a correct hint.
2010 auto it = other.insert(other.lower_bound(3), std::move(nh));
2011 EXPECT_THAT(other, ElementsAre(0, 3, 100));
2012 EXPECT_EQ(it, other.find(3));
2013
2014 nh = src.extract(src.find(5));
2015 // Test an incorrect hint.
2016 it = other.insert(other.end(), std::move(nh));
2017 EXPECT_THAT(other, ElementsAre(0, 3, 5, 100));
2018 EXPECT_EQ(it, other.find(5));
2019 }
2020
2021 phmap::btree_multiset<InsertMultiHintData, InsertMultiHintDataKeyCompare> src =
2022 {{1, 2}, {3, 4}, {3, 5}};
2023 auto nh = src.extract(src.lower_bound(3));
2024 EXPECT_EQ(nh.value(), (InsertMultiHintData{3, 4}));
2025 phmap::btree_multiset<InsertMultiHintData, InsertMultiHintDataKeyCompare>
2026 other = {{3, 1}, {3, 2}, {3, 3}};
2027 auto it = other.insert(--other.end(), std::move(nh));
2028 EXPECT_THAT(
2029 other, ElementsAre(InsertMultiHintData{3, 1}, InsertMultiHintData{3, 2},
2030 InsertMultiHintData{3, 4}, InsertMultiHintData{3, 3}));
2031 EXPECT_EQ(it, --(--other.end()));
2032
2033 nh = src.extract(src.find(3));
2034 EXPECT_EQ(nh.value(), (InsertMultiHintData{3, 5}));
2035 it = other.insert(other.begin(), std::move(nh));
2036 EXPECT_THAT(other,
2037 ElementsAre(InsertMultiHintData{3, 5}, InsertMultiHintData{3, 1},
2038 InsertMultiHintData{3, 2}, InsertMultiHintData{3, 4},
2039 InsertMultiHintData{3, 3}));
2040 EXPECT_EQ(it, other.begin());
2041 }
2042
2043 struct IntCompareToCmp {
2044 phmap::weak_ordering operator()(int a, int b) const {
2045 if (a < b) return phmap::weak_ordering::less;
2046 if (a > b) return phmap::weak_ordering::greater;
2047 return phmap::weak_ordering::equivalent;
2048 }
2049 };
2050
2051 TEST(Btree, MergeIntoUniqueContainers) {
2052 phmap::btree_set<int, IntCompareToCmp> src1 = {1, 2, 3};
2053 phmap::btree_multiset<int> src2 = {3, 4, 4, 5};
2054 phmap::btree_set<int> dst;
2055
2056 dst.merge(src1);
2057 EXPECT_TRUE(src1.empty());
2058 EXPECT_THAT(dst, ElementsAre(1, 2, 3));
2059 dst.merge(src2);
2060 EXPECT_THAT(src2, ElementsAre(3, 4));
2061 EXPECT_THAT(dst, ElementsAre(1, 2, 3, 4, 5));
2062 }
2063
2064 TEST(Btree, MergeIntoUniqueContainersWithCompareTo) {
2065 phmap::btree_set<int, IntCompareToCmp> src1 = {1, 2, 3};
2066 phmap::btree_multiset<int> src2 = {3, 4, 4, 5};
2067 phmap::btree_set<int, IntCompareToCmp> dst;
2068
2069 dst.merge(src1);
2070 EXPECT_TRUE(src1.empty());
2071 EXPECT_THAT(dst, ElementsAre(1, 2, 3));
2072 dst.merge(src2);
2073 EXPECT_THAT(src2, ElementsAre(3, 4));
2074 EXPECT_THAT(dst, ElementsAre(1, 2, 3, 4, 5));
2075 }
2076
2077 TEST(Btree, MergeIntoMultiContainers) {
2078 phmap::btree_set<int, IntCompareToCmp> src1 = {1, 2, 3};
2079 phmap::btree_multiset<int> src2 = {3, 4, 4, 5};
2080 phmap::btree_multiset<int> dst;
2081
2082 dst.merge(src1);
2083 EXPECT_TRUE(src1.empty());
2084 EXPECT_THAT(dst, ElementsAre(1, 2, 3));
2085 dst.merge(src2);
2086 EXPECT_TRUE(src2.empty());
2087 EXPECT_THAT(dst, ElementsAre(1, 2, 3, 3, 4, 4, 5));
2088 }
2089
2090 TEST(Btree, MergeIntoMultiContainersWithCompareTo) {
2091 phmap::btree_set<int, IntCompareToCmp> src1 = {1, 2, 3};
2092 phmap::btree_multiset<int> src2 = {3, 4, 4, 5};
2093 phmap::btree_multiset<int, IntCompareToCmp> dst;
2094
2095 dst.merge(src1);
2096 EXPECT_TRUE(src1.empty());
2097 EXPECT_THAT(dst, ElementsAre(1, 2, 3));
2098 dst.merge(src2);
2099 EXPECT_TRUE(src2.empty());
2100 EXPECT_THAT(dst, ElementsAre(1, 2, 3, 3, 4, 4, 5));
2101 }
2102
2103 TEST(Btree, MergeIntoMultiMapsWithDifferentComparators) {
2104 phmap::btree_map<int, int, IntCompareToCmp> src1 = {{1, 1}, {2, 2}, {3, 3}};
2105 phmap::btree_multimap<int, int, std::greater<int>> src2 = {
2106 {5, 5}, {4, 1}, {4, 4}, {3, 2}};
2107 phmap::btree_multimap<int, int> dst;
2108
2109 dst.merge(src1);
2110 EXPECT_TRUE(src1.empty());
2111 EXPECT_THAT(dst, ElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3)));
2112 dst.merge(src2);
2113 EXPECT_TRUE(src2.empty());
2114 EXPECT_THAT(dst, ElementsAre(Pair(1, 1), Pair(2, 2), Pair(3, 3), Pair(3, 2),
2115 Pair(4, 1), Pair(4, 4), Pair(5, 5)));
2116 }
2117
2118 struct KeyCompareToWeakOrdering {
2119 template <typename T>
2120 phmap::weak_ordering operator()(const T &a, const T &b) const {
2121 return a < b ? phmap::weak_ordering::less
2122 : a == b ? phmap::weak_ordering::equivalent
2123 : phmap::weak_ordering::greater;
2124 }
2125 };
2126
2127 struct KeyCompareToStrongOrdering {
2128 template <typename T>
2129 phmap::strong_ordering operator()(const T &a, const T &b) const {
2130 return a < b ? phmap::strong_ordering::less
2131 : a == b ? phmap::strong_ordering::equal
2132 : phmap::strong_ordering::greater;
2133 }
2134 };
2135
2136 TEST(Btree, UserProvidedKeyCompareToComparators) {
2137 phmap::btree_set<int, KeyCompareToWeakOrdering> weak_set = {1, 2, 3};
2138 EXPECT_TRUE(weak_set.contains(2));
2139 EXPECT_FALSE(weak_set.contains(4));
2140
2141 phmap::btree_set<int, KeyCompareToStrongOrdering> strong_set = {1, 2, 3};
2142 EXPECT_TRUE(strong_set.contains(2));
2143 EXPECT_FALSE(strong_set.contains(4));
2144 }
2145
2146 TEST(Btree, TryEmplaceBasicTest) {
2147 phmap::btree_map<int, std::string> m;
2148
2149 // Should construct a std::string from the literal.
2150 m.try_emplace(1, "one");
2151 EXPECT_EQ(1, m.size());
2152
2153 // Try other std::string constructors and const lvalue key.
2154 const int key(42);
2155 m.try_emplace(key, 3, 'a');
2156 m.try_emplace(2, std::string("two"));
2157
2158 EXPECT_TRUE(std::is_sorted(m.begin(), m.end()));
2159 EXPECT_THAT(m, ElementsAreArray(std::vector<std::pair<int, std::string>>{
2160 {1, "one"}, {2, "two"}, {42, "aaa"}}));
2161 }
2162
2163 TEST(Btree, TryEmplaceWithHintWorks) {
2164 // Use a counting comparator here to verify that hint is used.
2165 int calls = 0;
2166 auto cmp = [&calls](int x, int y) {
2167 ++calls;
2168 return x < y;
2169 };
2170 using Cmp = decltype(cmp);
2171
2172 phmap::btree_map<int, int, Cmp> m(cmp);
2173 for (int i = 0; i < 128; ++i) {
2174 m.emplace(i, i);
2175 }
2176
2177 // Sanity check for the comparator
2178 calls = 0;
2179 m.emplace(127, 127);
2180 EXPECT_GE(calls, 4);
2181
2182 // Try with begin hint:
2183 calls = 0;
2184 auto it = m.try_emplace(m.begin(), -1, -1);
2185 EXPECT_EQ(129, m.size());
2186 EXPECT_EQ(it, m.begin());
2187 EXPECT_LE(calls, 2);
2188
2189 // Try with end hint:
2190 calls = 0;
2191 std::pair<int, int> pair1024 = {1024, 1024};
2192 it = m.try_emplace(m.end(), pair1024.first, pair1024.second);
2193 EXPECT_EQ(130, m.size());
2194 EXPECT_EQ(it, --m.end());
2195 EXPECT_LE(calls, 2);
2196
2197 // Try value already present, bad hint; ensure no duplicate added:
2198 calls = 0;
2199 it = m.try_emplace(m.end(), 16, 17);
2200 EXPECT_EQ(130, m.size());
2201 EXPECT_GE(calls, 4);
2202 EXPECT_EQ(it, m.find(16));
2203
2204 // Try value already present, hint points directly to it:
2205 calls = 0;
2206 it = m.try_emplace(it, 16, 17);
2207 EXPECT_EQ(130, m.size());
2208 EXPECT_LE(calls, 2);
2209 EXPECT_EQ(it, m.find(16));
2210
2211 m.erase(2);
2212 EXPECT_EQ(129, m.size());
2213 auto hint = m.find(3);
2214 // Try emplace in the middle of two other elements.
2215 calls = 0;
2216 m.try_emplace(hint, 2, 2);
2217 EXPECT_EQ(130, m.size());
2218 EXPECT_LE(calls, 2);
2219
2220 EXPECT_TRUE(std::is_sorted(m.begin(), m.end()));
2221 }
2222
2223 TEST(Btree, TryEmplaceWithBadHint) {
2224 phmap::btree_map<int, int> m = {{1, 1}, {9, 9}};
2225
2226 // Bad hint (too small), should still emplace:
2227 auto it = m.try_emplace(m.begin(), 2, 2);
2228 EXPECT_EQ(it, ++m.begin());
2229 EXPECT_THAT(m, ElementsAreArray(
2230 std::vector<std::pair<int, int>>{{1, 1}, {2, 2}, {9, 9}}));
2231
2232 // Bad hint, too large this time:
2233 it = m.try_emplace(++(++m.begin()), 0, 0);
2234 EXPECT_EQ(it, m.begin());
2235 EXPECT_THAT(m, ElementsAreArray(std::vector<std::pair<int, int>>{
2236 {0, 0}, {1, 1}, {2, 2}, {9, 9}}));
2237 }
2238
2239 TEST(Btree, TryEmplaceMaintainsSortedOrder) {
2240 phmap::btree_map<int, std::string> m;
2241 std::pair<int, std::string> pair5 = {5, "five"};
2242
2243 // Test both lvalue & rvalue emplace.
2244 m.try_emplace(10, "ten");
2245 m.try_emplace(pair5.first, pair5.second);
2246 EXPECT_EQ(2, m.size());
2247 EXPECT_TRUE(std::is_sorted(m.begin(), m.end()));
2248
2249 int int100{100};
2250 m.try_emplace(int100, "hundred");
2251 m.try_emplace(1, "one");
2252 EXPECT_EQ(4, m.size());
2253 EXPECT_TRUE(std::is_sorted(m.begin(), m.end()));
2254 }
2255
2256 TEST(Btree, TryEmplaceWithHintAndNoValueArgsWorks) {
2257 phmap::btree_map<int, int> m;
2258 m.try_emplace(m.end(), 1);
2259 EXPECT_EQ(0, m[1]);
2260 }
2261
2262 TEST(Btree, TryEmplaceWithHintAndMultipleValueArgsWorks) {
2263 phmap::btree_map<int, std::string> m;
2264 m.try_emplace(m.end(), 1, 10, 'a');
2265 EXPECT_EQ(std::string(10, 'a'), m[1]);
2266 }
2267
2268 TEST(Btree, MoveAssignmentAllocatorPropagation) {
2269 InstanceTracker tracker;
2270
2271 int64_t bytes1 = 0, bytes2 = 0;
2272 PropagatingCountingAlloc<MovableOnlyInstance> allocator1(&bytes1);
2273 PropagatingCountingAlloc<MovableOnlyInstance> allocator2(&bytes2);
2274 std::less<MovableOnlyInstance> cmp;
2275
2276 // Test propagating allocator_type.
2277 {
2278 phmap::btree_set<MovableOnlyInstance, std::less<MovableOnlyInstance>,
2279 PropagatingCountingAlloc<MovableOnlyInstance>>
2280 set1(cmp, allocator1), set2(cmp, allocator2);
2281
2282 for (int i = 0; i < 100; ++i) set1.insert(MovableOnlyInstance(i));
2283
2284 tracker.ResetCopiesMovesSwaps();
2285 set2 = std::move(set1);
2286 EXPECT_EQ(tracker.moves(), 0);
2287 }
2288 // Test non-propagating allocator_type with equal allocators.
2289 {
2290 phmap::btree_set<MovableOnlyInstance, std::less<MovableOnlyInstance>,
2291 CountingAllocator<MovableOnlyInstance>>
2292 set1(cmp, allocator1), set2(cmp, allocator1);
2293
2294 for (int i = 0; i < 100; ++i) set1.insert(MovableOnlyInstance(i));
2295
2296 tracker.ResetCopiesMovesSwaps();
2297 set2 = std::move(set1);
2298 EXPECT_EQ(tracker.moves(), 0);
2299 }
2300 // Test non-propagating allocator_type with different allocators.
2301 {
2302 phmap::btree_set<MovableOnlyInstance, std::less<MovableOnlyInstance>,
2303 CountingAllocator<MovableOnlyInstance>>
2304 set1(cmp, allocator1), set2(cmp, allocator2);
2305
2306 for (int i = 0; i < 100; ++i) set1.insert(MovableOnlyInstance(i));
2307
2308 tracker.ResetCopiesMovesSwaps();
2309 set2 = std::move(set1);
2310 EXPECT_GE(tracker.moves(), 100);
2311 }
2312 }
2313
2314 TEST(Btree, EmptyTree) {
2315 phmap::btree_set<int> s;
2316 EXPECT_TRUE(s.empty());
2317 EXPECT_EQ(s.size(), 0);
2318 EXPECT_GT(s.max_size(), 0);
2319 }
2320
2321 bool IsEven(int k) { return k % 2 == 0; }
2322
2323 TEST(Btree, EraseIf) {
2324 // Test that erase_if works with all the container types and supports lambdas.
2325 {
2326 phmap::btree_set<int> s = {1, 3, 5, 6, 100};
2327 erase_if(s, [](int k) { return k > 3; });
2328 EXPECT_THAT(s, ElementsAre(1, 3));
2329 }
2330 {
2331 phmap::btree_multiset<int> s = {1, 3, 3, 5, 6, 6, 100};
2332 erase_if(s, [](int k) { return k <= 3; });
2333 EXPECT_THAT(s, ElementsAre(5, 6, 6, 100));
2334 }
2335 {
2336 phmap::btree_map<int, int> m = {{1, 1}, {3, 3}, {6, 6}, {100, 100}};
2337 erase_if(m, [](std::pair<const int, int> kv) { return kv.first > 3; });
2338 EXPECT_THAT(m, ElementsAre(Pair(1, 1), Pair(3, 3)));
2339 }
2340 {
2341 phmap::btree_multimap<int, int> m = {{1, 1}, {3, 3}, {3, 6},
2342 {6, 6}, {6, 7}, {100, 6}};
2343 erase_if(m, [](std::pair<const int, int> kv) { return kv.second == 6; });
2344 EXPECT_THAT(m, ElementsAre(Pair(1, 1), Pair(3, 3), Pair(6, 7)));
2345 }
2346 // Test that erasing all elements from a large set works and test support for
2347 // function pointers.
2348 {
2349 phmap::btree_set<int> s;
2350 for (int i = 0; i < 1000; ++i) s.insert(2 * i);
2351 erase_if(s, IsEven);
2352 EXPECT_THAT(s, IsEmpty());
2353 }
2354 // Test that erase_if supports other format of function pointers.
2355 {
2356 phmap::btree_set<int> s = {1, 3, 5, 6, 100};
2357 erase_if(s, &IsEven);
2358 EXPECT_THAT(s, ElementsAre(1, 3, 5));
2359 }
2360 }
2361
2362 } // namespace
2363 } // namespace priv
2364 } // namespace phmap