contrib/libc++/include/__hash_table

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