__hash_table revision 249989
1829SN/A// -*- C++ -*- 27424SN/A//===----------------------------------------------------------------------===// 3829SN/A// 4829SN/A// The LLVM Compiler Infrastructure 5829SN/A// 6829SN/A// This file is dual licensed under the MIT and the University of Illinois Open 72362SN/A// Source Licenses. See LICENSE.TXT for details. 8829SN/A// 92362SN/A//===----------------------------------------------------------------------===// 10829SN/A 11829SN/A#ifndef _LIBCPP__HASH_TABLE 12829SN/A#define _LIBCPP__HASH_TABLE 13829SN/A 14829SN/A#include <__config> 15829SN/A#include <initializer_list> 16829SN/A#include <memory> 17829SN/A#include <iterator> 18829SN/A#include <algorithm> 19829SN/A#include <cmath> 20829SN/A 212362SN/A#include <__undef_min_max> 222362SN/A 232362SN/A#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 24829SN/A#pragma GCC system_header 2515409Sserb#endif 26829SN/A 27829SN/A_LIBCPP_BEGIN_NAMESPACE_STD 28829SN/A 29829SN/A_LIBCPP_FUNC_VIS 30829SN/Asize_t __next_prime(size_t __n); 31829SN/A 32829SN/Atemplate <class _NodePtr> 33829SN/Astruct __hash_node_base 34829SN/A{ 35829SN/A typedef __hash_node_base __first_node; 36829SN/A // typedef _NodePtr pointer; 37829SN/A 38829SN/A _NodePtr __next_; 397424SN/A 40829SN/A _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 4112839Sprr}; 42829SN/A 43829SN/Atemplate <class _Tp, class _VoidPtr> 44829SN/Astruct __hash_node 45829SN/A : public __hash_node_base 46829SN/A < 47829SN/A typename pointer_traits<_VoidPtr>::template 48829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 49829SN/A rebind<__hash_node<_Tp, _VoidPtr> > 50829SN/A#else 51829SN/A rebind<__hash_node<_Tp, _VoidPtr> >::other 52829SN/A#endif 53829SN/A > 54829SN/A{ 55829SN/A typedef _Tp value_type; 56829SN/A 57829SN/A size_t __hash_; 58829SN/A value_type __value_; 59829SN/A}; 60829SN/A 61829SN/Ainline _LIBCPP_INLINE_VISIBILITY 62829SN/Abool 63829SN/A__is_power2(size_t __bc) 64829SN/A{ 65829SN/A return __bc > 2 && !(__bc & (__bc - 1)); 66829SN/A} 67829SN/A 68829SN/Ainline _LIBCPP_INLINE_VISIBILITY 69829SN/Asize_t 70829SN/A__constrain_hash(size_t __h, size_t __bc) 71829SN/A{ 72829SN/A return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 73829SN/A} 74829SN/A 75829SN/Ainline _LIBCPP_INLINE_VISIBILITY 76829SN/Asize_t 77829SN/A__next_pow2(size_t __n) 78829SN/A{ 79829SN/A return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 80829SN/A} 81829SN/A 82829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 83829SN/Atemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_iterator; 84829SN/Atemplate <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_iterator; 85829SN/Atemplate <class _HashIterator> class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 86829SN/Atemplate <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 87829SN/A class _LIBCPP_TYPE_VIS unordered_map; 88829SN/A 89829SN/Atemplate <class _NodePtr> 90829SN/Aclass _LIBCPP_TYPE_VIS __hash_iterator 91829SN/A{ 92829SN/A typedef _NodePtr __node_pointer; 93829SN/A 94829SN/A __node_pointer __node_; 95829SN/A 96829SN/Apublic: 97829SN/A typedef forward_iterator_tag iterator_category; 98829SN/A typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 99829SN/A typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 100829SN/A typedef value_type& reference; 101829SN/A typedef typename pointer_traits<__node_pointer>::template 102829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 103829SN/A rebind<value_type> 104829SN/A#else 105829SN/A rebind<value_type>::other 106829SN/A#endif 107829SN/A pointer; 108829SN/A 109829SN/A _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT {} 110829SN/A 111829SN/A _LIBCPP_INLINE_VISIBILITY 112829SN/A reference operator*() const {return __node_->__value_;} 113829SN/A _LIBCPP_INLINE_VISIBILITY 114829SN/A pointer operator->() const {return _VSTD::addressof(__node_->__value_);} 115829SN/A 116829SN/A _LIBCPP_INLINE_VISIBILITY 117829SN/A __hash_iterator& operator++() 118829SN/A { 119829SN/A __node_ = __node_->__next_; 120829SN/A return *this; 121829SN/A } 122829SN/A 123829SN/A _LIBCPP_INLINE_VISIBILITY 124829SN/A __hash_iterator operator++(int) 125829SN/A { 126829SN/A __hash_iterator __t(*this); 127829SN/A ++(*this); 128829SN/A return __t; 129829SN/A } 130829SN/A 131829SN/A friend _LIBCPP_INLINE_VISIBILITY 132829SN/A bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 133829SN/A {return __x.__node_ == __y.__node_;} 134829SN/A friend _LIBCPP_INLINE_VISIBILITY 135829SN/A bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 136829SN/A {return __x.__node_ != __y.__node_;} 137829SN/A 138829SN/Aprivate: 139829SN/A _LIBCPP_INLINE_VISIBILITY 140829SN/A __hash_iterator(__node_pointer __node) _NOEXCEPT 141829SN/A : __node_(__node) 142829SN/A {} 143829SN/A 144829SN/A template <class, class, class, class> friend class __hash_table; 145829SN/A template <class> friend class _LIBCPP_TYPE_VIS __hash_const_iterator; 146829SN/A template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator; 147829SN/A template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 148829SN/A template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 149829SN/A}; 150829SN/A 151829SN/Atemplate <class _ConstNodePtr> 152829SN/Aclass _LIBCPP_TYPE_VIS __hash_const_iterator 153829SN/A{ 154829SN/A typedef _ConstNodePtr __node_pointer; 155829SN/A 156829SN/A __node_pointer __node_; 157829SN/A 158829SN/A typedef typename remove_const< 159829SN/A typename pointer_traits<__node_pointer>::element_type 160829SN/A >::type __node; 161829SN/A 162829SN/Apublic: 163829SN/A typedef forward_iterator_tag iterator_category; 164829SN/A typedef typename __node::value_type value_type; 165829SN/A typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 166829SN/A typedef const value_type& reference; 167829SN/A typedef typename pointer_traits<__node_pointer>::template 168829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 169829SN/A rebind<const value_type> 170829SN/A#else 171829SN/A rebind<const value_type>::other 172829SN/A#endif 173829SN/A pointer; 174829SN/A typedef typename pointer_traits<__node_pointer>::template 175829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 176829SN/A rebind<__node> 177829SN/A#else 178829SN/A rebind<__node>::other 179829SN/A#endif 180829SN/A __non_const_node_pointer; 181829SN/A typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 182829SN/A 183829SN/A _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT {} 184829SN/A _LIBCPP_INLINE_VISIBILITY 185829SN/A __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 186829SN/A : __node_(__x.__node_) 187829SN/A {} 188829SN/A 189829SN/A _LIBCPP_INLINE_VISIBILITY 190829SN/A reference operator*() const {return __node_->__value_;} 191829SN/A _LIBCPP_INLINE_VISIBILITY 192829SN/A pointer operator->() const {return _VSTD::addressof(__node_->__value_);} 193829SN/A 194829SN/A _LIBCPP_INLINE_VISIBILITY 195829SN/A __hash_const_iterator& operator++() 196829SN/A { 197829SN/A __node_ = __node_->__next_; 198829SN/A return *this; 199829SN/A } 200829SN/A 201829SN/A _LIBCPP_INLINE_VISIBILITY 202829SN/A __hash_const_iterator operator++(int) 203829SN/A { 204829SN/A __hash_const_iterator __t(*this); 205829SN/A ++(*this); 206829SN/A return __t; 207829SN/A } 208829SN/A 209829SN/A friend _LIBCPP_INLINE_VISIBILITY 210829SN/A bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 211829SN/A {return __x.__node_ == __y.__node_;} 212829SN/A friend _LIBCPP_INLINE_VISIBILITY 213829SN/A bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 214829SN/A {return __x.__node_ != __y.__node_;} 215829SN/A 216829SN/Aprivate: 217829SN/A _LIBCPP_INLINE_VISIBILITY 218829SN/A __hash_const_iterator(__node_pointer __node) _NOEXCEPT 219829SN/A : __node_(__node) 220829SN/A {} 221829SN/A 222829SN/A template <class, class, class, class> friend class __hash_table; 223829SN/A template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 224829SN/A template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_map; 225829SN/A template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS unordered_multimap; 226829SN/A}; 227829SN/A 228829SN/Atemplate <class _ConstNodePtr> class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 229829SN/A 230829SN/Atemplate <class _NodePtr> 231829SN/Aclass _LIBCPP_TYPE_VIS __hash_local_iterator 232829SN/A{ 233829SN/A typedef _NodePtr __node_pointer; 234829SN/A 235829SN/A __node_pointer __node_; 236829SN/A size_t __bucket_; 237829SN/A size_t __bucket_count_; 238829SN/A 239829SN/A typedef pointer_traits<__node_pointer> __pointer_traits; 240829SN/Apublic: 241829SN/A typedef forward_iterator_tag iterator_category; 242829SN/A typedef typename __pointer_traits::element_type::value_type value_type; 243829SN/A typedef typename __pointer_traits::difference_type difference_type; 244829SN/A typedef value_type& reference; 245829SN/A typedef typename __pointer_traits::template 246829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 247829SN/A rebind<value_type> 248829SN/A#else 249829SN/A rebind<value_type>::other 250829SN/A#endif 251829SN/A pointer; 252829SN/A 253829SN/A _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT {} 254829SN/A 255829SN/A _LIBCPP_INLINE_VISIBILITY 256829SN/A reference operator*() const {return __node_->__value_;} 257829SN/A _LIBCPP_INLINE_VISIBILITY 258829SN/A pointer operator->() const {return &__node_->__value_;} 259829SN/A 260829SN/A _LIBCPP_INLINE_VISIBILITY 261829SN/A __hash_local_iterator& operator++() 262829SN/A { 263829SN/A __node_ = __node_->__next_; 264829SN/A if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 265829SN/A __node_ = nullptr; 266829SN/A return *this; 267829SN/A } 268829SN/A 269829SN/A _LIBCPP_INLINE_VISIBILITY 270829SN/A __hash_local_iterator operator++(int) 271829SN/A { 272829SN/A __hash_local_iterator __t(*this); 273829SN/A ++(*this); 274829SN/A return __t; 275829SN/A } 276829SN/A 277829SN/A friend _LIBCPP_INLINE_VISIBILITY 278829SN/A bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 279829SN/A {return __x.__node_ == __y.__node_;} 280829SN/A friend _LIBCPP_INLINE_VISIBILITY 281829SN/A bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 282829SN/A {return __x.__node_ != __y.__node_;} 283829SN/A 284829SN/Aprivate: 285829SN/A _LIBCPP_INLINE_VISIBILITY 286829SN/A __hash_local_iterator(__node_pointer __node, size_t __bucket, 287829SN/A size_t __bucket_count) _NOEXCEPT 288829SN/A : __node_(__node), 289829SN/A __bucket_(__bucket), 290829SN/A __bucket_count_(__bucket_count) 291829SN/A { 292829SN/A if (__node_ != nullptr) 293829SN/A __node_ = __node_->__next_; 294829SN/A } 295829SN/A 296829SN/A template <class, class, class, class> friend class __hash_table; 297829SN/A template <class> friend class _LIBCPP_TYPE_VIS __hash_const_local_iterator; 298829SN/A template <class> friend class _LIBCPP_TYPE_VIS __hash_map_iterator; 299829SN/A}; 300829SN/A 301829SN/Atemplate <class _ConstNodePtr> 302829SN/Aclass _LIBCPP_TYPE_VIS __hash_const_local_iterator 303829SN/A{ 304829SN/A typedef _ConstNodePtr __node_pointer; 305829SN/A 306829SN/A __node_pointer __node_; 307829SN/A size_t __bucket_; 308829SN/A size_t __bucket_count_; 309829SN/A 310829SN/A typedef pointer_traits<__node_pointer> __pointer_traits; 311829SN/A typedef typename __pointer_traits::element_type __node; 312829SN/A typedef typename remove_const<__node>::type __non_const_node; 313829SN/A typedef typename pointer_traits<__node_pointer>::template 314829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 315829SN/A rebind<__non_const_node> 316829SN/A#else 317829SN/A rebind<__non_const_node>::other 318829SN/A#endif 319829SN/A __non_const_node_pointer; 320829SN/A typedef __hash_local_iterator<__non_const_node_pointer> 321829SN/A __non_const_iterator; 322829SN/Apublic: 323829SN/A typedef forward_iterator_tag iterator_category; 324829SN/A typedef typename remove_const< 325829SN/A typename __pointer_traits::element_type::value_type 326829SN/A >::type value_type; 327829SN/A typedef typename __pointer_traits::difference_type difference_type; 328829SN/A typedef const value_type& reference; 329829SN/A typedef typename __pointer_traits::template 330829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 331829SN/A rebind<const value_type> 332829SN/A#else 333829SN/A rebind<const value_type>::other 334829SN/A#endif 335829SN/A pointer; 336829SN/A 337829SN/A _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT {} 338829SN/A _LIBCPP_INLINE_VISIBILITY 339829SN/A __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 340829SN/A : __node_(__x.__node_), 341829SN/A __bucket_(__x.__bucket_), 342829SN/A __bucket_count_(__x.__bucket_count_) 343829SN/A {} 344829SN/A 345829SN/A _LIBCPP_INLINE_VISIBILITY 346829SN/A reference operator*() const {return __node_->__value_;} 347829SN/A _LIBCPP_INLINE_VISIBILITY 348829SN/A pointer operator->() const {return &__node_->__value_;} 349829SN/A 350829SN/A _LIBCPP_INLINE_VISIBILITY 351829SN/A __hash_const_local_iterator& operator++() 352829SN/A { 353829SN/A __node_ = __node_->__next_; 354829SN/A if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 355829SN/A __node_ = nullptr; 356829SN/A return *this; 357829SN/A } 358829SN/A 359829SN/A _LIBCPP_INLINE_VISIBILITY 360829SN/A __hash_const_local_iterator operator++(int) 361829SN/A { 362829SN/A __hash_const_local_iterator __t(*this); 363829SN/A ++(*this); 364829SN/A return __t; 365829SN/A } 366829SN/A 367829SN/A friend _LIBCPP_INLINE_VISIBILITY 368829SN/A bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 369829SN/A {return __x.__node_ == __y.__node_;} 370829SN/A friend _LIBCPP_INLINE_VISIBILITY 371829SN/A bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 372829SN/A {return __x.__node_ != __y.__node_;} 373829SN/A 374829SN/Aprivate: 375829SN/A _LIBCPP_INLINE_VISIBILITY 376829SN/A __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 377829SN/A size_t __bucket_count) _NOEXCEPT 378829SN/A : __node_(__node), 379829SN/A __bucket_(__bucket), 380829SN/A __bucket_count_(__bucket_count) 381829SN/A { 382829SN/A if (__node_ != nullptr) 383829SN/A __node_ = __node_->__next_; 384829SN/A } 385829SN/A 386829SN/A template <class, class, class, class> friend class __hash_table; 387829SN/A template <class> friend class _LIBCPP_TYPE_VIS __hash_map_const_iterator; 388829SN/A}; 389829SN/A 390829SN/Atemplate <class _Alloc> 391829SN/Aclass __bucket_list_deallocator 392829SN/A{ 393829SN/A typedef _Alloc allocator_type; 394829SN/A typedef allocator_traits<allocator_type> __alloc_traits; 395829SN/A typedef typename __alloc_traits::size_type size_type; 396829SN/A 397829SN/A __compressed_pair<size_type, allocator_type> __data_; 398829SN/Apublic: 399829SN/A typedef typename __alloc_traits::pointer pointer; 400829SN/A 401829SN/A _LIBCPP_INLINE_VISIBILITY 402829SN/A __bucket_list_deallocator() 403829SN/A _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 404829SN/A : __data_(0) {} 405829SN/A 406829SN/A _LIBCPP_INLINE_VISIBILITY 407829SN/A __bucket_list_deallocator(const allocator_type& __a, size_type __size) 408829SN/A _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 409829SN/A : __data_(__size, __a) {} 410829SN/A 411829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 412829SN/A 413829SN/A _LIBCPP_INLINE_VISIBILITY 414829SN/A __bucket_list_deallocator(__bucket_list_deallocator&& __x) 415829SN/A _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 416829SN/A : __data_(_VSTD::move(__x.__data_)) 417829SN/A { 418829SN/A __x.size() = 0; 419829SN/A } 420829SN/A 421829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 422829SN/A 423829SN/A _LIBCPP_INLINE_VISIBILITY 424829SN/A size_type& size() _NOEXCEPT {return __data_.first();} 425829SN/A _LIBCPP_INLINE_VISIBILITY 426829SN/A size_type size() const _NOEXCEPT {return __data_.first();} 427829SN/A 428829SN/A _LIBCPP_INLINE_VISIBILITY 429829SN/A allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 430829SN/A _LIBCPP_INLINE_VISIBILITY 431829SN/A const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 432829SN/A 433829SN/A _LIBCPP_INLINE_VISIBILITY 434829SN/A void operator()(pointer __p) _NOEXCEPT 435829SN/A { 436829SN/A __alloc_traits::deallocate(__alloc(), __p, size()); 437829SN/A } 438829SN/A}; 439829SN/A 440829SN/Atemplate <class _Alloc> class __hash_map_node_destructor; 441829SN/A 442829SN/Atemplate <class _Alloc> 443829SN/Aclass __hash_node_destructor 444829SN/A{ 445829SN/A typedef _Alloc allocator_type; 446829SN/A typedef allocator_traits<allocator_type> __alloc_traits; 447829SN/A typedef typename __alloc_traits::value_type::value_type value_type; 448829SN/Apublic: 449829SN/A typedef typename __alloc_traits::pointer pointer; 450829SN/Aprivate: 451829SN/A 452829SN/A allocator_type& __na_; 453829SN/A 454829SN/A __hash_node_destructor& operator=(const __hash_node_destructor&); 455829SN/A 456829SN/Apublic: 457829SN/A bool __value_constructed; 458829SN/A 459829SN/A _LIBCPP_INLINE_VISIBILITY 460829SN/A explicit __hash_node_destructor(allocator_type& __na, 461829SN/A bool __constructed = false) _NOEXCEPT 462829SN/A : __na_(__na), 463829SN/A __value_constructed(__constructed) 464829SN/A {} 465829SN/A 466829SN/A _LIBCPP_INLINE_VISIBILITY 467829SN/A void operator()(pointer __p) _NOEXCEPT 468829SN/A { 469829SN/A if (__value_constructed) 470829SN/A __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 471829SN/A if (__p) 472829SN/A __alloc_traits::deallocate(__na_, __p, 1); 473829SN/A } 474829SN/A 475829SN/A template <class> friend class __hash_map_node_destructor; 476829SN/A}; 477829SN/A 478829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 479829SN/Aclass __hash_table 480829SN/A{ 481829SN/Apublic: 482829SN/A typedef _Tp value_type; 483829SN/A typedef _Hash hasher; 484829SN/A typedef _Equal key_equal; 485829SN/A typedef _Alloc allocator_type; 486829SN/A 487829SN/Aprivate: 488829SN/A typedef allocator_traits<allocator_type> __alloc_traits; 489829SN/Apublic: 490829SN/A typedef value_type& reference; 491829SN/A typedef const value_type& const_reference; 492829SN/A typedef typename __alloc_traits::pointer pointer; 493829SN/A typedef typename __alloc_traits::const_pointer const_pointer; 494829SN/A typedef typename __alloc_traits::size_type size_type; 495829SN/A typedef typename __alloc_traits::difference_type difference_type; 496829SN/Apublic: 497829SN/A // Create __node 498829SN/A typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 499829SN/A typedef typename __alloc_traits::template 500829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 501829SN/A rebind_alloc<__node> 502829SN/A#else 503829SN/A rebind_alloc<__node>::other 504829SN/A#endif 505829SN/A __node_allocator; 506829SN/A typedef allocator_traits<__node_allocator> __node_traits; 507829SN/A typedef typename __node_traits::pointer __node_pointer; 508829SN/A typedef typename __node_traits::const_pointer __node_const_pointer; 509829SN/A typedef __hash_node_base<__node_pointer> __first_node; 510829SN/A 511829SN/Aprivate: 512829SN/A 513829SN/A typedef typename __node_traits::template 514829SN/A#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 515829SN/A rebind_alloc<__node_pointer> 516829SN/A#else 517829SN/A rebind_alloc<__node_pointer>::other 518829SN/A#endif 519829SN/A __pointer_allocator; 520829SN/A typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 521829SN/A typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 522829SN/A typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 523829SN/A typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 524829SN/A 525829SN/A // --- Member data begin --- 526829SN/A __bucket_list __bucket_list_; 527829SN/A __compressed_pair<__first_node, __node_allocator> __p1_; 528829SN/A __compressed_pair<size_type, hasher> __p2_; 529829SN/A __compressed_pair<float, key_equal> __p3_; 530829SN/A // --- Member data end --- 531829SN/A 532829SN/A _LIBCPP_INLINE_VISIBILITY 533829SN/A size_type& size() _NOEXCEPT {return __p2_.first();} 534829SN/Apublic: 535829SN/A _LIBCPP_INLINE_VISIBILITY 536829SN/A size_type size() const _NOEXCEPT {return __p2_.first();} 537829SN/A 538829SN/A _LIBCPP_INLINE_VISIBILITY 539829SN/A hasher& hash_function() _NOEXCEPT {return __p2_.second();} 540829SN/A _LIBCPP_INLINE_VISIBILITY 541829SN/A const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 542829SN/A 543829SN/A _LIBCPP_INLINE_VISIBILITY 544829SN/A float& max_load_factor() _NOEXCEPT {return __p3_.first();} 545829SN/A _LIBCPP_INLINE_VISIBILITY 546829SN/A float max_load_factor() const _NOEXCEPT {return __p3_.first();} 547829SN/A 548829SN/A _LIBCPP_INLINE_VISIBILITY 549829SN/A key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 550829SN/A _LIBCPP_INLINE_VISIBILITY 551829SN/A const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 552829SN/A 553829SN/A _LIBCPP_INLINE_VISIBILITY 554829SN/A __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 555829SN/A _LIBCPP_INLINE_VISIBILITY 556829SN/A const __node_allocator& __node_alloc() const _NOEXCEPT 557829SN/A {return __p1_.second();} 558829SN/A 559829SN/Apublic: 560829SN/A typedef __hash_iterator<__node_pointer> iterator; 561829SN/A typedef __hash_const_iterator<__node_const_pointer> const_iterator; 562829SN/A typedef __hash_local_iterator<__node_pointer> local_iterator; 563829SN/A typedef __hash_const_local_iterator<__node_const_pointer> const_local_iterator; 564829SN/A 565829SN/A __hash_table() 566829SN/A _NOEXCEPT_( 567829SN/A is_nothrow_default_constructible<__bucket_list>::value && 568829SN/A is_nothrow_default_constructible<__first_node>::value && 569829SN/A is_nothrow_default_constructible<__node_allocator>::value && 570829SN/A is_nothrow_default_constructible<hasher>::value && 571829SN/A is_nothrow_default_constructible<key_equal>::value); 572829SN/A __hash_table(const hasher& __hf, const key_equal& __eql); 573829SN/A __hash_table(const hasher& __hf, const key_equal& __eql, 574829SN/A const allocator_type& __a); 575829SN/A explicit __hash_table(const allocator_type& __a); 576829SN/A __hash_table(const __hash_table& __u); 577829SN/A __hash_table(const __hash_table& __u, const allocator_type& __a); 578829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 579829SN/A __hash_table(__hash_table&& __u) 580829SN/A _NOEXCEPT_( 581829SN/A is_nothrow_move_constructible<__bucket_list>::value && 582829SN/A is_nothrow_move_constructible<__first_node>::value && 583829SN/A is_nothrow_move_constructible<__node_allocator>::value && 584829SN/A is_nothrow_move_constructible<hasher>::value && 585829SN/A is_nothrow_move_constructible<key_equal>::value); 586829SN/A __hash_table(__hash_table&& __u, const allocator_type& __a); 587829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 588829SN/A ~__hash_table(); 589829SN/A 590829SN/A __hash_table& operator=(const __hash_table& __u); 591829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 592829SN/A __hash_table& operator=(__hash_table&& __u) 593829SN/A _NOEXCEPT_( 594829SN/A __node_traits::propagate_on_container_move_assignment::value && 595829SN/A is_nothrow_move_assignable<__node_allocator>::value && 596829SN/A is_nothrow_move_assignable<hasher>::value && 597829SN/A is_nothrow_move_assignable<key_equal>::value); 598829SN/A#endif 599829SN/A template <class _InputIterator> 600829SN/A void __assign_unique(_InputIterator __first, _InputIterator __last); 601829SN/A template <class _InputIterator> 602829SN/A void __assign_multi(_InputIterator __first, _InputIterator __last); 603829SN/A 604829SN/A _LIBCPP_INLINE_VISIBILITY 605829SN/A size_type max_size() const _NOEXCEPT 606829SN/A { 607829SN/A return allocator_traits<__pointer_allocator>::max_size( 608829SN/A __bucket_list_.get_deleter().__alloc()); 609829SN/A } 610829SN/A 611829SN/A pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 612829SN/A iterator __node_insert_multi(__node_pointer __nd); 613829SN/A iterator __node_insert_multi(const_iterator __p, 614829SN/A __node_pointer __nd); 615829SN/A 616829SN/A#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 617829SN/A template <class... _Args> 618829SN/A pair<iterator, bool> __emplace_unique(_Args&&... __args); 619829SN/A template <class... _Args> 620829SN/A iterator __emplace_multi(_Args&&... __args); 621829SN/A template <class... _Args> 622829SN/A iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 623829SN/A#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 624829SN/A 625829SN/A pair<iterator, bool> __insert_unique(const value_type& __x); 626829SN/A 627829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 628829SN/A template <class _Pp> 629829SN/A pair<iterator, bool> __insert_unique(_Pp&& __x); 630829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 631829SN/A 632829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 633829SN/A template <class _Pp> 634829SN/A iterator __insert_multi(_Pp&& __x); 635829SN/A template <class _Pp> 636829SN/A iterator __insert_multi(const_iterator __p, _Pp&& __x); 637829SN/A#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 638829SN/A iterator __insert_multi(const value_type& __x); 639829SN/A iterator __insert_multi(const_iterator __p, const value_type& __x); 640829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 641829SN/A 642829SN/A void clear() _NOEXCEPT; 643829SN/A void rehash(size_type __n); 644829SN/A _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 645829SN/A {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 646829SN/A 647829SN/A _LIBCPP_INLINE_VISIBILITY 648829SN/A size_type bucket_count() const _NOEXCEPT 649829SN/A { 650829SN/A return __bucket_list_.get_deleter().size(); 651829SN/A } 652829SN/A 653829SN/A iterator begin() _NOEXCEPT; 654829SN/A iterator end() _NOEXCEPT; 655829SN/A const_iterator begin() const _NOEXCEPT; 656829SN/A const_iterator end() const _NOEXCEPT; 657829SN/A 658829SN/A template <class _Key> 659829SN/A _LIBCPP_INLINE_VISIBILITY 660829SN/A size_type bucket(const _Key& __k) const 661829SN/A {return __constrain_hash(hash_function()(__k), bucket_count());} 662829SN/A 663829SN/A template <class _Key> 664829SN/A iterator find(const _Key& __x); 665829SN/A template <class _Key> 666829SN/A const_iterator find(const _Key& __x) const; 667829SN/A 668829SN/A typedef __hash_node_destructor<__node_allocator> _Dp; 669829SN/A typedef unique_ptr<__node, _Dp> __node_holder; 670829SN/A 671829SN/A iterator erase(const_iterator __p); 672829SN/A iterator erase(const_iterator __first, const_iterator __last); 673829SN/A template <class _Key> 674829SN/A size_type __erase_unique(const _Key& __k); 675829SN/A template <class _Key> 676829SN/A size_type __erase_multi(const _Key& __k); 677829SN/A __node_holder remove(const_iterator __p) _NOEXCEPT; 678829SN/A 679829SN/A template <class _Key> 680829SN/A size_type __count_unique(const _Key& __k) const; 681829SN/A template <class _Key> 682829SN/A size_type __count_multi(const _Key& __k) const; 683829SN/A 684829SN/A template <class _Key> 685829SN/A pair<iterator, iterator> 686829SN/A __equal_range_unique(const _Key& __k); 687829SN/A template <class _Key> 688829SN/A pair<const_iterator, const_iterator> 689829SN/A __equal_range_unique(const _Key& __k) const; 690829SN/A 691829SN/A template <class _Key> 692829SN/A pair<iterator, iterator> 693829SN/A __equal_range_multi(const _Key& __k); 694829SN/A template <class _Key> 695829SN/A pair<const_iterator, const_iterator> 696829SN/A __equal_range_multi(const _Key& __k) const; 697829SN/A 698829SN/A void swap(__hash_table& __u) 699829SN/A _NOEXCEPT_( 700829SN/A (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 701829SN/A __is_nothrow_swappable<__pointer_allocator>::value) && 702829SN/A (!__node_traits::propagate_on_container_swap::value || 703829SN/A __is_nothrow_swappable<__node_allocator>::value) && 704829SN/A __is_nothrow_swappable<hasher>::value && 705829SN/A __is_nothrow_swappable<key_equal>::value); 706829SN/A 707829SN/A _LIBCPP_INLINE_VISIBILITY 708829SN/A size_type max_bucket_count() const _NOEXCEPT 709829SN/A {return __bucket_list_.get_deleter().__alloc().max_size();} 710829SN/A size_type bucket_size(size_type __n) const; 711829SN/A _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 712829SN/A { 713829SN/A size_type __bc = bucket_count(); 714829SN/A return __bc != 0 ? (float)size() / __bc : 0.f; 715829SN/A } 716829SN/A _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 717829SN/A {max_load_factor() = _VSTD::max(__mlf, load_factor());} 718829SN/A 719829SN/A _LIBCPP_INLINE_VISIBILITY local_iterator begin(size_type __n) 720829SN/A {return local_iterator(__bucket_list_[__n], __n, bucket_count());} 721829SN/A _LIBCPP_INLINE_VISIBILITY local_iterator end(size_type __n) 722829SN/A {return local_iterator(nullptr, __n, bucket_count());} 723829SN/A _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const 724829SN/A {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());} 725829SN/A _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const 726829SN/A {return const_local_iterator(nullptr, __n, bucket_count());} 727829SN/Aprivate: 728829SN/A void __rehash(size_type __n); 729829SN/A 730829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 731829SN/A#ifndef _LIBCPP_HAS_NO_VARIADICS 732829SN/A template <class ..._Args> 733829SN/A __node_holder __construct_node(_Args&& ...__args); 734829SN/A#endif // _LIBCPP_HAS_NO_VARIADICS 735829SN/A __node_holder __construct_node(value_type&& __v, size_t __hash); 736829SN/A#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 737829SN/A __node_holder __construct_node(const value_type& __v); 738829SN/A#endif 739829SN/A __node_holder __construct_node(const value_type& __v, size_t __hash); 740829SN/A 741829SN/A _LIBCPP_INLINE_VISIBILITY 742829SN/A void __copy_assign_alloc(const __hash_table& __u) 743829SN/A {__copy_assign_alloc(__u, integral_constant<bool, 744829SN/A __node_traits::propagate_on_container_copy_assignment::value>());} 745829SN/A void __copy_assign_alloc(const __hash_table& __u, true_type); 746829SN/A _LIBCPP_INLINE_VISIBILITY 747829SN/A void __copy_assign_alloc(const __hash_table&, false_type) {} 748829SN/A 749829SN/A void __move_assign(__hash_table& __u, false_type); 750829SN/A void __move_assign(__hash_table& __u, true_type) 751829SN/A _NOEXCEPT_( 752829SN/A is_nothrow_move_assignable<__node_allocator>::value && 753829SN/A is_nothrow_move_assignable<hasher>::value && 754829SN/A is_nothrow_move_assignable<key_equal>::value); 755829SN/A _LIBCPP_INLINE_VISIBILITY 756829SN/A void __move_assign_alloc(__hash_table& __u) 757829SN/A _NOEXCEPT_( 758829SN/A !__node_traits::propagate_on_container_move_assignment::value || 759829SN/A (is_nothrow_move_assignable<__pointer_allocator>::value && 760829SN/A is_nothrow_move_assignable<__node_allocator>::value)) 761829SN/A {__move_assign_alloc(__u, integral_constant<bool, 762829SN/A __node_traits::propagate_on_container_move_assignment::value>());} 763829SN/A _LIBCPP_INLINE_VISIBILITY 764829SN/A void __move_assign_alloc(__hash_table& __u, true_type) 765829SN/A _NOEXCEPT_( 766829SN/A is_nothrow_move_assignable<__pointer_allocator>::value && 767829SN/A is_nothrow_move_assignable<__node_allocator>::value) 768829SN/A { 769829SN/A __bucket_list_.get_deleter().__alloc() = 770829SN/A _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 771829SN/A __node_alloc() = _VSTD::move(__u.__node_alloc()); 772829SN/A } 773829SN/A _LIBCPP_INLINE_VISIBILITY 774829SN/A void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 775829SN/A 776829SN/A template <class _Ap> 777829SN/A _LIBCPP_INLINE_VISIBILITY 778829SN/A static 779829SN/A void 780829SN/A __swap_alloc(_Ap& __x, _Ap& __y) 781829SN/A _NOEXCEPT_( 782829SN/A !allocator_traits<_Ap>::propagate_on_container_swap::value || 783829SN/A __is_nothrow_swappable<_Ap>::value) 784829SN/A { 785829SN/A __swap_alloc(__x, __y, 786829SN/A integral_constant<bool, 787829SN/A allocator_traits<_Ap>::propagate_on_container_swap::value 788829SN/A >()); 789829SN/A } 790829SN/A 791829SN/A template <class _Ap> 792829SN/A _LIBCPP_INLINE_VISIBILITY 793829SN/A static 794829SN/A void 795829SN/A __swap_alloc(_Ap& __x, _Ap& __y, true_type) 796829SN/A _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 797829SN/A { 798829SN/A using _VSTD::swap; 799829SN/A swap(__x, __y); 800829SN/A } 801829SN/A 802829SN/A template <class _Ap> 803829SN/A _LIBCPP_INLINE_VISIBILITY 804829SN/A static 805829SN/A void 806829SN/A __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 807829SN/A 808829SN/A void __deallocate(__node_pointer __np) _NOEXCEPT; 809829SN/A __node_pointer __detach() _NOEXCEPT; 810829SN/A}; 811829SN/A 812829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 813829SN/Ainline _LIBCPP_INLINE_VISIBILITY 814829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 815829SN/A _NOEXCEPT_( 816829SN/A is_nothrow_default_constructible<__bucket_list>::value && 817829SN/A is_nothrow_default_constructible<__first_node>::value && 818829SN/A is_nothrow_default_constructible<hasher>::value && 819829SN/A is_nothrow_default_constructible<key_equal>::value) 820829SN/A : __p2_(0), 821829SN/A __p3_(1.0f) 822829SN/A{ 823829SN/A} 824829SN/A 825829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 826829SN/Ainline _LIBCPP_INLINE_VISIBILITY 827829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 828829SN/A const key_equal& __eql) 829829SN/A : __bucket_list_(nullptr, __bucket_list_deleter()), 830829SN/A __p1_(), 831829SN/A __p2_(0, __hf), 832829SN/A __p3_(1.0f, __eql) 833829SN/A{ 834829SN/A} 835829SN/A 836829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 837829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 838829SN/A const key_equal& __eql, 839829SN/A const allocator_type& __a) 840829SN/A : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 841829SN/A __p1_(__node_allocator(__a)), 842829SN/A __p2_(0, __hf), 843829SN/A __p3_(1.0f, __eql) 844829SN/A{ 845829SN/A} 846829SN/A 847829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 848829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 849829SN/A : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 850829SN/A __p1_(__node_allocator(__a)), 851829SN/A __p2_(0), 852829SN/A __p3_(1.0f) 853829SN/A{ 854829SN/A} 855829SN/A 856829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 857829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 858829SN/A : __bucket_list_(nullptr, 859829SN/A __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 860829SN/A select_on_container_copy_construction( 861829SN/A __u.__bucket_list_.get_deleter().__alloc()), 0)), 862829SN/A __p1_(allocator_traits<__node_allocator>:: 863829SN/A select_on_container_copy_construction(__u.__node_alloc())), 864829SN/A __p2_(0, __u.hash_function()), 865829SN/A __p3_(__u.__p3_) 866829SN/A{ 867829SN/A} 868829SN/A 869829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 870829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 871829SN/A const allocator_type& __a) 872829SN/A : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 873829SN/A __p1_(__node_allocator(__a)), 874829SN/A __p2_(0, __u.hash_function()), 875829SN/A __p3_(__u.__p3_) 876829SN/A{ 877829SN/A} 878829SN/A 879829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 880829SN/A 881829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 882829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 883829SN/A _NOEXCEPT_( 884829SN/A is_nothrow_move_constructible<__bucket_list>::value && 885829SN/A is_nothrow_move_constructible<__first_node>::value && 886829SN/A is_nothrow_move_constructible<hasher>::value && 887829SN/A is_nothrow_move_constructible<key_equal>::value) 888829SN/A : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 889829SN/A __p1_(_VSTD::move(__u.__p1_)), 890829SN/A __p2_(_VSTD::move(__u.__p2_)), 891829SN/A __p3_(_VSTD::move(__u.__p3_)) 892829SN/A{ 893829SN/A if (size() > 0) 894829SN/A { 895829SN/A __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 896829SN/A static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 897829SN/A __u.__p1_.first().__next_ = nullptr; 898829SN/A __u.size() = 0; 899829SN/A } 900829SN/A} 901829SN/A 902829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 903829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 904829SN/A const allocator_type& __a) 905829SN/A : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 906829SN/A __p1_(__node_allocator(__a)), 907829SN/A __p2_(0, _VSTD::move(__u.hash_function())), 908829SN/A __p3_(_VSTD::move(__u.__p3_)) 909829SN/A{ 910829SN/A if (__a == allocator_type(__u.__node_alloc())) 911829SN/A { 912829SN/A __bucket_list_.reset(__u.__bucket_list_.release()); 913829SN/A __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 914829SN/A __u.__bucket_list_.get_deleter().size() = 0; 915829SN/A if (__u.size() > 0) 916829SN/A { 917829SN/A __p1_.first().__next_ = __u.__p1_.first().__next_; 918829SN/A __u.__p1_.first().__next_ = nullptr; 919829SN/A __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 920829SN/A static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 921829SN/A size() = __u.size(); 922829SN/A __u.size() = 0; 923829SN/A } 924829SN/A } 925829SN/A} 926829SN/A 927829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 928829SN/A 929829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 930829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 931829SN/A{ 932829SN/A __deallocate(__p1_.first().__next_); 933829SN/A} 934829SN/A 935829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 936829SN/Avoid 937829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 938829SN/A const __hash_table& __u, true_type) 939829SN/A{ 940829SN/A if (__node_alloc() != __u.__node_alloc()) 941829SN/A { 942829SN/A clear(); 943829SN/A __bucket_list_.reset(); 944829SN/A __bucket_list_.get_deleter().size() = 0; 945829SN/A } 946829SN/A __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 947829SN/A __node_alloc() = __u.__node_alloc(); 948829SN/A} 949829SN/A 950829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 951829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>& 952829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 953829SN/A{ 954829SN/A if (this != &__u) 955829SN/A { 956829SN/A __copy_assign_alloc(__u); 957829SN/A hash_function() = __u.hash_function(); 958829SN/A key_eq() = __u.key_eq(); 959829SN/A max_load_factor() = __u.max_load_factor(); 960829SN/A __assign_multi(__u.begin(), __u.end()); 961829SN/A } 962829SN/A return *this; 963829SN/A} 964829SN/A 965829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 966829SN/Avoid 967829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 968829SN/A _NOEXCEPT 969829SN/A{ 970829SN/A __node_allocator& __na = __node_alloc(); 971829SN/A while (__np != nullptr) 972829SN/A { 973829SN/A __node_pointer __next = __np->__next_; 974829SN/A __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 975829SN/A __node_traits::deallocate(__na, __np, 1); 976829SN/A __np = __next; 977829SN/A } 978829SN/A} 979829SN/A 980829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 981829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 982829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 983829SN/A{ 984829SN/A size_type __bc = bucket_count(); 985829SN/A for (size_type __i = 0; __i < __bc; ++__i) 986829SN/A __bucket_list_[__i] = nullptr; 987829SN/A size() = 0; 988829SN/A __node_pointer __cache = __p1_.first().__next_; 989829SN/A __p1_.first().__next_ = nullptr; 990829SN/A return __cache; 991829SN/A} 992829SN/A 993829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 994829SN/A 995829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 996829SN/Avoid 997829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 998829SN/A __hash_table& __u, true_type) 999829SN/A _NOEXCEPT_( 1000829SN/A is_nothrow_move_assignable<__node_allocator>::value && 1001829SN/A is_nothrow_move_assignable<hasher>::value && 1002829SN/A is_nothrow_move_assignable<key_equal>::value) 1003829SN/A{ 1004829SN/A clear(); 1005829SN/A __bucket_list_.reset(__u.__bucket_list_.release()); 1006829SN/A __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1007829SN/A __u.__bucket_list_.get_deleter().size() = 0; 1008829SN/A __move_assign_alloc(__u); 1009829SN/A size() = __u.size(); 1010829SN/A hash_function() = _VSTD::move(__u.hash_function()); 1011829SN/A max_load_factor() = __u.max_load_factor(); 1012829SN/A key_eq() = _VSTD::move(__u.key_eq()); 1013829SN/A __p1_.first().__next_ = __u.__p1_.first().__next_; 1014829SN/A if (size() > 0) 1015829SN/A { 1016829SN/A __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1017829SN/A static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1018829SN/A __u.__p1_.first().__next_ = nullptr; 1019829SN/A __u.size() = 0; 1020829SN/A } 1021829SN/A} 1022829SN/A 1023829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1024829SN/Avoid 1025829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1026829SN/A __hash_table& __u, false_type) 1027829SN/A{ 1028829SN/A if (__node_alloc() == __u.__node_alloc()) 1029829SN/A __move_assign(__u, true_type()); 1030829SN/A else 1031829SN/A { 1032829SN/A hash_function() = _VSTD::move(__u.hash_function()); 1033829SN/A key_eq() = _VSTD::move(__u.key_eq()); 1034829SN/A max_load_factor() = __u.max_load_factor(); 1035829SN/A if (bucket_count() != 0) 1036829SN/A { 1037829SN/A __node_pointer __cache = __detach(); 1038829SN/A#ifndef _LIBCPP_NO_EXCEPTIONS 1039829SN/A try 1040829SN/A { 1041829SN/A#endif // _LIBCPP_NO_EXCEPTIONS 1042829SN/A const_iterator __i = __u.begin(); 1043829SN/A while (__cache != nullptr && __u.size() != 0) 1044829SN/A { 1045829SN/A __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1046829SN/A __node_pointer __next = __cache->__next_; 1047829SN/A __node_insert_multi(__cache); 1048829SN/A __cache = __next; 1049829SN/A } 1050829SN/A#ifndef _LIBCPP_NO_EXCEPTIONS 1051829SN/A } 1052829SN/A catch (...) 1053829SN/A { 1054829SN/A __deallocate(__cache); 1055829SN/A throw; 1056829SN/A } 1057829SN/A#endif // _LIBCPP_NO_EXCEPTIONS 1058829SN/A __deallocate(__cache); 1059829SN/A } 1060829SN/A const_iterator __i = __u.begin(); 1061829SN/A while (__u.size() != 0) 1062829SN/A { 1063829SN/A __node_holder __h = 1064829SN/A __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1065829SN/A __node_insert_multi(__h.get()); 1066829SN/A __h.release(); 1067829SN/A } 1068829SN/A } 1069829SN/A} 1070829SN/A 1071829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1072829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1073829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1074829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1075829SN/A _NOEXCEPT_( 1076829SN/A __node_traits::propagate_on_container_move_assignment::value && 1077829SN/A is_nothrow_move_assignable<__node_allocator>::value && 1078829SN/A is_nothrow_move_assignable<hasher>::value && 1079829SN/A is_nothrow_move_assignable<key_equal>::value) 1080829SN/A{ 1081829SN/A __move_assign(__u, integral_constant<bool, 1082829SN/A __node_traits::propagate_on_container_move_assignment::value>()); 1083829SN/A return *this; 1084829SN/A} 1085829SN/A 1086829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1087829SN/A 1088829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1089829SN/Atemplate <class _InputIterator> 1090829SN/Avoid 1091829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1092829SN/A _InputIterator __last) 1093829SN/A{ 1094829SN/A if (bucket_count() != 0) 1095829SN/A { 1096829SN/A __node_pointer __cache = __detach(); 1097829SN/A#ifndef _LIBCPP_NO_EXCEPTIONS 1098829SN/A try 1099829SN/A { 1100829SN/A#endif // _LIBCPP_NO_EXCEPTIONS 1101829SN/A for (; __cache != nullptr && __first != __last; ++__first) 1102829SN/A { 1103829SN/A __cache->__value_ = *__first; 1104829SN/A __node_pointer __next = __cache->__next_; 1105829SN/A __node_insert_unique(__cache); 1106829SN/A __cache = __next; 1107829SN/A } 1108829SN/A#ifndef _LIBCPP_NO_EXCEPTIONS 1109829SN/A } 1110829SN/A catch (...) 1111829SN/A { 1112829SN/A __deallocate(__cache); 1113829SN/A throw; 1114829SN/A } 1115829SN/A#endif // _LIBCPP_NO_EXCEPTIONS 1116829SN/A __deallocate(__cache); 1117829SN/A } 1118829SN/A for (; __first != __last; ++__first) 1119829SN/A __insert_unique(*__first); 1120829SN/A} 1121829SN/A 1122829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1123829SN/Atemplate <class _InputIterator> 1124829SN/Avoid 1125829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1126829SN/A _InputIterator __last) 1127829SN/A{ 1128829SN/A if (bucket_count() != 0) 1129829SN/A { 1130829SN/A __node_pointer __cache = __detach(); 1131829SN/A#ifndef _LIBCPP_NO_EXCEPTIONS 1132829SN/A try 1133829SN/A { 1134829SN/A#endif // _LIBCPP_NO_EXCEPTIONS 1135829SN/A for (; __cache != nullptr && __first != __last; ++__first) 1136829SN/A { 1137829SN/A __cache->__value_ = *__first; 1138829SN/A __node_pointer __next = __cache->__next_; 1139829SN/A __node_insert_multi(__cache); 1140829SN/A __cache = __next; 1141829SN/A } 1142829SN/A#ifndef _LIBCPP_NO_EXCEPTIONS 1143829SN/A } 1144829SN/A catch (...) 1145829SN/A { 1146829SN/A __deallocate(__cache); 1147829SN/A throw; 1148829SN/A } 1149829SN/A#endif // _LIBCPP_NO_EXCEPTIONS 1150829SN/A __deallocate(__cache); 1151829SN/A } 1152829SN/A for (; __first != __last; ++__first) 1153829SN/A __insert_multi(*__first); 1154829SN/A} 1155829SN/A 1156829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1157829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1158829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1159829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1160829SN/A{ 1161829SN/A return iterator(__p1_.first().__next_); 1162829SN/A} 1163829SN/A 1164829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1165829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1166829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1167829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1168829SN/A{ 1169829SN/A return iterator(nullptr); 1170829SN/A} 1171829SN/A 1172829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1173829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1174829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1175829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1176829SN/A{ 1177829SN/A return const_iterator(__p1_.first().__next_); 1178829SN/A} 1179829SN/A 1180829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1181829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1182829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1183829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1184829SN/A{ 1185829SN/A return const_iterator(nullptr); 1186829SN/A} 1187829SN/A 1188829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1189829SN/Avoid 1190829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1191829SN/A{ 1192829SN/A if (size() > 0) 1193829SN/A { 1194829SN/A __deallocate(__p1_.first().__next_); 1195829SN/A __p1_.first().__next_ = nullptr; 1196829SN/A size_type __bc = bucket_count(); 1197829SN/A for (size_type __i = 0; __i < __bc; ++__i) 1198829SN/A __bucket_list_[__i] = nullptr; 1199829SN/A size() = 0; 1200829SN/A } 1201829SN/A} 1202829SN/A 1203829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1204829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1205829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1206829SN/A{ 1207829SN/A __nd->__hash_ = hash_function()(__nd->__value_); 1208829SN/A size_type __bc = bucket_count(); 1209829SN/A bool __inserted = false; 1210829SN/A __node_pointer __ndptr; 1211829SN/A size_t __chash; 1212829SN/A if (__bc != 0) 1213829SN/A { 1214829SN/A __chash = __constrain_hash(__nd->__hash_, __bc); 1215829SN/A __ndptr = __bucket_list_[__chash]; 1216829SN/A if (__ndptr != nullptr) 1217829SN/A { 1218829SN/A for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1219829SN/A __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1220829SN/A __ndptr = __ndptr->__next_) 1221829SN/A { 1222829SN/A if (key_eq()(__ndptr->__value_, __nd->__value_)) 1223829SN/A goto __done; 1224829SN/A } 1225829SN/A } 1226829SN/A } 1227829SN/A { 1228829SN/A if (size()+1 > __bc * max_load_factor() || __bc == 0) 1229829SN/A { 1230829SN/A rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1231829SN/A size_type(ceil(float(size() + 1) / max_load_factor())))); 1232829SN/A __bc = bucket_count(); 1233829SN/A __chash = __constrain_hash(__nd->__hash_, __bc); 1234829SN/A } 1235829SN/A // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1236829SN/A __node_pointer __pn = __bucket_list_[__chash]; 1237829SN/A if (__pn == nullptr) 1238829SN/A { 1239829SN/A __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1240829SN/A __nd->__next_ = __pn->__next_; 1241829SN/A __pn->__next_ = __nd; 1242829SN/A // fix up __bucket_list_ 1243829SN/A __bucket_list_[__chash] = __pn; 1244829SN/A if (__nd->__next_ != nullptr) 1245829SN/A __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1246829SN/A } 1247829SN/A else 1248829SN/A { 1249829SN/A __nd->__next_ = __pn->__next_; 1250829SN/A __pn->__next_ = __nd; 1251829SN/A } 1252829SN/A __ndptr = __nd; 1253829SN/A // increment size 1254829SN/A ++size(); 1255829SN/A __inserted = true; 1256829SN/A } 1257829SN/A__done: 1258829SN/A return pair<iterator, bool>(iterator(__ndptr), __inserted); 1259829SN/A} 1260829SN/A 1261829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1262829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1263829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1264829SN/A{ 1265829SN/A __cp->__hash_ = hash_function()(__cp->__value_); 1266829SN/A size_type __bc = bucket_count(); 1267829SN/A if (size()+1 > __bc * max_load_factor() || __bc == 0) 1268829SN/A { 1269829SN/A rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1270829SN/A size_type(ceil(float(size() + 1) / max_load_factor())))); 1271829SN/A __bc = bucket_count(); 1272829SN/A } 1273829SN/A size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1274829SN/A __node_pointer __pn = __bucket_list_[__chash]; 1275829SN/A if (__pn == nullptr) 1276829SN/A { 1277829SN/A __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1278829SN/A __cp->__next_ = __pn->__next_; 1279829SN/A __pn->__next_ = __cp; 1280829SN/A // fix up __bucket_list_ 1281829SN/A __bucket_list_[__chash] = __pn; 1282829SN/A if (__cp->__next_ != nullptr) 1283829SN/A __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1284829SN/A } 1285829SN/A else 1286829SN/A { 1287829SN/A for (bool __found = false; __pn->__next_ != nullptr && 1288829SN/A __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1289829SN/A __pn = __pn->__next_) 1290829SN/A { 1291829SN/A // __found key_eq() action 1292829SN/A // false false loop 1293829SN/A // true true loop 1294829SN/A // false true set __found to true 1295829SN/A // true false break 1296829SN/A if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1297829SN/A key_eq()(__pn->__next_->__value_, __cp->__value_))) 1298829SN/A { 1299829SN/A if (!__found) 1300829SN/A __found = true; 1301829SN/A else 1302829SN/A break; 1303829SN/A } 1304829SN/A } 1305829SN/A __cp->__next_ = __pn->__next_; 1306829SN/A __pn->__next_ = __cp; 1307829SN/A if (__cp->__next_ != nullptr) 1308829SN/A { 1309829SN/A size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1310829SN/A if (__nhash != __chash) 1311829SN/A __bucket_list_[__nhash] = __cp; 1312829SN/A } 1313829SN/A } 1314829SN/A ++size(); 1315829SN/A return iterator(__cp); 1316829SN/A} 1317829SN/A 1318829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1319829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1320829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1321829SN/A const_iterator __p, __node_pointer __cp) 1322829SN/A{ 1323829SN/A if (__p != end() && key_eq()(*__p, __cp->__value_)) 1324829SN/A { 1325829SN/A __node_pointer __np = const_cast<__node_pointer>(__p.__node_); 1326829SN/A __cp->__hash_ = __np->__hash_; 1327829SN/A size_type __bc = bucket_count(); 1328829SN/A if (size()+1 > __bc * max_load_factor() || __bc == 0) 1329829SN/A { 1330829SN/A rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1331829SN/A size_type(ceil(float(size() + 1) / max_load_factor())))); 1332829SN/A __bc = bucket_count(); 1333829SN/A } 1334829SN/A size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1335829SN/A __node_pointer __pp = __bucket_list_[__chash]; 1336829SN/A while (__pp->__next_ != __np) 1337829SN/A __pp = __pp->__next_; 1338829SN/A __cp->__next_ = __np; 1339829SN/A __pp->__next_ = __cp; 1340829SN/A ++size(); 1341829SN/A return iterator(__cp); 1342829SN/A } 1343829SN/A return __node_insert_multi(__cp); 1344829SN/A} 1345829SN/A 1346829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1347829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1348829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1349829SN/A{ 1350829SN/A size_t __hash = hash_function()(__x); 1351829SN/A size_type __bc = bucket_count(); 1352829SN/A bool __inserted = false; 1353829SN/A __node_pointer __nd; 1354829SN/A size_t __chash; 1355829SN/A if (__bc != 0) 1356829SN/A { 1357829SN/A __chash = __constrain_hash(__hash, __bc); 1358829SN/A __nd = __bucket_list_[__chash]; 1359829SN/A if (__nd != nullptr) 1360829SN/A { 1361829SN/A for (__nd = __nd->__next_; __nd != nullptr && 1362829SN/A __constrain_hash(__nd->__hash_, __bc) == __chash; 1363829SN/A __nd = __nd->__next_) 1364829SN/A { 1365829SN/A if (key_eq()(__nd->__value_, __x)) 1366829SN/A goto __done; 1367829SN/A } 1368829SN/A } 1369829SN/A } 1370829SN/A { 1371829SN/A __node_holder __h = __construct_node(__x, __hash); 1372829SN/A if (size()+1 > __bc * max_load_factor() || __bc == 0) 1373829SN/A { 1374829SN/A rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1375829SN/A size_type(ceil(float(size() + 1) / max_load_factor())))); 1376829SN/A __bc = bucket_count(); 1377829SN/A __chash = __constrain_hash(__hash, __bc); 1378829SN/A } 1379829SN/A // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1380829SN/A __node_pointer __pn = __bucket_list_[__chash]; 1381829SN/A if (__pn == nullptr) 1382829SN/A { 1383829SN/A __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1384829SN/A __h->__next_ = __pn->__next_; 1385829SN/A __pn->__next_ = __h.get(); 1386829SN/A // fix up __bucket_list_ 1387829SN/A __bucket_list_[__chash] = __pn; 1388829SN/A if (__h->__next_ != nullptr) 1389829SN/A __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1390829SN/A } 1391829SN/A else 1392829SN/A { 1393829SN/A __h->__next_ = __pn->__next_; 1394829SN/A __pn->__next_ = __h.get(); 1395829SN/A } 1396829SN/A __nd = __h.release(); 1397829SN/A // increment size 1398829SN/A ++size(); 1399829SN/A __inserted = true; 1400829SN/A } 1401829SN/A__done: 1402829SN/A return pair<iterator, bool>(iterator(__nd), __inserted); 1403829SN/A} 1404829SN/A 1405829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1406829SN/A#ifndef _LIBCPP_HAS_NO_VARIADICS 1407829SN/A 1408829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1409829SN/Atemplate <class... _Args> 1410829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1411829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1412829SN/A{ 1413829SN/A __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1414829SN/A pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1415829SN/A if (__r.second) 1416829SN/A __h.release(); 1417829SN/A return __r; 1418829SN/A} 1419829SN/A 1420829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1421829SN/Atemplate <class... _Args> 1422829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1423829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1424829SN/A{ 1425829SN/A __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1426829SN/A iterator __r = __node_insert_multi(__h.get()); 1427829SN/A __h.release(); 1428829SN/A return __r; 1429829SN/A} 1430829SN/A 1431829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1432829SN/Atemplate <class... _Args> 1433829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1434829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1435829SN/A const_iterator __p, _Args&&... __args) 1436829SN/A{ 1437829SN/A __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1438829SN/A iterator __r = __node_insert_multi(__p, __h.get()); 1439829SN/A __h.release(); 1440829SN/A return __r; 1441829SN/A} 1442829SN/A 1443829SN/A#endif // _LIBCPP_HAS_NO_VARIADICS 1444829SN/A 1445829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1446829SN/Atemplate <class _Pp> 1447829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1448829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1449829SN/A{ 1450829SN/A __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1451829SN/A pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1452829SN/A if (__r.second) 1453829SN/A __h.release(); 1454829SN/A return __r; 1455829SN/A} 1456829SN/A 1457829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1458829SN/A 1459829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1460829SN/A 1461829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1462829SN/Atemplate <class _Pp> 1463829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1464829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1465829SN/A{ 1466829SN/A __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1467829SN/A iterator __r = __node_insert_multi(__h.get()); 1468829SN/A __h.release(); 1469829SN/A return __r; 1470829SN/A} 1471829SN/A 1472829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1473829SN/Atemplate <class _Pp> 1474829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1475829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1476829SN/A _Pp&& __x) 1477829SN/A{ 1478829SN/A __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1479829SN/A iterator __r = __node_insert_multi(__p, __h.get()); 1480829SN/A __h.release(); 1481829SN/A return __r; 1482829SN/A} 1483829SN/A 1484829SN/A#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1485829SN/A 1486829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1487829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1488829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1489829SN/A{ 1490829SN/A __node_holder __h = __construct_node(__x); 1491829SN/A iterator __r = __node_insert_multi(__h.get()); 1492829SN/A __h.release(); 1493829SN/A return __r; 1494829SN/A} 1495829SN/A 1496829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1497829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1498829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1499829SN/A const value_type& __x) 1500829SN/A{ 1501829SN/A __node_holder __h = __construct_node(__x); 1502829SN/A iterator __r = __node_insert_multi(__p, __h.get()); 1503829SN/A __h.release(); 1504829SN/A return __r; 1505829SN/A} 1506829SN/A 1507829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1508829SN/A 1509829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1510829SN/Avoid 1511829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1512829SN/A{ 1513829SN/A if (__n == 1) 1514829SN/A __n = 2; 1515829SN/A else if (__n & (__n - 1)) 1516829SN/A __n = __next_prime(__n); 1517829SN/A size_type __bc = bucket_count(); 1518829SN/A if (__n > __bc) 1519829SN/A __rehash(__n); 1520829SN/A else if (__n < __bc) 1521829SN/A { 1522829SN/A __n = _VSTD::max<size_type> 1523829SN/A ( 1524829SN/A __n, 1525829SN/A __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1526829SN/A __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1527829SN/A ); 1528829SN/A if (__n < __bc) 1529829SN/A __rehash(__n); 1530829SN/A } 1531829SN/A} 1532829SN/A 1533829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1534829SN/Avoid 1535829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1536829SN/A{ 1537829SN/A __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1538829SN/A __bucket_list_.reset(__nbc > 0 ? 1539829SN/A __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1540829SN/A __bucket_list_.get_deleter().size() = __nbc; 1541829SN/A if (__nbc > 0) 1542829SN/A { 1543829SN/A for (size_type __i = 0; __i < __nbc; ++__i) 1544829SN/A __bucket_list_[__i] = nullptr; 1545829SN/A __node_pointer __pp(static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()))); 1546829SN/A __node_pointer __cp = __pp->__next_; 1547829SN/A if (__cp != nullptr) 1548829SN/A { 1549829SN/A size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1550829SN/A __bucket_list_[__chash] = __pp; 1551829SN/A size_type __phash = __chash; 1552829SN/A for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1553829SN/A __cp = __pp->__next_) 1554829SN/A { 1555829SN/A __chash = __constrain_hash(__cp->__hash_, __nbc); 1556829SN/A if (__chash == __phash) 1557829SN/A __pp = __cp; 1558829SN/A else 1559829SN/A { 1560829SN/A if (__bucket_list_[__chash] == nullptr) 1561829SN/A { 1562829SN/A __bucket_list_[__chash] = __pp; 1563829SN/A __pp = __cp; 1564829SN/A __phash = __chash; 1565829SN/A } 1566829SN/A else 1567829SN/A { 1568829SN/A __node_pointer __np = __cp; 1569829SN/A for (; __np->__next_ != nullptr && 1570829SN/A key_eq()(__cp->__value_, __np->__next_->__value_); 1571829SN/A __np = __np->__next_) 1572829SN/A ; 1573829SN/A __pp->__next_ = __np->__next_; 1574829SN/A __np->__next_ = __bucket_list_[__chash]->__next_; 1575829SN/A __bucket_list_[__chash]->__next_ = __cp; 1576829SN/A 1577829SN/A } 1578829SN/A } 1579829SN/A } 1580829SN/A } 1581829SN/A } 1582829SN/A} 1583829SN/A 1584829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1585829SN/Atemplate <class _Key> 1586829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1587829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 1588829SN/A{ 1589829SN/A size_t __hash = hash_function()(__k); 1590829SN/A size_type __bc = bucket_count(); 1591829SN/A if (__bc != 0) 1592829SN/A { 1593829SN/A size_t __chash = __constrain_hash(__hash, __bc); 1594829SN/A __node_pointer __nd = __bucket_list_[__chash]; 1595829SN/A if (__nd != nullptr) 1596829SN/A { 1597829SN/A for (__nd = __nd->__next_; __nd != nullptr && 1598829SN/A __constrain_hash(__nd->__hash_, __bc) == __chash; 1599829SN/A __nd = __nd->__next_) 1600829SN/A { 1601829SN/A if (key_eq()(__nd->__value_, __k)) 1602829SN/A return iterator(__nd); 1603829SN/A } 1604829SN/A } 1605829SN/A } 1606829SN/A return end(); 1607829SN/A} 1608829SN/A 1609829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1610829SN/Atemplate <class _Key> 1611829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1612829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 1613829SN/A{ 1614829SN/A size_t __hash = hash_function()(__k); 1615829SN/A size_type __bc = bucket_count(); 1616829SN/A if (__bc != 0) 1617829SN/A { 1618829SN/A size_t __chash = __constrain_hash(__hash, __bc); 1619829SN/A __node_const_pointer __nd = __bucket_list_[__chash]; 1620829SN/A if (__nd != nullptr) 1621829SN/A { 1622829SN/A for (__nd = __nd->__next_; __nd != nullptr && 1623829SN/A __constrain_hash(__nd->__hash_, __bc) == __chash; 1624829SN/A __nd = __nd->__next_) 1625829SN/A { 1626829SN/A if (key_eq()(__nd->__value_, __k)) 1627829SN/A return const_iterator(__nd); 1628829SN/A } 1629829SN/A } 1630829SN/A 1631829SN/A } 1632829SN/A return end(); 1633829SN/A} 1634829SN/A 1635829SN/A#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1636829SN/A#ifndef _LIBCPP_HAS_NO_VARIADICS 1637829SN/A 1638829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1639829SN/Atemplate <class ..._Args> 1640829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1641829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 1642829SN/A{ 1643829SN/A __node_allocator& __na = __node_alloc(); 1644829SN/A __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1645829SN/A __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1646829SN/A __h.get_deleter().__value_constructed = true; 1647829SN/A __h->__hash_ = hash_function()(__h->__value_); 1648829SN/A __h->__next_ = nullptr; 1649829SN/A return __h; 1650829SN/A} 1651829SN/A 1652829SN/A#endif // _LIBCPP_HAS_NO_VARIADICS 1653829SN/A 1654829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1655829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1656829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 1657829SN/A size_t __hash) 1658829SN/A{ 1659829SN/A __node_allocator& __na = __node_alloc(); 1660829SN/A __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1661829SN/A __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1662829SN/A __h.get_deleter().__value_constructed = true; 1663829SN/A __h->__hash_ = __hash; 1664829SN/A __h->__next_ = nullptr; 1665829SN/A return _VSTD::move(__h); 1666829SN/A} 1667829SN/A 1668829SN/A#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1669829SN/A 1670829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1671829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1672829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 1673829SN/A{ 1674829SN/A __node_allocator& __na = __node_alloc(); 1675829SN/A __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1676829SN/A __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1677829SN/A __h.get_deleter().__value_constructed = true; 1678829SN/A __h->__hash_ = hash_function()(__h->__value_); 1679829SN/A __h->__next_ = nullptr; 1680829SN/A return _VSTD::move(__h); 1681829SN/A} 1682829SN/A 1683829SN/A#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1684829SN/A 1685829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1686829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1687829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 1688829SN/A size_t __hash) 1689829SN/A{ 1690829SN/A __node_allocator& __na = __node_alloc(); 1691829SN/A __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1692829SN/A __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1693829SN/A __h.get_deleter().__value_constructed = true; 1694829SN/A __h->__hash_ = __hash; 1695829SN/A __h->__next_ = nullptr; 1696829SN/A return _VSTD::move(__h); 1697829SN/A} 1698829SN/A 1699829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1700829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1701829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 1702829SN/A{ 1703829SN/A __node_pointer __np = const_cast<__node_pointer>(__p.__node_); 1704829SN/A iterator __r(__np); 1705829SN/A ++__r; 1706829SN/A remove(__p); 1707829SN/A return __r; 1708829SN/A} 1709829SN/A 1710829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1711829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1712829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 1713829SN/A const_iterator __last) 1714829SN/A{ 1715829SN/A for (const_iterator __p = __first; __first != __last; __p = __first) 1716829SN/A { 1717829SN/A ++__first; 1718829SN/A erase(__p); 1719829SN/A } 1720829SN/A __node_pointer __np = const_cast<__node_pointer>(__last.__node_); 1721829SN/A return iterator (__np); 1722829SN/A} 1723829SN/A 1724829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1725829SN/Atemplate <class _Key> 1726829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1727829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 1728829SN/A{ 1729829SN/A iterator __i = find(__k); 1730829SN/A if (__i == end()) 1731829SN/A return 0; 1732829SN/A erase(__i); 1733829SN/A return 1; 1734829SN/A} 1735829SN/A 1736829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1737829SN/Atemplate <class _Key> 1738829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1739829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 1740829SN/A{ 1741829SN/A size_type __r = 0; 1742829SN/A iterator __i = find(__k); 1743829SN/A if (__i != end()) 1744829SN/A { 1745829SN/A iterator __e = end(); 1746829SN/A do 1747829SN/A { 1748829SN/A erase(__i++); 1749829SN/A ++__r; 1750829SN/A } while (__i != __e && key_eq()(*__i, __k)); 1751829SN/A } 1752829SN/A return __r; 1753829SN/A} 1754829SN/A 1755829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1756829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1757829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 1758829SN/A{ 1759829SN/A // current node 1760829SN/A __node_pointer __cn = const_cast<__node_pointer>(__p.__node_); 1761829SN/A size_type __bc = bucket_count(); 1762829SN/A size_t __chash = __constrain_hash(__cn->__hash_, __bc); 1763829SN/A // find previous node 1764829SN/A __node_pointer __pn = __bucket_list_[__chash]; 1765829SN/A for (; __pn->__next_ != __cn; __pn = __pn->__next_) 1766829SN/A ; 1767829SN/A // Fix up __bucket_list_ 1768829SN/A // if __pn is not in same bucket (before begin is not in same bucket) && 1769829SN/A // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 1770829SN/A if (__pn == _VSTD::addressof(__p1_.first()) || __constrain_hash(__pn->__hash_, __bc) != __chash) 1771829SN/A { 1772829SN/A if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 1773829SN/A __bucket_list_[__chash] = nullptr; 1774829SN/A } 1775829SN/A // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 1776829SN/A if (__cn->__next_ != nullptr) 1777829SN/A { 1778829SN/A size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 1779829SN/A if (__nhash != __chash) 1780829SN/A __bucket_list_[__nhash] = __pn; 1781829SN/A } 1782829SN/A // remove __cn 1783829SN/A __pn->__next_ = __cn->__next_; 1784829SN/A __cn->__next_ = nullptr; 1785829SN/A --size(); 1786829SN/A return __node_holder(__cn, _Dp(__node_alloc(), true)); 1787829SN/A} 1788829SN/A 1789829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1790829SN/Atemplate <class _Key> 1791829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1792829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1793829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 1794829SN/A{ 1795829SN/A return static_cast<size_type>(find(__k) != end()); 1796829SN/A} 1797829SN/A 1798829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1799829SN/Atemplate <class _Key> 1800829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1801829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 1802829SN/A{ 1803829SN/A size_type __r = 0; 1804829SN/A const_iterator __i = find(__k); 1805829SN/A if (__i != end()) 1806829SN/A { 1807829SN/A const_iterator __e = end(); 1808829SN/A do 1809829SN/A { 1810829SN/A ++__i; 1811829SN/A ++__r; 1812829SN/A } while (__i != __e && key_eq()(*__i, __k)); 1813829SN/A } 1814829SN/A return __r; 1815829SN/A} 1816829SN/A 1817829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1818829SN/Atemplate <class _Key> 1819829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 1820829SN/A typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 1821829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 1822829SN/A const _Key& __k) 1823829SN/A{ 1824829SN/A iterator __i = find(__k); 1825829SN/A iterator __j = __i; 1826829SN/A if (__i != end()) 1827829SN/A ++__j; 1828829SN/A return pair<iterator, iterator>(__i, __j); 1829829SN/A} 1830829SN/A 1831829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1832829SN/Atemplate <class _Key> 1833829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 1834829SN/A typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 1835829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 1836829SN/A const _Key& __k) const 1837829SN/A{ 1838829SN/A const_iterator __i = find(__k); 1839829SN/A const_iterator __j = __i; 1840829SN/A if (__i != end()) 1841829SN/A ++__j; 1842829SN/A return pair<const_iterator, const_iterator>(__i, __j); 1843829SN/A} 1844829SN/A 1845829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1846829SN/Atemplate <class _Key> 1847829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 1848829SN/A typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 1849829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 1850829SN/A const _Key& __k) 1851829SN/A{ 1852829SN/A iterator __i = find(__k); 1853829SN/A iterator __j = __i; 1854829SN/A if (__i != end()) 1855829SN/A { 1856829SN/A iterator __e = end(); 1857829SN/A do 1858829SN/A { 1859829SN/A ++__j; 1860829SN/A } while (__j != __e && key_eq()(*__j, __k)); 1861829SN/A } 1862829SN/A return pair<iterator, iterator>(__i, __j); 1863829SN/A} 1864829SN/A 1865829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1866829SN/Atemplate <class _Key> 1867829SN/Apair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 1868829SN/A typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 1869829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 1870829SN/A const _Key& __k) const 1871829SN/A{ 1872829SN/A const_iterator __i = find(__k); 1873829SN/A const_iterator __j = __i; 1874829SN/A if (__i != end()) 1875829SN/A { 1876829SN/A const_iterator __e = end(); 1877829SN/A do 1878829SN/A { 1879829SN/A ++__j; 1880829SN/A } while (__j != __e && key_eq()(*__j, __k)); 1881829SN/A } 1882829SN/A return pair<const_iterator, const_iterator>(__i, __j); 1883829SN/A} 1884829SN/A 1885829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1886829SN/Avoid 1887829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 1888829SN/A _NOEXCEPT_( 1889829SN/A (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 1890829SN/A __is_nothrow_swappable<__pointer_allocator>::value) && 1891829SN/A (!__node_traits::propagate_on_container_swap::value || 1892829SN/A __is_nothrow_swappable<__node_allocator>::value) && 1893829SN/A __is_nothrow_swappable<hasher>::value && 1894829SN/A __is_nothrow_swappable<key_equal>::value) 1895829SN/A{ 1896829SN/A { 1897829SN/A __node_pointer_pointer __npp = __bucket_list_.release(); 1898829SN/A __bucket_list_.reset(__u.__bucket_list_.release()); 1899829SN/A __u.__bucket_list_.reset(__npp); 1900829SN/A } 1901829SN/A _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 1902829SN/A __swap_alloc(__bucket_list_.get_deleter().__alloc(), 1903829SN/A __u.__bucket_list_.get_deleter().__alloc()); 1904829SN/A __swap_alloc(__node_alloc(), __u.__node_alloc()); 1905829SN/A _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 1906829SN/A __p2_.swap(__u.__p2_); 1907829SN/A __p3_.swap(__u.__p3_); 1908829SN/A if (size() > 0) 1909829SN/A __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1910829SN/A static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1911829SN/A if (__u.size() > 0) 1912829SN/A __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 1913829SN/A static_cast<__node_pointer>(_VSTD::addressof(__u.__p1_.first())); 1914829SN/A} 1915829SN/A 1916829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1917829SN/Atypename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1918829SN/A__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 1919829SN/A{ 1920829SN/A __node_const_pointer __np = __bucket_list_[__n]; 1921829SN/A size_type __bc = bucket_count(); 1922829SN/A size_type __r = 0; 1923829SN/A if (__np != nullptr) 1924829SN/A { 1925829SN/A for (__np = __np->__next_; __np != nullptr && 1926829SN/A __constrain_hash(__np->__hash_, __bc) == __n; 1927829SN/A __np = __np->__next_, ++__r) 1928829SN/A ; 1929829SN/A } 1930829SN/A return __r; 1931829SN/A} 1932829SN/A 1933829SN/Atemplate <class _Tp, class _Hash, class _Equal, class _Alloc> 1934829SN/Ainline _LIBCPP_INLINE_VISIBILITY 1935829SN/Avoid 1936829SN/Aswap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 1937829SN/A __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 1938829SN/A _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1939829SN/A{ 1940829SN/A __x.swap(__y); 1941829SN/A} 1942829SN/A 1943829SN/A_LIBCPP_END_NAMESPACE_STD 1944829SN/A 1945829SN/A#endif // _LIBCPP__HASH_TABLE 1946829SN/A