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 <__bits> // __libcpp_clz
  17 #include <__config>
  18 #include <__debug>
  19 #include <__functional/hash.h>
  20 #include <__iterator/iterator_traits.h>
  21 #include <__utility/swap.h>
  22 #include <cmath>
  23 #include <initializer_list>
  24 #include <memory>
  25 #include <type_traits>
  26
  27 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  28 #  pragma GCC system_header
  29 #endif
  30
  31 _LIBCPP_PUSH_MACROS
  32 #include <__undef_macros>
  33
  34
  35 _LIBCPP_BEGIN_NAMESPACE_STD
  36
  37 template <class _Key, class _Tp>
  38 struct __hash_value_type;
  39
  40 template <class _Tp>
  41 struct __is_hash_value_type_imp : false_type {};
  42
  43 template <class _Key, class _Value>
  44 struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
  45
  46 template <class ..._Args>
  47 struct __is_hash_value_type : false_type {};
  48
  49 template <class _One>
  50 struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__uncvref_t<_One> > {};
  51
  52 _LIBCPP_FUNC_VIS
  53 size_t __next_prime(size_t __n);
  54
  55 template <class _NodePtr>
  56 struct __hash_node_base
  57 {
  58     typedef typename pointer_traits<_NodePtr>::element_type __node_type;
  59     typedef __hash_node_base __first_node;
  60     typedef typename __rebind_pointer<_NodePtr, __first_node>::type __node_base_pointer;
  61     typedef _NodePtr __node_pointer;
  62
  63 #if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
  64   typedef __node_base_pointer __next_pointer;
  65 #else
  66   typedef typename conditional<
  67       is_pointer<__node_pointer>::value,
  68       __node_base_pointer,
  69       __node_pointer>::type   __next_pointer;
  70 #endif
  71
  72     __next_pointer    __next_;
  73
  74     _LIBCPP_INLINE_VISIBILITY
  75     __next_pointer __ptr() _NOEXCEPT {
  76         return static_cast<__next_pointer>(
  77             pointer_traits<__node_base_pointer>::pointer_to(*this));
  78     }
  79
  80     _LIBCPP_INLINE_VISIBILITY
  81     __node_pointer __upcast() _NOEXCEPT {
  82         return static_cast<__node_pointer>(
  83             pointer_traits<__node_base_pointer>::pointer_to(*this));
  84     }
  85
  86     _LIBCPP_INLINE_VISIBILITY
  87     size_t __hash() const _NOEXCEPT {
  88         return static_cast<__node_type const&>(*this).__hash_;
  89     }
  90
  91     _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
  92 };
  93
  94 template <class _Tp, class _VoidPtr>
  95 struct _LIBCPP_STANDALONE_DEBUG __hash_node
  96     : public __hash_node_base
  97              <
  98                  typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type
  99              >
 100 {
 101     typedef _Tp __node_value_type;
 102
 103     size_t            __hash_;
 104     __node_value_type __value_;
 105 };
 106
 107 inline _LIBCPP_INLINE_VISIBILITY
 108 bool
 109 __is_hash_power2(size_t __bc)
 110 {
 111     return __bc > 2 && !(__bc & (__bc - 1));
 112 }
 113
 114 inline _LIBCPP_INLINE_VISIBILITY
 115 size_t
 116 __constrain_hash(size_t __h, size_t __bc)
 117 {
 118     return !(__bc & (__bc - 1)) ? __h & (__bc - 1) :
 119         (__h < __bc ? __h : __h % __bc);
 120 }
 121
 122 inline _LIBCPP_INLINE_VISIBILITY
 123 size_t
 124 __next_hash_pow2(size_t __n)
 125 {
 126     return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n-1)));
 127 }
 128
 129
 130 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
 131
 132 template <class _NodePtr>      class _LIBCPP_TEMPLATE_VIS __hash_iterator;
 133 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 134 template <class _NodePtr>      class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
 135 template <class _ConstNodePtr> class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 136 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 137 template <class _HashIterator> class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 138
 139 template <class _Tp>
 140 struct __hash_key_value_types {
 141   static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
 142   typedef _Tp key_type;
 143   typedef _Tp __node_value_type;
 144   typedef _Tp __container_value_type;
 145   static const bool __is_map = false;
 146
 147   _LIBCPP_INLINE_VISIBILITY
 148   static key_type const& __get_key(_Tp const& __v) {
 149     return __v;
 150   }
 151   _LIBCPP_INLINE_VISIBILITY
 152   static __container_value_type const& __get_value(__node_value_type const& __v) {
 153     return __v;
 154   }
 155   _LIBCPP_INLINE_VISIBILITY
 156   static __container_value_type* __get_ptr(__node_value_type& __n) {
 157     return _VSTD::addressof(__n);
 158   }
 159   _LIBCPP_INLINE_VISIBILITY
 160   static __container_value_type&& __move(__node_value_type& __v) {
 161     return _VSTD::move(__v);
 162   }
 163 };
 164
 165 template <class _Key, class _Tp>
 166 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
 167   typedef _Key                                         key_type;
 168   typedef _Tp                                          mapped_type;
 169   typedef __hash_value_type<_Key, _Tp>                 __node_value_type;
 170   typedef pair<const _Key, _Tp>                        __container_value_type;
 171   typedef __container_value_type                       __map_value_type;
 172   static const bool __is_map = true;
 173
 174   _LIBCPP_INLINE_VISIBILITY
 175   static key_type const& __get_key(__container_value_type const& __v) {
 176     return __v.first;
 177   }
 178
 179   template <class _Up>
 180   _LIBCPP_INLINE_VISIBILITY
 181   static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value,
 182       __container_value_type const&>::type
 183   __get_value(_Up& __t) {
 184     return __t.__get_value();
 185   }
 186
 187   template <class _Up>
 188   _LIBCPP_INLINE_VISIBILITY
 189   static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value,
 190       __container_value_type const&>::type
 191   __get_value(_Up& __t) {
 192     return __t;
 193   }
 194
 195   _LIBCPP_INLINE_VISIBILITY
 196   static __container_value_type* __get_ptr(__node_value_type& __n) {
 197     return _VSTD::addressof(__n.__get_value());
 198   }
 199   _LIBCPP_INLINE_VISIBILITY
 200   static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) {
 201     return __v.__move();
 202   }
 203 };
 204
 205 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>,
 206           bool = _KVTypes::__is_map>
 207 struct __hash_map_pointer_types {};
 208
 209 template <class _Tp, class _AllocPtr, class _KVTypes>
 210 struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
 211   typedef typename _KVTypes::__map_value_type   _Mv;
 212   typedef typename __rebind_pointer<_AllocPtr, _Mv>::type
 213                                                        __map_value_type_pointer;
 214   typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type
 215                                                  __const_map_value_type_pointer;
 216 };
 217
 218 template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
 219 struct __hash_node_types;
 220
 221 template <class _NodePtr, class _Tp, class _VoidPtr>
 222 struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
 223     : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr>
 224
 225 {
 226   typedef __hash_key_value_types<_Tp>           __base;
 227
 228 public:
 229   typedef ptrdiff_t difference_type;
 230   typedef size_t size_type;
 231
 232   typedef typename __rebind_pointer<_NodePtr, void>::type       __void_pointer;
 233
 234   typedef typename pointer_traits<_NodePtr>::element_type       __node_type;
 235   typedef _NodePtr                                              __node_pointer;
 236
 237   typedef __hash_node_base<__node_pointer>                      __node_base_type;
 238   typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type
 239                                                              __node_base_pointer;
 240
 241   typedef typename __node_base_type::__next_pointer          __next_pointer;
 242
 243   typedef _Tp                                                 __node_value_type;
 244   typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type
 245                                                       __node_value_type_pointer;
 246   typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type
 247                                                 __const_node_value_type_pointer;
 248
 249 private:
 250     static_assert(!is_const<__node_type>::value,
 251                 "_NodePtr should never be a pointer to const");
 252     static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value),
 253                   "_VoidPtr does not point to unqualified void type");
 254     static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type,
 255                           _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");
 256 };
 257
 258 template <class _HashIterator>
 259 struct __hash_node_types_from_iterator;
 260 template <class _NodePtr>
 261 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 262 template <class _NodePtr>
 263 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 264 template <class _NodePtr>
 265 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 266 template <class _NodePtr>
 267 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
 268
 269
 270 template <class _NodeValueTp, class _VoidPtr>
 271 struct __make_hash_node_types {
 272   typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
 273   typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr;
 274   typedef __hash_node_types<_NodePtr> type;
 275 };
 276
 277 template <class _NodePtr>
 278 class _LIBCPP_TEMPLATE_VIS __hash_iterator
 279 {
 280     typedef __hash_node_types<_NodePtr> _NodeTypes;
 281     typedef _NodePtr                            __node_pointer;
 282     typedef typename _NodeTypes::__next_pointer __next_pointer;
 283
 284     __next_pointer            __node_;
 285
 286 public:
 287     typedef forward_iterator_tag                           iterator_category;
 288     typedef typename _NodeTypes::__node_value_type         value_type;
 289     typedef typename _NodeTypes::difference_type           difference_type;
 290     typedef value_type&                                    reference;
 291     typedef typename _NodeTypes::__node_value_type_pointer pointer;
 292
 293     _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT : __node_(nullptr) {
 294         _VSTD::__debug_db_insert_i(this);
 295     }
 296
 297 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 298     _LIBCPP_INLINE_VISIBILITY
 299     __hash_iterator(const __hash_iterator& __i)
 300         : __node_(__i.__node_)
 301     {
 302         __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 303     }
 304
 305     _LIBCPP_INLINE_VISIBILITY
 306     ~__hash_iterator()
 307     {
 308         __get_db()->__erase_i(this);
 309     }
 310
 311     _LIBCPP_INLINE_VISIBILITY
 312     __hash_iterator& operator=(const __hash_iterator& __i)
 313     {
 314         if (this != _VSTD::addressof(__i))
 315         {
 316             __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 317             __node_ = __i.__node_;
 318         }
 319         return *this;
 320     }
 321 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 322
 323     _LIBCPP_INLINE_VISIBILITY
 324     reference operator*() const {
 325         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 326                              "Attempted to dereference a non-dereferenceable unordered container iterator");
 327         return __node_->__upcast()->__value_;
 328     }
 329
 330     _LIBCPP_INLINE_VISIBILITY
 331     pointer operator->() const {
 332         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 333                            "Attempted to dereference a non-dereferenceable unordered container iterator");
 334         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 335     }
 336
 337     _LIBCPP_INLINE_VISIBILITY
 338     __hash_iterator& operator++() {
 339         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 340                        "Attempted to increment a non-incrementable unordered container iterator");
 341         __node_ = __node_->__next_;
 342         return *this;
 343     }
 344
 345     _LIBCPP_INLINE_VISIBILITY
 346     __hash_iterator operator++(int)
 347     {
 348         __hash_iterator __t(*this);
 349         ++(*this);
 350         return __t;
 351     }
 352
 353     friend _LIBCPP_INLINE_VISIBILITY
 354     bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
 355     {
 356         return __x.__node_ == __y.__node_;
 357     }
 358     friend _LIBCPP_INLINE_VISIBILITY
 359     bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
 360         {return !(__x == __y);}
 361
 362 private:
 363     _LIBCPP_INLINE_VISIBILITY
 364     explicit __hash_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
 365         : __node_(__node)
 366         {
 367             (void)__c;
 368 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 369             __get_db()->__insert_ic(this, __c);
 370 #endif
 371         }
 372     template <class, class, class, class> friend class __hash_table;
 373     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
 374     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 375     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
 376     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 377 };
 378
 379 template <class _NodePtr>
 380 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator
 381 {
 382     static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
 383     typedef __hash_node_types<_NodePtr> _NodeTypes;
 384     typedef _NodePtr                            __node_pointer;
 385     typedef typename _NodeTypes::__next_pointer __next_pointer;
 386
 387     __next_pointer __node_;
 388
 389 public:
 390     typedef __hash_iterator<_NodePtr> __non_const_iterator;
 391
 392     typedef forward_iterator_tag                                 iterator_category;
 393     typedef typename _NodeTypes::__node_value_type               value_type;
 394     typedef typename _NodeTypes::difference_type                 difference_type;
 395     typedef const value_type&                                    reference;
 396     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 397
 398
 399     _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {
 400         _VSTD::__debug_db_insert_i(this);
 401     }
 402
 403     _LIBCPP_INLINE_VISIBILITY
 404     __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
 405         : __node_(__x.__node_)
 406     {
 407 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 408         __get_db()->__iterator_copy(this, _VSTD::addressof(__x));
 409 #endif
 410     }
 411
 412 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 413     _LIBCPP_INLINE_VISIBILITY
 414     __hash_const_iterator(const __hash_const_iterator& __i)
 415         : __node_(__i.__node_)
 416     {
 417         __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 418     }
 419
 420     _LIBCPP_INLINE_VISIBILITY
 421     ~__hash_const_iterator()
 422     {
 423         __get_db()->__erase_i(this);
 424     }
 425
 426     _LIBCPP_INLINE_VISIBILITY
 427     __hash_const_iterator& operator=(const __hash_const_iterator& __i)
 428     {
 429         if (this != _VSTD::addressof(__i))
 430         {
 431             __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 432             __node_ = __i.__node_;
 433         }
 434         return *this;
 435     }
 436 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 437
 438     _LIBCPP_INLINE_VISIBILITY
 439     reference operator*() const {
 440         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 441                            "Attempted to dereference a non-dereferenceable unordered container const_iterator");
 442         return __node_->__upcast()->__value_;
 443     }
 444     _LIBCPP_INLINE_VISIBILITY
 445     pointer operator->() const {
 446         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 447                            "Attempted to dereference a non-dereferenceable unordered container const_iterator");
 448         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 449     }
 450
 451     _LIBCPP_INLINE_VISIBILITY
 452     __hash_const_iterator& operator++() {
 453         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 454                              "Attempted to increment a non-incrementable unordered container const_iterator");
 455         __node_ = __node_->__next_;
 456         return *this;
 457     }
 458
 459     _LIBCPP_INLINE_VISIBILITY
 460     __hash_const_iterator operator++(int)
 461     {
 462         __hash_const_iterator __t(*this);
 463         ++(*this);
 464         return __t;
 465     }
 466
 467     friend _LIBCPP_INLINE_VISIBILITY
 468     bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 469     {
 470         return __x.__node_ == __y.__node_;
 471     }
 472     friend _LIBCPP_INLINE_VISIBILITY
 473     bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 474         {return !(__x == __y);}
 475
 476 private:
 477     _LIBCPP_INLINE_VISIBILITY
 478     explicit __hash_const_iterator(__next_pointer __node, const void* __c) _NOEXCEPT
 479         : __node_(__node)
 480         {
 481             (void)__c;
 482 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 483             __get_db()->__insert_ic(this, __c);
 484 #endif
 485         }
 486     template <class, class, class, class> friend class __hash_table;
 487     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 488     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
 489     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
 490 };
 491
 492 template <class _NodePtr>
 493 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator
 494 {
 495     typedef __hash_node_types<_NodePtr> _NodeTypes;
 496     typedef _NodePtr                            __node_pointer;
 497     typedef typename _NodeTypes::__next_pointer __next_pointer;
 498
 499     __next_pointer         __node_;
 500     size_t                 __bucket_;
 501     size_t                 __bucket_count_;
 502
 503 public:
 504     typedef forward_iterator_tag                                iterator_category;
 505     typedef typename _NodeTypes::__node_value_type              value_type;
 506     typedef typename _NodeTypes::difference_type                difference_type;
 507     typedef value_type&                                         reference;
 508     typedef typename _NodeTypes::__node_value_type_pointer      pointer;
 509
 510     _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {
 511         _VSTD::__debug_db_insert_i(this);
 512     }
 513
 514 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 515     _LIBCPP_INLINE_VISIBILITY
 516     __hash_local_iterator(const __hash_local_iterator& __i)
 517         : __node_(__i.__node_),
 518           __bucket_(__i.__bucket_),
 519           __bucket_count_(__i.__bucket_count_)
 520     {
 521         __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 522     }
 523
 524     _LIBCPP_INLINE_VISIBILITY
 525     ~__hash_local_iterator()
 526     {
 527         __get_db()->__erase_i(this);
 528     }
 529
 530     _LIBCPP_INLINE_VISIBILITY
 531     __hash_local_iterator& operator=(const __hash_local_iterator& __i)
 532     {
 533         if (this != _VSTD::addressof(__i))
 534         {
 535             __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 536             __node_ = __i.__node_;
 537             __bucket_ = __i.__bucket_;
 538             __bucket_count_ = __i.__bucket_count_;
 539         }
 540         return *this;
 541     }
 542 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 543
 544     _LIBCPP_INLINE_VISIBILITY
 545     reference operator*() const {
 546         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 547                            "Attempted to dereference a non-dereferenceable unordered container local_iterator");
 548         return __node_->__upcast()->__value_;
 549     }
 550
 551     _LIBCPP_INLINE_VISIBILITY
 552     pointer operator->() const {
 553         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 554                              "Attempted to dereference a non-dereferenceable unordered container local_iterator");
 555         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 556     }
 557
 558     _LIBCPP_INLINE_VISIBILITY
 559     __hash_local_iterator& operator++() {
 560         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 561                        "Attempted to increment a non-incrementable unordered container local_iterator");
 562         __node_ = __node_->__next_;
 563         if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
 564             __node_ = nullptr;
 565         return *this;
 566     }
 567
 568     _LIBCPP_INLINE_VISIBILITY
 569     __hash_local_iterator operator++(int)
 570     {
 571         __hash_local_iterator __t(*this);
 572         ++(*this);
 573         return __t;
 574     }
 575
 576     friend _LIBCPP_INLINE_VISIBILITY
 577     bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 578     {
 579         return __x.__node_ == __y.__node_;
 580     }
 581     friend _LIBCPP_INLINE_VISIBILITY
 582     bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 583         {return !(__x == __y);}
 584
 585 private:
 586     _LIBCPP_INLINE_VISIBILITY
 587     explicit __hash_local_iterator(__next_pointer __node, size_t __bucket,
 588                                    size_t __bucket_count, const void* __c) _NOEXCEPT
 589         : __node_(__node),
 590           __bucket_(__bucket),
 591           __bucket_count_(__bucket_count)
 592         {
 593             (void)__c;
 594 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 595             __get_db()->__insert_ic(this, __c);
 596 #endif
 597             if (__node_ != nullptr)
 598                 __node_ = __node_->__next_;
 599         }
 600     template <class, class, class, class> friend class __hash_table;
 601     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 602     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
 603 };
 604
 605 template <class _ConstNodePtr>
 606 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator
 607 {
 608     typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
 609     typedef _ConstNodePtr                       __node_pointer;
 610     typedef typename _NodeTypes::__next_pointer __next_pointer;
 611
 612     __next_pointer         __node_;
 613     size_t                 __bucket_;
 614     size_t                 __bucket_count_;
 615
 616     typedef pointer_traits<__node_pointer>          __pointer_traits;
 617     typedef typename __pointer_traits::element_type __node;
 618     typedef typename remove_const<__node>::type     __non_const_node;
 619     typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type
 620         __non_const_node_pointer;
 621 public:
 622     typedef __hash_local_iterator<__non_const_node_pointer>
 623                                                     __non_const_iterator;
 624
 625     typedef forward_iterator_tag                                 iterator_category;
 626     typedef typename _NodeTypes::__node_value_type               value_type;
 627     typedef typename _NodeTypes::difference_type                 difference_type;
 628     typedef const value_type&                                    reference;
 629     typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
 630
 631
 632     _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {
 633         _VSTD::__debug_db_insert_i(this);
 634     }
 635
 636     _LIBCPP_INLINE_VISIBILITY
 637     __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
 638         : __node_(__x.__node_),
 639           __bucket_(__x.__bucket_),
 640           __bucket_count_(__x.__bucket_count_)
 641     {
 642 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 643         __get_db()->__iterator_copy(this, _VSTD::addressof(__x));
 644 #endif
 645     }
 646
 647 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 648     _LIBCPP_INLINE_VISIBILITY
 649     __hash_const_local_iterator(const __hash_const_local_iterator& __i)
 650         : __node_(__i.__node_),
 651           __bucket_(__i.__bucket_),
 652           __bucket_count_(__i.__bucket_count_)
 653     {
 654         __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 655     }
 656
 657     _LIBCPP_INLINE_VISIBILITY
 658     ~__hash_const_local_iterator()
 659     {
 660         __get_db()->__erase_i(this);
 661     }
 662
 663     _LIBCPP_INLINE_VISIBILITY
 664     __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
 665     {
 666         if (this != _VSTD::addressof(__i))
 667         {
 668             __get_db()->__iterator_copy(this, _VSTD::addressof(__i));
 669             __node_ = __i.__node_;
 670             __bucket_ = __i.__bucket_;
 671             __bucket_count_ = __i.__bucket_count_;
 672         }
 673         return *this;
 674     }
 675 #endif // _LIBCPP_ENABLE_DEBUG_MODE
 676
 677     _LIBCPP_INLINE_VISIBILITY
 678     reference operator*() const {
 679         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 680                            "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
 681         return __node_->__upcast()->__value_;
 682     }
 683
 684     _LIBCPP_INLINE_VISIBILITY
 685     pointer operator->() const {
 686         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 687                            "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
 688         return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__value_);
 689     }
 690
 691     _LIBCPP_INLINE_VISIBILITY
 692     __hash_const_local_iterator& operator++() {
 693         _LIBCPP_DEBUG_ASSERT(__get_const_db()->__dereferenceable(this),
 694                        "Attempted to increment a non-incrementable unordered container const_local_iterator");
 695         __node_ = __node_->__next_;
 696         if (__node_ != nullptr && __constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
 697             __node_ = nullptr;
 698         return *this;
 699     }
 700
 701     _LIBCPP_INLINE_VISIBILITY
 702     __hash_const_local_iterator operator++(int)
 703     {
 704         __hash_const_local_iterator __t(*this);
 705         ++(*this);
 706         return __t;
 707     }
 708
 709     friend _LIBCPP_INLINE_VISIBILITY
 710     bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 711     {
 712         return __x.__node_ == __y.__node_;
 713     }
 714     friend _LIBCPP_INLINE_VISIBILITY
 715     bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 716         {return !(__x == __y);}
 717
 718 private:
 719     _LIBCPP_INLINE_VISIBILITY
 720     explicit __hash_const_local_iterator(__next_pointer __node_ptr, size_t __bucket,
 721                                          size_t __bucket_count, const void* __c) _NOEXCEPT
 722         : __node_(__node_ptr),
 723           __bucket_(__bucket),
 724           __bucket_count_(__bucket_count)
 725         {
 726             (void)__c;
 727 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
 728             __get_db()->__insert_ic(this, __c);
 729 #endif
 730             if (__node_ != nullptr)
 731                 __node_ = __node_->__next_;
 732         }
 733     template <class, class, class, class> friend class __hash_table;
 734     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
 735 };
 736
 737 template <class _Alloc>
 738 class __bucket_list_deallocator
 739 {
 740     typedef _Alloc                                          allocator_type;
 741     typedef allocator_traits<allocator_type>                __alloc_traits;
 742     typedef typename __alloc_traits::size_type              size_type;
 743
 744     __compressed_pair<size_type, allocator_type> __data_;
 745 public:
 746     typedef typename __alloc_traits::pointer pointer;
 747
 748     _LIBCPP_INLINE_VISIBILITY
 749     __bucket_list_deallocator()
 750         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 751         : __data_(0, __default_init_tag()) {}
 752
 753     _LIBCPP_INLINE_VISIBILITY
 754     __bucket_list_deallocator(const allocator_type& __a, size_type __size)
 755         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
 756         : __data_(__size, __a) {}
 757
 758     _LIBCPP_INLINE_VISIBILITY
 759     __bucket_list_deallocator(__bucket_list_deallocator&& __x)
 760         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 761         : __data_(_VSTD::move(__x.__data_))
 762     {
 763         __x.size() = 0;
 764     }
 765
 766     _LIBCPP_INLINE_VISIBILITY
 767     size_type& size() _NOEXCEPT {return __data_.first();}
 768     _LIBCPP_INLINE_VISIBILITY
 769     size_type  size() const _NOEXCEPT {return __data_.first();}
 770
 771     _LIBCPP_INLINE_VISIBILITY
 772     allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
 773     _LIBCPP_INLINE_VISIBILITY
 774     const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
 775
 776     _LIBCPP_INLINE_VISIBILITY
 777     void operator()(pointer __p) _NOEXCEPT
 778     {
 779         __alloc_traits::deallocate(__alloc(), __p, size());
 780     }
 781 };
 782
 783 template <class _Alloc> class __hash_map_node_destructor;
 784
 785 template <class _Alloc>
 786 class __hash_node_destructor
 787 {
 788     typedef _Alloc                                          allocator_type;
 789     typedef allocator_traits<allocator_type>                __alloc_traits;
 790
 791 public:
 792     typedef typename __alloc_traits::pointer                pointer;
 793 private:
 794     typedef __hash_node_types<pointer> _NodeTypes;
 795
 796     allocator_type& __na_;
 797
 798 public:
 799     bool __value_constructed;
 800
 801     __hash_node_destructor(__hash_node_destructor const&) = default;
 802     __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
 803
 804
 805     _LIBCPP_INLINE_VISIBILITY
 806     explicit __hash_node_destructor(allocator_type& __na,
 807                                     bool __constructed = false) _NOEXCEPT
 808         : __na_(__na),
 809           __value_constructed(__constructed)
 810         {}
 811
 812     _LIBCPP_INLINE_VISIBILITY
 813     void operator()(pointer __p) _NOEXCEPT
 814     {
 815         if (__value_constructed)
 816             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
 817         if (__p)
 818             __alloc_traits::deallocate(__na_, __p, 1);
 819     }
 820
 821     template <class> friend class __hash_map_node_destructor;
 822 };
 823
 824 #if _LIBCPP_STD_VER > 14
 825 template <class _NodeType, class _Alloc>
 826 struct __generic_container_node_destructor;
 827
 828 template <class _Tp, class _VoidPtr, class _Alloc>
 829 struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>
 830     : __hash_node_destructor<_Alloc>
 831 {
 832     using __hash_node_destructor<_Alloc>::__hash_node_destructor;
 833 };
 834 #endif
 835
 836 template <class _Key, class _Hash, class _Equal>
 837 struct __enforce_unordered_container_requirements {
 838 #ifndef _LIBCPP_CXX03_LANG
 839     static_assert(__check_hash_requirements<_Key, _Hash>::value,
 840     "the specified hash does not meet the Hash requirements");
 841     static_assert(is_copy_constructible<_Equal>::value,
 842     "the specified comparator is required to be copy constructible");
 843 #endif
 844     typedef int type;
 845 };
 846
 847 template <class _Key, class _Hash, class _Equal>
 848 #ifndef _LIBCPP_CXX03_LANG
 849     _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
 850     "the specified comparator type does not provide a viable const call operator")
 851     _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
 852     "the specified hash functor does not provide a viable const call operator")
 853 #endif
 854 typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
 855 __diagnose_unordered_container_requirements(int);
 856
 857 // This dummy overload is used so that the compiler won't emit a spurious
 858 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
 859 // when the overload above causes a hard error.
 860 template <class _Key, class _Hash, class _Equal>
 861 int __diagnose_unordered_container_requirements(void*);
 862
 863 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 864 class __hash_table
 865 {
 866 public:
 867     typedef _Tp    value_type;
 868     typedef _Hash  hasher;
 869     typedef _Equal key_equal;
 870     typedef _Alloc allocator_type;
 871
 872 private:
 873     typedef allocator_traits<allocator_type> __alloc_traits;
 874     typedef typename
 875       __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type
 876                                                                      _NodeTypes;
 877 public:
 878
 879     typedef typename _NodeTypes::__node_value_type           __node_value_type;
 880     typedef typename _NodeTypes::__container_value_type      __container_value_type;
 881     typedef typename _NodeTypes::key_type                    key_type;
 882     typedef value_type&                              reference;
 883     typedef const value_type&                        const_reference;
 884     typedef typename __alloc_traits::pointer         pointer;
 885     typedef typename __alloc_traits::const_pointer   const_pointer;
 886 #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
 887     typedef typename __alloc_traits::size_type       size_type;
 888 #else
 889     typedef typename _NodeTypes::size_type           size_type;
 890 #endif
 891     typedef typename _NodeTypes::difference_type     difference_type;
 892 public:
 893     // Create __node
 894
 895     typedef typename _NodeTypes::__node_type __node;
 896     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
 897     typedef allocator_traits<__node_allocator>       __node_traits;
 898     typedef typename _NodeTypes::__void_pointer      __void_pointer;
 899     typedef typename _NodeTypes::__node_pointer      __node_pointer;
 900     typedef typename _NodeTypes::__node_pointer      __node_const_pointer;
 901     typedef typename _NodeTypes::__node_base_type    __first_node;
 902     typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
 903     typedef typename _NodeTypes::__next_pointer      __next_pointer;
 904
 905 private:
 906     // check for sane allocator pointer rebinding semantics. Rebinding the
 907     // allocator for a new pointer type should be exactly the same as rebinding
 908     // the pointer using 'pointer_traits'.
 909     static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value),
 910                   "Allocator does not rebind pointers in a sane manner.");
 911     typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type
 912         __node_base_allocator;
 913     typedef allocator_traits<__node_base_allocator> __node_base_traits;
 914     static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value),
 915                  "Allocator does not rebind pointers in a sane manner.");
 916
 917 private:
 918
 919     typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator;
 920     typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
 921     typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
 922     typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
 923     typedef typename __bucket_list_deleter::pointer       __node_pointer_pointer;
 924
 925     // --- Member data begin ---
 926     __bucket_list                                         __bucket_list_;
 927     __compressed_pair<__first_node, __node_allocator>     __p1_;
 928     __compressed_pair<size_type, hasher>                  __p2_;
 929     __compressed_pair<float, key_equal>                   __p3_;
 930     // --- Member data end ---
 931
 932     _LIBCPP_INLINE_VISIBILITY
 933     size_type& size() _NOEXCEPT {return __p2_.first();}
 934 public:
 935     _LIBCPP_INLINE_VISIBILITY
 936     size_type  size() const _NOEXCEPT {return __p2_.first();}
 937
 938     _LIBCPP_INLINE_VISIBILITY
 939     hasher& hash_function() _NOEXCEPT {return __p2_.second();}
 940     _LIBCPP_INLINE_VISIBILITY
 941     const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
 942
 943     _LIBCPP_INLINE_VISIBILITY
 944     float& max_load_factor() _NOEXCEPT {return __p3_.first();}
 945     _LIBCPP_INLINE_VISIBILITY
 946     float  max_load_factor() const _NOEXCEPT {return __p3_.first();}
 947
 948     _LIBCPP_INLINE_VISIBILITY
 949     key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
 950     _LIBCPP_INLINE_VISIBILITY
 951     const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
 952
 953     _LIBCPP_INLINE_VISIBILITY
 954     __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
 955     _LIBCPP_INLINE_VISIBILITY
 956     const __node_allocator& __node_alloc() const _NOEXCEPT
 957         {return __p1_.second();}
 958
 959 public:
 960     typedef __hash_iterator<__node_pointer>                   iterator;
 961     typedef __hash_const_iterator<__node_pointer>             const_iterator;
 962     typedef __hash_local_iterator<__node_pointer>             local_iterator;
 963     typedef __hash_const_local_iterator<__node_pointer>       const_local_iterator;
 964
 965     _LIBCPP_INLINE_VISIBILITY
 966     __hash_table()
 967         _NOEXCEPT_(
 968             is_nothrow_default_constructible<__bucket_list>::value &&
 969             is_nothrow_default_constructible<__first_node>::value &&
 970             is_nothrow_default_constructible<__node_allocator>::value &&
 971             is_nothrow_default_constructible<hasher>::value &&
 972             is_nothrow_default_constructible<key_equal>::value);
 973     _LIBCPP_INLINE_VISIBILITY
 974     __hash_table(const hasher& __hf, const key_equal& __eql);
 975     __hash_table(const hasher& __hf, const key_equal& __eql,
 976                  const allocator_type& __a);
 977     explicit __hash_table(const allocator_type& __a);
 978     __hash_table(const __hash_table& __u);
 979     __hash_table(const __hash_table& __u, const allocator_type& __a);
 980     __hash_table(__hash_table&& __u)
 981         _NOEXCEPT_(
 982             is_nothrow_move_constructible<__bucket_list>::value &&
 983             is_nothrow_move_constructible<__first_node>::value &&
 984             is_nothrow_move_constructible<__node_allocator>::value &&
 985             is_nothrow_move_constructible<hasher>::value &&
 986             is_nothrow_move_constructible<key_equal>::value);
 987     __hash_table(__hash_table&& __u, const allocator_type& __a);
 988     ~__hash_table();
 989
 990     __hash_table& operator=(const __hash_table& __u);
 991     _LIBCPP_INLINE_VISIBILITY
 992     __hash_table& operator=(__hash_table&& __u)
 993         _NOEXCEPT_(
 994             __node_traits::propagate_on_container_move_assignment::value &&
 995             is_nothrow_move_assignable<__node_allocator>::value &&
 996             is_nothrow_move_assignable<hasher>::value &&
 997             is_nothrow_move_assignable<key_equal>::value);
 998     template <class _InputIterator>
 999         void __assign_unique(_InputIterator __first, _InputIterator __last);
1000     template <class _InputIterator>
1001         void __assign_multi(_InputIterator __first, _InputIterator __last);
1002
1003     _LIBCPP_INLINE_VISIBILITY
1004     size_type max_size() const _NOEXCEPT
1005     {
1006         return _VSTD::min<size_type>(
1007             __node_traits::max_size(__node_alloc()),
1008             numeric_limits<difference_type >::max()
1009         );
1010     }
1011
1012 private:
1013     _LIBCPP_INLINE_VISIBILITY
1014     __next_pointer __node_insert_multi_prepare(size_t __cp_hash,
1015                                                value_type& __cp_val);
1016     _LIBCPP_INLINE_VISIBILITY
1017     void __node_insert_multi_perform(__node_pointer __cp,
1018                                      __next_pointer __pn) _NOEXCEPT;
1019
1020     _LIBCPP_INLINE_VISIBILITY
1021     __next_pointer __node_insert_unique_prepare(size_t __nd_hash,
1022                                                 value_type& __nd_val);
1023     _LIBCPP_INLINE_VISIBILITY
1024     void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
1025
1026 public:
1027     _LIBCPP_INLINE_VISIBILITY
1028     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
1029     _LIBCPP_INLINE_VISIBILITY
1030     iterator             __node_insert_multi(__node_pointer __nd);
1031     _LIBCPP_INLINE_VISIBILITY
1032     iterator             __node_insert_multi(const_iterator __p,
1033                                              __node_pointer __nd);
1034
1035     template <class _Key, class ..._Args>
1036     _LIBCPP_INLINE_VISIBILITY
1037     pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
1038
1039     template <class... _Args>
1040     _LIBCPP_INLINE_VISIBILITY
1041     pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
1042
1043     template <class _Pp>
1044     _LIBCPP_INLINE_VISIBILITY
1045     pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1046       return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1047                                           __can_extract_key<_Pp, key_type>());
1048     }
1049
1050     template <class _First, class _Second>
1051     _LIBCPP_INLINE_VISIBILITY
1052     typename enable_if<
1053         __can_extract_map_key<_First, key_type, __container_value_type>::value,
1054         pair<iterator, bool>
1055     >::type __emplace_unique(_First&& __f, _Second&& __s) {
1056         return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f),
1057                                               _VSTD::forward<_Second>(__s));
1058     }
1059
1060     template <class... _Args>
1061     _LIBCPP_INLINE_VISIBILITY
1062     pair<iterator, bool> __emplace_unique(_Args&&... __args) {
1063       return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...);
1064     }
1065
1066     template <class _Pp>
1067     _LIBCPP_INLINE_VISIBILITY
1068     pair<iterator, bool>
1069     __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1070       return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1071     }
1072     template <class _Pp>
1073     _LIBCPP_INLINE_VISIBILITY
1074     pair<iterator, bool>
1075     __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1076       return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1077     }
1078     template <class _Pp>
1079     _LIBCPP_INLINE_VISIBILITY
1080     pair<iterator, bool>
1081     __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1082       return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1083     }
1084
1085     template <class... _Args>
1086     _LIBCPP_INLINE_VISIBILITY
1087     iterator __emplace_multi(_Args&&... __args);
1088     template <class... _Args>
1089     _LIBCPP_INLINE_VISIBILITY
1090     iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
1091
1092
1093     _LIBCPP_INLINE_VISIBILITY
1094     pair<iterator, bool>
1095     __insert_unique(__container_value_type&& __x) {
1096       return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x));
1097     }
1098
1099     template <class _Pp, class = typename enable_if<
1100             !__is_same_uncvref<_Pp, __container_value_type>::value
1101         >::type>
1102     _LIBCPP_INLINE_VISIBILITY
1103     pair<iterator, bool> __insert_unique(_Pp&& __x) {
1104       return __emplace_unique(_VSTD::forward<_Pp>(__x));
1105     }
1106
1107     template <class _Pp>
1108     _LIBCPP_INLINE_VISIBILITY
1109     iterator __insert_multi(_Pp&& __x) {
1110       return __emplace_multi(_VSTD::forward<_Pp>(__x));
1111     }
1112
1113     template <class _Pp>
1114     _LIBCPP_INLINE_VISIBILITY
1115     iterator __insert_multi(const_iterator __p, _Pp&& __x) {
1116         return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x));
1117     }
1118
1119     _LIBCPP_INLINE_VISIBILITY
1120     pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
1121         return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
1122     }
1123
1124 #if _LIBCPP_STD_VER > 14
1125     template <class _NodeHandle, class _InsertReturnType>
1126     _LIBCPP_INLINE_VISIBILITY
1127     _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
1128     template <class _NodeHandle>
1129     _LIBCPP_INLINE_VISIBILITY
1130     iterator __node_handle_insert_unique(const_iterator __hint,
1131                                          _NodeHandle&& __nh);
1132     template <class _Table>
1133     _LIBCPP_INLINE_VISIBILITY
1134     void __node_handle_merge_unique(_Table& __source);
1135
1136     template <class _NodeHandle>
1137     _LIBCPP_INLINE_VISIBILITY
1138     iterator __node_handle_insert_multi(_NodeHandle&& __nh);
1139     template <class _NodeHandle>
1140     _LIBCPP_INLINE_VISIBILITY
1141     iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
1142     template <class _Table>
1143     _LIBCPP_INLINE_VISIBILITY
1144     void __node_handle_merge_multi(_Table& __source);
1145
1146     template <class _NodeHandle>
1147     _LIBCPP_INLINE_VISIBILITY
1148     _NodeHandle __node_handle_extract(key_type const& __key);
1149     template <class _NodeHandle>
1150     _LIBCPP_INLINE_VISIBILITY
1151     _NodeHandle __node_handle_extract(const_iterator __it);
1152 #endif
1153
1154     void clear() _NOEXCEPT;
1155     void rehash(size_type __n);
1156     _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
1157         {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
1158
1159     _LIBCPP_INLINE_VISIBILITY
1160     size_type bucket_count() const _NOEXCEPT
1161     {
1162         return __bucket_list_.get_deleter().size();
1163     }
1164
1165     _LIBCPP_INLINE_VISIBILITY
1166     iterator       begin() _NOEXCEPT;
1167     _LIBCPP_INLINE_VISIBILITY
1168     iterator       end() _NOEXCEPT;
1169     _LIBCPP_INLINE_VISIBILITY
1170     const_iterator begin() const _NOEXCEPT;
1171     _LIBCPP_INLINE_VISIBILITY
1172     const_iterator end() const _NOEXCEPT;
1173
1174     template <class _Key>
1175         _LIBCPP_INLINE_VISIBILITY
1176         size_type bucket(const _Key& __k) const
1177         {
1178             _LIBCPP_ASSERT(bucket_count() > 0,
1179                 "unordered container::bucket(key) called when bucket_count() == 0");
1180             return __constrain_hash(hash_function()(__k), bucket_count());
1181         }
1182
1183     template <class _Key>
1184         iterator       find(const _Key& __x);
1185     template <class _Key>
1186         const_iterator find(const _Key& __x) const;
1187
1188     typedef __hash_node_destructor<__node_allocator> _Dp;
1189     typedef unique_ptr<__node, _Dp> __node_holder;
1190
1191     iterator erase(const_iterator __p);
1192     iterator erase(const_iterator __first, const_iterator __last);
1193     template <class _Key>
1194         size_type __erase_unique(const _Key& __k);
1195     template <class _Key>
1196         size_type __erase_multi(const _Key& __k);
1197     __node_holder remove(const_iterator __p) _NOEXCEPT;
1198
1199     template <class _Key>
1200         _LIBCPP_INLINE_VISIBILITY
1201         size_type __count_unique(const _Key& __k) const;
1202     template <class _Key>
1203         size_type __count_multi(const _Key& __k) const;
1204
1205     template <class _Key>
1206         pair<iterator, iterator>
1207         __equal_range_unique(const _Key& __k);
1208     template <class _Key>
1209         pair<const_iterator, const_iterator>
1210         __equal_range_unique(const _Key& __k) const;
1211
1212     template <class _Key>
1213         pair<iterator, iterator>
1214         __equal_range_multi(const _Key& __k);
1215     template <class _Key>
1216         pair<const_iterator, const_iterator>
1217         __equal_range_multi(const _Key& __k) const;
1218
1219     void swap(__hash_table& __u)
1220 #if _LIBCPP_STD_VER <= 11
1221         _NOEXCEPT_(
1222             __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
1223             && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
1224                   || __is_nothrow_swappable<__pointer_allocator>::value)
1225             && (!__node_traits::propagate_on_container_swap::value
1226                   || __is_nothrow_swappable<__node_allocator>::value)
1227             );
1228 #else
1229      _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value);
1230 #endif
1231
1232     _LIBCPP_INLINE_VISIBILITY
1233     size_type max_bucket_count() const _NOEXCEPT
1234         {return max_size(); }
1235     size_type bucket_size(size_type __n) const;
1236     _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
1237     {
1238         size_type __bc = bucket_count();
1239         return __bc != 0 ? (float)size() / __bc : 0.f;
1240     }
1241     _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
1242     {
1243         _LIBCPP_ASSERT(__mlf > 0,
1244             "unordered container::max_load_factor(lf) called with lf <= 0");
1245         max_load_factor() = _VSTD::max(__mlf, load_factor());
1246     }
1247
1248     _LIBCPP_INLINE_VISIBILITY
1249     local_iterator
1250     begin(size_type __n)
1251     {
1252         _LIBCPP_ASSERT(__n < bucket_count(),
1253             "unordered container::begin(n) called with n >= bucket_count()");
1254         return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1255     }
1256
1257     _LIBCPP_INLINE_VISIBILITY
1258     local_iterator
1259     end(size_type __n)
1260     {
1261         _LIBCPP_ASSERT(__n < bucket_count(),
1262             "unordered container::end(n) called with n >= bucket_count()");
1263         return local_iterator(nullptr, __n, bucket_count(), this);
1264     }
1265
1266     _LIBCPP_INLINE_VISIBILITY
1267     const_local_iterator
1268     cbegin(size_type __n) const
1269     {
1270         _LIBCPP_ASSERT(__n < bucket_count(),
1271             "unordered container::cbegin(n) called with n >= bucket_count()");
1272         return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1273     }
1274
1275     _LIBCPP_INLINE_VISIBILITY
1276     const_local_iterator
1277     cend(size_type __n) const
1278     {
1279         _LIBCPP_ASSERT(__n < bucket_count(),
1280             "unordered container::cend(n) called with n >= bucket_count()");
1281         return const_local_iterator(nullptr, __n, bucket_count(), this);
1282     }
1283
1284 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
1285
1286     bool __dereferenceable(const const_iterator* __i) const;
1287     bool __decrementable(const const_iterator* __i) const;
1288     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1289     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1290
1291 #endif // _LIBCPP_ENABLE_DEBUG_MODE
1292
1293 private:
1294     void __rehash(size_type __n);
1295
1296     template <class ..._Args>
1297     __node_holder __construct_node(_Args&& ...__args);
1298
1299     template <class _First, class ..._Rest>
1300     __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
1301
1302
1303     _LIBCPP_INLINE_VISIBILITY
1304     void __copy_assign_alloc(const __hash_table& __u)
1305         {__copy_assign_alloc(__u, integral_constant<bool,
1306              __node_traits::propagate_on_container_copy_assignment::value>());}
1307     void __copy_assign_alloc(const __hash_table& __u, true_type);
1308     _LIBCPP_INLINE_VISIBILITY
1309         void __copy_assign_alloc(const __hash_table&, false_type) {}
1310
1311     void __move_assign(__hash_table& __u, false_type);
1312     void __move_assign(__hash_table& __u, true_type)
1313         _NOEXCEPT_(
1314             is_nothrow_move_assignable<__node_allocator>::value &&
1315             is_nothrow_move_assignable<hasher>::value &&
1316             is_nothrow_move_assignable<key_equal>::value);
1317     _LIBCPP_INLINE_VISIBILITY
1318     void __move_assign_alloc(__hash_table& __u)
1319         _NOEXCEPT_(
1320             !__node_traits::propagate_on_container_move_assignment::value ||
1321             (is_nothrow_move_assignable<__pointer_allocator>::value &&
1322              is_nothrow_move_assignable<__node_allocator>::value))
1323         {__move_assign_alloc(__u, integral_constant<bool,
1324              __node_traits::propagate_on_container_move_assignment::value>());}
1325     _LIBCPP_INLINE_VISIBILITY
1326     void __move_assign_alloc(__hash_table& __u, true_type)
1327         _NOEXCEPT_(
1328             is_nothrow_move_assignable<__pointer_allocator>::value &&
1329             is_nothrow_move_assignable<__node_allocator>::value)
1330     {
1331         __bucket_list_.get_deleter().__alloc() =
1332                 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1333         __node_alloc() = _VSTD::move(__u.__node_alloc());
1334     }
1335     _LIBCPP_INLINE_VISIBILITY
1336         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1337
1338     void __deallocate_node(__next_pointer __np) _NOEXCEPT;
1339     __next_pointer __detach() _NOEXCEPT;
1340
1341     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1342     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1343 };
1344
1345 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1346 inline
1347 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
1348     _NOEXCEPT_(
1349         is_nothrow_default_constructible<__bucket_list>::value &&
1350         is_nothrow_default_constructible<__first_node>::value &&
1351         is_nothrow_default_constructible<__node_allocator>::value &&
1352         is_nothrow_default_constructible<hasher>::value &&
1353         is_nothrow_default_constructible<key_equal>::value)
1354     : __p2_(0, __default_init_tag()),
1355       __p3_(1.0f, __default_init_tag())
1356 {
1357 }
1358
1359 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1360 inline
1361 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1362                                                        const key_equal& __eql)
1363     : __bucket_list_(nullptr, __bucket_list_deleter()),
1364       __p1_(),
1365       __p2_(0, __hf),
1366       __p3_(1.0f, __eql)
1367 {
1368 }
1369
1370 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1371 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1372                                                        const key_equal& __eql,
1373                                                        const allocator_type& __a)
1374     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1375       __p1_(__default_init_tag(), __node_allocator(__a)),
1376       __p2_(0, __hf),
1377       __p3_(1.0f, __eql)
1378 {
1379 }
1380
1381 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1382 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1383     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1384       __p1_(__default_init_tag(), __node_allocator(__a)),
1385       __p2_(0, __default_init_tag()),
1386       __p3_(1.0f, __default_init_tag())
1387 {
1388 }
1389
1390 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1391 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1392     : __bucket_list_(nullptr,
1393           __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1394               select_on_container_copy_construction(
1395                   __u.__bucket_list_.get_deleter().__alloc()), 0)),
1396       __p1_(__default_init_tag(), allocator_traits<__node_allocator>::
1397           select_on_container_copy_construction(__u.__node_alloc())),
1398       __p2_(0, __u.hash_function()),
1399       __p3_(__u.__p3_)
1400 {
1401 }
1402
1403 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1404 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1405                                                        const allocator_type& __a)
1406     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1407       __p1_(__default_init_tag(), __node_allocator(__a)),
1408       __p2_(0, __u.hash_function()),
1409       __p3_(__u.__p3_)
1410 {
1411 }
1412
1413 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1414 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
1415         _NOEXCEPT_(
1416             is_nothrow_move_constructible<__bucket_list>::value &&
1417             is_nothrow_move_constructible<__first_node>::value &&
1418             is_nothrow_move_constructible<__node_allocator>::value &&
1419             is_nothrow_move_constructible<hasher>::value &&
1420             is_nothrow_move_constructible<key_equal>::value)
1421     : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1422       __p1_(_VSTD::move(__u.__p1_)),
1423       __p2_(_VSTD::move(__u.__p2_)),
1424       __p3_(_VSTD::move(__u.__p3_))
1425 {
1426     if (size() > 0)
1427     {
1428         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1429             __p1_.first().__ptr();
1430         __u.__p1_.first().__next_ = nullptr;
1431         __u.size() = 0;
1432     }
1433 }
1434
1435 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1436 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1437                                                        const allocator_type& __a)
1438     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1439       __p1_(__default_init_tag(), __node_allocator(__a)),
1440       __p2_(0, _VSTD::move(__u.hash_function())),
1441       __p3_(_VSTD::move(__u.__p3_))
1442 {
1443     if (__a == allocator_type(__u.__node_alloc()))
1444     {
1445         __bucket_list_.reset(__u.__bucket_list_.release());
1446         __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1447         __u.__bucket_list_.get_deleter().size() = 0;
1448         if (__u.size() > 0)
1449         {
1450             __p1_.first().__next_ = __u.__p1_.first().__next_;
1451             __u.__p1_.first().__next_ = nullptr;
1452             __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1453                 __p1_.first().__ptr();
1454             size() = __u.size();
1455             __u.size() = 0;
1456         }
1457     }
1458 }
1459
1460 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1461 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1462 {
1463 #if defined(_LIBCPP_CXX03_LANG)
1464     static_assert((is_copy_constructible<key_equal>::value),
1465                  "Predicate must be copy-constructible.");
1466     static_assert((is_copy_constructible<hasher>::value),
1467                  "Hasher must be copy-constructible.");
1468 #endif
1469
1470     __deallocate_node(__p1_.first().__next_);
1471     std::__debug_db_erase_c(this);
1472 }
1473
1474 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1475 void
1476 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1477         const __hash_table& __u, true_type)
1478 {
1479     if (__node_alloc() != __u.__node_alloc())
1480     {
1481         clear();
1482         __bucket_list_.reset();
1483         __bucket_list_.get_deleter().size() = 0;
1484     }
1485     __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1486     __node_alloc() = __u.__node_alloc();
1487 }
1488
1489 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1490 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1491 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1492 {
1493     if (this != _VSTD::addressof(__u))
1494     {
1495         __copy_assign_alloc(__u);
1496         hash_function() = __u.hash_function();
1497         key_eq() = __u.key_eq();
1498         max_load_factor() = __u.max_load_factor();
1499         __assign_multi(__u.begin(), __u.end());
1500     }
1501     return *this;
1502 }
1503
1504 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1505 void
1506 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
1507     _NOEXCEPT
1508 {
1509     __node_allocator& __na = __node_alloc();
1510     while (__np != nullptr)
1511     {
1512         __next_pointer __next = __np->__next_;
1513 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
1514         __c_node* __c = __get_db()->__find_c_and_lock(this);
1515         for (__i_node** __p = __c->end_; __p != __c->beg_; )
1516         {
1517             --__p;
1518             iterator* __i = static_cast<iterator*>((*__p)->__i_);
1519             if (__i->__node_ == __np)
1520             {
1521                 (*__p)->__c_ = nullptr;
1522                 if (--__c->end_ != __p)
1523                     _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1524             }
1525         }
1526         __get_db()->unlock();
1527 #endif
1528         __node_pointer __real_np = __np->__upcast();
1529         __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_));
1530         __node_traits::deallocate(__na, __real_np, 1);
1531         __np = __next;
1532     }
1533 }
1534
1535 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1536 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1537 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
1538 {
1539     size_type __bc = bucket_count();
1540     for (size_type __i = 0; __i < __bc; ++__i)
1541         __bucket_list_[__i] = nullptr;
1542     size() = 0;
1543     __next_pointer __cache = __p1_.first().__next_;
1544     __p1_.first().__next_ = nullptr;
1545     return __cache;
1546 }
1547
1548 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1549 void
1550 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1551         __hash_table& __u, true_type)
1552     _NOEXCEPT_(
1553         is_nothrow_move_assignable<__node_allocator>::value &&
1554         is_nothrow_move_assignable<hasher>::value &&
1555         is_nothrow_move_assignable<key_equal>::value)
1556 {
1557     clear();
1558     __bucket_list_.reset(__u.__bucket_list_.release());
1559     __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1560     __u.__bucket_list_.get_deleter().size() = 0;
1561     __move_assign_alloc(__u);
1562     size() = __u.size();
1563     hash_function() = _VSTD::move(__u.hash_function());
1564     max_load_factor() = __u.max_load_factor();
1565     key_eq() = _VSTD::move(__u.key_eq());
1566     __p1_.first().__next_ = __u.__p1_.first().__next_;
1567     if (size() > 0)
1568     {
1569         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
1570             __p1_.first().__ptr();
1571         __u.__p1_.first().__next_ = nullptr;
1572         __u.size() = 0;
1573     }
1574     std::__debug_db_swap(this, std::addressof(__u));
1575 }
1576
1577 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1578 void
1579 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1580         __hash_table& __u, false_type)
1581 {
1582     if (__node_alloc() == __u.__node_alloc())
1583         __move_assign(__u, true_type());
1584     else
1585     {
1586         hash_function() = _VSTD::move(__u.hash_function());
1587         key_eq() = _VSTD::move(__u.key_eq());
1588         max_load_factor() = __u.max_load_factor();
1589         if (bucket_count() != 0)
1590         {
1591             __next_pointer __cache = __detach();
1592 #ifndef _LIBCPP_NO_EXCEPTIONS
1593             try
1594             {
1595 #endif // _LIBCPP_NO_EXCEPTIONS
1596                 const_iterator __i = __u.begin();
1597                 while (__cache != nullptr && __u.size() != 0)
1598                 {
1599                     __cache->__upcast()->__value_ =
1600                         _VSTD::move(__u.remove(__i++)->__value_);
1601                     __next_pointer __next = __cache->__next_;
1602                     __node_insert_multi(__cache->__upcast());
1603                     __cache = __next;
1604                 }
1605 #ifndef _LIBCPP_NO_EXCEPTIONS
1606             }
1607             catch (...)
1608             {
1609                 __deallocate_node(__cache);
1610                 throw;
1611             }
1612 #endif // _LIBCPP_NO_EXCEPTIONS
1613             __deallocate_node(__cache);
1614         }
1615         const_iterator __i = __u.begin();
1616         while (__u.size() != 0)
1617         {
1618             __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_));
1619             __node_insert_multi(__h.get());
1620             __h.release();
1621         }
1622     }
1623 }
1624
1625 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1626 inline
1627 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1628 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1629     _NOEXCEPT_(
1630         __node_traits::propagate_on_container_move_assignment::value &&
1631         is_nothrow_move_assignable<__node_allocator>::value &&
1632         is_nothrow_move_assignable<hasher>::value &&
1633         is_nothrow_move_assignable<key_equal>::value)
1634 {
1635     __move_assign(__u, integral_constant<bool,
1636                   __node_traits::propagate_on_container_move_assignment::value>());
1637     return *this;
1638 }
1639
1640 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1641 template <class _InputIterator>
1642 void
1643 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1644                                                           _InputIterator __last)
1645 {
1646     typedef iterator_traits<_InputIterator> _ITraits;
1647     typedef typename _ITraits::value_type _ItValueType;
1648     static_assert((is_same<_ItValueType, __container_value_type>::value),
1649                   "__assign_unique may only be called with the containers value type");
1650
1651     if (bucket_count() != 0)
1652     {
1653         __next_pointer __cache = __detach();
1654 #ifndef _LIBCPP_NO_EXCEPTIONS
1655         try
1656         {
1657 #endif // _LIBCPP_NO_EXCEPTIONS
1658             for (; __cache != nullptr && __first != __last; ++__first)
1659             {
1660                 __cache->__upcast()->__value_ = *__first;
1661                 __next_pointer __next = __cache->__next_;
1662                 __node_insert_unique(__cache->__upcast());
1663                 __cache = __next;
1664             }
1665 #ifndef _LIBCPP_NO_EXCEPTIONS
1666         }
1667         catch (...)
1668         {
1669             __deallocate_node(__cache);
1670             throw;
1671         }
1672 #endif // _LIBCPP_NO_EXCEPTIONS
1673         __deallocate_node(__cache);
1674     }
1675     for (; __first != __last; ++__first)
1676         __insert_unique(*__first);
1677 }
1678
1679 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1680 template <class _InputIterator>
1681 void
1682 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1683                                                          _InputIterator __last)
1684 {
1685     typedef iterator_traits<_InputIterator> _ITraits;
1686     typedef typename _ITraits::value_type _ItValueType;
1687     static_assert((is_same<_ItValueType, __container_value_type>::value ||
1688                   is_same<_ItValueType, __node_value_type>::value),
1689                   "__assign_multi may only be called with the containers value type"
1690                   " or the nodes value type");
1691     if (bucket_count() != 0)
1692     {
1693         __next_pointer __cache = __detach();
1694 #ifndef _LIBCPP_NO_EXCEPTIONS
1695         try
1696         {
1697 #endif // _LIBCPP_NO_EXCEPTIONS
1698             for (; __cache != nullptr && __first != __last; ++__first)
1699             {
1700                 __cache->__upcast()->__value_ = *__first;
1701                 __next_pointer __next = __cache->__next_;
1702                 __node_insert_multi(__cache->__upcast());
1703                 __cache = __next;
1704             }
1705 #ifndef _LIBCPP_NO_EXCEPTIONS
1706         }
1707         catch (...)
1708         {
1709             __deallocate_node(__cache);
1710             throw;
1711         }
1712 #endif // _LIBCPP_NO_EXCEPTIONS
1713         __deallocate_node(__cache);
1714     }
1715     for (; __first != __last; ++__first)
1716         __insert_multi(_NodeTypes::__get_value(*__first));
1717 }
1718
1719 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1720 inline
1721 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1722 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1723 {
1724     return iterator(__p1_.first().__next_, this);
1725 }
1726
1727 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1728 inline
1729 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1730 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1731 {
1732     return iterator(nullptr, this);
1733 }
1734
1735 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1736 inline
1737 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1738 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1739 {
1740     return const_iterator(__p1_.first().__next_, this);
1741 }
1742
1743 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1744 inline
1745 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1746 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1747 {
1748     return const_iterator(nullptr, this);
1749 }
1750
1751 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1752 void
1753 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1754 {
1755     if (size() > 0)
1756     {
1757         __deallocate_node(__p1_.first().__next_);
1758         __p1_.first().__next_ = nullptr;
1759         size_type __bc = bucket_count();
1760         for (size_type __i = 0; __i < __bc; ++__i)
1761             __bucket_list_[__i] = nullptr;
1762         size() = 0;
1763     }
1764 }
1765
1766
1767 // Prepare the container for an insertion of the value __value with the hash
1768 // __hash. This does a lookup into the container to see if __value is already
1769 // present, and performs a rehash if necessary. Returns a pointer to the
1770 // existing element if it exists, otherwise nullptr.
1771 //
1772 // Note that this function does forward exceptions if key_eq() throws, and never
1773 // mutates __value or actually inserts into the map.
1774 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1775 _LIBCPP_INLINE_VISIBILITY
1776 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1777 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
1778     size_t __hash, value_type& __value)
1779 {
1780     size_type __bc = bucket_count();
1781
1782     if (__bc != 0)
1783     {
1784         size_t __chash = __constrain_hash(__hash, __bc);
1785         __next_pointer __ndptr = __bucket_list_[__chash];
1786         if (__ndptr != nullptr)
1787         {
1788             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1789                                              __constrain_hash(__ndptr->__hash(), __bc) == __chash;
1790                                                      __ndptr = __ndptr->__next_)
1791             {
1792                 if (key_eq()(__ndptr->__upcast()->__value_, __value))
1793                     return __ndptr;
1794             }
1795         }
1796     }
1797     if (size()+1 > __bc * max_load_factor() || __bc == 0)
1798     {
1799         rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1800                                      size_type(ceil(float(size() + 1) / max_load_factor()))));
1801     }
1802     return nullptr;
1803 }
1804
1805 // Insert the node __nd into the container by pushing it into the right bucket,
1806 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
1807 // rehashing has already occurred and that no element with the same key exists
1808 // in the map.
1809 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1810 _LIBCPP_INLINE_VISIBILITY
1811 void
1812 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
1813     __node_pointer __nd) _NOEXCEPT
1814 {
1815     size_type __bc = bucket_count();
1816     size_t __chash = __constrain_hash(__nd->__hash(), __bc);
1817     // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1818     __next_pointer __pn = __bucket_list_[__chash];
1819     if (__pn == nullptr)
1820     {
1821         __pn =__p1_.first().__ptr();
1822         __nd->__next_ = __pn->__next_;
1823         __pn->__next_ = __nd->__ptr();
1824         // fix up __bucket_list_
1825         __bucket_list_[__chash] = __pn;
1826         if (__nd->__next_ != nullptr)
1827             __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
1828     }
1829     else
1830     {
1831         __nd->__next_ = __pn->__next_;
1832         __pn->__next_ = __nd->__ptr();
1833     }
1834     ++size();
1835 }
1836
1837 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1838 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1839 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1840 {
1841     __nd->__hash_ = hash_function()(__nd->__value_);
1842     __next_pointer __existing_node =
1843         __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
1844
1845     // Insert the node, unless it already exists in the container.
1846     bool __inserted = false;
1847     if (__existing_node == nullptr)
1848     {
1849         __node_insert_unique_perform(__nd);
1850         __existing_node = __nd->__ptr();
1851         __inserted = true;
1852     }
1853     return pair<iterator, bool>(iterator(__existing_node, this), __inserted);
1854 }
1855
1856 // Prepare the container for an insertion of the value __cp_val with the hash
1857 // __cp_hash. This does a lookup into the container to see if __cp_value is
1858 // already present, and performs a rehash if necessary. Returns a pointer to the
1859 // last occurrence of __cp_val in the map.
1860 //
1861 // Note that this function does forward exceptions if key_eq() throws, and never
1862 // mutates __value or actually inserts into the map.
1863 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1864 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1865 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
1866     size_t __cp_hash, value_type& __cp_val)
1867 {
1868     size_type __bc = bucket_count();
1869     if (size()+1 > __bc * max_load_factor() || __bc == 0)
1870     {
1871         rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1872                        size_type(ceil(float(size() + 1) / max_load_factor()))));
1873         __bc = bucket_count();
1874     }
1875     size_t __chash = __constrain_hash(__cp_hash, __bc);
1876     __next_pointer __pn = __bucket_list_[__chash];
1877     if (__pn != nullptr)
1878     {
1879         for (bool __found = false; __pn->__next_ != nullptr &&
1880                                    __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
1881                                                            __pn = __pn->__next_)
1882         {
1883             //      __found    key_eq()     action
1884             //      false       false       loop
1885             //      true        true        loop
1886             //      false       true        set __found to true
1887             //      true        false       break
1888             if (__found != (__pn->__next_->__hash() == __cp_hash &&
1889                             key_eq()(__pn->__next_->__upcast()->__value_, __cp_val)))
1890             {
1891                 if (!__found)
1892                     __found = true;
1893                 else
1894                     break;
1895             }
1896         }
1897     }
1898     return __pn;
1899 }
1900
1901 // Insert the node __cp into the container after __pn (which is the last node in
1902 // the bucket that compares equal to __cp). Rehashing, and checking for
1903 // uniqueness has already been performed (in __node_insert_multi_prepare), so
1904 // all we need to do is update the bucket and size(). Assumes that __cp->__hash
1905 // is up-to-date.
1906 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1907 void
1908 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
1909     __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
1910 {
1911     size_type __bc = bucket_count();
1912     size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1913     if (__pn == nullptr)
1914     {
1915         __pn =__p1_.first().__ptr();
1916         __cp->__next_ = __pn->__next_;
1917         __pn->__next_ = __cp->__ptr();
1918         // fix up __bucket_list_
1919         __bucket_list_[__chash] = __pn;
1920         if (__cp->__next_ != nullptr)
1921             __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
1922                 = __cp->__ptr();
1923     }
1924     else
1925     {
1926         __cp->__next_ = __pn->__next_;
1927         __pn->__next_ = __cp->__ptr();
1928         if (__cp->__next_ != nullptr)
1929         {
1930             size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
1931             if (__nhash != __chash)
1932                 __bucket_list_[__nhash] = __cp->__ptr();
1933         }
1934     }
1935     ++size();
1936 }
1937
1938
1939 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1940 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1941 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1942 {
1943     __cp->__hash_ = hash_function()(__cp->__value_);
1944     __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_);
1945     __node_insert_multi_perform(__cp, __pn);
1946
1947     return iterator(__cp->__ptr(), this);
1948 }
1949
1950 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1951 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1952 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1953         const_iterator __p, __node_pointer __cp)
1954 {
1955     _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
1956                          "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1957                          " referring to this unordered container");
1958     if (__p != end() && key_eq()(*__p, __cp->__value_))
1959     {
1960         __next_pointer __np = __p.__node_;
1961         __cp->__hash_ = __np->__hash();
1962         size_type __bc = bucket_count();
1963         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1964         {
1965             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1966                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1967             __bc = bucket_count();
1968         }
1969         size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1970         __next_pointer __pp = __bucket_list_[__chash];
1971         while (__pp->__next_ != __np)
1972             __pp = __pp->__next_;
1973         __cp->__next_ = __np;
1974         __pp->__next_ = static_cast<__next_pointer>(__cp);
1975         ++size();
1976         return iterator(static_cast<__next_pointer>(__cp), this);
1977     }
1978     return __node_insert_multi(__cp);
1979 }
1980
1981
1982
1983 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1984 template <class _Key, class ..._Args>
1985 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1986 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)
1987 {
1988
1989     size_t __hash = hash_function()(__k);
1990     size_type __bc = bucket_count();
1991     bool __inserted = false;
1992     __next_pointer __nd;
1993     size_t __chash;
1994     if (__bc != 0)
1995     {
1996         __chash = __constrain_hash(__hash, __bc);
1997         __nd = __bucket_list_[__chash];
1998         if (__nd != nullptr)
1999         {
2000             for (__nd = __nd->__next_; __nd != nullptr &&
2001                 (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash);
2002                                                            __nd = __nd->__next_)
2003             {
2004                 if (key_eq()(__nd->__upcast()->__value_, __k))
2005                     goto __done;
2006             }
2007         }
2008     }
2009     {
2010         __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...);
2011         if (size()+1 > __bc * max_load_factor() || __bc == 0)
2012         {
2013             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
2014                            size_type(ceil(float(size() + 1) / max_load_factor()))));
2015             __bc = bucket_count();
2016             __chash = __constrain_hash(__hash, __bc);
2017         }
2018         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
2019         __next_pointer __pn = __bucket_list_[__chash];
2020         if (__pn == nullptr)
2021         {
2022             __pn = __p1_.first().__ptr();
2023             __h->__next_ = __pn->__next_;
2024             __pn->__next_ = __h.get()->__ptr();
2025             // fix up __bucket_list_
2026             __bucket_list_[__chash] = __pn;
2027             if (__h->__next_ != nullptr)
2028                 __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)]
2029                     = __h.get()->__ptr();
2030         }
2031         else
2032         {
2033             __h->__next_ = __pn->__next_;
2034             __pn->__next_ = static_cast<__next_pointer>(__h.get());
2035         }
2036         __nd = static_cast<__next_pointer>(__h.release());
2037         // increment size
2038         ++size();
2039         __inserted = true;
2040     }
2041 __done:
2042     return pair<iterator, bool>(iterator(__nd, this), __inserted);
2043 }
2044
2045 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2046 template <class... _Args>
2047 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
2048 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args)
2049 {
2050     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2051     pair<iterator, bool> __r = __node_insert_unique(__h.get());
2052     if (__r.second)
2053         __h.release();
2054     return __r;
2055 }
2056
2057 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2058 template <class... _Args>
2059 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2060 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
2061 {
2062     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2063     iterator __r = __node_insert_multi(__h.get());
2064     __h.release();
2065     return __r;
2066 }
2067
2068 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2069 template <class... _Args>
2070 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2071 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
2072         const_iterator __p, _Args&&... __args)
2073 {
2074     _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
2075                          "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
2076                          " referring to this unordered container");
2077     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2078     iterator __r = __node_insert_multi(__p, __h.get());
2079     __h.release();
2080     return __r;
2081 }
2082
2083 #if _LIBCPP_STD_VER > 14
2084 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2085 template <class _NodeHandle, class _InsertReturnType>
2086 _LIBCPP_INLINE_VISIBILITY
2087 _InsertReturnType
2088 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
2089     _NodeHandle&& __nh)
2090 {
2091     if (__nh.empty())
2092         return _InsertReturnType{end(), false, _NodeHandle()};
2093     pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
2094     if (__result.second)
2095         __nh.__release_ptr();
2096     return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
2097 }
2098
2099 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2100 template <class _NodeHandle>
2101 _LIBCPP_INLINE_VISIBILITY
2102 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2103 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
2104     const_iterator, _NodeHandle&& __nh)
2105 {
2106     if (__nh.empty())
2107         return end();
2108     pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
2109     if (__result.second)
2110         __nh.__release_ptr();
2111     return __result.first;
2112 }
2113
2114 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2115 template <class _NodeHandle>
2116 _LIBCPP_INLINE_VISIBILITY
2117 _NodeHandle
2118 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
2119     key_type const& __key)
2120 {
2121     iterator __i = find(__key);
2122     if (__i == end())
2123         return _NodeHandle();
2124     return __node_handle_extract<_NodeHandle>(__i);
2125 }
2126
2127 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2128 template <class _NodeHandle>
2129 _LIBCPP_INLINE_VISIBILITY
2130 _NodeHandle
2131 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
2132     const_iterator __p)
2133 {
2134     allocator_type __alloc(__node_alloc());
2135     return _NodeHandle(remove(__p).release(), __alloc);
2136 }
2137
2138 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2139 template <class _Table>
2140 _LIBCPP_INLINE_VISIBILITY
2141 void
2142 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
2143     _Table& __source)
2144 {
2145     static_assert(is_same<__node, typename _Table::__node>::value, "");
2146
2147     for (typename _Table::iterator __it = __source.begin();
2148          __it != __source.end();)
2149     {
2150         __node_pointer __src_ptr = __it.__node_->__upcast();
2151         size_t __hash = hash_function()(__src_ptr->__value_);
2152         __next_pointer __existing_node =
2153             __node_insert_unique_prepare(__hash, __src_ptr->__value_);
2154         auto __prev_iter = __it++;
2155         if (__existing_node == nullptr)
2156         {
2157             (void)__source.remove(__prev_iter).release();
2158             __src_ptr->__hash_ = __hash;
2159             __node_insert_unique_perform(__src_ptr);
2160         }
2161     }
2162 }
2163
2164 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2165 template <class _NodeHandle>
2166 _LIBCPP_INLINE_VISIBILITY
2167 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2168 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
2169     _NodeHandle&& __nh)
2170 {
2171     if (__nh.empty())
2172         return end();
2173     iterator __result = __node_insert_multi(__nh.__ptr_);
2174     __nh.__release_ptr();
2175     return __result;
2176 }
2177
2178 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2179 template <class _NodeHandle>
2180 _LIBCPP_INLINE_VISIBILITY
2181 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2182 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
2183     const_iterator __hint, _NodeHandle&& __nh)
2184 {
2185     if (__nh.empty())
2186         return end();
2187     iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
2188     __nh.__release_ptr();
2189     return __result;
2190 }
2191
2192 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2193 template <class _Table>
2194 _LIBCPP_INLINE_VISIBILITY
2195 void
2196 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
2197     _Table& __source)
2198 {
2199     static_assert(is_same<typename _Table::__node, __node>::value, "");
2200
2201     for (typename _Table::iterator __it = __source.begin();
2202          __it != __source.end();)
2203     {
2204         __node_pointer __src_ptr = __it.__node_->__upcast();
2205         size_t __src_hash = hash_function()(__src_ptr->__value_);
2206         __next_pointer __pn =
2207             __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
2208         (void)__source.remove(__it++).release();
2209         __src_ptr->__hash_ = __src_hash;
2210         __node_insert_multi_perform(__src_ptr, __pn);
2211     }
2212 }
2213 #endif // _LIBCPP_STD_VER > 14
2214
2215 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2216 void
2217 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
2218 _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK
2219 {
2220     if (__n == 1)
2221         __n = 2;
2222     else if (__n & (__n - 1))
2223         __n = __next_prime(__n);
2224     size_type __bc = bucket_count();
2225     if (__n > __bc)
2226         __rehash(__n);
2227     else if (__n < __bc)
2228     {
2229         __n = _VSTD::max<size_type>
2230               (
2231                   __n,
2232                   __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
2233                                            __next_prime(size_t(ceil(float(size()) / max_load_factor())))
2234               );
2235         if (__n < __bc)
2236             __rehash(__n);
2237     }
2238 }
2239
2240 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2241 void
2242 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
2243 {
2244     std::__debug_db_invalidate_all(this);
2245     __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
2246     __bucket_list_.reset(__nbc > 0 ?
2247                       __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
2248     __bucket_list_.get_deleter().size() = __nbc;
2249     if (__nbc > 0)
2250     {
2251         for (size_type __i = 0; __i < __nbc; ++__i)
2252             __bucket_list_[__i] = nullptr;
2253         __next_pointer __pp = __p1_.first().__ptr();
2254         __next_pointer __cp = __pp->__next_;
2255         if (__cp != nullptr)
2256         {
2257             size_type __chash = __constrain_hash(__cp->__hash(), __nbc);
2258             __bucket_list_[__chash] = __pp;
2259             size_type __phash = __chash;
2260             for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr;
2261                                                            __cp = __pp->__next_)
2262             {
2263                 __chash = __constrain_hash(__cp->__hash(), __nbc);
2264                 if (__chash == __phash)
2265                     __pp = __cp;
2266                 else
2267                 {
2268                     if (__bucket_list_[__chash] == nullptr)
2269                     {
2270                         __bucket_list_[__chash] = __pp;
2271                         __pp = __cp;
2272                         __phash = __chash;
2273                     }
2274                     else
2275                     {
2276                         __next_pointer __np = __cp;
2277                         for (; __np->__next_ != nullptr &&
2278                                key_eq()(__cp->__upcast()->__value_,
2279                                         __np->__next_->__upcast()->__value_);
2280                                                            __np = __np->__next_)
2281                             ;
2282                         __pp->__next_ = __np->__next_;
2283                         __np->__next_ = __bucket_list_[__chash]->__next_;
2284                         __bucket_list_[__chash]->__next_ = __cp;
2285
2286                     }
2287                 }
2288             }
2289         }
2290     }
2291 }
2292
2293 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2294 template <class _Key>
2295 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2296 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
2297 {
2298     size_t __hash = hash_function()(__k);
2299     size_type __bc = bucket_count();
2300     if (__bc != 0)
2301     {
2302         size_t __chash = __constrain_hash(__hash, __bc);
2303         __next_pointer __nd = __bucket_list_[__chash];
2304         if (__nd != nullptr)
2305         {
2306             for (__nd = __nd->__next_; __nd != nullptr &&
2307                 (__nd->__hash() == __hash
2308                   || __constrain_hash(__nd->__hash(), __bc) == __chash);
2309                                                            __nd = __nd->__next_)
2310             {
2311                 if ((__nd->__hash() == __hash)
2312                     && key_eq()(__nd->__upcast()->__value_, __k))
2313                     return iterator(__nd, this);
2314             }
2315         }
2316     }
2317     return end();
2318 }
2319
2320 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2321 template <class _Key>
2322 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
2323 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
2324 {
2325     size_t __hash = hash_function()(__k);
2326     size_type __bc = bucket_count();
2327     if (__bc != 0)
2328     {
2329         size_t __chash = __constrain_hash(__hash, __bc);
2330         __next_pointer __nd = __bucket_list_[__chash];
2331         if (__nd != nullptr)
2332         {
2333             for (__nd = __nd->__next_; __nd != nullptr &&
2334                 (__hash == __nd->__hash()
2335                     || __constrain_hash(__nd->__hash(), __bc) == __chash);
2336                                                            __nd = __nd->__next_)
2337             {
2338                 if ((__nd->__hash() == __hash)
2339                     && key_eq()(__nd->__upcast()->__value_, __k))
2340                     return const_iterator(__nd, this);
2341             }
2342         }
2343
2344     }
2345     return end();
2346 }
2347
2348 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2349 template <class ..._Args>
2350 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2351 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
2352 {
2353     static_assert(!__is_hash_value_type<_Args...>::value,
2354                   "Construct cannot be called with a hash value type");
2355     __node_allocator& __na = __node_alloc();
2356     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2357     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...);
2358     __h.get_deleter().__value_constructed = true;
2359     __h->__hash_ = hash_function()(__h->__value_);
2360     __h->__next_ = nullptr;
2361     return __h;
2362 }
2363
2364 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2365 template <class _First, class ..._Rest>
2366 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2367 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(
2368     size_t __hash, _First&& __f, _Rest&& ...__rest)
2369 {
2370     static_assert(!__is_hash_value_type<_First, _Rest...>::value,
2371                   "Construct cannot be called with a hash value type");
2372     __node_allocator& __na = __node_alloc();
2373     __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2374     __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_),
2375                              _VSTD::forward<_First>(__f),
2376                              _VSTD::forward<_Rest>(__rest)...);
2377     __h.get_deleter().__value_constructed = true;
2378     __h->__hash_ = __hash;
2379     __h->__next_ = nullptr;
2380     return __h;
2381 }
2382
2383 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2384 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2385 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
2386 {
2387     __next_pointer __np = __p.__node_;
2388     _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__p)) == this,
2389                          "unordered container erase(iterator) called with an iterator not"
2390                          " referring to this container");
2391     _LIBCPP_ASSERT(__p != end(),
2392                    "unordered container erase(iterator) called with a non-dereferenceable iterator");
2393     iterator __r(__np, this);
2394     ++__r;
2395     remove(__p);
2396     return __r;
2397 }
2398
2399 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2400 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2401 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
2402                                                 const_iterator __last)
2403 {
2404     _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__first)) == this,
2405                          "unordered container::erase(iterator, iterator) called with an iterator not"
2406                          " referring to this container");
2407     _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__last)) == this,
2408                          "unordered container::erase(iterator, iterator) called with an iterator not"
2409                          " referring to this container");
2410     for (const_iterator __p = __first; __first != __last; __p = __first)
2411     {
2412         ++__first;
2413         erase(__p);
2414     }
2415     __next_pointer __np = __last.__node_;
2416     return iterator (__np, this);
2417 }
2418
2419 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2420 template <class _Key>
2421 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2422 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
2423 {
2424     iterator __i = find(__k);
2425     if (__i == end())
2426         return 0;
2427     erase(__i);
2428     return 1;
2429 }
2430
2431 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2432 template <class _Key>
2433 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2434 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
2435 {
2436     size_type __r = 0;
2437     iterator __i = find(__k);
2438     if (__i != end())
2439     {
2440         iterator __e = end();
2441         do
2442         {
2443             erase(__i++);
2444             ++__r;
2445         } while (__i != __e && key_eq()(*__i, __k));
2446     }
2447     return __r;
2448 }
2449
2450 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2451 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2452 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
2453 {
2454     // current node
2455     __next_pointer __cn = __p.__node_;
2456     size_type __bc = bucket_count();
2457     size_t __chash = __constrain_hash(__cn->__hash(), __bc);
2458     // find previous node
2459     __next_pointer __pn = __bucket_list_[__chash];
2460     for (; __pn->__next_ != __cn; __pn = __pn->__next_)
2461         ;
2462     // Fix up __bucket_list_
2463         // if __pn is not in same bucket (before begin is not in same bucket) &&
2464         //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
2465     if (__pn == __p1_.first().__ptr()
2466             || __constrain_hash(__pn->__hash(), __bc) != __chash)
2467     {
2468         if (__cn->__next_ == nullptr
2469             || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
2470             __bucket_list_[__chash] = nullptr;
2471     }
2472         // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
2473     if (__cn->__next_ != nullptr)
2474     {
2475         size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc);
2476         if (__nhash != __chash)
2477             __bucket_list_[__nhash] = __pn;
2478     }
2479     // remove __cn
2480     __pn->__next_ = __cn->__next_;
2481     __cn->__next_ = nullptr;
2482     --size();
2483 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
2484     __c_node* __c = __get_db()->__find_c_and_lock(this);
2485     for (__i_node** __dp = __c->end_; __dp != __c->beg_; )
2486     {
2487         --__dp;
2488         iterator* __i = static_cast<iterator*>((*__dp)->__i_);
2489         if (__i->__node_ == __cn)
2490         {
2491             (*__dp)->__c_ = nullptr;
2492             if (--__c->end_ != __dp)
2493                 _VSTD::memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*));
2494         }
2495     }
2496     __get_db()->unlock();
2497 #endif
2498     return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
2499 }
2500
2501 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2502 template <class _Key>
2503 inline
2504 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2505 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
2506 {
2507     return static_cast<size_type>(find(__k) != end());
2508 }
2509
2510 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2511 template <class _Key>
2512 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2513 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
2514 {
2515     size_type __r = 0;
2516     const_iterator __i = find(__k);
2517     if (__i != end())
2518     {
2519         const_iterator __e = end();
2520         do
2521         {
2522             ++__i;
2523             ++__r;
2524         } while (__i != __e && key_eq()(*__i, __k));
2525     }
2526     return __r;
2527 }
2528
2529 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2530 template <class _Key>
2531 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2532      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2533 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2534         const _Key& __k)
2535 {
2536     iterator __i = find(__k);
2537     iterator __j = __i;
2538     if (__i != end())
2539         ++__j;
2540     return pair<iterator, iterator>(__i, __j);
2541 }
2542
2543 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2544 template <class _Key>
2545 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2546      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2547 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2548         const _Key& __k) const
2549 {
2550     const_iterator __i = find(__k);
2551     const_iterator __j = __i;
2552     if (__i != end())
2553         ++__j;
2554     return pair<const_iterator, const_iterator>(__i, __j);
2555 }
2556
2557 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2558 template <class _Key>
2559 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2560      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2561 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2562         const _Key& __k)
2563 {
2564     iterator __i = find(__k);
2565     iterator __j = __i;
2566     if (__i != end())
2567     {
2568         iterator __e = end();
2569         do
2570         {
2571             ++__j;
2572         } while (__j != __e && key_eq()(*__j, __k));
2573     }
2574     return pair<iterator, iterator>(__i, __j);
2575 }
2576
2577 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2578 template <class _Key>
2579 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2580      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2581 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2582         const _Key& __k) const
2583 {
2584     const_iterator __i = find(__k);
2585     const_iterator __j = __i;
2586     if (__i != end())
2587     {
2588         const_iterator __e = end();
2589         do
2590         {
2591             ++__j;
2592         } while (__j != __e && key_eq()(*__j, __k));
2593     }
2594     return pair<const_iterator, const_iterator>(__i, __j);
2595 }
2596
2597 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2598 void
2599 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2600 #if _LIBCPP_STD_VER <= 11
2601     _NOEXCEPT_(
2602         __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
2603         && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
2604               || __is_nothrow_swappable<__pointer_allocator>::value)
2605         && (!__node_traits::propagate_on_container_swap::value
2606               || __is_nothrow_swappable<__node_allocator>::value)
2607             )
2608 #else
2609   _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
2610 #endif
2611 {
2612     _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value ||
2613                    this->__node_alloc() == __u.__node_alloc(),
2614                    "list::swap: Either propagate_on_container_swap must be true"
2615                    " or the allocators must compare equal");
2616     {
2617     __node_pointer_pointer __npp = __bucket_list_.release();
2618     __bucket_list_.reset(__u.__bucket_list_.release());
2619     __u.__bucket_list_.reset(__npp);
2620     }
2621     _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2622     _VSTD::__swap_allocator(__bucket_list_.get_deleter().__alloc(),
2623              __u.__bucket_list_.get_deleter().__alloc());
2624     _VSTD::__swap_allocator(__node_alloc(), __u.__node_alloc());
2625     _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
2626     __p2_.swap(__u.__p2_);
2627     __p3_.swap(__u.__p3_);
2628     if (size() > 0)
2629         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] =
2630             __p1_.first().__ptr();
2631     if (__u.size() > 0)
2632         __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
2633             __u.__p1_.first().__ptr();
2634     std::__debug_db_swap(this, std::addressof(__u));
2635 }
2636
2637 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2638 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2639 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2640 {
2641     _LIBCPP_ASSERT(__n < bucket_count(),
2642         "unordered container::bucket_size(n) called with n >= bucket_count()");
2643     __next_pointer __np = __bucket_list_[__n];
2644     size_type __bc = bucket_count();
2645     size_type __r = 0;
2646     if (__np != nullptr)
2647     {
2648         for (__np = __np->__next_; __np != nullptr &&
2649                                    __constrain_hash(__np->__hash(), __bc) == __n;
2650                                                     __np = __np->__next_, (void) ++__r)
2651             ;
2652     }
2653     return __r;
2654 }
2655
2656 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2657 inline _LIBCPP_INLINE_VISIBILITY
2658 void
2659 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2660      __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2661     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2662 {
2663     __x.swap(__y);
2664 }
2665
2666 #ifdef _LIBCPP_ENABLE_DEBUG_MODE
2667
2668 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2669 bool
2670 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
2671 {
2672     return __i->__node_ != nullptr;
2673 }
2674
2675 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2676 bool
2677 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
2678 {
2679     return false;
2680 }
2681
2682 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2683 bool
2684 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2685 {
2686     return false;
2687 }
2688
2689 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2690 bool
2691 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2692 {
2693     return false;
2694 }
2695
2696 #endif // _LIBCPP_ENABLE_DEBUG_MODE
2697
2698 _LIBCPP_END_NAMESPACE_STD
2699
2700 _LIBCPP_POP_MACROS
2701
2702 #endif // _LIBCPP___HASH_TABLE