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