2125 lines · plain
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___HASH_TABLE11#define _LIBCPP___HASH_TABLE12 13#include <__algorithm/fill_n.h>14#include <__algorithm/max.h>15#include <__algorithm/min.h>16#include <__assert>17#include <__bit/countl.h>18#include <__config>19#include <__cstddef/ptrdiff_t.h>20#include <__cstddef/size_t.h>21#include <__functional/hash.h>22#include <__iterator/iterator_traits.h>23#include <__math/rounding_functions.h>24#include <__memory/addressof.h>25#include <__memory/allocator_traits.h>26#include <__memory/compressed_pair.h>27#include <__memory/construct_at.h>28#include <__memory/pointer_traits.h>29#include <__memory/swap_allocator.h>30#include <__memory/unique_ptr.h>31#include <__new/launder.h>32#include <__type_traits/copy_cvref.h>33#include <__type_traits/enable_if.h>34#include <__type_traits/invoke.h>35#include <__type_traits/is_const.h>36#include <__type_traits/is_constructible.h>37#include <__type_traits/is_nothrow_assignable.h>38#include <__type_traits/is_nothrow_constructible.h>39#include <__type_traits/is_reference.h>40#include <__type_traits/is_same.h>41#include <__type_traits/is_swappable.h>42#include <__type_traits/remove_const.h>43#include <__type_traits/remove_cvref.h>44#include <__utility/forward.h>45#include <__utility/move.h>46#include <__utility/pair.h>47#include <__utility/scope_guard.h>48#include <__utility/swap.h>49#include <__utility/try_key_extraction.h>50#include <limits>51 52#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)53# pragma GCC system_header54#endif55 56_LIBCPP_PUSH_MACROS57#include <__undef_macros>58 59_LIBCPP_BEGIN_NAMESPACE_STD60 61template <class _Key, class _Tp>62struct __hash_value_type;63 64template <class _Tp>65struct __is_hash_value_type_imp : false_type {};66 67template <class _Key, class _Value>68struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};69 70template <class... _Args>71struct __is_hash_value_type : false_type {};72 73template <class _One>74struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};75 76_LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);77 78template <class _NodePtr>79struct __hash_node_base {80 typedef typename pointer_traits<_NodePtr>::element_type __node_type;81 typedef __hash_node_base __first_node;82 typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;83 typedef _NodePtr __node_pointer;84 typedef __node_base_pointer __next_pointer;85 86 __next_pointer __next_;87 88 _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT {89 return static_cast<__next_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));90 }91 92 _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT {93 return static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));94 }95 96 _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; }97 98 _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {}99 _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}100};101 102template <class _Tp>103struct __get_hash_node_value_type {104 using type _LIBCPP_NODEBUG = _Tp;105};106 107template <class _Key, class _Tp>108struct __get_hash_node_value_type<__hash_value_type<_Key, _Tp> > {109 using type _LIBCPP_NODEBUG = pair<const _Key, _Tp>;110};111 112template <class _Tp>113using __get_hash_node_value_type_t _LIBCPP_NODEBUG = typename __get_hash_node_value_type<_Tp>::type;114 115template <class _Tp>116struct __get_hash_node_key_type {117 using type _LIBCPP_NODEBUG = _Tp;118};119 120template <class _Key, class _Tp>121struct __get_hash_node_key_type<__hash_value_type<_Key, _Tp> > {122 using type _LIBCPP_NODEBUG = _Key;123};124 125template <class _Tp>126using __get_hash_node_key_type_t _LIBCPP_NODEBUG = typename __get_hash_node_key_type<_Tp>::type;127 128template <class _Tp, class _VoidPtr>129struct __hash_node : public __hash_node_base< __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > {130 using __node_value_type _LIBCPP_NODEBUG = __get_hash_node_value_type_t<_Tp>;131 using _Base _LIBCPP_NODEBUG = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;132 using __next_pointer _LIBCPP_NODEBUG = typename _Base::__next_pointer;133 134 size_t __hash_;135 136 // We allow starting the lifetime of nodes without initializing the value held by the node,137 // since that is handled by the hash table itself in order to be allocator-aware.138#ifndef _LIBCPP_CXX03_LANG139 140private:141 union {142 __node_value_type __value_;143 };144 145public:146 _LIBCPP_HIDE_FROM_ABI __node_value_type& __get_value() { return __value_; }147#else148 149private:150 _ALIGNAS_TYPE(__node_value_type) char __buffer_[sizeof(__node_value_type)];151 152public:153 _LIBCPP_HIDE_FROM_ABI __node_value_type& __get_value() {154 return *std::__launder(reinterpret_cast<__node_value_type*>(&__buffer_));155 }156#endif157 158 template <class _Alloc, class... _Args>159 _LIBCPP_HIDE_FROM_ABI explicit __hash_node(size_t __hash, _Alloc& __na, _Args&&... __args)160 : _Base(nullptr), __hash_(__hash) {161 allocator_traits<_Alloc>::construct(__na, std::addressof(__get_value()), std::forward<_Args>(__args)...);162 }163 164 _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}165};166 167inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); }168 169inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) {170 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc);171}172 173inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) {174 return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - std::__countl_zero(__n - 1)));175}176 177template <class _Tp, class _Hash, class _Equal, class _Alloc>178class __hash_table;179 180template <class _NodePtr>181class __hash_iterator;182template <class _ConstNodePtr>183class __hash_const_iterator;184template <class _NodePtr>185class __hash_local_iterator;186template <class _ConstNodePtr>187class __hash_const_local_iterator;188template <class _HashIterator>189class __hash_map_iterator;190template <class _HashIterator>191class __hash_map_const_iterator;192 193template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>194struct __hash_node_types;195 196template <class _NodePtr, class _Tp, class _VoidPtr>197struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> > {198 typedef typename pointer_traits<_NodePtr>::element_type __node_type;199 200 typedef typename __hash_node_base<_NodePtr>::__next_pointer __next_pointer;201 202 using __node_value_type _LIBCPP_NODEBUG = __get_hash_node_value_type_t<_Tp>;203 204private:205 static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");206 static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,207 "_VoidPtr does not point to unqualified void type");208 static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,209 "_VoidPtr does not rebind to _NodePtr.");210};211 212template <class _HashIterator>213struct __hash_node_types_from_iterator;214template <class _NodePtr>215struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};216template <class _NodePtr>217struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};218template <class _NodePtr>219struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};220template <class _NodePtr>221struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};222 223template <class _NodePtr>224class __hash_iterator {225 typedef __hash_node_types<_NodePtr> _NodeTypes;226 typedef _NodePtr __node_pointer;227 typedef typename _NodeTypes::__next_pointer __next_pointer;228 229 __next_pointer __node_;230 231public:232 typedef forward_iterator_tag iterator_category;233 typedef typename _NodeTypes::__node_value_type value_type;234 using difference_type = ptrdiff_t;235 typedef value_type& reference;236 using pointer = __rebind_pointer_t<_NodePtr, value_type>;237 238 _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {}239 240 _LIBCPP_HIDE_FROM_ABI reference operator*() const {241 _LIBCPP_ASSERT_NON_NULL(242 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");243 return __node_->__upcast()->__get_value();244 }245 246 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {247 _LIBCPP_ASSERT_NON_NULL(248 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");249 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());250 }251 252 _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() {253 _LIBCPP_ASSERT_NON_NULL(254 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container iterator");255 __node_ = __node_->__next_;256 return *this;257 }258 259 _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) {260 __hash_iterator __t(*this);261 ++(*this);262 return __t;263 }264 265 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) {266 return __x.__node_ == __y.__node_;267 }268 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {269 return !(__x == __y);270 }271 272private:273 _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}274 275 template <class, class, class, class>276 friend class __hash_table;277 template <class>278 friend class __hash_const_iterator;279 template <class>280 friend class __hash_map_iterator;281 template <class, class, class, class, class>282 friend class unordered_map;283 template <class, class, class, class, class>284 friend class unordered_multimap;285};286 287template <class _NodePtr>288class __hash_const_iterator {289 static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");290 typedef __hash_node_types<_NodePtr> _NodeTypes;291 typedef _NodePtr __node_pointer;292 typedef typename _NodeTypes::__next_pointer __next_pointer;293 294 __next_pointer __node_;295 296public:297 typedef __hash_iterator<_NodePtr> __non_const_iterator;298 299 typedef forward_iterator_tag iterator_category;300 typedef typename _NodeTypes::__node_value_type value_type;301 using difference_type = ptrdiff_t;302 typedef const value_type& reference;303 using pointer = __rebind_pointer_t<_NodePtr, const value_type>;304 305 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {}306 307 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) {}308 309 _LIBCPP_HIDE_FROM_ABI reference operator*() const {310 _LIBCPP_ASSERT_NON_NULL(311 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");312 return __node_->__upcast()->__get_value();313 }314 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {315 _LIBCPP_ASSERT_NON_NULL(316 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");317 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());318 }319 320 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() {321 _LIBCPP_ASSERT_NON_NULL(322 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_iterator");323 __node_ = __node_->__next_;324 return *this;325 }326 327 _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) {328 __hash_const_iterator __t(*this);329 ++(*this);330 return __t;331 }332 333 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {334 return __x.__node_ == __y.__node_;335 }336 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {337 return !(__x == __y);338 }339 340private:341 _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}342 343 template <class, class, class, class>344 friend class __hash_table;345 template <class>346 friend class __hash_map_const_iterator;347 template <class, class, class, class, class>348 friend class unordered_map;349 template <class, class, class, class, class>350 friend class unordered_multimap;351};352 353template <class _NodePtr>354class __hash_local_iterator {355 typedef __hash_node_types<_NodePtr> _NodeTypes;356 typedef _NodePtr __node_pointer;357 typedef typename _NodeTypes::__next_pointer __next_pointer;358 359 __next_pointer __node_;360 size_t __bucket_;361 size_t __bucket_count_;362 363public:364 typedef forward_iterator_tag iterator_category;365 typedef typename _NodeTypes::__node_value_type value_type;366 using difference_type = ptrdiff_t;367 typedef value_type& reference;368 using pointer = __rebind_pointer_t<_NodePtr, value_type>;369 370 _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {}371 372 _LIBCPP_HIDE_FROM_ABI reference operator*() const {373 _LIBCPP_ASSERT_NON_NULL(374 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");375 return __node_->__upcast()->__get_value();376 }377 378 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {379 _LIBCPP_ASSERT_NON_NULL(380 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");381 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());382 }383 384 _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() {385 _LIBCPP_ASSERT_NON_NULL(386 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container local_iterator");387 __node_ = __node_->__next_;388 if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)389 __node_ = nullptr;390 return *this;391 }392 393 _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) {394 __hash_local_iterator __t(*this);395 ++(*this);396 return __t;397 }398 399 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {400 return __x.__node_ == __y.__node_;401 }402 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {403 return !(__x == __y);404 }405 406private:407 _LIBCPP_HIDE_FROM_ABI explicit __hash_local_iterator(408 __next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT409 : __node_(__node),410 __bucket_(__bucket),411 __bucket_count_(__bucket_count) {412 if (__node_ != nullptr)413 __node_ = __node_->__next_;414 }415 416 template <class, class, class, class>417 friend class __hash_table;418 template <class>419 friend class __hash_const_local_iterator;420 template <class>421 friend class __hash_map_iterator;422};423 424template <class _ConstNodePtr>425class __hash_const_local_iterator {426 typedef __hash_node_types<_ConstNodePtr> _NodeTypes;427 typedef _ConstNodePtr __node_pointer;428 typedef typename _NodeTypes::__next_pointer __next_pointer;429 430 __next_pointer __node_;431 size_t __bucket_;432 size_t __bucket_count_;433 434 typedef pointer_traits<__node_pointer> __pointer_traits;435 typedef typename __pointer_traits::element_type __node;436 typedef __remove_const_t<__node> __non_const_node;437 typedef __rebind_pointer_t<__node_pointer, __non_const_node> __non_const_node_pointer;438 439public:440 typedef __hash_local_iterator<__non_const_node_pointer> __non_const_iterator;441 442 typedef forward_iterator_tag iterator_category;443 typedef typename _NodeTypes::__node_value_type value_type;444 using difference_type = ptrdiff_t;445 typedef const value_type& reference;446 using pointer = __rebind_pointer_t<_ConstNodePtr, const value_type>;447 448 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {}449 450 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT451 : __node_(__x.__node_),452 __bucket_(__x.__bucket_),453 __bucket_count_(__x.__bucket_count_) {}454 455 _LIBCPP_HIDE_FROM_ABI reference operator*() const {456 _LIBCPP_ASSERT_NON_NULL(457 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");458 return __node_->__upcast()->__get_value();459 }460 461 _LIBCPP_HIDE_FROM_ABI pointer operator->() const {462 _LIBCPP_ASSERT_NON_NULL(463 __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");464 return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());465 }466 467 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator& operator++() {468 _LIBCPP_ASSERT_NON_NULL(469 __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_local_iterator");470 __node_ = __node_->__next_;471 if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)472 __node_ = nullptr;473 return *this;474 }475 476 _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator operator++(int) {477 __hash_const_local_iterator __t(*this);478 ++(*this);479 return __t;480 }481 482 friend _LIBCPP_HIDE_FROM_ABI bool483 operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {484 return __x.__node_ == __y.__node_;485 }486 friend _LIBCPP_HIDE_FROM_ABI bool487 operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {488 return !(__x == __y);489 }490 491private:492 _LIBCPP_HIDE_FROM_ABI explicit __hash_const_local_iterator(493 __next_pointer __node_ptr, size_t __bucket, size_t __bucket_count) _NOEXCEPT494 : __node_(__node_ptr),495 __bucket_(__bucket),496 __bucket_count_(__bucket_count) {497 if (__node_ != nullptr)498 __node_ = __node_->__next_;499 }500 501 template <class, class, class, class>502 friend class __hash_table;503 template <class>504 friend class __hash_map_const_iterator;505};506 507template <class _Alloc>508class __bucket_list_deallocator {509 typedef _Alloc allocator_type;510 typedef allocator_traits<allocator_type> __alloc_traits;511 typedef typename __alloc_traits::size_type size_type;512 513 _LIBCPP_COMPRESSED_PAIR(size_type, __size_, allocator_type, __alloc_);514 515public:516 typedef typename __alloc_traits::pointer pointer;517 518 _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)519 : __size_(0) {}520 521 _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(const allocator_type& __a, size_type __size)522 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)523 : __size_(__size), __alloc_(__a) {}524 525 _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(__bucket_list_deallocator&& __x)526 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)527 : __size_(std::move(__x.__size_)), __alloc_(std::move(__x.__alloc_)) {528 __x.size() = 0;529 }530 531 _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; }532 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }533 534 _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __alloc_; }535 _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __alloc_; }536 537 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { __alloc_traits::deallocate(__alloc(), __p, size()); }538};539 540template <class _Alloc>541class __hash_map_node_destructor;542 543template <class _Alloc>544class __hash_node_destructor {545 typedef _Alloc allocator_type;546 typedef allocator_traits<allocator_type> __alloc_traits;547 548public:549 typedef typename __alloc_traits::pointer pointer;550 551private:552 allocator_type& __na_;553 554public:555 bool __value_constructed;556 557 _LIBCPP_HIDE_FROM_ABI __hash_node_destructor(__hash_node_destructor const&) = default;558 _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;559 560 _LIBCPP_HIDE_FROM_ABI explicit __hash_node_destructor(allocator_type& __na, bool __constructed = false) _NOEXCEPT561 : __na_(__na),562 __value_constructed(__constructed) {}563 564 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {565 if (__value_constructed) {566 __alloc_traits::destroy(__na_, std::addressof(__p->__get_value()));567 std::__destroy_at(std::addressof(*__p));568 }569 if (__p)570 __alloc_traits::deallocate(__na_, __p, 1);571 }572 573 template <class>574 friend class __hash_map_node_destructor;575};576 577#if _LIBCPP_STD_VER >= 17578template <class _NodeType, class _Alloc>579struct __generic_container_node_destructor;580 581template <class _Tp, class _VoidPtr, class _Alloc>582struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> : __hash_node_destructor<_Alloc> {583 using __hash_node_destructor<_Alloc>::__hash_node_destructor;584};585#endif586 587template <class _Key, class _Hash, class _Equal>588struct __enforce_unordered_container_requirements {589#ifndef _LIBCPP_CXX03_LANG590 static_assert(__check_hash_requirements<_Key, _Hash>::value,591 "the specified hash does not meet the Hash requirements");592 static_assert(is_copy_constructible<_Equal>::value, "the specified comparator is required to be copy constructible");593#endif594 typedef int type;595};596 597template <class _Key, class _Hash, class _Equal>598#ifndef _LIBCPP_CXX03_LANG599_LIBCPP_DIAGNOSE_WARNING(!__is_invocable_v<_Equal const&, _Key const&, _Key const&>,600 "the specified comparator type does not provide a viable const call operator")601_LIBCPP_DIAGNOSE_WARNING(!__is_invocable_v<_Hash const&, _Key const&>,602 "the specified hash functor does not provide a viable const call operator")603#endif604 typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type605 __diagnose_unordered_container_requirements(int);606 607// This dummy overload is used so that the compiler won't emit a spurious608// "no matching function for call to __diagnose_unordered_xxx" diagnostic609// when the overload above causes a hard error.610template <class _Key, class _Hash, class _Equal>611int __diagnose_unordered_container_requirements(void*);612 613template <class _Tp, class _Hash, class _Equal, class _Alloc>614class __hash_table {615public:616 using value_type = __get_hash_node_value_type_t<_Tp>;617 using key_type = __get_hash_node_key_type_t<_Tp>;618 619 typedef _Hash hasher;620 typedef _Equal key_equal;621 typedef _Alloc allocator_type;622 623private:624 typedef allocator_traits<allocator_type> __alloc_traits;625 626public:627 typedef value_type& reference;628 typedef const value_type& const_reference;629 typedef typename __alloc_traits::pointer pointer;630 typedef typename __alloc_traits::const_pointer const_pointer;631#ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE632 typedef typename __alloc_traits::size_type size_type;633#else634 using size_type = size_t;635#endif636 using difference_type = ptrdiff_t;637 638public:639 // Create __node640 641 using __void_pointer _LIBCPP_NODEBUG = typename __alloc_traits::void_pointer;642 643 using __node _LIBCPP_NODEBUG = __hash_node<_Tp, __void_pointer>;644 using __node_allocator _LIBCPP_NODEBUG = __rebind_alloc<__alloc_traits, __node>;645 using __node_traits _LIBCPP_NODEBUG = allocator_traits<__node_allocator>;646 using __node_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<__void_pointer, __node>;647 648 using __first_node _LIBCPP_NODEBUG = __hash_node_base<__node_pointer>;649 using __node_base_pointer _LIBCPP_NODEBUG = __rebind_pointer_t<__void_pointer, __first_node>;650 using __next_pointer _LIBCPP_NODEBUG = __node_base_pointer;651 652private:653 // check for sane allocator pointer rebinding semantics. Rebinding the654 // allocator for a new pointer type should be exactly the same as rebinding655 // the pointer using 'pointer_traits'.656 static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,657 "Allocator does not rebind pointers in a sane manner.");658 typedef __rebind_alloc<__node_traits, __first_node> __node_base_allocator;659 typedef allocator_traits<__node_base_allocator> __node_base_traits;660 static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,661 "Allocator does not rebind pointers in a sane manner.");662 663private:664 typedef __rebind_alloc<__node_traits, __next_pointer> __pointer_allocator;665 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;666 typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;667 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;668 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;669 670 // --- Member data begin ---671 __bucket_list __bucket_list_;672 _LIBCPP_COMPRESSED_PAIR(__first_node, __first_node_, __node_allocator, __node_alloc_);673 _LIBCPP_COMPRESSED_PAIR(size_type, __size_, hasher, __hasher_);674 _LIBCPP_COMPRESSED_PAIR(float, __max_load_factor_, key_equal, __key_eq_);675 // --- Member data end ---676 677 _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; }678 679 _LIBCPP_HIDE_FROM_ABI void680 __copy_construct(__next_pointer __other_iter, __next_pointer __own_iter, size_t __current_chash) {681 auto __bucket_count = bucket_count();682 683 for (; __other_iter; __other_iter = __other_iter->__next_) {684 __node_holder __new_node = __construct_node_hash(__other_iter->__hash(), __other_iter->__upcast()->__get_value());685 686 size_t __new_chash = std::__constrain_hash(__new_node->__hash(), __bucket_count);687 if (__new_chash != __current_chash) {688 __bucket_list_[__new_chash] = __own_iter;689 __current_chash = __new_chash;690 }691 692 __own_iter->__next_ = static_cast<__next_pointer>(__new_node.release());693 __own_iter = __own_iter->__next_;694 }695 }696 697 _LIBCPP_HIDE_FROM_ABI void __copy_construct(__next_pointer __other_iter) {698 __next_pointer __own_iter = __first_node_.__ptr();699 {700 __node_holder __new_node = __construct_node_hash(__other_iter->__hash(), __other_iter->__upcast()->__get_value());701 __own_iter->__next_ = static_cast<__next_pointer>(__new_node.release());702 }703 704 size_t __current_chash = std::__constrain_hash(__own_iter->__next_->__hash(), bucket_count());705 __bucket_list_[__current_chash] = __own_iter;706 __other_iter = __other_iter->__next_;707 __own_iter = __own_iter->__next_;708 __copy_construct(__other_iter, __own_iter, __current_chash);709 }710 711public:712 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }713 714 _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT { return __hasher_; }715 _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT { return __hasher_; }716 717 _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT { return __max_load_factor_; }718 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __max_load_factor_; }719 720 _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT { return __key_eq_; }721 _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT { return __key_eq_; }722 723 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __node_alloc_; }724 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __node_alloc_; }725 726public:727 typedef __hash_iterator<__node_pointer> iterator;728 typedef __hash_const_iterator<__node_pointer> const_iterator;729 typedef __hash_local_iterator<__node_pointer> local_iterator;730 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;731 732 _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_(733 is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&734 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&735 is_nothrow_default_constructible<key_equal>::value);736 _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql);737 _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a);738 _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);739 _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);740 _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);741 _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u) _NOEXCEPT_(742 is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&743 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&744 is_nothrow_move_constructible<key_equal>::value);745 _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);746 _LIBCPP_HIDE_FROM_ABI ~__hash_table();747 748 _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);749 _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u)750 _NOEXCEPT_(is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value &&751 ((__node_traits::propagate_on_container_move_assignment::value &&752 is_nothrow_move_assignable<__node_allocator>::value) ||753 allocator_traits<__node_allocator>::is_always_equal::value));754 template <class _InputIterator>755 _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);756 template <class _InputIterator>757 _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);758 759 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {760 return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());761 }762 763private:764 _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val);765 _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT;766 767 _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val);768 _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;769 770public:771 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd);772 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);773 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);774 775 template <class... _Args>776 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {777 return std::__try_key_extraction<key_type>(778 [this](const key_type& __key, _Args&&... __args2) {779 size_t __hash = hash_function()(__key);780 size_type __bc = bucket_count();781 bool __inserted = false;782 __next_pointer __nd;783 size_t __chash;784 if (__bc != 0) {785 __chash = std::__constrain_hash(__hash, __bc);786 __nd = __bucket_list_[__chash];787 if (__nd != nullptr) {788 for (__nd = __nd->__next_;789 __nd != nullptr &&790 (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);791 __nd = __nd->__next_) {792 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __key))793 goto __done;794 }795 }796 }797 {798 __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...);799 if (size() + 1 > __bc * max_load_factor()) {800 __rehash_unique(std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),801 size_type(__math::ceil(float(size() + 1) / max_load_factor()))));802 __bc = bucket_count();803 __chash = std::__constrain_hash(__hash, __bc);804 }805 // insert_after __bucket_list_[__chash], or __first_node if bucket is null806 __next_pointer __pn = __bucket_list_[__chash];807 if (__pn == nullptr) {808 __pn = __first_node_.__ptr();809 __h->__next_ = __pn->__next_;810 __pn->__next_ = __h.get()->__ptr();811 // fix up __bucket_list_812 __bucket_list_[__chash] = __pn;813 if (__h->__next_ != nullptr)814 __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();815 } else {816 __h->__next_ = __pn->__next_;817 __pn->__next_ = static_cast<__next_pointer>(__h.get());818 }819 __nd = static_cast<__next_pointer>(__h.release());820 // increment size821 ++size();822 __inserted = true;823 }824 __done:825 return pair<iterator, bool>(iterator(__nd), __inserted);826 },827 [this](_Args&&... __args2) {828 __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);829 pair<iterator, bool> __r = __node_insert_unique(__h.get());830 if (__r.second)831 __h.release();832 return __r;833 },834 std::forward<_Args>(__args)...);835 }836 837 template <class... _Args>838 _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);839 template <class... _Args>840 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);841 842 template <class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>843 _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(value_type&& __value) {844 __node_holder __h = __construct_node(const_cast<key_type&&>(__value.first), std::move(__value.second));845 __node_insert_unique(__h.get());846 __h.release();847 }848 849 template <class _ValueT = _Tp, __enable_if_t<!__is_hash_value_type<_ValueT>::value, int> = 0>850 _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(value_type&& __value) {851 __node_holder __h = __construct_node(std::move(__value));852 __node_insert_unique(__h.get());853 __h.release();854 }855 856 template <class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>857 _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(value_type&& __value) {858 __node_holder __h = __construct_node(const_cast<key_type&&>(__value.first), std::move(__value.second));859 __node_insert_multi(__h.get());860 __h.release();861 }862 863 template <class _ValueT = _Tp, __enable_if_t<!__is_hash_value_type<_ValueT>::value, int> = 0>864 _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(value_type&& __value) {865 __node_holder __h = __construct_node(std::move(__value));866 __node_insert_multi(__h.get());867 __h.release();868 }869 870#if _LIBCPP_STD_VER >= 17871 template <class _NodeHandle, class _InsertReturnType>872 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);873 template <class _NodeHandle>874 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh);875 template <class _Table>876 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source);877 878 template <class _NodeHandle>879 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh);880 template <class _NodeHandle>881 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);882 template <class _Table>883 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source);884 885 template <class _NodeHandle>886 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key);887 template <class _NodeHandle>888 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it);889#endif890 891 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;892 _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); }893 _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); }894 _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) {895 __rehash_unique(static_cast<size_type>(__math::ceil(__n / max_load_factor())));896 }897 _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) {898 __rehash_multi(static_cast<size_type>(__math::ceil(__n / max_load_factor())));899 }900 901 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); }902 903 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;904 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;905 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;906 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;907 908 template <class _Key>909 _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const {910 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(911 bucket_count() > 0, "unordered container::bucket(key) called when bucket_count() == 0");912 return std::__constrain_hash(hash_function()(__k), bucket_count());913 }914 915 template <class _Key>916 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __x);917 template <class _Key>918 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;919 920 typedef __hash_node_destructor<__node_allocator> _Dp;921 typedef unique_ptr<__node, _Dp> __node_holder;922 923 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);924 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);925 template <class _Key>926 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);927 template <class _Key>928 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);929 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;930 931 template <class _Key>932 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;933 template <class _Key>934 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;935 936 template <class _Key>937 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);938 template <class _Key>939 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;940 941 template <class _Key>942 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);943 template <class _Key>944 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;945 946 _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)947#if _LIBCPP_STD_VER <= 11948 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&949 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||950 __is_nothrow_swappable_v<__pointer_allocator>) &&951 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));952#else953 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>);954#endif955 956 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return max_size(); }957 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;958 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT {959 size_type __bc = bucket_count();960 return __bc != 0 ? (float)size() / __bc : 0.f;961 }962 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT {963 // While passing a non-positive load factor is undefined behavior, in practice the result will be benign (the964 // call will be equivalent to `max_load_factor(load_factor())`, which is also the case for passing a valid value965 // less than the current `load_factor`).966 _LIBCPP_ASSERT_PEDANTIC(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0");967 max_load_factor() = std::max(__mlf, load_factor());968 }969 970 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) {971 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(972 __n < bucket_count(), "unordered container::begin(n) called with n >= bucket_count()");973 return local_iterator(__bucket_list_[__n], __n, bucket_count());974 }975 976 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) {977 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(978 __n < bucket_count(), "unordered container::end(n) called with n >= bucket_count()");979 return local_iterator(nullptr, __n, bucket_count());980 }981 982 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const {983 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(984 __n < bucket_count(), "unordered container::cbegin(n) called with n >= bucket_count()");985 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());986 }987 988 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const {989 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(990 __n < bucket_count(), "unordered container::cend(n) called with n >= bucket_count()");991 return const_local_iterator(nullptr, __n, bucket_count());992 }993 994private:995 template <bool _UniqueKeys>996 _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);997 template <bool _UniqueKeys>998 _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);999 1000 template <class... _Args>1001 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);1002 1003 template <class... _Args>1004 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args);1005 1006 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {1007 __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());1008 }1009 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);1010 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {}1011 1012 _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);1013 _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)1014 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&1015 is_nothrow_move_assignable<key_equal>::value);1016 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_(1017 !__node_traits::propagate_on_container_move_assignment::value ||1018 (is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value)) {1019 __move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());1020 }1021 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_(1022 is_nothrow_move_assignable<__pointer_allocator>::value&& is_nothrow_move_assignable<__node_allocator>::value) {1023 __bucket_list_.get_deleter().__alloc() = std::move(__u.__bucket_list_.get_deleter().__alloc());1024 __node_alloc() = std::move(__u.__node_alloc());1025 }1026 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}1027 1028 _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__node_pointer __nd) _NOEXCEPT {1029 auto& __alloc = __node_alloc();1030 __node_traits::destroy(__alloc, std::addressof(__nd->__get_value()));1031 std::__destroy_at(std::__to_address(__nd));1032 __node_traits::deallocate(__alloc, __nd, 1);1033 }1034 1035 _LIBCPP_HIDE_FROM_ABI void __deallocate_node_list(__next_pointer __np) _NOEXCEPT {1036 while (__np != nullptr) {1037 __next_pointer __next = __np->__next_;1038 __deallocate_node(__np->__upcast());1039 __np = __next;1040 }1041 }1042 1043 _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;1044 1045 template <class _From, class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>1046 _LIBCPP_HIDE_FROM_ABI void __assign_value(__get_hash_node_value_type_t<_Tp>& __lhs, _From&& __rhs) {1047 // This is technically UB, since the object was constructed as `const`.1048 // Clang doesn't optimize on this currently though.1049 const_cast<key_type&>(__lhs.first) = const_cast<__copy_cvref_t<_From, key_type>&&>(__rhs.first);1050 __lhs.second = std::forward<_From>(__rhs).second;1051 }1052 1053 template <class _From, class _ValueT = _Tp, __enable_if_t<!__is_hash_value_type<_ValueT>::value, int> = 0>1054 _LIBCPP_HIDE_FROM_ABI void __assign_value(_Tp& __lhs, _From&& __rhs) {1055 __lhs = std::forward<_From>(__rhs);1056 }1057 1058 template <class, class, class, class, class>1059 friend class unordered_map;1060 template <class, class, class, class, class>1061 friend class unordered_multimap;1062};1063 1064template <class _Tp, class _Hash, class _Equal, class _Alloc>1065inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() _NOEXCEPT_(1066 is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&1067 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&1068 is_nothrow_default_constructible<key_equal>::value)1069 : __size_(0), __max_load_factor_(1.0f) {}1070 1071template <class _Tp, class _Hash, class _Equal, class _Alloc>1072inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, const key_equal& __eql)1073 : __bucket_list_(nullptr, __bucket_list_deleter()),1074 __first_node_(),1075 __node_alloc_(),1076 __size_(0),1077 __hasher_(__hf),1078 __max_load_factor_(1.0f),1079 __key_eq_(__eql) {}1080 1081template <class _Tp, class _Hash, class _Equal, class _Alloc>1082__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(1083 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)1084 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),1085 __node_alloc_(__node_allocator(__a)),1086 __size_(0),1087 __hasher_(__hf),1088 __max_load_factor_(1.0f),1089 __key_eq_(__eql) {}1090 1091template <class _Tp, class _Hash, class _Equal, class _Alloc>1092__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)1093 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),1094 __node_alloc_(__node_allocator(__a)),1095 __size_(0),1096 __max_load_factor_(1.0f) {}1097 1098template <class _Tp, class _Hash, class _Equal, class _Alloc>1099__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __other)1100 : __bucket_list_(nullptr,1101 __bucket_list_deleter(__pointer_alloc_traits::select_on_container_copy_construction(1102 __other.__bucket_list_.get_deleter().__alloc()),1103 0)),1104 __node_alloc_(__node_traits::select_on_container_copy_construction(__other.__node_alloc())),1105 __size_(0),1106 __hasher_(__other.hash_function()),1107 __max_load_factor_(__other.__max_load_factor_),1108 __key_eq_(__other.__key_eq_) {1109 if (__other.size() == 0)1110 return;1111 1112 auto& __bucket_list_del = __bucket_list_.get_deleter();1113 auto __bucket_count = __other.bucket_count();1114 __bucket_list_.reset(__pointer_alloc_traits::allocate(__bucket_list_del.__alloc(), __bucket_count));1115 __bucket_list_del.size() = __bucket_count;1116 1117 std::fill_n(__bucket_list_.get(), __bucket_count, nullptr);1118 1119 __copy_construct(__other.__first_node_.__next_);1120 __size_ = __other.size();1121}1122 1123template <class _Tp, class _Hash, class _Equal, class _Alloc>1124__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, const allocator_type& __a)1125 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),1126 __node_alloc_(__node_allocator(__a)),1127 __size_(0),1128 __hasher_(__u.hash_function()),1129 __max_load_factor_(__u.__max_load_factor_),1130 __key_eq_(__u.__key_eq_) {}1131 1132template <class _Tp, class _Hash, class _Equal, class _Alloc>1133__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) _NOEXCEPT_(1134 is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&1135 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&1136 is_nothrow_move_constructible<key_equal>::value)1137 : __bucket_list_(std::move(__u.__bucket_list_)),1138 __first_node_(std::move(__u.__first_node_)),1139 __node_alloc_(std::move(__u.__node_alloc_)),1140 __size_(std::move(__u.__size_)),1141 __hasher_(std::move(__u.__hasher_)),1142 __max_load_factor_(__u.__max_load_factor_),1143 __key_eq_(std::move(__u.__key_eq_)) {1144 if (size() > 0) {1145 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();1146 __u.__first_node_.__next_ = nullptr;1147 __u.size() = 0;1148 }1149}1150 1151template <class _Tp, class _Hash, class _Equal, class _Alloc>1152__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a)1153 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),1154 __node_alloc_(__node_allocator(__a)),1155 __size_(0),1156 __hasher_(std::move(__u.__hasher_)),1157 __max_load_factor_(__u.__max_load_factor_),1158 __key_eq_(std::move(__u.__key_eq_)) {1159 if (__a == allocator_type(__u.__node_alloc())) {1160 __bucket_list_.reset(__u.__bucket_list_.release());1161 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();1162 __u.__bucket_list_.get_deleter().size() = 0;1163 if (__u.size() > 0) {1164 __first_node_.__next_ = __u.__first_node_.__next_;1165 __u.__first_node_.__next_ = nullptr;1166 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();1167 size() = __u.size();1168 __u.size() = 0;1169 }1170 }1171}1172 1173template <class _Tp, class _Hash, class _Equal, class _Alloc>1174__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {1175#if defined(_LIBCPP_CXX03_LANG)1176 static_assert(is_copy_constructible<key_equal>::value, "Predicate must be copy-constructible.");1177 static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");1178#endif1179 1180 __deallocate_node_list(__first_node_.__next_);1181}1182 1183template <class _Tp, class _Hash, class _Equal, class _Alloc>1184void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(const __hash_table& __u, true_type) {1185 if (__node_alloc() != __u.__node_alloc()) {1186 clear();1187 __bucket_list_.reset();1188 __bucket_list_.get_deleter().size() = 0;1189 }1190 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();1191 __node_alloc() = __u.__node_alloc();1192}1193 1194template <class _Tp, class _Hash, class _Equal, class _Alloc>1195__hash_table<_Tp, _Hash, _Equal, _Alloc>&1196__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other) {1197 if (this == std::addressof(__other))1198 return *this;1199 1200 __copy_assign_alloc(__other);1201 hash_function() = __other.hash_function();1202 key_eq() = __other.key_eq();1203 max_load_factor() = __other.max_load_factor();1204 1205 if (__other.size() == 0) {1206 clear();1207 return *this;1208 }1209 1210 auto __bucket_count = __other.bucket_count();1211 if (__bucket_count != bucket_count()) {1212 auto& __bucket_list_del = __bucket_list_.get_deleter();1213 __bucket_list_.reset(__pointer_alloc_traits::allocate(__bucket_list_del.__alloc(), __bucket_count));1214 __bucket_list_del.size() = __bucket_count;1215 }1216 std::fill_n(__bucket_list_.get(), __bucket_count, nullptr);1217 1218 if (!__first_node_.__next_) {1219 __copy_construct(__other.__first_node_.__next_);1220 __size_ = __other.size();1221 return *this;1222 }1223 1224 __next_pointer __other_iter = __other.__first_node_.__next_;1225 __next_pointer __own_iter = __first_node_.__ptr();1226 {1227 __node_pointer __next = __own_iter->__next_->__upcast();1228 __assign_value(__next->__get_value(), __other_iter->__upcast()->__get_value());1229 __next->__hash_ = __other_iter->__hash();1230 }1231 size_t __current_chash = std::__constrain_hash(__own_iter->__next_->__hash(), __bucket_count);1232 __bucket_list_[__current_chash] = __own_iter;1233 __other_iter = __other_iter->__next_;1234 __own_iter = __own_iter->__next_;1235 1236 // Go through the nodes of the incoming hash table and copy then into the destination hash table, reusing as many1237 // existing nodes as posssible in the destination.1238 while (__other_iter && __own_iter->__next_) {1239 __node_pointer __next = __own_iter->__next_->__upcast();1240 __assign_value(__next->__get_value(), __other_iter->__upcast()->__get_value());1241 __next->__hash_ = __other_iter->__hash();1242 1243 size_t __new_chash = std::__constrain_hash(__next->__hash_, __bucket_count);1244 if (__new_chash != __current_chash) {1245 __bucket_list_[__new_chash] = __own_iter;1246 __current_chash = __new_chash;1247 }1248 1249 __other_iter = __other_iter->__next_;1250 __own_iter = __own_iter->__next_;1251 }1252 1253 // At this point we either have consumed the whole incoming hash table, or we don't have any more nodes to reuse in1254 // the destination. Either continue with constructing new nodes, or deallocate the left over nodes.1255 if (__own_iter->__next_) {1256 __deallocate_node_list(__own_iter->__next_);1257 __own_iter->__next_ = nullptr;1258 } else {1259 __copy_construct(__other_iter, __own_iter, __current_chash);1260 }1261 1262 __size_ = __other.size();1263 1264 return *this;1265}1266 1267template <class _Tp, class _Hash, class _Equal, class _Alloc>1268typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer1269__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {1270 size_type __bc = bucket_count();1271 for (size_type __i = 0; __i < __bc; ++__i)1272 __bucket_list_[__i] = nullptr;1273 size() = 0;1274 __next_pointer __cache = __first_node_.__next_;1275 __first_node_.__next_ = nullptr;1276 return __cache;1277}1278 1279template <class _Tp, class _Hash, class _Equal, class _Alloc>1280void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, true_type)1281 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&1282 is_nothrow_move_assignable<key_equal>::value) {1283 clear();1284 __bucket_list_.reset(__u.__bucket_list_.release());1285 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();1286 __u.__bucket_list_.get_deleter().size() = 0;1287 __move_assign_alloc(__u);1288 size() = __u.size();1289 hash_function() = std::move(__u.hash_function());1290 max_load_factor() = __u.max_load_factor();1291 key_eq() = std::move(__u.key_eq());1292 __first_node_.__next_ = __u.__first_node_.__next_;1293 if (size() > 0) {1294 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();1295 __u.__first_node_.__next_ = nullptr;1296 __u.size() = 0;1297 }1298}1299 1300template <class _Tp, class _Hash, class _Equal, class _Alloc>1301void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, false_type) {1302 if (__node_alloc() == __u.__node_alloc())1303 __move_assign(__u, true_type());1304 else {1305 hash_function() = std::move(__u.hash_function());1306 key_eq() = std::move(__u.key_eq());1307 max_load_factor() = __u.max_load_factor();1308 if (bucket_count() != 0) {1309 __next_pointer __cache = __detach();1310 auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); });1311 const_iterator __i = __u.begin();1312 while (__cache != nullptr && __u.size() != 0) {1313 __assign_value(__cache->__upcast()->__get_value(), std::move(__u.remove(__i++)->__get_value()));1314 __next_pointer __next = __cache->__next_;1315 __node_insert_multi(__cache->__upcast());1316 __cache = __next;1317 }1318 }1319 const_iterator __i = __u.begin();1320 while (__u.size() != 0)1321 __insert_multi_from_orphaned_node(std::move(__u.remove(__i++)->__get_value()));1322 }1323}1324 1325template <class _Tp, class _Hash, class _Equal, class _Alloc>1326inline __hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)1327 _NOEXCEPT_(is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value &&1328 ((__node_traits::propagate_on_container_move_assignment::value &&1329 is_nothrow_move_assignable<__node_allocator>::value) ||1330 allocator_traits<__node_allocator>::is_always_equal::value)) {1331 __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());1332 return *this;1333}1334 1335template <class _Tp, class _Hash, class _Equal, class _Alloc>1336template <class _InputIterator>1337void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, _InputIterator __last) {1338 typedef iterator_traits<_InputIterator> _ITraits;1339 typedef typename _ITraits::value_type _ItValueType;1340 static_assert(1341 is_same<_ItValueType, value_type>::value, "__assign_unique may only be called with the containers value type");1342 1343 if (bucket_count() != 0) {1344 __next_pointer __cache = __detach();1345 auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); });1346 for (; __cache != nullptr && __first != __last; ++__first) {1347 __assign_value(__cache->__upcast()->__get_value(), *__first);1348 __next_pointer __next = __cache->__next_;1349 __node_insert_unique(__cache->__upcast());1350 __cache = __next;1351 }1352 }1353 for (; __first != __last; ++__first)1354 __emplace_unique(*__first);1355}1356 1357template <class _Tp, class _Hash, class _Equal, class _Alloc>1358template <class _InputIterator>1359void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, _InputIterator __last) {1360 typedef iterator_traits<_InputIterator> _ITraits;1361 typedef typename _ITraits::value_type _ItValueType;1362 static_assert(is_same<_ItValueType, value_type>::value,1363 "__assign_multi may only be called with the containers value type or the nodes value type");1364 if (bucket_count() != 0) {1365 __next_pointer __cache = __detach();1366 auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(__cache); });1367 for (; __cache != nullptr && __first != __last; ++__first) {1368 __assign_value(__cache->__upcast()->__get_value(), *__first);1369 __next_pointer __next = __cache->__next_;1370 __node_insert_multi(__cache->__upcast());1371 __cache = __next;1372 }1373 }1374 for (; __first != __last; ++__first)1375 __emplace_multi(*__first);1376}1377 1378template <class _Tp, class _Hash, class _Equal, class _Alloc>1379inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1380__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT {1381 return iterator(__first_node_.__next_);1382}1383 1384template <class _Tp, class _Hash, class _Equal, class _Alloc>1385inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1386__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT {1387 return iterator(nullptr);1388}1389 1390template <class _Tp, class _Hash, class _Equal, class _Alloc>1391inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator1392__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT {1393 return const_iterator(__first_node_.__next_);1394}1395 1396template <class _Tp, class _Hash, class _Equal, class _Alloc>1397inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator1398__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {1399 return const_iterator(nullptr);1400}1401 1402template <class _Tp, class _Hash, class _Equal, class _Alloc>1403void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {1404 if (size() > 0) {1405 __deallocate_node_list(__first_node_.__next_);1406 __first_node_.__next_ = nullptr;1407 size_type __bc = bucket_count();1408 for (size_type __i = 0; __i < __bc; ++__i)1409 __bucket_list_[__i] = nullptr;1410 size() = 0;1411 }1412}1413 1414// Prepare the container for an insertion of the value __value with the hash1415// __hash. This does a lookup into the container to see if __value is already1416// present, and performs a rehash if necessary. Returns a pointer to the1417// existing element if it exists, otherwise nullptr.1418//1419// Note that this function does forward exceptions if key_eq() throws, and never1420// mutates __value or actually inserts into the map.1421template <class _Tp, class _Hash, class _Equal, class _Alloc>1422_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer1423__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {1424 size_type __bc = bucket_count();1425 1426 if (__bc != 0) {1427 size_t __chash = std::__constrain_hash(__hash, __bc);1428 __next_pointer __ndptr = __bucket_list_[__chash];1429 if (__ndptr != nullptr) {1430 for (__ndptr = __ndptr->__next_;1431 __ndptr != nullptr &&1432 (__ndptr->__hash() == __hash || std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);1433 __ndptr = __ndptr->__next_) {1434 if ((__ndptr->__hash() == __hash) && key_eq()(__ndptr->__upcast()->__get_value(), __value))1435 return __ndptr;1436 }1437 }1438 }1439 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {1440 __rehash_unique(std::max<size_type>(1441 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));1442 }1443 return nullptr;1444}1445 1446// Insert the node __nd into the container by pushing it into the right bucket,1447// and updating size(). Assumes that __nd->__hash is up-to-date, and that1448// rehashing has already occurred and that no element with the same key exists1449// in the map.1450template <class _Tp, class _Hash, class _Equal, class _Alloc>1451_LIBCPP_HIDE_FROM_ABI void1452__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {1453 size_type __bc = bucket_count();1454 size_t __chash = std::__constrain_hash(__nd->__hash(), __bc);1455 // insert_after __bucket_list_[__chash], or __first_node if bucket is null1456 __next_pointer __pn = __bucket_list_[__chash];1457 if (__pn == nullptr) {1458 __pn = __first_node_.__ptr();1459 __nd->__next_ = __pn->__next_;1460 __pn->__next_ = __nd->__ptr();1461 // fix up __bucket_list_1462 __bucket_list_[__chash] = __pn;1463 if (__nd->__next_ != nullptr)1464 __bucket_list_[std::__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();1465 } else {1466 __nd->__next_ = __pn->__next_;1467 __pn->__next_ = __nd->__ptr();1468 }1469 ++size();1470}1471 1472template <class _Tp, class _Hash, class _Equal, class _Alloc>1473pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>1474__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) {1475 __nd->__hash_ = hash_function()(__nd->__get_value());1476 __next_pointer __existing_node = __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value());1477 1478 // Insert the node, unless it already exists in the container.1479 bool __inserted = false;1480 if (__existing_node == nullptr) {1481 __node_insert_unique_perform(__nd);1482 __existing_node = __nd->__ptr();1483 __inserted = true;1484 }1485 return pair<iterator, bool>(iterator(__existing_node), __inserted);1486}1487 1488// Prepare the container for an insertion of the value __cp_val with the hash1489// __cp_hash. This does a lookup into the container to see if __cp_value is1490// already present, and performs a rehash if necessary. Returns a pointer to the1491// last occurrence of __cp_val in the map.1492//1493// Note that this function does forward exceptions if key_eq() throws, and never1494// mutates __value or actually inserts into the map.1495template <class _Tp, class _Hash, class _Equal, class _Alloc>1496typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer1497__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {1498 size_type __bc = bucket_count();1499 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {1500 __rehash_multi(std::max<size_type>(1501 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));1502 __bc = bucket_count();1503 }1504 size_t __chash = std::__constrain_hash(__cp_hash, __bc);1505 __next_pointer __pn = __bucket_list_[__chash];1506 if (__pn != nullptr) {1507 for (bool __found = false;1508 __pn->__next_ != nullptr && std::__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;1509 __pn = __pn->__next_) {1510 // __found key_eq() action1511 // false false loop1512 // true true loop1513 // false true set __found to true1514 // true false break1515 if (__found !=1516 (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) {1517 if (!__found)1518 __found = true;1519 else1520 break;1521 }1522 }1523 }1524 return __pn;1525}1526 1527// Insert the node __cp into the container after __pn (which is the last node in1528// the bucket that compares equal to __cp). Rehashing, and checking for1529// uniqueness has already been performed (in __node_insert_multi_prepare), so1530// all we need to do is update the bucket and size(). Assumes that __cp->__hash1531// is up-to-date.1532template <class _Tp, class _Hash, class _Equal, class _Alloc>1533void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(1534 __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {1535 size_type __bc = bucket_count();1536 size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);1537 if (__pn == nullptr) {1538 __pn = __first_node_.__ptr();1539 __cp->__next_ = __pn->__next_;1540 __pn->__next_ = __cp->__ptr();1541 // fix up __bucket_list_1542 __bucket_list_[__chash] = __pn;1543 if (__cp->__next_ != nullptr)1544 __bucket_list_[std::__constrain_hash(__cp->__next_->__hash(), __bc)] = __cp->__ptr();1545 } else {1546 __cp->__next_ = __pn->__next_;1547 __pn->__next_ = __cp->__ptr();1548 if (__cp->__next_ != nullptr) {1549 size_t __nhash = std::__constrain_hash(__cp->__next_->__hash(), __bc);1550 if (__nhash != __chash)1551 __bucket_list_[__nhash] = __cp->__ptr();1552 }1553 }1554 ++size();1555}1556 1557template <class _Tp, class _Hash, class _Equal, class _Alloc>1558typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1559__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) {1560 __cp->__hash_ = hash_function()(__cp->__get_value());1561 __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value());1562 __node_insert_multi_perform(__cp, __pn);1563 1564 return iterator(__cp->__ptr());1565}1566 1567template <class _Tp, class _Hash, class _Equal, class _Alloc>1568typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1569__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {1570 if (__p != end() && key_eq()(*__p, __cp->__get_value())) {1571 __next_pointer __np = __p.__node_;1572 __cp->__hash_ = __np->__hash();1573 size_type __bc = bucket_count();1574 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {1575 __rehash_multi(std::max<size_type>(1576 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));1577 __bc = bucket_count();1578 }1579 size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);1580 __next_pointer __pp = __bucket_list_[__chash];1581 while (__pp->__next_ != __np)1582 __pp = __pp->__next_;1583 __cp->__next_ = __np;1584 __pp->__next_ = static_cast<__next_pointer>(__cp);1585 ++size();1586 return iterator(static_cast<__next_pointer>(__cp));1587 }1588 return __node_insert_multi(__cp);1589}1590 1591template <class _Tp, class _Hash, class _Equal, class _Alloc>1592template <class... _Args>1593typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1594__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {1595 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1596 iterator __r = __node_insert_multi(__h.get());1597 __h.release();1598 return __r;1599}1600 1601template <class _Tp, class _Hash, class _Equal, class _Alloc>1602template <class... _Args>1603typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1604__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {1605 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);1606 iterator __r = __node_insert_multi(__p, __h.get());1607 __h.release();1608 return __r;1609}1610 1611#if _LIBCPP_STD_VER >= 171612template <class _Tp, class _Hash, class _Equal, class _Alloc>1613template <class _NodeHandle, class _InsertReturnType>1614_LIBCPP_HIDE_FROM_ABI _InsertReturnType1615__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(_NodeHandle&& __nh) {1616 if (__nh.empty())1617 return _InsertReturnType{end(), false, _NodeHandle()};1618 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);1619 if (__result.second)1620 __nh.__release_ptr();1621 return _InsertReturnType{__result.first, __result.second, std::move(__nh)};1622}1623 1624template <class _Tp, class _Hash, class _Equal, class _Alloc>1625template <class _NodeHandle>1626_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1627__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {1628 if (__nh.empty())1629 return end();1630 pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);1631 if (__result.second)1632 __nh.__release_ptr();1633 return __result.first;1634}1635 1636template <class _Tp, class _Hash, class _Equal, class _Alloc>1637template <class _NodeHandle>1638_LIBCPP_HIDE_FROM_ABI _NodeHandle1639__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(key_type const& __key) {1640 iterator __i = find(__key);1641 if (__i == end())1642 return _NodeHandle();1643 return __node_handle_extract<_NodeHandle>(__i);1644}1645 1646template <class _Tp, class _Hash, class _Equal, class _Alloc>1647template <class _NodeHandle>1648_LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(const_iterator __p) {1649 allocator_type __alloc(__node_alloc());1650 return _NodeHandle(remove(__p).release(), __alloc);1651}1652 1653template <class _Tp, class _Hash, class _Equal, class _Alloc>1654template <class _Table>1655_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(_Table& __source) {1656 static_assert(is_same<__node, typename _Table::__node>::value, "");1657 1658 for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {1659 __node_pointer __src_ptr = __it.__node_->__upcast();1660 size_t __hash = hash_function()(__src_ptr->__get_value());1661 __next_pointer __existing_node = __node_insert_unique_prepare(__hash, __src_ptr->__get_value());1662 auto __prev_iter = __it++;1663 if (__existing_node == nullptr) {1664 (void)__source.remove(__prev_iter).release();1665 __src_ptr->__hash_ = __hash;1666 __node_insert_unique_perform(__src_ptr);1667 }1668 }1669}1670 1671template <class _Tp, class _Hash, class _Equal, class _Alloc>1672template <class _NodeHandle>1673_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1674__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(_NodeHandle&& __nh) {1675 if (__nh.empty())1676 return end();1677 iterator __result = __node_insert_multi(__nh.__ptr_);1678 __nh.__release_ptr();1679 return __result;1680}1681 1682template <class _Tp, class _Hash, class _Equal, class _Alloc>1683template <class _NodeHandle>1684_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1685__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {1686 if (__nh.empty())1687 return end();1688 iterator __result = __node_insert_multi(__hint, __nh.__ptr_);1689 __nh.__release_ptr();1690 return __result;1691}1692 1693template <class _Tp, class _Hash, class _Equal, class _Alloc>1694template <class _Table>1695_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(_Table& __source) {1696 static_assert(is_same<typename _Table::__node, __node>::value, "");1697 1698 for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {1699 __node_pointer __src_ptr = __it.__node_->__upcast();1700 size_t __src_hash = hash_function()(__src_ptr->__get_value());1701 __next_pointer __pn = __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value());1702 (void)__source.remove(__it++).release();1703 __src_ptr->__hash_ = __src_hash;1704 __node_insert_multi_perform(__src_ptr, __pn);1705 }1706}1707#endif // _LIBCPP_STD_VER >= 171708 1709template <class _Tp, class _Hash, class _Equal, class _Alloc>1710template <bool _UniqueKeys>1711void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {1712 if (__n == 1)1713 __n = 2;1714 else if (__n & (__n - 1))1715 __n = std::__next_prime(__n);1716 size_type __bc = bucket_count();1717 if (__n > __bc)1718 __do_rehash<_UniqueKeys>(__n);1719 else if (__n < __bc) {1720 __n = std::max<size_type>(1721 __n,1722 std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(__math::ceil(float(size()) / max_load_factor())))1723 : std::__next_prime(size_t(__math::ceil(float(size()) / max_load_factor()))));1724 if (__n < __bc)1725 __do_rehash<_UniqueKeys>(__n);1726 }1727}1728 1729template <class _Tp, class _Hash, class _Equal, class _Alloc>1730template <bool _UniqueKeys>1731void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __bucket_count) {1732 __pointer_allocator& __ptr_alloc = __bucket_list_.get_deleter().__alloc();1733 __bucket_list_.reset(__bucket_count > 0 ? __pointer_alloc_traits::allocate(__ptr_alloc, __bucket_count) : nullptr);1734 __bucket_list_.get_deleter().size() = __bucket_count;1735 1736 if (__bucket_count == 0)1737 return;1738 1739 for (size_type __i = 0; __i < __bucket_count; ++__i)1740 __bucket_list_[__i] = nullptr;1741 __next_pointer __pp = __first_node_.__ptr();1742 __next_pointer __cp = __pp->__next_;1743 1744 if (!__cp)1745 return;1746 1747 size_type __chash = std::__constrain_hash(__cp->__hash(), __bucket_count);1748 __bucket_list_[__chash] = __pp;1749 size_type __phash = __chash;1750 for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {1751 __chash = std::__constrain_hash(__cp->__hash(), __bucket_count);1752 if (__chash == __phash)1753 __pp = __cp;1754 else {1755 if (__bucket_list_[__chash] == nullptr) {1756 __bucket_list_[__chash] = __pp;1757 __pp = __cp;1758 __phash = __chash;1759 } else {1760 __next_pointer __np = __cp;1761 if _LIBCPP_CONSTEXPR (!_UniqueKeys) {1762 for (; __np->__next_ != nullptr &&1763 key_eq()(__cp->__upcast()->__get_value(), __np->__next_->__upcast()->__get_value());1764 __np = __np->__next_)1765 ;1766 }1767 __pp->__next_ = __np->__next_;1768 __np->__next_ = __bucket_list_[__chash]->__next_;1769 __bucket_list_[__chash]->__next_ = __cp;1770 }1771 }1772 }1773}1774 1775template <class _Tp, class _Hash, class _Equal, class _Alloc>1776template <class _Key>1777typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1778__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) {1779 size_type __bc = bucket_count();1780 if (__bc != 0 && size() != 0) {1781 size_t __hash = hash_function()(__k);1782 size_t __chash = std::__constrain_hash(__hash, __bc);1783 __next_pointer __nd = __bucket_list_[__chash];1784 if (__nd != nullptr) {1785 for (__nd = __nd->__next_;1786 __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);1787 __nd = __nd->__next_) {1788 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))1789 return iterator(__nd);1790 }1791 }1792 }1793 return end();1794}1795 1796template <class _Tp, class _Hash, class _Equal, class _Alloc>1797template <class _Key>1798typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator1799__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const {1800 size_type __bc = bucket_count();1801 if (__bc != 0 && size() != 0) {1802 size_t __hash = hash_function()(__k);1803 size_t __chash = std::__constrain_hash(__hash, __bc);1804 __next_pointer __nd = __bucket_list_[__chash];1805 if (__nd != nullptr) {1806 for (__nd = __nd->__next_;1807 __nd != nullptr && (__hash == __nd->__hash() || std::__constrain_hash(__nd->__hash(), __bc) == __chash);1808 __nd = __nd->__next_) {1809 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))1810 return const_iterator(__nd);1811 }1812 }1813 }1814 return end();1815}1816 1817template <class _Tp, class _Hash, class _Equal, class _Alloc>1818template <class... _Args>1819typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder1820__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {1821 static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");1822 __node_allocator& __na = __node_alloc();1823 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1824 1825 // Begin the lifetime of the node itself and the value_type contained within.1826 //1827 // We don't use the allocator's construct() method to construct the node itself since the1828 // Cpp17FooInsertable named requirements don't require the allocator's construct() method1829 // to work on anything other than the value_type.1830 std::__construct_at(std::addressof(*__h), /* hash = */ 0, __na, std::forward<_Args>(__args)...);1831 1832 __h.get_deleter().__value_constructed = true;1833 1834 __h->__hash_ = hash_function()(__h->__get_value());1835 return __h;1836}1837 1838template <class _Tp, class _Hash, class _Equal, class _Alloc>1839template <class... _Args>1840typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder1841__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _Args&&... __args) {1842 static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");1843 __node_allocator& __na = __node_alloc();1844 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));1845 std::__construct_at(std::addressof(*__h), /* hash = */ __hash, __na, std::forward<_Args>(__args)...);1846 __h.get_deleter().__value_constructed = true;1847 return __h;1848}1849 1850template <class _Tp, class _Hash, class _Equal, class _Alloc>1851typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1852__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {1853 __next_pointer __np = __p.__node_;1854 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(1855 __p != end(), "unordered container::erase(iterator) called with a non-dereferenceable iterator");1856 iterator __r(__np);1857 ++__r;1858 remove(__p);1859 return __r;1860}1861 1862template <class _Tp, class _Hash, class _Equal, class _Alloc>1863typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator1864__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {1865 if (__first == __last)1866 return iterator(__last.__node_);1867 1868 // current node1869 __next_pointer __current = __first.__node_;1870 size_type __bucket_count = bucket_count();1871 size_t __chash = std::__constrain_hash(__current->__hash(), __bucket_count);1872 // find previous node1873 __next_pointer __before_first = __bucket_list_[__chash];1874 for (; __before_first->__next_ != __current; __before_first = __before_first->__next_)1875 ;1876 1877 __next_pointer __last_node = __last.__node_;1878 1879 // If __before_first is in the same bucket (i.e. the first element we erase is not the first in the bucket), clear1880 // this bucket first without re-linking it1881 if (__before_first != __first_node_.__ptr() &&1882 std::__constrain_hash(__before_first->__hash(), __bucket_count) == __chash) {1883 while (__current != __last_node) {1884 auto __next = __current->__next_;1885 __deallocate_node(__current->__upcast());1886 __current = __next;1887 --__size_;1888 1889 if (__next) {1890 if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) {1891 __bucket_list_[__next_chash] = __before_first;1892 __chash = __next_chash;1893 break;1894 }1895 }1896 }1897 }1898 1899 while (__current != __last_node) {1900 auto __next = __current->__next_;1901 __deallocate_node(__current->__upcast());1902 __current = __next;1903 --__size_;1904 1905 // When switching buckets, set the old bucket to be empty and update the next bucket to have __before_first as its1906 // before-first element1907 if (__next) {1908 if (auto __next_chash = std::__constrain_hash(__next->__hash(), __bucket_count); __next_chash != __chash) {1909 __bucket_list_[__chash] = nullptr;1910 __bucket_list_[__next_chash] = __before_first;1911 __chash = __next_chash;1912 }1913 } else { // When __next is a nullptr we've fully erased the last bucket. Update the bucket list accordingly.1914 __bucket_list_[__chash] = nullptr;1915 }1916 }1917 1918 // re-link __before_first with __last1919 __before_first->__next_ = __current;1920 1921 return iterator(__last.__node_);1922}1923 1924template <class _Tp, class _Hash, class _Equal, class _Alloc>1925template <class _Key>1926typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type1927__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) {1928 iterator __i = find(__k);1929 if (__i == end())1930 return 0;1931 erase(__i);1932 return 1;1933}1934 1935template <class _Tp, class _Hash, class _Equal, class _Alloc>1936template <class _Key>1937typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type1938__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) {1939 size_type __r = 0;1940 iterator __i = find(__k);1941 if (__i != end()) {1942 iterator __e = end();1943 do {1944 erase(__i++);1945 ++__r;1946 } while (__i != __e && key_eq()(*__i, __k));1947 }1948 return __r;1949}1950 1951template <class _Tp, class _Hash, class _Equal, class _Alloc>1952typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder1953__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT {1954 // current node1955 __next_pointer __cn = __p.__node_;1956 size_type __bc = bucket_count();1957 size_t __chash = std::__constrain_hash(__cn->__hash(), __bc);1958 // find previous node1959 __next_pointer __pn = __bucket_list_[__chash];1960 for (; __pn->__next_ != __cn; __pn = __pn->__next_)1961 ;1962 // Fix up __bucket_list_1963 // if __pn is not in same bucket (before begin is not in same bucket) &&1964 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)1965 if (__pn == __first_node_.__ptr() || std::__constrain_hash(__pn->__hash(), __bc) != __chash) {1966 if (__cn->__next_ == nullptr || std::__constrain_hash(__cn->__next_->__hash(), __bc) != __chash)1967 __bucket_list_[__chash] = nullptr;1968 }1969 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)1970 if (__cn->__next_ != nullptr) {1971 size_t __nhash = std::__constrain_hash(__cn->__next_->__hash(), __bc);1972 if (__nhash != __chash)1973 __bucket_list_[__nhash] = __pn;1974 }1975 // remove __cn1976 __pn->__next_ = __cn->__next_;1977 __cn->__next_ = nullptr;1978 --size();1979 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));1980}1981 1982template <class _Tp, class _Hash, class _Equal, class _Alloc>1983template <class _Key>1984inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type1985__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const {1986 return static_cast<size_type>(find(__k) != end());1987}1988 1989template <class _Tp, class _Hash, class _Equal, class _Alloc>1990template <class _Key>1991typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type1992__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const {1993 size_type __r = 0;1994 const_iterator __i = find(__k);1995 if (__i != end()) {1996 const_iterator __e = end();1997 do {1998 ++__i;1999 ++__r;2000 } while (__i != __e && key_eq()(*__i, __k));2001 }2002 return __r;2003}2004 2005template <class _Tp, class _Hash, class _Equal, class _Alloc>2006template <class _Key>2007pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,2008 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>2009__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) {2010 iterator __i = find(__k);2011 iterator __j = __i;2012 if (__i != end())2013 ++__j;2014 return pair<iterator, iterator>(__i, __j);2015}2016 2017template <class _Tp, class _Hash, class _Equal, class _Alloc>2018template <class _Key>2019pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,2020 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>2021__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) const {2022 const_iterator __i = find(__k);2023 const_iterator __j = __i;2024 if (__i != end())2025 ++__j;2026 return pair<const_iterator, const_iterator>(__i, __j);2027}2028 2029template <class _Tp, class _Hash, class _Equal, class _Alloc>2030template <class _Key>2031pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,2032 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>2033__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) {2034 iterator __i = find(__k);2035 iterator __j = __i;2036 if (__i != end()) {2037 iterator __e = end();2038 do {2039 ++__j;2040 } while (__j != __e && key_eq()(*__j, __k));2041 }2042 return pair<iterator, iterator>(__i, __j);2043}2044 2045template <class _Tp, class _Hash, class _Equal, class _Alloc>2046template <class _Key>2047pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,2048 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>2049__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) const {2050 const_iterator __i = find(__k);2051 const_iterator __j = __i;2052 if (__i != end()) {2053 const_iterator __e = end();2054 do {2055 ++__j;2056 } while (__j != __e && key_eq()(*__j, __k));2057 }2058 return pair<const_iterator, const_iterator>(__i, __j);2059}2060 2061template <class _Tp, class _Hash, class _Equal, class _Alloc>2062void __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)2063#if _LIBCPP_STD_VER <= 112064 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&2065 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||2066 __is_nothrow_swappable_v<__pointer_allocator>) &&2067 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))2068#else2069 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>)2070#endif2071{2072 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(2073 __node_traits::propagate_on_container_swap::value || this->__node_alloc() == __u.__node_alloc(),2074 "unordered container::swap: Either propagate_on_container_swap "2075 "must be true or the allocators must compare equal");2076 {2077 __node_pointer_pointer __npp = __bucket_list_.release();2078 __bucket_list_.reset(__u.__bucket_list_.release());2079 __u.__bucket_list_.reset(__npp);2080 }2081 std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());2082 std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc());2083 std::__swap_allocator(__node_alloc(), __u.__node_alloc());2084 std::swap(__first_node_.__next_, __u.__first_node_.__next_);2085 using std::swap;2086 swap(__size_, __u.__size_);2087 swap(__hasher_, __u.__hasher_);2088 swap(__max_load_factor_, __u.__max_load_factor_);2089 swap(__key_eq_, __u.__key_eq_);2090 if (size() > 0)2091 __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();2092 if (__u.size() > 0)2093 __u.__bucket_list_[std::__constrain_hash(__u.__first_node_.__next_->__hash(), __u.bucket_count())] =2094 __u.__first_node_.__ptr();2095}2096 2097template <class _Tp, class _Hash, class _Equal, class _Alloc>2098typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type2099__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const {2100 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(2101 __n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");2102 __next_pointer __np = __bucket_list_[__n];2103 size_type __bc = bucket_count();2104 size_type __r = 0;2105 if (__np != nullptr) {2106 for (__np = __np->__next_; __np != nullptr && std::__constrain_hash(__np->__hash(), __bc) == __n;2107 __np = __np->__next_, (void)++__r)2108 ;2109 }2110 return __r;2111}2112 2113template <class _Tp, class _Hash, class _Equal, class _Alloc>2114inline _LIBCPP_HIDE_FROM_ABI void2115swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)2116 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {2117 __x.swap(__y);2118}2119 2120_LIBCPP_END_NAMESPACE_STD2121 2122_LIBCPP_POP_MACROS2123 2124#endif // _LIBCPP___HASH_TABLE2125