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