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 23#ifdef _LIBCPP_DEBUG 24# include <__debug> 25#else 26# define _LIBCPP_ASSERT(x, m) ((void)0) 27#endif 28 29#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 30#pragma GCC system_header 31#endif 32 33_LIBCPP_BEGIN_NAMESPACE_STD 34 35_LIBCPP_FUNC_VIS 36size_t __next_prime(size_t __n); 37 38template <class _NodePtr> 39struct __hash_node_base 40{ 41 typedef __hash_node_base __first_node; 42 43 _NodePtr __next_; 44 45 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 46}; 47 48template <class _Tp, class _VoidPtr> 49struct __hash_node 50 : public __hash_node_base 51 < 52 typename pointer_traits<_VoidPtr>::template 53#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 54 rebind<__hash_node<_Tp, _VoidPtr> > 55#else 56 rebind<__hash_node<_Tp, _VoidPtr> >::other 57#endif 58 > 59{ 60 typedef _Tp value_type; 61 62 size_t __hash_; 63 value_type __value_; 64}; 65 66inline _LIBCPP_INLINE_VISIBILITY 67bool 68__is_power2(size_t __bc) 69{ 70 return __bc > 2 && !(__bc & (__bc - 1)); 71} 72 73inline _LIBCPP_INLINE_VISIBILITY 74size_t 75__constrain_hash(size_t __h, size_t __bc) 76{ 77 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 78} 79 80inline _LIBCPP_INLINE_VISIBILITY 81size_t 82__next_pow2(size_t __n) 83{ 84 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 85} 86 87template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 88template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 89template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 90template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 91template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 92 class _LIBCPP_TYPE_VIS_ONLY unordered_map; 93 94template <class _NodePtr> 95class _LIBCPP_TYPE_VIS_ONLY __hash_iterator 96{ 97 typedef _NodePtr __node_pointer; 98 99 __node_pointer __node_; 100 101public: 102 typedef forward_iterator_tag iterator_category; 103 typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 104 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 105 typedef value_type& reference; 106 typedef typename pointer_traits<__node_pointer>::template 107#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 108 rebind<value_type> 109#else 110 rebind<value_type>::other 111#endif 112 pointer; 113 114 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 115#if _LIBCPP_STD_VER > 11 116 : __node_(nullptr) 117#endif 118 { 119#if _LIBCPP_DEBUG_LEVEL >= 2 120 __get_db()->__insert_i(this); 121#endif 122 } 123 124#if _LIBCPP_DEBUG_LEVEL >= 2 125 126 _LIBCPP_INLINE_VISIBILITY 127 __hash_iterator(const __hash_iterator& __i) 128 : __node_(__i.__node_) 129 { 130 __get_db()->__iterator_copy(this, &__i); 131 } 132 133 _LIBCPP_INLINE_VISIBILITY 134 ~__hash_iterator() 135 { 136 __get_db()->__erase_i(this); 137 } 138 139 _LIBCPP_INLINE_VISIBILITY 140 __hash_iterator& operator=(const __hash_iterator& __i) 141 { 142 if (this != &__i) 143 { 144 __get_db()->__iterator_copy(this, &__i); 145 __node_ = __i.__node_; 146 } 147 return *this; 148 } 149 150#endif // _LIBCPP_DEBUG_LEVEL >= 2 151 152 _LIBCPP_INLINE_VISIBILITY 153 reference operator*() const 154 { 155#if _LIBCPP_DEBUG_LEVEL >= 2 156 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 157 "Attempted to dereference a non-dereferenceable unordered container iterator"); 158#endif 159 return __node_->__value_; 160 } 161 _LIBCPP_INLINE_VISIBILITY 162 pointer operator->() const 163 { 164#if _LIBCPP_DEBUG_LEVEL >= 2 165 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 166 "Attempted to dereference a non-dereferenceable unordered container iterator"); 167#endif 168 return pointer_traits<pointer>::pointer_to(__node_->__value_); 169 } 170 171 _LIBCPP_INLINE_VISIBILITY 172 __hash_iterator& operator++() 173 { 174#if _LIBCPP_DEBUG_LEVEL >= 2 175 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 176 "Attempted to increment non-incrementable unordered container iterator"); 177#endif 178 __node_ = __node_->__next_; 179 return *this; 180 } 181 182 _LIBCPP_INLINE_VISIBILITY 183 __hash_iterator operator++(int) 184 { 185 __hash_iterator __t(*this); 186 ++(*this); 187 return __t; 188 } 189 190 friend _LIBCPP_INLINE_VISIBILITY 191 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 192 { 193 return __x.__node_ == __y.__node_; 194 } 195 friend _LIBCPP_INLINE_VISIBILITY 196 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 197 {return !(__x == __y);} 198 199private: 200#if _LIBCPP_DEBUG_LEVEL >= 2 201 _LIBCPP_INLINE_VISIBILITY 202 __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 203 : __node_(__node) 204 { 205 __get_db()->__insert_ic(this, __c); 206 } 207#else 208 _LIBCPP_INLINE_VISIBILITY 209 __hash_iterator(__node_pointer __node) _NOEXCEPT 210 : __node_(__node) 211 {} 212#endif 213 214 template <class, class, class, class> friend class __hash_table; 215 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 216 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 217 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 218 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 219}; 220 221template <class _ConstNodePtr> 222class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 223{ 224 typedef _ConstNodePtr __node_pointer; 225 226 __node_pointer __node_; 227 228 typedef typename remove_const< 229 typename pointer_traits<__node_pointer>::element_type 230 >::type __node; 231 232public: 233 typedef forward_iterator_tag iterator_category; 234 typedef typename __node::value_type value_type; 235 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 236 typedef const value_type& reference; 237 typedef typename pointer_traits<__node_pointer>::template 238#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 239 rebind<const value_type> 240#else 241 rebind<const value_type>::other 242#endif 243 pointer; 244 typedef typename pointer_traits<__node_pointer>::template 245#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 246 rebind<__node> 247#else 248 rebind<__node>::other 249#endif 250 __non_const_node_pointer; 251 typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 252 253 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 254#if _LIBCPP_STD_VER > 11 255 : __node_(nullptr) 256#endif 257 { 258#if _LIBCPP_DEBUG_LEVEL >= 2 259 __get_db()->__insert_i(this); 260#endif 261 } 262 _LIBCPP_INLINE_VISIBILITY 263 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 264 : __node_(__x.__node_) 265 { 266#if _LIBCPP_DEBUG_LEVEL >= 2 267 __get_db()->__iterator_copy(this, &__x); 268#endif 269 } 270 271#if _LIBCPP_DEBUG_LEVEL >= 2 272 273 _LIBCPP_INLINE_VISIBILITY 274 __hash_const_iterator(const __hash_const_iterator& __i) 275 : __node_(__i.__node_) 276 { 277 __get_db()->__iterator_copy(this, &__i); 278 } 279 280 _LIBCPP_INLINE_VISIBILITY 281 ~__hash_const_iterator() 282 { 283 __get_db()->__erase_i(this); 284 } 285 286 _LIBCPP_INLINE_VISIBILITY 287 __hash_const_iterator& operator=(const __hash_const_iterator& __i) 288 { 289 if (this != &__i) 290 { 291 __get_db()->__iterator_copy(this, &__i); 292 __node_ = __i.__node_; 293 } 294 return *this; 295 } 296 297#endif // _LIBCPP_DEBUG_LEVEL >= 2 298 299 _LIBCPP_INLINE_VISIBILITY 300 reference operator*() const 301 { 302#if _LIBCPP_DEBUG_LEVEL >= 2 303 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 304 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 305#endif 306 return __node_->__value_; 307 } 308 _LIBCPP_INLINE_VISIBILITY 309 pointer operator->() const 310 { 311#if _LIBCPP_DEBUG_LEVEL >= 2 312 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 313 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 314#endif 315 return pointer_traits<pointer>::pointer_to(__node_->__value_); 316 } 317 318 _LIBCPP_INLINE_VISIBILITY 319 __hash_const_iterator& operator++() 320 { 321#if _LIBCPP_DEBUG_LEVEL >= 2 322 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 323 "Attempted to increment non-incrementable unordered container const_iterator"); 324#endif 325 __node_ = __node_->__next_; 326 return *this; 327 } 328 329 _LIBCPP_INLINE_VISIBILITY 330 __hash_const_iterator operator++(int) 331 { 332 __hash_const_iterator __t(*this); 333 ++(*this); 334 return __t; 335 } 336 337 friend _LIBCPP_INLINE_VISIBILITY 338 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 339 { 340 return __x.__node_ == __y.__node_; 341 } 342 friend _LIBCPP_INLINE_VISIBILITY 343 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 344 {return !(__x == __y);} 345 346private: 347#if _LIBCPP_DEBUG_LEVEL >= 2 348 _LIBCPP_INLINE_VISIBILITY 349 __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 350 : __node_(__node) 351 { 352 __get_db()->__insert_ic(this, __c); 353 } 354#else 355 _LIBCPP_INLINE_VISIBILITY 356 __hash_const_iterator(__node_pointer __node) _NOEXCEPT 357 : __node_(__node) 358 {} 359#endif 360 361 template <class, class, class, class> friend class __hash_table; 362 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 363 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 364 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 365}; 366 367template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 368 369template <class _NodePtr> 370class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 371{ 372 typedef _NodePtr __node_pointer; 373 374 __node_pointer __node_; 375 size_t __bucket_; 376 size_t __bucket_count_; 377 378 typedef pointer_traits<__node_pointer> __pointer_traits; 379public: 380 typedef forward_iterator_tag iterator_category; 381 typedef typename __pointer_traits::element_type::value_type value_type; 382 typedef typename __pointer_traits::difference_type difference_type; 383 typedef value_type& reference; 384 typedef typename __pointer_traits::template 385#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 386 rebind<value_type> 387#else 388 rebind<value_type>::other 389#endif 390 pointer; 391 392 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 393 { 394#if _LIBCPP_DEBUG_LEVEL >= 2 395 __get_db()->__insert_i(this); 396#endif 397 } 398 399#if _LIBCPP_DEBUG_LEVEL >= 2 400 401 _LIBCPP_INLINE_VISIBILITY 402 __hash_local_iterator(const __hash_local_iterator& __i) 403 : __node_(__i.__node_), 404 __bucket_(__i.__bucket_), 405 __bucket_count_(__i.__bucket_count_) 406 { 407 __get_db()->__iterator_copy(this, &__i); 408 } 409 410 _LIBCPP_INLINE_VISIBILITY 411 ~__hash_local_iterator() 412 { 413 __get_db()->__erase_i(this); 414 } 415 416 _LIBCPP_INLINE_VISIBILITY 417 __hash_local_iterator& operator=(const __hash_local_iterator& __i) 418 { 419 if (this != &__i) 420 { 421 __get_db()->__iterator_copy(this, &__i); 422 __node_ = __i.__node_; 423 __bucket_ = __i.__bucket_; 424 __bucket_count_ = __i.__bucket_count_; 425 } 426 return *this; 427 } 428 429#endif // _LIBCPP_DEBUG_LEVEL >= 2 430 431 _LIBCPP_INLINE_VISIBILITY 432 reference operator*() const 433 { 434#if _LIBCPP_DEBUG_LEVEL >= 2 435 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 436 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 437#endif 438 return __node_->__value_; 439 } 440 _LIBCPP_INLINE_VISIBILITY 441 pointer operator->() const 442 { 443#if _LIBCPP_DEBUG_LEVEL >= 2 444 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 445 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 446#endif 447 return pointer_traits<pointer>::pointer_to(__node_->__value_); 448 } 449 450 _LIBCPP_INLINE_VISIBILITY 451 __hash_local_iterator& operator++() 452 { 453#if _LIBCPP_DEBUG_LEVEL >= 2 454 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 455 "Attempted to increment non-incrementable unordered container local_iterator"); 456#endif 457 __node_ = __node_->__next_; 458 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 459 __node_ = nullptr; 460 return *this; 461 } 462 463 _LIBCPP_INLINE_VISIBILITY 464 __hash_local_iterator operator++(int) 465 { 466 __hash_local_iterator __t(*this); 467 ++(*this); 468 return __t; 469 } 470 471 friend _LIBCPP_INLINE_VISIBILITY 472 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 473 { 474 return __x.__node_ == __y.__node_; 475 } 476 friend _LIBCPP_INLINE_VISIBILITY 477 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 478 {return !(__x == __y);} 479 480private: 481#if _LIBCPP_DEBUG_LEVEL >= 2 482 _LIBCPP_INLINE_VISIBILITY 483 __hash_local_iterator(__node_pointer __node, size_t __bucket, 484 size_t __bucket_count, const void* __c) _NOEXCEPT 485 : __node_(__node), 486 __bucket_(__bucket), 487 __bucket_count_(__bucket_count) 488 { 489 __get_db()->__insert_ic(this, __c); 490 if (__node_ != nullptr) 491 __node_ = __node_->__next_; 492 } 493#else 494 _LIBCPP_INLINE_VISIBILITY 495 __hash_local_iterator(__node_pointer __node, size_t __bucket, 496 size_t __bucket_count) _NOEXCEPT 497 : __node_(__node), 498 __bucket_(__bucket), 499 __bucket_count_(__bucket_count) 500 { 501 if (__node_ != nullptr) 502 __node_ = __node_->__next_; 503 } 504#endif 505 template <class, class, class, class> friend class __hash_table; 506 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 507 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 508}; 509 510template <class _ConstNodePtr> 511class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 512{ 513 typedef _ConstNodePtr __node_pointer; 514 515 __node_pointer __node_; 516 size_t __bucket_; 517 size_t __bucket_count_; 518 519 typedef pointer_traits<__node_pointer> __pointer_traits; 520 typedef typename __pointer_traits::element_type __node; 521 typedef typename remove_const<__node>::type __non_const_node; 522 typedef typename pointer_traits<__node_pointer>::template 523#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 524 rebind<__non_const_node> 525#else 526 rebind<__non_const_node>::other 527#endif 528 __non_const_node_pointer; 529 typedef __hash_local_iterator<__non_const_node_pointer> 530 __non_const_iterator; 531public: 532 typedef forward_iterator_tag iterator_category; 533 typedef typename remove_const< 534 typename __pointer_traits::element_type::value_type 535 >::type value_type; 536 typedef typename __pointer_traits::difference_type difference_type; 537 typedef const value_type& reference; 538 typedef typename __pointer_traits::template 539#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 540 rebind<const value_type> 541#else 542 rebind<const value_type>::other 543#endif 544 pointer; 545 546 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 547 { 548#if _LIBCPP_DEBUG_LEVEL >= 2 549 __get_db()->__insert_i(this); 550#endif 551 } 552 553 _LIBCPP_INLINE_VISIBILITY 554 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 555 : __node_(__x.__node_), 556 __bucket_(__x.__bucket_), 557 __bucket_count_(__x.__bucket_count_) 558 { 559#if _LIBCPP_DEBUG_LEVEL >= 2 560 __get_db()->__iterator_copy(this, &__x); 561#endif 562 } 563 564#if _LIBCPP_DEBUG_LEVEL >= 2 565 566 _LIBCPP_INLINE_VISIBILITY 567 __hash_const_local_iterator(const __hash_const_local_iterator& __i) 568 : __node_(__i.__node_), 569 __bucket_(__i.__bucket_), 570 __bucket_count_(__i.__bucket_count_) 571 { 572 __get_db()->__iterator_copy(this, &__i); 573 } 574 575 _LIBCPP_INLINE_VISIBILITY 576 ~__hash_const_local_iterator() 577 { 578 __get_db()->__erase_i(this); 579 } 580 581 _LIBCPP_INLINE_VISIBILITY 582 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 583 { 584 if (this != &__i) 585 { 586 __get_db()->__iterator_copy(this, &__i); 587 __node_ = __i.__node_; 588 __bucket_ = __i.__bucket_; 589 __bucket_count_ = __i.__bucket_count_; 590 } 591 return *this; 592 } 593 594#endif // _LIBCPP_DEBUG_LEVEL >= 2 595 596 _LIBCPP_INLINE_VISIBILITY 597 reference operator*() const 598 { 599#if _LIBCPP_DEBUG_LEVEL >= 2 600 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 601 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 602#endif 603 return __node_->__value_; 604 } 605 _LIBCPP_INLINE_VISIBILITY 606 pointer operator->() const 607 { 608#if _LIBCPP_DEBUG_LEVEL >= 2 609 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 610 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 611#endif 612 return pointer_traits<pointer>::pointer_to(__node_->__value_); 613 } 614 615 _LIBCPP_INLINE_VISIBILITY 616 __hash_const_local_iterator& operator++() 617 { 618#if _LIBCPP_DEBUG_LEVEL >= 2 619 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 620 "Attempted to increment non-incrementable unordered container const_local_iterator"); 621#endif 622 __node_ = __node_->__next_; 623 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 624 __node_ = nullptr; 625 return *this; 626 } 627 628 _LIBCPP_INLINE_VISIBILITY 629 __hash_const_local_iterator operator++(int) 630 { 631 __hash_const_local_iterator __t(*this); 632 ++(*this); 633 return __t; 634 } 635 636 friend _LIBCPP_INLINE_VISIBILITY 637 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 638 { 639 return __x.__node_ == __y.__node_; 640 } 641 friend _LIBCPP_INLINE_VISIBILITY 642 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 643 {return !(__x == __y);} 644 645private: 646#if _LIBCPP_DEBUG_LEVEL >= 2 647 _LIBCPP_INLINE_VISIBILITY 648 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 649 size_t __bucket_count, const void* __c) _NOEXCEPT 650 : __node_(__node), 651 __bucket_(__bucket), 652 __bucket_count_(__bucket_count) 653 { 654 __get_db()->__insert_ic(this, __c); 655 if (__node_ != nullptr) 656 __node_ = __node_->__next_; 657 } 658#else 659 _LIBCPP_INLINE_VISIBILITY 660 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 661 size_t __bucket_count) _NOEXCEPT 662 : __node_(__node), 663 __bucket_(__bucket), 664 __bucket_count_(__bucket_count) 665 { 666 if (__node_ != nullptr) 667 __node_ = __node_->__next_; 668 } 669#endif 670 template <class, class, class, class> friend class __hash_table; 671 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 672}; 673 674template <class _Alloc> 675class __bucket_list_deallocator 676{ 677 typedef _Alloc allocator_type; 678 typedef allocator_traits<allocator_type> __alloc_traits; 679 typedef typename __alloc_traits::size_type size_type; 680 681 __compressed_pair<size_type, allocator_type> __data_; 682public: 683 typedef typename __alloc_traits::pointer pointer; 684 685 _LIBCPP_INLINE_VISIBILITY 686 __bucket_list_deallocator() 687 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 688 : __data_(0) {} 689 690 _LIBCPP_INLINE_VISIBILITY 691 __bucket_list_deallocator(const allocator_type& __a, size_type __size) 692 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 693 : __data_(__size, __a) {} 694 695#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 696 697 _LIBCPP_INLINE_VISIBILITY 698 __bucket_list_deallocator(__bucket_list_deallocator&& __x) 699 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 700 : __data_(_VSTD::move(__x.__data_)) 701 { 702 __x.size() = 0; 703 } 704 705#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 706 707 _LIBCPP_INLINE_VISIBILITY 708 size_type& size() _NOEXCEPT {return __data_.first();} 709 _LIBCPP_INLINE_VISIBILITY 710 size_type size() const _NOEXCEPT {return __data_.first();} 711 712 _LIBCPP_INLINE_VISIBILITY 713 allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 714 _LIBCPP_INLINE_VISIBILITY 715 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 716 717 _LIBCPP_INLINE_VISIBILITY 718 void operator()(pointer __p) _NOEXCEPT 719 { 720 __alloc_traits::deallocate(__alloc(), __p, size()); 721 } 722}; 723 724template <class _Alloc> class __hash_map_node_destructor; 725 726template <class _Alloc> 727class __hash_node_destructor 728{ 729 typedef _Alloc allocator_type; 730 typedef allocator_traits<allocator_type> __alloc_traits; 731 typedef typename __alloc_traits::value_type::value_type value_type; 732public: 733 typedef typename __alloc_traits::pointer pointer; 734private: 735 736 allocator_type& __na_; 737 738 __hash_node_destructor& operator=(const __hash_node_destructor&); 739 740public: 741 bool __value_constructed; 742 743 _LIBCPP_INLINE_VISIBILITY 744 explicit __hash_node_destructor(allocator_type& __na, 745 bool __constructed = false) _NOEXCEPT 746 : __na_(__na), 747 __value_constructed(__constructed) 748 {} 749 750 _LIBCPP_INLINE_VISIBILITY 751 void operator()(pointer __p) _NOEXCEPT 752 { 753 if (__value_constructed) 754 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 755 if (__p) 756 __alloc_traits::deallocate(__na_, __p, 1); 757 } 758 759 template <class> friend class __hash_map_node_destructor; 760}; 761 762template <class _Tp, class _Hash, class _Equal, class _Alloc> 763class __hash_table 764{ 765public: 766 typedef _Tp value_type; 767 typedef _Hash hasher; 768 typedef _Equal key_equal; 769 typedef _Alloc allocator_type; 770 771private: 772 typedef allocator_traits<allocator_type> __alloc_traits; 773public: 774 typedef value_type& reference; 775 typedef const value_type& const_reference; 776 typedef typename __alloc_traits::pointer pointer; 777 typedef typename __alloc_traits::const_pointer const_pointer; 778 typedef typename __alloc_traits::size_type size_type; 779 typedef typename __alloc_traits::difference_type difference_type; 780public: 781 // Create __node 782 typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 783 typedef typename __alloc_traits::template 784#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 785 rebind_alloc<__node> 786#else 787 rebind_alloc<__node>::other 788#endif 789 __node_allocator; 790 typedef allocator_traits<__node_allocator> __node_traits; 791 typedef typename __node_traits::pointer __node_pointer; 792 typedef typename __node_traits::pointer __node_const_pointer; 793 typedef __hash_node_base<__node_pointer> __first_node; 794 typedef typename pointer_traits<__node_pointer>::template 795#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 796 rebind<__first_node> 797#else 798 rebind<__first_node>::other 799#endif 800 __node_base_pointer; 801 802private: 803 804 typedef typename __node_traits::template 805#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 806 rebind_alloc<__node_pointer> 807#else 808 rebind_alloc<__node_pointer>::other 809#endif 810 __pointer_allocator; 811 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 812 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 813 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 814 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 815 816 // --- Member data begin --- 817 __bucket_list __bucket_list_; 818 __compressed_pair<__first_node, __node_allocator> __p1_; 819 __compressed_pair<size_type, hasher> __p2_; 820 __compressed_pair<float, key_equal> __p3_; 821 // --- Member data end --- 822 823 _LIBCPP_INLINE_VISIBILITY 824 size_type& size() _NOEXCEPT {return __p2_.first();} 825public: 826 _LIBCPP_INLINE_VISIBILITY 827 size_type size() const _NOEXCEPT {return __p2_.first();} 828 829 _LIBCPP_INLINE_VISIBILITY 830 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 831 _LIBCPP_INLINE_VISIBILITY 832 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 833 834 _LIBCPP_INLINE_VISIBILITY 835 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 836 _LIBCPP_INLINE_VISIBILITY 837 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 838 839 _LIBCPP_INLINE_VISIBILITY 840 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 841 _LIBCPP_INLINE_VISIBILITY 842 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 843 844 _LIBCPP_INLINE_VISIBILITY 845 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 846 _LIBCPP_INLINE_VISIBILITY 847 const __node_allocator& __node_alloc() const _NOEXCEPT 848 {return __p1_.second();} 849 850public: 851 typedef __hash_iterator<__node_pointer> iterator; 852 typedef __hash_const_iterator<__node_pointer> const_iterator; 853 typedef __hash_local_iterator<__node_pointer> local_iterator; 854 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 855 856 __hash_table() 857 _NOEXCEPT_( 858 is_nothrow_default_constructible<__bucket_list>::value && 859 is_nothrow_default_constructible<__first_node>::value && 860 is_nothrow_default_constructible<__node_allocator>::value && 861 is_nothrow_default_constructible<hasher>::value && 862 is_nothrow_default_constructible<key_equal>::value); 863 __hash_table(const hasher& __hf, const key_equal& __eql); 864 __hash_table(const hasher& __hf, const key_equal& __eql, 865 const allocator_type& __a); 866 explicit __hash_table(const allocator_type& __a); 867 __hash_table(const __hash_table& __u); 868 __hash_table(const __hash_table& __u, const allocator_type& __a); 869#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 870 __hash_table(__hash_table&& __u) 871 _NOEXCEPT_( 872 is_nothrow_move_constructible<__bucket_list>::value && 873 is_nothrow_move_constructible<__first_node>::value && 874 is_nothrow_move_constructible<__node_allocator>::value && 875 is_nothrow_move_constructible<hasher>::value && 876 is_nothrow_move_constructible<key_equal>::value); 877 __hash_table(__hash_table&& __u, const allocator_type& __a); 878#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 879 ~__hash_table(); 880 881 __hash_table& operator=(const __hash_table& __u); 882#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 883 __hash_table& operator=(__hash_table&& __u) 884 _NOEXCEPT_( 885 __node_traits::propagate_on_container_move_assignment::value && 886 is_nothrow_move_assignable<__node_allocator>::value && 887 is_nothrow_move_assignable<hasher>::value && 888 is_nothrow_move_assignable<key_equal>::value); 889#endif 890 template <class _InputIterator> 891 void __assign_unique(_InputIterator __first, _InputIterator __last); 892 template <class _InputIterator> 893 void __assign_multi(_InputIterator __first, _InputIterator __last); 894 895 _LIBCPP_INLINE_VISIBILITY 896 size_type max_size() const _NOEXCEPT 897 { 898 return allocator_traits<__pointer_allocator>::max_size( 899 __bucket_list_.get_deleter().__alloc()); 900 } 901 902 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 903 iterator __node_insert_multi(__node_pointer __nd); 904 iterator __node_insert_multi(const_iterator __p, 905 __node_pointer __nd); 906 907#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 908 template <class... _Args> 909 pair<iterator, bool> __emplace_unique(_Args&&... __args); 910 template <class... _Args> 911 iterator __emplace_multi(_Args&&... __args); 912 template <class... _Args> 913 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 914#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 915 916 pair<iterator, bool> __insert_unique(const value_type& __x); 917 918#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 919 template <class _Pp> 920 pair<iterator, bool> __insert_unique(_Pp&& __x); 921#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 922 923#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 924 template <class _Pp> 925 iterator __insert_multi(_Pp&& __x); 926 template <class _Pp> 927 iterator __insert_multi(const_iterator __p, _Pp&& __x); 928#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 929 iterator __insert_multi(const value_type& __x); 930 iterator __insert_multi(const_iterator __p, const value_type& __x); 931#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 932 933 void clear() _NOEXCEPT; 934 void rehash(size_type __n); 935 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 936 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 937 938 _LIBCPP_INLINE_VISIBILITY 939 size_type bucket_count() const _NOEXCEPT 940 { 941 return __bucket_list_.get_deleter().size(); 942 } 943 944 iterator begin() _NOEXCEPT; 945 iterator end() _NOEXCEPT; 946 const_iterator begin() const _NOEXCEPT; 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 size_type __count_unique(const _Key& __k) const; 976 template <class _Key> 977 size_type __count_multi(const _Key& __k) const; 978 979 template <class _Key> 980 pair<iterator, iterator> 981 __equal_range_unique(const _Key& __k); 982 template <class _Key> 983 pair<const_iterator, const_iterator> 984 __equal_range_unique(const _Key& __k) const; 985 986 template <class _Key> 987 pair<iterator, iterator> 988 __equal_range_multi(const _Key& __k); 989 template <class _Key> 990 pair<const_iterator, const_iterator> 991 __equal_range_multi(const _Key& __k) const; 992 993 void swap(__hash_table& __u) 994 _NOEXCEPT_( 995 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 996 __is_nothrow_swappable<__pointer_allocator>::value) && 997 (!__node_traits::propagate_on_container_swap::value || 998 __is_nothrow_swappable<__node_allocator>::value) && 999 __is_nothrow_swappable<hasher>::value && 1000 __is_nothrow_swappable<key_equal>::value); 1001 1002 _LIBCPP_INLINE_VISIBILITY 1003 size_type max_bucket_count() const _NOEXCEPT 1004 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1005 size_type bucket_size(size_type __n) const; 1006 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1007 { 1008 size_type __bc = bucket_count(); 1009 return __bc != 0 ? (float)size() / __bc : 0.f; 1010 } 1011 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1012 { 1013 _LIBCPP_ASSERT(__mlf > 0, 1014 "unordered container::max_load_factor(lf) called with lf <= 0"); 1015 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1016 } 1017 1018 _LIBCPP_INLINE_VISIBILITY 1019 local_iterator 1020 begin(size_type __n) 1021 { 1022 _LIBCPP_ASSERT(__n < bucket_count(), 1023 "unordered container::begin(n) called with n >= bucket_count()"); 1024#if _LIBCPP_DEBUG_LEVEL >= 2 1025 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1026#else 1027 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1028#endif 1029 } 1030 1031 _LIBCPP_INLINE_VISIBILITY 1032 local_iterator 1033 end(size_type __n) 1034 { 1035 _LIBCPP_ASSERT(__n < bucket_count(), 1036 "unordered container::end(n) called with n >= bucket_count()"); 1037#if _LIBCPP_DEBUG_LEVEL >= 2 1038 return local_iterator(nullptr, __n, bucket_count(), this); 1039#else 1040 return local_iterator(nullptr, __n, bucket_count()); 1041#endif 1042 } 1043 1044 _LIBCPP_INLINE_VISIBILITY 1045 const_local_iterator 1046 cbegin(size_type __n) const 1047 { 1048 _LIBCPP_ASSERT(__n < bucket_count(), 1049 "unordered container::cbegin(n) called with n >= bucket_count()"); 1050#if _LIBCPP_DEBUG_LEVEL >= 2 1051 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1052#else 1053 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1054#endif 1055 } 1056 1057 _LIBCPP_INLINE_VISIBILITY 1058 const_local_iterator 1059 cend(size_type __n) const 1060 { 1061 _LIBCPP_ASSERT(__n < bucket_count(), 1062 "unordered container::cend(n) called with n >= bucket_count()"); 1063#if _LIBCPP_DEBUG_LEVEL >= 2 1064 return const_local_iterator(nullptr, __n, bucket_count(), this); 1065#else 1066 return const_local_iterator(nullptr, __n, bucket_count()); 1067#endif 1068 } 1069 1070#if _LIBCPP_DEBUG_LEVEL >= 2 1071 1072 bool __dereferenceable(const const_iterator* __i) const; 1073 bool __decrementable(const const_iterator* __i) const; 1074 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1075 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1076 1077#endif // _LIBCPP_DEBUG_LEVEL >= 2 1078 1079private: 1080 void __rehash(size_type __n); 1081 1082#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1083#ifndef _LIBCPP_HAS_NO_VARIADICS 1084 template <class ..._Args> 1085 __node_holder __construct_node(_Args&& ...__args); 1086#endif // _LIBCPP_HAS_NO_VARIADICS 1087 __node_holder __construct_node(value_type&& __v, size_t __hash); 1088#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1089 __node_holder __construct_node(const value_type& __v); 1090#endif 1091 __node_holder __construct_node(const value_type& __v, size_t __hash); 1092 1093 _LIBCPP_INLINE_VISIBILITY 1094 void __copy_assign_alloc(const __hash_table& __u) 1095 {__copy_assign_alloc(__u, integral_constant<bool, 1096 __node_traits::propagate_on_container_copy_assignment::value>());} 1097 void __copy_assign_alloc(const __hash_table& __u, true_type); 1098 _LIBCPP_INLINE_VISIBILITY 1099 void __copy_assign_alloc(const __hash_table&, false_type) {} 1100 1101 void __move_assign(__hash_table& __u, false_type); 1102 void __move_assign(__hash_table& __u, true_type) 1103 _NOEXCEPT_( 1104 is_nothrow_move_assignable<__node_allocator>::value && 1105 is_nothrow_move_assignable<hasher>::value && 1106 is_nothrow_move_assignable<key_equal>::value); 1107 _LIBCPP_INLINE_VISIBILITY 1108 void __move_assign_alloc(__hash_table& __u) 1109 _NOEXCEPT_( 1110 !__node_traits::propagate_on_container_move_assignment::value || 1111 (is_nothrow_move_assignable<__pointer_allocator>::value && 1112 is_nothrow_move_assignable<__node_allocator>::value)) 1113 {__move_assign_alloc(__u, integral_constant<bool, 1114 __node_traits::propagate_on_container_move_assignment::value>());} 1115 _LIBCPP_INLINE_VISIBILITY 1116 void __move_assign_alloc(__hash_table& __u, true_type) 1117 _NOEXCEPT_( 1118 is_nothrow_move_assignable<__pointer_allocator>::value && 1119 is_nothrow_move_assignable<__node_allocator>::value) 1120 { 1121 __bucket_list_.get_deleter().__alloc() = 1122 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1123 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1124 } 1125 _LIBCPP_INLINE_VISIBILITY 1126 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1127 1128 template <class _Ap> 1129 _LIBCPP_INLINE_VISIBILITY 1130 static 1131 void 1132 __swap_alloc(_Ap& __x, _Ap& __y) 1133 _NOEXCEPT_( 1134 !allocator_traits<_Ap>::propagate_on_container_swap::value || 1135 __is_nothrow_swappable<_Ap>::value) 1136 { 1137 __swap_alloc(__x, __y, 1138 integral_constant<bool, 1139 allocator_traits<_Ap>::propagate_on_container_swap::value 1140 >()); 1141 } 1142 1143 template <class _Ap> 1144 _LIBCPP_INLINE_VISIBILITY 1145 static 1146 void 1147 __swap_alloc(_Ap& __x, _Ap& __y, true_type) 1148 _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 1149 { 1150 using _VSTD::swap; 1151 swap(__x, __y); 1152 } 1153 1154 template <class _Ap> 1155 _LIBCPP_INLINE_VISIBILITY 1156 static 1157 void 1158 __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 1159 1160 void __deallocate(__node_pointer __np) _NOEXCEPT; 1161 __node_pointer __detach() _NOEXCEPT; 1162 1163 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1164 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1165}; 1166 1167template <class _Tp, class _Hash, class _Equal, class _Alloc> 1168inline _LIBCPP_INLINE_VISIBILITY 1169__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1170 _NOEXCEPT_( 1171 is_nothrow_default_constructible<__bucket_list>::value && 1172 is_nothrow_default_constructible<__first_node>::value && 1173 is_nothrow_default_constructible<hasher>::value && 1174 is_nothrow_default_constructible<key_equal>::value) 1175 : __p2_(0), 1176 __p3_(1.0f) 1177{ 1178} 1179 1180template <class _Tp, class _Hash, class _Equal, class _Alloc> 1181inline _LIBCPP_INLINE_VISIBILITY 1182__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1183 const key_equal& __eql) 1184 : __bucket_list_(nullptr, __bucket_list_deleter()), 1185 __p1_(), 1186 __p2_(0, __hf), 1187 __p3_(1.0f, __eql) 1188{ 1189} 1190 1191template <class _Tp, class _Hash, class _Equal, class _Alloc> 1192__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1193 const key_equal& __eql, 1194 const allocator_type& __a) 1195 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1196 __p1_(__node_allocator(__a)), 1197 __p2_(0, __hf), 1198 __p3_(1.0f, __eql) 1199{ 1200} 1201 1202template <class _Tp, class _Hash, class _Equal, class _Alloc> 1203__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1204 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1205 __p1_(__node_allocator(__a)), 1206 __p2_(0), 1207 __p3_(1.0f) 1208{ 1209} 1210 1211template <class _Tp, class _Hash, class _Equal, class _Alloc> 1212__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1213 : __bucket_list_(nullptr, 1214 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1215 select_on_container_copy_construction( 1216 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1217 __p1_(allocator_traits<__node_allocator>:: 1218 select_on_container_copy_construction(__u.__node_alloc())), 1219 __p2_(0, __u.hash_function()), 1220 __p3_(__u.__p3_) 1221{ 1222} 1223 1224template <class _Tp, class _Hash, class _Equal, class _Alloc> 1225__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1226 const allocator_type& __a) 1227 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1228 __p1_(__node_allocator(__a)), 1229 __p2_(0, __u.hash_function()), 1230 __p3_(__u.__p3_) 1231{ 1232} 1233 1234#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1235 1236template <class _Tp, class _Hash, class _Equal, class _Alloc> 1237__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1238 _NOEXCEPT_( 1239 is_nothrow_move_constructible<__bucket_list>::value && 1240 is_nothrow_move_constructible<__first_node>::value && 1241 is_nothrow_move_constructible<hasher>::value && 1242 is_nothrow_move_constructible<key_equal>::value) 1243 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1244 __p1_(_VSTD::move(__u.__p1_)), 1245 __p2_(_VSTD::move(__u.__p2_)), 1246 __p3_(_VSTD::move(__u.__p3_)) 1247{ 1248 if (size() > 0) 1249 { 1250 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1251 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1252 __u.__p1_.first().__next_ = nullptr; 1253 __u.size() = 0; 1254 } 1255} 1256 1257template <class _Tp, class _Hash, class _Equal, class _Alloc> 1258__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1259 const allocator_type& __a) 1260 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1261 __p1_(__node_allocator(__a)), 1262 __p2_(0, _VSTD::move(__u.hash_function())), 1263 __p3_(_VSTD::move(__u.__p3_)) 1264{ 1265 if (__a == allocator_type(__u.__node_alloc())) 1266 { 1267 __bucket_list_.reset(__u.__bucket_list_.release()); 1268 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1269 __u.__bucket_list_.get_deleter().size() = 0; 1270 if (__u.size() > 0) 1271 { 1272 __p1_.first().__next_ = __u.__p1_.first().__next_; 1273 __u.__p1_.first().__next_ = nullptr; 1274 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1275 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1276 size() = __u.size(); 1277 __u.size() = 0; 1278 } 1279 } 1280} 1281 1282#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1283 1284template <class _Tp, class _Hash, class _Equal, class _Alloc> 1285__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1286{ 1287 __deallocate(__p1_.first().__next_); 1288#if _LIBCPP_DEBUG_LEVEL >= 2 1289 __get_db()->__erase_c(this); 1290#endif 1291} 1292 1293template <class _Tp, class _Hash, class _Equal, class _Alloc> 1294void 1295__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1296 const __hash_table& __u, true_type) 1297{ 1298 if (__node_alloc() != __u.__node_alloc()) 1299 { 1300 clear(); 1301 __bucket_list_.reset(); 1302 __bucket_list_.get_deleter().size() = 0; 1303 } 1304 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1305 __node_alloc() = __u.__node_alloc(); 1306} 1307 1308template <class _Tp, class _Hash, class _Equal, class _Alloc> 1309__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1310__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1311{ 1312 if (this != &__u) 1313 { 1314 __copy_assign_alloc(__u); 1315 hash_function() = __u.hash_function(); 1316 key_eq() = __u.key_eq(); 1317 max_load_factor() = __u.max_load_factor(); 1318 __assign_multi(__u.begin(), __u.end()); 1319 } 1320 return *this; 1321} 1322 1323template <class _Tp, class _Hash, class _Equal, class _Alloc> 1324void 1325__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1326 _NOEXCEPT 1327{ 1328 __node_allocator& __na = __node_alloc(); 1329 while (__np != nullptr) 1330 { 1331 __node_pointer __next = __np->__next_; 1332#if _LIBCPP_DEBUG_LEVEL >= 2 1333 __c_node* __c = __get_db()->__find_c_and_lock(this); 1334 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1335 { 1336 --__p; 1337 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1338 if (__i->__node_ == __np) 1339 { 1340 (*__p)->__c_ = nullptr; 1341 if (--__c->end_ != __p) 1342 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1343 } 1344 } 1345 __get_db()->unlock(); 1346#endif 1347 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1348 __node_traits::deallocate(__na, __np, 1); 1349 __np = __next; 1350 } 1351} 1352 1353template <class _Tp, class _Hash, class _Equal, class _Alloc> 1354typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1355__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1356{ 1357 size_type __bc = bucket_count(); 1358 for (size_type __i = 0; __i < __bc; ++__i) 1359 __bucket_list_[__i] = nullptr; 1360 size() = 0; 1361 __node_pointer __cache = __p1_.first().__next_; 1362 __p1_.first().__next_ = nullptr; 1363 return __cache; 1364} 1365 1366#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1367 1368template <class _Tp, class _Hash, class _Equal, class _Alloc> 1369void 1370__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1371 __hash_table& __u, true_type) 1372 _NOEXCEPT_( 1373 is_nothrow_move_assignable<__node_allocator>::value && 1374 is_nothrow_move_assignable<hasher>::value && 1375 is_nothrow_move_assignable<key_equal>::value) 1376{ 1377 clear(); 1378 __bucket_list_.reset(__u.__bucket_list_.release()); 1379 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1380 __u.__bucket_list_.get_deleter().size() = 0; 1381 __move_assign_alloc(__u); 1382 size() = __u.size(); 1383 hash_function() = _VSTD::move(__u.hash_function()); 1384 max_load_factor() = __u.max_load_factor(); 1385 key_eq() = _VSTD::move(__u.key_eq()); 1386 __p1_.first().__next_ = __u.__p1_.first().__next_; 1387 if (size() > 0) 1388 { 1389 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1390 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1391 __u.__p1_.first().__next_ = nullptr; 1392 __u.size() = 0; 1393 } 1394#if _LIBCPP_DEBUG_LEVEL >= 2 1395 __get_db()->swap(this, &__u); 1396#endif 1397} 1398 1399template <class _Tp, class _Hash, class _Equal, class _Alloc> 1400void 1401__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1402 __hash_table& __u, false_type) 1403{ 1404 if (__node_alloc() == __u.__node_alloc()) 1405 __move_assign(__u, true_type()); 1406 else 1407 { 1408 hash_function() = _VSTD::move(__u.hash_function()); 1409 key_eq() = _VSTD::move(__u.key_eq()); 1410 max_load_factor() = __u.max_load_factor(); 1411 if (bucket_count() != 0) 1412 { 1413 __node_pointer __cache = __detach(); 1414#ifndef _LIBCPP_NO_EXCEPTIONS 1415 try 1416 { 1417#endif // _LIBCPP_NO_EXCEPTIONS 1418 const_iterator __i = __u.begin(); 1419 while (__cache != nullptr && __u.size() != 0) 1420 { 1421 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1422 __node_pointer __next = __cache->__next_; 1423 __node_insert_multi(__cache); 1424 __cache = __next; 1425 } 1426#ifndef _LIBCPP_NO_EXCEPTIONS 1427 } 1428 catch (...) 1429 { 1430 __deallocate(__cache); 1431 throw; 1432 } 1433#endif // _LIBCPP_NO_EXCEPTIONS 1434 __deallocate(__cache); 1435 } 1436 const_iterator __i = __u.begin(); 1437 while (__u.size() != 0) 1438 { 1439 __node_holder __h = 1440 __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1441 __node_insert_multi(__h.get()); 1442 __h.release(); 1443 } 1444 } 1445} 1446 1447template <class _Tp, class _Hash, class _Equal, class _Alloc> 1448inline _LIBCPP_INLINE_VISIBILITY 1449__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1450__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1451 _NOEXCEPT_( 1452 __node_traits::propagate_on_container_move_assignment::value && 1453 is_nothrow_move_assignable<__node_allocator>::value && 1454 is_nothrow_move_assignable<hasher>::value && 1455 is_nothrow_move_assignable<key_equal>::value) 1456{ 1457 __move_assign(__u, integral_constant<bool, 1458 __node_traits::propagate_on_container_move_assignment::value>()); 1459 return *this; 1460} 1461 1462#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1463 1464template <class _Tp, class _Hash, class _Equal, class _Alloc> 1465template <class _InputIterator> 1466void 1467__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1468 _InputIterator __last) 1469{ 1470 if (bucket_count() != 0) 1471 { 1472 __node_pointer __cache = __detach(); 1473#ifndef _LIBCPP_NO_EXCEPTIONS 1474 try 1475 { 1476#endif // _LIBCPP_NO_EXCEPTIONS 1477 for (; __cache != nullptr && __first != __last; ++__first) 1478 { 1479 __cache->__value_ = *__first; 1480 __node_pointer __next = __cache->__next_; 1481 __node_insert_unique(__cache); 1482 __cache = __next; 1483 } 1484#ifndef _LIBCPP_NO_EXCEPTIONS 1485 } 1486 catch (...) 1487 { 1488 __deallocate(__cache); 1489 throw; 1490 } 1491#endif // _LIBCPP_NO_EXCEPTIONS 1492 __deallocate(__cache); 1493 } 1494 for (; __first != __last; ++__first) 1495 __insert_unique(*__first); 1496} 1497 1498template <class _Tp, class _Hash, class _Equal, class _Alloc> 1499template <class _InputIterator> 1500void 1501__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1502 _InputIterator __last) 1503{ 1504 if (bucket_count() != 0) 1505 { 1506 __node_pointer __cache = __detach(); 1507#ifndef _LIBCPP_NO_EXCEPTIONS 1508 try 1509 { 1510#endif // _LIBCPP_NO_EXCEPTIONS 1511 for (; __cache != nullptr && __first != __last; ++__first) 1512 { 1513 __cache->__value_ = *__first; 1514 __node_pointer __next = __cache->__next_; 1515 __node_insert_multi(__cache); 1516 __cache = __next; 1517 } 1518#ifndef _LIBCPP_NO_EXCEPTIONS 1519 } 1520 catch (...) 1521 { 1522 __deallocate(__cache); 1523 throw; 1524 } 1525#endif // _LIBCPP_NO_EXCEPTIONS 1526 __deallocate(__cache); 1527 } 1528 for (; __first != __last; ++__first) 1529 __insert_multi(*__first); 1530} 1531 1532template <class _Tp, class _Hash, class _Equal, class _Alloc> 1533inline _LIBCPP_INLINE_VISIBILITY 1534typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1535__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1536{ 1537#if _LIBCPP_DEBUG_LEVEL >= 2 1538 return iterator(__p1_.first().__next_, this); 1539#else 1540 return iterator(__p1_.first().__next_); 1541#endif 1542} 1543 1544template <class _Tp, class _Hash, class _Equal, class _Alloc> 1545inline _LIBCPP_INLINE_VISIBILITY 1546typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1547__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1548{ 1549#if _LIBCPP_DEBUG_LEVEL >= 2 1550 return iterator(nullptr, this); 1551#else 1552 return iterator(nullptr); 1553#endif 1554} 1555 1556template <class _Tp, class _Hash, class _Equal, class _Alloc> 1557inline _LIBCPP_INLINE_VISIBILITY 1558typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1559__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1560{ 1561#if _LIBCPP_DEBUG_LEVEL >= 2 1562 return const_iterator(__p1_.first().__next_, this); 1563#else 1564 return const_iterator(__p1_.first().__next_); 1565#endif 1566} 1567 1568template <class _Tp, class _Hash, class _Equal, class _Alloc> 1569inline _LIBCPP_INLINE_VISIBILITY 1570typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1571__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1572{ 1573#if _LIBCPP_DEBUG_LEVEL >= 2 1574 return const_iterator(nullptr, this); 1575#else 1576 return const_iterator(nullptr); 1577#endif 1578} 1579 1580template <class _Tp, class _Hash, class _Equal, class _Alloc> 1581void 1582__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1583{ 1584 if (size() > 0) 1585 { 1586 __deallocate(__p1_.first().__next_); 1587 __p1_.first().__next_ = nullptr; 1588 size_type __bc = bucket_count(); 1589 for (size_type __i = 0; __i < __bc; ++__i) 1590 __bucket_list_[__i] = nullptr; 1591 size() = 0; 1592 } 1593} 1594 1595template <class _Tp, class _Hash, class _Equal, class _Alloc> 1596pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1597__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1598{ 1599 __nd->__hash_ = hash_function()(__nd->__value_); 1600 size_type __bc = bucket_count(); 1601 bool __inserted = false; 1602 __node_pointer __ndptr; 1603 size_t __chash; 1604 if (__bc != 0) 1605 { 1606 __chash = __constrain_hash(__nd->__hash_, __bc); 1607 __ndptr = __bucket_list_[__chash]; 1608 if (__ndptr != nullptr) 1609 { 1610 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1611 __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1612 __ndptr = __ndptr->__next_) 1613 { 1614 if (key_eq()(__ndptr->__value_, __nd->__value_)) 1615 goto __done; 1616 } 1617 } 1618 } 1619 { 1620 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1621 { 1622 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1623 size_type(ceil(float(size() + 1) / max_load_factor())))); 1624 __bc = bucket_count(); 1625 __chash = __constrain_hash(__nd->__hash_, __bc); 1626 } 1627 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1628 __node_pointer __pn = __bucket_list_[__chash]; 1629 if (__pn == nullptr) 1630 { 1631 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1632 __nd->__next_ = __pn->__next_; 1633 __pn->__next_ = __nd; 1634 // fix up __bucket_list_ 1635 __bucket_list_[__chash] = __pn; 1636 if (__nd->__next_ != nullptr) 1637 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1638 } 1639 else 1640 { 1641 __nd->__next_ = __pn->__next_; 1642 __pn->__next_ = __nd; 1643 } 1644 __ndptr = __nd; 1645 // increment size 1646 ++size(); 1647 __inserted = true; 1648 } 1649__done: 1650#if _LIBCPP_DEBUG_LEVEL >= 2 1651 return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1652#else 1653 return pair<iterator, bool>(iterator(__ndptr), __inserted); 1654#endif 1655} 1656 1657template <class _Tp, class _Hash, class _Equal, class _Alloc> 1658typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1659__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1660{ 1661 __cp->__hash_ = hash_function()(__cp->__value_); 1662 size_type __bc = bucket_count(); 1663 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1664 { 1665 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1666 size_type(ceil(float(size() + 1) / max_load_factor())))); 1667 __bc = bucket_count(); 1668 } 1669 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1670 __node_pointer __pn = __bucket_list_[__chash]; 1671 if (__pn == nullptr) 1672 { 1673 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1674 __cp->__next_ = __pn->__next_; 1675 __pn->__next_ = __cp; 1676 // fix up __bucket_list_ 1677 __bucket_list_[__chash] = __pn; 1678 if (__cp->__next_ != nullptr) 1679 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1680 } 1681 else 1682 { 1683 for (bool __found = false; __pn->__next_ != nullptr && 1684 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1685 __pn = __pn->__next_) 1686 { 1687 // __found key_eq() action 1688 // false false loop 1689 // true true loop 1690 // false true set __found to true 1691 // true false break 1692 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1693 key_eq()(__pn->__next_->__value_, __cp->__value_))) 1694 { 1695 if (!__found) 1696 __found = true; 1697 else 1698 break; 1699 } 1700 } 1701 __cp->__next_ = __pn->__next_; 1702 __pn->__next_ = __cp; 1703 if (__cp->__next_ != nullptr) 1704 { 1705 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1706 if (__nhash != __chash) 1707 __bucket_list_[__nhash] = __cp; 1708 } 1709 } 1710 ++size(); 1711#if _LIBCPP_DEBUG_LEVEL >= 2 1712 return iterator(__cp, this); 1713#else 1714 return iterator(__cp); 1715#endif 1716} 1717 1718template <class _Tp, class _Hash, class _Equal, class _Alloc> 1719typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1720__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1721 const_iterator __p, __node_pointer __cp) 1722{ 1723#if _LIBCPP_DEBUG_LEVEL >= 2 1724 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1725 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1726 " referring to this unordered container"); 1727#endif 1728 if (__p != end() && key_eq()(*__p, __cp->__value_)) 1729 { 1730 __node_pointer __np = __p.__node_; 1731 __cp->__hash_ = __np->__hash_; 1732 size_type __bc = bucket_count(); 1733 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1734 { 1735 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1736 size_type(ceil(float(size() + 1) / max_load_factor())))); 1737 __bc = bucket_count(); 1738 } 1739 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1740 __node_pointer __pp = __bucket_list_[__chash]; 1741 while (__pp->__next_ != __np) 1742 __pp = __pp->__next_; 1743 __cp->__next_ = __np; 1744 __pp->__next_ = __cp; 1745 ++size(); 1746#if _LIBCPP_DEBUG_LEVEL >= 2 1747 return iterator(__cp, this); 1748#else 1749 return iterator(__cp); 1750#endif 1751 } 1752 return __node_insert_multi(__cp); 1753} 1754 1755template <class _Tp, class _Hash, class _Equal, class _Alloc> 1756pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1757__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1758{ 1759 size_t __hash = hash_function()(__x); 1760 size_type __bc = bucket_count(); 1761 bool __inserted = false; 1762 __node_pointer __nd; 1763 size_t __chash; 1764 if (__bc != 0) 1765 { 1766 __chash = __constrain_hash(__hash, __bc); 1767 __nd = __bucket_list_[__chash]; 1768 if (__nd != nullptr) 1769 { 1770 for (__nd = __nd->__next_; __nd != nullptr && 1771 __constrain_hash(__nd->__hash_, __bc) == __chash; 1772 __nd = __nd->__next_) 1773 { 1774 if (key_eq()(__nd->__value_, __x)) 1775 goto __done; 1776 } 1777 } 1778 } 1779 { 1780 __node_holder __h = __construct_node(__x, __hash); 1781 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1782 { 1783 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1784 size_type(ceil(float(size() + 1) / max_load_factor())))); 1785 __bc = bucket_count(); 1786 __chash = __constrain_hash(__hash, __bc); 1787 } 1788 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1789 __node_pointer __pn = __bucket_list_[__chash]; 1790 if (__pn == nullptr) 1791 { 1792 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1793 __h->__next_ = __pn->__next_; 1794 __pn->__next_ = __h.get(); 1795 // fix up __bucket_list_ 1796 __bucket_list_[__chash] = __pn; 1797 if (__h->__next_ != nullptr) 1798 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1799 } 1800 else 1801 { 1802 __h->__next_ = __pn->__next_; 1803 __pn->__next_ = __h.get(); 1804 } 1805 __nd = __h.release(); 1806 // increment size 1807 ++size(); 1808 __inserted = true; 1809 } 1810__done: 1811#if _LIBCPP_DEBUG_LEVEL >= 2 1812 return pair<iterator, bool>(iterator(__nd, this), __inserted); 1813#else 1814 return pair<iterator, bool>(iterator(__nd), __inserted); 1815#endif 1816} 1817 1818#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1819#ifndef _LIBCPP_HAS_NO_VARIADICS 1820 1821template <class _Tp, class _Hash, class _Equal, class _Alloc> 1822template <class... _Args> 1823pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1824__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1825{ 1826 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1827 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1828 if (__r.second) 1829 __h.release(); 1830 return __r; 1831} 1832 1833template <class _Tp, class _Hash, class _Equal, class _Alloc> 1834template <class... _Args> 1835typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1836__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1837{ 1838 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1839 iterator __r = __node_insert_multi(__h.get()); 1840 __h.release(); 1841 return __r; 1842} 1843 1844template <class _Tp, class _Hash, class _Equal, class _Alloc> 1845template <class... _Args> 1846typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1847__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1848 const_iterator __p, _Args&&... __args) 1849{ 1850#if _LIBCPP_DEBUG_LEVEL >= 2 1851 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1852 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1853 " referring to this unordered container"); 1854#endif 1855 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1856 iterator __r = __node_insert_multi(__p, __h.get()); 1857 __h.release(); 1858 return __r; 1859} 1860 1861#endif // _LIBCPP_HAS_NO_VARIADICS 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_power2(__bc) ? __next_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 _VSTD::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 _VSTD::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 _LIBCPP_INLINE_VISIBILITY 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 _NOEXCEPT_( 2365 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 2366 __is_nothrow_swappable<__pointer_allocator>::value) && 2367 (!__node_traits::propagate_on_container_swap::value || 2368 __is_nothrow_swappable<__node_allocator>::value) && 2369 __is_nothrow_swappable<hasher>::value && 2370 __is_nothrow_swappable<key_equal>::value) 2371{ 2372 { 2373 __node_pointer_pointer __npp = __bucket_list_.release(); 2374 __bucket_list_.reset(__u.__bucket_list_.release()); 2375 __u.__bucket_list_.reset(__npp); 2376 } 2377 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2378 __swap_alloc(__bucket_list_.get_deleter().__alloc(), 2379 __u.__bucket_list_.get_deleter().__alloc()); 2380 __swap_alloc(__node_alloc(), __u.__node_alloc()); 2381 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2382 __p2_.swap(__u.__p2_); 2383 __p3_.swap(__u.__p3_); 2384 if (size() > 0) 2385 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2386 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2387 if (__u.size() > 0) 2388 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2389 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2390#if _LIBCPP_DEBUG_LEVEL >= 2 2391 __get_db()->swap(this, &__u); 2392#endif 2393} 2394 2395template <class _Tp, class _Hash, class _Equal, class _Alloc> 2396typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2397__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2398{ 2399 _LIBCPP_ASSERT(__n < bucket_count(), 2400 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2401 __node_const_pointer __np = __bucket_list_[__n]; 2402 size_type __bc = bucket_count(); 2403 size_type __r = 0; 2404 if (__np != nullptr) 2405 { 2406 for (__np = __np->__next_; __np != nullptr && 2407 __constrain_hash(__np->__hash_, __bc) == __n; 2408 __np = __np->__next_, ++__r) 2409 ; 2410 } 2411 return __r; 2412} 2413 2414template <class _Tp, class _Hash, class _Equal, class _Alloc> 2415inline _LIBCPP_INLINE_VISIBILITY 2416void 2417swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2418 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2419 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2420{ 2421 __x.swap(__y); 2422} 2423 2424#if _LIBCPP_DEBUG_LEVEL >= 2 2425 2426template <class _Tp, class _Hash, class _Equal, class _Alloc> 2427bool 2428__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2429{ 2430 return __i->__node_ != nullptr; 2431} 2432 2433template <class _Tp, class _Hash, class _Equal, class _Alloc> 2434bool 2435__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2436{ 2437 return false; 2438} 2439 2440template <class _Tp, class _Hash, class _Equal, class _Alloc> 2441bool 2442__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2443{ 2444 return false; 2445} 2446 2447template <class _Tp, class _Hash, class _Equal, class _Alloc> 2448bool 2449__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2450{ 2451 return false; 2452} 2453 2454#endif // _LIBCPP_DEBUG_LEVEL >= 2 2455_LIBCPP_END_NAMESPACE_STD 2456 2457#endif // _LIBCPP__HASH_TABLE 2458