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