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