1 // -*- C++ -*- 2 //===----------------------------------------------------------------------===// 3 // 4 // The LLVM Compiler Infrastructure 5 // 6 // This file is dual licensed under the MIT and the University of Illinois Open 7 // Source Licenses. See LICENSE.TXT for details. 8 // 9 //===----------------------------------------------------------------------===// 10 11 #ifndef _LIBCPP__HASH_TABLE 12 #define _LIBCPP__HASH_TABLE 13 14 #include <__config> 15 #include <initializer_list> 16 #include <memory> 17 #include <iterator> 18 #include <algorithm> 19 #include <cmath> 20 21 #include <__undef_min_max> 22 23 #ifdef _LIBCPP_DEBUG 24 # include <__debug> 25 #else 26 # define _LIBCPP_ASSERT(x, m) ((void)0) 27 #endif 28 29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 30 #pragma GCC system_header 31 #endif 32 33 _LIBCPP_BEGIN_NAMESPACE_STD 34 35 _LIBCPP_FUNC_VIS 36 size_t __next_prime(size_t __n); 37 38 template <class _NodePtr> 39 struct __hash_node_base 40 { 41 typedef __hash_node_base __first_node; 42 43 _NodePtr __next_; 44 45 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 46 }; 47 48 template <class _Tp, class _VoidPtr> 49 struct __hash_node 50 : public __hash_node_base 51 < 52 typename pointer_traits<_VoidPtr>::template 53 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 54 rebind<__hash_node<_Tp, _VoidPtr> > 55 #else 56 rebind<__hash_node<_Tp, _VoidPtr> >::other 57 #endif 58 > 59 { 60 typedef _Tp value_type; 61 62 size_t __hash_; 63 value_type __value_; 64 }; 65 66 inline _LIBCPP_INLINE_VISIBILITY 67 bool 68 __is_power2(size_t __bc) 69 { 70 return __bc > 2 && !(__bc & (__bc - 1)); 71 } 72 73 inline _LIBCPP_INLINE_VISIBILITY 74 size_t 75 __constrain_hash(size_t __h, size_t __bc) 76 { 77 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 78 } 79 80 inline _LIBCPP_INLINE_VISIBILITY 81 size_t 82 __next_pow2(size_t __n) 83 { 84 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 85 } 86 87 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 88 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 89 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 90 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 91 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 92 class _LIBCPP_TYPE_VIS_ONLY unordered_map; 93 94 template <class _NodePtr> 95 class _LIBCPP_TYPE_VIS_ONLY __hash_iterator 96 { 97 typedef _NodePtr __node_pointer; 98 99 __node_pointer __node_; 100 101 public: 102 typedef forward_iterator_tag iterator_category; 103 typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 104 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 105 typedef value_type& reference; 106 typedef typename pointer_traits<__node_pointer>::template 107 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 108 rebind<value_type> 109 #else 110 rebind<value_type>::other 111 #endif 112 pointer; 113 114 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 115 #if _LIBCPP_STD_VER > 11 116 : __node_(nullptr) 117 #endif 118 { 119 #if _LIBCPP_DEBUG_LEVEL >= 2 120 __get_db()->__insert_i(this); 121 #endif 122 } 123 124 #if _LIBCPP_DEBUG_LEVEL >= 2 125 126 _LIBCPP_INLINE_VISIBILITY 127 __hash_iterator(const __hash_iterator& __i) 128 : __node_(__i.__node_) 129 { 130 __get_db()->__iterator_copy(this, &__i); 131 } 132 133 _LIBCPP_INLINE_VISIBILITY 134 ~__hash_iterator() 135 { 136 __get_db()->__erase_i(this); 137 } 138 139 _LIBCPP_INLINE_VISIBILITY 140 __hash_iterator& operator=(const __hash_iterator& __i) 141 { 142 if (this != &__i) 143 { 144 __get_db()->__iterator_copy(this, &__i); 145 __node_ = __i.__node_; 146 } 147 return *this; 148 } 149 150 #endif // _LIBCPP_DEBUG_LEVEL >= 2 151 152 _LIBCPP_INLINE_VISIBILITY 153 reference operator*() const 154 { 155 #if _LIBCPP_DEBUG_LEVEL >= 2 156 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 157 "Attempted to dereference a non-dereferenceable unordered container iterator"); 158 #endif 159 return __node_->__value_; 160 } 161 _LIBCPP_INLINE_VISIBILITY 162 pointer operator->() const 163 { 164 #if _LIBCPP_DEBUG_LEVEL >= 2 165 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 166 "Attempted to dereference a non-dereferenceable unordered container iterator"); 167 #endif 168 return pointer_traits<pointer>::pointer_to(__node_->__value_); 169 } 170 171 _LIBCPP_INLINE_VISIBILITY 172 __hash_iterator& operator++() 173 { 174 #if _LIBCPP_DEBUG_LEVEL >= 2 175 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 176 "Attempted to increment non-incrementable unordered container iterator"); 177 #endif 178 __node_ = __node_->__next_; 179 return *this; 180 } 181 182 _LIBCPP_INLINE_VISIBILITY 183 __hash_iterator operator++(int) 184 { 185 __hash_iterator __t(*this); 186 ++(*this); 187 return __t; 188 } 189 190 friend _LIBCPP_INLINE_VISIBILITY 191 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 192 { 193 return __x.__node_ == __y.__node_; 194 } 195 friend _LIBCPP_INLINE_VISIBILITY 196 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 197 {return !(__x == __y);} 198 199 private: 200 #if _LIBCPP_DEBUG_LEVEL >= 2 201 _LIBCPP_INLINE_VISIBILITY 202 __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 203 : __node_(__node) 204 { 205 __get_db()->__insert_ic(this, __c); 206 } 207 #else 208 _LIBCPP_INLINE_VISIBILITY 209 __hash_iterator(__node_pointer __node) _NOEXCEPT 210 : __node_(__node) 211 {} 212 #endif 213 214 template <class, class, class, class> friend class __hash_table; 215 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 216 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 217 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 218 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 219 }; 220 221 template <class _ConstNodePtr> 222 class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 223 { 224 typedef _ConstNodePtr __node_pointer; 225 226 __node_pointer __node_; 227 228 typedef typename remove_const< 229 typename pointer_traits<__node_pointer>::element_type 230 >::type __node; 231 232 public: 233 typedef forward_iterator_tag iterator_category; 234 typedef typename __node::value_type value_type; 235 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 236 typedef const value_type& reference; 237 typedef typename pointer_traits<__node_pointer>::template 238 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 239 rebind<const value_type> 240 #else 241 rebind<const value_type>::other 242 #endif 243 pointer; 244 typedef typename pointer_traits<__node_pointer>::template 245 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 246 rebind<__node> 247 #else 248 rebind<__node>::other 249 #endif 250 __non_const_node_pointer; 251 typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 252 253 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 254 #if _LIBCPP_STD_VER > 11 255 : __node_(nullptr) 256 #endif 257 { 258 #if _LIBCPP_DEBUG_LEVEL >= 2 259 __get_db()->__insert_i(this); 260 #endif 261 } 262 _LIBCPP_INLINE_VISIBILITY 263 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 264 : __node_(__x.__node_) 265 { 266 #if _LIBCPP_DEBUG_LEVEL >= 2 267 __get_db()->__iterator_copy(this, &__x); 268 #endif 269 } 270 271 #if _LIBCPP_DEBUG_LEVEL >= 2 272 273 _LIBCPP_INLINE_VISIBILITY 274 __hash_const_iterator(const __hash_const_iterator& __i) 275 : __node_(__i.__node_) 276 { 277 __get_db()->__iterator_copy(this, &__i); 278 } 279 280 _LIBCPP_INLINE_VISIBILITY 281 ~__hash_const_iterator() 282 { 283 __get_db()->__erase_i(this); 284 } 285 286 _LIBCPP_INLINE_VISIBILITY 287 __hash_const_iterator& operator=(const __hash_const_iterator& __i) 288 { 289 if (this != &__i) 290 { 291 __get_db()->__iterator_copy(this, &__i); 292 __node_ = __i.__node_; 293 } 294 return *this; 295 } 296 297 #endif // _LIBCPP_DEBUG_LEVEL >= 2 298 299 _LIBCPP_INLINE_VISIBILITY 300 reference operator*() const 301 { 302 #if _LIBCPP_DEBUG_LEVEL >= 2 303 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 304 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 305 #endif 306 return __node_->__value_; 307 } 308 _LIBCPP_INLINE_VISIBILITY 309 pointer operator->() const 310 { 311 #if _LIBCPP_DEBUG_LEVEL >= 2 312 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 313 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 314 #endif 315 return pointer_traits<pointer>::pointer_to(__node_->__value_); 316 } 317 318 _LIBCPP_INLINE_VISIBILITY 319 __hash_const_iterator& operator++() 320 { 321 #if _LIBCPP_DEBUG_LEVEL >= 2 322 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 323 "Attempted to increment non-incrementable unordered container const_iterator"); 324 #endif 325 __node_ = __node_->__next_; 326 return *this; 327 } 328 329 _LIBCPP_INLINE_VISIBILITY 330 __hash_const_iterator operator++(int) 331 { 332 __hash_const_iterator __t(*this); 333 ++(*this); 334 return __t; 335 } 336 337 friend _LIBCPP_INLINE_VISIBILITY 338 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 339 { 340 return __x.__node_ == __y.__node_; 341 } 342 friend _LIBCPP_INLINE_VISIBILITY 343 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 344 {return !(__x == __y);} 345 346 private: 347 #if _LIBCPP_DEBUG_LEVEL >= 2 348 _LIBCPP_INLINE_VISIBILITY 349 __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 350 : __node_(__node) 351 { 352 __get_db()->__insert_ic(this, __c); 353 } 354 #else 355 _LIBCPP_INLINE_VISIBILITY 356 __hash_const_iterator(__node_pointer __node) _NOEXCEPT 357 : __node_(__node) 358 {} 359 #endif 360 361 template <class, class, class, class> friend class __hash_table; 362 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 363 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 364 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 365 }; 366 367 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 368 369 template <class _NodePtr> 370 class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 371 { 372 typedef _NodePtr __node_pointer; 373 374 __node_pointer __node_; 375 size_t __bucket_; 376 size_t __bucket_count_; 377 378 typedef pointer_traits<__node_pointer> __pointer_traits; 379 public: 380 typedef forward_iterator_tag iterator_category; 381 typedef typename __pointer_traits::element_type::value_type value_type; 382 typedef typename __pointer_traits::difference_type difference_type; 383 typedef value_type& reference; 384 typedef typename __pointer_traits::template 385 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 386 rebind<value_type> 387 #else 388 rebind<value_type>::other 389 #endif 390 pointer; 391 392 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 393 { 394 #if _LIBCPP_DEBUG_LEVEL >= 2 395 __get_db()->__insert_i(this); 396 #endif 397 } 398 399 #if _LIBCPP_DEBUG_LEVEL >= 2 400 401 _LIBCPP_INLINE_VISIBILITY 402 __hash_local_iterator(const __hash_local_iterator& __i) 403 : __node_(__i.__node_), 404 __bucket_(__i.__bucket_), 405 __bucket_count_(__i.__bucket_count_) 406 { 407 __get_db()->__iterator_copy(this, &__i); 408 } 409 410 _LIBCPP_INLINE_VISIBILITY 411 ~__hash_local_iterator() 412 { 413 __get_db()->__erase_i(this); 414 } 415 416 _LIBCPP_INLINE_VISIBILITY 417 __hash_local_iterator& operator=(const __hash_local_iterator& __i) 418 { 419 if (this != &__i) 420 { 421 __get_db()->__iterator_copy(this, &__i); 422 __node_ = __i.__node_; 423 __bucket_ = __i.__bucket_; 424 __bucket_count_ = __i.__bucket_count_; 425 } 426 return *this; 427 } 428 429 #endif // _LIBCPP_DEBUG_LEVEL >= 2 430 431 _LIBCPP_INLINE_VISIBILITY 432 reference operator*() const 433 { 434 #if _LIBCPP_DEBUG_LEVEL >= 2 435 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 436 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 437 #endif 438 return __node_->__value_; 439 } 440 _LIBCPP_INLINE_VISIBILITY 441 pointer operator->() const 442 { 443 #if _LIBCPP_DEBUG_LEVEL >= 2 444 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 445 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 446 #endif 447 return pointer_traits<pointer>::pointer_to(__node_->__value_); 448 } 449 450 _LIBCPP_INLINE_VISIBILITY 451 __hash_local_iterator& operator++() 452 { 453 #if _LIBCPP_DEBUG_LEVEL >= 2 454 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 455 "Attempted to increment non-incrementable unordered container local_iterator"); 456 #endif 457 __node_ = __node_->__next_; 458 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 459 __node_ = nullptr; 460 return *this; 461 } 462 463 _LIBCPP_INLINE_VISIBILITY 464 __hash_local_iterator operator++(int) 465 { 466 __hash_local_iterator __t(*this); 467 ++(*this); 468 return __t; 469 } 470 471 friend _LIBCPP_INLINE_VISIBILITY 472 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 473 { 474 return __x.__node_ == __y.__node_; 475 } 476 friend _LIBCPP_INLINE_VISIBILITY 477 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 478 {return !(__x == __y);} 479 480 private: 481 #if _LIBCPP_DEBUG_LEVEL >= 2 482 _LIBCPP_INLINE_VISIBILITY 483 __hash_local_iterator(__node_pointer __node, size_t __bucket, 484 size_t __bucket_count, const void* __c) _NOEXCEPT 485 : __node_(__node), 486 __bucket_(__bucket), 487 __bucket_count_(__bucket_count) 488 { 489 __get_db()->__insert_ic(this, __c); 490 if (__node_ != nullptr) 491 __node_ = __node_->__next_; 492 } 493 #else 494 _LIBCPP_INLINE_VISIBILITY 495 __hash_local_iterator(__node_pointer __node, size_t __bucket, 496 size_t __bucket_count) _NOEXCEPT 497 : __node_(__node), 498 __bucket_(__bucket), 499 __bucket_count_(__bucket_count) 500 { 501 if (__node_ != nullptr) 502 __node_ = __node_->__next_; 503 } 504 #endif 505 template <class, class, class, class> friend class __hash_table; 506 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 507 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 508 }; 509 510 template <class _ConstNodePtr> 511 class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 512 { 513 typedef _ConstNodePtr __node_pointer; 514 515 __node_pointer __node_; 516 size_t __bucket_; 517 size_t __bucket_count_; 518 519 typedef pointer_traits<__node_pointer> __pointer_traits; 520 typedef typename __pointer_traits::element_type __node; 521 typedef typename remove_const<__node>::type __non_const_node; 522 typedef typename pointer_traits<__node_pointer>::template 523 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 524 rebind<__non_const_node> 525 #else 526 rebind<__non_const_node>::other 527 #endif 528 __non_const_node_pointer; 529 typedef __hash_local_iterator<__non_const_node_pointer> 530 __non_const_iterator; 531 public: 532 typedef forward_iterator_tag iterator_category; 533 typedef typename remove_const< 534 typename __pointer_traits::element_type::value_type 535 >::type value_type; 536 typedef typename __pointer_traits::difference_type difference_type; 537 typedef const value_type& reference; 538 typedef typename __pointer_traits::template 539 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 540 rebind<const value_type> 541 #else 542 rebind<const value_type>::other 543 #endif 544 pointer; 545 546 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 547 { 548 #if _LIBCPP_DEBUG_LEVEL >= 2 549 __get_db()->__insert_i(this); 550 #endif 551 } 552 553 _LIBCPP_INLINE_VISIBILITY 554 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 555 : __node_(__x.__node_), 556 __bucket_(__x.__bucket_), 557 __bucket_count_(__x.__bucket_count_) 558 { 559 #if _LIBCPP_DEBUG_LEVEL >= 2 560 __get_db()->__iterator_copy(this, &__x); 561 #endif 562 } 563 564 #if _LIBCPP_DEBUG_LEVEL >= 2 565 566 _LIBCPP_INLINE_VISIBILITY 567 __hash_const_local_iterator(const __hash_const_local_iterator& __i) 568 : __node_(__i.__node_), 569 __bucket_(__i.__bucket_), 570 __bucket_count_(__i.__bucket_count_) 571 { 572 __get_db()->__iterator_copy(this, &__i); 573 } 574 575 _LIBCPP_INLINE_VISIBILITY 576 ~__hash_const_local_iterator() 577 { 578 __get_db()->__erase_i(this); 579 } 580 581 _LIBCPP_INLINE_VISIBILITY 582 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 583 { 584 if (this != &__i) 585 { 586 __get_db()->__iterator_copy(this, &__i); 587 __node_ = __i.__node_; 588 __bucket_ = __i.__bucket_; 589 __bucket_count_ = __i.__bucket_count_; 590 } 591 return *this; 592 } 593 594 #endif // _LIBCPP_DEBUG_LEVEL >= 2 595 596 _LIBCPP_INLINE_VISIBILITY 597 reference operator*() const 598 { 599 #if _LIBCPP_DEBUG_LEVEL >= 2 600 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 601 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 602 #endif 603 return __node_->__value_; 604 } 605 _LIBCPP_INLINE_VISIBILITY 606 pointer operator->() const 607 { 608 #if _LIBCPP_DEBUG_LEVEL >= 2 609 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 610 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 611 #endif 612 return pointer_traits<pointer>::pointer_to(__node_->__value_); 613 } 614 615 _LIBCPP_INLINE_VISIBILITY 616 __hash_const_local_iterator& operator++() 617 { 618 #if _LIBCPP_DEBUG_LEVEL >= 2 619 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 620 "Attempted to increment non-incrementable unordered container const_local_iterator"); 621 #endif 622 __node_ = __node_->__next_; 623 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 624 __node_ = nullptr; 625 return *this; 626 } 627 628 _LIBCPP_INLINE_VISIBILITY 629 __hash_const_local_iterator operator++(int) 630 { 631 __hash_const_local_iterator __t(*this); 632 ++(*this); 633 return __t; 634 } 635 636 friend _LIBCPP_INLINE_VISIBILITY 637 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 638 { 639 return __x.__node_ == __y.__node_; 640 } 641 friend _LIBCPP_INLINE_VISIBILITY 642 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 643 {return !(__x == __y);} 644 645 private: 646 #if _LIBCPP_DEBUG_LEVEL >= 2 647 _LIBCPP_INLINE_VISIBILITY 648 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 649 size_t __bucket_count, const void* __c) _NOEXCEPT 650 : __node_(__node), 651 __bucket_(__bucket), 652 __bucket_count_(__bucket_count) 653 { 654 __get_db()->__insert_ic(this, __c); 655 if (__node_ != nullptr) 656 __node_ = __node_->__next_; 657 } 658 #else 659 _LIBCPP_INLINE_VISIBILITY 660 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 661 size_t __bucket_count) _NOEXCEPT 662 : __node_(__node), 663 __bucket_(__bucket), 664 __bucket_count_(__bucket_count) 665 { 666 if (__node_ != nullptr) 667 __node_ = __node_->__next_; 668 } 669 #endif 670 template <class, class, class, class> friend class __hash_table; 671 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 672 }; 673 674 template <class _Alloc> 675 class __bucket_list_deallocator 676 { 677 typedef _Alloc allocator_type; 678 typedef allocator_traits<allocator_type> __alloc_traits; 679 typedef typename __alloc_traits::size_type size_type; 680 681 __compressed_pair<size_type, allocator_type> __data_; 682 public: 683 typedef typename __alloc_traits::pointer pointer; 684 685 _LIBCPP_INLINE_VISIBILITY 686 __bucket_list_deallocator() 687 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 688 : __data_(0) {} 689 690 _LIBCPP_INLINE_VISIBILITY 691 __bucket_list_deallocator(const allocator_type& __a, size_type __size) 692 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 693 : __data_(__size, __a) {} 694 695 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 696 697 _LIBCPP_INLINE_VISIBILITY 698 __bucket_list_deallocator(__bucket_list_deallocator&& __x) 699 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 700 : __data_(_VSTD::move(__x.__data_)) 701 { 702 __x.size() = 0; 703 } 704 705 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 706 707 _LIBCPP_INLINE_VISIBILITY 708 size_type& size() _NOEXCEPT {return __data_.first();} 709 _LIBCPP_INLINE_VISIBILITY 710 size_type size() const _NOEXCEPT {return __data_.first();} 711 712 _LIBCPP_INLINE_VISIBILITY 713 allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 714 _LIBCPP_INLINE_VISIBILITY 715 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 716 717 _LIBCPP_INLINE_VISIBILITY 718 void operator()(pointer __p) _NOEXCEPT 719 { 720 __alloc_traits::deallocate(__alloc(), __p, size()); 721 } 722 }; 723 724 template <class _Alloc> class __hash_map_node_destructor; 725 726 template <class _Alloc> 727 class __hash_node_destructor 728 { 729 typedef _Alloc allocator_type; 730 typedef allocator_traits<allocator_type> __alloc_traits; 731 typedef typename __alloc_traits::value_type::value_type value_type; 732 public: 733 typedef typename __alloc_traits::pointer pointer; 734 private: 735 736 allocator_type& __na_; 737 738 __hash_node_destructor& operator=(const __hash_node_destructor&); 739 740 public: 741 bool __value_constructed; 742 743 _LIBCPP_INLINE_VISIBILITY 744 explicit __hash_node_destructor(allocator_type& __na, 745 bool __constructed = false) _NOEXCEPT 746 : __na_(__na), 747 __value_constructed(__constructed) 748 {} 749 750 _LIBCPP_INLINE_VISIBILITY 751 void operator()(pointer __p) _NOEXCEPT 752 { 753 if (__value_constructed) 754 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 755 if (__p) 756 __alloc_traits::deallocate(__na_, __p, 1); 757 } 758 759 template <class> friend class __hash_map_node_destructor; 760 }; 761 762 template <class _Tp, class _Hash, class _Equal, class _Alloc> 763 class __hash_table 764 { 765 public: 766 typedef _Tp value_type; 767 typedef _Hash hasher; 768 typedef _Equal key_equal; 769 typedef _Alloc allocator_type; 770 771 private: 772 typedef allocator_traits<allocator_type> __alloc_traits; 773 public: 774 typedef value_type& reference; 775 typedef const value_type& const_reference; 776 typedef typename __alloc_traits::pointer pointer; 777 typedef typename __alloc_traits::const_pointer const_pointer; 778 typedef typename __alloc_traits::size_type size_type; 779 typedef typename __alloc_traits::difference_type difference_type; 780 public: 781 // Create __node 782 typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 783 typedef typename __alloc_traits::template 784 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 785 rebind_alloc<__node> 786 #else 787 rebind_alloc<__node>::other 788 #endif 789 __node_allocator; 790 typedef allocator_traits<__node_allocator> __node_traits; 791 typedef typename __node_traits::pointer __node_pointer; 792 typedef typename __node_traits::pointer __node_const_pointer; 793 typedef __hash_node_base<__node_pointer> __first_node; 794 typedef typename pointer_traits<__node_pointer>::template 795 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 796 rebind<__first_node> 797 #else 798 rebind<__first_node>::other 799 #endif 800 __node_base_pointer; 801 802 private: 803 804 typedef typename __node_traits::template 805 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 806 rebind_alloc<__node_pointer> 807 #else 808 rebind_alloc<__node_pointer>::other 809 #endif 810 __pointer_allocator; 811 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 812 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 813 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 814 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 815 816 // --- Member data begin --- 817 __bucket_list __bucket_list_; 818 __compressed_pair<__first_node, __node_allocator> __p1_; 819 __compressed_pair<size_type, hasher> __p2_; 820 __compressed_pair<float, key_equal> __p3_; 821 // --- Member data end --- 822 823 _LIBCPP_INLINE_VISIBILITY 824 size_type& size() _NOEXCEPT {return __p2_.first();} 825 public: 826 _LIBCPP_INLINE_VISIBILITY 827 size_type size() const _NOEXCEPT {return __p2_.first();} 828 829 _LIBCPP_INLINE_VISIBILITY 830 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 831 _LIBCPP_INLINE_VISIBILITY 832 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 833 834 _LIBCPP_INLINE_VISIBILITY 835 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 836 _LIBCPP_INLINE_VISIBILITY 837 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 838 839 _LIBCPP_INLINE_VISIBILITY 840 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 841 _LIBCPP_INLINE_VISIBILITY 842 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 843 844 _LIBCPP_INLINE_VISIBILITY 845 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 846 _LIBCPP_INLINE_VISIBILITY 847 const __node_allocator& __node_alloc() const _NOEXCEPT 848 {return __p1_.second();} 849 850 public: 851 typedef __hash_iterator<__node_pointer> iterator; 852 typedef __hash_const_iterator<__node_pointer> const_iterator; 853 typedef __hash_local_iterator<__node_pointer> local_iterator; 854 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 855 856 __hash_table() 857 _NOEXCEPT_( 858 is_nothrow_default_constructible<__bucket_list>::value && 859 is_nothrow_default_constructible<__first_node>::value && 860 is_nothrow_default_constructible<__node_allocator>::value && 861 is_nothrow_default_constructible<hasher>::value && 862 is_nothrow_default_constructible<key_equal>::value); 863 __hash_table(const hasher& __hf, const key_equal& __eql); 864 __hash_table(const hasher& __hf, const key_equal& __eql, 865 const allocator_type& __a); 866 explicit __hash_table(const allocator_type& __a); 867 __hash_table(const __hash_table& __u); 868 __hash_table(const __hash_table& __u, const allocator_type& __a); 869 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 870 __hash_table(__hash_table&& __u) 871 _NOEXCEPT_( 872 is_nothrow_move_constructible<__bucket_list>::value && 873 is_nothrow_move_constructible<__first_node>::value && 874 is_nothrow_move_constructible<__node_allocator>::value && 875 is_nothrow_move_constructible<hasher>::value && 876 is_nothrow_move_constructible<key_equal>::value); 877 __hash_table(__hash_table&& __u, const allocator_type& __a); 878 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 879 ~__hash_table(); 880 881 __hash_table& operator=(const __hash_table& __u); 882 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 883 __hash_table& operator=(__hash_table&& __u) 884 _NOEXCEPT_( 885 __node_traits::propagate_on_container_move_assignment::value && 886 is_nothrow_move_assignable<__node_allocator>::value && 887 is_nothrow_move_assignable<hasher>::value && 888 is_nothrow_move_assignable<key_equal>::value); 889 #endif 890 template <class _InputIterator> 891 void __assign_unique(_InputIterator __first, _InputIterator __last); 892 template <class _InputIterator> 893 void __assign_multi(_InputIterator __first, _InputIterator __last); 894 895 _LIBCPP_INLINE_VISIBILITY 896 size_type max_size() const _NOEXCEPT 897 { 898 return allocator_traits<__pointer_allocator>::max_size( 899 __bucket_list_.get_deleter().__alloc()); 900 } 901 902 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 903 iterator __node_insert_multi(__node_pointer __nd); 904 iterator __node_insert_multi(const_iterator __p, 905 __node_pointer __nd); 906 907 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 908 template <class... _Args> 909 pair<iterator, bool> __emplace_unique(_Args&&... __args); 910 template <class... _Args> 911 iterator __emplace_multi(_Args&&... __args); 912 template <class... _Args> 913 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 914 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 915 916 pair<iterator, bool> __insert_unique(const value_type& __x); 917 918 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 919 template <class _Pp> 920 pair<iterator, bool> __insert_unique(_Pp&& __x); 921 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 922 923 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 924 template <class _Pp> 925 iterator __insert_multi(_Pp&& __x); 926 template <class _Pp> 927 iterator __insert_multi(const_iterator __p, _Pp&& __x); 928 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 929 iterator __insert_multi(const value_type& __x); 930 iterator __insert_multi(const_iterator __p, const value_type& __x); 931 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 932 933 void clear() _NOEXCEPT; 934 void rehash(size_type __n); 935 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 936 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 937 938 _LIBCPP_INLINE_VISIBILITY 939 size_type bucket_count() const _NOEXCEPT 940 { 941 return __bucket_list_.get_deleter().size(); 942 } 943 944 iterator begin() _NOEXCEPT; 945 iterator end() _NOEXCEPT; 946 const_iterator begin() const _NOEXCEPT; 947 const_iterator end() const _NOEXCEPT; 948 949 template <class _Key> 950 _LIBCPP_INLINE_VISIBILITY 951 size_type bucket(const _Key& __k) const 952 { 953 _LIBCPP_ASSERT(bucket_count() > 0, 954 "unordered container::bucket(key) called when bucket_count() == 0"); 955 return __constrain_hash(hash_function()(__k), bucket_count()); 956 } 957 958 template <class _Key> 959 iterator find(const _Key& __x); 960 template <class _Key> 961 const_iterator find(const _Key& __x) const; 962 963 typedef __hash_node_destructor<__node_allocator> _Dp; 964 typedef unique_ptr<__node, _Dp> __node_holder; 965 966 iterator erase(const_iterator __p); 967 iterator erase(const_iterator __first, const_iterator __last); 968 template <class _Key> 969 size_type __erase_unique(const _Key& __k); 970 template <class _Key> 971 size_type __erase_multi(const _Key& __k); 972 __node_holder remove(const_iterator __p) _NOEXCEPT; 973 974 template <class _Key> 975 size_type __count_unique(const _Key& __k) const; 976 template <class _Key> 977 size_type __count_multi(const _Key& __k) const; 978 979 template <class _Key> 980 pair<iterator, iterator> 981 __equal_range_unique(const _Key& __k); 982 template <class _Key> 983 pair<const_iterator, const_iterator> 984 __equal_range_unique(const _Key& __k) const; 985 986 template <class _Key> 987 pair<iterator, iterator> 988 __equal_range_multi(const _Key& __k); 989 template <class _Key> 990 pair<const_iterator, const_iterator> 991 __equal_range_multi(const _Key& __k) const; 992 993 void swap(__hash_table& __u) 994 _NOEXCEPT_( 995 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 996 __is_nothrow_swappable<__pointer_allocator>::value) && 997 (!__node_traits::propagate_on_container_swap::value || 998 __is_nothrow_swappable<__node_allocator>::value) && 999 __is_nothrow_swappable<hasher>::value && 1000 __is_nothrow_swappable<key_equal>::value); 1001 1002 _LIBCPP_INLINE_VISIBILITY 1003 size_type max_bucket_count() const _NOEXCEPT 1004 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1005 size_type bucket_size(size_type __n) const; 1006 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1007 { 1008 size_type __bc = bucket_count(); 1009 return __bc != 0 ? (float)size() / __bc : 0.f; 1010 } 1011 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1012 { 1013 _LIBCPP_ASSERT(__mlf > 0, 1014 "unordered container::max_load_factor(lf) called with lf <= 0"); 1015 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1016 } 1017 1018 _LIBCPP_INLINE_VISIBILITY 1019 local_iterator 1020 begin(size_type __n) 1021 { 1022 _LIBCPP_ASSERT(__n < bucket_count(), 1023 "unordered container::begin(n) called with n >= bucket_count()"); 1024 #if _LIBCPP_DEBUG_LEVEL >= 2 1025 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1026 #else 1027 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1028 #endif 1029 } 1030 1031 _LIBCPP_INLINE_VISIBILITY 1032 local_iterator 1033 end(size_type __n) 1034 { 1035 _LIBCPP_ASSERT(__n < bucket_count(), 1036 "unordered container::end(n) called with n >= bucket_count()"); 1037 #if _LIBCPP_DEBUG_LEVEL >= 2 1038 return local_iterator(nullptr, __n, bucket_count(), this); 1039 #else 1040 return local_iterator(nullptr, __n, bucket_count()); 1041 #endif 1042 } 1043 1044 _LIBCPP_INLINE_VISIBILITY 1045 const_local_iterator 1046 cbegin(size_type __n) const 1047 { 1048 _LIBCPP_ASSERT(__n < bucket_count(), 1049 "unordered container::cbegin(n) called with n >= bucket_count()"); 1050 #if _LIBCPP_DEBUG_LEVEL >= 2 1051 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1052 #else 1053 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1054 #endif 1055 } 1056 1057 _LIBCPP_INLINE_VISIBILITY 1058 const_local_iterator 1059 cend(size_type __n) const 1060 { 1061 _LIBCPP_ASSERT(__n < bucket_count(), 1062 "unordered container::cend(n) called with n >= bucket_count()"); 1063 #if _LIBCPP_DEBUG_LEVEL >= 2 1064 return const_local_iterator(nullptr, __n, bucket_count(), this); 1065 #else 1066 return const_local_iterator(nullptr, __n, bucket_count()); 1067 #endif 1068 } 1069 1070 #if _LIBCPP_DEBUG_LEVEL >= 2 1071 1072 bool __dereferenceable(const const_iterator* __i) const; 1073 bool __decrementable(const const_iterator* __i) const; 1074 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1075 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1076 1077 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1078 1079 private: 1080 void __rehash(size_type __n); 1081 1082 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1083 #ifndef _LIBCPP_HAS_NO_VARIADICS 1084 template <class ..._Args> 1085 __node_holder __construct_node(_Args&& ...__args); 1086 #endif // _LIBCPP_HAS_NO_VARIADICS 1087 __node_holder __construct_node(value_type&& __v, size_t __hash); 1088 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1089 __node_holder __construct_node(const value_type& __v); 1090 #endif 1091 __node_holder __construct_node(const value_type& __v, size_t __hash); 1092 1093 _LIBCPP_INLINE_VISIBILITY 1094 void __copy_assign_alloc(const __hash_table& __u) 1095 {__copy_assign_alloc(__u, integral_constant<bool, 1096 __node_traits::propagate_on_container_copy_assignment::value>());} 1097 void __copy_assign_alloc(const __hash_table& __u, true_type); 1098 _LIBCPP_INLINE_VISIBILITY 1099 void __copy_assign_alloc(const __hash_table&, false_type) {} 1100 1101 void __move_assign(__hash_table& __u, false_type); 1102 void __move_assign(__hash_table& __u, true_type) 1103 _NOEXCEPT_( 1104 is_nothrow_move_assignable<__node_allocator>::value && 1105 is_nothrow_move_assignable<hasher>::value && 1106 is_nothrow_move_assignable<key_equal>::value); 1107 _LIBCPP_INLINE_VISIBILITY 1108 void __move_assign_alloc(__hash_table& __u) 1109 _NOEXCEPT_( 1110 !__node_traits::propagate_on_container_move_assignment::value || 1111 (is_nothrow_move_assignable<__pointer_allocator>::value && 1112 is_nothrow_move_assignable<__node_allocator>::value)) 1113 {__move_assign_alloc(__u, integral_constant<bool, 1114 __node_traits::propagate_on_container_move_assignment::value>());} 1115 _LIBCPP_INLINE_VISIBILITY 1116 void __move_assign_alloc(__hash_table& __u, true_type) 1117 _NOEXCEPT_( 1118 is_nothrow_move_assignable<__pointer_allocator>::value && 1119 is_nothrow_move_assignable<__node_allocator>::value) 1120 { 1121 __bucket_list_.get_deleter().__alloc() = 1122 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1123 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1124 } 1125 _LIBCPP_INLINE_VISIBILITY 1126 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1127 1128 template <class _Ap> 1129 _LIBCPP_INLINE_VISIBILITY 1130 static 1131 void 1132 __swap_alloc(_Ap& __x, _Ap& __y) 1133 _NOEXCEPT_( 1134 !allocator_traits<_Ap>::propagate_on_container_swap::value || 1135 __is_nothrow_swappable<_Ap>::value) 1136 { 1137 __swap_alloc(__x, __y, 1138 integral_constant<bool, 1139 allocator_traits<_Ap>::propagate_on_container_swap::value 1140 >()); 1141 } 1142 1143 template <class _Ap> 1144 _LIBCPP_INLINE_VISIBILITY 1145 static 1146 void 1147 __swap_alloc(_Ap& __x, _Ap& __y, true_type) 1148 _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 1149 { 1150 using _VSTD::swap; 1151 swap(__x, __y); 1152 } 1153 1154 template <class _Ap> 1155 _LIBCPP_INLINE_VISIBILITY 1156 static 1157 void 1158 __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 1159 1160 void __deallocate(__node_pointer __np) _NOEXCEPT; 1161 __node_pointer __detach() _NOEXCEPT; 1162 1163 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1164 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1165 }; 1166 1167 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1168 inline _LIBCPP_INLINE_VISIBILITY 1169 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1170 _NOEXCEPT_( 1171 is_nothrow_default_constructible<__bucket_list>::value && 1172 is_nothrow_default_constructible<__first_node>::value && 1173 is_nothrow_default_constructible<hasher>::value && 1174 is_nothrow_default_constructible<key_equal>::value) 1175 : __p2_(0), 1176 __p3_(1.0f) 1177 { 1178 } 1179 1180 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1181 inline _LIBCPP_INLINE_VISIBILITY 1182 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1183 const key_equal& __eql) 1184 : __bucket_list_(nullptr, __bucket_list_deleter()), 1185 __p1_(), 1186 __p2_(0, __hf), 1187 __p3_(1.0f, __eql) 1188 { 1189 } 1190 1191 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1192 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1193 const key_equal& __eql, 1194 const allocator_type& __a) 1195 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1196 __p1_(__node_allocator(__a)), 1197 __p2_(0, __hf), 1198 __p3_(1.0f, __eql) 1199 { 1200 } 1201 1202 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1203 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1204 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1205 __p1_(__node_allocator(__a)), 1206 __p2_(0), 1207 __p3_(1.0f) 1208 { 1209 } 1210 1211 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1212 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1213 : __bucket_list_(nullptr, 1214 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1215 select_on_container_copy_construction( 1216 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1217 __p1_(allocator_traits<__node_allocator>:: 1218 select_on_container_copy_construction(__u.__node_alloc())), 1219 __p2_(0, __u.hash_function()), 1220 __p3_(__u.__p3_) 1221 { 1222 } 1223 1224 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1225 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1226 const allocator_type& __a) 1227 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1228 __p1_(__node_allocator(__a)), 1229 __p2_(0, __u.hash_function()), 1230 __p3_(__u.__p3_) 1231 { 1232 } 1233 1234 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1235 1236 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1237 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1238 _NOEXCEPT_( 1239 is_nothrow_move_constructible<__bucket_list>::value && 1240 is_nothrow_move_constructible<__first_node>::value && 1241 is_nothrow_move_constructible<hasher>::value && 1242 is_nothrow_move_constructible<key_equal>::value) 1243 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1244 __p1_(_VSTD::move(__u.__p1_)), 1245 __p2_(_VSTD::move(__u.__p2_)), 1246 __p3_(_VSTD::move(__u.__p3_)) 1247 { 1248 if (size() > 0) 1249 { 1250 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1251 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1252 __u.__p1_.first().__next_ = nullptr; 1253 __u.size() = 0; 1254 } 1255 } 1256 1257 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1258 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1259 const allocator_type& __a) 1260 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1261 __p1_(__node_allocator(__a)), 1262 __p2_(0, _VSTD::move(__u.hash_function())), 1263 __p3_(_VSTD::move(__u.__p3_)) 1264 { 1265 if (__a == allocator_type(__u.__node_alloc())) 1266 { 1267 __bucket_list_.reset(__u.__bucket_list_.release()); 1268 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1269 __u.__bucket_list_.get_deleter().size() = 0; 1270 if (__u.size() > 0) 1271 { 1272 __p1_.first().__next_ = __u.__p1_.first().__next_; 1273 __u.__p1_.first().__next_ = nullptr; 1274 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1275 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1276 size() = __u.size(); 1277 __u.size() = 0; 1278 } 1279 } 1280 } 1281 1282 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1283 1284 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1285 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1286 { 1287 __deallocate(__p1_.first().__next_); 1288 #if _LIBCPP_DEBUG_LEVEL >= 2 1289 __get_db()->__erase_c(this); 1290 #endif 1291 } 1292 1293 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1294 void 1295 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1296 const __hash_table& __u, true_type) 1297 { 1298 if (__node_alloc() != __u.__node_alloc()) 1299 { 1300 clear(); 1301 __bucket_list_.reset(); 1302 __bucket_list_.get_deleter().size() = 0; 1303 } 1304 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1305 __node_alloc() = __u.__node_alloc(); 1306 } 1307 1308 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1309 __hash_table<_Tp, _Hash, _Equal, _Alloc>& 1310 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1311 { 1312 if (this != &__u) 1313 { 1314 __copy_assign_alloc(__u); 1315 hash_function() = __u.hash_function(); 1316 key_eq() = __u.key_eq(); 1317 max_load_factor() = __u.max_load_factor(); 1318 __assign_multi(__u.begin(), __u.end()); 1319 } 1320 return *this; 1321 } 1322 1323 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1324 void 1325 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1326 _NOEXCEPT 1327 { 1328 __node_allocator& __na = __node_alloc(); 1329 while (__np != nullptr) 1330 { 1331 __node_pointer __next = __np->__next_; 1332 #if _LIBCPP_DEBUG_LEVEL >= 2 1333 __c_node* __c = __get_db()->__find_c_and_lock(this); 1334 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1335 { 1336 --__p; 1337 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1338 if (__i->__node_ == __np) 1339 { 1340 (*__p)->__c_ = nullptr; 1341 if (--__c->end_ != __p) 1342 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1343 } 1344 } 1345 __get_db()->unlock(); 1346 #endif 1347 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1348 __node_traits::deallocate(__na, __np, 1); 1349 __np = __next; 1350 } 1351 } 1352 1353 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1354 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1355 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1356 { 1357 size_type __bc = bucket_count(); 1358 for (size_type __i = 0; __i < __bc; ++__i) 1359 __bucket_list_[__i] = nullptr; 1360 size() = 0; 1361 __node_pointer __cache = __p1_.first().__next_; 1362 __p1_.first().__next_ = nullptr; 1363 return __cache; 1364 } 1365 1366 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1367 1368 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1369 void 1370 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1371 __hash_table& __u, true_type) 1372 _NOEXCEPT_( 1373 is_nothrow_move_assignable<__node_allocator>::value && 1374 is_nothrow_move_assignable<hasher>::value && 1375 is_nothrow_move_assignable<key_equal>::value) 1376 { 1377 clear(); 1378 __bucket_list_.reset(__u.__bucket_list_.release()); 1379 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1380 __u.__bucket_list_.get_deleter().size() = 0; 1381 __move_assign_alloc(__u); 1382 size() = __u.size(); 1383 hash_function() = _VSTD::move(__u.hash_function()); 1384 max_load_factor() = __u.max_load_factor(); 1385 key_eq() = _VSTD::move(__u.key_eq()); 1386 __p1_.first().__next_ = __u.__p1_.first().__next_; 1387 if (size() > 0) 1388 { 1389 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1390 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1391 __u.__p1_.first().__next_ = nullptr; 1392 __u.size() = 0; 1393 } 1394 #if _LIBCPP_DEBUG_LEVEL >= 2 1395 __get_db()->swap(this, &__u); 1396 #endif 1397 } 1398 1399 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1400 void 1401 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1402 __hash_table& __u, false_type) 1403 { 1404 if (__node_alloc() == __u.__node_alloc()) 1405 __move_assign(__u, true_type()); 1406 else 1407 { 1408 hash_function() = _VSTD::move(__u.hash_function()); 1409 key_eq() = _VSTD::move(__u.key_eq()); 1410 max_load_factor() = __u.max_load_factor(); 1411 if (bucket_count() != 0) 1412 { 1413 __node_pointer __cache = __detach(); 1414 #ifndef _LIBCPP_NO_EXCEPTIONS 1415 try 1416 { 1417 #endif // _LIBCPP_NO_EXCEPTIONS 1418 const_iterator __i = __u.begin(); 1419 while (__cache != nullptr && __u.size() != 0) 1420 { 1421 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1422 __node_pointer __next = __cache->__next_; 1423 __node_insert_multi(__cache); 1424 __cache = __next; 1425 } 1426 #ifndef _LIBCPP_NO_EXCEPTIONS 1427 } 1428 catch (...) 1429 { 1430 __deallocate(__cache); 1431 throw; 1432 } 1433 #endif // _LIBCPP_NO_EXCEPTIONS 1434 __deallocate(__cache); 1435 } 1436 const_iterator __i = __u.begin(); 1437 while (__u.size() != 0) 1438 { 1439 __node_holder __h = 1440 __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1441 __node_insert_multi(__h.get()); 1442 __h.release(); 1443 } 1444 } 1445 } 1446 1447 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1448 inline _LIBCPP_INLINE_VISIBILITY 1449 __hash_table<_Tp, _Hash, _Equal, _Alloc>& 1450 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1451 _NOEXCEPT_( 1452 __node_traits::propagate_on_container_move_assignment::value && 1453 is_nothrow_move_assignable<__node_allocator>::value && 1454 is_nothrow_move_assignable<hasher>::value && 1455 is_nothrow_move_assignable<key_equal>::value) 1456 { 1457 __move_assign(__u, integral_constant<bool, 1458 __node_traits::propagate_on_container_move_assignment::value>()); 1459 return *this; 1460 } 1461 1462 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1463 1464 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1465 template <class _InputIterator> 1466 void 1467 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1468 _InputIterator __last) 1469 { 1470 if (bucket_count() != 0) 1471 { 1472 __node_pointer __cache = __detach(); 1473 #ifndef _LIBCPP_NO_EXCEPTIONS 1474 try 1475 { 1476 #endif // _LIBCPP_NO_EXCEPTIONS 1477 for (; __cache != nullptr && __first != __last; ++__first) 1478 { 1479 __cache->__value_ = *__first; 1480 __node_pointer __next = __cache->__next_; 1481 __node_insert_unique(__cache); 1482 __cache = __next; 1483 } 1484 #ifndef _LIBCPP_NO_EXCEPTIONS 1485 } 1486 catch (...) 1487 { 1488 __deallocate(__cache); 1489 throw; 1490 } 1491 #endif // _LIBCPP_NO_EXCEPTIONS 1492 __deallocate(__cache); 1493 } 1494 for (; __first != __last; ++__first) 1495 __insert_unique(*__first); 1496 } 1497 1498 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1499 template <class _InputIterator> 1500 void 1501 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1502 _InputIterator __last) 1503 { 1504 if (bucket_count() != 0) 1505 { 1506 __node_pointer __cache = __detach(); 1507 #ifndef _LIBCPP_NO_EXCEPTIONS 1508 try 1509 { 1510 #endif // _LIBCPP_NO_EXCEPTIONS 1511 for (; __cache != nullptr && __first != __last; ++__first) 1512 { 1513 __cache->__value_ = *__first; 1514 __node_pointer __next = __cache->__next_; 1515 __node_insert_multi(__cache); 1516 __cache = __next; 1517 } 1518 #ifndef _LIBCPP_NO_EXCEPTIONS 1519 } 1520 catch (...) 1521 { 1522 __deallocate(__cache); 1523 throw; 1524 } 1525 #endif // _LIBCPP_NO_EXCEPTIONS 1526 __deallocate(__cache); 1527 } 1528 for (; __first != __last; ++__first) 1529 __insert_multi(*__first); 1530 } 1531 1532 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1533 inline _LIBCPP_INLINE_VISIBILITY 1534 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1535 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1536 { 1537 #if _LIBCPP_DEBUG_LEVEL >= 2 1538 return iterator(__p1_.first().__next_, this); 1539 #else 1540 return iterator(__p1_.first().__next_); 1541 #endif 1542 } 1543 1544 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1545 inline _LIBCPP_INLINE_VISIBILITY 1546 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1547 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1548 { 1549 #if _LIBCPP_DEBUG_LEVEL >= 2 1550 return iterator(nullptr, this); 1551 #else 1552 return iterator(nullptr); 1553 #endif 1554 } 1555 1556 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1557 inline _LIBCPP_INLINE_VISIBILITY 1558 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1559 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1560 { 1561 #if _LIBCPP_DEBUG_LEVEL >= 2 1562 return const_iterator(__p1_.first().__next_, this); 1563 #else 1564 return const_iterator(__p1_.first().__next_); 1565 #endif 1566 } 1567 1568 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1569 inline _LIBCPP_INLINE_VISIBILITY 1570 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1571 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1572 { 1573 #if _LIBCPP_DEBUG_LEVEL >= 2 1574 return const_iterator(nullptr, this); 1575 #else 1576 return const_iterator(nullptr); 1577 #endif 1578 } 1579 1580 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1581 void 1582 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1583 { 1584 if (size() > 0) 1585 { 1586 __deallocate(__p1_.first().__next_); 1587 __p1_.first().__next_ = nullptr; 1588 size_type __bc = bucket_count(); 1589 for (size_type __i = 0; __i < __bc; ++__i) 1590 __bucket_list_[__i] = nullptr; 1591 size() = 0; 1592 } 1593 } 1594 1595 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1596 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1597 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1598 { 1599 __nd->__hash_ = hash_function()(__nd->__value_); 1600 size_type __bc = bucket_count(); 1601 bool __inserted = false; 1602 __node_pointer __ndptr; 1603 size_t __chash; 1604 if (__bc != 0) 1605 { 1606 __chash = __constrain_hash(__nd->__hash_, __bc); 1607 __ndptr = __bucket_list_[__chash]; 1608 if (__ndptr != nullptr) 1609 { 1610 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1611 __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1612 __ndptr = __ndptr->__next_) 1613 { 1614 if (key_eq()(__ndptr->__value_, __nd->__value_)) 1615 goto __done; 1616 } 1617 } 1618 } 1619 { 1620 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1621 { 1622 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1623 size_type(ceil(float(size() + 1) / max_load_factor())))); 1624 __bc = bucket_count(); 1625 __chash = __constrain_hash(__nd->__hash_, __bc); 1626 } 1627 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1628 __node_pointer __pn = __bucket_list_[__chash]; 1629 if (__pn == nullptr) 1630 { 1631 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1632 __nd->__next_ = __pn->__next_; 1633 __pn->__next_ = __nd; 1634 // fix up __bucket_list_ 1635 __bucket_list_[__chash] = __pn; 1636 if (__nd->__next_ != nullptr) 1637 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1638 } 1639 else 1640 { 1641 __nd->__next_ = __pn->__next_; 1642 __pn->__next_ = __nd; 1643 } 1644 __ndptr = __nd; 1645 // increment size 1646 ++size(); 1647 __inserted = true; 1648 } 1649 __done: 1650 #if _LIBCPP_DEBUG_LEVEL >= 2 1651 return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1652 #else 1653 return pair<iterator, bool>(iterator(__ndptr), __inserted); 1654 #endif 1655 } 1656 1657 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1658 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1659 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1660 { 1661 __cp->__hash_ = hash_function()(__cp->__value_); 1662 size_type __bc = bucket_count(); 1663 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1664 { 1665 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1666 size_type(ceil(float(size() + 1) / max_load_factor())))); 1667 __bc = bucket_count(); 1668 } 1669 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1670 __node_pointer __pn = __bucket_list_[__chash]; 1671 if (__pn == nullptr) 1672 { 1673 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1674 __cp->__next_ = __pn->__next_; 1675 __pn->__next_ = __cp; 1676 // fix up __bucket_list_ 1677 __bucket_list_[__chash] = __pn; 1678 if (__cp->__next_ != nullptr) 1679 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1680 } 1681 else 1682 { 1683 for (bool __found = false; __pn->__next_ != nullptr && 1684 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1685 __pn = __pn->__next_) 1686 { 1687 // __found key_eq() action 1688 // false false loop 1689 // true true loop 1690 // false true set __found to true 1691 // true false break 1692 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1693 key_eq()(__pn->__next_->__value_, __cp->__value_))) 1694 { 1695 if (!__found) 1696 __found = true; 1697 else 1698 break; 1699 } 1700 } 1701 __cp->__next_ = __pn->__next_; 1702 __pn->__next_ = __cp; 1703 if (__cp->__next_ != nullptr) 1704 { 1705 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1706 if (__nhash != __chash) 1707 __bucket_list_[__nhash] = __cp; 1708 } 1709 } 1710 ++size(); 1711 #if _LIBCPP_DEBUG_LEVEL >= 2 1712 return iterator(__cp, this); 1713 #else 1714 return iterator(__cp); 1715 #endif 1716 } 1717 1718 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1719 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1720 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1721 const_iterator __p, __node_pointer __cp) 1722 { 1723 #if _LIBCPP_DEBUG_LEVEL >= 2 1724 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1725 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1726 " referring to this unordered container"); 1727 #endif 1728 if (__p != end() && key_eq()(*__p, __cp->__value_)) 1729 { 1730 __node_pointer __np = __p.__node_; 1731 __cp->__hash_ = __np->__hash_; 1732 size_type __bc = bucket_count(); 1733 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1734 { 1735 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1736 size_type(ceil(float(size() + 1) / max_load_factor())))); 1737 __bc = bucket_count(); 1738 } 1739 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1740 __node_pointer __pp = __bucket_list_[__chash]; 1741 while (__pp->__next_ != __np) 1742 __pp = __pp->__next_; 1743 __cp->__next_ = __np; 1744 __pp->__next_ = __cp; 1745 ++size(); 1746 #if _LIBCPP_DEBUG_LEVEL >= 2 1747 return iterator(__cp, this); 1748 #else 1749 return iterator(__cp); 1750 #endif 1751 } 1752 return __node_insert_multi(__cp); 1753 } 1754 1755 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1756 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1757 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1758 { 1759 size_t __hash = hash_function()(__x); 1760 size_type __bc = bucket_count(); 1761 bool __inserted = false; 1762 __node_pointer __nd; 1763 size_t __chash; 1764 if (__bc != 0) 1765 { 1766 __chash = __constrain_hash(__hash, __bc); 1767 __nd = __bucket_list_[__chash]; 1768 if (__nd != nullptr) 1769 { 1770 for (__nd = __nd->__next_; __nd != nullptr && 1771 __constrain_hash(__nd->__hash_, __bc) == __chash; 1772 __nd = __nd->__next_) 1773 { 1774 if (key_eq()(__nd->__value_, __x)) 1775 goto __done; 1776 } 1777 } 1778 } 1779 { 1780 __node_holder __h = __construct_node(__x, __hash); 1781 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1782 { 1783 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1784 size_type(ceil(float(size() + 1) / max_load_factor())))); 1785 __bc = bucket_count(); 1786 __chash = __constrain_hash(__hash, __bc); 1787 } 1788 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1789 __node_pointer __pn = __bucket_list_[__chash]; 1790 if (__pn == nullptr) 1791 { 1792 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1793 __h->__next_ = __pn->__next_; 1794 __pn->__next_ = __h.get(); 1795 // fix up __bucket_list_ 1796 __bucket_list_[__chash] = __pn; 1797 if (__h->__next_ != nullptr) 1798 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1799 } 1800 else 1801 { 1802 __h->__next_ = __pn->__next_; 1803 __pn->__next_ = __h.get(); 1804 } 1805 __nd = __h.release(); 1806 // increment size 1807 ++size(); 1808 __inserted = true; 1809 } 1810 __done: 1811 #if _LIBCPP_DEBUG_LEVEL >= 2 1812 return pair<iterator, bool>(iterator(__nd, this), __inserted); 1813 #else 1814 return pair<iterator, bool>(iterator(__nd), __inserted); 1815 #endif 1816 } 1817 1818 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1819 #ifndef _LIBCPP_HAS_NO_VARIADICS 1820 1821 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1822 template <class... _Args> 1823 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1824 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1825 { 1826 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1827 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1828 if (__r.second) 1829 __h.release(); 1830 return __r; 1831 } 1832 1833 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1834 template <class... _Args> 1835 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1836 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1837 { 1838 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1839 iterator __r = __node_insert_multi(__h.get()); 1840 __h.release(); 1841 return __r; 1842 } 1843 1844 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1845 template <class... _Args> 1846 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1847 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1848 const_iterator __p, _Args&&... __args) 1849 { 1850 #if _LIBCPP_DEBUG_LEVEL >= 2 1851 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1852 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1853 " referring to this unordered container"); 1854 #endif 1855 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1856 iterator __r = __node_insert_multi(__p, __h.get()); 1857 __h.release(); 1858 return __r; 1859 } 1860 1861 #endif // _LIBCPP_HAS_NO_VARIADICS 1862 1863 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1864 template <class _Pp> 1865 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1866 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1867 { 1868 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1869 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1870 if (__r.second) 1871 __h.release(); 1872 return __r; 1873 } 1874 1875 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1876 1877 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1878 1879 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1880 template <class _Pp> 1881 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1882 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1883 { 1884 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1885 iterator __r = __node_insert_multi(__h.get()); 1886 __h.release(); 1887 return __r; 1888 } 1889 1890 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1891 template <class _Pp> 1892 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1893 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1894 _Pp&& __x) 1895 { 1896 #if _LIBCPP_DEBUG_LEVEL >= 2 1897 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1898 "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1899 " referring to this unordered container"); 1900 #endif 1901 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1902 iterator __r = __node_insert_multi(__p, __h.get()); 1903 __h.release(); 1904 return __r; 1905 } 1906 1907 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1908 1909 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1910 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1911 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1912 { 1913 __node_holder __h = __construct_node(__x); 1914 iterator __r = __node_insert_multi(__h.get()); 1915 __h.release(); 1916 return __r; 1917 } 1918 1919 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1920 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1921 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1922 const value_type& __x) 1923 { 1924 #if _LIBCPP_DEBUG_LEVEL >= 2 1925 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1926 "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1927 " referring to this unordered container"); 1928 #endif 1929 __node_holder __h = __construct_node(__x); 1930 iterator __r = __node_insert_multi(__p, __h.get()); 1931 __h.release(); 1932 return __r; 1933 } 1934 1935 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1936 1937 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1938 void 1939 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1940 { 1941 if (__n == 1) 1942 __n = 2; 1943 else if (__n & (__n - 1)) 1944 __n = __next_prime(__n); 1945 size_type __bc = bucket_count(); 1946 if (__n > __bc) 1947 __rehash(__n); 1948 else if (__n < __bc) 1949 { 1950 __n = _VSTD::max<size_type> 1951 ( 1952 __n, 1953 __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1954 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1955 ); 1956 if (__n < __bc) 1957 __rehash(__n); 1958 } 1959 } 1960 1961 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1962 void 1963 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1964 { 1965 #if _LIBCPP_DEBUG_LEVEL >= 2 1966 __get_db()->__invalidate_all(this); 1967 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1968 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1969 __bucket_list_.reset(__nbc > 0 ? 1970 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1971 __bucket_list_.get_deleter().size() = __nbc; 1972 if (__nbc > 0) 1973 { 1974 for (size_type __i = 0; __i < __nbc; ++__i) 1975 __bucket_list_[__i] = nullptr; 1976 __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1977 __node_pointer __cp = __pp->__next_; 1978 if (__cp != nullptr) 1979 { 1980 size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1981 __bucket_list_[__chash] = __pp; 1982 size_type __phash = __chash; 1983 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1984 __cp = __pp->__next_) 1985 { 1986 __chash = __constrain_hash(__cp->__hash_, __nbc); 1987 if (__chash == __phash) 1988 __pp = __cp; 1989 else 1990 { 1991 if (__bucket_list_[__chash] == nullptr) 1992 { 1993 __bucket_list_[__chash] = __pp; 1994 __pp = __cp; 1995 __phash = __chash; 1996 } 1997 else 1998 { 1999 __node_pointer __np = __cp; 2000 for (; __np->__next_ != nullptr && 2001 key_eq()(__cp->__value_, __np->__next_->__value_); 2002 __np = __np->__next_) 2003 ; 2004 __pp->__next_ = __np->__next_; 2005 __np->__next_ = __bucket_list_[__chash]->__next_; 2006 __bucket_list_[__chash]->__next_ = __cp; 2007 2008 } 2009 } 2010 } 2011 } 2012 } 2013 } 2014 2015 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2016 template <class _Key> 2017 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2018 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2019 { 2020 size_t __hash = hash_function()(__k); 2021 size_type __bc = bucket_count(); 2022 if (__bc != 0) 2023 { 2024 size_t __chash = __constrain_hash(__hash, __bc); 2025 __node_pointer __nd = __bucket_list_[__chash]; 2026 if (__nd != nullptr) 2027 { 2028 for (__nd = __nd->__next_; __nd != nullptr && 2029 __constrain_hash(__nd->__hash_, __bc) == __chash; 2030 __nd = __nd->__next_) 2031 { 2032 if (key_eq()(__nd->__value_, __k)) 2033 #if _LIBCPP_DEBUG_LEVEL >= 2 2034 return iterator(__nd, this); 2035 #else 2036 return iterator(__nd); 2037 #endif 2038 } 2039 } 2040 } 2041 return end(); 2042 } 2043 2044 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2045 template <class _Key> 2046 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2047 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2048 { 2049 size_t __hash = hash_function()(__k); 2050 size_type __bc = bucket_count(); 2051 if (__bc != 0) 2052 { 2053 size_t __chash = __constrain_hash(__hash, __bc); 2054 __node_const_pointer __nd = __bucket_list_[__chash]; 2055 if (__nd != nullptr) 2056 { 2057 for (__nd = __nd->__next_; __nd != nullptr && 2058 __constrain_hash(__nd->__hash_, __bc) == __chash; 2059 __nd = __nd->__next_) 2060 { 2061 if (key_eq()(__nd->__value_, __k)) 2062 #if _LIBCPP_DEBUG_LEVEL >= 2 2063 return const_iterator(__nd, this); 2064 #else 2065 return const_iterator(__nd); 2066 #endif 2067 } 2068 } 2069 2070 } 2071 return end(); 2072 } 2073 2074 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2075 #ifndef _LIBCPP_HAS_NO_VARIADICS 2076 2077 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2078 template <class ..._Args> 2079 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2080 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2081 { 2082 __node_allocator& __na = __node_alloc(); 2083 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2084 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2085 __h.get_deleter().__value_constructed = true; 2086 __h->__hash_ = hash_function()(__h->__value_); 2087 __h->__next_ = nullptr; 2088 return __h; 2089 } 2090 2091 #endif // _LIBCPP_HAS_NO_VARIADICS 2092 2093 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2094 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2095 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2096 size_t __hash) 2097 { 2098 __node_allocator& __na = __node_alloc(); 2099 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2100 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2101 __h.get_deleter().__value_constructed = true; 2102 __h->__hash_ = __hash; 2103 __h->__next_ = nullptr; 2104 return __h; 2105 } 2106 2107 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2108 2109 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2110 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2111 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2112 { 2113 __node_allocator& __na = __node_alloc(); 2114 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2115 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2116 __h.get_deleter().__value_constructed = true; 2117 __h->__hash_ = hash_function()(__h->__value_); 2118 __h->__next_ = nullptr; 2119 return _VSTD::move(__h); // explicitly moved for C++03 2120 } 2121 2122 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2123 2124 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2125 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2126 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2127 size_t __hash) 2128 { 2129 __node_allocator& __na = __node_alloc(); 2130 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2131 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2132 __h.get_deleter().__value_constructed = true; 2133 __h->__hash_ = __hash; 2134 __h->__next_ = nullptr; 2135 return _VSTD::move(__h); // explicitly moved for C++03 2136 } 2137 2138 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2139 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2140 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2141 { 2142 __node_pointer __np = __p.__node_; 2143 #if _LIBCPP_DEBUG_LEVEL >= 2 2144 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2145 "unordered container erase(iterator) called with an iterator not" 2146 " referring to this container"); 2147 _LIBCPP_ASSERT(__p != end(), 2148 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2149 iterator __r(__np, this); 2150 #else 2151 iterator __r(__np); 2152 #endif 2153 ++__r; 2154 remove(__p); 2155 return __r; 2156 } 2157 2158 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2159 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2160 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2161 const_iterator __last) 2162 { 2163 #if _LIBCPP_DEBUG_LEVEL >= 2 2164 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2165 "unodered container::erase(iterator, iterator) called with an iterator not" 2166 " referring to this unodered container"); 2167 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2168 "unodered container::erase(iterator, iterator) called with an iterator not" 2169 " referring to this unodered container"); 2170 #endif 2171 for (const_iterator __p = __first; __first != __last; __p = __first) 2172 { 2173 ++__first; 2174 erase(__p); 2175 } 2176 __node_pointer __np = __last.__node_; 2177 #if _LIBCPP_DEBUG_LEVEL >= 2 2178 return iterator (__np, this); 2179 #else 2180 return iterator (__np); 2181 #endif 2182 } 2183 2184 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2185 template <class _Key> 2186 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2187 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2188 { 2189 iterator __i = find(__k); 2190 if (__i == end()) 2191 return 0; 2192 erase(__i); 2193 return 1; 2194 } 2195 2196 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2197 template <class _Key> 2198 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2199 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2200 { 2201 size_type __r = 0; 2202 iterator __i = find(__k); 2203 if (__i != end()) 2204 { 2205 iterator __e = end(); 2206 do 2207 { 2208 erase(__i++); 2209 ++__r; 2210 } while (__i != __e && key_eq()(*__i, __k)); 2211 } 2212 return __r; 2213 } 2214 2215 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2216 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2217 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2218 { 2219 // current node 2220 __node_pointer __cn = __p.__node_; 2221 size_type __bc = bucket_count(); 2222 size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2223 // find previous node 2224 __node_pointer __pn = __bucket_list_[__chash]; 2225 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2226 ; 2227 // Fix up __bucket_list_ 2228 // if __pn is not in same bucket (before begin is not in same bucket) && 2229 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2230 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2231 || __constrain_hash(__pn->__hash_, __bc) != __chash) 2232 { 2233 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2234 __bucket_list_[__chash] = nullptr; 2235 } 2236 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2237 if (__cn->__next_ != nullptr) 2238 { 2239 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2240 if (__nhash != __chash) 2241 __bucket_list_[__nhash] = __pn; 2242 } 2243 // remove __cn 2244 __pn->__next_ = __cn->__next_; 2245 __cn->__next_ = nullptr; 2246 --size(); 2247 #if _LIBCPP_DEBUG_LEVEL >= 2 2248 __c_node* __c = __get_db()->__find_c_and_lock(this); 2249 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2250 { 2251 --__p; 2252 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2253 if (__i->__node_ == __cn) 2254 { 2255 (*__p)->__c_ = nullptr; 2256 if (--__c->end_ != __p) 2257 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2258 } 2259 } 2260 __get_db()->unlock(); 2261 #endif 2262 return __node_holder(__cn, _Dp(__node_alloc(), true)); 2263 } 2264 2265 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2266 template <class _Key> 2267 inline _LIBCPP_INLINE_VISIBILITY 2268 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2269 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2270 { 2271 return static_cast<size_type>(find(__k) != end()); 2272 } 2273 2274 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2275 template <class _Key> 2276 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2277 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2278 { 2279 size_type __r = 0; 2280 const_iterator __i = find(__k); 2281 if (__i != end()) 2282 { 2283 const_iterator __e = end(); 2284 do 2285 { 2286 ++__i; 2287 ++__r; 2288 } while (__i != __e && key_eq()(*__i, __k)); 2289 } 2290 return __r; 2291 } 2292 2293 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2294 template <class _Key> 2295 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2296 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2297 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2298 const _Key& __k) 2299 { 2300 iterator __i = find(__k); 2301 iterator __j = __i; 2302 if (__i != end()) 2303 ++__j; 2304 return pair<iterator, iterator>(__i, __j); 2305 } 2306 2307 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2308 template <class _Key> 2309 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2310 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2311 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2312 const _Key& __k) const 2313 { 2314 const_iterator __i = find(__k); 2315 const_iterator __j = __i; 2316 if (__i != end()) 2317 ++__j; 2318 return pair<const_iterator, const_iterator>(__i, __j); 2319 } 2320 2321 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2322 template <class _Key> 2323 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2324 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2325 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2326 const _Key& __k) 2327 { 2328 iterator __i = find(__k); 2329 iterator __j = __i; 2330 if (__i != end()) 2331 { 2332 iterator __e = end(); 2333 do 2334 { 2335 ++__j; 2336 } while (__j != __e && key_eq()(*__j, __k)); 2337 } 2338 return pair<iterator, iterator>(__i, __j); 2339 } 2340 2341 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2342 template <class _Key> 2343 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2344 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2345 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2346 const _Key& __k) const 2347 { 2348 const_iterator __i = find(__k); 2349 const_iterator __j = __i; 2350 if (__i != end()) 2351 { 2352 const_iterator __e = end(); 2353 do 2354 { 2355 ++__j; 2356 } while (__j != __e && key_eq()(*__j, __k)); 2357 } 2358 return pair<const_iterator, const_iterator>(__i, __j); 2359 } 2360 2361 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2362 void 2363 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2364 _NOEXCEPT_( 2365 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 2366 __is_nothrow_swappable<__pointer_allocator>::value) && 2367 (!__node_traits::propagate_on_container_swap::value || 2368 __is_nothrow_swappable<__node_allocator>::value) && 2369 __is_nothrow_swappable<hasher>::value && 2370 __is_nothrow_swappable<key_equal>::value) 2371 { 2372 { 2373 __node_pointer_pointer __npp = __bucket_list_.release(); 2374 __bucket_list_.reset(__u.__bucket_list_.release()); 2375 __u.__bucket_list_.reset(__npp); 2376 } 2377 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2378 __swap_alloc(__bucket_list_.get_deleter().__alloc(), 2379 __u.__bucket_list_.get_deleter().__alloc()); 2380 __swap_alloc(__node_alloc(), __u.__node_alloc()); 2381 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2382 __p2_.swap(__u.__p2_); 2383 __p3_.swap(__u.__p3_); 2384 if (size() > 0) 2385 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2386 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2387 if (__u.size() > 0) 2388 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2389 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2390 #if _LIBCPP_DEBUG_LEVEL >= 2 2391 __get_db()->swap(this, &__u); 2392 #endif 2393 } 2394 2395 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2396 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2397 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2398 { 2399 _LIBCPP_ASSERT(__n < bucket_count(), 2400 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2401 __node_const_pointer __np = __bucket_list_[__n]; 2402 size_type __bc = bucket_count(); 2403 size_type __r = 0; 2404 if (__np != nullptr) 2405 { 2406 for (__np = __np->__next_; __np != nullptr && 2407 __constrain_hash(__np->__hash_, __bc) == __n; 2408 __np = __np->__next_, ++__r) 2409 ; 2410 } 2411 return __r; 2412 } 2413 2414 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2415 inline _LIBCPP_INLINE_VISIBILITY 2416 void 2417 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2418 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2419 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2420 { 2421 __x.swap(__y); 2422 } 2423 2424 #if _LIBCPP_DEBUG_LEVEL >= 2 2425 2426 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2427 bool 2428 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2429 { 2430 return __i->__node_ != nullptr; 2431 } 2432 2433 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2434 bool 2435 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2436 { 2437 return false; 2438 } 2439 2440 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2441 bool 2442 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2443 { 2444 return false; 2445 } 2446 2447 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2448 bool 2449 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2450 { 2451 return false; 2452 } 2453 2454 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2455 _LIBCPP_END_NAMESPACE_STD 2456 2457 #endif // _LIBCPP__HASH_TABLE 2458
