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