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