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