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