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 <deque> 8 #include <forward_list> 9 #include <functional> 10 #include <iterator> 11 #include <list> 12 #include <map> 13 #include <set> 14 #include <string> 15 #include <unordered_map> 16 #include <unordered_set> 17 #include <vector> 18 19 #include "base/strings/string16.h" 20 #include "base/strings/utf_string_conversions.h" 21 #include "testing/gtest/include/gtest/gtest.h" 22 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 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 82 struct CustomIntHash { 83 size_t operator()(int elem) const { return std::hash<int>()(elem) + 1; } 84 }; 85 86 struct HashByFirst { 87 size_t operator()(const std::pair<int, int>& elem) const { 88 return std::hash<int>()(elem.first); 89 } 90 }; 91 92 } // namespace 93 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 { 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 { 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 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 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 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>>(); 384 RunEraseIfTest<std::map<int, int, std::greater<int>>>(); 385 } 386 387 TEST(Erase, Multimap) { 388 RunEraseIfTest<std::multimap<int, int>>(); 389 RunEraseIfTest<std::multimap<int, int, std::greater<int>>>(); 390 } 391 392 TEST(Erase, Set) { 393 RunEraseIfTest<std::set<std::pair<int, int>>>(); 394 RunEraseIfTest< 395 std::set<std::pair<int, int>, std::greater<std::pair<int, int>>>>(); 396 } 397 398 TEST(Erase, Multiset) { 399 RunEraseIfTest<std::multiset<std::pair<int, int>>>(); 400 RunEraseIfTest< 401 std::multiset<std::pair<int, int>, std::greater<std::pair<int, int>>>>(); 402 } 403 404 TEST(Erase, UnorderedMap) { 405 RunEraseIfTest<std::unordered_map<int, int>>(); 406 RunEraseIfTest<std::unordered_map<int, int, CustomIntHash>>(); 407 } 408 409 TEST(Erase, UnorderedMultimap) { 410 RunEraseIfTest<std::unordered_multimap<int, int>>(); 411 RunEraseIfTest<std::unordered_multimap<int, int, CustomIntHash>>(); 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 422 } // namespace 423 } // namespace base 424
