__hash_table revision 289082
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) 987289082Sdim#if _LIBCPP_STD_VER <= 11 988227825Stheraven _NOEXCEPT_( 989288943Sdim __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 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) 994289082Sdim ); 995289082Sdim#else 996289082Sdim _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 997288943Sdim#endif 998227825Stheraven 999227825Stheraven _LIBCPP_INLINE_VISIBILITY 1000227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1001253146Stheraven {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1002227825Stheraven size_type bucket_size(size_type __n) const; 1003227825Stheraven _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1004227825Stheraven { 1005227825Stheraven size_type __bc = bucket_count(); 1006227825Stheraven return __bc != 0 ? (float)size() / __bc : 0.f; 1007227825Stheraven } 1008227825Stheraven _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1009261272Sdim { 1010261272Sdim _LIBCPP_ASSERT(__mlf > 0, 1011261272Sdim "unordered container::max_load_factor(lf) called with lf <= 0"); 1012261272Sdim max_load_factor() = _VSTD::max(__mlf, load_factor()); 1013261272Sdim } 1014227825Stheraven 1015261272Sdim _LIBCPP_INLINE_VISIBILITY 1016261272Sdim local_iterator 1017261272Sdim begin(size_type __n) 1018261272Sdim { 1019261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1020261272Sdim "unordered container::begin(n) called with n >= bucket_count()"); 1021261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1022261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1023261272Sdim#else 1024261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1025261272Sdim#endif 1026261272Sdim } 1027261272Sdim 1028261272Sdim _LIBCPP_INLINE_VISIBILITY 1029261272Sdim local_iterator 1030261272Sdim end(size_type __n) 1031261272Sdim { 1032261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1033261272Sdim "unordered container::end(n) called with n >= bucket_count()"); 1034261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1035261272Sdim return local_iterator(nullptr, __n, bucket_count(), this); 1036261272Sdim#else 1037261272Sdim return local_iterator(nullptr, __n, bucket_count()); 1038261272Sdim#endif 1039261272Sdim } 1040261272Sdim 1041261272Sdim _LIBCPP_INLINE_VISIBILITY 1042261272Sdim const_local_iterator 1043261272Sdim cbegin(size_type __n) const 1044261272Sdim { 1045261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1046261272Sdim "unordered container::cbegin(n) called with n >= bucket_count()"); 1047261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1048261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1049261272Sdim#else 1050261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1051261272Sdim#endif 1052261272Sdim } 1053261272Sdim 1054261272Sdim _LIBCPP_INLINE_VISIBILITY 1055261272Sdim const_local_iterator 1056261272Sdim cend(size_type __n) const 1057261272Sdim { 1058261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1059261272Sdim "unordered container::cend(n) called with n >= bucket_count()"); 1060261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1061261272Sdim return const_local_iterator(nullptr, __n, bucket_count(), this); 1062261272Sdim#else 1063261272Sdim return const_local_iterator(nullptr, __n, bucket_count()); 1064261272Sdim#endif 1065261272Sdim } 1066261272Sdim 1067261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1068261272Sdim 1069261272Sdim bool __dereferenceable(const const_iterator* __i) const; 1070261272Sdim bool __decrementable(const const_iterator* __i) const; 1071261272Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1072261272Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1073261272Sdim 1074261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1075261272Sdim 1076227825Stheravenprivate: 1077227825Stheraven void __rehash(size_type __n); 1078227825Stheraven 1079227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1080227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1081227825Stheraven template <class ..._Args> 1082227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1083227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1084227825Stheraven __node_holder __construct_node(value_type&& __v, size_t __hash); 1085227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1086227825Stheraven __node_holder __construct_node(const value_type& __v); 1087227825Stheraven#endif 1088227825Stheraven __node_holder __construct_node(const value_type& __v, size_t __hash); 1089227825Stheraven 1090227825Stheraven _LIBCPP_INLINE_VISIBILITY 1091227825Stheraven void __copy_assign_alloc(const __hash_table& __u) 1092227825Stheraven {__copy_assign_alloc(__u, integral_constant<bool, 1093227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1094227825Stheraven void __copy_assign_alloc(const __hash_table& __u, true_type); 1095227825Stheraven _LIBCPP_INLINE_VISIBILITY 1096232924Stheraven void __copy_assign_alloc(const __hash_table&, false_type) {} 1097227825Stheraven 1098227825Stheraven void __move_assign(__hash_table& __u, false_type); 1099227825Stheraven void __move_assign(__hash_table& __u, true_type) 1100227825Stheraven _NOEXCEPT_( 1101227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1102227825Stheraven is_nothrow_move_assignable<hasher>::value && 1103227825Stheraven is_nothrow_move_assignable<key_equal>::value); 1104227825Stheraven _LIBCPP_INLINE_VISIBILITY 1105227825Stheraven void __move_assign_alloc(__hash_table& __u) 1106227825Stheraven _NOEXCEPT_( 1107227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1108227825Stheraven (is_nothrow_move_assignable<__pointer_allocator>::value && 1109227825Stheraven is_nothrow_move_assignable<__node_allocator>::value)) 1110227825Stheraven {__move_assign_alloc(__u, integral_constant<bool, 1111227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1112227825Stheraven _LIBCPP_INLINE_VISIBILITY 1113227825Stheraven void __move_assign_alloc(__hash_table& __u, true_type) 1114227825Stheraven _NOEXCEPT_( 1115227825Stheraven is_nothrow_move_assignable<__pointer_allocator>::value && 1116227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1117227825Stheraven { 1118227825Stheraven __bucket_list_.get_deleter().__alloc() = 1119227825Stheraven _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1120227825Stheraven __node_alloc() = _VSTD::move(__u.__node_alloc()); 1121227825Stheraven } 1122227825Stheraven _LIBCPP_INLINE_VISIBILITY 1123227825Stheraven void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1124227825Stheraven 1125227825Stheraven void __deallocate(__node_pointer __np) _NOEXCEPT; 1126227825Stheraven __node_pointer __detach() _NOEXCEPT; 1127253146Stheraven 1128261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1129261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1130227825Stheraven}; 1131227825Stheraven 1132227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1133227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1134227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1135227825Stheraven _NOEXCEPT_( 1136227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 1137227825Stheraven is_nothrow_default_constructible<__first_node>::value && 1138227825Stheraven is_nothrow_default_constructible<hasher>::value && 1139227825Stheraven is_nothrow_default_constructible<key_equal>::value) 1140227825Stheraven : __p2_(0), 1141227825Stheraven __p3_(1.0f) 1142227825Stheraven{ 1143227825Stheraven} 1144227825Stheraven 1145227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1146227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1147227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1148227825Stheraven const key_equal& __eql) 1149227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter()), 1150227825Stheraven __p1_(), 1151227825Stheraven __p2_(0, __hf), 1152227825Stheraven __p3_(1.0f, __eql) 1153227825Stheraven{ 1154227825Stheraven} 1155227825Stheraven 1156227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1157227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1158227825Stheraven const key_equal& __eql, 1159227825Stheraven const allocator_type& __a) 1160227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1161227825Stheraven __p1_(__node_allocator(__a)), 1162227825Stheraven __p2_(0, __hf), 1163227825Stheraven __p3_(1.0f, __eql) 1164227825Stheraven{ 1165227825Stheraven} 1166227825Stheraven 1167227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1168227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1169227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1170227825Stheraven __p1_(__node_allocator(__a)), 1171227825Stheraven __p2_(0), 1172227825Stheraven __p3_(1.0f) 1173227825Stheraven{ 1174227825Stheraven} 1175227825Stheraven 1176227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1177227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1178227825Stheraven : __bucket_list_(nullptr, 1179227825Stheraven __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1180227825Stheraven select_on_container_copy_construction( 1181227825Stheraven __u.__bucket_list_.get_deleter().__alloc()), 0)), 1182227825Stheraven __p1_(allocator_traits<__node_allocator>:: 1183227825Stheraven select_on_container_copy_construction(__u.__node_alloc())), 1184227825Stheraven __p2_(0, __u.hash_function()), 1185227825Stheraven __p3_(__u.__p3_) 1186227825Stheraven{ 1187227825Stheraven} 1188227825Stheraven 1189227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1190227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1191227825Stheraven const allocator_type& __a) 1192227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1193227825Stheraven __p1_(__node_allocator(__a)), 1194227825Stheraven __p2_(0, __u.hash_function()), 1195227825Stheraven __p3_(__u.__p3_) 1196227825Stheraven{ 1197227825Stheraven} 1198227825Stheraven 1199227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1200227825Stheraven 1201227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1202227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1203227825Stheraven _NOEXCEPT_( 1204227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 1205227825Stheraven is_nothrow_move_constructible<__first_node>::value && 1206227825Stheraven is_nothrow_move_constructible<hasher>::value && 1207227825Stheraven is_nothrow_move_constructible<key_equal>::value) 1208227825Stheraven : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1209227825Stheraven __p1_(_VSTD::move(__u.__p1_)), 1210227825Stheraven __p2_(_VSTD::move(__u.__p2_)), 1211227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1212227825Stheraven{ 1213227825Stheraven if (size() > 0) 1214227825Stheraven { 1215241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1216253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1217227825Stheraven __u.__p1_.first().__next_ = nullptr; 1218227825Stheraven __u.size() = 0; 1219227825Stheraven } 1220227825Stheraven} 1221227825Stheraven 1222227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1223227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1224227825Stheraven const allocator_type& __a) 1225227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1226227825Stheraven __p1_(__node_allocator(__a)), 1227227825Stheraven __p2_(0, _VSTD::move(__u.hash_function())), 1228227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1229227825Stheraven{ 1230227825Stheraven if (__a == allocator_type(__u.__node_alloc())) 1231227825Stheraven { 1232227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1233227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1234227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1235227825Stheraven if (__u.size() > 0) 1236227825Stheraven { 1237227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1238227825Stheraven __u.__p1_.first().__next_ = nullptr; 1239241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1240253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1241227825Stheraven size() = __u.size(); 1242227825Stheraven __u.size() = 0; 1243227825Stheraven } 1244227825Stheraven } 1245227825Stheraven} 1246227825Stheraven 1247227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1248227825Stheraven 1249227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1250227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1251227825Stheraven{ 1252227825Stheraven __deallocate(__p1_.first().__next_); 1253261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1254261272Sdim __get_db()->__erase_c(this); 1255261272Sdim#endif 1256227825Stheraven} 1257227825Stheraven 1258227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1259227825Stheravenvoid 1260227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1261227825Stheraven const __hash_table& __u, true_type) 1262227825Stheraven{ 1263227825Stheraven if (__node_alloc() != __u.__node_alloc()) 1264227825Stheraven { 1265227825Stheraven clear(); 1266227825Stheraven __bucket_list_.reset(); 1267227825Stheraven __bucket_list_.get_deleter().size() = 0; 1268227825Stheraven } 1269227825Stheraven __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1270227825Stheraven __node_alloc() = __u.__node_alloc(); 1271227825Stheraven} 1272227825Stheraven 1273227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1274227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1275227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1276227825Stheraven{ 1277227825Stheraven if (this != &__u) 1278227825Stheraven { 1279227825Stheraven __copy_assign_alloc(__u); 1280227825Stheraven hash_function() = __u.hash_function(); 1281227825Stheraven key_eq() = __u.key_eq(); 1282227825Stheraven max_load_factor() = __u.max_load_factor(); 1283227825Stheraven __assign_multi(__u.begin(), __u.end()); 1284227825Stheraven } 1285227825Stheraven return *this; 1286227825Stheraven} 1287227825Stheraven 1288227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1289227825Stheravenvoid 1290227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1291227825Stheraven _NOEXCEPT 1292227825Stheraven{ 1293227825Stheraven __node_allocator& __na = __node_alloc(); 1294227825Stheraven while (__np != nullptr) 1295227825Stheraven { 1296227825Stheraven __node_pointer __next = __np->__next_; 1297261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1298261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 1299261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1300261272Sdim { 1301261272Sdim --__p; 1302261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 1303261272Sdim if (__i->__node_ == __np) 1304261272Sdim { 1305261272Sdim (*__p)->__c_ = nullptr; 1306261272Sdim if (--__c->end_ != __p) 1307261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1308261272Sdim } 1309261272Sdim } 1310261272Sdim __get_db()->unlock(); 1311261272Sdim#endif 1312227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1313227825Stheraven __node_traits::deallocate(__na, __np, 1); 1314227825Stheraven __np = __next; 1315227825Stheraven } 1316227825Stheraven} 1317227825Stheraven 1318227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1319227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1320227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1321227825Stheraven{ 1322227825Stheraven size_type __bc = bucket_count(); 1323227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1324227825Stheraven __bucket_list_[__i] = nullptr; 1325227825Stheraven size() = 0; 1326227825Stheraven __node_pointer __cache = __p1_.first().__next_; 1327227825Stheraven __p1_.first().__next_ = nullptr; 1328227825Stheraven return __cache; 1329227825Stheraven} 1330227825Stheraven 1331227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1332227825Stheraven 1333227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1334227825Stheravenvoid 1335227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1336227825Stheraven __hash_table& __u, true_type) 1337227825Stheraven _NOEXCEPT_( 1338227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1339227825Stheraven is_nothrow_move_assignable<hasher>::value && 1340227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1341227825Stheraven{ 1342227825Stheraven clear(); 1343227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1344227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1345227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1346227825Stheraven __move_assign_alloc(__u); 1347227825Stheraven size() = __u.size(); 1348227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1349227825Stheraven max_load_factor() = __u.max_load_factor(); 1350227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1351227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1352227825Stheraven if (size() > 0) 1353227825Stheraven { 1354241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1355253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1356227825Stheraven __u.__p1_.first().__next_ = nullptr; 1357227825Stheraven __u.size() = 0; 1358227825Stheraven } 1359261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1360261272Sdim __get_db()->swap(this, &__u); 1361261272Sdim#endif 1362227825Stheraven} 1363227825Stheraven 1364227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1365227825Stheravenvoid 1366227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1367227825Stheraven __hash_table& __u, false_type) 1368227825Stheraven{ 1369227825Stheraven if (__node_alloc() == __u.__node_alloc()) 1370227825Stheraven __move_assign(__u, true_type()); 1371227825Stheraven else 1372227825Stheraven { 1373227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1374227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1375227825Stheraven max_load_factor() = __u.max_load_factor(); 1376227825Stheraven if (bucket_count() != 0) 1377227825Stheraven { 1378227825Stheraven __node_pointer __cache = __detach(); 1379227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1380227825Stheraven try 1381227825Stheraven { 1382227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1383227825Stheraven const_iterator __i = __u.begin(); 1384227825Stheraven while (__cache != nullptr && __u.size() != 0) 1385227825Stheraven { 1386227825Stheraven __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1387227825Stheraven __node_pointer __next = __cache->__next_; 1388227825Stheraven __node_insert_multi(__cache); 1389227825Stheraven __cache = __next; 1390227825Stheraven } 1391227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1392227825Stheraven } 1393227825Stheraven catch (...) 1394227825Stheraven { 1395227825Stheraven __deallocate(__cache); 1396227825Stheraven throw; 1397227825Stheraven } 1398227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1399227825Stheraven __deallocate(__cache); 1400227825Stheraven } 1401227825Stheraven const_iterator __i = __u.begin(); 1402227825Stheraven while (__u.size() != 0) 1403227825Stheraven { 1404227825Stheraven __node_holder __h = 1405227825Stheraven __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1406227825Stheraven __node_insert_multi(__h.get()); 1407227825Stheraven __h.release(); 1408227825Stheraven } 1409227825Stheraven } 1410227825Stheraven} 1411227825Stheraven 1412227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1413227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1414227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1415227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1416227825Stheraven _NOEXCEPT_( 1417227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1418227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1419227825Stheraven is_nothrow_move_assignable<hasher>::value && 1420227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1421227825Stheraven{ 1422227825Stheraven __move_assign(__u, integral_constant<bool, 1423227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1424227825Stheraven return *this; 1425227825Stheraven} 1426227825Stheraven 1427227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1428227825Stheraven 1429227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1430227825Stheraventemplate <class _InputIterator> 1431227825Stheravenvoid 1432227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1433227825Stheraven _InputIterator __last) 1434227825Stheraven{ 1435227825Stheraven if (bucket_count() != 0) 1436227825Stheraven { 1437227825Stheraven __node_pointer __cache = __detach(); 1438227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1439227825Stheraven try 1440227825Stheraven { 1441227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1442227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1443227825Stheraven { 1444227825Stheraven __cache->__value_ = *__first; 1445227825Stheraven __node_pointer __next = __cache->__next_; 1446227825Stheraven __node_insert_unique(__cache); 1447227825Stheraven __cache = __next; 1448227825Stheraven } 1449227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1450227825Stheraven } 1451227825Stheraven catch (...) 1452227825Stheraven { 1453227825Stheraven __deallocate(__cache); 1454227825Stheraven throw; 1455227825Stheraven } 1456227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1457227825Stheraven __deallocate(__cache); 1458227825Stheraven } 1459227825Stheraven for (; __first != __last; ++__first) 1460227825Stheraven __insert_unique(*__first); 1461227825Stheraven} 1462227825Stheraven 1463227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1464227825Stheraventemplate <class _InputIterator> 1465227825Stheravenvoid 1466227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1467227825Stheraven _InputIterator __last) 1468227825Stheraven{ 1469227825Stheraven if (bucket_count() != 0) 1470227825Stheraven { 1471227825Stheraven __node_pointer __cache = __detach(); 1472227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1473227825Stheraven try 1474227825Stheraven { 1475227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1476227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1477227825Stheraven { 1478227825Stheraven __cache->__value_ = *__first; 1479227825Stheraven __node_pointer __next = __cache->__next_; 1480227825Stheraven __node_insert_multi(__cache); 1481227825Stheraven __cache = __next; 1482227825Stheraven } 1483227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1484227825Stheraven } 1485227825Stheraven catch (...) 1486227825Stheraven { 1487227825Stheraven __deallocate(__cache); 1488227825Stheraven throw; 1489227825Stheraven } 1490227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1491227825Stheraven __deallocate(__cache); 1492227825Stheraven } 1493227825Stheraven for (; __first != __last; ++__first) 1494227825Stheraven __insert_multi(*__first); 1495227825Stheraven} 1496227825Stheraven 1497227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1498227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1499227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1500227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1501227825Stheraven{ 1502261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1503261272Sdim return iterator(__p1_.first().__next_, this); 1504261272Sdim#else 1505227825Stheraven return iterator(__p1_.first().__next_); 1506261272Sdim#endif 1507227825Stheraven} 1508227825Stheraven 1509227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1510227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1511227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1512227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1513227825Stheraven{ 1514261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1515261272Sdim return iterator(nullptr, this); 1516261272Sdim#else 1517227825Stheraven return iterator(nullptr); 1518261272Sdim#endif 1519227825Stheraven} 1520227825Stheraven 1521227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1522227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1523227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1524227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1525227825Stheraven{ 1526261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1527261272Sdim return const_iterator(__p1_.first().__next_, this); 1528261272Sdim#else 1529227825Stheraven return const_iterator(__p1_.first().__next_); 1530261272Sdim#endif 1531227825Stheraven} 1532227825Stheraven 1533227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1534227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1535227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1536227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1537227825Stheraven{ 1538261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1539261272Sdim return const_iterator(nullptr, this); 1540261272Sdim#else 1541227825Stheraven return const_iterator(nullptr); 1542261272Sdim#endif 1543227825Stheraven} 1544227825Stheraven 1545227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1546227825Stheravenvoid 1547227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1548227825Stheraven{ 1549227825Stheraven if (size() > 0) 1550227825Stheraven { 1551227825Stheraven __deallocate(__p1_.first().__next_); 1552227825Stheraven __p1_.first().__next_ = nullptr; 1553227825Stheraven size_type __bc = bucket_count(); 1554227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1555227825Stheraven __bucket_list_[__i] = nullptr; 1556227825Stheraven size() = 0; 1557227825Stheraven } 1558227825Stheraven} 1559227825Stheraven 1560227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1561227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1562227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1563227825Stheraven{ 1564227825Stheraven __nd->__hash_ = hash_function()(__nd->__value_); 1565227825Stheraven size_type __bc = bucket_count(); 1566227825Stheraven bool __inserted = false; 1567227825Stheraven __node_pointer __ndptr; 1568227825Stheraven size_t __chash; 1569227825Stheraven if (__bc != 0) 1570227825Stheraven { 1571241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1572227825Stheraven __ndptr = __bucket_list_[__chash]; 1573227825Stheraven if (__ndptr != nullptr) 1574227825Stheraven { 1575227825Stheraven for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1576241900Sdim __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1577227825Stheraven __ndptr = __ndptr->__next_) 1578227825Stheraven { 1579227825Stheraven if (key_eq()(__ndptr->__value_, __nd->__value_)) 1580227825Stheraven goto __done; 1581227825Stheraven } 1582227825Stheraven } 1583227825Stheraven } 1584227825Stheraven { 1585227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1586227825Stheraven { 1587288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1588227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1589227825Stheraven __bc = bucket_count(); 1590241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1591227825Stheraven } 1592227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1593227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1594227825Stheraven if (__pn == nullptr) 1595227825Stheraven { 1596253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1597227825Stheraven __nd->__next_ = __pn->__next_; 1598227825Stheraven __pn->__next_ = __nd; 1599227825Stheraven // fix up __bucket_list_ 1600227825Stheraven __bucket_list_[__chash] = __pn; 1601227825Stheraven if (__nd->__next_ != nullptr) 1602241900Sdim __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1603227825Stheraven } 1604227825Stheraven else 1605227825Stheraven { 1606227825Stheraven __nd->__next_ = __pn->__next_; 1607227825Stheraven __pn->__next_ = __nd; 1608227825Stheraven } 1609227825Stheraven __ndptr = __nd; 1610227825Stheraven // increment size 1611227825Stheraven ++size(); 1612227825Stheraven __inserted = true; 1613227825Stheraven } 1614227825Stheraven__done: 1615261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1616261272Sdim return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1617261272Sdim#else 1618227825Stheraven return pair<iterator, bool>(iterator(__ndptr), __inserted); 1619261272Sdim#endif 1620227825Stheraven} 1621227825Stheraven 1622227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1623227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1624227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1625227825Stheraven{ 1626227825Stheraven __cp->__hash_ = hash_function()(__cp->__value_); 1627227825Stheraven size_type __bc = bucket_count(); 1628227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1629227825Stheraven { 1630288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1631227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1632227825Stheraven __bc = bucket_count(); 1633227825Stheraven } 1634241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1635227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1636227825Stheraven if (__pn == nullptr) 1637227825Stheraven { 1638253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1639227825Stheraven __cp->__next_ = __pn->__next_; 1640227825Stheraven __pn->__next_ = __cp; 1641227825Stheraven // fix up __bucket_list_ 1642227825Stheraven __bucket_list_[__chash] = __pn; 1643227825Stheraven if (__cp->__next_ != nullptr) 1644241900Sdim __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1645227825Stheraven } 1646227825Stheraven else 1647227825Stheraven { 1648227825Stheraven for (bool __found = false; __pn->__next_ != nullptr && 1649241900Sdim __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1650227825Stheraven __pn = __pn->__next_) 1651227825Stheraven { 1652227825Stheraven // __found key_eq() action 1653227825Stheraven // false false loop 1654227825Stheraven // true true loop 1655227825Stheraven // false true set __found to true 1656227825Stheraven // true false break 1657227825Stheraven if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1658227825Stheraven key_eq()(__pn->__next_->__value_, __cp->__value_))) 1659227825Stheraven { 1660227825Stheraven if (!__found) 1661227825Stheraven __found = true; 1662227825Stheraven else 1663227825Stheraven break; 1664227825Stheraven } 1665227825Stheraven } 1666227825Stheraven __cp->__next_ = __pn->__next_; 1667227825Stheraven __pn->__next_ = __cp; 1668227825Stheraven if (__cp->__next_ != nullptr) 1669227825Stheraven { 1670241900Sdim size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1671227825Stheraven if (__nhash != __chash) 1672227825Stheraven __bucket_list_[__nhash] = __cp; 1673227825Stheraven } 1674227825Stheraven } 1675227825Stheraven ++size(); 1676261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1677261272Sdim return iterator(__cp, this); 1678261272Sdim#else 1679227825Stheraven return iterator(__cp); 1680261272Sdim#endif 1681227825Stheraven} 1682227825Stheraven 1683227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1684227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1685227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1686227825Stheraven const_iterator __p, __node_pointer __cp) 1687227825Stheraven{ 1688261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1689261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1690261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1691261272Sdim " referring to this unordered container"); 1692261272Sdim#endif 1693227825Stheraven if (__p != end() && key_eq()(*__p, __cp->__value_)) 1694227825Stheraven { 1695253146Stheraven __node_pointer __np = __p.__node_; 1696227825Stheraven __cp->__hash_ = __np->__hash_; 1697227825Stheraven size_type __bc = bucket_count(); 1698227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1699227825Stheraven { 1700288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1701227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1702227825Stheraven __bc = bucket_count(); 1703227825Stheraven } 1704241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1705227825Stheraven __node_pointer __pp = __bucket_list_[__chash]; 1706227825Stheraven while (__pp->__next_ != __np) 1707227825Stheraven __pp = __pp->__next_; 1708227825Stheraven __cp->__next_ = __np; 1709227825Stheraven __pp->__next_ = __cp; 1710227825Stheraven ++size(); 1711261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1712261272Sdim return iterator(__cp, this); 1713261272Sdim#else 1714227825Stheraven return iterator(__cp); 1715261272Sdim#endif 1716227825Stheraven } 1717227825Stheraven return __node_insert_multi(__cp); 1718227825Stheraven} 1719227825Stheraven 1720227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1721227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1722227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1723227825Stheraven{ 1724288943Sdim return __insert_unique_value(__x); 1725288943Sdim} 1726288943Sdim 1727288943Sdim 1728288943Sdim#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1729288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1730288943Sdimtemplate <class _ValueTp> 1731288943Sdim_LIBCPP_INLINE_VISIBILITY 1732288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1733288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x) 1734288943Sdim#else 1735288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1736288943Sdim_LIBCPP_INLINE_VISIBILITY 1737288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1738288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x) 1739288943Sdim#endif 1740288943Sdim{ 1741288943Sdim#if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1742288943Sdim typedef const value_type& _ValueTp; 1743288943Sdim#endif 1744227825Stheraven size_t __hash = hash_function()(__x); 1745227825Stheraven size_type __bc = bucket_count(); 1746227825Stheraven bool __inserted = false; 1747227825Stheraven __node_pointer __nd; 1748227825Stheraven size_t __chash; 1749227825Stheraven if (__bc != 0) 1750227825Stheraven { 1751241900Sdim __chash = __constrain_hash(__hash, __bc); 1752227825Stheraven __nd = __bucket_list_[__chash]; 1753227825Stheraven if (__nd != nullptr) 1754227825Stheraven { 1755227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1756241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1757227825Stheraven __nd = __nd->__next_) 1758227825Stheraven { 1759227825Stheraven if (key_eq()(__nd->__value_, __x)) 1760227825Stheraven goto __done; 1761227825Stheraven } 1762227825Stheraven } 1763227825Stheraven } 1764227825Stheraven { 1765288943Sdim __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash); 1766227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1767227825Stheraven { 1768288943Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1769227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1770227825Stheraven __bc = bucket_count(); 1771241900Sdim __chash = __constrain_hash(__hash, __bc); 1772227825Stheraven } 1773227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1774227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1775227825Stheraven if (__pn == nullptr) 1776227825Stheraven { 1777253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1778227825Stheraven __h->__next_ = __pn->__next_; 1779227825Stheraven __pn->__next_ = __h.get(); 1780227825Stheraven // fix up __bucket_list_ 1781227825Stheraven __bucket_list_[__chash] = __pn; 1782227825Stheraven if (__h->__next_ != nullptr) 1783241900Sdim __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1784227825Stheraven } 1785227825Stheraven else 1786227825Stheraven { 1787227825Stheraven __h->__next_ = __pn->__next_; 1788227825Stheraven __pn->__next_ = __h.get(); 1789227825Stheraven } 1790227825Stheraven __nd = __h.release(); 1791227825Stheraven // increment size 1792227825Stheraven ++size(); 1793227825Stheraven __inserted = true; 1794227825Stheraven } 1795227825Stheraven__done: 1796261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1797261272Sdim return pair<iterator, bool>(iterator(__nd, this), __inserted); 1798261272Sdim#else 1799227825Stheraven return pair<iterator, bool>(iterator(__nd), __inserted); 1800261272Sdim#endif 1801227825Stheraven} 1802227825Stheraven 1803227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1804227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1805227825Stheraven 1806227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1807227825Stheraventemplate <class... _Args> 1808227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1809227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1810227825Stheraven{ 1811227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1812227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1813227825Stheraven if (__r.second) 1814227825Stheraven __h.release(); 1815227825Stheraven return __r; 1816227825Stheraven} 1817227825Stheraven 1818227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1819227825Stheraventemplate <class... _Args> 1820227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1821227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1822227825Stheraven{ 1823227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1824227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1825227825Stheraven __h.release(); 1826227825Stheraven return __r; 1827227825Stheraven} 1828227825Stheraven 1829227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1830227825Stheraventemplate <class... _Args> 1831227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1832227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1833227825Stheraven const_iterator __p, _Args&&... __args) 1834227825Stheraven{ 1835261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1836261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1837261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1838261272Sdim " referring to this unordered container"); 1839261272Sdim#endif 1840227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1841227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1842227825Stheraven __h.release(); 1843227825Stheraven return __r; 1844227825Stheraven} 1845227825Stheraven 1846227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1847227825Stheraven 1848227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1849288943Sdimpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1850288943Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x) 1851288943Sdim{ 1852288943Sdim return __insert_unique_value(_VSTD::move(__x)); 1853288943Sdim} 1854288943Sdim 1855288943Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1856232924Stheraventemplate <class _Pp> 1857227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1858232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1859227825Stheraven{ 1860232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1861227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1862227825Stheraven if (__r.second) 1863227825Stheraven __h.release(); 1864227825Stheraven return __r; 1865227825Stheraven} 1866227825Stheraven 1867227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1868227825Stheraven 1869227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1870227825Stheraven 1871227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1872232924Stheraventemplate <class _Pp> 1873227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1874232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1875227825Stheraven{ 1876232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1877227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1878227825Stheraven __h.release(); 1879227825Stheraven return __r; 1880227825Stheraven} 1881227825Stheraven 1882227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1883232924Stheraventemplate <class _Pp> 1884227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1885227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1886232924Stheraven _Pp&& __x) 1887227825Stheraven{ 1888261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1889261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1890261272Sdim "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1891261272Sdim " referring to this unordered container"); 1892261272Sdim#endif 1893232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1894227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1895227825Stheraven __h.release(); 1896227825Stheraven return __r; 1897227825Stheraven} 1898227825Stheraven 1899227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1900227825Stheraven 1901227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1902227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1903227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1904227825Stheraven{ 1905227825Stheraven __node_holder __h = __construct_node(__x); 1906227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1907227825Stheraven __h.release(); 1908227825Stheraven return __r; 1909227825Stheraven} 1910227825Stheraven 1911227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1912227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1913227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1914227825Stheraven const value_type& __x) 1915227825Stheraven{ 1916261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1917261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1918261272Sdim "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1919261272Sdim " referring to this unordered container"); 1920261272Sdim#endif 1921227825Stheraven __node_holder __h = __construct_node(__x); 1922227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1923227825Stheraven __h.release(); 1924227825Stheraven return __r; 1925227825Stheraven} 1926227825Stheraven 1927227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1928227825Stheraven 1929227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1930227825Stheravenvoid 1931227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1932227825Stheraven{ 1933241900Sdim if (__n == 1) 1934241900Sdim __n = 2; 1935241900Sdim else if (__n & (__n - 1)) 1936241900Sdim __n = __next_prime(__n); 1937227825Stheraven size_type __bc = bucket_count(); 1938227825Stheraven if (__n > __bc) 1939227825Stheraven __rehash(__n); 1940241900Sdim else if (__n < __bc) 1941227825Stheraven { 1942227825Stheraven __n = _VSTD::max<size_type> 1943227825Stheraven ( 1944227825Stheraven __n, 1945288943Sdim __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1946288943Sdim __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1947227825Stheraven ); 1948227825Stheraven if (__n < __bc) 1949227825Stheraven __rehash(__n); 1950227825Stheraven } 1951227825Stheraven} 1952227825Stheraven 1953227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1954227825Stheravenvoid 1955227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1956227825Stheraven{ 1957261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1958261272Sdim __get_db()->__invalidate_all(this); 1959261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1960227825Stheraven __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1961227825Stheraven __bucket_list_.reset(__nbc > 0 ? 1962227825Stheraven __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1963227825Stheraven __bucket_list_.get_deleter().size() = __nbc; 1964227825Stheraven if (__nbc > 0) 1965227825Stheraven { 1966227825Stheraven for (size_type __i = 0; __i < __nbc; ++__i) 1967227825Stheraven __bucket_list_[__i] = nullptr; 1968253146Stheraven __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1969227825Stheraven __node_pointer __cp = __pp->__next_; 1970227825Stheraven if (__cp != nullptr) 1971227825Stheraven { 1972241900Sdim size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1973227825Stheraven __bucket_list_[__chash] = __pp; 1974227825Stheraven size_type __phash = __chash; 1975227825Stheraven for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1976227825Stheraven __cp = __pp->__next_) 1977227825Stheraven { 1978241900Sdim __chash = __constrain_hash(__cp->__hash_, __nbc); 1979227825Stheraven if (__chash == __phash) 1980227825Stheraven __pp = __cp; 1981227825Stheraven else 1982227825Stheraven { 1983227825Stheraven if (__bucket_list_[__chash] == nullptr) 1984227825Stheraven { 1985227825Stheraven __bucket_list_[__chash] = __pp; 1986227825Stheraven __pp = __cp; 1987227825Stheraven __phash = __chash; 1988227825Stheraven } 1989227825Stheraven else 1990227825Stheraven { 1991227825Stheraven __node_pointer __np = __cp; 1992227825Stheraven for (; __np->__next_ != nullptr && 1993227825Stheraven key_eq()(__cp->__value_, __np->__next_->__value_); 1994227825Stheraven __np = __np->__next_) 1995227825Stheraven ; 1996227825Stheraven __pp->__next_ = __np->__next_; 1997227825Stheraven __np->__next_ = __bucket_list_[__chash]->__next_; 1998227825Stheraven __bucket_list_[__chash]->__next_ = __cp; 1999227825Stheraven 2000227825Stheraven } 2001227825Stheraven } 2002227825Stheraven } 2003227825Stheraven } 2004227825Stheraven } 2005227825Stheraven} 2006227825Stheraven 2007227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2008227825Stheraventemplate <class _Key> 2009227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2010227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2011227825Stheraven{ 2012227825Stheraven size_t __hash = hash_function()(__k); 2013227825Stheraven size_type __bc = bucket_count(); 2014227825Stheraven if (__bc != 0) 2015227825Stheraven { 2016241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2017227825Stheraven __node_pointer __nd = __bucket_list_[__chash]; 2018227825Stheraven if (__nd != nullptr) 2019227825Stheraven { 2020227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2021241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2022227825Stheraven __nd = __nd->__next_) 2023227825Stheraven { 2024227825Stheraven if (key_eq()(__nd->__value_, __k)) 2025261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2026261272Sdim return iterator(__nd, this); 2027261272Sdim#else 2028227825Stheraven return iterator(__nd); 2029261272Sdim#endif 2030227825Stheraven } 2031227825Stheraven } 2032227825Stheraven } 2033227825Stheraven return end(); 2034227825Stheraven} 2035227825Stheraven 2036227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2037227825Stheraventemplate <class _Key> 2038227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2039227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2040227825Stheraven{ 2041227825Stheraven size_t __hash = hash_function()(__k); 2042227825Stheraven size_type __bc = bucket_count(); 2043227825Stheraven if (__bc != 0) 2044227825Stheraven { 2045241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2046227825Stheraven __node_const_pointer __nd = __bucket_list_[__chash]; 2047227825Stheraven if (__nd != nullptr) 2048227825Stheraven { 2049227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2050241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2051227825Stheraven __nd = __nd->__next_) 2052227825Stheraven { 2053227825Stheraven if (key_eq()(__nd->__value_, __k)) 2054261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2055261272Sdim return const_iterator(__nd, this); 2056261272Sdim#else 2057227825Stheraven return const_iterator(__nd); 2058261272Sdim#endif 2059227825Stheraven } 2060227825Stheraven } 2061227825Stheraven 2062227825Stheraven } 2063227825Stheraven return end(); 2064227825Stheraven} 2065227825Stheraven 2066227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2067227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 2068227825Stheraven 2069227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2070227825Stheraventemplate <class ..._Args> 2071227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2072227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2073227825Stheraven{ 2074227825Stheraven __node_allocator& __na = __node_alloc(); 2075232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2076227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2077227825Stheraven __h.get_deleter().__value_constructed = true; 2078227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2079227825Stheraven __h->__next_ = nullptr; 2080227825Stheraven return __h; 2081227825Stheraven} 2082227825Stheraven 2083227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2084227825Stheraven 2085227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2086227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2087227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2088227825Stheraven size_t __hash) 2089227825Stheraven{ 2090227825Stheraven __node_allocator& __na = __node_alloc(); 2091232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2092227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2093227825Stheraven __h.get_deleter().__value_constructed = true; 2094227825Stheraven __h->__hash_ = __hash; 2095227825Stheraven __h->__next_ = nullptr; 2096261272Sdim return __h; 2097227825Stheraven} 2098227825Stheraven 2099227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2100227825Stheraven 2101227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2102227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2103227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2104227825Stheraven{ 2105227825Stheraven __node_allocator& __na = __node_alloc(); 2106232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2107227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2108227825Stheraven __h.get_deleter().__value_constructed = true; 2109227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2110227825Stheraven __h->__next_ = nullptr; 2111261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 2112227825Stheraven} 2113227825Stheraven 2114227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2115227825Stheraven 2116227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2117227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2118227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2119227825Stheraven size_t __hash) 2120227825Stheraven{ 2121227825Stheraven __node_allocator& __na = __node_alloc(); 2122232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2123227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2124227825Stheraven __h.get_deleter().__value_constructed = true; 2125227825Stheraven __h->__hash_ = __hash; 2126227825Stheraven __h->__next_ = nullptr; 2127261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 2128227825Stheraven} 2129227825Stheraven 2130227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2131227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2132227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2133227825Stheraven{ 2134253146Stheraven __node_pointer __np = __p.__node_; 2135261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2136261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2137261272Sdim "unordered container erase(iterator) called with an iterator not" 2138261272Sdim " referring to this container"); 2139261272Sdim _LIBCPP_ASSERT(__p != end(), 2140261272Sdim "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2141261272Sdim iterator __r(__np, this); 2142261272Sdim#else 2143227825Stheraven iterator __r(__np); 2144261272Sdim#endif 2145227825Stheraven ++__r; 2146227825Stheraven remove(__p); 2147227825Stheraven return __r; 2148227825Stheraven} 2149227825Stheraven 2150227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2151227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2152227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2153227825Stheraven const_iterator __last) 2154227825Stheraven{ 2155261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2156261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2157261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2158261272Sdim " referring to this unodered container"); 2159261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2160261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2161261272Sdim " referring to this unodered container"); 2162261272Sdim#endif 2163227825Stheraven for (const_iterator __p = __first; __first != __last; __p = __first) 2164227825Stheraven { 2165227825Stheraven ++__first; 2166227825Stheraven erase(__p); 2167227825Stheraven } 2168253146Stheraven __node_pointer __np = __last.__node_; 2169261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2170261272Sdim return iterator (__np, this); 2171261272Sdim#else 2172227825Stheraven return iterator (__np); 2173261272Sdim#endif 2174227825Stheraven} 2175227825Stheraven 2176227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2177227825Stheraventemplate <class _Key> 2178227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2179227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2180227825Stheraven{ 2181227825Stheraven iterator __i = find(__k); 2182227825Stheraven if (__i == end()) 2183227825Stheraven return 0; 2184227825Stheraven erase(__i); 2185227825Stheraven return 1; 2186227825Stheraven} 2187227825Stheraven 2188227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2189227825Stheraventemplate <class _Key> 2190227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2191227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2192227825Stheraven{ 2193227825Stheraven size_type __r = 0; 2194227825Stheraven iterator __i = find(__k); 2195227825Stheraven if (__i != end()) 2196227825Stheraven { 2197227825Stheraven iterator __e = end(); 2198227825Stheraven do 2199227825Stheraven { 2200227825Stheraven erase(__i++); 2201227825Stheraven ++__r; 2202227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2203227825Stheraven } 2204227825Stheraven return __r; 2205227825Stheraven} 2206227825Stheraven 2207227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2208227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2209227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2210227825Stheraven{ 2211227825Stheraven // current node 2212253146Stheraven __node_pointer __cn = __p.__node_; 2213227825Stheraven size_type __bc = bucket_count(); 2214241900Sdim size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2215227825Stheraven // find previous node 2216227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 2217227825Stheraven for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2218227825Stheraven ; 2219227825Stheraven // Fix up __bucket_list_ 2220227825Stheraven // if __pn is not in same bucket (before begin is not in same bucket) && 2221227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2222253146Stheraven if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2223253146Stheraven || __constrain_hash(__pn->__hash_, __bc) != __chash) 2224227825Stheraven { 2225241900Sdim if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2226227825Stheraven __bucket_list_[__chash] = nullptr; 2227227825Stheraven } 2228227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2229227825Stheraven if (__cn->__next_ != nullptr) 2230227825Stheraven { 2231241900Sdim size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2232227825Stheraven if (__nhash != __chash) 2233227825Stheraven __bucket_list_[__nhash] = __pn; 2234227825Stheraven } 2235227825Stheraven // remove __cn 2236227825Stheraven __pn->__next_ = __cn->__next_; 2237227825Stheraven __cn->__next_ = nullptr; 2238227825Stheraven --size(); 2239261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2240261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 2241261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2242261272Sdim { 2243261272Sdim --__p; 2244261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 2245261272Sdim if (__i->__node_ == __cn) 2246261272Sdim { 2247261272Sdim (*__p)->__c_ = nullptr; 2248261272Sdim if (--__c->end_ != __p) 2249261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2250261272Sdim } 2251261272Sdim } 2252261272Sdim __get_db()->unlock(); 2253261272Sdim#endif 2254232924Stheraven return __node_holder(__cn, _Dp(__node_alloc(), true)); 2255227825Stheraven} 2256227825Stheraven 2257227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2258227825Stheraventemplate <class _Key> 2259227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2260227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2261227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2262227825Stheraven{ 2263227825Stheraven return static_cast<size_type>(find(__k) != end()); 2264227825Stheraven} 2265227825Stheraven 2266227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2267227825Stheraventemplate <class _Key> 2268227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2269227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2270227825Stheraven{ 2271227825Stheraven size_type __r = 0; 2272227825Stheraven const_iterator __i = find(__k); 2273227825Stheraven if (__i != end()) 2274227825Stheraven { 2275227825Stheraven const_iterator __e = end(); 2276227825Stheraven do 2277227825Stheraven { 2278227825Stheraven ++__i; 2279227825Stheraven ++__r; 2280227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2281227825Stheraven } 2282227825Stheraven return __r; 2283227825Stheraven} 2284227825Stheraven 2285227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2286227825Stheraventemplate <class _Key> 2287227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2288227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2289227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2290227825Stheraven const _Key& __k) 2291227825Stheraven{ 2292227825Stheraven iterator __i = find(__k); 2293227825Stheraven iterator __j = __i; 2294227825Stheraven if (__i != end()) 2295227825Stheraven ++__j; 2296227825Stheraven return pair<iterator, iterator>(__i, __j); 2297227825Stheraven} 2298227825Stheraven 2299227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2300227825Stheraventemplate <class _Key> 2301227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2302227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2303227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2304227825Stheraven const _Key& __k) const 2305227825Stheraven{ 2306227825Stheraven const_iterator __i = find(__k); 2307227825Stheraven const_iterator __j = __i; 2308227825Stheraven if (__i != end()) 2309227825Stheraven ++__j; 2310227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2311227825Stheraven} 2312227825Stheraven 2313227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2314227825Stheraventemplate <class _Key> 2315227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2316227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2317227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2318227825Stheraven const _Key& __k) 2319227825Stheraven{ 2320227825Stheraven iterator __i = find(__k); 2321227825Stheraven iterator __j = __i; 2322227825Stheraven if (__i != end()) 2323227825Stheraven { 2324227825Stheraven iterator __e = end(); 2325227825Stheraven do 2326227825Stheraven { 2327227825Stheraven ++__j; 2328227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2329227825Stheraven } 2330227825Stheraven return pair<iterator, iterator>(__i, __j); 2331227825Stheraven} 2332227825Stheraven 2333227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2334227825Stheraventemplate <class _Key> 2335227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2336227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2337227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2338227825Stheraven const _Key& __k) const 2339227825Stheraven{ 2340227825Stheraven const_iterator __i = find(__k); 2341227825Stheraven const_iterator __j = __i; 2342227825Stheraven if (__i != end()) 2343227825Stheraven { 2344227825Stheraven const_iterator __e = end(); 2345227825Stheraven do 2346227825Stheraven { 2347227825Stheraven ++__j; 2348227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2349227825Stheraven } 2350227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2351227825Stheraven} 2352227825Stheraven 2353227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2354227825Stheravenvoid 2355227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2356289082Sdim#if _LIBCPP_STD_VER <= 11 2357227825Stheraven _NOEXCEPT_( 2358288943Sdim __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2359288943Sdim && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2360288943Sdim || __is_nothrow_swappable<__pointer_allocator>::value) 2361288943Sdim && (!__node_traits::propagate_on_container_swap::value 2362288943Sdim || __is_nothrow_swappable<__node_allocator>::value) 2363289082Sdim ) 2364289082Sdim#else 2365289082Sdim _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2366288943Sdim#endif 2367227825Stheraven{ 2368227825Stheraven { 2369227825Stheraven __node_pointer_pointer __npp = __bucket_list_.release(); 2370227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 2371227825Stheraven __u.__bucket_list_.reset(__npp); 2372227825Stheraven } 2373227825Stheraven _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2374288943Sdim __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2375227825Stheraven __u.__bucket_list_.get_deleter().__alloc()); 2376288943Sdim __swap_allocator(__node_alloc(), __u.__node_alloc()); 2377227825Stheraven _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2378227825Stheraven __p2_.swap(__u.__p2_); 2379227825Stheraven __p3_.swap(__u.__p3_); 2380227825Stheraven if (size() > 0) 2381241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2382253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2383227825Stheraven if (__u.size() > 0) 2384241900Sdim __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2385253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2386261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2387261272Sdim __get_db()->swap(this, &__u); 2388261272Sdim#endif 2389227825Stheraven} 2390227825Stheraven 2391227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2392227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2393227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2394227825Stheraven{ 2395261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 2396261272Sdim "unordered container::bucket_size(n) called with n >= bucket_count()"); 2397227825Stheraven __node_const_pointer __np = __bucket_list_[__n]; 2398227825Stheraven size_type __bc = bucket_count(); 2399227825Stheraven size_type __r = 0; 2400227825Stheraven if (__np != nullptr) 2401227825Stheraven { 2402227825Stheraven for (__np = __np->__next_; __np != nullptr && 2403241900Sdim __constrain_hash(__np->__hash_, __bc) == __n; 2404227825Stheraven __np = __np->__next_, ++__r) 2405227825Stheraven ; 2406227825Stheraven } 2407227825Stheraven return __r; 2408227825Stheraven} 2409227825Stheraven 2410227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2411227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2412227825Stheravenvoid 2413227825Stheravenswap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2414227825Stheraven __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2415227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2416227825Stheraven{ 2417227825Stheraven __x.swap(__y); 2418227825Stheraven} 2419227825Stheraven 2420261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2421261272Sdim 2422261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2423261272Sdimbool 2424261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2425261272Sdim{ 2426261272Sdim return __i->__node_ != nullptr; 2427261272Sdim} 2428261272Sdim 2429261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2430261272Sdimbool 2431261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2432261272Sdim{ 2433261272Sdim return false; 2434261272Sdim} 2435261272Sdim 2436261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2437261272Sdimbool 2438261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2439261272Sdim{ 2440261272Sdim return false; 2441261272Sdim} 2442261272Sdim 2443261272Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2444261272Sdimbool 2445261272Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2446261272Sdim{ 2447261272Sdim return false; 2448261272Sdim} 2449261272Sdim 2450261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 2451227825Stheraven_LIBCPP_END_NAMESPACE_STD 2452227825Stheraven 2453227825Stheraven#endif // _LIBCPP__HASH_TABLE 2454