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