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