__hash_table revision 276792
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> 22232924Stheraven 23276792Sdim#include <__debug> 24261272Sdim 25227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 26227825Stheraven#pragma GCC system_header 27227825Stheraven#endif 28227825Stheraven 29227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 30227825Stheraven 31249989Sdim_LIBCPP_FUNC_VIS 32227825Stheravensize_t __next_prime(size_t __n); 33227825Stheraven 34227825Stheraventemplate <class _NodePtr> 35227825Stheravenstruct __hash_node_base 36227825Stheraven{ 37227825Stheraven typedef __hash_node_base __first_node; 38227825Stheraven 39227825Stheraven _NodePtr __next_; 40227825Stheraven 41227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 42227825Stheraven}; 43227825Stheraven 44227825Stheraventemplate <class _Tp, class _VoidPtr> 45227825Stheravenstruct __hash_node 46227825Stheraven : public __hash_node_base 47227825Stheraven < 48227825Stheraven typename pointer_traits<_VoidPtr>::template 49227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 50227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> > 51227825Stheraven#else 52227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> >::other 53227825Stheraven#endif 54227825Stheraven > 55227825Stheraven{ 56227825Stheraven typedef _Tp value_type; 57227825Stheraven 58227825Stheraven size_t __hash_; 59227825Stheraven value_type __value_; 60227825Stheraven}; 61227825Stheraven 62241900Sdiminline _LIBCPP_INLINE_VISIBILITY 63241900Sdimbool 64241900Sdim__is_power2(size_t __bc) 65241900Sdim{ 66241900Sdim return __bc > 2 && !(__bc & (__bc - 1)); 67241900Sdim} 68241900Sdim 69241900Sdiminline _LIBCPP_INLINE_VISIBILITY 70241900Sdimsize_t 71241900Sdim__constrain_hash(size_t __h, size_t __bc) 72241900Sdim{ 73241900Sdim return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 74241900Sdim} 75241900Sdim 76241900Sdiminline _LIBCPP_INLINE_VISIBILITY 77241900Sdimsize_t 78241900Sdim__next_pow2(size_t __n) 79241900Sdim{ 80241900Sdim return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 81241900Sdim} 82241900Sdim 83227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 84261272Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 85261272Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 86261272Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 87227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 88261272Sdim class _LIBCPP_TYPE_VIS_ONLY unordered_map; 89227825Stheraven 90227825Stheraventemplate <class _NodePtr> 91261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_iterator 92227825Stheraven{ 93227825Stheraven typedef _NodePtr __node_pointer; 94227825Stheraven 95227825Stheraven __node_pointer __node_; 96227825Stheraven 97227825Stheravenpublic: 98227825Stheraven typedef forward_iterator_tag iterator_category; 99227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 100227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 101227825Stheraven typedef value_type& reference; 102227825Stheraven typedef typename pointer_traits<__node_pointer>::template 103227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 104227825Stheraven rebind<value_type> 105227825Stheraven#else 106227825Stheraven rebind<value_type>::other 107227825Stheraven#endif 108227825Stheraven pointer; 109227825Stheraven 110261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 111261272Sdim#if _LIBCPP_STD_VER > 11 112261272Sdim : __node_(nullptr) 113261272Sdim#endif 114261272Sdim { 115261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 116261272Sdim __get_db()->__insert_i(this); 117261272Sdim#endif 118261272Sdim } 119227825Stheraven 120261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 121261272Sdim 122227825Stheraven _LIBCPP_INLINE_VISIBILITY 123261272Sdim __hash_iterator(const __hash_iterator& __i) 124261272Sdim : __node_(__i.__node_) 125261272Sdim { 126261272Sdim __get_db()->__iterator_copy(this, &__i); 127261272Sdim } 128261272Sdim 129227825Stheraven _LIBCPP_INLINE_VISIBILITY 130261272Sdim ~__hash_iterator() 131261272Sdim { 132261272Sdim __get_db()->__erase_i(this); 133261272Sdim } 134227825Stheraven 135227825Stheraven _LIBCPP_INLINE_VISIBILITY 136261272Sdim __hash_iterator& operator=(const __hash_iterator& __i) 137261272Sdim { 138261272Sdim if (this != &__i) 139261272Sdim { 140261272Sdim __get_db()->__iterator_copy(this, &__i); 141261272Sdim __node_ = __i.__node_; 142261272Sdim } 143261272Sdim return *this; 144261272Sdim } 145261272Sdim 146261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 147261272Sdim 148261272Sdim _LIBCPP_INLINE_VISIBILITY 149261272Sdim reference operator*() const 150261272Sdim { 151261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 152261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 153261272Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 154261272Sdim#endif 155261272Sdim return __node_->__value_; 156261272Sdim } 157261272Sdim _LIBCPP_INLINE_VISIBILITY 158261272Sdim pointer operator->() const 159261272Sdim { 160261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 161261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 162261272Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 163261272Sdim#endif 164261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 165261272Sdim } 166261272Sdim 167261272Sdim _LIBCPP_INLINE_VISIBILITY 168227825Stheraven __hash_iterator& operator++() 169227825Stheraven { 170261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 171261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 172261272Sdim "Attempted to increment non-incrementable unordered container iterator"); 173261272Sdim#endif 174227825Stheraven __node_ = __node_->__next_; 175227825Stheraven return *this; 176227825Stheraven } 177227825Stheraven 178227825Stheraven _LIBCPP_INLINE_VISIBILITY 179227825Stheraven __hash_iterator operator++(int) 180227825Stheraven { 181227825Stheraven __hash_iterator __t(*this); 182227825Stheraven ++(*this); 183227825Stheraven return __t; 184227825Stheraven } 185227825Stheraven 186227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 187227825Stheraven bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 188261272Sdim { 189261272Sdim return __x.__node_ == __y.__node_; 190261272Sdim } 191227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 192227825Stheraven bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 193261272Sdim {return !(__x == __y);} 194227825Stheraven 195227825Stheravenprivate: 196261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 197227825Stheraven _LIBCPP_INLINE_VISIBILITY 198261272Sdim __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 199261272Sdim : __node_(__node) 200261272Sdim { 201261272Sdim __get_db()->__insert_ic(this, __c); 202261272Sdim } 203261272Sdim#else 204261272Sdim _LIBCPP_INLINE_VISIBILITY 205227825Stheraven __hash_iterator(__node_pointer __node) _NOEXCEPT 206227825Stheraven : __node_(__node) 207227825Stheraven {} 208261272Sdim#endif 209227825Stheraven 210227825Stheraven template <class, class, class, class> friend class __hash_table; 211261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 212261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 213261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 214261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 215227825Stheraven}; 216227825Stheraven 217227825Stheraventemplate <class _ConstNodePtr> 218261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 219227825Stheraven{ 220227825Stheraven typedef _ConstNodePtr __node_pointer; 221227825Stheraven 222227825Stheraven __node_pointer __node_; 223227825Stheraven 224227825Stheraven typedef typename remove_const< 225227825Stheraven typename pointer_traits<__node_pointer>::element_type 226227825Stheraven >::type __node; 227227825Stheraven 228227825Stheravenpublic: 229227825Stheraven typedef forward_iterator_tag iterator_category; 230227825Stheraven typedef typename __node::value_type value_type; 231227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 232227825Stheraven typedef const value_type& reference; 233227825Stheraven typedef typename pointer_traits<__node_pointer>::template 234227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 235227825Stheraven rebind<const value_type> 236227825Stheraven#else 237227825Stheraven rebind<const value_type>::other 238227825Stheraven#endif 239227825Stheraven pointer; 240227825Stheraven typedef typename pointer_traits<__node_pointer>::template 241227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 242227825Stheraven rebind<__node> 243227825Stheraven#else 244227825Stheraven rebind<__node>::other 245227825Stheraven#endif 246227825Stheraven __non_const_node_pointer; 247227825Stheraven typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 248227825Stheraven 249261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 250261272Sdim#if _LIBCPP_STD_VER > 11 251261272Sdim : __node_(nullptr) 252261272Sdim#endif 253261272Sdim { 254261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 255261272Sdim __get_db()->__insert_i(this); 256261272Sdim#endif 257261272Sdim } 258227825Stheraven _LIBCPP_INLINE_VISIBILITY 259227825Stheraven __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 260227825Stheraven : __node_(__x.__node_) 261261272Sdim { 262261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 263261272Sdim __get_db()->__iterator_copy(this, &__x); 264261272Sdim#endif 265261272Sdim } 266227825Stheraven 267261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 268261272Sdim 269227825Stheraven _LIBCPP_INLINE_VISIBILITY 270261272Sdim __hash_const_iterator(const __hash_const_iterator& __i) 271261272Sdim : __node_(__i.__node_) 272261272Sdim { 273261272Sdim __get_db()->__iterator_copy(this, &__i); 274261272Sdim } 275261272Sdim 276227825Stheraven _LIBCPP_INLINE_VISIBILITY 277261272Sdim ~__hash_const_iterator() 278261272Sdim { 279261272Sdim __get_db()->__erase_i(this); 280261272Sdim } 281227825Stheraven 282227825Stheraven _LIBCPP_INLINE_VISIBILITY 283261272Sdim __hash_const_iterator& operator=(const __hash_const_iterator& __i) 284261272Sdim { 285261272Sdim if (this != &__i) 286261272Sdim { 287261272Sdim __get_db()->__iterator_copy(this, &__i); 288261272Sdim __node_ = __i.__node_; 289261272Sdim } 290261272Sdim return *this; 291261272Sdim } 292261272Sdim 293261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 294261272Sdim 295261272Sdim _LIBCPP_INLINE_VISIBILITY 296261272Sdim reference operator*() const 297261272Sdim { 298261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 299261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 300261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 301261272Sdim#endif 302261272Sdim return __node_->__value_; 303261272Sdim } 304261272Sdim _LIBCPP_INLINE_VISIBILITY 305261272Sdim pointer operator->() const 306261272Sdim { 307261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 308261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 309261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 310261272Sdim#endif 311261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 312261272Sdim } 313261272Sdim 314261272Sdim _LIBCPP_INLINE_VISIBILITY 315227825Stheraven __hash_const_iterator& operator++() 316227825Stheraven { 317261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 318261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 319261272Sdim "Attempted to increment non-incrementable unordered container const_iterator"); 320261272Sdim#endif 321227825Stheraven __node_ = __node_->__next_; 322227825Stheraven return *this; 323227825Stheraven } 324227825Stheraven 325227825Stheraven _LIBCPP_INLINE_VISIBILITY 326227825Stheraven __hash_const_iterator operator++(int) 327227825Stheraven { 328227825Stheraven __hash_const_iterator __t(*this); 329227825Stheraven ++(*this); 330227825Stheraven return __t; 331227825Stheraven } 332227825Stheraven 333227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 334227825Stheraven bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 335261272Sdim { 336261272Sdim return __x.__node_ == __y.__node_; 337261272Sdim } 338227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 339227825Stheraven bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 340261272Sdim {return !(__x == __y);} 341227825Stheraven 342227825Stheravenprivate: 343261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 344227825Stheraven _LIBCPP_INLINE_VISIBILITY 345261272Sdim __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 346261272Sdim : __node_(__node) 347261272Sdim { 348261272Sdim __get_db()->__insert_ic(this, __c); 349261272Sdim } 350261272Sdim#else 351261272Sdim _LIBCPP_INLINE_VISIBILITY 352227825Stheraven __hash_const_iterator(__node_pointer __node) _NOEXCEPT 353227825Stheraven : __node_(__node) 354227825Stheraven {} 355261272Sdim#endif 356227825Stheraven 357227825Stheraven template <class, class, class, class> friend class __hash_table; 358261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 359261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 360261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 361227825Stheraven}; 362227825Stheraven 363261272Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 364227825Stheraven 365227825Stheraventemplate <class _NodePtr> 366261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 367227825Stheraven{ 368227825Stheraven typedef _NodePtr __node_pointer; 369227825Stheraven 370227825Stheraven __node_pointer __node_; 371227825Stheraven size_t __bucket_; 372227825Stheraven size_t __bucket_count_; 373227825Stheraven 374227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 375227825Stheravenpublic: 376227825Stheraven typedef forward_iterator_tag iterator_category; 377227825Stheraven typedef typename __pointer_traits::element_type::value_type value_type; 378227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 379227825Stheraven typedef value_type& reference; 380227825Stheraven typedef typename __pointer_traits::template 381227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 382227825Stheraven rebind<value_type> 383227825Stheraven#else 384227825Stheraven rebind<value_type>::other 385227825Stheraven#endif 386227825Stheraven pointer; 387227825Stheraven 388261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 389261272Sdim { 390261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 391261272Sdim __get_db()->__insert_i(this); 392261272Sdim#endif 393261272Sdim } 394227825Stheraven 395261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 396261272Sdim 397227825Stheraven _LIBCPP_INLINE_VISIBILITY 398261272Sdim __hash_local_iterator(const __hash_local_iterator& __i) 399261272Sdim : __node_(__i.__node_), 400261272Sdim __bucket_(__i.__bucket_), 401261272Sdim __bucket_count_(__i.__bucket_count_) 402261272Sdim { 403261272Sdim __get_db()->__iterator_copy(this, &__i); 404261272Sdim } 405261272Sdim 406227825Stheraven _LIBCPP_INLINE_VISIBILITY 407261272Sdim ~__hash_local_iterator() 408261272Sdim { 409261272Sdim __get_db()->__erase_i(this); 410261272Sdim } 411227825Stheraven 412227825Stheraven _LIBCPP_INLINE_VISIBILITY 413261272Sdim __hash_local_iterator& operator=(const __hash_local_iterator& __i) 414261272Sdim { 415261272Sdim if (this != &__i) 416261272Sdim { 417261272Sdim __get_db()->__iterator_copy(this, &__i); 418261272Sdim __node_ = __i.__node_; 419261272Sdim __bucket_ = __i.__bucket_; 420261272Sdim __bucket_count_ = __i.__bucket_count_; 421261272Sdim } 422261272Sdim return *this; 423261272Sdim } 424261272Sdim 425261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 426261272Sdim 427261272Sdim _LIBCPP_INLINE_VISIBILITY 428261272Sdim reference operator*() const 429261272Sdim { 430261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 431261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 432261272Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 433261272Sdim#endif 434261272Sdim return __node_->__value_; 435261272Sdim } 436261272Sdim _LIBCPP_INLINE_VISIBILITY 437261272Sdim pointer operator->() const 438261272Sdim { 439261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 440261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 441261272Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 442261272Sdim#endif 443261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 444261272Sdim } 445261272Sdim 446261272Sdim _LIBCPP_INLINE_VISIBILITY 447227825Stheraven __hash_local_iterator& operator++() 448227825Stheraven { 449261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 450261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 451261272Sdim "Attempted to increment non-incrementable unordered container local_iterator"); 452261272Sdim#endif 453227825Stheraven __node_ = __node_->__next_; 454241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 455227825Stheraven __node_ = nullptr; 456227825Stheraven return *this; 457227825Stheraven } 458227825Stheraven 459227825Stheraven _LIBCPP_INLINE_VISIBILITY 460227825Stheraven __hash_local_iterator operator++(int) 461227825Stheraven { 462227825Stheraven __hash_local_iterator __t(*this); 463227825Stheraven ++(*this); 464227825Stheraven return __t; 465227825Stheraven } 466227825Stheraven 467227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 468227825Stheraven bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 469261272Sdim { 470261272Sdim return __x.__node_ == __y.__node_; 471261272Sdim } 472227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 473227825Stheraven bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 474261272Sdim {return !(__x == __y);} 475227825Stheraven 476227825Stheravenprivate: 477261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 478227825Stheraven _LIBCPP_INLINE_VISIBILITY 479227825Stheraven __hash_local_iterator(__node_pointer __node, size_t __bucket, 480261272Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 481261272Sdim : __node_(__node), 482261272Sdim __bucket_(__bucket), 483261272Sdim __bucket_count_(__bucket_count) 484261272Sdim { 485261272Sdim __get_db()->__insert_ic(this, __c); 486261272Sdim if (__node_ != nullptr) 487261272Sdim __node_ = __node_->__next_; 488261272Sdim } 489261272Sdim#else 490261272Sdim _LIBCPP_INLINE_VISIBILITY 491261272Sdim __hash_local_iterator(__node_pointer __node, size_t __bucket, 492227825Stheraven size_t __bucket_count) _NOEXCEPT 493227825Stheraven : __node_(__node), 494227825Stheraven __bucket_(__bucket), 495227825Stheraven __bucket_count_(__bucket_count) 496227825Stheraven { 497227825Stheraven if (__node_ != nullptr) 498227825Stheraven __node_ = __node_->__next_; 499227825Stheraven } 500261272Sdim#endif 501227825Stheraven template <class, class, class, class> friend class __hash_table; 502261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 503261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 504227825Stheraven}; 505227825Stheraven 506227825Stheraventemplate <class _ConstNodePtr> 507261272Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 508227825Stheraven{ 509227825Stheraven typedef _ConstNodePtr __node_pointer; 510227825Stheraven 511227825Stheraven __node_pointer __node_; 512227825Stheraven size_t __bucket_; 513227825Stheraven size_t __bucket_count_; 514227825Stheraven 515227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 516227825Stheraven typedef typename __pointer_traits::element_type __node; 517227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 518227825Stheraven typedef typename pointer_traits<__node_pointer>::template 519227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 520227825Stheraven rebind<__non_const_node> 521227825Stheraven#else 522227825Stheraven rebind<__non_const_node>::other 523227825Stheraven#endif 524227825Stheraven __non_const_node_pointer; 525227825Stheraven typedef __hash_local_iterator<__non_const_node_pointer> 526227825Stheraven __non_const_iterator; 527227825Stheravenpublic: 528227825Stheraven typedef forward_iterator_tag iterator_category; 529227825Stheraven typedef typename remove_const< 530227825Stheraven typename __pointer_traits::element_type::value_type 531227825Stheraven >::type value_type; 532227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 533227825Stheraven typedef const value_type& reference; 534227825Stheraven typedef typename __pointer_traits::template 535227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 536227825Stheraven rebind<const value_type> 537227825Stheraven#else 538227825Stheraven rebind<const value_type>::other 539227825Stheraven#endif 540227825Stheraven pointer; 541227825Stheraven 542261272Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 543261272Sdim { 544261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 545261272Sdim __get_db()->__insert_i(this); 546261272Sdim#endif 547261272Sdim } 548261272Sdim 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 551227825Stheraven : __node_(__x.__node_), 552227825Stheraven __bucket_(__x.__bucket_), 553227825Stheraven __bucket_count_(__x.__bucket_count_) 554261272Sdim { 555261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 556261272Sdim __get_db()->__iterator_copy(this, &__x); 557261272Sdim#endif 558261272Sdim } 559227825Stheraven 560261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 561261272Sdim 562227825Stheraven _LIBCPP_INLINE_VISIBILITY 563261272Sdim __hash_const_local_iterator(const __hash_const_local_iterator& __i) 564261272Sdim : __node_(__i.__node_), 565261272Sdim __bucket_(__i.__bucket_), 566261272Sdim __bucket_count_(__i.__bucket_count_) 567261272Sdim { 568261272Sdim __get_db()->__iterator_copy(this, &__i); 569261272Sdim } 570261272Sdim 571227825Stheraven _LIBCPP_INLINE_VISIBILITY 572261272Sdim ~__hash_const_local_iterator() 573261272Sdim { 574261272Sdim __get_db()->__erase_i(this); 575261272Sdim } 576227825Stheraven 577227825Stheraven _LIBCPP_INLINE_VISIBILITY 578261272Sdim __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 579261272Sdim { 580261272Sdim if (this != &__i) 581261272Sdim { 582261272Sdim __get_db()->__iterator_copy(this, &__i); 583261272Sdim __node_ = __i.__node_; 584261272Sdim __bucket_ = __i.__bucket_; 585261272Sdim __bucket_count_ = __i.__bucket_count_; 586261272Sdim } 587261272Sdim return *this; 588261272Sdim } 589261272Sdim 590261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 591261272Sdim 592261272Sdim _LIBCPP_INLINE_VISIBILITY 593261272Sdim reference operator*() const 594261272Sdim { 595261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 596261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 597261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 598261272Sdim#endif 599261272Sdim return __node_->__value_; 600261272Sdim } 601261272Sdim _LIBCPP_INLINE_VISIBILITY 602261272Sdim pointer operator->() const 603261272Sdim { 604261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 605261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 606261272Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 607261272Sdim#endif 608261272Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 609261272Sdim } 610261272Sdim 611261272Sdim _LIBCPP_INLINE_VISIBILITY 612227825Stheraven __hash_const_local_iterator& operator++() 613227825Stheraven { 614261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 615261272Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 616261272Sdim "Attempted to increment non-incrementable unordered container const_local_iterator"); 617261272Sdim#endif 618227825Stheraven __node_ = __node_->__next_; 619241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 620227825Stheraven __node_ = nullptr; 621227825Stheraven return *this; 622227825Stheraven } 623227825Stheraven 624227825Stheraven _LIBCPP_INLINE_VISIBILITY 625227825Stheraven __hash_const_local_iterator operator++(int) 626227825Stheraven { 627227825Stheraven __hash_const_local_iterator __t(*this); 628227825Stheraven ++(*this); 629227825Stheraven return __t; 630227825Stheraven } 631227825Stheraven 632227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 633227825Stheraven bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 634261272Sdim { 635261272Sdim return __x.__node_ == __y.__node_; 636261272Sdim } 637227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 638227825Stheraven bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 639261272Sdim {return !(__x == __y);} 640227825Stheraven 641227825Stheravenprivate: 642261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 643227825Stheraven _LIBCPP_INLINE_VISIBILITY 644227825Stheraven __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 645261272Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 646261272Sdim : __node_(__node), 647261272Sdim __bucket_(__bucket), 648261272Sdim __bucket_count_(__bucket_count) 649261272Sdim { 650261272Sdim __get_db()->__insert_ic(this, __c); 651261272Sdim if (__node_ != nullptr) 652261272Sdim __node_ = __node_->__next_; 653261272Sdim } 654261272Sdim#else 655261272Sdim _LIBCPP_INLINE_VISIBILITY 656261272Sdim __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 657227825Stheraven size_t __bucket_count) _NOEXCEPT 658227825Stheraven : __node_(__node), 659227825Stheraven __bucket_(__bucket), 660227825Stheraven __bucket_count_(__bucket_count) 661227825Stheraven { 662227825Stheraven if (__node_ != nullptr) 663227825Stheraven __node_ = __node_->__next_; 664227825Stheraven } 665261272Sdim#endif 666227825Stheraven template <class, class, class, class> friend class __hash_table; 667261272Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 668227825Stheraven}; 669227825Stheraven 670227825Stheraventemplate <class _Alloc> 671227825Stheravenclass __bucket_list_deallocator 672227825Stheraven{ 673227825Stheraven typedef _Alloc allocator_type; 674227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 675227825Stheraven typedef typename __alloc_traits::size_type size_type; 676227825Stheraven 677227825Stheraven __compressed_pair<size_type, allocator_type> __data_; 678227825Stheravenpublic: 679227825Stheraven typedef typename __alloc_traits::pointer pointer; 680227825Stheraven 681227825Stheraven _LIBCPP_INLINE_VISIBILITY 682227825Stheraven __bucket_list_deallocator() 683227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 684227825Stheraven : __data_(0) {} 685227825Stheraven 686227825Stheraven _LIBCPP_INLINE_VISIBILITY 687227825Stheraven __bucket_list_deallocator(const allocator_type& __a, size_type __size) 688227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 689227825Stheraven : __data_(__size, __a) {} 690227825Stheraven 691227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 692227825Stheraven 693227825Stheraven _LIBCPP_INLINE_VISIBILITY 694227825Stheraven __bucket_list_deallocator(__bucket_list_deallocator&& __x) 695227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 696227825Stheraven : __data_(_VSTD::move(__x.__data_)) 697227825Stheraven { 698227825Stheraven __x.size() = 0; 699227825Stheraven } 700227825Stheraven 701227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 702227825Stheraven 703227825Stheraven _LIBCPP_INLINE_VISIBILITY 704227825Stheraven size_type& size() _NOEXCEPT {return __data_.first();} 705227825Stheraven _LIBCPP_INLINE_VISIBILITY 706227825Stheraven size_type size() const _NOEXCEPT {return __data_.first();} 707227825Stheraven 708227825Stheraven _LIBCPP_INLINE_VISIBILITY 709227825Stheraven allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 710227825Stheraven _LIBCPP_INLINE_VISIBILITY 711227825Stheraven const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 712227825Stheraven 713227825Stheraven _LIBCPP_INLINE_VISIBILITY 714227825Stheraven void operator()(pointer __p) _NOEXCEPT 715227825Stheraven { 716227825Stheraven __alloc_traits::deallocate(__alloc(), __p, size()); 717227825Stheraven } 718227825Stheraven}; 719227825Stheraven 720227825Stheraventemplate <class _Alloc> class __hash_map_node_destructor; 721227825Stheraven 722227825Stheraventemplate <class _Alloc> 723227825Stheravenclass __hash_node_destructor 724227825Stheraven{ 725227825Stheraven typedef _Alloc allocator_type; 726227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 727227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 728227825Stheravenpublic: 729227825Stheraven typedef typename __alloc_traits::pointer pointer; 730227825Stheravenprivate: 731227825Stheraven 732227825Stheraven allocator_type& __na_; 733227825Stheraven 734227825Stheraven __hash_node_destructor& operator=(const __hash_node_destructor&); 735227825Stheraven 736227825Stheravenpublic: 737227825Stheraven bool __value_constructed; 738227825Stheraven 739227825Stheraven _LIBCPP_INLINE_VISIBILITY 740227825Stheraven explicit __hash_node_destructor(allocator_type& __na, 741227825Stheraven bool __constructed = false) _NOEXCEPT 742227825Stheraven : __na_(__na), 743227825Stheraven __value_constructed(__constructed) 744227825Stheraven {} 745227825Stheraven 746227825Stheraven _LIBCPP_INLINE_VISIBILITY 747227825Stheraven void operator()(pointer __p) _NOEXCEPT 748227825Stheraven { 749227825Stheraven if (__value_constructed) 750227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 751227825Stheraven if (__p) 752227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 753227825Stheraven } 754227825Stheraven 755227825Stheraven template <class> friend class __hash_map_node_destructor; 756227825Stheraven}; 757227825Stheraven 758227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 759227825Stheravenclass __hash_table 760227825Stheraven{ 761227825Stheravenpublic: 762227825Stheraven typedef _Tp value_type; 763227825Stheraven typedef _Hash hasher; 764227825Stheraven typedef _Equal key_equal; 765227825Stheraven typedef _Alloc allocator_type; 766227825Stheraven 767227825Stheravenprivate: 768227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 769227825Stheravenpublic: 770227825Stheraven typedef value_type& reference; 771227825Stheraven typedef const value_type& const_reference; 772227825Stheraven typedef typename __alloc_traits::pointer pointer; 773227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 774227825Stheraven typedef typename __alloc_traits::size_type size_type; 775227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 776227825Stheravenpublic: 777227825Stheraven // Create __node 778227825Stheraven typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 779227825Stheraven typedef typename __alloc_traits::template 780227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 781227825Stheraven rebind_alloc<__node> 782227825Stheraven#else 783227825Stheraven rebind_alloc<__node>::other 784227825Stheraven#endif 785227825Stheraven __node_allocator; 786227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 787227825Stheraven typedef typename __node_traits::pointer __node_pointer; 788253146Stheraven typedef typename __node_traits::pointer __node_const_pointer; 789232924Stheraven typedef __hash_node_base<__node_pointer> __first_node; 790253146Stheraven typedef typename pointer_traits<__node_pointer>::template 791253146Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 792253146Stheraven rebind<__first_node> 793253146Stheraven#else 794253146Stheraven rebind<__first_node>::other 795253146Stheraven#endif 796253146Stheraven __node_base_pointer; 797227825Stheraven 798227825Stheravenprivate: 799227825Stheraven 800227825Stheraven typedef typename __node_traits::template 801227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 802227825Stheraven rebind_alloc<__node_pointer> 803227825Stheraven#else 804227825Stheraven rebind_alloc<__node_pointer>::other 805227825Stheraven#endif 806227825Stheraven __pointer_allocator; 807227825Stheraven typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 808227825Stheraven typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 809227825Stheraven typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 810227825Stheraven typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 811227825Stheraven 812227825Stheraven // --- Member data begin --- 813227825Stheraven __bucket_list __bucket_list_; 814227825Stheraven __compressed_pair<__first_node, __node_allocator> __p1_; 815227825Stheraven __compressed_pair<size_type, hasher> __p2_; 816227825Stheraven __compressed_pair<float, key_equal> __p3_; 817227825Stheraven // --- Member data end --- 818227825Stheraven 819227825Stheraven _LIBCPP_INLINE_VISIBILITY 820227825Stheraven size_type& size() _NOEXCEPT {return __p2_.first();} 821227825Stheravenpublic: 822227825Stheraven _LIBCPP_INLINE_VISIBILITY 823227825Stheraven size_type size() const _NOEXCEPT {return __p2_.first();} 824227825Stheraven 825227825Stheraven _LIBCPP_INLINE_VISIBILITY 826227825Stheraven hasher& hash_function() _NOEXCEPT {return __p2_.second();} 827227825Stheraven _LIBCPP_INLINE_VISIBILITY 828227825Stheraven const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 829227825Stheraven 830227825Stheraven _LIBCPP_INLINE_VISIBILITY 831227825Stheraven float& max_load_factor() _NOEXCEPT {return __p3_.first();} 832227825Stheraven _LIBCPP_INLINE_VISIBILITY 833227825Stheraven float max_load_factor() const _NOEXCEPT {return __p3_.first();} 834227825Stheraven 835227825Stheraven _LIBCPP_INLINE_VISIBILITY 836227825Stheraven key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 837227825Stheraven _LIBCPP_INLINE_VISIBILITY 838227825Stheraven const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 839227825Stheraven 840227825Stheraven _LIBCPP_INLINE_VISIBILITY 841227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 842227825Stheraven _LIBCPP_INLINE_VISIBILITY 843227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 844227825Stheraven {return __p1_.second();} 845227825Stheraven 846227825Stheravenpublic: 847227825Stheraven typedef __hash_iterator<__node_pointer> iterator; 848253146Stheraven typedef __hash_const_iterator<__node_pointer> const_iterator; 849227825Stheraven typedef __hash_local_iterator<__node_pointer> local_iterator; 850253146Stheraven typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 851227825Stheraven 852227825Stheraven __hash_table() 853227825Stheraven _NOEXCEPT_( 854227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 855227825Stheraven is_nothrow_default_constructible<__first_node>::value && 856227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 857227825Stheraven is_nothrow_default_constructible<hasher>::value && 858227825Stheraven is_nothrow_default_constructible<key_equal>::value); 859227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql); 860227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql, 861227825Stheraven const allocator_type& __a); 862227825Stheraven explicit __hash_table(const allocator_type& __a); 863227825Stheraven __hash_table(const __hash_table& __u); 864227825Stheraven __hash_table(const __hash_table& __u, const allocator_type& __a); 865227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 866227825Stheraven __hash_table(__hash_table&& __u) 867227825Stheraven _NOEXCEPT_( 868227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 869227825Stheraven is_nothrow_move_constructible<__first_node>::value && 870227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 871227825Stheraven is_nothrow_move_constructible<hasher>::value && 872227825Stheraven is_nothrow_move_constructible<key_equal>::value); 873227825Stheraven __hash_table(__hash_table&& __u, const allocator_type& __a); 874227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 875227825Stheraven ~__hash_table(); 876227825Stheraven 877227825Stheraven __hash_table& operator=(const __hash_table& __u); 878227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 879227825Stheraven __hash_table& operator=(__hash_table&& __u) 880227825Stheraven _NOEXCEPT_( 881227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 882227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 883227825Stheraven is_nothrow_move_assignable<hasher>::value && 884227825Stheraven is_nothrow_move_assignable<key_equal>::value); 885227825Stheraven#endif 886227825Stheraven template <class _InputIterator> 887227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 888227825Stheraven template <class _InputIterator> 889227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 890227825Stheraven 891227825Stheraven _LIBCPP_INLINE_VISIBILITY 892227825Stheraven size_type max_size() const _NOEXCEPT 893227825Stheraven { 894227825Stheraven return allocator_traits<__pointer_allocator>::max_size( 895227825Stheraven __bucket_list_.get_deleter().__alloc()); 896227825Stheraven } 897227825Stheraven 898227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 899227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 900227825Stheraven iterator __node_insert_multi(const_iterator __p, 901227825Stheraven __node_pointer __nd); 902227825Stheraven 903227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 904227825Stheraven template <class... _Args> 905227825Stheraven pair<iterator, bool> __emplace_unique(_Args&&... __args); 906227825Stheraven template <class... _Args> 907227825Stheraven iterator __emplace_multi(_Args&&... __args); 908227825Stheraven template <class... _Args> 909227825Stheraven iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 910227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 911227825Stheraven 912227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __x); 913227825Stheraven 914227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 915232924Stheraven template <class _Pp> 916232924Stheraven pair<iterator, bool> __insert_unique(_Pp&& __x); 917227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 918227825Stheraven 919227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 920232924Stheraven template <class _Pp> 921232924Stheraven iterator __insert_multi(_Pp&& __x); 922232924Stheraven template <class _Pp> 923232924Stheraven iterator __insert_multi(const_iterator __p, _Pp&& __x); 924227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 925227825Stheraven iterator __insert_multi(const value_type& __x); 926227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __x); 927227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 928227825Stheraven 929227825Stheraven void clear() _NOEXCEPT; 930227825Stheraven void rehash(size_type __n); 931227825Stheraven _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 932227825Stheraven {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 933227825Stheraven 934227825Stheraven _LIBCPP_INLINE_VISIBILITY 935227825Stheraven size_type bucket_count() const _NOEXCEPT 936227825Stheraven { 937227825Stheraven return __bucket_list_.get_deleter().size(); 938227825Stheraven } 939227825Stheraven 940227825Stheraven iterator begin() _NOEXCEPT; 941227825Stheraven iterator end() _NOEXCEPT; 942227825Stheraven const_iterator begin() const _NOEXCEPT; 943227825Stheraven const_iterator end() const _NOEXCEPT; 944227825Stheraven 945227825Stheraven template <class _Key> 946227825Stheraven _LIBCPP_INLINE_VISIBILITY 947227825Stheraven size_type bucket(const _Key& __k) const 948261272Sdim { 949261272Sdim _LIBCPP_ASSERT(bucket_count() > 0, 950261272Sdim "unordered container::bucket(key) called when bucket_count() == 0"); 951261272Sdim return __constrain_hash(hash_function()(__k), bucket_count()); 952261272Sdim } 953227825Stheraven 954227825Stheraven template <class _Key> 955227825Stheraven iterator find(const _Key& __x); 956227825Stheraven template <class _Key> 957227825Stheraven const_iterator find(const _Key& __x) const; 958227825Stheraven 959232924Stheraven typedef __hash_node_destructor<__node_allocator> _Dp; 960232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 961227825Stheraven 962227825Stheraven iterator erase(const_iterator __p); 963227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 964227825Stheraven template <class _Key> 965227825Stheraven size_type __erase_unique(const _Key& __k); 966227825Stheraven template <class _Key> 967227825Stheraven size_type __erase_multi(const _Key& __k); 968227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 969227825Stheraven 970227825Stheraven template <class _Key> 971227825Stheraven size_type __count_unique(const _Key& __k) const; 972227825Stheraven template <class _Key> 973227825Stheraven size_type __count_multi(const _Key& __k) const; 974227825Stheraven 975227825Stheraven template <class _Key> 976227825Stheraven pair<iterator, iterator> 977227825Stheraven __equal_range_unique(const _Key& __k); 978227825Stheraven template <class _Key> 979227825Stheraven pair<const_iterator, const_iterator> 980227825Stheraven __equal_range_unique(const _Key& __k) const; 981227825Stheraven 982227825Stheraven template <class _Key> 983227825Stheraven pair<iterator, iterator> 984227825Stheraven __equal_range_multi(const _Key& __k); 985227825Stheraven template <class _Key> 986227825Stheraven pair<const_iterator, const_iterator> 987227825Stheraven __equal_range_multi(const _Key& __k) const; 988227825Stheraven 989227825Stheraven void swap(__hash_table& __u) 990227825Stheraven _NOEXCEPT_( 991227825Stheraven (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 992227825Stheraven __is_nothrow_swappable<__pointer_allocator>::value) && 993227825Stheraven (!__node_traits::propagate_on_container_swap::value || 994227825Stheraven __is_nothrow_swappable<__node_allocator>::value) && 995227825Stheraven __is_nothrow_swappable<hasher>::value && 996227825Stheraven __is_nothrow_swappable<key_equal>::value); 997227825Stheraven 998227825Stheraven _LIBCPP_INLINE_VISIBILITY 999227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1000253146Stheraven {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1001227825Stheraven size_type bucket_size(size_type __n) const; 1002227825Stheraven _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1003227825Stheraven { 1004227825Stheraven size_type __bc = bucket_count(); 1005227825Stheraven return __bc != 0 ? (float)size() / __bc : 0.f; 1006227825Stheraven } 1007227825Stheraven _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1008261272Sdim { 1009261272Sdim _LIBCPP_ASSERT(__mlf > 0, 1010261272Sdim "unordered container::max_load_factor(lf) called with lf <= 0"); 1011261272Sdim max_load_factor() = _VSTD::max(__mlf, load_factor()); 1012261272Sdim } 1013227825Stheraven 1014261272Sdim _LIBCPP_INLINE_VISIBILITY 1015261272Sdim local_iterator 1016261272Sdim begin(size_type __n) 1017261272Sdim { 1018261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1019261272Sdim "unordered container::begin(n) called with n >= bucket_count()"); 1020261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1021261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1022261272Sdim#else 1023261272Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1024261272Sdim#endif 1025261272Sdim } 1026261272Sdim 1027261272Sdim _LIBCPP_INLINE_VISIBILITY 1028261272Sdim local_iterator 1029261272Sdim end(size_type __n) 1030261272Sdim { 1031261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1032261272Sdim "unordered container::end(n) called with n >= bucket_count()"); 1033261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1034261272Sdim return local_iterator(nullptr, __n, bucket_count(), this); 1035261272Sdim#else 1036261272Sdim return local_iterator(nullptr, __n, bucket_count()); 1037261272Sdim#endif 1038261272Sdim } 1039261272Sdim 1040261272Sdim _LIBCPP_INLINE_VISIBILITY 1041261272Sdim const_local_iterator 1042261272Sdim cbegin(size_type __n) const 1043261272Sdim { 1044261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1045261272Sdim "unordered container::cbegin(n) called with n >= bucket_count()"); 1046261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1047261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1048261272Sdim#else 1049261272Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1050261272Sdim#endif 1051261272Sdim } 1052261272Sdim 1053261272Sdim _LIBCPP_INLINE_VISIBILITY 1054261272Sdim const_local_iterator 1055261272Sdim cend(size_type __n) const 1056261272Sdim { 1057261272Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1058261272Sdim "unordered container::cend(n) called with n >= bucket_count()"); 1059261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1060261272Sdim return const_local_iterator(nullptr, __n, bucket_count(), this); 1061261272Sdim#else 1062261272Sdim return const_local_iterator(nullptr, __n, bucket_count()); 1063261272Sdim#endif 1064261272Sdim } 1065261272Sdim 1066261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1067261272Sdim 1068261272Sdim bool __dereferenceable(const const_iterator* __i) const; 1069261272Sdim bool __decrementable(const const_iterator* __i) const; 1070261272Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1071261272Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1072261272Sdim 1073261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1074261272Sdim 1075227825Stheravenprivate: 1076227825Stheraven void __rehash(size_type __n); 1077227825Stheraven 1078227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1079227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1080227825Stheraven template <class ..._Args> 1081227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1082227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1083227825Stheraven __node_holder __construct_node(value_type&& __v, size_t __hash); 1084227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1085227825Stheraven __node_holder __construct_node(const value_type& __v); 1086227825Stheraven#endif 1087227825Stheraven __node_holder __construct_node(const value_type& __v, size_t __hash); 1088227825Stheraven 1089227825Stheraven _LIBCPP_INLINE_VISIBILITY 1090227825Stheraven void __copy_assign_alloc(const __hash_table& __u) 1091227825Stheraven {__copy_assign_alloc(__u, integral_constant<bool, 1092227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1093227825Stheraven void __copy_assign_alloc(const __hash_table& __u, true_type); 1094227825Stheraven _LIBCPP_INLINE_VISIBILITY 1095232924Stheraven void __copy_assign_alloc(const __hash_table&, false_type) {} 1096227825Stheraven 1097227825Stheraven void __move_assign(__hash_table& __u, false_type); 1098227825Stheraven void __move_assign(__hash_table& __u, true_type) 1099227825Stheraven _NOEXCEPT_( 1100227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1101227825Stheraven is_nothrow_move_assignable<hasher>::value && 1102227825Stheraven is_nothrow_move_assignable<key_equal>::value); 1103227825Stheraven _LIBCPP_INLINE_VISIBILITY 1104227825Stheraven void __move_assign_alloc(__hash_table& __u) 1105227825Stheraven _NOEXCEPT_( 1106227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1107227825Stheraven (is_nothrow_move_assignable<__pointer_allocator>::value && 1108227825Stheraven is_nothrow_move_assignable<__node_allocator>::value)) 1109227825Stheraven {__move_assign_alloc(__u, integral_constant<bool, 1110227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1111227825Stheraven _LIBCPP_INLINE_VISIBILITY 1112227825Stheraven void __move_assign_alloc(__hash_table& __u, true_type) 1113227825Stheraven _NOEXCEPT_( 1114227825Stheraven is_nothrow_move_assignable<__pointer_allocator>::value && 1115227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1116227825Stheraven { 1117227825Stheraven __bucket_list_.get_deleter().__alloc() = 1118227825Stheraven _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1119227825Stheraven __node_alloc() = _VSTD::move(__u.__node_alloc()); 1120227825Stheraven } 1121227825Stheraven _LIBCPP_INLINE_VISIBILITY 1122227825Stheraven void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1123227825Stheraven 1124232924Stheraven template <class _Ap> 1125227825Stheraven _LIBCPP_INLINE_VISIBILITY 1126227825Stheraven static 1127227825Stheraven void 1128232924Stheraven __swap_alloc(_Ap& __x, _Ap& __y) 1129227825Stheraven _NOEXCEPT_( 1130232924Stheraven !allocator_traits<_Ap>::propagate_on_container_swap::value || 1131232924Stheraven __is_nothrow_swappable<_Ap>::value) 1132227825Stheraven { 1133227825Stheraven __swap_alloc(__x, __y, 1134227825Stheraven integral_constant<bool, 1135232924Stheraven allocator_traits<_Ap>::propagate_on_container_swap::value 1136227825Stheraven >()); 1137227825Stheraven } 1138227825Stheraven 1139232924Stheraven template <class _Ap> 1140227825Stheraven _LIBCPP_INLINE_VISIBILITY 1141227825Stheraven static 1142227825Stheraven void 1143232924Stheraven __swap_alloc(_Ap& __x, _Ap& __y, true_type) 1144232924Stheraven _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 1145227825Stheraven { 1146227825Stheraven using _VSTD::swap; 1147227825Stheraven swap(__x, __y); 1148227825Stheraven } 1149227825Stheraven 1150232924Stheraven template <class _Ap> 1151227825Stheraven _LIBCPP_INLINE_VISIBILITY 1152227825Stheraven static 1153227825Stheraven void 1154232924Stheraven __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 1155227825Stheraven 1156227825Stheraven void __deallocate(__node_pointer __np) _NOEXCEPT; 1157227825Stheraven __node_pointer __detach() _NOEXCEPT; 1158253146Stheraven 1159261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1160261272Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1161227825Stheraven}; 1162227825Stheraven 1163227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1164227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1165227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1166227825Stheraven _NOEXCEPT_( 1167227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 1168227825Stheraven is_nothrow_default_constructible<__first_node>::value && 1169227825Stheraven is_nothrow_default_constructible<hasher>::value && 1170227825Stheraven is_nothrow_default_constructible<key_equal>::value) 1171227825Stheraven : __p2_(0), 1172227825Stheraven __p3_(1.0f) 1173227825Stheraven{ 1174227825Stheraven} 1175227825Stheraven 1176227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1177227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1178227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1179227825Stheraven const key_equal& __eql) 1180227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter()), 1181227825Stheraven __p1_(), 1182227825Stheraven __p2_(0, __hf), 1183227825Stheraven __p3_(1.0f, __eql) 1184227825Stheraven{ 1185227825Stheraven} 1186227825Stheraven 1187227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1188227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1189227825Stheraven const key_equal& __eql, 1190227825Stheraven const allocator_type& __a) 1191227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1192227825Stheraven __p1_(__node_allocator(__a)), 1193227825Stheraven __p2_(0, __hf), 1194227825Stheraven __p3_(1.0f, __eql) 1195227825Stheraven{ 1196227825Stheraven} 1197227825Stheraven 1198227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1199227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1200227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1201227825Stheraven __p1_(__node_allocator(__a)), 1202227825Stheraven __p2_(0), 1203227825Stheraven __p3_(1.0f) 1204227825Stheraven{ 1205227825Stheraven} 1206227825Stheraven 1207227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1208227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1209227825Stheraven : __bucket_list_(nullptr, 1210227825Stheraven __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1211227825Stheraven select_on_container_copy_construction( 1212227825Stheraven __u.__bucket_list_.get_deleter().__alloc()), 0)), 1213227825Stheraven __p1_(allocator_traits<__node_allocator>:: 1214227825Stheraven select_on_container_copy_construction(__u.__node_alloc())), 1215227825Stheraven __p2_(0, __u.hash_function()), 1216227825Stheraven __p3_(__u.__p3_) 1217227825Stheraven{ 1218227825Stheraven} 1219227825Stheraven 1220227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1221227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1222227825Stheraven const allocator_type& __a) 1223227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1224227825Stheraven __p1_(__node_allocator(__a)), 1225227825Stheraven __p2_(0, __u.hash_function()), 1226227825Stheraven __p3_(__u.__p3_) 1227227825Stheraven{ 1228227825Stheraven} 1229227825Stheraven 1230227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1231227825Stheraven 1232227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1233227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1234227825Stheraven _NOEXCEPT_( 1235227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 1236227825Stheraven is_nothrow_move_constructible<__first_node>::value && 1237227825Stheraven is_nothrow_move_constructible<hasher>::value && 1238227825Stheraven is_nothrow_move_constructible<key_equal>::value) 1239227825Stheraven : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1240227825Stheraven __p1_(_VSTD::move(__u.__p1_)), 1241227825Stheraven __p2_(_VSTD::move(__u.__p2_)), 1242227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1243227825Stheraven{ 1244227825Stheraven if (size() > 0) 1245227825Stheraven { 1246241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1247253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1248227825Stheraven __u.__p1_.first().__next_ = nullptr; 1249227825Stheraven __u.size() = 0; 1250227825Stheraven } 1251227825Stheraven} 1252227825Stheraven 1253227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1254227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1255227825Stheraven const allocator_type& __a) 1256227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1257227825Stheraven __p1_(__node_allocator(__a)), 1258227825Stheraven __p2_(0, _VSTD::move(__u.hash_function())), 1259227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1260227825Stheraven{ 1261227825Stheraven if (__a == allocator_type(__u.__node_alloc())) 1262227825Stheraven { 1263227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1264227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1265227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1266227825Stheraven if (__u.size() > 0) 1267227825Stheraven { 1268227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1269227825Stheraven __u.__p1_.first().__next_ = nullptr; 1270241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1271253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1272227825Stheraven size() = __u.size(); 1273227825Stheraven __u.size() = 0; 1274227825Stheraven } 1275227825Stheraven } 1276227825Stheraven} 1277227825Stheraven 1278227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1279227825Stheraven 1280227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1281227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1282227825Stheraven{ 1283227825Stheraven __deallocate(__p1_.first().__next_); 1284261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1285261272Sdim __get_db()->__erase_c(this); 1286261272Sdim#endif 1287227825Stheraven} 1288227825Stheraven 1289227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1290227825Stheravenvoid 1291227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1292227825Stheraven const __hash_table& __u, true_type) 1293227825Stheraven{ 1294227825Stheraven if (__node_alloc() != __u.__node_alloc()) 1295227825Stheraven { 1296227825Stheraven clear(); 1297227825Stheraven __bucket_list_.reset(); 1298227825Stheraven __bucket_list_.get_deleter().size() = 0; 1299227825Stheraven } 1300227825Stheraven __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1301227825Stheraven __node_alloc() = __u.__node_alloc(); 1302227825Stheraven} 1303227825Stheraven 1304227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1305227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1306227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1307227825Stheraven{ 1308227825Stheraven if (this != &__u) 1309227825Stheraven { 1310227825Stheraven __copy_assign_alloc(__u); 1311227825Stheraven hash_function() = __u.hash_function(); 1312227825Stheraven key_eq() = __u.key_eq(); 1313227825Stheraven max_load_factor() = __u.max_load_factor(); 1314227825Stheraven __assign_multi(__u.begin(), __u.end()); 1315227825Stheraven } 1316227825Stheraven return *this; 1317227825Stheraven} 1318227825Stheraven 1319227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1320227825Stheravenvoid 1321227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1322227825Stheraven _NOEXCEPT 1323227825Stheraven{ 1324227825Stheraven __node_allocator& __na = __node_alloc(); 1325227825Stheraven while (__np != nullptr) 1326227825Stheraven { 1327227825Stheraven __node_pointer __next = __np->__next_; 1328261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1329261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 1330261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1331261272Sdim { 1332261272Sdim --__p; 1333261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 1334261272Sdim if (__i->__node_ == __np) 1335261272Sdim { 1336261272Sdim (*__p)->__c_ = nullptr; 1337261272Sdim if (--__c->end_ != __p) 1338261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1339261272Sdim } 1340261272Sdim } 1341261272Sdim __get_db()->unlock(); 1342261272Sdim#endif 1343227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1344227825Stheraven __node_traits::deallocate(__na, __np, 1); 1345227825Stheraven __np = __next; 1346227825Stheraven } 1347227825Stheraven} 1348227825Stheraven 1349227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1350227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1351227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1352227825Stheraven{ 1353227825Stheraven size_type __bc = bucket_count(); 1354227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1355227825Stheraven __bucket_list_[__i] = nullptr; 1356227825Stheraven size() = 0; 1357227825Stheraven __node_pointer __cache = __p1_.first().__next_; 1358227825Stheraven __p1_.first().__next_ = nullptr; 1359227825Stheraven return __cache; 1360227825Stheraven} 1361227825Stheraven 1362227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1363227825Stheraven 1364227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1365227825Stheravenvoid 1366227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1367227825Stheraven __hash_table& __u, true_type) 1368227825Stheraven _NOEXCEPT_( 1369227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1370227825Stheraven is_nothrow_move_assignable<hasher>::value && 1371227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1372227825Stheraven{ 1373227825Stheraven clear(); 1374227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1375227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1376227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1377227825Stheraven __move_assign_alloc(__u); 1378227825Stheraven size() = __u.size(); 1379227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1380227825Stheraven max_load_factor() = __u.max_load_factor(); 1381227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1382227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1383227825Stheraven if (size() > 0) 1384227825Stheraven { 1385241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1386253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1387227825Stheraven __u.__p1_.first().__next_ = nullptr; 1388227825Stheraven __u.size() = 0; 1389227825Stheraven } 1390261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1391261272Sdim __get_db()->swap(this, &__u); 1392261272Sdim#endif 1393227825Stheraven} 1394227825Stheraven 1395227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1396227825Stheravenvoid 1397227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1398227825Stheraven __hash_table& __u, false_type) 1399227825Stheraven{ 1400227825Stheraven if (__node_alloc() == __u.__node_alloc()) 1401227825Stheraven __move_assign(__u, true_type()); 1402227825Stheraven else 1403227825Stheraven { 1404227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1405227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1406227825Stheraven max_load_factor() = __u.max_load_factor(); 1407227825Stheraven if (bucket_count() != 0) 1408227825Stheraven { 1409227825Stheraven __node_pointer __cache = __detach(); 1410227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1411227825Stheraven try 1412227825Stheraven { 1413227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1414227825Stheraven const_iterator __i = __u.begin(); 1415227825Stheraven while (__cache != nullptr && __u.size() != 0) 1416227825Stheraven { 1417227825Stheraven __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1418227825Stheraven __node_pointer __next = __cache->__next_; 1419227825Stheraven __node_insert_multi(__cache); 1420227825Stheraven __cache = __next; 1421227825Stheraven } 1422227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1423227825Stheraven } 1424227825Stheraven catch (...) 1425227825Stheraven { 1426227825Stheraven __deallocate(__cache); 1427227825Stheraven throw; 1428227825Stheraven } 1429227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1430227825Stheraven __deallocate(__cache); 1431227825Stheraven } 1432227825Stheraven const_iterator __i = __u.begin(); 1433227825Stheraven while (__u.size() != 0) 1434227825Stheraven { 1435227825Stheraven __node_holder __h = 1436227825Stheraven __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1437227825Stheraven __node_insert_multi(__h.get()); 1438227825Stheraven __h.release(); 1439227825Stheraven } 1440227825Stheraven } 1441227825Stheraven} 1442227825Stheraven 1443227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1444227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1445227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1446227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1447227825Stheraven _NOEXCEPT_( 1448227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1449227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1450227825Stheraven is_nothrow_move_assignable<hasher>::value && 1451227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1452227825Stheraven{ 1453227825Stheraven __move_assign(__u, integral_constant<bool, 1454227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1455227825Stheraven return *this; 1456227825Stheraven} 1457227825Stheraven 1458227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1459227825Stheraven 1460227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1461227825Stheraventemplate <class _InputIterator> 1462227825Stheravenvoid 1463227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1464227825Stheraven _InputIterator __last) 1465227825Stheraven{ 1466227825Stheraven if (bucket_count() != 0) 1467227825Stheraven { 1468227825Stheraven __node_pointer __cache = __detach(); 1469227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1470227825Stheraven try 1471227825Stheraven { 1472227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1473227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1474227825Stheraven { 1475227825Stheraven __cache->__value_ = *__first; 1476227825Stheraven __node_pointer __next = __cache->__next_; 1477227825Stheraven __node_insert_unique(__cache); 1478227825Stheraven __cache = __next; 1479227825Stheraven } 1480227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1481227825Stheraven } 1482227825Stheraven catch (...) 1483227825Stheraven { 1484227825Stheraven __deallocate(__cache); 1485227825Stheraven throw; 1486227825Stheraven } 1487227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1488227825Stheraven __deallocate(__cache); 1489227825Stheraven } 1490227825Stheraven for (; __first != __last; ++__first) 1491227825Stheraven __insert_unique(*__first); 1492227825Stheraven} 1493227825Stheraven 1494227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1495227825Stheraventemplate <class _InputIterator> 1496227825Stheravenvoid 1497227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1498227825Stheraven _InputIterator __last) 1499227825Stheraven{ 1500227825Stheraven if (bucket_count() != 0) 1501227825Stheraven { 1502227825Stheraven __node_pointer __cache = __detach(); 1503227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1504227825Stheraven try 1505227825Stheraven { 1506227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1507227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1508227825Stheraven { 1509227825Stheraven __cache->__value_ = *__first; 1510227825Stheraven __node_pointer __next = __cache->__next_; 1511227825Stheraven __node_insert_multi(__cache); 1512227825Stheraven __cache = __next; 1513227825Stheraven } 1514227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1515227825Stheraven } 1516227825Stheraven catch (...) 1517227825Stheraven { 1518227825Stheraven __deallocate(__cache); 1519227825Stheraven throw; 1520227825Stheraven } 1521227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1522227825Stheraven __deallocate(__cache); 1523227825Stheraven } 1524227825Stheraven for (; __first != __last; ++__first) 1525227825Stheraven __insert_multi(*__first); 1526227825Stheraven} 1527227825Stheraven 1528227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1529227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1530227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1531227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1532227825Stheraven{ 1533261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1534261272Sdim return iterator(__p1_.first().__next_, this); 1535261272Sdim#else 1536227825Stheraven return iterator(__p1_.first().__next_); 1537261272Sdim#endif 1538227825Stheraven} 1539227825Stheraven 1540227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1541227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1542227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1543227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1544227825Stheraven{ 1545261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1546261272Sdim return iterator(nullptr, this); 1547261272Sdim#else 1548227825Stheraven return iterator(nullptr); 1549261272Sdim#endif 1550227825Stheraven} 1551227825Stheraven 1552227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1553227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1554227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1555227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1556227825Stheraven{ 1557261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1558261272Sdim return const_iterator(__p1_.first().__next_, this); 1559261272Sdim#else 1560227825Stheraven return const_iterator(__p1_.first().__next_); 1561261272Sdim#endif 1562227825Stheraven} 1563227825Stheraven 1564227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1565227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1566227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1567227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1568227825Stheraven{ 1569261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1570261272Sdim return const_iterator(nullptr, this); 1571261272Sdim#else 1572227825Stheraven return const_iterator(nullptr); 1573261272Sdim#endif 1574227825Stheraven} 1575227825Stheraven 1576227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1577227825Stheravenvoid 1578227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1579227825Stheraven{ 1580227825Stheraven if (size() > 0) 1581227825Stheraven { 1582227825Stheraven __deallocate(__p1_.first().__next_); 1583227825Stheraven __p1_.first().__next_ = nullptr; 1584227825Stheraven size_type __bc = bucket_count(); 1585227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1586227825Stheraven __bucket_list_[__i] = nullptr; 1587227825Stheraven size() = 0; 1588227825Stheraven } 1589227825Stheraven} 1590227825Stheraven 1591227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1592227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1593227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1594227825Stheraven{ 1595227825Stheraven __nd->__hash_ = hash_function()(__nd->__value_); 1596227825Stheraven size_type __bc = bucket_count(); 1597227825Stheraven bool __inserted = false; 1598227825Stheraven __node_pointer __ndptr; 1599227825Stheraven size_t __chash; 1600227825Stheraven if (__bc != 0) 1601227825Stheraven { 1602241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1603227825Stheraven __ndptr = __bucket_list_[__chash]; 1604227825Stheraven if (__ndptr != nullptr) 1605227825Stheraven { 1606227825Stheraven for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1607241900Sdim __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1608227825Stheraven __ndptr = __ndptr->__next_) 1609227825Stheraven { 1610227825Stheraven if (key_eq()(__ndptr->__value_, __nd->__value_)) 1611227825Stheraven goto __done; 1612227825Stheraven } 1613227825Stheraven } 1614227825Stheraven } 1615227825Stheraven { 1616227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1617227825Stheraven { 1618241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1619227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1620227825Stheraven __bc = bucket_count(); 1621241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1622227825Stheraven } 1623227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1624227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1625227825Stheraven if (__pn == nullptr) 1626227825Stheraven { 1627253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1628227825Stheraven __nd->__next_ = __pn->__next_; 1629227825Stheraven __pn->__next_ = __nd; 1630227825Stheraven // fix up __bucket_list_ 1631227825Stheraven __bucket_list_[__chash] = __pn; 1632227825Stheraven if (__nd->__next_ != nullptr) 1633241900Sdim __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1634227825Stheraven } 1635227825Stheraven else 1636227825Stheraven { 1637227825Stheraven __nd->__next_ = __pn->__next_; 1638227825Stheraven __pn->__next_ = __nd; 1639227825Stheraven } 1640227825Stheraven __ndptr = __nd; 1641227825Stheraven // increment size 1642227825Stheraven ++size(); 1643227825Stheraven __inserted = true; 1644227825Stheraven } 1645227825Stheraven__done: 1646261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1647261272Sdim return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1648261272Sdim#else 1649227825Stheraven return pair<iterator, bool>(iterator(__ndptr), __inserted); 1650261272Sdim#endif 1651227825Stheraven} 1652227825Stheraven 1653227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1654227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1655227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1656227825Stheraven{ 1657227825Stheraven __cp->__hash_ = hash_function()(__cp->__value_); 1658227825Stheraven size_type __bc = bucket_count(); 1659227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1660227825Stheraven { 1661241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1662227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1663227825Stheraven __bc = bucket_count(); 1664227825Stheraven } 1665241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1666227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1667227825Stheraven if (__pn == nullptr) 1668227825Stheraven { 1669253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1670227825Stheraven __cp->__next_ = __pn->__next_; 1671227825Stheraven __pn->__next_ = __cp; 1672227825Stheraven // fix up __bucket_list_ 1673227825Stheraven __bucket_list_[__chash] = __pn; 1674227825Stheraven if (__cp->__next_ != nullptr) 1675241900Sdim __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1676227825Stheraven } 1677227825Stheraven else 1678227825Stheraven { 1679227825Stheraven for (bool __found = false; __pn->__next_ != nullptr && 1680241900Sdim __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1681227825Stheraven __pn = __pn->__next_) 1682227825Stheraven { 1683227825Stheraven // __found key_eq() action 1684227825Stheraven // false false loop 1685227825Stheraven // true true loop 1686227825Stheraven // false true set __found to true 1687227825Stheraven // true false break 1688227825Stheraven if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1689227825Stheraven key_eq()(__pn->__next_->__value_, __cp->__value_))) 1690227825Stheraven { 1691227825Stheraven if (!__found) 1692227825Stheraven __found = true; 1693227825Stheraven else 1694227825Stheraven break; 1695227825Stheraven } 1696227825Stheraven } 1697227825Stheraven __cp->__next_ = __pn->__next_; 1698227825Stheraven __pn->__next_ = __cp; 1699227825Stheraven if (__cp->__next_ != nullptr) 1700227825Stheraven { 1701241900Sdim size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1702227825Stheraven if (__nhash != __chash) 1703227825Stheraven __bucket_list_[__nhash] = __cp; 1704227825Stheraven } 1705227825Stheraven } 1706227825Stheraven ++size(); 1707261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1708261272Sdim return iterator(__cp, this); 1709261272Sdim#else 1710227825Stheraven return iterator(__cp); 1711261272Sdim#endif 1712227825Stheraven} 1713227825Stheraven 1714227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1715227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1716227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1717227825Stheraven const_iterator __p, __node_pointer __cp) 1718227825Stheraven{ 1719261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1720261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1721261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1722261272Sdim " referring to this unordered container"); 1723261272Sdim#endif 1724227825Stheraven if (__p != end() && key_eq()(*__p, __cp->__value_)) 1725227825Stheraven { 1726253146Stheraven __node_pointer __np = __p.__node_; 1727227825Stheraven __cp->__hash_ = __np->__hash_; 1728227825Stheraven size_type __bc = bucket_count(); 1729227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1730227825Stheraven { 1731241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1732227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1733227825Stheraven __bc = bucket_count(); 1734227825Stheraven } 1735241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1736227825Stheraven __node_pointer __pp = __bucket_list_[__chash]; 1737227825Stheraven while (__pp->__next_ != __np) 1738227825Stheraven __pp = __pp->__next_; 1739227825Stheraven __cp->__next_ = __np; 1740227825Stheraven __pp->__next_ = __cp; 1741227825Stheraven ++size(); 1742261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1743261272Sdim return iterator(__cp, this); 1744261272Sdim#else 1745227825Stheraven return iterator(__cp); 1746261272Sdim#endif 1747227825Stheraven } 1748227825Stheraven return __node_insert_multi(__cp); 1749227825Stheraven} 1750227825Stheraven 1751227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1752227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1753227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1754227825Stheraven{ 1755227825Stheraven size_t __hash = hash_function()(__x); 1756227825Stheraven size_type __bc = bucket_count(); 1757227825Stheraven bool __inserted = false; 1758227825Stheraven __node_pointer __nd; 1759227825Stheraven size_t __chash; 1760227825Stheraven if (__bc != 0) 1761227825Stheraven { 1762241900Sdim __chash = __constrain_hash(__hash, __bc); 1763227825Stheraven __nd = __bucket_list_[__chash]; 1764227825Stheraven if (__nd != nullptr) 1765227825Stheraven { 1766227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1767241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1768227825Stheraven __nd = __nd->__next_) 1769227825Stheraven { 1770227825Stheraven if (key_eq()(__nd->__value_, __x)) 1771227825Stheraven goto __done; 1772227825Stheraven } 1773227825Stheraven } 1774227825Stheraven } 1775227825Stheraven { 1776227825Stheraven __node_holder __h = __construct_node(__x, __hash); 1777227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1778227825Stheraven { 1779241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1780227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1781227825Stheraven __bc = bucket_count(); 1782241900Sdim __chash = __constrain_hash(__hash, __bc); 1783227825Stheraven } 1784227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1785227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1786227825Stheraven if (__pn == nullptr) 1787227825Stheraven { 1788253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1789227825Stheraven __h->__next_ = __pn->__next_; 1790227825Stheraven __pn->__next_ = __h.get(); 1791227825Stheraven // fix up __bucket_list_ 1792227825Stheraven __bucket_list_[__chash] = __pn; 1793227825Stheraven if (__h->__next_ != nullptr) 1794241900Sdim __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1795227825Stheraven } 1796227825Stheraven else 1797227825Stheraven { 1798227825Stheraven __h->__next_ = __pn->__next_; 1799227825Stheraven __pn->__next_ = __h.get(); 1800227825Stheraven } 1801227825Stheraven __nd = __h.release(); 1802227825Stheraven // increment size 1803227825Stheraven ++size(); 1804227825Stheraven __inserted = true; 1805227825Stheraven } 1806227825Stheraven__done: 1807261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1808261272Sdim return pair<iterator, bool>(iterator(__nd, this), __inserted); 1809261272Sdim#else 1810227825Stheraven return pair<iterator, bool>(iterator(__nd), __inserted); 1811261272Sdim#endif 1812227825Stheraven} 1813227825Stheraven 1814227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1815227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1816227825Stheraven 1817227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1818227825Stheraventemplate <class... _Args> 1819227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1820227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1821227825Stheraven{ 1822227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1823227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1824227825Stheraven if (__r.second) 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_multi(_Args&&... __args) 1833227825Stheraven{ 1834227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1835227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1836227825Stheraven __h.release(); 1837227825Stheraven return __r; 1838227825Stheraven} 1839227825Stheraven 1840227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1841227825Stheraventemplate <class... _Args> 1842227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1843227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1844227825Stheraven const_iterator __p, _Args&&... __args) 1845227825Stheraven{ 1846261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1847261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1848261272Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1849261272Sdim " referring to this unordered container"); 1850261272Sdim#endif 1851227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1852227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1853227825Stheraven __h.release(); 1854227825Stheraven return __r; 1855227825Stheraven} 1856227825Stheraven 1857227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1858227825Stheraven 1859227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1860232924Stheraventemplate <class _Pp> 1861227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1862232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1863227825Stheraven{ 1864232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1865227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1866227825Stheraven if (__r.second) 1867227825Stheraven __h.release(); 1868227825Stheraven return __r; 1869227825Stheraven} 1870227825Stheraven 1871227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1872227825Stheraven 1873227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1874227825Stheraven 1875227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1876232924Stheraventemplate <class _Pp> 1877227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1878232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1879227825Stheraven{ 1880232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1881227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1882227825Stheraven __h.release(); 1883227825Stheraven return __r; 1884227825Stheraven} 1885227825Stheraven 1886227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1887232924Stheraventemplate <class _Pp> 1888227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1889227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1890232924Stheraven _Pp&& __x) 1891227825Stheraven{ 1892261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1893261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1894261272Sdim "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1895261272Sdim " referring to this unordered container"); 1896261272Sdim#endif 1897232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1898227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1899227825Stheraven __h.release(); 1900227825Stheraven return __r; 1901227825Stheraven} 1902227825Stheraven 1903227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1904227825Stheraven 1905227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1906227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1907227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1908227825Stheraven{ 1909227825Stheraven __node_holder __h = __construct_node(__x); 1910227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1911227825Stheraven __h.release(); 1912227825Stheraven return __r; 1913227825Stheraven} 1914227825Stheraven 1915227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1916227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1917227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1918227825Stheraven const value_type& __x) 1919227825Stheraven{ 1920261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1921261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1922261272Sdim "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1923261272Sdim " referring to this unordered container"); 1924261272Sdim#endif 1925227825Stheraven __node_holder __h = __construct_node(__x); 1926227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1927227825Stheraven __h.release(); 1928227825Stheraven return __r; 1929227825Stheraven} 1930227825Stheraven 1931227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1932227825Stheraven 1933227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1934227825Stheravenvoid 1935227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1936227825Stheraven{ 1937241900Sdim if (__n == 1) 1938241900Sdim __n = 2; 1939241900Sdim else if (__n & (__n - 1)) 1940241900Sdim __n = __next_prime(__n); 1941227825Stheraven size_type __bc = bucket_count(); 1942227825Stheraven if (__n > __bc) 1943227825Stheraven __rehash(__n); 1944241900Sdim else if (__n < __bc) 1945227825Stheraven { 1946227825Stheraven __n = _VSTD::max<size_type> 1947227825Stheraven ( 1948227825Stheraven __n, 1949241900Sdim __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1950241900Sdim __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1951227825Stheraven ); 1952227825Stheraven if (__n < __bc) 1953227825Stheraven __rehash(__n); 1954227825Stheraven } 1955227825Stheraven} 1956227825Stheraven 1957227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1958227825Stheravenvoid 1959227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1960227825Stheraven{ 1961261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1962261272Sdim __get_db()->__invalidate_all(this); 1963261272Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1964227825Stheraven __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1965227825Stheraven __bucket_list_.reset(__nbc > 0 ? 1966227825Stheraven __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1967227825Stheraven __bucket_list_.get_deleter().size() = __nbc; 1968227825Stheraven if (__nbc > 0) 1969227825Stheraven { 1970227825Stheraven for (size_type __i = 0; __i < __nbc; ++__i) 1971227825Stheraven __bucket_list_[__i] = nullptr; 1972253146Stheraven __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1973227825Stheraven __node_pointer __cp = __pp->__next_; 1974227825Stheraven if (__cp != nullptr) 1975227825Stheraven { 1976241900Sdim size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1977227825Stheraven __bucket_list_[__chash] = __pp; 1978227825Stheraven size_type __phash = __chash; 1979227825Stheraven for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1980227825Stheraven __cp = __pp->__next_) 1981227825Stheraven { 1982241900Sdim __chash = __constrain_hash(__cp->__hash_, __nbc); 1983227825Stheraven if (__chash == __phash) 1984227825Stheraven __pp = __cp; 1985227825Stheraven else 1986227825Stheraven { 1987227825Stheraven if (__bucket_list_[__chash] == nullptr) 1988227825Stheraven { 1989227825Stheraven __bucket_list_[__chash] = __pp; 1990227825Stheraven __pp = __cp; 1991227825Stheraven __phash = __chash; 1992227825Stheraven } 1993227825Stheraven else 1994227825Stheraven { 1995227825Stheraven __node_pointer __np = __cp; 1996227825Stheraven for (; __np->__next_ != nullptr && 1997227825Stheraven key_eq()(__cp->__value_, __np->__next_->__value_); 1998227825Stheraven __np = __np->__next_) 1999227825Stheraven ; 2000227825Stheraven __pp->__next_ = __np->__next_; 2001227825Stheraven __np->__next_ = __bucket_list_[__chash]->__next_; 2002227825Stheraven __bucket_list_[__chash]->__next_ = __cp; 2003227825Stheraven 2004227825Stheraven } 2005227825Stheraven } 2006227825Stheraven } 2007227825Stheraven } 2008227825Stheraven } 2009227825Stheraven} 2010227825Stheraven 2011227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2012227825Stheraventemplate <class _Key> 2013227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2014227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2015227825Stheraven{ 2016227825Stheraven size_t __hash = hash_function()(__k); 2017227825Stheraven size_type __bc = bucket_count(); 2018227825Stheraven if (__bc != 0) 2019227825Stheraven { 2020241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2021227825Stheraven __node_pointer __nd = __bucket_list_[__chash]; 2022227825Stheraven if (__nd != nullptr) 2023227825Stheraven { 2024227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2025241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2026227825Stheraven __nd = __nd->__next_) 2027227825Stheraven { 2028227825Stheraven if (key_eq()(__nd->__value_, __k)) 2029261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2030261272Sdim return iterator(__nd, this); 2031261272Sdim#else 2032227825Stheraven return iterator(__nd); 2033261272Sdim#endif 2034227825Stheraven } 2035227825Stheraven } 2036227825Stheraven } 2037227825Stheraven return end(); 2038227825Stheraven} 2039227825Stheraven 2040227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2041227825Stheraventemplate <class _Key> 2042227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2043227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2044227825Stheraven{ 2045227825Stheraven size_t __hash = hash_function()(__k); 2046227825Stheraven size_type __bc = bucket_count(); 2047227825Stheraven if (__bc != 0) 2048227825Stheraven { 2049241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 2050227825Stheraven __node_const_pointer __nd = __bucket_list_[__chash]; 2051227825Stheraven if (__nd != nullptr) 2052227825Stheraven { 2053227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2054241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2055227825Stheraven __nd = __nd->__next_) 2056227825Stheraven { 2057227825Stheraven if (key_eq()(__nd->__value_, __k)) 2058261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2059261272Sdim return const_iterator(__nd, this); 2060261272Sdim#else 2061227825Stheraven return const_iterator(__nd); 2062261272Sdim#endif 2063227825Stheraven } 2064227825Stheraven } 2065227825Stheraven 2066227825Stheraven } 2067227825Stheraven return end(); 2068227825Stheraven} 2069227825Stheraven 2070227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2071227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 2072227825Stheraven 2073227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2074227825Stheraventemplate <class ..._Args> 2075227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2076227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2077227825Stheraven{ 2078227825Stheraven __node_allocator& __na = __node_alloc(); 2079232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2080227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2081227825Stheraven __h.get_deleter().__value_constructed = true; 2082227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2083227825Stheraven __h->__next_ = nullptr; 2084227825Stheraven return __h; 2085227825Stheraven} 2086227825Stheraven 2087227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2088227825Stheraven 2089227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2090227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2091227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2092227825Stheraven size_t __hash) 2093227825Stheraven{ 2094227825Stheraven __node_allocator& __na = __node_alloc(); 2095232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2096227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2097227825Stheraven __h.get_deleter().__value_constructed = true; 2098227825Stheraven __h->__hash_ = __hash; 2099227825Stheraven __h->__next_ = nullptr; 2100261272Sdim return __h; 2101227825Stheraven} 2102227825Stheraven 2103227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2104227825Stheraven 2105227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2106227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2107227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2108227825Stheraven{ 2109227825Stheraven __node_allocator& __na = __node_alloc(); 2110232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2111227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2112227825Stheraven __h.get_deleter().__value_constructed = true; 2113227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2114227825Stheraven __h->__next_ = nullptr; 2115261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 2116227825Stheraven} 2117227825Stheraven 2118227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2119227825Stheraven 2120227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2121227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2122227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2123227825Stheraven size_t __hash) 2124227825Stheraven{ 2125227825Stheraven __node_allocator& __na = __node_alloc(); 2126232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2127227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2128227825Stheraven __h.get_deleter().__value_constructed = true; 2129227825Stheraven __h->__hash_ = __hash; 2130227825Stheraven __h->__next_ = nullptr; 2131261272Sdim return _VSTD::move(__h); // explicitly moved for C++03 2132227825Stheraven} 2133227825Stheraven 2134227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2135227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2136227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2137227825Stheraven{ 2138253146Stheraven __node_pointer __np = __p.__node_; 2139261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2140261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2141261272Sdim "unordered container erase(iterator) called with an iterator not" 2142261272Sdim " referring to this container"); 2143261272Sdim _LIBCPP_ASSERT(__p != end(), 2144261272Sdim "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2145261272Sdim iterator __r(__np, this); 2146261272Sdim#else 2147227825Stheraven iterator __r(__np); 2148261272Sdim#endif 2149227825Stheraven ++__r; 2150227825Stheraven remove(__p); 2151227825Stheraven return __r; 2152227825Stheraven} 2153227825Stheraven 2154227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2155227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2156227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2157227825Stheraven const_iterator __last) 2158227825Stheraven{ 2159261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2160261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2161261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2162261272Sdim " referring to this unodered container"); 2163261272Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2164261272Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2165261272Sdim " referring to this unodered container"); 2166261272Sdim#endif 2167227825Stheraven for (const_iterator __p = __first; __first != __last; __p = __first) 2168227825Stheraven { 2169227825Stheraven ++__first; 2170227825Stheraven erase(__p); 2171227825Stheraven } 2172253146Stheraven __node_pointer __np = __last.__node_; 2173261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2174261272Sdim return iterator (__np, this); 2175261272Sdim#else 2176227825Stheraven return iterator (__np); 2177261272Sdim#endif 2178227825Stheraven} 2179227825Stheraven 2180227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2181227825Stheraventemplate <class _Key> 2182227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2183227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2184227825Stheraven{ 2185227825Stheraven iterator __i = find(__k); 2186227825Stheraven if (__i == end()) 2187227825Stheraven return 0; 2188227825Stheraven erase(__i); 2189227825Stheraven return 1; 2190227825Stheraven} 2191227825Stheraven 2192227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2193227825Stheraventemplate <class _Key> 2194227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2195227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2196227825Stheraven{ 2197227825Stheraven size_type __r = 0; 2198227825Stheraven iterator __i = find(__k); 2199227825Stheraven if (__i != end()) 2200227825Stheraven { 2201227825Stheraven iterator __e = end(); 2202227825Stheraven do 2203227825Stheraven { 2204227825Stheraven erase(__i++); 2205227825Stheraven ++__r; 2206227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2207227825Stheraven } 2208227825Stheraven return __r; 2209227825Stheraven} 2210227825Stheraven 2211227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2212227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2213227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2214227825Stheraven{ 2215227825Stheraven // current node 2216253146Stheraven __node_pointer __cn = __p.__node_; 2217227825Stheraven size_type __bc = bucket_count(); 2218241900Sdim size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2219227825Stheraven // find previous node 2220227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 2221227825Stheraven for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2222227825Stheraven ; 2223227825Stheraven // Fix up __bucket_list_ 2224227825Stheraven // if __pn is not in same bucket (before begin is not in same bucket) && 2225227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2226253146Stheraven if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2227253146Stheraven || __constrain_hash(__pn->__hash_, __bc) != __chash) 2228227825Stheraven { 2229241900Sdim if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2230227825Stheraven __bucket_list_[__chash] = nullptr; 2231227825Stheraven } 2232227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2233227825Stheraven if (__cn->__next_ != nullptr) 2234227825Stheraven { 2235241900Sdim size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2236227825Stheraven if (__nhash != __chash) 2237227825Stheraven __bucket_list_[__nhash] = __pn; 2238227825Stheraven } 2239227825Stheraven // remove __cn 2240227825Stheraven __pn->__next_ = __cn->__next_; 2241227825Stheraven __cn->__next_ = nullptr; 2242227825Stheraven --size(); 2243261272Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2244261272Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 2245261272Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2246261272Sdim { 2247261272Sdim --__p; 2248261272Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 2249261272Sdim if (__i->__node_ == __cn) 2250261272Sdim { 2251261272Sdim (*__p)->__c_ = nullptr; 2252261272Sdim if (--__c->end_ != __p) 2253261272Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2254261272Sdim } 2255261272Sdim } 2256261272Sdim __get_db()->unlock(); 2257261272Sdim#endif 2258232924Stheraven return __node_holder(__cn, _Dp(__node_alloc(), true)); 2259227825Stheraven} 2260227825Stheraven 2261227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2262227825Stheraventemplate <class _Key> 2263227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2264227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2265227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2266227825Stheraven{ 2267227825Stheraven return static_cast<size_type>(find(__k) != end()); 2268227825Stheraven} 2269227825Stheraven 2270227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2271227825Stheraventemplate <class _Key> 2272227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2273227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2274227825Stheraven{ 2275227825Stheraven size_type __r = 0; 2276227825Stheraven const_iterator __i = find(__k); 2277227825Stheraven if (__i != end()) 2278227825Stheraven { 2279227825Stheraven const_iterator __e = end(); 2280227825Stheraven do 2281227825Stheraven { 2282227825Stheraven ++__i; 2283227825Stheraven ++__r; 2284227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2285227825Stheraven } 2286227825Stheraven return __r; 2287227825Stheraven} 2288227825Stheraven 2289227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2290227825Stheraventemplate <class _Key> 2291227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2292227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2293227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2294227825Stheraven const _Key& __k) 2295227825Stheraven{ 2296227825Stheraven iterator __i = find(__k); 2297227825Stheraven iterator __j = __i; 2298227825Stheraven if (__i != end()) 2299227825Stheraven ++__j; 2300227825Stheraven return pair<iterator, iterator>(__i, __j); 2301227825Stheraven} 2302227825Stheraven 2303227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2304227825Stheraventemplate <class _Key> 2305227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2306227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2307227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2308227825Stheraven const _Key& __k) const 2309227825Stheraven{ 2310227825Stheraven const_iterator __i = find(__k); 2311227825Stheraven const_iterator __j = __i; 2312227825Stheraven if (__i != end()) 2313227825Stheraven ++__j; 2314227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2315227825Stheraven} 2316227825Stheraven 2317227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2318227825Stheraventemplate <class _Key> 2319227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2320227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2321227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2322227825Stheraven const _Key& __k) 2323227825Stheraven{ 2324227825Stheraven iterator __i = find(__k); 2325227825Stheraven iterator __j = __i; 2326227825Stheraven if (__i != end()) 2327227825Stheraven { 2328227825Stheraven iterator __e = end(); 2329227825Stheraven do 2330227825Stheraven { 2331227825Stheraven ++__j; 2332227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2333227825Stheraven } 2334227825Stheraven return pair<iterator, iterator>(__i, __j); 2335227825Stheraven} 2336227825Stheraven 2337227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2338227825Stheraventemplate <class _Key> 2339227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2340227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2341227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2342227825Stheraven const _Key& __k) const 2343227825Stheraven{ 2344227825Stheraven const_iterator __i = find(__k); 2345227825Stheraven const_iterator __j = __i; 2346227825Stheraven if (__i != end()) 2347227825Stheraven { 2348227825Stheraven const_iterator __e = end(); 2349227825Stheraven do 2350227825Stheraven { 2351227825Stheraven ++__j; 2352227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2353227825Stheraven } 2354227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2355227825Stheraven} 2356227825Stheraven 2357227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2358227825Stheravenvoid 2359227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2360227825Stheraven _NOEXCEPT_( 2361227825Stheraven (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 2362227825Stheraven __is_nothrow_swappable<__pointer_allocator>::value) && 2363227825Stheraven (!__node_traits::propagate_on_container_swap::value || 2364227825Stheraven __is_nothrow_swappable<__node_allocator>::value) && 2365227825Stheraven __is_nothrow_swappable<hasher>::value && 2366227825Stheraven __is_nothrow_swappable<key_equal>::value) 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()); 2374227825Stheraven __swap_alloc(__bucket_list_.get_deleter().__alloc(), 2375227825Stheraven __u.__bucket_list_.get_deleter().__alloc()); 2376227825Stheraven __swap_alloc(__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