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