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