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