1 /*
2 * Copyright (c) 2021 The WebRTC project authors. All Rights Reserved.
3 *
4 * Use of this source code is governed by a BSD-style license
5 * that can be found in the LICENSE file in the root of the source
6 * tree. An additional intellectual property rights grant can be found
7 * in the file PATENTS. All contributing project authors may
8 * be found in the AUTHORS file in the root of the source tree.
9 */
10
11 // This implementation is borrowed from Chromium.
12
13 #include "rtc_base/containers/flat_set.h"
14
15 #include <algorithm>
16 #include <string>
17 #include <utility>
18 #include <vector>
19
20 #include "rtc_base/containers/move_only_int.h"
21 #include "test/gmock.h"
22 #include "test/gtest.h"
23
24 // A flat_set is basically a interface to flat_tree. So several basic
25 // operations are tested to make sure things are set up properly, but the bulk
26 // of the tests are in flat_tree_unittests.cc.
27
28 using ::testing::ElementsAre;
29
30 namespace webrtc {
31 namespace {
32
TEST(FlatSet,IncompleteType)33 TEST(FlatSet, IncompleteType) {
34 struct A {
35 using Set = flat_set<A>;
36 int data;
37 Set set_with_incomplete_type;
38 Set::iterator it;
39 Set::const_iterator cit;
40
41 // We do not declare operator< because clang complains that it's unused.
42 };
43
44 A a;
45 }
46
TEST(FlatSet,RangeConstructor)47 TEST(FlatSet, RangeConstructor) {
48 flat_set<int>::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3};
49
50 flat_set<int> cont(std::begin(input_vals), std::end(input_vals));
51 EXPECT_THAT(cont, ElementsAre(1, 2, 3));
52 }
53
TEST(FlatSet,MoveConstructor)54 TEST(FlatSet, MoveConstructor) {
55 int input_range[] = {1, 2, 3, 4};
56
57 flat_set<MoveOnlyInt> original(std::begin(input_range),
58 std::end(input_range));
59 flat_set<MoveOnlyInt> moved(std::move(original));
60
61 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
62 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
63 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
64 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
65 }
66
TEST(FlatSet,InitializerListConstructor)67 TEST(FlatSet, InitializerListConstructor) {
68 flat_set<int> cont({1, 2, 3, 4, 5, 6, 10, 8});
69 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
70 }
71
TEST(FlatSet,InsertFindSize)72 TEST(FlatSet, InsertFindSize) {
73 flat_set<int> s;
74 s.insert(1);
75 s.insert(1);
76 s.insert(2);
77
78 EXPECT_EQ(2u, s.size());
79 EXPECT_EQ(1, *s.find(1));
80 EXPECT_EQ(2, *s.find(2));
81 EXPECT_EQ(s.end(), s.find(7));
82 }
83
TEST(FlatSet,CopySwap)84 TEST(FlatSet, CopySwap) {
85 flat_set<int> original;
86 original.insert(1);
87 original.insert(2);
88 EXPECT_THAT(original, ElementsAre(1, 2));
89
90 flat_set<int> copy(original);
91 EXPECT_THAT(copy, ElementsAre(1, 2));
92
93 copy.erase(copy.begin());
94 copy.insert(10);
95 EXPECT_THAT(copy, ElementsAre(2, 10));
96
97 original.swap(copy);
98 EXPECT_THAT(original, ElementsAre(2, 10));
99 EXPECT_THAT(copy, ElementsAre(1, 2));
100 }
101
TEST(FlatSet,UsingTransparentCompare)102 TEST(FlatSet, UsingTransparentCompare) {
103 using ExplicitInt = webrtc::MoveOnlyInt;
104 flat_set<ExplicitInt> s;
105 const auto& s1 = s;
106 int x = 0;
107
108 // Check if we can use lookup functions without converting to key_type.
109 // Correctness is checked in flat_tree tests.
110 s.count(x);
111 s1.count(x);
112 s.find(x);
113 s1.find(x);
114 s.equal_range(x);
115 s1.equal_range(x);
116 s.lower_bound(x);
117 s1.lower_bound(x);
118 s.upper_bound(x);
119 s1.upper_bound(x);
120 s.erase(x);
121
122 // Check if we broke overload resolution.
123 s.emplace(0);
124 s.emplace(1);
125 s.erase(s.begin());
126 s.erase(s.cbegin());
127 }
128
TEST(FlatSet,SupportsEraseIf)129 TEST(FlatSet, SupportsEraseIf) {
130 flat_set<MoveOnlyInt> s;
131 s.emplace(MoveOnlyInt(1));
132 s.emplace(MoveOnlyInt(2));
133 s.emplace(MoveOnlyInt(3));
134 s.emplace(MoveOnlyInt(4));
135 s.emplace(MoveOnlyInt(5));
136
137 EraseIf(s, [to_be_removed = MoveOnlyInt(2)](const MoveOnlyInt& elem) {
138 return elem == to_be_removed;
139 });
140
141 EXPECT_EQ(s.size(), 4u);
142 ASSERT_TRUE(s.find(MoveOnlyInt(1)) != s.end());
143 ASSERT_FALSE(s.find(MoveOnlyInt(2)) != s.end());
144 ASSERT_TRUE(s.find(MoveOnlyInt(3)) != s.end());
145 ASSERT_TRUE(s.find(MoveOnlyInt(4)) != s.end());
146 ASSERT_TRUE(s.find(MoveOnlyInt(5)) != s.end());
147 }
148 } // namespace
149 } // namespace webrtc
150