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#if _LIBCPP_STD_VER <= 11 988 _NOEXCEPT_( 989 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 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 ); 995#else 996 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 997#endif 998 999 _LIBCPP_INLINE_VISIBILITY 1000 size_type max_bucket_count() const _NOEXCEPT 1001 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1002 size_type bucket_size(size_type __n) const; 1003 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1004 { 1005 size_type __bc = bucket_count(); 1006 return __bc != 0 ? (float)size() / __bc : 0.f; 1007 } 1008 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1009 { 1010 _LIBCPP_ASSERT(__mlf > 0, 1011 "unordered container::max_load_factor(lf) called with lf <= 0"); 1012 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1013 } 1014 1015 _LIBCPP_INLINE_VISIBILITY 1016 local_iterator 1017 begin(size_type __n) 1018 { 1019 _LIBCPP_ASSERT(__n < bucket_count(), 1020 "unordered container::begin(n) called with n >= bucket_count()"); 1021#if _LIBCPP_DEBUG_LEVEL >= 2 1022 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1023#else 1024 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1025#endif 1026 } 1027 1028 _LIBCPP_INLINE_VISIBILITY 1029 local_iterator 1030 end(size_type __n) 1031 { 1032 _LIBCPP_ASSERT(__n < bucket_count(), 1033 "unordered container::end(n) called with n >= bucket_count()"); 1034#if _LIBCPP_DEBUG_LEVEL >= 2 1035 return local_iterator(nullptr, __n, bucket_count(), this); 1036#else 1037 return local_iterator(nullptr, __n, bucket_count()); 1038#endif 1039 } 1040 1041 _LIBCPP_INLINE_VISIBILITY 1042 const_local_iterator 1043 cbegin(size_type __n) const 1044 { 1045 _LIBCPP_ASSERT(__n < bucket_count(), 1046 "unordered container::cbegin(n) called with n >= bucket_count()"); 1047#if _LIBCPP_DEBUG_LEVEL >= 2 1048 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1049#else 1050 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1051#endif 1052 } 1053 1054 _LIBCPP_INLINE_VISIBILITY 1055 const_local_iterator 1056 cend(size_type __n) const 1057 { 1058 _LIBCPP_ASSERT(__n < bucket_count(), 1059 "unordered container::cend(n) called with n >= bucket_count()"); 1060#if _LIBCPP_DEBUG_LEVEL >= 2 1061 return const_local_iterator(nullptr, __n, bucket_count(), this); 1062#else 1063 return const_local_iterator(nullptr, __n, bucket_count()); 1064#endif 1065 } 1066 1067#if _LIBCPP_DEBUG_LEVEL >= 2 1068 1069 bool __dereferenceable(const const_iterator* __i) const; 1070 bool __decrementable(const const_iterator* __i) const; 1071 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1072 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1073 1074#endif // _LIBCPP_DEBUG_LEVEL >= 2 1075 1076private: 1077 void __rehash(size_type __n); 1078 1079#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1080#ifndef _LIBCPP_HAS_NO_VARIADICS 1081 template <class ..._Args> 1082 __node_holder __construct_node(_Args&& ...__args); 1083#endif // _LIBCPP_HAS_NO_VARIADICS 1084 __node_holder __construct_node(value_type&& __v, size_t __hash); 1085#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1086 __node_holder __construct_node(const value_type& __v); 1087#endif 1088 __node_holder __construct_node(const value_type& __v, size_t __hash); 1089 1090 _LIBCPP_INLINE_VISIBILITY 1091 void __copy_assign_alloc(const __hash_table& __u) 1092 {__copy_assign_alloc(__u, integral_constant<bool, 1093 __node_traits::propagate_on_container_copy_assignment::value>());} 1094 void __copy_assign_alloc(const __hash_table& __u, true_type); 1095 _LIBCPP_INLINE_VISIBILITY 1096 void __copy_assign_alloc(const __hash_table&, false_type) {} 1097 1098 void __move_assign(__hash_table& __u, false_type); 1099 void __move_assign(__hash_table& __u, true_type) 1100 _NOEXCEPT_( 1101 is_nothrow_move_assignable<__node_allocator>::value && 1102 is_nothrow_move_assignable<hasher>::value && 1103 is_nothrow_move_assignable<key_equal>::value); 1104 _LIBCPP_INLINE_VISIBILITY 1105 void __move_assign_alloc(__hash_table& __u) 1106 _NOEXCEPT_( 1107 !__node_traits::propagate_on_container_move_assignment::value || 1108 (is_nothrow_move_assignable<__pointer_allocator>::value && 1109 is_nothrow_move_assignable<__node_allocator>::value)) 1110 {__move_assign_alloc(__u, integral_constant<bool, 1111 __node_traits::propagate_on_container_move_assignment::value>());} 1112 _LIBCPP_INLINE_VISIBILITY 1113 void __move_assign_alloc(__hash_table& __u, true_type) 1114 _NOEXCEPT_( 1115 is_nothrow_move_assignable<__pointer_allocator>::value && 1116 is_nothrow_move_assignable<__node_allocator>::value) 1117 { 1118 __bucket_list_.get_deleter().__alloc() = 1119 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1120 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1121 } 1122 _LIBCPP_INLINE_VISIBILITY 1123 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1124 1125 void __deallocate(__node_pointer __np) _NOEXCEPT; 1126 __node_pointer __detach() _NOEXCEPT; 1127 1128 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1129 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1130}; 1131 1132template <class _Tp, class _Hash, class _Equal, class _Alloc> 1133inline _LIBCPP_INLINE_VISIBILITY 1134__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1135 _NOEXCEPT_( 1136 is_nothrow_default_constructible<__bucket_list>::value && 1137 is_nothrow_default_constructible<__first_node>::value && 1138 is_nothrow_default_constructible<hasher>::value && 1139 is_nothrow_default_constructible<key_equal>::value) 1140 : __p2_(0), 1141 __p3_(1.0f) 1142{ 1143} 1144 1145template <class _Tp, class _Hash, class _Equal, class _Alloc> 1146inline _LIBCPP_INLINE_VISIBILITY 1147__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1148 const key_equal& __eql) 1149 : __bucket_list_(nullptr, __bucket_list_deleter()), 1150 __p1_(), 1151 __p2_(0, __hf), 1152 __p3_(1.0f, __eql) 1153{ 1154} 1155 1156template <class _Tp, class _Hash, class _Equal, class _Alloc> 1157__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1158 const key_equal& __eql, 1159 const allocator_type& __a) 1160 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1161 __p1_(__node_allocator(__a)), 1162 __p2_(0, __hf), 1163 __p3_(1.0f, __eql) 1164{ 1165} 1166 1167template <class _Tp, class _Hash, class _Equal, class _Alloc> 1168__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1169 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1170 __p1_(__node_allocator(__a)), 1171 __p2_(0), 1172 __p3_(1.0f) 1173{ 1174} 1175 1176template <class _Tp, class _Hash, class _Equal, class _Alloc> 1177__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1178 : __bucket_list_(nullptr, 1179 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1180 select_on_container_copy_construction( 1181 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1182 __p1_(allocator_traits<__node_allocator>:: 1183 select_on_container_copy_construction(__u.__node_alloc())), 1184 __p2_(0, __u.hash_function()), 1185 __p3_(__u.__p3_) 1186{ 1187} 1188 1189template <class _Tp, class _Hash, class _Equal, class _Alloc> 1190__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1191 const allocator_type& __a) 1192 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1193 __p1_(__node_allocator(__a)), 1194 __p2_(0, __u.hash_function()), 1195 __p3_(__u.__p3_) 1196{ 1197} 1198 1199#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1200 1201template <class _Tp, class _Hash, class _Equal, class _Alloc> 1202__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1203 _NOEXCEPT_( 1204 is_nothrow_move_constructible<__bucket_list>::value && 1205 is_nothrow_move_constructible<__first_node>::value && 1206 is_nothrow_move_constructible<hasher>::value && 1207 is_nothrow_move_constructible<key_equal>::value) 1208 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1209 __p1_(_VSTD::move(__u.__p1_)), 1210 __p2_(_VSTD::move(__u.__p2_)), 1211 __p3_(_VSTD::move(__u.__p3_)) 1212{ 1213 if (size() > 0) 1214 { 1215 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1216 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1217 __u.__p1_.first().__next_ = nullptr; 1218 __u.size() = 0; 1219 } 1220} 1221 1222template <class _Tp, class _Hash, class _Equal, class _Alloc> 1223__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1224 const allocator_type& __a) 1225 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1226 __p1_(__node_allocator(__a)), 1227 __p2_(0, _VSTD::move(__u.hash_function())), 1228 __p3_(_VSTD::move(__u.__p3_)) 1229{ 1230 if (__a == allocator_type(__u.__node_alloc())) 1231 { 1232 __bucket_list_.reset(__u.__bucket_list_.release()); 1233 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1234 __u.__bucket_list_.get_deleter().size() = 0; 1235 if (__u.size() > 0) 1236 { 1237 __p1_.first().__next_ = __u.__p1_.first().__next_; 1238 __u.__p1_.first().__next_ = nullptr; 1239 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1240 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1241 size() = __u.size(); 1242 __u.size() = 0; 1243 } 1244 } 1245} 1246 1247#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1248 1249template <class _Tp, class _Hash, class _Equal, class _Alloc> 1250__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1251{ 1252 __deallocate(__p1_.first().__next_); 1253#if _LIBCPP_DEBUG_LEVEL >= 2 1254 __get_db()->__erase_c(this); 1255#endif 1256} 1257 1258template <class _Tp, class _Hash, class _Equal, class _Alloc> 1259void 1260__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1261 const __hash_table& __u, true_type) 1262{ 1263 if (__node_alloc() != __u.__node_alloc()) 1264 { 1265 clear(); 1266 __bucket_list_.reset(); 1267 __bucket_list_.get_deleter().size() = 0; 1268 } 1269 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1270 __node_alloc() = __u.__node_alloc(); 1271} 1272 1273template <class _Tp, class _Hash, class _Equal, class _Alloc> 1274__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1275__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1276{ 1277 if (this != &__u) 1278 { 1279 __copy_assign_alloc(__u); 1280 hash_function() = __u.hash_function(); 1281 key_eq() = __u.key_eq(); 1282 max_load_factor() = __u.max_load_factor(); 1283 __assign_multi(__u.begin(), __u.end()); 1284 } 1285 return *this; 1286} 1287 1288template <class _Tp, class _Hash, class _Equal, class _Alloc> 1289void 1290__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1291 _NOEXCEPT 1292{ 1293 __node_allocator& __na = __node_alloc(); 1294 while (__np != nullptr) 1295 { 1296 __node_pointer __next = __np->__next_; 1297#if _LIBCPP_DEBUG_LEVEL >= 2 1298 __c_node* __c = __get_db()->__find_c_and_lock(this); 1299 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1300 { 1301 --__p; 1302 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1303 if (__i->__node_ == __np) 1304 { 1305 (*__p)->__c_ = nullptr; 1306 if (--__c->end_ != __p) 1307 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1308 } 1309 } 1310 __get_db()->unlock(); 1311#endif 1312 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1313 __node_traits::deallocate(__na, __np, 1); 1314 __np = __next; 1315 } 1316} 1317 1318template <class _Tp, class _Hash, class _Equal, class _Alloc> 1319typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1320__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1321{ 1322 size_type __bc = bucket_count(); 1323 for (size_type __i = 0; __i < __bc; ++__i) 1324 __bucket_list_[__i] = nullptr; 1325 size() = 0; 1326 __node_pointer __cache = __p1_.first().__next_; 1327 __p1_.first().__next_ = nullptr; 1328 return __cache; 1329} 1330 1331#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1332 1333template <class _Tp, class _Hash, class _Equal, class _Alloc> 1334void 1335__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1336 __hash_table& __u, true_type) 1337 _NOEXCEPT_( 1338 is_nothrow_move_assignable<__node_allocator>::value && 1339 is_nothrow_move_assignable<hasher>::value && 1340 is_nothrow_move_assignable<key_equal>::value) 1341{ 1342 clear(); 1343 __bucket_list_.reset(__u.__bucket_list_.release()); 1344 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1345 __u.__bucket_list_.get_deleter().size() = 0; 1346 __move_assign_alloc(__u); 1347 size() = __u.size(); 1348 hash_function() = _VSTD::move(__u.hash_function()); 1349 max_load_factor() = __u.max_load_factor(); 1350 key_eq() = _VSTD::move(__u.key_eq()); 1351 __p1_.first().__next_ = __u.__p1_.first().__next_; 1352 if (size() > 0) 1353 { 1354 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1355 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1356 __u.__p1_.first().__next_ = nullptr; 1357 __u.size() = 0; 1358 } 1359#if _LIBCPP_DEBUG_LEVEL >= 2 1360 __get_db()->swap(this, &__u); 1361#endif 1362} 1363 1364template <class _Tp, class _Hash, class _Equal, class _Alloc> 1365void 1366__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1367 __hash_table& __u, false_type) 1368{ 1369 if (__node_alloc() == __u.__node_alloc()) 1370 __move_assign(__u, true_type()); 1371 else 1372 { 1373 hash_function() = _VSTD::move(__u.hash_function()); 1374 key_eq() = _VSTD::move(__u.key_eq()); 1375 max_load_factor() = __u.max_load_factor(); 1376 if (bucket_count() != 0) 1377 { 1378 __node_pointer __cache = __detach(); 1379#ifndef _LIBCPP_NO_EXCEPTIONS 1380 try 1381 { 1382#endif // _LIBCPP_NO_EXCEPTIONS 1383 const_iterator __i = __u.begin(); 1384 while (__cache != nullptr && __u.size() != 0) 1385 { 1386 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1387 __node_pointer __next = __cache->__next_; 1388 __node_insert_multi(__cache); 1389 __cache = __next; 1390 } 1391#ifndef _LIBCPP_NO_EXCEPTIONS 1392 } 1393 catch (...) 1394 { 1395 __deallocate(__cache); 1396 throw; 1397 } 1398#endif // _LIBCPP_NO_EXCEPTIONS 1399 __deallocate(__cache); 1400 } 1401 const_iterator __i = __u.begin(); 1402 while (__u.size() != 0) 1403 { 1404 __node_holder __h = 1405 __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1406 __node_insert_multi(__h.get()); 1407 __h.release(); 1408 } 1409 } 1410} 1411 1412template <class _Tp, class _Hash, class _Equal, class _Alloc> 1413inline _LIBCPP_INLINE_VISIBILITY 1414__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1415__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1416 _NOEXCEPT_( 1417 __node_traits::propagate_on_container_move_assignment::value && 1418 is_nothrow_move_assignable<__node_allocator>::value && 1419 is_nothrow_move_assignable<hasher>::value && 1420 is_nothrow_move_assignable<key_equal>::value) 1421{ 1422 __move_assign(__u, integral_constant<bool, 1423 __node_traits::propagate_on_container_move_assignment::value>()); 1424 return *this; 1425} 1426 1427#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1428 1429template <class _Tp, class _Hash, class _Equal, class _Alloc> 1430template <class _InputIterator> 1431void 1432__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1433 _InputIterator __last) 1434{ 1435 if (bucket_count() != 0) 1436 { 1437 __node_pointer __cache = __detach(); 1438#ifndef _LIBCPP_NO_EXCEPTIONS 1439 try 1440 { 1441#endif // _LIBCPP_NO_EXCEPTIONS 1442 for (; __cache != nullptr && __first != __last; ++__first) 1443 { 1444 __cache->__value_ = *__first; 1445 __node_pointer __next = __cache->__next_; 1446 __node_insert_unique(__cache); 1447 __cache = __next; 1448 } 1449#ifndef _LIBCPP_NO_EXCEPTIONS 1450 } 1451 catch (...) 1452 { 1453 __deallocate(__cache); 1454 throw; 1455 } 1456#endif // _LIBCPP_NO_EXCEPTIONS 1457 __deallocate(__cache); 1458 } 1459 for (; __first != __last; ++__first) 1460 __insert_unique(*__first); 1461} 1462 1463template <class _Tp, class _Hash, class _Equal, class _Alloc> 1464template <class _InputIterator> 1465void 1466__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1467 _InputIterator __last) 1468{ 1469 if (bucket_count() != 0) 1470 { 1471 __node_pointer __cache = __detach(); 1472#ifndef _LIBCPP_NO_EXCEPTIONS 1473 try 1474 { 1475#endif // _LIBCPP_NO_EXCEPTIONS 1476 for (; __cache != nullptr && __first != __last; ++__first) 1477 { 1478 __cache->__value_ = *__first; 1479 __node_pointer __next = __cache->__next_; 1480 __node_insert_multi(__cache); 1481 __cache = __next; 1482 } 1483#ifndef _LIBCPP_NO_EXCEPTIONS 1484 } 1485 catch (...) 1486 { 1487 __deallocate(__cache); 1488 throw; 1489 } 1490#endif // _LIBCPP_NO_EXCEPTIONS 1491 __deallocate(__cache); 1492 } 1493 for (; __first != __last; ++__first) 1494 __insert_multi(*__first); 1495} 1496 1497template <class _Tp, class _Hash, class _Equal, class _Alloc> 1498inline _LIBCPP_INLINE_VISIBILITY 1499typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1500__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1501{ 1502#if _LIBCPP_DEBUG_LEVEL >= 2 1503 return iterator(__p1_.first().__next_, this); 1504#else 1505 return iterator(__p1_.first().__next_); 1506#endif 1507} 1508 1509template <class _Tp, class _Hash, class _Equal, class _Alloc> 1510inline _LIBCPP_INLINE_VISIBILITY 1511typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1512__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1513{ 1514#if _LIBCPP_DEBUG_LEVEL >= 2 1515 return iterator(nullptr, this); 1516#else 1517 return iterator(nullptr); 1518#endif 1519} 1520 1521template <class _Tp, class _Hash, class _Equal, class _Alloc> 1522inline _LIBCPP_INLINE_VISIBILITY 1523typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1524__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1525{ 1526#if _LIBCPP_DEBUG_LEVEL >= 2 1527 return const_iterator(__p1_.first().__next_, this); 1528#else 1529 return const_iterator(__p1_.first().__next_); 1530#endif 1531} 1532 1533template <class _Tp, class _Hash, class _Equal, class _Alloc> 1534inline _LIBCPP_INLINE_VISIBILITY 1535typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1536__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1537{ 1538#if _LIBCPP_DEBUG_LEVEL >= 2 1539 return const_iterator(nullptr, this); 1540#else 1541 return const_iterator(nullptr); 1542#endif 1543} 1544 1545template <class _Tp, class _Hash, class _Equal, class _Alloc> 1546void 1547__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1548{ 1549 if (size() > 0) 1550 { 1551 __deallocate(__p1_.first().__next_); 1552 __p1_.first().__next_ = nullptr; 1553 size_type __bc = bucket_count(); 1554 for (size_type __i = 0; __i < __bc; ++__i) 1555 __bucket_list_[__i] = nullptr; 1556 size() = 0; 1557 } 1558} 1559 1560template <class _Tp, class _Hash, class _Equal, class _Alloc> 1561pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1562__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1563{ 1564 __nd->__hash_ = hash_function()(__nd->__value_); 1565 size_type __bc = bucket_count(); 1566 bool __inserted = false; 1567 __node_pointer __ndptr; 1568 size_t __chash; 1569 if (__bc != 0) 1570 { 1571 __chash = __constrain_hash(__nd->__hash_, __bc); 1572 __ndptr = __bucket_list_[__chash]; 1573 if (__ndptr != nullptr) 1574 { 1575 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1576 __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1577 __ndptr = __ndptr->__next_) 1578 { 1579 if (key_eq()(__ndptr->__value_, __nd->__value_)) 1580 goto __done; 1581 } 1582 } 1583 } 1584 { 1585 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1586 { 1587 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1588 size_type(ceil(float(size() + 1) / max_load_factor())))); 1589 __bc = bucket_count(); 1590 __chash = __constrain_hash(__nd->__hash_, __bc); 1591 } 1592 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1593 __node_pointer __pn = __bucket_list_[__chash]; 1594 if (__pn == nullptr) 1595 { 1596 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1597 __nd->__next_ = __pn->__next_; 1598 __pn->__next_ = __nd; 1599 // fix up __bucket_list_ 1600 __bucket_list_[__chash] = __pn; 1601 if (__nd->__next_ != nullptr) 1602 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1603 } 1604 else 1605 { 1606 __nd->__next_ = __pn->__next_; 1607 __pn->__next_ = __nd; 1608 } 1609 __ndptr = __nd; 1610 // increment size 1611 ++size(); 1612 __inserted = true; 1613 } 1614__done: 1615#if _LIBCPP_DEBUG_LEVEL >= 2 1616 return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1617#else 1618 return pair<iterator, bool>(iterator(__ndptr), __inserted); 1619#endif 1620} 1621 1622template <class _Tp, class _Hash, class _Equal, class _Alloc> 1623typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1624__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1625{ 1626 __cp->__hash_ = hash_function()(__cp->__value_); 1627 size_type __bc = bucket_count(); 1628 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1629 { 1630 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1631 size_type(ceil(float(size() + 1) / max_load_factor())))); 1632 __bc = bucket_count(); 1633 } 1634 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1635 __node_pointer __pn = __bucket_list_[__chash]; 1636 if (__pn == nullptr) 1637 { 1638 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1639 __cp->__next_ = __pn->__next_; 1640 __pn->__next_ = __cp; 1641 // fix up __bucket_list_ 1642 __bucket_list_[__chash] = __pn; 1643 if (__cp->__next_ != nullptr) 1644 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1645 } 1646 else 1647 { 1648 for (bool __found = false; __pn->__next_ != nullptr && 1649 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1650 __pn = __pn->__next_) 1651 { 1652 // __found key_eq() action 1653 // false false loop 1654 // true true loop 1655 // false true set __found to true 1656 // true false break 1657 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1658 key_eq()(__pn->__next_->__value_, __cp->__value_))) 1659 { 1660 if (!__found) 1661 __found = true; 1662 else 1663 break; 1664 } 1665 } 1666 __cp->__next_ = __pn->__next_; 1667 __pn->__next_ = __cp; 1668 if (__cp->__next_ != nullptr) 1669 { 1670 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1671 if (__nhash != __chash) 1672 __bucket_list_[__nhash] = __cp; 1673 } 1674 } 1675 ++size(); 1676#if _LIBCPP_DEBUG_LEVEL >= 2 1677 return iterator(__cp, this); 1678#else 1679 return iterator(__cp); 1680#endif 1681} 1682 1683template <class _Tp, class _Hash, class _Equal, class _Alloc> 1684typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1685__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1686 const_iterator __p, __node_pointer __cp) 1687{ 1688#if _LIBCPP_DEBUG_LEVEL >= 2 1689 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1690 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1691 " referring to this unordered container"); 1692#endif 1693 if (__p != end() && key_eq()(*__p, __cp->__value_)) 1694 { 1695 __node_pointer __np = __p.__node_; 1696 __cp->__hash_ = __np->__hash_; 1697 size_type __bc = bucket_count(); 1698 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1699 { 1700 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1701 size_type(ceil(float(size() + 1) / max_load_factor())))); 1702 __bc = bucket_count(); 1703 } 1704 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1705 __node_pointer __pp = __bucket_list_[__chash]; 1706 while (__pp->__next_ != __np) 1707 __pp = __pp->__next_; 1708 __cp->__next_ = __np; 1709 __pp->__next_ = __cp; 1710 ++size(); 1711#if _LIBCPP_DEBUG_LEVEL >= 2 1712 return iterator(__cp, this); 1713#else 1714 return iterator(__cp); 1715#endif 1716 } 1717 return __node_insert_multi(__cp); 1718} 1719 1720template <class _Tp, class _Hash, class _Equal, class _Alloc> 1721pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1722__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1723{ 1724 return __insert_unique_value(__x); 1725} 1726 1727 1728#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1729template <class _Tp, class _Hash, class _Equal, class _Alloc> 1730template <class _ValueTp> 1731_LIBCPP_INLINE_VISIBILITY 1732pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1733__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x) 1734#else 1735template <class _Tp, class _Hash, class _Equal, class _Alloc> 1736_LIBCPP_INLINE_VISIBILITY 1737pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1738__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x) 1739#endif 1740{ 1741#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1742 typedef const value_type& _ValueTp; 1743#endif 1744 size_t __hash = hash_function()(__x); 1745 size_type __bc = bucket_count(); 1746 bool __inserted = false; 1747 __node_pointer __nd; 1748 size_t __chash; 1749 if (__bc != 0) 1750 { 1751 __chash = __constrain_hash(__hash, __bc); 1752 __nd = __bucket_list_[__chash]; 1753 if (__nd != nullptr) 1754 { 1755 for (__nd = __nd->__next_; __nd != nullptr && 1756 __constrain_hash(__nd->__hash_, __bc) == __chash; 1757 __nd = __nd->__next_) 1758 { 1759 if (key_eq()(__nd->__value_, __x)) 1760 goto __done; 1761 } 1762 } 1763 } 1764 { 1765 __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash); 1766 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1767 { 1768 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1769 size_type(ceil(float(size() + 1) / max_load_factor())))); 1770 __bc = bucket_count(); 1771 __chash = __constrain_hash(__hash, __bc); 1772 } 1773 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1774 __node_pointer __pn = __bucket_list_[__chash]; 1775 if (__pn == nullptr) 1776 { 1777 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1778 __h->__next_ = __pn->__next_; 1779 __pn->__next_ = __h.get(); 1780 // fix up __bucket_list_ 1781 __bucket_list_[__chash] = __pn; 1782 if (__h->__next_ != nullptr) 1783 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1784 } 1785 else 1786 { 1787 __h->__next_ = __pn->__next_; 1788 __pn->__next_ = __h.get(); 1789 } 1790 __nd = __h.release(); 1791 // increment size 1792 ++size(); 1793 __inserted = true; 1794 } 1795__done: 1796#if _LIBCPP_DEBUG_LEVEL >= 2 1797 return pair<iterator, bool>(iterator(__nd, this), __inserted); 1798#else 1799 return pair<iterator, bool>(iterator(__nd), __inserted); 1800#endif 1801} 1802 1803#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1804#ifndef _LIBCPP_HAS_NO_VARIADICS 1805 1806template <class _Tp, class _Hash, class _Equal, class _Alloc> 1807template <class... _Args> 1808pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1809__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1810{ 1811 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1812 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1813 if (__r.second) 1814 __h.release(); 1815 return __r; 1816} 1817 1818template <class _Tp, class _Hash, class _Equal, class _Alloc> 1819template <class... _Args> 1820typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1821__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1822{ 1823 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1824 iterator __r = __node_insert_multi(__h.get()); 1825 __h.release(); 1826 return __r; 1827} 1828 1829template <class _Tp, class _Hash, class _Equal, class _Alloc> 1830template <class... _Args> 1831typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1832__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1833 const_iterator __p, _Args&&... __args) 1834{ 1835#if _LIBCPP_DEBUG_LEVEL >= 2 1836 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1837 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1838 " referring to this unordered container"); 1839#endif 1840 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1841 iterator __r = __node_insert_multi(__p, __h.get()); 1842 __h.release(); 1843 return __r; 1844} 1845 1846#endif // _LIBCPP_HAS_NO_VARIADICS 1847 1848template <class _Tp, class _Hash, class _Equal, class _Alloc> 1849pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1850__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x) 1851{ 1852 return __insert_unique_value(_VSTD::move(__x)); 1853} 1854 1855template <class _Tp, class _Hash, class _Equal, class _Alloc> 1856template <class _Pp> 1857pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1858__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1859{ 1860 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1861 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1862 if (__r.second) 1863 __h.release(); 1864 return __r; 1865} 1866 1867#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1868 1869#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1870 1871template <class _Tp, class _Hash, class _Equal, class _Alloc> 1872template <class _Pp> 1873typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1874__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1875{ 1876 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1877 iterator __r = __node_insert_multi(__h.get()); 1878 __h.release(); 1879 return __r; 1880} 1881 1882template <class _Tp, class _Hash, class _Equal, class _Alloc> 1883template <class _Pp> 1884typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1885__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1886 _Pp&& __x) 1887{ 1888#if _LIBCPP_DEBUG_LEVEL >= 2 1889 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1890 "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1891 " referring to this unordered container"); 1892#endif 1893 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1894 iterator __r = __node_insert_multi(__p, __h.get()); 1895 __h.release(); 1896 return __r; 1897} 1898 1899#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1900 1901template <class _Tp, class _Hash, class _Equal, class _Alloc> 1902typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1903__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1904{ 1905 __node_holder __h = __construct_node(__x); 1906 iterator __r = __node_insert_multi(__h.get()); 1907 __h.release(); 1908 return __r; 1909} 1910 1911template <class _Tp, class _Hash, class _Equal, class _Alloc> 1912typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1913__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1914 const value_type& __x) 1915{ 1916#if _LIBCPP_DEBUG_LEVEL >= 2 1917 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1918 "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1919 " referring to this unordered container"); 1920#endif 1921 __node_holder __h = __construct_node(__x); 1922 iterator __r = __node_insert_multi(__p, __h.get()); 1923 __h.release(); 1924 return __r; 1925} 1926 1927#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1928 1929template <class _Tp, class _Hash, class _Equal, class _Alloc> 1930void 1931__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1932{ 1933 if (__n == 1) 1934 __n = 2; 1935 else if (__n & (__n - 1)) 1936 __n = __next_prime(__n); 1937 size_type __bc = bucket_count(); 1938 if (__n > __bc) 1939 __rehash(__n); 1940 else if (__n < __bc) 1941 { 1942 __n = _VSTD::max<size_type> 1943 ( 1944 __n, 1945 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1946 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1947 ); 1948 if (__n < __bc) 1949 __rehash(__n); 1950 } 1951} 1952 1953template <class _Tp, class _Hash, class _Equal, class _Alloc> 1954void 1955__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1956{ 1957#if _LIBCPP_DEBUG_LEVEL >= 2 1958 __get_db()->__invalidate_all(this); 1959#endif // _LIBCPP_DEBUG_LEVEL >= 2 1960 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1961 __bucket_list_.reset(__nbc > 0 ? 1962 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1963 __bucket_list_.get_deleter().size() = __nbc; 1964 if (__nbc > 0) 1965 { 1966 for (size_type __i = 0; __i < __nbc; ++__i) 1967 __bucket_list_[__i] = nullptr; 1968 __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1969 __node_pointer __cp = __pp->__next_; 1970 if (__cp != nullptr) 1971 { 1972 size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1973 __bucket_list_[__chash] = __pp; 1974 size_type __phash = __chash; 1975 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1976 __cp = __pp->__next_) 1977 { 1978 __chash = __constrain_hash(__cp->__hash_, __nbc); 1979 if (__chash == __phash) 1980 __pp = __cp; 1981 else 1982 { 1983 if (__bucket_list_[__chash] == nullptr) 1984 { 1985 __bucket_list_[__chash] = __pp; 1986 __pp = __cp; 1987 __phash = __chash; 1988 } 1989 else 1990 { 1991 __node_pointer __np = __cp; 1992 for (; __np->__next_ != nullptr && 1993 key_eq()(__cp->__value_, __np->__next_->__value_); 1994 __np = __np->__next_) 1995 ; 1996 __pp->__next_ = __np->__next_; 1997 __np->__next_ = __bucket_list_[__chash]->__next_; 1998 __bucket_list_[__chash]->__next_ = __cp; 1999 2000 } 2001 } 2002 } 2003 } 2004 } 2005} 2006 2007template <class _Tp, class _Hash, class _Equal, class _Alloc> 2008template <class _Key> 2009typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2010__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2011{ 2012 size_t __hash = hash_function()(__k); 2013 size_type __bc = bucket_count(); 2014 if (__bc != 0) 2015 { 2016 size_t __chash = __constrain_hash(__hash, __bc); 2017 __node_pointer __nd = __bucket_list_[__chash]; 2018 if (__nd != nullptr) 2019 { 2020 for (__nd = __nd->__next_; __nd != nullptr && 2021 __constrain_hash(__nd->__hash_, __bc) == __chash; 2022 __nd = __nd->__next_) 2023 { 2024 if (key_eq()(__nd->__value_, __k)) 2025#if _LIBCPP_DEBUG_LEVEL >= 2 2026 return iterator(__nd, this); 2027#else 2028 return iterator(__nd); 2029#endif 2030 } 2031 } 2032 } 2033 return end(); 2034} 2035 2036template <class _Tp, class _Hash, class _Equal, class _Alloc> 2037template <class _Key> 2038typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2039__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2040{ 2041 size_t __hash = hash_function()(__k); 2042 size_type __bc = bucket_count(); 2043 if (__bc != 0) 2044 { 2045 size_t __chash = __constrain_hash(__hash, __bc); 2046 __node_const_pointer __nd = __bucket_list_[__chash]; 2047 if (__nd != nullptr) 2048 { 2049 for (__nd = __nd->__next_; __nd != nullptr && 2050 __constrain_hash(__nd->__hash_, __bc) == __chash; 2051 __nd = __nd->__next_) 2052 { 2053 if (key_eq()(__nd->__value_, __k)) 2054#if _LIBCPP_DEBUG_LEVEL >= 2 2055 return const_iterator(__nd, this); 2056#else 2057 return const_iterator(__nd); 2058#endif 2059 } 2060 } 2061 2062 } 2063 return end(); 2064} 2065 2066#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2067#ifndef _LIBCPP_HAS_NO_VARIADICS 2068 2069template <class _Tp, class _Hash, class _Equal, class _Alloc> 2070template <class ..._Args> 2071typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2072__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2073{ 2074 __node_allocator& __na = __node_alloc(); 2075 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2076 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2077 __h.get_deleter().__value_constructed = true; 2078 __h->__hash_ = hash_function()(__h->__value_); 2079 __h->__next_ = nullptr; 2080 return __h; 2081} 2082 2083#endif // _LIBCPP_HAS_NO_VARIADICS 2084 2085template <class _Tp, class _Hash, class _Equal, class _Alloc> 2086typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2087__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2088 size_t __hash) 2089{ 2090 __node_allocator& __na = __node_alloc(); 2091 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2092 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2093 __h.get_deleter().__value_constructed = true; 2094 __h->__hash_ = __hash; 2095 __h->__next_ = nullptr; 2096 return __h; 2097} 2098 2099#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2100 2101template <class _Tp, class _Hash, class _Equal, class _Alloc> 2102typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2103__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2104{ 2105 __node_allocator& __na = __node_alloc(); 2106 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2107 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2108 __h.get_deleter().__value_constructed = true; 2109 __h->__hash_ = hash_function()(__h->__value_); 2110 __h->__next_ = nullptr; 2111 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2112} 2113 2114#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2115 2116template <class _Tp, class _Hash, class _Equal, class _Alloc> 2117typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2118__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2119 size_t __hash) 2120{ 2121 __node_allocator& __na = __node_alloc(); 2122 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2123 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2124 __h.get_deleter().__value_constructed = true; 2125 __h->__hash_ = __hash; 2126 __h->__next_ = nullptr; 2127 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2128} 2129 2130template <class _Tp, class _Hash, class _Equal, class _Alloc> 2131typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2132__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2133{ 2134 __node_pointer __np = __p.__node_; 2135#if _LIBCPP_DEBUG_LEVEL >= 2 2136 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2137 "unordered container erase(iterator) called with an iterator not" 2138 " referring to this container"); 2139 _LIBCPP_ASSERT(__p != end(), 2140 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2141 iterator __r(__np, this); 2142#else 2143 iterator __r(__np); 2144#endif 2145 ++__r; 2146 remove(__p); 2147 return __r; 2148} 2149 2150template <class _Tp, class _Hash, class _Equal, class _Alloc> 2151typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2152__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2153 const_iterator __last) 2154{ 2155#if _LIBCPP_DEBUG_LEVEL >= 2 2156 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2157 "unodered container::erase(iterator, iterator) called with an iterator not" 2158 " referring to this unodered container"); 2159 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2160 "unodered container::erase(iterator, iterator) called with an iterator not" 2161 " referring to this unodered container"); 2162#endif 2163 for (const_iterator __p = __first; __first != __last; __p = __first) 2164 { 2165 ++__first; 2166 erase(__p); 2167 } 2168 __node_pointer __np = __last.__node_; 2169#if _LIBCPP_DEBUG_LEVEL >= 2 2170 return iterator (__np, this); 2171#else 2172 return iterator (__np); 2173#endif 2174} 2175 2176template <class _Tp, class _Hash, class _Equal, class _Alloc> 2177template <class _Key> 2178typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2179__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2180{ 2181 iterator __i = find(__k); 2182 if (__i == end()) 2183 return 0; 2184 erase(__i); 2185 return 1; 2186} 2187 2188template <class _Tp, class _Hash, class _Equal, class _Alloc> 2189template <class _Key> 2190typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2191__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2192{ 2193 size_type __r = 0; 2194 iterator __i = find(__k); 2195 if (__i != end()) 2196 { 2197 iterator __e = end(); 2198 do 2199 { 2200 erase(__i++); 2201 ++__r; 2202 } while (__i != __e && key_eq()(*__i, __k)); 2203 } 2204 return __r; 2205} 2206 2207template <class _Tp, class _Hash, class _Equal, class _Alloc> 2208typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2209__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2210{ 2211 // current node 2212 __node_pointer __cn = __p.__node_; 2213 size_type __bc = bucket_count(); 2214 size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2215 // find previous node 2216 __node_pointer __pn = __bucket_list_[__chash]; 2217 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2218 ; 2219 // Fix up __bucket_list_ 2220 // if __pn is not in same bucket (before begin is not in same bucket) && 2221 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2222 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2223 || __constrain_hash(__pn->__hash_, __bc) != __chash) 2224 { 2225 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2226 __bucket_list_[__chash] = nullptr; 2227 } 2228 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2229 if (__cn->__next_ != nullptr) 2230 { 2231 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2232 if (__nhash != __chash) 2233 __bucket_list_[__nhash] = __pn; 2234 } 2235 // remove __cn 2236 __pn->__next_ = __cn->__next_; 2237 __cn->__next_ = nullptr; 2238 --size(); 2239#if _LIBCPP_DEBUG_LEVEL >= 2 2240 __c_node* __c = __get_db()->__find_c_and_lock(this); 2241 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2242 { 2243 --__p; 2244 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2245 if (__i->__node_ == __cn) 2246 { 2247 (*__p)->__c_ = nullptr; 2248 if (--__c->end_ != __p) 2249 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2250 } 2251 } 2252 __get_db()->unlock(); 2253#endif 2254 return __node_holder(__cn, _Dp(__node_alloc(), true)); 2255} 2256 2257template <class _Tp, class _Hash, class _Equal, class _Alloc> 2258template <class _Key> 2259inline _LIBCPP_INLINE_VISIBILITY 2260typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2261__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2262{ 2263 return static_cast<size_type>(find(__k) != end()); 2264} 2265 2266template <class _Tp, class _Hash, class _Equal, class _Alloc> 2267template <class _Key> 2268typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2269__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2270{ 2271 size_type __r = 0; 2272 const_iterator __i = find(__k); 2273 if (__i != end()) 2274 { 2275 const_iterator __e = end(); 2276 do 2277 { 2278 ++__i; 2279 ++__r; 2280 } while (__i != __e && key_eq()(*__i, __k)); 2281 } 2282 return __r; 2283} 2284 2285template <class _Tp, class _Hash, class _Equal, class _Alloc> 2286template <class _Key> 2287pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2288 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2289__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2290 const _Key& __k) 2291{ 2292 iterator __i = find(__k); 2293 iterator __j = __i; 2294 if (__i != end()) 2295 ++__j; 2296 return pair<iterator, iterator>(__i, __j); 2297} 2298 2299template <class _Tp, class _Hash, class _Equal, class _Alloc> 2300template <class _Key> 2301pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2302 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2303__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2304 const _Key& __k) const 2305{ 2306 const_iterator __i = find(__k); 2307 const_iterator __j = __i; 2308 if (__i != end()) 2309 ++__j; 2310 return pair<const_iterator, const_iterator>(__i, __j); 2311} 2312 2313template <class _Tp, class _Hash, class _Equal, class _Alloc> 2314template <class _Key> 2315pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2316 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2317__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2318 const _Key& __k) 2319{ 2320 iterator __i = find(__k); 2321 iterator __j = __i; 2322 if (__i != end()) 2323 { 2324 iterator __e = end(); 2325 do 2326 { 2327 ++__j; 2328 } while (__j != __e && key_eq()(*__j, __k)); 2329 } 2330 return pair<iterator, iterator>(__i, __j); 2331} 2332 2333template <class _Tp, class _Hash, class _Equal, class _Alloc> 2334template <class _Key> 2335pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2336 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2337__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2338 const _Key& __k) const 2339{ 2340 const_iterator __i = find(__k); 2341 const_iterator __j = __i; 2342 if (__i != end()) 2343 { 2344 const_iterator __e = end(); 2345 do 2346 { 2347 ++__j; 2348 } while (__j != __e && key_eq()(*__j, __k)); 2349 } 2350 return pair<const_iterator, const_iterator>(__i, __j); 2351} 2352 2353template <class _Tp, class _Hash, class _Equal, class _Alloc> 2354void 2355__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2356#if _LIBCPP_STD_VER <= 11 2357 _NOEXCEPT_( 2358 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2359 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2360 || __is_nothrow_swappable<__pointer_allocator>::value) 2361 && (!__node_traits::propagate_on_container_swap::value 2362 || __is_nothrow_swappable<__node_allocator>::value) 2363 ) 2364#else 2365 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2366#endif 2367{ 2368 { 2369 __node_pointer_pointer __npp = __bucket_list_.release(); 2370 __bucket_list_.reset(__u.__bucket_list_.release()); 2371 __u.__bucket_list_.reset(__npp); 2372 } 2373 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2374 __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2375 __u.__bucket_list_.get_deleter().__alloc()); 2376 __swap_allocator(__node_alloc(), __u.__node_alloc()); 2377 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2378 __p2_.swap(__u.__p2_); 2379 __p3_.swap(__u.__p3_); 2380 if (size() > 0) 2381 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2382 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2383 if (__u.size() > 0) 2384 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2385 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2386#if _LIBCPP_DEBUG_LEVEL >= 2 2387 __get_db()->swap(this, &__u); 2388#endif 2389} 2390 2391template <class _Tp, class _Hash, class _Equal, class _Alloc> 2392typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2393__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2394{ 2395 _LIBCPP_ASSERT(__n < bucket_count(), 2396 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2397 __node_const_pointer __np = __bucket_list_[__n]; 2398 size_type __bc = bucket_count(); 2399 size_type __r = 0; 2400 if (__np != nullptr) 2401 { 2402 for (__np = __np->__next_; __np != nullptr && 2403 __constrain_hash(__np->__hash_, __bc) == __n; 2404 __np = __np->__next_, ++__r) 2405 ; 2406 } 2407 return __r; 2408} 2409 2410template <class _Tp, class _Hash, class _Equal, class _Alloc> 2411inline _LIBCPP_INLINE_VISIBILITY 2412void 2413swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2414 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2415 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2416{ 2417 __x.swap(__y); 2418} 2419 2420#if _LIBCPP_DEBUG_LEVEL >= 2 2421 2422template <class _Tp, class _Hash, class _Equal, class _Alloc> 2423bool 2424__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2425{ 2426 return __i->__node_ != nullptr; 2427} 2428 2429template <class _Tp, class _Hash, class _Equal, class _Alloc> 2430bool 2431__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2432{ 2433 return false; 2434} 2435 2436template <class _Tp, class _Hash, class _Equal, class _Alloc> 2437bool 2438__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2439{ 2440 return false; 2441} 2442 2443template <class _Tp, class _Hash, class _Equal, class _Alloc> 2444bool 2445__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2446{ 2447 return false; 2448} 2449 2450#endif // _LIBCPP_DEBUG_LEVEL >= 2 2451_LIBCPP_END_NAMESPACE_STD 2452 2453#endif // _LIBCPP__HASH_TABLE 2454