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