1 // Copyright 2012 The Chromium Authors. All rights reserved.
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/stl_util.h"
6
7 #include <array>
8 #include <deque>
9 #include <forward_list>
10 #include <functional>
11 #include <initializer_list>
12 #include <iterator>
13 #include <list>
14 #include <map>
15 #include <queue>
16 #include <set>
17 #include <stack>
18 #include <string>
19 #include <type_traits>
20 #include <unordered_map>
21 #include <unordered_set>
22 #include <vector>
23
24 #include "base/containers/queue.h"
25 #include "base/strings/string16.h"
26 #include "base/strings/utf_string_conversions.h"
27 #include "testing/gmock/include/gmock/gmock.h"
28 #include "testing/gtest/include/gtest/gtest.h"
29
30 namespace {
31
32 // Used as test case to ensure the various base::STLXxx functions don't require
33 // more than operators "<" and "==" on values stored in containers.
34 class ComparableValue {
35 public:
ComparableValue(int value)36 explicit ComparableValue(int value) : value_(value) {}
37
operator ==(const ComparableValue & rhs) const38 bool operator==(const ComparableValue& rhs) const {
39 return value_ == rhs.value_;
40 }
41
operator <(const ComparableValue & rhs) const42 bool operator<(const ComparableValue& rhs) const {
43 return value_ < rhs.value_;
44 }
45
46 private:
47 int value_;
48 };
49
50 template <typename Container>
RunEraseTest()51 void RunEraseTest() {
52 const std::pair<Container, Container> test_data[] = {
53 {Container(), Container()}, {{1, 2, 3}, {1, 3}}, {{1, 2, 3, 2}, {1, 3}}};
54
55 for (auto test_case : test_data) {
56 base::Erase(test_case.first, 2);
57 EXPECT_EQ(test_case.second, test_case.first);
58 }
59 }
60
61 // This test is written for containers of std::pair<int, int> to support maps.
62 template <typename Container>
RunEraseIfTest()63 void RunEraseIfTest() {
64 struct {
65 Container input;
66 Container erase_even;
67 Container erase_odd;
68 } test_data[] = {
69 {Container(), Container(), Container()},
70 {{{1, 1}, {2, 2}, {3, 3}}, {{1, 1}, {3, 3}}, {{2, 2}}},
71 {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}, {{1, 1}, {3, 3}}, {{2, 2}, {4, 4}}},
72 };
73
74 for (auto test_case : test_data) {
75 base::EraseIf(test_case.input, [](const std::pair<int, int>& elem) {
76 return !(elem.first & 1);
77 });
78 EXPECT_EQ(test_case.erase_even, test_case.input);
79 }
80
81 for (auto test_case : test_data) {
82 base::EraseIf(test_case.input, [](const std::pair<int, int>& elem) {
83 return elem.first & 1;
84 });
85 EXPECT_EQ(test_case.erase_odd, test_case.input);
86 }
87 }
88
89 struct CustomIntHash {
operator ()__anoncff81e220111::CustomIntHash90 size_t operator()(int elem) const { return std::hash<int>()(elem) + 1; }
91 };
92
93 struct HashByFirst {
operator ()__anoncff81e220111::HashByFirst94 size_t operator()(const std::pair<int, int>& elem) const {
95 return std::hash<int>()(elem.first);
96 }
97 };
98
99 } // namespace
100
101 namespace base {
102 namespace {
103
TEST(STLUtilTest,Size)104 TEST(STLUtilTest, Size) {
105 {
106 std::vector<int> vector = {1, 2, 3, 4, 5};
107 static_assert(
108 std::is_same<decltype(base::size(vector)),
109 decltype(vector.size())>::value,
110 "base::size(vector) should have the same type as vector.size()");
111 EXPECT_EQ(vector.size(), base::size(vector));
112 }
113
114 {
115 std::string empty_str;
116 static_assert(
117 std::is_same<decltype(base::size(empty_str)),
118 decltype(empty_str.size())>::value,
119 "base::size(empty_str) should have the same type as empty_str.size()");
120 EXPECT_EQ(0u, base::size(empty_str));
121 }
122
123 {
124 std::array<int, 4> array = {{1, 2, 3, 4}};
125 static_assert(
126 std::is_same<decltype(base::size(array)),
127 decltype(array.size())>::value,
128 "base::size(array) should have the same type as array.size()");
129 static_assert(base::size(array) == array.size(),
130 "base::size(array) should be equal to array.size()");
131 }
132
133 {
134 int array[] = {1, 2, 3};
135 static_assert(std::is_same<size_t, decltype(base::size(array))>::value,
136 "base::size(array) should be of type size_t");
137 static_assert(3u == base::size(array), "base::size(array) should be 3");
138 }
139 }
140
TEST(STLUtilTest,Empty)141 TEST(STLUtilTest, Empty) {
142 {
143 std::vector<int> vector;
144 static_assert(
145 std::is_same<decltype(base::empty(vector)),
146 decltype(vector.empty())>::value,
147 "base::empty(vector) should have the same type as vector.empty()");
148 EXPECT_EQ(vector.empty(), base::empty(vector));
149 }
150
151 {
152 std::array<int, 4> array = {{1, 2, 3, 4}};
153 static_assert(
154 std::is_same<decltype(base::empty(array)),
155 decltype(array.empty())>::value,
156 "base::empty(array) should have the same type as array.empty()");
157 static_assert(base::empty(array) == array.empty(),
158 "base::empty(array) should be equal to array.empty()");
159 }
160
161 {
162 int array[] = {1, 2, 3};
163 static_assert(std::is_same<bool, decltype(base::empty(array))>::value,
164 "base::empty(array) should be of type bool");
165 static_assert(!base::empty(array), "base::empty(array) should be false");
166 }
167
168 {
169 constexpr std::initializer_list<int> il;
170 static_assert(std::is_same<bool, decltype(base::empty(il))>::value,
171 "base::empty(il) should be of type bool");
172 static_assert(base::empty(il), "base::empty(il) should be true");
173 }
174 }
175
TEST(STLUtilTest,Data)176 TEST(STLUtilTest, Data) {
177 {
178 std::vector<int> vector = {1, 2, 3, 4, 5};
179 static_assert(
180 std::is_same<decltype(base::data(vector)),
181 decltype(vector.data())>::value,
182 "base::data(vector) should have the same type as vector.data()");
183 EXPECT_EQ(vector.data(), base::data(vector));
184 }
185
186 {
187 const std::string cstr = "const string";
188 static_assert(
189 std::is_same<decltype(base::data(cstr)), decltype(cstr.data())>::value,
190 "base::data(cstr) should have the same type as cstr.data()");
191
192 EXPECT_EQ(cstr.data(), base::data(cstr));
193 }
194
195 {
196 std::string str = "mutable string";
197 static_assert(std::is_same<decltype(base::data(str)), char*>::value,
198 "base::data(str) should be of type char*");
199 EXPECT_EQ(str.data(), base::data(str));
200 }
201
202 {
203 std::string empty_str;
204 static_assert(std::is_same<decltype(base::data(empty_str)), char*>::value,
205 "base::data(empty_str) should be of type char*");
206 EXPECT_EQ(empty_str.data(), base::data(empty_str));
207 }
208
209 {
210 std::array<int, 4> array = {{1, 2, 3, 4}};
211 static_assert(
212 std::is_same<decltype(base::data(array)),
213 decltype(array.data())>::value,
214 "base::data(array) should have the same type as array.data()");
215 // std::array::data() is not constexpr prior to C++17, hence the runtime
216 // check.
217 EXPECT_EQ(array.data(), base::data(array));
218 }
219
220 {
221 constexpr int array[] = {1, 2, 3};
222 static_assert(std::is_same<const int*, decltype(base::data(array))>::value,
223 "base::data(array) should be of type const int*");
224 static_assert(array == base::data(array),
225 "base::data(array) should be array");
226 }
227
228 {
229 constexpr std::initializer_list<int> il;
230 static_assert(
231 std::is_same<decltype(il.begin()), decltype(base::data(il))>::value,
232 "base::data(il) should have the same type as il.begin()");
233 static_assert(il.begin() == base::data(il),
234 "base::data(il) should be equal to il.begin()");
235 }
236 }
237
TEST(STLUtilTest,GetUnderlyingContainer)238 TEST(STLUtilTest, GetUnderlyingContainer) {
239 {
240 std::queue<int> queue({1, 2, 3, 4, 5});
241 static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
242 const std::deque<int>&>::value,
243 "GetUnderlyingContainer(queue) should be of type deque");
244 EXPECT_THAT(GetUnderlyingContainer(queue),
245 testing::ElementsAre(1, 2, 3, 4, 5));
246 }
247
248 {
249 std::queue<int> queue;
250 EXPECT_THAT(GetUnderlyingContainer(queue), testing::ElementsAre());
251 }
252
253 {
254 base::queue<int> queue({1, 2, 3, 4, 5});
255 static_assert(
256 std::is_same<decltype(GetUnderlyingContainer(queue)),
257 const base::circular_deque<int>&>::value,
258 "GetUnderlyingContainer(queue) should be of type circular_deque");
259 EXPECT_THAT(GetUnderlyingContainer(queue),
260 testing::ElementsAre(1, 2, 3, 4, 5));
261 }
262
263 {
264 std::vector<int> values = {1, 2, 3, 4, 5};
265 std::priority_queue<int> queue(values.begin(), values.end());
266 static_assert(std::is_same<decltype(GetUnderlyingContainer(queue)),
267 const std::vector<int>&>::value,
268 "GetUnderlyingContainer(queue) should be of type vector");
269 EXPECT_THAT(GetUnderlyingContainer(queue),
270 testing::UnorderedElementsAre(1, 2, 3, 4, 5));
271 }
272
273 {
274 std::stack<int> stack({1, 2, 3, 4, 5});
275 static_assert(std::is_same<decltype(GetUnderlyingContainer(stack)),
276 const std::deque<int>&>::value,
277 "GetUnderlyingContainer(stack) should be of type deque");
278 EXPECT_THAT(GetUnderlyingContainer(stack),
279 testing::ElementsAre(1, 2, 3, 4, 5));
280 }
281 }
282
TEST(STLUtilTest,STLIsSorted)283 TEST(STLUtilTest, STLIsSorted) {
284 {
285 std::set<int> set;
286 set.insert(24);
287 set.insert(1);
288 set.insert(12);
289 EXPECT_TRUE(STLIsSorted(set));
290 }
291
292 {
293 std::set<ComparableValue> set;
294 set.insert(ComparableValue(24));
295 set.insert(ComparableValue(1));
296 set.insert(ComparableValue(12));
297 EXPECT_TRUE(STLIsSorted(set));
298 }
299
300 {
301 std::vector<int> vector;
302 vector.push_back(1);
303 vector.push_back(1);
304 vector.push_back(4);
305 vector.push_back(64);
306 vector.push_back(12432);
307 EXPECT_TRUE(STLIsSorted(vector));
308 vector.back() = 1;
309 EXPECT_FALSE(STLIsSorted(vector));
310 }
311 }
312
TEST(STLUtilTest,STLSetDifference)313 TEST(STLUtilTest, STLSetDifference) {
314 std::set<int> a1;
315 a1.insert(1);
316 a1.insert(2);
317 a1.insert(3);
318 a1.insert(4);
319
320 std::set<int> a2;
321 a2.insert(3);
322 a2.insert(4);
323 a2.insert(5);
324 a2.insert(6);
325 a2.insert(7);
326
327 {
328 std::set<int> difference;
329 difference.insert(1);
330 difference.insert(2);
331 EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a1, a2));
332 }
333
334 {
335 std::set<int> difference;
336 difference.insert(5);
337 difference.insert(6);
338 difference.insert(7);
339 EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a2, a1));
340 }
341
342 {
343 std::vector<int> difference;
344 difference.push_back(1);
345 difference.push_back(2);
346 EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a1, a2));
347 }
348
349 {
350 std::vector<int> difference;
351 difference.push_back(5);
352 difference.push_back(6);
353 difference.push_back(7);
354 EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a2, a1));
355 }
356 }
357
TEST(STLUtilTest,STLSetUnion)358 TEST(STLUtilTest, STLSetUnion) {
359 std::set<int> a1;
360 a1.insert(1);
361 a1.insert(2);
362 a1.insert(3);
363 a1.insert(4);
364
365 std::set<int> a2;
366 a2.insert(3);
367 a2.insert(4);
368 a2.insert(5);
369 a2.insert(6);
370 a2.insert(7);
371
372 {
373 std::set<int> result;
374 result.insert(1);
375 result.insert(2);
376 result.insert(3);
377 result.insert(4);
378 result.insert(5);
379 result.insert(6);
380 result.insert(7);
381 EXPECT_EQ(result, STLSetUnion<std::set<int> >(a1, a2));
382 }
383
384 {
385 std::set<int> result;
386 result.insert(1);
387 result.insert(2);
388 result.insert(3);
389 result.insert(4);
390 result.insert(5);
391 result.insert(6);
392 result.insert(7);
393 EXPECT_EQ(result, STLSetUnion<std::set<int> >(a2, a1));
394 }
395
396 {
397 std::vector<int> result;
398 result.push_back(1);
399 result.push_back(2);
400 result.push_back(3);
401 result.push_back(4);
402 result.push_back(5);
403 result.push_back(6);
404 result.push_back(7);
405 EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a1, a2));
406 }
407
408 {
409 std::vector<int> result;
410 result.push_back(1);
411 result.push_back(2);
412 result.push_back(3);
413 result.push_back(4);
414 result.push_back(5);
415 result.push_back(6);
416 result.push_back(7);
417 EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a2, a1));
418 }
419 }
420
TEST(STLUtilTest,STLSetIntersection)421 TEST(STLUtilTest, STLSetIntersection) {
422 std::set<int> a1;
423 a1.insert(1);
424 a1.insert(2);
425 a1.insert(3);
426 a1.insert(4);
427
428 std::set<int> a2;
429 a2.insert(3);
430 a2.insert(4);
431 a2.insert(5);
432 a2.insert(6);
433 a2.insert(7);
434
435 {
436 std::set<int> result;
437 result.insert(3);
438 result.insert(4);
439 EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a1, a2));
440 }
441
442 {
443 std::set<int> result;
444 result.insert(3);
445 result.insert(4);
446 EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a2, a1));
447 }
448
449 {
450 std::vector<int> result;
451 result.push_back(3);
452 result.push_back(4);
453 EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a1, a2));
454 }
455
456 {
457 std::vector<int> result;
458 result.push_back(3);
459 result.push_back(4);
460 EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a2, a1));
461 }
462 }
463
TEST(STLUtilTest,STLIncludes)464 TEST(STLUtilTest, STLIncludes) {
465 std::set<int> a1;
466 a1.insert(1);
467 a1.insert(2);
468 a1.insert(3);
469 a1.insert(4);
470
471 std::set<int> a2;
472 a2.insert(3);
473 a2.insert(4);
474
475 std::set<int> a3;
476 a3.insert(3);
477 a3.insert(4);
478 a3.insert(5);
479
480 EXPECT_TRUE(STLIncludes<std::set<int> >(a1, a2));
481 EXPECT_FALSE(STLIncludes<std::set<int> >(a1, a3));
482 EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a1));
483 EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a3));
484 EXPECT_FALSE(STLIncludes<std::set<int> >(a3, a1));
485 EXPECT_TRUE(STLIncludes<std::set<int> >(a3, a2));
486 }
487
TEST(Erase,String)488 TEST(Erase, String) {
489 const std::pair<std::string, std::string> test_data[] = {
490 {"", ""}, {"abc", "bc"}, {"abca", "bc"},
491 };
492
493 for (auto test_case : test_data) {
494 Erase(test_case.first, 'a');
495 EXPECT_EQ(test_case.second, test_case.first);
496 }
497
498 for (auto test_case : test_data) {
499 EraseIf(test_case.first, [](char elem) { return elem < 'b'; });
500 EXPECT_EQ(test_case.second, test_case.first);
501 }
502 }
503
TEST(Erase,String16)504 TEST(Erase, String16) {
505 std::pair<base::string16, base::string16> test_data[] = {
506 {base::string16(), base::string16()},
507 {UTF8ToUTF16("abc"), UTF8ToUTF16("bc")},
508 {UTF8ToUTF16("abca"), UTF8ToUTF16("bc")},
509 };
510
511 const base::string16 letters = UTF8ToUTF16("ab");
512 for (auto test_case : test_data) {
513 Erase(test_case.first, letters[0]);
514 EXPECT_EQ(test_case.second, test_case.first);
515 }
516
517 for (auto test_case : test_data) {
518 EraseIf(test_case.first, [&](short elem) { return elem < letters[1]; });
519 EXPECT_EQ(test_case.second, test_case.first);
520 }
521 }
522
TEST(Erase,Deque)523 TEST(Erase, Deque) {
524 RunEraseTest<std::deque<int>>();
525 RunEraseIfTest<std::deque<std::pair<int, int>>>();
526 }
527
TEST(Erase,Vector)528 TEST(Erase, Vector) {
529 RunEraseTest<std::vector<int>>();
530 RunEraseIfTest<std::vector<std::pair<int, int>>>();
531 }
532
TEST(Erase,ForwardList)533 TEST(Erase, ForwardList) {
534 RunEraseTest<std::forward_list<int>>();
535 RunEraseIfTest<std::forward_list<std::pair<int, int>>>();
536 }
537
TEST(Erase,List)538 TEST(Erase, List) {
539 RunEraseTest<std::list<int>>();
540 RunEraseIfTest<std::list<std::pair<int, int>>>();
541 }
542
TEST(Erase,Map)543 TEST(Erase, Map) {
544 RunEraseIfTest<std::map<int, int>>();
545 RunEraseIfTest<std::map<int, int, std::greater<int>>>();
546 }
547
TEST(Erase,Multimap)548 TEST(Erase, Multimap) {
549 RunEraseIfTest<std::multimap<int, int>>();
550 RunEraseIfTest<std::multimap<int, int, std::greater<int>>>();
551 }
552
TEST(Erase,Set)553 TEST(Erase, Set) {
554 RunEraseIfTest<std::set<std::pair<int, int>>>();
555 RunEraseIfTest<
556 std::set<std::pair<int, int>, std::greater<std::pair<int, int>>>>();
557 }
558
TEST(Erase,Multiset)559 TEST(Erase, Multiset) {
560 RunEraseIfTest<std::multiset<std::pair<int, int>>>();
561 RunEraseIfTest<
562 std::multiset<std::pair<int, int>, std::greater<std::pair<int, int>>>>();
563 }
564
TEST(Erase,UnorderedMap)565 TEST(Erase, UnorderedMap) {
566 RunEraseIfTest<std::unordered_map<int, int>>();
567 RunEraseIfTest<std::unordered_map<int, int, CustomIntHash>>();
568 }
569
TEST(Erase,UnorderedMultimap)570 TEST(Erase, UnorderedMultimap) {
571 RunEraseIfTest<std::unordered_multimap<int, int>>();
572 RunEraseIfTest<std::unordered_multimap<int, int, CustomIntHash>>();
573 }
574
TEST(Erase,UnorderedSet)575 TEST(Erase, UnorderedSet) {
576 RunEraseIfTest<std::unordered_set<std::pair<int, int>, HashByFirst>>();
577 }
578
TEST(Erase,UnorderedMultiset)579 TEST(Erase, UnorderedMultiset) {
580 RunEraseIfTest<std::unordered_multiset<std::pair<int, int>, HashByFirst>>();
581 }
582
TEST(Erase,IsNotIn)583 TEST(Erase, IsNotIn) {
584 // Should keep both '2' but only one '4', like std::set_intersection.
585 std::vector<int> lhs = {0, 2, 2, 4, 4, 4, 6, 8, 10};
586 std::vector<int> rhs = {1, 2, 2, 4, 5, 6, 7};
587 std::vector<int> expected = {2, 2, 4, 6};
588 EraseIf(lhs, IsNotIn<std::vector<int>>(rhs));
589 EXPECT_EQ(expected, lhs);
590 }
591
TEST(ContainsValue,OrdinaryArrays)592 TEST(ContainsValue, OrdinaryArrays) {
593 const char allowed_chars[] = {'a', 'b', 'c', 'd'};
594 EXPECT_TRUE(ContainsValue(allowed_chars, 'a'));
595 EXPECT_FALSE(ContainsValue(allowed_chars, 'z'));
596 EXPECT_FALSE(ContainsValue(allowed_chars, 0));
597
598 const char allowed_chars_including_nul[] = "abcd";
599 EXPECT_TRUE(ContainsValue(allowed_chars_including_nul, 0));
600 }
601
TEST(STLUtilTest,OptionalOrNullptr)602 TEST(STLUtilTest, OptionalOrNullptr) {
603 Optional<float> optional;
604 EXPECT_EQ(nullptr, base::OptionalOrNullptr(optional));
605
606 optional = 0.1f;
607 EXPECT_EQ(&optional.value(), base::OptionalOrNullptr(optional));
608 EXPECT_NE(nullptr, base::OptionalOrNullptr(optional));
609 }
610
611 } // namespace
612 } // namespace base
613