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