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