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