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