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