headers/libs/libc++/__hash_table

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP__HASH_TABLE
  12 #define _LIBCPP__HASH_TABLE
  13
  14 #include <__config>
  15 #include <initializer_list>
  16 #include <memory>
  17 #include <iterator>
  18 #include <algorithm>
  19 #include <cmath>
  20
  21 #include <__undef_min_max>
  22 #include <__undef___deallocate>
  23
  24 #include <__debug>
  25
  26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  27 #pragma GCC system_header
  28 #endif
  29
  30 _LIBCPP_BEGIN_NAMESPACE_STD
  31
  32 _LIBCPP_FUNC_VIS
  33 size_t __next_prime(size_t __n);
  34
  35 template <class _NodePtr>
  36 struct __hash_node_base
  37 {
  38     typedef __hash_node_base __first_node;
  39
  40     _NodePtr    __next_;
  41
  42     _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
  43 };
  44
  45 template <class _Tp, class _VoidPtr>
  46 struct __hash_node
  47     : public __hash_node_base
  48              <
  49                  typename pointer_traits<_VoidPtr>::template
  50 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
  51                      rebind<__hash_node<_Tp, _VoidPtr> >
  52 #else
  53                      rebind<__hash_node<_Tp, _VoidPtr> >::other
  54 #endif
  55              >
  56 {
  57     typedef _Tp value_type;
  58
  59     size_t     __hash_;
  60     value_type __value_;
  61 };
  62
  63 inline _LIBCPP_INLINE_VISIBILITY
  64 bool
  65 __is_hash_power2(size_t __bc)
  66 {
  67     return __bc > 2 && !(__bc & (__bc - 1));
  68 }
  69
  70 inline _LIBCPP_INLINE_VISIBILITY
  71 size_t
  72 __constrain_hash(size_t __h, size_t __bc)
  73 {
  74     return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc;
  75 }
  76
  77 inline _LIBCPP_INLINE_VISIBILITY
  78 size_t
  79 __next_hash_pow2(size_t __n)
  80 {
  81     return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
  82 }
  83
  84 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
  85 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
  86 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
  87 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
  88
  89 template <class _NodePtr>
  90 class _LIBCPP_TYPE_VIS_ONLY __hash_iterator
  91 {
  92     typedef _NodePtr __node_pointer;
  93
  94     __node_pointer            __node_;
  95
  96 public:
  97     typedef forward_iterator_tag                         iterator_category;
  98     typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type;
  99     typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
 100     typedef value_type&                                  reference;
 101     typedef typename pointer_traits<__node_pointer>::template
 102 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 103                      rebind<value_type>
 104 #else
 105                      rebind<value_type>::other
 106 #endif
 107                                                          pointer;
 108
 109     _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT
 110 #if _LIBCPP_STD_VER > 11
 111     : __node_(nullptr)
 112 #endif
 113     {
 114 #if _LIBCPP_DEBUG_LEVEL >= 2
 115         __get_db()->__insert_i(this);
 116 #endif
 117     }
 118
 119 #if _LIBCPP_DEBUG_LEVEL >= 2
 120
 121     _LIBCPP_INLINE_VISIBILITY
 122     __hash_iterator(const __hash_iterator& __i)
 123         : __node_(__i.__node_)
 124     {
 125         __get_db()->__iterator_copy(this, &__i);
 126     }
 127
 128     _LIBCPP_INLINE_VISIBILITY
 129     ~__hash_iterator()
 130     {
 131         __get_db()->__erase_i(this);
 132     }
 133
 134     _LIBCPP_INLINE_VISIBILITY
 135     __hash_iterator& operator=(const __hash_iterator& __i)
 136     {
 137         if (this != &__i)
 138         {
 139             __get_db()->__iterator_copy(this, &__i);
 140             __node_ = __i.__node_;
 141         }
 142         return *this;
 143     }
 144
 145 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 146
 147     _LIBCPP_INLINE_VISIBILITY
 148         reference operator*() const
 149         {
 150 #if _LIBCPP_DEBUG_LEVEL >= 2
 151             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 152                            "Attempted to dereference a non-dereferenceable unordered container iterator");
 153 #endif
 154             return __node_->__value_;
 155         }
 156     _LIBCPP_INLINE_VISIBILITY
 157         pointer operator->() const
 158         {
 159 #if _LIBCPP_DEBUG_LEVEL >= 2
 160             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 161                            "Attempted to dereference a non-dereferenceable unordered container iterator");
 162 #endif
 163             return pointer_traits<pointer>::pointer_to(__node_->__value_);
 164         }
 165
 166     _LIBCPP_INLINE_VISIBILITY
 167     __hash_iterator& operator++()
 168     {
 169 #if _LIBCPP_DEBUG_LEVEL >= 2
 170         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 171                        "Attempted to increment non-incrementable unordered container iterator");
 172 #endif
 173         __node_ = __node_->__next_;
 174         return *this;
 175     }
 176
 177     _LIBCPP_INLINE_VISIBILITY
 178     __hash_iterator operator++(int)
 179     {
 180         __hash_iterator __t(*this);
 181         ++(*this);
 182         return __t;
 183     }
 184
 185     friend _LIBCPP_INLINE_VISIBILITY
 186     bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
 187     {
 188         return __x.__node_ == __y.__node_;
 189     }
 190     friend _LIBCPP_INLINE_VISIBILITY
 191     bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
 192         {return !(__x == __y);}
 193
 194 private:
 195 #if _LIBCPP_DEBUG_LEVEL >= 2
 196     _LIBCPP_INLINE_VISIBILITY
 197     __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
 198         : __node_(__node)
 199         {
 200             __get_db()->__insert_ic(this, __c);
 201         }
 202 #else
 203     _LIBCPP_INLINE_VISIBILITY
 204     __hash_iterator(__node_pointer __node) _NOEXCEPT
 205         : __node_(__node)
 206         {}
 207 #endif
 208
 209     template <class, class, class, class> friend class __hash_table;
 210     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
 211     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
 212     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
 213     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
 214 };
 215
 216 template <class _ConstNodePtr>
 217 class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator
 218 {
 219     typedef _ConstNodePtr __node_pointer;
 220
 221     __node_pointer         __node_;
 222
 223     typedef typename remove_const<
 224         typename pointer_traits<__node_pointer>::element_type
 225                                  >::type __node;
 226
 227 public:
 228     typedef forward_iterator_tag                       iterator_category;
 229     typedef typename __node::value_type                value_type;
 230     typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
 231     typedef const value_type&                          reference;
 232     typedef typename pointer_traits<__node_pointer>::template
 233 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 234             rebind<const value_type>
 235 #else
 236             rebind<const value_type>::other
 237 #endif
 238                                                        pointer;
 239     typedef typename pointer_traits<__node_pointer>::template
 240 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 241             rebind<__node>
 242 #else
 243             rebind<__node>::other
 244 #endif
 245                                                       __non_const_node_pointer;
 246     typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
 247
 248     _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT
 249 #if _LIBCPP_STD_VER > 11
 250     : __node_(nullptr)
 251 #endif
 252     {
 253 #if _LIBCPP_DEBUG_LEVEL >= 2
 254         __get_db()->__insert_i(this);
 255 #endif
 256     }
 257     _LIBCPP_INLINE_VISIBILITY
 258     __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
 259         : __node_(__x.__node_)
 260     {
 261 #if _LIBCPP_DEBUG_LEVEL >= 2
 262         __get_db()->__iterator_copy(this, &__x);
 263 #endif
 264     }
 265
 266 #if _LIBCPP_DEBUG_LEVEL >= 2
 267
 268     _LIBCPP_INLINE_VISIBILITY
 269     __hash_const_iterator(const __hash_const_iterator& __i)
 270         : __node_(__i.__node_)
 271     {
 272         __get_db()->__iterator_copy(this, &__i);
 273     }
 274
 275     _LIBCPP_INLINE_VISIBILITY
 276     ~__hash_const_iterator()
 277     {
 278         __get_db()->__erase_i(this);
 279     }
 280
 281     _LIBCPP_INLINE_VISIBILITY
 282     __hash_const_iterator& operator=(const __hash_const_iterator& __i)
 283     {
 284         if (this != &__i)
 285         {
 286             __get_db()->__iterator_copy(this, &__i);
 287             __node_ = __i.__node_;
 288         }
 289         return *this;
 290     }
 291
 292 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 293
 294     _LIBCPP_INLINE_VISIBILITY
 295         reference operator*() const
 296         {
 297 #if _LIBCPP_DEBUG_LEVEL >= 2
 298             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 299                            "Attempted to dereference a non-dereferenceable unordered container const_iterator");
 300 #endif
 301             return __node_->__value_;
 302         }
 303     _LIBCPP_INLINE_VISIBILITY
 304         pointer operator->() const
 305         {
 306 #if _LIBCPP_DEBUG_LEVEL >= 2
 307             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 308                            "Attempted to dereference a non-dereferenceable unordered container const_iterator");
 309 #endif
 310             return pointer_traits<pointer>::pointer_to(__node_->__value_);
 311         }
 312
 313     _LIBCPP_INLINE_VISIBILITY
 314     __hash_const_iterator& operator++()
 315     {
 316 #if _LIBCPP_DEBUG_LEVEL >= 2
 317         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 318                        "Attempted to increment non-incrementable unordered container const_iterator");
 319 #endif
 320         __node_ = __node_->__next_;
 321         return *this;
 322     }
 323
 324     _LIBCPP_INLINE_VISIBILITY
 325     __hash_const_iterator operator++(int)
 326     {
 327         __hash_const_iterator __t(*this);
 328         ++(*this);
 329         return __t;
 330     }
 331
 332     friend _LIBCPP_INLINE_VISIBILITY
 333     bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 334     {
 335         return __x.__node_ == __y.__node_;
 336     }
 337     friend _LIBCPP_INLINE_VISIBILITY
 338     bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
 339         {return !(__x == __y);}
 340
 341 private:
 342 #if _LIBCPP_DEBUG_LEVEL >= 2
 343     _LIBCPP_INLINE_VISIBILITY
 344     __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
 345         : __node_(__node)
 346         {
 347             __get_db()->__insert_ic(this, __c);
 348         }
 349 #else
 350     _LIBCPP_INLINE_VISIBILITY
 351     __hash_const_iterator(__node_pointer __node) _NOEXCEPT
 352         : __node_(__node)
 353         {}
 354 #endif
 355
 356     template <class, class, class, class> friend class __hash_table;
 357     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
 358     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
 359     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
 360 };
 361
 362 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
 363
 364 template <class _NodePtr>
 365 class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator
 366 {
 367     typedef _NodePtr __node_pointer;
 368
 369     __node_pointer         __node_;
 370     size_t                 __bucket_;
 371     size_t                 __bucket_count_;
 372
 373     typedef pointer_traits<__node_pointer>          __pointer_traits;
 374 public:
 375     typedef forward_iterator_tag                                iterator_category;
 376     typedef typename __pointer_traits::element_type::value_type value_type;
 377     typedef typename __pointer_traits::difference_type          difference_type;
 378     typedef value_type&                                         reference;
 379     typedef typename __pointer_traits::template
 380 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 381             rebind<value_type>
 382 #else
 383             rebind<value_type>::other
 384 #endif
 385                                                                 pointer;
 386
 387     _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT
 388     {
 389 #if _LIBCPP_DEBUG_LEVEL >= 2
 390         __get_db()->__insert_i(this);
 391 #endif
 392     }
 393
 394 #if _LIBCPP_DEBUG_LEVEL >= 2
 395
 396     _LIBCPP_INLINE_VISIBILITY
 397     __hash_local_iterator(const __hash_local_iterator& __i)
 398         : __node_(__i.__node_),
 399           __bucket_(__i.__bucket_),
 400           __bucket_count_(__i.__bucket_count_)
 401     {
 402         __get_db()->__iterator_copy(this, &__i);
 403     }
 404
 405     _LIBCPP_INLINE_VISIBILITY
 406     ~__hash_local_iterator()
 407     {
 408         __get_db()->__erase_i(this);
 409     }
 410
 411     _LIBCPP_INLINE_VISIBILITY
 412     __hash_local_iterator& operator=(const __hash_local_iterator& __i)
 413     {
 414         if (this != &__i)
 415         {
 416             __get_db()->__iterator_copy(this, &__i);
 417             __node_ = __i.__node_;
 418             __bucket_ = __i.__bucket_;
 419             __bucket_count_ = __i.__bucket_count_;
 420         }
 421         return *this;
 422     }
 423
 424 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 425
 426     _LIBCPP_INLINE_VISIBILITY
 427         reference operator*() const
 428         {
 429 #if _LIBCPP_DEBUG_LEVEL >= 2
 430             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 431                            "Attempted to dereference a non-dereferenceable unordered container local_iterator");
 432 #endif
 433             return __node_->__value_;
 434         }
 435     _LIBCPP_INLINE_VISIBILITY
 436         pointer operator->() const
 437         {
 438 #if _LIBCPP_DEBUG_LEVEL >= 2
 439             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 440                            "Attempted to dereference a non-dereferenceable unordered container local_iterator");
 441 #endif
 442             return pointer_traits<pointer>::pointer_to(__node_->__value_);
 443         }
 444
 445     _LIBCPP_INLINE_VISIBILITY
 446     __hash_local_iterator& operator++()
 447     {
 448 #if _LIBCPP_DEBUG_LEVEL >= 2
 449         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 450                        "Attempted to increment non-incrementable unordered container local_iterator");
 451 #endif
 452         __node_ = __node_->__next_;
 453         if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
 454             __node_ = nullptr;
 455         return *this;
 456     }
 457
 458     _LIBCPP_INLINE_VISIBILITY
 459     __hash_local_iterator operator++(int)
 460     {
 461         __hash_local_iterator __t(*this);
 462         ++(*this);
 463         return __t;
 464     }
 465
 466     friend _LIBCPP_INLINE_VISIBILITY
 467     bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 468     {
 469         return __x.__node_ == __y.__node_;
 470     }
 471     friend _LIBCPP_INLINE_VISIBILITY
 472     bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
 473         {return !(__x == __y);}
 474
 475 private:
 476 #if _LIBCPP_DEBUG_LEVEL >= 2
 477     _LIBCPP_INLINE_VISIBILITY
 478     __hash_local_iterator(__node_pointer __node, size_t __bucket,
 479                           size_t __bucket_count, const void* __c) _NOEXCEPT
 480         : __node_(__node),
 481           __bucket_(__bucket),
 482           __bucket_count_(__bucket_count)
 483         {
 484             __get_db()->__insert_ic(this, __c);
 485             if (__node_ != nullptr)
 486                 __node_ = __node_->__next_;
 487         }
 488 #else
 489     _LIBCPP_INLINE_VISIBILITY
 490     __hash_local_iterator(__node_pointer __node, size_t __bucket,
 491                           size_t __bucket_count) _NOEXCEPT
 492         : __node_(__node),
 493           __bucket_(__bucket),
 494           __bucket_count_(__bucket_count)
 495         {
 496             if (__node_ != nullptr)
 497                 __node_ = __node_->__next_;
 498         }
 499 #endif
 500     template <class, class, class, class> friend class __hash_table;
 501     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
 502     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
 503 };
 504
 505 template <class _ConstNodePtr>
 506 class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator
 507 {
 508     typedef _ConstNodePtr __node_pointer;
 509
 510     __node_pointer         __node_;
 511     size_t                 __bucket_;
 512     size_t                 __bucket_count_;
 513
 514     typedef pointer_traits<__node_pointer>          __pointer_traits;
 515     typedef typename __pointer_traits::element_type __node;
 516     typedef typename remove_const<__node>::type     __non_const_node;
 517     typedef typename pointer_traits<__node_pointer>::template
 518 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 519             rebind<__non_const_node>
 520 #else
 521             rebind<__non_const_node>::other
 522 #endif
 523                                                     __non_const_node_pointer;
 524     typedef __hash_local_iterator<__non_const_node_pointer>
 525                                                     __non_const_iterator;
 526 public:
 527     typedef forward_iterator_tag                       iterator_category;
 528     typedef typename remove_const<
 529                         typename __pointer_traits::element_type::value_type
 530                      >::type                           value_type;
 531     typedef typename __pointer_traits::difference_type difference_type;
 532     typedef const value_type&                          reference;
 533     typedef typename __pointer_traits::template
 534 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 535             rebind<const value_type>
 536 #else
 537             rebind<const value_type>::other
 538 #endif
 539                                                        pointer;
 540
 541     _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT
 542     {
 543 #if _LIBCPP_DEBUG_LEVEL >= 2
 544         __get_db()->__insert_i(this);
 545 #endif
 546     }
 547
 548     _LIBCPP_INLINE_VISIBILITY
 549     __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
 550         : __node_(__x.__node_),
 551           __bucket_(__x.__bucket_),
 552           __bucket_count_(__x.__bucket_count_)
 553     {
 554 #if _LIBCPP_DEBUG_LEVEL >= 2
 555         __get_db()->__iterator_copy(this, &__x);
 556 #endif
 557     }
 558
 559 #if _LIBCPP_DEBUG_LEVEL >= 2
 560
 561     _LIBCPP_INLINE_VISIBILITY
 562     __hash_const_local_iterator(const __hash_const_local_iterator& __i)
 563         : __node_(__i.__node_),
 564           __bucket_(__i.__bucket_),
 565           __bucket_count_(__i.__bucket_count_)
 566     {
 567         __get_db()->__iterator_copy(this, &__i);
 568     }
 569
 570     _LIBCPP_INLINE_VISIBILITY
 571     ~__hash_const_local_iterator()
 572     {
 573         __get_db()->__erase_i(this);
 574     }
 575
 576     _LIBCPP_INLINE_VISIBILITY
 577     __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
 578     {
 579         if (this != &__i)
 580         {
 581             __get_db()->__iterator_copy(this, &__i);
 582             __node_ = __i.__node_;
 583             __bucket_ = __i.__bucket_;
 584             __bucket_count_ = __i.__bucket_count_;
 585         }
 586         return *this;
 587     }
 588
 589 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 590
 591     _LIBCPP_INLINE_VISIBILITY
 592         reference operator*() const
 593         {
 594 #if _LIBCPP_DEBUG_LEVEL >= 2
 595             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 596                            "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
 597 #endif
 598             return __node_->__value_;
 599         }
 600     _LIBCPP_INLINE_VISIBILITY
 601         pointer operator->() const
 602         {
 603 #if _LIBCPP_DEBUG_LEVEL >= 2
 604             _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 605                            "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
 606 #endif
 607             return pointer_traits<pointer>::pointer_to(__node_->__value_);
 608         }
 609
 610     _LIBCPP_INLINE_VISIBILITY
 611     __hash_const_local_iterator& operator++()
 612     {
 613 #if _LIBCPP_DEBUG_LEVEL >= 2
 614         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
 615                        "Attempted to increment non-incrementable unordered container const_local_iterator");
 616 #endif
 617         __node_ = __node_->__next_;
 618         if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
 619             __node_ = nullptr;
 620         return *this;
 621     }
 622
 623     _LIBCPP_INLINE_VISIBILITY
 624     __hash_const_local_iterator operator++(int)
 625     {
 626         __hash_const_local_iterator __t(*this);
 627         ++(*this);
 628         return __t;
 629     }
 630
 631     friend _LIBCPP_INLINE_VISIBILITY
 632     bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 633     {
 634         return __x.__node_ == __y.__node_;
 635     }
 636     friend _LIBCPP_INLINE_VISIBILITY
 637     bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
 638         {return !(__x == __y);}
 639
 640 private:
 641 #if _LIBCPP_DEBUG_LEVEL >= 2
 642     _LIBCPP_INLINE_VISIBILITY
 643     __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
 644                                 size_t __bucket_count, const void* __c) _NOEXCEPT
 645         : __node_(__node),
 646           __bucket_(__bucket),
 647           __bucket_count_(__bucket_count)
 648         {
 649             __get_db()->__insert_ic(this, __c);
 650             if (__node_ != nullptr)
 651                 __node_ = __node_->__next_;
 652         }
 653 #else
 654     _LIBCPP_INLINE_VISIBILITY
 655     __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
 656                                 size_t __bucket_count) _NOEXCEPT
 657         : __node_(__node),
 658           __bucket_(__bucket),
 659           __bucket_count_(__bucket_count)
 660         {
 661             if (__node_ != nullptr)
 662                 __node_ = __node_->__next_;
 663         }
 664 #endif
 665     template <class, class, class, class> friend class __hash_table;
 666     template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
 667 };
 668
 669 template <class _Alloc>
 670 class __bucket_list_deallocator
 671 {
 672     typedef _Alloc                                          allocator_type;
 673     typedef allocator_traits<allocator_type>                __alloc_traits;
 674     typedef typename __alloc_traits::size_type              size_type;
 675
 676     __compressed_pair<size_type, allocator_type> __data_;
 677 public:
 678     typedef typename __alloc_traits::pointer pointer;
 679
 680     _LIBCPP_INLINE_VISIBILITY
 681     __bucket_list_deallocator()
 682         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
 683         : __data_(0) {}
 684
 685     _LIBCPP_INLINE_VISIBILITY
 686     __bucket_list_deallocator(const allocator_type& __a, size_type __size)
 687         _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
 688         : __data_(__size, __a) {}
 689
 690 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 691
 692     _LIBCPP_INLINE_VISIBILITY
 693     __bucket_list_deallocator(__bucket_list_deallocator&& __x)
 694         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
 695         : __data_(_VSTD::move(__x.__data_))
 696     {
 697         __x.size() = 0;
 698     }
 699
 700 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 701
 702     _LIBCPP_INLINE_VISIBILITY
 703     size_type& size() _NOEXCEPT {return __data_.first();}
 704     _LIBCPP_INLINE_VISIBILITY
 705     size_type  size() const _NOEXCEPT {return __data_.first();}
 706
 707     _LIBCPP_INLINE_VISIBILITY
 708     allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
 709     _LIBCPP_INLINE_VISIBILITY
 710     const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
 711
 712     _LIBCPP_INLINE_VISIBILITY
 713     void operator()(pointer __p) _NOEXCEPT
 714     {
 715         __alloc_traits::deallocate(__alloc(), __p, size());
 716     }
 717 };
 718
 719 template <class _Alloc> class __hash_map_node_destructor;
 720
 721 template <class _Alloc>
 722 class __hash_node_destructor
 723 {
 724     typedef _Alloc                                          allocator_type;
 725     typedef allocator_traits<allocator_type>                __alloc_traits;
 726     typedef typename __alloc_traits::value_type::value_type value_type;
 727 public:
 728     typedef typename __alloc_traits::pointer                pointer;
 729 private:
 730
 731     allocator_type& __na_;
 732
 733     __hash_node_destructor& operator=(const __hash_node_destructor&);
 734
 735 public:
 736     bool __value_constructed;
 737
 738     _LIBCPP_INLINE_VISIBILITY
 739     explicit __hash_node_destructor(allocator_type& __na,
 740                                     bool __constructed = false) _NOEXCEPT
 741         : __na_(__na),
 742           __value_constructed(__constructed)
 743         {}
 744
 745     _LIBCPP_INLINE_VISIBILITY
 746     void operator()(pointer __p) _NOEXCEPT
 747     {
 748         if (__value_constructed)
 749             __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
 750         if (__p)
 751             __alloc_traits::deallocate(__na_, __p, 1);
 752     }
 753
 754     template <class> friend class __hash_map_node_destructor;
 755 };
 756
 757 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 758 class __hash_table
 759 {
 760 public:
 761     typedef _Tp    value_type;
 762     typedef _Hash  hasher;
 763     typedef _Equal key_equal;
 764     typedef _Alloc allocator_type;
 765
 766 private:
 767     typedef allocator_traits<allocator_type> __alloc_traits;
 768 public:
 769     typedef value_type&                              reference;
 770     typedef const value_type&                        const_reference;
 771     typedef typename __alloc_traits::pointer         pointer;
 772     typedef typename __alloc_traits::const_pointer   const_pointer;
 773     typedef typename __alloc_traits::size_type       size_type;
 774     typedef typename __alloc_traits::difference_type difference_type;
 775 public:
 776     // Create __node
 777     typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node;
 778     typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator;
 779     typedef allocator_traits<__node_allocator>       __node_traits;
 780     typedef typename __node_traits::pointer          __node_pointer;
 781     typedef typename __node_traits::pointer          __node_const_pointer;
 782     typedef __hash_node_base<__node_pointer>         __first_node;
 783     typedef typename pointer_traits<__node_pointer>::template
 784 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
 785             rebind<__first_node>
 786 #else
 787             rebind<__first_node>::other
 788 #endif
 789                                                      __node_base_pointer;
 790
 791 private:
 792
 793     typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator;
 794     typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
 795     typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list;
 796     typedef allocator_traits<__pointer_allocator>          __pointer_alloc_traits;
 797     typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
 798
 799     // --- Member data begin ---
 800     __bucket_list                                     __bucket_list_;
 801     __compressed_pair<__first_node, __node_allocator> __p1_;
 802     __compressed_pair<size_type, hasher>              __p2_;
 803     __compressed_pair<float, key_equal>               __p3_;
 804     // --- Member data end ---
 805
 806     _LIBCPP_INLINE_VISIBILITY
 807     size_type& size() _NOEXCEPT {return __p2_.first();}
 808 public:
 809     _LIBCPP_INLINE_VISIBILITY
 810     size_type  size() const _NOEXCEPT {return __p2_.first();}
 811
 812     _LIBCPP_INLINE_VISIBILITY
 813     hasher& hash_function() _NOEXCEPT {return __p2_.second();}
 814     _LIBCPP_INLINE_VISIBILITY
 815     const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
 816
 817     _LIBCPP_INLINE_VISIBILITY
 818     float& max_load_factor() _NOEXCEPT {return __p3_.first();}
 819     _LIBCPP_INLINE_VISIBILITY
 820     float  max_load_factor() const _NOEXCEPT {return __p3_.first();}
 821
 822     _LIBCPP_INLINE_VISIBILITY
 823     key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
 824     _LIBCPP_INLINE_VISIBILITY
 825     const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
 826
 827     _LIBCPP_INLINE_VISIBILITY
 828     __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
 829     _LIBCPP_INLINE_VISIBILITY
 830     const __node_allocator& __node_alloc() const _NOEXCEPT
 831         {return __p1_.second();}
 832
 833 public:
 834     typedef __hash_iterator<__node_pointer>                   iterator;
 835     typedef __hash_const_iterator<__node_pointer>             const_iterator;
 836     typedef __hash_local_iterator<__node_pointer>             local_iterator;
 837     typedef __hash_const_local_iterator<__node_pointer>       const_local_iterator;
 838
 839     _LIBCPP_INLINE_VISIBILITY
 840     __hash_table()
 841         _NOEXCEPT_(
 842             is_nothrow_default_constructible<__bucket_list>::value &&
 843             is_nothrow_default_constructible<__first_node>::value &&
 844             is_nothrow_default_constructible<__node_allocator>::value &&
 845             is_nothrow_default_constructible<hasher>::value &&
 846             is_nothrow_default_constructible<key_equal>::value);
 847     _LIBCPP_INLINE_VISIBILITY
 848     __hash_table(const hasher& __hf, const key_equal& __eql);
 849     __hash_table(const hasher& __hf, const key_equal& __eql,
 850                  const allocator_type& __a);
 851     explicit __hash_table(const allocator_type& __a);
 852     __hash_table(const __hash_table& __u);
 853     __hash_table(const __hash_table& __u, const allocator_type& __a);
 854 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 855     __hash_table(__hash_table&& __u)
 856         _NOEXCEPT_(
 857             is_nothrow_move_constructible<__bucket_list>::value &&
 858             is_nothrow_move_constructible<__first_node>::value &&
 859             is_nothrow_move_constructible<__node_allocator>::value &&
 860             is_nothrow_move_constructible<hasher>::value &&
 861             is_nothrow_move_constructible<key_equal>::value);
 862     __hash_table(__hash_table&& __u, const allocator_type& __a);
 863 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 864     ~__hash_table();
 865
 866     __hash_table& operator=(const __hash_table& __u);
 867 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 868     _LIBCPP_INLINE_VISIBILITY
 869     __hash_table& operator=(__hash_table&& __u)
 870         _NOEXCEPT_(
 871             __node_traits::propagate_on_container_move_assignment::value &&
 872             is_nothrow_move_assignable<__node_allocator>::value &&
 873             is_nothrow_move_assignable<hasher>::value &&
 874             is_nothrow_move_assignable<key_equal>::value);
 875 #endif
 876     template <class _InputIterator>
 877         void __assign_unique(_InputIterator __first, _InputIterator __last);
 878     template <class _InputIterator>
 879         void __assign_multi(_InputIterator __first, _InputIterator __last);
 880
 881     _LIBCPP_INLINE_VISIBILITY
 882     size_type max_size() const _NOEXCEPT
 883     {
 884         return allocator_traits<__pointer_allocator>::max_size(
 885             __bucket_list_.get_deleter().__alloc());
 886     }
 887
 888     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
 889     iterator             __node_insert_multi(__node_pointer __nd);
 890     iterator             __node_insert_multi(const_iterator __p,
 891                                              __node_pointer __nd);
 892
 893 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 894     template <class... _Args>
 895         pair<iterator, bool> __emplace_unique(_Args&&... __args);
 896     template <class... _Args>
 897         iterator __emplace_multi(_Args&&... __args);
 898     template <class... _Args>
 899         iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
 900 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
 901
 902 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 903     template <class _ValueTp>
 904     _LIBCPP_INLINE_VISIBILITY
 905     pair<iterator, bool> __insert_unique_value(_ValueTp&& __x);
 906 #else
 907     _LIBCPP_INLINE_VISIBILITY
 908     pair<iterator, bool> __insert_unique_value(const value_type& __x);
 909 #endif
 910
 911     pair<iterator, bool> __insert_unique(const value_type& __x);
 912
 913 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 914     pair<iterator, bool> __insert_unique(value_type&& __x);
 915     template <class _Pp>
 916     pair<iterator, bool> __insert_unique(_Pp&& __x);
 917 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 918
 919 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 920     template <class _Pp>
 921         iterator __insert_multi(_Pp&& __x);
 922     template <class _Pp>
 923         iterator __insert_multi(const_iterator __p, _Pp&& __x);
 924 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 925     iterator __insert_multi(const value_type& __x);
 926     iterator __insert_multi(const_iterator __p, const value_type& __x);
 927 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 928
 929     void clear() _NOEXCEPT;
 930     void rehash(size_type __n);
 931     _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
 932         {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
 933
 934     _LIBCPP_INLINE_VISIBILITY
 935     size_type bucket_count() const _NOEXCEPT
 936     {
 937         return __bucket_list_.get_deleter().size();
 938     }
 939
 940     _LIBCPP_INLINE_VISIBILITY
 941     iterator       begin() _NOEXCEPT;
 942     _LIBCPP_INLINE_VISIBILITY
 943     iterator       end() _NOEXCEPT;
 944     _LIBCPP_INLINE_VISIBILITY
 945     const_iterator begin() const _NOEXCEPT;
 946     _LIBCPP_INLINE_VISIBILITY
 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         _LIBCPP_INLINE_VISIBILITY
 976         size_type __count_unique(const _Key& __k) const;
 977     template <class _Key>
 978         size_type __count_multi(const _Key& __k) const;
 979
 980     template <class _Key>
 981         pair<iterator, iterator>
 982         __equal_range_unique(const _Key& __k);
 983     template <class _Key>
 984         pair<const_iterator, const_iterator>
 985         __equal_range_unique(const _Key& __k) const;
 986
 987     template <class _Key>
 988         pair<iterator, iterator>
 989         __equal_range_multi(const _Key& __k);
 990     template <class _Key>
 991         pair<const_iterator, const_iterator>
 992         __equal_range_multi(const _Key& __k) const;
 993
 994     void swap(__hash_table& __u)
 995 #if _LIBCPP_STD_VER <= 11
 996         _NOEXCEPT_(
 997             __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
 998             && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
 999                   || __is_nothrow_swappable<__pointer_allocator>::value)
1000             && (!__node_traits::propagate_on_container_swap::value
1001                   || __is_nothrow_swappable<__node_allocator>::value)
1002             );
1003 #else
1004      _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value);
1005 #endif
1006
1007     _LIBCPP_INLINE_VISIBILITY
1008     size_type max_bucket_count() const _NOEXCEPT
1009         {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());}
1010     size_type bucket_size(size_type __n) const;
1011     _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
1012     {
1013         size_type __bc = bucket_count();
1014         return __bc != 0 ? (float)size() / __bc : 0.f;
1015     }
1016     _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
1017     {
1018         _LIBCPP_ASSERT(__mlf > 0,
1019             "unordered container::max_load_factor(lf) called with lf <= 0");
1020         max_load_factor() = _VSTD::max(__mlf, load_factor());
1021     }
1022
1023     _LIBCPP_INLINE_VISIBILITY
1024     local_iterator
1025     begin(size_type __n)
1026     {
1027         _LIBCPP_ASSERT(__n < bucket_count(),
1028             "unordered container::begin(n) called with n >= bucket_count()");
1029 #if _LIBCPP_DEBUG_LEVEL >= 2
1030         return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1031 #else
1032         return local_iterator(__bucket_list_[__n], __n, bucket_count());
1033 #endif
1034     }
1035
1036     _LIBCPP_INLINE_VISIBILITY
1037     local_iterator
1038     end(size_type __n)
1039     {
1040         _LIBCPP_ASSERT(__n < bucket_count(),
1041             "unordered container::end(n) called with n >= bucket_count()");
1042 #if _LIBCPP_DEBUG_LEVEL >= 2
1043         return local_iterator(nullptr, __n, bucket_count(), this);
1044 #else
1045         return local_iterator(nullptr, __n, bucket_count());
1046 #endif
1047     }
1048
1049     _LIBCPP_INLINE_VISIBILITY
1050     const_local_iterator
1051     cbegin(size_type __n) const
1052     {
1053         _LIBCPP_ASSERT(__n < bucket_count(),
1054             "unordered container::cbegin(n) called with n >= bucket_count()");
1055 #if _LIBCPP_DEBUG_LEVEL >= 2
1056         return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1057 #else
1058         return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1059 #endif
1060     }
1061
1062     _LIBCPP_INLINE_VISIBILITY
1063     const_local_iterator
1064     cend(size_type __n) const
1065     {
1066         _LIBCPP_ASSERT(__n < bucket_count(),
1067             "unordered container::cend(n) called with n >= bucket_count()");
1068 #if _LIBCPP_DEBUG_LEVEL >= 2
1069         return const_local_iterator(nullptr, __n, bucket_count(), this);
1070 #else
1071         return const_local_iterator(nullptr, __n, bucket_count());
1072 #endif
1073     }
1074
1075 #if _LIBCPP_DEBUG_LEVEL >= 2
1076
1077     bool __dereferenceable(const const_iterator* __i) const;
1078     bool __decrementable(const const_iterator* __i) const;
1079     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1080     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1081
1082 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1083
1084 private:
1085     void __rehash(size_type __n);
1086
1087 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1088 #ifndef _LIBCPP_HAS_NO_VARIADICS
1089     template <class ..._Args>
1090         __node_holder __construct_node(_Args&& ...__args);
1091 #endif  // _LIBCPP_HAS_NO_VARIADICS
1092     __node_holder __construct_node(value_type&& __v, size_t __hash);
1093 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1094     __node_holder __construct_node(const value_type& __v);
1095 #endif
1096     __node_holder __construct_node(const value_type& __v, size_t __hash);
1097
1098     _LIBCPP_INLINE_VISIBILITY
1099     void __copy_assign_alloc(const __hash_table& __u)
1100         {__copy_assign_alloc(__u, integral_constant<bool,
1101              __node_traits::propagate_on_container_copy_assignment::value>());}
1102     void __copy_assign_alloc(const __hash_table& __u, true_type);
1103     _LIBCPP_INLINE_VISIBILITY
1104         void __copy_assign_alloc(const __hash_table&, false_type) {}
1105
1106     void __move_assign(__hash_table& __u, false_type);
1107     void __move_assign(__hash_table& __u, true_type)
1108         _NOEXCEPT_(
1109             is_nothrow_move_assignable<__node_allocator>::value &&
1110             is_nothrow_move_assignable<hasher>::value &&
1111             is_nothrow_move_assignable<key_equal>::value);
1112     _LIBCPP_INLINE_VISIBILITY
1113     void __move_assign_alloc(__hash_table& __u)
1114         _NOEXCEPT_(
1115             !__node_traits::propagate_on_container_move_assignment::value ||
1116             (is_nothrow_move_assignable<__pointer_allocator>::value &&
1117              is_nothrow_move_assignable<__node_allocator>::value))
1118         {__move_assign_alloc(__u, integral_constant<bool,
1119              __node_traits::propagate_on_container_move_assignment::value>());}
1120     _LIBCPP_INLINE_VISIBILITY
1121     void __move_assign_alloc(__hash_table& __u, true_type)
1122         _NOEXCEPT_(
1123             is_nothrow_move_assignable<__pointer_allocator>::value &&
1124             is_nothrow_move_assignable<__node_allocator>::value)
1125     {
1126         __bucket_list_.get_deleter().__alloc() =
1127                 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1128         __node_alloc() = _VSTD::move(__u.__node_alloc());
1129     }
1130     _LIBCPP_INLINE_VISIBILITY
1131         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1132
1133     void __deallocate(__node_pointer __np) _NOEXCEPT;
1134     __node_pointer __detach() _NOEXCEPT;
1135
1136     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
1137     template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
1138 };
1139
1140 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1141 inline
1142 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
1143     _NOEXCEPT_(
1144         is_nothrow_default_constructible<__bucket_list>::value &&
1145         is_nothrow_default_constructible<__first_node>::value &&
1146         is_nothrow_default_constructible<hasher>::value &&
1147         is_nothrow_default_constructible<key_equal>::value)
1148     : __p2_(0),
1149       __p3_(1.0f)
1150 {
1151 }
1152
1153 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1154 inline
1155 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1156                                                        const key_equal& __eql)
1157     : __bucket_list_(nullptr, __bucket_list_deleter()),
1158       __p1_(),
1159       __p2_(0, __hf),
1160       __p3_(1.0f, __eql)
1161 {
1162 }
1163
1164 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1165 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1166                                                        const key_equal& __eql,
1167                                                        const allocator_type& __a)
1168     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1169       __p1_(__node_allocator(__a)),
1170       __p2_(0, __hf),
1171       __p3_(1.0f, __eql)
1172 {
1173 }
1174
1175 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1176 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1177     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1178       __p1_(__node_allocator(__a)),
1179       __p2_(0),
1180       __p3_(1.0f)
1181 {
1182 }
1183
1184 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1185 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1186     : __bucket_list_(nullptr,
1187           __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1188               select_on_container_copy_construction(
1189                   __u.__bucket_list_.get_deleter().__alloc()), 0)),
1190       __p1_(allocator_traits<__node_allocator>::
1191           select_on_container_copy_construction(__u.__node_alloc())),
1192       __p2_(0, __u.hash_function()),
1193       __p3_(__u.__p3_)
1194 {
1195 }
1196
1197 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1198 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1199                                                        const allocator_type& __a)
1200     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1201       __p1_(__node_allocator(__a)),
1202       __p2_(0, __u.hash_function()),
1203       __p3_(__u.__p3_)
1204 {
1205 }
1206
1207 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1208
1209 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1210 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
1211         _NOEXCEPT_(
1212             is_nothrow_move_constructible<__bucket_list>::value &&
1213             is_nothrow_move_constructible<__first_node>::value &&
1214             is_nothrow_move_constructible<hasher>::value &&
1215             is_nothrow_move_constructible<key_equal>::value)
1216     : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1217       __p1_(_VSTD::move(__u.__p1_)),
1218       __p2_(_VSTD::move(__u.__p2_)),
1219       __p3_(_VSTD::move(__u.__p3_))
1220 {
1221     if (size() > 0)
1222     {
1223         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1224             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1225         __u.__p1_.first().__next_ = nullptr;
1226         __u.size() = 0;
1227     }
1228 }
1229
1230 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1231 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1232                                                        const allocator_type& __a)
1233     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1234       __p1_(__node_allocator(__a)),
1235       __p2_(0, _VSTD::move(__u.hash_function())),
1236       __p3_(_VSTD::move(__u.__p3_))
1237 {
1238     if (__a == allocator_type(__u.__node_alloc()))
1239     {
1240         __bucket_list_.reset(__u.__bucket_list_.release());
1241         __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1242         __u.__bucket_list_.get_deleter().size() = 0;
1243         if (__u.size() > 0)
1244         {
1245             __p1_.first().__next_ = __u.__p1_.first().__next_;
1246             __u.__p1_.first().__next_ = nullptr;
1247             __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1248                 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1249             size() = __u.size();
1250             __u.size() = 0;
1251         }
1252     }
1253 }
1254
1255 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1256
1257 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1258 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1259 {
1260     __deallocate(__p1_.first().__next_);
1261 #if _LIBCPP_DEBUG_LEVEL >= 2
1262     __get_db()->__erase_c(this);
1263 #endif
1264 }
1265
1266 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1267 void
1268 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1269         const __hash_table& __u, true_type)
1270 {
1271     if (__node_alloc() != __u.__node_alloc())
1272     {
1273         clear();
1274         __bucket_list_.reset();
1275         __bucket_list_.get_deleter().size() = 0;
1276     }
1277     __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1278     __node_alloc() = __u.__node_alloc();
1279 }
1280
1281 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1282 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1283 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1284 {
1285     if (this != &__u)
1286     {
1287         __copy_assign_alloc(__u);
1288         hash_function() = __u.hash_function();
1289         key_eq() = __u.key_eq();
1290         max_load_factor() = __u.max_load_factor();
1291         __assign_multi(__u.begin(), __u.end());
1292     }
1293     return *this;
1294 }
1295
1296 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1297 void
1298 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
1299     _NOEXCEPT
1300 {
1301     __node_allocator& __na = __node_alloc();
1302     while (__np != nullptr)
1303     {
1304         __node_pointer __next = __np->__next_;
1305 #if _LIBCPP_DEBUG_LEVEL >= 2
1306         __c_node* __c = __get_db()->__find_c_and_lock(this);
1307         for (__i_node** __p = __c->end_; __p != __c->beg_; )
1308         {
1309             --__p;
1310             iterator* __i = static_cast<iterator*>((*__p)->__i_);
1311             if (__i->__node_ == __np)
1312             {
1313                 (*__p)->__c_ = nullptr;
1314                 if (--__c->end_ != __p)
1315                     memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1316             }
1317         }
1318         __get_db()->unlock();
1319 #endif
1320         __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1321         __node_traits::deallocate(__na, __np, 1);
1322         __np = __next;
1323     }
1324 }
1325
1326 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1327 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
1328 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
1329 {
1330     size_type __bc = bucket_count();
1331     for (size_type __i = 0; __i < __bc; ++__i)
1332         __bucket_list_[__i] = nullptr;
1333     size() = 0;
1334     __node_pointer __cache = __p1_.first().__next_;
1335     __p1_.first().__next_ = nullptr;
1336     return __cache;
1337 }
1338
1339 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1340
1341 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1342 void
1343 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1344         __hash_table& __u, true_type)
1345     _NOEXCEPT_(
1346         is_nothrow_move_assignable<__node_allocator>::value &&
1347         is_nothrow_move_assignable<hasher>::value &&
1348         is_nothrow_move_assignable<key_equal>::value)
1349 {
1350     clear();
1351     __bucket_list_.reset(__u.__bucket_list_.release());
1352     __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1353     __u.__bucket_list_.get_deleter().size() = 0;
1354     __move_assign_alloc(__u);
1355     size() = __u.size();
1356     hash_function() = _VSTD::move(__u.hash_function());
1357     max_load_factor() = __u.max_load_factor();
1358     key_eq() = _VSTD::move(__u.key_eq());
1359     __p1_.first().__next_ = __u.__p1_.first().__next_;
1360     if (size() > 0)
1361     {
1362         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1363             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1364         __u.__p1_.first().__next_ = nullptr;
1365         __u.size() = 0;
1366     }
1367 #if _LIBCPP_DEBUG_LEVEL >= 2
1368     __get_db()->swap(this, &__u);
1369 #endif
1370 }
1371
1372 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1373 void
1374 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1375         __hash_table& __u, false_type)
1376 {
1377     if (__node_alloc() == __u.__node_alloc())
1378         __move_assign(__u, true_type());
1379     else
1380     {
1381         hash_function() = _VSTD::move(__u.hash_function());
1382         key_eq() = _VSTD::move(__u.key_eq());
1383         max_load_factor() = __u.max_load_factor();
1384         if (bucket_count() != 0)
1385         {
1386             __node_pointer __cache = __detach();
1387 #ifndef _LIBCPP_NO_EXCEPTIONS
1388             try
1389             {
1390 #endif  // _LIBCPP_NO_EXCEPTIONS
1391                 const_iterator __i = __u.begin();
1392                 while (__cache != nullptr && __u.size() != 0)
1393                 {
1394                     __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_);
1395                     __node_pointer __next = __cache->__next_;
1396                     __node_insert_multi(__cache);
1397                     __cache = __next;
1398                 }
1399 #ifndef _LIBCPP_NO_EXCEPTIONS
1400             }
1401             catch (...)
1402             {
1403                 __deallocate(__cache);
1404                 throw;
1405             }
1406 #endif  // _LIBCPP_NO_EXCEPTIONS
1407             __deallocate(__cache);
1408         }
1409         const_iterator __i = __u.begin();
1410         while (__u.size() != 0)
1411         {
1412             __node_holder __h =
1413                     __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
1414             __node_insert_multi(__h.get());
1415             __h.release();
1416         }
1417     }
1418 }
1419
1420 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1421 inline
1422 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1423 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1424     _NOEXCEPT_(
1425         __node_traits::propagate_on_container_move_assignment::value &&
1426         is_nothrow_move_assignable<__node_allocator>::value &&
1427         is_nothrow_move_assignable<hasher>::value &&
1428         is_nothrow_move_assignable<key_equal>::value)
1429 {
1430     __move_assign(__u, integral_constant<bool,
1431                   __node_traits::propagate_on_container_move_assignment::value>());
1432     return *this;
1433 }
1434
1435 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1436
1437 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1438 template <class _InputIterator>
1439 void
1440 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1441                                                           _InputIterator __last)
1442 {
1443     if (bucket_count() != 0)
1444     {
1445         __node_pointer __cache = __detach();
1446 #ifndef _LIBCPP_NO_EXCEPTIONS
1447         try
1448         {
1449 #endif  // _LIBCPP_NO_EXCEPTIONS
1450             for (; __cache != nullptr && __first != __last; ++__first)
1451             {
1452                 __cache->__value_ = *__first;
1453                 __node_pointer __next = __cache->__next_;
1454                 __node_insert_unique(__cache);
1455                 __cache = __next;
1456             }
1457 #ifndef _LIBCPP_NO_EXCEPTIONS
1458         }
1459         catch (...)
1460         {
1461             __deallocate(__cache);
1462             throw;
1463         }
1464 #endif  // _LIBCPP_NO_EXCEPTIONS
1465         __deallocate(__cache);
1466     }
1467     for (; __first != __last; ++__first)
1468         __insert_unique(*__first);
1469 }
1470
1471 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1472 template <class _InputIterator>
1473 void
1474 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1475                                                          _InputIterator __last)
1476 {
1477     if (bucket_count() != 0)
1478     {
1479         __node_pointer __cache = __detach();
1480 #ifndef _LIBCPP_NO_EXCEPTIONS
1481         try
1482         {
1483 #endif  // _LIBCPP_NO_EXCEPTIONS
1484             for (; __cache != nullptr && __first != __last; ++__first)
1485             {
1486                 __cache->__value_ = *__first;
1487                 __node_pointer __next = __cache->__next_;
1488                 __node_insert_multi(__cache);
1489                 __cache = __next;
1490             }
1491 #ifndef _LIBCPP_NO_EXCEPTIONS
1492         }
1493         catch (...)
1494         {
1495             __deallocate(__cache);
1496             throw;
1497         }
1498 #endif  // _LIBCPP_NO_EXCEPTIONS
1499         __deallocate(__cache);
1500     }
1501     for (; __first != __last; ++__first)
1502         __insert_multi(*__first);
1503 }
1504
1505 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1506 inline
1507 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1508 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1509 {
1510 #if _LIBCPP_DEBUG_LEVEL >= 2
1511     return iterator(__p1_.first().__next_, this);
1512 #else
1513     return iterator(__p1_.first().__next_);
1514 #endif
1515 }
1516
1517 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1518 inline
1519 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1520 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1521 {
1522 #if _LIBCPP_DEBUG_LEVEL >= 2
1523     return iterator(nullptr, this);
1524 #else
1525     return iterator(nullptr);
1526 #endif
1527 }
1528
1529 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1530 inline
1531 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1532 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1533 {
1534 #if _LIBCPP_DEBUG_LEVEL >= 2
1535     return const_iterator(__p1_.first().__next_, this);
1536 #else
1537     return const_iterator(__p1_.first().__next_);
1538 #endif
1539 }
1540
1541 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1542 inline
1543 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1544 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1545 {
1546 #if _LIBCPP_DEBUG_LEVEL >= 2
1547     return const_iterator(nullptr, this);
1548 #else
1549     return const_iterator(nullptr);
1550 #endif
1551 }
1552
1553 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1554 void
1555 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1556 {
1557     if (size() > 0)
1558     {
1559         __deallocate(__p1_.first().__next_);
1560         __p1_.first().__next_ = nullptr;
1561         size_type __bc = bucket_count();
1562         for (size_type __i = 0; __i < __bc; ++__i)
1563             __bucket_list_[__i] = nullptr;
1564         size() = 0;
1565     }
1566 }
1567
1568 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1569 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1570 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1571 {
1572     __nd->__hash_ = hash_function()(__nd->__value_);
1573     size_type __bc = bucket_count();
1574     bool __inserted = false;
1575     __node_pointer __ndptr;
1576     size_t __chash;
1577     if (__bc != 0)
1578     {
1579         __chash = __constrain_hash(__nd->__hash_, __bc);
1580         __ndptr = __bucket_list_[__chash];
1581         if (__ndptr != nullptr)
1582         {
1583             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1584                                              __constrain_hash(__ndptr->__hash_, __bc) == __chash;
1585                                                      __ndptr = __ndptr->__next_)
1586             {
1587                 if (key_eq()(__ndptr->__value_, __nd->__value_))
1588                     goto __done;
1589             }
1590         }
1591     }
1592     {
1593         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1594         {
1595             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1596                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1597             __bc = bucket_count();
1598             __chash = __constrain_hash(__nd->__hash_, __bc);
1599         }
1600         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1601         __node_pointer __pn = __bucket_list_[__chash];
1602         if (__pn == nullptr)
1603         {
1604             __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1605             __nd->__next_ = __pn->__next_;
1606             __pn->__next_ = __nd;
1607             // fix up __bucket_list_
1608             __bucket_list_[__chash] = __pn;
1609             if (__nd->__next_ != nullptr)
1610                 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd;
1611         }
1612         else
1613         {
1614             __nd->__next_ = __pn->__next_;
1615             __pn->__next_ = __nd;
1616         }
1617         __ndptr = __nd;
1618         // increment size
1619         ++size();
1620         __inserted = true;
1621     }
1622 __done:
1623 #if _LIBCPP_DEBUG_LEVEL >= 2
1624     return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
1625 #else
1626     return pair<iterator, bool>(iterator(__ndptr), __inserted);
1627 #endif
1628 }
1629
1630 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1631 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1632 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1633 {
1634     __cp->__hash_ = hash_function()(__cp->__value_);
1635     size_type __bc = bucket_count();
1636     if (size()+1 > __bc * max_load_factor() || __bc == 0)
1637     {
1638         rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1639                        size_type(ceil(float(size() + 1) / max_load_factor()))));
1640         __bc = bucket_count();
1641     }
1642     size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1643     __node_pointer __pn = __bucket_list_[__chash];
1644     if (__pn == nullptr)
1645     {
1646         __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1647         __cp->__next_ = __pn->__next_;
1648         __pn->__next_ = __cp;
1649         // fix up __bucket_list_
1650         __bucket_list_[__chash] = __pn;
1651         if (__cp->__next_ != nullptr)
1652             __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp;
1653     }
1654     else
1655     {
1656         for (bool __found = false; __pn->__next_ != nullptr &&
1657                                    __constrain_hash(__pn->__next_->__hash_, __bc) == __chash;
1658                                                            __pn = __pn->__next_)
1659         {
1660             //      __found    key_eq()     action
1661             //      false       false       loop
1662             //      true        true        loop
1663             //      false       true        set __found to true
1664             //      true        false       break
1665             if (__found != (__pn->__next_->__hash_ == __cp->__hash_ &&
1666                             key_eq()(__pn->__next_->__value_, __cp->__value_)))
1667             {
1668                 if (!__found)
1669                     __found = true;
1670                 else
1671                     break;
1672             }
1673         }
1674         __cp->__next_ = __pn->__next_;
1675         __pn->__next_ = __cp;
1676         if (__cp->__next_ != nullptr)
1677         {
1678             size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc);
1679             if (__nhash != __chash)
1680                 __bucket_list_[__nhash] = __cp;
1681         }
1682     }
1683     ++size();
1684 #if _LIBCPP_DEBUG_LEVEL >= 2
1685     return iterator(__cp, this);
1686 #else
1687     return iterator(__cp);
1688 #endif
1689 }
1690
1691 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1692 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1693 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1694         const_iterator __p, __node_pointer __cp)
1695 {
1696 #if _LIBCPP_DEBUG_LEVEL >= 2
1697     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1698         "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1699         " referring to this unordered container");
1700 #endif
1701     if (__p != end() && key_eq()(*__p, __cp->__value_))
1702     {
1703         __node_pointer __np = __p.__node_;
1704         __cp->__hash_ = __np->__hash_;
1705         size_type __bc = bucket_count();
1706         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1707         {
1708             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1709                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1710             __bc = bucket_count();
1711         }
1712         size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1713         __node_pointer __pp = __bucket_list_[__chash];
1714         while (__pp->__next_ != __np)
1715             __pp = __pp->__next_;
1716         __cp->__next_ = __np;
1717         __pp->__next_ = __cp;
1718         ++size();
1719 #if _LIBCPP_DEBUG_LEVEL >= 2
1720         return iterator(__cp, this);
1721 #else
1722         return iterator(__cp);
1723 #endif
1724     }
1725     return __node_insert_multi(__cp);
1726 }
1727
1728 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1729 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1730 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
1731 {
1732     return __insert_unique_value(__x);
1733 }
1734
1735
1736 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1737 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1738 template <class _ValueTp>
1739 _LIBCPP_INLINE_VISIBILITY
1740 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1741 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x)
1742 #else
1743 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1744 _LIBCPP_INLINE_VISIBILITY
1745 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1746 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x)
1747 #endif
1748 {
1749 #if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
1750     typedef const value_type& _ValueTp;
1751 #endif
1752     size_t __hash = hash_function()(__x);
1753     size_type __bc = bucket_count();
1754     bool __inserted = false;
1755     __node_pointer __nd;
1756     size_t __chash;
1757     if (__bc != 0)
1758     {
1759         __chash = __constrain_hash(__hash, __bc);
1760         __nd = __bucket_list_[__chash];
1761         if (__nd != nullptr)
1762         {
1763             for (__nd = __nd->__next_; __nd != nullptr &&
1764                                        __constrain_hash(__nd->__hash_, __bc) == __chash;
1765                                                            __nd = __nd->__next_)
1766             {
1767                 if (key_eq()(__nd->__value_, __x))
1768                     goto __done;
1769             }
1770         }
1771     }
1772     {
1773         __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash);
1774         if (size()+1 > __bc * max_load_factor() || __bc == 0)
1775         {
1776             rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
1777                            size_type(ceil(float(size() + 1) / max_load_factor()))));
1778             __bc = bucket_count();
1779             __chash = __constrain_hash(__hash, __bc);
1780         }
1781         // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1782         __node_pointer __pn = __bucket_list_[__chash];
1783         if (__pn == nullptr)
1784         {
1785             __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1786             __h->__next_ = __pn->__next_;
1787             __pn->__next_ = __h.get();
1788             // fix up __bucket_list_
1789             __bucket_list_[__chash] = __pn;
1790             if (__h->__next_ != nullptr)
1791                 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get();
1792         }
1793         else
1794         {
1795             __h->__next_ = __pn->__next_;
1796             __pn->__next_ = __h.get();
1797         }
1798         __nd = __h.release();
1799         // increment size
1800         ++size();
1801         __inserted = true;
1802     }
1803 __done:
1804 #if _LIBCPP_DEBUG_LEVEL >= 2
1805     return pair<iterator, bool>(iterator(__nd, this), __inserted);
1806 #else
1807     return pair<iterator, bool>(iterator(__nd), __inserted);
1808 #endif
1809 }
1810
1811 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1812 #ifndef _LIBCPP_HAS_NO_VARIADICS
1813
1814 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1815 template <class... _Args>
1816 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1817 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args)
1818 {
1819     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1820     pair<iterator, bool> __r = __node_insert_unique(__h.get());
1821     if (__r.second)
1822         __h.release();
1823     return __r;
1824 }
1825
1826 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1827 template <class... _Args>
1828 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1829 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
1830 {
1831     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1832     iterator __r = __node_insert_multi(__h.get());
1833     __h.release();
1834     return __r;
1835 }
1836
1837 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1838 template <class... _Args>
1839 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1840 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
1841         const_iterator __p, _Args&&... __args)
1842 {
1843 #if _LIBCPP_DEBUG_LEVEL >= 2
1844     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1845         "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1846         " referring to this unordered container");
1847 #endif
1848     __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1849     iterator __r = __node_insert_multi(__p, __h.get());
1850     __h.release();
1851     return __r;
1852 }
1853
1854 #endif  // _LIBCPP_HAS_NO_VARIADICS
1855
1856 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1857 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1858 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x)
1859 {
1860     return __insert_unique_value(_VSTD::move(__x));
1861 }
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_hash_power2(__bc) ? __next_hash_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 _LIBCPP_EXPLICIT_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 _LIBCPP_EXPLICIT_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
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 #if _LIBCPP_STD_VER <= 11
2365     _NOEXCEPT_(
2366         __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value
2367         && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value
2368               || __is_nothrow_swappable<__pointer_allocator>::value)
2369         && (!__node_traits::propagate_on_container_swap::value
2370               || __is_nothrow_swappable<__node_allocator>::value)
2371             )
2372 #else
2373   _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value)
2374 #endif
2375 {
2376     {
2377     __node_pointer_pointer __npp = __bucket_list_.release();
2378     __bucket_list_.reset(__u.__bucket_list_.release());
2379     __u.__bucket_list_.reset(__npp);
2380     }
2381     _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2382     __swap_allocator(__bucket_list_.get_deleter().__alloc(),
2383              __u.__bucket_list_.get_deleter().__alloc());
2384     __swap_allocator(__node_alloc(), __u.__node_alloc());
2385     _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
2386     __p2_.swap(__u.__p2_);
2387     __p3_.swap(__u.__p3_);
2388     if (size() > 0)
2389         __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
2390             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
2391     if (__u.size() > 0)
2392         __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
2393             static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
2394 #if _LIBCPP_DEBUG_LEVEL >= 2
2395     __get_db()->swap(this, &__u);
2396 #endif
2397 }
2398
2399 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2400 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2401 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2402 {
2403     _LIBCPP_ASSERT(__n < bucket_count(),
2404         "unordered container::bucket_size(n) called with n >= bucket_count()");
2405     __node_const_pointer __np = __bucket_list_[__n];
2406     size_type __bc = bucket_count();
2407     size_type __r = 0;
2408     if (__np != nullptr)
2409     {
2410         for (__np = __np->__next_; __np != nullptr &&
2411                                    __constrain_hash(__np->__hash_, __bc) == __n;
2412                                                     __np = __np->__next_, ++__r)
2413             ;
2414     }
2415     return __r;
2416 }
2417
2418 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2419 inline _LIBCPP_INLINE_VISIBILITY
2420 void
2421 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2422      __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2423     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2424 {
2425     __x.swap(__y);
2426 }
2427
2428 #if _LIBCPP_DEBUG_LEVEL >= 2
2429
2430 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2431 bool
2432 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
2433 {
2434     return __i->__node_ != nullptr;
2435 }
2436
2437 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2438 bool
2439 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
2440 {
2441     return false;
2442 }
2443
2444 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2445 bool
2446 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2447 {
2448     return false;
2449 }
2450
2451 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2452 bool
2453 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2454 {
2455     return false;
2456 }
2457
2458 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
2459 _LIBCPP_END_NAMESPACE_STD
2460
2461 #endif  // _LIBCPP__HASH_TABLE