libcxx/include/__hash_table

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