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