kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 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 | |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 7 | #include <deque> |
| 8 | #include <forward_list> |
| 9 | #include <functional> |
| 10 | #include <iterator> |
| 11 | #include <list> |
| 12 | #include <map> |
kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 13 | #include <set> |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 14 | #include <string> |
| 15 | #include <unordered_map> |
| 16 | #include <unordered_set> |
| 17 | #include <vector> |
kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 18 | |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 19 | #include "base/strings/string16.h" |
| 20 | #include "base/strings/utf_string_conversions.h" |
kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 21 | #include "testing/gtest/include/gtest/gtest.h" |
| 22 | |
rpaquay@chromium.org | ceb7484 | 2014-01-30 02:13:27 +0900 | [diff] [blame] | 23 | namespace { |
| 24 | |
| 25 | // Used as test case to ensure the various base::STLXxx functions don't require |
| 26 | // more than operators "<" and "==" on values stored in containers. |
| 27 | class ComparableValue { |
| 28 | public: |
| 29 | explicit ComparableValue(int value) : value_(value) {} |
| 30 | |
| 31 | bool operator==(const ComparableValue& rhs) const { |
| 32 | return value_ == rhs.value_; |
| 33 | } |
| 34 | |
| 35 | bool operator<(const ComparableValue& rhs) const { |
| 36 | return value_ < rhs.value_; |
| 37 | } |
| 38 | |
| 39 | private: |
| 40 | int value_; |
| 41 | }; |
| 42 | |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 43 | template <typename Container> |
| 44 | void RunEraseTest() { |
| 45 | const std::pair<Container, Container> test_data[] = { |
| 46 | {Container(), Container()}, {{1, 2, 3}, {1, 3}}, {{1, 2, 3, 2}, {1, 3}}}; |
| 47 | |
| 48 | for (auto test_case : test_data) { |
| 49 | base::Erase(test_case.first, 2); |
| 50 | EXPECT_EQ(test_case.second, test_case.first); |
| 51 | } |
| 52 | } |
| 53 | |
| 54 | // This test is written for containers of std::pair<int, int> to support maps. |
| 55 | template <typename Container> |
| 56 | void RunEraseIfTest() { |
| 57 | struct { |
| 58 | Container input; |
| 59 | Container erase_even; |
| 60 | Container erase_odd; |
| 61 | } test_data[] = { |
| 62 | {Container(), Container(), Container()}, |
| 63 | {{{1, 1}, {2, 2}, {3, 3}}, {{1, 1}, {3, 3}}, {{2, 2}}}, |
| 64 | {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}, {{1, 1}, {3, 3}}, {{2, 2}, {4, 4}}}, |
| 65 | }; |
| 66 | |
| 67 | for (auto test_case : test_data) { |
| 68 | base::EraseIf(test_case.input, [](const std::pair<int, int>& elem) { |
| 69 | return !(elem.first & 1); |
| 70 | }); |
| 71 | EXPECT_EQ(test_case.erase_even, test_case.input); |
| 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_odd, test_case.input); |
| 79 | } |
| 80 | } |
| 81 | |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 82 | struct CustomIntHash { |
| 83 | size_t operator()(int elem) const { return std::hash<int>()(elem) + 1; } |
| 84 | }; |
| 85 | |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 86 | struct HashByFirst { |
| 87 | size_t operator()(const std::pair<int, int>& elem) const { |
| 88 | return std::hash<int>()(elem.first); |
| 89 | } |
| 90 | }; |
| 91 | |
danakj | 651c3e2 | 2015-03-07 10:51:42 +0900 | [diff] [blame] | 92 | } // namespace |
rpaquay@chromium.org | ceb7484 | 2014-01-30 02:13:27 +0900 | [diff] [blame] | 93 | |
kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 94 | namespace base { |
| 95 | namespace { |
| 96 | |
| 97 | TEST(STLUtilTest, STLIsSorted) { |
| 98 | { |
| 99 | std::set<int> set; |
| 100 | set.insert(24); |
| 101 | set.insert(1); |
| 102 | set.insert(12); |
| 103 | EXPECT_TRUE(STLIsSorted(set)); |
| 104 | } |
| 105 | |
| 106 | { |
rpaquay@chromium.org | ceb7484 | 2014-01-30 02:13:27 +0900 | [diff] [blame] | 107 | std::set<ComparableValue> set; |
| 108 | set.insert(ComparableValue(24)); |
| 109 | set.insert(ComparableValue(1)); |
| 110 | set.insert(ComparableValue(12)); |
| 111 | EXPECT_TRUE(STLIsSorted(set)); |
| 112 | } |
| 113 | |
| 114 | { |
kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 115 | std::vector<int> vector; |
| 116 | vector.push_back(1); |
| 117 | vector.push_back(1); |
| 118 | vector.push_back(4); |
| 119 | vector.push_back(64); |
| 120 | vector.push_back(12432); |
| 121 | EXPECT_TRUE(STLIsSorted(vector)); |
| 122 | vector.back() = 1; |
| 123 | EXPECT_FALSE(STLIsSorted(vector)); |
| 124 | } |
| 125 | } |
| 126 | |
| 127 | TEST(STLUtilTest, STLSetDifference) { |
| 128 | std::set<int> a1; |
| 129 | a1.insert(1); |
| 130 | a1.insert(2); |
| 131 | a1.insert(3); |
| 132 | a1.insert(4); |
| 133 | |
| 134 | std::set<int> a2; |
| 135 | a2.insert(3); |
| 136 | a2.insert(4); |
| 137 | a2.insert(5); |
| 138 | a2.insert(6); |
| 139 | a2.insert(7); |
| 140 | |
| 141 | { |
| 142 | std::set<int> difference; |
| 143 | difference.insert(1); |
| 144 | difference.insert(2); |
| 145 | EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a1, a2)); |
| 146 | } |
| 147 | |
| 148 | { |
| 149 | std::set<int> difference; |
| 150 | difference.insert(5); |
| 151 | difference.insert(6); |
| 152 | difference.insert(7); |
| 153 | EXPECT_EQ(difference, STLSetDifference<std::set<int> >(a2, a1)); |
| 154 | } |
| 155 | |
| 156 | { |
| 157 | std::vector<int> difference; |
| 158 | difference.push_back(1); |
| 159 | difference.push_back(2); |
| 160 | EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a1, a2)); |
| 161 | } |
| 162 | |
| 163 | { |
| 164 | std::vector<int> difference; |
| 165 | difference.push_back(5); |
| 166 | difference.push_back(6); |
| 167 | difference.push_back(7); |
| 168 | EXPECT_EQ(difference, STLSetDifference<std::vector<int> >(a2, a1)); |
| 169 | } |
| 170 | } |
| 171 | |
rpaquay@chromium.org | ceb7484 | 2014-01-30 02:13:27 +0900 | [diff] [blame] | 172 | TEST(STLUtilTest, STLSetUnion) { |
| 173 | std::set<int> a1; |
| 174 | a1.insert(1); |
| 175 | a1.insert(2); |
| 176 | a1.insert(3); |
| 177 | a1.insert(4); |
| 178 | |
| 179 | std::set<int> a2; |
| 180 | a2.insert(3); |
| 181 | a2.insert(4); |
| 182 | a2.insert(5); |
| 183 | a2.insert(6); |
| 184 | a2.insert(7); |
| 185 | |
| 186 | { |
| 187 | std::set<int> result; |
| 188 | result.insert(1); |
| 189 | result.insert(2); |
| 190 | result.insert(3); |
| 191 | result.insert(4); |
| 192 | result.insert(5); |
| 193 | result.insert(6); |
| 194 | result.insert(7); |
| 195 | EXPECT_EQ(result, STLSetUnion<std::set<int> >(a1, a2)); |
| 196 | } |
| 197 | |
| 198 | { |
| 199 | std::set<int> result; |
| 200 | result.insert(1); |
| 201 | result.insert(2); |
| 202 | result.insert(3); |
| 203 | result.insert(4); |
| 204 | result.insert(5); |
| 205 | result.insert(6); |
| 206 | result.insert(7); |
| 207 | EXPECT_EQ(result, STLSetUnion<std::set<int> >(a2, a1)); |
| 208 | } |
| 209 | |
| 210 | { |
| 211 | std::vector<int> result; |
| 212 | result.push_back(1); |
| 213 | result.push_back(2); |
| 214 | result.push_back(3); |
| 215 | result.push_back(4); |
| 216 | result.push_back(5); |
| 217 | result.push_back(6); |
| 218 | result.push_back(7); |
| 219 | EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a1, a2)); |
| 220 | } |
| 221 | |
| 222 | { |
| 223 | std::vector<int> result; |
| 224 | result.push_back(1); |
| 225 | result.push_back(2); |
| 226 | result.push_back(3); |
| 227 | result.push_back(4); |
| 228 | result.push_back(5); |
| 229 | result.push_back(6); |
| 230 | result.push_back(7); |
| 231 | EXPECT_EQ(result, STLSetUnion<std::vector<int> >(a2, a1)); |
| 232 | } |
| 233 | } |
| 234 | |
| 235 | TEST(STLUtilTest, STLSetIntersection) { |
| 236 | std::set<int> a1; |
| 237 | a1.insert(1); |
| 238 | a1.insert(2); |
| 239 | a1.insert(3); |
| 240 | a1.insert(4); |
| 241 | |
| 242 | std::set<int> a2; |
| 243 | a2.insert(3); |
| 244 | a2.insert(4); |
| 245 | a2.insert(5); |
| 246 | a2.insert(6); |
| 247 | a2.insert(7); |
| 248 | |
| 249 | { |
| 250 | std::set<int> result; |
| 251 | result.insert(3); |
| 252 | result.insert(4); |
| 253 | EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a1, a2)); |
| 254 | } |
| 255 | |
| 256 | { |
| 257 | std::set<int> result; |
| 258 | result.insert(3); |
| 259 | result.insert(4); |
| 260 | EXPECT_EQ(result, STLSetIntersection<std::set<int> >(a2, a1)); |
| 261 | } |
| 262 | |
| 263 | { |
| 264 | std::vector<int> result; |
| 265 | result.push_back(3); |
| 266 | result.push_back(4); |
| 267 | EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a1, a2)); |
| 268 | } |
| 269 | |
| 270 | { |
| 271 | std::vector<int> result; |
| 272 | result.push_back(3); |
| 273 | result.push_back(4); |
| 274 | EXPECT_EQ(result, STLSetIntersection<std::vector<int> >(a2, a1)); |
| 275 | } |
| 276 | } |
| 277 | |
| 278 | TEST(STLUtilTest, STLIncludes) { |
| 279 | std::set<int> a1; |
| 280 | a1.insert(1); |
| 281 | a1.insert(2); |
| 282 | a1.insert(3); |
| 283 | a1.insert(4); |
| 284 | |
| 285 | std::set<int> a2; |
| 286 | a2.insert(3); |
| 287 | a2.insert(4); |
| 288 | |
| 289 | std::set<int> a3; |
| 290 | a3.insert(3); |
| 291 | a3.insert(4); |
| 292 | a3.insert(5); |
| 293 | |
| 294 | EXPECT_TRUE(STLIncludes<std::set<int> >(a1, a2)); |
| 295 | EXPECT_FALSE(STLIncludes<std::set<int> >(a1, a3)); |
| 296 | EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a1)); |
| 297 | EXPECT_FALSE(STLIncludes<std::set<int> >(a2, a3)); |
| 298 | EXPECT_FALSE(STLIncludes<std::set<int> >(a3, a1)); |
| 299 | EXPECT_TRUE(STLIncludes<std::set<int> >(a3, a2)); |
| 300 | } |
| 301 | |
thestig | 828ec19 | 2015-01-14 12:41:38 +0900 | [diff] [blame] | 302 | TEST(StringAsArrayTest, Empty) { |
| 303 | std::string empty; |
| 304 | EXPECT_EQ(nullptr, string_as_array(&empty)); |
| 305 | } |
| 306 | |
| 307 | TEST(StringAsArrayTest, NullTerminated) { |
| 308 | // If any std::string implementation is not null-terminated, this should |
| 309 | // fail. All compilers we use return a null-terminated buffer, but please do |
| 310 | // not rely on this fact in your code. |
| 311 | std::string str("abcde"); |
| 312 | str.resize(3); |
| 313 | EXPECT_STREQ("abc", string_as_array(&str)); |
| 314 | } |
| 315 | |
| 316 | TEST(StringAsArrayTest, WriteCopy) { |
| 317 | // With a COW implementation, this test will fail if |
| 318 | // string_as_array(&str) is implemented as |
| 319 | // const_cast<char*>(str->data()). |
| 320 | std::string s1("abc"); |
| 321 | const std::string s2(s1); |
| 322 | string_as_array(&s1)[1] = 'x'; |
| 323 | EXPECT_EQ("axc", s1); |
| 324 | EXPECT_EQ("abc", s2); |
| 325 | } |
| 326 | |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 327 | TEST(Erase, String) { |
| 328 | const std::pair<std::string, std::string> test_data[] = { |
| 329 | {"", ""}, {"abc", "bc"}, {"abca", "bc"}, |
| 330 | }; |
| 331 | |
| 332 | for (auto test_case : test_data) { |
| 333 | Erase(test_case.first, 'a'); |
| 334 | EXPECT_EQ(test_case.second, test_case.first); |
| 335 | } |
| 336 | |
| 337 | for (auto test_case : test_data) { |
| 338 | EraseIf(test_case.first, [](char elem) { return elem < 'b'; }); |
| 339 | EXPECT_EQ(test_case.second, test_case.first); |
| 340 | } |
| 341 | } |
| 342 | |
| 343 | TEST(Erase, String16) { |
| 344 | std::pair<base::string16, base::string16> test_data[] = { |
| 345 | {base::string16(), base::string16()}, |
| 346 | {UTF8ToUTF16("abc"), UTF8ToUTF16("bc")}, |
| 347 | {UTF8ToUTF16("abca"), UTF8ToUTF16("bc")}, |
| 348 | }; |
| 349 | |
| 350 | const base::string16 letters = UTF8ToUTF16("ab"); |
| 351 | for (auto test_case : test_data) { |
| 352 | Erase(test_case.first, letters[0]); |
| 353 | EXPECT_EQ(test_case.second, test_case.first); |
| 354 | } |
| 355 | |
| 356 | for (auto test_case : test_data) { |
| 357 | EraseIf(test_case.first, [&](short elem) { return elem < letters[1]; }); |
| 358 | EXPECT_EQ(test_case.second, test_case.first); |
| 359 | } |
| 360 | } |
| 361 | |
| 362 | TEST(Erase, Deque) { |
| 363 | RunEraseTest<std::deque<int>>(); |
| 364 | RunEraseIfTest<std::deque<std::pair<int, int>>>(); |
| 365 | } |
| 366 | |
| 367 | TEST(Erase, Vector) { |
| 368 | RunEraseTest<std::vector<int>>(); |
| 369 | RunEraseIfTest<std::vector<std::pair<int, int>>>(); |
| 370 | } |
| 371 | |
| 372 | TEST(Erase, ForwardList) { |
| 373 | RunEraseTest<std::forward_list<int>>(); |
| 374 | RunEraseIfTest<std::forward_list<std::pair<int, int>>>(); |
| 375 | } |
| 376 | |
| 377 | TEST(Erase, List) { |
| 378 | RunEraseTest<std::list<int>>(); |
| 379 | RunEraseIfTest<std::list<std::pair<int, int>>>(); |
| 380 | } |
| 381 | |
| 382 | TEST(Erase, Map) { |
| 383 | RunEraseIfTest<std::map<int, int>>(); |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 384 | RunEraseIfTest<std::map<int, int, std::greater<int>>>(); |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 385 | } |
| 386 | |
| 387 | TEST(Erase, Multimap) { |
| 388 | RunEraseIfTest<std::multimap<int, int>>(); |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 389 | RunEraseIfTest<std::multimap<int, int, std::greater<int>>>(); |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 390 | } |
| 391 | |
| 392 | TEST(Erase, Set) { |
| 393 | RunEraseIfTest<std::set<std::pair<int, int>>>(); |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 394 | RunEraseIfTest< |
| 395 | std::set<std::pair<int, int>, std::greater<std::pair<int, int>>>>(); |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 396 | } |
| 397 | |
| 398 | TEST(Erase, Multiset) { |
| 399 | RunEraseIfTest<std::multiset<std::pair<int, int>>>(); |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 400 | RunEraseIfTest< |
| 401 | std::multiset<std::pair<int, int>, std::greater<std::pair<int, int>>>>(); |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 402 | } |
| 403 | |
| 404 | TEST(Erase, UnorderedMap) { |
| 405 | RunEraseIfTest<std::unordered_map<int, int>>(); |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 406 | RunEraseIfTest<std::unordered_map<int, int, CustomIntHash>>(); |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 407 | } |
| 408 | |
| 409 | TEST(Erase, UnorderedMultimap) { |
| 410 | RunEraseIfTest<std::unordered_multimap<int, int>>(); |
jdoerrie | 3812af8 | 2017-03-14 00:31:10 +0900 | [diff] [blame] | 411 | RunEraseIfTest<std::unordered_multimap<int, int, CustomIntHash>>(); |
dyaroshev | 0280170 | 2017-03-08 10:24:49 +0900 | [diff] [blame] | 412 | } |
| 413 | |
| 414 | TEST(Erase, UnorderedSet) { |
| 415 | RunEraseIfTest<std::unordered_set<std::pair<int, int>, HashByFirst>>(); |
| 416 | } |
| 417 | |
| 418 | TEST(Erase, UnorderedMultiset) { |
| 419 | RunEraseIfTest<std::unordered_multiset<std::pair<int, int>, HashByFirst>>(); |
| 420 | } |
| 421 | |
tsepez | 166225e | 2017-04-21 03:11:46 +0900 | [diff] [blame] | 422 | TEST(ContainsValue, OrdinaryArrays) { |
| 423 | const char allowed_chars[] = {'a', 'b', 'c', 'd'}; |
| 424 | EXPECT_TRUE(ContainsValue(allowed_chars, 'a')); |
| 425 | EXPECT_FALSE(ContainsValue(allowed_chars, 'z')); |
| 426 | EXPECT_FALSE(ContainsValue(allowed_chars, 0)); |
| 427 | |
| 428 | const char allowed_chars_including_nul[] = "abcd"; |
| 429 | EXPECT_TRUE(ContainsValue(allowed_chars_including_nul, 0)); |
| 430 | } |
| 431 | |
kalman@chromium.org | 028e624 | 2012-12-06 06:40:27 +0900 | [diff] [blame] | 432 | } // namespace |
| 433 | } // namespace base |