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) : 94 (__h < __bc ? __h : __h % __bc); 95} 96 97inline _LIBCPP_INLINE_VISIBILITY 98size_t 99__next_hash_pow2(size_t __n) 100{ 101 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1)); 102} 103 104 105template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table; 106 107template <class _NodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_iterator; 108template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 109template <class _NodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator; 110template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 111template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 112template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 113 114template <class _Tp> 115struct __hash_key_value_types { 116 static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, ""); 117 typedef _Tp key_type; 118 typedef _Tp __node_value_type; 119 typedef _Tp __container_value_type; 120 static const bool __is_map = false; 121 122 _LIBCPP_INLINE_VISIBILITY 123 static key_type const& __get_key(_Tp const& __v) { 124 return __v; 125 } 126 _LIBCPP_INLINE_VISIBILITY 127 static __container_value_type const& __get_value(__node_value_type const& __v) { 128 return __v; 129 } 130 _LIBCPP_INLINE_VISIBILITY 131 static __container_value_type* __get_ptr(__node_value_type& __n) { 132 return _VSTD::addressof(__n); 133 } 134#ifndef _LIBCPP_CXX03_LANG 135 _LIBCPP_INLINE_VISIBILITY 136 static __container_value_type&& __move(__node_value_type& __v) { 137 return _VSTD::move(__v); 138 } 139#endif 140}; 141 142template <class _Key, class _Tp> 143struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > { 144 typedef _Key key_type; 145 typedef _Tp mapped_type; 146 typedef __hash_value_type<_Key, _Tp> __node_value_type; 147 typedef pair<const _Key, _Tp> __container_value_type; 148 typedef pair<_Key, _Tp> __nc_value_type; 149 typedef __container_value_type __map_value_type; 150 static const bool __is_map = true; 151 152 _LIBCPP_INLINE_VISIBILITY 153 static key_type const& __get_key(__container_value_type const& __v) { 154 return __v.first; 155 } 156 157 template <class _Up> 158 _LIBCPP_INLINE_VISIBILITY 159 static typename enable_if<__is_same_uncvref<_Up, __node_value_type>::value, 160 __container_value_type const&>::type 161 __get_value(_Up& __t) { 162 return __t.__cc; 163 } 164 165 template <class _Up> 166 _LIBCPP_INLINE_VISIBILITY 167 static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, 168 __container_value_type const&>::type 169 __get_value(_Up& __t) { 170 return __t; 171 } 172 173 _LIBCPP_INLINE_VISIBILITY 174 static __container_value_type* __get_ptr(__node_value_type& __n) { 175 return _VSTD::addressof(__n.__cc); 176 } 177#ifndef _LIBCPP_CXX03_LANG 178 _LIBCPP_INLINE_VISIBILITY 179 static __nc_value_type&& __move(__node_value_type& __v) { 180 return _VSTD::move(__v.__nc); 181 } 182#endif 183 184}; 185 186template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, 187 bool = _KVTypes::__is_map> 188struct __hash_map_pointer_types {}; 189 190template <class _Tp, class _AllocPtr, class _KVTypes> 191struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> { 192 typedef typename _KVTypes::__map_value_type _Mv; 193 typedef typename __rebind_pointer<_AllocPtr, _Mv>::type 194 __map_value_type_pointer; 195 typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type 196 __const_map_value_type_pointer; 197}; 198 199template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type> 200struct __hash_node_types; 201 202template <class _NodePtr, class _Tp, class _VoidPtr> 203struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> > 204 : public __hash_key_value_types<_Tp>, __hash_map_pointer_types<_Tp, _VoidPtr> 205 206{ 207 typedef __hash_key_value_types<_Tp> __base; 208 209public: 210 typedef ptrdiff_t difference_type; 211 typedef size_t size_type; 212 213 typedef typename __rebind_pointer<_NodePtr, void>::type __void_pointer; 214 215 typedef typename pointer_traits<_NodePtr>::element_type __node_type; 216 typedef _NodePtr __node_pointer; 217 218 typedef __hash_node_base<__node_pointer> __node_base_type; 219 typedef typename __rebind_pointer<_NodePtr, __node_base_type>::type 220 __node_base_pointer; 221 222 typedef _Tp __node_value_type; 223 typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type 224 __node_value_type_pointer; 225 typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type 226 __const_node_value_type_pointer; 227private: 228 static_assert(!is_const<__node_type>::value, 229 "_NodePtr should never be a pointer to const"); 230 static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value), 231 "_VoidPtr does not point to unqualified void type"); 232 static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type, 233 _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr."); 234}; 235 236 237 238template <class _HashIterator> 239struct __hash_node_types_from_iterator; 240template <class _NodePtr> 241struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 242template <class _NodePtr> 243struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 244template <class _NodePtr> 245struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 246template <class _NodePtr> 247struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {}; 248 249 250template <class _NodeValueTp, class _VoidPtr> 251struct __make_hash_node_types { 252 typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp; 253 typedef typename __rebind_pointer<_VoidPtr, _NodeTp>::type _NodePtr; 254 typedef __hash_node_types<_NodePtr> type; 255}; 256 257template <class _NodePtr> 258class _LIBCPP_TYPE_VIS_ONLY __hash_iterator 259{ 260 typedef __hash_node_types<_NodePtr> _NodeTypes; 261 typedef _NodePtr __node_pointer; 262 263 __node_pointer __node_; 264 265public: 266 typedef forward_iterator_tag iterator_category; 267 typedef typename _NodeTypes::__node_value_type value_type; 268 typedef typename _NodeTypes::difference_type difference_type; 269 typedef value_type& reference; 270 typedef typename _NodeTypes::__node_value_type_pointer pointer; 271 272 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT 273#if _LIBCPP_STD_VER > 11 274 : __node_(nullptr) 275#endif 276 { 277#if _LIBCPP_DEBUG_LEVEL >= 2 278 __get_db()->__insert_i(this); 279#endif 280 } 281 282#if _LIBCPP_DEBUG_LEVEL >= 2 283 284 _LIBCPP_INLINE_VISIBILITY 285 __hash_iterator(const __hash_iterator& __i) 286 : __node_(__i.__node_) 287 { 288 __get_db()->__iterator_copy(this, &__i); 289 } 290 291 _LIBCPP_INLINE_VISIBILITY 292 ~__hash_iterator() 293 { 294 __get_db()->__erase_i(this); 295 } 296 297 _LIBCPP_INLINE_VISIBILITY 298 __hash_iterator& operator=(const __hash_iterator& __i) 299 { 300 if (this != &__i) 301 { 302 __get_db()->__iterator_copy(this, &__i); 303 __node_ = __i.__node_; 304 } 305 return *this; 306 } 307 308#endif // _LIBCPP_DEBUG_LEVEL >= 2 309 310 _LIBCPP_INLINE_VISIBILITY 311 reference operator*() const 312 { 313#if _LIBCPP_DEBUG_LEVEL >= 2 314 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 315 "Attempted to dereference a non-dereferenceable unordered container iterator"); 316#endif 317 return __node_->__value_; 318 } 319 _LIBCPP_INLINE_VISIBILITY 320 pointer operator->() const 321 { 322#if _LIBCPP_DEBUG_LEVEL >= 2 323 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 324 "Attempted to dereference a non-dereferenceable unordered container iterator"); 325#endif 326 return pointer_traits<pointer>::pointer_to(__node_->__value_); 327 } 328 329 _LIBCPP_INLINE_VISIBILITY 330 __hash_iterator& operator++() 331 { 332#if _LIBCPP_DEBUG_LEVEL >= 2 333 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 334 "Attempted to increment non-incrementable unordered container iterator"); 335#endif 336 __node_ = __node_->__next_; 337 return *this; 338 } 339 340 _LIBCPP_INLINE_VISIBILITY 341 __hash_iterator operator++(int) 342 { 343 __hash_iterator __t(*this); 344 ++(*this); 345 return __t; 346 } 347 348 friend _LIBCPP_INLINE_VISIBILITY 349 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) 350 { 351 return __x.__node_ == __y.__node_; 352 } 353 friend _LIBCPP_INLINE_VISIBILITY 354 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) 355 {return !(__x == __y);} 356 357private: 358#if _LIBCPP_DEBUG_LEVEL >= 2 359 _LIBCPP_INLINE_VISIBILITY 360 __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 361 : __node_(__node) 362 { 363 __get_db()->__insert_ic(this, __c); 364 } 365#else 366 _LIBCPP_INLINE_VISIBILITY 367 __hash_iterator(__node_pointer __node) _NOEXCEPT 368 : __node_(__node) 369 {} 370#endif 371 372 template <class, class, class, class> friend class __hash_table; 373 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator; 374 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 375 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 376 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 377}; 378 379template <class _NodePtr> 380class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator 381{ 382 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, ""); 383 typedef __hash_node_types<_NodePtr> _NodeTypes; 384 typedef _NodePtr __node_pointer; 385 386 __node_pointer __node_; 387 388public: 389 typedef __hash_iterator<_NodePtr> __non_const_iterator; 390 391 typedef forward_iterator_tag iterator_category; 392 typedef typename _NodeTypes::__node_value_type value_type; 393 typedef typename _NodeTypes::difference_type difference_type; 394 typedef const value_type& reference; 395 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 396 397 398 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT 399#if _LIBCPP_STD_VER > 11 400 : __node_(nullptr) 401#endif 402 { 403#if _LIBCPP_DEBUG_LEVEL >= 2 404 __get_db()->__insert_i(this); 405#endif 406 } 407 _LIBCPP_INLINE_VISIBILITY 408 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT 409 : __node_(__x.__node_) 410 { 411#if _LIBCPP_DEBUG_LEVEL >= 2 412 __get_db()->__iterator_copy(this, &__x); 413#endif 414 } 415 416#if _LIBCPP_DEBUG_LEVEL >= 2 417 418 _LIBCPP_INLINE_VISIBILITY 419 __hash_const_iterator(const __hash_const_iterator& __i) 420 : __node_(__i.__node_) 421 { 422 __get_db()->__iterator_copy(this, &__i); 423 } 424 425 _LIBCPP_INLINE_VISIBILITY 426 ~__hash_const_iterator() 427 { 428 __get_db()->__erase_i(this); 429 } 430 431 _LIBCPP_INLINE_VISIBILITY 432 __hash_const_iterator& operator=(const __hash_const_iterator& __i) 433 { 434 if (this != &__i) 435 { 436 __get_db()->__iterator_copy(this, &__i); 437 __node_ = __i.__node_; 438 } 439 return *this; 440 } 441 442#endif // _LIBCPP_DEBUG_LEVEL >= 2 443 444 _LIBCPP_INLINE_VISIBILITY 445 reference operator*() const 446 { 447#if _LIBCPP_DEBUG_LEVEL >= 2 448 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 449 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 450#endif 451 return __node_->__value_; 452 } 453 _LIBCPP_INLINE_VISIBILITY 454 pointer operator->() const 455 { 456#if _LIBCPP_DEBUG_LEVEL >= 2 457 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 458 "Attempted to dereference a non-dereferenceable unordered container const_iterator"); 459#endif 460 return pointer_traits<pointer>::pointer_to(__node_->__value_); 461 } 462 463 _LIBCPP_INLINE_VISIBILITY 464 __hash_const_iterator& operator++() 465 { 466#if _LIBCPP_DEBUG_LEVEL >= 2 467 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 468 "Attempted to increment non-incrementable unordered container const_iterator"); 469#endif 470 __node_ = __node_->__next_; 471 return *this; 472 } 473 474 _LIBCPP_INLINE_VISIBILITY 475 __hash_const_iterator operator++(int) 476 { 477 __hash_const_iterator __t(*this); 478 ++(*this); 479 return __t; 480 } 481 482 friend _LIBCPP_INLINE_VISIBILITY 483 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 484 { 485 return __x.__node_ == __y.__node_; 486 } 487 friend _LIBCPP_INLINE_VISIBILITY 488 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) 489 {return !(__x == __y);} 490 491private: 492#if _LIBCPP_DEBUG_LEVEL >= 2 493 _LIBCPP_INLINE_VISIBILITY 494 __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT 495 : __node_(__node) 496 { 497 __get_db()->__insert_ic(this, __c); 498 } 499#else 500 _LIBCPP_INLINE_VISIBILITY 501 __hash_const_iterator(__node_pointer __node) _NOEXCEPT 502 : __node_(__node) 503 {} 504#endif 505 506 template <class, class, class, class> friend class __hash_table; 507 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 508 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 509 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 510}; 511 512template <class _NodePtr> 513class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator 514{ 515 typedef __hash_node_types<_NodePtr> _NodeTypes; 516 typedef _NodePtr __node_pointer; 517 518 __node_pointer __node_; 519 size_t __bucket_; 520 size_t __bucket_count_; 521 522public: 523 typedef forward_iterator_tag iterator_category; 524 typedef typename _NodeTypes::__node_value_type value_type; 525 typedef typename _NodeTypes::difference_type difference_type; 526 typedef value_type& reference; 527 typedef typename _NodeTypes::__node_value_type_pointer pointer; 528 529 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT 530 { 531#if _LIBCPP_DEBUG_LEVEL >= 2 532 __get_db()->__insert_i(this); 533#endif 534 } 535 536#if _LIBCPP_DEBUG_LEVEL >= 2 537 538 _LIBCPP_INLINE_VISIBILITY 539 __hash_local_iterator(const __hash_local_iterator& __i) 540 : __node_(__i.__node_), 541 __bucket_(__i.__bucket_), 542 __bucket_count_(__i.__bucket_count_) 543 { 544 __get_db()->__iterator_copy(this, &__i); 545 } 546 547 _LIBCPP_INLINE_VISIBILITY 548 ~__hash_local_iterator() 549 { 550 __get_db()->__erase_i(this); 551 } 552 553 _LIBCPP_INLINE_VISIBILITY 554 __hash_local_iterator& operator=(const __hash_local_iterator& __i) 555 { 556 if (this != &__i) 557 { 558 __get_db()->__iterator_copy(this, &__i); 559 __node_ = __i.__node_; 560 __bucket_ = __i.__bucket_; 561 __bucket_count_ = __i.__bucket_count_; 562 } 563 return *this; 564 } 565 566#endif // _LIBCPP_DEBUG_LEVEL >= 2 567 568 _LIBCPP_INLINE_VISIBILITY 569 reference operator*() const 570 { 571#if _LIBCPP_DEBUG_LEVEL >= 2 572 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 573 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 574#endif 575 return __node_->__value_; 576 } 577 _LIBCPP_INLINE_VISIBILITY 578 pointer operator->() const 579 { 580#if _LIBCPP_DEBUG_LEVEL >= 2 581 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 582 "Attempted to dereference a non-dereferenceable unordered container local_iterator"); 583#endif 584 return pointer_traits<pointer>::pointer_to(__node_->__value_); 585 } 586 587 _LIBCPP_INLINE_VISIBILITY 588 __hash_local_iterator& operator++() 589 { 590#if _LIBCPP_DEBUG_LEVEL >= 2 591 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 592 "Attempted to increment non-incrementable unordered container local_iterator"); 593#endif 594 __node_ = __node_->__next_; 595 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 596 __node_ = nullptr; 597 return *this; 598 } 599 600 _LIBCPP_INLINE_VISIBILITY 601 __hash_local_iterator operator++(int) 602 { 603 __hash_local_iterator __t(*this); 604 ++(*this); 605 return __t; 606 } 607 608 friend _LIBCPP_INLINE_VISIBILITY 609 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 610 { 611 return __x.__node_ == __y.__node_; 612 } 613 friend _LIBCPP_INLINE_VISIBILITY 614 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) 615 {return !(__x == __y);} 616 617private: 618#if _LIBCPP_DEBUG_LEVEL >= 2 619 _LIBCPP_INLINE_VISIBILITY 620 __hash_local_iterator(__node_pointer __node, size_t __bucket, 621 size_t __bucket_count, const void* __c) _NOEXCEPT 622 : __node_(__node), 623 __bucket_(__bucket), 624 __bucket_count_(__bucket_count) 625 { 626 __get_db()->__insert_ic(this, __c); 627 if (__node_ != nullptr) 628 __node_ = __node_->__next_; 629 } 630#else 631 _LIBCPP_INLINE_VISIBILITY 632 __hash_local_iterator(__node_pointer __node, size_t __bucket, 633 size_t __bucket_count) _NOEXCEPT 634 : __node_(__node), 635 __bucket_(__bucket), 636 __bucket_count_(__bucket_count) 637 { 638 if (__node_ != nullptr) 639 __node_ = __node_->__next_; 640 } 641#endif 642 template <class, class, class, class> friend class __hash_table; 643 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator; 644 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator; 645}; 646 647template <class _ConstNodePtr> 648class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator 649{ 650 typedef __hash_node_types<_ConstNodePtr> _NodeTypes; 651 typedef _ConstNodePtr __node_pointer; 652 653 __node_pointer __node_; 654 size_t __bucket_; 655 size_t __bucket_count_; 656 657 typedef pointer_traits<__node_pointer> __pointer_traits; 658 typedef typename __pointer_traits::element_type __node; 659 typedef typename remove_const<__node>::type __non_const_node; 660 typedef typename __rebind_pointer<__node_pointer, __non_const_node>::type 661 __non_const_node_pointer; 662public: 663 typedef __hash_local_iterator<__non_const_node_pointer> 664 __non_const_iterator; 665 666 typedef forward_iterator_tag iterator_category; 667 typedef typename _NodeTypes::__node_value_type value_type; 668 typedef typename _NodeTypes::difference_type difference_type; 669 typedef const value_type& reference; 670 typedef typename _NodeTypes::__const_node_value_type_pointer pointer; 671 672 673 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT 674 { 675#if _LIBCPP_DEBUG_LEVEL >= 2 676 __get_db()->__insert_i(this); 677#endif 678 } 679 680 _LIBCPP_INLINE_VISIBILITY 681 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT 682 : __node_(__x.__node_), 683 __bucket_(__x.__bucket_), 684 __bucket_count_(__x.__bucket_count_) 685 { 686#if _LIBCPP_DEBUG_LEVEL >= 2 687 __get_db()->__iterator_copy(this, &__x); 688#endif 689 } 690 691#if _LIBCPP_DEBUG_LEVEL >= 2 692 693 _LIBCPP_INLINE_VISIBILITY 694 __hash_const_local_iterator(const __hash_const_local_iterator& __i) 695 : __node_(__i.__node_), 696 __bucket_(__i.__bucket_), 697 __bucket_count_(__i.__bucket_count_) 698 { 699 __get_db()->__iterator_copy(this, &__i); 700 } 701 702 _LIBCPP_INLINE_VISIBILITY 703 ~__hash_const_local_iterator() 704 { 705 __get_db()->__erase_i(this); 706 } 707 708 _LIBCPP_INLINE_VISIBILITY 709 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i) 710 { 711 if (this != &__i) 712 { 713 __get_db()->__iterator_copy(this, &__i); 714 __node_ = __i.__node_; 715 __bucket_ = __i.__bucket_; 716 __bucket_count_ = __i.__bucket_count_; 717 } 718 return *this; 719 } 720 721#endif // _LIBCPP_DEBUG_LEVEL >= 2 722 723 _LIBCPP_INLINE_VISIBILITY 724 reference operator*() const 725 { 726#if _LIBCPP_DEBUG_LEVEL >= 2 727 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 728 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 729#endif 730 return __node_->__value_; 731 } 732 _LIBCPP_INLINE_VISIBILITY 733 pointer operator->() const 734 { 735#if _LIBCPP_DEBUG_LEVEL >= 2 736 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 737 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator"); 738#endif 739 return pointer_traits<pointer>::pointer_to(__node_->__value_); 740 } 741 742 _LIBCPP_INLINE_VISIBILITY 743 __hash_const_local_iterator& operator++() 744 { 745#if _LIBCPP_DEBUG_LEVEL >= 2 746 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 747 "Attempted to increment non-incrementable unordered container const_local_iterator"); 748#endif 749 __node_ = __node_->__next_; 750 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_) 751 __node_ = nullptr; 752 return *this; 753 } 754 755 _LIBCPP_INLINE_VISIBILITY 756 __hash_const_local_iterator operator++(int) 757 { 758 __hash_const_local_iterator __t(*this); 759 ++(*this); 760 return __t; 761 } 762 763 friend _LIBCPP_INLINE_VISIBILITY 764 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 765 { 766 return __x.__node_ == __y.__node_; 767 } 768 friend _LIBCPP_INLINE_VISIBILITY 769 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) 770 {return !(__x == __y);} 771 772private: 773#if _LIBCPP_DEBUG_LEVEL >= 2 774 _LIBCPP_INLINE_VISIBILITY 775 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 776 size_t __bucket_count, const void* __c) _NOEXCEPT 777 : __node_(__node), 778 __bucket_(__bucket), 779 __bucket_count_(__bucket_count) 780 { 781 __get_db()->__insert_ic(this, __c); 782 if (__node_ != nullptr) 783 __node_ = __node_->__next_; 784 } 785#else 786 _LIBCPP_INLINE_VISIBILITY 787 __hash_const_local_iterator(__node_pointer __node, size_t __bucket, 788 size_t __bucket_count) _NOEXCEPT 789 : __node_(__node), 790 __bucket_(__bucket), 791 __bucket_count_(__bucket_count) 792 { 793 if (__node_ != nullptr) 794 __node_ = __node_->__next_; 795 } 796#endif 797 template <class, class, class, class> friend class __hash_table; 798 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator; 799}; 800 801template <class _Alloc> 802class __bucket_list_deallocator 803{ 804 typedef _Alloc allocator_type; 805 typedef allocator_traits<allocator_type> __alloc_traits; 806 typedef typename __alloc_traits::size_type size_type; 807 808 __compressed_pair<size_type, allocator_type> __data_; 809public: 810 typedef typename __alloc_traits::pointer pointer; 811 812 _LIBCPP_INLINE_VISIBILITY 813 __bucket_list_deallocator() 814 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 815 : __data_(0) {} 816 817 _LIBCPP_INLINE_VISIBILITY 818 __bucket_list_deallocator(const allocator_type& __a, size_type __size) 819 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 820 : __data_(__size, __a) {} 821 822#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 823 824 _LIBCPP_INLINE_VISIBILITY 825 __bucket_list_deallocator(__bucket_list_deallocator&& __x) 826 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 827 : __data_(_VSTD::move(__x.__data_)) 828 { 829 __x.size() = 0; 830 } 831 832#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 833 834 _LIBCPP_INLINE_VISIBILITY 835 size_type& size() _NOEXCEPT {return __data_.first();} 836 _LIBCPP_INLINE_VISIBILITY 837 size_type size() const _NOEXCEPT {return __data_.first();} 838 839 _LIBCPP_INLINE_VISIBILITY 840 allocator_type& __alloc() _NOEXCEPT {return __data_.second();} 841 _LIBCPP_INLINE_VISIBILITY 842 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();} 843 844 _LIBCPP_INLINE_VISIBILITY 845 void operator()(pointer __p) _NOEXCEPT 846 { 847 __alloc_traits::deallocate(__alloc(), __p, size()); 848 } 849}; 850 851template <class _Alloc> class __hash_map_node_destructor; 852 853template <class _Alloc> 854class __hash_node_destructor 855{ 856 typedef _Alloc allocator_type; 857 typedef allocator_traits<allocator_type> __alloc_traits; 858 859public: 860 typedef typename __alloc_traits::pointer pointer; 861private: 862 typedef __hash_node_types<pointer> _NodeTypes; 863 864 allocator_type& __na_; 865 866 __hash_node_destructor& operator=(const __hash_node_destructor&); 867 868public: 869 bool __value_constructed; 870 871 _LIBCPP_INLINE_VISIBILITY 872 explicit __hash_node_destructor(allocator_type& __na, 873 bool __constructed = false) _NOEXCEPT 874 : __na_(__na), 875 __value_constructed(__constructed) 876 {} 877 878 _LIBCPP_INLINE_VISIBILITY 879 void operator()(pointer __p) _NOEXCEPT 880 { 881 if (__value_constructed) 882 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 883 if (__p) 884 __alloc_traits::deallocate(__na_, __p, 1); 885 } 886 887 template <class> friend class __hash_map_node_destructor; 888}; 889 890template <class _Tp, class _Hash, class _Equal, class _Alloc> 891class __hash_table 892{ 893public: 894 typedef _Tp value_type; 895 typedef _Hash hasher; 896 typedef _Equal key_equal; 897 typedef _Alloc allocator_type; 898 899private: 900 typedef allocator_traits<allocator_type> __alloc_traits; 901 typedef typename 902 __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type 903 _NodeTypes; 904public: 905 906 typedef typename _NodeTypes::__node_value_type __node_value_type; 907 typedef typename _NodeTypes::__container_value_type __container_value_type; 908 typedef typename _NodeTypes::key_type key_type; 909 typedef value_type& reference; 910 typedef const value_type& const_reference; 911 typedef typename __alloc_traits::pointer pointer; 912 typedef typename __alloc_traits::const_pointer const_pointer; 913#ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE 914 typedef typename __alloc_traits::size_type size_type; 915#else 916 typedef typename _NodeTypes::size_type size_type; 917#endif 918 typedef typename _NodeTypes::difference_type difference_type; 919public: 920 // Create __node 921 922 typedef typename _NodeTypes::__node_type __node; 923 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 924 typedef allocator_traits<__node_allocator> __node_traits; 925 typedef typename _NodeTypes::__void_pointer __void_pointer; 926 typedef typename _NodeTypes::__node_pointer __node_pointer; 927 typedef typename _NodeTypes::__node_pointer __node_const_pointer; 928 typedef typename _NodeTypes::__node_base_type __first_node; 929 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 930 931private: 932 // check for sane allocator pointer rebinding semantics. Rebinding the 933 // allocator for a new pointer type should be exactly the same as rebinding 934 // the pointer using 'pointer_traits'. 935 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), 936 "Allocator does not rebind pointers in a sane manner."); 937 typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type 938 __node_base_allocator; 939 typedef allocator_traits<__node_base_allocator> __node_base_traits; 940 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), 941 "Allocator does not rebind pointers in a sane manner."); 942 943private: 944 945 typedef typename __rebind_alloc_helper<__node_traits, __node_pointer>::type __pointer_allocator; 946 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 947 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list; 948 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 949 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 950 951 // --- Member data begin --- 952 __bucket_list __bucket_list_; 953 __compressed_pair<__first_node, __node_allocator> __p1_; 954 __compressed_pair<size_type, hasher> __p2_; 955 __compressed_pair<float, key_equal> __p3_; 956 // --- Member data end --- 957 958 _LIBCPP_INLINE_VISIBILITY 959 size_type& size() _NOEXCEPT {return __p2_.first();} 960public: 961 _LIBCPP_INLINE_VISIBILITY 962 size_type size() const _NOEXCEPT {return __p2_.first();} 963 964 _LIBCPP_INLINE_VISIBILITY 965 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 966 _LIBCPP_INLINE_VISIBILITY 967 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 968 969 _LIBCPP_INLINE_VISIBILITY 970 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 971 _LIBCPP_INLINE_VISIBILITY 972 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 973 974 _LIBCPP_INLINE_VISIBILITY 975 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 976 _LIBCPP_INLINE_VISIBILITY 977 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 978 979 _LIBCPP_INLINE_VISIBILITY 980 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 981 _LIBCPP_INLINE_VISIBILITY 982 const __node_allocator& __node_alloc() const _NOEXCEPT 983 {return __p1_.second();} 984 985public: 986 typedef __hash_iterator<__node_pointer> iterator; 987 typedef __hash_const_iterator<__node_pointer> const_iterator; 988 typedef __hash_local_iterator<__node_pointer> local_iterator; 989 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 990 991 _LIBCPP_INLINE_VISIBILITY 992 __hash_table() 993 _NOEXCEPT_( 994 is_nothrow_default_constructible<__bucket_list>::value && 995 is_nothrow_default_constructible<__first_node>::value && 996 is_nothrow_default_constructible<__node_allocator>::value && 997 is_nothrow_default_constructible<hasher>::value && 998 is_nothrow_default_constructible<key_equal>::value); 999 _LIBCPP_INLINE_VISIBILITY 1000 __hash_table(const hasher& __hf, const key_equal& __eql); 1001 __hash_table(const hasher& __hf, const key_equal& __eql, 1002 const allocator_type& __a); 1003 explicit __hash_table(const allocator_type& __a); 1004 __hash_table(const __hash_table& __u); 1005 __hash_table(const __hash_table& __u, const allocator_type& __a); 1006#ifndef _LIBCPP_CXX03_LANG 1007 __hash_table(__hash_table&& __u) 1008 _NOEXCEPT_( 1009 is_nothrow_move_constructible<__bucket_list>::value && 1010 is_nothrow_move_constructible<__first_node>::value && 1011 is_nothrow_move_constructible<__node_allocator>::value && 1012 is_nothrow_move_constructible<hasher>::value && 1013 is_nothrow_move_constructible<key_equal>::value); 1014 __hash_table(__hash_table&& __u, const allocator_type& __a); 1015#endif // _LIBCPP_CXX03_LANG 1016 ~__hash_table(); 1017 1018 __hash_table& operator=(const __hash_table& __u); 1019#ifndef _LIBCPP_CXX03_LANG 1020 _LIBCPP_INLINE_VISIBILITY 1021 __hash_table& operator=(__hash_table&& __u) 1022 _NOEXCEPT_( 1023 __node_traits::propagate_on_container_move_assignment::value && 1024 is_nothrow_move_assignable<__node_allocator>::value && 1025 is_nothrow_move_assignable<hasher>::value && 1026 is_nothrow_move_assignable<key_equal>::value); 1027#endif 1028 template <class _InputIterator> 1029 void __assign_unique(_InputIterator __first, _InputIterator __last); 1030 template <class _InputIterator> 1031 void __assign_multi(_InputIterator __first, _InputIterator __last); 1032 1033 _LIBCPP_INLINE_VISIBILITY 1034 size_type max_size() const _NOEXCEPT 1035 { 1036 return allocator_traits<__pointer_allocator>::max_size( 1037 __bucket_list_.get_deleter().__alloc()); 1038 } 1039 1040 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 1041 iterator __node_insert_multi(__node_pointer __nd); 1042 iterator __node_insert_multi(const_iterator __p, 1043 __node_pointer __nd); 1044 1045#ifndef _LIBCPP_CXX03_LANG 1046 template <class _Key, class ..._Args> 1047 _LIBCPP_INLINE_VISIBILITY 1048 pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args); 1049 1050 template <class... _Args> 1051 _LIBCPP_INLINE_VISIBILITY 1052 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 1053 1054 template <class _Pp> 1055 _LIBCPP_INLINE_VISIBILITY 1056 pair<iterator, bool> __emplace_unique(_Pp&& __x) { 1057 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), 1058 __can_extract_key<_Pp, key_type>()); 1059 } 1060 1061 template <class _First, class _Second> 1062 _LIBCPP_INLINE_VISIBILITY 1063 typename enable_if< 1064 __can_extract_map_key<_First, key_type, __container_value_type>::value, 1065 pair<iterator, bool> 1066 >::type __emplace_unique(_First&& __f, _Second&& __s) { 1067 return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), 1068 _VSTD::forward<_Second>(__s)); 1069 } 1070 1071 template <class... _Args> 1072 _LIBCPP_INLINE_VISIBILITY 1073 pair<iterator, bool> __emplace_unique(_Args&&... __args) { 1074 return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); 1075 } 1076 1077 template <class _Pp> 1078 _LIBCPP_INLINE_VISIBILITY 1079 pair<iterator, bool> 1080 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 1081 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); 1082 } 1083 template <class _Pp> 1084 _LIBCPP_INLINE_VISIBILITY 1085 pair<iterator, bool> 1086 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 1087 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); 1088 } 1089 template <class _Pp> 1090 _LIBCPP_INLINE_VISIBILITY 1091 pair<iterator, bool> 1092 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 1093 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); 1094 } 1095 1096 template <class... _Args> 1097 _LIBCPP_INLINE_VISIBILITY 1098 iterator __emplace_multi(_Args&&... __args); 1099 template <class... _Args> 1100 _LIBCPP_INLINE_VISIBILITY 1101 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 1102 1103 1104 _LIBCPP_INLINE_VISIBILITY 1105 pair<iterator, bool> 1106 __insert_unique(__container_value_type&& __x) { 1107 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x)); 1108 } 1109 1110 template <class _Pp, class = typename enable_if< 1111 !__is_same_uncvref<_Pp, __container_value_type>::value 1112 >::type> 1113 _LIBCPP_INLINE_VISIBILITY 1114 pair<iterator, bool> __insert_unique(_Pp&& __x) { 1115 return __emplace_unique(_VSTD::forward<_Pp>(__x)); 1116 } 1117 1118 template <class _Pp> 1119 _LIBCPP_INLINE_VISIBILITY 1120 iterator __insert_multi(_Pp&& __x) { 1121 return __emplace_multi(_VSTD::forward<_Pp>(__x)); 1122 } 1123 1124 template <class _Pp> 1125 _LIBCPP_INLINE_VISIBILITY 1126 iterator __insert_multi(const_iterator __p, _Pp&& __x) { 1127 return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x)); 1128 } 1129 1130#else // !defined(_LIBCPP_CXX03_LANG) 1131 template <class _Key, class _Args> 1132 pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args); 1133 1134 iterator __insert_multi(const __container_value_type& __x); 1135 iterator __insert_multi(const_iterator __p, const __container_value_type& __x); 1136#endif 1137 1138 _LIBCPP_INLINE_VISIBILITY 1139 pair<iterator, bool> __insert_unique(const __container_value_type& __x) { 1140 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); 1141 } 1142 1143 void clear() _NOEXCEPT; 1144 void rehash(size_type __n); 1145 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 1146 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 1147 1148 _LIBCPP_INLINE_VISIBILITY 1149 size_type bucket_count() const _NOEXCEPT 1150 { 1151 return __bucket_list_.get_deleter().size(); 1152 } 1153 1154 _LIBCPP_INLINE_VISIBILITY 1155 iterator begin() _NOEXCEPT; 1156 _LIBCPP_INLINE_VISIBILITY 1157 iterator end() _NOEXCEPT; 1158 _LIBCPP_INLINE_VISIBILITY 1159 const_iterator begin() const _NOEXCEPT; 1160 _LIBCPP_INLINE_VISIBILITY 1161 const_iterator end() const _NOEXCEPT; 1162 1163 template <class _Key> 1164 _LIBCPP_INLINE_VISIBILITY 1165 size_type bucket(const _Key& __k) const 1166 { 1167 _LIBCPP_ASSERT(bucket_count() > 0, 1168 "unordered container::bucket(key) called when bucket_count() == 0"); 1169 return __constrain_hash(hash_function()(__k), bucket_count()); 1170 } 1171 1172 template <class _Key> 1173 iterator find(const _Key& __x); 1174 template <class _Key> 1175 const_iterator find(const _Key& __x) const; 1176 1177 typedef __hash_node_destructor<__node_allocator> _Dp; 1178 typedef unique_ptr<__node, _Dp> __node_holder; 1179 1180 iterator erase(const_iterator __p); 1181 iterator erase(const_iterator __first, const_iterator __last); 1182 template <class _Key> 1183 size_type __erase_unique(const _Key& __k); 1184 template <class _Key> 1185 size_type __erase_multi(const _Key& __k); 1186 __node_holder remove(const_iterator __p) _NOEXCEPT; 1187 1188 template <class _Key> 1189 _LIBCPP_INLINE_VISIBILITY 1190 size_type __count_unique(const _Key& __k) const; 1191 template <class _Key> 1192 size_type __count_multi(const _Key& __k) const; 1193 1194 template <class _Key> 1195 pair<iterator, iterator> 1196 __equal_range_unique(const _Key& __k); 1197 template <class _Key> 1198 pair<const_iterator, const_iterator> 1199 __equal_range_unique(const _Key& __k) const; 1200 1201 template <class _Key> 1202 pair<iterator, iterator> 1203 __equal_range_multi(const _Key& __k); 1204 template <class _Key> 1205 pair<const_iterator, const_iterator> 1206 __equal_range_multi(const _Key& __k) const; 1207 1208 void swap(__hash_table& __u) 1209#if _LIBCPP_STD_VER <= 11 1210 _NOEXCEPT_( 1211 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 1212 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 1213 || __is_nothrow_swappable<__pointer_allocator>::value) 1214 && (!__node_traits::propagate_on_container_swap::value 1215 || __is_nothrow_swappable<__node_allocator>::value) 1216 ); 1217#else 1218 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 1219#endif 1220 1221 _LIBCPP_INLINE_VISIBILITY 1222 size_type max_bucket_count() const _NOEXCEPT 1223 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());} 1224 size_type bucket_size(size_type __n) const; 1225 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1226 { 1227 size_type __bc = bucket_count(); 1228 return __bc != 0 ? (float)size() / __bc : 0.f; 1229 } 1230 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1231 { 1232 _LIBCPP_ASSERT(__mlf > 0, 1233 "unordered container::max_load_factor(lf) called with lf <= 0"); 1234 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1235 } 1236 1237 _LIBCPP_INLINE_VISIBILITY 1238 local_iterator 1239 begin(size_type __n) 1240 { 1241 _LIBCPP_ASSERT(__n < bucket_count(), 1242 "unordered container::begin(n) called with n >= bucket_count()"); 1243#if _LIBCPP_DEBUG_LEVEL >= 2 1244 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1245#else 1246 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1247#endif 1248 } 1249 1250 _LIBCPP_INLINE_VISIBILITY 1251 local_iterator 1252 end(size_type __n) 1253 { 1254 _LIBCPP_ASSERT(__n < bucket_count(), 1255 "unordered container::end(n) called with n >= bucket_count()"); 1256#if _LIBCPP_DEBUG_LEVEL >= 2 1257 return local_iterator(nullptr, __n, bucket_count(), this); 1258#else 1259 return local_iterator(nullptr, __n, bucket_count()); 1260#endif 1261 } 1262 1263 _LIBCPP_INLINE_VISIBILITY 1264 const_local_iterator 1265 cbegin(size_type __n) const 1266 { 1267 _LIBCPP_ASSERT(__n < bucket_count(), 1268 "unordered container::cbegin(n) called with n >= bucket_count()"); 1269#if _LIBCPP_DEBUG_LEVEL >= 2 1270 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1271#else 1272 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1273#endif 1274 } 1275 1276 _LIBCPP_INLINE_VISIBILITY 1277 const_local_iterator 1278 cend(size_type __n) const 1279 { 1280 _LIBCPP_ASSERT(__n < bucket_count(), 1281 "unordered container::cend(n) called with n >= bucket_count()"); 1282#if _LIBCPP_DEBUG_LEVEL >= 2 1283 return const_local_iterator(nullptr, __n, bucket_count(), this); 1284#else 1285 return const_local_iterator(nullptr, __n, bucket_count()); 1286#endif 1287 } 1288 1289#if _LIBCPP_DEBUG_LEVEL >= 2 1290 1291 bool __dereferenceable(const const_iterator* __i) const; 1292 bool __decrementable(const const_iterator* __i) const; 1293 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1294 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1295 1296#endif // _LIBCPP_DEBUG_LEVEL >= 2 1297 1298private: 1299 void __rehash(size_type __n); 1300 1301#ifndef _LIBCPP_CXX03_LANG 1302 template <class ..._Args> 1303 __node_holder __construct_node(_Args&& ...__args); 1304 1305 template <class _First, class ..._Rest> 1306 __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest); 1307#else // _LIBCPP_CXX03_LANG 1308 __node_holder __construct_node(const __container_value_type& __v); 1309 __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v); 1310#endif 1311 1312 1313 _LIBCPP_INLINE_VISIBILITY 1314 void __copy_assign_alloc(const __hash_table& __u) 1315 {__copy_assign_alloc(__u, integral_constant<bool, 1316 __node_traits::propagate_on_container_copy_assignment::value>());} 1317 void __copy_assign_alloc(const __hash_table& __u, true_type); 1318 _LIBCPP_INLINE_VISIBILITY 1319 void __copy_assign_alloc(const __hash_table&, false_type) {} 1320 1321#ifndef _LIBCPP_CXX03_LANG 1322 void __move_assign(__hash_table& __u, false_type); 1323 void __move_assign(__hash_table& __u, true_type) 1324 _NOEXCEPT_( 1325 is_nothrow_move_assignable<__node_allocator>::value && 1326 is_nothrow_move_assignable<hasher>::value && 1327 is_nothrow_move_assignable<key_equal>::value); 1328 _LIBCPP_INLINE_VISIBILITY 1329 void __move_assign_alloc(__hash_table& __u) 1330 _NOEXCEPT_( 1331 !__node_traits::propagate_on_container_move_assignment::value || 1332 (is_nothrow_move_assignable<__pointer_allocator>::value && 1333 is_nothrow_move_assignable<__node_allocator>::value)) 1334 {__move_assign_alloc(__u, integral_constant<bool, 1335 __node_traits::propagate_on_container_move_assignment::value>());} 1336 _LIBCPP_INLINE_VISIBILITY 1337 void __move_assign_alloc(__hash_table& __u, true_type) 1338 _NOEXCEPT_( 1339 is_nothrow_move_assignable<__pointer_allocator>::value && 1340 is_nothrow_move_assignable<__node_allocator>::value) 1341 { 1342 __bucket_list_.get_deleter().__alloc() = 1343 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1344 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1345 } 1346 _LIBCPP_INLINE_VISIBILITY 1347 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1348#endif // _LIBCPP_CXX03_LANG 1349 1350 void __deallocate(__node_pointer __np) _NOEXCEPT; 1351 __node_pointer __detach() _NOEXCEPT; 1352 1353 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map; 1354 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap; 1355}; 1356 1357template <class _Tp, class _Hash, class _Equal, class _Alloc> 1358inline 1359__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1360 _NOEXCEPT_( 1361 is_nothrow_default_constructible<__bucket_list>::value && 1362 is_nothrow_default_constructible<__first_node>::value && 1363 is_nothrow_default_constructible<__node_allocator>::value && 1364 is_nothrow_default_constructible<hasher>::value && 1365 is_nothrow_default_constructible<key_equal>::value) 1366 : __p2_(0), 1367 __p3_(1.0f) 1368{ 1369} 1370 1371template <class _Tp, class _Hash, class _Equal, class _Alloc> 1372inline 1373__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1374 const key_equal& __eql) 1375 : __bucket_list_(nullptr, __bucket_list_deleter()), 1376 __p1_(), 1377 __p2_(0, __hf), 1378 __p3_(1.0f, __eql) 1379{ 1380} 1381 1382template <class _Tp, class _Hash, class _Equal, class _Alloc> 1383__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1384 const key_equal& __eql, 1385 const allocator_type& __a) 1386 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1387 __p1_(__node_allocator(__a)), 1388 __p2_(0, __hf), 1389 __p3_(1.0f, __eql) 1390{ 1391} 1392 1393template <class _Tp, class _Hash, class _Equal, class _Alloc> 1394__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1395 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1396 __p1_(__node_allocator(__a)), 1397 __p2_(0), 1398 __p3_(1.0f) 1399{ 1400} 1401 1402template <class _Tp, class _Hash, class _Equal, class _Alloc> 1403__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1404 : __bucket_list_(nullptr, 1405 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1406 select_on_container_copy_construction( 1407 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1408 __p1_(allocator_traits<__node_allocator>:: 1409 select_on_container_copy_construction(__u.__node_alloc())), 1410 __p2_(0, __u.hash_function()), 1411 __p3_(__u.__p3_) 1412{ 1413} 1414 1415template <class _Tp, class _Hash, class _Equal, class _Alloc> 1416__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1417 const allocator_type& __a) 1418 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1419 __p1_(__node_allocator(__a)), 1420 __p2_(0, __u.hash_function()), 1421 __p3_(__u.__p3_) 1422{ 1423} 1424 1425#ifndef _LIBCPP_CXX03_LANG 1426 1427template <class _Tp, class _Hash, class _Equal, class _Alloc> 1428__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1429 _NOEXCEPT_( 1430 is_nothrow_move_constructible<__bucket_list>::value && 1431 is_nothrow_move_constructible<__first_node>::value && 1432 is_nothrow_move_constructible<__node_allocator>::value && 1433 is_nothrow_move_constructible<hasher>::value && 1434 is_nothrow_move_constructible<key_equal>::value) 1435 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1436 __p1_(_VSTD::move(__u.__p1_)), 1437 __p2_(_VSTD::move(__u.__p2_)), 1438 __p3_(_VSTD::move(__u.__p3_)) 1439{ 1440 if (size() > 0) 1441 { 1442 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1443 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1444 __u.__p1_.first().__next_ = nullptr; 1445 __u.size() = 0; 1446 } 1447} 1448 1449template <class _Tp, class _Hash, class _Equal, class _Alloc> 1450__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1451 const allocator_type& __a) 1452 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1453 __p1_(__node_allocator(__a)), 1454 __p2_(0, _VSTD::move(__u.hash_function())), 1455 __p3_(_VSTD::move(__u.__p3_)) 1456{ 1457 if (__a == allocator_type(__u.__node_alloc())) 1458 { 1459 __bucket_list_.reset(__u.__bucket_list_.release()); 1460 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1461 __u.__bucket_list_.get_deleter().size() = 0; 1462 if (__u.size() > 0) 1463 { 1464 __p1_.first().__next_ = __u.__p1_.first().__next_; 1465 __u.__p1_.first().__next_ = nullptr; 1466 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 1467 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 1468 size() = __u.size(); 1469 __u.size() = 0; 1470 } 1471 } 1472} 1473 1474#endif // _LIBCPP_CXX03_LANG 1475 1476template <class _Tp, class _Hash, class _Equal, class _Alloc> 1477__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1478{ 1479 static_assert((is_copy_constructible<key_equal>::value), 1480 "Predicate must be copy-constructible."); 1481 static_assert((is_copy_constructible<hasher>::value), 1482 "Hasher must be copy-constructible."); 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 (__nd->__hash_ == __hash 2206 || __constrain_hash(__nd->__hash_, __bc) == __chash); 2207 __nd = __nd->__next_) 2208 { 2209 if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k)) 2210#if _LIBCPP_DEBUG_LEVEL >= 2 2211 return iterator(__nd, this); 2212#else 2213 return iterator(__nd); 2214#endif 2215 } 2216 } 2217 } 2218 return end(); 2219} 2220 2221template <class _Tp, class _Hash, class _Equal, class _Alloc> 2222template <class _Key> 2223typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2224__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2225{ 2226 size_t __hash = hash_function()(__k); 2227 size_type __bc = bucket_count(); 2228 if (__bc != 0) 2229 { 2230 size_t __chash = __constrain_hash(__hash, __bc); 2231 __node_const_pointer __nd = __bucket_list_[__chash]; 2232 if (__nd != nullptr) 2233 { 2234 for (__nd = __nd->__next_; __nd != nullptr && 2235 (__hash == __nd->__hash_ || __constrain_hash(__nd->__hash_, __bc) == __chash); 2236 __nd = __nd->__next_) 2237 { 2238 if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k)) 2239#if _LIBCPP_DEBUG_LEVEL >= 2 2240 return const_iterator(__nd, this); 2241#else 2242 return const_iterator(__nd); 2243#endif 2244 } 2245 } 2246 2247 } 2248 return end(); 2249} 2250 2251#ifndef _LIBCPP_CXX03_LANG 2252 2253template <class _Tp, class _Hash, class _Equal, class _Alloc> 2254template <class ..._Args> 2255typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2256__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2257{ 2258 static_assert(!__is_hash_value_type<_Args...>::value, 2259 "Construct cannot be called with a hash value type"); 2260 __node_allocator& __na = __node_alloc(); 2261 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2262 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); 2263 __h.get_deleter().__value_constructed = true; 2264 __h->__hash_ = hash_function()(__h->__value_); 2265 __h->__next_ = nullptr; 2266 return __h; 2267} 2268 2269template <class _Tp, class _Hash, class _Equal, class _Alloc> 2270template <class _First, class ..._Rest> 2271typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2272__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash( 2273 size_t __hash, _First&& __f, _Rest&& ...__rest) 2274{ 2275 static_assert(!__is_hash_value_type<_First, _Rest...>::value, 2276 "Construct cannot be called with a hash value type"); 2277 __node_allocator& __na = __node_alloc(); 2278 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2279 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), 2280 _VSTD::forward<_First>(__f), 2281 _VSTD::forward<_Rest>(__rest)...); 2282 __h.get_deleter().__value_constructed = true; 2283 __h->__hash_ = __hash; 2284 __h->__next_ = nullptr; 2285 return __h; 2286} 2287 2288#else // _LIBCPP_CXX03_LANG 2289 2290template <class _Tp, class _Hash, class _Equal, class _Alloc> 2291typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2292__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v) 2293{ 2294 __node_allocator& __na = __node_alloc(); 2295 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2296 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); 2297 __h.get_deleter().__value_constructed = true; 2298 __h->__hash_ = hash_function()(__h->__value_); 2299 __h->__next_ = nullptr; 2300 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2301} 2302 2303template <class _Tp, class _Hash, class _Equal, class _Alloc> 2304typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2305__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, 2306 const __container_value_type& __v) 2307{ 2308 __node_allocator& __na = __node_alloc(); 2309 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2310 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); 2311 __h.get_deleter().__value_constructed = true; 2312 __h->__hash_ = __hash; 2313 __h->__next_ = nullptr; 2314 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2315} 2316 2317#endif // _LIBCPP_CXX03_LANG 2318 2319template <class _Tp, class _Hash, class _Equal, class _Alloc> 2320typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2321__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2322{ 2323 __node_pointer __np = __p.__node_; 2324#if _LIBCPP_DEBUG_LEVEL >= 2 2325 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2326 "unordered container erase(iterator) called with an iterator not" 2327 " referring to this container"); 2328 _LIBCPP_ASSERT(__p != end(), 2329 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2330 iterator __r(__np, this); 2331#else 2332 iterator __r(__np); 2333#endif 2334 ++__r; 2335 remove(__p); 2336 return __r; 2337} 2338 2339template <class _Tp, class _Hash, class _Equal, class _Alloc> 2340typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2341__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2342 const_iterator __last) 2343{ 2344#if _LIBCPP_DEBUG_LEVEL >= 2 2345 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2346 "unodered container::erase(iterator, iterator) called with an iterator not" 2347 " referring to this unodered container"); 2348 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2349 "unodered container::erase(iterator, iterator) called with an iterator not" 2350 " referring to this unodered container"); 2351#endif 2352 for (const_iterator __p = __first; __first != __last; __p = __first) 2353 { 2354 ++__first; 2355 erase(__p); 2356 } 2357 __node_pointer __np = __last.__node_; 2358#if _LIBCPP_DEBUG_LEVEL >= 2 2359 return iterator (__np, this); 2360#else 2361 return iterator (__np); 2362#endif 2363} 2364 2365template <class _Tp, class _Hash, class _Equal, class _Alloc> 2366template <class _Key> 2367typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2368__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2369{ 2370 iterator __i = find(__k); 2371 if (__i == end()) 2372 return 0; 2373 erase(__i); 2374 return 1; 2375} 2376 2377template <class _Tp, class _Hash, class _Equal, class _Alloc> 2378template <class _Key> 2379typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2380__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2381{ 2382 size_type __r = 0; 2383 iterator __i = find(__k); 2384 if (__i != end()) 2385 { 2386 iterator __e = end(); 2387 do 2388 { 2389 erase(__i++); 2390 ++__r; 2391 } while (__i != __e && key_eq()(*__i, __k)); 2392 } 2393 return __r; 2394} 2395 2396template <class _Tp, class _Hash, class _Equal, class _Alloc> 2397typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2398__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2399{ 2400 // current node 2401 __node_pointer __cn = __p.__node_; 2402 size_type __bc = bucket_count(); 2403 size_t __chash = __constrain_hash(__cn->__hash_, __bc); 2404 // find previous node 2405 __node_pointer __pn = __bucket_list_[__chash]; 2406 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2407 ; 2408 // Fix up __bucket_list_ 2409 // if __pn is not in same bucket (before begin is not in same bucket) && 2410 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2411 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())) 2412 || __constrain_hash(__pn->__hash_, __bc) != __chash) 2413 { 2414 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash) 2415 __bucket_list_[__chash] = nullptr; 2416 } 2417 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2418 if (__cn->__next_ != nullptr) 2419 { 2420 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc); 2421 if (__nhash != __chash) 2422 __bucket_list_[__nhash] = __pn; 2423 } 2424 // remove __cn 2425 __pn->__next_ = __cn->__next_; 2426 __cn->__next_ = nullptr; 2427 --size(); 2428#if _LIBCPP_DEBUG_LEVEL >= 2 2429 __c_node* __c = __get_db()->__find_c_and_lock(this); 2430 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 2431 { 2432 --__p; 2433 iterator* __i = static_cast<iterator*>((*__p)->__i_); 2434 if (__i->__node_ == __cn) 2435 { 2436 (*__p)->__c_ = nullptr; 2437 if (--__c->end_ != __p) 2438 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2439 } 2440 } 2441 __get_db()->unlock(); 2442#endif 2443 return __node_holder(__cn, _Dp(__node_alloc(), true)); 2444} 2445 2446template <class _Tp, class _Hash, class _Equal, class _Alloc> 2447template <class _Key> 2448inline 2449typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2450__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2451{ 2452 return static_cast<size_type>(find(__k) != end()); 2453} 2454 2455template <class _Tp, class _Hash, class _Equal, class _Alloc> 2456template <class _Key> 2457typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2458__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2459{ 2460 size_type __r = 0; 2461 const_iterator __i = find(__k); 2462 if (__i != end()) 2463 { 2464 const_iterator __e = end(); 2465 do 2466 { 2467 ++__i; 2468 ++__r; 2469 } while (__i != __e && key_eq()(*__i, __k)); 2470 } 2471 return __r; 2472} 2473 2474template <class _Tp, class _Hash, class _Equal, class _Alloc> 2475template <class _Key> 2476pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2477 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2478__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2479 const _Key& __k) 2480{ 2481 iterator __i = find(__k); 2482 iterator __j = __i; 2483 if (__i != end()) 2484 ++__j; 2485 return pair<iterator, iterator>(__i, __j); 2486} 2487 2488template <class _Tp, class _Hash, class _Equal, class _Alloc> 2489template <class _Key> 2490pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2491 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2492__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2493 const _Key& __k) const 2494{ 2495 const_iterator __i = find(__k); 2496 const_iterator __j = __i; 2497 if (__i != end()) 2498 ++__j; 2499 return pair<const_iterator, const_iterator>(__i, __j); 2500} 2501 2502template <class _Tp, class _Hash, class _Equal, class _Alloc> 2503template <class _Key> 2504pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2505 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2506__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2507 const _Key& __k) 2508{ 2509 iterator __i = find(__k); 2510 iterator __j = __i; 2511 if (__i != end()) 2512 { 2513 iterator __e = end(); 2514 do 2515 { 2516 ++__j; 2517 } while (__j != __e && key_eq()(*__j, __k)); 2518 } 2519 return pair<iterator, iterator>(__i, __j); 2520} 2521 2522template <class _Tp, class _Hash, class _Equal, class _Alloc> 2523template <class _Key> 2524pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2525 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2526__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2527 const _Key& __k) const 2528{ 2529 const_iterator __i = find(__k); 2530 const_iterator __j = __i; 2531 if (__i != end()) 2532 { 2533 const_iterator __e = end(); 2534 do 2535 { 2536 ++__j; 2537 } while (__j != __e && key_eq()(*__j, __k)); 2538 } 2539 return pair<const_iterator, const_iterator>(__i, __j); 2540} 2541 2542template <class _Tp, class _Hash, class _Equal, class _Alloc> 2543void 2544__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2545#if _LIBCPP_STD_VER <= 11 2546 _NOEXCEPT_( 2547 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2548 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2549 || __is_nothrow_swappable<__pointer_allocator>::value) 2550 && (!__node_traits::propagate_on_container_swap::value 2551 || __is_nothrow_swappable<__node_allocator>::value) 2552 ) 2553#else 2554 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2555#endif 2556{ 2557 { 2558 __node_pointer_pointer __npp = __bucket_list_.release(); 2559 __bucket_list_.reset(__u.__bucket_list_.release()); 2560 __u.__bucket_list_.reset(__npp); 2561 } 2562 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2563 __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2564 __u.__bucket_list_.get_deleter().__alloc()); 2565 __swap_allocator(__node_alloc(), __u.__node_alloc()); 2566 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2567 __p2_.swap(__u.__p2_); 2568 __p3_.swap(__u.__p3_); 2569 if (size() > 0) 2570 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] = 2571 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())); 2572 if (__u.size() > 0) 2573 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] = 2574 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first())); 2575#if _LIBCPP_DEBUG_LEVEL >= 2 2576 __get_db()->swap(this, &__u); 2577#endif 2578} 2579 2580template <class _Tp, class _Hash, class _Equal, class _Alloc> 2581typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2582__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2583{ 2584 _LIBCPP_ASSERT(__n < bucket_count(), 2585 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2586 __node_const_pointer __np = __bucket_list_[__n]; 2587 size_type __bc = bucket_count(); 2588 size_type __r = 0; 2589 if (__np != nullptr) 2590 { 2591 for (__np = __np->__next_; __np != nullptr && 2592 __constrain_hash(__np->__hash_, __bc) == __n; 2593 __np = __np->__next_, ++__r) 2594 ; 2595 } 2596 return __r; 2597} 2598 2599template <class _Tp, class _Hash, class _Equal, class _Alloc> 2600inline _LIBCPP_INLINE_VISIBILITY 2601void 2602swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2603 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2604 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2605{ 2606 __x.swap(__y); 2607} 2608 2609#if _LIBCPP_DEBUG_LEVEL >= 2 2610 2611template <class _Tp, class _Hash, class _Equal, class _Alloc> 2612bool 2613__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2614{ 2615 return __i->__node_ != nullptr; 2616} 2617 2618template <class _Tp, class _Hash, class _Equal, class _Alloc> 2619bool 2620__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2621{ 2622 return false; 2623} 2624 2625template <class _Tp, class _Hash, class _Equal, class _Alloc> 2626bool 2627__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2628{ 2629 return false; 2630} 2631 2632template <class _Tp, class _Hash, class _Equal, class _Alloc> 2633bool 2634__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2635{ 2636 return false; 2637} 2638 2639#endif // _LIBCPP_DEBUG_LEVEL >= 2 2640_LIBCPP_END_NAMESPACE_STD 2641 2642#endif // _LIBCPP__HASH_TABLE 2643