1227825Stheraven// -*- C++ -*- 2227825Stheraven//===----------------------------------------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP__HASH_TABLE 12227825Stheraven#define _LIBCPP__HASH_TABLE 13227825Stheraven 14227825Stheraven#include <__config> 15227825Stheraven#include <initializer_list> 16227825Stheraven#include <memory> 17227825Stheraven#include <iterator> 18227825Stheraven#include <algorithm> 19227825Stheraven#include <cmath> 20227825Stheraven 21232924Stheraven#include <__undef_min_max> 22288943Sdim#include <__undef___deallocate> 23232924Stheraven 24276792Sdim#include <__debug> 25261272Sdim 26227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27227825Stheraven#pragma GCC system_header 28227825Stheraven#endif 29227825Stheraven 30227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 31227825Stheraven 32249989Sdim_LIBCPP_FUNC_VIS 33227825Stheravensize_t __next_prime(size_t __n); 34227825Stheraven 35227825Stheraventemplate <class _NodePtr> 36227825Stheravenstruct __hash_node_base 37227825Stheraven{ 38227825Stheraven typedef __hash_node_base __first_node; 39227825Stheraven 40227825Stheraven _NodePtr __next_; 41227825Stheraven 42227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 43227825Stheraven}; 44227825Stheraven 45227825Stheraventemplate <class _Tp, class _VoidPtr> 46227825Stheravenstruct __hash_node 47227825Stheraven : public __hash_node_base 48227825Stheraven < 49300770Sdim typename __rebind_pointer<_VoidPtr, __hash_node<_Tp, _VoidPtr> >::type 50227825Stheraven > 51227825Stheraven{ 52227825Stheraven typedef _Tp value_type; 53227825Stheraven 54227825Stheraven size_t __hash_; 55227825Stheraven value_type __value_; 56227825Stheraven}; 57227825Stheraven 58241900Sdiminline _LIBCPP_INLINE_VISIBILITY 59241900Sdimbool 60288943Sdim__is_hash_power2(size_t __bc) 61241900Sdim{ 62241900Sdim return __bc > 2 && !(__bc & (__bc - 1)); 63241900Sdim} 64241900Sdim 65241900Sdiminline _LIBCPP_INLINE_VISIBILITY 66241900Sdimsize_t 67241900Sdim__constrain_hash(size_t __h, size_t __bc) 68241900Sdim{ 69241900Sdim return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 70241900Sdim} 71241900Sdim 72241900Sdiminline _LIBCPP_INLINE_VISIBILITY 73241900Sdimsize_t 74288943Sdim__next_hash_pow2(size_t __n) 75241900Sdim{ 76241900Sdim return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 77241900Sdim} 78241900Sdim 79227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 80261272Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 81261272Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 82261272Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 83227825Stheraven 84227825Stheraventemplate <class _NodePtr> 85261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_iterator 86227825Stheraven{ 87227825Stheraven typedef _NodePtr __node_pointer; 88227825Stheraven 89227825Stheraven __node_pointer __node_; 90227825Stheraven 91227825Stheravenpublic: 92227825Stheraven typedef forward_iterator_tag iterator_category; 93227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 94227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 95227825Stheraven typedef value_type& reference; 96300770Sdim typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; 97227825Stheraven 98261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 99261272Sdim#if _LIBCPP_STD_VER > 11 100261272Sdim : __node_(nullptr) 101261272Sdim#endif 102261272Sdim { 103261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 104261272Sdim __get_db()->__insert_i(this); 105261272Sdim#endif 106261272Sdim } 107227825Stheraven 108261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 109261272Sdim 110227825Stheraven _LIBCPP_INLINE_VISIBILITY 111261272Sdim __hash_iterator(const __hash_iterator& __i) 112261272Sdim : __node_(__i.__node_) 113261272Sdim { 114261272Sdim __get_db()->__iterator_copy(this, &__i); 115261272Sdim } 116261272Sdim 117227825Stheraven _LIBCPP_INLINE_VISIBILITY 118261272Sdim ~__hash_iterator() 119261272Sdim { 120261272Sdim __get_db()->__erase_i(this); 121261272Sdim } 122227825Stheraven 123227825Stheraven _LIBCPP_INLINE_VISIBILITY 124261272Sdim __hash_iterator& operator=(const __hash_iterator& __i) 125261272Sdim { 126261272Sdim if (this != &__i) 127261272Sdim { 128261272Sdim __get_db()->__iterator_copy(this, &__i); 129261272Sdim __node_ = __i.__node_; 130261272Sdim } 131261272Sdim return *this; 132261272Sdim } 133261272Sdim 134261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 135261272Sdim 136261272Sdim _LIBCPP_INLINE_VISIBILITY 137261272Sdim reference operator*() const 138261272Sdim { 139261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 140261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 141261272Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 142261272Sdim#endif 143261272Sdim return __node_->__value_; 144261272Sdim } 145261272Sdim _LIBCPP_INLINE_VISIBILITY 146261272Sdim pointer operator->() const 147261272Sdim { 148261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 149261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 150261272Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 151261272Sdim#endif 152261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 153261272Sdim } 154261272Sdim 155261272Sdim _LIBCPP_INLINE_VISIBILITY 156227825Stheraven __hash_iterator& operator++() 157227825Stheraven { 158261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 159261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 160261272Sdim "Attempted to increment non-incrementable unordered container iterator"); 161261272Sdim#endif 162227825Stheraven __node_ = __node_->__next_; 163227825Stheraven return *this; 164227825Stheraven } 165227825Stheraven 166227825Stheraven _LIBCPP_INLINE_VISIBILITY 167227825Stheraven __hash_iterator operator++(int) 168227825Stheraven { 169227825Stheraven __hash_iterator __t(*this); 170227825Stheraven ++(*this); 171227825Stheraven return __t; 172227825Stheraven } 173227825Stheraven 174227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 175227825Stheraven bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 176261272Sdim { 177261272Sdim return __x.__node_ == __y.__node_; 178261272Sdim } 179227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 180227825Stheraven bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 181261272Sdim {return !(__x == __y);} 182227825Stheraven 183227825Stheravenprivate: 184261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 185227825Stheraven _LIBCPP_INLINE_VISIBILITY 186261272Sdim __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 187261272Sdim : __node_(__node) 188261272Sdim { 189261272Sdim __get_db()->__insert_ic(this, __c); 190261272Sdim } 191261272Sdim#else 192261272Sdim _LIBCPP_INLINE_VISIBILITY 193227825Stheraven __hash_iterator(__node_pointer __node) _NOEXCEPT 194227825Stheraven : __node_(__node) 195227825Stheraven {} 196261272Sdim#endif 197227825Stheraven 198227825Stheraven template <class, class, class, class> friend class __hash_table; 199261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 200261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 201261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 202261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 203227825Stheraven}; 204227825Stheraven 205227825Stheraventemplate <class _ConstNodePtr> 206261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 207227825Stheraven{ 208227825Stheraven typedef _ConstNodePtr __node_pointer; 209227825Stheraven 210227825Stheraven __node_pointer __node_; 211227825Stheraven 212227825Stheraven typedef typename remove_const< 213227825Stheraven typename pointer_traits<__node_pointer>::element_type 214227825Stheraven >::type __node; 215227825Stheraven 216227825Stheravenpublic: 217227825Stheraven typedef forward_iterator_tag iterator_category; 218227825Stheraven typedef typename __node::value_type value_type; 219227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 220227825Stheraven typedef const value_type& reference; 221300770Sdim typedef typename __rebind_pointer<__node_pointer, const value_type>::type pointer; 222300770Sdim typedef typename __rebind_pointer<__node_pointer, __node>::type __non_const_node_pointer; 223227825Stheraven typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 224227825Stheraven 225261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 226261272Sdim#if _LIBCPP_STD_VER > 11 227261272Sdim : __node_(nullptr) 228261272Sdim#endif 229261272Sdim { 230261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 231261272Sdim __get_db()->__insert_i(this); 232261272Sdim#endif 233261272Sdim } 234227825Stheraven _LIBCPP_INLINE_VISIBILITY 235227825Stheraven __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 236227825Stheraven : __node_(__x.__node_) 237261272Sdim { 238261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 239261272Sdim __get_db()->__iterator_copy(this, &__x); 240261272Sdim#endif 241261272Sdim } 242227825Stheraven 243261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 244261272Sdim 245227825Stheraven _LIBCPP_INLINE_VISIBILITY 246261272Sdim __hash_const_iterator(const __hash_const_iterator& __i) 247261272Sdim : __node_(__i.__node_) 248261272Sdim { 249261272Sdim __get_db()->__iterator_copy(this, &__i); 250261272Sdim } 251261272Sdim 252227825Stheraven _LIBCPP_INLINE_VISIBILITY 253261272Sdim ~__hash_const_iterator() 254261272Sdim { 255261272Sdim __get_db()->__erase_i(this); 256261272Sdim } 257227825Stheraven 258227825Stheraven _LIBCPP_INLINE_VISIBILITY 259261272Sdim __hash_const_iterator& operator=(const __hash_const_iterator& __i) 260261272Sdim { 261261272Sdim if (this != &__i) 262261272Sdim { 263261272Sdim __get_db()->__iterator_copy(this, &__i); 264261272Sdim __node_ = __i.__node_; 265261272Sdim } 266261272Sdim return *this; 267261272Sdim } 268261272Sdim 269261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 270261272Sdim 271261272Sdim _LIBCPP_INLINE_VISIBILITY 272261272Sdim reference operator*() const 273261272Sdim { 274261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 275261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 276261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 277261272Sdim#endif 278261272Sdim return __node_->__value_; 279261272Sdim } 280261272Sdim _LIBCPP_INLINE_VISIBILITY 281261272Sdim pointer operator->() const 282261272Sdim { 283261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 284261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 285261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 286261272Sdim#endif 287261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 288261272Sdim } 289261272Sdim 290261272Sdim _LIBCPP_INLINE_VISIBILITY 291227825Stheraven __hash_const_iterator& operator++() 292227825Stheraven { 293261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 294261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 295261272Sdim "Attempted to increment non-incrementable unordered container const_iterator"); 296261272Sdim#endif 297227825Stheraven __node_ = __node_->__next_; 298227825Stheraven return *this; 299227825Stheraven } 300227825Stheraven 301227825Stheraven _LIBCPP_INLINE_VISIBILITY 302227825Stheraven __hash_const_iterator operator++(int) 303227825Stheraven { 304227825Stheraven __hash_const_iterator __t(*this); 305227825Stheraven ++(*this); 306227825Stheraven return __t; 307227825Stheraven } 308227825Stheraven 309227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 310227825Stheraven bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 311261272Sdim { 312261272Sdim return __x.__node_ == __y.__node_; 313261272Sdim } 314227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 315227825Stheraven bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 316261272Sdim {return !(__x == __y);} 317227825Stheraven 318227825Stheravenprivate: 319261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 320227825Stheraven _LIBCPP_INLINE_VISIBILITY 321261272Sdim __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 322261272Sdim : __node_(__node) 323261272Sdim { 324261272Sdim __get_db()->__insert_ic(this, __c); 325261272Sdim } 326261272Sdim#else 327261272Sdim _LIBCPP_INLINE_VISIBILITY 328227825Stheraven __hash_const_iterator(__node_pointer __node) _NOEXCEPT 329227825Stheraven : __node_(__node) 330227825Stheraven {} 331261272Sdim#endif 332227825Stheraven 333227825Stheraven template <class, class, class, class> friend class __hash_table; 334261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 335261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 336261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 337227825Stheraven}; 338227825Stheraven 339261272Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 340227825Stheraven 341227825Stheraventemplate <class _NodePtr> 342261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 343227825Stheraven{ 344227825Stheraven typedef _NodePtr __node_pointer; 345227825Stheraven 346227825Stheraven __node_pointer __node_; 347227825Stheraven size_t __bucket_; 348227825Stheraven size_t __bucket_count_; 349227825Stheraven 350227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 351227825Stheravenpublic: 352227825Stheraven typedef forward_iterator_tag iterator_category; 353227825Stheraven typedef typename __pointer_traits::element_type::value_type value_type; 354227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 355227825Stheraven typedef value_type& reference; 356300770Sdim typedef typename __rebind_pointer<__node_pointer, value_type>::type pointer; 357227825Stheraven 358261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 359261272Sdim { 360261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 361261272Sdim __get_db()->__insert_i(this); 362261272Sdim#endif 363261272Sdim } 364227825Stheraven 365261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 366261272Sdim 367227825Stheraven _LIBCPP_INLINE_VISIBILITY 368261272Sdim __hash_local_iterator(const __hash_local_iterator& __i) 369261272Sdim : __node_(__i.__node_), 370261272Sdim __bucket_(__i.__bucket_), 371261272Sdim __bucket_count_(__i.__bucket_count_) 372261272Sdim { 373261272Sdim __get_db()->__iterator_copy(this, &__i); 374261272Sdim } 375261272Sdim 376227825Stheraven _LIBCPP_INLINE_VISIBILITY 377261272Sdim ~__hash_local_iterator() 378261272Sdim { 379261272Sdim __get_db()->__erase_i(this); 380261272Sdim } 381227825Stheraven 382227825Stheraven _LIBCPP_INLINE_VISIBILITY 383261272Sdim __hash_local_iterator& operator=(const __hash_local_iterator& __i) 384261272Sdim { 385261272Sdim if (this != &__i) 386261272Sdim { 387261272Sdim __get_db()->__iterator_copy(this, &__i); 388261272Sdim __node_ = __i.__node_; 389261272Sdim __bucket_ = __i.__bucket_; 390261272Sdim __bucket_count_ = __i.__bucket_count_; 391261272Sdim } 392261272Sdim return *this; 393261272Sdim } 394261272Sdim 395261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 396261272Sdim 397261272Sdim _LIBCPP_INLINE_VISIBILITY 398261272Sdim reference operator*() const 399261272Sdim { 400261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 401261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 402261272Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 403261272Sdim#endif 404261272Sdim return __node_->__value_; 405261272Sdim } 406261272Sdim _LIBCPP_INLINE_VISIBILITY 407261272Sdim pointer operator->() const 408261272Sdim { 409261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 410261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 411261272Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 412261272Sdim#endif 413261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 414261272Sdim } 415261272Sdim 416261272Sdim _LIBCPP_INLINE_VISIBILITY 417227825Stheraven __hash_local_iterator& operator++() 418227825Stheraven { 419261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 420261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 421261272Sdim "Attempted to increment non-incrementable unordered container local_iterator"); 422261272Sdim#endif 423227825Stheraven __node_ = __node_->__next_; 424241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 425227825Stheraven __node_ = nullptr; 426227825Stheraven return *this; 427227825Stheraven } 428227825Stheraven 429227825Stheraven _LIBCPP_INLINE_VISIBILITY 430227825Stheraven __hash_local_iterator operator++(int) 431227825Stheraven { 432227825Stheraven __hash_local_iterator __t(*this); 433227825Stheraven ++(*this); 434227825Stheraven return __t; 435227825Stheraven } 436227825Stheraven 437227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 438227825Stheraven bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 439261272Sdim { 440261272Sdim return __x.__node_ == __y.__node_; 441261272Sdim } 442227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 443227825Stheraven bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 444261272Sdim {return !(__x == __y);} 445227825Stheraven 446227825Stheravenprivate: 447261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 448227825Stheraven _LIBCPP_INLINE_VISIBILITY 449227825Stheraven __hash_local_iterator(__node_pointer __node, size_t __bucket, 450261272Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 451261272Sdim : __node_(__node), 452261272Sdim __bucket_(__bucket), 453261272Sdim __bucket_count_(__bucket_count) 454261272Sdim { 455261272Sdim __get_db()->__insert_ic(this, __c); 456261272Sdim if (__node_ != nullptr) 457261272Sdim __node_ = __node_->__next_; 458261272Sdim } 459261272Sdim#else 460261272Sdim _LIBCPP_INLINE_VISIBILITY 461261272Sdim __hash_local_iterator(__node_pointer __node, size_t __bucket, 462227825Stheraven size_t __bucket_count) _NOEXCEPT 463227825Stheraven : __node_(__node), 464227825Stheraven __bucket_(__bucket), 465227825Stheraven __bucket_count_(__bucket_count) 466227825Stheraven { 467227825Stheraven if (__node_ != nullptr) 468227825Stheraven __node_ = __node_->__next_; 469227825Stheraven } 470261272Sdim#endif 471227825Stheraven template <class, class, class, class> friend class __hash_table; 472261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 473261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 474227825Stheraven}; 475227825Stheraven 476227825Stheraventemplate <class _ConstNodePtr> 477261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 478227825Stheraven{ 479227825Stheraven typedef _ConstNodePtr __node_pointer; 480227825Stheraven 481227825Stheraven __node_pointer __node_; 482227825Stheraven size_t __bucket_; 483227825Stheraven size_t __bucket_count_; 484227825Stheraven 485227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 486227825Stheraven typedef typename __pointer_traits::element_type __node; 487227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 488300770Sdim typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type 489300770Sdim __non_const_node_pointer; 490300770Sdim 491227825Stheraven typedef __hash_local_iterator<__non_const_node_pointer> 492227825Stheraven __non_const_iterator; 493227825Stheravenpublic: 494227825Stheraven typedef forward_iterator_tag iterator_category; 495227825Stheraven typedef typename remove_const< 496227825Stheraven typename __pointer_traits::element_type::value_type 497227825Stheraven >::type value_type; 498227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 499227825Stheraven typedef const value_type& reference; 500300770Sdim typedef typename __rebind_pointer<__node_pointer, const value_type>::type 501300770Sdim pointer; 502227825Stheraven 503300770Sdim 504261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 505261272Sdim { 506261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 507261272Sdim __get_db()->__insert_i(this); 508261272Sdim#endif 509261272Sdim } 510261272Sdim 511227825Stheraven _LIBCPP_INLINE_VISIBILITY 512227825Stheraven __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 513227825Stheraven : __node_(__x.__node_), 514227825Stheraven __bucket_(__x.__bucket_), 515227825Stheraven __bucket_count_(__x.__bucket_count_) 516261272Sdim { 517261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 518261272Sdim __get_db()->__iterator_copy(this, &__x); 519261272Sdim#endif 520261272Sdim } 521227825Stheraven 522261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 523261272Sdim 524227825Stheraven _LIBCPP_INLINE_VISIBILITY 525261272Sdim __hash_const_local_iterator(const __hash_const_local_iterator& __i) 526261272Sdim : __node_(__i.__node_), 527261272Sdim __bucket_(__i.__bucket_), 528261272Sdim __bucket_count_(__i.__bucket_count_) 529261272Sdim { 530261272Sdim __get_db()->__iterator_copy(this, &__i); 531261272Sdim } 532261272Sdim 533227825Stheraven _LIBCPP_INLINE_VISIBILITY 534261272Sdim ~__hash_const_local_iterator() 535261272Sdim { 536261272Sdim __get_db()->__erase_i(this); 537261272Sdim } 538227825Stheraven 539227825Stheraven _LIBCPP_INLINE_VISIBILITY 540261272Sdim __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 541261272Sdim { 542261272Sdim if (this != &__i) 543261272Sdim { 544261272Sdim __get_db()->__iterator_copy(this, &__i); 545261272Sdim __node_ = __i.__node_; 546261272Sdim __bucket_ = __i.__bucket_; 547261272Sdim __bucket_count_ = __i.__bucket_count_; 548261272Sdim } 549261272Sdim return *this; 550261272Sdim } 551261272Sdim 552261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 553261272Sdim 554261272Sdim _LIBCPP_INLINE_VISIBILITY 555261272Sdim reference operator*() const 556261272Sdim { 557261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 558261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 559261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 560261272Sdim#endif 561261272Sdim return __node_->__value_; 562261272Sdim } 563261272Sdim _LIBCPP_INLINE_VISIBILITY 564261272Sdim pointer operator->() const 565261272Sdim { 566261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 567261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 568261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 569261272Sdim#endif 570261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 571261272Sdim } 572261272Sdim 573261272Sdim _LIBCPP_INLINE_VISIBILITY 574227825Stheraven __hash_const_local_iterator& operator++() 575227825Stheraven { 576261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 577261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 578261272Sdim "Attempted to increment non-incrementable unordered container const_local_iterator"); 579261272Sdim#endif 580227825Stheraven __node_ = __node_->__next_; 581241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 582227825Stheraven __node_ = nullptr; 583227825Stheraven return *this; 584227825Stheraven } 585227825Stheraven 586227825Stheraven _LIBCPP_INLINE_VISIBILITY 587227825Stheraven __hash_const_local_iterator operator++(int) 588227825Stheraven { 589227825Stheraven __hash_const_local_iterator __t(*this); 590227825Stheraven ++(*this); 591227825Stheraven return __t; 592227825Stheraven } 593227825Stheraven 594227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 595227825Stheraven bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 596261272Sdim { 597261272Sdim return __x.__node_ == __y.__node_; 598261272Sdim } 599227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 600227825Stheraven bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 601261272Sdim {return !(__x == __y);} 602227825Stheraven 603227825Stheravenprivate: 604261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 605227825Stheraven _LIBCPP_INLINE_VISIBILITY 606227825Stheraven __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 607261272Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 608261272Sdim : __node_(__node), 609261272Sdim __bucket_(__bucket), 610261272Sdim __bucket_count_(__bucket_count) 611261272Sdim { 612261272Sdim __get_db()->__insert_ic(this, __c); 613261272Sdim if (__node_ != nullptr) 614261272Sdim __node_ = __node_->__next_; 615261272Sdim } 616261272Sdim#else 617261272Sdim _LIBCPP_INLINE_VISIBILITY 618261272Sdim __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 619227825Stheraven size_t __bucket_count) _NOEXCEPT 620227825Stheraven : __node_(__node), 621227825Stheraven __bucket_(__bucket), 622227825Stheraven __bucket_count_(__bucket_count) 623227825Stheraven { 624227825Stheraven if (__node_ != nullptr) 625227825Stheraven __node_ = __node_->__next_; 626227825Stheraven } 627261272Sdim#endif 628227825Stheraven template <class, class, class, class> friend class __hash_table; 629261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 630227825Stheraven}; 631227825Stheraven 632227825Stheraventemplate <class _Alloc> 633227825Stheravenclass __bucket_list_deallocator 634227825Stheraven{ 635227825Stheraven typedef _Alloc allocator_type; 636227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 637227825Stheraven typedef typename __alloc_traits::size_type size_type; 638227825Stheraven 639227825Stheraven __compressed_pair<size_type, allocator_type> __data_; 640227825Stheravenpublic: 641227825Stheraven typedef typename __alloc_traits::pointer pointer; 642227825Stheraven 643227825Stheraven _LIBCPP_INLINE_VISIBILITY 644227825Stheraven __bucket_list_deallocator() 645227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 646227825Stheraven : __data_(0) {} 647227825Stheraven 648227825Stheraven _LIBCPP_INLINE_VISIBILITY 649227825Stheraven __bucket_list_deallocator(const allocator_type& __a, size_type __size) 650227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 651227825Stheraven : __data_(__size, __a) {} 652227825Stheraven 653227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 654227825Stheraven 655227825Stheraven _LIBCPP_INLINE_VISIBILITY 656227825Stheraven __bucket_list_deallocator(__bucket_list_deallocator&& __x) 657227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 658227825Stheraven : __data_(_VSTD::move(__x.__data_)) 659227825Stheraven { 660227825Stheraven __x.size() = 0; 661227825Stheraven } 662227825Stheraven 663227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 664227825Stheraven 665227825Stheraven _LIBCPP_INLINE_VISIBILITY 666227825Stheraven size_type& size() _NOEXCEPT {return __data_.first();} 667227825Stheraven _LIBCPP_INLINE_VISIBILITY 668227825Stheraven size_type size() const _NOEXCEPT {return __data_.first();} 669227825Stheraven 670227825Stheraven _LIBCPP_INLINE_VISIBILITY 671227825Stheraven allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 672227825Stheraven _LIBCPP_INLINE_VISIBILITY 673227825Stheraven const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 674227825Stheraven 675227825Stheraven _LIBCPP_INLINE_VISIBILITY 676227825Stheraven void operator()(pointer __p) _NOEXCEPT 677227825Stheraven { 678227825Stheraven __alloc_traits::deallocate(__alloc(), __p, size()); 679227825Stheraven } 680227825Stheraven}; 681227825Stheraven 682227825Stheraventemplate <class _Alloc> class __hash_map_node_destructor; 683227825Stheraven 684227825Stheraventemplate <class _Alloc> 685227825Stheravenclass __hash_node_destructor 686227825Stheraven{ 687227825Stheraven typedef _Alloc allocator_type; 688227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 689227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 690227825Stheravenpublic: 691227825Stheraven typedef typename __alloc_traits::pointer pointer; 692227825Stheravenprivate: 693227825Stheraven 694227825Stheraven allocator_type& __na_; 695227825Stheraven 696227825Stheraven __hash_node_destructor& operator=(const __hash_node_destructor&); 697227825Stheraven 698227825Stheravenpublic: 699227825Stheraven bool __value_constructed; 700227825Stheraven 701227825Stheraven _LIBCPP_INLINE_VISIBILITY 702227825Stheraven explicit __hash_node_destructor(allocator_type& __na, 703227825Stheraven bool __constructed = false) _NOEXCEPT 704227825Stheraven : __na_(__na), 705227825Stheraven __value_constructed(__constructed) 706227825Stheraven {} 707227825Stheraven 708227825Stheraven _LIBCPP_INLINE_VISIBILITY 709227825Stheraven void operator()(pointer __p) _NOEXCEPT 710227825Stheraven { 711227825Stheraven if (__value_constructed) 712227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 713227825Stheraven if (__p) 714227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 715227825Stheraven } 716227825Stheraven 717227825Stheraven template <class> friend class __hash_map_node_destructor; 718227825Stheraven}; 719227825Stheraven 720227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 721227825Stheravenclass __hash_table 722227825Stheraven{ 723227825Stheravenpublic: 724227825Stheraven typedef _Tp value_type; 725227825Stheraven typedef _Hash hasher; 726227825Stheraven typedef _Equal key_equal; 727227825Stheraven typedef _Alloc allocator_type; 728227825Stheraven 729227825Stheravenprivate: 730227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 731227825Stheravenpublic: 732227825Stheraven typedef value_type& reference; 733227825Stheraven typedef const value_type& const_reference; 734227825Stheraven typedef typename __alloc_traits::pointer pointer; 735227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 736227825Stheraven typedef typename __alloc_traits::size_type size_type; 737227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 738227825Stheravenpublic: 739227825Stheraven // Create __node 740227825Stheraven typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 741288943Sdim typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 742227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 743227825Stheraven typedef typename __node_traits::pointer __node_pointer; 744253146Stheraven typedef typename __node_traits::pointer __node_const_pointer; 745232924Stheraven typedef __hash_node_base<__node_pointer> __first_node; 746300770Sdim typedef typename __rebind_pointer<__node_pointer, __first_node>::type 747300770Sdim __node_base_pointer; 748227825Stheraven 749227825Stheravenprivate: 750227825Stheraven 751288943Sdim typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator; 752227825Stheraven typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 753227825Stheraven typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 754227825Stheraven typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 755227825Stheraven typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 756227825Stheraven 757227825Stheraven // --- Member data begin --- 758227825Stheraven __bucket_list __bucket_list_; 759227825Stheraven __compressed_pair<__first_node, __node_allocator> __p1_; 760227825Stheraven __compressed_pair<size_type, hasher> __p2_; 761227825Stheraven __compressed_pair<float, key_equal> __p3_; 762227825Stheraven // --- Member data end --- 763227825Stheraven 764227825Stheraven _LIBCPP_INLINE_VISIBILITY 765227825Stheraven size_type& size() _NOEXCEPT {return __p2_.first();} 766227825Stheravenpublic: 767227825Stheraven _LIBCPP_INLINE_VISIBILITY 768227825Stheraven size_type size() const _NOEXCEPT {return __p2_.first();} 769227825Stheraven 770227825Stheraven _LIBCPP_INLINE_VISIBILITY 771227825Stheraven hasher& hash_function() _NOEXCEPT {return __p2_.second();} 772227825Stheraven _LIBCPP_INLINE_VISIBILITY 773227825Stheraven const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 774227825Stheraven 775227825Stheraven _LIBCPP_INLINE_VISIBILITY 776227825Stheraven float& max_load_factor() _NOEXCEPT {return __p3_.first();} 777227825Stheraven _LIBCPP_INLINE_VISIBILITY 778227825Stheraven float max_load_factor() const _NOEXCEPT {return __p3_.first();} 779227825Stheraven 780227825Stheraven _LIBCPP_INLINE_VISIBILITY 781227825Stheraven key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 782227825Stheraven _LIBCPP_INLINE_VISIBILITY 783227825Stheraven const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 784227825Stheraven 785227825Stheraven _LIBCPP_INLINE_VISIBILITY 786227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 787227825Stheraven _LIBCPP_INLINE_VISIBILITY 788227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 789227825Stheraven {return __p1_.second();} 790227825Stheraven 791227825Stheravenpublic: 792227825Stheraven typedef __hash_iterator<__node_pointer> iterator; 793253146Stheraven typedef __hash_const_iterator<__node_pointer> const_iterator; 794227825Stheraven typedef __hash_local_iterator<__node_pointer> local_iterator; 795253146Stheraven typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 796227825Stheraven 797300770Sdim _LIBCPP_INLINE_VISIBILITY 798227825Stheraven __hash_table() 799227825Stheraven _NOEXCEPT_( 800227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 801227825Stheraven is_nothrow_default_constructible<__first_node>::value && 802227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 803227825Stheraven is_nothrow_default_constructible<hasher>::value && 804227825Stheraven is_nothrow_default_constructible<key_equal>::value); 805300770Sdim _LIBCPP_INLINE_VISIBILITY 806227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql); 807227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql, 808227825Stheraven const allocator_type& __a); 809227825Stheraven explicit __hash_table(const allocator_type& __a); 810227825Stheraven __hash_table(const __hash_table& __u); 811227825Stheraven __hash_table(const __hash_table& __u, const allocator_type& __a); 812227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 813227825Stheraven __hash_table(__hash_table&& __u) 814227825Stheraven _NOEXCEPT_( 815227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 816227825Stheraven is_nothrow_move_constructible<__first_node>::value && 817227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 818227825Stheraven is_nothrow_move_constructible<hasher>::value && 819227825Stheraven is_nothrow_move_constructible<key_equal>::value); 820227825Stheraven __hash_table(__hash_table&& __u, const allocator_type& __a); 821227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 822227825Stheraven ~__hash_table(); 823227825Stheraven 824227825Stheraven __hash_table& operator=(const __hash_table& __u); 825227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 826300770Sdim _LIBCPP_INLINE_VISIBILITY 827227825Stheraven __hash_table& operator=(__hash_table&& __u) 828227825Stheraven _NOEXCEPT_( 829227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 830227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 831227825Stheraven is_nothrow_move_assignable<hasher>::value && 832227825Stheraven is_nothrow_move_assignable<key_equal>::value); 833227825Stheraven#endif 834227825Stheraven template <class _InputIterator> 835227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 836227825Stheraven template <class _InputIterator> 837227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 838227825Stheraven 839227825Stheraven _LIBCPP_INLINE_VISIBILITY 840227825Stheraven size_type max_size() const _NOEXCEPT 841227825Stheraven { 842227825Stheraven return allocator_traits<__pointer_allocator>::max_size( 843227825Stheraven __bucket_list_.get_deleter().__alloc()); 844227825Stheraven } 845227825Stheraven 846227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 847227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 848227825Stheraven iterator __node_insert_multi(const_iterator __p, 849227825Stheraven __node_pointer __nd); 850227825Stheraven 851227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 852227825Stheraven template <class... _Args> 853227825Stheraven pair<iterator, bool> __emplace_unique(_Args&&... __args); 854227825Stheraven template <class... _Args> 855227825Stheraven iterator __emplace_multi(_Args&&... __args); 856227825Stheraven template <class... _Args> 857227825Stheraven iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 858227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 859227825Stheraven 860288943Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 861288943Sdim template <class _ValueTp> 862288943Sdim _LIBCPP_INLINE_VISIBILITY 863288943Sdim pair<iterator, bool> __insert_unique_value(_ValueTp&& __x); 864288943Sdim#else 865288943Sdim _LIBCPP_INLINE_VISIBILITY 866288943Sdim pair<iterator, bool> __insert_unique_value(const value_type& __x); 867288943Sdim#endif 868288943Sdim 869227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __x); 870227825Stheraven 871227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 872288943Sdim pair<iterator, bool> __insert_unique(value_type&& __x); 873232924Stheraven template <class _Pp> 874288943Sdim pair<iterator, bool> __insert_unique(_Pp&& __x); 875227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 876227825Stheraven 877227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 878232924Stheraven template <class _Pp> 879232924Stheraven iterator __insert_multi(_Pp&& __x); 880232924Stheraven template <class _Pp> 881232924Stheraven iterator __insert_multi(const_iterator __p, _Pp&& __x); 882227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 883227825Stheraven iterator __insert_multi(const value_type& __x); 884227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __x); 885227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 886227825Stheraven 887227825Stheraven void clear() _NOEXCEPT; 888227825Stheraven void rehash(size_type __n); 889227825Stheraven _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 890227825Stheraven {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 891227825Stheraven 892227825Stheraven _LIBCPP_INLINE_VISIBILITY 893227825Stheraven size_type bucket_count() const _NOEXCEPT 894227825Stheraven { 895227825Stheraven return __bucket_list_.get_deleter().size(); 896227825Stheraven } 897227825Stheraven 898300770Sdim _LIBCPP_INLINE_VISIBILITY 899227825Stheraven iterator begin() _NOEXCEPT; 900300770Sdim _LIBCPP_INLINE_VISIBILITY 901227825Stheraven iterator end() _NOEXCEPT; 902300770Sdim _LIBCPP_INLINE_VISIBILITY 903227825Stheraven const_iterator begin() const _NOEXCEPT; 904300770Sdim _LIBCPP_INLINE_VISIBILITY 905227825Stheraven const_iterator end() const _NOEXCEPT; 906227825Stheraven 907227825Stheraven template <class _Key> 908227825Stheraven _LIBCPP_INLINE_VISIBILITY 909227825Stheraven size_type bucket(const _Key& __k) const 910261272Sdim { 911261272Sdim _LIBCPP_ASSERT(bucket_count() > 0, 912261272Sdim "unordered container::bucket(key) called when bucket_count() == 0"); 913261272Sdim return __constrain_hash(hash_function()(__k), bucket_count()); 914261272Sdim } 915227825Stheraven 916227825Stheraven template <class _Key> 917227825Stheraven iterator find(const _Key& __x); 918227825Stheraven template <class _Key> 919227825Stheraven const_iterator find(const _Key& __x) const; 920227825Stheraven 921232924Stheraven typedef __hash_node_destructor<__node_allocator> _Dp; 922232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 923227825Stheraven 924227825Stheraven iterator erase(const_iterator __p); 925227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 926227825Stheraven template <class _Key> 927227825Stheraven size_type __erase_unique(const _Key& __k); 928227825Stheraven template <class _Key> 929227825Stheraven size_type __erase_multi(const _Key& __k); 930227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 931227825Stheraven 932227825Stheraven template <class _Key> 933300770Sdim _LIBCPP_INLINE_VISIBILITY 934227825Stheraven size_type __count_unique(const _Key& __k) const; 935227825Stheraven template <class _Key> 936227825Stheraven size_type __count_multi(const _Key& __k) const; 937227825Stheraven 938227825Stheraven template <class _Key> 939227825Stheraven pair<iterator, iterator> 940227825Stheraven __equal_range_unique(const _Key& __k); 941227825Stheraven template <class _Key> 942227825Stheraven pair<const_iterator, const_iterator> 943227825Stheraven __equal_range_unique(const _Key& __k) const; 944227825Stheraven 945227825Stheraven template <class _Key> 946227825Stheraven pair<iterator, iterator> 947227825Stheraven __equal_range_multi(const _Key& __k); 948227825Stheraven template <class _Key> 949227825Stheraven pair<const_iterator, const_iterator> 950227825Stheraven __equal_range_multi(const _Key& __k) const; 951227825Stheraven 952227825Stheraven void swap(__hash_table& __u) 953289082Sdim#if _LIBCPP_STD_VER <= 11 954227825Stheraven _NOEXCEPT_( 955288943Sdim __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 956288943Sdim && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 957288943Sdim || __is_nothrow_swappable<__pointer_allocator>::value) 958288943Sdim && (!__node_traits::propagate_on_container_swap::value 959288943Sdim || __is_nothrow_swappable<__node_allocator>::value) 960289082Sdim ); 961289082Sdim#else 962289082Sdim _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 963288943Sdim#endif 964227825Stheraven 965227825Stheraven _LIBCPP_INLINE_VISIBILITY 966227825Stheraven size_type max_bucket_count() const _NOEXCEPT 967253146Stheraven {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 968227825Stheraven size_type bucket_size(size_type __n) const; 969227825Stheraven _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 970227825Stheraven { 971227825Stheraven size_type __bc = bucket_count(); 972227825Stheraven return __bc != 0 ? (float)size() / __bc : 0.f; 973227825Stheraven } 974227825Stheraven _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 975261272Sdim { 976261272Sdim _LIBCPP_ASSERT(__mlf > 0, 977261272Sdim "unordered container::max_load_factor(lf) called with lf <= 0"); 978261272Sdim max_load_factor() = _VSTD::max(__mlf, load_factor()); 979261272Sdim } 980227825Stheraven 981261272Sdim _LIBCPP_INLINE_VISIBILITY 982261272Sdim local_iterator 983261272Sdim begin(size_type __n) 984261272Sdim { 985261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 986261272Sdim "unordered container::begin(n) called with n >= bucket_count()"); 987261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 988261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 989261272Sdim#else 990261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count()); 991261272Sdim#endif 992261272Sdim } 993261272Sdim 994261272Sdim _LIBCPP_INLINE_VISIBILITY 995261272Sdim local_iterator 996261272Sdim end(size_type __n) 997261272Sdim { 998261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 999261272Sdim "unordered container::end(n) called with n >= bucket_count()"); 1000261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1001261272Sdim return local_iterator(nullptr, __n, bucket_count(), this); 1002261272Sdim#else 1003261272Sdim return local_iterator(nullptr, __n, bucket_count()); 1004261272Sdim#endif 1005261272Sdim } 1006261272Sdim 1007261272Sdim _LIBCPP_INLINE_VISIBILITY 1008261272Sdim const_local_iterator 1009261272Sdim cbegin(size_type __n) const 1010261272Sdim { 1011261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1012261272Sdim "unordered container::cbegin(n) called with n >= bucket_count()"); 1013261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1014261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1015261272Sdim#else 1016261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1017261272Sdim#endif 1018261272Sdim } 1019261272Sdim 1020261272Sdim _LIBCPP_INLINE_VISIBILITY 1021261272Sdim const_local_iterator 1022261272Sdim cend(size_type __n) const 1023261272Sdim { 1024261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1025261272Sdim "unordered container::cend(n) called with n >= bucket_count()"); 1026261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1027261272Sdim return const_local_iterator(nullptr, __n, bucket_count(), this); 1028261272Sdim#else 1029261272Sdim return const_local_iterator(nullptr, __n, bucket_count()); 1030261272Sdim#endif 1031261272Sdim } 1032261272Sdim 1033261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1034261272Sdim 1035261272Sdim bool __dereferenceable(const const_iterator* __i) const; 1036261272Sdim bool __decrementable(const const_iterator* __i) const; 1037261272Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1038261272Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1039261272Sdim 1040261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1041261272Sdim 1042227825Stheravenprivate: 1043227825Stheraven void __rehash(size_type __n); 1044227825Stheraven 1045227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1046227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1047227825Stheraven template <class ..._Args> 1048227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1049227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1050227825Stheraven __node_holder __construct_node(value_type&& __v, size_t __hash); 1051227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1052227825Stheraven __node_holder __construct_node(const value_type& __v); 1053227825Stheraven#endif 1054227825Stheraven __node_holder __construct_node(const value_type& __v, size_t __hash); 1055227825Stheraven 1056227825Stheraven _LIBCPP_INLINE_VISIBILITY 1057227825Stheraven void __copy_assign_alloc(const __hash_table& __u) 1058227825Stheraven {__copy_assign_alloc(__u, integral_constant<bool, 1059227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1060227825Stheraven void __copy_assign_alloc(const __hash_table& __u, true_type); 1061227825Stheraven _LIBCPP_INLINE_VISIBILITY 1062232924Stheraven void __copy_assign_alloc(const __hash_table&, false_type) {} 1063227825Stheraven 1064227825Stheraven void __move_assign(__hash_table& __u, false_type); 1065227825Stheraven void __move_assign(__hash_table& __u, true_type) 1066227825Stheraven _NOEXCEPT_( 1067227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1068227825Stheraven is_nothrow_move_assignable<hasher>::value && 1069227825Stheraven is_nothrow_move_assignable<key_equal>::value); 1070227825Stheraven _LIBCPP_INLINE_VISIBILITY 1071227825Stheraven void __move_assign_alloc(__hash_table& __u) 1072227825Stheraven _NOEXCEPT_( 1073227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1074227825Stheraven (is_nothrow_move_assignable<__pointer_allocator>::value && 1075227825Stheraven is_nothrow_move_assignable<__node_allocator>::value)) 1076227825Stheraven {__move_assign_alloc(__u, integral_constant<bool, 1077227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1078227825Stheraven _LIBCPP_INLINE_VISIBILITY 1079227825Stheraven void __move_assign_alloc(__hash_table& __u, true_type) 1080227825Stheraven _NOEXCEPT_( 1081227825Stheraven is_nothrow_move_assignable<__pointer_allocator>::value && 1082227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1083227825Stheraven { 1084227825Stheraven __bucket_list_.get_deleter().__alloc() = 1085227825Stheraven _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1086227825Stheraven __node_alloc() = _VSTD::move(__u.__node_alloc()); 1087227825Stheraven } 1088227825Stheraven _LIBCPP_INLINE_VISIBILITY 1089227825Stheraven void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1090227825Stheraven 1091227825Stheraven void __deallocate(__node_pointer __np) _NOEXCEPT; 1092227825Stheraven __node_pointer __detach() _NOEXCEPT; 1093253146Stheraven 1094261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1095261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1096227825Stheraven}; 1097227825Stheraven 1098227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1099300770Sdiminline 1100227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1101227825Stheraven _NOEXCEPT_( 1102227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 1103227825Stheraven is_nothrow_default_constructible<__first_node>::value && 1104300770Sdim is_nothrow_default_constructible<__node_allocator>::value && 1105227825Stheraven is_nothrow_default_constructible<hasher>::value && 1106227825Stheraven is_nothrow_default_constructible<key_equal>::value) 1107227825Stheraven : __p2_(0), 1108227825Stheraven __p3_(1.0f) 1109227825Stheraven{ 1110227825Stheraven} 1111227825Stheraven 1112227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1113300770Sdiminline 1114227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1115227825Stheraven const key_equal& __eql) 1116227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter()), 1117227825Stheraven __p1_(), 1118227825Stheraven __p2_(0, __hf), 1119227825Stheraven __p3_(1.0f, __eql) 1120227825Stheraven{ 1121227825Stheraven} 1122227825Stheraven 1123227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1124227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1125227825Stheraven const key_equal& __eql, 1126227825Stheraven const allocator_type& __a) 1127227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1128227825Stheraven __p1_(__node_allocator(__a)), 1129227825Stheraven __p2_(0, __hf), 1130227825Stheraven __p3_(1.0f, __eql) 1131227825Stheraven{ 1132227825Stheraven} 1133227825Stheraven 1134227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1135227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1136227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1137227825Stheraven __p1_(__node_allocator(__a)), 1138227825Stheraven __p2_(0), 1139227825Stheraven __p3_(1.0f) 1140227825Stheraven{ 1141227825Stheraven} 1142227825Stheraven 1143227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1144227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1145227825Stheraven : __bucket_list_(nullptr, 1146227825Stheraven __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1147227825Stheraven select_on_container_copy_construction( 1148227825Stheraven __u.__bucket_list_.get_deleter().__alloc()), 0)), 1149227825Stheraven __p1_(allocator_traits<__node_allocator>:: 1150227825Stheraven select_on_container_copy_construction(__u.__node_alloc())), 1151227825Stheraven __p2_(0, __u.hash_function()), 1152227825Stheraven __p3_(__u.__p3_) 1153227825Stheraven{ 1154227825Stheraven} 1155227825Stheraven 1156227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1157227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1158227825Stheraven const allocator_type& __a) 1159227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1160227825Stheraven __p1_(__node_allocator(__a)), 1161227825Stheraven __p2_(0, __u.hash_function()), 1162227825Stheraven __p3_(__u.__p3_) 1163227825Stheraven{ 1164227825Stheraven} 1165227825Stheraven 1166227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1167227825Stheraven 1168227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1169227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1170227825Stheraven _NOEXCEPT_( 1171227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 1172227825Stheraven is_nothrow_move_constructible<__first_node>::value && 1173300770Sdim is_nothrow_move_constructible<__node_allocator>::value && 1174227825Stheraven is_nothrow_move_constructible<hasher>::value && 1175227825Stheraven is_nothrow_move_constructible<key_equal>::value) 1176227825Stheraven : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1177227825Stheraven __p1_(_VSTD::move(__u.__p1_)), 1178227825Stheraven __p2_(_VSTD::move(__u.__p2_)), 1179227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1180227825Stheraven{ 1181227825Stheraven if (size() > 0) 1182227825Stheraven { 1183241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1184253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1185227825Stheraven __u.__p1_.first().__next_ = nullptr; 1186227825Stheraven __u.size() = 0; 1187227825Stheraven } 1188227825Stheraven} 1189227825Stheraven 1190227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1191227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1192227825Stheraven const allocator_type& __a) 1193227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1194227825Stheraven __p1_(__node_allocator(__a)), 1195227825Stheraven __p2_(0, _VSTD::move(__u.hash_function())), 1196227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1197227825Stheraven{ 1198227825Stheraven if (__a == allocator_type(__u.__node_alloc())) 1199227825Stheraven { 1200227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1201227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1202227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1203227825Stheraven if (__u.size() > 0) 1204227825Stheraven { 1205227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1206227825Stheraven __u.__p1_.first().__next_ = nullptr; 1207241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1208253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1209227825Stheraven size() = __u.size(); 1210227825Stheraven __u.size() = 0; 1211227825Stheraven } 1212227825Stheraven } 1213227825Stheraven} 1214227825Stheraven 1215227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1216227825Stheraven 1217227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1218227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1219227825Stheraven{ 1220227825Stheraven __deallocate(__p1_.first().__next_); 1221261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1222261272Sdim __get_db()->__erase_c(this); 1223261272Sdim#endif 1224227825Stheraven} 1225227825Stheraven 1226227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1227227825Stheravenvoid 1228227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1229227825Stheraven const __hash_table& __u, true_type) 1230227825Stheraven{ 1231227825Stheraven if (__node_alloc() != __u.__node_alloc()) 1232227825Stheraven { 1233227825Stheraven clear(); 1234227825Stheraven __bucket_list_.reset(); 1235227825Stheraven __bucket_list_.get_deleter().size() = 0; 1236227825Stheraven } 1237227825Stheraven __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1238227825Stheraven __node_alloc() = __u.__node_alloc(); 1239227825Stheraven} 1240227825Stheraven 1241227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1242227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1243227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1244227825Stheraven{ 1245227825Stheraven if (this != &__u) 1246227825Stheraven { 1247227825Stheraven __copy_assign_alloc(__u); 1248227825Stheraven hash_function() = __u.hash_function(); 1249227825Stheraven key_eq() = __u.key_eq(); 1250227825Stheraven max_load_factor() = __u.max_load_factor(); 1251227825Stheraven __assign_multi(__u.begin(), __u.end()); 1252227825Stheraven } 1253227825Stheraven return *this; 1254227825Stheraven} 1255227825Stheraven 1256227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1257227825Stheravenvoid 1258227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1259227825Stheraven _NOEXCEPT 1260227825Stheraven{ 1261227825Stheraven __node_allocator& __na = __node_alloc(); 1262227825Stheraven while (__np != nullptr) 1263227825Stheraven { 1264227825Stheraven __node_pointer __next = __np->__next_; 1265261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1266261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 1267261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1268261272Sdim { 1269261272Sdim --__p; 1270261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 1271261272Sdim if (__i->__node_ == __np) 1272261272Sdim { 1273261272Sdim (*__p)->__c_ = nullptr; 1274261272Sdim if (--__c->end_ != __p) 1275261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1276261272Sdim } 1277261272Sdim } 1278261272Sdim __get_db()->unlock(); 1279261272Sdim#endif 1280227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1281227825Stheraven __node_traits::deallocate(__na, __np, 1); 1282227825Stheraven __np = __next; 1283227825Stheraven } 1284227825Stheraven} 1285227825Stheraven 1286227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1287227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1288227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1289227825Stheraven{ 1290227825Stheraven size_type __bc = bucket_count(); 1291227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1292227825Stheraven __bucket_list_[__i] = nullptr; 1293227825Stheraven size() = 0; 1294227825Stheraven __node_pointer __cache = __p1_.first().__next_; 1295227825Stheraven __p1_.first().__next_ = nullptr; 1296227825Stheraven return __cache; 1297227825Stheraven} 1298227825Stheraven 1299227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1300227825Stheraven 1301227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1302227825Stheravenvoid 1303227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1304227825Stheraven __hash_table& __u, true_type) 1305227825Stheraven _NOEXCEPT_( 1306227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1307227825Stheraven is_nothrow_move_assignable<hasher>::value && 1308227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1309227825Stheraven{ 1310227825Stheraven clear(); 1311227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1312227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1313227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1314227825Stheraven __move_assign_alloc(__u); 1315227825Stheraven size() = __u.size(); 1316227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1317227825Stheraven max_load_factor() = __u.max_load_factor(); 1318227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1319227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1320227825Stheraven if (size() > 0) 1321227825Stheraven { 1322241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1323253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1324227825Stheraven __u.__p1_.first().__next_ = nullptr; 1325227825Stheraven __u.size() = 0; 1326227825Stheraven } 1327261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1328261272Sdim __get_db()->swap(this, &__u); 1329261272Sdim#endif 1330227825Stheraven} 1331227825Stheraven 1332227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1333227825Stheravenvoid 1334227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1335227825Stheraven __hash_table& __u, false_type) 1336227825Stheraven{ 1337227825Stheraven if (__node_alloc() == __u.__node_alloc()) 1338227825Stheraven __move_assign(__u, true_type()); 1339227825Stheraven else 1340227825Stheraven { 1341227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1342227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1343227825Stheraven max_load_factor() = __u.max_load_factor(); 1344227825Stheraven if (bucket_count() != 0) 1345227825Stheraven { 1346227825Stheraven __node_pointer __cache = __detach(); 1347227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1348227825Stheraven try 1349227825Stheraven { 1350227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1351227825Stheraven const_iterator __i = __u.begin(); 1352227825Stheraven while (__cache != nullptr && __u.size() != 0) 1353227825Stheraven { 1354227825Stheraven __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1355227825Stheraven __node_pointer __next = __cache->__next_; 1356227825Stheraven __node_insert_multi(__cache); 1357227825Stheraven __cache = __next; 1358227825Stheraven } 1359227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1360227825Stheraven } 1361227825Stheraven catch (...) 1362227825Stheraven { 1363227825Stheraven __deallocate(__cache); 1364227825Stheraven throw; 1365227825Stheraven } 1366227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1367227825Stheraven __deallocate(__cache); 1368227825Stheraven } 1369227825Stheraven const_iterator __i = __u.begin(); 1370227825Stheraven while (__u.size() != 0) 1371227825Stheraven { 1372227825Stheraven __node_holder __h = 1373227825Stheraven __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1374227825Stheraven __node_insert_multi(__h.get()); 1375227825Stheraven __h.release(); 1376227825Stheraven } 1377227825Stheraven } 1378227825Stheraven} 1379227825Stheraven 1380227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1381300770Sdiminline 1382227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1383227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1384227825Stheraven _NOEXCEPT_( 1385227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1386227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1387227825Stheraven is_nothrow_move_assignable<hasher>::value && 1388227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1389227825Stheraven{ 1390227825Stheraven __move_assign(__u, integral_constant<bool, 1391227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1392227825Stheraven return *this; 1393227825Stheraven} 1394227825Stheraven 1395227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1396227825Stheraven 1397227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1398227825Stheraventemplate <class _InputIterator> 1399227825Stheravenvoid 1400227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1401227825Stheraven _InputIterator __last) 1402227825Stheraven{ 1403227825Stheraven if (bucket_count() != 0) 1404227825Stheraven { 1405227825Stheraven __node_pointer __cache = __detach(); 1406227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1407227825Stheraven try 1408227825Stheraven { 1409227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1410227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1411227825Stheraven { 1412227825Stheraven __cache->__value_ = *__first; 1413227825Stheraven __node_pointer __next = __cache->__next_; 1414227825Stheraven __node_insert_unique(__cache); 1415227825Stheraven __cache = __next; 1416227825Stheraven } 1417227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1418227825Stheraven } 1419227825Stheraven catch (...) 1420227825Stheraven { 1421227825Stheraven __deallocate(__cache); 1422227825Stheraven throw; 1423227825Stheraven } 1424227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1425227825Stheraven __deallocate(__cache); 1426227825Stheraven } 1427227825Stheraven for (; __first != __last; ++__first) 1428227825Stheraven __insert_unique(*__first); 1429227825Stheraven} 1430227825Stheraven 1431227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1432227825Stheraventemplate <class _InputIterator> 1433227825Stheravenvoid 1434227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1435227825Stheraven _InputIterator __last) 1436227825Stheraven{ 1437227825Stheraven if (bucket_count() != 0) 1438227825Stheraven { 1439227825Stheraven __node_pointer __cache = __detach(); 1440227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1441227825Stheraven try 1442227825Stheraven { 1443227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1444227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1445227825Stheraven { 1446227825Stheraven __cache->__value_ = *__first; 1447227825Stheraven __node_pointer __next = __cache->__next_; 1448227825Stheraven __node_insert_multi(__cache); 1449227825Stheraven __cache = __next; 1450227825Stheraven } 1451227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1452227825Stheraven } 1453227825Stheraven catch (...) 1454227825Stheraven { 1455227825Stheraven __deallocate(__cache); 1456227825Stheraven throw; 1457227825Stheraven } 1458227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1459227825Stheraven __deallocate(__cache); 1460227825Stheraven } 1461227825Stheraven for (; __first != __last; ++__first) 1462227825Stheraven __insert_multi(*__first); 1463227825Stheraven} 1464227825Stheraven 1465227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1466300770Sdiminline 1467227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1468227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1469227825Stheraven{ 1470261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1471261272Sdim return iterator(__p1_.first().__next_, this); 1472261272Sdim#else 1473227825Stheraven return iterator(__p1_.first().__next_); 1474261272Sdim#endif 1475227825Stheraven} 1476227825Stheraven 1477227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1478300770Sdiminline 1479227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1480227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1481227825Stheraven{ 1482261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1483261272Sdim return iterator(nullptr, this); 1484261272Sdim#else 1485227825Stheraven return iterator(nullptr); 1486261272Sdim#endif 1487227825Stheraven} 1488227825Stheraven 1489227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1490300770Sdiminline 1491227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1492227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1493227825Stheraven{ 1494261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1495261272Sdim return const_iterator(__p1_.first().__next_, this); 1496261272Sdim#else 1497227825Stheraven return const_iterator(__p1_.first().__next_); 1498261272Sdim#endif 1499227825Stheraven} 1500227825Stheraven 1501227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1502300770Sdiminline 1503227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1504227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1505227825Stheraven{ 1506261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1507261272Sdim return const_iterator(nullptr, this); 1508261272Sdim#else 1509227825Stheraven return const_iterator(nullptr); 1510261272Sdim#endif 1511227825Stheraven} 1512227825Stheraven 1513227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1514227825Stheravenvoid 1515227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1516227825Stheraven{ 1517227825Stheraven if (size() > 0) 1518227825Stheraven { 1519227825Stheraven __deallocate(__p1_.first().__next_); 1520227825Stheraven __p1_.first().__next_ = nullptr; 1521227825Stheraven size_type __bc = bucket_count(); 1522227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1523227825Stheraven __bucket_list_[__i] = nullptr; 1524227825Stheraven size() = 0; 1525227825Stheraven } 1526227825Stheraven} 1527227825Stheraven 1528227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1529227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1530227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1531227825Stheraven{ 1532227825Stheraven __nd->__hash_ = hash_function()(__nd->__value_); 1533227825Stheraven size_type __bc = bucket_count(); 1534227825Stheraven bool __inserted = false; 1535227825Stheraven __node_pointer __ndptr; 1536227825Stheraven size_t __chash; 1537227825Stheraven if (__bc != 0) 1538227825Stheraven { 1539241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1540227825Stheraven __ndptr = __bucket_list_[__chash]; 1541227825Stheraven if (__ndptr != nullptr) 1542227825Stheraven { 1543227825Stheraven for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1544241900Sdim __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1545227825Stheraven __ndptr = __ndptr->__next_) 1546227825Stheraven { 1547227825Stheraven if (key_eq()(__ndptr->__value_, __nd->__value_)) 1548227825Stheraven goto __done; 1549227825Stheraven } 1550227825Stheraven } 1551227825Stheraven } 1552227825Stheraven { 1553227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1554227825Stheraven { 1555288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1556227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1557227825Stheraven __bc = bucket_count(); 1558241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1559227825Stheraven } 1560227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1561227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1562227825Stheraven if (__pn == nullptr) 1563227825Stheraven { 1564253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1565227825Stheraven __nd->__next_ = __pn->__next_; 1566227825Stheraven __pn->__next_ = __nd; 1567227825Stheraven // fix up __bucket_list_ 1568227825Stheraven __bucket_list_[__chash] = __pn; 1569227825Stheraven if (__nd->__next_ != nullptr) 1570241900Sdim __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1571227825Stheraven } 1572227825Stheraven else 1573227825Stheraven { 1574227825Stheraven __nd->__next_ = __pn->__next_; 1575227825Stheraven __pn->__next_ = __nd; 1576227825Stheraven } 1577227825Stheraven __ndptr = __nd; 1578227825Stheraven // increment size 1579227825Stheraven ++size(); 1580227825Stheraven __inserted = true; 1581227825Stheraven } 1582227825Stheraven__done: 1583261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1584261272Sdim return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1585261272Sdim#else 1586227825Stheraven return pair<iterator, bool>(iterator(__ndptr), __inserted); 1587261272Sdim#endif 1588227825Stheraven} 1589227825Stheraven 1590227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1591227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1592227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1593227825Stheraven{ 1594227825Stheraven __cp->__hash_ = hash_function()(__cp->__value_); 1595227825Stheraven size_type __bc = bucket_count(); 1596227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1597227825Stheraven { 1598288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1599227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1600227825Stheraven __bc = bucket_count(); 1601227825Stheraven } 1602241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1603227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1604227825Stheraven if (__pn == nullptr) 1605227825Stheraven { 1606253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1607227825Stheraven __cp->__next_ = __pn->__next_; 1608227825Stheraven __pn->__next_ = __cp; 1609227825Stheraven // fix up __bucket_list_ 1610227825Stheraven __bucket_list_[__chash] = __pn; 1611227825Stheraven if (__cp->__next_ != nullptr) 1612241900Sdim __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1613227825Stheraven } 1614227825Stheraven else 1615227825Stheraven { 1616227825Stheraven for (bool __found = false; __pn->__next_ != nullptr && 1617241900Sdim __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1618227825Stheraven __pn = __pn->__next_) 1619227825Stheraven { 1620227825Stheraven // __found key_eq() action 1621227825Stheraven // false false loop 1622227825Stheraven // true true loop 1623227825Stheraven // false true set __found to true 1624227825Stheraven // true false break 1625227825Stheraven if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1626227825Stheraven key_eq()(__pn->__next_->__value_, __cp->__value_))) 1627227825Stheraven { 1628227825Stheraven if (!__found) 1629227825Stheraven __found = true; 1630227825Stheraven else 1631227825Stheraven break; 1632227825Stheraven } 1633227825Stheraven } 1634227825Stheraven __cp->__next_ = __pn->__next_; 1635227825Stheraven __pn->__next_ = __cp; 1636227825Stheraven if (__cp->__next_ != nullptr) 1637227825Stheraven { 1638241900Sdim size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1639227825Stheraven if (__nhash != __chash) 1640227825Stheraven __bucket_list_[__nhash] = __cp; 1641227825Stheraven } 1642227825Stheraven } 1643227825Stheraven ++size(); 1644261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1645261272Sdim return iterator(__cp, this); 1646261272Sdim#else 1647227825Stheraven return iterator(__cp); 1648261272Sdim#endif 1649227825Stheraven} 1650227825Stheraven 1651227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1652227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1653227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1654227825Stheraven const_iterator __p, __node_pointer __cp) 1655227825Stheraven{ 1656261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1657261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1658261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1659261272Sdim " referring to this unordered container"); 1660261272Sdim#endif 1661227825Stheraven if (__p != end() && key_eq()(*__p, __cp->__value_)) 1662227825Stheraven { 1663253146Stheraven __node_pointer __np = __p.__node_; 1664227825Stheraven __cp->__hash_ = __np->__hash_; 1665227825Stheraven size_type __bc = bucket_count(); 1666227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1667227825Stheraven { 1668288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1669227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1670227825Stheraven __bc = bucket_count(); 1671227825Stheraven } 1672241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1673227825Stheraven __node_pointer __pp = __bucket_list_[__chash]; 1674227825Stheraven while (__pp->__next_ != __np) 1675227825Stheraven __pp = __pp->__next_; 1676227825Stheraven __cp->__next_ = __np; 1677227825Stheraven __pp->__next_ = __cp; 1678227825Stheraven ++size(); 1679261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1680261272Sdim return iterator(__cp, this); 1681261272Sdim#else 1682227825Stheraven return iterator(__cp); 1683261272Sdim#endif 1684227825Stheraven } 1685227825Stheraven return __node_insert_multi(__cp); 1686227825Stheraven} 1687227825Stheraven 1688227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1689227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1690227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1691227825Stheraven{ 1692288943Sdim return __insert_unique_value(__x); 1693288943Sdim} 1694288943Sdim 1695288943Sdim 1696288943Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1697288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1698288943Sdimtemplate <class _ValueTp> 1699288943Sdim_LIBCPP_INLINE_VISIBILITY 1700288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1701288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x) 1702288943Sdim#else 1703288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1704288943Sdim_LIBCPP_INLINE_VISIBILITY 1705288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1706288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x) 1707288943Sdim#endif 1708288943Sdim{ 1709288943Sdim#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1710288943Sdim typedef const value_type& _ValueTp; 1711288943Sdim#endif 1712227825Stheraven size_t __hash = hash_function()(__x); 1713227825Stheraven size_type __bc = bucket_count(); 1714227825Stheraven bool __inserted = false; 1715227825Stheraven __node_pointer __nd; 1716227825Stheraven size_t __chash; 1717227825Stheraven if (__bc != 0) 1718227825Stheraven { 1719241900Sdim __chash = __constrain_hash(__hash, __bc); 1720227825Stheraven __nd = __bucket_list_[__chash]; 1721227825Stheraven if (__nd != nullptr) 1722227825Stheraven { 1723227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1724241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1725227825Stheraven __nd = __nd->__next_) 1726227825Stheraven { 1727227825Stheraven if (key_eq()(__nd->__value_, __x)) 1728227825Stheraven goto __done; 1729227825Stheraven } 1730227825Stheraven } 1731227825Stheraven } 1732227825Stheraven { 1733288943Sdim __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash); 1734227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1735227825Stheraven { 1736288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1737227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1738227825Stheraven __bc = bucket_count(); 1739241900Sdim __chash = __constrain_hash(__hash, __bc); 1740227825Stheraven } 1741227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1742227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1743227825Stheraven if (__pn == nullptr) 1744227825Stheraven { 1745253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1746227825Stheraven __h->__next_ = __pn->__next_; 1747227825Stheraven __pn->__next_ = __h.get(); 1748227825Stheraven // fix up __bucket_list_ 1749227825Stheraven __bucket_list_[__chash] = __pn; 1750227825Stheraven if (__h->__next_ != nullptr) 1751241900Sdim __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1752227825Stheraven } 1753227825Stheraven else 1754227825Stheraven { 1755227825Stheraven __h->__next_ = __pn->__next_; 1756227825Stheraven __pn->__next_ = __h.get(); 1757227825Stheraven } 1758227825Stheraven __nd = __h.release(); 1759227825Stheraven // increment size 1760227825Stheraven ++size(); 1761227825Stheraven __inserted = true; 1762227825Stheraven } 1763227825Stheraven__done: 1764261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1765261272Sdim return pair<iterator, bool>(iterator(__nd, this), __inserted); 1766261272Sdim#else 1767227825Stheraven return pair<iterator, bool>(iterator(__nd), __inserted); 1768261272Sdim#endif 1769227825Stheraven} 1770227825Stheraven 1771227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1772227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1773227825Stheraven 1774227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1775227825Stheraventemplate <class... _Args> 1776227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1777227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1778227825Stheraven{ 1779227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1780227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1781227825Stheraven if (__r.second) 1782227825Stheraven __h.release(); 1783227825Stheraven return __r; 1784227825Stheraven} 1785227825Stheraven 1786227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1787227825Stheraventemplate <class... _Args> 1788227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1789227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1790227825Stheraven{ 1791227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1792227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1793227825Stheraven __h.release(); 1794227825Stheraven return __r; 1795227825Stheraven} 1796227825Stheraven 1797227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1798227825Stheraventemplate <class... _Args> 1799227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1800227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1801227825Stheraven const_iterator __p, _Args&&... __args) 1802227825Stheraven{ 1803261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1804261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1805261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1806261272Sdim " referring to this unordered container"); 1807261272Sdim#endif 1808227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1809227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1810227825Stheraven __h.release(); 1811227825Stheraven return __r; 1812227825Stheraven} 1813227825Stheraven 1814227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1815227825Stheraven 1816227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1817288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1818288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x) 1819288943Sdim{ 1820288943Sdim return __insert_unique_value(_VSTD::move(__x)); 1821288943Sdim} 1822288943Sdim 1823288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1824232924Stheraventemplate <class _Pp> 1825227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1826232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1827227825Stheraven{ 1828232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1829227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1830227825Stheraven if (__r.second) 1831227825Stheraven __h.release(); 1832227825Stheraven return __r; 1833227825Stheraven} 1834227825Stheraven 1835227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1836227825Stheraven 1837227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1838227825Stheraven 1839227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1840232924Stheraventemplate <class _Pp> 1841227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1842232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1843227825Stheraven{ 1844232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1845227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1846227825Stheraven __h.release(); 1847227825Stheraven return __r; 1848227825Stheraven} 1849227825Stheraven 1850227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1851232924Stheraventemplate <class _Pp> 1852227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1853227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1854232924Stheraven _Pp&& __x) 1855227825Stheraven{ 1856261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1857261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1858261272Sdim "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1859261272Sdim " referring to this unordered container"); 1860261272Sdim#endif 1861232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1862227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1863227825Stheraven __h.release(); 1864227825Stheraven return __r; 1865227825Stheraven} 1866227825Stheraven 1867227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1868227825Stheraven 1869227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1870227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1871227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1872227825Stheraven{ 1873227825Stheraven __node_holder __h = __construct_node(__x); 1874227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1875227825Stheraven __h.release(); 1876227825Stheraven return __r; 1877227825Stheraven} 1878227825Stheraven 1879227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1880227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1881227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1882227825Stheraven const value_type& __x) 1883227825Stheraven{ 1884261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1885261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1886261272Sdim "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1887261272Sdim " referring to this unordered container"); 1888261272Sdim#endif 1889227825Stheraven __node_holder __h = __construct_node(__x); 1890227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1891227825Stheraven __h.release(); 1892227825Stheraven return __r; 1893227825Stheraven} 1894227825Stheraven 1895227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1896227825Stheraven 1897227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1898227825Stheravenvoid 1899227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1900227825Stheraven{ 1901241900Sdim if (__n == 1) 1902241900Sdim __n = 2; 1903241900Sdim else if (__n & (__n - 1)) 1904241900Sdim __n = __next_prime(__n); 1905227825Stheraven size_type __bc = bucket_count(); 1906227825Stheraven if (__n > __bc) 1907227825Stheraven __rehash(__n); 1908241900Sdim else if (__n < __bc) 1909227825Stheraven { 1910227825Stheraven __n = _VSTD::max<size_type> 1911227825Stheraven ( 1912227825Stheraven __n, 1913288943Sdim __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1914288943Sdim __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1915227825Stheraven ); 1916227825Stheraven if (__n < __bc) 1917227825Stheraven __rehash(__n); 1918227825Stheraven } 1919227825Stheraven} 1920227825Stheraven 1921227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1922227825Stheravenvoid 1923227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1924227825Stheraven{ 1925261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1926261272Sdim __get_db()->__invalidate_all(this); 1927261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1928227825Stheraven __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1929227825Stheraven __bucket_list_.reset(__nbc > 0 ? 1930227825Stheraven __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1931227825Stheraven __bucket_list_.get_deleter().size() = __nbc; 1932227825Stheraven if (__nbc > 0) 1933227825Stheraven { 1934227825Stheraven for (size_type __i = 0; __i < __nbc; ++__i) 1935227825Stheraven __bucket_list_[__i] = nullptr; 1936253146Stheraven __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1937227825Stheraven __node_pointer __cp = __pp->__next_; 1938227825Stheraven if (__cp != nullptr) 1939227825Stheraven { 1940241900Sdim size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1941227825Stheraven __bucket_list_[__chash] = __pp; 1942227825Stheraven size_type __phash = __chash; 1943227825Stheraven for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1944227825Stheraven __cp = __pp->__next_) 1945227825Stheraven { 1946241900Sdim __chash = __constrain_hash(__cp->__hash_, __nbc); 1947227825Stheraven if (__chash == __phash) 1948227825Stheraven __pp = __cp; 1949227825Stheraven else 1950227825Stheraven { 1951227825Stheraven if (__bucket_list_[__chash] == nullptr) 1952227825Stheraven { 1953227825Stheraven __bucket_list_[__chash] = __pp; 1954227825Stheraven __pp = __cp; 1955227825Stheraven __phash = __chash; 1956227825Stheraven } 1957227825Stheraven else 1958227825Stheraven { 1959227825Stheraven __node_pointer __np = __cp; 1960227825Stheraven for (; __np->__next_ != nullptr && 1961227825Stheraven key_eq()(__cp->__value_, __np->__next_->__value_); 1962227825Stheraven __np = __np->__next_) 1963227825Stheraven ; 1964227825Stheraven __pp->__next_ = __np->__next_; 1965227825Stheraven __np->__next_ = __bucket_list_[__chash]->__next_; 1966227825Stheraven __bucket_list_[__chash]->__next_ = __cp; 1967227825Stheraven 1968227825Stheraven } 1969227825Stheraven } 1970227825Stheraven } 1971227825Stheraven } 1972227825Stheraven } 1973227825Stheraven} 1974227825Stheraven 1975227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1976227825Stheraventemplate <class _Key> 1977227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1978227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 1979227825Stheraven{ 1980227825Stheraven size_t __hash = hash_function()(__k); 1981227825Stheraven size_type __bc = bucket_count(); 1982227825Stheraven if (__bc != 0) 1983227825Stheraven { 1984241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 1985227825Stheraven __node_pointer __nd = __bucket_list_[__chash]; 1986227825Stheraven if (__nd != nullptr) 1987227825Stheraven { 1988227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1989241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1990227825Stheraven __nd = __nd->__next_) 1991227825Stheraven { 1992227825Stheraven if (key_eq()(__nd->__value_, __k)) 1993261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1994261272Sdim return iterator(__nd, this); 1995261272Sdim#else 1996227825Stheraven return iterator(__nd); 1997261272Sdim#endif 1998227825Stheraven } 1999227825Stheraven } 2000227825Stheraven } 2001227825Stheraven return end(); 2002227825Stheraven} 2003227825Stheraven 2004227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2005227825Stheraventemplate <class _Key> 2006227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2007227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2008227825Stheraven{ 2009227825Stheraven size_t __hash = hash_function()(__k); 2010227825Stheraven size_type __bc = bucket_count(); 2011227825Stheraven if (__bc != 0) 2012227825Stheraven { 2013241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2014227825Stheraven __node_const_pointer __nd = __bucket_list_[__chash]; 2015227825Stheraven if (__nd != nullptr) 2016227825Stheraven { 2017227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2018241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2019227825Stheraven __nd = __nd->__next_) 2020227825Stheraven { 2021227825Stheraven if (key_eq()(__nd->__value_, __k)) 2022261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2023261272Sdim return const_iterator(__nd, this); 2024261272Sdim#else 2025227825Stheraven return const_iterator(__nd); 2026261272Sdim#endif 2027227825Stheraven } 2028227825Stheraven } 2029227825Stheraven 2030227825Stheraven } 2031227825Stheraven return end(); 2032227825Stheraven} 2033227825Stheraven 2034227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2035227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 2036227825Stheraven 2037227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2038227825Stheraventemplate <class ..._Args> 2039227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2040227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2041227825Stheraven{ 2042227825Stheraven __node_allocator& __na = __node_alloc(); 2043232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2044227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2045227825Stheraven __h.get_deleter().__value_constructed = true; 2046227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2047227825Stheraven __h->__next_ = nullptr; 2048227825Stheraven return __h; 2049227825Stheraven} 2050227825Stheraven 2051227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2052227825Stheraven 2053227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2054227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2055227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2056227825Stheraven size_t __hash) 2057227825Stheraven{ 2058227825Stheraven __node_allocator& __na = __node_alloc(); 2059232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2060227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2061227825Stheraven __h.get_deleter().__value_constructed = true; 2062227825Stheraven __h->__hash_ = __hash; 2063227825Stheraven __h->__next_ = nullptr; 2064261272Sdim return __h; 2065227825Stheraven} 2066227825Stheraven 2067227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2068227825Stheraven 2069227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2070227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2071227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2072227825Stheraven{ 2073227825Stheraven __node_allocator& __na = __node_alloc(); 2074232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2075227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2076227825Stheraven __h.get_deleter().__value_constructed = true; 2077227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2078227825Stheraven __h->__next_ = nullptr; 2079300770Sdim return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2080227825Stheraven} 2081227825Stheraven 2082227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2083227825Stheraven 2084227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2085227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2086227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2087227825Stheraven size_t __hash) 2088227825Stheraven{ 2089227825Stheraven __node_allocator& __na = __node_alloc(); 2090232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2091227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2092227825Stheraven __h.get_deleter().__value_constructed = true; 2093227825Stheraven __h->__hash_ = __hash; 2094227825Stheraven __h->__next_ = nullptr; 2095300770Sdim return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2096227825Stheraven} 2097227825Stheraven 2098227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2099227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2100227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2101227825Stheraven{ 2102253146Stheraven __node_pointer __np = __p.__node_; 2103261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2104261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2105261272Sdim "unordered container erase(iterator) called with an iterator not" 2106261272Sdim " referring to this container"); 2107261272Sdim _LIBCPP_ASSERT(__p != end(), 2108261272Sdim "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2109261272Sdim iterator __r(__np, this); 2110261272Sdim#else 2111227825Stheraven iterator __r(__np); 2112261272Sdim#endif 2113227825Stheraven ++__r; 2114227825Stheraven remove(__p); 2115227825Stheraven return __r; 2116227825Stheraven} 2117227825Stheraven 2118227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2119227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2120227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2121227825Stheraven const_iterator __last) 2122227825Stheraven{ 2123261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2124261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2125261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2126261272Sdim " referring to this unodered container"); 2127261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2128261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2129261272Sdim " referring to this unodered container"); 2130261272Sdim#endif 2131227825Stheraven for (const_iterator __p = __first; __first != __last; __p = __first) 2132227825Stheraven { 2133227825Stheraven ++__first; 2134227825Stheraven erase(__p); 2135227825Stheraven } 2136253146Stheraven __node_pointer __np = __last.__node_; 2137261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2138261272Sdim return iterator (__np, this); 2139261272Sdim#else 2140227825Stheraven return iterator (__np); 2141261272Sdim#endif 2142227825Stheraven} 2143227825Stheraven 2144227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2145227825Stheraventemplate <class _Key> 2146227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2147227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2148227825Stheraven{ 2149227825Stheraven iterator __i = find(__k); 2150227825Stheraven if (__i == end()) 2151227825Stheraven return 0; 2152227825Stheraven erase(__i); 2153227825Stheraven return 1; 2154227825Stheraven} 2155227825Stheraven 2156227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2157227825Stheraventemplate <class _Key> 2158227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2159227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2160227825Stheraven{ 2161227825Stheraven size_type __r = 0; 2162227825Stheraven iterator __i = find(__k); 2163227825Stheraven if (__i != end()) 2164227825Stheraven { 2165227825Stheraven iterator __e = end(); 2166227825Stheraven do 2167227825Stheraven { 2168227825Stheraven erase(__i++); 2169227825Stheraven ++__r; 2170227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2171227825Stheraven } 2172227825Stheraven return __r; 2173227825Stheraven} 2174227825Stheraven 2175227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2176227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2177227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2178227825Stheraven{ 2179227825Stheraven // current node 2180253146Stheraven __node_pointer __cn = __p.__node_; 2181227825Stheraven size_type __bc = bucket_count(); 2182241900Sdim size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2183227825Stheraven // find previous node 2184227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 2185227825Stheraven for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2186227825Stheraven ; 2187227825Stheraven // Fix up __bucket_list_ 2188227825Stheraven // if __pn is not in same bucket (before begin is not in same bucket) && 2189227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2190253146Stheraven if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2191253146Stheraven || __constrain_hash(__pn->__hash_, __bc) != __chash) 2192227825Stheraven { 2193241900Sdim if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2194227825Stheraven __bucket_list_[__chash] = nullptr; 2195227825Stheraven } 2196227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2197227825Stheraven if (__cn->__next_ != nullptr) 2198227825Stheraven { 2199241900Sdim size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2200227825Stheraven if (__nhash != __chash) 2201227825Stheraven __bucket_list_[__nhash] = __pn; 2202227825Stheraven } 2203227825Stheraven // remove __cn 2204227825Stheraven __pn->__next_ = __cn->__next_; 2205227825Stheraven __cn->__next_ = nullptr; 2206227825Stheraven --size(); 2207261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2208261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 2209261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2210261272Sdim { 2211261272Sdim --__p; 2212261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 2213261272Sdim if (__i->__node_ == __cn) 2214261272Sdim { 2215261272Sdim (*__p)->__c_ = nullptr; 2216261272Sdim if (--__c->end_ != __p) 2217261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2218261272Sdim } 2219261272Sdim } 2220261272Sdim __get_db()->unlock(); 2221261272Sdim#endif 2222232924Stheraven return __node_holder(__cn, _Dp(__node_alloc(), true)); 2223227825Stheraven} 2224227825Stheraven 2225227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2226227825Stheraventemplate <class _Key> 2227300770Sdiminline 2228227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2229227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2230227825Stheraven{ 2231227825Stheraven return static_cast<size_type>(find(__k) != end()); 2232227825Stheraven} 2233227825Stheraven 2234227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2235227825Stheraventemplate <class _Key> 2236227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2237227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2238227825Stheraven{ 2239227825Stheraven size_type __r = 0; 2240227825Stheraven const_iterator __i = find(__k); 2241227825Stheraven if (__i != end()) 2242227825Stheraven { 2243227825Stheraven const_iterator __e = end(); 2244227825Stheraven do 2245227825Stheraven { 2246227825Stheraven ++__i; 2247227825Stheraven ++__r; 2248227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2249227825Stheraven } 2250227825Stheraven return __r; 2251227825Stheraven} 2252227825Stheraven 2253227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2254227825Stheraventemplate <class _Key> 2255227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2256227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2257227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2258227825Stheraven const _Key& __k) 2259227825Stheraven{ 2260227825Stheraven iterator __i = find(__k); 2261227825Stheraven iterator __j = __i; 2262227825Stheraven if (__i != end()) 2263227825Stheraven ++__j; 2264227825Stheraven return pair<iterator, iterator>(__i, __j); 2265227825Stheraven} 2266227825Stheraven 2267227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2268227825Stheraventemplate <class _Key> 2269227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2270227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2271227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2272227825Stheraven const _Key& __k) const 2273227825Stheraven{ 2274227825Stheraven const_iterator __i = find(__k); 2275227825Stheraven const_iterator __j = __i; 2276227825Stheraven if (__i != end()) 2277227825Stheraven ++__j; 2278227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2279227825Stheraven} 2280227825Stheraven 2281227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2282227825Stheraventemplate <class _Key> 2283227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2284227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2285227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2286227825Stheraven const _Key& __k) 2287227825Stheraven{ 2288227825Stheraven iterator __i = find(__k); 2289227825Stheraven iterator __j = __i; 2290227825Stheraven if (__i != end()) 2291227825Stheraven { 2292227825Stheraven iterator __e = end(); 2293227825Stheraven do 2294227825Stheraven { 2295227825Stheraven ++__j; 2296227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2297227825Stheraven } 2298227825Stheraven return pair<iterator, iterator>(__i, __j); 2299227825Stheraven} 2300227825Stheraven 2301227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2302227825Stheraventemplate <class _Key> 2303227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2304227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2305227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2306227825Stheraven const _Key& __k) const 2307227825Stheraven{ 2308227825Stheraven const_iterator __i = find(__k); 2309227825Stheraven const_iterator __j = __i; 2310227825Stheraven if (__i != end()) 2311227825Stheraven { 2312227825Stheraven const_iterator __e = end(); 2313227825Stheraven do 2314227825Stheraven { 2315227825Stheraven ++__j; 2316227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2317227825Stheraven } 2318227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2319227825Stheraven} 2320227825Stheraven 2321227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2322227825Stheravenvoid 2323227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2324289082Sdim#if _LIBCPP_STD_VER <= 11 2325227825Stheraven _NOEXCEPT_( 2326288943Sdim __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2327288943Sdim && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2328288943Sdim || __is_nothrow_swappable<__pointer_allocator>::value) 2329288943Sdim && (!__node_traits::propagate_on_container_swap::value 2330288943Sdim || __is_nothrow_swappable<__node_allocator>::value) 2331289082Sdim ) 2332289082Sdim#else 2333289082Sdim _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2334288943Sdim#endif 2335227825Stheraven{ 2336227825Stheraven { 2337227825Stheraven __node_pointer_pointer __npp = __bucket_list_.release(); 2338227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 2339227825Stheraven __u.__bucket_list_.reset(__npp); 2340227825Stheraven } 2341227825Stheraven _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2342288943Sdim __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2343227825Stheraven __u.__bucket_list_.get_deleter().__alloc()); 2344288943Sdim __swap_allocator(__node_alloc(), __u.__node_alloc()); 2345227825Stheraven _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2346227825Stheraven __p2_.swap(__u.__p2_); 2347227825Stheraven __p3_.swap(__u.__p3_); 2348227825Stheraven if (size() > 0) 2349241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2350253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2351227825Stheraven if (__u.size() > 0) 2352241900Sdim __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2353253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2354261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2355261272Sdim __get_db()->swap(this, &__u); 2356261272Sdim#endif 2357227825Stheraven} 2358227825Stheraven 2359227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2360227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2361227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2362227825Stheraven{ 2363261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 2364261272Sdim "unordered container::bucket_size(n) called with n >= bucket_count()"); 2365227825Stheraven __node_const_pointer __np = __bucket_list_[__n]; 2366227825Stheraven size_type __bc = bucket_count(); 2367227825Stheraven size_type __r = 0; 2368227825Stheraven if (__np != nullptr) 2369227825Stheraven { 2370227825Stheraven for (__np = __np->__next_; __np != nullptr && 2371241900Sdim __constrain_hash(__np->__hash_, __bc) == __n; 2372227825Stheraven __np = __np->__next_, ++__r) 2373227825Stheraven ; 2374227825Stheraven } 2375227825Stheraven return __r; 2376227825Stheraven} 2377227825Stheraven 2378227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2379227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2380227825Stheravenvoid 2381227825Stheravenswap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2382227825Stheraven __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2383227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2384227825Stheraven{ 2385227825Stheraven __x.swap(__y); 2386227825Stheraven} 2387227825Stheraven 2388261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2389261272Sdim 2390261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2391261272Sdimbool 2392261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2393261272Sdim{ 2394261272Sdim return __i->__node_ != nullptr; 2395261272Sdim} 2396261272Sdim 2397261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2398261272Sdimbool 2399261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2400261272Sdim{ 2401261272Sdim return false; 2402261272Sdim} 2403261272Sdim 2404261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2405261272Sdimbool 2406261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2407261272Sdim{ 2408261272Sdim return false; 2409261272Sdim} 2410261272Sdim 2411261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2412261272Sdimbool 2413261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2414261272Sdim{ 2415261272Sdim return false; 2416261272Sdim} 2417261272Sdim 2418261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 2419227825Stheraven_LIBCPP_END_NAMESPACE_STD 2420227825Stheraven 2421227825Stheraven#endif // _LIBCPP__HASH_TABLE 2422