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