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