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