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 __alloc_traits::template 781 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 782 rebind_alloc<__node> 783 #else 784 rebind_alloc<__node>::other 785 #endif 786 __node_allocator; 787 typedef allocator_traits<__node_allocator> __node_traits; 788 typedef typename __node_traits::pointer __node_pointer; 789 typedef typename __node_traits::pointer __node_const_pointer; 790 typedef __hash_node_base<__node_pointer> __first_node; 791 typedef typename pointer_traits<__node_pointer>::template 792 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 793 rebind<__first_node> 794 #else 795 rebind<__first_node>::other 796 #endif 797 __node_base_pointer; 798 799 private: 800 801 typedef typename __node_traits::template 802 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 803 rebind_alloc<__node_pointer> 804 #else 805 rebind_alloc<__node_pointer>::other 806 #endif 807 __pointer_allocator; 808 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 809 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 810 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 811 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 812 813 // --- Member data begin --- 814 __bucket_list __bucket_list_; 815 __compressed_pair<__first_node, __node_allocator> __p1_; 816 __compressed_pair<size_type, hasher> __p2_; 817 __compressed_pair<float, key_equal> __p3_; 818 // --- Member data end --- 819 820 _LIBCPP_INLINE_VISIBILITY 821 size_type& size() _NOEXCEPT {return __p2_.first();} 822 public: 823 _LIBCPP_INLINE_VISIBILITY 824 size_type size() const _NOEXCEPT {return __p2_.first();} 825 826 _LIBCPP_INLINE_VISIBILITY 827 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 828 _LIBCPP_INLINE_VISIBILITY 829 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 830 831 _LIBCPP_INLINE_VISIBILITY 832 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 833 _LIBCPP_INLINE_VISIBILITY 834 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 835 836 _LIBCPP_INLINE_VISIBILITY 837 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 838 _LIBCPP_INLINE_VISIBILITY 839 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 840 841 _LIBCPP_INLINE_VISIBILITY 842 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 843 _LIBCPP_INLINE_VISIBILITY 844 const __node_allocator& __node_alloc() const _NOEXCEPT 845 {return __p1_.second();} 846 847 public: 848 typedef __hash_iterator<__node_pointer> iterator; 849 typedef __hash_const_iterator<__node_pointer> const_iterator; 850 typedef __hash_local_iterator<__node_pointer> local_iterator; 851 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 852 853 __hash_table() 854 _NOEXCEPT_( 855 is_nothrow_default_constructible<__bucket_list>::value && 856 is_nothrow_default_constructible<__first_node>::value && 857 is_nothrow_default_constructible<__node_allocator>::value && 858 is_nothrow_default_constructible<hasher>::value && 859 is_nothrow_default_constructible<key_equal>::value); 860 __hash_table(const hasher& __hf, const key_equal& __eql); 861 __hash_table(const hasher& __hf, const key_equal& __eql, 862 const allocator_type& __a); 863 explicit __hash_table(const allocator_type& __a); 864 __hash_table(const __hash_table& __u); 865 __hash_table(const __hash_table& __u, const allocator_type& __a); 866 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 867 __hash_table(__hash_table&& __u) 868 _NOEXCEPT_( 869 is_nothrow_move_constructible<__bucket_list>::value && 870 is_nothrow_move_constructible<__first_node>::value && 871 is_nothrow_move_constructible<__node_allocator>::value && 872 is_nothrow_move_constructible<hasher>::value && 873 is_nothrow_move_constructible<key_equal>::value); 874 __hash_table(__hash_table&& __u, const allocator_type& __a); 875 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 876 ~__hash_table(); 877 878 __hash_table& operator=(const __hash_table& __u); 879 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 880 __hash_table& operator=(__hash_table&& __u) 881 _NOEXCEPT_( 882 __node_traits::propagate_on_container_move_assignment::value && 883 is_nothrow_move_assignable<__node_allocator>::value && 884 is_nothrow_move_assignable<hasher>::value && 885 is_nothrow_move_assignable<key_equal>::value); 886 #endif 887 template <class _InputIterator> 888 void __assign_unique(_InputIterator __first, _InputIterator __last); 889 template <class _InputIterator> 890 void __assign_multi(_InputIterator __first, _InputIterator __last); 891 892 _LIBCPP_INLINE_VISIBILITY 893 size_type max_size() const _NOEXCEPT 894 { 895 return allocator_traits<__pointer_allocator>::max_size( 896 __bucket_list_.get_deleter().__alloc()); 897 } 898 899 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 900 iterator __node_insert_multi(__node_pointer __nd); 901 iterator __node_insert_multi(const_iterator __p, 902 __node_pointer __nd); 903 904 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 905 template <class... _Args> 906 pair<iterator, bool> __emplace_unique(_Args&&... __args); 907 template <class... _Args> 908 iterator __emplace_multi(_Args&&... __args); 909 template <class... _Args> 910 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 911 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 912 913 pair<iterator, bool> __insert_unique(const value_type& __x); 914 915 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 916 template <class _Pp> 917 pair<iterator, bool> __insert_unique(_Pp&& __x); 918 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 919 920 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 921 template <class _Pp> 922 iterator __insert_multi(_Pp&& __x); 923 template <class _Pp> 924 iterator __insert_multi(const_iterator __p, _Pp&& __x); 925 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 926 iterator __insert_multi(const value_type& __x); 927 iterator __insert_multi(const_iterator __p, const value_type& __x); 928 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 929 930 void clear() _NOEXCEPT; 931 void rehash(size_type __n); 932 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 933 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 934 935 _LIBCPP_INLINE_VISIBILITY 936 size_type bucket_count() const _NOEXCEPT 937 { 938 return __bucket_list_.get_deleter().size(); 939 } 940 941 iterator begin() _NOEXCEPT; 942 iterator end() _NOEXCEPT; 943 const_iterator begin() const _NOEXCEPT; 944 const_iterator end() const _NOEXCEPT; 945 946 template <class _Key> 947 _LIBCPP_INLINE_VISIBILITY 948 size_type bucket(const _Key& __k) const 949 { 950 _LIBCPP_ASSERT(bucket_count() > 0, 951 "unordered container::bucket(key) called when bucket_count() == 0"); 952 return __constrain_hash(hash_function()(__k), bucket_count()); 953 } 954 955 template <class _Key> 956 iterator find(const _Key& __x); 957 template <class _Key> 958 const_iterator find(const _Key& __x) const; 959 960 typedef __hash_node_destructor<__node_allocator> _Dp; 961 typedef unique_ptr<__node, _Dp> __node_holder; 962 963 iterator erase(const_iterator __p); 964 iterator erase(const_iterator __first, const_iterator __last); 965 template <class _Key> 966 size_type __erase_unique(const _Key& __k); 967 template <class _Key> 968 size_type __erase_multi(const _Key& __k); 969 __node_holder remove(const_iterator __p) _NOEXCEPT; 970 971 template <class _Key> 972 size_type __count_unique(const _Key& __k) const; 973 template <class _Key> 974 size_type __count_multi(const _Key& __k) const; 975 976 template <class _Key> 977 pair<iterator, iterator> 978 __equal_range_unique(const _Key& __k); 979 template <class _Key> 980 pair<const_iterator, const_iterator> 981 __equal_range_unique(const _Key& __k) const; 982 983 template <class _Key> 984 pair<iterator, iterator> 985 __equal_range_multi(const _Key& __k); 986 template <class _Key> 987 pair<const_iterator, const_iterator> 988 __equal_range_multi(const _Key& __k) const; 989 990 void swap(__hash_table& __u) 991 _NOEXCEPT_( 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 __is_nothrow_swappable<hasher>::value && 997 __is_nothrow_swappable<key_equal>::value); 998 999 _LIBCPP_INLINE_VISIBILITY 1000 size_type max_bucket_count() const _NOEXCEPT 1001 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1002 size_type bucket_size(size_type __n) const; 1003 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1004 { 1005 size_type __bc = bucket_count(); 1006 return __bc != 0 ? (float)size() / __bc : 0.f; 1007 } 1008 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1009 { 1010 _LIBCPP_ASSERT(__mlf > 0, 1011 "unordered container::max_load_factor(lf) called with lf <= 0"); 1012 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1013 } 1014 1015 _LIBCPP_INLINE_VISIBILITY 1016 local_iterator 1017 begin(size_type __n) 1018 { 1019 _LIBCPP_ASSERT(__n < bucket_count(), 1020 "unordered container::begin(n) called with n >= bucket_count()"); 1021 #if _LIBCPP_DEBUG_LEVEL >= 2 1022 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1023 #else 1024 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1025 #endif 1026 } 1027 1028 _LIBCPP_INLINE_VISIBILITY 1029 local_iterator 1030 end(size_type __n) 1031 { 1032 _LIBCPP_ASSERT(__n < bucket_count(), 1033 "unordered container::end(n) called with n >= bucket_count()"); 1034 #if _LIBCPP_DEBUG_LEVEL >= 2 1035 return local_iterator(nullptr, __n, bucket_count(), this); 1036 #else 1037 return local_iterator(nullptr, __n, bucket_count()); 1038 #endif 1039 } 1040 1041 _LIBCPP_INLINE_VISIBILITY 1042 const_local_iterator 1043 cbegin(size_type __n) const 1044 { 1045 _LIBCPP_ASSERT(__n < bucket_count(), 1046 "unordered container::cbegin(n) called with n >= bucket_count()"); 1047 #if _LIBCPP_DEBUG_LEVEL >= 2 1048 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1049 #else 1050 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1051 #endif 1052 } 1053 1054 _LIBCPP_INLINE_VISIBILITY 1055 const_local_iterator 1056 cend(size_type __n) const 1057 { 1058 _LIBCPP_ASSERT(__n < bucket_count(), 1059 "unordered container::cend(n) called with n >= bucket_count()"); 1060 #if _LIBCPP_DEBUG_LEVEL >= 2 1061 return const_local_iterator(nullptr, __n, bucket_count(), this); 1062 #else 1063 return const_local_iterator(nullptr, __n, bucket_count()); 1064 #endif 1065 } 1066 1067 #if _LIBCPP_DEBUG_LEVEL >= 2 1068 1069 bool __dereferenceable(const const_iterator* __i) const; 1070 bool __decrementable(const const_iterator* __i) const; 1071 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1072 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1073 1074 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1075 1076 private: 1077 void __rehash(size_type __n); 1078 1079 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1080 #ifndef _LIBCPP_HAS_NO_VARIADICS 1081 template <class ..._Args> 1082 __node_holder __construct_node(_Args&& ...__args); 1083 #endif // _LIBCPP_HAS_NO_VARIADICS 1084 __node_holder __construct_node(value_type&& __v, size_t __hash); 1085 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1086 __node_holder __construct_node(const value_type& __v); 1087 #endif 1088 __node_holder __construct_node(const value_type& __v, size_t __hash); 1089 1090 _LIBCPP_INLINE_VISIBILITY 1091 void __copy_assign_alloc(const __hash_table& __u) 1092 {__copy_assign_alloc(__u, integral_constant<bool, 1093 __node_traits::propagate_on_container_copy_assignment::value>());} 1094 void __copy_assign_alloc(const __hash_table& __u, true_type); 1095 _LIBCPP_INLINE_VISIBILITY 1096 void __copy_assign_alloc(const __hash_table&, false_type) {} 1097 1098 void __move_assign(__hash_table& __u, false_type); 1099 void __move_assign(__hash_table& __u, true_type) 1100 _NOEXCEPT_( 1101 is_nothrow_move_assignable<__node_allocator>::value && 1102 is_nothrow_move_assignable<hasher>::value && 1103 is_nothrow_move_assignable<key_equal>::value); 1104 _LIBCPP_INLINE_VISIBILITY 1105 void __move_assign_alloc(__hash_table& __u) 1106 _NOEXCEPT_( 1107 !__node_traits::propagate_on_container_move_assignment::value || 1108 (is_nothrow_move_assignable<__pointer_allocator>::value && 1109 is_nothrow_move_assignable<__node_allocator>::value)) 1110 {__move_assign_alloc(__u, integral_constant<bool, 1111 __node_traits::propagate_on_container_move_assignment::value>());} 1112 _LIBCPP_INLINE_VISIBILITY 1113 void __move_assign_alloc(__hash_table& __u, true_type) 1114 _NOEXCEPT_( 1115 is_nothrow_move_assignable<__pointer_allocator>::value && 1116 is_nothrow_move_assignable<__node_allocator>::value) 1117 { 1118 __bucket_list_.get_deleter().__alloc() = 1119 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1120 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1121 } 1122 _LIBCPP_INLINE_VISIBILITY 1123 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1124 1125 template <class _Ap> 1126 _LIBCPP_INLINE_VISIBILITY 1127 static 1128 void 1129 __swap_alloc(_Ap& __x, _Ap& __y) 1130 _NOEXCEPT_( 1131 !allocator_traits<_Ap>::propagate_on_container_swap::value || 1132 __is_nothrow_swappable<_Ap>::value) 1133 { 1134 __swap_alloc(__x, __y, 1135 integral_constant<bool, 1136 allocator_traits<_Ap>::propagate_on_container_swap::value 1137 >()); 1138 } 1139 1140 template <class _Ap> 1141 _LIBCPP_INLINE_VISIBILITY 1142 static 1143 void 1144 __swap_alloc(_Ap& __x, _Ap& __y, true_type) 1145 _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value) 1146 { 1147 using _VSTD::swap; 1148 swap(__x, __y); 1149 } 1150 1151 template <class _Ap> 1152 _LIBCPP_INLINE_VISIBILITY 1153 static 1154 void 1155 __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {} 1156 1157 void __deallocate(__node_pointer __np) _NOEXCEPT; 1158 __node_pointer __detach() _NOEXCEPT; 1159 1160 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1161 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1162 }; 1163 1164 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1165 inline _LIBCPP_INLINE_VISIBILITY 1166 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1167 _NOEXCEPT_( 1168 is_nothrow_default_constructible<__bucket_list>::value && 1169 is_nothrow_default_constructible<__first_node>::value && 1170 is_nothrow_default_constructible<hasher>::value && 1171 is_nothrow_default_constructible<key_equal>::value) 1172 : __p2_(0), 1173 __p3_(1.0f) 1174 { 1175 } 1176 1177 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1178 inline _LIBCPP_INLINE_VISIBILITY 1179 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1180 const key_equal& __eql) 1181 : __bucket_list_(nullptr, __bucket_list_deleter()), 1182 __p1_(), 1183 __p2_(0, __hf), 1184 __p3_(1.0f, __eql) 1185 { 1186 } 1187 1188 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1189 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1190 const key_equal& __eql, 1191 const allocator_type& __a) 1192 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1193 __p1_(__node_allocator(__a)), 1194 __p2_(0, __hf), 1195 __p3_(1.0f, __eql) 1196 { 1197 } 1198 1199 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1200 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1201 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1202 __p1_(__node_allocator(__a)), 1203 __p2_(0), 1204 __p3_(1.0f) 1205 { 1206 } 1207 1208 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1209 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1210 : __bucket_list_(nullptr, 1211 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1212 select_on_container_copy_construction( 1213 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1214 __p1_(allocator_traits<__node_allocator>:: 1215 select_on_container_copy_construction(__u.__node_alloc())), 1216 __p2_(0, __u.hash_function()), 1217 __p3_(__u.__p3_) 1218 { 1219 } 1220 1221 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1222 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1223 const allocator_type& __a) 1224 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1225 __p1_(__node_allocator(__a)), 1226 __p2_(0, __u.hash_function()), 1227 __p3_(__u.__p3_) 1228 { 1229 } 1230 1231 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1232 1233 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1234 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1235 _NOEXCEPT_( 1236 is_nothrow_move_constructible<__bucket_list>::value && 1237 is_nothrow_move_constructible<__first_node>::value && 1238 is_nothrow_move_constructible<hasher>::value && 1239 is_nothrow_move_constructible<key_equal>::value) 1240 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1241 __p1_(_VSTD::move(__u.__p1_)), 1242 __p2_(_VSTD::move(__u.__p2_)), 1243 __p3_(_VSTD::move(__u.__p3_)) 1244 { 1245 if (size() > 0) 1246 { 1247 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1248 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1249 __u.__p1_.first().__next_ = nullptr; 1250 __u.size() = 0; 1251 } 1252 } 1253 1254 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1255 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1256 const allocator_type& __a) 1257 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1258 __p1_(__node_allocator(__a)), 1259 __p2_(0, _VSTD::move(__u.hash_function())), 1260 __p3_(_VSTD::move(__u.__p3_)) 1261 { 1262 if (__a == allocator_type(__u.__node_alloc())) 1263 { 1264 __bucket_list_.reset(__u.__bucket_list_.release()); 1265 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1266 __u.__bucket_list_.get_deleter().size() = 0; 1267 if (__u.size() > 0) 1268 { 1269 __p1_.first().__next_ = __u.__p1_.first().__next_; 1270 __u.__p1_.first().__next_ = nullptr; 1271 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1272 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1273 size() = __u.size(); 1274 __u.size() = 0; 1275 } 1276 } 1277 } 1278 1279 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1280 1281 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1282 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1283 { 1284 __deallocate(__p1_.first().__next_); 1285 #if _LIBCPP_DEBUG_LEVEL >= 2 1286 __get_db()->__erase_c(this); 1287 #endif 1288 } 1289 1290 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1291 void 1292 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1293 const __hash_table& __u, true_type) 1294 { 1295 if (__node_alloc() != __u.__node_alloc()) 1296 { 1297 clear(); 1298 __bucket_list_.reset(); 1299 __bucket_list_.get_deleter().size() = 0; 1300 } 1301 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1302 __node_alloc() = __u.__node_alloc(); 1303 } 1304 1305 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1306 __hash_table<_Tp, _Hash, _Equal, _Alloc>& 1307 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1308 { 1309 if (this != &__u) 1310 { 1311 __copy_assign_alloc(__u); 1312 hash_function() = __u.hash_function(); 1313 key_eq() = __u.key_eq(); 1314 max_load_factor() = __u.max_load_factor(); 1315 __assign_multi(__u.begin(), __u.end()); 1316 } 1317 return *this; 1318 } 1319 1320 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1321 void 1322 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np) 1323 _NOEXCEPT 1324 { 1325 __node_allocator& __na = __node_alloc(); 1326 while (__np != nullptr) 1327 { 1328 __node_pointer __next = __np->__next_; 1329 #if _LIBCPP_DEBUG_LEVEL >= 2 1330 __c_node* __c = __get_db()->__find_c_and_lock(this); 1331 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1332 { 1333 --__p; 1334 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1335 if (__i->__node_ == __np) 1336 { 1337 (*__p)->__c_ = nullptr; 1338 if (--__c->end_ != __p) 1339 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1340 } 1341 } 1342 __get_db()->unlock(); 1343 #endif 1344 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_)); 1345 __node_traits::deallocate(__na, __np, 1); 1346 __np = __next; 1347 } 1348 } 1349 1350 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1351 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer 1352 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1353 { 1354 size_type __bc = bucket_count(); 1355 for (size_type __i = 0; __i < __bc; ++__i) 1356 __bucket_list_[__i] = nullptr; 1357 size() = 0; 1358 __node_pointer __cache = __p1_.first().__next_; 1359 __p1_.first().__next_ = nullptr; 1360 return __cache; 1361 } 1362 1363 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1364 1365 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1366 void 1367 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1368 __hash_table& __u, true_type) 1369 _NOEXCEPT_( 1370 is_nothrow_move_assignable<__node_allocator>::value && 1371 is_nothrow_move_assignable<hasher>::value && 1372 is_nothrow_move_assignable<key_equal>::value) 1373 { 1374 clear(); 1375 __bucket_list_.reset(__u.__bucket_list_.release()); 1376 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1377 __u.__bucket_list_.get_deleter().size() = 0; 1378 __move_assign_alloc(__u); 1379 size() = __u.size(); 1380 hash_function() = _VSTD::move(__u.hash_function()); 1381 max_load_factor() = __u.max_load_factor(); 1382 key_eq() = _VSTD::move(__u.key_eq()); 1383 __p1_.first().__next_ = __u.__p1_.first().__next_; 1384 if (size() > 0) 1385 { 1386 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1387 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1388 __u.__p1_.first().__next_ = nullptr; 1389 __u.size() = 0; 1390 } 1391 #if _LIBCPP_DEBUG_LEVEL >= 2 1392 __get_db()->swap(this, &__u); 1393 #endif 1394 } 1395 1396 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1397 void 1398 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1399 __hash_table& __u, false_type) 1400 { 1401 if (__node_alloc() == __u.__node_alloc()) 1402 __move_assign(__u, true_type()); 1403 else 1404 { 1405 hash_function() = _VSTD::move(__u.hash_function()); 1406 key_eq() = _VSTD::move(__u.key_eq()); 1407 max_load_factor() = __u.max_load_factor(); 1408 if (bucket_count() != 0) 1409 { 1410 __node_pointer __cache = __detach(); 1411 #ifndef _LIBCPP_NO_EXCEPTIONS 1412 try 1413 { 1414 #endif // _LIBCPP_NO_EXCEPTIONS 1415 const_iterator __i = __u.begin(); 1416 while (__cache != nullptr && __u.size() != 0) 1417 { 1418 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_); 1419 __node_pointer __next = __cache->__next_; 1420 __node_insert_multi(__cache); 1421 __cache = __next; 1422 } 1423 #ifndef _LIBCPP_NO_EXCEPTIONS 1424 } 1425 catch (...) 1426 { 1427 __deallocate(__cache); 1428 throw; 1429 } 1430 #endif // _LIBCPP_NO_EXCEPTIONS 1431 __deallocate(__cache); 1432 } 1433 const_iterator __i = __u.begin(); 1434 while (__u.size() != 0) 1435 { 1436 __node_holder __h = 1437 __construct_node(_VSTD::move(__u.remove(__i++)->__value_)); 1438 __node_insert_multi(__h.get()); 1439 __h.release(); 1440 } 1441 } 1442 } 1443 1444 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1445 inline _LIBCPP_INLINE_VISIBILITY 1446 __hash_table<_Tp, _Hash, _Equal, _Alloc>& 1447 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1448 _NOEXCEPT_( 1449 __node_traits::propagate_on_container_move_assignment::value && 1450 is_nothrow_move_assignable<__node_allocator>::value && 1451 is_nothrow_move_assignable<hasher>::value && 1452 is_nothrow_move_assignable<key_equal>::value) 1453 { 1454 __move_assign(__u, integral_constant<bool, 1455 __node_traits::propagate_on_container_move_assignment::value>()); 1456 return *this; 1457 } 1458 1459 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1460 1461 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1462 template <class _InputIterator> 1463 void 1464 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1465 _InputIterator __last) 1466 { 1467 if (bucket_count() != 0) 1468 { 1469 __node_pointer __cache = __detach(); 1470 #ifndef _LIBCPP_NO_EXCEPTIONS 1471 try 1472 { 1473 #endif // _LIBCPP_NO_EXCEPTIONS 1474 for (; __cache != nullptr && __first != __last; ++__first) 1475 { 1476 __cache->__value_ = *__first; 1477 __node_pointer __next = __cache->__next_; 1478 __node_insert_unique(__cache); 1479 __cache = __next; 1480 } 1481 #ifndef _LIBCPP_NO_EXCEPTIONS 1482 } 1483 catch (...) 1484 { 1485 __deallocate(__cache); 1486 throw; 1487 } 1488 #endif // _LIBCPP_NO_EXCEPTIONS 1489 __deallocate(__cache); 1490 } 1491 for (; __first != __last; ++__first) 1492 __insert_unique(*__first); 1493 } 1494 1495 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1496 template <class _InputIterator> 1497 void 1498 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1499 _InputIterator __last) 1500 { 1501 if (bucket_count() != 0) 1502 { 1503 __node_pointer __cache = __detach(); 1504 #ifndef _LIBCPP_NO_EXCEPTIONS 1505 try 1506 { 1507 #endif // _LIBCPP_NO_EXCEPTIONS 1508 for (; __cache != nullptr && __first != __last; ++__first) 1509 { 1510 __cache->__value_ = *__first; 1511 __node_pointer __next = __cache->__next_; 1512 __node_insert_multi(__cache); 1513 __cache = __next; 1514 } 1515 #ifndef _LIBCPP_NO_EXCEPTIONS 1516 } 1517 catch (...) 1518 { 1519 __deallocate(__cache); 1520 throw; 1521 } 1522 #endif // _LIBCPP_NO_EXCEPTIONS 1523 __deallocate(__cache); 1524 } 1525 for (; __first != __last; ++__first) 1526 __insert_multi(*__first); 1527 } 1528 1529 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1530 inline _LIBCPP_INLINE_VISIBILITY 1531 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1532 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1533 { 1534 #if _LIBCPP_DEBUG_LEVEL >= 2 1535 return iterator(__p1_.first().__next_, this); 1536 #else 1537 return iterator(__p1_.first().__next_); 1538 #endif 1539 } 1540 1541 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1542 inline _LIBCPP_INLINE_VISIBILITY 1543 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1544 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1545 { 1546 #if _LIBCPP_DEBUG_LEVEL >= 2 1547 return iterator(nullptr, this); 1548 #else 1549 return iterator(nullptr); 1550 #endif 1551 } 1552 1553 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1554 inline _LIBCPP_INLINE_VISIBILITY 1555 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1556 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1557 { 1558 #if _LIBCPP_DEBUG_LEVEL >= 2 1559 return const_iterator(__p1_.first().__next_, this); 1560 #else 1561 return const_iterator(__p1_.first().__next_); 1562 #endif 1563 } 1564 1565 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1566 inline _LIBCPP_INLINE_VISIBILITY 1567 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1568 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1569 { 1570 #if _LIBCPP_DEBUG_LEVEL >= 2 1571 return const_iterator(nullptr, this); 1572 #else 1573 return const_iterator(nullptr); 1574 #endif 1575 } 1576 1577 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1578 void 1579 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1580 { 1581 if (size() > 0) 1582 { 1583 __deallocate(__p1_.first().__next_); 1584 __p1_.first().__next_ = nullptr; 1585 size_type __bc = bucket_count(); 1586 for (size_type __i = 0; __i < __bc; ++__i) 1587 __bucket_list_[__i] = nullptr; 1588 size() = 0; 1589 } 1590 } 1591 1592 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1593 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1594 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1595 { 1596 __nd->__hash_ = hash_function()(__nd->__value_); 1597 size_type __bc = bucket_count(); 1598 bool __inserted = false; 1599 __node_pointer __ndptr; 1600 size_t __chash; 1601 if (__bc != 0) 1602 { 1603 __chash = __constrain_hash(__nd->__hash_, __bc); 1604 __ndptr = __bucket_list_[__chash]; 1605 if (__ndptr != nullptr) 1606 { 1607 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1608 __constrain_hash(__ndptr->__hash_, __bc) == __chash; 1609 __ndptr = __ndptr->__next_) 1610 { 1611 if (key_eq()(__ndptr->__value_, __nd->__value_)) 1612 goto __done; 1613 } 1614 } 1615 } 1616 { 1617 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1618 { 1619 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1620 size_type(ceil(float(size() + 1) / max_load_factor())))); 1621 __bc = bucket_count(); 1622 __chash = __constrain_hash(__nd->__hash_, __bc); 1623 } 1624 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1625 __node_pointer __pn = __bucket_list_[__chash]; 1626 if (__pn == nullptr) 1627 { 1628 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1629 __nd->__next_ = __pn->__next_; 1630 __pn->__next_ = __nd; 1631 // fix up __bucket_list_ 1632 __bucket_list_[__chash] = __pn; 1633 if (__nd->__next_ != nullptr) 1634 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd; 1635 } 1636 else 1637 { 1638 __nd->__next_ = __pn->__next_; 1639 __pn->__next_ = __nd; 1640 } 1641 __ndptr = __nd; 1642 // increment size 1643 ++size(); 1644 __inserted = true; 1645 } 1646 __done: 1647 #if _LIBCPP_DEBUG_LEVEL >= 2 1648 return pair<iterator, bool>(iterator(__ndptr, this), __inserted); 1649 #else 1650 return pair<iterator, bool>(iterator(__ndptr), __inserted); 1651 #endif 1652 } 1653 1654 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1655 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1656 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 1657 { 1658 __cp->__hash_ = hash_function()(__cp->__value_); 1659 size_type __bc = bucket_count(); 1660 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1661 { 1662 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1663 size_type(ceil(float(size() + 1) / max_load_factor())))); 1664 __bc = bucket_count(); 1665 } 1666 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1667 __node_pointer __pn = __bucket_list_[__chash]; 1668 if (__pn == nullptr) 1669 { 1670 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1671 __cp->__next_ = __pn->__next_; 1672 __pn->__next_ = __cp; 1673 // fix up __bucket_list_ 1674 __bucket_list_[__chash] = __pn; 1675 if (__cp->__next_ != nullptr) 1676 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp; 1677 } 1678 else 1679 { 1680 for (bool __found = false; __pn->__next_ != nullptr && 1681 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash; 1682 __pn = __pn->__next_) 1683 { 1684 // __found key_eq() action 1685 // false false loop 1686 // true true loop 1687 // false true set __found to true 1688 // true false break 1689 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ && 1690 key_eq()(__pn->__next_->__value_, __cp->__value_))) 1691 { 1692 if (!__found) 1693 __found = true; 1694 else 1695 break; 1696 } 1697 } 1698 __cp->__next_ = __pn->__next_; 1699 __pn->__next_ = __cp; 1700 if (__cp->__next_ != nullptr) 1701 { 1702 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc); 1703 if (__nhash != __chash) 1704 __bucket_list_[__nhash] = __cp; 1705 } 1706 } 1707 ++size(); 1708 #if _LIBCPP_DEBUG_LEVEL >= 2 1709 return iterator(__cp, this); 1710 #else 1711 return iterator(__cp); 1712 #endif 1713 } 1714 1715 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1716 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1717 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 1718 const_iterator __p, __node_pointer __cp) 1719 { 1720 #if _LIBCPP_DEBUG_LEVEL >= 2 1721 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1722 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1723 " referring to this unordered container"); 1724 #endif 1725 if (__p != end() && key_eq()(*__p, __cp->__value_)) 1726 { 1727 __node_pointer __np = __p.__node_; 1728 __cp->__hash_ = __np->__hash_; 1729 size_type __bc = bucket_count(); 1730 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1731 { 1732 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1733 size_type(ceil(float(size() + 1) / max_load_factor())))); 1734 __bc = bucket_count(); 1735 } 1736 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 1737 __node_pointer __pp = __bucket_list_[__chash]; 1738 while (__pp->__next_ != __np) 1739 __pp = __pp->__next_; 1740 __cp->__next_ = __np; 1741 __pp->__next_ = __cp; 1742 ++size(); 1743 #if _LIBCPP_DEBUG_LEVEL >= 2 1744 return iterator(__cp, this); 1745 #else 1746 return iterator(__cp); 1747 #endif 1748 } 1749 return __node_insert_multi(__cp); 1750 } 1751 1752 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1753 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1754 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x) 1755 { 1756 size_t __hash = hash_function()(__x); 1757 size_type __bc = bucket_count(); 1758 bool __inserted = false; 1759 __node_pointer __nd; 1760 size_t __chash; 1761 if (__bc != 0) 1762 { 1763 __chash = __constrain_hash(__hash, __bc); 1764 __nd = __bucket_list_[__chash]; 1765 if (__nd != nullptr) 1766 { 1767 for (__nd = __nd->__next_; __nd != nullptr && 1768 __constrain_hash(__nd->__hash_, __bc) == __chash; 1769 __nd = __nd->__next_) 1770 { 1771 if (key_eq()(__nd->__value_, __x)) 1772 goto __done; 1773 } 1774 } 1775 } 1776 { 1777 __node_holder __h = __construct_node(__x, __hash); 1778 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1779 { 1780 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1781 size_type(ceil(float(size() + 1) / max_load_factor())))); 1782 __bc = bucket_count(); 1783 __chash = __constrain_hash(__hash, __bc); 1784 } 1785 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1786 __node_pointer __pn = __bucket_list_[__chash]; 1787 if (__pn == nullptr) 1788 { 1789 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1790 __h->__next_ = __pn->__next_; 1791 __pn->__next_ = __h.get(); 1792 // fix up __bucket_list_ 1793 __bucket_list_[__chash] = __pn; 1794 if (__h->__next_ != nullptr) 1795 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get(); 1796 } 1797 else 1798 { 1799 __h->__next_ = __pn->__next_; 1800 __pn->__next_ = __h.get(); 1801 } 1802 __nd = __h.release(); 1803 // increment size 1804 ++size(); 1805 __inserted = true; 1806 } 1807 __done: 1808 #if _LIBCPP_DEBUG_LEVEL >= 2 1809 return pair<iterator, bool>(iterator(__nd, this), __inserted); 1810 #else 1811 return pair<iterator, bool>(iterator(__nd), __inserted); 1812 #endif 1813 } 1814 1815 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1816 #ifndef _LIBCPP_HAS_NO_VARIADICS 1817 1818 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1819 template <class... _Args> 1820 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1821 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args) 1822 { 1823 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1824 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1825 if (__r.second) 1826 __h.release(); 1827 return __r; 1828 } 1829 1830 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1831 template <class... _Args> 1832 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1833 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 1834 { 1835 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1836 iterator __r = __node_insert_multi(__h.get()); 1837 __h.release(); 1838 return __r; 1839 } 1840 1841 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1842 template <class... _Args> 1843 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1844 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 1845 const_iterator __p, _Args&&... __args) 1846 { 1847 #if _LIBCPP_DEBUG_LEVEL >= 2 1848 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1849 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 1850 " referring to this unordered container"); 1851 #endif 1852 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 1853 iterator __r = __node_insert_multi(__p, __h.get()); 1854 __h.release(); 1855 return __r; 1856 } 1857 1858 #endif // _LIBCPP_HAS_NO_VARIADICS 1859 1860 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1861 template <class _Pp> 1862 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1863 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x) 1864 { 1865 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1866 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 1867 if (__r.second) 1868 __h.release(); 1869 return __r; 1870 } 1871 1872 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1873 1874 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1875 1876 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1877 template <class _Pp> 1878 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1879 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x) 1880 { 1881 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1882 iterator __r = __node_insert_multi(__h.get()); 1883 __h.release(); 1884 return __r; 1885 } 1886 1887 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1888 template <class _Pp> 1889 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1890 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1891 _Pp&& __x) 1892 { 1893 #if _LIBCPP_DEBUG_LEVEL >= 2 1894 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1895 "unordered container::insert(const_iterator, rvalue) called with an iterator not" 1896 " referring to this unordered container"); 1897 #endif 1898 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x)); 1899 iterator __r = __node_insert_multi(__p, __h.get()); 1900 __h.release(); 1901 return __r; 1902 } 1903 1904 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1905 1906 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1907 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1908 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x) 1909 { 1910 __node_holder __h = __construct_node(__x); 1911 iterator __r = __node_insert_multi(__h.get()); 1912 __h.release(); 1913 return __r; 1914 } 1915 1916 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1917 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1918 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 1919 const value_type& __x) 1920 { 1921 #if _LIBCPP_DEBUG_LEVEL >= 2 1922 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 1923 "unordered container::insert(const_iterator, lvalue) called with an iterator not" 1924 " referring to this unordered container"); 1925 #endif 1926 __node_holder __h = __construct_node(__x); 1927 iterator __r = __node_insert_multi(__p, __h.get()); 1928 __h.release(); 1929 return __r; 1930 } 1931 1932 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1933 1934 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1935 void 1936 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 1937 { 1938 if (__n == 1) 1939 __n = 2; 1940 else if (__n & (__n - 1)) 1941 __n = __next_prime(__n); 1942 size_type __bc = bucket_count(); 1943 if (__n > __bc) 1944 __rehash(__n); 1945 else if (__n < __bc) 1946 { 1947 __n = _VSTD::max<size_type> 1948 ( 1949 __n, 1950 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 1951 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 1952 ); 1953 if (__n < __bc) 1954 __rehash(__n); 1955 } 1956 } 1957 1958 template <class _Tp, class _Hash, class _Equal, class _Alloc> 1959 void 1960 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 1961 { 1962 #if _LIBCPP_DEBUG_LEVEL >= 2 1963 __get_db()->__invalidate_all(this); 1964 #endif // _LIBCPP_DEBUG_LEVEL >= 2 1965 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 1966 __bucket_list_.reset(__nbc > 0 ? 1967 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 1968 __bucket_list_.get_deleter().size() = __nbc; 1969 if (__nbc > 0) 1970 { 1971 for (size_type __i = 0; __i < __nbc; ++__i) 1972 __bucket_list_[__i] = nullptr; 1973 __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))); 1974 __node_pointer __cp = __pp->__next_; 1975 if (__cp != nullptr) 1976 { 1977 size_type __chash = __constrain_hash(__cp->__hash_, __nbc); 1978 __bucket_list_[__chash] = __pp; 1979 size_type __phash = __chash; 1980 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 1981 __cp = __pp->__next_) 1982 { 1983 __chash = __constrain_hash(__cp->__hash_, __nbc); 1984 if (__chash == __phash) 1985 __pp = __cp; 1986 else 1987 { 1988 if (__bucket_list_[__chash] == nullptr) 1989 { 1990 __bucket_list_[__chash] = __pp; 1991 __pp = __cp; 1992 __phash = __chash; 1993 } 1994 else 1995 { 1996 __node_pointer __np = __cp; 1997 for (; __np->__next_ != nullptr && 1998 key_eq()(__cp->__value_, __np->__next_->__value_); 1999 __np = __np->__next_) 2000 ; 2001 __pp->__next_ = __np->__next_; 2002 __np->__next_ = __bucket_list_[__chash]->__next_; 2003 __bucket_list_[__chash]->__next_ = __cp; 2004 2005 } 2006 } 2007 } 2008 } 2009 } 2010 } 2011 2012 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2013 template <class _Key> 2014 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2015 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2016 { 2017 size_t __hash = hash_function()(__k); 2018 size_type __bc = bucket_count(); 2019 if (__bc != 0) 2020 { 2021 size_t __chash = __constrain_hash(__hash, __bc); 2022 __node_pointer __nd = __bucket_list_[__chash]; 2023 if (__nd != nullptr) 2024 { 2025 for (__nd = __nd->__next_; __nd != nullptr && 2026 __constrain_hash(__nd->__hash_, __bc) == __chash; 2027 __nd = __nd->__next_) 2028 { 2029 if (key_eq()(__nd->__value_, __k)) 2030 #if _LIBCPP_DEBUG_LEVEL >= 2 2031 return iterator(__nd, this); 2032 #else 2033 return iterator(__nd); 2034 #endif 2035 } 2036 } 2037 } 2038 return end(); 2039 } 2040 2041 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2042 template <class _Key> 2043 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2044 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2045 { 2046 size_t __hash = hash_function()(__k); 2047 size_type __bc = bucket_count(); 2048 if (__bc != 0) 2049 { 2050 size_t __chash = __constrain_hash(__hash, __bc); 2051 __node_const_pointer __nd = __bucket_list_[__chash]; 2052 if (__nd != nullptr) 2053 { 2054 for (__nd = __nd->__next_; __nd != nullptr && 2055 __constrain_hash(__nd->__hash_, __bc) == __chash; 2056 __nd = __nd->__next_) 2057 { 2058 if (key_eq()(__nd->__value_, __k)) 2059 #if _LIBCPP_DEBUG_LEVEL >= 2 2060 return const_iterator(__nd, this); 2061 #else 2062 return const_iterator(__nd); 2063 #endif 2064 } 2065 } 2066 2067 } 2068 return end(); 2069 } 2070 2071 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2072 #ifndef _LIBCPP_HAS_NO_VARIADICS 2073 2074 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2075 template <class ..._Args> 2076 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2077 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2078 { 2079 __node_allocator& __na = __node_alloc(); 2080 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2081 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...); 2082 __h.get_deleter().__value_constructed = true; 2083 __h->__hash_ = hash_function()(__h->__value_); 2084 __h->__next_ = nullptr; 2085 return __h; 2086 } 2087 2088 #endif // _LIBCPP_HAS_NO_VARIADICS 2089 2090 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2091 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2092 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v, 2093 size_t __hash) 2094 { 2095 __node_allocator& __na = __node_alloc(); 2096 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2097 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v)); 2098 __h.get_deleter().__value_constructed = true; 2099 __h->__hash_ = __hash; 2100 __h->__next_ = nullptr; 2101 return __h; 2102 } 2103 2104 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2105 2106 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2107 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2108 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v) 2109 { 2110 __node_allocator& __na = __node_alloc(); 2111 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2112 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2113 __h.get_deleter().__value_constructed = true; 2114 __h->__hash_ = hash_function()(__h->__value_); 2115 __h->__next_ = nullptr; 2116 return _VSTD::move(__h); // explicitly moved for C++03 2117 } 2118 2119 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2120 2121 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2122 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2123 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v, 2124 size_t __hash) 2125 { 2126 __node_allocator& __na = __node_alloc(); 2127 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2128 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v); 2129 __h.get_deleter().__value_constructed = true; 2130 __h->__hash_ = __hash; 2131 __h->__next_ = nullptr; 2132 return _VSTD::move(__h); // explicitly moved for C++03 2133 } 2134 2135 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2136 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2137 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2138 { 2139 __node_pointer __np = __p.__node_; 2140 #if _LIBCPP_DEBUG_LEVEL >= 2 2141 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2142 "unordered container erase(iterator) called with an iterator not" 2143 " referring to this container"); 2144 _LIBCPP_ASSERT(__p != end(), 2145 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2146 iterator __r(__np, this); 2147 #else 2148 iterator __r(__np); 2149 #endif 2150 ++__r; 2151 remove(__p); 2152 return __r; 2153 } 2154 2155 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2156 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2157 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2158 const_iterator __last) 2159 { 2160 #if _LIBCPP_DEBUG_LEVEL >= 2 2161 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2162 "unodered container::erase(iterator, iterator) called with an iterator not" 2163 " referring to this unodered container"); 2164 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2165 "unodered container::erase(iterator, iterator) called with an iterator not" 2166 " referring to this unodered container"); 2167 #endif 2168 for (const_iterator __p = __first; __first != __last; __p = __first) 2169 { 2170 ++__first; 2171 erase(__p); 2172 } 2173 __node_pointer __np = __last.__node_; 2174 #if _LIBCPP_DEBUG_LEVEL >= 2 2175 return iterator (__np, this); 2176 #else 2177 return iterator (__np); 2178 #endif 2179 } 2180 2181 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2182 template <class _Key> 2183 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2184 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2185 { 2186 iterator __i = find(__k); 2187 if (__i == end()) 2188 return 0; 2189 erase(__i); 2190 return 1; 2191 } 2192 2193 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2194 template <class _Key> 2195 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2196 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2197 { 2198 size_type __r = 0; 2199 iterator __i = find(__k); 2200 if (__i != end()) 2201 { 2202 iterator __e = end(); 2203 do 2204 { 2205 erase(__i++); 2206 ++__r; 2207 } while (__i != __e && key_eq()(*__i, __k)); 2208 } 2209 return __r; 2210 } 2211 2212 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2213 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2214 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2215 { 2216 // current node 2217 __node_pointer __cn = __p.__node_; 2218 size_type __bc = bucket_count(); 2219 size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2220 // find previous node 2221 __node_pointer __pn = __bucket_list_[__chash]; 2222 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2223 ; 2224 // Fix up __bucket_list_ 2225 // if __pn is not in same bucket (before begin is not in same bucket) && 2226 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2227 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2228 || __constrain_hash(__pn->__hash_, __bc) != __chash) 2229 { 2230 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2231 __bucket_list_[__chash] = nullptr; 2232 } 2233 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2234 if (__cn->__next_ != nullptr) 2235 { 2236 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2237 if (__nhash != __chash) 2238 __bucket_list_[__nhash] = __pn; 2239 } 2240 // remove __cn 2241 __pn->__next_ = __cn->__next_; 2242 __cn->__next_ = nullptr; 2243 --size(); 2244 #if _LIBCPP_DEBUG_LEVEL >= 2 2245 __c_node* __c = __get_db()->__find_c_and_lock(this); 2246 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2247 { 2248 --__p; 2249 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2250 if (__i->__node_ == __cn) 2251 { 2252 (*__p)->__c_ = nullptr; 2253 if (--__c->end_ != __p) 2254 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2255 } 2256 } 2257 __get_db()->unlock(); 2258 #endif 2259 return __node_holder(__cn, _Dp(__node_alloc(), true)); 2260 } 2261 2262 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2263 template <class _Key> 2264 inline _LIBCPP_INLINE_VISIBILITY 2265 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2266 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2267 { 2268 return static_cast<size_type>(find(__k) != end()); 2269 } 2270 2271 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2272 template <class _Key> 2273 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2274 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2275 { 2276 size_type __r = 0; 2277 const_iterator __i = find(__k); 2278 if (__i != end()) 2279 { 2280 const_iterator __e = end(); 2281 do 2282 { 2283 ++__i; 2284 ++__r; 2285 } while (__i != __e && key_eq()(*__i, __k)); 2286 } 2287 return __r; 2288 } 2289 2290 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2291 template <class _Key> 2292 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2293 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2294 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2295 const _Key& __k) 2296 { 2297 iterator __i = find(__k); 2298 iterator __j = __i; 2299 if (__i != end()) 2300 ++__j; 2301 return pair<iterator, iterator>(__i, __j); 2302 } 2303 2304 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2305 template <class _Key> 2306 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2307 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2308 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2309 const _Key& __k) const 2310 { 2311 const_iterator __i = find(__k); 2312 const_iterator __j = __i; 2313 if (__i != end()) 2314 ++__j; 2315 return pair<const_iterator, const_iterator>(__i, __j); 2316 } 2317 2318 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2319 template <class _Key> 2320 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2321 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2322 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2323 const _Key& __k) 2324 { 2325 iterator __i = find(__k); 2326 iterator __j = __i; 2327 if (__i != end()) 2328 { 2329 iterator __e = end(); 2330 do 2331 { 2332 ++__j; 2333 } while (__j != __e && key_eq()(*__j, __k)); 2334 } 2335 return pair<iterator, iterator>(__i, __j); 2336 } 2337 2338 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2339 template <class _Key> 2340 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2341 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2342 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2343 const _Key& __k) const 2344 { 2345 const_iterator __i = find(__k); 2346 const_iterator __j = __i; 2347 if (__i != end()) 2348 { 2349 const_iterator __e = end(); 2350 do 2351 { 2352 ++__j; 2353 } while (__j != __e && key_eq()(*__j, __k)); 2354 } 2355 return pair<const_iterator, const_iterator>(__i, __j); 2356 } 2357 2358 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2359 void 2360 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2361 _NOEXCEPT_( 2362 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value || 2363 __is_nothrow_swappable<__pointer_allocator>::value) && 2364 (!__node_traits::propagate_on_container_swap::value || 2365 __is_nothrow_swappable<__node_allocator>::value) && 2366 __is_nothrow_swappable<hasher>::value && 2367 __is_nothrow_swappable<key_equal>::value) 2368 { 2369 { 2370 __node_pointer_pointer __npp = __bucket_list_.release(); 2371 __bucket_list_.reset(__u.__bucket_list_.release()); 2372 __u.__bucket_list_.reset(__npp); 2373 } 2374 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2375 __swap_alloc(__bucket_list_.get_deleter().__alloc(), 2376 __u.__bucket_list_.get_deleter().__alloc()); 2377 __swap_alloc(__node_alloc(), __u.__node_alloc()); 2378 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2379 __p2_.swap(__u.__p2_); 2380 __p3_.swap(__u.__p3_); 2381 if (size() > 0) 2382 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2383 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2384 if (__u.size() > 0) 2385 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2386 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2387 #if _LIBCPP_DEBUG_LEVEL >= 2 2388 __get_db()->swap(this, &__u); 2389 #endif 2390 } 2391 2392 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2393 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2394 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2395 { 2396 _LIBCPP_ASSERT(__n < bucket_count(), 2397 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2398 __node_const_pointer __np = __bucket_list_[__n]; 2399 size_type __bc = bucket_count(); 2400 size_type __r = 0; 2401 if (__np != nullptr) 2402 { 2403 for (__np = __np->__next_; __np != nullptr && 2404 __constrain_hash(__np->__hash_, __bc) == __n; 2405 __np = __np->__next_, ++__r) 2406 ; 2407 } 2408 return __r; 2409 } 2410 2411 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2412 inline _LIBCPP_INLINE_VISIBILITY 2413 void 2414 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2415 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2416 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2417 { 2418 __x.swap(__y); 2419 } 2420 2421 #if _LIBCPP_DEBUG_LEVEL >= 2 2422 2423 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2424 bool 2425 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2426 { 2427 return __i->__node_ != nullptr; 2428 } 2429 2430 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2431 bool 2432 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2433 { 2434 return false; 2435 } 2436 2437 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2438 bool 2439 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2440 { 2441 return false; 2442 } 2443 2444 template <class _Tp, class _Hash, class _Equal, class _Alloc> 2445 bool 2446 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2447 { 2448 return false; 2449 } 2450 2451 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2452 _LIBCPP_END_NAMESPACE_STD 2453 2454 #endif // _LIBCPP__HASH_TABLE 2455
