1 // 2 // Copyright 2016 Daniel James. 3 // Distributed under the Boost Software License, Version 1.0. (See accompanying 4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 6 // clang-format off 7 #include "../helpers/prefix.hpp" 8 #include <boost/unordered_set.hpp> 9 #include <boost/unordered_map.hpp> 10 #include "../helpers/postfix.hpp" 11 // clang-format on 12 13 #include <boost/functional/hash/hash.hpp> 14 #include "../helpers/test.hpp" 15 #include "../helpers/count.hpp" 16 #include <string> 17 18 // Test that various emplace methods work with different numbers of 19 // arguments. 20 21 namespace emplace_tests { 22 // Constructible with 2 to 10 arguments 23 struct emplace_value : private test::counted_object 24 { 25 typedef int A0; 26 typedef std::string A1; 27 typedef char A2; 28 typedef int A3; 29 typedef int A4; 30 typedef int A5; 31 typedef int A6; 32 typedef int A7; 33 typedef int A8; 34 typedef int A9; 35 36 int arg_count; 37 38 A0 a0; 39 A1 a1; 40 A2 a2; 41 A3 a3; 42 A4 a4; 43 A5 a5; 44 A6 a6; 45 A7 a7; 46 A8 a8; 47 A9 a9; 48 emplace_valueemplace_tests::emplace_value49 emplace_value(A0 const& b0, A1 const& b1) : arg_count(2), a0(b0), a1(b1) {} 50 emplace_valueemplace_tests::emplace_value51 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2) 52 : arg_count(3), a0(b0), a1(b1), a2(b2) 53 { 54 } 55 emplace_valueemplace_tests::emplace_value56 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3) 57 : arg_count(4), a0(b0), a1(b1), a2(b2), a3(b3) 58 { 59 } 60 emplace_valueemplace_tests::emplace_value61 emplace_value( 62 A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, A4 const& b4) 63 : arg_count(5), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4) 64 { 65 } 66 emplace_valueemplace_tests::emplace_value67 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, 68 A4 const& b4, A5 const& b5) 69 : arg_count(6), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5) 70 { 71 } 72 emplace_valueemplace_tests::emplace_value73 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, 74 A4 const& b4, A5 const& b5, A6 const& b6) 75 : arg_count(7), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6) 76 { 77 } 78 emplace_valueemplace_tests::emplace_value79 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, 80 A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7) 81 : arg_count(8), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6), 82 a7(b7) 83 { 84 } 85 emplace_valueemplace_tests::emplace_value86 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, 87 A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7, A8 const& b8) 88 : arg_count(9), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6), 89 a7(b7), a8(b8) 90 { 91 } 92 emplace_valueemplace_tests::emplace_value93 emplace_value(A0 const& b0, A1 const& b1, A2 const& b2, A3 const& b3, 94 A4 const& b4, A5 const& b5, A6 const& b6, A7 const& b7, A8 const& b8, 95 A9 const& b9) 96 : arg_count(10), a0(b0), a1(b1), a2(b2), a3(b3), a4(b4), a5(b5), a6(b6), 97 a7(b7), a8(b8), a9(b9) 98 { 99 } 100 hash_value(emplace_value const & x)101 friend std::size_t hash_value(emplace_value const& x) 102 { 103 std::size_t r1 = 23894278u; 104 if (x.arg_count >= 1) 105 boost::hash_combine(r1, x.a0); 106 if (x.arg_count >= 2) 107 boost::hash_combine(r1, x.a1); 108 if (x.arg_count >= 3) 109 boost::hash_combine(r1, x.a2); 110 if (x.arg_count >= 4) 111 boost::hash_combine(r1, x.a3); 112 if (x.arg_count >= 5) 113 boost::hash_combine(r1, x.a4); 114 if (x.arg_count >= 6) 115 boost::hash_combine(r1, x.a5); 116 if (x.arg_count >= 7) 117 boost::hash_combine(r1, x.a6); 118 if (x.arg_count >= 8) 119 boost::hash_combine(r1, x.a7); 120 if (x.arg_count >= 9) 121 boost::hash_combine(r1, x.a8); 122 if (x.arg_count >= 10) 123 boost::hash_combine(r1, x.a9); 124 return r1; 125 } 126 operator ==(emplace_value const & x,emplace_value const & y)127 friend bool operator==(emplace_value const& x, emplace_value const& y) 128 { 129 if (x.arg_count != y.arg_count) { 130 return false; 131 } 132 if (x.arg_count >= 1 && x.a0 != y.a0) { 133 return false; 134 } 135 if (x.arg_count >= 2 && x.a1 != y.a1) { 136 return false; 137 } 138 if (x.arg_count >= 3 && x.a2 != y.a2) { 139 return false; 140 } 141 if (x.arg_count >= 4 && x.a3 != y.a3) { 142 return false; 143 } 144 if (x.arg_count >= 5 && x.a4 != y.a4) { 145 return false; 146 } 147 if (x.arg_count >= 6 && x.a5 != y.a5) { 148 return false; 149 } 150 if (x.arg_count >= 7 && x.a6 != y.a6) { 151 return false; 152 } 153 if (x.arg_count >= 8 && x.a7 != y.a7) { 154 return false; 155 } 156 if (x.arg_count >= 9 && x.a8 != y.a8) { 157 return false; 158 } 159 if (x.arg_count >= 10 && x.a9 != y.a9) { 160 return false; 161 } 162 return true; 163 } 164 165 private: 166 emplace_value(); 167 emplace_value(emplace_value const&); 168 }; 169 UNORDERED_AUTO_TEST(emplace_set)170 UNORDERED_AUTO_TEST (emplace_set) { 171 test::check_instances check_; 172 173 typedef boost::unordered_set<emplace_value, boost::hash<emplace_value> > 174 container; 175 typedef container::iterator iterator; 176 typedef std::pair<iterator, bool> return_type; 177 container x(10); 178 iterator i1; 179 return_type r1, r2; 180 181 // 2 args 182 183 emplace_value v1(10, "x"); 184 r1 = x.emplace(10, std::string("x")); 185 BOOST_TEST_EQ(x.size(), 1u); 186 BOOST_TEST(r1.second); 187 BOOST_TEST(*r1.first == v1); 188 BOOST_TEST(r1.first == x.find(v1)); 189 BOOST_TEST_EQ(check_.instances(), 2); 190 BOOST_TEST_EQ(check_.constructions(), 2); 191 192 // 3 args 193 194 emplace_value v2(3, "foo", 'a'); 195 r1 = x.emplace(3, "foo", 'a'); 196 BOOST_TEST_EQ(x.size(), 2u); 197 BOOST_TEST(r1.second); 198 BOOST_TEST(*r1.first == v2); 199 BOOST_TEST(r1.first == x.find(v2)); 200 BOOST_TEST_EQ(check_.instances(), 4); 201 BOOST_TEST_EQ(check_.constructions(), 4); 202 203 // 7 args with hint + duplicate 204 205 emplace_value v3(25, "something", 'z', 4, 5, 6, 7); 206 i1 = x.emplace_hint(r1.first, 25, "something", 'z', 4, 5, 6, 7); 207 BOOST_TEST_EQ(x.size(), 3u); 208 BOOST_TEST(*i1 == v3); 209 BOOST_TEST(i1 == x.find(v3)); 210 BOOST_TEST_EQ(check_.instances(), 6); 211 BOOST_TEST_EQ(check_.constructions(), 6); 212 213 r2 = x.emplace(25, "something", 'z', 4, 5, 6, 7); 214 BOOST_TEST_EQ(x.size(), 3u); 215 BOOST_TEST(!r2.second); 216 BOOST_TEST(i1 == r2.first); 217 // The container has to construct an object in order to check 218 // whether it can emplace, so there's an extra cosntruction 219 // here. 220 BOOST_TEST_EQ(check_.instances(), 6); 221 BOOST_TEST_EQ(check_.constructions(), 7); 222 223 // 10 args + hint duplicate 224 225 std::string s1; 226 emplace_value v4(10, s1, 'a', 4, 5, 6, 7, 8, 9, 10); 227 r1 = x.emplace(10, s1, 'a', 4, 5, 6, 7, 8, 9, 10); 228 BOOST_TEST_EQ(x.size(), 4u); 229 BOOST_TEST(r1.second); 230 BOOST_TEST(*r1.first == v4); 231 BOOST_TEST(r1.first == x.find(v4)); 232 BOOST_TEST_EQ(check_.instances(), 8); 233 BOOST_TEST_EQ(check_.constructions(), 9); 234 235 BOOST_TEST( 236 r1.first == x.emplace_hint(r1.first, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10)); 237 BOOST_TEST( 238 r1.first == x.emplace_hint(r2.first, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10)); 239 BOOST_TEST( 240 r1.first == x.emplace_hint(x.end(), 10, "", 'a', 4, 5, 6, 7, 8, 9, 10)); 241 BOOST_TEST_EQ(check_.instances(), 8); 242 BOOST_TEST_EQ(check_.constructions(), 12); 243 244 BOOST_TEST_EQ(x.size(), 4u); 245 BOOST_TEST(x.count(v1) == 1); 246 BOOST_TEST(x.count(v2) == 1); 247 BOOST_TEST(x.count(v3) == 1); 248 BOOST_TEST(x.count(v4) == 1); 249 } 250 UNORDERED_AUTO_TEST(emplace_multiset)251 UNORDERED_AUTO_TEST (emplace_multiset) { 252 test::check_instances check_; 253 254 typedef boost::unordered_multiset<emplace_value, 255 boost::hash<emplace_value> > 256 container; 257 typedef container::iterator iterator; 258 container x(10); 259 iterator i1, i2; 260 261 // 2 args. 262 263 emplace_value v1(10, "x"); 264 i1 = x.emplace(10, std::string("x")); 265 BOOST_TEST_EQ(x.size(), 1u); 266 BOOST_TEST(i1 == x.find(v1)); 267 BOOST_TEST_EQ(check_.instances(), 2); 268 BOOST_TEST_EQ(check_.constructions(), 2); 269 270 // 4 args + duplicate 271 272 emplace_value v2(4, "foo", 'a', 15); 273 i1 = x.emplace(4, "foo", 'a', 15); 274 BOOST_TEST_EQ(x.size(), 2u); 275 BOOST_TEST(i1 == x.find(v2)); 276 BOOST_TEST_EQ(check_.instances(), 4); 277 BOOST_TEST_EQ(check_.constructions(), 4); 278 279 i2 = x.emplace(4, "foo", 'a', 15); 280 BOOST_TEST_EQ(x.size(), 3u); 281 BOOST_TEST(i1 != i2); 282 BOOST_TEST(*i1 == *i2); 283 BOOST_TEST(x.count(*i1) == 2); 284 BOOST_TEST_EQ(check_.instances(), 5); 285 BOOST_TEST_EQ(check_.constructions(), 5); 286 287 // 7 args + duplicate using hint. 288 289 emplace_value v3(7, "", 'z', 4, 5, 6, 7); 290 i1 = x.emplace(7, "", 'z', 4, 5, 6, 7); 291 BOOST_TEST_EQ(x.size(), 4u); 292 BOOST_TEST_EQ(i1->a2, 'z'); 293 BOOST_TEST(x.count(*i1) == 1); 294 BOOST_TEST(i1 == x.find(v3)); 295 BOOST_TEST_EQ(check_.instances(), 7); 296 BOOST_TEST_EQ(check_.constructions(), 7); 297 298 i2 = x.emplace_hint(i1, 7, "", 'z', 4, 5, 6, 7); 299 BOOST_TEST_EQ(x.size(), 5u); 300 BOOST_TEST(*i1 == *i2); 301 BOOST_TEST(i1 != i2); 302 BOOST_TEST(x.count(*i1) == 2); 303 BOOST_TEST_EQ(check_.instances(), 8); 304 BOOST_TEST_EQ(check_.constructions(), 8); 305 306 // 10 args with bad hint + duplicate 307 308 emplace_value v4(10, "", 'a', 4, 5, 6, 7, 8, 9, 10); 309 i1 = x.emplace_hint(i2, 10, "", 'a', 4, 5, 6, 7, 8, 9, 10); 310 BOOST_TEST_EQ(x.size(), 6u); 311 BOOST_TEST_EQ(i1->arg_count, 10); 312 BOOST_TEST(i1 == x.find(v4)); 313 BOOST_TEST_EQ(check_.instances(), 10); 314 BOOST_TEST_EQ(check_.constructions(), 10); 315 316 i2 = x.emplace_hint(x.end(), 10, "", 'a', 4, 5, 6, 7, 8, 9, 10); 317 BOOST_TEST_EQ(x.size(), 7u); 318 BOOST_TEST(*i1 == *i2); 319 BOOST_TEST(i1 != i2); 320 BOOST_TEST(x.count(*i1) == 2); 321 BOOST_TEST_EQ(check_.instances(), 11); 322 BOOST_TEST_EQ(check_.constructions(), 11); 323 324 BOOST_TEST_EQ(x.count(v1), 1u); 325 BOOST_TEST_EQ(x.count(v2), 2u); 326 BOOST_TEST_EQ(x.count(v3), 2u); 327 } 328 UNORDERED_AUTO_TEST(emplace_map)329 UNORDERED_AUTO_TEST (emplace_map) { 330 test::check_instances check_; 331 332 typedef boost::unordered_map<emplace_value, emplace_value, 333 boost::hash<emplace_value> > 334 container; 335 typedef container::iterator iterator; 336 typedef std::pair<iterator, bool> return_type; 337 container x(10); 338 return_type r1, r2; 339 340 // 5/8 args + duplicate 341 342 emplace_value k1(5, "", 'b', 4, 5); 343 emplace_value m1(8, "xxx", 'z', 4, 5, 6, 7, 8); 344 r1 = x.emplace(boost::unordered::piecewise_construct, 345 boost::make_tuple(5, "", 'b', 4, 5), 346 boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8)); 347 BOOST_TEST_EQ(x.size(), 1u); 348 BOOST_TEST(r1.second); 349 BOOST_TEST(x.find(k1) == r1.first); 350 BOOST_TEST(x.find(k1)->second == m1); 351 BOOST_TEST_EQ(check_.instances(), 4); 352 BOOST_TEST_EQ(check_.constructions(), 4); 353 354 r2 = x.emplace(boost::unordered::piecewise_construct, 355 boost::make_tuple(5, "", 'b', 4, 5), 356 boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8)); 357 BOOST_TEST_EQ(x.size(), 1u); 358 BOOST_TEST(!r2.second); 359 BOOST_TEST(r1.first == r2.first); 360 BOOST_TEST(x.find(k1)->second == m1); 361 BOOST_TEST_EQ(check_.instances(), 4); 362 // constructions could possibly be 5 if the implementation only 363 // constructed the key. 364 BOOST_TEST_EQ(check_.constructions(), 6); 365 366 // 9/3 args + duplicates with hints, different mapped value. 367 368 emplace_value k2(9, "", 'b', 4, 5, 6, 7, 8, 9); 369 emplace_value m2(3, "aaa", 'm'); 370 r1 = x.emplace(boost::unordered::piecewise_construct, 371 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 372 boost::make_tuple(3, "aaa", 'm')); 373 BOOST_TEST_EQ(x.size(), 2u); 374 BOOST_TEST(r1.second); 375 BOOST_TEST(r1.first->first.arg_count == 9); 376 BOOST_TEST(r1.first->second.arg_count == 3); 377 BOOST_TEST(x.find(k2) == r1.first); 378 BOOST_TEST(x.find(k2)->second == m2); 379 BOOST_TEST_EQ(check_.instances(), 8); 380 BOOST_TEST_EQ(check_.constructions(), 10); 381 382 BOOST_TEST(r1.first == 383 x.emplace_hint(r1.first, boost::unordered::piecewise_construct, 384 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 385 boost::make_tuple(15, "jkjk"))); 386 BOOST_TEST(r1.first == 387 x.emplace_hint(r2.first, boost::unordered::piecewise_construct, 388 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 389 boost::make_tuple(275, "xxx", 'm', 6))); 390 BOOST_TEST(r1.first == 391 x.emplace_hint(x.end(), boost::unordered::piecewise_construct, 392 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 393 boost::make_tuple(-10, "blah blah", '\0'))); 394 BOOST_TEST_EQ(x.size(), 2u); 395 BOOST_TEST(x.find(k2)->second == m2); 396 BOOST_TEST_EQ(check_.instances(), 8); 397 BOOST_TEST_EQ(check_.constructions(), 16); 398 } 399 UNORDERED_AUTO_TEST(emplace_multimap)400 UNORDERED_AUTO_TEST (emplace_multimap) { 401 test::check_instances check_; 402 403 typedef boost::unordered_multimap<emplace_value, emplace_value, 404 boost::hash<emplace_value> > 405 container; 406 typedef container::iterator iterator; 407 container x(10); 408 iterator i1, i2, i3, i4; 409 410 // 5/8 args + duplicate 411 412 emplace_value k1(5, "", 'b', 4, 5); 413 emplace_value m1(8, "xxx", 'z', 4, 5, 6, 7, 8); 414 i1 = x.emplace(boost::unordered::piecewise_construct, 415 boost::make_tuple(5, "", 'b', 4, 5), 416 boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8)); 417 BOOST_TEST_EQ(x.size(), 1u); 418 BOOST_TEST(x.find(k1) == i1); 419 BOOST_TEST(x.find(k1)->second == m1); 420 BOOST_TEST_EQ(check_.instances(), 4); 421 BOOST_TEST_EQ(check_.constructions(), 4); 422 423 emplace_value m1a(8, "xxx", 'z', 4, 5, 6, 7, 8); 424 i2 = x.emplace(boost::unordered::piecewise_construct, 425 boost::make_tuple(5, "", 'b', 4, 5), 426 boost::make_tuple(8, "xxx", 'z', 4, 5, 6, 7, 8)); 427 BOOST_TEST_EQ(x.size(), 2u); 428 BOOST_TEST(i1 != i2); 429 BOOST_TEST(i1->second == m1); 430 BOOST_TEST(i2->second == m1a); 431 BOOST_TEST_EQ(check_.instances(), 7); 432 BOOST_TEST_EQ(check_.constructions(), 7); 433 434 // 9/3 args + duplicates with hints, different mapped value. 435 436 emplace_value k2(9, "", 'b', 4, 5, 6, 7, 8, 9); 437 emplace_value m2(3, "aaa", 'm'); 438 i1 = x.emplace(boost::unordered::piecewise_construct, 439 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 440 boost::make_tuple(3, "aaa", 'm')); 441 BOOST_TEST_EQ(x.size(), 3u); 442 BOOST_TEST(i1->first.arg_count == 9); 443 BOOST_TEST(i1->second.arg_count == 3); 444 BOOST_TEST_EQ(check_.instances(), 11); 445 BOOST_TEST_EQ(check_.constructions(), 11); 446 447 emplace_value m2a(15, "jkjk"); 448 i2 = x.emplace_hint(i2, boost::unordered::piecewise_construct, 449 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 450 boost::make_tuple(15, "jkjk")); 451 emplace_value m2b(275, "xxx", 'm', 6); 452 i3 = x.emplace_hint(i1, boost::unordered::piecewise_construct, 453 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 454 boost::make_tuple(275, "xxx", 'm', 6)); 455 emplace_value m2c(-10, "blah blah", '\0'); 456 i4 = x.emplace_hint(x.end(), boost::unordered::piecewise_construct, 457 boost::make_tuple(9, "", 'b', 4, 5, 6, 7, 8, 9), 458 boost::make_tuple(-10, "blah blah", '\0')); 459 BOOST_TEST_EQ(x.size(), 6u); 460 BOOST_TEST(x.find(k2)->second == m2); 461 BOOST_TEST_EQ(check_.instances(), 20); 462 BOOST_TEST_EQ(check_.constructions(), 20); 463 } 464 UNORDERED_AUTO_TEST(try_emplace)465 UNORDERED_AUTO_TEST (try_emplace) { 466 test::check_instances check_; 467 468 typedef boost::unordered_map<int, emplace_value> container; 469 typedef container::iterator iterator; 470 typedef std::pair<iterator, bool> return_type; 471 container x(10); 472 return_type r1, r2, r3; 473 474 int k1 = 3; 475 emplace_value m1(414, "grr"); 476 r1 = x.try_emplace(3, 414, "grr"); 477 BOOST_TEST(r1.second); 478 BOOST_TEST(r1.first->first == k1); 479 BOOST_TEST(r1.first->second == m1); 480 BOOST_TEST_EQ(x.size(), 1u); 481 BOOST_TEST_EQ(check_.instances(), 2); 482 BOOST_TEST_EQ(check_.constructions(), 2); 483 484 int k2 = 10; 485 emplace_value m2(25, "", 'z'); 486 r2 = x.try_emplace(10, 25, std::string(""), 'z'); 487 BOOST_TEST(r2.second); 488 BOOST_TEST(r2.first->first == k2); 489 BOOST_TEST(r2.first->second == m2); 490 BOOST_TEST_EQ(x.size(), 2u); 491 BOOST_TEST_EQ(check_.instances(), 4); 492 BOOST_TEST_EQ(check_.constructions(), 4); 493 494 BOOST_TEST(x.find(k1)->second == m1); 495 BOOST_TEST(x.find(k2)->second == m2); 496 497 r3 = x.try_emplace(k2, 68, "jfeoj", 'p', 49309, 2323); 498 BOOST_TEST(!r3.second); 499 BOOST_TEST(r3.first == r2.first); 500 BOOST_TEST(r3.first->second == m2); 501 BOOST_TEST_EQ(x.size(), 2u); 502 BOOST_TEST_EQ(check_.instances(), 4); 503 BOOST_TEST_EQ(check_.constructions(), 4); 504 505 BOOST_TEST(r2.first == x.try_emplace(r2.first, k2, 808709, "what")); 506 BOOST_TEST( 507 r2.first == 508 x.try_emplace(r2.first, k2, 10, "xxx", 'a', 4, 5, 6, 7, 8, 9, 10)); 509 BOOST_TEST(r2.first->second == m2); 510 BOOST_TEST_EQ(x.size(), 2u); 511 } 512 } 513 514 RUN_TESTS() 515