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