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