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