__hash_table revision 360784
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, __default_init_tag()) {} 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 828public: 829 bool __value_constructed; 830 831 __hash_node_destructor(__hash_node_destructor const&) = default; 832 __hash_node_destructor& operator=(const __hash_node_destructor&) = delete; 833 834 835 _LIBCPP_INLINE_VISIBILITY 836 explicit __hash_node_destructor(allocator_type& __na, 837 bool __constructed = false) _NOEXCEPT 838 : __na_(__na), 839 __value_constructed(__constructed) 840 {} 841 842 _LIBCPP_INLINE_VISIBILITY 843 void operator()(pointer __p) _NOEXCEPT 844 { 845 if (__value_constructed) 846 __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); 847 if (__p) 848 __alloc_traits::deallocate(__na_, __p, 1); 849 } 850 851 template <class> friend class __hash_map_node_destructor; 852}; 853 854#if _LIBCPP_STD_VER > 14 855template <class _NodeType, class _Alloc> 856struct __generic_container_node_destructor; 857 858template <class _Tp, class _VoidPtr, class _Alloc> 859struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> 860 : __hash_node_destructor<_Alloc> 861{ 862 using __hash_node_destructor<_Alloc>::__hash_node_destructor; 863}; 864#endif 865 866template <class _Key, class _Hash, class _Equal> 867struct __enforce_unordered_container_requirements { 868#ifndef _LIBCPP_CXX03_LANG 869 static_assert(__check_hash_requirements<_Key, _Hash>::value, 870 "the specified hash does not meet the Hash requirements"); 871 static_assert(is_copy_constructible<_Equal>::value, 872 "the specified comparator is required to be copy constructible"); 873#endif 874 typedef int type; 875}; 876 877template <class _Key, class _Hash, class _Equal> 878#ifndef _LIBCPP_CXX03_LANG 879 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value, 880 "the specified comparator type does not provide a viable const call operator") 881 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value, 882 "the specified hash functor does not provide a viable const call operator") 883#endif 884typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type 885__diagnose_unordered_container_requirements(int); 886 887// This dummy overload is used so that the compiler won't emit a spurious 888// "no matching function for call to __diagnose_unordered_xxx" diagnostic 889// when the overload above causes a hard error. 890template <class _Key, class _Hash, class _Equal> 891int __diagnose_unordered_container_requirements(void*); 892 893template <class _Tp, class _Hash, class _Equal, class _Alloc> 894class __hash_table 895{ 896public: 897 typedef _Tp value_type; 898 typedef _Hash hasher; 899 typedef _Equal key_equal; 900 typedef _Alloc allocator_type; 901 902private: 903 typedef allocator_traits<allocator_type> __alloc_traits; 904 typedef typename 905 __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type 906 _NodeTypes; 907public: 908 909 typedef typename _NodeTypes::__node_value_type __node_value_type; 910 typedef typename _NodeTypes::__container_value_type __container_value_type; 911 typedef typename _NodeTypes::key_type key_type; 912 typedef value_type& reference; 913 typedef const value_type& const_reference; 914 typedef typename __alloc_traits::pointer pointer; 915 typedef typename __alloc_traits::const_pointer const_pointer; 916#ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE 917 typedef typename __alloc_traits::size_type size_type; 918#else 919 typedef typename _NodeTypes::size_type size_type; 920#endif 921 typedef typename _NodeTypes::difference_type difference_type; 922public: 923 // Create __node 924 925 typedef typename _NodeTypes::__node_type __node; 926 typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; 927 typedef allocator_traits<__node_allocator> __node_traits; 928 typedef typename _NodeTypes::__void_pointer __void_pointer; 929 typedef typename _NodeTypes::__node_pointer __node_pointer; 930 typedef typename _NodeTypes::__node_pointer __node_const_pointer; 931 typedef typename _NodeTypes::__node_base_type __first_node; 932 typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; 933 typedef typename _NodeTypes::__next_pointer __next_pointer; 934 935private: 936 // check for sane allocator pointer rebinding semantics. Rebinding the 937 // allocator for a new pointer type should be exactly the same as rebinding 938 // the pointer using 'pointer_traits'. 939 static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), 940 "Allocator does not rebind pointers in a sane manner."); 941 typedef typename __rebind_alloc_helper<__node_traits, __first_node>::type 942 __node_base_allocator; 943 typedef allocator_traits<__node_base_allocator> __node_base_traits; 944 static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), 945 "Allocator does not rebind pointers in a sane manner."); 946 947private: 948 949 typedef typename __rebind_alloc_helper<__node_traits, __next_pointer>::type __pointer_allocator; 950 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter; 951 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list; 952 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits; 953 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer; 954 955 // --- Member data begin --- 956 __bucket_list __bucket_list_; 957 __compressed_pair<__first_node, __node_allocator> __p1_; 958 __compressed_pair<size_type, hasher> __p2_; 959 __compressed_pair<float, key_equal> __p3_; 960 // --- Member data end --- 961 962 _LIBCPP_INLINE_VISIBILITY 963 size_type& size() _NOEXCEPT {return __p2_.first();} 964public: 965 _LIBCPP_INLINE_VISIBILITY 966 size_type size() const _NOEXCEPT {return __p2_.first();} 967 968 _LIBCPP_INLINE_VISIBILITY 969 hasher& hash_function() _NOEXCEPT {return __p2_.second();} 970 _LIBCPP_INLINE_VISIBILITY 971 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();} 972 973 _LIBCPP_INLINE_VISIBILITY 974 float& max_load_factor() _NOEXCEPT {return __p3_.first();} 975 _LIBCPP_INLINE_VISIBILITY 976 float max_load_factor() const _NOEXCEPT {return __p3_.first();} 977 978 _LIBCPP_INLINE_VISIBILITY 979 key_equal& key_eq() _NOEXCEPT {return __p3_.second();} 980 _LIBCPP_INLINE_VISIBILITY 981 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();} 982 983 _LIBCPP_INLINE_VISIBILITY 984 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();} 985 _LIBCPP_INLINE_VISIBILITY 986 const __node_allocator& __node_alloc() const _NOEXCEPT 987 {return __p1_.second();} 988 989public: 990 typedef __hash_iterator<__node_pointer> iterator; 991 typedef __hash_const_iterator<__node_pointer> const_iterator; 992 typedef __hash_local_iterator<__node_pointer> local_iterator; 993 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator; 994 995 _LIBCPP_INLINE_VISIBILITY 996 __hash_table() 997 _NOEXCEPT_( 998 is_nothrow_default_constructible<__bucket_list>::value && 999 is_nothrow_default_constructible<__first_node>::value && 1000 is_nothrow_default_constructible<__node_allocator>::value && 1001 is_nothrow_default_constructible<hasher>::value && 1002 is_nothrow_default_constructible<key_equal>::value); 1003 _LIBCPP_INLINE_VISIBILITY 1004 __hash_table(const hasher& __hf, const key_equal& __eql); 1005 __hash_table(const hasher& __hf, const key_equal& __eql, 1006 const allocator_type& __a); 1007 explicit __hash_table(const allocator_type& __a); 1008 __hash_table(const __hash_table& __u); 1009 __hash_table(const __hash_table& __u, const allocator_type& __a); 1010#ifndef _LIBCPP_CXX03_LANG 1011 __hash_table(__hash_table&& __u) 1012 _NOEXCEPT_( 1013 is_nothrow_move_constructible<__bucket_list>::value && 1014 is_nothrow_move_constructible<__first_node>::value && 1015 is_nothrow_move_constructible<__node_allocator>::value && 1016 is_nothrow_move_constructible<hasher>::value && 1017 is_nothrow_move_constructible<key_equal>::value); 1018 __hash_table(__hash_table&& __u, const allocator_type& __a); 1019#endif // _LIBCPP_CXX03_LANG 1020 ~__hash_table(); 1021 1022 __hash_table& operator=(const __hash_table& __u); 1023#ifndef _LIBCPP_CXX03_LANG 1024 _LIBCPP_INLINE_VISIBILITY 1025 __hash_table& operator=(__hash_table&& __u) 1026 _NOEXCEPT_( 1027 __node_traits::propagate_on_container_move_assignment::value && 1028 is_nothrow_move_assignable<__node_allocator>::value && 1029 is_nothrow_move_assignable<hasher>::value && 1030 is_nothrow_move_assignable<key_equal>::value); 1031#endif 1032 template <class _InputIterator> 1033 void __assign_unique(_InputIterator __first, _InputIterator __last); 1034 template <class _InputIterator> 1035 void __assign_multi(_InputIterator __first, _InputIterator __last); 1036 1037 _LIBCPP_INLINE_VISIBILITY 1038 size_type max_size() const _NOEXCEPT 1039 { 1040 return std::min<size_type>( 1041 __node_traits::max_size(__node_alloc()), 1042 numeric_limits<difference_type >::max() 1043 ); 1044 } 1045 1046private: 1047 _LIBCPP_INLINE_VISIBILITY 1048 __next_pointer __node_insert_multi_prepare(size_t __cp_hash, 1049 value_type& __cp_val); 1050 _LIBCPP_INLINE_VISIBILITY 1051 void __node_insert_multi_perform(__node_pointer __cp, 1052 __next_pointer __pn) _NOEXCEPT; 1053 1054 _LIBCPP_INLINE_VISIBILITY 1055 __next_pointer __node_insert_unique_prepare(size_t __nd_hash, 1056 value_type& __nd_val); 1057 _LIBCPP_INLINE_VISIBILITY 1058 void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT; 1059 1060public: 1061 _LIBCPP_INLINE_VISIBILITY 1062 pair<iterator, bool> __node_insert_unique(__node_pointer __nd); 1063 _LIBCPP_INLINE_VISIBILITY 1064 iterator __node_insert_multi(__node_pointer __nd); 1065 _LIBCPP_INLINE_VISIBILITY 1066 iterator __node_insert_multi(const_iterator __p, 1067 __node_pointer __nd); 1068 1069#ifndef _LIBCPP_CXX03_LANG 1070 template <class _Key, class ..._Args> 1071 _LIBCPP_INLINE_VISIBILITY 1072 pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args); 1073 1074 template <class... _Args> 1075 _LIBCPP_INLINE_VISIBILITY 1076 pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); 1077 1078 template <class _Pp> 1079 _LIBCPP_INLINE_VISIBILITY 1080 pair<iterator, bool> __emplace_unique(_Pp&& __x) { 1081 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), 1082 __can_extract_key<_Pp, key_type>()); 1083 } 1084 1085 template <class _First, class _Second> 1086 _LIBCPP_INLINE_VISIBILITY 1087 typename enable_if< 1088 __can_extract_map_key<_First, key_type, __container_value_type>::value, 1089 pair<iterator, bool> 1090 >::type __emplace_unique(_First&& __f, _Second&& __s) { 1091 return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), 1092 _VSTD::forward<_Second>(__s)); 1093 } 1094 1095 template <class... _Args> 1096 _LIBCPP_INLINE_VISIBILITY 1097 pair<iterator, bool> __emplace_unique(_Args&&... __args) { 1098 return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); 1099 } 1100 1101 template <class _Pp> 1102 _LIBCPP_INLINE_VISIBILITY 1103 pair<iterator, bool> 1104 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { 1105 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); 1106 } 1107 template <class _Pp> 1108 _LIBCPP_INLINE_VISIBILITY 1109 pair<iterator, bool> 1110 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { 1111 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); 1112 } 1113 template <class _Pp> 1114 _LIBCPP_INLINE_VISIBILITY 1115 pair<iterator, bool> 1116 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { 1117 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); 1118 } 1119 1120 template <class... _Args> 1121 _LIBCPP_INLINE_VISIBILITY 1122 iterator __emplace_multi(_Args&&... __args); 1123 template <class... _Args> 1124 _LIBCPP_INLINE_VISIBILITY 1125 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); 1126 1127 1128 _LIBCPP_INLINE_VISIBILITY 1129 pair<iterator, bool> 1130 __insert_unique(__container_value_type&& __x) { 1131 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), _VSTD::move(__x)); 1132 } 1133 1134 template <class _Pp, class = typename enable_if< 1135 !__is_same_uncvref<_Pp, __container_value_type>::value 1136 >::type> 1137 _LIBCPP_INLINE_VISIBILITY 1138 pair<iterator, bool> __insert_unique(_Pp&& __x) { 1139 return __emplace_unique(_VSTD::forward<_Pp>(__x)); 1140 } 1141 1142 template <class _Pp> 1143 _LIBCPP_INLINE_VISIBILITY 1144 iterator __insert_multi(_Pp&& __x) { 1145 return __emplace_multi(_VSTD::forward<_Pp>(__x)); 1146 } 1147 1148 template <class _Pp> 1149 _LIBCPP_INLINE_VISIBILITY 1150 iterator __insert_multi(const_iterator __p, _Pp&& __x) { 1151 return __emplace_hint_multi(__p, _VSTD::forward<_Pp>(__x)); 1152 } 1153 1154#else // !defined(_LIBCPP_CXX03_LANG) 1155 template <class _Key, class _Args> 1156 _LIBCPP_INLINE_VISIBILITY 1157 pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args); 1158 1159 iterator __insert_multi(const __container_value_type& __x); 1160 iterator __insert_multi(const_iterator __p, const __container_value_type& __x); 1161#endif 1162 1163 _LIBCPP_INLINE_VISIBILITY 1164 pair<iterator, bool> __insert_unique(const __container_value_type& __x) { 1165 return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x); 1166 } 1167 1168#if _LIBCPP_STD_VER > 14 1169 template <class _NodeHandle, class _InsertReturnType> 1170 _LIBCPP_INLINE_VISIBILITY 1171 _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh); 1172 template <class _NodeHandle> 1173 _LIBCPP_INLINE_VISIBILITY 1174 iterator __node_handle_insert_unique(const_iterator __hint, 1175 _NodeHandle&& __nh); 1176 template <class _Table> 1177 _LIBCPP_INLINE_VISIBILITY 1178 void __node_handle_merge_unique(_Table& __source); 1179 1180 template <class _NodeHandle> 1181 _LIBCPP_INLINE_VISIBILITY 1182 iterator __node_handle_insert_multi(_NodeHandle&& __nh); 1183 template <class _NodeHandle> 1184 _LIBCPP_INLINE_VISIBILITY 1185 iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh); 1186 template <class _Table> 1187 _LIBCPP_INLINE_VISIBILITY 1188 void __node_handle_merge_multi(_Table& __source); 1189 1190 template <class _NodeHandle> 1191 _LIBCPP_INLINE_VISIBILITY 1192 _NodeHandle __node_handle_extract(key_type const& __key); 1193 template <class _NodeHandle> 1194 _LIBCPP_INLINE_VISIBILITY 1195 _NodeHandle __node_handle_extract(const_iterator __it); 1196#endif 1197 1198 void clear() _NOEXCEPT; 1199 void rehash(size_type __n); 1200 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n) 1201 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));} 1202 1203 _LIBCPP_INLINE_VISIBILITY 1204 size_type bucket_count() const _NOEXCEPT 1205 { 1206 return __bucket_list_.get_deleter().size(); 1207 } 1208 1209 _LIBCPP_INLINE_VISIBILITY 1210 iterator begin() _NOEXCEPT; 1211 _LIBCPP_INLINE_VISIBILITY 1212 iterator end() _NOEXCEPT; 1213 _LIBCPP_INLINE_VISIBILITY 1214 const_iterator begin() const _NOEXCEPT; 1215 _LIBCPP_INLINE_VISIBILITY 1216 const_iterator end() const _NOEXCEPT; 1217 1218 template <class _Key> 1219 _LIBCPP_INLINE_VISIBILITY 1220 size_type bucket(const _Key& __k) const 1221 { 1222 _LIBCPP_ASSERT(bucket_count() > 0, 1223 "unordered container::bucket(key) called when bucket_count() == 0"); 1224 return __constrain_hash(hash_function()(__k), bucket_count()); 1225 } 1226 1227 template <class _Key> 1228 iterator find(const _Key& __x); 1229 template <class _Key> 1230 const_iterator find(const _Key& __x) const; 1231 1232 typedef __hash_node_destructor<__node_allocator> _Dp; 1233 typedef unique_ptr<__node, _Dp> __node_holder; 1234 1235 iterator erase(const_iterator __p); 1236 iterator erase(const_iterator __first, const_iterator __last); 1237 template <class _Key> 1238 size_type __erase_unique(const _Key& __k); 1239 template <class _Key> 1240 size_type __erase_multi(const _Key& __k); 1241 __node_holder remove(const_iterator __p) _NOEXCEPT; 1242 1243 template <class _Key> 1244 _LIBCPP_INLINE_VISIBILITY 1245 size_type __count_unique(const _Key& __k) const; 1246 template <class _Key> 1247 size_type __count_multi(const _Key& __k) const; 1248 1249 template <class _Key> 1250 pair<iterator, iterator> 1251 __equal_range_unique(const _Key& __k); 1252 template <class _Key> 1253 pair<const_iterator, const_iterator> 1254 __equal_range_unique(const _Key& __k) const; 1255 1256 template <class _Key> 1257 pair<iterator, iterator> 1258 __equal_range_multi(const _Key& __k); 1259 template <class _Key> 1260 pair<const_iterator, const_iterator> 1261 __equal_range_multi(const _Key& __k) const; 1262 1263 void swap(__hash_table& __u) 1264#if _LIBCPP_STD_VER <= 11 1265 _NOEXCEPT_( 1266 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 1267 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 1268 || __is_nothrow_swappable<__pointer_allocator>::value) 1269 && (!__node_traits::propagate_on_container_swap::value 1270 || __is_nothrow_swappable<__node_allocator>::value) 1271 ); 1272#else 1273 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value); 1274#endif 1275 1276 _LIBCPP_INLINE_VISIBILITY 1277 size_type max_bucket_count() const _NOEXCEPT 1278 {return max_size(); } 1279 size_type bucket_size(size_type __n) const; 1280 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT 1281 { 1282 size_type __bc = bucket_count(); 1283 return __bc != 0 ? (float)size() / __bc : 0.f; 1284 } 1285 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT 1286 { 1287 _LIBCPP_ASSERT(__mlf > 0, 1288 "unordered container::max_load_factor(lf) called with lf <= 0"); 1289 max_load_factor() = _VSTD::max(__mlf, load_factor()); 1290 } 1291 1292 _LIBCPP_INLINE_VISIBILITY 1293 local_iterator 1294 begin(size_type __n) 1295 { 1296 _LIBCPP_ASSERT(__n < bucket_count(), 1297 "unordered container::begin(n) called with n >= bucket_count()"); 1298#if _LIBCPP_DEBUG_LEVEL >= 2 1299 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1300#else 1301 return local_iterator(__bucket_list_[__n], __n, bucket_count()); 1302#endif 1303 } 1304 1305 _LIBCPP_INLINE_VISIBILITY 1306 local_iterator 1307 end(size_type __n) 1308 { 1309 _LIBCPP_ASSERT(__n < bucket_count(), 1310 "unordered container::end(n) called with n >= bucket_count()"); 1311#if _LIBCPP_DEBUG_LEVEL >= 2 1312 return local_iterator(nullptr, __n, bucket_count(), this); 1313#else 1314 return local_iterator(nullptr, __n, bucket_count()); 1315#endif 1316 } 1317 1318 _LIBCPP_INLINE_VISIBILITY 1319 const_local_iterator 1320 cbegin(size_type __n) const 1321 { 1322 _LIBCPP_ASSERT(__n < bucket_count(), 1323 "unordered container::cbegin(n) called with n >= bucket_count()"); 1324#if _LIBCPP_DEBUG_LEVEL >= 2 1325 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this); 1326#else 1327 return const_local_iterator(__bucket_list_[__n], __n, bucket_count()); 1328#endif 1329 } 1330 1331 _LIBCPP_INLINE_VISIBILITY 1332 const_local_iterator 1333 cend(size_type __n) const 1334 { 1335 _LIBCPP_ASSERT(__n < bucket_count(), 1336 "unordered container::cend(n) called with n >= bucket_count()"); 1337#if _LIBCPP_DEBUG_LEVEL >= 2 1338 return const_local_iterator(nullptr, __n, bucket_count(), this); 1339#else 1340 return const_local_iterator(nullptr, __n, bucket_count()); 1341#endif 1342 } 1343 1344#if _LIBCPP_DEBUG_LEVEL >= 2 1345 1346 bool __dereferenceable(const const_iterator* __i) const; 1347 bool __decrementable(const const_iterator* __i) const; 1348 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 1349 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 1350 1351#endif // _LIBCPP_DEBUG_LEVEL >= 2 1352 1353private: 1354 void __rehash(size_type __n); 1355 1356#ifndef _LIBCPP_CXX03_LANG 1357 template <class ..._Args> 1358 __node_holder __construct_node(_Args&& ...__args); 1359 1360 template <class _First, class ..._Rest> 1361 __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest); 1362#else // _LIBCPP_CXX03_LANG 1363 __node_holder __construct_node(const __container_value_type& __v); 1364 __node_holder __construct_node_hash(size_t __hash, const __container_value_type& __v); 1365#endif 1366 1367 1368 _LIBCPP_INLINE_VISIBILITY 1369 void __copy_assign_alloc(const __hash_table& __u) 1370 {__copy_assign_alloc(__u, integral_constant<bool, 1371 __node_traits::propagate_on_container_copy_assignment::value>());} 1372 void __copy_assign_alloc(const __hash_table& __u, true_type); 1373 _LIBCPP_INLINE_VISIBILITY 1374 void __copy_assign_alloc(const __hash_table&, false_type) {} 1375 1376#ifndef _LIBCPP_CXX03_LANG 1377 void __move_assign(__hash_table& __u, false_type); 1378 void __move_assign(__hash_table& __u, true_type) 1379 _NOEXCEPT_( 1380 is_nothrow_move_assignable<__node_allocator>::value && 1381 is_nothrow_move_assignable<hasher>::value && 1382 is_nothrow_move_assignable<key_equal>::value); 1383 _LIBCPP_INLINE_VISIBILITY 1384 void __move_assign_alloc(__hash_table& __u) 1385 _NOEXCEPT_( 1386 !__node_traits::propagate_on_container_move_assignment::value || 1387 (is_nothrow_move_assignable<__pointer_allocator>::value && 1388 is_nothrow_move_assignable<__node_allocator>::value)) 1389 {__move_assign_alloc(__u, integral_constant<bool, 1390 __node_traits::propagate_on_container_move_assignment::value>());} 1391 _LIBCPP_INLINE_VISIBILITY 1392 void __move_assign_alloc(__hash_table& __u, true_type) 1393 _NOEXCEPT_( 1394 is_nothrow_move_assignable<__pointer_allocator>::value && 1395 is_nothrow_move_assignable<__node_allocator>::value) 1396 { 1397 __bucket_list_.get_deleter().__alloc() = 1398 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc()); 1399 __node_alloc() = _VSTD::move(__u.__node_alloc()); 1400 } 1401 _LIBCPP_INLINE_VISIBILITY 1402 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {} 1403#endif // _LIBCPP_CXX03_LANG 1404 1405 void __deallocate_node(__next_pointer __np) _NOEXCEPT; 1406 __next_pointer __detach() _NOEXCEPT; 1407 1408 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map; 1409 template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; 1410}; 1411 1412template <class _Tp, class _Hash, class _Equal, class _Alloc> 1413inline 1414__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() 1415 _NOEXCEPT_( 1416 is_nothrow_default_constructible<__bucket_list>::value && 1417 is_nothrow_default_constructible<__first_node>::value && 1418 is_nothrow_default_constructible<__node_allocator>::value && 1419 is_nothrow_default_constructible<hasher>::value && 1420 is_nothrow_default_constructible<key_equal>::value) 1421 : __p2_(0, __default_init_tag()), 1422 __p3_(1.0f, __default_init_tag()) 1423{ 1424} 1425 1426template <class _Tp, class _Hash, class _Equal, class _Alloc> 1427inline 1428__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1429 const key_equal& __eql) 1430 : __bucket_list_(nullptr, __bucket_list_deleter()), 1431 __p1_(), 1432 __p2_(0, __hf), 1433 __p3_(1.0f, __eql) 1434{ 1435} 1436 1437template <class _Tp, class _Hash, class _Equal, class _Alloc> 1438__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, 1439 const key_equal& __eql, 1440 const allocator_type& __a) 1441 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1442 __p1_(__default_init_tag(), __node_allocator(__a)), 1443 __p2_(0, __hf), 1444 __p3_(1.0f, __eql) 1445{ 1446} 1447 1448template <class _Tp, class _Hash, class _Equal, class _Alloc> 1449__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a) 1450 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1451 __p1_(__default_init_tag(), __node_allocator(__a)), 1452 __p2_(0, __default_init_tag()), 1453 __p3_(1.0f, __default_init_tag()) 1454{ 1455} 1456 1457template <class _Tp, class _Hash, class _Equal, class _Alloc> 1458__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u) 1459 : __bucket_list_(nullptr, 1460 __bucket_list_deleter(allocator_traits<__pointer_allocator>:: 1461 select_on_container_copy_construction( 1462 __u.__bucket_list_.get_deleter().__alloc()), 0)), 1463 __p1_(__default_init_tag(), allocator_traits<__node_allocator>:: 1464 select_on_container_copy_construction(__u.__node_alloc())), 1465 __p2_(0, __u.hash_function()), 1466 __p3_(__u.__p3_) 1467{ 1468} 1469 1470template <class _Tp, class _Hash, class _Equal, class _Alloc> 1471__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 1472 const allocator_type& __a) 1473 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1474 __p1_(__default_init_tag(), __node_allocator(__a)), 1475 __p2_(0, __u.hash_function()), 1476 __p3_(__u.__p3_) 1477{ 1478} 1479 1480#ifndef _LIBCPP_CXX03_LANG 1481 1482template <class _Tp, class _Hash, class _Equal, class _Alloc> 1483__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) 1484 _NOEXCEPT_( 1485 is_nothrow_move_constructible<__bucket_list>::value && 1486 is_nothrow_move_constructible<__first_node>::value && 1487 is_nothrow_move_constructible<__node_allocator>::value && 1488 is_nothrow_move_constructible<hasher>::value && 1489 is_nothrow_move_constructible<key_equal>::value) 1490 : __bucket_list_(_VSTD::move(__u.__bucket_list_)), 1491 __p1_(_VSTD::move(__u.__p1_)), 1492 __p2_(_VSTD::move(__u.__p2_)), 1493 __p3_(_VSTD::move(__u.__p3_)) 1494{ 1495 if (size() > 0) 1496 { 1497 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 1498 __p1_.first().__ptr(); 1499 __u.__p1_.first().__next_ = nullptr; 1500 __u.size() = 0; 1501 } 1502} 1503 1504template <class _Tp, class _Hash, class _Equal, class _Alloc> 1505__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, 1506 const allocator_type& __a) 1507 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)), 1508 __p1_(__default_init_tag(), __node_allocator(__a)), 1509 __p2_(0, _VSTD::move(__u.hash_function())), 1510 __p3_(_VSTD::move(__u.__p3_)) 1511{ 1512 if (__a == allocator_type(__u.__node_alloc())) 1513 { 1514 __bucket_list_.reset(__u.__bucket_list_.release()); 1515 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1516 __u.__bucket_list_.get_deleter().size() = 0; 1517 if (__u.size() > 0) 1518 { 1519 __p1_.first().__next_ = __u.__p1_.first().__next_; 1520 __u.__p1_.first().__next_ = nullptr; 1521 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 1522 __p1_.first().__ptr(); 1523 size() = __u.size(); 1524 __u.size() = 0; 1525 } 1526 } 1527} 1528 1529#endif // _LIBCPP_CXX03_LANG 1530 1531template <class _Tp, class _Hash, class _Equal, class _Alloc> 1532__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() 1533{ 1534#if defined(_LIBCPP_CXX03_LANG) 1535 static_assert((is_copy_constructible<key_equal>::value), 1536 "Predicate must be copy-constructible."); 1537 static_assert((is_copy_constructible<hasher>::value), 1538 "Hasher must be copy-constructible."); 1539#endif 1540 1541 __deallocate_node(__p1_.first().__next_); 1542#if _LIBCPP_DEBUG_LEVEL >= 2 1543 __get_db()->__erase_c(this); 1544#endif 1545} 1546 1547template <class _Tp, class _Hash, class _Equal, class _Alloc> 1548void 1549__hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc( 1550 const __hash_table& __u, true_type) 1551{ 1552 if (__node_alloc() != __u.__node_alloc()) 1553 { 1554 clear(); 1555 __bucket_list_.reset(); 1556 __bucket_list_.get_deleter().size() = 0; 1557 } 1558 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc(); 1559 __node_alloc() = __u.__node_alloc(); 1560} 1561 1562template <class _Tp, class _Hash, class _Equal, class _Alloc> 1563__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1564__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) 1565{ 1566 if (this != &__u) 1567 { 1568 __copy_assign_alloc(__u); 1569 hash_function() = __u.hash_function(); 1570 key_eq() = __u.key_eq(); 1571 max_load_factor() = __u.max_load_factor(); 1572 __assign_multi(__u.begin(), __u.end()); 1573 } 1574 return *this; 1575} 1576 1577template <class _Tp, class _Hash, class _Equal, class _Alloc> 1578void 1579__hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) 1580 _NOEXCEPT 1581{ 1582 __node_allocator& __na = __node_alloc(); 1583 while (__np != nullptr) 1584 { 1585 __next_pointer __next = __np->__next_; 1586#if _LIBCPP_DEBUG_LEVEL >= 2 1587 __c_node* __c = __get_db()->__find_c_and_lock(this); 1588 for (__i_node** __p = __c->end_; __p != __c->beg_; ) 1589 { 1590 --__p; 1591 iterator* __i = static_cast<iterator*>((*__p)->__i_); 1592 if (__i->__node_ == __np) 1593 { 1594 (*__p)->__c_ = nullptr; 1595 if (--__c->end_ != __p) 1596 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 1597 } 1598 } 1599 __get_db()->unlock(); 1600#endif 1601 __node_pointer __real_np = __np->__upcast(); 1602 __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__value_)); 1603 __node_traits::deallocate(__na, __real_np, 1); 1604 __np = __next; 1605 } 1606} 1607 1608template <class _Tp, class _Hash, class _Equal, class _Alloc> 1609typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer 1610__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT 1611{ 1612 size_type __bc = bucket_count(); 1613 for (size_type __i = 0; __i < __bc; ++__i) 1614 __bucket_list_[__i] = nullptr; 1615 size() = 0; 1616 __next_pointer __cache = __p1_.first().__next_; 1617 __p1_.first().__next_ = nullptr; 1618 return __cache; 1619} 1620 1621#ifndef _LIBCPP_CXX03_LANG 1622 1623template <class _Tp, class _Hash, class _Equal, class _Alloc> 1624void 1625__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1626 __hash_table& __u, true_type) 1627 _NOEXCEPT_( 1628 is_nothrow_move_assignable<__node_allocator>::value && 1629 is_nothrow_move_assignable<hasher>::value && 1630 is_nothrow_move_assignable<key_equal>::value) 1631{ 1632 clear(); 1633 __bucket_list_.reset(__u.__bucket_list_.release()); 1634 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size(); 1635 __u.__bucket_list_.get_deleter().size() = 0; 1636 __move_assign_alloc(__u); 1637 size() = __u.size(); 1638 hash_function() = _VSTD::move(__u.hash_function()); 1639 max_load_factor() = __u.max_load_factor(); 1640 key_eq() = _VSTD::move(__u.key_eq()); 1641 __p1_.first().__next_ = __u.__p1_.first().__next_; 1642 if (size() > 0) 1643 { 1644 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 1645 __p1_.first().__ptr(); 1646 __u.__p1_.first().__next_ = nullptr; 1647 __u.size() = 0; 1648 } 1649#if _LIBCPP_DEBUG_LEVEL >= 2 1650 __get_db()->swap(this, &__u); 1651#endif 1652} 1653 1654template <class _Tp, class _Hash, class _Equal, class _Alloc> 1655void 1656__hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign( 1657 __hash_table& __u, false_type) 1658{ 1659 if (__node_alloc() == __u.__node_alloc()) 1660 __move_assign(__u, true_type()); 1661 else 1662 { 1663 hash_function() = _VSTD::move(__u.hash_function()); 1664 key_eq() = _VSTD::move(__u.key_eq()); 1665 max_load_factor() = __u.max_load_factor(); 1666 if (bucket_count() != 0) 1667 { 1668 __next_pointer __cache = __detach(); 1669#ifndef _LIBCPP_NO_EXCEPTIONS 1670 try 1671 { 1672#endif // _LIBCPP_NO_EXCEPTIONS 1673 const_iterator __i = __u.begin(); 1674 while (__cache != nullptr && __u.size() != 0) 1675 { 1676 __cache->__upcast()->__value_ = 1677 _VSTD::move(__u.remove(__i++)->__value_); 1678 __next_pointer __next = __cache->__next_; 1679 __node_insert_multi(__cache->__upcast()); 1680 __cache = __next; 1681 } 1682#ifndef _LIBCPP_NO_EXCEPTIONS 1683 } 1684 catch (...) 1685 { 1686 __deallocate_node(__cache); 1687 throw; 1688 } 1689#endif // _LIBCPP_NO_EXCEPTIONS 1690 __deallocate_node(__cache); 1691 } 1692 const_iterator __i = __u.begin(); 1693 while (__u.size() != 0) 1694 { 1695 __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__value_)); 1696 __node_insert_multi(__h.get()); 1697 __h.release(); 1698 } 1699 } 1700} 1701 1702template <class _Tp, class _Hash, class _Equal, class _Alloc> 1703inline 1704__hash_table<_Tp, _Hash, _Equal, _Alloc>& 1705__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) 1706 _NOEXCEPT_( 1707 __node_traits::propagate_on_container_move_assignment::value && 1708 is_nothrow_move_assignable<__node_allocator>::value && 1709 is_nothrow_move_assignable<hasher>::value && 1710 is_nothrow_move_assignable<key_equal>::value) 1711{ 1712 __move_assign(__u, integral_constant<bool, 1713 __node_traits::propagate_on_container_move_assignment::value>()); 1714 return *this; 1715} 1716 1717#endif // _LIBCPP_CXX03_LANG 1718 1719template <class _Tp, class _Hash, class _Equal, class _Alloc> 1720template <class _InputIterator> 1721void 1722__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, 1723 _InputIterator __last) 1724{ 1725 typedef iterator_traits<_InputIterator> _ITraits; 1726 typedef typename _ITraits::value_type _ItValueType; 1727 static_assert((is_same<_ItValueType, __container_value_type>::value), 1728 "__assign_unique may only be called with the containers value type"); 1729 1730 if (bucket_count() != 0) 1731 { 1732 __next_pointer __cache = __detach(); 1733#ifndef _LIBCPP_NO_EXCEPTIONS 1734 try 1735 { 1736#endif // _LIBCPP_NO_EXCEPTIONS 1737 for (; __cache != nullptr && __first != __last; ++__first) 1738 { 1739 __cache->__upcast()->__value_ = *__first; 1740 __next_pointer __next = __cache->__next_; 1741 __node_insert_unique(__cache->__upcast()); 1742 __cache = __next; 1743 } 1744#ifndef _LIBCPP_NO_EXCEPTIONS 1745 } 1746 catch (...) 1747 { 1748 __deallocate_node(__cache); 1749 throw; 1750 } 1751#endif // _LIBCPP_NO_EXCEPTIONS 1752 __deallocate_node(__cache); 1753 } 1754 for (; __first != __last; ++__first) 1755 __insert_unique(*__first); 1756} 1757 1758template <class _Tp, class _Hash, class _Equal, class _Alloc> 1759template <class _InputIterator> 1760void 1761__hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, 1762 _InputIterator __last) 1763{ 1764 typedef iterator_traits<_InputIterator> _ITraits; 1765 typedef typename _ITraits::value_type _ItValueType; 1766 static_assert((is_same<_ItValueType, __container_value_type>::value || 1767 is_same<_ItValueType, __node_value_type>::value), 1768 "__assign_multi may only be called with the containers value type" 1769 " or the nodes value type"); 1770 if (bucket_count() != 0) 1771 { 1772 __next_pointer __cache = __detach(); 1773#ifndef _LIBCPP_NO_EXCEPTIONS 1774 try 1775 { 1776#endif // _LIBCPP_NO_EXCEPTIONS 1777 for (; __cache != nullptr && __first != __last; ++__first) 1778 { 1779 __cache->__upcast()->__value_ = *__first; 1780 __next_pointer __next = __cache->__next_; 1781 __node_insert_multi(__cache->__upcast()); 1782 __cache = __next; 1783 } 1784#ifndef _LIBCPP_NO_EXCEPTIONS 1785 } 1786 catch (...) 1787 { 1788 __deallocate_node(__cache); 1789 throw; 1790 } 1791#endif // _LIBCPP_NO_EXCEPTIONS 1792 __deallocate_node(__cache); 1793 } 1794 for (; __first != __last; ++__first) 1795 __insert_multi(_NodeTypes::__get_value(*__first)); 1796} 1797 1798template <class _Tp, class _Hash, class _Equal, class _Alloc> 1799inline 1800typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1801__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT 1802{ 1803#if _LIBCPP_DEBUG_LEVEL >= 2 1804 return iterator(__p1_.first().__next_, this); 1805#else 1806 return iterator(__p1_.first().__next_); 1807#endif 1808} 1809 1810template <class _Tp, class _Hash, class _Equal, class _Alloc> 1811inline 1812typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 1813__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT 1814{ 1815#if _LIBCPP_DEBUG_LEVEL >= 2 1816 return iterator(nullptr, this); 1817#else 1818 return iterator(nullptr); 1819#endif 1820} 1821 1822template <class _Tp, class _Hash, class _Equal, class _Alloc> 1823inline 1824typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1825__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT 1826{ 1827#if _LIBCPP_DEBUG_LEVEL >= 2 1828 return const_iterator(__p1_.first().__next_, this); 1829#else 1830 return const_iterator(__p1_.first().__next_); 1831#endif 1832} 1833 1834template <class _Tp, class _Hash, class _Equal, class _Alloc> 1835inline 1836typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 1837__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT 1838{ 1839#if _LIBCPP_DEBUG_LEVEL >= 2 1840 return const_iterator(nullptr, this); 1841#else 1842 return const_iterator(nullptr); 1843#endif 1844} 1845 1846template <class _Tp, class _Hash, class _Equal, class _Alloc> 1847void 1848__hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT 1849{ 1850 if (size() > 0) 1851 { 1852 __deallocate_node(__p1_.first().__next_); 1853 __p1_.first().__next_ = nullptr; 1854 size_type __bc = bucket_count(); 1855 for (size_type __i = 0; __i < __bc; ++__i) 1856 __bucket_list_[__i] = nullptr; 1857 size() = 0; 1858 } 1859} 1860 1861 1862// Prepare the container for an insertion of the value __value with the hash 1863// __hash. This does a lookup into the container to see if __value is already 1864// present, and performs a rehash if necessary. Returns a pointer to the 1865// existing element if it exists, otherwise nullptr. 1866// 1867// Note that this function does forward exceptions if key_eq() throws, and never 1868// mutates __value or actually inserts into the map. 1869template <class _Tp, class _Hash, class _Equal, class _Alloc> 1870_LIBCPP_INLINE_VISIBILITY 1871typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer 1872__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare( 1873 size_t __hash, value_type& __value) 1874{ 1875 size_type __bc = bucket_count(); 1876 1877 if (__bc != 0) 1878 { 1879 size_t __chash = __constrain_hash(__hash, __bc); 1880 __next_pointer __ndptr = __bucket_list_[__chash]; 1881 if (__ndptr != nullptr) 1882 { 1883 for (__ndptr = __ndptr->__next_; __ndptr != nullptr && 1884 __constrain_hash(__ndptr->__hash(), __bc) == __chash; 1885 __ndptr = __ndptr->__next_) 1886 { 1887 if (key_eq()(__ndptr->__upcast()->__value_, __value)) 1888 return __ndptr; 1889 } 1890 } 1891 } 1892 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1893 { 1894 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1895 size_type(ceil(float(size() + 1) / max_load_factor())))); 1896 } 1897 return nullptr; 1898} 1899 1900// Insert the node __nd into the container by pushing it into the right bucket, 1901// and updating size(). Assumes that __nd->__hash is up-to-date, and that 1902// rehashing has already occurred and that no element with the same key exists 1903// in the map. 1904template <class _Tp, class _Hash, class _Equal, class _Alloc> 1905_LIBCPP_INLINE_VISIBILITY 1906void 1907__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform( 1908 __node_pointer __nd) _NOEXCEPT 1909{ 1910 size_type __bc = bucket_count(); 1911 size_t __chash = __constrain_hash(__nd->__hash(), __bc); 1912 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 1913 __next_pointer __pn = __bucket_list_[__chash]; 1914 if (__pn == nullptr) 1915 { 1916 __pn =__p1_.first().__ptr(); 1917 __nd->__next_ = __pn->__next_; 1918 __pn->__next_ = __nd->__ptr(); 1919 // fix up __bucket_list_ 1920 __bucket_list_[__chash] = __pn; 1921 if (__nd->__next_ != nullptr) 1922 __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr(); 1923 } 1924 else 1925 { 1926 __nd->__next_ = __pn->__next_; 1927 __pn->__next_ = __nd->__ptr(); 1928 } 1929 ++size(); 1930} 1931 1932template <class _Tp, class _Hash, class _Equal, class _Alloc> 1933pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 1934__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) 1935{ 1936 __nd->__hash_ = hash_function()(__nd->__value_); 1937 __next_pointer __existing_node = 1938 __node_insert_unique_prepare(__nd->__hash(), __nd->__value_); 1939 1940 // Insert the node, unless it already exists in the container. 1941 bool __inserted = false; 1942 if (__existing_node == nullptr) 1943 { 1944 __node_insert_unique_perform(__nd); 1945 __existing_node = __nd->__ptr(); 1946 __inserted = true; 1947 } 1948#if _LIBCPP_DEBUG_LEVEL >= 2 1949 return pair<iterator, bool>(iterator(__existing_node, this), __inserted); 1950#else 1951 return pair<iterator, bool>(iterator(__existing_node), __inserted); 1952#endif 1953} 1954 1955// Prepare the container for an insertion of the value __cp_val with the hash 1956// __cp_hash. This does a lookup into the container to see if __cp_value is 1957// already present, and performs a rehash if necessary. Returns a pointer to the 1958// last occurance of __cp_val in the map. 1959// 1960// Note that this function does forward exceptions if key_eq() throws, and never 1961// mutates __value or actually inserts into the map. 1962template <class _Tp, class _Hash, class _Equal, class _Alloc> 1963typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer 1964__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare( 1965 size_t __cp_hash, value_type& __cp_val) 1966{ 1967 size_type __bc = bucket_count(); 1968 if (size()+1 > __bc * max_load_factor() || __bc == 0) 1969 { 1970 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 1971 size_type(ceil(float(size() + 1) / max_load_factor())))); 1972 __bc = bucket_count(); 1973 } 1974 size_t __chash = __constrain_hash(__cp_hash, __bc); 1975 __next_pointer __pn = __bucket_list_[__chash]; 1976 if (__pn != nullptr) 1977 { 1978 for (bool __found = false; __pn->__next_ != nullptr && 1979 __constrain_hash(__pn->__next_->__hash(), __bc) == __chash; 1980 __pn = __pn->__next_) 1981 { 1982 // __found key_eq() action 1983 // false false loop 1984 // true true loop 1985 // false true set __found to true 1986 // true false break 1987 if (__found != (__pn->__next_->__hash() == __cp_hash && 1988 key_eq()(__pn->__next_->__upcast()->__value_, __cp_val))) 1989 { 1990 if (!__found) 1991 __found = true; 1992 else 1993 break; 1994 } 1995 } 1996 } 1997 return __pn; 1998} 1999 2000// Insert the node __cp into the container after __pn (which is the last node in 2001// the bucket that compares equal to __cp). Rehashing, and checking for 2002// uniqueness has already been performed (in __node_insert_multi_prepare), so 2003// all we need to do is update the bucket and size(). Assumes that __cp->__hash 2004// is up-to-date. 2005template <class _Tp, class _Hash, class _Equal, class _Alloc> 2006void 2007__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform( 2008 __node_pointer __cp, __next_pointer __pn) _NOEXCEPT 2009{ 2010 size_type __bc = bucket_count(); 2011 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 2012 if (__pn == nullptr) 2013 { 2014 __pn =__p1_.first().__ptr(); 2015 __cp->__next_ = __pn->__next_; 2016 __pn->__next_ = __cp->__ptr(); 2017 // fix up __bucket_list_ 2018 __bucket_list_[__chash] = __pn; 2019 if (__cp->__next_ != nullptr) 2020 __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)] 2021 = __cp->__ptr(); 2022 } 2023 else 2024 { 2025 __cp->__next_ = __pn->__next_; 2026 __pn->__next_ = __cp->__ptr(); 2027 if (__cp->__next_ != nullptr) 2028 { 2029 size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc); 2030 if (__nhash != __chash) 2031 __bucket_list_[__nhash] = __cp->__ptr(); 2032 } 2033 } 2034 ++size(); 2035} 2036 2037 2038template <class _Tp, class _Hash, class _Equal, class _Alloc> 2039typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2040__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) 2041{ 2042 __cp->__hash_ = hash_function()(__cp->__value_); 2043 __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_); 2044 __node_insert_multi_perform(__cp, __pn); 2045 2046#if _LIBCPP_DEBUG_LEVEL >= 2 2047 return iterator(__cp->__ptr(), this); 2048#else 2049 return iterator(__cp->__ptr()); 2050#endif 2051} 2052 2053template <class _Tp, class _Hash, class _Equal, class _Alloc> 2054typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2055__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi( 2056 const_iterator __p, __node_pointer __cp) 2057{ 2058#if _LIBCPP_DEBUG_LEVEL >= 2 2059 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2060 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 2061 " referring to this unordered container"); 2062#endif 2063 if (__p != end() && key_eq()(*__p, __cp->__value_)) 2064 { 2065 __next_pointer __np = __p.__node_; 2066 __cp->__hash_ = __np->__hash(); 2067 size_type __bc = bucket_count(); 2068 if (size()+1 > __bc * max_load_factor() || __bc == 0) 2069 { 2070 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 2071 size_type(ceil(float(size() + 1) / max_load_factor())))); 2072 __bc = bucket_count(); 2073 } 2074 size_t __chash = __constrain_hash(__cp->__hash_, __bc); 2075 __next_pointer __pp = __bucket_list_[__chash]; 2076 while (__pp->__next_ != __np) 2077 __pp = __pp->__next_; 2078 __cp->__next_ = __np; 2079 __pp->__next_ = static_cast<__next_pointer>(__cp); 2080 ++size(); 2081#if _LIBCPP_DEBUG_LEVEL >= 2 2082 return iterator(static_cast<__next_pointer>(__cp), this); 2083#else 2084 return iterator(static_cast<__next_pointer>(__cp)); 2085#endif 2086 } 2087 return __node_insert_multi(__cp); 2088} 2089 2090 2091 2092#ifndef _LIBCPP_CXX03_LANG 2093template <class _Tp, class _Hash, class _Equal, class _Alloc> 2094template <class _Key, class ..._Args> 2095pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 2096__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) 2097#else 2098template <class _Tp, class _Hash, class _Equal, class _Alloc> 2099template <class _Key, class _Args> 2100pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 2101__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args& __args) 2102#endif 2103{ 2104 2105 size_t __hash = hash_function()(__k); 2106 size_type __bc = bucket_count(); 2107 bool __inserted = false; 2108 __next_pointer __nd; 2109 size_t __chash; 2110 if (__bc != 0) 2111 { 2112 __chash = __constrain_hash(__hash, __bc); 2113 __nd = __bucket_list_[__chash]; 2114 if (__nd != nullptr) 2115 { 2116 for (__nd = __nd->__next_; __nd != nullptr && 2117 (__nd->__hash() == __hash || __constrain_hash(__nd->__hash(), __bc) == __chash); 2118 __nd = __nd->__next_) 2119 { 2120 if (key_eq()(__nd->__upcast()->__value_, __k)) 2121 goto __done; 2122 } 2123 } 2124 } 2125 { 2126#ifndef _LIBCPP_CXX03_LANG 2127 __node_holder __h = __construct_node_hash(__hash, _VSTD::forward<_Args>(__args)...); 2128#else 2129 __node_holder __h = __construct_node_hash(__hash, __args); 2130#endif 2131 if (size()+1 > __bc * max_load_factor() || __bc == 0) 2132 { 2133 rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc), 2134 size_type(ceil(float(size() + 1) / max_load_factor())))); 2135 __bc = bucket_count(); 2136 __chash = __constrain_hash(__hash, __bc); 2137 } 2138 // insert_after __bucket_list_[__chash], or __first_node if bucket is null 2139 __next_pointer __pn = __bucket_list_[__chash]; 2140 if (__pn == nullptr) 2141 { 2142 __pn = __p1_.first().__ptr(); 2143 __h->__next_ = __pn->__next_; 2144 __pn->__next_ = __h.get()->__ptr(); 2145 // fix up __bucket_list_ 2146 __bucket_list_[__chash] = __pn; 2147 if (__h->__next_ != nullptr) 2148 __bucket_list_[__constrain_hash(__h->__next_->__hash(), __bc)] 2149 = __h.get()->__ptr(); 2150 } 2151 else 2152 { 2153 __h->__next_ = __pn->__next_; 2154 __pn->__next_ = static_cast<__next_pointer>(__h.get()); 2155 } 2156 __nd = static_cast<__next_pointer>(__h.release()); 2157 // increment size 2158 ++size(); 2159 __inserted = true; 2160 } 2161__done: 2162#if _LIBCPP_DEBUG_LEVEL >= 2 2163 return pair<iterator, bool>(iterator(__nd, this), __inserted); 2164#else 2165 return pair<iterator, bool>(iterator(__nd), __inserted); 2166#endif 2167} 2168 2169#ifndef _LIBCPP_CXX03_LANG 2170 2171template <class _Tp, class _Hash, class _Equal, class _Alloc> 2172template <class... _Args> 2173pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool> 2174__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) 2175{ 2176 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2177 pair<iterator, bool> __r = __node_insert_unique(__h.get()); 2178 if (__r.second) 2179 __h.release(); 2180 return __r; 2181} 2182 2183template <class _Tp, class _Hash, class _Equal, class _Alloc> 2184template <class... _Args> 2185typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2186__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) 2187{ 2188 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2189 iterator __r = __node_insert_multi(__h.get()); 2190 __h.release(); 2191 return __r; 2192} 2193 2194template <class _Tp, class _Hash, class _Equal, class _Alloc> 2195template <class... _Args> 2196typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2197__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi( 2198 const_iterator __p, _Args&&... __args) 2199{ 2200#if _LIBCPP_DEBUG_LEVEL >= 2 2201 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2202 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not" 2203 " referring to this unordered container"); 2204#endif 2205 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); 2206 iterator __r = __node_insert_multi(__p, __h.get()); 2207 __h.release(); 2208 return __r; 2209} 2210 2211#else // _LIBCPP_CXX03_LANG 2212 2213template <class _Tp, class _Hash, class _Equal, class _Alloc> 2214typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2215__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const __container_value_type& __x) 2216{ 2217 __node_holder __h = __construct_node(__x); 2218 iterator __r = __node_insert_multi(__h.get()); 2219 __h.release(); 2220 return __r; 2221} 2222 2223template <class _Tp, class _Hash, class _Equal, class _Alloc> 2224typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2225__hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p, 2226 const __container_value_type& __x) 2227{ 2228#if _LIBCPP_DEBUG_LEVEL >= 2 2229 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2230 "unordered container::insert(const_iterator, lvalue) called with an iterator not" 2231 " referring to this unordered container"); 2232#endif 2233 __node_holder __h = __construct_node(__x); 2234 iterator __r = __node_insert_multi(__p, __h.get()); 2235 __h.release(); 2236 return __r; 2237} 2238 2239#endif // _LIBCPP_CXX03_LANG 2240 2241#if _LIBCPP_STD_VER > 14 2242template <class _Tp, class _Hash, class _Equal, class _Alloc> 2243template <class _NodeHandle, class _InsertReturnType> 2244_LIBCPP_INLINE_VISIBILITY 2245_InsertReturnType 2246__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( 2247 _NodeHandle&& __nh) 2248{ 2249 if (__nh.empty()) 2250 return _InsertReturnType{end(), false, _NodeHandle()}; 2251 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); 2252 if (__result.second) 2253 __nh.__release_ptr(); 2254 return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)}; 2255} 2256 2257template <class _Tp, class _Hash, class _Equal, class _Alloc> 2258template <class _NodeHandle> 2259_LIBCPP_INLINE_VISIBILITY 2260typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2261__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique( 2262 const_iterator, _NodeHandle&& __nh) 2263{ 2264 if (__nh.empty()) 2265 return end(); 2266 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_); 2267 if (__result.second) 2268 __nh.__release_ptr(); 2269 return __result.first; 2270} 2271 2272template <class _Tp, class _Hash, class _Equal, class _Alloc> 2273template <class _NodeHandle> 2274_LIBCPP_INLINE_VISIBILITY 2275_NodeHandle 2276__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( 2277 key_type const& __key) 2278{ 2279 iterator __i = find(__key); 2280 if (__i == end()) 2281 return _NodeHandle(); 2282 return __node_handle_extract<_NodeHandle>(__i); 2283} 2284 2285template <class _Tp, class _Hash, class _Equal, class _Alloc> 2286template <class _NodeHandle> 2287_LIBCPP_INLINE_VISIBILITY 2288_NodeHandle 2289__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract( 2290 const_iterator __p) 2291{ 2292 allocator_type __alloc(__node_alloc()); 2293 return _NodeHandle(remove(__p).release(), __alloc); 2294} 2295 2296template <class _Tp, class _Hash, class _Equal, class _Alloc> 2297template <class _Table> 2298_LIBCPP_INLINE_VISIBILITY 2299void 2300__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique( 2301 _Table& __source) 2302{ 2303 static_assert(is_same<__node, typename _Table::__node>::value, ""); 2304 2305 for (typename _Table::iterator __it = __source.begin(); 2306 __it != __source.end();) 2307 { 2308 __node_pointer __src_ptr = __it.__node_->__upcast(); 2309 size_t __hash = hash_function()(__src_ptr->__value_); 2310 __next_pointer __existing_node = 2311 __node_insert_unique_prepare(__hash, __src_ptr->__value_); 2312 auto __prev_iter = __it++; 2313 if (__existing_node == nullptr) 2314 { 2315 (void)__source.remove(__prev_iter).release(); 2316 __src_ptr->__hash_ = __hash; 2317 __node_insert_unique_perform(__src_ptr); 2318 } 2319 } 2320} 2321 2322template <class _Tp, class _Hash, class _Equal, class _Alloc> 2323template <class _NodeHandle> 2324_LIBCPP_INLINE_VISIBILITY 2325typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2326__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( 2327 _NodeHandle&& __nh) 2328{ 2329 if (__nh.empty()) 2330 return end(); 2331 iterator __result = __node_insert_multi(__nh.__ptr_); 2332 __nh.__release_ptr(); 2333 return __result; 2334} 2335 2336template <class _Tp, class _Hash, class _Equal, class _Alloc> 2337template <class _NodeHandle> 2338_LIBCPP_INLINE_VISIBILITY 2339typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2340__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi( 2341 const_iterator __hint, _NodeHandle&& __nh) 2342{ 2343 if (__nh.empty()) 2344 return end(); 2345 iterator __result = __node_insert_multi(__hint, __nh.__ptr_); 2346 __nh.__release_ptr(); 2347 return __result; 2348} 2349 2350template <class _Tp, class _Hash, class _Equal, class _Alloc> 2351template <class _Table> 2352_LIBCPP_INLINE_VISIBILITY 2353void 2354__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi( 2355 _Table& __source) 2356{ 2357 static_assert(is_same<typename _Table::__node, __node>::value, ""); 2358 2359 for (typename _Table::iterator __it = __source.begin(); 2360 __it != __source.end();) 2361 { 2362 __node_pointer __src_ptr = __it.__node_->__upcast(); 2363 size_t __src_hash = hash_function()(__src_ptr->__value_); 2364 __next_pointer __pn = 2365 __node_insert_multi_prepare(__src_hash, __src_ptr->__value_); 2366 (void)__source.remove(__it++).release(); 2367 __src_ptr->__hash_ = __src_hash; 2368 __node_insert_multi_perform(__src_ptr, __pn); 2369 } 2370} 2371#endif // _LIBCPP_STD_VER > 14 2372 2373template <class _Tp, class _Hash, class _Equal, class _Alloc> 2374void 2375__hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n) 2376_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 2377{ 2378 if (__n == 1) 2379 __n = 2; 2380 else if (__n & (__n - 1)) 2381 __n = __next_prime(__n); 2382 size_type __bc = bucket_count(); 2383 if (__n > __bc) 2384 __rehash(__n); 2385 else if (__n < __bc) 2386 { 2387 __n = _VSTD::max<size_type> 2388 ( 2389 __n, 2390 __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) : 2391 __next_prime(size_t(ceil(float(size()) / max_load_factor()))) 2392 ); 2393 if (__n < __bc) 2394 __rehash(__n); 2395 } 2396} 2397 2398template <class _Tp, class _Hash, class _Equal, class _Alloc> 2399void 2400__hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc) 2401{ 2402#if _LIBCPP_DEBUG_LEVEL >= 2 2403 __get_db()->__invalidate_all(this); 2404#endif // _LIBCPP_DEBUG_LEVEL >= 2 2405 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc(); 2406 __bucket_list_.reset(__nbc > 0 ? 2407 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr); 2408 __bucket_list_.get_deleter().size() = __nbc; 2409 if (__nbc > 0) 2410 { 2411 for (size_type __i = 0; __i < __nbc; ++__i) 2412 __bucket_list_[__i] = nullptr; 2413 __next_pointer __pp = __p1_.first().__ptr(); 2414 __next_pointer __cp = __pp->__next_; 2415 if (__cp != nullptr) 2416 { 2417 size_type __chash = __constrain_hash(__cp->__hash(), __nbc); 2418 __bucket_list_[__chash] = __pp; 2419 size_type __phash = __chash; 2420 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr; 2421 __cp = __pp->__next_) 2422 { 2423 __chash = __constrain_hash(__cp->__hash(), __nbc); 2424 if (__chash == __phash) 2425 __pp = __cp; 2426 else 2427 { 2428 if (__bucket_list_[__chash] == nullptr) 2429 { 2430 __bucket_list_[__chash] = __pp; 2431 __pp = __cp; 2432 __phash = __chash; 2433 } 2434 else 2435 { 2436 __next_pointer __np = __cp; 2437 for (; __np->__next_ != nullptr && 2438 key_eq()(__cp->__upcast()->__value_, 2439 __np->__next_->__upcast()->__value_); 2440 __np = __np->__next_) 2441 ; 2442 __pp->__next_ = __np->__next_; 2443 __np->__next_ = __bucket_list_[__chash]->__next_; 2444 __bucket_list_[__chash]->__next_ = __cp; 2445 2446 } 2447 } 2448 } 2449 } 2450 } 2451} 2452 2453template <class _Tp, class _Hash, class _Equal, class _Alloc> 2454template <class _Key> 2455typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2456__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) 2457{ 2458 size_t __hash = hash_function()(__k); 2459 size_type __bc = bucket_count(); 2460 if (__bc != 0) 2461 { 2462 size_t __chash = __constrain_hash(__hash, __bc); 2463 __next_pointer __nd = __bucket_list_[__chash]; 2464 if (__nd != nullptr) 2465 { 2466 for (__nd = __nd->__next_; __nd != nullptr && 2467 (__nd->__hash() == __hash 2468 || __constrain_hash(__nd->__hash(), __bc) == __chash); 2469 __nd = __nd->__next_) 2470 { 2471 if ((__nd->__hash() == __hash) 2472 && key_eq()(__nd->__upcast()->__value_, __k)) 2473#if _LIBCPP_DEBUG_LEVEL >= 2 2474 return iterator(__nd, this); 2475#else 2476 return iterator(__nd); 2477#endif 2478 } 2479 } 2480 } 2481 return end(); 2482} 2483 2484template <class _Tp, class _Hash, class _Equal, class _Alloc> 2485template <class _Key> 2486typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator 2487__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const 2488{ 2489 size_t __hash = hash_function()(__k); 2490 size_type __bc = bucket_count(); 2491 if (__bc != 0) 2492 { 2493 size_t __chash = __constrain_hash(__hash, __bc); 2494 __next_pointer __nd = __bucket_list_[__chash]; 2495 if (__nd != nullptr) 2496 { 2497 for (__nd = __nd->__next_; __nd != nullptr && 2498 (__hash == __nd->__hash() 2499 || __constrain_hash(__nd->__hash(), __bc) == __chash); 2500 __nd = __nd->__next_) 2501 { 2502 if ((__nd->__hash() == __hash) 2503 && key_eq()(__nd->__upcast()->__value_, __k)) 2504#if _LIBCPP_DEBUG_LEVEL >= 2 2505 return const_iterator(__nd, this); 2506#else 2507 return const_iterator(__nd); 2508#endif 2509 } 2510 } 2511 2512 } 2513 return end(); 2514} 2515 2516#ifndef _LIBCPP_CXX03_LANG 2517 2518template <class _Tp, class _Hash, class _Equal, class _Alloc> 2519template <class ..._Args> 2520typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2521__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args) 2522{ 2523 static_assert(!__is_hash_value_type<_Args...>::value, 2524 "Construct cannot be called with a hash value type"); 2525 __node_allocator& __na = __node_alloc(); 2526 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2527 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); 2528 __h.get_deleter().__value_constructed = true; 2529 __h->__hash_ = hash_function()(__h->__value_); 2530 __h->__next_ = nullptr; 2531 return __h; 2532} 2533 2534template <class _Tp, class _Hash, class _Equal, class _Alloc> 2535template <class _First, class ..._Rest> 2536typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2537__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash( 2538 size_t __hash, _First&& __f, _Rest&& ...__rest) 2539{ 2540 static_assert(!__is_hash_value_type<_First, _Rest...>::value, 2541 "Construct cannot be called with a hash value type"); 2542 __node_allocator& __na = __node_alloc(); 2543 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2544 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), 2545 _VSTD::forward<_First>(__f), 2546 _VSTD::forward<_Rest>(__rest)...); 2547 __h.get_deleter().__value_constructed = true; 2548 __h->__hash_ = __hash; 2549 __h->__next_ = nullptr; 2550 return __h; 2551} 2552 2553#else // _LIBCPP_CXX03_LANG 2554 2555template <class _Tp, class _Hash, class _Equal, class _Alloc> 2556typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2557__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const __container_value_type& __v) 2558{ 2559 __node_allocator& __na = __node_alloc(); 2560 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2561 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); 2562 __h.get_deleter().__value_constructed = true; 2563 __h->__hash_ = hash_function()(__h->__value_); 2564 __h->__next_ = nullptr; 2565 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2566} 2567 2568template <class _Tp, class _Hash, class _Equal, class _Alloc> 2569typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2570__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, 2571 const __container_value_type& __v) 2572{ 2573 __node_allocator& __na = __node_alloc(); 2574 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); 2575 __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); 2576 __h.get_deleter().__value_constructed = true; 2577 __h->__hash_ = __hash; 2578 __h->__next_ = nullptr; 2579 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03 2580} 2581 2582#endif // _LIBCPP_CXX03_LANG 2583 2584template <class _Tp, class _Hash, class _Equal, class _Alloc> 2585typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2586__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) 2587{ 2588 __next_pointer __np = __p.__node_; 2589#if _LIBCPP_DEBUG_LEVEL >= 2 2590 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, 2591 "unordered container erase(iterator) called with an iterator not" 2592 " referring to this container"); 2593 _LIBCPP_ASSERT(__p != end(), 2594 "unordered container erase(iterator) called with a non-dereferenceable iterator"); 2595 iterator __r(__np, this); 2596#else 2597 iterator __r(__np); 2598#endif 2599 ++__r; 2600 remove(__p); 2601 return __r; 2602} 2603 2604template <class _Tp, class _Hash, class _Equal, class _Alloc> 2605typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator 2606__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, 2607 const_iterator __last) 2608{ 2609#if _LIBCPP_DEBUG_LEVEL >= 2 2610 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 2611 "unodered container::erase(iterator, iterator) called with an iterator not" 2612 " referring to this unodered container"); 2613 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 2614 "unodered container::erase(iterator, iterator) called with an iterator not" 2615 " referring to this unodered container"); 2616#endif 2617 for (const_iterator __p = __first; __first != __last; __p = __first) 2618 { 2619 ++__first; 2620 erase(__p); 2621 } 2622 __next_pointer __np = __last.__node_; 2623#if _LIBCPP_DEBUG_LEVEL >= 2 2624 return iterator (__np, this); 2625#else 2626 return iterator (__np); 2627#endif 2628} 2629 2630template <class _Tp, class _Hash, class _Equal, class _Alloc> 2631template <class _Key> 2632typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2633__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) 2634{ 2635 iterator __i = find(__k); 2636 if (__i == end()) 2637 return 0; 2638 erase(__i); 2639 return 1; 2640} 2641 2642template <class _Tp, class _Hash, class _Equal, class _Alloc> 2643template <class _Key> 2644typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2645__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) 2646{ 2647 size_type __r = 0; 2648 iterator __i = find(__k); 2649 if (__i != end()) 2650 { 2651 iterator __e = end(); 2652 do 2653 { 2654 erase(__i++); 2655 ++__r; 2656 } while (__i != __e && key_eq()(*__i, __k)); 2657 } 2658 return __r; 2659} 2660 2661template <class _Tp, class _Hash, class _Equal, class _Alloc> 2662typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder 2663__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT 2664{ 2665 // current node 2666 __next_pointer __cn = __p.__node_; 2667 size_type __bc = bucket_count(); 2668 size_t __chash = __constrain_hash(__cn->__hash(), __bc); 2669 // find previous node 2670 __next_pointer __pn = __bucket_list_[__chash]; 2671 for (; __pn->__next_ != __cn; __pn = __pn->__next_) 2672 ; 2673 // Fix up __bucket_list_ 2674 // if __pn is not in same bucket (before begin is not in same bucket) && 2675 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket) 2676 if (__pn == __p1_.first().__ptr() 2677 || __constrain_hash(__pn->__hash(), __bc) != __chash) 2678 { 2679 if (__cn->__next_ == nullptr 2680 || __constrain_hash(__cn->__next_->__hash(), __bc) != __chash) 2681 __bucket_list_[__chash] = nullptr; 2682 } 2683 // if __cn->__next_ is not in same bucket (nullptr is in same bucket) 2684 if (__cn->__next_ != nullptr) 2685 { 2686 size_t __nhash = __constrain_hash(__cn->__next_->__hash(), __bc); 2687 if (__nhash != __chash) 2688 __bucket_list_[__nhash] = __pn; 2689 } 2690 // remove __cn 2691 __pn->__next_ = __cn->__next_; 2692 __cn->__next_ = nullptr; 2693 --size(); 2694#if _LIBCPP_DEBUG_LEVEL >= 2 2695 __c_node* __c = __get_db()->__find_c_and_lock(this); 2696 for (__i_node** __dp = __c->end_; __dp != __c->beg_; ) 2697 { 2698 --__dp; 2699 iterator* __i = static_cast<iterator*>((*__dp)->__i_); 2700 if (__i->__node_ == __cn) 2701 { 2702 (*__dp)->__c_ = nullptr; 2703 if (--__c->end_ != __dp) 2704 memmove(__dp, __dp+1, (__c->end_ - __dp)*sizeof(__i_node*)); 2705 } 2706 } 2707 __get_db()->unlock(); 2708#endif 2709 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true)); 2710} 2711 2712template <class _Tp, class _Hash, class _Equal, class _Alloc> 2713template <class _Key> 2714inline 2715typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2716__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const 2717{ 2718 return static_cast<size_type>(find(__k) != end()); 2719} 2720 2721template <class _Tp, class _Hash, class _Equal, class _Alloc> 2722template <class _Key> 2723typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2724__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const 2725{ 2726 size_type __r = 0; 2727 const_iterator __i = find(__k); 2728 if (__i != end()) 2729 { 2730 const_iterator __e = end(); 2731 do 2732 { 2733 ++__i; 2734 ++__r; 2735 } while (__i != __e && key_eq()(*__i, __k)); 2736 } 2737 return __r; 2738} 2739 2740template <class _Tp, class _Hash, class _Equal, class _Alloc> 2741template <class _Key> 2742pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2743 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2744__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2745 const _Key& __k) 2746{ 2747 iterator __i = find(__k); 2748 iterator __j = __i; 2749 if (__i != end()) 2750 ++__j; 2751 return pair<iterator, iterator>(__i, __j); 2752} 2753 2754template <class _Tp, class _Hash, class _Equal, class _Alloc> 2755template <class _Key> 2756pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2757 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2758__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique( 2759 const _Key& __k) const 2760{ 2761 const_iterator __i = find(__k); 2762 const_iterator __j = __i; 2763 if (__i != end()) 2764 ++__j; 2765 return pair<const_iterator, const_iterator>(__i, __j); 2766} 2767 2768template <class _Tp, class _Hash, class _Equal, class _Alloc> 2769template <class _Key> 2770pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, 2771 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator> 2772__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2773 const _Key& __k) 2774{ 2775 iterator __i = find(__k); 2776 iterator __j = __i; 2777 if (__i != end()) 2778 { 2779 iterator __e = end(); 2780 do 2781 { 2782 ++__j; 2783 } while (__j != __e && key_eq()(*__j, __k)); 2784 } 2785 return pair<iterator, iterator>(__i, __j); 2786} 2787 2788template <class _Tp, class _Hash, class _Equal, class _Alloc> 2789template <class _Key> 2790pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator, 2791 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator> 2792__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi( 2793 const _Key& __k) const 2794{ 2795 const_iterator __i = find(__k); 2796 const_iterator __j = __i; 2797 if (__i != end()) 2798 { 2799 const_iterator __e = end(); 2800 do 2801 { 2802 ++__j; 2803 } while (__j != __e && key_eq()(*__j, __k)); 2804 } 2805 return pair<const_iterator, const_iterator>(__i, __j); 2806} 2807 2808template <class _Tp, class _Hash, class _Equal, class _Alloc> 2809void 2810__hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u) 2811#if _LIBCPP_STD_VER <= 11 2812 _NOEXCEPT_( 2813 __is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value 2814 && (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value 2815 || __is_nothrow_swappable<__pointer_allocator>::value) 2816 && (!__node_traits::propagate_on_container_swap::value 2817 || __is_nothrow_swappable<__node_allocator>::value) 2818 ) 2819#else 2820 _NOEXCEPT_(__is_nothrow_swappable<hasher>::value && __is_nothrow_swappable<key_equal>::value) 2821#endif 2822{ 2823 _LIBCPP_ASSERT(__node_traits::propagate_on_container_swap::value || 2824 this->__node_alloc() == __u.__node_alloc(), 2825 "list::swap: Either propagate_on_container_swap must be true" 2826 " or the allocators must compare equal"); 2827 { 2828 __node_pointer_pointer __npp = __bucket_list_.release(); 2829 __bucket_list_.reset(__u.__bucket_list_.release()); 2830 __u.__bucket_list_.reset(__npp); 2831 } 2832 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size()); 2833 __swap_allocator(__bucket_list_.get_deleter().__alloc(), 2834 __u.__bucket_list_.get_deleter().__alloc()); 2835 __swap_allocator(__node_alloc(), __u.__node_alloc()); 2836 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_); 2837 __p2_.swap(__u.__p2_); 2838 __p3_.swap(__u.__p3_); 2839 if (size() > 0) 2840 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = 2841 __p1_.first().__ptr(); 2842 if (__u.size() > 0) 2843 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] = 2844 __u.__p1_.first().__ptr(); 2845#if _LIBCPP_DEBUG_LEVEL >= 2 2846 __get_db()->swap(this, &__u); 2847#endif 2848} 2849 2850template <class _Tp, class _Hash, class _Equal, class _Alloc> 2851typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type 2852__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const 2853{ 2854 _LIBCPP_ASSERT(__n < bucket_count(), 2855 "unordered container::bucket_size(n) called with n >= bucket_count()"); 2856 __next_pointer __np = __bucket_list_[__n]; 2857 size_type __bc = bucket_count(); 2858 size_type __r = 0; 2859 if (__np != nullptr) 2860 { 2861 for (__np = __np->__next_; __np != nullptr && 2862 __constrain_hash(__np->__hash(), __bc) == __n; 2863 __np = __np->__next_, ++__r) 2864 ; 2865 } 2866 return __r; 2867} 2868 2869template <class _Tp, class _Hash, class _Equal, class _Alloc> 2870inline _LIBCPP_INLINE_VISIBILITY 2871void 2872swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, 2873 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y) 2874 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2875{ 2876 __x.swap(__y); 2877} 2878 2879#if _LIBCPP_DEBUG_LEVEL >= 2 2880 2881template <class _Tp, class _Hash, class _Equal, class _Alloc> 2882bool 2883__hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const 2884{ 2885 return __i->__node_ != nullptr; 2886} 2887 2888template <class _Tp, class _Hash, class _Equal, class _Alloc> 2889bool 2890__hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const 2891{ 2892 return false; 2893} 2894 2895template <class _Tp, class _Hash, class _Equal, class _Alloc> 2896bool 2897__hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const 2898{ 2899 return false; 2900} 2901 2902template <class _Tp, class _Hash, class _Equal, class _Alloc> 2903bool 2904__hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const 2905{ 2906 return false; 2907} 2908 2909#endif // _LIBCPP_DEBUG_LEVEL >= 2 2910 2911_LIBCPP_END_NAMESPACE_STD 2912 2913_LIBCPP_POP_MACROS 2914 2915#endif // _LIBCPP__HASH_TABLE 2916