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