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