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