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