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