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 #include <__undef___deallocate> 23 24 #include <__debug> 25 26 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 27 #pragma GCC system_header 28 #endif 29 30 _LIBCPP_BEGIN_NAMESPACE_STD 31 32 _LIBCPP_FUNC_VIS 33 size_t __next_prime(size_t __n); 34 35 template <class _NodePtr> 36 struct __hash_node_base 37 { 38 typedef __hash_node_base __first_node; 39 40 _NodePtr __next_; 41 42 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {} 43 }; 44 45 template <class _Tp, class _VoidPtr> 46 struct __hash_node 47 : public __hash_node_base 48 < 49 typename pointer_traits<_VoidPtr>::template 50 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 51 rebind<__hash_node<_Tp, _VoidPtr> > 52 #else 53 rebind<__hash_node<_Tp, _VoidPtr> >::other 54 #endif 55 > 56 { 57 typedef _Tp value_type; 58 59 size_t __hash_; 60 value_type __value_; 61 }; 62 63 inline _LIBCPP_INLINE_VISIBILITY 64 bool 65 __is_hash_power2(size_t __bc) 66 { 67 return __bc > 2 && !(__bc & (__bc - 1)); 68 } 69 70 inline _LIBCPP_INLINE_VISIBILITY 71 size_t 72 __constrain_hash(size_t __h, size_t __bc) 73 { 74 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc; 75 } 76 77 inline _LIBCPP_INLINE_VISIBILITY 78 size_t 79 __next_hash_pow2(size_t __n) 80 { 81 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 82 } 83 84 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 85 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 86 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 87 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 88 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 89 class _LIBCPP_TYPE_VIS_ONLY unordered_map; 90 91 template <class _NodePtr> 92 class _LIBCPP_TYPE_VIS_ONLY __hash_iterator 93 { 94 typedef _NodePtr __node_pointer; 95 96 __node_pointer __node_; 97 98 public: 99 typedef forward_iterator_tag iterator_category; 100 typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type; 101 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 102 typedef value_type& reference; 103 typedef typename pointer_traits<__node_pointer>::template 104 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 105 rebind<value_type> 106 #else 107 rebind<value_type>::other 108 #endif 109 pointer; 110 111 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 112 #if _LIBCPP_STD_VER > 11 113 : __node_(nullptr) 114 #endif 115 { 116 #if _LIBCPP_DEBUG_LEVEL >= 2 117 __get_db()->__insert_i(this); 118 #endif 119 } 120 121 #if _LIBCPP_DEBUG_LEVEL >= 2 122 123 _LIBCPP_INLINE_VISIBILITY 124 __hash_iterator(const __hash_iterator& __i) 125 : __node_(__i.__node_) 126 { 127 __get_db()->__iterator_copy(this, &__i); 128 } 129 130 _LIBCPP_INLINE_VISIBILITY 131 ~__hash_iterator() 132 { 133 __get_db()->__erase_i(this); 134 } 135 136 _LIBCPP_INLINE_VISIBILITY 137 __hash_iterator& operator=(const __hash_iterator& __i) 138 { 139 if (this != &__i) 140 { 141 __get_db()->__iterator_copy(this, &__i); 142 __node_ = __i.__node_; 143 } 144 return *this; 145 } 146 147 #endif // _LIBCPP_DEBUG_LEVEL >= 2 148 149 _LIBCPP_INLINE_VISIBILITY 150 reference operator*() const 151 { 152 #if _LIBCPP_DEBUG_LEVEL >= 2 153 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 154 "Attempted to dereference a non-dereferenceable unordered container iterator"); 155 #endif 156 return __node_->__value_; 157 } 158 _LIBCPP_INLINE_VISIBILITY 159 pointer operator->() const 160 { 161 #if _LIBCPP_DEBUG_LEVEL >= 2 162 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 163 "Attempted to dereference a non-dereferenceable unordered container iterator"); 164 #endif 165 return pointer_traits<pointer>::pointer_to(__node_->__value_); 166 } 167 168 _LIBCPP_INLINE_VISIBILITY 169 __hash_iterator& operator++() 170 { 171 #if _LIBCPP_DEBUG_LEVEL >= 2 172 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 173 "Attempted to increment non-incrementable unordered container iterator"); 174 #endif 175 __node_ = __node_->__next_; 176 return *this; 177 } 178 179 _LIBCPP_INLINE_VISIBILITY 180 __hash_iterator operator++(int) 181 { 182 __hash_iterator __t(*this); 183 ++(*this); 184 return __t; 185 } 186 187 friend _LIBCPP_INLINE_VISIBILITY 188 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 189 { 190 return __x.__node_ == __y.__node_; 191 } 192 friend _LIBCPP_INLINE_VISIBILITY 193 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 194 {return !(__x == __y);} 195 196 private: 197 #if _LIBCPP_DEBUG_LEVEL >= 2 198 _LIBCPP_INLINE_VISIBILITY 199 __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 200 : __node_(__node) 201 { 202 __get_db()->__insert_ic(this, __c); 203 } 204 #else 205 _LIBCPP_INLINE_VISIBILITY 206 __hash_iterator(__node_pointer __node) _NOEXCEPT 207 : __node_(__node) 208 {} 209 #endif 210 211 template <class, class, class, class> friend class __hash_table; 212 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 213 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 214 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 215 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 216 }; 217 218 template <class _ConstNodePtr> 219 class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 220 { 221 typedef _ConstNodePtr __node_pointer; 222 223 __node_pointer __node_; 224 225 typedef typename remove_const< 226 typename pointer_traits<__node_pointer>::element_type 227 >::type __node; 228 229 public: 230 typedef forward_iterator_tag iterator_category; 231 typedef typename __node::value_type value_type; 232 typedef typename pointer_traits<__node_pointer>::difference_type difference_type; 233 typedef const value_type& reference; 234 typedef typename pointer_traits<__node_pointer>::template 235 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 236 rebind<const value_type> 237 #else 238 rebind<const value_type>::other 239 #endif 240 pointer; 241 typedef typename pointer_traits<__node_pointer>::template 242 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 243 rebind<__node> 244 #else 245 rebind<__node>::other 246 #endif 247 __non_const_node_pointer; 248 typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator; 249 250 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 251 #if _LIBCPP_STD_VER > 11 252 : __node_(nullptr) 253 #endif 254 { 255 #if _LIBCPP_DEBUG_LEVEL >= 2 256 __get_db()->__insert_i(this); 257 #endif 258 } 259 _LIBCPP_INLINE_VISIBILITY 260 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 261 : __node_(__x.__node_) 262 { 263 #if _LIBCPP_DEBUG_LEVEL >= 2 264 __get_db()->__iterator_copy(this, &__x); 265 #endif 266 } 267 268 #if _LIBCPP_DEBUG_LEVEL >= 2 269 270 _LIBCPP_INLINE_VISIBILITY 271 __hash_const_iterator(const __hash_const_iterator& __i) 272 : __node_(__i.__node_) 273 { 274 __get_db()->__iterator_copy(this, &__i); 275 } 276 277 _LIBCPP_INLINE_VISIBILITY 278 ~__hash_const_iterator() 279 { 280 __get_db()->__erase_i(this); 281 } 282 283 _LIBCPP_INLINE_VISIBILITY 284 __hash_const_iterator& operator=(const __hash_const_iterator& __i) 285 { 286 if (this != &__i) 287 { 288 __get_db()->__iterator_copy(this, &__i); 289 __node_ = __i.__node_; 290 } 291 return *this; 292 } 293 294 #endif // _LIBCPP_DEBUG_LEVEL >= 2 295 296 _LIBCPP_INLINE_VISIBILITY 297 reference operator*() const 298 { 299 #if _LIBCPP_DEBUG_LEVEL >= 2 300 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 301 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 302 #endif 303 return __node_->__value_; 304 } 305 _LIBCPP_INLINE_VISIBILITY 306 pointer operator->() const 307 { 308 #if _LIBCPP_DEBUG_LEVEL >= 2 309 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 310 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 311 #endif 312 return pointer_traits<pointer>::pointer_to(__node_->__value_); 313 } 314 315 _LIBCPP_INLINE_VISIBILITY 316 __hash_const_iterator& operator++() 317 { 318 #if _LIBCPP_DEBUG_LEVEL >= 2 319 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 320 "Attempted to increment non-incrementable unordered container const_iterator"); 321 #endif 322 __node_ = __node_->__next_; 323 return *this; 324 } 325 326 _LIBCPP_INLINE_VISIBILITY 327 __hash_const_iterator operator++(int) 328 { 329 __hash_const_iterator __t(*this); 330 ++(*this); 331 return __t; 332 } 333 334 friend _LIBCPP_INLINE_VISIBILITY 335 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 336 { 337 return __x.__node_ == __y.__node_; 338 } 339 friend _LIBCPP_INLINE_VISIBILITY 340 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 341 {return !(__x == __y);} 342 343 private: 344 #if _LIBCPP_DEBUG_LEVEL >= 2 345 _LIBCPP_INLINE_VISIBILITY 346 __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 347 : __node_(__node) 348 { 349 __get_db()->__insert_ic(this, __c); 350 } 351 #else 352 _LIBCPP_INLINE_VISIBILITY 353 __hash_const_iterator(__node_pointer __node) _NOEXCEPT 354 : __node_(__node) 355 {} 356 #endif 357 358 template <class, class, class, class> friend class __hash_table; 359 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 360 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 361 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 362 }; 363 364 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 365 366 template <class _NodePtr> 367 class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 368 { 369 typedef _NodePtr __node_pointer; 370 371 __node_pointer __node_; 372 size_t __bucket_; 373 size_t __bucket_count_; 374 375 typedef pointer_traits<__node_pointer> __pointer_traits; 376 public: 377 typedef forward_iterator_tag iterator_category; 378 typedef typename __pointer_traits::element_type::value_type value_type; 379 typedef typename __pointer_traits::difference_type difference_type; 380 typedef value_type& reference; 381 typedef typename __pointer_traits::template 382 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 383 rebind<value_type> 384 #else 385 rebind<value_type>::other 386 #endif 387 pointer; 388 389 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 390 { 391 #if _LIBCPP_DEBUG_LEVEL >= 2 392 __get_db()->__insert_i(this); 393 #endif 394 } 395 396 #if _LIBCPP_DEBUG_LEVEL >= 2 397 398 _LIBCPP_INLINE_VISIBILITY 399 __hash_local_iterator(const __hash_local_iterator& __i) 400 : __node_(__i.__node_), 401 __bucket_(__i.__bucket_), 402 __bucket_count_(__i.__bucket_count_) 403 { 404 __get_db()->__iterator_copy(this, &__i); 405 } 406 407 _LIBCPP_INLINE_VISIBILITY 408 ~__hash_local_iterator() 409 { 410 __get_db()->__erase_i(this); 411 } 412 413 _LIBCPP_INLINE_VISIBILITY 414 __hash_local_iterator& operator=(const __hash_local_iterator& __i) 415 { 416 if (this != &__i) 417 { 418 __get_db()->__iterator_copy(this, &__i); 419 __node_ = __i.__node_; 420 __bucket_ = __i.__bucket_; 421 __bucket_count_ = __i.__bucket_count_; 422 } 423 return *this; 424 } 425 426 #endif // _LIBCPP_DEBUG_LEVEL >= 2 427 428 _LIBCPP_INLINE_VISIBILITY 429 reference operator*() const 430 { 431 #if _LIBCPP_DEBUG_LEVEL >= 2 432 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 433 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 434 #endif 435 return __node_->__value_; 436 } 437 _LIBCPP_INLINE_VISIBILITY 438 pointer operator->() const 439 { 440 #if _LIBCPP_DEBUG_LEVEL >= 2 441 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 442 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 443 #endif 444 return pointer_traits<pointer>::pointer_to(__node_->__value_); 445 } 446 447 _LIBCPP_INLINE_VISIBILITY 448 __hash_local_iterator& operator++() 449 { 450 #if _LIBCPP_DEBUG_LEVEL >= 2 451 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 452 "Attempted to increment non-incrementable unordered container local_iterator"); 453 #endif 454 __node_ = __node_->__next_; 455 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 456 __node_ = nullptr; 457 return *this; 458 } 459 460 _LIBCPP_INLINE_VISIBILITY 461 __hash_local_iterator operator++(int) 462 { 463 __hash_local_iterator __t(*this); 464 ++(*this); 465 return __t; 466 } 467 468 friend _LIBCPP_INLINE_VISIBILITY 469 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 470 { 471 return __x.__node_ == __y.__node_; 472 } 473 friend _LIBCPP_INLINE_VISIBILITY 474 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 475 {return !(__x == __y);} 476 477 private: 478 #if _LIBCPP_DEBUG_LEVEL >= 2 479 _LIBCPP_INLINE_VISIBILITY 480 __hash_local_iterator(__node_pointer __node, size_t __bucket, 481 size_t __bucket_count, const void* __c) _NOEXCEPT 482 : __node_(__node), 483 __bucket_(__bucket), 484 __bucket_count_(__bucket_count) 485 { 486 __get_db()->__insert_ic(this, __c); 487 if (__node_ != nullptr) 488 __node_ = __node_->__next_; 489 } 490 #else 491 _LIBCPP_INLINE_VISIBILITY 492 __hash_local_iterator(__node_pointer __node, size_t __bucket, 493 size_t __bucket_count) _NOEXCEPT 494 : __node_(__node), 495 __bucket_(__bucket), 496 __bucket_count_(__bucket_count) 497 { 498 if (__node_ != nullptr) 499 __node_ = __node_->__next_; 500 } 501 #endif 502 template <class, class, class, class> friend class __hash_table; 503 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 504 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 505 }; 506 507 template <class _ConstNodePtr> 508 class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 509 { 510 typedef _ConstNodePtr __node_pointer; 511 512 __node_pointer __node_; 513 size_t __bucket_; 514 size_t __bucket_count_; 515 516 typedef pointer_traits<__node_pointer> __pointer_traits; 517 typedef typename __pointer_traits::element_type __node; 518 typedef typename remove_const<__node>::type __non_const_node; 519 typedef typename pointer_traits<__node_pointer>::template 520 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 521 rebind<__non_const_node> 522 #else 523 rebind<__non_const_node>::other 524 #endif 525 __non_const_node_pointer; 526 typedef __hash_local_iterator<__non_const_node_pointer> 527 __non_const_iterator; 528 public: 529 typedef forward_iterator_tag iterator_category; 530 typedef typename remove_const< 531 typename __pointer_traits::element_type::value_type 532 >::type value_type; 533 typedef typename __pointer_traits::difference_type difference_type; 534 typedef const value_type& reference; 535 typedef typename __pointer_traits::template 536 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 537 rebind<const value_type> 538 #else 539 rebind<const value_type>::other 540 #endif 541 pointer; 542 543 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 544 { 545 #if _LIBCPP_DEBUG_LEVEL >= 2 546 __get_db()->__insert_i(this); 547 #endif 548 } 549 550 _LIBCPP_INLINE_VISIBILITY 551 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 552 : __node_(__x.__node_), 553 __bucket_(__x.__bucket_), 554 __bucket_count_(__x.__bucket_count_) 555 { 556 #if _LIBCPP_DEBUG_LEVEL >= 2 557 __get_db()->__iterator_copy(this, &__x); 558 #endif 559 } 560 561 #if _LIBCPP_DEBUG_LEVEL >= 2 562 563 _LIBCPP_INLINE_VISIBILITY 564 __hash_const_local_iterator(const __hash_const_local_iterator& __i) 565 : __node_(__i.__node_), 566 __bucket_(__i.__bucket_), 567 __bucket_count_(__i.__bucket_count_) 568 { 569 __get_db()->__iterator_copy(this, &__i); 570 } 571 572 _LIBCPP_INLINE_VISIBILITY 573 ~__hash_const_local_iterator() 574 { 575 __get_db()->__erase_i(this); 576 } 577 578 _LIBCPP_INLINE_VISIBILITY 579 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 580 { 581 if (this != &__i) 582 { 583 __get_db()->__iterator_copy(this, &__i); 584 __node_ = __i.__node_; 585 __bucket_ = __i.__bucket_; 586 __bucket_count_ = __i.__bucket_count_; 587 } 588 return *this; 589 } 590 591 #endif // _LIBCPP_DEBUG_LEVEL >= 2 592 593 _LIBCPP_INLINE_VISIBILITY 594 reference operator*() const 595 { 596 #if _LIBCPP_DEBUG_LEVEL >= 2 597 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 598 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 599 #endif 600 return __node_->__value_; 601 } 602 _LIBCPP_INLINE_VISIBILITY 603 pointer operator->() const 604 { 605 #if _LIBCPP_DEBUG_LEVEL >= 2 606 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 607 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 608 #endif 609 return pointer_traits<pointer>::pointer_to(__node_->__value_); 610 } 611 612 _LIBCPP_INLINE_VISIBILITY 613 __hash_const_local_iterator& operator++() 614 { 615 #if _LIBCPP_DEBUG_LEVEL >= 2 616 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 617 "Attempted to increment non-incrementable unordered container const_local_iterator"); 618 #endif 619 __node_ = __node_->__next_; 620 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 621 __node_ = nullptr; 622 return *this; 623 } 624 625 _LIBCPP_INLINE_VISIBILITY 626 __hash_const_local_iterator operator++(int) 627 { 628 __hash_const_local_iterator __t(*this); 629 ++(*this); 630 return __t; 631 } 632 633 friend _LIBCPP_INLINE_VISIBILITY 634 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 635 { 636 return __x.__node_ == __y.__node_; 637 } 638 friend _LIBCPP_INLINE_VISIBILITY 639 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 640 {return !(__x == __y);} 641 642 private: 643 #if _LIBCPP_DEBUG_LEVEL >= 2 644 _LIBCPP_INLINE_VISIBILITY 645 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 646 size_t __bucket_count, const void* __c) _NOEXCEPT 647 : __node_(__node), 648 __bucket_(__bucket), 649 __bucket_count_(__bucket_count) 650 { 651 __get_db()->__insert_ic(this, __c); 652 if (__node_ != nullptr) 653 __node_ = __node_->__next_; 654 } 655 #else 656 _LIBCPP_INLINE_VISIBILITY 657 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 658 size_t __bucket_count) _NOEXCEPT 659 : __node_(__node), 660 __bucket_(__bucket), 661 __bucket_count_(__bucket_count) 662 { 663 if (__node_ != nullptr) 664 __node_ = __node_->__next_; 665 } 666 #endif 667 template <class, class, class, class> friend class __hash_table; 668 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 669 }; 670 671 template <class _Alloc> 672 class __bucket_list_deallocator 673 { 674 typedef _Alloc allocator_type; 675 typedef allocator_traits<allocator_type> __alloc_traits; 676 typedef typename __alloc_traits::size_type size_type; 677 678 __compressed_pair<size_type, allocator_type> __data_; 679 public: 680 typedef typename __alloc_traits::pointer pointer; 681 682 _LIBCPP_INLINE_VISIBILITY 683 __bucket_list_deallocator() 684 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 685 : __data_(0) {} 686 687 _LIBCPP_INLINE_VISIBILITY 688 __bucket_list_deallocator(const allocator_type& __a, size_type __size) 689 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 690 : __data_(__size, __a) {} 691 692 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 693 694 _LIBCPP_INLINE_VISIBILITY 695 __bucket_list_deallocator(__bucket_list_deallocator&& __x) 696 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 697 : __data_(_VSTD::move(__x.__data_)) 698 { 699 __x.size() = 0; 700 } 701 702 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 703 704 _LIBCPP_INLINE_VISIBILITY 705 size_type& size() _NOEXCEPT {return __data_.first();} 706 _LIBCPP_INLINE_VISIBILITY 707 size_type size() const _NOEXCEPT {return __data_.first();} 708 709 _LIBCPP_INLINE_VISIBILITY 710 allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 711 _LIBCPP_INLINE_VISIBILITY 712 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 713 714 _LIBCPP_INLINE_VISIBILITY 715 void operator()(pointer __p) _NOEXCEPT 716 { 717 __alloc_traits::deallocate(__alloc(), __p, size()); 718 } 719 }; 720 721 template <class _Alloc> class __hash_map_node_destructor; 722 723 template <class _Alloc> 724 class __hash_node_destructor 725 { 726 typedef _Alloc allocator_type; 727 typedef allocator_traits<allocator_type> __alloc_traits; 728 typedef typename __alloc_traits::value_type::value_type value_type; 729 public: 730 typedef typename __alloc_traits::pointer pointer; 731 private: 732 733 allocator_type& __na_; 734 735 __hash_node_destructor& operator=(const __hash_node_destructor&); 736 737 public: 738 bool __value_constructed; 739 740 _LIBCPP_INLINE_VISIBILITY 741 explicit __hash_node_destructor(allocator_type& __na, 742 bool __constructed = false) _NOEXCEPT 743 : __na_(__na), 744 __value_constructed(__constructed) 745 {} 746 747 _LIBCPP_INLINE_VISIBILITY 748 void operator()(pointer __p) _NOEXCEPT 749 { 750 if (__value_constructed) 751 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_)); 752 if (__p) 753 __alloc_traits::deallocate(__na_, __p, 1); 754 } 755 756 template <class> friend class __hash_map_node_destructor; 757 }; 758 759 template <class _Tp, class _Hash, class _Equal, class _Alloc> 760 class __hash_table 761 { 762 public: 763 typedef _Tp value_type; 764 typedef _Hash hasher; 765 typedef _Equal key_equal; 766 typedef _Alloc allocator_type; 767 768 private: 769 typedef allocator_traits<allocator_type> __alloc_traits; 770 public: 771 typedef value_type& reference; 772 typedef const value_type& const_reference; 773 typedef typename __alloc_traits::pointer pointer; 774 typedef typename __alloc_traits::const_pointer const_pointer; 775 typedef typename __alloc_traits::size_type size_type; 776 typedef typename __alloc_traits::difference_type difference_type; 777 public: 778 // Create __node 779 typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node; 780 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 781 typedef allocator_traits<__node_allocator> __node_traits; 782 typedef typename __node_traits::pointer __node_pointer; 783 typedef typename __node_traits::pointer __node_const_pointer; 784 typedef __hash_node_base<__node_pointer> __first_node; 785 typedef typename pointer_traits<__node_pointer>::template 786 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 787 rebind<__first_node> 788 #else 789 rebind<__first_node>::other 790 #endif 791 __node_base_pointer; 792 793 private: 794 795 typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator; 796 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 797 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 798 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 799 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 800 801 // --- Member data begin --- 802 __bucket_list __bucket_list_; 803 __compressed_pair<__first_node, __node_allocator> __p1_; 804 __compressed_pair<size_type, hasher> __p2_; 805 __compressed_pair<float, key_equal> __p3_; 806 // --- Member data end --- 807 808 _LIBCPP_INLINE_VISIBILITY 809 size_type& size() _NOEXCEPT {return __p2_.first();} 810 public: 811 _LIBCPP_INLINE_VISIBILITY 812 size_type size() const _NOEXCEPT {return __p2_.first();} 813 814 _LIBCPP_INLINE_VISIBILITY 815 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 816 _LIBCPP_INLINE_VISIBILITY 817 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 818 819 _LIBCPP_INLINE_VISIBILITY 820 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 821 _LIBCPP_INLINE_VISIBILITY 822 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 823 824 _LIBCPP_INLINE_VISIBILITY 825 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 826 _LIBCPP_INLINE_VISIBILITY 827 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 828 829 _LIBCPP_INLINE_VISIBILITY 830 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 831 _LIBCPP_INLINE_VISIBILITY 832 const __node_allocator& __node_alloc() const _NOEXCEPT 833 {return __p1_.second();} 834 835 public: 836 typedef __hash_iterator<__node_pointer> iterator; 837 typedef __hash_const_iterator<__node_pointer> const_iterator; 838 typedef __hash_local_iterator<__node_pointer> local_iterator; 839 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 840 841 __hash_table() 842 _NOEXCEPT_( 843 is_nothrow_default_constructible<__bucket_list>::value && 844 is_nothrow_default_constructible<__first_node>::value && 845 is_nothrow_default_constructible<__node_allocator>::value && 846 is_nothrow_default_constructible<hasher>::value && 847 is_nothrow_default_constructible<key_equal>::value); 848 __hash_table(const hasher& __hf, const key_equal& __eql); 849 __hash_table(const hasher& __hf, const key_equal& __eql, 850 const allocator_type& __a); 851 explicit __hash_table(const allocator_type& __a); 852 __hash_table(const __hash_table& __u); 853 __hash_table(const __hash_table& __u, const allocator_type& __a); 854 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 855 __hash_table(__hash_table&& __u) 856 _NOEXCEPT_( 857 is_nothrow_move_constructible<__bucket_list>::value && 858 is_nothrow_move_constructible<__first_node>::value && 859 is_nothrow_move_constructible<__node_allocator>::value && 860 is_nothrow_move_constructible<hasher>::value && 861 is_nothrow_move_constructible<key_equal>::value); 862 __hash_table(__hash_table&& __u, const allocator_type& __a); 863 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 864 ~__hash_table(); 865 866 __hash_table& operator=(const __hash_table& __u); 867 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 868 __hash_table& operator=(__hash_table&& __u) 869 _NOEXCEPT_( 870 __node_traits::propagate_on_container_move_assignment::value && 871 is_nothrow_move_assignable<__node_allocator>::value && 872 is_nothrow_move_assignable<hasher>::value && 873 is_nothrow_move_assignable<key_equal>::value); 874 #endif 875 template <class _InputIterator> 876 void __assign_unique(_InputIterator __first, _InputIterator __last); 877 template <class _InputIterator> 878 void __assign_multi(_InputIterator __first, _InputIterator __last); 879 880 _LIBCPP_INLINE_VISIBILITY 881 size_type max_size() const _NOEXCEPT 882 { 883 return allocator_traits<__pointer_allocator>::max_size( 884 __bucket_list_.get_deleter().__alloc()); 885 } 886 887 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 888 iterator __node_insert_multi(__node_pointer __nd); 889 iterator __node_insert_multi(const_iterator __p, 890 __node_pointer __nd); 891 892 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 893 template <class... _Args> 894 pair<iterator, bool> __emplace_unique(_Args&&... __args); 895 template <class... _Args> 896 iterator __emplace_multi(_Args&&... __args); 897 template <class... _Args> 898 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 899 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 900 901 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 902 template <class _ValueTp> 903 _LIBCPP_INLINE_VISIBILITY 904 pair<iterator, bool> __insert_unique_value(_ValueTp&& __x); 905 #else 906 _LIBCPP_INLINE_VISIBILITY 907 pair<iterator, bool> __insert_unique_value(const value_type& __x); 908 #endif 909 910 pair<iterator, bool> __insert_unique(const value_type& __x); 911 912 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 913 pair<iterator, bool> __insert_unique(value_type&& __x); 914 template <class _Pp> 915 pair<iterator, bool> __insert_unique(_Pp&& __x); 916 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 917 918 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 919 template <class _Pp> 920 iterator __insert_multi(_Pp&& __x); 921 template <class _Pp> 922 iterator __insert_multi(const_iterator __p, _Pp&& __x); 923 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 924 iterator __insert_multi(const value_type& __x); 925 iterator __insert_multi(const_iterator __p, const value_type& __x); 926 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 927 928 void clear() _NOEXCEPT; 929 void rehash(size_type __n); 930 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 931 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 932 933 _LIBCPP_INLINE_VISIBILITY 934 size_type bucket_count() const _NOEXCEPT 935 { 936 return __bucket_list_.get_deleter().size(); 937 } 938 939 iterator begin() _NOEXCEPT; 940 iterator end() _NOEXCEPT; 941 const_iterator begin() const _NOEXCEPT; 942 const_iterator end() const _NOEXCEPT; 943 944 template <class _Key> 945 _LIBCPP_INLINE_VISIBILITY 946 size_type bucket(const _Key& __k) const 947 { 948 _LIBCPP_ASSERT(bucket_count() > 0, 949 "unordered container::bucket(key) called when bucket_count() == 0"); 950 return __constrain_hash(hash_function()(__k), bucket_count()); 951 } 952 953 template <class _Key> 954 iterator find(const _Key& __x); 955 template <class _Key> 956 const_iterator find(const _Key& __x) const; 957 958 typedef __hash_node_destructor<__node_allocator> _Dp; 959 typedef unique_ptr<__node, _Dp> __node_holder; 960 961 iterator erase(const_iterator __p); 962 iterator erase(const_iterator __first, const_iterator __last); 963 template <class _Key> 964 size_type __erase_unique(const _Key& __k); 965 template <class _Key> 966 size_type __erase_multi(const _Key& __k); 967 __node_holder remove(const_iterator __p) _NOEXCEPT; 968 969 template <class _Key> 970 size_type __count_unique(const _Key& __k) const; 971 template <class _Key> 972 size_type __count_multi(const _Key& __k) const; 973 974 template <class _Key> 975 pair<iterator, iterator> 976 __equal_range_unique(const _Key& __k); 977 template <class _Key> 978 pair<const_iterator, const_iterator> 979 __equal_range_unique(const _Key& __k) const; 980 981 template <class _Key> 982 pair<iterator, iterator> 983 __equal_range_multi(const _Key& __k); 984 template <class _Key> 985 pair<const_iterator, const_iterator> 986 __equal_range_multi(const _Key& __k) const; 987 988 void swap(__hash_table& __u) 989 #if _LIBCPP_STD_VER <= 11 990 _NOEXCEPT_( 991 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 992 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 993 || __is_nothrow_swappable<__pointer_allocator>::value) 994 && (!__node_traits::propagate_on_container_swap::value 995 || __is_nothrow_swappable<__node_allocator>::value) 996 ); 997 #else 998 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 999 #endif 1000 1001 _LIBCPP_INLINE_VISIBILITY 1002 size_type max_bucket_count() const _NOEXCEPT 1003 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1004 size_type bucket_size(size_type __n) const; 1005 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1006 { 1007 size_type __bc = bucket_count(); 1008 return __bc != 0 ? (float)size() / __bc : 0.f; 1009 } 1010 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1011 { 1012 _LIBCPP_ASSERT(__mlf > 0, 1013 "unordered container::max_load_factor(lf) called with lf <= 0"); 1014 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1015 } 1016 1017 _LIBCPP_INLINE_VISIBILITY 1018 local_iterator 1019 begin(size_type __n) 1020 { 1021 _LIBCPP_ASSERT(__n < bucket_count(), 1022 "unordered container::begin(n) called with n >= bucket_count()"); 1023 #if _LIBCPP_DEBUG_LEVEL >= 2 1024 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1025 #else 1026 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1027 #endif 1028 } 1029 1030 _LIBCPP_INLINE_VISIBILITY 1031 local_iterator 1032 end(size_type __n) 1033 { 1034 _LIBCPP_ASSERT(__n < bucket_count(), 1035 "unordered container::end(n) called with n >= bucket_count()"); 1036 #if _LIBCPP_DEBUG_LEVEL >= 2 1037 return local_iterator(nullptr, __n, bucket_count(), this); 1038 #else 1039 return local_iterator(nullptr, __n, bucket_count()); 1040 #endif 1041 } 1042 1043 _LIBCPP_INLINE_VISIBILITY 1044 const_local_iterator 1045 cbegin(size_type __n) const 1046 { 1047 _LIBCPP_ASSERT(__n < bucket_count(), 1048 "unordered container::cbegin(n) called with n >= bucket_count()"); 1049 #if _LIBCPP_DEBUG_LEVEL >= 2 1050 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1051 #else 1052 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1053 #endif 1054 } 1055 1056 _LIBCPP_INLINE_VISIBILITY 1057 const_local_iterator 1058 cend(size_type __n) const 1059 { 1060 _LIBCPP_ASSERT(__n < bucket_count(), 1061 "unordered container::cend(n) called with n >= bucket_count()"); 1062 #if _LIBCPP_DEBUG_LEVEL >= 2 1063 return const_local_iterator(nullptr, __n, bucket_count(), this); 1064 #else 1065 return const_local_iterator(nullptr, __n, bucket_count()); 1066 #endif 1067 } 1068 1069 #if _LIBCPP_DEBUG_LEVEL >= 2 1070 1071 bool __dereferenceable(const const_iterator* __i) const; 1072 bool __decrementable(const const_iterator* __i) const; 1073 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1074 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1075 1076 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1077 1078 private: 1079 void __rehash(size_type __n); 1080 1081 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1082 #ifndef _LIBCPP_HAS_NO_VARIADICS 1083 template <class ..._Args> 1084 __node_holder __construct_node(_Args&& ...__args); 1085 #endif // _LIBCPP_HAS_NO_VARIADICS 1086 __node_holder __construct_node(value_type&& __v, size_t __hash); 1087 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1088 __node_holder __construct_node(const value_type& __v); 1089 #endif 1090 __node_holder __construct_node(const value_type& __v, size_t __hash); 1091 1092 _LIBCPP_INLINE_VISIBILITY 1093 void __copy_assign_alloc(const __hash_table& __u) 1094 {__copy_assign_alloc(__u, integral_constant<bool, 1095 __node_traits::propagate_on_container_copy_assignment::value>());} 1096 void __copy_assign_alloc(const __hash_table& __u, true_type); 1097 _LIBCPP_INLINE_VISIBILITY 1098 void __copy_assign_alloc(const __hash_table&, false_type) {} 1099 1100 void __move_assign(__hash_table& __u, false_type); 1101 void __move_assign(__hash_table& __u, true_type) 1102 _NOEXCEPT_( 1103 is_nothrow_move_assignable<__node_allocator>::value && 1104 is_nothrow_move_assignable<hasher>::value && 1105 is_nothrow_move_assignable<key_equal>::value); 1106 _LIBCPP_INLINE_VISIBILITY 1107 void __move_assign_alloc(__hash_table& __u) 1108 _NOEXCEPT_( 1109 !__node_traits::propagate_on_container_move_assignment::value || 1110 (is_nothrow_move_assignable<__pointer_allocator>::value && 1111 is_nothrow_move_assignable<__node_allocator>::value)) 1112 {__move_assign_alloc(__u, integral_constant<bool, 1113 __node_traits::propagate_on_container_move_assignment::value>());} 1114 _LIBCPP_INLINE_VISIBILITY 1115 void __move_assign_alloc(__hash_table& __u, true_type) 1116 _NOEXCEPT_( 1117 is_nothrow_move_assignable<__pointer_allocator>::value && 1118 is_nothrow_move_assignable<__node_allocator>::value) 1119 { 1120 __bucket_list_.get_deleter().__alloc() = 1121 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1122 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1123 } 1124 _LIBCPP_INLINE_VISIBILITY 1125 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1126 1127 void __deallocate(__node_pointer __np) _NOEXCEPT; 1128 __node_pointer __detach() _NOEXCEPT; 1129 1130 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1131 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1132 }; 1133 1134 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1135 inline _LIBCPP_INLINE_VISIBILITY 1136 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1137 _NOEXCEPT_( 1138 is_nothrow_default_constructible<__bucket_list>::value && 1139 is_nothrow_default_constructible<__first_node>::value && 1140 is_nothrow_default_constructible<hasher>::value && 1141 is_nothrow_default_constructible<key_equal>::value) 1142 : __p2_(0), 1143 __p3_(1.0f) 1144 { 1145 } 1146 1147 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1148 inline _LIBCPP_INLINE_VISIBILITY 1149 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1150 const key_equal& __eql) 1151 : __bucket_list_(nullptr, __bucket_list_deleter()), 1152 __p1_(), 1153 __p2_(0, __hf), 1154 __p3_(1.0f, __eql) 1155 { 1156 } 1157 1158 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1159 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1160 const key_equal& __eql, 1161 const allocator_type& __a) 1162 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1163 __p1_(__node_allocator(__a)), 1164 __p2_(0, __hf), 1165 __p3_(1.0f, __eql) 1166 { 1167 } 1168 1169 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1170 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1171 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1172 __p1_(__node_allocator(__a)), 1173 __p2_(0), 1174 __p3_(1.0f) 1175 { 1176 } 1177 1178 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1179 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1180 : __bucket_list_(nullptr, 1181 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1182 select_on_container_copy_construction( 1183 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1184 __p1_(allocator_traits<__node_allocator>:: 1185 select_on_container_copy_construction(__u.__node_alloc())), 1186 __p2_(0, __u.hash_function()), 1187 __p3_(__u.__p3_) 1188 { 1189 } 1190 1191 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1192 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1193 const allocator_type& __a) 1194 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1195 __p1_(__node_allocator(__a)), 1196 __p2_(0, __u.hash_function()), 1197 __p3_(__u.__p3_) 1198 { 1199 } 1200 1201 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1202 1203 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1204 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1205 _NOEXCEPT_( 1206 is_nothrow_move_constructible<__bucket_list>::value && 1207 is_nothrow_move_constructible<__first_node>::value && 1208 is_nothrow_move_constructible<hasher>::value && 1209 is_nothrow_move_constructible<key_equal>::value) 1210 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1211 __p1_(_VSTD::move(__u.__p1_)), 1212 __p2_(_VSTD::move(__u.__p2_)), 1213 __p3_(_VSTD::move(__u.__p3_)) 1214 { 1215 if (size() > 0) 1216 { 1217 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1218 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1219 __u.__p1_.first().__next_ = nullptr; 1220 __u.size() = 0; 1221 } 1222 } 1223 1224 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1225 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1226 const allocator_type& __a) 1227 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1228 __p1_(__node_allocator(__a)), 1229 __p2_(0, _VSTD::move(__u.hash_function())), 1230 __p3_(_VSTD::move(__u.__p3_)) 1231 { 1232 if (__a == allocator_type(__u.__node_alloc())) 1233 { 1234 __bucket_list_.reset(__u.__bucket_list_.release()); 1235 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1236 __u.__bucket_list_.get_deleter().size() = 0; 1237 if (__u.size() > 0) 1238 { 1239 __p1_.first().__next_ = __u.__p1_.first().__next_; 1240 __u.__p1_.first().__next_ = nullptr; 1241 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1242 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1243 size() = __u.size(); 1244 __u.size() = 0; 1245 } 1246 } 1247 } 1248 1249 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1250 1251 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1252 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1253 { 1254 __deallocate(__p1_.first().__next_); 1255 #if _LIBCPP_DEBUG_LEVEL >= 2 1256 __get_db()->__erase_c(this); 1257 #endif 1258 } 1259 1260 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1261 void 1262 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1263 const __hash_table& __u, true_type) 1264 { 1265 if (__node_alloc() != __u.__node_alloc()) 1266 { 1267 clear(); 1268 __bucket_list_.reset(); 1269 __bucket_list_.get_deleter().size() = 0; 1270 } 1271 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1272 __node_alloc() = __u.__node_alloc(); 1273 } 1274 1275 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1276 __hash_table<_Tp, _Hash, _Equal, _Alloc>& 1277 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1278 { 1279 if (this != &__u) 1280 { 1281 __copy_assign_alloc(__u); 1282 hash_function() = __u.hash_function(); 1283 key_eq() = __u.key_eq(); 1284 max_load_factor() = __u.max_load_factor(); 1285 __assign_multi(__u.begin(), __u.end()); 1286 } 1287 return *this; 1288 } 1289 1290 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1291 void 1292 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1293 _NOEXCEPT 1294 { 1295 __node_allocator& __na = __node_alloc(); 1296 while (__np != nullptr) 1297 { 1298 __node_pointer __next = __np->__next_; 1299 #if _LIBCPP_DEBUG_LEVEL >= 2 1300 __c_node* __c = __get_db()->__find_c_and_lock(this); 1301 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1302 { 1303 --__p; 1304 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1305 if (__i->__node_ == __np) 1306 { 1307 (*__p)->__c_ = nullptr; 1308 if (--__c->end_ != __p) 1309 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1310 } 1311 } 1312 __get_db()->unlock(); 1313 #endif 1314 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1315 __node_traits::deallocate(__na, __np, 1); 1316 __np = __next; 1317 } 1318 } 1319 1320 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1321 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1322 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1323 { 1324 size_type __bc = bucket_count(); 1325 for (size_type __i = 0; __i < __bc; ++__i) 1326 __bucket_list_[__i] = nullptr; 1327 size() = 0; 1328 __node_pointer __cache = __p1_.first().__next_; 1329 __p1_.first().__next_ = nullptr; 1330 return __cache; 1331 } 1332 1333 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1334 1335 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1336 void 1337 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1338 __hash_table& __u, true_type) 1339 _NOEXCEPT_( 1340 is_nothrow_move_assignable<__node_allocator>::value && 1341 is_nothrow_move_assignable<hasher>::value && 1342 is_nothrow_move_assignable<key_equal>::value) 1343 { 1344 clear(); 1345 __bucket_list_.reset(__u.__bucket_list_.release()); 1346 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1347 __u.__bucket_list_.get_deleter().size() = 0; 1348 __move_assign_alloc(__u); 1349 size() = __u.size(); 1350 hash_function() = _VSTD::move(__u.hash_function()); 1351 max_load_factor() = __u.max_load_factor(); 1352 key_eq() = _VSTD::move(__u.key_eq()); 1353 __p1_.first().__next_ = __u.__p1_.first().__next_; 1354 if (size() > 0) 1355 { 1356 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1357 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1358 __u.__p1_.first().__next_ = nullptr; 1359 __u.size() = 0; 1360 } 1361 #if _LIBCPP_DEBUG_LEVEL >= 2 1362 __get_db()->swap(this, &__u); 1363 #endif 1364 } 1365 1366 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1367 void 1368 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1369 __hash_table& __u, false_type) 1370 { 1371 if (__node_alloc() == __u.__node_alloc()) 1372 __move_assign(__u, true_type()); 1373 else 1374 { 1375 hash_function() = _VSTD::move(__u.hash_function()); 1376 key_eq() = _VSTD::move(__u.key_eq()); 1377 max_load_factor() = __u.max_load_factor(); 1378 if (bucket_count() != 0) 1379 { 1380 __node_pointer __cache = __detach(); 1381 #ifndef _LIBCPP_NO_EXCEPTIONS 1382 try 1383 { 1384 #endif // _LIBCPP_NO_EXCEPTIONS 1385 const_iterator __i = __u.begin(); 1386 while (__cache != nullptr && __u.size() != 0) 1387 { 1388 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1389 __node_pointer __next = __cache->__next_; 1390 __node_insert_multi(__cache); 1391 __cache = __next; 1392 } 1393 #ifndef _LIBCPP_NO_EXCEPTIONS 1394 } 1395 catch (...) 1396 { 1397 __deallocate(__cache); 1398 throw; 1399 } 1400 #endif // _LIBCPP_NO_EXCEPTIONS 1401 __deallocate(__cache); 1402 } 1403 const_iterator __i = __u.begin(); 1404 while (__u.size() != 0) 1405 { 1406 __node_holder __h = 1407 __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1408 __node_insert_multi(__h.get()); 1409 __h.release(); 1410 } 1411 } 1412 } 1413 1414 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1415 inline _LIBCPP_INLINE_VISIBILITY 1416 __hash_table<_Tp, _Hash, _Equal, _Alloc>& 1417 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1418 _NOEXCEPT_( 1419 __node_traits::propagate_on_container_move_assignment::value && 1420 is_nothrow_move_assignable<__node_allocator>::value && 1421 is_nothrow_move_assignable<hasher>::value && 1422 is_nothrow_move_assignable<key_equal>::value) 1423 { 1424 __move_assign(__u, integral_constant<bool, 1425 __node_traits::propagate_on_container_move_assignment::value>()); 1426 return *this; 1427 } 1428 1429 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1430 1431 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1432 template <class _InputIterator> 1433 void 1434 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1435 _InputIterator __last) 1436 { 1437 if (bucket_count() != 0) 1438 { 1439 __node_pointer __cache = __detach(); 1440 #ifndef _LIBCPP_NO_EXCEPTIONS 1441 try 1442 { 1443 #endif // _LIBCPP_NO_EXCEPTIONS 1444 for (; __cache != nullptr && __first != __last; ++__first) 1445 { 1446 __cache->__value_ = *__first; 1447 __node_pointer __next = __cache->__next_; 1448 __node_insert_unique(__cache); 1449 __cache = __next; 1450 } 1451 #ifndef _LIBCPP_NO_EXCEPTIONS 1452 } 1453 catch (...) 1454 { 1455 __deallocate(__cache); 1456 throw; 1457 } 1458 #endif // _LIBCPP_NO_EXCEPTIONS 1459 __deallocate(__cache); 1460 } 1461 for (; __first != __last; ++__first) 1462 __insert_unique(*__first); 1463 } 1464 1465 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1466 template <class _InputIterator> 1467 void 1468 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1469 _InputIterator __last) 1470 { 1471 if (bucket_count() != 0) 1472 { 1473 __node_pointer __cache = __detach(); 1474 #ifndef _LIBCPP_NO_EXCEPTIONS 1475 try 1476 { 1477 #endif // _LIBCPP_NO_EXCEPTIONS 1478 for (; __cache != nullptr && __first != __last; ++__first) 1479 { 1480 __cache->__value_ = *__first; 1481 __node_pointer __next = __cache->__next_; 1482 __node_insert_multi(__cache); 1483 __cache = __next; 1484 } 1485 #ifndef _LIBCPP_NO_EXCEPTIONS 1486 } 1487 catch (...) 1488 { 1489 __deallocate(__cache); 1490 throw; 1491 } 1492 #endif // _LIBCPP_NO_EXCEPTIONS 1493 __deallocate(__cache); 1494 } 1495 for (; __first != __last; ++__first) 1496 __insert_multi(*__first); 1497 } 1498 1499 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1500 inline _LIBCPP_INLINE_VISIBILITY 1501 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1502 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1503 { 1504 #if _LIBCPP_DEBUG_LEVEL >= 2 1505 return iterator(__p1_.first().__next_, this); 1506 #else 1507 return iterator(__p1_.first().__next_); 1508 #endif 1509 } 1510 1511 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1512 inline _LIBCPP_INLINE_VISIBILITY 1513 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1514 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1515 { 1516 #if _LIBCPP_DEBUG_LEVEL >= 2 1517 return iterator(nullptr, this); 1518 #else 1519 return iterator(nullptr); 1520 #endif 1521 } 1522 1523 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1524 inline _LIBCPP_INLINE_VISIBILITY 1525 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1526 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1527 { 1528 #if _LIBCPP_DEBUG_LEVEL >= 2 1529 return const_iterator(__p1_.first().__next_, this); 1530 #else 1531 return const_iterator(__p1_.first().__next_); 1532 #endif 1533 } 1534 1535 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1536 inline _LIBCPP_INLINE_VISIBILITY 1537 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1538 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1539 { 1540 #if _LIBCPP_DEBUG_LEVEL >= 2 1541 return const_iterator(nullptr, this); 1542 #else 1543 return const_iterator(nullptr); 1544 #endif 1545 } 1546 1547 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1548 void 1549 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1550 { 1551 if (size() > 0) 1552 { 1553 __deallocate(__p1_.first().__next_); 1554 __p1_.first().__next_ = nullptr; 1555 size_type __bc = bucket_count(); 1556 for (size_type __i = 0; __i < __bc; ++__i) 1557 __bucket_list_[__i] = nullptr; 1558 size() = 0; 1559 } 1560 } 1561 1562 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1563 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1564 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1565 { 1566 __nd->__hash_ = hash_function()(__nd->__value_); 1567 size_type __bc = bucket_count(); 1568 bool __inserted = false; 1569 __node_pointer __ndptr; 1570 size_t __chash; 1571 if (__bc != 0) 1572 { 1573 __chash = __constrain_hash(__nd->__hash_, __bc); 1574 __ndptr = __bucket_list_[__chash]; 1575 if (__ndptr != nullptr) 1576 { 1577 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1578 __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1579 __ndptr = __ndptr->__next_) 1580 { 1581 if (key_eq()(__ndptr->__value_, __nd->__value_)) 1582 goto __done; 1583 } 1584 } 1585 } 1586 { 1587 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1588 { 1589 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1590 size_type(ceil(float(size() + 1) / max_load_factor())))); 1591 __bc = bucket_count(); 1592 __chash = __constrain_hash(__nd->__hash_, __bc); 1593 } 1594 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1595 __node_pointer __pn = __bucket_list_[__chash]; 1596 if (__pn == nullptr) 1597 { 1598 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1599 __nd->__next_ = __pn->__next_; 1600 __pn->__next_ = __nd; 1601 // fix up __bucket_list_ 1602 __bucket_list_[__chash] = __pn; 1603 if (__nd->__next_ != nullptr) 1604 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1605 } 1606 else 1607 { 1608 __nd->__next_ = __pn->__next_; 1609 __pn->__next_ = __nd; 1610 } 1611 __ndptr = __nd; 1612 // increment size 1613 ++size(); 1614 __inserted = true; 1615 } 1616 __done: 1617 #if _LIBCPP_DEBUG_LEVEL >= 2 1618 return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1619 #else 1620 return pair<iterator, bool>(iterator(__ndptr), __inserted); 1621 #endif 1622 } 1623 1624 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1625 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1626 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1627 { 1628 __cp->__hash_ = hash_function()(__cp->__value_); 1629 size_type __bc = bucket_count(); 1630 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1631 { 1632 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1633 size_type(ceil(float(size() + 1) / max_load_factor())))); 1634 __bc = bucket_count(); 1635 } 1636 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1637 __node_pointer __pn = __bucket_list_[__chash]; 1638 if (__pn == nullptr) 1639 { 1640 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1641 __cp->__next_ = __pn->__next_; 1642 __pn->__next_ = __cp; 1643 // fix up __bucket_list_ 1644 __bucket_list_[__chash] = __pn; 1645 if (__cp->__next_ != nullptr) 1646 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1647 } 1648 else 1649 { 1650 for (bool __found = false; __pn->__next_ != nullptr && 1651 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1652 __pn = __pn->__next_) 1653 { 1654 // __found key_eq() action 1655 // false false loop 1656 // true true loop 1657 // false true set __found to true 1658 // true false break 1659 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1660 key_eq()(__pn->__next_->__value_, __cp->__value_))) 1661 { 1662 if (!__found) 1663 __found = true; 1664 else 1665 break; 1666 } 1667 } 1668 __cp->__next_ = __pn->__next_; 1669 __pn->__next_ = __cp; 1670 if (__cp->__next_ != nullptr) 1671 { 1672 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1673 if (__nhash != __chash) 1674 __bucket_list_[__nhash] = __cp; 1675 } 1676 } 1677 ++size(); 1678 #if _LIBCPP_DEBUG_LEVEL >= 2 1679 return iterator(__cp, this); 1680 #else 1681 return iterator(__cp); 1682 #endif 1683 } 1684 1685 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1686 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1687 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1688 const_iterator __p, __node_pointer __cp) 1689 { 1690 #if _LIBCPP_DEBUG_LEVEL >= 2 1691 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1692 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1693 " referring to this unordered container"); 1694 #endif 1695 if (__p != end() && key_eq()(*__p, __cp->__value_)) 1696 { 1697 __node_pointer __np = __p.__node_; 1698 __cp->__hash_ = __np->__hash_; 1699 size_type __bc = bucket_count(); 1700 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1701 { 1702 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1703 size_type(ceil(float(size() + 1) / max_load_factor())))); 1704 __bc = bucket_count(); 1705 } 1706 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1707 __node_pointer __pp = __bucket_list_[__chash]; 1708 while (__pp->__next_ != __np) 1709 __pp = __pp->__next_; 1710 __cp->__next_ = __np; 1711 __pp->__next_ = __cp; 1712 ++size(); 1713 #if _LIBCPP_DEBUG_LEVEL >= 2 1714 return iterator(__cp, this); 1715 #else 1716 return iterator(__cp); 1717 #endif 1718 } 1719 return __node_insert_multi(__cp); 1720 } 1721 1722 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1723 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1724 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1725 { 1726 return __insert_unique_value(__x); 1727 } 1728 1729 1730 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1731 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1732 template <class _ValueTp> 1733 _LIBCPP_INLINE_VISIBILITY 1734 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1735 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(_ValueTp&& __x) 1736 #else 1737 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1738 _LIBCPP_INLINE_VISIBILITY 1739 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1740 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique_value(const value_type& __x) 1741 #endif 1742 { 1743 #if defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 1744 typedef const value_type& _ValueTp; 1745 #endif 1746 size_t __hash = hash_function()(__x); 1747 size_type __bc = bucket_count(); 1748 bool __inserted = false; 1749 __node_pointer __nd; 1750 size_t __chash; 1751 if (__bc != 0) 1752 { 1753 __chash = __constrain_hash(__hash, __bc); 1754 __nd = __bucket_list_[__chash]; 1755 if (__nd != nullptr) 1756 { 1757 for (__nd = __nd->__next_; __nd != nullptr && 1758 __constrain_hash(__nd->__hash_, __bc) == __chash; 1759 __nd = __nd->__next_) 1760 { 1761 if (key_eq()(__nd->__value_, __x)) 1762 goto __done; 1763 } 1764 } 1765 } 1766 { 1767 __node_holder __h = __construct_node(_VSTD::forward<_ValueTp>(__x), __hash); 1768 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1769 { 1770 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1771 size_type(ceil(float(size() + 1) / max_load_factor())))); 1772 __bc = bucket_count(); 1773 __chash = __constrain_hash(__hash, __bc); 1774 } 1775 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1776 __node_pointer __pn = __bucket_list_[__chash]; 1777 if (__pn == nullptr) 1778 { 1779 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1780 __h->__next_ = __pn->__next_; 1781 __pn->__next_ = __h.get(); 1782 // fix up __bucket_list_ 1783 __bucket_list_[__chash] = __pn; 1784 if (__h->__next_ != nullptr) 1785 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1786 } 1787 else 1788 { 1789 __h->__next_ = __pn->__next_; 1790 __pn->__next_ = __h.get(); 1791 } 1792 __nd = __h.release(); 1793 // increment size 1794 ++size(); 1795 __inserted = true; 1796 } 1797 __done: 1798 #if _LIBCPP_DEBUG_LEVEL >= 2 1799 return pair<iterator, bool>(iterator(__nd, this), __inserted); 1800 #else 1801 return pair<iterator, bool>(iterator(__nd), __inserted); 1802 #endif 1803 } 1804 1805 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1806 #ifndef _LIBCPP_HAS_NO_VARIADICS 1807 1808 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1809 template <class... _Args> 1810 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1811 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1812 { 1813 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1814 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1815 if (__r.second) 1816 __h.release(); 1817 return __r; 1818 } 1819 1820 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1821 template <class... _Args> 1822 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1823 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1824 { 1825 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1826 iterator __r = __node_insert_multi(__h.get()); 1827 __h.release(); 1828 return __r; 1829 } 1830 1831 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1832 template <class... _Args> 1833 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1834 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1835 const_iterator __p, _Args&&... __args) 1836 { 1837 #if _LIBCPP_DEBUG_LEVEL >= 2 1838 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1839 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1840 " referring to this unordered container"); 1841 #endif 1842 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1843 iterator __r = __node_insert_multi(__p, __h.get()); 1844 __h.release(); 1845 return __r; 1846 } 1847 1848 #endif // _LIBCPP_HAS_NO_VARIADICS 1849 1850 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1851 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1852 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(value_type&& __x) 1853 { 1854 return __insert_unique_value(_VSTD::move(__x)); 1855 } 1856 1857 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1858 template <class _Pp> 1859 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1860 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1861 { 1862 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1863 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1864 if (__r.second) 1865 __h.release(); 1866 return __r; 1867 } 1868 1869 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1870 1871 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1872 1873 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1874 template <class _Pp> 1875 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1876 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1877 { 1878 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1879 iterator __r = __node_insert_multi(__h.get()); 1880 __h.release(); 1881 return __r; 1882 } 1883 1884 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1885 template <class _Pp> 1886 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1887 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1888 _Pp&& __x) 1889 { 1890 #if _LIBCPP_DEBUG_LEVEL >= 2 1891 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1892 "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1893 " referring to this unordered container"); 1894 #endif 1895 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1896 iterator __r = __node_insert_multi(__p, __h.get()); 1897 __h.release(); 1898 return __r; 1899 } 1900 1901 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1902 1903 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1904 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1905 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1906 { 1907 __node_holder __h = __construct_node(__x); 1908 iterator __r = __node_insert_multi(__h.get()); 1909 __h.release(); 1910 return __r; 1911 } 1912 1913 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1914 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1915 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1916 const value_type& __x) 1917 { 1918 #if _LIBCPP_DEBUG_LEVEL >= 2 1919 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1920 "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1921 " referring to this unordered container"); 1922 #endif 1923 __node_holder __h = __construct_node(__x); 1924 iterator __r = __node_insert_multi(__p, __h.get()); 1925 __h.release(); 1926 return __r; 1927 } 1928 1929 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1930 1931 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1932 void 1933 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1934 { 1935 if (__n == 1) 1936 __n = 2; 1937 else if (__n & (__n - 1)) 1938 __n = __next_prime(__n); 1939 size_type __bc = bucket_count(); 1940 if (__n > __bc) 1941 __rehash(__n); 1942 else if (__n < __bc) 1943 { 1944 __n = _VSTD::max<size_type> 1945 ( 1946 __n, 1947 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1948 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1949 ); 1950 if (__n < __bc) 1951 __rehash(__n); 1952 } 1953 } 1954 1955 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1956 void 1957 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1958 { 1959 #if _LIBCPP_DEBUG_LEVEL >= 2 1960 __get_db()->__invalidate_all(this); 1961 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1962 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1963 __bucket_list_.reset(__nbc > 0 ? 1964 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1965 __bucket_list_.get_deleter().size() = __nbc; 1966 if (__nbc > 0) 1967 { 1968 for (size_type __i = 0; __i < __nbc; ++__i) 1969 __bucket_list_[__i] = nullptr; 1970 __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1971 __node_pointer __cp = __pp->__next_; 1972 if (__cp != nullptr) 1973 { 1974 size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1975 __bucket_list_[__chash] = __pp; 1976 size_type __phash = __chash; 1977 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1978 __cp = __pp->__next_) 1979 { 1980 __chash = __constrain_hash(__cp->__hash_, __nbc); 1981 if (__chash == __phash) 1982 __pp = __cp; 1983 else 1984 { 1985 if (__bucket_list_[__chash] == nullptr) 1986 { 1987 __bucket_list_[__chash] = __pp; 1988 __pp = __cp; 1989 __phash = __chash; 1990 } 1991 else 1992 { 1993 __node_pointer __np = __cp; 1994 for (; __np->__next_ != nullptr && 1995 key_eq()(__cp->__value_, __np->__next_->__value_); 1996 __np = __np->__next_) 1997 ; 1998 __pp->__next_ = __np->__next_; 1999 __np->__next_ = __bucket_list_[__chash]->__next_; 2000 __bucket_list_[__chash]->__next_ = __cp; 2001 2002 } 2003 } 2004 } 2005 } 2006 } 2007 } 2008 2009 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2010 template <class _Key> 2011 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2012 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2013 { 2014 size_t __hash = hash_function()(__k); 2015 size_type __bc = bucket_count(); 2016 if (__bc != 0) 2017 { 2018 size_t __chash = __constrain_hash(__hash, __bc); 2019 __node_pointer __nd = __bucket_list_[__chash]; 2020 if (__nd != nullptr) 2021 { 2022 for (__nd = __nd->__next_; __nd != nullptr && 2023 __constrain_hash(__nd->__hash_, __bc) == __chash; 2024 __nd = __nd->__next_) 2025 { 2026 if (key_eq()(__nd->__value_, __k)) 2027 #if _LIBCPP_DEBUG_LEVEL >= 2 2028 return iterator(__nd, this); 2029 #else 2030 return iterator(__nd); 2031 #endif 2032 } 2033 } 2034 } 2035 return end(); 2036 } 2037 2038 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2039 template <class _Key> 2040 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2041 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2042 { 2043 size_t __hash = hash_function()(__k); 2044 size_type __bc = bucket_count(); 2045 if (__bc != 0) 2046 { 2047 size_t __chash = __constrain_hash(__hash, __bc); 2048 __node_const_pointer __nd = __bucket_list_[__chash]; 2049 if (__nd != nullptr) 2050 { 2051 for (__nd = __nd->__next_; __nd != nullptr && 2052 __constrain_hash(__nd->__hash_, __bc) == __chash; 2053 __nd = __nd->__next_) 2054 { 2055 if (key_eq()(__nd->__value_, __k)) 2056 #if _LIBCPP_DEBUG_LEVEL >= 2 2057 return const_iterator(__nd, this); 2058 #else 2059 return const_iterator(__nd); 2060 #endif 2061 } 2062 } 2063 2064 } 2065 return end(); 2066 } 2067 2068 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2069 #ifndef _LIBCPP_HAS_NO_VARIADICS 2070 2071 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2072 template <class ..._Args> 2073 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2074 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2075 { 2076 __node_allocator& __na = __node_alloc(); 2077 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2078 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2079 __h.get_deleter().__value_constructed = true; 2080 __h->__hash_ = hash_function()(__h->__value_); 2081 __h->__next_ = nullptr; 2082 return __h; 2083 } 2084 2085 #endif // _LIBCPP_HAS_NO_VARIADICS 2086 2087 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2088 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2089 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2090 size_t __hash) 2091 { 2092 __node_allocator& __na = __node_alloc(); 2093 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2094 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2095 __h.get_deleter().__value_constructed = true; 2096 __h->__hash_ = __hash; 2097 __h->__next_ = nullptr; 2098 return __h; 2099 } 2100 2101 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2102 2103 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2104 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2105 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2106 { 2107 __node_allocator& __na = __node_alloc(); 2108 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2109 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2110 __h.get_deleter().__value_constructed = true; 2111 __h->__hash_ = hash_function()(__h->__value_); 2112 __h->__next_ = nullptr; 2113 return _VSTD::move(__h); // explicitly moved for C++03 2114 } 2115 2116 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2117 2118 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2119 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2120 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2121 size_t __hash) 2122 { 2123 __node_allocator& __na = __node_alloc(); 2124 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2125 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2126 __h.get_deleter().__value_constructed = true; 2127 __h->__hash_ = __hash; 2128 __h->__next_ = nullptr; 2129 return _VSTD::move(__h); // explicitly moved for C++03 2130 } 2131 2132 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2133 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2134 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2135 { 2136 __node_pointer __np = __p.__node_; 2137 #if _LIBCPP_DEBUG_LEVEL >= 2 2138 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2139 "unordered container erase(iterator) called with an iterator not" 2140 " referring to this container"); 2141 _LIBCPP_ASSERT(__p != end(), 2142 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2143 iterator __r(__np, this); 2144 #else 2145 iterator __r(__np); 2146 #endif 2147 ++__r; 2148 remove(__p); 2149 return __r; 2150 } 2151 2152 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2153 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2154 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2155 const_iterator __last) 2156 { 2157 #if _LIBCPP_DEBUG_LEVEL >= 2 2158 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2159 "unodered container::erase(iterator, iterator) called with an iterator not" 2160 " referring to this unodered container"); 2161 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2162 "unodered container::erase(iterator, iterator) called with an iterator not" 2163 " referring to this unodered container"); 2164 #endif 2165 for (const_iterator __p = __first; __first != __last; __p = __first) 2166 { 2167 ++__first; 2168 erase(__p); 2169 } 2170 __node_pointer __np = __last.__node_; 2171 #if _LIBCPP_DEBUG_LEVEL >= 2 2172 return iterator (__np, this); 2173 #else 2174 return iterator (__np); 2175 #endif 2176 } 2177 2178 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2179 template <class _Key> 2180 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2181 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2182 { 2183 iterator __i = find(__k); 2184 if (__i == end()) 2185 return 0; 2186 erase(__i); 2187 return 1; 2188 } 2189 2190 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2191 template <class _Key> 2192 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2193 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2194 { 2195 size_type __r = 0; 2196 iterator __i = find(__k); 2197 if (__i != end()) 2198 { 2199 iterator __e = end(); 2200 do 2201 { 2202 erase(__i++); 2203 ++__r; 2204 } while (__i != __e && key_eq()(*__i, __k)); 2205 } 2206 return __r; 2207 } 2208 2209 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2210 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2211 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2212 { 2213 // current node 2214 __node_pointer __cn = __p.__node_; 2215 size_type __bc = bucket_count(); 2216 size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2217 // find previous node 2218 __node_pointer __pn = __bucket_list_[__chash]; 2219 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2220 ; 2221 // Fix up __bucket_list_ 2222 // if __pn is not in same bucket (before begin is not in same bucket) && 2223 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2224 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2225 || __constrain_hash(__pn->__hash_, __bc) != __chash) 2226 { 2227 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2228 __bucket_list_[__chash] = nullptr; 2229 } 2230 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2231 if (__cn->__next_ != nullptr) 2232 { 2233 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2234 if (__nhash != __chash) 2235 __bucket_list_[__nhash] = __pn; 2236 } 2237 // remove __cn 2238 __pn->__next_ = __cn->__next_; 2239 __cn->__next_ = nullptr; 2240 --size(); 2241 #if _LIBCPP_DEBUG_LEVEL >= 2 2242 __c_node* __c = __get_db()->__find_c_and_lock(this); 2243 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2244 { 2245 --__p; 2246 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2247 if (__i->__node_ == __cn) 2248 { 2249 (*__p)->__c_ = nullptr; 2250 if (--__c->end_ != __p) 2251 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2252 } 2253 } 2254 __get_db()->unlock(); 2255 #endif 2256 return __node_holder(__cn, _Dp(__node_alloc(), true)); 2257 } 2258 2259 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2260 template <class _Key> 2261 inline _LIBCPP_INLINE_VISIBILITY 2262 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2263 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2264 { 2265 return static_cast<size_type>(find(__k) != end()); 2266 } 2267 2268 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2269 template <class _Key> 2270 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2271 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2272 { 2273 size_type __r = 0; 2274 const_iterator __i = find(__k); 2275 if (__i != end()) 2276 { 2277 const_iterator __e = end(); 2278 do 2279 { 2280 ++__i; 2281 ++__r; 2282 } while (__i != __e && key_eq()(*__i, __k)); 2283 } 2284 return __r; 2285 } 2286 2287 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2288 template <class _Key> 2289 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2290 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2291 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2292 const _Key& __k) 2293 { 2294 iterator __i = find(__k); 2295 iterator __j = __i; 2296 if (__i != end()) 2297 ++__j; 2298 return pair<iterator, iterator>(__i, __j); 2299 } 2300 2301 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2302 template <class _Key> 2303 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2304 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2305 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2306 const _Key& __k) const 2307 { 2308 const_iterator __i = find(__k); 2309 const_iterator __j = __i; 2310 if (__i != end()) 2311 ++__j; 2312 return pair<const_iterator, const_iterator>(__i, __j); 2313 } 2314 2315 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2316 template <class _Key> 2317 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2318 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2319 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2320 const _Key& __k) 2321 { 2322 iterator __i = find(__k); 2323 iterator __j = __i; 2324 if (__i != end()) 2325 { 2326 iterator __e = end(); 2327 do 2328 { 2329 ++__j; 2330 } while (__j != __e && key_eq()(*__j, __k)); 2331 } 2332 return pair<iterator, iterator>(__i, __j); 2333 } 2334 2335 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2336 template <class _Key> 2337 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2338 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2339 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2340 const _Key& __k) const 2341 { 2342 const_iterator __i = find(__k); 2343 const_iterator __j = __i; 2344 if (__i != end()) 2345 { 2346 const_iterator __e = end(); 2347 do 2348 { 2349 ++__j; 2350 } while (__j != __e && key_eq()(*__j, __k)); 2351 } 2352 return pair<const_iterator, const_iterator>(__i, __j); 2353 } 2354 2355 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2356 void 2357 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2358 #if _LIBCPP_STD_VER <= 11 2359 _NOEXCEPT_( 2360 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2361 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2362 || __is_nothrow_swappable<__pointer_allocator>::value) 2363 && (!__node_traits::propagate_on_container_swap::value 2364 || __is_nothrow_swappable<__node_allocator>::value) 2365 ) 2366 #else 2367 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2368 #endif 2369 { 2370 { 2371 __node_pointer_pointer __npp = __bucket_list_.release(); 2372 __bucket_list_.reset(__u.__bucket_list_.release()); 2373 __u.__bucket_list_.reset(__npp); 2374 } 2375 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2376 __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2377 __u.__bucket_list_.get_deleter().__alloc()); 2378 __swap_allocator(__node_alloc(), __u.__node_alloc()); 2379 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2380 __p2_.swap(__u.__p2_); 2381 __p3_.swap(__u.__p3_); 2382 if (size() > 0) 2383 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2384 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2385 if (__u.size() > 0) 2386 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2387 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2388 #if _LIBCPP_DEBUG_LEVEL >= 2 2389 __get_db()->swap(this, &__u); 2390 #endif 2391 } 2392 2393 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2394 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2395 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2396 { 2397 _LIBCPP_ASSERT(__n < bucket_count(), 2398 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2399 __node_const_pointer __np = __bucket_list_[__n]; 2400 size_type __bc = bucket_count(); 2401 size_type __r = 0; 2402 if (__np != nullptr) 2403 { 2404 for (__np = __np->__next_; __np != nullptr && 2405 __constrain_hash(__np->__hash_, __bc) == __n; 2406 __np = __np->__next_, ++__r) 2407 ; 2408 } 2409 return __r; 2410 } 2411 2412 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2413 inline _LIBCPP_INLINE_VISIBILITY 2414 void 2415 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2416 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2417 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2418 { 2419 __x.swap(__y); 2420 } 2421 2422 #if _LIBCPP_DEBUG_LEVEL >= 2 2423 2424 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2425 bool 2426 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2427 { 2428 return __i->__node_ != nullptr; 2429 } 2430 2431 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2432 bool 2433 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2434 { 2435 return false; 2436 } 2437 2438 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2439 bool 2440 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2441 { 2442 return false; 2443 } 2444 2445 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2446 bool 2447 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2448 { 2449 return false; 2450 } 2451 2452 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2453 _LIBCPP_END_NAMESPACE_STD 2454 2455 #endif // _LIBCPP__HASH_TABLE 2456
