__hash_table revision 253146
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===----------------------------------------------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP__HASH_TABLE 12227825Stheraven#define _LIBCPP__HASH_TABLE 13227825Stheraven 14227825Stheraven#include <__config> 15227825Stheraven#include <initializer_list> 16227825Stheraven#include <memory> 17227825Stheraven#include <iterator> 18227825Stheraven#include <algorithm> 19227825Stheraven#include <cmath> 20227825Stheraven 21232924Stheraven#include <__undef_min_max> 22232924Stheraven 23227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 24227825Stheraven#pragma GCC system_header 25227825Stheraven#endif 26227825Stheraven 27227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 28227825Stheraven 29249989Sdim_LIBCPP_FUNC_VIS 30227825Stheravensize_t __next_prime(size_t __n); 31227825Stheraven 32227825Stheraventemplate <class _NodePtr> 33227825Stheravenstruct __hash_node_base 34227825Stheraven{ 35227825Stheraven typedef __hash_node_base __first_node; 36227825Stheraven 37227825Stheraven _NodePtr __next_; 38227825Stheraven 39227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 40227825Stheraven}; 41227825Stheraven 42227825Stheraventemplate <class _Tp, class _VoidPtr> 43227825Stheravenstruct __hash_node 44227825Stheraven : public __hash_node_base 45227825Stheraven < 46227825Stheraven typename pointer_traits<_VoidPtr>::template 47227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 48227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> > 49227825Stheraven#else 50227825Stheraven rebind<__hash_node<_Tp, _VoidPtr> >::other 51227825Stheraven#endif 52227825Stheraven > 53227825Stheraven{ 54227825Stheraven typedef _Tp value_type; 55227825Stheraven 56227825Stheraven size_t __hash_; 57227825Stheraven value_type __value_; 58227825Stheraven}; 59227825Stheraven 60241900Sdiminline _LIBCPP_INLINE_VISIBILITY 61241900Sdimbool 62241900Sdim__is_power2(size_t __bc) 63241900Sdim{ 64241900Sdim return __bc > 2 && !(__bc & (__bc - 1)); 65241900Sdim} 66241900Sdim 67241900Sdiminline _LIBCPP_INLINE_VISIBILITY 68241900Sdimsize_t 69241900Sdim__constrain_hash(size_t __h, size_t __bc) 70241900Sdim{ 71241900Sdim return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 72241900Sdim} 73241900Sdim 74241900Sdiminline _LIBCPP_INLINE_VISIBILITY 75241900Sdimsize_t 76241900Sdim__next_pow2(size_t __n) 77241900Sdim{ 78241900Sdim return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 79241900Sdim} 80241900Sdim 81227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 82249989Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_iterator; 83249989Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_iterator; 84249989Sdimtemplate <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 85227825Stheraventemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 86249989Sdim class _LIBCPP_TYPE_VIS unordered_map; 87227825Stheraven 88227825Stheraventemplate <class _NodePtr> 89249989Sdimclass _LIBCPP_TYPE_VIS __hash_iterator 90227825Stheraven{ 91227825Stheraven typedef _NodePtr __node_pointer; 92227825Stheraven 93227825Stheraven __node_pointer __node_; 94227825Stheraven 95227825Stheravenpublic: 96227825Stheraven typedef forward_iterator_tag iterator_category; 97227825Stheraven typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 98227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 99227825Stheraven typedef value_type& reference; 100227825Stheraven typedef typename pointer_traits<__node_pointer>::template 101227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 102227825Stheraven rebind<value_type> 103227825Stheraven#else 104227825Stheraven rebind<value_type>::other 105227825Stheraven#endif 106227825Stheraven pointer; 107227825Stheraven 108227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT {} 109227825Stheraven 110227825Stheraven _LIBCPP_INLINE_VISIBILITY 111227825Stheraven reference operator*() const {return __node_->__value_;} 112227825Stheraven _LIBCPP_INLINE_VISIBILITY 113253146Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);} 114227825Stheraven 115227825Stheraven _LIBCPP_INLINE_VISIBILITY 116227825Stheraven __hash_iterator& operator++() 117227825Stheraven { 118227825Stheraven __node_ = __node_->__next_; 119227825Stheraven return *this; 120227825Stheraven } 121227825Stheraven 122227825Stheraven _LIBCPP_INLINE_VISIBILITY 123227825Stheraven __hash_iterator operator++(int) 124227825Stheraven { 125227825Stheraven __hash_iterator __t(*this); 126227825Stheraven ++(*this); 127227825Stheraven return __t; 128227825Stheraven } 129227825Stheraven 130227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 131227825Stheraven bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 132227825Stheraven {return __x.__node_ == __y.__node_;} 133227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 134227825Stheraven bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 135227825Stheraven {return __x.__node_ != __y.__node_;} 136227825Stheraven 137227825Stheravenprivate: 138227825Stheraven _LIBCPP_INLINE_VISIBILITY 139227825Stheraven __hash_iterator(__node_pointer __node) _NOEXCEPT 140227825Stheraven : __node_(__node) 141227825Stheraven {} 142227825Stheraven 143227825Stheraven template <class, class, class, class> friend class __hash_table; 144249989Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator; 145249989Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator; 146249989Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 147249989Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 148227825Stheraven}; 149227825Stheraven 150227825Stheraventemplate <class _ConstNodePtr> 151249989Sdimclass _LIBCPP_TYPE_VIS __hash_const_iterator 152227825Stheraven{ 153227825Stheraven typedef _ConstNodePtr __node_pointer; 154227825Stheraven 155227825Stheraven __node_pointer __node_; 156227825Stheraven 157227825Stheraven typedef typename remove_const< 158227825Stheraven typename pointer_traits<__node_pointer>::element_type 159227825Stheraven >::type __node; 160227825Stheraven 161227825Stheravenpublic: 162227825Stheraven typedef forward_iterator_tag iterator_category; 163227825Stheraven typedef typename __node::value_type value_type; 164227825Stheraven typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 165227825Stheraven typedef const value_type& reference; 166227825Stheraven typedef typename pointer_traits<__node_pointer>::template 167227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 168227825Stheraven rebind<const value_type> 169227825Stheraven#else 170227825Stheraven rebind<const value_type>::other 171227825Stheraven#endif 172227825Stheraven pointer; 173227825Stheraven typedef typename pointer_traits<__node_pointer>::template 174227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 175227825Stheraven rebind<__node> 176227825Stheraven#else 177227825Stheraven rebind<__node>::other 178227825Stheraven#endif 179227825Stheraven __non_const_node_pointer; 180227825Stheraven typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 181227825Stheraven 182227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT {} 183227825Stheraven _LIBCPP_INLINE_VISIBILITY 184227825Stheraven __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 185227825Stheraven : __node_(__x.__node_) 186227825Stheraven {} 187227825Stheraven 188227825Stheraven _LIBCPP_INLINE_VISIBILITY 189227825Stheraven reference operator*() const {return __node_->__value_;} 190227825Stheraven _LIBCPP_INLINE_VISIBILITY 191253146Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);} 192227825Stheraven 193227825Stheraven _LIBCPP_INLINE_VISIBILITY 194227825Stheraven __hash_const_iterator& operator++() 195227825Stheraven { 196227825Stheraven __node_ = __node_->__next_; 197227825Stheraven return *this; 198227825Stheraven } 199227825Stheraven 200227825Stheraven _LIBCPP_INLINE_VISIBILITY 201227825Stheraven __hash_const_iterator operator++(int) 202227825Stheraven { 203227825Stheraven __hash_const_iterator __t(*this); 204227825Stheraven ++(*this); 205227825Stheraven return __t; 206227825Stheraven } 207227825Stheraven 208227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 209227825Stheraven bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 210227825Stheraven {return __x.__node_ == __y.__node_;} 211227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 212227825Stheraven bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 213227825Stheraven {return __x.__node_ != __y.__node_;} 214227825Stheraven 215227825Stheravenprivate: 216227825Stheraven _LIBCPP_INLINE_VISIBILITY 217227825Stheraven __hash_const_iterator(__node_pointer __node) _NOEXCEPT 218227825Stheraven : __node_(__node) 219227825Stheraven {} 220227825Stheraven 221227825Stheraven template <class, class, class, class> friend class __hash_table; 222249989Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 223249989Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 224249989Sdim template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 225227825Stheraven}; 226227825Stheraven 227249989Sdimtemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 228227825Stheraven 229227825Stheraventemplate <class _NodePtr> 230249989Sdimclass _LIBCPP_TYPE_VIS __hash_local_iterator 231227825Stheraven{ 232227825Stheraven typedef _NodePtr __node_pointer; 233227825Stheraven 234227825Stheraven __node_pointer __node_; 235227825Stheraven size_t __bucket_; 236227825Stheraven size_t __bucket_count_; 237227825Stheraven 238227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 239227825Stheravenpublic: 240227825Stheraven typedef forward_iterator_tag iterator_category; 241227825Stheraven typedef typename __pointer_traits::element_type::value_type value_type; 242227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 243227825Stheraven typedef value_type& reference; 244227825Stheraven typedef typename __pointer_traits::template 245227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 246227825Stheraven rebind<value_type> 247227825Stheraven#else 248227825Stheraven rebind<value_type>::other 249227825Stheraven#endif 250227825Stheraven pointer; 251227825Stheraven 252227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT {} 253227825Stheraven 254227825Stheraven _LIBCPP_INLINE_VISIBILITY 255227825Stheraven reference operator*() const {return __node_->__value_;} 256227825Stheraven _LIBCPP_INLINE_VISIBILITY 257253146Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);} 258227825Stheraven 259227825Stheraven _LIBCPP_INLINE_VISIBILITY 260227825Stheraven __hash_local_iterator& operator++() 261227825Stheraven { 262227825Stheraven __node_ = __node_->__next_; 263241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 264227825Stheraven __node_ = nullptr; 265227825Stheraven return *this; 266227825Stheraven } 267227825Stheraven 268227825Stheraven _LIBCPP_INLINE_VISIBILITY 269227825Stheraven __hash_local_iterator operator++(int) 270227825Stheraven { 271227825Stheraven __hash_local_iterator __t(*this); 272227825Stheraven ++(*this); 273227825Stheraven return __t; 274227825Stheraven } 275227825Stheraven 276227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 277227825Stheraven bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 278227825Stheraven {return __x.__node_ == __y.__node_;} 279227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 280227825Stheraven bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 281227825Stheraven {return __x.__node_ != __y.__node_;} 282227825Stheraven 283227825Stheravenprivate: 284227825Stheraven _LIBCPP_INLINE_VISIBILITY 285227825Stheraven __hash_local_iterator(__node_pointer __node, size_t __bucket, 286227825Stheraven size_t __bucket_count) _NOEXCEPT 287227825Stheraven : __node_(__node), 288227825Stheraven __bucket_(__bucket), 289227825Stheraven __bucket_count_(__bucket_count) 290227825Stheraven { 291227825Stheraven if (__node_ != nullptr) 292227825Stheraven __node_ = __node_->__next_; 293227825Stheraven } 294227825Stheraven 295227825Stheraven template <class, class, class, class> friend class __hash_table; 296249989Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 297249989Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator; 298227825Stheraven}; 299227825Stheraven 300227825Stheraventemplate <class _ConstNodePtr> 301249989Sdimclass _LIBCPP_TYPE_VIS __hash_const_local_iterator 302227825Stheraven{ 303227825Stheraven typedef _ConstNodePtr __node_pointer; 304227825Stheraven 305227825Stheraven __node_pointer __node_; 306227825Stheraven size_t __bucket_; 307227825Stheraven size_t __bucket_count_; 308227825Stheraven 309227825Stheraven typedef pointer_traits<__node_pointer> __pointer_traits; 310227825Stheraven typedef typename __pointer_traits::element_type __node; 311227825Stheraven typedef typename remove_const<__node>::type __non_const_node; 312227825Stheraven typedef typename pointer_traits<__node_pointer>::template 313227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 314227825Stheraven rebind<__non_const_node> 315227825Stheraven#else 316227825Stheraven rebind<__non_const_node>::other 317227825Stheraven#endif 318227825Stheraven __non_const_node_pointer; 319227825Stheraven typedef __hash_local_iterator<__non_const_node_pointer> 320227825Stheraven __non_const_iterator; 321227825Stheravenpublic: 322227825Stheraven typedef forward_iterator_tag iterator_category; 323227825Stheraven typedef typename remove_const< 324227825Stheraven typename __pointer_traits::element_type::value_type 325227825Stheraven >::type value_type; 326227825Stheraven typedef typename __pointer_traits::difference_type difference_type; 327227825Stheraven typedef const value_type& reference; 328227825Stheraven typedef typename __pointer_traits::template 329227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 330227825Stheraven rebind<const value_type> 331227825Stheraven#else 332227825Stheraven rebind<const value_type>::other 333227825Stheraven#endif 334227825Stheraven pointer; 335227825Stheraven 336227825Stheraven _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT {} 337227825Stheraven _LIBCPP_INLINE_VISIBILITY 338227825Stheraven __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 339227825Stheraven : __node_(__x.__node_), 340227825Stheraven __bucket_(__x.__bucket_), 341227825Stheraven __bucket_count_(__x.__bucket_count_) 342227825Stheraven {} 343227825Stheraven 344227825Stheraven _LIBCPP_INLINE_VISIBILITY 345227825Stheraven reference operator*() const {return __node_->__value_;} 346227825Stheraven _LIBCPP_INLINE_VISIBILITY 347253146Stheraven pointer operator->() const {return pointer_traits<pointer>::pointer_to(__node_->__value_);} 348227825Stheraven 349227825Stheraven _LIBCPP_INLINE_VISIBILITY 350227825Stheraven __hash_const_local_iterator& operator++() 351227825Stheraven { 352227825Stheraven __node_ = __node_->__next_; 353241900Sdim if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 354227825Stheraven __node_ = nullptr; 355227825Stheraven return *this; 356227825Stheraven } 357227825Stheraven 358227825Stheraven _LIBCPP_INLINE_VISIBILITY 359227825Stheraven __hash_const_local_iterator operator++(int) 360227825Stheraven { 361227825Stheraven __hash_const_local_iterator __t(*this); 362227825Stheraven ++(*this); 363227825Stheraven return __t; 364227825Stheraven } 365227825Stheraven 366227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 367227825Stheraven bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 368227825Stheraven {return __x.__node_ == __y.__node_;} 369227825Stheraven friend _LIBCPP_INLINE_VISIBILITY 370227825Stheraven bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 371227825Stheraven {return __x.__node_ != __y.__node_;} 372227825Stheraven 373227825Stheravenprivate: 374227825Stheraven _LIBCPP_INLINE_VISIBILITY 375227825Stheraven __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 376227825Stheraven size_t __bucket_count) _NOEXCEPT 377227825Stheraven : __node_(__node), 378227825Stheraven __bucket_(__bucket), 379227825Stheraven __bucket_count_(__bucket_count) 380227825Stheraven { 381227825Stheraven if (__node_ != nullptr) 382227825Stheraven __node_ = __node_->__next_; 383227825Stheraven } 384227825Stheraven 385227825Stheraven template <class, class, class, class> friend class __hash_table; 386249989Sdim template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 387227825Stheraven}; 388227825Stheraven 389227825Stheraventemplate <class _Alloc> 390227825Stheravenclass __bucket_list_deallocator 391227825Stheraven{ 392227825Stheraven typedef _Alloc allocator_type; 393227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 394227825Stheraven typedef typename __alloc_traits::size_type size_type; 395227825Stheraven 396227825Stheraven __compressed_pair<size_type, allocator_type> __data_; 397227825Stheravenpublic: 398227825Stheraven typedef typename __alloc_traits::pointer pointer; 399227825Stheraven 400227825Stheraven _LIBCPP_INLINE_VISIBILITY 401227825Stheraven __bucket_list_deallocator() 402227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 403227825Stheraven : __data_(0) {} 404227825Stheraven 405227825Stheraven _LIBCPP_INLINE_VISIBILITY 406227825Stheraven __bucket_list_deallocator(const allocator_type& __a, size_type __size) 407227825Stheraven _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 408227825Stheraven : __data_(__size, __a) {} 409227825Stheraven 410227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 411227825Stheraven 412227825Stheraven _LIBCPP_INLINE_VISIBILITY 413227825Stheraven __bucket_list_deallocator(__bucket_list_deallocator&& __x) 414227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 415227825Stheraven : __data_(_VSTD::move(__x.__data_)) 416227825Stheraven { 417227825Stheraven __x.size() = 0; 418227825Stheraven } 419227825Stheraven 420227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 421227825Stheraven 422227825Stheraven _LIBCPP_INLINE_VISIBILITY 423227825Stheraven size_type& size() _NOEXCEPT {return __data_.first();} 424227825Stheraven _LIBCPP_INLINE_VISIBILITY 425227825Stheraven size_type size() const _NOEXCEPT {return __data_.first();} 426227825Stheraven 427227825Stheraven _LIBCPP_INLINE_VISIBILITY 428227825Stheraven allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 429227825Stheraven _LIBCPP_INLINE_VISIBILITY 430227825Stheraven const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 431227825Stheraven 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433227825Stheraven void operator()(pointer __p) _NOEXCEPT 434227825Stheraven { 435227825Stheraven __alloc_traits::deallocate(__alloc(), __p, size()); 436227825Stheraven } 437227825Stheraven}; 438227825Stheraven 439227825Stheraventemplate <class _Alloc> class __hash_map_node_destructor; 440227825Stheraven 441227825Stheraventemplate <class _Alloc> 442227825Stheravenclass __hash_node_destructor 443227825Stheraven{ 444227825Stheraven typedef _Alloc allocator_type; 445227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 446227825Stheraven typedef typename __alloc_traits::value_type::value_type value_type; 447227825Stheravenpublic: 448227825Stheraven typedef typename __alloc_traits::pointer pointer; 449227825Stheravenprivate: 450227825Stheraven 451227825Stheraven allocator_type& __na_; 452227825Stheraven 453227825Stheraven __hash_node_destructor& operator=(const __hash_node_destructor&); 454227825Stheraven 455227825Stheravenpublic: 456227825Stheraven bool __value_constructed; 457227825Stheraven 458227825Stheraven _LIBCPP_INLINE_VISIBILITY 459227825Stheraven explicit __hash_node_destructor(allocator_type& __na, 460227825Stheraven bool __constructed = false) _NOEXCEPT 461227825Stheraven : __na_(__na), 462227825Stheraven __value_constructed(__constructed) 463227825Stheraven {} 464227825Stheraven 465227825Stheraven _LIBCPP_INLINE_VISIBILITY 466227825Stheraven void operator()(pointer __p) _NOEXCEPT 467227825Stheraven { 468227825Stheraven if (__value_constructed) 469227825Stheraven __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 470227825Stheraven if (__p) 471227825Stheraven __alloc_traits::deallocate(__na_, __p, 1); 472227825Stheraven } 473227825Stheraven 474227825Stheraven template <class> friend class __hash_map_node_destructor; 475227825Stheraven}; 476227825Stheraven 477227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 478227825Stheravenclass __hash_table 479227825Stheraven{ 480227825Stheravenpublic: 481227825Stheraven typedef _Tp value_type; 482227825Stheraven typedef _Hash hasher; 483227825Stheraven typedef _Equal key_equal; 484227825Stheraven typedef _Alloc allocator_type; 485227825Stheraven 486227825Stheravenprivate: 487227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 488227825Stheravenpublic: 489227825Stheraven typedef value_type& reference; 490227825Stheraven typedef const value_type& const_reference; 491227825Stheraven typedef typename __alloc_traits::pointer pointer; 492227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 493227825Stheraven typedef typename __alloc_traits::size_type size_type; 494227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 495227825Stheravenpublic: 496227825Stheraven // Create __node 497227825Stheraven typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 498227825Stheraven typedef typename __alloc_traits::template 499227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 500227825Stheraven rebind_alloc<__node> 501227825Stheraven#else 502227825Stheraven rebind_alloc<__node>::other 503227825Stheraven#endif 504227825Stheraven __node_allocator; 505227825Stheraven typedef allocator_traits<__node_allocator> __node_traits; 506227825Stheraven typedef typename __node_traits::pointer __node_pointer; 507253146Stheraven typedef typename __node_traits::pointer __node_const_pointer; 508232924Stheraven typedef __hash_node_base<__node_pointer> __first_node; 509253146Stheraven typedef typename pointer_traits<__node_pointer>::template 510253146Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 511253146Stheraven rebind<__first_node> 512253146Stheraven#else 513253146Stheraven rebind<__first_node>::other 514253146Stheraven#endif 515253146Stheraven __node_base_pointer; 516227825Stheraven 517227825Stheravenprivate: 518227825Stheraven 519227825Stheraven typedef typename __node_traits::template 520227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 521227825Stheraven rebind_alloc<__node_pointer> 522227825Stheraven#else 523227825Stheraven rebind_alloc<__node_pointer>::other 524227825Stheraven#endif 525227825Stheraven __pointer_allocator; 526227825Stheraven typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 527227825Stheraven typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 528227825Stheraven typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 529227825Stheraven typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 530227825Stheraven 531227825Stheraven // --- Member data begin --- 532227825Stheraven __bucket_list __bucket_list_; 533227825Stheraven __compressed_pair<__first_node, __node_allocator> __p1_; 534227825Stheraven __compressed_pair<size_type, hasher> __p2_; 535227825Stheraven __compressed_pair<float, key_equal> __p3_; 536227825Stheraven // --- Member data end --- 537227825Stheraven 538227825Stheraven _LIBCPP_INLINE_VISIBILITY 539227825Stheraven size_type& size() _NOEXCEPT {return __p2_.first();} 540227825Stheravenpublic: 541227825Stheraven _LIBCPP_INLINE_VISIBILITY 542227825Stheraven size_type size() const _NOEXCEPT {return __p2_.first();} 543227825Stheraven 544227825Stheraven _LIBCPP_INLINE_VISIBILITY 545227825Stheraven hasher& hash_function() _NOEXCEPT {return __p2_.second();} 546227825Stheraven _LIBCPP_INLINE_VISIBILITY 547227825Stheraven const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 548227825Stheraven 549227825Stheraven _LIBCPP_INLINE_VISIBILITY 550227825Stheraven float& max_load_factor() _NOEXCEPT {return __p3_.first();} 551227825Stheraven _LIBCPP_INLINE_VISIBILITY 552227825Stheraven float max_load_factor() const _NOEXCEPT {return __p3_.first();} 553227825Stheraven 554227825Stheraven _LIBCPP_INLINE_VISIBILITY 555227825Stheraven key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 558227825Stheraven 559227825Stheraven _LIBCPP_INLINE_VISIBILITY 560227825Stheraven __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 561227825Stheraven _LIBCPP_INLINE_VISIBILITY 562227825Stheraven const __node_allocator& __node_alloc() const _NOEXCEPT 563227825Stheraven {return __p1_.second();} 564227825Stheraven 565227825Stheravenpublic: 566227825Stheraven typedef __hash_iterator<__node_pointer> iterator; 567253146Stheraven typedef __hash_const_iterator<__node_pointer> const_iterator; 568227825Stheraven typedef __hash_local_iterator<__node_pointer> local_iterator; 569253146Stheraven typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 570227825Stheraven 571227825Stheraven __hash_table() 572227825Stheraven _NOEXCEPT_( 573227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 574227825Stheraven is_nothrow_default_constructible<__first_node>::value && 575227825Stheraven is_nothrow_default_constructible<__node_allocator>::value && 576227825Stheraven is_nothrow_default_constructible<hasher>::value && 577227825Stheraven is_nothrow_default_constructible<key_equal>::value); 578227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql); 579227825Stheraven __hash_table(const hasher& __hf, const key_equal& __eql, 580227825Stheraven const allocator_type& __a); 581227825Stheraven explicit __hash_table(const allocator_type& __a); 582227825Stheraven __hash_table(const __hash_table& __u); 583227825Stheraven __hash_table(const __hash_table& __u, const allocator_type& __a); 584227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 585227825Stheraven __hash_table(__hash_table&& __u) 586227825Stheraven _NOEXCEPT_( 587227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 588227825Stheraven is_nothrow_move_constructible<__first_node>::value && 589227825Stheraven is_nothrow_move_constructible<__node_allocator>::value && 590227825Stheraven is_nothrow_move_constructible<hasher>::value && 591227825Stheraven is_nothrow_move_constructible<key_equal>::value); 592227825Stheraven __hash_table(__hash_table&& __u, const allocator_type& __a); 593227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 594227825Stheraven ~__hash_table(); 595227825Stheraven 596227825Stheraven __hash_table& operator=(const __hash_table& __u); 597227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 598227825Stheraven __hash_table& operator=(__hash_table&& __u) 599227825Stheraven _NOEXCEPT_( 600227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 601227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 602227825Stheraven is_nothrow_move_assignable<hasher>::value && 603227825Stheraven is_nothrow_move_assignable<key_equal>::value); 604227825Stheraven#endif 605227825Stheraven template <class _InputIterator> 606227825Stheraven void __assign_unique(_InputIterator __first, _InputIterator __last); 607227825Stheraven template <class _InputIterator> 608227825Stheraven void __assign_multi(_InputIterator __first, _InputIterator __last); 609227825Stheraven 610227825Stheraven _LIBCPP_INLINE_VISIBILITY 611227825Stheraven size_type max_size() const _NOEXCEPT 612227825Stheraven { 613227825Stheraven return allocator_traits<__pointer_allocator>::max_size( 614227825Stheraven __bucket_list_.get_deleter().__alloc()); 615227825Stheraven } 616227825Stheraven 617227825Stheraven pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 618227825Stheraven iterator __node_insert_multi(__node_pointer __nd); 619227825Stheraven iterator __node_insert_multi(const_iterator __p, 620227825Stheraven __node_pointer __nd); 621227825Stheraven 622227825Stheraven#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 623227825Stheraven template <class... _Args> 624227825Stheraven pair<iterator, bool> __emplace_unique(_Args&&... __args); 625227825Stheraven template <class... _Args> 626227825Stheraven iterator __emplace_multi(_Args&&... __args); 627227825Stheraven template <class... _Args> 628227825Stheraven iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 629227825Stheraven#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 630227825Stheraven 631227825Stheraven pair<iterator, bool> __insert_unique(const value_type& __x); 632227825Stheraven 633227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 634232924Stheraven template <class _Pp> 635232924Stheraven pair<iterator, bool> __insert_unique(_Pp&& __x); 636227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 637227825Stheraven 638227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 639232924Stheraven template <class _Pp> 640232924Stheraven iterator __insert_multi(_Pp&& __x); 641232924Stheraven template <class _Pp> 642232924Stheraven iterator __insert_multi(const_iterator __p, _Pp&& __x); 643227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 644227825Stheraven iterator __insert_multi(const value_type& __x); 645227825Stheraven iterator __insert_multi(const_iterator __p, const value_type& __x); 646227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 647227825Stheraven 648227825Stheraven void clear() _NOEXCEPT; 649227825Stheraven void rehash(size_type __n); 650227825Stheraven _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 651227825Stheraven {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 652227825Stheraven 653227825Stheraven _LIBCPP_INLINE_VISIBILITY 654227825Stheraven size_type bucket_count() const _NOEXCEPT 655227825Stheraven { 656227825Stheraven return __bucket_list_.get_deleter().size(); 657227825Stheraven } 658227825Stheraven 659227825Stheraven iterator begin() _NOEXCEPT; 660227825Stheraven iterator end() _NOEXCEPT; 661227825Stheraven const_iterator begin() const _NOEXCEPT; 662227825Stheraven const_iterator end() const _NOEXCEPT; 663227825Stheraven 664227825Stheraven template <class _Key> 665227825Stheraven _LIBCPP_INLINE_VISIBILITY 666227825Stheraven size_type bucket(const _Key& __k) const 667241900Sdim {return __constrain_hash(hash_function()(__k), bucket_count());} 668227825Stheraven 669227825Stheraven template <class _Key> 670227825Stheraven iterator find(const _Key& __x); 671227825Stheraven template <class _Key> 672227825Stheraven const_iterator find(const _Key& __x) const; 673227825Stheraven 674232924Stheraven typedef __hash_node_destructor<__node_allocator> _Dp; 675232924Stheraven typedef unique_ptr<__node, _Dp> __node_holder; 676227825Stheraven 677227825Stheraven iterator erase(const_iterator __p); 678227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 679227825Stheraven template <class _Key> 680227825Stheraven size_type __erase_unique(const _Key& __k); 681227825Stheraven template <class _Key> 682227825Stheraven size_type __erase_multi(const _Key& __k); 683227825Stheraven __node_holder remove(const_iterator __p) _NOEXCEPT; 684227825Stheraven 685227825Stheraven template <class _Key> 686227825Stheraven size_type __count_unique(const _Key& __k) const; 687227825Stheraven template <class _Key> 688227825Stheraven size_type __count_multi(const _Key& __k) const; 689227825Stheraven 690227825Stheraven template <class _Key> 691227825Stheraven pair<iterator, iterator> 692227825Stheraven __equal_range_unique(const _Key& __k); 693227825Stheraven template <class _Key> 694227825Stheraven pair<const_iterator, const_iterator> 695227825Stheraven __equal_range_unique(const _Key& __k) const; 696227825Stheraven 697227825Stheraven template <class _Key> 698227825Stheraven pair<iterator, iterator> 699227825Stheraven __equal_range_multi(const _Key& __k); 700227825Stheraven template <class _Key> 701227825Stheraven pair<const_iterator, const_iterator> 702227825Stheraven __equal_range_multi(const _Key& __k) const; 703227825Stheraven 704227825Stheraven void swap(__hash_table& __u) 705227825Stheraven _NOEXCEPT_( 706227825Stheraven (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 707227825Stheraven __is_nothrow_swappable<__pointer_allocator>::value) && 708227825Stheraven (!__node_traits::propagate_on_container_swap::value || 709227825Stheraven __is_nothrow_swappable<__node_allocator>::value) && 710227825Stheraven __is_nothrow_swappable<hasher>::value && 711227825Stheraven __is_nothrow_swappable<key_equal>::value); 712227825Stheraven 713227825Stheraven _LIBCPP_INLINE_VISIBILITY 714227825Stheraven size_type max_bucket_count() const _NOEXCEPT 715253146Stheraven {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 716227825Stheraven size_type bucket_size(size_type __n) const; 717227825Stheraven _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 718227825Stheraven { 719227825Stheraven size_type __bc = bucket_count(); 720227825Stheraven return __bc != 0 ? (float)size() / __bc : 0.f; 721227825Stheraven } 722227825Stheraven _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 723227825Stheraven {max_load_factor() = _VSTD::max(__mlf, load_factor());} 724227825Stheraven 725227825Stheraven _LIBCPP_INLINE_VISIBILITY local_iterator begin(size_type __n) 726227825Stheraven {return local_iterator(__bucket_list_[__n], __n, bucket_count());} 727227825Stheraven _LIBCPP_INLINE_VISIBILITY local_iterator end(size_type __n) 728227825Stheraven {return local_iterator(nullptr, __n, bucket_count());} 729227825Stheraven _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const 730227825Stheraven {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());} 731227825Stheraven _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const 732227825Stheraven {return const_local_iterator(nullptr, __n, bucket_count());} 733227825Stheravenprivate: 734227825Stheraven void __rehash(size_type __n); 735227825Stheraven 736227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 737227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 738227825Stheraven template <class ..._Args> 739227825Stheraven __node_holder __construct_node(_Args&& ...__args); 740227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 741227825Stheraven __node_holder __construct_node(value_type&& __v, size_t __hash); 742227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 743227825Stheraven __node_holder __construct_node(const value_type& __v); 744227825Stheraven#endif 745227825Stheraven __node_holder __construct_node(const value_type& __v, size_t __hash); 746227825Stheraven 747227825Stheraven _LIBCPP_INLINE_VISIBILITY 748227825Stheraven void __copy_assign_alloc(const __hash_table& __u) 749227825Stheraven {__copy_assign_alloc(__u, integral_constant<bool, 750227825Stheraven __node_traits::propagate_on_container_copy_assignment::value>());} 751227825Stheraven void __copy_assign_alloc(const __hash_table& __u, true_type); 752227825Stheraven _LIBCPP_INLINE_VISIBILITY 753232924Stheraven void __copy_assign_alloc(const __hash_table&, false_type) {} 754227825Stheraven 755227825Stheraven void __move_assign(__hash_table& __u, false_type); 756227825Stheraven void __move_assign(__hash_table& __u, true_type) 757227825Stheraven _NOEXCEPT_( 758227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 759227825Stheraven is_nothrow_move_assignable<hasher>::value && 760227825Stheraven is_nothrow_move_assignable<key_equal>::value); 761227825Stheraven _LIBCPP_INLINE_VISIBILITY 762227825Stheraven void __move_assign_alloc(__hash_table& __u) 763227825Stheraven _NOEXCEPT_( 764227825Stheraven !__node_traits::propagate_on_container_move_assignment::value || 765227825Stheraven (is_nothrow_move_assignable<__pointer_allocator>::value && 766227825Stheraven is_nothrow_move_assignable<__node_allocator>::value)) 767227825Stheraven {__move_assign_alloc(__u, integral_constant<bool, 768227825Stheraven __node_traits::propagate_on_container_move_assignment::value>());} 769227825Stheraven _LIBCPP_INLINE_VISIBILITY 770227825Stheraven void __move_assign_alloc(__hash_table& __u, true_type) 771227825Stheraven _NOEXCEPT_( 772227825Stheraven is_nothrow_move_assignable<__pointer_allocator>::value && 773227825Stheraven is_nothrow_move_assignable<__node_allocator>::value) 774227825Stheraven { 775227825Stheraven __bucket_list_.get_deleter().__alloc() = 776227825Stheraven _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 777227825Stheraven __node_alloc() = _VSTD::move(__u.__node_alloc()); 778227825Stheraven } 779227825Stheraven _LIBCPP_INLINE_VISIBILITY 780227825Stheraven void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 781227825Stheraven 782232924Stheraven template <class _Ap> 783227825Stheraven _LIBCPP_INLINE_VISIBILITY 784227825Stheraven static 785227825Stheraven void 786232924Stheraven __swap_alloc(_Ap& __x, _Ap& __y) 787227825Stheraven _NOEXCEPT_( 788232924Stheraven !allocator_traits<_Ap>::propagate_on_container_swap::value || 789232924Stheraven __is_nothrow_swappable<_Ap>::value) 790227825Stheraven { 791227825Stheraven __swap_alloc(__x, __y, 792227825Stheraven integral_constant<bool, 793232924Stheraven allocator_traits<_Ap>::propagate_on_container_swap::value 794227825Stheraven >()); 795227825Stheraven } 796227825Stheraven 797232924Stheraven template <class _Ap> 798227825Stheraven _LIBCPP_INLINE_VISIBILITY 799227825Stheraven static 800227825Stheraven void 801232924Stheraven __swap_alloc(_Ap& __x, _Ap& __y, true_type) 802232924Stheraven _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 803227825Stheraven { 804227825Stheraven using _VSTD::swap; 805227825Stheraven swap(__x, __y); 806227825Stheraven } 807227825Stheraven 808232924Stheraven template <class _Ap> 809227825Stheraven _LIBCPP_INLINE_VISIBILITY 810227825Stheraven static 811227825Stheraven void 812232924Stheraven __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 813227825Stheraven 814227825Stheraven void __deallocate(__node_pointer __np) _NOEXCEPT; 815227825Stheraven __node_pointer __detach() _NOEXCEPT; 816253146Stheraven 817253146Stheraven template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 818253146Stheraven template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 819227825Stheraven}; 820227825Stheraven 821227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 822227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 823227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 824227825Stheraven _NOEXCEPT_( 825227825Stheraven is_nothrow_default_constructible<__bucket_list>::value && 826227825Stheraven is_nothrow_default_constructible<__first_node>::value && 827227825Stheraven is_nothrow_default_constructible<hasher>::value && 828227825Stheraven is_nothrow_default_constructible<key_equal>::value) 829227825Stheraven : __p2_(0), 830227825Stheraven __p3_(1.0f) 831227825Stheraven{ 832227825Stheraven} 833227825Stheraven 834227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 835227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 836227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 837227825Stheraven const key_equal& __eql) 838227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter()), 839227825Stheraven __p1_(), 840227825Stheraven __p2_(0, __hf), 841227825Stheraven __p3_(1.0f, __eql) 842227825Stheraven{ 843227825Stheraven} 844227825Stheraven 845227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 846227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 847227825Stheraven const key_equal& __eql, 848227825Stheraven const allocator_type& __a) 849227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 850227825Stheraven __p1_(__node_allocator(__a)), 851227825Stheraven __p2_(0, __hf), 852227825Stheraven __p3_(1.0f, __eql) 853227825Stheraven{ 854227825Stheraven} 855227825Stheraven 856227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 857227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 858227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 859227825Stheraven __p1_(__node_allocator(__a)), 860227825Stheraven __p2_(0), 861227825Stheraven __p3_(1.0f) 862227825Stheraven{ 863227825Stheraven} 864227825Stheraven 865227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 866227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 867227825Stheraven : __bucket_list_(nullptr, 868227825Stheraven __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 869227825Stheraven select_on_container_copy_construction( 870227825Stheraven __u.__bucket_list_.get_deleter().__alloc()), 0)), 871227825Stheraven __p1_(allocator_traits<__node_allocator>:: 872227825Stheraven select_on_container_copy_construction(__u.__node_alloc())), 873227825Stheraven __p2_(0, __u.hash_function()), 874227825Stheraven __p3_(__u.__p3_) 875227825Stheraven{ 876227825Stheraven} 877227825Stheraven 878227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 879227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 880227825Stheraven const allocator_type& __a) 881227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 882227825Stheraven __p1_(__node_allocator(__a)), 883227825Stheraven __p2_(0, __u.hash_function()), 884227825Stheraven __p3_(__u.__p3_) 885227825Stheraven{ 886227825Stheraven} 887227825Stheraven 888227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 889227825Stheraven 890227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 891227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 892227825Stheraven _NOEXCEPT_( 893227825Stheraven is_nothrow_move_constructible<__bucket_list>::value && 894227825Stheraven is_nothrow_move_constructible<__first_node>::value && 895227825Stheraven is_nothrow_move_constructible<hasher>::value && 896227825Stheraven is_nothrow_move_constructible<key_equal>::value) 897227825Stheraven : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 898227825Stheraven __p1_(_VSTD::move(__u.__p1_)), 899227825Stheraven __p2_(_VSTD::move(__u.__p2_)), 900227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 901227825Stheraven{ 902227825Stheraven if (size() > 0) 903227825Stheraven { 904241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 905253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 906227825Stheraven __u.__p1_.first().__next_ = nullptr; 907227825Stheraven __u.size() = 0; 908227825Stheraven } 909227825Stheraven} 910227825Stheraven 911227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 912227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 913227825Stheraven const allocator_type& __a) 914227825Stheraven : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 915227825Stheraven __p1_(__node_allocator(__a)), 916227825Stheraven __p2_(0, _VSTD::move(__u.hash_function())), 917227825Stheraven __p3_(_VSTD::move(__u.__p3_)) 918227825Stheraven{ 919227825Stheraven if (__a == allocator_type(__u.__node_alloc())) 920227825Stheraven { 921227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 922227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 923227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 924227825Stheraven if (__u.size() > 0) 925227825Stheraven { 926227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 927227825Stheraven __u.__p1_.first().__next_ = nullptr; 928241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 929253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 930227825Stheraven size() = __u.size(); 931227825Stheraven __u.size() = 0; 932227825Stheraven } 933227825Stheraven } 934227825Stheraven} 935227825Stheraven 936227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 937227825Stheraven 938227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 939227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 940227825Stheraven{ 941227825Stheraven __deallocate(__p1_.first().__next_); 942227825Stheraven} 943227825Stheraven 944227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 945227825Stheravenvoid 946227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 947227825Stheraven const __hash_table& __u, true_type) 948227825Stheraven{ 949227825Stheraven if (__node_alloc() != __u.__node_alloc()) 950227825Stheraven { 951227825Stheraven clear(); 952227825Stheraven __bucket_list_.reset(); 953227825Stheraven __bucket_list_.get_deleter().size() = 0; 954227825Stheraven } 955227825Stheraven __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 956227825Stheraven __node_alloc() = __u.__node_alloc(); 957227825Stheraven} 958227825Stheraven 959227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 960227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 961227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 962227825Stheraven{ 963227825Stheraven if (this != &__u) 964227825Stheraven { 965227825Stheraven __copy_assign_alloc(__u); 966227825Stheraven hash_function() = __u.hash_function(); 967227825Stheraven key_eq() = __u.key_eq(); 968227825Stheraven max_load_factor() = __u.max_load_factor(); 969227825Stheraven __assign_multi(__u.begin(), __u.end()); 970227825Stheraven } 971227825Stheraven return *this; 972227825Stheraven} 973227825Stheraven 974227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 975227825Stheravenvoid 976227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 977227825Stheraven _NOEXCEPT 978227825Stheraven{ 979227825Stheraven __node_allocator& __na = __node_alloc(); 980227825Stheraven while (__np != nullptr) 981227825Stheraven { 982227825Stheraven __node_pointer __next = __np->__next_; 983227825Stheraven __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 984227825Stheraven __node_traits::deallocate(__na, __np, 1); 985227825Stheraven __np = __next; 986227825Stheraven } 987227825Stheraven} 988227825Stheraven 989227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 990227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 991227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 992227825Stheraven{ 993227825Stheraven size_type __bc = bucket_count(); 994227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 995227825Stheraven __bucket_list_[__i] = nullptr; 996227825Stheraven size() = 0; 997227825Stheraven __node_pointer __cache = __p1_.first().__next_; 998227825Stheraven __p1_.first().__next_ = nullptr; 999227825Stheraven return __cache; 1000227825Stheraven} 1001227825Stheraven 1002227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1003227825Stheraven 1004227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1005227825Stheravenvoid 1006227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1007227825Stheraven __hash_table& __u, true_type) 1008227825Stheraven _NOEXCEPT_( 1009227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1010227825Stheraven is_nothrow_move_assignable<hasher>::value && 1011227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1012227825Stheraven{ 1013227825Stheraven clear(); 1014227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1015227825Stheraven __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1016227825Stheraven __u.__bucket_list_.get_deleter().size() = 0; 1017227825Stheraven __move_assign_alloc(__u); 1018227825Stheraven size() = __u.size(); 1019227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1020227825Stheraven max_load_factor() = __u.max_load_factor(); 1021227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1022227825Stheraven __p1_.first().__next_ = __u.__p1_.first().__next_; 1023227825Stheraven if (size() > 0) 1024227825Stheraven { 1025241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1026253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1027227825Stheraven __u.__p1_.first().__next_ = nullptr; 1028227825Stheraven __u.size() = 0; 1029227825Stheraven } 1030227825Stheraven} 1031227825Stheraven 1032227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1033227825Stheravenvoid 1034227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1035227825Stheraven __hash_table& __u, false_type) 1036227825Stheraven{ 1037227825Stheraven if (__node_alloc() == __u.__node_alloc()) 1038227825Stheraven __move_assign(__u, true_type()); 1039227825Stheraven else 1040227825Stheraven { 1041227825Stheraven hash_function() = _VSTD::move(__u.hash_function()); 1042227825Stheraven key_eq() = _VSTD::move(__u.key_eq()); 1043227825Stheraven max_load_factor() = __u.max_load_factor(); 1044227825Stheraven if (bucket_count() != 0) 1045227825Stheraven { 1046227825Stheraven __node_pointer __cache = __detach(); 1047227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1048227825Stheraven try 1049227825Stheraven { 1050227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1051227825Stheraven const_iterator __i = __u.begin(); 1052227825Stheraven while (__cache != nullptr && __u.size() != 0) 1053227825Stheraven { 1054227825Stheraven __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1055227825Stheraven __node_pointer __next = __cache->__next_; 1056227825Stheraven __node_insert_multi(__cache); 1057227825Stheraven __cache = __next; 1058227825Stheraven } 1059227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1060227825Stheraven } 1061227825Stheraven catch (...) 1062227825Stheraven { 1063227825Stheraven __deallocate(__cache); 1064227825Stheraven throw; 1065227825Stheraven } 1066227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1067227825Stheraven __deallocate(__cache); 1068227825Stheraven } 1069227825Stheraven const_iterator __i = __u.begin(); 1070227825Stheraven while (__u.size() != 0) 1071227825Stheraven { 1072227825Stheraven __node_holder __h = 1073227825Stheraven __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1074227825Stheraven __node_insert_multi(__h.get()); 1075227825Stheraven __h.release(); 1076227825Stheraven } 1077227825Stheraven } 1078227825Stheraven} 1079227825Stheraven 1080227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1081227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1082227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1083227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1084227825Stheraven _NOEXCEPT_( 1085227825Stheraven __node_traits::propagate_on_container_move_assignment::value && 1086227825Stheraven is_nothrow_move_assignable<__node_allocator>::value && 1087227825Stheraven is_nothrow_move_assignable<hasher>::value && 1088227825Stheraven is_nothrow_move_assignable<key_equal>::value) 1089227825Stheraven{ 1090227825Stheraven __move_assign(__u, integral_constant<bool, 1091227825Stheraven __node_traits::propagate_on_container_move_assignment::value>()); 1092227825Stheraven return *this; 1093227825Stheraven} 1094227825Stheraven 1095227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1096227825Stheraven 1097227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1098227825Stheraventemplate <class _InputIterator> 1099227825Stheravenvoid 1100227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1101227825Stheraven _InputIterator __last) 1102227825Stheraven{ 1103227825Stheraven if (bucket_count() != 0) 1104227825Stheraven { 1105227825Stheraven __node_pointer __cache = __detach(); 1106227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1107227825Stheraven try 1108227825Stheraven { 1109227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1110227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1111227825Stheraven { 1112227825Stheraven __cache->__value_ = *__first; 1113227825Stheraven __node_pointer __next = __cache->__next_; 1114227825Stheraven __node_insert_unique(__cache); 1115227825Stheraven __cache = __next; 1116227825Stheraven } 1117227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1118227825Stheraven } 1119227825Stheraven catch (...) 1120227825Stheraven { 1121227825Stheraven __deallocate(__cache); 1122227825Stheraven throw; 1123227825Stheraven } 1124227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1125227825Stheraven __deallocate(__cache); 1126227825Stheraven } 1127227825Stheraven for (; __first != __last; ++__first) 1128227825Stheraven __insert_unique(*__first); 1129227825Stheraven} 1130227825Stheraven 1131227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1132227825Stheraventemplate <class _InputIterator> 1133227825Stheravenvoid 1134227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1135227825Stheraven _InputIterator __last) 1136227825Stheraven{ 1137227825Stheraven if (bucket_count() != 0) 1138227825Stheraven { 1139227825Stheraven __node_pointer __cache = __detach(); 1140227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1141227825Stheraven try 1142227825Stheraven { 1143227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1144227825Stheraven for (; __cache != nullptr && __first != __last; ++__first) 1145227825Stheraven { 1146227825Stheraven __cache->__value_ = *__first; 1147227825Stheraven __node_pointer __next = __cache->__next_; 1148227825Stheraven __node_insert_multi(__cache); 1149227825Stheraven __cache = __next; 1150227825Stheraven } 1151227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1152227825Stheraven } 1153227825Stheraven catch (...) 1154227825Stheraven { 1155227825Stheraven __deallocate(__cache); 1156227825Stheraven throw; 1157227825Stheraven } 1158227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1159227825Stheraven __deallocate(__cache); 1160227825Stheraven } 1161227825Stheraven for (; __first != __last; ++__first) 1162227825Stheraven __insert_multi(*__first); 1163227825Stheraven} 1164227825Stheraven 1165227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1166227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1167227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1168227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1169227825Stheraven{ 1170227825Stheraven return iterator(__p1_.first().__next_); 1171227825Stheraven} 1172227825Stheraven 1173227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1174227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1175227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1176227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1177227825Stheraven{ 1178227825Stheraven return iterator(nullptr); 1179227825Stheraven} 1180227825Stheraven 1181227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1182227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1183227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1184227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1185227825Stheraven{ 1186227825Stheraven return const_iterator(__p1_.first().__next_); 1187227825Stheraven} 1188227825Stheraven 1189227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1190227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1191227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1192227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1193227825Stheraven{ 1194227825Stheraven return const_iterator(nullptr); 1195227825Stheraven} 1196227825Stheraven 1197227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1198227825Stheravenvoid 1199227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1200227825Stheraven{ 1201227825Stheraven if (size() > 0) 1202227825Stheraven { 1203227825Stheraven __deallocate(__p1_.first().__next_); 1204227825Stheraven __p1_.first().__next_ = nullptr; 1205227825Stheraven size_type __bc = bucket_count(); 1206227825Stheraven for (size_type __i = 0; __i < __bc; ++__i) 1207227825Stheraven __bucket_list_[__i] = nullptr; 1208227825Stheraven size() = 0; 1209227825Stheraven } 1210227825Stheraven} 1211227825Stheraven 1212227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1213227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1214227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1215227825Stheraven{ 1216227825Stheraven __nd->__hash_ = hash_function()(__nd->__value_); 1217227825Stheraven size_type __bc = bucket_count(); 1218227825Stheraven bool __inserted = false; 1219227825Stheraven __node_pointer __ndptr; 1220227825Stheraven size_t __chash; 1221227825Stheraven if (__bc != 0) 1222227825Stheraven { 1223241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1224227825Stheraven __ndptr = __bucket_list_[__chash]; 1225227825Stheraven if (__ndptr != nullptr) 1226227825Stheraven { 1227227825Stheraven for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1228241900Sdim __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1229227825Stheraven __ndptr = __ndptr->__next_) 1230227825Stheraven { 1231227825Stheraven if (key_eq()(__ndptr->__value_, __nd->__value_)) 1232227825Stheraven goto __done; 1233227825Stheraven } 1234227825Stheraven } 1235227825Stheraven } 1236227825Stheraven { 1237227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1238227825Stheraven { 1239241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1240227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1241227825Stheraven __bc = bucket_count(); 1242241900Sdim __chash = __constrain_hash(__nd->__hash_, __bc); 1243227825Stheraven } 1244227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1245227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1246227825Stheraven if (__pn == nullptr) 1247227825Stheraven { 1248253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1249227825Stheraven __nd->__next_ = __pn->__next_; 1250227825Stheraven __pn->__next_ = __nd; 1251227825Stheraven // fix up __bucket_list_ 1252227825Stheraven __bucket_list_[__chash] = __pn; 1253227825Stheraven if (__nd->__next_ != nullptr) 1254241900Sdim __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1255227825Stheraven } 1256227825Stheraven else 1257227825Stheraven { 1258227825Stheraven __nd->__next_ = __pn->__next_; 1259227825Stheraven __pn->__next_ = __nd; 1260227825Stheraven } 1261227825Stheraven __ndptr = __nd; 1262227825Stheraven // increment size 1263227825Stheraven ++size(); 1264227825Stheraven __inserted = true; 1265227825Stheraven } 1266227825Stheraven__done: 1267227825Stheraven return pair<iterator, bool>(iterator(__ndptr), __inserted); 1268227825Stheraven} 1269227825Stheraven 1270227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1271227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1272227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1273227825Stheraven{ 1274227825Stheraven __cp->__hash_ = hash_function()(__cp->__value_); 1275227825Stheraven size_type __bc = bucket_count(); 1276227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1277227825Stheraven { 1278241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1279227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1280227825Stheraven __bc = bucket_count(); 1281227825Stheraven } 1282241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1283227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1284227825Stheraven if (__pn == nullptr) 1285227825Stheraven { 1286253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1287227825Stheraven __cp->__next_ = __pn->__next_; 1288227825Stheraven __pn->__next_ = __cp; 1289227825Stheraven // fix up __bucket_list_ 1290227825Stheraven __bucket_list_[__chash] = __pn; 1291227825Stheraven if (__cp->__next_ != nullptr) 1292241900Sdim __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1293227825Stheraven } 1294227825Stheraven else 1295227825Stheraven { 1296227825Stheraven for (bool __found = false; __pn->__next_ != nullptr && 1297241900Sdim __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1298227825Stheraven __pn = __pn->__next_) 1299227825Stheraven { 1300227825Stheraven // __found key_eq() action 1301227825Stheraven // false false loop 1302227825Stheraven // true true loop 1303227825Stheraven // false true set __found to true 1304227825Stheraven // true false break 1305227825Stheraven if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1306227825Stheraven key_eq()(__pn->__next_->__value_, __cp->__value_))) 1307227825Stheraven { 1308227825Stheraven if (!__found) 1309227825Stheraven __found = true; 1310227825Stheraven else 1311227825Stheraven break; 1312227825Stheraven } 1313227825Stheraven } 1314227825Stheraven __cp->__next_ = __pn->__next_; 1315227825Stheraven __pn->__next_ = __cp; 1316227825Stheraven if (__cp->__next_ != nullptr) 1317227825Stheraven { 1318241900Sdim size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1319227825Stheraven if (__nhash != __chash) 1320227825Stheraven __bucket_list_[__nhash] = __cp; 1321227825Stheraven } 1322227825Stheraven } 1323227825Stheraven ++size(); 1324227825Stheraven return iterator(__cp); 1325227825Stheraven} 1326227825Stheraven 1327227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1328227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1329227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1330227825Stheraven const_iterator __p, __node_pointer __cp) 1331227825Stheraven{ 1332227825Stheraven if (__p != end() && key_eq()(*__p, __cp->__value_)) 1333227825Stheraven { 1334253146Stheraven __node_pointer __np = __p.__node_; 1335227825Stheraven __cp->__hash_ = __np->__hash_; 1336227825Stheraven size_type __bc = bucket_count(); 1337227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1338227825Stheraven { 1339241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1340227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1341227825Stheraven __bc = bucket_count(); 1342227825Stheraven } 1343241900Sdim size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1344227825Stheraven __node_pointer __pp = __bucket_list_[__chash]; 1345227825Stheraven while (__pp->__next_ != __np) 1346227825Stheraven __pp = __pp->__next_; 1347227825Stheraven __cp->__next_ = __np; 1348227825Stheraven __pp->__next_ = __cp; 1349227825Stheraven ++size(); 1350227825Stheraven return iterator(__cp); 1351227825Stheraven } 1352227825Stheraven return __node_insert_multi(__cp); 1353227825Stheraven} 1354227825Stheraven 1355227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1356227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1357227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1358227825Stheraven{ 1359227825Stheraven size_t __hash = hash_function()(__x); 1360227825Stheraven size_type __bc = bucket_count(); 1361227825Stheraven bool __inserted = false; 1362227825Stheraven __node_pointer __nd; 1363227825Stheraven size_t __chash; 1364227825Stheraven if (__bc != 0) 1365227825Stheraven { 1366241900Sdim __chash = __constrain_hash(__hash, __bc); 1367227825Stheraven __nd = __bucket_list_[__chash]; 1368227825Stheraven if (__nd != nullptr) 1369227825Stheraven { 1370227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1371241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1372227825Stheraven __nd = __nd->__next_) 1373227825Stheraven { 1374227825Stheraven if (key_eq()(__nd->__value_, __x)) 1375227825Stheraven goto __done; 1376227825Stheraven } 1377227825Stheraven } 1378227825Stheraven } 1379227825Stheraven { 1380227825Stheraven __node_holder __h = __construct_node(__x, __hash); 1381227825Stheraven if (size()+1 > __bc * max_load_factor() || __bc == 0) 1382227825Stheraven { 1383241900Sdim rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1384227825Stheraven size_type(ceil(float(size() + 1) / max_load_factor())))); 1385227825Stheraven __bc = bucket_count(); 1386241900Sdim __chash = __constrain_hash(__hash, __bc); 1387227825Stheraven } 1388227825Stheraven // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1389227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1390227825Stheraven if (__pn == nullptr) 1391227825Stheraven { 1392253146Stheraven __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1393227825Stheraven __h->__next_ = __pn->__next_; 1394227825Stheraven __pn->__next_ = __h.get(); 1395227825Stheraven // fix up __bucket_list_ 1396227825Stheraven __bucket_list_[__chash] = __pn; 1397227825Stheraven if (__h->__next_ != nullptr) 1398241900Sdim __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1399227825Stheraven } 1400227825Stheraven else 1401227825Stheraven { 1402227825Stheraven __h->__next_ = __pn->__next_; 1403227825Stheraven __pn->__next_ = __h.get(); 1404227825Stheraven } 1405227825Stheraven __nd = __h.release(); 1406227825Stheraven // increment size 1407227825Stheraven ++size(); 1408227825Stheraven __inserted = true; 1409227825Stheraven } 1410227825Stheraven__done: 1411227825Stheraven return pair<iterator, bool>(iterator(__nd), __inserted); 1412227825Stheraven} 1413227825Stheraven 1414227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1415227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1416227825Stheraven 1417227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1418227825Stheraventemplate <class... _Args> 1419227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1420227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1421227825Stheraven{ 1422227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1423227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1424227825Stheraven if (__r.second) 1425227825Stheraven __h.release(); 1426227825Stheraven return __r; 1427227825Stheraven} 1428227825Stheraven 1429227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1430227825Stheraventemplate <class... _Args> 1431227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1432227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1433227825Stheraven{ 1434227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1435227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1436227825Stheraven __h.release(); 1437227825Stheraven return __r; 1438227825Stheraven} 1439227825Stheraven 1440227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1441227825Stheraventemplate <class... _Args> 1442227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1443227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1444227825Stheraven const_iterator __p, _Args&&... __args) 1445227825Stheraven{ 1446227825Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1447227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1448227825Stheraven __h.release(); 1449227825Stheraven return __r; 1450227825Stheraven} 1451227825Stheraven 1452227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1453227825Stheraven 1454227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1455232924Stheraventemplate <class _Pp> 1456227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1457232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1458227825Stheraven{ 1459232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1460227825Stheraven pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1461227825Stheraven if (__r.second) 1462227825Stheraven __h.release(); 1463227825Stheraven return __r; 1464227825Stheraven} 1465227825Stheraven 1466227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1467227825Stheraven 1468227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1469227825Stheraven 1470227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1471232924Stheraventemplate <class _Pp> 1472227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1473232924Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1474227825Stheraven{ 1475232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1476227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1477227825Stheraven __h.release(); 1478227825Stheraven return __r; 1479227825Stheraven} 1480227825Stheraven 1481227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1482232924Stheraventemplate <class _Pp> 1483227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1484227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1485232924Stheraven _Pp&& __x) 1486227825Stheraven{ 1487232924Stheraven __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1488227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1489227825Stheraven __h.release(); 1490227825Stheraven return __r; 1491227825Stheraven} 1492227825Stheraven 1493227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1494227825Stheraven 1495227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1496227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1497227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1498227825Stheraven{ 1499227825Stheraven __node_holder __h = __construct_node(__x); 1500227825Stheraven iterator __r = __node_insert_multi(__h.get()); 1501227825Stheraven __h.release(); 1502227825Stheraven return __r; 1503227825Stheraven} 1504227825Stheraven 1505227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1506227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1507227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1508227825Stheraven const value_type& __x) 1509227825Stheraven{ 1510227825Stheraven __node_holder __h = __construct_node(__x); 1511227825Stheraven iterator __r = __node_insert_multi(__p, __h.get()); 1512227825Stheraven __h.release(); 1513227825Stheraven return __r; 1514227825Stheraven} 1515227825Stheraven 1516227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1517227825Stheraven 1518227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1519227825Stheravenvoid 1520227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1521227825Stheraven{ 1522241900Sdim if (__n == 1) 1523241900Sdim __n = 2; 1524241900Sdim else if (__n & (__n - 1)) 1525241900Sdim __n = __next_prime(__n); 1526227825Stheraven size_type __bc = bucket_count(); 1527227825Stheraven if (__n > __bc) 1528227825Stheraven __rehash(__n); 1529241900Sdim else if (__n < __bc) 1530227825Stheraven { 1531227825Stheraven __n = _VSTD::max<size_type> 1532227825Stheraven ( 1533227825Stheraven __n, 1534241900Sdim __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1535241900Sdim __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1536227825Stheraven ); 1537227825Stheraven if (__n < __bc) 1538227825Stheraven __rehash(__n); 1539227825Stheraven } 1540227825Stheraven} 1541227825Stheraven 1542227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1543227825Stheravenvoid 1544227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1545227825Stheraven{ 1546227825Stheraven __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1547227825Stheraven __bucket_list_.reset(__nbc > 0 ? 1548227825Stheraven __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1549227825Stheraven __bucket_list_.get_deleter().size() = __nbc; 1550227825Stheraven if (__nbc > 0) 1551227825Stheraven { 1552227825Stheraven for (size_type __i = 0; __i < __nbc; ++__i) 1553227825Stheraven __bucket_list_[__i] = nullptr; 1554253146Stheraven __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1555227825Stheraven __node_pointer __cp = __pp->__next_; 1556227825Stheraven if (__cp != nullptr) 1557227825Stheraven { 1558241900Sdim size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1559227825Stheraven __bucket_list_[__chash] = __pp; 1560227825Stheraven size_type __phash = __chash; 1561227825Stheraven for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1562227825Stheraven __cp = __pp->__next_) 1563227825Stheraven { 1564241900Sdim __chash = __constrain_hash(__cp->__hash_, __nbc); 1565227825Stheraven if (__chash == __phash) 1566227825Stheraven __pp = __cp; 1567227825Stheraven else 1568227825Stheraven { 1569227825Stheraven if (__bucket_list_[__chash] == nullptr) 1570227825Stheraven { 1571227825Stheraven __bucket_list_[__chash] = __pp; 1572227825Stheraven __pp = __cp; 1573227825Stheraven __phash = __chash; 1574227825Stheraven } 1575227825Stheraven else 1576227825Stheraven { 1577227825Stheraven __node_pointer __np = __cp; 1578227825Stheraven for (; __np->__next_ != nullptr && 1579227825Stheraven key_eq()(__cp->__value_, __np->__next_->__value_); 1580227825Stheraven __np = __np->__next_) 1581227825Stheraven ; 1582227825Stheraven __pp->__next_ = __np->__next_; 1583227825Stheraven __np->__next_ = __bucket_list_[__chash]->__next_; 1584227825Stheraven __bucket_list_[__chash]->__next_ = __cp; 1585227825Stheraven 1586227825Stheraven } 1587227825Stheraven } 1588227825Stheraven } 1589227825Stheraven } 1590227825Stheraven } 1591227825Stheraven} 1592227825Stheraven 1593227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1594227825Stheraventemplate <class _Key> 1595227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1596227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 1597227825Stheraven{ 1598227825Stheraven size_t __hash = hash_function()(__k); 1599227825Stheraven size_type __bc = bucket_count(); 1600227825Stheraven if (__bc != 0) 1601227825Stheraven { 1602241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 1603227825Stheraven __node_pointer __nd = __bucket_list_[__chash]; 1604227825Stheraven if (__nd != nullptr) 1605227825Stheraven { 1606227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1607241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1608227825Stheraven __nd = __nd->__next_) 1609227825Stheraven { 1610227825Stheraven if (key_eq()(__nd->__value_, __k)) 1611227825Stheraven return iterator(__nd); 1612227825Stheraven } 1613227825Stheraven } 1614227825Stheraven } 1615227825Stheraven return end(); 1616227825Stheraven} 1617227825Stheraven 1618227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1619227825Stheraventemplate <class _Key> 1620227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1621227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 1622227825Stheraven{ 1623227825Stheraven size_t __hash = hash_function()(__k); 1624227825Stheraven size_type __bc = bucket_count(); 1625227825Stheraven if (__bc != 0) 1626227825Stheraven { 1627241900Sdim size_t __chash = __constrain_hash(__hash, __bc); 1628227825Stheraven __node_const_pointer __nd = __bucket_list_[__chash]; 1629227825Stheraven if (__nd != nullptr) 1630227825Stheraven { 1631227825Stheraven for (__nd = __nd->__next_; __nd != nullptr && 1632241900Sdim __constrain_hash(__nd->__hash_, __bc) == __chash; 1633227825Stheraven __nd = __nd->__next_) 1634227825Stheraven { 1635227825Stheraven if (key_eq()(__nd->__value_, __k)) 1636227825Stheraven return const_iterator(__nd); 1637227825Stheraven } 1638227825Stheraven } 1639227825Stheraven 1640227825Stheraven } 1641227825Stheraven return end(); 1642227825Stheraven} 1643227825Stheraven 1644227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1645227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1646227825Stheraven 1647227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1648227825Stheraventemplate <class ..._Args> 1649227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1650227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 1651227825Stheraven{ 1652227825Stheraven __node_allocator& __na = __node_alloc(); 1653232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1654227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1655227825Stheraven __h.get_deleter().__value_constructed = true; 1656227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 1657227825Stheraven __h->__next_ = nullptr; 1658227825Stheraven return __h; 1659227825Stheraven} 1660227825Stheraven 1661227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1662227825Stheraven 1663227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1664227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1665227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 1666227825Stheraven size_t __hash) 1667227825Stheraven{ 1668227825Stheraven __node_allocator& __na = __node_alloc(); 1669232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1670227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1671227825Stheraven __h.get_deleter().__value_constructed = true; 1672227825Stheraven __h->__hash_ = __hash; 1673227825Stheraven __h->__next_ = nullptr; 1674227825Stheraven return _VSTD::move(__h); 1675227825Stheraven} 1676227825Stheraven 1677227825Stheraven#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1678227825Stheraven 1679227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1680227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1681227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 1682227825Stheraven{ 1683227825Stheraven __node_allocator& __na = __node_alloc(); 1684232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1685227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1686227825Stheraven __h.get_deleter().__value_constructed = true; 1687227825Stheraven __h->__hash_ = hash_function()(__h->__value_); 1688227825Stheraven __h->__next_ = nullptr; 1689227825Stheraven return _VSTD::move(__h); 1690227825Stheraven} 1691227825Stheraven 1692227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1693227825Stheraven 1694227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1695227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1696227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 1697227825Stheraven size_t __hash) 1698227825Stheraven{ 1699227825Stheraven __node_allocator& __na = __node_alloc(); 1700232924Stheraven __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1701227825Stheraven __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1702227825Stheraven __h.get_deleter().__value_constructed = true; 1703227825Stheraven __h->__hash_ = __hash; 1704227825Stheraven __h->__next_ = nullptr; 1705227825Stheraven return _VSTD::move(__h); 1706227825Stheraven} 1707227825Stheraven 1708227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1709227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1710227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 1711227825Stheraven{ 1712253146Stheraven __node_pointer __np = __p.__node_; 1713227825Stheraven iterator __r(__np); 1714227825Stheraven ++__r; 1715227825Stheraven remove(__p); 1716227825Stheraven return __r; 1717227825Stheraven} 1718227825Stheraven 1719227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1720227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1721227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 1722227825Stheraven const_iterator __last) 1723227825Stheraven{ 1724227825Stheraven for (const_iterator __p = __first; __first != __last; __p = __first) 1725227825Stheraven { 1726227825Stheraven ++__first; 1727227825Stheraven erase(__p); 1728227825Stheraven } 1729253146Stheraven __node_pointer __np = __last.__node_; 1730227825Stheraven return iterator (__np); 1731227825Stheraven} 1732227825Stheraven 1733227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1734227825Stheraventemplate <class _Key> 1735227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1736227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 1737227825Stheraven{ 1738227825Stheraven iterator __i = find(__k); 1739227825Stheraven if (__i == end()) 1740227825Stheraven return 0; 1741227825Stheraven erase(__i); 1742227825Stheraven return 1; 1743227825Stheraven} 1744227825Stheraven 1745227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1746227825Stheraventemplate <class _Key> 1747227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1748227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 1749227825Stheraven{ 1750227825Stheraven size_type __r = 0; 1751227825Stheraven iterator __i = find(__k); 1752227825Stheraven if (__i != end()) 1753227825Stheraven { 1754227825Stheraven iterator __e = end(); 1755227825Stheraven do 1756227825Stheraven { 1757227825Stheraven erase(__i++); 1758227825Stheraven ++__r; 1759227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 1760227825Stheraven } 1761227825Stheraven return __r; 1762227825Stheraven} 1763227825Stheraven 1764227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1765227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1766227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 1767227825Stheraven{ 1768227825Stheraven // current node 1769253146Stheraven __node_pointer __cn = __p.__node_; 1770227825Stheraven size_type __bc = bucket_count(); 1771241900Sdim size_t __chash = __constrain_hash(__cn->__hash_, __bc); 1772227825Stheraven // find previous node 1773227825Stheraven __node_pointer __pn = __bucket_list_[__chash]; 1774227825Stheraven for (; __pn->__next_ != __cn; __pn = __pn->__next_) 1775227825Stheraven ; 1776227825Stheraven // Fix up __bucket_list_ 1777227825Stheraven // if __pn is not in same bucket (before begin is not in same bucket) && 1778227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 1779253146Stheraven if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 1780253146Stheraven || __constrain_hash(__pn->__hash_, __bc) != __chash) 1781227825Stheraven { 1782241900Sdim if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 1783227825Stheraven __bucket_list_[__chash] = nullptr; 1784227825Stheraven } 1785227825Stheraven // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 1786227825Stheraven if (__cn->__next_ != nullptr) 1787227825Stheraven { 1788241900Sdim size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 1789227825Stheraven if (__nhash != __chash) 1790227825Stheraven __bucket_list_[__nhash] = __pn; 1791227825Stheraven } 1792227825Stheraven // remove __cn 1793227825Stheraven __pn->__next_ = __cn->__next_; 1794227825Stheraven __cn->__next_ = nullptr; 1795227825Stheraven --size(); 1796232924Stheraven return __node_holder(__cn, _Dp(__node_alloc(), true)); 1797227825Stheraven} 1798227825Stheraven 1799227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1800227825Stheraventemplate <class _Key> 1801227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1802227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1803227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 1804227825Stheraven{ 1805227825Stheraven return static_cast<size_type>(find(__k) != end()); 1806227825Stheraven} 1807227825Stheraven 1808227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1809227825Stheraventemplate <class _Key> 1810227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1811227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 1812227825Stheraven{ 1813227825Stheraven size_type __r = 0; 1814227825Stheraven const_iterator __i = find(__k); 1815227825Stheraven if (__i != end()) 1816227825Stheraven { 1817227825Stheraven const_iterator __e = end(); 1818227825Stheraven do 1819227825Stheraven { 1820227825Stheraven ++__i; 1821227825Stheraven ++__r; 1822227825Stheraven } while (__i != __e && key_eq()(*__i, __k)); 1823227825Stheraven } 1824227825Stheraven return __r; 1825227825Stheraven} 1826227825Stheraven 1827227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1828227825Stheraventemplate <class _Key> 1829227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 1830227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 1831227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 1832227825Stheraven const _Key& __k) 1833227825Stheraven{ 1834227825Stheraven iterator __i = find(__k); 1835227825Stheraven iterator __j = __i; 1836227825Stheraven if (__i != end()) 1837227825Stheraven ++__j; 1838227825Stheraven return pair<iterator, iterator>(__i, __j); 1839227825Stheraven} 1840227825Stheraven 1841227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1842227825Stheraventemplate <class _Key> 1843227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 1844227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 1845227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 1846227825Stheraven const _Key& __k) const 1847227825Stheraven{ 1848227825Stheraven const_iterator __i = find(__k); 1849227825Stheraven const_iterator __j = __i; 1850227825Stheraven if (__i != end()) 1851227825Stheraven ++__j; 1852227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 1853227825Stheraven} 1854227825Stheraven 1855227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1856227825Stheraventemplate <class _Key> 1857227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 1858227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 1859227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 1860227825Stheraven const _Key& __k) 1861227825Stheraven{ 1862227825Stheraven iterator __i = find(__k); 1863227825Stheraven iterator __j = __i; 1864227825Stheraven if (__i != end()) 1865227825Stheraven { 1866227825Stheraven iterator __e = end(); 1867227825Stheraven do 1868227825Stheraven { 1869227825Stheraven ++__j; 1870227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 1871227825Stheraven } 1872227825Stheraven return pair<iterator, iterator>(__i, __j); 1873227825Stheraven} 1874227825Stheraven 1875227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1876227825Stheraventemplate <class _Key> 1877227825Stheravenpair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 1878227825Stheraven typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 1879227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 1880227825Stheraven const _Key& __k) const 1881227825Stheraven{ 1882227825Stheraven const_iterator __i = find(__k); 1883227825Stheraven const_iterator __j = __i; 1884227825Stheraven if (__i != end()) 1885227825Stheraven { 1886227825Stheraven const_iterator __e = end(); 1887227825Stheraven do 1888227825Stheraven { 1889227825Stheraven ++__j; 1890227825Stheraven } while (__j != __e && key_eq()(*__j, __k)); 1891227825Stheraven } 1892227825Stheraven return pair<const_iterator, const_iterator>(__i, __j); 1893227825Stheraven} 1894227825Stheraven 1895227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1896227825Stheravenvoid 1897227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 1898227825Stheraven _NOEXCEPT_( 1899227825Stheraven (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 1900227825Stheraven __is_nothrow_swappable<__pointer_allocator>::value) && 1901227825Stheraven (!__node_traits::propagate_on_container_swap::value || 1902227825Stheraven __is_nothrow_swappable<__node_allocator>::value) && 1903227825Stheraven __is_nothrow_swappable<hasher>::value && 1904227825Stheraven __is_nothrow_swappable<key_equal>::value) 1905227825Stheraven{ 1906227825Stheraven { 1907227825Stheraven __node_pointer_pointer __npp = __bucket_list_.release(); 1908227825Stheraven __bucket_list_.reset(__u.__bucket_list_.release()); 1909227825Stheraven __u.__bucket_list_.reset(__npp); 1910227825Stheraven } 1911227825Stheraven _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 1912227825Stheraven __swap_alloc(__bucket_list_.get_deleter().__alloc(), 1913227825Stheraven __u.__bucket_list_.get_deleter().__alloc()); 1914227825Stheraven __swap_alloc(__node_alloc(), __u.__node_alloc()); 1915227825Stheraven _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 1916227825Stheraven __p2_.swap(__u.__p2_); 1917227825Stheraven __p3_.swap(__u.__p3_); 1918227825Stheraven if (size() > 0) 1919241900Sdim __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1920253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1921227825Stheraven if (__u.size() > 0) 1922241900Sdim __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 1923253146Stheraven static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 1924227825Stheraven} 1925227825Stheraven 1926227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1927227825Stheraventypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1928227825Stheraven__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 1929227825Stheraven{ 1930227825Stheraven __node_const_pointer __np = __bucket_list_[__n]; 1931227825Stheraven size_type __bc = bucket_count(); 1932227825Stheraven size_type __r = 0; 1933227825Stheraven if (__np != nullptr) 1934227825Stheraven { 1935227825Stheraven for (__np = __np->__next_; __np != nullptr && 1936241900Sdim __constrain_hash(__np->__hash_, __bc) == __n; 1937227825Stheraven __np = __np->__next_, ++__r) 1938227825Stheraven ; 1939227825Stheraven } 1940227825Stheraven return __r; 1941227825Stheraven} 1942227825Stheraven 1943227825Stheraventemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1944227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1945227825Stheravenvoid 1946227825Stheravenswap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 1947227825Stheraven __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 1948227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1949227825Stheraven{ 1950227825Stheraven __x.swap(__y); 1951227825Stheraven} 1952227825Stheraven 1953227825Stheraven_LIBCPP_END_NAMESPACE_STD 1954227825Stheraven 1955227825Stheraven#endif // _LIBCPP__HASH_TABLE 1956