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#include <utility> 21#include <type_traits> 22 23#include <__debug> 24 25#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26#pragma GCC system_header 27#endif 28 29_LIBCPP_PUSH_MACROS 30#include <__undef_macros> 31 32 33_LIBCPP_BEGIN_NAMESPACE_STD 34 35template <class _Key, class _Tp> 36struct __hash_value_type; 37 38template <class _Key, class _Cp, class _Hash, 39 bool = is_empty<_Hash>::value && !__libcpp_is_final<_Hash>::value> 40class __unordered_map_hasher; 41 42template <class _Key, class _Cp, class _Pred, 43 bool = is_empty<_Pred>::value && !__libcpp_is_final<_Pred>::value 44 > 45class __unordered_map_equal; 46 47#ifndef _LIBCPP_CXX03_LANG 48template <class _Tp> 49struct __is_hash_value_type_imp : false_type {}; 50 51template <class _Key, class _Value> 52struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value>> : true_type {}; 53 54template <class ..._Args> 55struct __is_hash_value_type : false_type {}; 56 57template <class _One> 58struct __is_hash_value_type<_One> : __is_hash_value_type_imp<typename __uncvref<_One>::type> {}; 59#endif 60 61_LIBCPP_FUNC_VIS 62size_t __next_prime(size_t __n); 63 64template <class _NodePtr> 65struct __hash_node_base 66{ 67 typedef typename pointer_traits<_NodePtr>::element_type __node_type; 68 typedef __hash_node_base __first_node; 69 typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer; 70 typedef _NodePtr __node_pointer; 71 72#if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB) 73 typedef __node_base_pointer __next_pointer; 74#else 75 typedef typename conditional< 76 is_pointer<__node_pointer>::value, 77 __node_base_pointer, 78 __node_pointer>::type __next_pointer; 79#endif 80 81 __next_pointer __next_; 82 83 _LIBCPP_INLINE_VISIBILITY 84 __next_pointer __ptr() _NOEXCEPT { 85 return static_cast<__next_pointer>( 86 pointer_traits<__node_base_pointer>::pointer_to(*this)); 87 } 88 89 _LIBCPP_INLINE_VISIBILITY 90 __node_pointer __upcast() _NOEXCEPT { 91 return static_cast<__node_pointer>( 92 pointer_traits<__node_base_pointer>::pointer_to(*this)); 93 } 94 95 _LIBCPP_INLINE_VISIBILITY 96 size_t __hash() const _NOEXCEPT { 97 return static_cast<__node_type const&>(*this).__hash_; 98 } 99 100 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 101}; 102 103template <class _Tp, class _VoidPtr> 104struct __hash_node 105 : public __hash_node_base 106 < 107 typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type 108 > 109{ 110 typedef _Tp __node_value_type; 111 112 size_t __hash_; 113 __node_value_type __value_; 114}; 115 116inline _LIBCPP_INLINE_VISIBILITY 117bool 118__is_hash_power2(size_t __bc) 119{ 120 return __bc > 2 && !(__bc & (__bc - 1)); 121} 122 123inline _LIBCPP_INLINE_VISIBILITY 124size_t 125__constrain_hash(size_t __h, size_t __bc) 126{ 127 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : 128 (__h < __bc ? __h : __h % __bc); 129} 130 131inline _LIBCPP_INLINE_VISIBILITY 132size_t 133__next_hash_pow2(size_t __n) 134{ 135 return __n < 2 ? __n : (size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1))); 136} 137 138 139template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 140 141template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_iterator; 142template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 143template <class _NodePtr> class _LIBCPP_TEMPLATE_VIS __hash_local_iterator; 144template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 145template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator; 146template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 147 148template <class _Tp> 149struct __hash_key_value_types { 150 static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, ""); 151 typedef _Tp key_type; 152 typedef _Tp __node_value_type; 153 typedef _Tp __container_value_type; 154 static const bool __is_map = false; 155 156 _LIBCPP_INLINE_VISIBILITY 157 static key_type const& __get_key(_Tp const& __v) { 158 return __v; 159 } 160 _LIBCPP_INLINE_VISIBILITY 161 static __container_value_type const& __get_value(__node_value_type const& __v) { 162 return __v; 163 } 164 _LIBCPP_INLINE_VISIBILITY 165 static __container_value_type* __get_ptr(__node_value_type& __n) { 166 return _VSTD::addressof(__n); 167 } 168#ifndef _LIBCPP_CXX03_LANG 169 _LIBCPP_INLINE_VISIBILITY 170 static __container_value_type&& __move(__node_value_type& __v) { 171 return _VSTD::move(__v); 172 } 173#endif 174}; 175 176template <class _Key, class _Tp> 177struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > { 178 typedef _Key key_type; 179 typedef _Tp mapped_type; 180 typedef __hash_value_type<_Key, _Tp> __node_value_type; 181 typedef pair<const _Key, _Tp> __container_value_type; 182 typedef __container_value_type __map_value_type; 183 static const bool __is_map = true; 184 185 _LIBCPP_INLINE_VISIBILITY 186 static key_type const& __get_key(__container_value_type const& __v) { 187 return __v.first; 188 } 189 190 template <class _Up> 191 _LIBCPP_INLINE_VISIBILITY 192 static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value, 193 __container_value_type const&>::type 194 __get_value(_Up& __t) { 195 return __t.__get_value(); 196 } 197 198 template <class _Up> 199 _LIBCPP_INLINE_VISIBILITY 200 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, 201 __container_value_type const&>::type 202 __get_value(_Up& __t) { 203 return __t; 204 } 205 206 _LIBCPP_INLINE_VISIBILITY 207 static __container_value_type* __get_ptr(__node_value_type& __n) { 208 return _VSTD::addressof(__n.__get_value()); 209 } 210#ifndef _LIBCPP_CXX03_LANG 211 _LIBCPP_INLINE_VISIBILITY 212 static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { 213 return __v.__move(); 214 } 215#endif 216 217}; 218 219template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, 220 bool = _KVTypes::__is_map> 221struct __hash_map_pointer_types {}; 222 223template <class _Tp, class _AllocPtr, class _KVTypes> 224struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> { 225 typedef typename _KVTypes::__map_value_type _Mv; 226 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type 227 __map_value_type_pointer; 228 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type 229 __const_map_value_type_pointer; 230}; 231 232template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type> 233struct __hash_node_types; 234 235template <class _NodePtr, class _Tp, class _VoidPtr> 236struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> > 237 : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr> 238 239{ 240 typedef __hash_key_value_types<_Tp> __base; 241 242public: 243 typedef ptrdiff_t difference_type; 244 typedef size_t size_type; 245 246 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer; 247 248 typedef typename pointer_traits<_NodePtr>::element_type __node_type; 249 typedef _NodePtr __node_pointer; 250 251 typedef __hash_node_base<__node_pointer> __node_base_type; 252 typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type 253 __node_base_pointer; 254 255 typedef typename __node_base_type::__next_pointer __next_pointer; 256 257 typedef _Tp __node_value_type; 258 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type 259 __node_value_type_pointer; 260 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type 261 __const_node_value_type_pointer; 262 263private: 264 static_assert(!is_const<__node_type>::value, 265 "_NodePtr should never be a pointer to const"); 266 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value), 267 "_VoidPtr does not point to unqualified void type"); 268 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type, 269 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr."); 270}; 271 272template <class _HashIterator> 273struct __hash_node_types_from_iterator; 274template <class _NodePtr> 275struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 276template <class _NodePtr> 277struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 278template <class _NodePtr> 279struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 280template <class _NodePtr> 281struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 282 283 284template <class _NodeValueTp, class _VoidPtr> 285struct __make_hash_node_types { 286 typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp; 287 typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr; 288 typedef __hash_node_types<_NodePtr> type; 289}; 290 291template <class _NodePtr> 292class _LIBCPP_TEMPLATE_VIS __hash_iterator 293{ 294 typedef __hash_node_types<_NodePtr> _NodeTypes; 295 typedef _NodePtr __node_pointer; 296 typedef typename _NodeTypes::__next_pointer __next_pointer; 297 298 __next_pointer __node_; 299 300public: 301 typedef forward_iterator_tag iterator_category; 302 typedef typename _NodeTypes::__node_value_type value_type; 303 typedef typename _NodeTypes::difference_type difference_type; 304 typedef value_type& reference; 305 typedef typename _NodeTypes::__node_value_type_pointer pointer; 306 307 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) { 308 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this)); 309 } 310 311#if _LIBCPP_DEBUG_LEVEL >= 2 312 _LIBCPP_INLINE_VISIBILITY 313 __hash_iterator(const __hash_iterator& __i) 314 : __node_(__i.__node_) 315 { 316 __get_db()->__iterator_copy(this, &__i); 317 } 318 319 _LIBCPP_INLINE_VISIBILITY 320 ~__hash_iterator() 321 { 322 __get_db()->__erase_i(this); 323 } 324 325 _LIBCPP_INLINE_VISIBILITY 326 __hash_iterator& operator=(const __hash_iterator& __i) 327 { 328 if (this != &__i) 329 { 330 __get_db()->__iterator_copy(this, &__i); 331 __node_ = __i.__node_; 332 } 333 return *this; 334 } 335#endif // _LIBCPP_DEBUG_LEVEL >= 2 336 337 _LIBCPP_INLINE_VISIBILITY 338 reference operator*() const { 339 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 340 "Attempted to dereference a non-dereferenceable unordered container iterator"); 341 return __node_->__upcast()->__value_; 342 } 343 344 _LIBCPP_INLINE_VISIBILITY 345 pointer operator->() const { 346 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 347 "Attempted to dereference a non-dereferenceable unordered container iterator"); 348 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); 349 } 350 351 _LIBCPP_INLINE_VISIBILITY 352 __hash_iterator& operator++() { 353 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 354 "Attempted to increment non-incrementable unordered container iterator"); 355 __node_ = __node_->__next_; 356 return *this; 357 } 358 359 _LIBCPP_INLINE_VISIBILITY 360 __hash_iterator operator++(int) 361 { 362 __hash_iterator __t(*this); 363 ++(*this); 364 return __t; 365 } 366 367 friend _LIBCPP_INLINE_VISIBILITY 368 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 369 { 370 return __x.__node_ == __y.__node_; 371 } 372 friend _LIBCPP_INLINE_VISIBILITY 373 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 374 {return !(__x == __y);} 375 376private: 377#if _LIBCPP_DEBUG_LEVEL >= 2 378 _LIBCPP_INLINE_VISIBILITY 379 __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT 380 : __node_(__node) 381 { 382 __get_db()->__insert_ic(this, __c); 383 } 384#else 385 _LIBCPP_INLINE_VISIBILITY 386 __hash_iterator(__next_pointer __node) _NOEXCEPT 387 : __node_(__node) 388 {} 389#endif 390 template <class, class, class, class> friend class __hash_table; 391 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator; 392 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator; 393 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 394 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 395}; 396 397template <class _NodePtr> 398class _LIBCPP_TEMPLATE_VIS __hash_const_iterator 399{ 400 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, ""); 401 typedef __hash_node_types<_NodePtr> _NodeTypes; 402 typedef _NodePtr __node_pointer; 403 typedef typename _NodeTypes::__next_pointer __next_pointer; 404 405 __next_pointer __node_; 406 407public: 408 typedef __hash_iterator<_NodePtr> __non_const_iterator; 409 410 typedef forward_iterator_tag iterator_category; 411 typedef typename _NodeTypes::__node_value_type value_type; 412 typedef typename _NodeTypes::difference_type difference_type; 413 typedef const value_type& reference; 414 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 415 416 417 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) { 418 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this)); 419 } 420 421 _LIBCPP_INLINE_VISIBILITY 422 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 423 : __node_(__x.__node_) 424 { 425 _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x)); 426 } 427 428#if _LIBCPP_DEBUG_LEVEL >= 2 429 _LIBCPP_INLINE_VISIBILITY 430 __hash_const_iterator(const __hash_const_iterator& __i) 431 : __node_(__i.__node_) 432 { 433 __get_db()->__iterator_copy(this, &__i); 434 } 435 436 _LIBCPP_INLINE_VISIBILITY 437 ~__hash_const_iterator() 438 { 439 __get_db()->__erase_i(this); 440 } 441 442 _LIBCPP_INLINE_VISIBILITY 443 __hash_const_iterator& operator=(const __hash_const_iterator& __i) 444 { 445 if (this != &__i) 446 { 447 __get_db()->__iterator_copy(this, &__i); 448 __node_ = __i.__node_; 449 } 450 return *this; 451 } 452#endif // _LIBCPP_DEBUG_LEVEL >= 2 453 454 _LIBCPP_INLINE_VISIBILITY 455 reference operator*() const { 456 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 457 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 458 return __node_->__upcast()->__value_; 459 } 460 _LIBCPP_INLINE_VISIBILITY 461 pointer operator->() const { 462 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 463 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 464 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); 465 } 466 467 _LIBCPP_INLINE_VISIBILITY 468 __hash_const_iterator& operator++() { 469 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 470 "Attempted to increment non-incrementable unordered container const_iterator"); 471 __node_ = __node_->__next_; 472 return *this; 473 } 474 475 _LIBCPP_INLINE_VISIBILITY 476 __hash_const_iterator operator++(int) 477 { 478 __hash_const_iterator __t(*this); 479 ++(*this); 480 return __t; 481 } 482 483 friend _LIBCPP_INLINE_VISIBILITY 484 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 485 { 486 return __x.__node_ == __y.__node_; 487 } 488 friend _LIBCPP_INLINE_VISIBILITY 489 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 490 {return !(__x == __y);} 491 492private: 493#if _LIBCPP_DEBUG_LEVEL >= 2 494 _LIBCPP_INLINE_VISIBILITY 495 __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT 496 : __node_(__node) 497 { 498 __get_db()->__insert_ic(this, __c); 499 } 500#else 501 _LIBCPP_INLINE_VISIBILITY 502 __hash_const_iterator(__next_pointer __node) _NOEXCEPT 503 : __node_(__node) 504 {} 505#endif 506 template <class, class, class, class> friend class __hash_table; 507 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 508 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 509 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 510}; 511 512template <class _NodePtr> 513class _LIBCPP_TEMPLATE_VIS __hash_local_iterator 514{ 515 typedef __hash_node_types<_NodePtr> _NodeTypes; 516 typedef _NodePtr __node_pointer; 517 typedef typename _NodeTypes::__next_pointer __next_pointer; 518 519 __next_pointer __node_; 520 size_t __bucket_; 521 size_t __bucket_count_; 522 523public: 524 typedef forward_iterator_tag iterator_category; 525 typedef typename _NodeTypes::__node_value_type value_type; 526 typedef typename _NodeTypes::difference_type difference_type; 527 typedef value_type& reference; 528 typedef typename _NodeTypes::__node_value_type_pointer pointer; 529 530 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) { 531 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this)); 532 } 533 534#if _LIBCPP_DEBUG_LEVEL >= 2 535 _LIBCPP_INLINE_VISIBILITY 536 __hash_local_iterator(const __hash_local_iterator& __i) 537 : __node_(__i.__node_), 538 __bucket_(__i.__bucket_), 539 __bucket_count_(__i.__bucket_count_) 540 { 541 __get_db()->__iterator_copy(this, &__i); 542 } 543 544 _LIBCPP_INLINE_VISIBILITY 545 ~__hash_local_iterator() 546 { 547 __get_db()->__erase_i(this); 548 } 549 550 _LIBCPP_INLINE_VISIBILITY 551 __hash_local_iterator& operator=(const __hash_local_iterator& __i) 552 { 553 if (this != &__i) 554 { 555 __get_db()->__iterator_copy(this, &__i); 556 __node_ = __i.__node_; 557 __bucket_ = __i.__bucket_; 558 __bucket_count_ = __i.__bucket_count_; 559 } 560 return *this; 561 } 562#endif // _LIBCPP_DEBUG_LEVEL >= 2 563 564 _LIBCPP_INLINE_VISIBILITY 565 reference operator*() const { 566 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 567 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 568 return __node_->__upcast()->__value_; 569 } 570 571 _LIBCPP_INLINE_VISIBILITY 572 pointer operator->() const { 573 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 574 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 575 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); 576 } 577 578 _LIBCPP_INLINE_VISIBILITY 579 __hash_local_iterator& operator++() { 580 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 581 "Attempted to increment non-incrementable unordered container local_iterator"); 582 __node_ = __node_->__next_; 583 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_) 584 __node_ = nullptr; 585 return *this; 586 } 587 588 _LIBCPP_INLINE_VISIBILITY 589 __hash_local_iterator operator++(int) 590 { 591 __hash_local_iterator __t(*this); 592 ++(*this); 593 return __t; 594 } 595 596 friend _LIBCPP_INLINE_VISIBILITY 597 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 598 { 599 return __x.__node_ == __y.__node_; 600 } 601 friend _LIBCPP_INLINE_VISIBILITY 602 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 603 {return !(__x == __y);} 604 605private: 606#if _LIBCPP_DEBUG_LEVEL >= 2 607 _LIBCPP_INLINE_VISIBILITY 608 __hash_local_iterator(__next_pointer __node, size_t __bucket, 609 size_t __bucket_count, const void* __c) _NOEXCEPT 610 : __node_(__node), 611 __bucket_(__bucket), 612 __bucket_count_(__bucket_count) 613 { 614 __get_db()->__insert_ic(this, __c); 615 if (__node_ != nullptr) 616 __node_ = __node_->__next_; 617 } 618#else 619 _LIBCPP_INLINE_VISIBILITY 620 __hash_local_iterator(__next_pointer __node, size_t __bucket, 621 size_t __bucket_count) _NOEXCEPT 622 : __node_(__node), 623 __bucket_(__bucket), 624 __bucket_count_(__bucket_count) 625 { 626 if (__node_ != nullptr) 627 __node_ = __node_->__next_; 628 } 629#endif 630 template <class, class, class, class> friend class __hash_table; 631 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator; 632 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator; 633}; 634 635template <class _ConstNodePtr> 636class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator 637{ 638 typedef __hash_node_types<_ConstNodePtr> _NodeTypes; 639 typedef _ConstNodePtr __node_pointer; 640 typedef typename _NodeTypes::__next_pointer __next_pointer; 641 642 __next_pointer __node_; 643 size_t __bucket_; 644 size_t __bucket_count_; 645 646 typedef pointer_traits<__node_pointer> __pointer_traits; 647 typedef typename __pointer_traits::element_type __node; 648 typedef typename remove_const<__node>::type __non_const_node; 649 typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type 650 __non_const_node_pointer; 651public: 652 typedef __hash_local_iterator<__non_const_node_pointer> 653 __non_const_iterator; 654 655 typedef forward_iterator_tag iterator_category; 656 typedef typename _NodeTypes::__node_value_type value_type; 657 typedef typename _NodeTypes::difference_type difference_type; 658 typedef const value_type& reference; 659 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 660 661 662 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) { 663 _LIBCPP_DEBUG_MODE(__get_db()->__insert_i(this)); 664 } 665 666 _LIBCPP_INLINE_VISIBILITY 667 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 668 : __node_(__x.__node_), 669 __bucket_(__x.__bucket_), 670 __bucket_count_(__x.__bucket_count_) 671 { 672 _LIBCPP_DEBUG_MODE(__get_db()->__iterator_copy(this, &__x)); 673 } 674 675#if _LIBCPP_DEBUG_LEVEL >= 2 676 _LIBCPP_INLINE_VISIBILITY 677 __hash_const_local_iterator(const __hash_const_local_iterator& __i) 678 : __node_(__i.__node_), 679 __bucket_(__i.__bucket_), 680 __bucket_count_(__i.__bucket_count_) 681 { 682 __get_db()->__iterator_copy(this, &__i); 683 } 684 685 _LIBCPP_INLINE_VISIBILITY 686 ~__hash_const_local_iterator() 687 { 688 __get_db()->__erase_i(this); 689 } 690 691 _LIBCPP_INLINE_VISIBILITY 692 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 693 { 694 if (this != &__i) 695 { 696 __get_db()->__iterator_copy(this, &__i); 697 __node_ = __i.__node_; 698 __bucket_ = __i.__bucket_; 699 __bucket_count_ = __i.__bucket_count_; 700 } 701 return *this; 702 } 703#endif // _LIBCPP_DEBUG_LEVEL >= 2 704 705 _LIBCPP_INLINE_VISIBILITY 706 reference operator*() const { 707 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 708 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 709 return __node_->__upcast()->__value_; 710 } 711 712 _LIBCPP_INLINE_VISIBILITY 713 pointer operator->() const { 714 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 715 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 716 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_); 717 } 718 719 _LIBCPP_INLINE_VISIBILITY 720 __hash_const_local_iterator& operator++() { 721 _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this), 722 "Attempted to increment non-incrementable unordered container const_local_iterator"); 723 __node_ = __node_->__next_; 724 if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_) 725 __node_ = nullptr; 726 return *this; 727 } 728 729 _LIBCPP_INLINE_VISIBILITY 730 __hash_const_local_iterator operator++(int) 731 { 732 __hash_const_local_iterator __t(*this); 733 ++(*this); 734 return __t; 735 } 736 737 friend _LIBCPP_INLINE_VISIBILITY 738 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 739 { 740 return __x.__node_ == __y.__node_; 741 } 742 friend _LIBCPP_INLINE_VISIBILITY 743 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 744 {return !(__x == __y);} 745 746private: 747#if _LIBCPP_DEBUG_LEVEL >= 2 748 _LIBCPP_INLINE_VISIBILITY 749 __hash_const_local_iterator(__next_pointer __node, size_t __bucket, 750 size_t __bucket_count, const void* __c) _NOEXCEPT 751 : __node_(__node), 752 __bucket_(__bucket), 753 __bucket_count_(__bucket_count) 754 { 755 __get_db()->__insert_ic(this, __c); 756 if (__node_ != nullptr) 757 __node_ = __node_->__next_; 758 } 759#else 760 _LIBCPP_INLINE_VISIBILITY 761 __hash_const_local_iterator(__next_pointer __node, size_t __bucket, 762 size_t __bucket_count) _NOEXCEPT 763 : __node_(__node), 764 __bucket_(__bucket), 765 __bucket_count_(__bucket_count) 766 { 767 if (__node_ != nullptr) 768 __node_ = __node_->__next_; 769 } 770#endif 771 template <class, class, class, class> friend class __hash_table; 772 template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator; 773}; 774 775template <class _Alloc> 776class __bucket_list_deallocator 777{ 778 typedef _Alloc allocator_type; 779 typedef allocator_traits<allocator_type> __alloc_traits; 780 typedef typename __alloc_traits::size_type size_type; 781 782 __compressed_pair<size_type, allocator_type> __data_; 783public: 784 typedef typename __alloc_traits::pointer pointer; 785 786 _LIBCPP_INLINE_VISIBILITY 787 __bucket_list_deallocator() 788 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 789 : __data_(0) {} 790 791 _LIBCPP_INLINE_VISIBILITY 792 __bucket_list_deallocator(const allocator_type& __a, size_type __size) 793 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 794 : __data_(__size, __a) {} 795 796#ifndef _LIBCPP_CXX03_LANG 797 _LIBCPP_INLINE_VISIBILITY 798 __bucket_list_deallocator(__bucket_list_deallocator&& __x) 799 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 800 : __data_(_VSTD::move(__x.__data_)) 801 { 802 __x.size() = 0; 803 } 804#endif 805 806 _LIBCPP_INLINE_VISIBILITY 807 size_type& size() _NOEXCEPT {return __data_.first();} 808 _LIBCPP_INLINE_VISIBILITY 809 size_type size() const _NOEXCEPT {return __data_.first();} 810 811 _LIBCPP_INLINE_VISIBILITY 812 allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 813 _LIBCPP_INLINE_VISIBILITY 814 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 815 816 _LIBCPP_INLINE_VISIBILITY 817 void operator()(pointer __p) _NOEXCEPT 818 { 819 __alloc_traits::deallocate(__alloc(), __p, size()); 820 } 821}; 822 823template <class _Alloc> class __hash_map_node_destructor; 824 825template <class _Alloc> 826class __hash_node_destructor 827{ 828 typedef _Alloc allocator_type; 829 typedef allocator_traits<allocator_type> __alloc_traits; 830 831public: 832 typedef typename __alloc_traits::pointer pointer; 833private: 834 typedef __hash_node_types<pointer> _NodeTypes; 835 836 allocator_type& __na_; 837 838 __hash_node_destructor& operator=(const __hash_node_destructor&); 839 840public: 841 bool __value_constructed; 842 843 _LIBCPP_INLINE_VISIBILITY 844 explicit __hash_node_destructor(allocator_type& __na, 845 bool __constructed = false) _NOEXCEPT 846 : __na_(__na), 847 __value_constructed(__constructed) 848 {} 849 850 _LIBCPP_INLINE_VISIBILITY 851 void operator()(pointer __p) _NOEXCEPT 852 { 853 if (__value_constructed) 854 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 855 if (__p) 856 __alloc_traits::deallocate(__na_, __p, 1); 857 } 858 859 template <class> friend class __hash_map_node_destructor; 860}; 861 862#if _LIBCPP_STD_VER > 14 863template <class _NodeType, class _Alloc> 864struct __generic_container_node_destructor; 865 866template <class _Tp, class _VoidPtr, class _Alloc> 867struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> 868 : __hash_node_destructor<_Alloc> 869{ 870 using __hash_node_destructor<_Alloc>::__hash_node_destructor; 871}; 872#endif 873 874#ifndef _LIBCPP_CXX03_LANG 875template <class _Key, class _Hash, class _Equal, class _Alloc> 876struct __diagnose_hash_table_helper { 877 static constexpr bool __trigger_diagnostics() 878 _LIBCPP_DIAGNOSE_WARNING(__check_hash_requirements<_Key, _Hash>::value 879 && !__invokable<_Hash const&, _Key const&>::value, 880 "the specified hash functor does not provide a const call operator") 881 _LIBCPP_DIAGNOSE_WARNING(is_copy_constructible<_Equal>::value 882 && !__invokable<_Equal const&, _Key const&, _Key const&>::value, 883 "the specified comparator type does not provide a const call operator") 884 { 885 static_assert(__check_hash_requirements<_Key, _Hash>::value, 886 "the specified hash does not meet the Hash requirements"); 887 static_assert(is_copy_constructible<_Equal>::value, 888 "the specified comparator is required to be copy constructible"); 889 return true; 890 } 891}; 892 893template <class _Key, class _Value, class _Hash, class _Equal, class _Alloc> 894struct __diagnose_hash_table_helper< 895 __hash_value_type<_Key, _Value>, 896 __unordered_map_hasher<_Key, __hash_value_type<_Key, _Value>, _Hash>, 897 __unordered_map_equal<_Key, __hash_value_type<_Key, _Value>, _Equal>, 898 _Alloc> 899: __diagnose_hash_table_helper<_Key, _Hash, _Equal, _Alloc> 900{ 901}; 902#endif // _LIBCPP_CXX03_LANG 903 904template <class _Tp, class _Hash, class _Equal, class _Alloc> 905class __hash_table 906{ 907public: 908 typedef _Tp value_type; 909 typedef _Hash hasher; 910 typedef _Equal key_equal; 911 typedef _Alloc allocator_type; 912 913private: 914 typedef allocator_traits<allocator_type> __alloc_traits; 915 typedef typename 916 __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type 917 _NodeTypes; 918public: 919 920 typedef typename _NodeTypes::__node_value_type __node_value_type; 921 typedef typename _NodeTypes::__container_value_type __container_value_type; 922 typedef typename _NodeTypes::key_type key_type; 923 typedef value_type& reference; 924 typedef const value_type& const_reference; 925 typedef typename __alloc_traits::pointer pointer; 926 typedef typename __alloc_traits::const_pointer const_pointer; 927#ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE 928 typedef typename __alloc_traits::size_type size_type; 929#else 930 typedef typename _NodeTypes::size_type size_type; 931#endif 932 typedef typename _NodeTypes::difference_type difference_type; 933public: 934 // Create __node 935 936 typedef typename _NodeTypes::__node_type __node; 937 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 938 typedef allocator_traits<__node_allocator> __node_traits; 939 typedef typename _NodeTypes::__void_pointer __void_pointer; 940 typedef typename _NodeTypes::__node_pointer __node_pointer; 941 typedef typename _NodeTypes::__node_pointer __node_const_pointer; 942 typedef typename _NodeTypes::__node_base_type __first_node; 943 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 944 typedef typename _NodeTypes::__next_pointer __next_pointer; 945 946private: 947 // check for sane allocator pointer rebinding semantics. Rebinding the 948 // allocator for a new pointer type should be exactly the same as rebinding 949 // the pointer using 'pointer_traits'. 950 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), 951 "Allocator does not rebind pointers in a sane manner."); 952 typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type 953 __node_base_allocator; 954 typedef allocator_traits<__node_base_allocator> __node_base_traits; 955 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), 956 "Allocator does not rebind pointers in a sane manner."); 957 958private: 959 960 typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator; 961 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 962 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list; 963 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 964 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 965 966#ifndef _LIBCPP_CXX03_LANG 967 static_assert(__diagnose_hash_table_helper<_Tp, _Hash, _Equal, _Alloc>::__trigger_diagnostics(), ""); 968#endif 969 970 // --- Member data begin --- 971 __bucket_list __bucket_list_; 972 __compressed_pair<__first_node, __node_allocator> __p1_; 973 __compressed_pair<size_type, hasher> __p2_; 974 __compressed_pair<float, key_equal> __p3_; 975 // --- Member data end --- 976 977 _LIBCPP_INLINE_VISIBILITY 978 size_type& size() _NOEXCEPT {return __p2_.first();} 979public: 980 _LIBCPP_INLINE_VISIBILITY 981 size_type size() const _NOEXCEPT {return __p2_.first();} 982 983 _LIBCPP_INLINE_VISIBILITY 984 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 985 _LIBCPP_INLINE_VISIBILITY 986 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 987 988 _LIBCPP_INLINE_VISIBILITY 989 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 990 _LIBCPP_INLINE_VISIBILITY 991 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 992 993 _LIBCPP_INLINE_VISIBILITY 994 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 995 _LIBCPP_INLINE_VISIBILITY 996 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 997 998 _LIBCPP_INLINE_VISIBILITY 999 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 1000 _LIBCPP_INLINE_VISIBILITY 1001 const __node_allocator& __node_alloc() const _NOEXCEPT 1002 {return __p1_.second();} 1003 1004public: 1005 typedef __hash_iterator<__node_pointer> iterator; 1006 typedef __hash_const_iterator<__node_pointer> const_iterator; 1007 typedef __hash_local_iterator<__node_pointer> local_iterator; 1008 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 1009 1010 _LIBCPP_INLINE_VISIBILITY 1011 __hash_table() 1012 _NOEXCEPT_( 1013 is_nothrow_default_constructible<__bucket_list>::value && 1014 is_nothrow_default_constructible<__first_node>::value && 1015 is_nothrow_default_constructible<__node_allocator>::value && 1016 is_nothrow_default_constructible<hasher>::value && 1017 is_nothrow_default_constructible<key_equal>::value); 1018 _LIBCPP_INLINE_VISIBILITY 1019 __hash_table(const hasher& __hf, const key_equal& __eql); 1020 __hash_table(const hasher& __hf, const key_equal& __eql, 1021 const allocator_type& __a); 1022 explicit __hash_table(const allocator_type& __a); 1023 __hash_table(const __hash_table& __u); 1024 __hash_table(const __hash_table& __u, const allocator_type& __a); 1025#ifndef _LIBCPP_CXX03_LANG 1026 __hash_table(__hash_table&& __u) 1027 _NOEXCEPT_( 1028 is_nothrow_move_constructible<__bucket_list>::value && 1029 is_nothrow_move_constructible<__first_node>::value && 1030 is_nothrow_move_constructible<__node_allocator>::value && 1031 is_nothrow_move_constructible<hasher>::value && 1032 is_nothrow_move_constructible<key_equal>::value); 1033 __hash_table(__hash_table&& __u, const allocator_type& __a); 1034#endif // _LIBCPP_CXX03_LANG 1035 ~__hash_table(); 1036 1037 __hash_table& operator=(const __hash_table& __u); 1038#ifndef _LIBCPP_CXX03_LANG 1039 _LIBCPP_INLINE_VISIBILITY 1040 __hash_table& operator=(__hash_table&& __u) 1041 _NOEXCEPT_( 1042 __node_traits::propagate_on_container_move_assignment::value && 1043 is_nothrow_move_assignable<__node_allocator>::value && 1044 is_nothrow_move_assignable<hasher>::value && 1045 is_nothrow_move_assignable<key_equal>::value); 1046#endif 1047 template <class _InputIterator> 1048 void __assign_unique(_InputIterator __first, _InputIterator __last); 1049 template <class _InputIterator> 1050 void __assign_multi(_InputIterator __first, _InputIterator __last); 1051 1052 _LIBCPP_INLINE_VISIBILITY 1053 size_type max_size() const _NOEXCEPT 1054 { 1055 return std::min<size_type>( 1056 __node_traits::max_size(__node_alloc()), 1057 numeric_limits<difference_type >::max() 1058 ); 1059 } 1060 1061private: 1062 _LIBCPP_INLINE_VISIBILITY 1063 __next_pointer __node_insert_multi_prepare(size_t __cp_hash, 1064 value_type& __cp_val); 1065 _LIBCPP_INLINE_VISIBILITY 1066 void __node_insert_multi_perform(__node_pointer __cp, 1067 __next_pointer __pn) _NOEXCEPT; 1068 1069 _LIBCPP_INLINE_VISIBILITY 1070 __next_pointer __node_insert_unique_prepare(size_t __nd_hash, 1071 value_type& __nd_val); 1072 _LIBCPP_INLINE_VISIBILITY 1073 void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; 1074 1075public: 1076 _LIBCPP_INLINE_VISIBILITY 1077 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 1078 _LIBCPP_INLINE_VISIBILITY 1079 iterator __node_insert_multi(__node_pointer __nd); 1080 _LIBCPP_INLINE_VISIBILITY 1081 iterator __node_insert_multi(const_iterator __p, 1082 __node_pointer __nd); 1083 1084#ifndef _LIBCPP_CXX03_LANG 1085 template <class _Key, class ..._Args> 1086 _LIBCPP_INLINE_VISIBILITY 1087 pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args); 1088 1089 template <class... _Args> 1090 _LIBCPP_INLINE_VISIBILITY 1091 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 1092 1093 template <class _Pp> 1094 _LIBCPP_INLINE_VISIBILITY 1095 pair<iterator, bool> __emplace_unique(_Pp&& __x) { 1096 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), 1097 __can_extract_key<_Pp, key_type>()); 1098 } 1099 1100 template <class _First, class _Second> 1101 _LIBCPP_INLINE_VISIBILITY 1102 typename enable_if< 1103 __can_extract_map_key<_First, key_type, __container_value_type>::value, 1104 pair<iterator, bool> 1105 >::type __emplace_unique(_First&& __f, _Second&& __s) { 1106 return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), 1107 _VSTD::forward<_Second>(__s)); 1108 } 1109 1110 template <class... _Args> 1111 _LIBCPP_INLINE_VISIBILITY 1112 pair<iterator, bool> __emplace_unique(_Args&&... __args) { 1113 return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); 1114 } 1115 1116 template <class _Pp> 1117 _LIBCPP_INLINE_VISIBILITY 1118 pair<iterator, bool> 1119 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 1120 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); 1121 } 1122 template <class _Pp> 1123 _LIBCPP_INLINE_VISIBILITY 1124 pair<iterator, bool> 1125 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 1126 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); 1127 } 1128 template <class _Pp> 1129 _LIBCPP_INLINE_VISIBILITY 1130 pair<iterator, bool> 1131 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 1132 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); 1133 } 1134 1135 template <class... _Args> 1136 _LIBCPP_INLINE_VISIBILITY 1137 iterator __emplace_multi(_Args&&... __args); 1138 template <class... _Args> 1139 _LIBCPP_INLINE_VISIBILITY 1140 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 1141 1142 1143 _LIBCPP_INLINE_VISIBILITY 1144 pair<iterator, bool> 1145 __insert_unique(__container_value_type&& __x) { 1146 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x)); 1147 } 1148 1149 template <class _Pp, class = typename enable_if< 1150 !__is_same_uncvref<_Pp, __container_value_type>::value 1151 >::type> 1152 _LIBCPP_INLINE_VISIBILITY 1153 pair<iterator, bool> __insert_unique(_Pp&& __x) { 1154 return __emplace_unique(_VSTD::forward<_Pp>(__x)); 1155 } 1156 1157 template <class _Pp> 1158 _LIBCPP_INLINE_VISIBILITY 1159 iterator __insert_multi(_Pp&& __x) { 1160 return __emplace_multi(_VSTD::forward<_Pp>(__x)); 1161 } 1162 1163 template <class _Pp> 1164 _LIBCPP_INLINE_VISIBILITY 1165 iterator __insert_multi(const_iterator __p, _Pp&& __x) { 1166 return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x)); 1167 } 1168 1169#else // !defined(_LIBCPP_CXX03_LANG) 1170 template <class _Key, class _Args> 1171 _LIBCPP_INLINE_VISIBILITY 1172 pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args); 1173 1174 iterator __insert_multi(const __container_value_type& __x); 1175 iterator __insert_multi(const_iterator __p, const __container_value_type& __x); 1176#endif 1177 1178 _LIBCPP_INLINE_VISIBILITY 1179 pair<iterator, bool> __insert_unique(const __container_value_type& __x) { 1180 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); 1181 } 1182 1183#if _LIBCPP_STD_VER > 14 1184 template <class _NodeHandle, class _InsertReturnType> 1185 _LIBCPP_INLINE_VISIBILITY 1186 _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); 1187 template <class _NodeHandle> 1188 _LIBCPP_INLINE_VISIBILITY 1189 iterator __node_handle_insert_unique(const_iterator __hint, 1190 _NodeHandle&& __nh); 1191 template <class _Table> 1192 _LIBCPP_INLINE_VISIBILITY 1193 void __node_handle_merge_unique(_Table& __source); 1194 1195 template <class _NodeHandle> 1196 _LIBCPP_INLINE_VISIBILITY 1197 iterator __node_handle_insert_multi(_NodeHandle&& __nh); 1198 template <class _NodeHandle> 1199 _LIBCPP_INLINE_VISIBILITY 1200 iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); 1201 template <class _Table> 1202 _LIBCPP_INLINE_VISIBILITY 1203 void __node_handle_merge_multi(_Table& __source); 1204 1205 template <class _NodeHandle> 1206 _LIBCPP_INLINE_VISIBILITY 1207 _NodeHandle __node_handle_extract(key_type const& __key); 1208 template <class _NodeHandle> 1209 _LIBCPP_INLINE_VISIBILITY 1210 _NodeHandle __node_handle_extract(const_iterator __it); 1211#endif 1212 1213 void clear() _NOEXCEPT; 1214 void rehash(size_type __n); 1215 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 1216 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 1217 1218 _LIBCPP_INLINE_VISIBILITY 1219 size_type bucket_count() const _NOEXCEPT 1220 { 1221 return __bucket_list_.get_deleter().size(); 1222 } 1223 1224 _LIBCPP_INLINE_VISIBILITY 1225 iterator begin() _NOEXCEPT; 1226 _LIBCPP_INLINE_VISIBILITY 1227 iterator end() _NOEXCEPT; 1228 _LIBCPP_INLINE_VISIBILITY 1229 const_iterator begin() const _NOEXCEPT; 1230 _LIBCPP_INLINE_VISIBILITY 1231 const_iterator end() const _NOEXCEPT; 1232 1233 template <class _Key> 1234 _LIBCPP_INLINE_VISIBILITY 1235 size_type bucket(const _Key& __k) const 1236 { 1237 _LIBCPP_ASSERT(bucket_count() > 0, 1238 "unordered container::bucket(key) called when bucket_count() == 0"); 1239 return __constrain_hash(hash_function()(__k), bucket_count()); 1240 } 1241 1242 template <class _Key> 1243 iterator find(const _Key& __x); 1244 template <class _Key> 1245 const_iterator find(const _Key& __x) const; 1246 1247 typedef __hash_node_destructor<__node_allocator> _Dp; 1248 typedef unique_ptr<__node, _Dp> __node_holder; 1249 1250 iterator erase(const_iterator __p); 1251 iterator erase(const_iterator __first, const_iterator __last); 1252 template <class _Key> 1253 size_type __erase_unique(const _Key& __k); 1254 template <class _Key> 1255 size_type __erase_multi(const _Key& __k); 1256 __node_holder remove(const_iterator __p) _NOEXCEPT; 1257 1258 template <class _Key> 1259 _LIBCPP_INLINE_VISIBILITY 1260 size_type __count_unique(const _Key& __k) const; 1261 template <class _Key> 1262 size_type __count_multi(const _Key& __k) const; 1263 1264 template <class _Key> 1265 pair<iterator, iterator> 1266 __equal_range_unique(const _Key& __k); 1267 template <class _Key> 1268 pair<const_iterator, const_iterator> 1269 __equal_range_unique(const _Key& __k) const; 1270 1271 template <class _Key> 1272 pair<iterator, iterator> 1273 __equal_range_multi(const _Key& __k); 1274 template <class _Key> 1275 pair<const_iterator, const_iterator> 1276 __equal_range_multi(const _Key& __k) const; 1277 1278 void swap(__hash_table& __u) 1279#if _LIBCPP_STD_VER <= 11 1280 _NOEXCEPT_DEBUG_( 1281 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 1282 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 1283 || __is_nothrow_swappable<__pointer_allocator>::value) 1284 && (!__node_traits::propagate_on_container_swap::value 1285 || __is_nothrow_swappable<__node_allocator>::value) 1286 ); 1287#else 1288 _NOEXCEPT_DEBUG_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 1289#endif 1290 1291 _LIBCPP_INLINE_VISIBILITY 1292 size_type max_bucket_count() const _NOEXCEPT 1293 {return max_size(); } 1294 size_type bucket_size(size_type __n) const; 1295 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1296 { 1297 size_type __bc = bucket_count(); 1298 return __bc != 0 ? (float)size() / __bc : 0.f; 1299 } 1300 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1301 { 1302 _LIBCPP_ASSERT(__mlf > 0, 1303 "unordered container::max_load_factor(lf) called with lf <= 0"); 1304 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1305 } 1306 1307 _LIBCPP_INLINE_VISIBILITY 1308 local_iterator 1309 begin(size_type __n) 1310 { 1311 _LIBCPP_ASSERT(__n < bucket_count(), 1312 "unordered container::begin(n) called with n >= bucket_count()"); 1313#if _LIBCPP_DEBUG_LEVEL >= 2 1314 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1315#else 1316 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1317#endif 1318 } 1319 1320 _LIBCPP_INLINE_VISIBILITY 1321 local_iterator 1322 end(size_type __n) 1323 { 1324 _LIBCPP_ASSERT(__n < bucket_count(), 1325 "unordered container::end(n) called with n >= bucket_count()"); 1326#if _LIBCPP_DEBUG_LEVEL >= 2 1327 return local_iterator(nullptr, __n, bucket_count(), this); 1328#else 1329 return local_iterator(nullptr, __n, bucket_count()); 1330#endif 1331 } 1332 1333 _LIBCPP_INLINE_VISIBILITY 1334 const_local_iterator 1335 cbegin(size_type __n) const 1336 { 1337 _LIBCPP_ASSERT(__n < bucket_count(), 1338 "unordered container::cbegin(n) called with n >= bucket_count()"); 1339#if _LIBCPP_DEBUG_LEVEL >= 2 1340 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1341#else 1342 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1343#endif 1344 } 1345 1346 _LIBCPP_INLINE_VISIBILITY 1347 const_local_iterator 1348 cend(size_type __n) const 1349 { 1350 _LIBCPP_ASSERT(__n < bucket_count(), 1351 "unordered container::cend(n) called with n >= bucket_count()"); 1352#if _LIBCPP_DEBUG_LEVEL >= 2 1353 return const_local_iterator(nullptr, __n, bucket_count(), this); 1354#else 1355 return const_local_iterator(nullptr, __n, bucket_count()); 1356#endif 1357 } 1358 1359#if _LIBCPP_DEBUG_LEVEL >= 2 1360 1361 bool __dereferenceable(const const_iterator* __i) const; 1362 bool __decrementable(const const_iterator* __i) const; 1363 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1364 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1365 1366#endif // _LIBCPP_DEBUG_LEVEL >= 2 1367 1368private: 1369 void __rehash(size_type __n); 1370 1371#ifndef _LIBCPP_CXX03_LANG 1372 template <class ..._Args> 1373 __node_holder __construct_node(_Args&& ...__args); 1374 1375 template <class _First, class ..._Rest> 1376 __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest); 1377#else // _LIBCPP_CXX03_LANG 1378 __node_holder __construct_node(const __container_value_type& __v); 1379 __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v); 1380#endif 1381 1382 1383 _LIBCPP_INLINE_VISIBILITY 1384 void __copy_assign_alloc(const __hash_table& __u) 1385 {__copy_assign_alloc(__u, integral_constant<bool, 1386 __node_traits::propagate_on_container_copy_assignment::value>());} 1387 void __copy_assign_alloc(const __hash_table& __u, true_type); 1388 _LIBCPP_INLINE_VISIBILITY 1389 void __copy_assign_alloc(const __hash_table&, false_type) {} 1390 1391#ifndef _LIBCPP_CXX03_LANG 1392 void __move_assign(__hash_table& __u, false_type); 1393 void __move_assign(__hash_table& __u, true_type) 1394 _NOEXCEPT_( 1395 is_nothrow_move_assignable<__node_allocator>::value && 1396 is_nothrow_move_assignable<hasher>::value && 1397 is_nothrow_move_assignable<key_equal>::value); 1398 _LIBCPP_INLINE_VISIBILITY 1399 void __move_assign_alloc(__hash_table& __u) 1400 _NOEXCEPT_( 1401 !__node_traits::propagate_on_container_move_assignment::value || 1402 (is_nothrow_move_assignable<__pointer_allocator>::value && 1403 is_nothrow_move_assignable<__node_allocator>::value)) 1404 {__move_assign_alloc(__u, integral_constant<bool, 1405 __node_traits::propagate_on_container_move_assignment::value>());} 1406 _LIBCPP_INLINE_VISIBILITY 1407 void __move_assign_alloc(__hash_table& __u, true_type) 1408 _NOEXCEPT_( 1409 is_nothrow_move_assignable<__pointer_allocator>::value && 1410 is_nothrow_move_assignable<__node_allocator>::value) 1411 { 1412 __bucket_list_.get_deleter().__alloc() = 1413 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1414 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1415 } 1416 _LIBCPP_INLINE_VISIBILITY 1417 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1418#endif // _LIBCPP_CXX03_LANG 1419 1420 void __deallocate_node(__next_pointer __np) _NOEXCEPT; 1421 __next_pointer __detach() _NOEXCEPT; 1422 1423 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1424 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1425}; 1426 1427template <class _Tp, class _Hash, class _Equal, class _Alloc> 1428inline 1429__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1430 _NOEXCEPT_( 1431 is_nothrow_default_constructible<__bucket_list>::value && 1432 is_nothrow_default_constructible<__first_node>::value && 1433 is_nothrow_default_constructible<__node_allocator>::value && 1434 is_nothrow_default_constructible<hasher>::value && 1435 is_nothrow_default_constructible<key_equal>::value) 1436 : __p2_(0), 1437 __p3_(1.0f) 1438{ 1439} 1440 1441template <class _Tp, class _Hash, class _Equal, class _Alloc> 1442inline 1443__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1444 const key_equal& __eql) 1445 : __bucket_list_(nullptr, __bucket_list_deleter()), 1446 __p1_(), 1447 __p2_(0, __hf), 1448 __p3_(1.0f, __eql) 1449{ 1450} 1451 1452template <class _Tp, class _Hash, class _Equal, class _Alloc> 1453__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1454 const key_equal& __eql, 1455 const allocator_type& __a) 1456 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1457 __p1_(__second_tag(), __node_allocator(__a)), 1458 __p2_(0, __hf), 1459 __p3_(1.0f, __eql) 1460{ 1461} 1462 1463template <class _Tp, class _Hash, class _Equal, class _Alloc> 1464__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1465 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1466 __p1_(__second_tag(), __node_allocator(__a)), 1467 __p2_(0), 1468 __p3_(1.0f) 1469{ 1470} 1471 1472template <class _Tp, class _Hash, class _Equal, class _Alloc> 1473__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1474 : __bucket_list_(nullptr, 1475 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1476 select_on_container_copy_construction( 1477 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1478 __p1_(__second_tag(), allocator_traits<__node_allocator>:: 1479 select_on_container_copy_construction(__u.__node_alloc())), 1480 __p2_(0, __u.hash_function()), 1481 __p3_(__u.__p3_) 1482{ 1483} 1484 1485template <class _Tp, class _Hash, class _Equal, class _Alloc> 1486__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1487 const allocator_type& __a) 1488 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1489 __p1_(__second_tag(), __node_allocator(__a)), 1490 __p2_(0, __u.hash_function()), 1491 __p3_(__u.__p3_) 1492{ 1493} 1494 1495#ifndef _LIBCPP_CXX03_LANG 1496 1497template <class _Tp, class _Hash, class _Equal, class _Alloc> 1498__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1499 _NOEXCEPT_( 1500 is_nothrow_move_constructible<__bucket_list>::value && 1501 is_nothrow_move_constructible<__first_node>::value && 1502 is_nothrow_move_constructible<__node_allocator>::value && 1503 is_nothrow_move_constructible<hasher>::value && 1504 is_nothrow_move_constructible<key_equal>::value) 1505 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1506 __p1_(_VSTD::move(__u.__p1_)), 1507 __p2_(_VSTD::move(__u.__p2_)), 1508 __p3_(_VSTD::move(__u.__p3_)) 1509{ 1510 if (size() > 0) 1511 { 1512 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 1513 __p1_.first().__ptr(); 1514 __u.__p1_.first().__next_ = nullptr; 1515 __u.size() = 0; 1516 } 1517} 1518 1519template <class _Tp, class _Hash, class _Equal, class _Alloc> 1520__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1521 const allocator_type& __a) 1522 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1523 __p1_(__second_tag(), __node_allocator(__a)), 1524 __p2_(0, _VSTD::move(__u.hash_function())), 1525 __p3_(_VSTD::move(__u.__p3_)) 1526{ 1527 if (__a == allocator_type(__u.__node_alloc())) 1528 { 1529 __bucket_list_.reset(__u.__bucket_list_.release()); 1530 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1531 __u.__bucket_list_.get_deleter().size() = 0; 1532 if (__u.size() > 0) 1533 { 1534 __p1_.first().__next_ = __u.__p1_.first().__next_; 1535 __u.__p1_.first().__next_ = nullptr; 1536 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 1537 __p1_.first().__ptr(); 1538 size() = __u.size(); 1539 __u.size() = 0; 1540 } 1541 } 1542} 1543 1544#endif // _LIBCPP_CXX03_LANG 1545 1546template <class _Tp, class _Hash, class _Equal, class _Alloc> 1547__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1548{ 1549#if defined(_LIBCPP_CXX03_LANG) 1550 static_assert((is_copy_constructible<key_equal>::value), 1551 "Predicate must be copy-constructible."); 1552 static_assert((is_copy_constructible<hasher>::value), 1553 "Hasher must be copy-constructible."); 1554#endif 1555 1556 __deallocate_node(__p1_.first().__next_); 1557#if _LIBCPP_DEBUG_LEVEL >= 2 1558 __get_db()->__erase_c(this); 1559#endif 1560} 1561 1562template <class _Tp, class _Hash, class _Equal, class _Alloc> 1563void 1564__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1565 const __hash_table& __u, true_type) 1566{ 1567 if (__node_alloc() != __u.__node_alloc()) 1568 { 1569 clear(); 1570 __bucket_list_.reset(); 1571 __bucket_list_.get_deleter().size() = 0; 1572 } 1573 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1574 __node_alloc() = __u.__node_alloc(); 1575} 1576 1577template <class _Tp, class _Hash, class _Equal, class _Alloc> 1578__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1579__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1580{ 1581 if (this != &__u) 1582 { 1583 __copy_assign_alloc(__u); 1584 hash_function() = __u.hash_function(); 1585 key_eq() = __u.key_eq(); 1586 max_load_factor() = __u.max_load_factor(); 1587 __assign_multi(__u.begin(), __u.end()); 1588 } 1589 return *this; 1590} 1591 1592template <class _Tp, class _Hash, class _Equal, class _Alloc> 1593void 1594__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) 1595 _NOEXCEPT 1596{ 1597 __node_allocator& __na = __node_alloc(); 1598 while (__np != nullptr) 1599 { 1600 __next_pointer __next = __np->__next_; 1601#if _LIBCPP_DEBUG_LEVEL >= 2 1602 __c_node* __c = __get_db()->__find_c_and_lock(this); 1603 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1604 { 1605 --__p; 1606 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1607 if (__i->__node_ == __np) 1608 { 1609 (*__p)->__c_ = nullptr; 1610 if (--__c->end_ != __p) 1611 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1612 } 1613 } 1614 __get_db()->unlock(); 1615#endif 1616 __node_pointer __real_np = __np->__upcast(); 1617 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_)); 1618 __node_traits::deallocate(__na, __real_np, 1); 1619 __np = __next; 1620 } 1621} 1622 1623template <class _Tp, class _Hash, class _Equal, class _Alloc> 1624typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer 1625__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1626{ 1627 size_type __bc = bucket_count(); 1628 for (size_type __i = 0; __i < __bc; ++__i) 1629 __bucket_list_[__i] = nullptr; 1630 size() = 0; 1631 __next_pointer __cache = __p1_.first().__next_; 1632 __p1_.first().__next_ = nullptr; 1633 return __cache; 1634} 1635 1636#ifndef _LIBCPP_CXX03_LANG 1637 1638template <class _Tp, class _Hash, class _Equal, class _Alloc> 1639void 1640__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1641 __hash_table& __u, true_type) 1642 _NOEXCEPT_( 1643 is_nothrow_move_assignable<__node_allocator>::value && 1644 is_nothrow_move_assignable<hasher>::value && 1645 is_nothrow_move_assignable<key_equal>::value) 1646{ 1647 clear(); 1648 __bucket_list_.reset(__u.__bucket_list_.release()); 1649 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1650 __u.__bucket_list_.get_deleter().size() = 0; 1651 __move_assign_alloc(__u); 1652 size() = __u.size(); 1653 hash_function() = _VSTD::move(__u.hash_function()); 1654 max_load_factor() = __u.max_load_factor(); 1655 key_eq() = _VSTD::move(__u.key_eq()); 1656 __p1_.first().__next_ = __u.__p1_.first().__next_; 1657 if (size() > 0) 1658 { 1659 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 1660 __p1_.first().__ptr(); 1661 __u.__p1_.first().__next_ = nullptr; 1662 __u.size() = 0; 1663 } 1664#if _LIBCPP_DEBUG_LEVEL >= 2 1665 __get_db()->swap(this, &__u); 1666#endif 1667} 1668 1669template <class _Tp, class _Hash, class _Equal, class _Alloc> 1670void 1671__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1672 __hash_table& __u, false_type) 1673{ 1674 if (__node_alloc() == __u.__node_alloc()) 1675 __move_assign(__u, true_type()); 1676 else 1677 { 1678 hash_function() = _VSTD::move(__u.hash_function()); 1679 key_eq() = _VSTD::move(__u.key_eq()); 1680 max_load_factor() = __u.max_load_factor(); 1681 if (bucket_count() != 0) 1682 { 1683 __next_pointer __cache = __detach(); 1684#ifndef _LIBCPP_NO_EXCEPTIONS 1685 try 1686 { 1687#endif // _LIBCPP_NO_EXCEPTIONS 1688 const_iterator __i = __u.begin(); 1689 while (__cache != nullptr && __u.size() != 0) 1690 { 1691 __cache->__upcast()->__value_ = 1692 _VSTD::move(__u.remove(__i++)->__value_); 1693 __next_pointer __next = __cache->__next_; 1694 __node_insert_multi(__cache->__upcast()); 1695 __cache = __next; 1696 } 1697#ifndef _LIBCPP_NO_EXCEPTIONS 1698 } 1699 catch (...) 1700 { 1701 __deallocate_node(__cache); 1702 throw; 1703 } 1704#endif // _LIBCPP_NO_EXCEPTIONS 1705 __deallocate_node(__cache); 1706 } 1707 const_iterator __i = __u.begin(); 1708 while (__u.size() != 0) 1709 { 1710 __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_)); 1711 __node_insert_multi(__h.get()); 1712 __h.release(); 1713 } 1714 } 1715} 1716 1717template <class _Tp, class _Hash, class _Equal, class _Alloc> 1718inline 1719__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1720__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1721 _NOEXCEPT_( 1722 __node_traits::propagate_on_container_move_assignment::value && 1723 is_nothrow_move_assignable<__node_allocator>::value && 1724 is_nothrow_move_assignable<hasher>::value && 1725 is_nothrow_move_assignable<key_equal>::value) 1726{ 1727 __move_assign(__u, integral_constant<bool, 1728 __node_traits::propagate_on_container_move_assignment::value>()); 1729 return *this; 1730} 1731 1732#endif // _LIBCPP_CXX03_LANG 1733 1734template <class _Tp, class _Hash, class _Equal, class _Alloc> 1735template <class _InputIterator> 1736void 1737__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1738 _InputIterator __last) 1739{ 1740 typedef iterator_traits<_InputIterator> _ITraits; 1741 typedef typename _ITraits::value_type _ItValueType; 1742 static_assert((is_same<_ItValueType, __container_value_type>::value), 1743 "__assign_unique may only be called with the containers value type"); 1744 1745 if (bucket_count() != 0) 1746 { 1747 __next_pointer __cache = __detach(); 1748#ifndef _LIBCPP_NO_EXCEPTIONS 1749 try 1750 { 1751#endif // _LIBCPP_NO_EXCEPTIONS 1752 for (; __cache != nullptr && __first != __last; ++__first) 1753 { 1754 __cache->__upcast()->__value_ = *__first; 1755 __next_pointer __next = __cache->__next_; 1756 __node_insert_unique(__cache->__upcast()); 1757 __cache = __next; 1758 } 1759#ifndef _LIBCPP_NO_EXCEPTIONS 1760 } 1761 catch (...) 1762 { 1763 __deallocate_node(__cache); 1764 throw; 1765 } 1766#endif // _LIBCPP_NO_EXCEPTIONS 1767 __deallocate_node(__cache); 1768 } 1769 for (; __first != __last; ++__first) 1770 __insert_unique(*__first); 1771} 1772 1773template <class _Tp, class _Hash, class _Equal, class _Alloc> 1774template <class _InputIterator> 1775void 1776__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1777 _InputIterator __last) 1778{ 1779 typedef iterator_traits<_InputIterator> _ITraits; 1780 typedef typename _ITraits::value_type _ItValueType; 1781 static_assert((is_same<_ItValueType, __container_value_type>::value || 1782 is_same<_ItValueType, __node_value_type>::value), 1783 "__assign_multi may only be called with the containers value type" 1784 " or the nodes value type"); 1785 if (bucket_count() != 0) 1786 { 1787 __next_pointer __cache = __detach(); 1788#ifndef _LIBCPP_NO_EXCEPTIONS 1789 try 1790 { 1791#endif // _LIBCPP_NO_EXCEPTIONS 1792 for (; __cache != nullptr && __first != __last; ++__first) 1793 { 1794 __cache->__upcast()->__value_ = *__first; 1795 __next_pointer __next = __cache->__next_; 1796 __node_insert_multi(__cache->__upcast()); 1797 __cache = __next; 1798 } 1799#ifndef _LIBCPP_NO_EXCEPTIONS 1800 } 1801 catch (...) 1802 { 1803 __deallocate_node(__cache); 1804 throw; 1805 } 1806#endif // _LIBCPP_NO_EXCEPTIONS 1807 __deallocate_node(__cache); 1808 } 1809 for (; __first != __last; ++__first) 1810 __insert_multi(_NodeTypes::__get_value(*__first)); 1811} 1812 1813template <class _Tp, class _Hash, class _Equal, class _Alloc> 1814inline 1815typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1816__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1817{ 1818#if _LIBCPP_DEBUG_LEVEL >= 2 1819 return iterator(__p1_.first().__next_, this); 1820#else 1821 return iterator(__p1_.first().__next_); 1822#endif 1823} 1824 1825template <class _Tp, class _Hash, class _Equal, class _Alloc> 1826inline 1827typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1828__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1829{ 1830#if _LIBCPP_DEBUG_LEVEL >= 2 1831 return iterator(nullptr, this); 1832#else 1833 return iterator(nullptr); 1834#endif 1835} 1836 1837template <class _Tp, class _Hash, class _Equal, class _Alloc> 1838inline 1839typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1840__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1841{ 1842#if _LIBCPP_DEBUG_LEVEL >= 2 1843 return const_iterator(__p1_.first().__next_, this); 1844#else 1845 return const_iterator(__p1_.first().__next_); 1846#endif 1847} 1848 1849template <class _Tp, class _Hash, class _Equal, class _Alloc> 1850inline 1851typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1852__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1853{ 1854#if _LIBCPP_DEBUG_LEVEL >= 2 1855 return const_iterator(nullptr, this); 1856#else 1857 return const_iterator(nullptr); 1858#endif 1859} 1860 1861template <class _Tp, class _Hash, class _Equal, class _Alloc> 1862void 1863__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1864{ 1865 if (size() > 0) 1866 { 1867 __deallocate_node(__p1_.first().__next_); 1868 __p1_.first().__next_ = nullptr; 1869 size_type __bc = bucket_count(); 1870 for (size_type __i = 0; __i < __bc; ++__i) 1871 __bucket_list_[__i] = nullptr; 1872 size() = 0; 1873 } 1874} 1875 1876 1877// Prepare the container for an insertion of the value __value with the hash 1878// __hash. This does a lookup into the container to see if __value is already 1879// present, and performs a rehash if necessary. Returns a pointer to the 1880// existing element if it exists, otherwise nullptr. 1881// 1882// Note that this function does forward exceptions if key_eq() throws, and never 1883// mutates __value or actually inserts into the map. 1884template <class _Tp, class _Hash, class _Equal, class _Alloc> 1885_LIBCPP_INLINE_VISIBILITY 1886typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer 1887__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( 1888 size_t __hash, value_type& __value) 1889{ 1890 size_type __bc = bucket_count(); 1891 1892 if (__bc != 0) 1893 { 1894 size_t __chash = __constrain_hash(__hash, __bc); 1895 __next_pointer __ndptr = __bucket_list_[__chash]; 1896 if (__ndptr != nullptr) 1897 { 1898 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1899 __constrain_hash(__ndptr->__hash(), __bc) == __chash; 1900 __ndptr = __ndptr->__next_) 1901 { 1902 if (key_eq()(__ndptr->__upcast()->__value_, __value)) 1903 return __ndptr; 1904 } 1905 } 1906 } 1907 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1908 { 1909 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1910 size_type(ceil(float(size() + 1) / max_load_factor())))); 1911 } 1912 return nullptr; 1913} 1914 1915// Insert the node __nd into the container by pushing it into the right bucket, 1916// and updating size(). Assumes that __nd->__hash is up-to-date, and that 1917// rehashing has already occurred and that no element with the same key exists 1918// in the map. 1919template <class _Tp, class _Hash, class _Equal, class _Alloc> 1920_LIBCPP_INLINE_VISIBILITY 1921void 1922__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( 1923 __node_pointer __nd) _NOEXCEPT 1924{ 1925 size_type __bc = bucket_count(); 1926 size_t __chash = __constrain_hash(__nd->__hash(), __bc); 1927 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1928 __next_pointer __pn = __bucket_list_[__chash]; 1929 if (__pn == nullptr) 1930 { 1931 __pn =__p1_.first().__ptr(); 1932 __nd->__next_ = __pn->__next_; 1933 __pn->__next_ = __nd->__ptr(); 1934 // fix up __bucket_list_ 1935 __bucket_list_[__chash] = __pn; 1936 if (__nd->__next_ != nullptr) 1937 __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); 1938 } 1939 else 1940 { 1941 __nd->__next_ = __pn->__next_; 1942 __pn->__next_ = __nd->__ptr(); 1943 } 1944 ++size(); 1945} 1946 1947template <class _Tp, class _Hash, class _Equal, class _Alloc> 1948pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1949__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1950{ 1951 __nd->__hash_ = hash_function()(__nd->__value_); 1952 __next_pointer __existing_node = 1953 __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); 1954 1955 // Insert the node, unless it already exists in the container. 1956 bool __inserted = false; 1957 if (__existing_node == nullptr) 1958 { 1959 __node_insert_unique_perform(__nd); 1960 __existing_node = __nd->__ptr(); 1961 __inserted = true; 1962 } 1963#if _LIBCPP_DEBUG_LEVEL >= 2 1964 return pair<iterator, bool>(iterator(__existing_node, this), __inserted); 1965#else 1966 return pair<iterator, bool>(iterator(__existing_node), __inserted); 1967#endif 1968} 1969 1970// Prepare the container for an insertion of the value __cp_val with the hash 1971// __cp_hash. This does a lookup into the container to see if __cp_value is 1972// already present, and performs a rehash if necessary. Returns a pointer to the 1973// last occurance of __cp_val in the map. 1974// 1975// Note that this function does forward exceptions if key_eq() throws, and never 1976// mutates __value or actually inserts into the map. 1977template <class _Tp, class _Hash, class _Equal, class _Alloc> 1978typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer 1979__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( 1980 size_t __cp_hash, value_type& __cp_val) 1981{ 1982 size_type __bc = bucket_count(); 1983 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1984 { 1985 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1986 size_type(ceil(float(size() + 1) / max_load_factor())))); 1987 __bc = bucket_count(); 1988 } 1989 size_t __chash = __constrain_hash(__cp_hash, __bc); 1990 __next_pointer __pn = __bucket_list_[__chash]; 1991 if (__pn != nullptr) 1992 { 1993 for (bool __found = false; __pn->__next_ != nullptr && 1994 __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; 1995 __pn = __pn->__next_) 1996 { 1997 // __found key_eq() action 1998 // false false loop 1999 // true true loop 2000 // false true set __found to true 2001 // true false break 2002 if (__found != (__pn->__next_->__hash() == __cp_hash && 2003 key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) 2004 { 2005 if (!__found) 2006 __found = true; 2007 else 2008 break; 2009 } 2010 } 2011 } 2012 return __pn; 2013} 2014 2015// Insert the node __cp into the container after __pn (which is the last node in 2016// the bucket that compares equal to __cp). Rehashing, and checking for 2017// uniqueness has already been performed (in __node_insert_multi_prepare), so 2018// all we need to do is update the bucket and size(). Assumes that __cp->__hash 2019// is up-to-date. 2020template <class _Tp, class _Hash, class _Equal, class _Alloc> 2021void 2022__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( 2023 __node_pointer __cp, __next_pointer __pn) _NOEXCEPT 2024{ 2025 size_type __bc = bucket_count(); 2026 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 2027 if (__pn == nullptr) 2028 { 2029 __pn =__p1_.first().__ptr(); 2030 __cp->__next_ = __pn->__next_; 2031 __pn->__next_ = __cp->__ptr(); 2032 // fix up __bucket_list_ 2033 __bucket_list_[__chash] = __pn; 2034 if (__cp->__next_ != nullptr) 2035 __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] 2036 = __cp->__ptr(); 2037 } 2038 else 2039 { 2040 __cp->__next_ = __pn->__next_; 2041 __pn->__next_ = __cp->__ptr(); 2042 if (__cp->__next_ != nullptr) 2043 { 2044 size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc); 2045 if (__nhash != __chash) 2046 __bucket_list_[__nhash] = __cp->__ptr(); 2047 } 2048 } 2049 ++size(); 2050} 2051 2052 2053template <class _Tp, class _Hash, class _Equal, class _Alloc> 2054typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2055__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 2056{ 2057 __cp->__hash_ = hash_function()(__cp->__value_); 2058 __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_); 2059 __node_insert_multi_perform(__cp, __pn); 2060 2061#if _LIBCPP_DEBUG_LEVEL >= 2 2062 return iterator(__cp->__ptr(), this); 2063#else 2064 return iterator(__cp->__ptr()); 2065#endif 2066} 2067 2068template <class _Tp, class _Hash, class _Equal, class _Alloc> 2069typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2070__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 2071 const_iterator __p, __node_pointer __cp) 2072{ 2073#if _LIBCPP_DEBUG_LEVEL >= 2 2074 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2075 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 2076 " referring to this unordered container"); 2077#endif 2078 if (__p != end() && key_eq()(*__p, __cp->__value_)) 2079 { 2080 __next_pointer __np = __p.__node_; 2081 __cp->__hash_ = __np->__hash(); 2082 size_type __bc = bucket_count(); 2083 if (size()+1 > __bc * max_load_factor() || __bc == 0) 2084 { 2085 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 2086 size_type(ceil(float(size() + 1) / max_load_factor())))); 2087 __bc = bucket_count(); 2088 } 2089 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 2090 __next_pointer __pp = __bucket_list_[__chash]; 2091 while (__pp->__next_ != __np) 2092 __pp = __pp->__next_; 2093 __cp->__next_ = __np; 2094 __pp->__next_ = static_cast<__next_pointer>(__cp); 2095 ++size(); 2096#if _LIBCPP_DEBUG_LEVEL >= 2 2097 return iterator(static_cast<__next_pointer>(__cp), this); 2098#else 2099 return iterator(static_cast<__next_pointer>(__cp)); 2100#endif 2101 } 2102 return __node_insert_multi(__cp); 2103} 2104 2105 2106 2107#ifndef _LIBCPP_CXX03_LANG 2108template <class _Tp, class _Hash, class _Equal, class _Alloc> 2109template <class _Key, class ..._Args> 2110pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 2111__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) 2112#else 2113template <class _Tp, class _Hash, class _Equal, class _Alloc> 2114template <class _Key, class _Args> 2115pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 2116__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args) 2117#endif 2118{ 2119 2120 size_t __hash = hash_function()(__k); 2121 size_type __bc = bucket_count(); 2122 bool __inserted = false; 2123 __next_pointer __nd; 2124 size_t __chash; 2125 if (__bc != 0) 2126 { 2127 __chash = __constrain_hash(__hash, __bc); 2128 __nd = __bucket_list_[__chash]; 2129 if (__nd != nullptr) 2130 { 2131 for (__nd = __nd->__next_; __nd != nullptr && 2132 (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash); 2133 __nd = __nd->__next_) 2134 { 2135 if (key_eq()(__nd->__upcast()->__value_, __k)) 2136 goto __done; 2137 } 2138 } 2139 } 2140 { 2141#ifndef _LIBCPP_CXX03_LANG 2142 __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...); 2143#else 2144 __node_holder __h = __construct_node_hash(__hash, __args); 2145#endif 2146 if (size()+1 > __bc * max_load_factor() || __bc == 0) 2147 { 2148 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 2149 size_type(ceil(float(size() + 1) / max_load_factor())))); 2150 __bc = bucket_count(); 2151 __chash = __constrain_hash(__hash, __bc); 2152 } 2153 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 2154 __next_pointer __pn = __bucket_list_[__chash]; 2155 if (__pn == nullptr) 2156 { 2157 __pn = __p1_.first().__ptr(); 2158 __h->__next_ = __pn->__next_; 2159 __pn->__next_ = __h.get()->__ptr(); 2160 // fix up __bucket_list_ 2161 __bucket_list_[__chash] = __pn; 2162 if (__h->__next_ != nullptr) 2163 __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)] 2164 = __h.get()->__ptr(); 2165 } 2166 else 2167 { 2168 __h->__next_ = __pn->__next_; 2169 __pn->__next_ = static_cast<__next_pointer>(__h.get()); 2170 } 2171 __nd = static_cast<__next_pointer>(__h.release()); 2172 // increment size 2173 ++size(); 2174 __inserted = true; 2175 } 2176__done: 2177#if _LIBCPP_DEBUG_LEVEL >= 2 2178 return pair<iterator, bool>(iterator(__nd, this), __inserted); 2179#else 2180 return pair<iterator, bool>(iterator(__nd), __inserted); 2181#endif 2182} 2183 2184#ifndef _LIBCPP_CXX03_LANG 2185 2186template <class _Tp, class _Hash, class _Equal, class _Alloc> 2187template <class... _Args> 2188pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 2189__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) 2190{ 2191 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2192 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 2193 if (__r.second) 2194 __h.release(); 2195 return __r; 2196} 2197 2198template <class _Tp, class _Hash, class _Equal, class _Alloc> 2199template <class... _Args> 2200typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2201__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 2202{ 2203 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2204 iterator __r = __node_insert_multi(__h.get()); 2205 __h.release(); 2206 return __r; 2207} 2208 2209template <class _Tp, class _Hash, class _Equal, class _Alloc> 2210template <class... _Args> 2211typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2212__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 2213 const_iterator __p, _Args&&... __args) 2214{ 2215#if _LIBCPP_DEBUG_LEVEL >= 2 2216 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2217 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 2218 " referring to this unordered container"); 2219#endif 2220 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2221 iterator __r = __node_insert_multi(__p, __h.get()); 2222 __h.release(); 2223 return __r; 2224} 2225 2226#else // _LIBCPP_CXX03_LANG 2227 2228template <class _Tp, class _Hash, class _Equal, class _Alloc> 2229typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2230__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const __container_value_type& __x) 2231{ 2232 __node_holder __h = __construct_node(__x); 2233 iterator __r = __node_insert_multi(__h.get()); 2234 __h.release(); 2235 return __r; 2236} 2237 2238template <class _Tp, class _Hash, class _Equal, class _Alloc> 2239typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2240__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 2241 const __container_value_type& __x) 2242{ 2243#if _LIBCPP_DEBUG_LEVEL >= 2 2244 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2245 "unordered container::insert(const_iterator, lvalue) called with an iterator not" 2246 " referring to this unordered container"); 2247#endif 2248 __node_holder __h = __construct_node(__x); 2249 iterator __r = __node_insert_multi(__p, __h.get()); 2250 __h.release(); 2251 return __r; 2252} 2253 2254#endif // _LIBCPP_CXX03_LANG 2255 2256#if _LIBCPP_STD_VER > 14 2257template <class _Tp, class _Hash, class _Equal, class _Alloc> 2258template <class _NodeHandle, class _InsertReturnType> 2259_LIBCPP_INLINE_VISIBILITY 2260_InsertReturnType 2261__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( 2262 _NodeHandle&& __nh) 2263{ 2264 if (__nh.empty()) 2265 return _InsertReturnType{end(), false, _NodeHandle()}; 2266 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); 2267 if (__result.second) 2268 __nh.__release(); 2269 return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; 2270} 2271 2272template <class _Tp, class _Hash, class _Equal, class _Alloc> 2273template <class _NodeHandle> 2274_LIBCPP_INLINE_VISIBILITY 2275typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2276__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( 2277 const_iterator, _NodeHandle&& __nh) 2278{ 2279 if (__nh.empty()) 2280 return end(); 2281 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); 2282 if (__result.second) 2283 __nh.__release(); 2284 return __result.first; 2285} 2286 2287template <class _Tp, class _Hash, class _Equal, class _Alloc> 2288template <class _NodeHandle> 2289_LIBCPP_INLINE_VISIBILITY 2290_NodeHandle 2291__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( 2292 key_type const& __key) 2293{ 2294 iterator __i = find(__key); 2295 if (__i == end()) 2296 return _NodeHandle(); 2297 return __node_handle_extract<_NodeHandle>(__i); 2298} 2299 2300template <class _Tp, class _Hash, class _Equal, class _Alloc> 2301template <class _NodeHandle> 2302_LIBCPP_INLINE_VISIBILITY 2303_NodeHandle 2304__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( 2305 const_iterator __p) 2306{ 2307 allocator_type __alloc(__node_alloc()); 2308 return _NodeHandle(remove(__p).release(), __alloc); 2309} 2310 2311template <class _Tp, class _Hash, class _Equal, class _Alloc> 2312template <class _Table> 2313_LIBCPP_INLINE_VISIBILITY 2314void 2315__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( 2316 _Table& __source) 2317{ 2318 static_assert(is_same<__node, typename _Table::__node>::value, ""); 2319 2320 for (typename _Table::iterator __it = __source.begin(); 2321 __it != __source.end();) 2322 { 2323 __node_pointer __src_ptr = __it.__node_->__upcast(); 2324 size_t __hash = hash_function()(__src_ptr->__value_); 2325 __next_pointer __existing_node = 2326 __node_insert_unique_prepare(__hash, __src_ptr->__value_); 2327 auto __prev_iter = __it++; 2328 if (__existing_node == nullptr) 2329 { 2330 (void)__source.remove(__prev_iter).release(); 2331 __src_ptr->__hash_ = __hash; 2332 __node_insert_unique_perform(__src_ptr); 2333 } 2334 } 2335} 2336 2337template <class _Tp, class _Hash, class _Equal, class _Alloc> 2338template <class _NodeHandle> 2339_LIBCPP_INLINE_VISIBILITY 2340typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2341__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( 2342 _NodeHandle&& __nh) 2343{ 2344 if (__nh.empty()) 2345 return end(); 2346 iterator __result = __node_insert_multi(__nh.__ptr_); 2347 __nh.__release(); 2348 return __result; 2349} 2350 2351template <class _Tp, class _Hash, class _Equal, class _Alloc> 2352template <class _NodeHandle> 2353_LIBCPP_INLINE_VISIBILITY 2354typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2355__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( 2356 const_iterator __hint, _NodeHandle&& __nh) 2357{ 2358 if (__nh.empty()) 2359 return end(); 2360 iterator __result = __node_insert_multi(__hint, __nh.__ptr_); 2361 __nh.__release(); 2362 return __result; 2363} 2364 2365template <class _Tp, class _Hash, class _Equal, class _Alloc> 2366template <class _Table> 2367_LIBCPP_INLINE_VISIBILITY 2368void 2369__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( 2370 _Table& __source) 2371{ 2372 static_assert(is_same<typename _Table::__node, __node>::value, ""); 2373 2374 for (typename _Table::iterator __it = __source.begin(); 2375 __it != __source.end();) 2376 { 2377 __node_pointer __src_ptr = __it.__node_->__upcast(); 2378 size_t __src_hash = hash_function()(__src_ptr->__value_); 2379 __next_pointer __pn = 2380 __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); 2381 (void)__source.remove(__it++).release(); 2382 __src_ptr->__hash_ = __src_hash; 2383 __node_insert_multi_perform(__src_ptr, __pn); 2384 } 2385} 2386#endif // _LIBCPP_STD_VER > 14 2387 2388template <class _Tp, class _Hash, class _Equal, class _Alloc> 2389void 2390__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 2391{ 2392 if (__n == 1) 2393 __n = 2; 2394 else if (__n & (__n - 1)) 2395 __n = __next_prime(__n); 2396 size_type __bc = bucket_count(); 2397 if (__n > __bc) 2398 __rehash(__n); 2399 else if (__n < __bc) 2400 { 2401 __n = _VSTD::max<size_type> 2402 ( 2403 __n, 2404 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 2405 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 2406 ); 2407 if (__n < __bc) 2408 __rehash(__n); 2409 } 2410} 2411 2412template <class _Tp, class _Hash, class _Equal, class _Alloc> 2413void 2414__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 2415{ 2416#if _LIBCPP_DEBUG_LEVEL >= 2 2417 __get_db()->__invalidate_all(this); 2418#endif // _LIBCPP_DEBUG_LEVEL >= 2 2419 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 2420 __bucket_list_.reset(__nbc > 0 ? 2421 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 2422 __bucket_list_.get_deleter().size() = __nbc; 2423 if (__nbc > 0) 2424 { 2425 for (size_type __i = 0; __i < __nbc; ++__i) 2426 __bucket_list_[__i] = nullptr; 2427 __next_pointer __pp = __p1_.first().__ptr(); 2428 __next_pointer __cp = __pp->__next_; 2429 if (__cp != nullptr) 2430 { 2431 size_type __chash = __constrain_hash(__cp->__hash(), __nbc); 2432 __bucket_list_[__chash] = __pp; 2433 size_type __phash = __chash; 2434 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 2435 __cp = __pp->__next_) 2436 { 2437 __chash = __constrain_hash(__cp->__hash(), __nbc); 2438 if (__chash == __phash) 2439 __pp = __cp; 2440 else 2441 { 2442 if (__bucket_list_[__chash] == nullptr) 2443 { 2444 __bucket_list_[__chash] = __pp; 2445 __pp = __cp; 2446 __phash = __chash; 2447 } 2448 else 2449 { 2450 __next_pointer __np = __cp; 2451 for (; __np->__next_ != nullptr && 2452 key_eq()(__cp->__upcast()->__value_, 2453 __np->__next_->__upcast()->__value_); 2454 __np = __np->__next_) 2455 ; 2456 __pp->__next_ = __np->__next_; 2457 __np->__next_ = __bucket_list_[__chash]->__next_; 2458 __bucket_list_[__chash]->__next_ = __cp; 2459 2460 } 2461 } 2462 } 2463 } 2464 } 2465} 2466 2467template <class _Tp, class _Hash, class _Equal, class _Alloc> 2468template <class _Key> 2469typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2470__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2471{ 2472 size_t __hash = hash_function()(__k); 2473 size_type __bc = bucket_count(); 2474 if (__bc != 0) 2475 { 2476 size_t __chash = __constrain_hash(__hash, __bc); 2477 __next_pointer __nd = __bucket_list_[__chash]; 2478 if (__nd != nullptr) 2479 { 2480 for (__nd = __nd->__next_; __nd != nullptr && 2481 (__nd->__hash() == __hash 2482 || __constrain_hash(__nd->__hash(), __bc) == __chash); 2483 __nd = __nd->__next_) 2484 { 2485 if ((__nd->__hash() == __hash) 2486 && key_eq()(__nd->__upcast()->__value_, __k)) 2487#if _LIBCPP_DEBUG_LEVEL >= 2 2488 return iterator(__nd, this); 2489#else 2490 return iterator(__nd); 2491#endif 2492 } 2493 } 2494 } 2495 return end(); 2496} 2497 2498template <class _Tp, class _Hash, class _Equal, class _Alloc> 2499template <class _Key> 2500typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2501__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2502{ 2503 size_t __hash = hash_function()(__k); 2504 size_type __bc = bucket_count(); 2505 if (__bc != 0) 2506 { 2507 size_t __chash = __constrain_hash(__hash, __bc); 2508 __next_pointer __nd = __bucket_list_[__chash]; 2509 if (__nd != nullptr) 2510 { 2511 for (__nd = __nd->__next_; __nd != nullptr && 2512 (__hash == __nd->__hash() 2513 || __constrain_hash(__nd->__hash(), __bc) == __chash); 2514 __nd = __nd->__next_) 2515 { 2516 if ((__nd->__hash() == __hash) 2517 && key_eq()(__nd->__upcast()->__value_, __k)) 2518#if _LIBCPP_DEBUG_LEVEL >= 2 2519 return const_iterator(__nd, this); 2520#else 2521 return const_iterator(__nd); 2522#endif 2523 } 2524 } 2525 2526 } 2527 return end(); 2528} 2529 2530#ifndef _LIBCPP_CXX03_LANG 2531 2532template <class _Tp, class _Hash, class _Equal, class _Alloc> 2533template <class ..._Args> 2534typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2535__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2536{ 2537 static_assert(!__is_hash_value_type<_Args...>::value, 2538 "Construct cannot be called with a hash value type"); 2539 __node_allocator& __na = __node_alloc(); 2540 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2541 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); 2542 __h.get_deleter().__value_constructed = true; 2543 __h->__hash_ = hash_function()(__h->__value_); 2544 __h->__next_ = nullptr; 2545 return __h; 2546} 2547 2548template <class _Tp, class _Hash, class _Equal, class _Alloc> 2549template <class _First, class ..._Rest> 2550typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2551__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash( 2552 size_t __hash, _First&& __f, _Rest&& ...__rest) 2553{ 2554 static_assert(!__is_hash_value_type<_First, _Rest...>::value, 2555 "Construct cannot be called with a hash value type"); 2556 __node_allocator& __na = __node_alloc(); 2557 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2558 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), 2559 _VSTD::forward<_First>(__f), 2560 _VSTD::forward<_Rest>(__rest)...); 2561 __h.get_deleter().__value_constructed = true; 2562 __h->__hash_ = __hash; 2563 __h->__next_ = nullptr; 2564 return __h; 2565} 2566 2567#else // _LIBCPP_CXX03_LANG 2568 2569template <class _Tp, class _Hash, class _Equal, class _Alloc> 2570typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2571__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v) 2572{ 2573 __node_allocator& __na = __node_alloc(); 2574 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2575 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); 2576 __h.get_deleter().__value_constructed = true; 2577 __h->__hash_ = hash_function()(__h->__value_); 2578 __h->__next_ = nullptr; 2579 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2580} 2581 2582template <class _Tp, class _Hash, class _Equal, class _Alloc> 2583typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2584__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, 2585 const __container_value_type& __v) 2586{ 2587 __node_allocator& __na = __node_alloc(); 2588 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2589 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); 2590 __h.get_deleter().__value_constructed = true; 2591 __h->__hash_ = __hash; 2592 __h->__next_ = nullptr; 2593 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2594} 2595 2596#endif // _LIBCPP_CXX03_LANG 2597 2598template <class _Tp, class _Hash, class _Equal, class _Alloc> 2599typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2600__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2601{ 2602 __next_pointer __np = __p.__node_; 2603#if _LIBCPP_DEBUG_LEVEL >= 2 2604 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2605 "unordered container erase(iterator) called with an iterator not" 2606 " referring to this container"); 2607 _LIBCPP_ASSERT(__p != end(), 2608 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2609 iterator __r(__np, this); 2610#else 2611 iterator __r(__np); 2612#endif 2613 ++__r; 2614 remove(__p); 2615 return __r; 2616} 2617 2618template <class _Tp, class _Hash, class _Equal, class _Alloc> 2619typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2620__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2621 const_iterator __last) 2622{ 2623#if _LIBCPP_DEBUG_LEVEL >= 2 2624 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2625 "unodered container::erase(iterator, iterator) called with an iterator not" 2626 " referring to this unodered container"); 2627 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2628 "unodered container::erase(iterator, iterator) called with an iterator not" 2629 " referring to this unodered container"); 2630#endif 2631 for (const_iterator __p = __first; __first != __last; __p = __first) 2632 { 2633 ++__first; 2634 erase(__p); 2635 } 2636 __next_pointer __np = __last.__node_; 2637#if _LIBCPP_DEBUG_LEVEL >= 2 2638 return iterator (__np, this); 2639#else 2640 return iterator (__np); 2641#endif 2642} 2643 2644template <class _Tp, class _Hash, class _Equal, class _Alloc> 2645template <class _Key> 2646typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2647__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2648{ 2649 iterator __i = find(__k); 2650 if (__i == end()) 2651 return 0; 2652 erase(__i); 2653 return 1; 2654} 2655 2656template <class _Tp, class _Hash, class _Equal, class _Alloc> 2657template <class _Key> 2658typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2659__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2660{ 2661 size_type __r = 0; 2662 iterator __i = find(__k); 2663 if (__i != end()) 2664 { 2665 iterator __e = end(); 2666 do 2667 { 2668 erase(__i++); 2669 ++__r; 2670 } while (__i != __e && key_eq()(*__i, __k)); 2671 } 2672 return __r; 2673} 2674 2675template <class _Tp, class _Hash, class _Equal, class _Alloc> 2676typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2677__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2678{ 2679 // current node 2680 __next_pointer __cn = __p.__node_; 2681 size_type __bc = bucket_count(); 2682 size_t __chash = __constrain_hash(__cn->__hash(), __bc); 2683 // find previous node 2684 __next_pointer __pn = __bucket_list_[__chash]; 2685 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2686 ; 2687 // Fix up __bucket_list_ 2688 // if __pn is not in same bucket (before begin is not in same bucket) && 2689 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2690 if (__pn == __p1_.first().__ptr() 2691 || __constrain_hash(__pn->__hash(), __bc) != __chash) 2692 { 2693 if (__cn->__next_ == nullptr 2694 || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash) 2695 __bucket_list_[__chash] = nullptr; 2696 } 2697 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2698 if (__cn->__next_ != nullptr) 2699 { 2700 size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc); 2701 if (__nhash != __chash) 2702 __bucket_list_[__nhash] = __pn; 2703 } 2704 // remove __cn 2705 __pn->__next_ = __cn->__next_; 2706 __cn->__next_ = nullptr; 2707 --size(); 2708#if _LIBCPP_DEBUG_LEVEL >= 2 2709 __c_node* __c = __get_db()->__find_c_and_lock(this); 2710 for (__i_node** __dp = __c->end_; __dp != __c->beg_; ) 2711 { 2712 --__dp; 2713 iterator* __i = static_cast<iterator*>((*__dp)->__i_); 2714 if (__i->__node_ == __cn) 2715 { 2716 (*__dp)->__c_ = nullptr; 2717 if (--__c->end_ != __dp) 2718 memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*)); 2719 } 2720 } 2721 __get_db()->unlock(); 2722#endif 2723 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true)); 2724} 2725 2726template <class _Tp, class _Hash, class _Equal, class _Alloc> 2727template <class _Key> 2728inline 2729typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2730__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2731{ 2732 return static_cast<size_type>(find(__k) != end()); 2733} 2734 2735template <class _Tp, class _Hash, class _Equal, class _Alloc> 2736template <class _Key> 2737typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2738__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2739{ 2740 size_type __r = 0; 2741 const_iterator __i = find(__k); 2742 if (__i != end()) 2743 { 2744 const_iterator __e = end(); 2745 do 2746 { 2747 ++__i; 2748 ++__r; 2749 } while (__i != __e && key_eq()(*__i, __k)); 2750 } 2751 return __r; 2752} 2753 2754template <class _Tp, class _Hash, class _Equal, class _Alloc> 2755template <class _Key> 2756pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2757 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2758__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2759 const _Key& __k) 2760{ 2761 iterator __i = find(__k); 2762 iterator __j = __i; 2763 if (__i != end()) 2764 ++__j; 2765 return pair<iterator, iterator>(__i, __j); 2766} 2767 2768template <class _Tp, class _Hash, class _Equal, class _Alloc> 2769template <class _Key> 2770pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2771 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2772__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2773 const _Key& __k) const 2774{ 2775 const_iterator __i = find(__k); 2776 const_iterator __j = __i; 2777 if (__i != end()) 2778 ++__j; 2779 return pair<const_iterator, const_iterator>(__i, __j); 2780} 2781 2782template <class _Tp, class _Hash, class _Equal, class _Alloc> 2783template <class _Key> 2784pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2785 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2786__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2787 const _Key& __k) 2788{ 2789 iterator __i = find(__k); 2790 iterator __j = __i; 2791 if (__i != end()) 2792 { 2793 iterator __e = end(); 2794 do 2795 { 2796 ++__j; 2797 } while (__j != __e && key_eq()(*__j, __k)); 2798 } 2799 return pair<iterator, iterator>(__i, __j); 2800} 2801 2802template <class _Tp, class _Hash, class _Equal, class _Alloc> 2803template <class _Key> 2804pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2805 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2806__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2807 const _Key& __k) const 2808{ 2809 const_iterator __i = find(__k); 2810 const_iterator __j = __i; 2811 if (__i != end()) 2812 { 2813 const_iterator __e = end(); 2814 do 2815 { 2816 ++__j; 2817 } while (__j != __e && key_eq()(*__j, __k)); 2818 } 2819 return pair<const_iterator, const_iterator>(__i, __j); 2820} 2821 2822template <class _Tp, class _Hash, class _Equal, class _Alloc> 2823void 2824__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2825#if _LIBCPP_STD_VER <= 11 2826 _NOEXCEPT_DEBUG_( 2827 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2828 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2829 || __is_nothrow_swappable<__pointer_allocator>::value) 2830 && (!__node_traits::propagate_on_container_swap::value 2831 || __is_nothrow_swappable<__node_allocator>::value) 2832 ) 2833#else 2834 _NOEXCEPT_DEBUG_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2835#endif 2836{ 2837 _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value || 2838 this->__node_alloc() == __u.__node_alloc(), 2839 "list::swap: Either propagate_on_container_swap must be true" 2840 " or the allocators must compare equal"); 2841 { 2842 __node_pointer_pointer __npp = __bucket_list_.release(); 2843 __bucket_list_.reset(__u.__bucket_list_.release()); 2844 __u.__bucket_list_.reset(__npp); 2845 } 2846 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2847 __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2848 __u.__bucket_list_.get_deleter().__alloc()); 2849 __swap_allocator(__node_alloc(), __u.__node_alloc()); 2850 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2851 __p2_.swap(__u.__p2_); 2852 __p3_.swap(__u.__p3_); 2853 if (size() > 0) 2854 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 2855 __p1_.first().__ptr(); 2856 if (__u.size() > 0) 2857 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] = 2858 __u.__p1_.first().__ptr(); 2859#if _LIBCPP_DEBUG_LEVEL >= 2 2860 __get_db()->swap(this, &__u); 2861#endif 2862} 2863 2864template <class _Tp, class _Hash, class _Equal, class _Alloc> 2865typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2866__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2867{ 2868 _LIBCPP_ASSERT(__n < bucket_count(), 2869 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2870 __next_pointer __np = __bucket_list_[__n]; 2871 size_type __bc = bucket_count(); 2872 size_type __r = 0; 2873 if (__np != nullptr) 2874 { 2875 for (__np = __np->__next_; __np != nullptr && 2876 __constrain_hash(__np->__hash(), __bc) == __n; 2877 __np = __np->__next_, ++__r) 2878 ; 2879 } 2880 return __r; 2881} 2882 2883template <class _Tp, class _Hash, class _Equal, class _Alloc> 2884inline _LIBCPP_INLINE_VISIBILITY 2885void 2886swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2887 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2888 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2889{ 2890 __x.swap(__y); 2891} 2892 2893#if _LIBCPP_DEBUG_LEVEL >= 2 2894 2895template <class _Tp, class _Hash, class _Equal, class _Alloc> 2896bool 2897__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2898{ 2899 return __i->__node_ != nullptr; 2900} 2901 2902template <class _Tp, class _Hash, class _Equal, class _Alloc> 2903bool 2904__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2905{ 2906 return false; 2907} 2908 2909template <class _Tp, class _Hash, class _Equal, class _Alloc> 2910bool 2911__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2912{ 2913 return false; 2914} 2915 2916template <class _Tp, class _Hash, class _Equal, class _Alloc> 2917bool 2918__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2919{ 2920 return false; 2921} 2922 2923#endif // _LIBCPP_DEBUG_LEVEL >= 2 2924 2925_LIBCPP_END_NAMESPACE_STD 2926 2927_LIBCPP_POP_MACROS 2928 2929#endif // _LIBCPP__HASH_TABLE 2930