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