__hash_table revision 288943
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 < 49227825Stheraven typename pointer_traits<_VoidPtr>::template 50227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 51227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> > 52227825Stheraven#else 53227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> >::other 54227825Stheraven#endif 55227825Stheraven > 56227825Stheraven{ 57227825Stheraven typedef _Tp value_type; 58227825Stheraven 59227825Stheraven size_t __hash_; 60227825Stheraven value_type __value_; 61227825Stheraven}; 62227825Stheraven 63241900Sdiminline _LIBCPP_INLINE_VISIBILITY 64241900Sdimbool 65288943Sdim__is_hash_power2(size_t __bc) 66241900Sdim{ 67241900Sdim return __bc > 2 && !(__bc & (__bc - 1)); 68241900Sdim} 69241900Sdim 70241900Sdiminline _LIBCPP_INLINE_VISIBILITY 71241900Sdimsize_t 72241900Sdim__constrain_hash(size_t __h, size_t __bc) 73241900Sdim{ 74241900Sdim return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 75241900Sdim} 76241900Sdim 77241900Sdiminline _LIBCPP_INLINE_VISIBILITY 78241900Sdimsize_t 79288943Sdim__next_hash_pow2(size_t __n) 80241900Sdim{ 81241900Sdim return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 82241900Sdim} 83241900Sdim 84227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 85261272Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 86261272Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 87261272Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 88227825Stheraven 89227825Stheraventemplate <class _NodePtr> 90261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_iterator 91227825Stheraven{ 92227825Stheraven typedef _NodePtr __node_pointer; 93227825Stheraven 94227825Stheraven __node_pointer __node_; 95227825Stheraven 96227825Stheravenpublic: 97227825Stheraven typedef forward_iterator_tag iterator_category; 98227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 99227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 100227825Stheraven typedef value_type& reference; 101227825Stheraven typedef typename pointer_traits<__node_pointer>::template 102227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 103227825Stheraven rebind<value_type> 104227825Stheraven#else 105227825Stheraven rebind<value_type>::other 106227825Stheraven#endif 107227825Stheraven pointer; 108227825Stheraven 109261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 110261272Sdim#if _LIBCPP_STD_VER > 11 111261272Sdim : __node_(nullptr) 112261272Sdim#endif 113261272Sdim { 114261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 115261272Sdim __get_db()->__insert_i(this); 116261272Sdim#endif 117261272Sdim } 118227825Stheraven 119261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 120261272Sdim 121227825Stheraven _LIBCPP_INLINE_VISIBILITY 122261272Sdim __hash_iterator(const __hash_iterator& __i) 123261272Sdim : __node_(__i.__node_) 124261272Sdim { 125261272Sdim __get_db()->__iterator_copy(this, &__i); 126261272Sdim } 127261272Sdim 128227825Stheraven _LIBCPP_INLINE_VISIBILITY 129261272Sdim ~__hash_iterator() 130261272Sdim { 131261272Sdim __get_db()->__erase_i(this); 132261272Sdim } 133227825Stheraven 134227825Stheraven _LIBCPP_INLINE_VISIBILITY 135261272Sdim __hash_iterator& operator=(const __hash_iterator& __i) 136261272Sdim { 137261272Sdim if (this != &__i) 138261272Sdim { 139261272Sdim __get_db()->__iterator_copy(this, &__i); 140261272Sdim __node_ = __i.__node_; 141261272Sdim } 142261272Sdim return *this; 143261272Sdim } 144261272Sdim 145261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 146261272Sdim 147261272Sdim _LIBCPP_INLINE_VISIBILITY 148261272Sdim reference operator*() const 149261272Sdim { 150261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 151261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 152261272Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 153261272Sdim#endif 154261272Sdim return __node_->__value_; 155261272Sdim } 156261272Sdim _LIBCPP_INLINE_VISIBILITY 157261272Sdim pointer operator->() const 158261272Sdim { 159261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 160261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 161261272Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 162261272Sdim#endif 163261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 164261272Sdim } 165261272Sdim 166261272Sdim _LIBCPP_INLINE_VISIBILITY 167227825Stheraven __hash_iterator& operator++() 168227825Stheraven { 169261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 170261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 171261272Sdim "Attempted to increment non-incrementable unordered container iterator"); 172261272Sdim#endif 173227825Stheraven __node_ = __node_->__next_; 174227825Stheraven return *this; 175227825Stheraven } 176227825Stheraven 177227825Stheraven _LIBCPP_INLINE_VISIBILITY 178227825Stheraven __hash_iterator operator++(int) 179227825Stheraven { 180227825Stheraven __hash_iterator __t(*this); 181227825Stheraven ++(*this); 182227825Stheraven return __t; 183227825Stheraven } 184227825Stheraven 185227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 186227825Stheraven bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 187261272Sdim { 188261272Sdim return __x.__node_ == __y.__node_; 189261272Sdim } 190227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 191227825Stheraven bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 192261272Sdim {return !(__x == __y);} 193227825Stheraven 194227825Stheravenprivate: 195261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 196227825Stheraven _LIBCPP_INLINE_VISIBILITY 197261272Sdim __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 198261272Sdim : __node_(__node) 199261272Sdim { 200261272Sdim __get_db()->__insert_ic(this, __c); 201261272Sdim } 202261272Sdim#else 203261272Sdim _LIBCPP_INLINE_VISIBILITY 204227825Stheraven __hash_iterator(__node_pointer __node) _NOEXCEPT 205227825Stheraven : __node_(__node) 206227825Stheraven {} 207261272Sdim#endif 208227825Stheraven 209227825Stheraven template <class, class, class, class> friend class __hash_table; 210261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 211261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 212261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 213261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 214227825Stheraven}; 215227825Stheraven 216227825Stheraventemplate <class _ConstNodePtr> 217261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 218227825Stheraven{ 219227825Stheraven typedef _ConstNodePtr __node_pointer; 220227825Stheraven 221227825Stheraven __node_pointer __node_; 222227825Stheraven 223227825Stheraven typedef typename remove_const< 224227825Stheraven typename pointer_traits<__node_pointer>::element_type 225227825Stheraven >::type __node; 226227825Stheraven 227227825Stheravenpublic: 228227825Stheraven typedef forward_iterator_tag iterator_category; 229227825Stheraven typedef typename __node::value_type value_type; 230227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 231227825Stheraven typedef const value_type& reference; 232227825Stheraven typedef typename pointer_traits<__node_pointer>::template 233227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 234227825Stheraven rebind<const value_type> 235227825Stheraven#else 236227825Stheraven rebind<const value_type>::other 237227825Stheraven#endif 238227825Stheraven pointer; 239227825Stheraven typedef typename pointer_traits<__node_pointer>::template 240227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 241227825Stheraven rebind<__node> 242227825Stheraven#else 243227825Stheraven rebind<__node>::other 244227825Stheraven#endif 245227825Stheraven __non_const_node_pointer; 246227825Stheraven typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 247227825Stheraven 248261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 249261272Sdim#if _LIBCPP_STD_VER > 11 250261272Sdim : __node_(nullptr) 251261272Sdim#endif 252261272Sdim { 253261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 254261272Sdim __get_db()->__insert_i(this); 255261272Sdim#endif 256261272Sdim } 257227825Stheraven _LIBCPP_INLINE_VISIBILITY 258227825Stheraven __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 259227825Stheraven : __node_(__x.__node_) 260261272Sdim { 261261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 262261272Sdim __get_db()->__iterator_copy(this, &__x); 263261272Sdim#endif 264261272Sdim } 265227825Stheraven 266261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 267261272Sdim 268227825Stheraven _LIBCPP_INLINE_VISIBILITY 269261272Sdim __hash_const_iterator(const __hash_const_iterator& __i) 270261272Sdim : __node_(__i.__node_) 271261272Sdim { 272261272Sdim __get_db()->__iterator_copy(this, &__i); 273261272Sdim } 274261272Sdim 275227825Stheraven _LIBCPP_INLINE_VISIBILITY 276261272Sdim ~__hash_const_iterator() 277261272Sdim { 278261272Sdim __get_db()->__erase_i(this); 279261272Sdim } 280227825Stheraven 281227825Stheraven _LIBCPP_INLINE_VISIBILITY 282261272Sdim __hash_const_iterator& operator=(const __hash_const_iterator& __i) 283261272Sdim { 284261272Sdim if (this != &__i) 285261272Sdim { 286261272Sdim __get_db()->__iterator_copy(this, &__i); 287261272Sdim __node_ = __i.__node_; 288261272Sdim } 289261272Sdim return *this; 290261272Sdim } 291261272Sdim 292261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 293261272Sdim 294261272Sdim _LIBCPP_INLINE_VISIBILITY 295261272Sdim reference operator*() const 296261272Sdim { 297261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 298261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 299261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 300261272Sdim#endif 301261272Sdim return __node_->__value_; 302261272Sdim } 303261272Sdim _LIBCPP_INLINE_VISIBILITY 304261272Sdim pointer operator->() const 305261272Sdim { 306261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 307261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 308261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 309261272Sdim#endif 310261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 311261272Sdim } 312261272Sdim 313261272Sdim _LIBCPP_INLINE_VISIBILITY 314227825Stheraven __hash_const_iterator& operator++() 315227825Stheraven { 316261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 317261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 318261272Sdim "Attempted to increment non-incrementable unordered container const_iterator"); 319261272Sdim#endif 320227825Stheraven __node_ = __node_->__next_; 321227825Stheraven return *this; 322227825Stheraven } 323227825Stheraven 324227825Stheraven _LIBCPP_INLINE_VISIBILITY 325227825Stheraven __hash_const_iterator operator++(int) 326227825Stheraven { 327227825Stheraven __hash_const_iterator __t(*this); 328227825Stheraven ++(*this); 329227825Stheraven return __t; 330227825Stheraven } 331227825Stheraven 332227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 333227825Stheraven bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 334261272Sdim { 335261272Sdim return __x.__node_ == __y.__node_; 336261272Sdim } 337227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 338227825Stheraven bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 339261272Sdim {return !(__x == __y);} 340227825Stheraven 341227825Stheravenprivate: 342261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 343227825Stheraven _LIBCPP_INLINE_VISIBILITY 344261272Sdim __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 345261272Sdim : __node_(__node) 346261272Sdim { 347261272Sdim __get_db()->__insert_ic(this, __c); 348261272Sdim } 349261272Sdim#else 350261272Sdim _LIBCPP_INLINE_VISIBILITY 351227825Stheraven __hash_const_iterator(__node_pointer __node) _NOEXCEPT 352227825Stheraven : __node_(__node) 353227825Stheraven {} 354261272Sdim#endif 355227825Stheraven 356227825Stheraven template <class, class, class, class> friend class __hash_table; 357261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 358261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 359261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 360227825Stheraven}; 361227825Stheraven 362261272Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 363227825Stheraven 364227825Stheraventemplate <class _NodePtr> 365261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 366227825Stheraven{ 367227825Stheraven typedef _NodePtr __node_pointer; 368227825Stheraven 369227825Stheraven __node_pointer __node_; 370227825Stheraven size_t __bucket_; 371227825Stheraven size_t __bucket_count_; 372227825Stheraven 373227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 374227825Stheravenpublic: 375227825Stheraven typedef forward_iterator_tag iterator_category; 376227825Stheraven typedef typename __pointer_traits::element_type::value_type value_type; 377227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 378227825Stheraven typedef value_type& reference; 379227825Stheraven typedef typename __pointer_traits::template 380227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 381227825Stheraven rebind<value_type> 382227825Stheraven#else 383227825Stheraven rebind<value_type>::other 384227825Stheraven#endif 385227825Stheraven pointer; 386227825Stheraven 387261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 388261272Sdim { 389261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 390261272Sdim __get_db()->__insert_i(this); 391261272Sdim#endif 392261272Sdim } 393227825Stheraven 394261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 395261272Sdim 396227825Stheraven _LIBCPP_INLINE_VISIBILITY 397261272Sdim __hash_local_iterator(const __hash_local_iterator& __i) 398261272Sdim : __node_(__i.__node_), 399261272Sdim __bucket_(__i.__bucket_), 400261272Sdim __bucket_count_(__i.__bucket_count_) 401261272Sdim { 402261272Sdim __get_db()->__iterator_copy(this, &__i); 403261272Sdim } 404261272Sdim 405227825Stheraven _LIBCPP_INLINE_VISIBILITY 406261272Sdim ~__hash_local_iterator() 407261272Sdim { 408261272Sdim __get_db()->__erase_i(this); 409261272Sdim } 410227825Stheraven 411227825Stheraven _LIBCPP_INLINE_VISIBILITY 412261272Sdim __hash_local_iterator& operator=(const __hash_local_iterator& __i) 413261272Sdim { 414261272Sdim if (this != &__i) 415261272Sdim { 416261272Sdim __get_db()->__iterator_copy(this, &__i); 417261272Sdim __node_ = __i.__node_; 418261272Sdim __bucket_ = __i.__bucket_; 419261272Sdim __bucket_count_ = __i.__bucket_count_; 420261272Sdim } 421261272Sdim return *this; 422261272Sdim } 423261272Sdim 424261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 425261272Sdim 426261272Sdim _LIBCPP_INLINE_VISIBILITY 427261272Sdim reference operator*() const 428261272Sdim { 429261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 430261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 431261272Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 432261272Sdim#endif 433261272Sdim return __node_->__value_; 434261272Sdim } 435261272Sdim _LIBCPP_INLINE_VISIBILITY 436261272Sdim pointer operator->() const 437261272Sdim { 438261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 439261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 440261272Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 441261272Sdim#endif 442261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 443261272Sdim } 444261272Sdim 445261272Sdim _LIBCPP_INLINE_VISIBILITY 446227825Stheraven __hash_local_iterator& operator++() 447227825Stheraven { 448261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 449261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 450261272Sdim "Attempted to increment non-incrementable unordered container local_iterator"); 451261272Sdim#endif 452227825Stheraven __node_ = __node_->__next_; 453241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 454227825Stheraven __node_ = nullptr; 455227825Stheraven return *this; 456227825Stheraven } 457227825Stheraven 458227825Stheraven _LIBCPP_INLINE_VISIBILITY 459227825Stheraven __hash_local_iterator operator++(int) 460227825Stheraven { 461227825Stheraven __hash_local_iterator __t(*this); 462227825Stheraven ++(*this); 463227825Stheraven return __t; 464227825Stheraven } 465227825Stheraven 466227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 467227825Stheraven bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 468261272Sdim { 469261272Sdim return __x.__node_ == __y.__node_; 470261272Sdim } 471227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 472227825Stheraven bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 473261272Sdim {return !(__x == __y);} 474227825Stheraven 475227825Stheravenprivate: 476261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 477227825Stheraven _LIBCPP_INLINE_VISIBILITY 478227825Stheraven __hash_local_iterator(__node_pointer __node, size_t __bucket, 479261272Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 480261272Sdim : __node_(__node), 481261272Sdim __bucket_(__bucket), 482261272Sdim __bucket_count_(__bucket_count) 483261272Sdim { 484261272Sdim __get_db()->__insert_ic(this, __c); 485261272Sdim if (__node_ != nullptr) 486261272Sdim __node_ = __node_->__next_; 487261272Sdim } 488261272Sdim#else 489261272Sdim _LIBCPP_INLINE_VISIBILITY 490261272Sdim __hash_local_iterator(__node_pointer __node, size_t __bucket, 491227825Stheraven size_t __bucket_count) _NOEXCEPT 492227825Stheraven : __node_(__node), 493227825Stheraven __bucket_(__bucket), 494227825Stheraven __bucket_count_(__bucket_count) 495227825Stheraven { 496227825Stheraven if (__node_ != nullptr) 497227825Stheraven __node_ = __node_->__next_; 498227825Stheraven } 499261272Sdim#endif 500227825Stheraven template <class, class, class, class> friend class __hash_table; 501261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 502261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 503227825Stheraven}; 504227825Stheraven 505227825Stheraventemplate <class _ConstNodePtr> 506261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 507227825Stheraven{ 508227825Stheraven typedef _ConstNodePtr __node_pointer; 509227825Stheraven 510227825Stheraven __node_pointer __node_; 511227825Stheraven size_t __bucket_; 512227825Stheraven size_t __bucket_count_; 513227825Stheraven 514227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 515227825Stheraven typedef typename __pointer_traits::element_type __node; 516227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 517227825Stheraven typedef typename pointer_traits<__node_pointer>::template 518227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 519227825Stheraven rebind<__non_const_node> 520227825Stheraven#else 521227825Stheraven rebind<__non_const_node>::other 522227825Stheraven#endif 523227825Stheraven __non_const_node_pointer; 524227825Stheraven typedef __hash_local_iterator<__non_const_node_pointer> 525227825Stheraven __non_const_iterator; 526227825Stheravenpublic: 527227825Stheraven typedef forward_iterator_tag iterator_category; 528227825Stheraven typedef typename remove_const< 529227825Stheraven typename __pointer_traits::element_type::value_type 530227825Stheraven >::type value_type; 531227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 532227825Stheraven typedef const value_type& reference; 533227825Stheraven typedef typename __pointer_traits::template 534227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 535227825Stheraven rebind<const value_type> 536227825Stheraven#else 537227825Stheraven rebind<const value_type>::other 538227825Stheraven#endif 539227825Stheraven pointer; 540227825Stheraven 541261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 542261272Sdim { 543261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 544261272Sdim __get_db()->__insert_i(this); 545261272Sdim#endif 546261272Sdim } 547261272Sdim 548227825Stheraven _LIBCPP_INLINE_VISIBILITY 549227825Stheraven __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 550227825Stheraven : __node_(__x.__node_), 551227825Stheraven __bucket_(__x.__bucket_), 552227825Stheraven __bucket_count_(__x.__bucket_count_) 553261272Sdim { 554261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 555261272Sdim __get_db()->__iterator_copy(this, &__x); 556261272Sdim#endif 557261272Sdim } 558227825Stheraven 559261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 560261272Sdim 561227825Stheraven _LIBCPP_INLINE_VISIBILITY 562261272Sdim __hash_const_local_iterator(const __hash_const_local_iterator& __i) 563261272Sdim : __node_(__i.__node_), 564261272Sdim __bucket_(__i.__bucket_), 565261272Sdim __bucket_count_(__i.__bucket_count_) 566261272Sdim { 567261272Sdim __get_db()->__iterator_copy(this, &__i); 568261272Sdim } 569261272Sdim 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571261272Sdim ~__hash_const_local_iterator() 572261272Sdim { 573261272Sdim __get_db()->__erase_i(this); 574261272Sdim } 575227825Stheraven 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577261272Sdim __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 578261272Sdim { 579261272Sdim if (this != &__i) 580261272Sdim { 581261272Sdim __get_db()->__iterator_copy(this, &__i); 582261272Sdim __node_ = __i.__node_; 583261272Sdim __bucket_ = __i.__bucket_; 584261272Sdim __bucket_count_ = __i.__bucket_count_; 585261272Sdim } 586261272Sdim return *this; 587261272Sdim } 588261272Sdim 589261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 590261272Sdim 591261272Sdim _LIBCPP_INLINE_VISIBILITY 592261272Sdim reference operator*() const 593261272Sdim { 594261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 595261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 596261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 597261272Sdim#endif 598261272Sdim return __node_->__value_; 599261272Sdim } 600261272Sdim _LIBCPP_INLINE_VISIBILITY 601261272Sdim pointer operator->() const 602261272Sdim { 603261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 604261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 605261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 606261272Sdim#endif 607261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 608261272Sdim } 609261272Sdim 610261272Sdim _LIBCPP_INLINE_VISIBILITY 611227825Stheraven __hash_const_local_iterator& operator++() 612227825Stheraven { 613261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 614261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 615261272Sdim "Attempted to increment non-incrementable unordered container const_local_iterator"); 616261272Sdim#endif 617227825Stheraven __node_ = __node_->__next_; 618241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 619227825Stheraven __node_ = nullptr; 620227825Stheraven return *this; 621227825Stheraven } 622227825Stheraven 623227825Stheraven _LIBCPP_INLINE_VISIBILITY 624227825Stheraven __hash_const_local_iterator operator++(int) 625227825Stheraven { 626227825Stheraven __hash_const_local_iterator __t(*this); 627227825Stheraven ++(*this); 628227825Stheraven return __t; 629227825Stheraven } 630227825Stheraven 631227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 632227825Stheraven bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 633261272Sdim { 634261272Sdim return __x.__node_ == __y.__node_; 635261272Sdim } 636227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 637227825Stheraven bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 638261272Sdim {return !(__x == __y);} 639227825Stheraven 640227825Stheravenprivate: 641261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 642227825Stheraven _LIBCPP_INLINE_VISIBILITY 643227825Stheraven __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 644261272Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 645261272Sdim : __node_(__node), 646261272Sdim __bucket_(__bucket), 647261272Sdim __bucket_count_(__bucket_count) 648261272Sdim { 649261272Sdim __get_db()->__insert_ic(this, __c); 650261272Sdim if (__node_ != nullptr) 651261272Sdim __node_ = __node_->__next_; 652261272Sdim } 653261272Sdim#else 654261272Sdim _LIBCPP_INLINE_VISIBILITY 655261272Sdim __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 656227825Stheraven size_t __bucket_count) _NOEXCEPT 657227825Stheraven : __node_(__node), 658227825Stheraven __bucket_(__bucket), 659227825Stheraven __bucket_count_(__bucket_count) 660227825Stheraven { 661227825Stheraven if (__node_ != nullptr) 662227825Stheraven __node_ = __node_->__next_; 663227825Stheraven } 664261272Sdim#endif 665227825Stheraven template <class, class, class, class> friend class __hash_table; 666261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 667227825Stheraven}; 668227825Stheraven 669227825Stheraventemplate <class _Alloc> 670227825Stheravenclass __bucket_list_deallocator 671227825Stheraven{ 672227825Stheraven typedef _Alloc allocator_type; 673227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 674227825Stheraven typedef typename __alloc_traits::size_type size_type; 675227825Stheraven 676227825Stheraven __compressed_pair<size_type, allocator_type> __data_; 677227825Stheravenpublic: 678227825Stheraven typedef typename __alloc_traits::pointer pointer; 679227825Stheraven 680227825Stheraven _LIBCPP_INLINE_VISIBILITY 681227825Stheraven __bucket_list_deallocator() 682227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 683227825Stheraven : __data_(0) {} 684227825Stheraven 685227825Stheraven _LIBCPP_INLINE_VISIBILITY 686227825Stheraven __bucket_list_deallocator(const allocator_type& __a, size_type __size) 687227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 688227825Stheraven : __data_(__size, __a) {} 689227825Stheraven 690227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 691227825Stheraven 692227825Stheraven _LIBCPP_INLINE_VISIBILITY 693227825Stheraven __bucket_list_deallocator(__bucket_list_deallocator&& __x) 694227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 695227825Stheraven : __data_(_VSTD::move(__x.__data_)) 696227825Stheraven { 697227825Stheraven __x.size() = 0; 698227825Stheraven } 699227825Stheraven 700227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 701227825Stheraven 702227825Stheraven _LIBCPP_INLINE_VISIBILITY 703227825Stheraven size_type& size() _NOEXCEPT {return __data_.first();} 704227825Stheraven _LIBCPP_INLINE_VISIBILITY 705227825Stheraven size_type size() const _NOEXCEPT {return __data_.first();} 706227825Stheraven 707227825Stheraven _LIBCPP_INLINE_VISIBILITY 708227825Stheraven allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 709227825Stheraven _LIBCPP_INLINE_VISIBILITY 710227825Stheraven const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 711227825Stheraven 712227825Stheraven _LIBCPP_INLINE_VISIBILITY 713227825Stheraven void operator()(pointer __p) _NOEXCEPT 714227825Stheraven { 715227825Stheraven __alloc_traits::deallocate(__alloc(), __p, size()); 716227825Stheraven } 717227825Stheraven}; 718227825Stheraven 719227825Stheraventemplate <class _Alloc> class __hash_map_node_destructor; 720227825Stheraven 721227825Stheraventemplate <class _Alloc> 722227825Stheravenclass __hash_node_destructor 723227825Stheraven{ 724227825Stheraven typedef _Alloc allocator_type; 725227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 726227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 727227825Stheravenpublic: 728227825Stheraven typedef typename __alloc_traits::pointer pointer; 729227825Stheravenprivate: 730227825Stheraven 731227825Stheraven allocator_type& __na_; 732227825Stheraven 733227825Stheraven __hash_node_destructor& operator=(const __hash_node_destructor&); 734227825Stheraven 735227825Stheravenpublic: 736227825Stheraven bool __value_constructed; 737227825Stheraven 738227825Stheraven _LIBCPP_INLINE_VISIBILITY 739227825Stheraven explicit __hash_node_destructor(allocator_type& __na, 740227825Stheraven bool __constructed = false) _NOEXCEPT 741227825Stheraven : __na_(__na), 742227825Stheraven __value_constructed(__constructed) 743227825Stheraven {} 744227825Stheraven 745227825Stheraven _LIBCPP_INLINE_VISIBILITY 746227825Stheraven void operator()(pointer __p) _NOEXCEPT 747227825Stheraven { 748227825Stheraven if (__value_constructed) 749227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 750227825Stheraven if (__p) 751227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 752227825Stheraven } 753227825Stheraven 754227825Stheraven template <class> friend class __hash_map_node_destructor; 755227825Stheraven}; 756227825Stheraven 757227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 758227825Stheravenclass __hash_table 759227825Stheraven{ 760227825Stheravenpublic: 761227825Stheraven typedef _Tp value_type; 762227825Stheraven typedef _Hash hasher; 763227825Stheraven typedef _Equal key_equal; 764227825Stheraven typedef _Alloc allocator_type; 765227825Stheraven 766227825Stheravenprivate: 767227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 768227825Stheravenpublic: 769227825Stheraven typedef value_type& reference; 770227825Stheraven typedef const value_type& const_reference; 771227825Stheraven typedef typename __alloc_traits::pointer pointer; 772227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 773227825Stheraven typedef typename __alloc_traits::size_type size_type; 774227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 775227825Stheravenpublic: 776227825Stheraven // Create __node 777227825Stheraven typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 778288943Sdim typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 779227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 780227825Stheraven typedef typename __node_traits::pointer __node_pointer; 781253146Stheraven typedef typename __node_traits::pointer __node_const_pointer; 782232924Stheraven typedef __hash_node_base<__node_pointer> __first_node; 783253146Stheraven typedef typename pointer_traits<__node_pointer>::template 784253146Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 785253146Stheraven rebind<__first_node> 786253146Stheraven#else 787253146Stheraven rebind<__first_node>::other 788253146Stheraven#endif 789253146Stheraven __node_base_pointer; 790227825Stheraven 791227825Stheravenprivate: 792227825Stheraven 793288943Sdim typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator; 794227825Stheraven typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 795227825Stheraven typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 796227825Stheraven typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 797227825Stheraven typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 798227825Stheraven 799227825Stheraven // --- Member data begin --- 800227825Stheraven __bucket_list __bucket_list_; 801227825Stheraven __compressed_pair<__first_node, __node_allocator> __p1_; 802227825Stheraven __compressed_pair<size_type, hasher> __p2_; 803227825Stheraven __compressed_pair<float, key_equal> __p3_; 804227825Stheraven // --- Member data end --- 805227825Stheraven 806227825Stheraven _LIBCPP_INLINE_VISIBILITY 807227825Stheraven size_type& size() _NOEXCEPT {return __p2_.first();} 808227825Stheravenpublic: 809227825Stheraven _LIBCPP_INLINE_VISIBILITY 810227825Stheraven size_type size() const _NOEXCEPT {return __p2_.first();} 811227825Stheraven 812227825Stheraven _LIBCPP_INLINE_VISIBILITY 813227825Stheraven hasher& hash_function() _NOEXCEPT {return __p2_.second();} 814227825Stheraven _LIBCPP_INLINE_VISIBILITY 815227825Stheraven const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 816227825Stheraven 817227825Stheraven _LIBCPP_INLINE_VISIBILITY 818227825Stheraven float& max_load_factor() _NOEXCEPT {return __p3_.first();} 819227825Stheraven _LIBCPP_INLINE_VISIBILITY 820227825Stheraven float max_load_factor() const _NOEXCEPT {return __p3_.first();} 821227825Stheraven 822227825Stheraven _LIBCPP_INLINE_VISIBILITY 823227825Stheraven key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 824227825Stheraven _LIBCPP_INLINE_VISIBILITY 825227825Stheraven const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 826227825Stheraven 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 829227825Stheraven _LIBCPP_INLINE_VISIBILITY 830227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 831227825Stheraven {return __p1_.second();} 832227825Stheraven 833227825Stheravenpublic: 834227825Stheraven typedef __hash_iterator<__node_pointer> iterator; 835253146Stheraven typedef __hash_const_iterator<__node_pointer> const_iterator; 836227825Stheraven typedef __hash_local_iterator<__node_pointer> local_iterator; 837253146Stheraven typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 838227825Stheraven 839227825Stheraven __hash_table() 840227825Stheraven _NOEXCEPT_( 841227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 842227825Stheraven is_nothrow_default_constructible<__first_node>::value && 843227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 844227825Stheraven is_nothrow_default_constructible<hasher>::value && 845227825Stheraven is_nothrow_default_constructible<key_equal>::value); 846227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql); 847227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql, 848227825Stheraven const allocator_type& __a); 849227825Stheraven explicit __hash_table(const allocator_type& __a); 850227825Stheraven __hash_table(const __hash_table& __u); 851227825Stheraven __hash_table(const __hash_table& __u, const allocator_type& __a); 852227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 853227825Stheraven __hash_table(__hash_table&& __u) 854227825Stheraven _NOEXCEPT_( 855227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 856227825Stheraven is_nothrow_move_constructible<__first_node>::value && 857227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 858227825Stheraven is_nothrow_move_constructible<hasher>::value && 859227825Stheraven is_nothrow_move_constructible<key_equal>::value); 860227825Stheraven __hash_table(__hash_table&& __u, const allocator_type& __a); 861227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 862227825Stheraven ~__hash_table(); 863227825Stheraven 864227825Stheraven __hash_table& operator=(const __hash_table& __u); 865227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 866227825Stheraven __hash_table& operator=(__hash_table&& __u) 867227825Stheraven _NOEXCEPT_( 868227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 869227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 870227825Stheraven is_nothrow_move_assignable<hasher>::value && 871227825Stheraven is_nothrow_move_assignable<key_equal>::value); 872227825Stheraven#endif 873227825Stheraven template <class _InputIterator> 874227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 875227825Stheraven template <class _InputIterator> 876227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 877227825Stheraven 878227825Stheraven _LIBCPP_INLINE_VISIBILITY 879227825Stheraven size_type max_size() const _NOEXCEPT 880227825Stheraven { 881227825Stheraven return allocator_traits<__pointer_allocator>::max_size( 882227825Stheraven __bucket_list_.get_deleter().__alloc()); 883227825Stheraven } 884227825Stheraven 885227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 886227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 887227825Stheraven iterator __node_insert_multi(const_iterator __p, 888227825Stheraven __node_pointer __nd); 889227825Stheraven 890227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 891227825Stheraven template <class... _Args> 892227825Stheraven pair<iterator, bool> __emplace_unique(_Args&&... __args); 893227825Stheraven template <class... _Args> 894227825Stheraven iterator __emplace_multi(_Args&&... __args); 895227825Stheraven template <class... _Args> 896227825Stheraven iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 897227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 898227825Stheraven 899288943Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 900288943Sdim template <class _ValueTp> 901288943Sdim _LIBCPP_INLINE_VISIBILITY 902288943Sdim pair<iterator, bool> __insert_unique_value(_ValueTp&& __x); 903288943Sdim#else 904288943Sdim _LIBCPP_INLINE_VISIBILITY 905288943Sdim pair<iterator, bool> __insert_unique_value(const value_type& __x); 906288943Sdim#endif 907288943Sdim 908227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __x); 909227825Stheraven 910227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 911288943Sdim pair<iterator, bool> __insert_unique(value_type&& __x); 912232924Stheraven template <class _Pp> 913288943Sdim pair<iterator, bool> __insert_unique(_Pp&& __x); 914227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 915227825Stheraven 916227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 917232924Stheraven template <class _Pp> 918232924Stheraven iterator __insert_multi(_Pp&& __x); 919232924Stheraven template <class _Pp> 920232924Stheraven iterator __insert_multi(const_iterator __p, _Pp&& __x); 921227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 922227825Stheraven iterator __insert_multi(const value_type& __x); 923227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __x); 924227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 925227825Stheraven 926227825Stheraven void clear() _NOEXCEPT; 927227825Stheraven void rehash(size_type __n); 928227825Stheraven _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 929227825Stheraven {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 930227825Stheraven 931227825Stheraven _LIBCPP_INLINE_VISIBILITY 932227825Stheraven size_type bucket_count() const _NOEXCEPT 933227825Stheraven { 934227825Stheraven return __bucket_list_.get_deleter().size(); 935227825Stheraven } 936227825Stheraven 937227825Stheraven iterator begin() _NOEXCEPT; 938227825Stheraven iterator end() _NOEXCEPT; 939227825Stheraven const_iterator begin() const _NOEXCEPT; 940227825Stheraven const_iterator end() const _NOEXCEPT; 941227825Stheraven 942227825Stheraven template <class _Key> 943227825Stheraven _LIBCPP_INLINE_VISIBILITY 944227825Stheraven size_type bucket(const _Key& __k) const 945261272Sdim { 946261272Sdim _LIBCPP_ASSERT(bucket_count() > 0, 947261272Sdim "unordered container::bucket(key) called when bucket_count() == 0"); 948261272Sdim return __constrain_hash(hash_function()(__k), bucket_count()); 949261272Sdim } 950227825Stheraven 951227825Stheraven template <class _Key> 952227825Stheraven iterator find(const _Key& __x); 953227825Stheraven template <class _Key> 954227825Stheraven const_iterator find(const _Key& __x) const; 955227825Stheraven 956232924Stheraven typedef __hash_node_destructor<__node_allocator> _Dp; 957232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 958227825Stheraven 959227825Stheraven iterator erase(const_iterator __p); 960227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 961227825Stheraven template <class _Key> 962227825Stheraven size_type __erase_unique(const _Key& __k); 963227825Stheraven template <class _Key> 964227825Stheraven size_type __erase_multi(const _Key& __k); 965227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 966227825Stheraven 967227825Stheraven template <class _Key> 968227825Stheraven size_type __count_unique(const _Key& __k) const; 969227825Stheraven template <class _Key> 970227825Stheraven size_type __count_multi(const _Key& __k) const; 971227825Stheraven 972227825Stheraven template <class _Key> 973227825Stheraven pair<iterator, iterator> 974227825Stheraven __equal_range_unique(const _Key& __k); 975227825Stheraven template <class _Key> 976227825Stheraven pair<const_iterator, const_iterator> 977227825Stheraven __equal_range_unique(const _Key& __k) const; 978227825Stheraven 979227825Stheraven template <class _Key> 980227825Stheraven pair<iterator, iterator> 981227825Stheraven __equal_range_multi(const _Key& __k); 982227825Stheraven template <class _Key> 983227825Stheraven pair<const_iterator, const_iterator> 984227825Stheraven __equal_range_multi(const _Key& __k) const; 985227825Stheraven 986227825Stheraven void swap(__hash_table& __u) 987227825Stheraven _NOEXCEPT_( 988288943Sdim __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 989288943Sdim#if _LIBCPP_STD_VER <= 11 990288943Sdim && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 991288943Sdim || __is_nothrow_swappable<__pointer_allocator>::value) 992288943Sdim && (!__node_traits::propagate_on_container_swap::value 993288943Sdim || __is_nothrow_swappable<__node_allocator>::value) 994288943Sdim#endif 995288943Sdim ); 996227825Stheraven 997227825Stheraven _LIBCPP_INLINE_VISIBILITY 998227825Stheraven size_type max_bucket_count() const _NOEXCEPT 999253146Stheraven {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1000227825Stheraven size_type bucket_size(size_type __n) const; 1001227825Stheraven _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1002227825Stheraven { 1003227825Stheraven size_type __bc = bucket_count(); 1004227825Stheraven return __bc != 0 ? (float)size() / __bc : 0.f; 1005227825Stheraven } 1006227825Stheraven _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1007261272Sdim { 1008261272Sdim _LIBCPP_ASSERT(__mlf > 0, 1009261272Sdim "unordered container::max_load_factor(lf) called with lf <= 0"); 1010261272Sdim max_load_factor() = _VSTD::max(__mlf, load_factor()); 1011261272Sdim } 1012227825Stheraven 1013261272Sdim _LIBCPP_INLINE_VISIBILITY 1014261272Sdim local_iterator 1015261272Sdim begin(size_type __n) 1016261272Sdim { 1017261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1018261272Sdim "unordered container::begin(n) called with n >= bucket_count()"); 1019261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1020261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1021261272Sdim#else 1022261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1023261272Sdim#endif 1024261272Sdim } 1025261272Sdim 1026261272Sdim _LIBCPP_INLINE_VISIBILITY 1027261272Sdim local_iterator 1028261272Sdim end(size_type __n) 1029261272Sdim { 1030261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1031261272Sdim "unordered container::end(n) called with n >= bucket_count()"); 1032261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1033261272Sdim return local_iterator(nullptr, __n, bucket_count(), this); 1034261272Sdim#else 1035261272Sdim return local_iterator(nullptr, __n, bucket_count()); 1036261272Sdim#endif 1037261272Sdim } 1038261272Sdim 1039261272Sdim _LIBCPP_INLINE_VISIBILITY 1040261272Sdim const_local_iterator 1041261272Sdim cbegin(size_type __n) const 1042261272Sdim { 1043261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1044261272Sdim "unordered container::cbegin(n) called with n >= bucket_count()"); 1045261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1046261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1047261272Sdim#else 1048261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1049261272Sdim#endif 1050261272Sdim } 1051261272Sdim 1052261272Sdim _LIBCPP_INLINE_VISIBILITY 1053261272Sdim const_local_iterator 1054261272Sdim cend(size_type __n) const 1055261272Sdim { 1056261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1057261272Sdim "unordered container::cend(n) called with n >= bucket_count()"); 1058261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1059261272Sdim return const_local_iterator(nullptr, __n, bucket_count(), this); 1060261272Sdim#else 1061261272Sdim return const_local_iterator(nullptr, __n, bucket_count()); 1062261272Sdim#endif 1063261272Sdim } 1064261272Sdim 1065261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1066261272Sdim 1067261272Sdim bool __dereferenceable(const const_iterator* __i) const; 1068261272Sdim bool __decrementable(const const_iterator* __i) const; 1069261272Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1070261272Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1071261272Sdim 1072261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1073261272Sdim 1074227825Stheravenprivate: 1075227825Stheraven void __rehash(size_type __n); 1076227825Stheraven 1077227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1078227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1079227825Stheraven template <class ..._Args> 1080227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1081227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1082227825Stheraven __node_holder __construct_node(value_type&& __v, size_t __hash); 1083227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1084227825Stheraven __node_holder __construct_node(const value_type& __v); 1085227825Stheraven#endif 1086227825Stheraven __node_holder __construct_node(const value_type& __v, size_t __hash); 1087227825Stheraven 1088227825Stheraven _LIBCPP_INLINE_VISIBILITY 1089227825Stheraven void __copy_assign_alloc(const __hash_table& __u) 1090227825Stheraven {__copy_assign_alloc(__u, integral_constant<bool, 1091227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1092227825Stheraven void __copy_assign_alloc(const __hash_table& __u, true_type); 1093227825Stheraven _LIBCPP_INLINE_VISIBILITY 1094232924Stheraven void __copy_assign_alloc(const __hash_table&, false_type) {} 1095227825Stheraven 1096227825Stheraven void __move_assign(__hash_table& __u, false_type); 1097227825Stheraven void __move_assign(__hash_table& __u, true_type) 1098227825Stheraven _NOEXCEPT_( 1099227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1100227825Stheraven is_nothrow_move_assignable<hasher>::value && 1101227825Stheraven is_nothrow_move_assignable<key_equal>::value); 1102227825Stheraven _LIBCPP_INLINE_VISIBILITY 1103227825Stheraven void __move_assign_alloc(__hash_table& __u) 1104227825Stheraven _NOEXCEPT_( 1105227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1106227825Stheraven (is_nothrow_move_assignable<__pointer_allocator>::value && 1107227825Stheraven is_nothrow_move_assignable<__node_allocator>::value)) 1108227825Stheraven {__move_assign_alloc(__u, integral_constant<bool, 1109227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1110227825Stheraven _LIBCPP_INLINE_VISIBILITY 1111227825Stheraven void __move_assign_alloc(__hash_table& __u, true_type) 1112227825Stheraven _NOEXCEPT_( 1113227825Stheraven is_nothrow_move_assignable<__pointer_allocator>::value && 1114227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1115227825Stheraven { 1116227825Stheraven __bucket_list_.get_deleter().__alloc() = 1117227825Stheraven _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1118227825Stheraven __node_alloc() = _VSTD::move(__u.__node_alloc()); 1119227825Stheraven } 1120227825Stheraven _LIBCPP_INLINE_VISIBILITY 1121227825Stheraven void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1122227825Stheraven 1123227825Stheraven void __deallocate(__node_pointer __np) _NOEXCEPT; 1124227825Stheraven __node_pointer __detach() _NOEXCEPT; 1125253146Stheraven 1126261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1127261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1128227825Stheraven}; 1129227825Stheraven 1130227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1131227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1132227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1133227825Stheraven _NOEXCEPT_( 1134227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 1135227825Stheraven is_nothrow_default_constructible<__first_node>::value && 1136227825Stheraven is_nothrow_default_constructible<hasher>::value && 1137227825Stheraven is_nothrow_default_constructible<key_equal>::value) 1138227825Stheraven : __p2_(0), 1139227825Stheraven __p3_(1.0f) 1140227825Stheraven{ 1141227825Stheraven} 1142227825Stheraven 1143227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1144227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1145227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1146227825Stheraven const key_equal& __eql) 1147227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter()), 1148227825Stheraven __p1_(), 1149227825Stheraven __p2_(0, __hf), 1150227825Stheraven __p3_(1.0f, __eql) 1151227825Stheraven{ 1152227825Stheraven} 1153227825Stheraven 1154227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1155227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1156227825Stheraven const key_equal& __eql, 1157227825Stheraven const allocator_type& __a) 1158227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1159227825Stheraven __p1_(__node_allocator(__a)), 1160227825Stheraven __p2_(0, __hf), 1161227825Stheraven __p3_(1.0f, __eql) 1162227825Stheraven{ 1163227825Stheraven} 1164227825Stheraven 1165227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1166227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1167227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1168227825Stheraven __p1_(__node_allocator(__a)), 1169227825Stheraven __p2_(0), 1170227825Stheraven __p3_(1.0f) 1171227825Stheraven{ 1172227825Stheraven} 1173227825Stheraven 1174227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1175227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1176227825Stheraven : __bucket_list_(nullptr, 1177227825Stheraven __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1178227825Stheraven select_on_container_copy_construction( 1179227825Stheraven __u.__bucket_list_.get_deleter().__alloc()), 0)), 1180227825Stheraven __p1_(allocator_traits<__node_allocator>:: 1181227825Stheraven select_on_container_copy_construction(__u.__node_alloc())), 1182227825Stheraven __p2_(0, __u.hash_function()), 1183227825Stheraven __p3_(__u.__p3_) 1184227825Stheraven{ 1185227825Stheraven} 1186227825Stheraven 1187227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1188227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1189227825Stheraven const allocator_type& __a) 1190227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1191227825Stheraven __p1_(__node_allocator(__a)), 1192227825Stheraven __p2_(0, __u.hash_function()), 1193227825Stheraven __p3_(__u.__p3_) 1194227825Stheraven{ 1195227825Stheraven} 1196227825Stheraven 1197227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1198227825Stheraven 1199227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1200227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1201227825Stheraven _NOEXCEPT_( 1202227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 1203227825Stheraven is_nothrow_move_constructible<__first_node>::value && 1204227825Stheraven is_nothrow_move_constructible<hasher>::value && 1205227825Stheraven is_nothrow_move_constructible<key_equal>::value) 1206227825Stheraven : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1207227825Stheraven __p1_(_VSTD::move(__u.__p1_)), 1208227825Stheraven __p2_(_VSTD::move(__u.__p2_)), 1209227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1210227825Stheraven{ 1211227825Stheraven if (size() > 0) 1212227825Stheraven { 1213241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1214253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1215227825Stheraven __u.__p1_.first().__next_ = nullptr; 1216227825Stheraven __u.size() = 0; 1217227825Stheraven } 1218227825Stheraven} 1219227825Stheraven 1220227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1221227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1222227825Stheraven const allocator_type& __a) 1223227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1224227825Stheraven __p1_(__node_allocator(__a)), 1225227825Stheraven __p2_(0, _VSTD::move(__u.hash_function())), 1226227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1227227825Stheraven{ 1228227825Stheraven if (__a == allocator_type(__u.__node_alloc())) 1229227825Stheraven { 1230227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1231227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1232227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1233227825Stheraven if (__u.size() > 0) 1234227825Stheraven { 1235227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1236227825Stheraven __u.__p1_.first().__next_ = nullptr; 1237241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1238253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1239227825Stheraven size() = __u.size(); 1240227825Stheraven __u.size() = 0; 1241227825Stheraven } 1242227825Stheraven } 1243227825Stheraven} 1244227825Stheraven 1245227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1246227825Stheraven 1247227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1248227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1249227825Stheraven{ 1250227825Stheraven __deallocate(__p1_.first().__next_); 1251261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1252261272Sdim __get_db()->__erase_c(this); 1253261272Sdim#endif 1254227825Stheraven} 1255227825Stheraven 1256227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1257227825Stheravenvoid 1258227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1259227825Stheraven const __hash_table& __u, true_type) 1260227825Stheraven{ 1261227825Stheraven if (__node_alloc() != __u.__node_alloc()) 1262227825Stheraven { 1263227825Stheraven clear(); 1264227825Stheraven __bucket_list_.reset(); 1265227825Stheraven __bucket_list_.get_deleter().size() = 0; 1266227825Stheraven } 1267227825Stheraven __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1268227825Stheraven __node_alloc() = __u.__node_alloc(); 1269227825Stheraven} 1270227825Stheraven 1271227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1272227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1273227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1274227825Stheraven{ 1275227825Stheraven if (this != &__u) 1276227825Stheraven { 1277227825Stheraven __copy_assign_alloc(__u); 1278227825Stheraven hash_function() = __u.hash_function(); 1279227825Stheraven key_eq() = __u.key_eq(); 1280227825Stheraven max_load_factor() = __u.max_load_factor(); 1281227825Stheraven __assign_multi(__u.begin(), __u.end()); 1282227825Stheraven } 1283227825Stheraven return *this; 1284227825Stheraven} 1285227825Stheraven 1286227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1287227825Stheravenvoid 1288227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1289227825Stheraven _NOEXCEPT 1290227825Stheraven{ 1291227825Stheraven __node_allocator& __na = __node_alloc(); 1292227825Stheraven while (__np != nullptr) 1293227825Stheraven { 1294227825Stheraven __node_pointer __next = __np->__next_; 1295261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1296261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 1297261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1298261272Sdim { 1299261272Sdim --__p; 1300261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 1301261272Sdim if (__i->__node_ == __np) 1302261272Sdim { 1303261272Sdim (*__p)->__c_ = nullptr; 1304261272Sdim if (--__c->end_ != __p) 1305261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1306261272Sdim } 1307261272Sdim } 1308261272Sdim __get_db()->unlock(); 1309261272Sdim#endif 1310227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1311227825Stheraven __node_traits::deallocate(__na, __np, 1); 1312227825Stheraven __np = __next; 1313227825Stheraven } 1314227825Stheraven} 1315227825Stheraven 1316227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1317227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1318227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1319227825Stheraven{ 1320227825Stheraven size_type __bc = bucket_count(); 1321227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1322227825Stheraven __bucket_list_[__i] = nullptr; 1323227825Stheraven size() = 0; 1324227825Stheraven __node_pointer __cache = __p1_.first().__next_; 1325227825Stheraven __p1_.first().__next_ = nullptr; 1326227825Stheraven return __cache; 1327227825Stheraven} 1328227825Stheraven 1329227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1330227825Stheraven 1331227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1332227825Stheravenvoid 1333227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1334227825Stheraven __hash_table& __u, true_type) 1335227825Stheraven _NOEXCEPT_( 1336227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1337227825Stheraven is_nothrow_move_assignable<hasher>::value && 1338227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1339227825Stheraven{ 1340227825Stheraven clear(); 1341227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1342227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1343227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1344227825Stheraven __move_assign_alloc(__u); 1345227825Stheraven size() = __u.size(); 1346227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1347227825Stheraven max_load_factor() = __u.max_load_factor(); 1348227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1349227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1350227825Stheraven if (size() > 0) 1351227825Stheraven { 1352241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1353253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1354227825Stheraven __u.__p1_.first().__next_ = nullptr; 1355227825Stheraven __u.size() = 0; 1356227825Stheraven } 1357261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1358261272Sdim __get_db()->swap(this, &__u); 1359261272Sdim#endif 1360227825Stheraven} 1361227825Stheraven 1362227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1363227825Stheravenvoid 1364227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1365227825Stheraven __hash_table& __u, false_type) 1366227825Stheraven{ 1367227825Stheraven if (__node_alloc() == __u.__node_alloc()) 1368227825Stheraven __move_assign(__u, true_type()); 1369227825Stheraven else 1370227825Stheraven { 1371227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1372227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1373227825Stheraven max_load_factor() = __u.max_load_factor(); 1374227825Stheraven if (bucket_count() != 0) 1375227825Stheraven { 1376227825Stheraven __node_pointer __cache = __detach(); 1377227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1378227825Stheraven try 1379227825Stheraven { 1380227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1381227825Stheraven const_iterator __i = __u.begin(); 1382227825Stheraven while (__cache != nullptr && __u.size() != 0) 1383227825Stheraven { 1384227825Stheraven __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1385227825Stheraven __node_pointer __next = __cache->__next_; 1386227825Stheraven __node_insert_multi(__cache); 1387227825Stheraven __cache = __next; 1388227825Stheraven } 1389227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1390227825Stheraven } 1391227825Stheraven catch (...) 1392227825Stheraven { 1393227825Stheraven __deallocate(__cache); 1394227825Stheraven throw; 1395227825Stheraven } 1396227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1397227825Stheraven __deallocate(__cache); 1398227825Stheraven } 1399227825Stheraven const_iterator __i = __u.begin(); 1400227825Stheraven while (__u.size() != 0) 1401227825Stheraven { 1402227825Stheraven __node_holder __h = 1403227825Stheraven __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1404227825Stheraven __node_insert_multi(__h.get()); 1405227825Stheraven __h.release(); 1406227825Stheraven } 1407227825Stheraven } 1408227825Stheraven} 1409227825Stheraven 1410227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1411227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1412227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1413227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1414227825Stheraven _NOEXCEPT_( 1415227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1416227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1417227825Stheraven is_nothrow_move_assignable<hasher>::value && 1418227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1419227825Stheraven{ 1420227825Stheraven __move_assign(__u, integral_constant<bool, 1421227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1422227825Stheraven return *this; 1423227825Stheraven} 1424227825Stheraven 1425227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1426227825Stheraven 1427227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1428227825Stheraventemplate <class _InputIterator> 1429227825Stheravenvoid 1430227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1431227825Stheraven _InputIterator __last) 1432227825Stheraven{ 1433227825Stheraven if (bucket_count() != 0) 1434227825Stheraven { 1435227825Stheraven __node_pointer __cache = __detach(); 1436227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1437227825Stheraven try 1438227825Stheraven { 1439227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1440227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1441227825Stheraven { 1442227825Stheraven __cache->__value_ = *__first; 1443227825Stheraven __node_pointer __next = __cache->__next_; 1444227825Stheraven __node_insert_unique(__cache); 1445227825Stheraven __cache = __next; 1446227825Stheraven } 1447227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1448227825Stheraven } 1449227825Stheraven catch (...) 1450227825Stheraven { 1451227825Stheraven __deallocate(__cache); 1452227825Stheraven throw; 1453227825Stheraven } 1454227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1455227825Stheraven __deallocate(__cache); 1456227825Stheraven } 1457227825Stheraven for (; __first != __last; ++__first) 1458227825Stheraven __insert_unique(*__first); 1459227825Stheraven} 1460227825Stheraven 1461227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1462227825Stheraventemplate <class _InputIterator> 1463227825Stheravenvoid 1464227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1465227825Stheraven _InputIterator __last) 1466227825Stheraven{ 1467227825Stheraven if (bucket_count() != 0) 1468227825Stheraven { 1469227825Stheraven __node_pointer __cache = __detach(); 1470227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1471227825Stheraven try 1472227825Stheraven { 1473227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1474227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1475227825Stheraven { 1476227825Stheraven __cache->__value_ = *__first; 1477227825Stheraven __node_pointer __next = __cache->__next_; 1478227825Stheraven __node_insert_multi(__cache); 1479227825Stheraven __cache = __next; 1480227825Stheraven } 1481227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1482227825Stheraven } 1483227825Stheraven catch (...) 1484227825Stheraven { 1485227825Stheraven __deallocate(__cache); 1486227825Stheraven throw; 1487227825Stheraven } 1488227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1489227825Stheraven __deallocate(__cache); 1490227825Stheraven } 1491227825Stheraven for (; __first != __last; ++__first) 1492227825Stheraven __insert_multi(*__first); 1493227825Stheraven} 1494227825Stheraven 1495227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1496227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1497227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1498227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1499227825Stheraven{ 1500261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1501261272Sdim return iterator(__p1_.first().__next_, this); 1502261272Sdim#else 1503227825Stheraven return iterator(__p1_.first().__next_); 1504261272Sdim#endif 1505227825Stheraven} 1506227825Stheraven 1507227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1508227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1509227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1510227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1511227825Stheraven{ 1512261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1513261272Sdim return iterator(nullptr, this); 1514261272Sdim#else 1515227825Stheraven return iterator(nullptr); 1516261272Sdim#endif 1517227825Stheraven} 1518227825Stheraven 1519227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1520227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1521227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1522227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1523227825Stheraven{ 1524261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1525261272Sdim return const_iterator(__p1_.first().__next_, this); 1526261272Sdim#else 1527227825Stheraven return const_iterator(__p1_.first().__next_); 1528261272Sdim#endif 1529227825Stheraven} 1530227825Stheraven 1531227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1532227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1533227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1534227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1535227825Stheraven{ 1536261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1537261272Sdim return const_iterator(nullptr, this); 1538261272Sdim#else 1539227825Stheraven return const_iterator(nullptr); 1540261272Sdim#endif 1541227825Stheraven} 1542227825Stheraven 1543227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1544227825Stheravenvoid 1545227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1546227825Stheraven{ 1547227825Stheraven if (size() > 0) 1548227825Stheraven { 1549227825Stheraven __deallocate(__p1_.first().__next_); 1550227825Stheraven __p1_.first().__next_ = nullptr; 1551227825Stheraven size_type __bc = bucket_count(); 1552227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1553227825Stheraven __bucket_list_[__i] = nullptr; 1554227825Stheraven size() = 0; 1555227825Stheraven } 1556227825Stheraven} 1557227825Stheraven 1558227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1559227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1560227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1561227825Stheraven{ 1562227825Stheraven __nd->__hash_ = hash_function()(__nd->__value_); 1563227825Stheraven size_type __bc = bucket_count(); 1564227825Stheraven bool __inserted = false; 1565227825Stheraven __node_pointer __ndptr; 1566227825Stheraven size_t __chash; 1567227825Stheraven if (__bc != 0) 1568227825Stheraven { 1569241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1570227825Stheraven __ndptr = __bucket_list_[__chash]; 1571227825Stheraven if (__ndptr != nullptr) 1572227825Stheraven { 1573227825Stheraven for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1574241900Sdim __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1575227825Stheraven __ndptr = __ndptr->__next_) 1576227825Stheraven { 1577227825Stheraven if (key_eq()(__ndptr->__value_, __nd->__value_)) 1578227825Stheraven goto __done; 1579227825Stheraven } 1580227825Stheraven } 1581227825Stheraven } 1582227825Stheraven { 1583227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1584227825Stheraven { 1585288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1586227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1587227825Stheraven __bc = bucket_count(); 1588241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1589227825Stheraven } 1590227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1591227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1592227825Stheraven if (__pn == nullptr) 1593227825Stheraven { 1594253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1595227825Stheraven __nd->__next_ = __pn->__next_; 1596227825Stheraven __pn->__next_ = __nd; 1597227825Stheraven // fix up __bucket_list_ 1598227825Stheraven __bucket_list_[__chash] = __pn; 1599227825Stheraven if (__nd->__next_ != nullptr) 1600241900Sdim __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1601227825Stheraven } 1602227825Stheraven else 1603227825Stheraven { 1604227825Stheraven __nd->__next_ = __pn->__next_; 1605227825Stheraven __pn->__next_ = __nd; 1606227825Stheraven } 1607227825Stheraven __ndptr = __nd; 1608227825Stheraven // increment size 1609227825Stheraven ++size(); 1610227825Stheraven __inserted = true; 1611227825Stheraven } 1612227825Stheraven__done: 1613261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1614261272Sdim return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1615261272Sdim#else 1616227825Stheraven return pair<iterator, bool>(iterator(__ndptr), __inserted); 1617261272Sdim#endif 1618227825Stheraven} 1619227825Stheraven 1620227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1621227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1622227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1623227825Stheraven{ 1624227825Stheraven __cp->__hash_ = hash_function()(__cp->__value_); 1625227825Stheraven size_type __bc = bucket_count(); 1626227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1627227825Stheraven { 1628288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1629227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1630227825Stheraven __bc = bucket_count(); 1631227825Stheraven } 1632241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1633227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1634227825Stheraven if (__pn == nullptr) 1635227825Stheraven { 1636253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1637227825Stheraven __cp->__next_ = __pn->__next_; 1638227825Stheraven __pn->__next_ = __cp; 1639227825Stheraven // fix up __bucket_list_ 1640227825Stheraven __bucket_list_[__chash] = __pn; 1641227825Stheraven if (__cp->__next_ != nullptr) 1642241900Sdim __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1643227825Stheraven } 1644227825Stheraven else 1645227825Stheraven { 1646227825Stheraven for (bool __found = false; __pn->__next_ != nullptr && 1647241900Sdim __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1648227825Stheraven __pn = __pn->__next_) 1649227825Stheraven { 1650227825Stheraven // __found key_eq() action 1651227825Stheraven // false false loop 1652227825Stheraven // true true loop 1653227825Stheraven // false true set __found to true 1654227825Stheraven // true false break 1655227825Stheraven if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1656227825Stheraven key_eq()(__pn->__next_->__value_, __cp->__value_))) 1657227825Stheraven { 1658227825Stheraven if (!__found) 1659227825Stheraven __found = true; 1660227825Stheraven else 1661227825Stheraven break; 1662227825Stheraven } 1663227825Stheraven } 1664227825Stheraven __cp->__next_ = __pn->__next_; 1665227825Stheraven __pn->__next_ = __cp; 1666227825Stheraven if (__cp->__next_ != nullptr) 1667227825Stheraven { 1668241900Sdim size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1669227825Stheraven if (__nhash != __chash) 1670227825Stheraven __bucket_list_[__nhash] = __cp; 1671227825Stheraven } 1672227825Stheraven } 1673227825Stheraven ++size(); 1674261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1675261272Sdim return iterator(__cp, this); 1676261272Sdim#else 1677227825Stheraven return iterator(__cp); 1678261272Sdim#endif 1679227825Stheraven} 1680227825Stheraven 1681227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1682227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1683227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1684227825Stheraven const_iterator __p, __node_pointer __cp) 1685227825Stheraven{ 1686261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1687261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1688261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1689261272Sdim " referring to this unordered container"); 1690261272Sdim#endif 1691227825Stheraven if (__p != end() && key_eq()(*__p, __cp->__value_)) 1692227825Stheraven { 1693253146Stheraven __node_pointer __np = __p.__node_; 1694227825Stheraven __cp->__hash_ = __np->__hash_; 1695227825Stheraven size_type __bc = bucket_count(); 1696227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1697227825Stheraven { 1698288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1699227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1700227825Stheraven __bc = bucket_count(); 1701227825Stheraven } 1702241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1703227825Stheraven __node_pointer __pp = __bucket_list_[__chash]; 1704227825Stheraven while (__pp->__next_ != __np) 1705227825Stheraven __pp = __pp->__next_; 1706227825Stheraven __cp->__next_ = __np; 1707227825Stheraven __pp->__next_ = __cp; 1708227825Stheraven ++size(); 1709261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1710261272Sdim return iterator(__cp, this); 1711261272Sdim#else 1712227825Stheraven return iterator(__cp); 1713261272Sdim#endif 1714227825Stheraven } 1715227825Stheraven return __node_insert_multi(__cp); 1716227825Stheraven} 1717227825Stheraven 1718227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1719227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1720227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1721227825Stheraven{ 1722288943Sdim return __insert_unique_value(__x); 1723288943Sdim} 1724288943Sdim 1725288943Sdim 1726288943Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1727288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1728288943Sdimtemplate <class _ValueTp> 1729288943Sdim_LIBCPP_INLINE_VISIBILITY 1730288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1731288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x) 1732288943Sdim#else 1733288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1734288943Sdim_LIBCPP_INLINE_VISIBILITY 1735288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1736288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x) 1737288943Sdim#endif 1738288943Sdim{ 1739288943Sdim#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1740288943Sdim typedef const value_type& _ValueTp; 1741288943Sdim#endif 1742227825Stheraven size_t __hash = hash_function()(__x); 1743227825Stheraven size_type __bc = bucket_count(); 1744227825Stheraven bool __inserted = false; 1745227825Stheraven __node_pointer __nd; 1746227825Stheraven size_t __chash; 1747227825Stheraven if (__bc != 0) 1748227825Stheraven { 1749241900Sdim __chash = __constrain_hash(__hash, __bc); 1750227825Stheraven __nd = __bucket_list_[__chash]; 1751227825Stheraven if (__nd != nullptr) 1752227825Stheraven { 1753227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1754241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1755227825Stheraven __nd = __nd->__next_) 1756227825Stheraven { 1757227825Stheraven if (key_eq()(__nd->__value_, __x)) 1758227825Stheraven goto __done; 1759227825Stheraven } 1760227825Stheraven } 1761227825Stheraven } 1762227825Stheraven { 1763288943Sdim __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash); 1764227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1765227825Stheraven { 1766288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1767227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1768227825Stheraven __bc = bucket_count(); 1769241900Sdim __chash = __constrain_hash(__hash, __bc); 1770227825Stheraven } 1771227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1772227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1773227825Stheraven if (__pn == nullptr) 1774227825Stheraven { 1775253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1776227825Stheraven __h->__next_ = __pn->__next_; 1777227825Stheraven __pn->__next_ = __h.get(); 1778227825Stheraven // fix up __bucket_list_ 1779227825Stheraven __bucket_list_[__chash] = __pn; 1780227825Stheraven if (__h->__next_ != nullptr) 1781241900Sdim __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1782227825Stheraven } 1783227825Stheraven else 1784227825Stheraven { 1785227825Stheraven __h->__next_ = __pn->__next_; 1786227825Stheraven __pn->__next_ = __h.get(); 1787227825Stheraven } 1788227825Stheraven __nd = __h.release(); 1789227825Stheraven // increment size 1790227825Stheraven ++size(); 1791227825Stheraven __inserted = true; 1792227825Stheraven } 1793227825Stheraven__done: 1794261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1795261272Sdim return pair<iterator, bool>(iterator(__nd, this), __inserted); 1796261272Sdim#else 1797227825Stheraven return pair<iterator, bool>(iterator(__nd), __inserted); 1798261272Sdim#endif 1799227825Stheraven} 1800227825Stheraven 1801227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1802227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1803227825Stheraven 1804227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1805227825Stheraventemplate <class... _Args> 1806227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1807227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1808227825Stheraven{ 1809227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1810227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1811227825Stheraven if (__r.second) 1812227825Stheraven __h.release(); 1813227825Stheraven return __r; 1814227825Stheraven} 1815227825Stheraven 1816227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1817227825Stheraventemplate <class... _Args> 1818227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1819227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1820227825Stheraven{ 1821227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1822227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1823227825Stheraven __h.release(); 1824227825Stheraven return __r; 1825227825Stheraven} 1826227825Stheraven 1827227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1828227825Stheraventemplate <class... _Args> 1829227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1830227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1831227825Stheraven const_iterator __p, _Args&&... __args) 1832227825Stheraven{ 1833261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1834261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1835261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1836261272Sdim " referring to this unordered container"); 1837261272Sdim#endif 1838227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1839227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1840227825Stheraven __h.release(); 1841227825Stheraven return __r; 1842227825Stheraven} 1843227825Stheraven 1844227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1845227825Stheraven 1846227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1847288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1848288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x) 1849288943Sdim{ 1850288943Sdim return __insert_unique_value(_VSTD::move(__x)); 1851288943Sdim} 1852288943Sdim 1853288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1854232924Stheraventemplate <class _Pp> 1855227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1856232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1857227825Stheraven{ 1858232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1859227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1860227825Stheraven if (__r.second) 1861227825Stheraven __h.release(); 1862227825Stheraven return __r; 1863227825Stheraven} 1864227825Stheraven 1865227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1866227825Stheraven 1867227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1868227825Stheraven 1869227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1870232924Stheraventemplate <class _Pp> 1871227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1872232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1873227825Stheraven{ 1874232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1875227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1876227825Stheraven __h.release(); 1877227825Stheraven return __r; 1878227825Stheraven} 1879227825Stheraven 1880227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1881232924Stheraventemplate <class _Pp> 1882227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1883227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1884232924Stheraven _Pp&& __x) 1885227825Stheraven{ 1886261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1887261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1888261272Sdim "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1889261272Sdim " referring to this unordered container"); 1890261272Sdim#endif 1891232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1892227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1893227825Stheraven __h.release(); 1894227825Stheraven return __r; 1895227825Stheraven} 1896227825Stheraven 1897227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1898227825Stheraven 1899227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1900227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1901227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1902227825Stheraven{ 1903227825Stheraven __node_holder __h = __construct_node(__x); 1904227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1905227825Stheraven __h.release(); 1906227825Stheraven return __r; 1907227825Stheraven} 1908227825Stheraven 1909227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1910227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1911227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1912227825Stheraven const value_type& __x) 1913227825Stheraven{ 1914261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1915261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1916261272Sdim "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1917261272Sdim " referring to this unordered container"); 1918261272Sdim#endif 1919227825Stheraven __node_holder __h = __construct_node(__x); 1920227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1921227825Stheraven __h.release(); 1922227825Stheraven return __r; 1923227825Stheraven} 1924227825Stheraven 1925227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1926227825Stheraven 1927227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1928227825Stheravenvoid 1929227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1930227825Stheraven{ 1931241900Sdim if (__n == 1) 1932241900Sdim __n = 2; 1933241900Sdim else if (__n & (__n - 1)) 1934241900Sdim __n = __next_prime(__n); 1935227825Stheraven size_type __bc = bucket_count(); 1936227825Stheraven if (__n > __bc) 1937227825Stheraven __rehash(__n); 1938241900Sdim else if (__n < __bc) 1939227825Stheraven { 1940227825Stheraven __n = _VSTD::max<size_type> 1941227825Stheraven ( 1942227825Stheraven __n, 1943288943Sdim __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1944288943Sdim __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1945227825Stheraven ); 1946227825Stheraven if (__n < __bc) 1947227825Stheraven __rehash(__n); 1948227825Stheraven } 1949227825Stheraven} 1950227825Stheraven 1951227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1952227825Stheravenvoid 1953227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1954227825Stheraven{ 1955261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1956261272Sdim __get_db()->__invalidate_all(this); 1957261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1958227825Stheraven __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1959227825Stheraven __bucket_list_.reset(__nbc > 0 ? 1960227825Stheraven __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1961227825Stheraven __bucket_list_.get_deleter().size() = __nbc; 1962227825Stheraven if (__nbc > 0) 1963227825Stheraven { 1964227825Stheraven for (size_type __i = 0; __i < __nbc; ++__i) 1965227825Stheraven __bucket_list_[__i] = nullptr; 1966253146Stheraven __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1967227825Stheraven __node_pointer __cp = __pp->__next_; 1968227825Stheraven if (__cp != nullptr) 1969227825Stheraven { 1970241900Sdim size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1971227825Stheraven __bucket_list_[__chash] = __pp; 1972227825Stheraven size_type __phash = __chash; 1973227825Stheraven for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1974227825Stheraven __cp = __pp->__next_) 1975227825Stheraven { 1976241900Sdim __chash = __constrain_hash(__cp->__hash_, __nbc); 1977227825Stheraven if (__chash == __phash) 1978227825Stheraven __pp = __cp; 1979227825Stheraven else 1980227825Stheraven { 1981227825Stheraven if (__bucket_list_[__chash] == nullptr) 1982227825Stheraven { 1983227825Stheraven __bucket_list_[__chash] = __pp; 1984227825Stheraven __pp = __cp; 1985227825Stheraven __phash = __chash; 1986227825Stheraven } 1987227825Stheraven else 1988227825Stheraven { 1989227825Stheraven __node_pointer __np = __cp; 1990227825Stheraven for (; __np->__next_ != nullptr && 1991227825Stheraven key_eq()(__cp->__value_, __np->__next_->__value_); 1992227825Stheraven __np = __np->__next_) 1993227825Stheraven ; 1994227825Stheraven __pp->__next_ = __np->__next_; 1995227825Stheraven __np->__next_ = __bucket_list_[__chash]->__next_; 1996227825Stheraven __bucket_list_[__chash]->__next_ = __cp; 1997227825Stheraven 1998227825Stheraven } 1999227825Stheraven } 2000227825Stheraven } 2001227825Stheraven } 2002227825Stheraven } 2003227825Stheraven} 2004227825Stheraven 2005227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2006227825Stheraventemplate <class _Key> 2007227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2008227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2009227825Stheraven{ 2010227825Stheraven size_t __hash = hash_function()(__k); 2011227825Stheraven size_type __bc = bucket_count(); 2012227825Stheraven if (__bc != 0) 2013227825Stheraven { 2014241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2015227825Stheraven __node_pointer __nd = __bucket_list_[__chash]; 2016227825Stheraven if (__nd != nullptr) 2017227825Stheraven { 2018227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2019241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2020227825Stheraven __nd = __nd->__next_) 2021227825Stheraven { 2022227825Stheraven if (key_eq()(__nd->__value_, __k)) 2023261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2024261272Sdim return iterator(__nd, this); 2025261272Sdim#else 2026227825Stheraven return iterator(__nd); 2027261272Sdim#endif 2028227825Stheraven } 2029227825Stheraven } 2030227825Stheraven } 2031227825Stheraven return end(); 2032227825Stheraven} 2033227825Stheraven 2034227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2035227825Stheraventemplate <class _Key> 2036227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2037227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2038227825Stheraven{ 2039227825Stheraven size_t __hash = hash_function()(__k); 2040227825Stheraven size_type __bc = bucket_count(); 2041227825Stheraven if (__bc != 0) 2042227825Stheraven { 2043241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2044227825Stheraven __node_const_pointer __nd = __bucket_list_[__chash]; 2045227825Stheraven if (__nd != nullptr) 2046227825Stheraven { 2047227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2048241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2049227825Stheraven __nd = __nd->__next_) 2050227825Stheraven { 2051227825Stheraven if (key_eq()(__nd->__value_, __k)) 2052261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2053261272Sdim return const_iterator(__nd, this); 2054261272Sdim#else 2055227825Stheraven return const_iterator(__nd); 2056261272Sdim#endif 2057227825Stheraven } 2058227825Stheraven } 2059227825Stheraven 2060227825Stheraven } 2061227825Stheraven return end(); 2062227825Stheraven} 2063227825Stheraven 2064227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2065227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 2066227825Stheraven 2067227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2068227825Stheraventemplate <class ..._Args> 2069227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2070227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2071227825Stheraven{ 2072227825Stheraven __node_allocator& __na = __node_alloc(); 2073232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2074227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2075227825Stheraven __h.get_deleter().__value_constructed = true; 2076227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2077227825Stheraven __h->__next_ = nullptr; 2078227825Stheraven return __h; 2079227825Stheraven} 2080227825Stheraven 2081227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2082227825Stheraven 2083227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2084227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2085227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2086227825Stheraven size_t __hash) 2087227825Stheraven{ 2088227825Stheraven __node_allocator& __na = __node_alloc(); 2089232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2090227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2091227825Stheraven __h.get_deleter().__value_constructed = true; 2092227825Stheraven __h->__hash_ = __hash; 2093227825Stheraven __h->__next_ = nullptr; 2094261272Sdim return __h; 2095227825Stheraven} 2096227825Stheraven 2097227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2098227825Stheraven 2099227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2100227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2101227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2102227825Stheraven{ 2103227825Stheraven __node_allocator& __na = __node_alloc(); 2104232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2105227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2106227825Stheraven __h.get_deleter().__value_constructed = true; 2107227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2108227825Stheraven __h->__next_ = nullptr; 2109261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 2110227825Stheraven} 2111227825Stheraven 2112227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2113227825Stheraven 2114227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2115227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2116227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2117227825Stheraven size_t __hash) 2118227825Stheraven{ 2119227825Stheraven __node_allocator& __na = __node_alloc(); 2120232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2121227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2122227825Stheraven __h.get_deleter().__value_constructed = true; 2123227825Stheraven __h->__hash_ = __hash; 2124227825Stheraven __h->__next_ = nullptr; 2125261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 2126227825Stheraven} 2127227825Stheraven 2128227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2129227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2130227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2131227825Stheraven{ 2132253146Stheraven __node_pointer __np = __p.__node_; 2133261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2134261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2135261272Sdim "unordered container erase(iterator) called with an iterator not" 2136261272Sdim " referring to this container"); 2137261272Sdim _LIBCPP_ASSERT(__p != end(), 2138261272Sdim "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2139261272Sdim iterator __r(__np, this); 2140261272Sdim#else 2141227825Stheraven iterator __r(__np); 2142261272Sdim#endif 2143227825Stheraven ++__r; 2144227825Stheraven remove(__p); 2145227825Stheraven return __r; 2146227825Stheraven} 2147227825Stheraven 2148227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2149227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2150227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2151227825Stheraven const_iterator __last) 2152227825Stheraven{ 2153261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2154261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2155261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2156261272Sdim " referring to this unodered container"); 2157261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2158261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2159261272Sdim " referring to this unodered container"); 2160261272Sdim#endif 2161227825Stheraven for (const_iterator __p = __first; __first != __last; __p = __first) 2162227825Stheraven { 2163227825Stheraven ++__first; 2164227825Stheraven erase(__p); 2165227825Stheraven } 2166253146Stheraven __node_pointer __np = __last.__node_; 2167261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2168261272Sdim return iterator (__np, this); 2169261272Sdim#else 2170227825Stheraven return iterator (__np); 2171261272Sdim#endif 2172227825Stheraven} 2173227825Stheraven 2174227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2175227825Stheraventemplate <class _Key> 2176227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2177227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2178227825Stheraven{ 2179227825Stheraven iterator __i = find(__k); 2180227825Stheraven if (__i == end()) 2181227825Stheraven return 0; 2182227825Stheraven erase(__i); 2183227825Stheraven return 1; 2184227825Stheraven} 2185227825Stheraven 2186227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2187227825Stheraventemplate <class _Key> 2188227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2189227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2190227825Stheraven{ 2191227825Stheraven size_type __r = 0; 2192227825Stheraven iterator __i = find(__k); 2193227825Stheraven if (__i != end()) 2194227825Stheraven { 2195227825Stheraven iterator __e = end(); 2196227825Stheraven do 2197227825Stheraven { 2198227825Stheraven erase(__i++); 2199227825Stheraven ++__r; 2200227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2201227825Stheraven } 2202227825Stheraven return __r; 2203227825Stheraven} 2204227825Stheraven 2205227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2206227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2207227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2208227825Stheraven{ 2209227825Stheraven // current node 2210253146Stheraven __node_pointer __cn = __p.__node_; 2211227825Stheraven size_type __bc = bucket_count(); 2212241900Sdim size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2213227825Stheraven // find previous node 2214227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 2215227825Stheraven for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2216227825Stheraven ; 2217227825Stheraven // Fix up __bucket_list_ 2218227825Stheraven // if __pn is not in same bucket (before begin is not in same bucket) && 2219227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2220253146Stheraven if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2221253146Stheraven || __constrain_hash(__pn->__hash_, __bc) != __chash) 2222227825Stheraven { 2223241900Sdim if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2224227825Stheraven __bucket_list_[__chash] = nullptr; 2225227825Stheraven } 2226227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2227227825Stheraven if (__cn->__next_ != nullptr) 2228227825Stheraven { 2229241900Sdim size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2230227825Stheraven if (__nhash != __chash) 2231227825Stheraven __bucket_list_[__nhash] = __pn; 2232227825Stheraven } 2233227825Stheraven // remove __cn 2234227825Stheraven __pn->__next_ = __cn->__next_; 2235227825Stheraven __cn->__next_ = nullptr; 2236227825Stheraven --size(); 2237261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2238261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 2239261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2240261272Sdim { 2241261272Sdim --__p; 2242261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 2243261272Sdim if (__i->__node_ == __cn) 2244261272Sdim { 2245261272Sdim (*__p)->__c_ = nullptr; 2246261272Sdim if (--__c->end_ != __p) 2247261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2248261272Sdim } 2249261272Sdim } 2250261272Sdim __get_db()->unlock(); 2251261272Sdim#endif 2252232924Stheraven return __node_holder(__cn, _Dp(__node_alloc(), true)); 2253227825Stheraven} 2254227825Stheraven 2255227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2256227825Stheraventemplate <class _Key> 2257227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2258227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2259227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2260227825Stheraven{ 2261227825Stheraven return static_cast<size_type>(find(__k) != end()); 2262227825Stheraven} 2263227825Stheraven 2264227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2265227825Stheraventemplate <class _Key> 2266227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2267227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2268227825Stheraven{ 2269227825Stheraven size_type __r = 0; 2270227825Stheraven const_iterator __i = find(__k); 2271227825Stheraven if (__i != end()) 2272227825Stheraven { 2273227825Stheraven const_iterator __e = end(); 2274227825Stheraven do 2275227825Stheraven { 2276227825Stheraven ++__i; 2277227825Stheraven ++__r; 2278227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2279227825Stheraven } 2280227825Stheraven return __r; 2281227825Stheraven} 2282227825Stheraven 2283227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2284227825Stheraventemplate <class _Key> 2285227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2286227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2287227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2288227825Stheraven const _Key& __k) 2289227825Stheraven{ 2290227825Stheraven iterator __i = find(__k); 2291227825Stheraven iterator __j = __i; 2292227825Stheraven if (__i != end()) 2293227825Stheraven ++__j; 2294227825Stheraven return pair<iterator, iterator>(__i, __j); 2295227825Stheraven} 2296227825Stheraven 2297227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2298227825Stheraventemplate <class _Key> 2299227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2300227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2301227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2302227825Stheraven const _Key& __k) const 2303227825Stheraven{ 2304227825Stheraven const_iterator __i = find(__k); 2305227825Stheraven const_iterator __j = __i; 2306227825Stheraven if (__i != end()) 2307227825Stheraven ++__j; 2308227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2309227825Stheraven} 2310227825Stheraven 2311227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2312227825Stheraventemplate <class _Key> 2313227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2314227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2315227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2316227825Stheraven const _Key& __k) 2317227825Stheraven{ 2318227825Stheraven iterator __i = find(__k); 2319227825Stheraven iterator __j = __i; 2320227825Stheraven if (__i != end()) 2321227825Stheraven { 2322227825Stheraven iterator __e = end(); 2323227825Stheraven do 2324227825Stheraven { 2325227825Stheraven ++__j; 2326227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2327227825Stheraven } 2328227825Stheraven return pair<iterator, iterator>(__i, __j); 2329227825Stheraven} 2330227825Stheraven 2331227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2332227825Stheraventemplate <class _Key> 2333227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2334227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2335227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2336227825Stheraven const _Key& __k) const 2337227825Stheraven{ 2338227825Stheraven const_iterator __i = find(__k); 2339227825Stheraven const_iterator __j = __i; 2340227825Stheraven if (__i != end()) 2341227825Stheraven { 2342227825Stheraven const_iterator __e = end(); 2343227825Stheraven do 2344227825Stheraven { 2345227825Stheraven ++__j; 2346227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2347227825Stheraven } 2348227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2349227825Stheraven} 2350227825Stheraven 2351227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2352227825Stheravenvoid 2353227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2354227825Stheraven _NOEXCEPT_( 2355288943Sdim __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2356288943Sdim#if _LIBCPP_STD_VER <= 11 2357288943Sdim && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2358288943Sdim || __is_nothrow_swappable<__pointer_allocator>::value) 2359288943Sdim && (!__node_traits::propagate_on_container_swap::value 2360288943Sdim || __is_nothrow_swappable<__node_allocator>::value) 2361288943Sdim#endif 2362288943Sdim ) 2363227825Stheraven{ 2364227825Stheraven { 2365227825Stheraven __node_pointer_pointer __npp = __bucket_list_.release(); 2366227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 2367227825Stheraven __u.__bucket_list_.reset(__npp); 2368227825Stheraven } 2369227825Stheraven _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2370288943Sdim __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2371227825Stheraven __u.__bucket_list_.get_deleter().__alloc()); 2372288943Sdim __swap_allocator(__node_alloc(), __u.__node_alloc()); 2373227825Stheraven _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2374227825Stheraven __p2_.swap(__u.__p2_); 2375227825Stheraven __p3_.swap(__u.__p3_); 2376227825Stheraven if (size() > 0) 2377241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2378253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2379227825Stheraven if (__u.size() > 0) 2380241900Sdim __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2381253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2382261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2383261272Sdim __get_db()->swap(this, &__u); 2384261272Sdim#endif 2385227825Stheraven} 2386227825Stheraven 2387227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2388227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2389227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2390227825Stheraven{ 2391261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 2392261272Sdim "unordered container::bucket_size(n) called with n >= bucket_count()"); 2393227825Stheraven __node_const_pointer __np = __bucket_list_[__n]; 2394227825Stheraven size_type __bc = bucket_count(); 2395227825Stheraven size_type __r = 0; 2396227825Stheraven if (__np != nullptr) 2397227825Stheraven { 2398227825Stheraven for (__np = __np->__next_; __np != nullptr && 2399241900Sdim __constrain_hash(__np->__hash_, __bc) == __n; 2400227825Stheraven __np = __np->__next_, ++__r) 2401227825Stheraven ; 2402227825Stheraven } 2403227825Stheraven return __r; 2404227825Stheraven} 2405227825Stheraven 2406227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2407227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2408227825Stheravenvoid 2409227825Stheravenswap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2410227825Stheraven __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2411227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2412227825Stheraven{ 2413227825Stheraven __x.swap(__y); 2414227825Stheraven} 2415227825Stheraven 2416261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2417261272Sdim 2418261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2419261272Sdimbool 2420261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2421261272Sdim{ 2422261272Sdim return __i->__node_ != nullptr; 2423261272Sdim} 2424261272Sdim 2425261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2426261272Sdimbool 2427261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2428261272Sdim{ 2429261272Sdim return false; 2430261272Sdim} 2431261272Sdim 2432261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2433261272Sdimbool 2434261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2435261272Sdim{ 2436261272Sdim return false; 2437261272Sdim} 2438261272Sdim 2439261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2440261272Sdimbool 2441261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2442261272Sdim{ 2443261272Sdim return false; 2444261272Sdim} 2445261272Sdim 2446261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 2447227825Stheraven_LIBCPP_END_NAMESPACE_STD 2448227825Stheraven 2449227825Stheraven#endif // _LIBCPP__HASH_TABLE 2450