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