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