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