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