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