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