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