1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP__HASH_TABLE 12#define _LIBCPP__HASH_TABLE 13 14#include <__config> 15#include <initializer_list> 16#include <memory> 17#include <iterator> 18#include <algorithm> 19#include <cmath> 20 21#include <__undef_min_max> 22 23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 24#pragma GCC system_header 25#endif 26 27_LIBCPP_BEGIN_NAMESPACE_STD 28 29_LIBCPP_VISIBLE 30size_t __next_prime(size_t __n); 31 32template <class _NodePtr> 33struct __hash_node_base 34{ 35 typedef __hash_node_base __first_node; 36 // typedef _NodePtr pointer; 37 38 _NodePtr __next_; 39 40 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 41}; 42 43template <class _Tp, class _VoidPtr> 44struct __hash_node 45 : public __hash_node_base 46 < 47 typename pointer_traits<_VoidPtr>::template 48#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 49 rebind<__hash_node<_Tp, _VoidPtr> > 50#else 51 rebind<__hash_node<_Tp, _VoidPtr> >::other 52#endif 53 > 54{ 55 typedef _Tp value_type; 56 57 size_t __hash_; 58 value_type __value_; 59}; 60 61inline _LIBCPP_INLINE_VISIBILITY 62bool 63__is_power2(size_t __bc) 64{ 65 return __bc > 2 && !(__bc & (__bc - 1)); 66} 67 68inline _LIBCPP_INLINE_VISIBILITY 69size_t 70__constrain_hash(size_t __h, size_t __bc) 71{ 72 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 73} 74 75inline _LIBCPP_INLINE_VISIBILITY 76size_t 77__next_pow2(size_t __n) 78{ 79 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 80} 81 82template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 83template <class _ConstNodePtr> class _LIBCPP_VISIBLE __hash_const_iterator; 84template <class _HashIterator> class _LIBCPP_VISIBLE __hash_map_iterator; 85template <class _HashIterator> class _LIBCPP_VISIBLE __hash_map_const_iterator; 86template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 87 class _LIBCPP_VISIBLE unordered_map; 88 89template <class _NodePtr> 90class _LIBCPP_VISIBLE __hash_iterator 91{ 92 typedef _NodePtr __node_pointer; 93 94 __node_pointer __node_; 95 96public: 97 typedef forward_iterator_tag iterator_category; 98 typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 99 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 100 typedef value_type& reference; 101 typedef typename pointer_traits<__node_pointer>::template 102#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 103 rebind<value_type> 104#else 105 rebind<value_type>::other 106#endif 107 pointer; 108 109 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT {} 110 111 _LIBCPP_INLINE_VISIBILITY 112 reference operator*() const {return __node_->__value_;} 113 _LIBCPP_INLINE_VISIBILITY 114 pointer operator->() const {return _VSTD::addressof(__node_->__value_);} 115 116 _LIBCPP_INLINE_VISIBILITY 117 __hash_iterator& operator++() 118 { 119 __node_ = __node_->__next_; 120 return *this; 121 } 122 123 _LIBCPP_INLINE_VISIBILITY 124 __hash_iterator operator++(int) 125 { 126 __hash_iterator __t(*this); 127 ++(*this); 128 return __t; 129 } 130 131 friend _LIBCPP_INLINE_VISIBILITY 132 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 133 {return __x.__node_ == __y.__node_;} 134 friend _LIBCPP_INLINE_VISIBILITY 135 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 136 {return __x.__node_ != __y.__node_;} 137 138private: 139 _LIBCPP_INLINE_VISIBILITY 140 __hash_iterator(__node_pointer __node) _NOEXCEPT 141 : __node_(__node) 142 {} 143 144 template <class, class, class, class> friend class __hash_table; 145 template <class> friend class _LIBCPP_VISIBLE __hash_const_iterator; 146 template <class> friend class _LIBCPP_VISIBLE __hash_map_iterator; 147 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 148 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 149}; 150 151template <class _ConstNodePtr> 152class _LIBCPP_VISIBLE __hash_const_iterator 153{ 154 typedef _ConstNodePtr __node_pointer; 155 156 __node_pointer __node_; 157 158 typedef typename remove_const< 159 typename pointer_traits<__node_pointer>::element_type 160 >::type __node; 161 162public: 163 typedef forward_iterator_tag iterator_category; 164 typedef typename __node::value_type value_type; 165 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 166 typedef const value_type& reference; 167 typedef typename pointer_traits<__node_pointer>::template 168#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 169 rebind<const value_type> 170#else 171 rebind<const value_type>::other 172#endif 173 pointer; 174 typedef typename pointer_traits<__node_pointer>::template 175#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 176 rebind<__node> 177#else 178 rebind<__node>::other 179#endif 180 __non_const_node_pointer; 181 typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 182 183 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT {} 184 _LIBCPP_INLINE_VISIBILITY 185 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 186 : __node_(__x.__node_) 187 {} 188 189 _LIBCPP_INLINE_VISIBILITY 190 reference operator*() const {return __node_->__value_;} 191 _LIBCPP_INLINE_VISIBILITY 192 pointer operator->() const {return _VSTD::addressof(__node_->__value_);} 193 194 _LIBCPP_INLINE_VISIBILITY 195 __hash_const_iterator& operator++() 196 { 197 __node_ = __node_->__next_; 198 return *this; 199 } 200 201 _LIBCPP_INLINE_VISIBILITY 202 __hash_const_iterator operator++(int) 203 { 204 __hash_const_iterator __t(*this); 205 ++(*this); 206 return __t; 207 } 208 209 friend _LIBCPP_INLINE_VISIBILITY 210 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 211 {return __x.__node_ == __y.__node_;} 212 friend _LIBCPP_INLINE_VISIBILITY 213 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 214 {return __x.__node_ != __y.__node_;} 215 216private: 217 _LIBCPP_INLINE_VISIBILITY 218 __hash_const_iterator(__node_pointer __node) _NOEXCEPT 219 : __node_(__node) 220 {} 221 222 template <class, class, class, class> friend class __hash_table; 223 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; 224 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_map; 225 template <class, class, class, class, class> friend class _LIBCPP_VISIBLE unordered_multimap; 226}; 227 228template <class _ConstNodePtr> class _LIBCPP_VISIBLE __hash_const_local_iterator; 229 230template <class _NodePtr> 231class _LIBCPP_VISIBLE __hash_local_iterator 232{ 233 typedef _NodePtr __node_pointer; 234 235 __node_pointer __node_; 236 size_t __bucket_; 237 size_t __bucket_count_; 238 239 typedef pointer_traits<__node_pointer> __pointer_traits; 240public: 241 typedef forward_iterator_tag iterator_category; 242 typedef typename __pointer_traits::element_type::value_type value_type; 243 typedef typename __pointer_traits::difference_type difference_type; 244 typedef value_type& reference; 245 typedef typename __pointer_traits::template 246#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 247 rebind<value_type> 248#else 249 rebind<value_type>::other 250#endif 251 pointer; 252 253 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT {} 254 255 _LIBCPP_INLINE_VISIBILITY 256 reference operator*() const {return __node_->__value_;} 257 _LIBCPP_INLINE_VISIBILITY 258 pointer operator->() const {return &__node_->__value_;} 259 260 _LIBCPP_INLINE_VISIBILITY 261 __hash_local_iterator& operator++() 262 { 263 __node_ = __node_->__next_; 264 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 265 __node_ = nullptr; 266 return *this; 267 } 268 269 _LIBCPP_INLINE_VISIBILITY 270 __hash_local_iterator operator++(int) 271 { 272 __hash_local_iterator __t(*this); 273 ++(*this); 274 return __t; 275 } 276 277 friend _LIBCPP_INLINE_VISIBILITY 278 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 279 {return __x.__node_ == __y.__node_;} 280 friend _LIBCPP_INLINE_VISIBILITY 281 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 282 {return __x.__node_ != __y.__node_;} 283 284private: 285 _LIBCPP_INLINE_VISIBILITY 286 __hash_local_iterator(__node_pointer __node, size_t __bucket, 287 size_t __bucket_count) _NOEXCEPT 288 : __node_(__node), 289 __bucket_(__bucket), 290 __bucket_count_(__bucket_count) 291 { 292 if (__node_ != nullptr) 293 __node_ = __node_->__next_; 294 } 295 296 template <class, class, class, class> friend class __hash_table; 297 template <class> friend class _LIBCPP_VISIBLE __hash_const_local_iterator; 298 template <class> friend class _LIBCPP_VISIBLE __hash_map_iterator; 299}; 300 301template <class _ConstNodePtr> 302class _LIBCPP_VISIBLE __hash_const_local_iterator 303{ 304 typedef _ConstNodePtr __node_pointer; 305 306 __node_pointer __node_; 307 size_t __bucket_; 308 size_t __bucket_count_; 309 310 typedef pointer_traits<__node_pointer> __pointer_traits; 311 typedef typename __pointer_traits::element_type __node; 312 typedef typename remove_const<__node>::type __non_const_node; 313 typedef typename pointer_traits<__node_pointer>::template 314#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 315 rebind<__non_const_node> 316#else 317 rebind<__non_const_node>::other 318#endif 319 __non_const_node_pointer; 320 typedef __hash_local_iterator<__non_const_node_pointer> 321 __non_const_iterator; 322public: 323 typedef forward_iterator_tag iterator_category; 324 typedef typename remove_const< 325 typename __pointer_traits::element_type::value_type 326 >::type value_type; 327 typedef typename __pointer_traits::difference_type difference_type; 328 typedef const value_type& reference; 329 typedef typename __pointer_traits::template 330#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 331 rebind<const value_type> 332#else 333 rebind<const value_type>::other 334#endif 335 pointer; 336 337 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT {} 338 _LIBCPP_INLINE_VISIBILITY 339 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 340 : __node_(__x.__node_), 341 __bucket_(__x.__bucket_), 342 __bucket_count_(__x.__bucket_count_) 343 {} 344 345 _LIBCPP_INLINE_VISIBILITY 346 reference operator*() const {return __node_->__value_;} 347 _LIBCPP_INLINE_VISIBILITY 348 pointer operator->() const {return &__node_->__value_;} 349 350 _LIBCPP_INLINE_VISIBILITY 351 __hash_const_local_iterator& operator++() 352 { 353 __node_ = __node_->__next_; 354 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 355 __node_ = nullptr; 356 return *this; 357 } 358 359 _LIBCPP_INLINE_VISIBILITY 360 __hash_const_local_iterator operator++(int) 361 { 362 __hash_const_local_iterator __t(*this); 363 ++(*this); 364 return __t; 365 } 366 367 friend _LIBCPP_INLINE_VISIBILITY 368 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 369 {return __x.__node_ == __y.__node_;} 370 friend _LIBCPP_INLINE_VISIBILITY 371 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 372 {return __x.__node_ != __y.__node_;} 373 374private: 375 _LIBCPP_INLINE_VISIBILITY 376 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 377 size_t __bucket_count) _NOEXCEPT 378 : __node_(__node), 379 __bucket_(__bucket), 380 __bucket_count_(__bucket_count) 381 { 382 if (__node_ != nullptr) 383 __node_ = __node_->__next_; 384 } 385 386 template <class, class, class, class> friend class __hash_table; 387 template <class> friend class _LIBCPP_VISIBLE __hash_map_const_iterator; 388}; 389 390template <class _Alloc> 391class __bucket_list_deallocator 392{ 393 typedef _Alloc allocator_type; 394 typedef allocator_traits<allocator_type> __alloc_traits; 395 typedef typename __alloc_traits::size_type size_type; 396 397 __compressed_pair<size_type, allocator_type> __data_; 398public: 399 typedef typename __alloc_traits::pointer pointer; 400 401 _LIBCPP_INLINE_VISIBILITY 402 __bucket_list_deallocator() 403 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 404 : __data_(0) {} 405 406 _LIBCPP_INLINE_VISIBILITY 407 __bucket_list_deallocator(const allocator_type& __a, size_type __size) 408 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 409 : __data_(__size, __a) {} 410 411#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 412 413 _LIBCPP_INLINE_VISIBILITY 414 __bucket_list_deallocator(__bucket_list_deallocator&& __x) 415 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 416 : __data_(_VSTD::move(__x.__data_)) 417 { 418 __x.size() = 0; 419 } 420 421#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 422 423 _LIBCPP_INLINE_VISIBILITY 424 size_type& size() _NOEXCEPT {return __data_.first();} 425 _LIBCPP_INLINE_VISIBILITY 426 size_type size() const _NOEXCEPT {return __data_.first();} 427 428 _LIBCPP_INLINE_VISIBILITY 429 allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 430 _LIBCPP_INLINE_VISIBILITY 431 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 432 433 _LIBCPP_INLINE_VISIBILITY 434 void operator()(pointer __p) _NOEXCEPT 435 { 436 __alloc_traits::deallocate(__alloc(), __p, size()); 437 } 438}; 439 440template <class _Alloc> class __hash_map_node_destructor; 441 442template <class _Alloc> 443class __hash_node_destructor 444{ 445 typedef _Alloc allocator_type; 446 typedef allocator_traits<allocator_type> __alloc_traits; 447 typedef typename __alloc_traits::value_type::value_type value_type; 448public: 449 typedef typename __alloc_traits::pointer pointer; 450private: 451 452 allocator_type& __na_; 453 454 __hash_node_destructor& operator=(const __hash_node_destructor&); 455 456public: 457 bool __value_constructed; 458 459 _LIBCPP_INLINE_VISIBILITY 460 explicit __hash_node_destructor(allocator_type& __na, 461 bool __constructed = false) _NOEXCEPT 462 : __na_(__na), 463 __value_constructed(__constructed) 464 {} 465 466 _LIBCPP_INLINE_VISIBILITY 467 void operator()(pointer __p) _NOEXCEPT 468 { 469 if (__value_constructed) 470 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 471 if (__p) 472 __alloc_traits::deallocate(__na_, __p, 1); 473 } 474 475 template <class> friend class __hash_map_node_destructor; 476}; 477 478template <class _Tp, class _Hash, class _Equal, class _Alloc> 479class __hash_table 480{ 481public: 482 typedef _Tp value_type; 483 typedef _Hash hasher; 484 typedef _Equal key_equal; 485 typedef _Alloc allocator_type; 486 487private: 488 typedef allocator_traits<allocator_type> __alloc_traits; 489public: 490 typedef value_type& reference; 491 typedef const value_type& const_reference; 492 typedef typename __alloc_traits::pointer pointer; 493 typedef typename __alloc_traits::const_pointer const_pointer; 494 typedef typename __alloc_traits::size_type size_type; 495 typedef typename __alloc_traits::difference_type difference_type; 496public: 497 // Create __node 498 typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 499 typedef typename __alloc_traits::template 500#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 501 rebind_alloc<__node> 502#else 503 rebind_alloc<__node>::other 504#endif 505 __node_allocator; 506 typedef allocator_traits<__node_allocator> __node_traits; 507 typedef typename __node_traits::pointer __node_pointer; 508 typedef typename __node_traits::const_pointer __node_const_pointer; 509 typedef __hash_node_base<__node_pointer> __first_node; 510 511private: 512 513 typedef typename __node_traits::template 514#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 515 rebind_alloc<__node_pointer> 516#else 517 rebind_alloc<__node_pointer>::other 518#endif 519 __pointer_allocator; 520 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 521 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 522 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 523 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 524 525 // --- Member data begin --- 526 __bucket_list __bucket_list_; 527 __compressed_pair<__first_node, __node_allocator> __p1_; 528 __compressed_pair<size_type, hasher> __p2_; 529 __compressed_pair<float, key_equal> __p3_; 530 // --- Member data end --- 531 532 _LIBCPP_INLINE_VISIBILITY 533 size_type& size() _NOEXCEPT {return __p2_.first();} 534public: 535 _LIBCPP_INLINE_VISIBILITY 536 size_type size() const _NOEXCEPT {return __p2_.first();} 537 538 _LIBCPP_INLINE_VISIBILITY 539 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 540 _LIBCPP_INLINE_VISIBILITY 541 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 542 543 _LIBCPP_INLINE_VISIBILITY 544 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 545 _LIBCPP_INLINE_VISIBILITY 546 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 547 548 _LIBCPP_INLINE_VISIBILITY 549 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 550 _LIBCPP_INLINE_VISIBILITY 551 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 552 553 _LIBCPP_INLINE_VISIBILITY 554 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 555 _LIBCPP_INLINE_VISIBILITY 556 const __node_allocator& __node_alloc() const _NOEXCEPT 557 {return __p1_.second();} 558 559public: 560 typedef __hash_iterator<__node_pointer> iterator; 561 typedef __hash_const_iterator<__node_const_pointer> const_iterator; 562 typedef __hash_local_iterator<__node_pointer> local_iterator; 563 typedef __hash_const_local_iterator<__node_const_pointer> const_local_iterator; 564 565 __hash_table() 566 _NOEXCEPT_( 567 is_nothrow_default_constructible<__bucket_list>::value && 568 is_nothrow_default_constructible<__first_node>::value && 569 is_nothrow_default_constructible<__node_allocator>::value && 570 is_nothrow_default_constructible<hasher>::value && 571 is_nothrow_default_constructible<key_equal>::value); 572 __hash_table(const hasher& __hf, const key_equal& __eql); 573 __hash_table(const hasher& __hf, const key_equal& __eql, 574 const allocator_type& __a); 575 explicit __hash_table(const allocator_type& __a); 576 __hash_table(const __hash_table& __u); 577 __hash_table(const __hash_table& __u, const allocator_type& __a); 578#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 579 __hash_table(__hash_table&& __u) 580 _NOEXCEPT_( 581 is_nothrow_move_constructible<__bucket_list>::value && 582 is_nothrow_move_constructible<__first_node>::value && 583 is_nothrow_move_constructible<__node_allocator>::value && 584 is_nothrow_move_constructible<hasher>::value && 585 is_nothrow_move_constructible<key_equal>::value); 586 __hash_table(__hash_table&& __u, const allocator_type& __a); 587#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 588 ~__hash_table(); 589 590 __hash_table& operator=(const __hash_table& __u); 591#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 592 __hash_table& operator=(__hash_table&& __u) 593 _NOEXCEPT_( 594 __node_traits::propagate_on_container_move_assignment::value && 595 is_nothrow_move_assignable<__node_allocator>::value && 596 is_nothrow_move_assignable<hasher>::value && 597 is_nothrow_move_assignable<key_equal>::value); 598#endif 599 template <class _InputIterator> 600 void __assign_unique(_InputIterator __first, _InputIterator __last); 601 template <class _InputIterator> 602 void __assign_multi(_InputIterator __first, _InputIterator __last); 603 604 _LIBCPP_INLINE_VISIBILITY 605 size_type max_size() const _NOEXCEPT 606 { 607 return allocator_traits<__pointer_allocator>::max_size( 608 __bucket_list_.get_deleter().__alloc()); 609 } 610 611 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 612 iterator __node_insert_multi(__node_pointer __nd); 613 iterator __node_insert_multi(const_iterator __p, 614 __node_pointer __nd); 615 616#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 617 template <class... _Args> 618 pair<iterator, bool> __emplace_unique(_Args&&... __args); 619 template <class... _Args> 620 iterator __emplace_multi(_Args&&... __args); 621 template <class... _Args> 622 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 623#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 624 625 pair<iterator, bool> __insert_unique(const value_type& __x); 626 627#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 628 template <class _Pp> 629 pair<iterator, bool> __insert_unique(_Pp&& __x); 630#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 631 632#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 633 template <class _Pp> 634 iterator __insert_multi(_Pp&& __x); 635 template <class _Pp> 636 iterator __insert_multi(const_iterator __p, _Pp&& __x); 637#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 638 iterator __insert_multi(const value_type& __x); 639 iterator __insert_multi(const_iterator __p, const value_type& __x); 640#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 641 642 void clear() _NOEXCEPT; 643 void rehash(size_type __n); 644 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 645 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 646 647 _LIBCPP_INLINE_VISIBILITY 648 size_type bucket_count() const _NOEXCEPT 649 { 650 return __bucket_list_.get_deleter().size(); 651 } 652 653 iterator begin() _NOEXCEPT; 654 iterator end() _NOEXCEPT; 655 const_iterator begin() const _NOEXCEPT; 656 const_iterator end() const _NOEXCEPT; 657 658 template <class _Key> 659 _LIBCPP_INLINE_VISIBILITY 660 size_type bucket(const _Key& __k) const 661 {return __constrain_hash(hash_function()(__k), bucket_count());} 662 663 template <class _Key> 664 iterator find(const _Key& __x); 665 template <class _Key> 666 const_iterator find(const _Key& __x) const; 667 668 typedef __hash_node_destructor<__node_allocator> _Dp; 669 typedef unique_ptr<__node, _Dp> __node_holder; 670 671 iterator erase(const_iterator __p); 672 iterator erase(const_iterator __first, const_iterator __last); 673 template <class _Key> 674 size_type __erase_unique(const _Key& __k); 675 template <class _Key> 676 size_type __erase_multi(const _Key& __k); 677 __node_holder remove(const_iterator __p) _NOEXCEPT; 678 679 template <class _Key> 680 size_type __count_unique(const _Key& __k) const; 681 template <class _Key> 682 size_type __count_multi(const _Key& __k) const; 683 684 template <class _Key> 685 pair<iterator, iterator> 686 __equal_range_unique(const _Key& __k); 687 template <class _Key> 688 pair<const_iterator, const_iterator> 689 __equal_range_unique(const _Key& __k) const; 690 691 template <class _Key> 692 pair<iterator, iterator> 693 __equal_range_multi(const _Key& __k); 694 template <class _Key> 695 pair<const_iterator, const_iterator> 696 __equal_range_multi(const _Key& __k) const; 697 698 void swap(__hash_table& __u) 699 _NOEXCEPT_( 700 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 701 __is_nothrow_swappable<__pointer_allocator>::value) && 702 (!__node_traits::propagate_on_container_swap::value || 703 __is_nothrow_swappable<__node_allocator>::value) && 704 __is_nothrow_swappable<hasher>::value && 705 __is_nothrow_swappable<key_equal>::value); 706 707 _LIBCPP_INLINE_VISIBILITY 708 size_type max_bucket_count() const _NOEXCEPT 709 {return __bucket_list_.get_deleter().__alloc().max_size();} 710 size_type bucket_size(size_type __n) const; 711 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 712 { 713 size_type __bc = bucket_count(); 714 return __bc != 0 ? (float)size() / __bc : 0.f; 715 } 716 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 717 {max_load_factor() = _VSTD::max(__mlf, load_factor());} 718 719 _LIBCPP_INLINE_VISIBILITY local_iterator begin(size_type __n) 720 {return local_iterator(__bucket_list_[__n], __n, bucket_count());} 721 _LIBCPP_INLINE_VISIBILITY local_iterator end(size_type __n) 722 {return local_iterator(nullptr, __n, bucket_count());} 723 _LIBCPP_INLINE_VISIBILITY const_local_iterator cbegin(size_type __n) const 724 {return const_local_iterator(__bucket_list_[__n], __n, bucket_count());} 725 _LIBCPP_INLINE_VISIBILITY const_local_iterator cend(size_type __n) const 726 {return const_local_iterator(nullptr, __n, bucket_count());} 727private: 728 void __rehash(size_type __n); 729 730#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 731#ifndef _LIBCPP_HAS_NO_VARIADICS 732 template <class ..._Args> 733 __node_holder __construct_node(_Args&& ...__args); 734#endif // _LIBCPP_HAS_NO_VARIADICS 735 __node_holder __construct_node(value_type&& __v, size_t __hash); 736#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 737 __node_holder __construct_node(const value_type& __v); 738#endif 739 __node_holder __construct_node(const value_type& __v, size_t __hash); 740 741 _LIBCPP_INLINE_VISIBILITY 742 void __copy_assign_alloc(const __hash_table& __u) 743 {__copy_assign_alloc(__u, integral_constant<bool, 744 __node_traits::propagate_on_container_copy_assignment::value>());} 745 void __copy_assign_alloc(const __hash_table& __u, true_type); 746 _LIBCPP_INLINE_VISIBILITY 747 void __copy_assign_alloc(const __hash_table&, false_type) {} 748 749 void __move_assign(__hash_table& __u, false_type); 750 void __move_assign(__hash_table& __u, true_type) 751 _NOEXCEPT_( 752 is_nothrow_move_assignable<__node_allocator>::value && 753 is_nothrow_move_assignable<hasher>::value && 754 is_nothrow_move_assignable<key_equal>::value); 755 _LIBCPP_INLINE_VISIBILITY 756 void __move_assign_alloc(__hash_table& __u) 757 _NOEXCEPT_( 758 !__node_traits::propagate_on_container_move_assignment::value || 759 (is_nothrow_move_assignable<__pointer_allocator>::value && 760 is_nothrow_move_assignable<__node_allocator>::value)) 761 {__move_assign_alloc(__u, integral_constant<bool, 762 __node_traits::propagate_on_container_move_assignment::value>());} 763 _LIBCPP_INLINE_VISIBILITY 764 void __move_assign_alloc(__hash_table& __u, true_type) 765 _NOEXCEPT_( 766 is_nothrow_move_assignable<__pointer_allocator>::value && 767 is_nothrow_move_assignable<__node_allocator>::value) 768 { 769 __bucket_list_.get_deleter().__alloc() = 770 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 771 __node_alloc() = _VSTD::move(__u.__node_alloc()); 772 } 773 _LIBCPP_INLINE_VISIBILITY 774 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 775 776 template <class _Ap> 777 _LIBCPP_INLINE_VISIBILITY 778 static 779 void 780 __swap_alloc(_Ap& __x, _Ap& __y) 781 _NOEXCEPT_( 782 !allocator_traits<_Ap>::propagate_on_container_swap::value || 783 __is_nothrow_swappable<_Ap>::value) 784 { 785 __swap_alloc(__x, __y, 786 integral_constant<bool, 787 allocator_traits<_Ap>::propagate_on_container_swap::value 788 >()); 789 } 790 791 template <class _Ap> 792 _LIBCPP_INLINE_VISIBILITY 793 static 794 void 795 __swap_alloc(_Ap& __x, _Ap& __y, true_type) 796 _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 797 { 798 using _VSTD::swap; 799 swap(__x, __y); 800 } 801 802 template <class _Ap> 803 _LIBCPP_INLINE_VISIBILITY 804 static 805 void 806 __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 807 808 void __deallocate(__node_pointer __np) _NOEXCEPT; 809 __node_pointer __detach() _NOEXCEPT; 810}; 811 812template <class _Tp, class _Hash, class _Equal, class _Alloc> 813inline _LIBCPP_INLINE_VISIBILITY 814__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 815 _NOEXCEPT_( 816 is_nothrow_default_constructible<__bucket_list>::value && 817 is_nothrow_default_constructible<__first_node>::value && 818 is_nothrow_default_constructible<hasher>::value && 819 is_nothrow_default_constructible<key_equal>::value) 820 : __p2_(0), 821 __p3_(1.0f) 822{ 823} 824 825template <class _Tp, class _Hash, class _Equal, class _Alloc> 826inline _LIBCPP_INLINE_VISIBILITY 827__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 828 const key_equal& __eql) 829 : __bucket_list_(nullptr, __bucket_list_deleter()), 830 __p1_(), 831 __p2_(0, __hf), 832 __p3_(1.0f, __eql) 833{ 834} 835 836template <class _Tp, class _Hash, class _Equal, class _Alloc> 837__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 838 const key_equal& __eql, 839 const allocator_type& __a) 840 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 841 __p1_(__node_allocator(__a)), 842 __p2_(0, __hf), 843 __p3_(1.0f, __eql) 844{ 845} 846 847template <class _Tp, class _Hash, class _Equal, class _Alloc> 848__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 849 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 850 __p1_(__node_allocator(__a)), 851 __p2_(0), 852 __p3_(1.0f) 853{ 854} 855 856template <class _Tp, class _Hash, class _Equal, class _Alloc> 857__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 858 : __bucket_list_(nullptr, 859 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 860 select_on_container_copy_construction( 861 __u.__bucket_list_.get_deleter().__alloc()), 0)), 862 __p1_(allocator_traits<__node_allocator>:: 863 select_on_container_copy_construction(__u.__node_alloc())), 864 __p2_(0, __u.hash_function()), 865 __p3_(__u.__p3_) 866{ 867} 868 869template <class _Tp, class _Hash, class _Equal, class _Alloc> 870__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 871 const allocator_type& __a) 872 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 873 __p1_(__node_allocator(__a)), 874 __p2_(0, __u.hash_function()), 875 __p3_(__u.__p3_) 876{ 877} 878 879#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 880 881template <class _Tp, class _Hash, class _Equal, class _Alloc> 882__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 883 _NOEXCEPT_( 884 is_nothrow_move_constructible<__bucket_list>::value && 885 is_nothrow_move_constructible<__first_node>::value && 886 is_nothrow_move_constructible<hasher>::value && 887 is_nothrow_move_constructible<key_equal>::value) 888 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 889 __p1_(_VSTD::move(__u.__p1_)), 890 __p2_(_VSTD::move(__u.__p2_)), 891 __p3_(_VSTD::move(__u.__p3_)) 892{ 893 if (size() > 0) 894 { 895 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 896 static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 897 __u.__p1_.first().__next_ = nullptr; 898 __u.size() = 0; 899 } 900} 901 902template <class _Tp, class _Hash, class _Equal, class _Alloc> 903__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 904 const allocator_type& __a) 905 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 906 __p1_(__node_allocator(__a)), 907 __p2_(0, _VSTD::move(__u.hash_function())), 908 __p3_(_VSTD::move(__u.__p3_)) 909{ 910 if (__a == allocator_type(__u.__node_alloc())) 911 { 912 __bucket_list_.reset(__u.__bucket_list_.release()); 913 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 914 __u.__bucket_list_.get_deleter().size() = 0; 915 if (__u.size() > 0) 916 { 917 __p1_.first().__next_ = __u.__p1_.first().__next_; 918 __u.__p1_.first().__next_ = nullptr; 919 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 920 static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 921 size() = __u.size(); 922 __u.size() = 0; 923 } 924 } 925} 926 927#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 928 929template <class _Tp, class _Hash, class _Equal, class _Alloc> 930__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 931{ 932 __deallocate(__p1_.first().__next_); 933} 934 935template <class _Tp, class _Hash, class _Equal, class _Alloc> 936void 937__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 938 const __hash_table& __u, true_type) 939{ 940 if (__node_alloc() != __u.__node_alloc()) 941 { 942 clear(); 943 __bucket_list_.reset(); 944 __bucket_list_.get_deleter().size() = 0; 945 } 946 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 947 __node_alloc() = __u.__node_alloc(); 948} 949 950template <class _Tp, class _Hash, class _Equal, class _Alloc> 951__hash_table<_Tp, _Hash, _Equal, _Alloc>& 952__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 953{ 954 if (this != &__u) 955 { 956 __copy_assign_alloc(__u); 957 hash_function() = __u.hash_function(); 958 key_eq() = __u.key_eq(); 959 max_load_factor() = __u.max_load_factor(); 960 __assign_multi(__u.begin(), __u.end()); 961 } 962 return *this; 963} 964 965template <class _Tp, class _Hash, class _Equal, class _Alloc> 966void 967__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 968 _NOEXCEPT 969{ 970 __node_allocator& __na = __node_alloc(); 971 while (__np != nullptr) 972 { 973 __node_pointer __next = __np->__next_; 974 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 975 __node_traits::deallocate(__na, __np, 1); 976 __np = __next; 977 } 978} 979 980template <class _Tp, class _Hash, class _Equal, class _Alloc> 981typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 982__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 983{ 984 size_type __bc = bucket_count(); 985 for (size_type __i = 0; __i < __bc; ++__i) 986 __bucket_list_[__i] = nullptr; 987 size() = 0; 988 __node_pointer __cache = __p1_.first().__next_; 989 __p1_.first().__next_ = nullptr; 990 return __cache; 991} 992 993#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 994 995template <class _Tp, class _Hash, class _Equal, class _Alloc> 996void 997__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 998 __hash_table& __u, true_type) 999 _NOEXCEPT_( 1000 is_nothrow_move_assignable<__node_allocator>::value && 1001 is_nothrow_move_assignable<hasher>::value && 1002 is_nothrow_move_assignable<key_equal>::value) 1003{ 1004 clear(); 1005 __bucket_list_.reset(__u.__bucket_list_.release()); 1006 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1007 __u.__bucket_list_.get_deleter().size() = 0; 1008 __move_assign_alloc(__u); 1009 size() = __u.size(); 1010 hash_function() = _VSTD::move(__u.hash_function()); 1011 max_load_factor() = __u.max_load_factor(); 1012 key_eq() = _VSTD::move(__u.key_eq()); 1013 __p1_.first().__next_ = __u.__p1_.first().__next_; 1014 if (size() > 0) 1015 { 1016 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1017 static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1018 __u.__p1_.first().__next_ = nullptr; 1019 __u.size() = 0; 1020 } 1021} 1022 1023template <class _Tp, class _Hash, class _Equal, class _Alloc> 1024void 1025__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1026 __hash_table& __u, false_type) 1027{ 1028 if (__node_alloc() == __u.__node_alloc()) 1029 __move_assign(__u, true_type()); 1030 else 1031 { 1032 hash_function() = _VSTD::move(__u.hash_function()); 1033 key_eq() = _VSTD::move(__u.key_eq()); 1034 max_load_factor() = __u.max_load_factor(); 1035 if (bucket_count() != 0) 1036 { 1037 __node_pointer __cache = __detach(); 1038#ifndef _LIBCPP_NO_EXCEPTIONS 1039 try 1040 { 1041#endif // _LIBCPP_NO_EXCEPTIONS 1042 const_iterator __i = __u.begin(); 1043 while (__cache != nullptr && __u.size() != 0) 1044 { 1045 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1046 __node_pointer __next = __cache->__next_; 1047 __node_insert_multi(__cache); 1048 __cache = __next; 1049 } 1050#ifndef _LIBCPP_NO_EXCEPTIONS 1051 } 1052 catch (...) 1053 { 1054 __deallocate(__cache); 1055 throw; 1056 } 1057#endif // _LIBCPP_NO_EXCEPTIONS 1058 __deallocate(__cache); 1059 } 1060 const_iterator __i = __u.begin(); 1061 while (__u.size() != 0) 1062 { 1063 __node_holder __h = 1064 __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1065 __node_insert_multi(__h.get()); 1066 __h.release(); 1067 } 1068 } 1069} 1070 1071template <class _Tp, class _Hash, class _Equal, class _Alloc> 1072inline _LIBCPP_INLINE_VISIBILITY 1073__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1074__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1075 _NOEXCEPT_( 1076 __node_traits::propagate_on_container_move_assignment::value && 1077 is_nothrow_move_assignable<__node_allocator>::value && 1078 is_nothrow_move_assignable<hasher>::value && 1079 is_nothrow_move_assignable<key_equal>::value) 1080{ 1081 __move_assign(__u, integral_constant<bool, 1082 __node_traits::propagate_on_container_move_assignment::value>()); 1083 return *this; 1084} 1085 1086#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1087 1088template <class _Tp, class _Hash, class _Equal, class _Alloc> 1089template <class _InputIterator> 1090void 1091__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1092 _InputIterator __last) 1093{ 1094 if (bucket_count() != 0) 1095 { 1096 __node_pointer __cache = __detach(); 1097#ifndef _LIBCPP_NO_EXCEPTIONS 1098 try 1099 { 1100#endif // _LIBCPP_NO_EXCEPTIONS 1101 for (; __cache != nullptr && __first != __last; ++__first) 1102 { 1103 __cache->__value_ = *__first; 1104 __node_pointer __next = __cache->__next_; 1105 __node_insert_unique(__cache); 1106 __cache = __next; 1107 } 1108#ifndef _LIBCPP_NO_EXCEPTIONS 1109 } 1110 catch (...) 1111 { 1112 __deallocate(__cache); 1113 throw; 1114 } 1115#endif // _LIBCPP_NO_EXCEPTIONS 1116 __deallocate(__cache); 1117 } 1118 for (; __first != __last; ++__first) 1119 __insert_unique(*__first); 1120} 1121 1122template <class _Tp, class _Hash, class _Equal, class _Alloc> 1123template <class _InputIterator> 1124void 1125__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1126 _InputIterator __last) 1127{ 1128 if (bucket_count() != 0) 1129 { 1130 __node_pointer __cache = __detach(); 1131#ifndef _LIBCPP_NO_EXCEPTIONS 1132 try 1133 { 1134#endif // _LIBCPP_NO_EXCEPTIONS 1135 for (; __cache != nullptr && __first != __last; ++__first) 1136 { 1137 __cache->__value_ = *__first; 1138 __node_pointer __next = __cache->__next_; 1139 __node_insert_multi(__cache); 1140 __cache = __next; 1141 } 1142#ifndef _LIBCPP_NO_EXCEPTIONS 1143 } 1144 catch (...) 1145 { 1146 __deallocate(__cache); 1147 throw; 1148 } 1149#endif // _LIBCPP_NO_EXCEPTIONS 1150 __deallocate(__cache); 1151 } 1152 for (; __first != __last; ++__first) 1153 __insert_multi(*__first); 1154} 1155 1156template <class _Tp, class _Hash, class _Equal, class _Alloc> 1157inline _LIBCPP_INLINE_VISIBILITY 1158typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1159__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1160{ 1161 return iterator(__p1_.first().__next_); 1162} 1163 1164template <class _Tp, class _Hash, class _Equal, class _Alloc> 1165inline _LIBCPP_INLINE_VISIBILITY 1166typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1167__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1168{ 1169 return iterator(nullptr); 1170} 1171 1172template <class _Tp, class _Hash, class _Equal, class _Alloc> 1173inline _LIBCPP_INLINE_VISIBILITY 1174typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1175__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1176{ 1177 return const_iterator(__p1_.first().__next_); 1178} 1179 1180template <class _Tp, class _Hash, class _Equal, class _Alloc> 1181inline _LIBCPP_INLINE_VISIBILITY 1182typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1183__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1184{ 1185 return const_iterator(nullptr); 1186} 1187 1188template <class _Tp, class _Hash, class _Equal, class _Alloc> 1189void 1190__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1191{ 1192 if (size() > 0) 1193 { 1194 __deallocate(__p1_.first().__next_); 1195 __p1_.first().__next_ = nullptr; 1196 size_type __bc = bucket_count(); 1197 for (size_type __i = 0; __i < __bc; ++__i) 1198 __bucket_list_[__i] = nullptr; 1199 size() = 0; 1200 } 1201} 1202 1203template <class _Tp, class _Hash, class _Equal, class _Alloc> 1204pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1205__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1206{ 1207 __nd->__hash_ = hash_function()(__nd->__value_); 1208 size_type __bc = bucket_count(); 1209 bool __inserted = false; 1210 __node_pointer __ndptr; 1211 size_t __chash; 1212 if (__bc != 0) 1213 { 1214 __chash = __constrain_hash(__nd->__hash_, __bc); 1215 __ndptr = __bucket_list_[__chash]; 1216 if (__ndptr != nullptr) 1217 { 1218 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1219 __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1220 __ndptr = __ndptr->__next_) 1221 { 1222 if (key_eq()(__ndptr->__value_, __nd->__value_)) 1223 goto __done; 1224 } 1225 } 1226 } 1227 { 1228 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1229 { 1230 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1231 size_type(ceil(float(size() + 1) / max_load_factor())))); 1232 __bc = bucket_count(); 1233 __chash = __constrain_hash(__nd->__hash_, __bc); 1234 } 1235 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1236 __node_pointer __pn = __bucket_list_[__chash]; 1237 if (__pn == nullptr) 1238 { 1239 __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1240 __nd->__next_ = __pn->__next_; 1241 __pn->__next_ = __nd; 1242 // fix up __bucket_list_ 1243 __bucket_list_[__chash] = __pn; 1244 if (__nd->__next_ != nullptr) 1245 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1246 } 1247 else 1248 { 1249 __nd->__next_ = __pn->__next_; 1250 __pn->__next_ = __nd; 1251 } 1252 __ndptr = __nd; 1253 // increment size 1254 ++size(); 1255 __inserted = true; 1256 } 1257__done: 1258 return pair<iterator, bool>(iterator(__ndptr), __inserted); 1259} 1260 1261template <class _Tp, class _Hash, class _Equal, class _Alloc> 1262typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1263__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1264{ 1265 __cp->__hash_ = hash_function()(__cp->__value_); 1266 size_type __bc = bucket_count(); 1267 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1268 { 1269 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1270 size_type(ceil(float(size() + 1) / max_load_factor())))); 1271 __bc = bucket_count(); 1272 } 1273 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1274 __node_pointer __pn = __bucket_list_[__chash]; 1275 if (__pn == nullptr) 1276 { 1277 __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1278 __cp->__next_ = __pn->__next_; 1279 __pn->__next_ = __cp; 1280 // fix up __bucket_list_ 1281 __bucket_list_[__chash] = __pn; 1282 if (__cp->__next_ != nullptr) 1283 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1284 } 1285 else 1286 { 1287 for (bool __found = false; __pn->__next_ != nullptr && 1288 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1289 __pn = __pn->__next_) 1290 { 1291 // __found key_eq() action 1292 // false false loop 1293 // true true loop 1294 // false true set __found to true 1295 // true false break 1296 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1297 key_eq()(__pn->__next_->__value_, __cp->__value_))) 1298 { 1299 if (!__found) 1300 __found = true; 1301 else 1302 break; 1303 } 1304 } 1305 __cp->__next_ = __pn->__next_; 1306 __pn->__next_ = __cp; 1307 if (__cp->__next_ != nullptr) 1308 { 1309 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1310 if (__nhash != __chash) 1311 __bucket_list_[__nhash] = __cp; 1312 } 1313 } 1314 ++size(); 1315 return iterator(__cp); 1316} 1317 1318template <class _Tp, class _Hash, class _Equal, class _Alloc> 1319typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1320__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1321 const_iterator __p, __node_pointer __cp) 1322{ 1323 if (__p != end() && key_eq()(*__p, __cp->__value_)) 1324 { 1325 __node_pointer __np = const_cast<__node_pointer>(__p.__node_); 1326 __cp->__hash_ = __np->__hash_; 1327 size_type __bc = bucket_count(); 1328 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1329 { 1330 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1331 size_type(ceil(float(size() + 1) / max_load_factor())))); 1332 __bc = bucket_count(); 1333 } 1334 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1335 __node_pointer __pp = __bucket_list_[__chash]; 1336 while (__pp->__next_ != __np) 1337 __pp = __pp->__next_; 1338 __cp->__next_ = __np; 1339 __pp->__next_ = __cp; 1340 ++size(); 1341 return iterator(__cp); 1342 } 1343 return __node_insert_multi(__cp); 1344} 1345 1346template <class _Tp, class _Hash, class _Equal, class _Alloc> 1347pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1348__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1349{ 1350 size_t __hash = hash_function()(__x); 1351 size_type __bc = bucket_count(); 1352 bool __inserted = false; 1353 __node_pointer __nd; 1354 size_t __chash; 1355 if (__bc != 0) 1356 { 1357 __chash = __constrain_hash(__hash, __bc); 1358 __nd = __bucket_list_[__chash]; 1359 if (__nd != nullptr) 1360 { 1361 for (__nd = __nd->__next_; __nd != nullptr && 1362 __constrain_hash(__nd->__hash_, __bc) == __chash; 1363 __nd = __nd->__next_) 1364 { 1365 if (key_eq()(__nd->__value_, __x)) 1366 goto __done; 1367 } 1368 } 1369 } 1370 { 1371 __node_holder __h = __construct_node(__x, __hash); 1372 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1373 { 1374 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc), 1375 size_type(ceil(float(size() + 1) / max_load_factor())))); 1376 __bc = bucket_count(); 1377 __chash = __constrain_hash(__hash, __bc); 1378 } 1379 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1380 __node_pointer __pn = __bucket_list_[__chash]; 1381 if (__pn == nullptr) 1382 { 1383 __pn = static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1384 __h->__next_ = __pn->__next_; 1385 __pn->__next_ = __h.get(); 1386 // fix up __bucket_list_ 1387 __bucket_list_[__chash] = __pn; 1388 if (__h->__next_ != nullptr) 1389 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1390 } 1391 else 1392 { 1393 __h->__next_ = __pn->__next_; 1394 __pn->__next_ = __h.get(); 1395 } 1396 __nd = __h.release(); 1397 // increment size 1398 ++size(); 1399 __inserted = true; 1400 } 1401__done: 1402 return pair<iterator, bool>(iterator(__nd), __inserted); 1403} 1404 1405#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1406#ifndef _LIBCPP_HAS_NO_VARIADICS 1407 1408template <class _Tp, class _Hash, class _Equal, class _Alloc> 1409template <class... _Args> 1410pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1411__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1412{ 1413 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1414 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1415 if (__r.second) 1416 __h.release(); 1417 return __r; 1418} 1419 1420template <class _Tp, class _Hash, class _Equal, class _Alloc> 1421template <class... _Args> 1422typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1423__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1424{ 1425 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1426 iterator __r = __node_insert_multi(__h.get()); 1427 __h.release(); 1428 return __r; 1429} 1430 1431template <class _Tp, class _Hash, class _Equal, class _Alloc> 1432template <class... _Args> 1433typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1434__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1435 const_iterator __p, _Args&&... __args) 1436{ 1437 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1438 iterator __r = __node_insert_multi(__p, __h.get()); 1439 __h.release(); 1440 return __r; 1441} 1442 1443#endif // _LIBCPP_HAS_NO_VARIADICS 1444 1445template <class _Tp, class _Hash, class _Equal, class _Alloc> 1446template <class _Pp> 1447pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1448__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1449{ 1450 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1451 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1452 if (__r.second) 1453 __h.release(); 1454 return __r; 1455} 1456 1457#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1458 1459#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1460 1461template <class _Tp, class _Hash, class _Equal, class _Alloc> 1462template <class _Pp> 1463typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1464__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1465{ 1466 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1467 iterator __r = __node_insert_multi(__h.get()); 1468 __h.release(); 1469 return __r; 1470} 1471 1472template <class _Tp, class _Hash, class _Equal, class _Alloc> 1473template <class _Pp> 1474typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1475__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1476 _Pp&& __x) 1477{ 1478 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1479 iterator __r = __node_insert_multi(__p, __h.get()); 1480 __h.release(); 1481 return __r; 1482} 1483 1484#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1485 1486template <class _Tp, class _Hash, class _Equal, class _Alloc> 1487typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1488__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1489{ 1490 __node_holder __h = __construct_node(__x); 1491 iterator __r = __node_insert_multi(__h.get()); 1492 __h.release(); 1493 return __r; 1494} 1495 1496template <class _Tp, class _Hash, class _Equal, class _Alloc> 1497typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1498__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1499 const value_type& __x) 1500{ 1501 __node_holder __h = __construct_node(__x); 1502 iterator __r = __node_insert_multi(__p, __h.get()); 1503 __h.release(); 1504 return __r; 1505} 1506 1507#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1508 1509template <class _Tp, class _Hash, class _Equal, class _Alloc> 1510void 1511__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1512{ 1513 if (__n == 1) 1514 __n = 2; 1515 else if (__n & (__n - 1)) 1516 __n = __next_prime(__n); 1517 size_type __bc = bucket_count(); 1518 if (__n > __bc) 1519 __rehash(__n); 1520 else if (__n < __bc) 1521 { 1522 __n = _VSTD::max<size_type> 1523 ( 1524 __n, 1525 __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1526 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1527 ); 1528 if (__n < __bc) 1529 __rehash(__n); 1530 } 1531} 1532 1533template <class _Tp, class _Hash, class _Equal, class _Alloc> 1534void 1535__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1536{ 1537 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1538 __bucket_list_.reset(__nbc > 0 ? 1539 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1540 __bucket_list_.get_deleter().size() = __nbc; 1541 if (__nbc > 0) 1542 { 1543 for (size_type __i = 0; __i < __nbc; ++__i) 1544 __bucket_list_[__i] = nullptr; 1545 __node_pointer __pp(static_cast<__node_pointer>(_VSTD::addressof(__p1_.first()))); 1546 __node_pointer __cp = __pp->__next_; 1547 if (__cp != nullptr) 1548 { 1549 size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1550 __bucket_list_[__chash] = __pp; 1551 size_type __phash = __chash; 1552 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1553 __cp = __pp->__next_) 1554 { 1555 __chash = __constrain_hash(__cp->__hash_, __nbc); 1556 if (__chash == __phash) 1557 __pp = __cp; 1558 else 1559 { 1560 if (__bucket_list_[__chash] == nullptr) 1561 { 1562 __bucket_list_[__chash] = __pp; 1563 __pp = __cp; 1564 __phash = __chash; 1565 } 1566 else 1567 { 1568 __node_pointer __np = __cp; 1569 for (; __np->__next_ != nullptr && 1570 key_eq()(__cp->__value_, __np->__next_->__value_); 1571 __np = __np->__next_) 1572 ; 1573 __pp->__next_ = __np->__next_; 1574 __np->__next_ = __bucket_list_[__chash]->__next_; 1575 __bucket_list_[__chash]->__next_ = __cp; 1576 1577 } 1578 } 1579 } 1580 } 1581 } 1582} 1583 1584template <class _Tp, class _Hash, class _Equal, class _Alloc> 1585template <class _Key> 1586typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1587__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 1588{ 1589 size_t __hash = hash_function()(__k); 1590 size_type __bc = bucket_count(); 1591 if (__bc != 0) 1592 { 1593 size_t __chash = __constrain_hash(__hash, __bc); 1594 __node_pointer __nd = __bucket_list_[__chash]; 1595 if (__nd != nullptr) 1596 { 1597 for (__nd = __nd->__next_; __nd != nullptr && 1598 __constrain_hash(__nd->__hash_, __bc) == __chash; 1599 __nd = __nd->__next_) 1600 { 1601 if (key_eq()(__nd->__value_, __k)) 1602 return iterator(__nd); 1603 } 1604 } 1605 } 1606 return end(); 1607} 1608 1609template <class _Tp, class _Hash, class _Equal, class _Alloc> 1610template <class _Key> 1611typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1612__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 1613{ 1614 size_t __hash = hash_function()(__k); 1615 size_type __bc = bucket_count(); 1616 if (__bc != 0) 1617 { 1618 size_t __chash = __constrain_hash(__hash, __bc); 1619 __node_const_pointer __nd = __bucket_list_[__chash]; 1620 if (__nd != nullptr) 1621 { 1622 for (__nd = __nd->__next_; __nd != nullptr && 1623 __constrain_hash(__nd->__hash_, __bc) == __chash; 1624 __nd = __nd->__next_) 1625 { 1626 if (key_eq()(__nd->__value_, __k)) 1627 return const_iterator(__nd); 1628 } 1629 } 1630 1631 } 1632 return end(); 1633} 1634 1635#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1636#ifndef _LIBCPP_HAS_NO_VARIADICS 1637 1638template <class _Tp, class _Hash, class _Equal, class _Alloc> 1639template <class ..._Args> 1640typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1641__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 1642{ 1643 __node_allocator& __na = __node_alloc(); 1644 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1645 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 1646 __h.get_deleter().__value_constructed = true; 1647 __h->__hash_ = hash_function()(__h->__value_); 1648 __h->__next_ = nullptr; 1649 return __h; 1650} 1651 1652#endif // _LIBCPP_HAS_NO_VARIADICS 1653 1654template <class _Tp, class _Hash, class _Equal, class _Alloc> 1655typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1656__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 1657 size_t __hash) 1658{ 1659 __node_allocator& __na = __node_alloc(); 1660 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1661 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 1662 __h.get_deleter().__value_constructed = true; 1663 __h->__hash_ = __hash; 1664 __h->__next_ = nullptr; 1665 return _VSTD::move(__h); 1666} 1667 1668#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1669 1670template <class _Tp, class _Hash, class _Equal, class _Alloc> 1671typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1672__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 1673{ 1674 __node_allocator& __na = __node_alloc(); 1675 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1676 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1677 __h.get_deleter().__value_constructed = true; 1678 __h->__hash_ = hash_function()(__h->__value_); 1679 __h->__next_ = nullptr; 1680 return _VSTD::move(__h); 1681} 1682 1683#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1684 1685template <class _Tp, class _Hash, class _Equal, class _Alloc> 1686typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1687__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 1688 size_t __hash) 1689{ 1690 __node_allocator& __na = __node_alloc(); 1691 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 1692 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 1693 __h.get_deleter().__value_constructed = true; 1694 __h->__hash_ = __hash; 1695 __h->__next_ = nullptr; 1696 return _VSTD::move(__h); 1697} 1698 1699template <class _Tp, class _Hash, class _Equal, class _Alloc> 1700typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1701__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 1702{ 1703 __node_pointer __np = const_cast<__node_pointer>(__p.__node_); 1704 iterator __r(__np); 1705 ++__r; 1706 remove(__p); 1707 return __r; 1708} 1709 1710template <class _Tp, class _Hash, class _Equal, class _Alloc> 1711typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1712__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 1713 const_iterator __last) 1714{ 1715 for (const_iterator __p = __first; __first != __last; __p = __first) 1716 { 1717 ++__first; 1718 erase(__p); 1719 } 1720 __node_pointer __np = const_cast<__node_pointer>(__last.__node_); 1721 return iterator (__np); 1722} 1723 1724template <class _Tp, class _Hash, class _Equal, class _Alloc> 1725template <class _Key> 1726typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1727__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 1728{ 1729 iterator __i = find(__k); 1730 if (__i == end()) 1731 return 0; 1732 erase(__i); 1733 return 1; 1734} 1735 1736template <class _Tp, class _Hash, class _Equal, class _Alloc> 1737template <class _Key> 1738typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1739__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 1740{ 1741 size_type __r = 0; 1742 iterator __i = find(__k); 1743 if (__i != end()) 1744 { 1745 iterator __e = end(); 1746 do 1747 { 1748 erase(__i++); 1749 ++__r; 1750 } while (__i != __e && key_eq()(*__i, __k)); 1751 } 1752 return __r; 1753} 1754 1755template <class _Tp, class _Hash, class _Equal, class _Alloc> 1756typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 1757__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 1758{ 1759 // current node 1760 __node_pointer __cn = const_cast<__node_pointer>(__p.__node_); 1761 size_type __bc = bucket_count(); 1762 size_t __chash = __constrain_hash(__cn->__hash_, __bc); 1763 // find previous node 1764 __node_pointer __pn = __bucket_list_[__chash]; 1765 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 1766 ; 1767 // Fix up __bucket_list_ 1768 // if __pn is not in same bucket (before begin is not in same bucket) && 1769 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 1770 if (__pn == _VSTD::addressof(__p1_.first()) || __constrain_hash(__pn->__hash_, __bc) != __chash) 1771 { 1772 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 1773 __bucket_list_[__chash] = nullptr; 1774 } 1775 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 1776 if (__cn->__next_ != nullptr) 1777 { 1778 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 1779 if (__nhash != __chash) 1780 __bucket_list_[__nhash] = __pn; 1781 } 1782 // remove __cn 1783 __pn->__next_ = __cn->__next_; 1784 __cn->__next_ = nullptr; 1785 --size(); 1786 return __node_holder(__cn, _Dp(__node_alloc(), true)); 1787} 1788 1789template <class _Tp, class _Hash, class _Equal, class _Alloc> 1790template <class _Key> 1791inline _LIBCPP_INLINE_VISIBILITY 1792typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1793__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 1794{ 1795 return static_cast<size_type>(find(__k) != end()); 1796} 1797 1798template <class _Tp, class _Hash, class _Equal, class _Alloc> 1799template <class _Key> 1800typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1801__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 1802{ 1803 size_type __r = 0; 1804 const_iterator __i = find(__k); 1805 if (__i != end()) 1806 { 1807 const_iterator __e = end(); 1808 do 1809 { 1810 ++__i; 1811 ++__r; 1812 } while (__i != __e && key_eq()(*__i, __k)); 1813 } 1814 return __r; 1815} 1816 1817template <class _Tp, class _Hash, class _Equal, class _Alloc> 1818template <class _Key> 1819pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 1820 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 1821__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 1822 const _Key& __k) 1823{ 1824 iterator __i = find(__k); 1825 iterator __j = __i; 1826 if (__i != end()) 1827 ++__j; 1828 return pair<iterator, iterator>(__i, __j); 1829} 1830 1831template <class _Tp, class _Hash, class _Equal, class _Alloc> 1832template <class _Key> 1833pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 1834 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 1835__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 1836 const _Key& __k) const 1837{ 1838 const_iterator __i = find(__k); 1839 const_iterator __j = __i; 1840 if (__i != end()) 1841 ++__j; 1842 return pair<const_iterator, const_iterator>(__i, __j); 1843} 1844 1845template <class _Tp, class _Hash, class _Equal, class _Alloc> 1846template <class _Key> 1847pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 1848 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 1849__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 1850 const _Key& __k) 1851{ 1852 iterator __i = find(__k); 1853 iterator __j = __i; 1854 if (__i != end()) 1855 { 1856 iterator __e = end(); 1857 do 1858 { 1859 ++__j; 1860 } while (__j != __e && key_eq()(*__j, __k)); 1861 } 1862 return pair<iterator, iterator>(__i, __j); 1863} 1864 1865template <class _Tp, class _Hash, class _Equal, class _Alloc> 1866template <class _Key> 1867pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 1868 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 1869__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 1870 const _Key& __k) const 1871{ 1872 const_iterator __i = find(__k); 1873 const_iterator __j = __i; 1874 if (__i != end()) 1875 { 1876 const_iterator __e = end(); 1877 do 1878 { 1879 ++__j; 1880 } while (__j != __e && key_eq()(*__j, __k)); 1881 } 1882 return pair<const_iterator, const_iterator>(__i, __j); 1883} 1884 1885template <class _Tp, class _Hash, class _Equal, class _Alloc> 1886void 1887__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 1888 _NOEXCEPT_( 1889 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 1890 __is_nothrow_swappable<__pointer_allocator>::value) && 1891 (!__node_traits::propagate_on_container_swap::value || 1892 __is_nothrow_swappable<__node_allocator>::value) && 1893 __is_nothrow_swappable<hasher>::value && 1894 __is_nothrow_swappable<key_equal>::value) 1895{ 1896 { 1897 __node_pointer_pointer __npp = __bucket_list_.release(); 1898 __bucket_list_.reset(__u.__bucket_list_.release()); 1899 __u.__bucket_list_.reset(__npp); 1900 } 1901 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 1902 __swap_alloc(__bucket_list_.get_deleter().__alloc(), 1903 __u.__bucket_list_.get_deleter().__alloc()); 1904 __swap_alloc(__node_alloc(), __u.__node_alloc()); 1905 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 1906 __p2_.swap(__u.__p2_); 1907 __p3_.swap(__u.__p3_); 1908 if (size() > 0) 1909 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1910 static_cast<__node_pointer>(_VSTD::addressof(__p1_.first())); 1911 if (__u.size() > 0) 1912 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 1913 static_cast<__node_pointer>(_VSTD::addressof(__u.__p1_.first())); 1914} 1915 1916template <class _Tp, class _Hash, class _Equal, class _Alloc> 1917typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 1918__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 1919{ 1920 __node_const_pointer __np = __bucket_list_[__n]; 1921 size_type __bc = bucket_count(); 1922 size_type __r = 0; 1923 if (__np != nullptr) 1924 { 1925 for (__np = __np->__next_; __np != nullptr && 1926 __constrain_hash(__np->__hash_, __bc) == __n; 1927 __np = __np->__next_, ++__r) 1928 ; 1929 } 1930 return __r; 1931} 1932 1933template <class _Tp, class _Hash, class _Equal, class _Alloc> 1934inline _LIBCPP_INLINE_VISIBILITY 1935void 1936swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 1937 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 1938 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1939{ 1940 __x.swap(__y); 1941} 1942 1943_LIBCPP_END_NAMESPACE_STD 1944 1945#endif // _LIBCPP__HASH_TABLE 1946