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