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