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