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