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