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 21232950Stheraven#include <__undef_min_max> 22232950Stheraven 23262801Sdim#ifdef _LIBCPP_DEBUG 24262801Sdim# include <__debug> 25262801Sdim#else 26262801Sdim# define _LIBCPP_ASSERT(x, m) ((void)0) 27262801Sdim#endif 28262801Sdim 29227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 30227825Stheraven#pragma GCC system_header 31227825Stheraven#endif 32227825Stheraven 33227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 34227825Stheraven 35250514Sdim_LIBCPP_FUNC_VIS 36227825Stheravensize_t __next_prime(size_t __n); 37227825Stheraven 38227825Stheraventemplate <class _NodePtr> 39227825Stheravenstruct __hash_node_base 40227825Stheraven{ 41227825Stheraven typedef __hash_node_base __first_node; 42227825Stheraven 43227825Stheraven _NodePtr __next_; 44227825Stheraven 45227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 46227825Stheraven}; 47227825Stheraven 48227825Stheraventemplate <class _Tp, class _VoidPtr> 49227825Stheravenstruct __hash_node 50227825Stheraven : public __hash_node_base 51227825Stheraven < 52227825Stheraven typename pointer_traits<_VoidPtr>::template 53227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 54227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> > 55227825Stheraven#else 56227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> >::other 57227825Stheraven#endif 58227825Stheraven > 59227825Stheraven{ 60227825Stheraven typedef _Tp value_type; 61227825Stheraven 62227825Stheraven size_t __hash_; 63227825Stheraven value_type __value_; 64227825Stheraven}; 65227825Stheraven 66243376Sdiminline _LIBCPP_INLINE_VISIBILITY 67243376Sdimbool 68243376Sdim__is_power2(size_t __bc) 69243376Sdim{ 70243376Sdim return __bc > 2 && !(__bc & (__bc - 1)); 71243376Sdim} 72243376Sdim 73243376Sdiminline _LIBCPP_INLINE_VISIBILITY 74243376Sdimsize_t 75243376Sdim__constrain_hash(size_t __h, size_t __bc) 76243376Sdim{ 77243376Sdim return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 78243376Sdim} 79243376Sdim 80243376Sdiminline _LIBCPP_INLINE_VISIBILITY 81243376Sdimsize_t 82243376Sdim__next_pow2(size_t __n) 83243376Sdim{ 84243376Sdim return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 85243376Sdim} 86243376Sdim 87227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 88262801Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 89262801Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 90262801Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 91227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 92262801Sdim class _LIBCPP_TYPE_VIS_ONLY unordered_map; 93227825Stheraven 94227825Stheraventemplate <class _NodePtr> 95262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_iterator 96227825Stheraven{ 97227825Stheraven typedef _NodePtr __node_pointer; 98227825Stheraven 99227825Stheraven __node_pointer __node_; 100227825Stheraven 101227825Stheravenpublic: 102227825Stheraven typedef forward_iterator_tag iterator_category; 103227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 104227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 105227825Stheraven typedef value_type& reference; 106227825Stheraven typedef typename pointer_traits<__node_pointer>::template 107227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 108227825Stheraven rebind<value_type> 109227825Stheraven#else 110227825Stheraven rebind<value_type>::other 111227825Stheraven#endif 112227825Stheraven pointer; 113227825Stheraven 114262801Sdim _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 115262801Sdim#if _LIBCPP_STD_VER > 11 116262801Sdim : __node_(nullptr) 117262801Sdim#endif 118262801Sdim { 119262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 120262801Sdim __get_db()->__insert_i(this); 121262801Sdim#endif 122262801Sdim } 123227825Stheraven 124262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 125262801Sdim 126227825Stheraven _LIBCPP_INLINE_VISIBILITY 127262801Sdim __hash_iterator(const __hash_iterator& __i) 128262801Sdim : __node_(__i.__node_) 129262801Sdim { 130262801Sdim __get_db()->__iterator_copy(this, &__i); 131262801Sdim } 132262801Sdim 133227825Stheraven _LIBCPP_INLINE_VISIBILITY 134262801Sdim ~__hash_iterator() 135262801Sdim { 136262801Sdim __get_db()->__erase_i(this); 137262801Sdim } 138227825Stheraven 139227825Stheraven _LIBCPP_INLINE_VISIBILITY 140262801Sdim __hash_iterator& operator=(const __hash_iterator& __i) 141262801Sdim { 142262801Sdim if (this != &__i) 143262801Sdim { 144262801Sdim __get_db()->__iterator_copy(this, &__i); 145262801Sdim __node_ = __i.__node_; 146262801Sdim } 147262801Sdim return *this; 148262801Sdim } 149262801Sdim 150262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 151262801Sdim 152262801Sdim _LIBCPP_INLINE_VISIBILITY 153262801Sdim reference operator*() const 154262801Sdim { 155262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 156262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 157262801Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 158262801Sdim#endif 159262801Sdim return __node_->__value_; 160262801Sdim } 161262801Sdim _LIBCPP_INLINE_VISIBILITY 162262801Sdim pointer operator->() const 163262801Sdim { 164262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 165262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 166262801Sdim "Attempted to dereference a non-dereferenceable unordered container iterator"); 167262801Sdim#endif 168262801Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 169262801Sdim } 170262801Sdim 171262801Sdim _LIBCPP_INLINE_VISIBILITY 172227825Stheraven __hash_iterator& operator++() 173227825Stheraven { 174262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 175262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 176262801Sdim "Attempted to increment non-incrementable unordered container iterator"); 177262801Sdim#endif 178227825Stheraven __node_ = __node_->__next_; 179227825Stheraven return *this; 180227825Stheraven } 181227825Stheraven 182227825Stheraven _LIBCPP_INLINE_VISIBILITY 183227825Stheraven __hash_iterator operator++(int) 184227825Stheraven { 185227825Stheraven __hash_iterator __t(*this); 186227825Stheraven ++(*this); 187227825Stheraven return __t; 188227825Stheraven } 189227825Stheraven 190227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 191227825Stheraven bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 192262801Sdim { 193262801Sdim return __x.__node_ == __y.__node_; 194262801Sdim } 195227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 196227825Stheraven bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 197262801Sdim {return !(__x == __y);} 198227825Stheraven 199227825Stheravenprivate: 200262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 201227825Stheraven _LIBCPP_INLINE_VISIBILITY 202262801Sdim __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 203262801Sdim : __node_(__node) 204262801Sdim { 205262801Sdim __get_db()->__insert_ic(this, __c); 206262801Sdim } 207262801Sdim#else 208262801Sdim _LIBCPP_INLINE_VISIBILITY 209227825Stheraven __hash_iterator(__node_pointer __node) _NOEXCEPT 210227825Stheraven : __node_(__node) 211227825Stheraven {} 212262801Sdim#endif 213227825Stheraven 214227825Stheraven template <class, class, class, class> friend class __hash_table; 215262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 216262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 217262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 218262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 219227825Stheraven}; 220227825Stheraven 221227825Stheraventemplate <class _ConstNodePtr> 222262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 223227825Stheraven{ 224227825Stheraven typedef _ConstNodePtr __node_pointer; 225227825Stheraven 226227825Stheraven __node_pointer __node_; 227227825Stheraven 228227825Stheraven typedef typename remove_const< 229227825Stheraven typename pointer_traits<__node_pointer>::element_type 230227825Stheraven >::type __node; 231227825Stheraven 232227825Stheravenpublic: 233227825Stheraven typedef forward_iterator_tag iterator_category; 234227825Stheraven typedef typename __node::value_type value_type; 235227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 236227825Stheraven typedef const value_type& reference; 237227825Stheraven typedef typename pointer_traits<__node_pointer>::template 238227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 239227825Stheraven rebind<const value_type> 240227825Stheraven#else 241227825Stheraven rebind<const value_type>::other 242227825Stheraven#endif 243227825Stheraven pointer; 244227825Stheraven typedef typename pointer_traits<__node_pointer>::template 245227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 246227825Stheraven rebind<__node> 247227825Stheraven#else 248227825Stheraven rebind<__node>::other 249227825Stheraven#endif 250227825Stheraven __non_const_node_pointer; 251227825Stheraven typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 252227825Stheraven 253262801Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 254262801Sdim#if _LIBCPP_STD_VER > 11 255262801Sdim : __node_(nullptr) 256262801Sdim#endif 257262801Sdim { 258262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 259262801Sdim __get_db()->__insert_i(this); 260262801Sdim#endif 261262801Sdim } 262227825Stheraven _LIBCPP_INLINE_VISIBILITY 263227825Stheraven __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 264227825Stheraven : __node_(__x.__node_) 265262801Sdim { 266262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 267262801Sdim __get_db()->__iterator_copy(this, &__x); 268262801Sdim#endif 269262801Sdim } 270227825Stheraven 271262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 272262801Sdim 273227825Stheraven _LIBCPP_INLINE_VISIBILITY 274262801Sdim __hash_const_iterator(const __hash_const_iterator& __i) 275262801Sdim : __node_(__i.__node_) 276262801Sdim { 277262801Sdim __get_db()->__iterator_copy(this, &__i); 278262801Sdim } 279262801Sdim 280227825Stheraven _LIBCPP_INLINE_VISIBILITY 281262801Sdim ~__hash_const_iterator() 282262801Sdim { 283262801Sdim __get_db()->__erase_i(this); 284262801Sdim } 285227825Stheraven 286227825Stheraven _LIBCPP_INLINE_VISIBILITY 287262801Sdim __hash_const_iterator& operator=(const __hash_const_iterator& __i) 288262801Sdim { 289262801Sdim if (this != &__i) 290262801Sdim { 291262801Sdim __get_db()->__iterator_copy(this, &__i); 292262801Sdim __node_ = __i.__node_; 293262801Sdim } 294262801Sdim return *this; 295262801Sdim } 296262801Sdim 297262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 298262801Sdim 299262801Sdim _LIBCPP_INLINE_VISIBILITY 300262801Sdim reference operator*() const 301262801Sdim { 302262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 303262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 304262801Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 305262801Sdim#endif 306262801Sdim return __node_->__value_; 307262801Sdim } 308262801Sdim _LIBCPP_INLINE_VISIBILITY 309262801Sdim pointer operator->() const 310262801Sdim { 311262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 312262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 313262801Sdim "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 314262801Sdim#endif 315262801Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 316262801Sdim } 317262801Sdim 318262801Sdim _LIBCPP_INLINE_VISIBILITY 319227825Stheraven __hash_const_iterator& operator++() 320227825Stheraven { 321262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 322262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 323262801Sdim "Attempted to increment non-incrementable unordered container const_iterator"); 324262801Sdim#endif 325227825Stheraven __node_ = __node_->__next_; 326227825Stheraven return *this; 327227825Stheraven } 328227825Stheraven 329227825Stheraven _LIBCPP_INLINE_VISIBILITY 330227825Stheraven __hash_const_iterator operator++(int) 331227825Stheraven { 332227825Stheraven __hash_const_iterator __t(*this); 333227825Stheraven ++(*this); 334227825Stheraven return __t; 335227825Stheraven } 336227825Stheraven 337227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 338227825Stheraven bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 339262801Sdim { 340262801Sdim return __x.__node_ == __y.__node_; 341262801Sdim } 342227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 343227825Stheraven bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 344262801Sdim {return !(__x == __y);} 345227825Stheraven 346227825Stheravenprivate: 347262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 348227825Stheraven _LIBCPP_INLINE_VISIBILITY 349262801Sdim __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 350262801Sdim : __node_(__node) 351262801Sdim { 352262801Sdim __get_db()->__insert_ic(this, __c); 353262801Sdim } 354262801Sdim#else 355262801Sdim _LIBCPP_INLINE_VISIBILITY 356227825Stheraven __hash_const_iterator(__node_pointer __node) _NOEXCEPT 357227825Stheraven : __node_(__node) 358227825Stheraven {} 359262801Sdim#endif 360227825Stheraven 361227825Stheraven template <class, class, class, class> friend class __hash_table; 362262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 363262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 364262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 365227825Stheraven}; 366227825Stheraven 367262801Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 368227825Stheraven 369227825Stheraventemplate <class _NodePtr> 370262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 371227825Stheraven{ 372227825Stheraven typedef _NodePtr __node_pointer; 373227825Stheraven 374227825Stheraven __node_pointer __node_; 375227825Stheraven size_t __bucket_; 376227825Stheraven size_t __bucket_count_; 377227825Stheraven 378227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 379227825Stheravenpublic: 380227825Stheraven typedef forward_iterator_tag iterator_category; 381227825Stheraven typedef typename __pointer_traits::element_type::value_type value_type; 382227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 383227825Stheraven typedef value_type& reference; 384227825Stheraven typedef typename __pointer_traits::template 385227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 386227825Stheraven rebind<value_type> 387227825Stheraven#else 388227825Stheraven rebind<value_type>::other 389227825Stheraven#endif 390227825Stheraven pointer; 391227825Stheraven 392262801Sdim _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 393262801Sdim { 394262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 395262801Sdim __get_db()->__insert_i(this); 396262801Sdim#endif 397262801Sdim } 398227825Stheraven 399262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 400262801Sdim 401227825Stheraven _LIBCPP_INLINE_VISIBILITY 402262801Sdim __hash_local_iterator(const __hash_local_iterator& __i) 403262801Sdim : __node_(__i.__node_), 404262801Sdim __bucket_(__i.__bucket_), 405262801Sdim __bucket_count_(__i.__bucket_count_) 406262801Sdim { 407262801Sdim __get_db()->__iterator_copy(this, &__i); 408262801Sdim } 409262801Sdim 410227825Stheraven _LIBCPP_INLINE_VISIBILITY 411262801Sdim ~__hash_local_iterator() 412262801Sdim { 413262801Sdim __get_db()->__erase_i(this); 414262801Sdim } 415227825Stheraven 416227825Stheraven _LIBCPP_INLINE_VISIBILITY 417262801Sdim __hash_local_iterator& operator=(const __hash_local_iterator& __i) 418262801Sdim { 419262801Sdim if (this != &__i) 420262801Sdim { 421262801Sdim __get_db()->__iterator_copy(this, &__i); 422262801Sdim __node_ = __i.__node_; 423262801Sdim __bucket_ = __i.__bucket_; 424262801Sdim __bucket_count_ = __i.__bucket_count_; 425262801Sdim } 426262801Sdim return *this; 427262801Sdim } 428262801Sdim 429262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 430262801Sdim 431262801Sdim _LIBCPP_INLINE_VISIBILITY 432262801Sdim reference operator*() const 433262801Sdim { 434262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 435262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 436262801Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 437262801Sdim#endif 438262801Sdim return __node_->__value_; 439262801Sdim } 440262801Sdim _LIBCPP_INLINE_VISIBILITY 441262801Sdim pointer operator->() const 442262801Sdim { 443262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 444262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 445262801Sdim "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 446262801Sdim#endif 447262801Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 448262801Sdim } 449262801Sdim 450262801Sdim _LIBCPP_INLINE_VISIBILITY 451227825Stheraven __hash_local_iterator& operator++() 452227825Stheraven { 453262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 454262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 455262801Sdim "Attempted to increment non-incrementable unordered container local_iterator"); 456262801Sdim#endif 457227825Stheraven __node_ = __node_->__next_; 458243376Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 459227825Stheraven __node_ = nullptr; 460227825Stheraven return *this; 461227825Stheraven } 462227825Stheraven 463227825Stheraven _LIBCPP_INLINE_VISIBILITY 464227825Stheraven __hash_local_iterator operator++(int) 465227825Stheraven { 466227825Stheraven __hash_local_iterator __t(*this); 467227825Stheraven ++(*this); 468227825Stheraven return __t; 469227825Stheraven } 470227825Stheraven 471227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 472227825Stheraven bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 473262801Sdim { 474262801Sdim return __x.__node_ == __y.__node_; 475262801Sdim } 476227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 477227825Stheraven bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 478262801Sdim {return !(__x == __y);} 479227825Stheraven 480227825Stheravenprivate: 481262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 482227825Stheraven _LIBCPP_INLINE_VISIBILITY 483227825Stheraven __hash_local_iterator(__node_pointer __node, size_t __bucket, 484262801Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 485262801Sdim : __node_(__node), 486262801Sdim __bucket_(__bucket), 487262801Sdim __bucket_count_(__bucket_count) 488262801Sdim { 489262801Sdim __get_db()->__insert_ic(this, __c); 490262801Sdim if (__node_ != nullptr) 491262801Sdim __node_ = __node_->__next_; 492262801Sdim } 493262801Sdim#else 494262801Sdim _LIBCPP_INLINE_VISIBILITY 495262801Sdim __hash_local_iterator(__node_pointer __node, size_t __bucket, 496227825Stheraven size_t __bucket_count) _NOEXCEPT 497227825Stheraven : __node_(__node), 498227825Stheraven __bucket_(__bucket), 499227825Stheraven __bucket_count_(__bucket_count) 500227825Stheraven { 501227825Stheraven if (__node_ != nullptr) 502227825Stheraven __node_ = __node_->__next_; 503227825Stheraven } 504262801Sdim#endif 505227825Stheraven template <class, class, class, class> friend class __hash_table; 506262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 507262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 508227825Stheraven}; 509227825Stheraven 510227825Stheraventemplate <class _ConstNodePtr> 511262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 512227825Stheraven{ 513227825Stheraven typedef _ConstNodePtr __node_pointer; 514227825Stheraven 515227825Stheraven __node_pointer __node_; 516227825Stheraven size_t __bucket_; 517227825Stheraven size_t __bucket_count_; 518227825Stheraven 519227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 520227825Stheraven typedef typename __pointer_traits::element_type __node; 521227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 522227825Stheraven typedef typename pointer_traits<__node_pointer>::template 523227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 524227825Stheraven rebind<__non_const_node> 525227825Stheraven#else 526227825Stheraven rebind<__non_const_node>::other 527227825Stheraven#endif 528227825Stheraven __non_const_node_pointer; 529227825Stheraven typedef __hash_local_iterator<__non_const_node_pointer> 530227825Stheraven __non_const_iterator; 531227825Stheravenpublic: 532227825Stheraven typedef forward_iterator_tag iterator_category; 533227825Stheraven typedef typename remove_const< 534227825Stheraven typename __pointer_traits::element_type::value_type 535227825Stheraven >::type value_type; 536227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 537227825Stheraven typedef const value_type& reference; 538227825Stheraven typedef typename __pointer_traits::template 539227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 540227825Stheraven rebind<const value_type> 541227825Stheraven#else 542227825Stheraven rebind<const value_type>::other 543227825Stheraven#endif 544227825Stheraven pointer; 545227825Stheraven 546262801Sdim _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 547262801Sdim { 548262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 549262801Sdim __get_db()->__insert_i(this); 550262801Sdim#endif 551262801Sdim } 552262801Sdim 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 555227825Stheraven : __node_(__x.__node_), 556227825Stheraven __bucket_(__x.__bucket_), 557227825Stheraven __bucket_count_(__x.__bucket_count_) 558262801Sdim { 559262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 560262801Sdim __get_db()->__iterator_copy(this, &__x); 561262801Sdim#endif 562262801Sdim } 563227825Stheraven 564262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 565262801Sdim 566227825Stheraven _LIBCPP_INLINE_VISIBILITY 567262801Sdim __hash_const_local_iterator(const __hash_const_local_iterator& __i) 568262801Sdim : __node_(__i.__node_), 569262801Sdim __bucket_(__i.__bucket_), 570262801Sdim __bucket_count_(__i.__bucket_count_) 571262801Sdim { 572262801Sdim __get_db()->__iterator_copy(this, &__i); 573262801Sdim } 574262801Sdim 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576262801Sdim ~__hash_const_local_iterator() 577262801Sdim { 578262801Sdim __get_db()->__erase_i(this); 579262801Sdim } 580227825Stheraven 581227825Stheraven _LIBCPP_INLINE_VISIBILITY 582262801Sdim __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 583262801Sdim { 584262801Sdim if (this != &__i) 585262801Sdim { 586262801Sdim __get_db()->__iterator_copy(this, &__i); 587262801Sdim __node_ = __i.__node_; 588262801Sdim __bucket_ = __i.__bucket_; 589262801Sdim __bucket_count_ = __i.__bucket_count_; 590262801Sdim } 591262801Sdim return *this; 592262801Sdim } 593262801Sdim 594262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 595262801Sdim 596262801Sdim _LIBCPP_INLINE_VISIBILITY 597262801Sdim reference operator*() const 598262801Sdim { 599262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 600262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 601262801Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 602262801Sdim#endif 603262801Sdim return __node_->__value_; 604262801Sdim } 605262801Sdim _LIBCPP_INLINE_VISIBILITY 606262801Sdim pointer operator->() const 607262801Sdim { 608262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 609262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 610262801Sdim "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 611262801Sdim#endif 612262801Sdim return pointer_traits<pointer>::pointer_to(__node_->__value_); 613262801Sdim } 614262801Sdim 615262801Sdim _LIBCPP_INLINE_VISIBILITY 616227825Stheraven __hash_const_local_iterator& operator++() 617227825Stheraven { 618262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 619262801Sdim _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 620262801Sdim "Attempted to increment non-incrementable unordered container const_local_iterator"); 621262801Sdim#endif 622227825Stheraven __node_ = __node_->__next_; 623243376Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 624227825Stheraven __node_ = nullptr; 625227825Stheraven return *this; 626227825Stheraven } 627227825Stheraven 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven __hash_const_local_iterator operator++(int) 630227825Stheraven { 631227825Stheraven __hash_const_local_iterator __t(*this); 632227825Stheraven ++(*this); 633227825Stheraven return __t; 634227825Stheraven } 635227825Stheraven 636227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 637227825Stheraven bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 638262801Sdim { 639262801Sdim return __x.__node_ == __y.__node_; 640262801Sdim } 641227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 642227825Stheraven bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 643262801Sdim {return !(__x == __y);} 644227825Stheraven 645227825Stheravenprivate: 646262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 647227825Stheraven _LIBCPP_INLINE_VISIBILITY 648227825Stheraven __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 649262801Sdim size_t __bucket_count, const void* __c) _NOEXCEPT 650262801Sdim : __node_(__node), 651262801Sdim __bucket_(__bucket), 652262801Sdim __bucket_count_(__bucket_count) 653262801Sdim { 654262801Sdim __get_db()->__insert_ic(this, __c); 655262801Sdim if (__node_ != nullptr) 656262801Sdim __node_ = __node_->__next_; 657262801Sdim } 658262801Sdim#else 659262801Sdim _LIBCPP_INLINE_VISIBILITY 660262801Sdim __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 661227825Stheraven size_t __bucket_count) _NOEXCEPT 662227825Stheraven : __node_(__node), 663227825Stheraven __bucket_(__bucket), 664227825Stheraven __bucket_count_(__bucket_count) 665227825Stheraven { 666227825Stheraven if (__node_ != nullptr) 667227825Stheraven __node_ = __node_->__next_; 668227825Stheraven } 669262801Sdim#endif 670227825Stheraven template <class, class, class, class> friend class __hash_table; 671262801Sdim template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 672227825Stheraven}; 673227825Stheraven 674227825Stheraventemplate <class _Alloc> 675227825Stheravenclass __bucket_list_deallocator 676227825Stheraven{ 677227825Stheraven typedef _Alloc allocator_type; 678227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 679227825Stheraven typedef typename __alloc_traits::size_type size_type; 680227825Stheraven 681227825Stheraven __compressed_pair<size_type, allocator_type> __data_; 682227825Stheravenpublic: 683227825Stheraven typedef typename __alloc_traits::pointer pointer; 684227825Stheraven 685227825Stheraven _LIBCPP_INLINE_VISIBILITY 686227825Stheraven __bucket_list_deallocator() 687227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 688227825Stheraven : __data_(0) {} 689227825Stheraven 690227825Stheraven _LIBCPP_INLINE_VISIBILITY 691227825Stheraven __bucket_list_deallocator(const allocator_type& __a, size_type __size) 692227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 693227825Stheraven : __data_(__size, __a) {} 694227825Stheraven 695227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 696227825Stheraven 697227825Stheraven _LIBCPP_INLINE_VISIBILITY 698227825Stheraven __bucket_list_deallocator(__bucket_list_deallocator&& __x) 699227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 700227825Stheraven : __data_(_VSTD::move(__x.__data_)) 701227825Stheraven { 702227825Stheraven __x.size() = 0; 703227825Stheraven } 704227825Stheraven 705227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 706227825Stheraven 707227825Stheraven _LIBCPP_INLINE_VISIBILITY 708227825Stheraven size_type& size() _NOEXCEPT {return __data_.first();} 709227825Stheraven _LIBCPP_INLINE_VISIBILITY 710227825Stheraven size_type size() const _NOEXCEPT {return __data_.first();} 711227825Stheraven 712227825Stheraven _LIBCPP_INLINE_VISIBILITY 713227825Stheraven allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 714227825Stheraven _LIBCPP_INLINE_VISIBILITY 715227825Stheraven const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 716227825Stheraven 717227825Stheraven _LIBCPP_INLINE_VISIBILITY 718227825Stheraven void operator()(pointer __p) _NOEXCEPT 719227825Stheraven { 720227825Stheraven __alloc_traits::deallocate(__alloc(), __p, size()); 721227825Stheraven } 722227825Stheraven}; 723227825Stheraven 724227825Stheraventemplate <class _Alloc> class __hash_map_node_destructor; 725227825Stheraven 726227825Stheraventemplate <class _Alloc> 727227825Stheravenclass __hash_node_destructor 728227825Stheraven{ 729227825Stheraven typedef _Alloc allocator_type; 730227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 731227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 732227825Stheravenpublic: 733227825Stheraven typedef typename __alloc_traits::pointer pointer; 734227825Stheravenprivate: 735227825Stheraven 736227825Stheraven allocator_type& __na_; 737227825Stheraven 738227825Stheraven __hash_node_destructor& operator=(const __hash_node_destructor&); 739227825Stheraven 740227825Stheravenpublic: 741227825Stheraven bool __value_constructed; 742227825Stheraven 743227825Stheraven _LIBCPP_INLINE_VISIBILITY 744227825Stheraven explicit __hash_node_destructor(allocator_type& __na, 745227825Stheraven bool __constructed = false) _NOEXCEPT 746227825Stheraven : __na_(__na), 747227825Stheraven __value_constructed(__constructed) 748227825Stheraven {} 749227825Stheraven 750227825Stheraven _LIBCPP_INLINE_VISIBILITY 751227825Stheraven void operator()(pointer __p) _NOEXCEPT 752227825Stheraven { 753227825Stheraven if (__value_constructed) 754227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 755227825Stheraven if (__p) 756227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 757227825Stheraven } 758227825Stheraven 759227825Stheraven template <class> friend class __hash_map_node_destructor; 760227825Stheraven}; 761227825Stheraven 762227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 763227825Stheravenclass __hash_table 764227825Stheraven{ 765227825Stheravenpublic: 766227825Stheraven typedef _Tp value_type; 767227825Stheraven typedef _Hash hasher; 768227825Stheraven typedef _Equal key_equal; 769227825Stheraven typedef _Alloc allocator_type; 770227825Stheraven 771227825Stheravenprivate: 772227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 773227825Stheravenpublic: 774227825Stheraven typedef value_type& reference; 775227825Stheraven typedef const value_type& const_reference; 776227825Stheraven typedef typename __alloc_traits::pointer pointer; 777227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 778227825Stheraven typedef typename __alloc_traits::size_type size_type; 779227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 780227825Stheravenpublic: 781227825Stheraven // Create __node 782227825Stheraven typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 783227825Stheraven typedef typename __alloc_traits::template 784227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 785227825Stheraven rebind_alloc<__node> 786227825Stheraven#else 787227825Stheraven rebind_alloc<__node>::other 788227825Stheraven#endif 789227825Stheraven __node_allocator; 790227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 791227825Stheraven typedef typename __node_traits::pointer __node_pointer; 792253222Sdim typedef typename __node_traits::pointer __node_const_pointer; 793232950Stheraven typedef __hash_node_base<__node_pointer> __first_node; 794253222Sdim typedef typename pointer_traits<__node_pointer>::template 795253222Sdim#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 796253222Sdim rebind<__first_node> 797253222Sdim#else 798253222Sdim rebind<__first_node>::other 799253222Sdim#endif 800253222Sdim __node_base_pointer; 801227825Stheraven 802227825Stheravenprivate: 803227825Stheraven 804227825Stheraven typedef typename __node_traits::template 805227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 806227825Stheraven rebind_alloc<__node_pointer> 807227825Stheraven#else 808227825Stheraven rebind_alloc<__node_pointer>::other 809227825Stheraven#endif 810227825Stheraven __pointer_allocator; 811227825Stheraven typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 812227825Stheraven typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 813227825Stheraven typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 814227825Stheraven typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 815227825Stheraven 816227825Stheraven // --- Member data begin --- 817227825Stheraven __bucket_list __bucket_list_; 818227825Stheraven __compressed_pair<__first_node, __node_allocator> __p1_; 819227825Stheraven __compressed_pair<size_type, hasher> __p2_; 820227825Stheraven __compressed_pair<float, key_equal> __p3_; 821227825Stheraven // --- Member data end --- 822227825Stheraven 823227825Stheraven _LIBCPP_INLINE_VISIBILITY 824227825Stheraven size_type& size() _NOEXCEPT {return __p2_.first();} 825227825Stheravenpublic: 826227825Stheraven _LIBCPP_INLINE_VISIBILITY 827227825Stheraven size_type size() const _NOEXCEPT {return __p2_.first();} 828227825Stheraven 829227825Stheraven _LIBCPP_INLINE_VISIBILITY 830227825Stheraven hasher& hash_function() _NOEXCEPT {return __p2_.second();} 831227825Stheraven _LIBCPP_INLINE_VISIBILITY 832227825Stheraven const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 833227825Stheraven 834227825Stheraven _LIBCPP_INLINE_VISIBILITY 835227825Stheraven float& max_load_factor() _NOEXCEPT {return __p3_.first();} 836227825Stheraven _LIBCPP_INLINE_VISIBILITY 837227825Stheraven float max_load_factor() const _NOEXCEPT {return __p3_.first();} 838227825Stheraven 839227825Stheraven _LIBCPP_INLINE_VISIBILITY 840227825Stheraven key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 841227825Stheraven _LIBCPP_INLINE_VISIBILITY 842227825Stheraven const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 843227825Stheraven 844227825Stheraven _LIBCPP_INLINE_VISIBILITY 845227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 846227825Stheraven _LIBCPP_INLINE_VISIBILITY 847227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 848227825Stheraven {return __p1_.second();} 849227825Stheraven 850227825Stheravenpublic: 851227825Stheraven typedef __hash_iterator<__node_pointer> iterator; 852253222Sdim typedef __hash_const_iterator<__node_pointer> const_iterator; 853227825Stheraven typedef __hash_local_iterator<__node_pointer> local_iterator; 854253222Sdim typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 855227825Stheraven 856227825Stheraven __hash_table() 857227825Stheraven _NOEXCEPT_( 858227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 859227825Stheraven is_nothrow_default_constructible<__first_node>::value && 860227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 861227825Stheraven is_nothrow_default_constructible<hasher>::value && 862227825Stheraven is_nothrow_default_constructible<key_equal>::value); 863227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql); 864227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql, 865227825Stheraven const allocator_type& __a); 866227825Stheraven explicit __hash_table(const allocator_type& __a); 867227825Stheraven __hash_table(const __hash_table& __u); 868227825Stheraven __hash_table(const __hash_table& __u, const allocator_type& __a); 869227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 870227825Stheraven __hash_table(__hash_table&& __u) 871227825Stheraven _NOEXCEPT_( 872227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 873227825Stheraven is_nothrow_move_constructible<__first_node>::value && 874227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 875227825Stheraven is_nothrow_move_constructible<hasher>::value && 876227825Stheraven is_nothrow_move_constructible<key_equal>::value); 877227825Stheraven __hash_table(__hash_table&& __u, const allocator_type& __a); 878227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 879227825Stheraven ~__hash_table(); 880227825Stheraven 881227825Stheraven __hash_table& operator=(const __hash_table& __u); 882227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 883227825Stheraven __hash_table& operator=(__hash_table&& __u) 884227825Stheraven _NOEXCEPT_( 885227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 886227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 887227825Stheraven is_nothrow_move_assignable<hasher>::value && 888227825Stheraven is_nothrow_move_assignable<key_equal>::value); 889227825Stheraven#endif 890227825Stheraven template <class _InputIterator> 891227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 892227825Stheraven template <class _InputIterator> 893227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 894227825Stheraven 895227825Stheraven _LIBCPP_INLINE_VISIBILITY 896227825Stheraven size_type max_size() const _NOEXCEPT 897227825Stheraven { 898227825Stheraven return allocator_traits<__pointer_allocator>::max_size( 899227825Stheraven __bucket_list_.get_deleter().__alloc()); 900227825Stheraven } 901227825Stheraven 902227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 903227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 904227825Stheraven iterator __node_insert_multi(const_iterator __p, 905227825Stheraven __node_pointer __nd); 906227825Stheraven 907227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 908227825Stheraven template <class... _Args> 909227825Stheraven pair<iterator, bool> __emplace_unique(_Args&&... __args); 910227825Stheraven template <class... _Args> 911227825Stheraven iterator __emplace_multi(_Args&&... __args); 912227825Stheraven template <class... _Args> 913227825Stheraven iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 914227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 915227825Stheraven 916227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __x); 917227825Stheraven 918227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 919232950Stheraven template <class _Pp> 920232950Stheraven pair<iterator, bool> __insert_unique(_Pp&& __x); 921227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 922227825Stheraven 923227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 924232950Stheraven template <class _Pp> 925232950Stheraven iterator __insert_multi(_Pp&& __x); 926232950Stheraven template <class _Pp> 927232950Stheraven iterator __insert_multi(const_iterator __p, _Pp&& __x); 928227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 929227825Stheraven iterator __insert_multi(const value_type& __x); 930227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __x); 931227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 932227825Stheraven 933227825Stheraven void clear() _NOEXCEPT; 934227825Stheraven void rehash(size_type __n); 935227825Stheraven _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 936227825Stheraven {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 937227825Stheraven 938227825Stheraven _LIBCPP_INLINE_VISIBILITY 939227825Stheraven size_type bucket_count() const _NOEXCEPT 940227825Stheraven { 941227825Stheraven return __bucket_list_.get_deleter().size(); 942227825Stheraven } 943227825Stheraven 944227825Stheraven iterator begin() _NOEXCEPT; 945227825Stheraven iterator end() _NOEXCEPT; 946227825Stheraven const_iterator begin() const _NOEXCEPT; 947227825Stheraven const_iterator end() const _NOEXCEPT; 948227825Stheraven 949227825Stheraven template <class _Key> 950227825Stheraven _LIBCPP_INLINE_VISIBILITY 951227825Stheraven size_type bucket(const _Key& __k) const 952262801Sdim { 953262801Sdim _LIBCPP_ASSERT(bucket_count() > 0, 954262801Sdim "unordered container::bucket(key) called when bucket_count() == 0"); 955262801Sdim return __constrain_hash(hash_function()(__k), bucket_count()); 956262801Sdim } 957227825Stheraven 958227825Stheraven template <class _Key> 959227825Stheraven iterator find(const _Key& __x); 960227825Stheraven template <class _Key> 961227825Stheraven const_iterator find(const _Key& __x) const; 962227825Stheraven 963232950Stheraven typedef __hash_node_destructor<__node_allocator> _Dp; 964232950Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 965227825Stheraven 966227825Stheraven iterator erase(const_iterator __p); 967227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 968227825Stheraven template <class _Key> 969227825Stheraven size_type __erase_unique(const _Key& __k); 970227825Stheraven template <class _Key> 971227825Stheraven size_type __erase_multi(const _Key& __k); 972227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 973227825Stheraven 974227825Stheraven template <class _Key> 975227825Stheraven size_type __count_unique(const _Key& __k) const; 976227825Stheraven template <class _Key> 977227825Stheraven size_type __count_multi(const _Key& __k) const; 978227825Stheraven 979227825Stheraven template <class _Key> 980227825Stheraven pair<iterator, iterator> 981227825Stheraven __equal_range_unique(const _Key& __k); 982227825Stheraven template <class _Key> 983227825Stheraven pair<const_iterator, const_iterator> 984227825Stheraven __equal_range_unique(const _Key& __k) const; 985227825Stheraven 986227825Stheraven template <class _Key> 987227825Stheraven pair<iterator, iterator> 988227825Stheraven __equal_range_multi(const _Key& __k); 989227825Stheraven template <class _Key> 990227825Stheraven pair<const_iterator, const_iterator> 991227825Stheraven __equal_range_multi(const _Key& __k) const; 992227825Stheraven 993227825Stheraven void swap(__hash_table& __u) 994227825Stheraven _NOEXCEPT_( 995227825Stheraven (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 996227825Stheraven __is_nothrow_swappable<__pointer_allocator>::value) && 997227825Stheraven (!__node_traits::propagate_on_container_swap::value || 998227825Stheraven __is_nothrow_swappable<__node_allocator>::value) && 999227825Stheraven __is_nothrow_swappable<hasher>::value && 1000227825Stheraven __is_nothrow_swappable<key_equal>::value); 1001227825Stheraven 1002227825Stheraven _LIBCPP_INLINE_VISIBILITY 1003227825Stheraven size_type max_bucket_count() const _NOEXCEPT 1004253222Sdim {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1005227825Stheraven size_type bucket_size(size_type __n) const; 1006227825Stheraven _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1007227825Stheraven { 1008227825Stheraven size_type __bc = bucket_count(); 1009227825Stheraven return __bc != 0 ? (float)size() / __bc : 0.f; 1010227825Stheraven } 1011227825Stheraven _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1012262801Sdim { 1013262801Sdim _LIBCPP_ASSERT(__mlf > 0, 1014262801Sdim "unordered container::max_load_factor(lf) called with lf <= 0"); 1015262801Sdim max_load_factor() = _VSTD::max(__mlf, load_factor()); 1016262801Sdim } 1017227825Stheraven 1018262801Sdim _LIBCPP_INLINE_VISIBILITY 1019262801Sdim local_iterator 1020262801Sdim begin(size_type __n) 1021262801Sdim { 1022262801Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1023262801Sdim "unordered container::begin(n) called with n >= bucket_count()"); 1024262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1025262801Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1026262801Sdim#else 1027262801Sdim return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1028262801Sdim#endif 1029262801Sdim } 1030262801Sdim 1031262801Sdim _LIBCPP_INLINE_VISIBILITY 1032262801Sdim local_iterator 1033262801Sdim end(size_type __n) 1034262801Sdim { 1035262801Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1036262801Sdim "unordered container::end(n) called with n >= bucket_count()"); 1037262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1038262801Sdim return local_iterator(nullptr, __n, bucket_count(), this); 1039262801Sdim#else 1040262801Sdim return local_iterator(nullptr, __n, bucket_count()); 1041262801Sdim#endif 1042262801Sdim } 1043262801Sdim 1044262801Sdim _LIBCPP_INLINE_VISIBILITY 1045262801Sdim const_local_iterator 1046262801Sdim cbegin(size_type __n) const 1047262801Sdim { 1048262801Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1049262801Sdim "unordered container::cbegin(n) called with n >= bucket_count()"); 1050262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1051262801Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1052262801Sdim#else 1053262801Sdim return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1054262801Sdim#endif 1055262801Sdim } 1056262801Sdim 1057262801Sdim _LIBCPP_INLINE_VISIBILITY 1058262801Sdim const_local_iterator 1059262801Sdim cend(size_type __n) const 1060262801Sdim { 1061262801Sdim _LIBCPP_ASSERT(__n < bucket_count(), 1062262801Sdim "unordered container::cend(n) called with n >= bucket_count()"); 1063262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1064262801Sdim return const_local_iterator(nullptr, __n, bucket_count(), this); 1065262801Sdim#else 1066262801Sdim return const_local_iterator(nullptr, __n, bucket_count()); 1067262801Sdim#endif 1068262801Sdim } 1069262801Sdim 1070262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1071262801Sdim 1072262801Sdim bool __dereferenceable(const const_iterator* __i) const; 1073262801Sdim bool __decrementable(const const_iterator* __i) const; 1074262801Sdim bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1075262801Sdim bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1076262801Sdim 1077262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1078262801Sdim 1079227825Stheravenprivate: 1080227825Stheraven void __rehash(size_type __n); 1081227825Stheraven 1082227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1083227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1084227825Stheraven template <class ..._Args> 1085227825Stheraven __node_holder __construct_node(_Args&& ...__args); 1086227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1087227825Stheraven __node_holder __construct_node(value_type&& __v, size_t __hash); 1088227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1089227825Stheraven __node_holder __construct_node(const value_type& __v); 1090227825Stheraven#endif 1091227825Stheraven __node_holder __construct_node(const value_type& __v, size_t __hash); 1092227825Stheraven 1093227825Stheraven _LIBCPP_INLINE_VISIBILITY 1094227825Stheraven void __copy_assign_alloc(const __hash_table& __u) 1095227825Stheraven {__copy_assign_alloc(__u, integral_constant<bool, 1096227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 1097227825Stheraven void __copy_assign_alloc(const __hash_table& __u, true_type); 1098227825Stheraven _LIBCPP_INLINE_VISIBILITY 1099232950Stheraven void __copy_assign_alloc(const __hash_table&, false_type) {} 1100227825Stheraven 1101227825Stheraven void __move_assign(__hash_table& __u, false_type); 1102227825Stheraven void __move_assign(__hash_table& __u, true_type) 1103227825Stheraven _NOEXCEPT_( 1104227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1105227825Stheraven is_nothrow_move_assignable<hasher>::value && 1106227825Stheraven is_nothrow_move_assignable<key_equal>::value); 1107227825Stheraven _LIBCPP_INLINE_VISIBILITY 1108227825Stheraven void __move_assign_alloc(__hash_table& __u) 1109227825Stheraven _NOEXCEPT_( 1110227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 1111227825Stheraven (is_nothrow_move_assignable<__pointer_allocator>::value && 1112227825Stheraven is_nothrow_move_assignable<__node_allocator>::value)) 1113227825Stheraven {__move_assign_alloc(__u, integral_constant<bool, 1114227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 1115227825Stheraven _LIBCPP_INLINE_VISIBILITY 1116227825Stheraven void __move_assign_alloc(__hash_table& __u, true_type) 1117227825Stheraven _NOEXCEPT_( 1118227825Stheraven is_nothrow_move_assignable<__pointer_allocator>::value && 1119227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 1120227825Stheraven { 1121227825Stheraven __bucket_list_.get_deleter().__alloc() = 1122227825Stheraven _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1123227825Stheraven __node_alloc() = _VSTD::move(__u.__node_alloc()); 1124227825Stheraven } 1125227825Stheraven _LIBCPP_INLINE_VISIBILITY 1126227825Stheraven void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1127227825Stheraven 1128232950Stheraven template <class _Ap> 1129227825Stheraven _LIBCPP_INLINE_VISIBILITY 1130227825Stheraven static 1131227825Stheraven void 1132232950Stheraven __swap_alloc(_Ap& __x, _Ap& __y) 1133227825Stheraven _NOEXCEPT_( 1134232950Stheraven !allocator_traits<_Ap>::propagate_on_container_swap::value || 1135232950Stheraven __is_nothrow_swappable<_Ap>::value) 1136227825Stheraven { 1137227825Stheraven __swap_alloc(__x, __y, 1138227825Stheraven integral_constant<bool, 1139232950Stheraven allocator_traits<_Ap>::propagate_on_container_swap::value 1140227825Stheraven >()); 1141227825Stheraven } 1142227825Stheraven 1143232950Stheraven template <class _Ap> 1144227825Stheraven _LIBCPP_INLINE_VISIBILITY 1145227825Stheraven static 1146227825Stheraven void 1147232950Stheraven __swap_alloc(_Ap& __x, _Ap& __y, true_type) 1148232950Stheraven _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 1149227825Stheraven { 1150227825Stheraven using _VSTD::swap; 1151227825Stheraven swap(__x, __y); 1152227825Stheraven } 1153227825Stheraven 1154232950Stheraven template <class _Ap> 1155227825Stheraven _LIBCPP_INLINE_VISIBILITY 1156227825Stheraven static 1157227825Stheraven void 1158232950Stheraven __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 1159227825Stheraven 1160227825Stheraven void __deallocate(__node_pointer __np) _NOEXCEPT; 1161227825Stheraven __node_pointer __detach() _NOEXCEPT; 1162253222Sdim 1163262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1164262801Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1165227825Stheraven}; 1166227825Stheraven 1167227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1168227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1169227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1170227825Stheraven _NOEXCEPT_( 1171227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 1172227825Stheraven is_nothrow_default_constructible<__first_node>::value && 1173227825Stheraven is_nothrow_default_constructible<hasher>::value && 1174227825Stheraven is_nothrow_default_constructible<key_equal>::value) 1175227825Stheraven : __p2_(0), 1176227825Stheraven __p3_(1.0f) 1177227825Stheraven{ 1178227825Stheraven} 1179227825Stheraven 1180227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1181227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1182227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1183227825Stheraven const key_equal& __eql) 1184227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter()), 1185227825Stheraven __p1_(), 1186227825Stheraven __p2_(0, __hf), 1187227825Stheraven __p3_(1.0f, __eql) 1188227825Stheraven{ 1189227825Stheraven} 1190227825Stheraven 1191227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1192227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1193227825Stheraven const key_equal& __eql, 1194227825Stheraven const allocator_type& __a) 1195227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1196227825Stheraven __p1_(__node_allocator(__a)), 1197227825Stheraven __p2_(0, __hf), 1198227825Stheraven __p3_(1.0f, __eql) 1199227825Stheraven{ 1200227825Stheraven} 1201227825Stheraven 1202227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1203227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1204227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1205227825Stheraven __p1_(__node_allocator(__a)), 1206227825Stheraven __p2_(0), 1207227825Stheraven __p3_(1.0f) 1208227825Stheraven{ 1209227825Stheraven} 1210227825Stheraven 1211227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1212227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1213227825Stheraven : __bucket_list_(nullptr, 1214227825Stheraven __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1215227825Stheraven select_on_container_copy_construction( 1216227825Stheraven __u.__bucket_list_.get_deleter().__alloc()), 0)), 1217227825Stheraven __p1_(allocator_traits<__node_allocator>:: 1218227825Stheraven select_on_container_copy_construction(__u.__node_alloc())), 1219227825Stheraven __p2_(0, __u.hash_function()), 1220227825Stheraven __p3_(__u.__p3_) 1221227825Stheraven{ 1222227825Stheraven} 1223227825Stheraven 1224227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1225227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1226227825Stheraven const allocator_type& __a) 1227227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1228227825Stheraven __p1_(__node_allocator(__a)), 1229227825Stheraven __p2_(0, __u.hash_function()), 1230227825Stheraven __p3_(__u.__p3_) 1231227825Stheraven{ 1232227825Stheraven} 1233227825Stheraven 1234227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1235227825Stheraven 1236227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1237227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1238227825Stheraven _NOEXCEPT_( 1239227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 1240227825Stheraven is_nothrow_move_constructible<__first_node>::value && 1241227825Stheraven is_nothrow_move_constructible<hasher>::value && 1242227825Stheraven is_nothrow_move_constructible<key_equal>::value) 1243227825Stheraven : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1244227825Stheraven __p1_(_VSTD::move(__u.__p1_)), 1245227825Stheraven __p2_(_VSTD::move(__u.__p2_)), 1246227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1247227825Stheraven{ 1248227825Stheraven if (size() > 0) 1249227825Stheraven { 1250243376Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1251253222Sdim static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1252227825Stheraven __u.__p1_.first().__next_ = nullptr; 1253227825Stheraven __u.size() = 0; 1254227825Stheraven } 1255227825Stheraven} 1256227825Stheraven 1257227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1258227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1259227825Stheraven const allocator_type& __a) 1260227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1261227825Stheraven __p1_(__node_allocator(__a)), 1262227825Stheraven __p2_(0, _VSTD::move(__u.hash_function())), 1263227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 1264227825Stheraven{ 1265227825Stheraven if (__a == allocator_type(__u.__node_alloc())) 1266227825Stheraven { 1267227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1268227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1269227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1270227825Stheraven if (__u.size() > 0) 1271227825Stheraven { 1272227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1273227825Stheraven __u.__p1_.first().__next_ = nullptr; 1274243376Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1275253222Sdim static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1276227825Stheraven size() = __u.size(); 1277227825Stheraven __u.size() = 0; 1278227825Stheraven } 1279227825Stheraven } 1280227825Stheraven} 1281227825Stheraven 1282227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1283227825Stheraven 1284227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1285227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1286227825Stheraven{ 1287227825Stheraven __deallocate(__p1_.first().__next_); 1288262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1289262801Sdim __get_db()->__erase_c(this); 1290262801Sdim#endif 1291227825Stheraven} 1292227825Stheraven 1293227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1294227825Stheravenvoid 1295227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1296227825Stheraven const __hash_table& __u, true_type) 1297227825Stheraven{ 1298227825Stheraven if (__node_alloc() != __u.__node_alloc()) 1299227825Stheraven { 1300227825Stheraven clear(); 1301227825Stheraven __bucket_list_.reset(); 1302227825Stheraven __bucket_list_.get_deleter().size() = 0; 1303227825Stheraven } 1304227825Stheraven __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1305227825Stheraven __node_alloc() = __u.__node_alloc(); 1306227825Stheraven} 1307227825Stheraven 1308227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1309227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1310227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1311227825Stheraven{ 1312227825Stheraven if (this != &__u) 1313227825Stheraven { 1314227825Stheraven __copy_assign_alloc(__u); 1315227825Stheraven hash_function() = __u.hash_function(); 1316227825Stheraven key_eq() = __u.key_eq(); 1317227825Stheraven max_load_factor() = __u.max_load_factor(); 1318227825Stheraven __assign_multi(__u.begin(), __u.end()); 1319227825Stheraven } 1320227825Stheraven return *this; 1321227825Stheraven} 1322227825Stheraven 1323227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1324227825Stheravenvoid 1325227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1326227825Stheraven _NOEXCEPT 1327227825Stheraven{ 1328227825Stheraven __node_allocator& __na = __node_alloc(); 1329227825Stheraven while (__np != nullptr) 1330227825Stheraven { 1331227825Stheraven __node_pointer __next = __np->__next_; 1332262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1333262801Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 1334262801Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1335262801Sdim { 1336262801Sdim --__p; 1337262801Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 1338262801Sdim if (__i->__node_ == __np) 1339262801Sdim { 1340262801Sdim (*__p)->__c_ = nullptr; 1341262801Sdim if (--__c->end_ != __p) 1342262801Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1343262801Sdim } 1344262801Sdim } 1345262801Sdim __get_db()->unlock(); 1346262801Sdim#endif 1347227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1348227825Stheraven __node_traits::deallocate(__na, __np, 1); 1349227825Stheraven __np = __next; 1350227825Stheraven } 1351227825Stheraven} 1352227825Stheraven 1353227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1354227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1355227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1356227825Stheraven{ 1357227825Stheraven size_type __bc = bucket_count(); 1358227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1359227825Stheraven __bucket_list_[__i] = nullptr; 1360227825Stheraven size() = 0; 1361227825Stheraven __node_pointer __cache = __p1_.first().__next_; 1362227825Stheraven __p1_.first().__next_ = nullptr; 1363227825Stheraven return __cache; 1364227825Stheraven} 1365227825Stheraven 1366227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1367227825Stheraven 1368227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1369227825Stheravenvoid 1370227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1371227825Stheraven __hash_table& __u, true_type) 1372227825Stheraven _NOEXCEPT_( 1373227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1374227825Stheraven is_nothrow_move_assignable<hasher>::value && 1375227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1376227825Stheraven{ 1377227825Stheraven clear(); 1378227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1379227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1380227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1381227825Stheraven __move_assign_alloc(__u); 1382227825Stheraven size() = __u.size(); 1383227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1384227825Stheraven max_load_factor() = __u.max_load_factor(); 1385227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1386227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1387227825Stheraven if (size() > 0) 1388227825Stheraven { 1389243376Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1390253222Sdim static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1391227825Stheraven __u.__p1_.first().__next_ = nullptr; 1392227825Stheraven __u.size() = 0; 1393227825Stheraven } 1394262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1395262801Sdim __get_db()->swap(this, &__u); 1396262801Sdim#endif 1397227825Stheraven} 1398227825Stheraven 1399227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1400227825Stheravenvoid 1401227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1402227825Stheraven __hash_table& __u, false_type) 1403227825Stheraven{ 1404227825Stheraven if (__node_alloc() == __u.__node_alloc()) 1405227825Stheraven __move_assign(__u, true_type()); 1406227825Stheraven else 1407227825Stheraven { 1408227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1409227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1410227825Stheraven max_load_factor() = __u.max_load_factor(); 1411227825Stheraven if (bucket_count() != 0) 1412227825Stheraven { 1413227825Stheraven __node_pointer __cache = __detach(); 1414227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1415227825Stheraven try 1416227825Stheraven { 1417227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1418227825Stheraven const_iterator __i = __u.begin(); 1419227825Stheraven while (__cache != nullptr && __u.size() != 0) 1420227825Stheraven { 1421227825Stheraven __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1422227825Stheraven __node_pointer __next = __cache->__next_; 1423227825Stheraven __node_insert_multi(__cache); 1424227825Stheraven __cache = __next; 1425227825Stheraven } 1426227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1427227825Stheraven } 1428227825Stheraven catch (...) 1429227825Stheraven { 1430227825Stheraven __deallocate(__cache); 1431227825Stheraven throw; 1432227825Stheraven } 1433227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1434227825Stheraven __deallocate(__cache); 1435227825Stheraven } 1436227825Stheraven const_iterator __i = __u.begin(); 1437227825Stheraven while (__u.size() != 0) 1438227825Stheraven { 1439227825Stheraven __node_holder __h = 1440227825Stheraven __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1441227825Stheraven __node_insert_multi(__h.get()); 1442227825Stheraven __h.release(); 1443227825Stheraven } 1444227825Stheraven } 1445227825Stheraven} 1446227825Stheraven 1447227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1448227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1449227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1450227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1451227825Stheraven _NOEXCEPT_( 1452227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1453227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1454227825Stheraven is_nothrow_move_assignable<hasher>::value && 1455227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1456227825Stheraven{ 1457227825Stheraven __move_assign(__u, integral_constant<bool, 1458227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1459227825Stheraven return *this; 1460227825Stheraven} 1461227825Stheraven 1462227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1463227825Stheraven 1464227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1465227825Stheraventemplate <class _InputIterator> 1466227825Stheravenvoid 1467227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1468227825Stheraven _InputIterator __last) 1469227825Stheraven{ 1470227825Stheraven if (bucket_count() != 0) 1471227825Stheraven { 1472227825Stheraven __node_pointer __cache = __detach(); 1473227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1474227825Stheraven try 1475227825Stheraven { 1476227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1477227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1478227825Stheraven { 1479227825Stheraven __cache->__value_ = *__first; 1480227825Stheraven __node_pointer __next = __cache->__next_; 1481227825Stheraven __node_insert_unique(__cache); 1482227825Stheraven __cache = __next; 1483227825Stheraven } 1484227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1485227825Stheraven } 1486227825Stheraven catch (...) 1487227825Stheraven { 1488227825Stheraven __deallocate(__cache); 1489227825Stheraven throw; 1490227825Stheraven } 1491227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1492227825Stheraven __deallocate(__cache); 1493227825Stheraven } 1494227825Stheraven for (; __first != __last; ++__first) 1495227825Stheraven __insert_unique(*__first); 1496227825Stheraven} 1497227825Stheraven 1498227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1499227825Stheraventemplate <class _InputIterator> 1500227825Stheravenvoid 1501227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1502227825Stheraven _InputIterator __last) 1503227825Stheraven{ 1504227825Stheraven if (bucket_count() != 0) 1505227825Stheraven { 1506227825Stheraven __node_pointer __cache = __detach(); 1507227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1508227825Stheraven try 1509227825Stheraven { 1510227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1511227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1512227825Stheraven { 1513227825Stheraven __cache->__value_ = *__first; 1514227825Stheraven __node_pointer __next = __cache->__next_; 1515227825Stheraven __node_insert_multi(__cache); 1516227825Stheraven __cache = __next; 1517227825Stheraven } 1518227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1519227825Stheraven } 1520227825Stheraven catch (...) 1521227825Stheraven { 1522227825Stheraven __deallocate(__cache); 1523227825Stheraven throw; 1524227825Stheraven } 1525227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1526227825Stheraven __deallocate(__cache); 1527227825Stheraven } 1528227825Stheraven for (; __first != __last; ++__first) 1529227825Stheraven __insert_multi(*__first); 1530227825Stheraven} 1531227825Stheraven 1532227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1533227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1534227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1535227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1536227825Stheraven{ 1537262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1538262801Sdim return iterator(__p1_.first().__next_, this); 1539262801Sdim#else 1540227825Stheraven return iterator(__p1_.first().__next_); 1541262801Sdim#endif 1542227825Stheraven} 1543227825Stheraven 1544227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1545227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1546227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1547227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1548227825Stheraven{ 1549262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1550262801Sdim return iterator(nullptr, this); 1551262801Sdim#else 1552227825Stheraven return iterator(nullptr); 1553262801Sdim#endif 1554227825Stheraven} 1555227825Stheraven 1556227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1557227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1558227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1559227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1560227825Stheraven{ 1561262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1562262801Sdim return const_iterator(__p1_.first().__next_, this); 1563262801Sdim#else 1564227825Stheraven return const_iterator(__p1_.first().__next_); 1565262801Sdim#endif 1566227825Stheraven} 1567227825Stheraven 1568227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1569227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1570227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1571227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1572227825Stheraven{ 1573262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1574262801Sdim return const_iterator(nullptr, this); 1575262801Sdim#else 1576227825Stheraven return const_iterator(nullptr); 1577262801Sdim#endif 1578227825Stheraven} 1579227825Stheraven 1580227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1581227825Stheravenvoid 1582227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1583227825Stheraven{ 1584227825Stheraven if (size() > 0) 1585227825Stheraven { 1586227825Stheraven __deallocate(__p1_.first().__next_); 1587227825Stheraven __p1_.first().__next_ = nullptr; 1588227825Stheraven size_type __bc = bucket_count(); 1589227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1590227825Stheraven __bucket_list_[__i] = nullptr; 1591227825Stheraven size() = 0; 1592227825Stheraven } 1593227825Stheraven} 1594227825Stheraven 1595227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1596227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1597227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1598227825Stheraven{ 1599227825Stheraven __nd->__hash_ = hash_function()(__nd->__value_); 1600227825Stheraven size_type __bc = bucket_count(); 1601227825Stheraven bool __inserted = false; 1602227825Stheraven __node_pointer __ndptr; 1603227825Stheraven size_t __chash; 1604227825Stheraven if (__bc != 0) 1605227825Stheraven { 1606243376Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1607227825Stheraven __ndptr = __bucket_list_[__chash]; 1608227825Stheraven if (__ndptr != nullptr) 1609227825Stheraven { 1610227825Stheraven for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1611243376Sdim __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1612227825Stheraven __ndptr = __ndptr->__next_) 1613227825Stheraven { 1614227825Stheraven if (key_eq()(__ndptr->__value_, __nd->__value_)) 1615227825Stheraven goto __done; 1616227825Stheraven } 1617227825Stheraven } 1618227825Stheraven } 1619227825Stheraven { 1620227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1621227825Stheraven { 1622243376Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1623227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1624227825Stheraven __bc = bucket_count(); 1625243376Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1626227825Stheraven } 1627227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1628227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1629227825Stheraven if (__pn == nullptr) 1630227825Stheraven { 1631253222Sdim __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1632227825Stheraven __nd->__next_ = __pn->__next_; 1633227825Stheraven __pn->__next_ = __nd; 1634227825Stheraven // fix up __bucket_list_ 1635227825Stheraven __bucket_list_[__chash] = __pn; 1636227825Stheraven if (__nd->__next_ != nullptr) 1637243376Sdim __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1638227825Stheraven } 1639227825Stheraven else 1640227825Stheraven { 1641227825Stheraven __nd->__next_ = __pn->__next_; 1642227825Stheraven __pn->__next_ = __nd; 1643227825Stheraven } 1644227825Stheraven __ndptr = __nd; 1645227825Stheraven // increment size 1646227825Stheraven ++size(); 1647227825Stheraven __inserted = true; 1648227825Stheraven } 1649227825Stheraven__done: 1650262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1651262801Sdim return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1652262801Sdim#else 1653227825Stheraven return pair<iterator, bool>(iterator(__ndptr), __inserted); 1654262801Sdim#endif 1655227825Stheraven} 1656227825Stheraven 1657227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1658227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1659227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1660227825Stheraven{ 1661227825Stheraven __cp->__hash_ = hash_function()(__cp->__value_); 1662227825Stheraven size_type __bc = bucket_count(); 1663227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1664227825Stheraven { 1665243376Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1666227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1667227825Stheraven __bc = bucket_count(); 1668227825Stheraven } 1669243376Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1670227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1671227825Stheraven if (__pn == nullptr) 1672227825Stheraven { 1673253222Sdim __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1674227825Stheraven __cp->__next_ = __pn->__next_; 1675227825Stheraven __pn->__next_ = __cp; 1676227825Stheraven // fix up __bucket_list_ 1677227825Stheraven __bucket_list_[__chash] = __pn; 1678227825Stheraven if (__cp->__next_ != nullptr) 1679243376Sdim __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1680227825Stheraven } 1681227825Stheraven else 1682227825Stheraven { 1683227825Stheraven for (bool __found = false; __pn->__next_ != nullptr && 1684243376Sdim __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1685227825Stheraven __pn = __pn->__next_) 1686227825Stheraven { 1687227825Stheraven // __found key_eq() action 1688227825Stheraven // false false loop 1689227825Stheraven // true true loop 1690227825Stheraven // false true set __found to true 1691227825Stheraven // true false break 1692227825Stheraven if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1693227825Stheraven key_eq()(__pn->__next_->__value_, __cp->__value_))) 1694227825Stheraven { 1695227825Stheraven if (!__found) 1696227825Stheraven __found = true; 1697227825Stheraven else 1698227825Stheraven break; 1699227825Stheraven } 1700227825Stheraven } 1701227825Stheraven __cp->__next_ = __pn->__next_; 1702227825Stheraven __pn->__next_ = __cp; 1703227825Stheraven if (__cp->__next_ != nullptr) 1704227825Stheraven { 1705243376Sdim size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1706227825Stheraven if (__nhash != __chash) 1707227825Stheraven __bucket_list_[__nhash] = __cp; 1708227825Stheraven } 1709227825Stheraven } 1710227825Stheraven ++size(); 1711262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1712262801Sdim return iterator(__cp, this); 1713262801Sdim#else 1714227825Stheraven return iterator(__cp); 1715262801Sdim#endif 1716227825Stheraven} 1717227825Stheraven 1718227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1719227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1720227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1721227825Stheraven const_iterator __p, __node_pointer __cp) 1722227825Stheraven{ 1723262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1724262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1725262801Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1726262801Sdim " referring to this unordered container"); 1727262801Sdim#endif 1728227825Stheraven if (__p != end() && key_eq()(*__p, __cp->__value_)) 1729227825Stheraven { 1730253222Sdim __node_pointer __np = __p.__node_; 1731227825Stheraven __cp->__hash_ = __np->__hash_; 1732227825Stheraven size_type __bc = bucket_count(); 1733227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1734227825Stheraven { 1735243376Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1736227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1737227825Stheraven __bc = bucket_count(); 1738227825Stheraven } 1739243376Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1740227825Stheraven __node_pointer __pp = __bucket_list_[__chash]; 1741227825Stheraven while (__pp->__next_ != __np) 1742227825Stheraven __pp = __pp->__next_; 1743227825Stheraven __cp->__next_ = __np; 1744227825Stheraven __pp->__next_ = __cp; 1745227825Stheraven ++size(); 1746262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1747262801Sdim return iterator(__cp, this); 1748262801Sdim#else 1749227825Stheraven return iterator(__cp); 1750262801Sdim#endif 1751227825Stheraven } 1752227825Stheraven return __node_insert_multi(__cp); 1753227825Stheraven} 1754227825Stheraven 1755227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1756227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1757227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1758227825Stheraven{ 1759227825Stheraven size_t __hash = hash_function()(__x); 1760227825Stheraven size_type __bc = bucket_count(); 1761227825Stheraven bool __inserted = false; 1762227825Stheraven __node_pointer __nd; 1763227825Stheraven size_t __chash; 1764227825Stheraven if (__bc != 0) 1765227825Stheraven { 1766243376Sdim __chash = __constrain_hash(__hash, __bc); 1767227825Stheraven __nd = __bucket_list_[__chash]; 1768227825Stheraven if (__nd != nullptr) 1769227825Stheraven { 1770227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1771243376Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1772227825Stheraven __nd = __nd->__next_) 1773227825Stheraven { 1774227825Stheraven if (key_eq()(__nd->__value_, __x)) 1775227825Stheraven goto __done; 1776227825Stheraven } 1777227825Stheraven } 1778227825Stheraven } 1779227825Stheraven { 1780227825Stheraven __node_holder __h = __construct_node(__x, __hash); 1781227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1782227825Stheraven { 1783243376Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1784227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1785227825Stheraven __bc = bucket_count(); 1786243376Sdim __chash = __constrain_hash(__hash, __bc); 1787227825Stheraven } 1788227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1789227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1790227825Stheraven if (__pn == nullptr) 1791227825Stheraven { 1792253222Sdim __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1793227825Stheraven __h->__next_ = __pn->__next_; 1794227825Stheraven __pn->__next_ = __h.get(); 1795227825Stheraven // fix up __bucket_list_ 1796227825Stheraven __bucket_list_[__chash] = __pn; 1797227825Stheraven if (__h->__next_ != nullptr) 1798243376Sdim __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1799227825Stheraven } 1800227825Stheraven else 1801227825Stheraven { 1802227825Stheraven __h->__next_ = __pn->__next_; 1803227825Stheraven __pn->__next_ = __h.get(); 1804227825Stheraven } 1805227825Stheraven __nd = __h.release(); 1806227825Stheraven // increment size 1807227825Stheraven ++size(); 1808227825Stheraven __inserted = true; 1809227825Stheraven } 1810227825Stheraven__done: 1811262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1812262801Sdim return pair<iterator, bool>(iterator(__nd, this), __inserted); 1813262801Sdim#else 1814227825Stheraven return pair<iterator, bool>(iterator(__nd), __inserted); 1815262801Sdim#endif 1816227825Stheraven} 1817227825Stheraven 1818227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1819227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1820227825Stheraven 1821227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1822227825Stheraventemplate <class... _Args> 1823227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1824227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1825227825Stheraven{ 1826227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1827227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1828227825Stheraven if (__r.second) 1829227825Stheraven __h.release(); 1830227825Stheraven return __r; 1831227825Stheraven} 1832227825Stheraven 1833227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1834227825Stheraventemplate <class... _Args> 1835227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1836227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1837227825Stheraven{ 1838227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1839227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1840227825Stheraven __h.release(); 1841227825Stheraven return __r; 1842227825Stheraven} 1843227825Stheraven 1844227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1845227825Stheraventemplate <class... _Args> 1846227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1847227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1848227825Stheraven const_iterator __p, _Args&&... __args) 1849227825Stheraven{ 1850262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1851262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1852262801Sdim "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1853262801Sdim " referring to this unordered container"); 1854262801Sdim#endif 1855227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1856227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1857227825Stheraven __h.release(); 1858227825Stheraven return __r; 1859227825Stheraven} 1860227825Stheraven 1861227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1862227825Stheraven 1863227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1864232950Stheraventemplate <class _Pp> 1865227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1866232950Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1867227825Stheraven{ 1868232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1869227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1870227825Stheraven if (__r.second) 1871227825Stheraven __h.release(); 1872227825Stheraven return __r; 1873227825Stheraven} 1874227825Stheraven 1875227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1876227825Stheraven 1877227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1878227825Stheraven 1879227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1880232950Stheraventemplate <class _Pp> 1881227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1882232950Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1883227825Stheraven{ 1884232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1885227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1886227825Stheraven __h.release(); 1887227825Stheraven return __r; 1888227825Stheraven} 1889227825Stheraven 1890227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1891232950Stheraventemplate <class _Pp> 1892227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1893227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1894232950Stheraven _Pp&& __x) 1895227825Stheraven{ 1896262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1897262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1898262801Sdim "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1899262801Sdim " referring to this unordered container"); 1900262801Sdim#endif 1901232950Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1902227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1903227825Stheraven __h.release(); 1904227825Stheraven return __r; 1905227825Stheraven} 1906227825Stheraven 1907227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1908227825Stheraven 1909227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1910227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1911227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1912227825Stheraven{ 1913227825Stheraven __node_holder __h = __construct_node(__x); 1914227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1915227825Stheraven __h.release(); 1916227825Stheraven return __r; 1917227825Stheraven} 1918227825Stheraven 1919227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1920227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1921227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1922227825Stheraven const value_type& __x) 1923227825Stheraven{ 1924262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1925262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1926262801Sdim "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1927262801Sdim " referring to this unordered container"); 1928262801Sdim#endif 1929227825Stheraven __node_holder __h = __construct_node(__x); 1930227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1931227825Stheraven __h.release(); 1932227825Stheraven return __r; 1933227825Stheraven} 1934227825Stheraven 1935227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1936227825Stheraven 1937227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1938227825Stheravenvoid 1939227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1940227825Stheraven{ 1941243376Sdim if (__n == 1) 1942243376Sdim __n = 2; 1943243376Sdim else if (__n & (__n - 1)) 1944243376Sdim __n = __next_prime(__n); 1945227825Stheraven size_type __bc = bucket_count(); 1946227825Stheraven if (__n > __bc) 1947227825Stheraven __rehash(__n); 1948243376Sdim else if (__n < __bc) 1949227825Stheraven { 1950227825Stheraven __n = _VSTD::max<size_type> 1951227825Stheraven ( 1952227825Stheraven __n, 1953243376Sdim __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1954243376Sdim __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1955227825Stheraven ); 1956227825Stheraven if (__n < __bc) 1957227825Stheraven __rehash(__n); 1958227825Stheraven } 1959227825Stheraven} 1960227825Stheraven 1961227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1962227825Stheravenvoid 1963227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1964227825Stheraven{ 1965262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1966262801Sdim __get_db()->__invalidate_all(this); 1967262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 1968227825Stheraven __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1969227825Stheraven __bucket_list_.reset(__nbc > 0 ? 1970227825Stheraven __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1971227825Stheraven __bucket_list_.get_deleter().size() = __nbc; 1972227825Stheraven if (__nbc > 0) 1973227825Stheraven { 1974227825Stheraven for (size_type __i = 0; __i < __nbc; ++__i) 1975227825Stheraven __bucket_list_[__i] = nullptr; 1976253222Sdim __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1977227825Stheraven __node_pointer __cp = __pp->__next_; 1978227825Stheraven if (__cp != nullptr) 1979227825Stheraven { 1980243376Sdim size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1981227825Stheraven __bucket_list_[__chash] = __pp; 1982227825Stheraven size_type __phash = __chash; 1983227825Stheraven for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1984227825Stheraven __cp = __pp->__next_) 1985227825Stheraven { 1986243376Sdim __chash = __constrain_hash(__cp->__hash_, __nbc); 1987227825Stheraven if (__chash == __phash) 1988227825Stheraven __pp = __cp; 1989227825Stheraven else 1990227825Stheraven { 1991227825Stheraven if (__bucket_list_[__chash] == nullptr) 1992227825Stheraven { 1993227825Stheraven __bucket_list_[__chash] = __pp; 1994227825Stheraven __pp = __cp; 1995227825Stheraven __phash = __chash; 1996227825Stheraven } 1997227825Stheraven else 1998227825Stheraven { 1999227825Stheraven __node_pointer __np = __cp; 2000227825Stheraven for (; __np->__next_ != nullptr && 2001227825Stheraven key_eq()(__cp->__value_, __np->__next_->__value_); 2002227825Stheraven __np = __np->__next_) 2003227825Stheraven ; 2004227825Stheraven __pp->__next_ = __np->__next_; 2005227825Stheraven __np->__next_ = __bucket_list_[__chash]->__next_; 2006227825Stheraven __bucket_list_[__chash]->__next_ = __cp; 2007227825Stheraven 2008227825Stheraven } 2009227825Stheraven } 2010227825Stheraven } 2011227825Stheraven } 2012227825Stheraven } 2013227825Stheraven} 2014227825Stheraven 2015227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2016227825Stheraventemplate <class _Key> 2017227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2018227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2019227825Stheraven{ 2020227825Stheraven size_t __hash = hash_function()(__k); 2021227825Stheraven size_type __bc = bucket_count(); 2022227825Stheraven if (__bc != 0) 2023227825Stheraven { 2024243376Sdim size_t __chash = __constrain_hash(__hash, __bc); 2025227825Stheraven __node_pointer __nd = __bucket_list_[__chash]; 2026227825Stheraven if (__nd != nullptr) 2027227825Stheraven { 2028227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2029243376Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2030227825Stheraven __nd = __nd->__next_) 2031227825Stheraven { 2032227825Stheraven if (key_eq()(__nd->__value_, __k)) 2033262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2034262801Sdim return iterator(__nd, this); 2035262801Sdim#else 2036227825Stheraven return iterator(__nd); 2037262801Sdim#endif 2038227825Stheraven } 2039227825Stheraven } 2040227825Stheraven } 2041227825Stheraven return end(); 2042227825Stheraven} 2043227825Stheraven 2044227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2045227825Stheraventemplate <class _Key> 2046227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2047227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2048227825Stheraven{ 2049227825Stheraven size_t __hash = hash_function()(__k); 2050227825Stheraven size_type __bc = bucket_count(); 2051227825Stheraven if (__bc != 0) 2052227825Stheraven { 2053243376Sdim size_t __chash = __constrain_hash(__hash, __bc); 2054227825Stheraven __node_const_pointer __nd = __bucket_list_[__chash]; 2055227825Stheraven if (__nd != nullptr) 2056227825Stheraven { 2057227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 2058243376Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 2059227825Stheraven __nd = __nd->__next_) 2060227825Stheraven { 2061227825Stheraven if (key_eq()(__nd->__value_, __k)) 2062262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2063262801Sdim return const_iterator(__nd, this); 2064262801Sdim#else 2065227825Stheraven return const_iterator(__nd); 2066262801Sdim#endif 2067227825Stheraven } 2068227825Stheraven } 2069227825Stheraven 2070227825Stheraven } 2071227825Stheraven return end(); 2072227825Stheraven} 2073227825Stheraven 2074227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2075227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 2076227825Stheraven 2077227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2078227825Stheraventemplate <class ..._Args> 2079227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2080227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2081227825Stheraven{ 2082227825Stheraven __node_allocator& __na = __node_alloc(); 2083232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2084227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2085227825Stheraven __h.get_deleter().__value_constructed = true; 2086227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2087227825Stheraven __h->__next_ = nullptr; 2088227825Stheraven return __h; 2089227825Stheraven} 2090227825Stheraven 2091227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2092227825Stheraven 2093227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2094227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2095227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2096227825Stheraven size_t __hash) 2097227825Stheraven{ 2098227825Stheraven __node_allocator& __na = __node_alloc(); 2099232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2100227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2101227825Stheraven __h.get_deleter().__value_constructed = true; 2102227825Stheraven __h->__hash_ = __hash; 2103227825Stheraven __h->__next_ = nullptr; 2104262801Sdim return __h; 2105227825Stheraven} 2106227825Stheraven 2107227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2108227825Stheraven 2109227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2110227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2111227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2112227825Stheraven{ 2113227825Stheraven __node_allocator& __na = __node_alloc(); 2114232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2115227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2116227825Stheraven __h.get_deleter().__value_constructed = true; 2117227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 2118227825Stheraven __h->__next_ = nullptr; 2119262801Sdim return _VSTD::move(__h); // explicitly moved for C++03 2120227825Stheraven} 2121227825Stheraven 2122227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2123227825Stheraven 2124227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2125227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2126227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2127227825Stheraven size_t __hash) 2128227825Stheraven{ 2129227825Stheraven __node_allocator& __na = __node_alloc(); 2130232950Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2131227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2132227825Stheraven __h.get_deleter().__value_constructed = true; 2133227825Stheraven __h->__hash_ = __hash; 2134227825Stheraven __h->__next_ = nullptr; 2135262801Sdim return _VSTD::move(__h); // explicitly moved for C++03 2136227825Stheraven} 2137227825Stheraven 2138227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2139227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2140227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2141227825Stheraven{ 2142253222Sdim __node_pointer __np = __p.__node_; 2143262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2144262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2145262801Sdim "unordered container erase(iterator) called with an iterator not" 2146262801Sdim " referring to this container"); 2147262801Sdim _LIBCPP_ASSERT(__p != end(), 2148262801Sdim "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2149262801Sdim iterator __r(__np, this); 2150262801Sdim#else 2151227825Stheraven iterator __r(__np); 2152262801Sdim#endif 2153227825Stheraven ++__r; 2154227825Stheraven remove(__p); 2155227825Stheraven return __r; 2156227825Stheraven} 2157227825Stheraven 2158227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2159227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2160227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2161227825Stheraven const_iterator __last) 2162227825Stheraven{ 2163262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2164262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2165262801Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2166262801Sdim " referring to this unodered container"); 2167262801Sdim _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2168262801Sdim "unodered container::erase(iterator, iterator) called with an iterator not" 2169262801Sdim " referring to this unodered container"); 2170262801Sdim#endif 2171227825Stheraven for (const_iterator __p = __first; __first != __last; __p = __first) 2172227825Stheraven { 2173227825Stheraven ++__first; 2174227825Stheraven erase(__p); 2175227825Stheraven } 2176253222Sdim __node_pointer __np = __last.__node_; 2177262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2178262801Sdim return iterator (__np, this); 2179262801Sdim#else 2180227825Stheraven return iterator (__np); 2181262801Sdim#endif 2182227825Stheraven} 2183227825Stheraven 2184227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2185227825Stheraventemplate <class _Key> 2186227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2187227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2188227825Stheraven{ 2189227825Stheraven iterator __i = find(__k); 2190227825Stheraven if (__i == end()) 2191227825Stheraven return 0; 2192227825Stheraven erase(__i); 2193227825Stheraven return 1; 2194227825Stheraven} 2195227825Stheraven 2196227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2197227825Stheraventemplate <class _Key> 2198227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2199227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2200227825Stheraven{ 2201227825Stheraven size_type __r = 0; 2202227825Stheraven iterator __i = find(__k); 2203227825Stheraven if (__i != end()) 2204227825Stheraven { 2205227825Stheraven iterator __e = end(); 2206227825Stheraven do 2207227825Stheraven { 2208227825Stheraven erase(__i++); 2209227825Stheraven ++__r; 2210227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2211227825Stheraven } 2212227825Stheraven return __r; 2213227825Stheraven} 2214227825Stheraven 2215227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2216227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2217227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2218227825Stheraven{ 2219227825Stheraven // current node 2220253222Sdim __node_pointer __cn = __p.__node_; 2221227825Stheraven size_type __bc = bucket_count(); 2222243376Sdim size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2223227825Stheraven // find previous node 2224227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 2225227825Stheraven for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2226227825Stheraven ; 2227227825Stheraven // Fix up __bucket_list_ 2228227825Stheraven // if __pn is not in same bucket (before begin is not in same bucket) && 2229227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2230253222Sdim if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2231253222Sdim || __constrain_hash(__pn->__hash_, __bc) != __chash) 2232227825Stheraven { 2233243376Sdim if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2234227825Stheraven __bucket_list_[__chash] = nullptr; 2235227825Stheraven } 2236227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2237227825Stheraven if (__cn->__next_ != nullptr) 2238227825Stheraven { 2239243376Sdim size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2240227825Stheraven if (__nhash != __chash) 2241227825Stheraven __bucket_list_[__nhash] = __pn; 2242227825Stheraven } 2243227825Stheraven // remove __cn 2244227825Stheraven __pn->__next_ = __cn->__next_; 2245227825Stheraven __cn->__next_ = nullptr; 2246227825Stheraven --size(); 2247262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2248262801Sdim __c_node* __c = __get_db()->__find_c_and_lock(this); 2249262801Sdim for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2250262801Sdim { 2251262801Sdim --__p; 2252262801Sdim iterator* __i = static_cast<iterator*>((*__p)->__i_); 2253262801Sdim if (__i->__node_ == __cn) 2254262801Sdim { 2255262801Sdim (*__p)->__c_ = nullptr; 2256262801Sdim if (--__c->end_ != __p) 2257262801Sdim memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2258262801Sdim } 2259262801Sdim } 2260262801Sdim __get_db()->unlock(); 2261262801Sdim#endif 2262232950Stheraven return __node_holder(__cn, _Dp(__node_alloc(), true)); 2263227825Stheraven} 2264227825Stheraven 2265227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2266227825Stheraventemplate <class _Key> 2267227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2268227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2269227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2270227825Stheraven{ 2271227825Stheraven return static_cast<size_type>(find(__k) != end()); 2272227825Stheraven} 2273227825Stheraven 2274227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2275227825Stheraventemplate <class _Key> 2276227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2277227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2278227825Stheraven{ 2279227825Stheraven size_type __r = 0; 2280227825Stheraven const_iterator __i = find(__k); 2281227825Stheraven if (__i != end()) 2282227825Stheraven { 2283227825Stheraven const_iterator __e = end(); 2284227825Stheraven do 2285227825Stheraven { 2286227825Stheraven ++__i; 2287227825Stheraven ++__r; 2288227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 2289227825Stheraven } 2290227825Stheraven return __r; 2291227825Stheraven} 2292227825Stheraven 2293227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2294227825Stheraventemplate <class _Key> 2295227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2296227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2297227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2298227825Stheraven const _Key& __k) 2299227825Stheraven{ 2300227825Stheraven iterator __i = find(__k); 2301227825Stheraven iterator __j = __i; 2302227825Stheraven if (__i != end()) 2303227825Stheraven ++__j; 2304227825Stheraven return pair<iterator, iterator>(__i, __j); 2305227825Stheraven} 2306227825Stheraven 2307227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2308227825Stheraventemplate <class _Key> 2309227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2310227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2311227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2312227825Stheraven const _Key& __k) const 2313227825Stheraven{ 2314227825Stheraven const_iterator __i = find(__k); 2315227825Stheraven const_iterator __j = __i; 2316227825Stheraven if (__i != end()) 2317227825Stheraven ++__j; 2318227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2319227825Stheraven} 2320227825Stheraven 2321227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2322227825Stheraventemplate <class _Key> 2323227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2324227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2325227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2326227825Stheraven const _Key& __k) 2327227825Stheraven{ 2328227825Stheraven iterator __i = find(__k); 2329227825Stheraven iterator __j = __i; 2330227825Stheraven if (__i != end()) 2331227825Stheraven { 2332227825Stheraven iterator __e = end(); 2333227825Stheraven do 2334227825Stheraven { 2335227825Stheraven ++__j; 2336227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2337227825Stheraven } 2338227825Stheraven return pair<iterator, iterator>(__i, __j); 2339227825Stheraven} 2340227825Stheraven 2341227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2342227825Stheraventemplate <class _Key> 2343227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2344227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2345227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2346227825Stheraven const _Key& __k) const 2347227825Stheraven{ 2348227825Stheraven const_iterator __i = find(__k); 2349227825Stheraven const_iterator __j = __i; 2350227825Stheraven if (__i != end()) 2351227825Stheraven { 2352227825Stheraven const_iterator __e = end(); 2353227825Stheraven do 2354227825Stheraven { 2355227825Stheraven ++__j; 2356227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 2357227825Stheraven } 2358227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 2359227825Stheraven} 2360227825Stheraven 2361227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2362227825Stheravenvoid 2363227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2364227825Stheraven _NOEXCEPT_( 2365227825Stheraven (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 2366227825Stheraven __is_nothrow_swappable<__pointer_allocator>::value) && 2367227825Stheraven (!__node_traits::propagate_on_container_swap::value || 2368227825Stheraven __is_nothrow_swappable<__node_allocator>::value) && 2369227825Stheraven __is_nothrow_swappable<hasher>::value && 2370227825Stheraven __is_nothrow_swappable<key_equal>::value) 2371227825Stheraven{ 2372227825Stheraven { 2373227825Stheraven __node_pointer_pointer __npp = __bucket_list_.release(); 2374227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 2375227825Stheraven __u.__bucket_list_.reset(__npp); 2376227825Stheraven } 2377227825Stheraven _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2378227825Stheraven __swap_alloc(__bucket_list_.get_deleter().__alloc(), 2379227825Stheraven __u.__bucket_list_.get_deleter().__alloc()); 2380227825Stheraven __swap_alloc(__node_alloc(), __u.__node_alloc()); 2381227825Stheraven _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2382227825Stheraven __p2_.swap(__u.__p2_); 2383227825Stheraven __p3_.swap(__u.__p3_); 2384227825Stheraven if (size() > 0) 2385243376Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2386253222Sdim static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2387227825Stheraven if (__u.size() > 0) 2388243376Sdim __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2389253222Sdim static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2390262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2391262801Sdim __get_db()->swap(this, &__u); 2392262801Sdim#endif 2393227825Stheraven} 2394227825Stheraven 2395227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2396227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2397227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2398227825Stheraven{ 2399262801Sdim _LIBCPP_ASSERT(__n < bucket_count(), 2400262801Sdim "unordered container::bucket_size(n) called with n >= bucket_count()"); 2401227825Stheraven __node_const_pointer __np = __bucket_list_[__n]; 2402227825Stheraven size_type __bc = bucket_count(); 2403227825Stheraven size_type __r = 0; 2404227825Stheraven if (__np != nullptr) 2405227825Stheraven { 2406227825Stheraven for (__np = __np->__next_; __np != nullptr && 2407243376Sdim __constrain_hash(__np->__hash_, __bc) == __n; 2408227825Stheraven __np = __np->__next_, ++__r) 2409227825Stheraven ; 2410227825Stheraven } 2411227825Stheraven return __r; 2412227825Stheraven} 2413227825Stheraven 2414227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2415227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2416227825Stheravenvoid 2417227825Stheravenswap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2418227825Stheraven __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2419227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2420227825Stheraven{ 2421227825Stheraven __x.swap(__y); 2422227825Stheraven} 2423227825Stheraven 2424262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 2425262801Sdim 2426262801Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2427262801Sdimbool 2428262801Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2429262801Sdim{ 2430262801Sdim return __i->__node_ != nullptr; 2431262801Sdim} 2432262801Sdim 2433262801Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2434262801Sdimbool 2435262801Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2436262801Sdim{ 2437262801Sdim return false; 2438262801Sdim} 2439262801Sdim 2440262801Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2441262801Sdimbool 2442262801Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2443262801Sdim{ 2444262801Sdim return false; 2445262801Sdim} 2446262801Sdim 2447262801Sdimtemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 2448262801Sdimbool 2449262801Sdim__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2450262801Sdim{ 2451262801Sdim return false; 2452262801Sdim} 2453262801Sdim 2454262801Sdim#endif // _LIBCPP_DEBUG_LEVEL >= 2 2455227825Stheraven_LIBCPP_END_NAMESPACE_STD 2456227825Stheraven 2457227825Stheraven#endif // _LIBCPP__HASH_TABLE 2458