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