[rtsan] Remove mkfifoat interceptor (#116997)
[llvm-project.git] / libcxx / include / __hash_table
bloba0c72f4c205413d6fb47c24fd9d051126b46da7e
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-exception
7 //
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP___HASH_TABLE
11 #define _LIBCPP___HASH_TABLE
13 #include <__algorithm/max.h>
14 #include <__algorithm/min.h>
15 #include <__assert>
16 #include <__bit/countl.h>
17 #include <__config>
18 #include <__cstddef/ptrdiff_t.h>
19 #include <__functional/hash.h>
20 #include <__iterator/iterator_traits.h>
21 #include <__math/rounding_functions.h>
22 #include <__memory/addressof.h>
23 #include <__memory/allocator_traits.h>
24 #include <__memory/compressed_pair.h>
25 #include <__memory/construct_at.h>
26 #include <__memory/pointer_traits.h>
27 #include <__memory/swap_allocator.h>
28 #include <__memory/unique_ptr.h>
29 #include <__type_traits/can_extract_key.h>
30 #include <__type_traits/conditional.h>
31 #include <__type_traits/enable_if.h>
32 #include <__type_traits/invoke.h>
33 #include <__type_traits/is_const.h>
34 #include <__type_traits/is_constructible.h>
35 #include <__type_traits/is_nothrow_assignable.h>
36 #include <__type_traits/is_nothrow_constructible.h>
37 #include <__type_traits/is_pointer.h>
38 #include <__type_traits/is_reference.h>
39 #include <__type_traits/is_same.h>
40 #include <__type_traits/is_swappable.h>
41 #include <__type_traits/remove_const.h>
42 #include <__type_traits/remove_cvref.h>
43 #include <__utility/forward.h>
44 #include <__utility/move.h>
45 #include <__utility/pair.h>
46 #include <__utility/swap.h>
47 #include <cstring>
48 #include <limits>
49 #include <new> // __launder
51 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
52 #  pragma GCC system_header
53 #endif
55 _LIBCPP_PUSH_MACROS
56 #include <__undef_macros>
58 _LIBCPP_BEGIN_NAMESPACE_STD
60 template <class _Key, class _Tp>
61 struct __hash_value_type;
63 template <class _Tp>
64 struct __is_hash_value_type_imp : false_type {};
66 template <class _Key, class _Value>
67 struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
69 template <class... _Args>
70 struct __is_hash_value_type : false_type {};
72 template <class _One>
73 struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};
75 _LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);
77 template <class _NodePtr>
78 struct __hash_node_base {
79   typedef typename pointer_traits<_NodePtr>::element_type __node_type;
80   typedef __hash_node_base __first_node;
81   typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;
82   typedef _NodePtr __node_pointer;
83   typedef __node_base_pointer __next_pointer;
85 // TODO(LLVM 22): Remove this check
86 #ifndef _LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB
87   static_assert(sizeof(__node_base_pointer) == sizeof(__node_pointer) && _LIBCPP_ALIGNOF(__node_base_pointer) ==
88                     _LIBCPP_ALIGNOF(__node_pointer),
89                 "It looks like you are using std::__hash_table (an implementation detail for the unordered containers) "
90                 "with a fancy pointer type that thas a different representation depending on whether it points to a "
91                 "__hash_table base pointer or a __hash_table node pointer (both of which are implementation details of "
92                 "the standard library). This means that your ABI is being broken between LLVM 19 and LLVM 20. If you "
93                 "don't care about your ABI being broken, define the _LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB macro to "
94                 "silence this diagnostic.");
95 #endif
97   __next_pointer __next_;
99   _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT {
100     return static_cast<__next_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
101   }
103   _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT {
104     return static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
105   }
107   _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; }
109   _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
110   _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}
113 template <class _Tp, class _VoidPtr>
114 struct __hash_node : public __hash_node_base< __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > {
115   typedef _Tp __node_value_type;
116   using _Base          = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;
117   using __next_pointer = typename _Base::__next_pointer;
119   size_t __hash_;
121   // We allow starting the lifetime of nodes without initializing the value held by the node,
122   // since that is handled by the hash table itself in order to be allocator-aware.
123 #ifndef _LIBCPP_CXX03_LANG
125 private:
126   union {
127     _Tp __value_;
128   };
130 public:
131   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
132 #else
134 private:
135   _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
137 public:
138   _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
139 #endif
141   _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {}
142   _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}
145 inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); }
147 inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) {
148   return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc);
151 inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) {
152   return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n - 1)));
155 template <class _Tp, class _Hash, class _Equal, class _Alloc>
156 class __hash_table;
158 template <class _NodePtr>
159 class _LIBCPP_TEMPLATE_VIS __hash_iterator;
160 template <class _ConstNodePtr>
161 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
162 template <class _NodePtr>
163 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
164 template <class _ConstNodePtr>
165 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
166 template <class _HashIterator>
167 class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
168 template <class _HashIterator>
169 class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
171 template <class _Tp>
172 struct __hash_key_value_types {
173   static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
174   typedef _Tp key_type;
175   typedef _Tp __node_value_type;
176   typedef _Tp __container_value_type;
177   static const bool __is_map = false;
179   _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; }
180   _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; }
181   _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { return std::addressof(__n); }
182   _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { return std::move(__v); }
185 template <class _Key, class _Tp>
186 struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
187   typedef _Key key_type;
188   typedef _Tp mapped_type;
189   typedef __hash_value_type<_Key, _Tp> __node_value_type;
190   typedef pair<const _Key, _Tp> __container_value_type;
191   typedef __container_value_type __map_value_type;
192   static const bool __is_map = true;
194   _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__container_value_type const& __v) { return __v.first; }
196   template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0>
197   _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
198     return __t.__get_value();
199   }
201   template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>
202   _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
203     return __t;
204   }
206   _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) {
207     return std::addressof(__n.__get_value());
208   }
209   _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); }
212 template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, bool = _KVTypes::__is_map>
213 struct __hash_map_pointer_types {};
215 template <class _Tp, class _AllocPtr, class _KVTypes>
216 struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
217   typedef typename _KVTypes::__map_value_type _Mv;
218   typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer;
219   typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer;
222 template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
223 struct __hash_node_types;
225 template <class _NodePtr, class _Tp, class _VoidPtr>
226 struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
227     : public __hash_key_value_types<_Tp>,
228       __hash_map_pointer_types<_Tp, _VoidPtr>
231   typedef __hash_key_value_types<_Tp> __base;
233 public:
234   typedef ptrdiff_t difference_type;
235   typedef size_t size_type;
237   typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
239   typedef typename pointer_traits<_NodePtr>::element_type __node_type;
240   typedef _NodePtr __node_pointer;
242   typedef __hash_node_base<__node_pointer> __node_base_type;
243   typedef __rebind_pointer_t<_NodePtr, __node_base_type> __node_base_pointer;
245   typedef typename __node_base_type::__next_pointer __next_pointer;
247   typedef _Tp __node_value_type;
248   typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer;
249   typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer;
251 private:
252   static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");
253   static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,
254                 "_VoidPtr does not point to unqualified void type");
255   static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,
256                 "_VoidPtr does not rebind to _NodePtr.");
259 template <class _HashIterator>
260 struct __hash_node_types_from_iterator;
261 template <class _NodePtr>
262 struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
263 template <class _NodePtr>
264 struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
265 template <class _NodePtr>
266 struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
267 template <class _NodePtr>
268 struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
270 template <class _NodeValueTp, class _VoidPtr>
271 struct __make_hash_node_types {
272   typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
273   typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr;
274   typedef __hash_node_types<_NodePtr> type;
277 template <class _NodePtr>
278 class _LIBCPP_TEMPLATE_VIS __hash_iterator {
279   typedef __hash_node_types<_NodePtr> _NodeTypes;
280   typedef _NodePtr __node_pointer;
281   typedef typename _NodeTypes::__next_pointer __next_pointer;
283   __next_pointer __node_;
285 public:
286   typedef forward_iterator_tag iterator_category;
287   typedef typename _NodeTypes::__node_value_type value_type;
288   typedef typename _NodeTypes::difference_type difference_type;
289   typedef value_type& reference;
290   typedef typename _NodeTypes::__node_value_type_pointer pointer;
292   _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {}
294   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
295     _LIBCPP_ASSERT_NON_NULL(
296         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
297     return __node_->__upcast()->__get_value();
298   }
300   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
301     _LIBCPP_ASSERT_NON_NULL(
302         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
303     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
304   }
306   _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() {
307     _LIBCPP_ASSERT_NON_NULL(
308         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container iterator");
309     __node_ = __node_->__next_;
310     return *this;
311   }
313   _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) {
314     __hash_iterator __t(*this);
315     ++(*this);
316     return __t;
317   }
319   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) {
320     return __x.__node_ == __y.__node_;
321   }
322   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {
323     return !(__x == __y);
324   }
326 private:
327   _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
329   template <class, class, class, class>
330   friend class __hash_table;
331   template <class>
332   friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
333   template <class>
334   friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
335   template <class, class, class, class, class>
336   friend class _LIBCPP_TEMPLATE_VIS unordered_map;
337   template <class, class, class, class, class>
338   friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
341 template <class _NodePtr>
342 class _LIBCPP_TEMPLATE_VIS __hash_const_iterator {
343   static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
344   typedef __hash_node_types<_NodePtr> _NodeTypes;
345   typedef _NodePtr __node_pointer;
346   typedef typename _NodeTypes::__next_pointer __next_pointer;
348   __next_pointer __node_;
350 public:
351   typedef __hash_iterator<_NodePtr> __non_const_iterator;
353   typedef forward_iterator_tag iterator_category;
354   typedef typename _NodeTypes::__node_value_type value_type;
355   typedef typename _NodeTypes::difference_type difference_type;
356   typedef const value_type& reference;
357   typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
359   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {}
361   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) {}
363   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
364     _LIBCPP_ASSERT_NON_NULL(
365         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
366     return __node_->__upcast()->__get_value();
367   }
368   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
369     _LIBCPP_ASSERT_NON_NULL(
370         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
371     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
372   }
374   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() {
375     _LIBCPP_ASSERT_NON_NULL(
376         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_iterator");
377     __node_ = __node_->__next_;
378     return *this;
379   }
381   _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) {
382     __hash_const_iterator __t(*this);
383     ++(*this);
384     return __t;
385   }
387   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
388     return __x.__node_ == __y.__node_;
389   }
390   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
391     return !(__x == __y);
392   }
394 private:
395   _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
397   template <class, class, class, class>
398   friend class __hash_table;
399   template <class>
400   friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
401   template <class, class, class, class, class>
402   friend class _LIBCPP_TEMPLATE_VIS unordered_map;
403   template <class, class, class, class, class>
404   friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
407 template <class _NodePtr>
408 class _LIBCPP_TEMPLATE_VIS __hash_local_iterator {
409   typedef __hash_node_types<_NodePtr> _NodeTypes;
410   typedef _NodePtr __node_pointer;
411   typedef typename _NodeTypes::__next_pointer __next_pointer;
413   __next_pointer __node_;
414   size_t __bucket_;
415   size_t __bucket_count_;
417 public:
418   typedef forward_iterator_tag iterator_category;
419   typedef typename _NodeTypes::__node_value_type value_type;
420   typedef typename _NodeTypes::difference_type difference_type;
421   typedef value_type& reference;
422   typedef typename _NodeTypes::__node_value_type_pointer pointer;
424   _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {}
426   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
427     _LIBCPP_ASSERT_NON_NULL(
428         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
429     return __node_->__upcast()->__get_value();
430   }
432   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
433     _LIBCPP_ASSERT_NON_NULL(
434         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
435     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
436   }
438   _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() {
439     _LIBCPP_ASSERT_NON_NULL(
440         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container local_iterator");
441     __node_ = __node_->__next_;
442     if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
443       __node_ = nullptr;
444     return *this;
445   }
447   _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) {
448     __hash_local_iterator __t(*this);
449     ++(*this);
450     return __t;
451   }
453   friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
454     return __x.__node_ == __y.__node_;
455   }
456   friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
457     return !(__x == __y);
458   }
460 private:
461   _LIBCPP_HIDE_FROM_ABI explicit __hash_local_iterator(
462       __next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT
463       : __node_(__node),
464         __bucket_(__bucket),
465         __bucket_count_(__bucket_count) {
466     if (__node_ != nullptr)
467       __node_ = __node_->__next_;
468   }
470   template <class, class, class, class>
471   friend class __hash_table;
472   template <class>
473   friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
474   template <class>
475   friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
478 template <class _ConstNodePtr>
479 class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator {
480   typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
481   typedef _ConstNodePtr __node_pointer;
482   typedef typename _NodeTypes::__next_pointer __next_pointer;
484   __next_pointer __node_;
485   size_t __bucket_;
486   size_t __bucket_count_;
488   typedef pointer_traits<__node_pointer> __pointer_traits;
489   typedef typename __pointer_traits::element_type __node;
490   typedef __remove_const_t<__node> __non_const_node;
491   typedef __rebind_pointer_t<__node_pointer, __non_const_node> __non_const_node_pointer;
493 public:
494   typedef __hash_local_iterator<__non_const_node_pointer> __non_const_iterator;
496   typedef forward_iterator_tag iterator_category;
497   typedef typename _NodeTypes::__node_value_type value_type;
498   typedef typename _NodeTypes::difference_type difference_type;
499   typedef const value_type& reference;
500   typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
502   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {}
504   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
505       : __node_(__x.__node_),
506         __bucket_(__x.__bucket_),
507         __bucket_count_(__x.__bucket_count_) {}
509   _LIBCPP_HIDE_FROM_ABI reference operator*() const {
510     _LIBCPP_ASSERT_NON_NULL(
511         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
512     return __node_->__upcast()->__get_value();
513   }
515   _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
516     _LIBCPP_ASSERT_NON_NULL(
517         __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
518     return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
519   }
521   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator& operator++() {
522     _LIBCPP_ASSERT_NON_NULL(
523         __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_local_iterator");
524     __node_ = __node_->__next_;
525     if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
526       __node_ = nullptr;
527     return *this;
528   }
530   _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator operator++(int) {
531     __hash_const_local_iterator __t(*this);
532     ++(*this);
533     return __t;
534   }
536   friend _LIBCPP_HIDE_FROM_ABI bool
537   operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
538     return __x.__node_ == __y.__node_;
539   }
540   friend _LIBCPP_HIDE_FROM_ABI bool
541   operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
542     return !(__x == __y);
543   }
545 private:
546   _LIBCPP_HIDE_FROM_ABI explicit __hash_const_local_iterator(
547       __next_pointer __node_ptr, size_t __bucket, size_t __bucket_count) _NOEXCEPT
548       : __node_(__node_ptr),
549         __bucket_(__bucket),
550         __bucket_count_(__bucket_count) {
551     if (__node_ != nullptr)
552       __node_ = __node_->__next_;
553   }
555   template <class, class, class, class>
556   friend class __hash_table;
557   template <class>
558   friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
561 template <class _Alloc>
562 class __bucket_list_deallocator {
563   typedef _Alloc allocator_type;
564   typedef allocator_traits<allocator_type> __alloc_traits;
565   typedef typename __alloc_traits::size_type size_type;
567   _LIBCPP_COMPRESSED_PAIR(size_type, __size_, allocator_type, __alloc_);
569 public:
570   typedef typename __alloc_traits::pointer pointer;
572   _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
573       : __size_(0) {}
575   _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(const allocator_type& __a, size_type __size)
576       _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
577       : __size_(__size), __alloc_(__a) {}
579   _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(__bucket_list_deallocator&& __x)
580       _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
581       : __size_(std::move(__x.__size_)), __alloc_(std::move(__x.__alloc_)) {
582     __x.size() = 0;
583   }
585   _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; }
586   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }
588   _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __alloc_; }
589   _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __alloc_; }
591   _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { __alloc_traits::deallocate(__alloc(), __p, size()); }
594 template <class _Alloc>
595 class __hash_map_node_destructor;
597 template <class _Alloc>
598 class __hash_node_destructor {
599   typedef _Alloc allocator_type;
600   typedef allocator_traits<allocator_type> __alloc_traits;
602 public:
603   typedef typename __alloc_traits::pointer pointer;
605 private:
606   typedef __hash_node_types<pointer> _NodeTypes;
608   allocator_type& __na_;
610 public:
611   bool __value_constructed;
613   _LIBCPP_HIDE_FROM_ABI __hash_node_destructor(__hash_node_destructor const&)            = default;
614   _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
616   _LIBCPP_HIDE_FROM_ABI explicit __hash_node_destructor(allocator_type& __na, bool __constructed = false) _NOEXCEPT
617       : __na_(__na),
618         __value_constructed(__constructed) {}
620   _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
621     if (__value_constructed) {
622       __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__get_value()));
623       std::__destroy_at(std::addressof(*__p));
624     }
625     if (__p)
626       __alloc_traits::deallocate(__na_, __p, 1);
627   }
629   template <class>
630   friend class __hash_map_node_destructor;
633 #if _LIBCPP_STD_VER >= 17
634 template <class _NodeType, class _Alloc>
635 struct __generic_container_node_destructor;
637 template <class _Tp, class _VoidPtr, class _Alloc>
638 struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> : __hash_node_destructor<_Alloc> {
639   using __hash_node_destructor<_Alloc>::__hash_node_destructor;
641 #endif
643 template <class _Key, class _Hash, class _Equal>
644 struct __enforce_unordered_container_requirements {
645 #ifndef _LIBCPP_CXX03_LANG
646   static_assert(__check_hash_requirements<_Key, _Hash>::value,
647                 "the specified hash does not meet the Hash requirements");
648   static_assert(is_copy_constructible<_Equal>::value, "the specified comparator is required to be copy constructible");
649 #endif
650   typedef int type;
653 template <class _Key, class _Hash, class _Equal>
654 #ifndef _LIBCPP_CXX03_LANG
655 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
656                          "the specified comparator type does not provide a viable const call operator")
657 _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
658                          "the specified hash functor does not provide a viable const call operator")
659 #endif
660     typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
661     __diagnose_unordered_container_requirements(int);
663 // This dummy overload is used so that the compiler won't emit a spurious
664 // "no matching function for call to __diagnose_unordered_xxx" diagnostic
665 // when the overload above causes a hard error.
666 template <class _Key, class _Hash, class _Equal>
667 int __diagnose_unordered_container_requirements(void*);
669 template <class _Tp, class _Hash, class _Equal, class _Alloc>
670 class __hash_table {
671 public:
672   typedef _Tp value_type;
673   typedef _Hash hasher;
674   typedef _Equal key_equal;
675   typedef _Alloc allocator_type;
677 private:
678   typedef allocator_traits<allocator_type> __alloc_traits;
679   typedef typename __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;
681 public:
682   typedef typename _NodeTypes::__node_value_type __node_value_type;
683   typedef typename _NodeTypes::__container_value_type __container_value_type;
684   typedef typename _NodeTypes::key_type key_type;
685   typedef value_type& reference;
686   typedef const value_type& const_reference;
687   typedef typename __alloc_traits::pointer pointer;
688   typedef typename __alloc_traits::const_pointer const_pointer;
689 #ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
690   typedef typename __alloc_traits::size_type size_type;
691 #else
692   typedef typename _NodeTypes::size_type size_type;
693 #endif
694   typedef typename _NodeTypes::difference_type difference_type;
696 public:
697   // Create __node
699   typedef typename _NodeTypes::__node_type __node;
700   typedef __rebind_alloc<__alloc_traits, __node> __node_allocator;
701   typedef allocator_traits<__node_allocator> __node_traits;
702   typedef typename _NodeTypes::__void_pointer __void_pointer;
703   typedef typename _NodeTypes::__node_pointer __node_pointer;
704   typedef typename _NodeTypes::__node_pointer __node_const_pointer;
705   typedef typename _NodeTypes::__node_base_type __first_node;
706   typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
707   typedef typename _NodeTypes::__next_pointer __next_pointer;
709 private:
710   // check for sane allocator pointer rebinding semantics. Rebinding the
711   // allocator for a new pointer type should be exactly the same as rebinding
712   // the pointer using 'pointer_traits'.
713   static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,
714                 "Allocator does not rebind pointers in a sane manner.");
715   typedef __rebind_alloc<__node_traits, __first_node> __node_base_allocator;
716   typedef allocator_traits<__node_base_allocator> __node_base_traits;
717   static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,
718                 "Allocator does not rebind pointers in a sane manner.");
720 private:
721   typedef __rebind_alloc<__node_traits, __next_pointer> __pointer_allocator;
722   typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
723   typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
724   typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
725   typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
727   // --- Member data begin ---
728   __bucket_list __bucket_list_;
729   _LIBCPP_COMPRESSED_PAIR(__first_node, __first_node_, __node_allocator, __node_alloc_);
730   _LIBCPP_COMPRESSED_PAIR(size_type, __size_, hasher, __hasher_);
731   _LIBCPP_COMPRESSED_PAIR(float, __max_load_factor_, key_equal, __key_eq_);
732   // --- Member data end ---
734   _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __size_; }
736 public:
737   _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }
739   _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT { return __hasher_; }
740   _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT { return __hasher_; }
742   _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT { return __max_load_factor_; }
743   _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __max_load_factor_; }
745   _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT { return __key_eq_; }
746   _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT { return __key_eq_; }
748   _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __node_alloc_; }
749   _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __node_alloc_; }
751 public:
752   typedef __hash_iterator<__node_pointer> iterator;
753   typedef __hash_const_iterator<__node_pointer> const_iterator;
754   typedef __hash_local_iterator<__node_pointer> local_iterator;
755   typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
757   _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_(
758       is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
759           is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
760               is_nothrow_default_constructible<key_equal>::value);
761   _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql);
762   _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
763   _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);
764   _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);
765   _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);
766   _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u) _NOEXCEPT_(
767       is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
768           is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
769               is_nothrow_move_constructible<key_equal>::value);
770   _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);
771   _LIBCPP_HIDE_FROM_ABI ~__hash_table();
773   _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);
774   _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u)
775       _NOEXCEPT_(__node_traits::propagate_on_container_move_assignment::value&&
776                      is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
777                          is_nothrow_move_assignable<key_equal>::value);
778   template <class _InputIterator>
779   _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);
780   template <class _InputIterator>
781   _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
783   _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
784     return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());
785   }
787 private:
788   _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val);
789   _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT;
791   _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val);
792   _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
794 public:
795   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
796   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
797   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
799   template <class _Key, class... _Args>
800   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
802   template <class... _Args>
803   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
805   template <class _Pp>
806   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
807     return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
808   }
810   template <class _First,
811             class _Second,
812             __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
813   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
814     return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
815   }
817   template <class... _Args>
818   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
819     return __emplace_unique_impl(std::forward<_Args>(__args)...);
820   }
822   template <class _Pp>
823   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
824     return __emplace_unique_impl(std::forward<_Pp>(__x));
825   }
826   template <class _Pp>
827   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
828     return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
829   }
830   template <class _Pp>
831   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
832     return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
833   }
835   template <class... _Args>
836   _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
837   template <class... _Args>
838   _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
840   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __x) {
841     return __emplace_unique_key_args(_NodeTypes::__get_key(__x), std::move(__x));
842   }
844   template <class _Pp, __enable_if_t<!__is_same_uncvref<_Pp, __container_value_type>::value, int> = 0>
845   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Pp&& __x) {
846     return __emplace_unique(std::forward<_Pp>(__x));
847   }
849   template <class _Pp>
850   _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Pp&& __x) {
851     return __emplace_multi(std::forward<_Pp>(__x));
852   }
854   template <class _Pp>
855   _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Pp&& __x) {
856     return __emplace_hint_multi(__p, std::forward<_Pp>(__x));
857   }
859   _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
860     return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
861   }
863 #if _LIBCPP_STD_VER >= 17
864   template <class _NodeHandle, class _InsertReturnType>
865   _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
866   template <class _NodeHandle>
867   _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh);
868   template <class _Table>
869   _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source);
871   template <class _NodeHandle>
872   _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh);
873   template <class _NodeHandle>
874   _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
875   template <class _Table>
876   _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source);
878   template <class _NodeHandle>
879   _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key);
880   template <class _NodeHandle>
881   _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it);
882 #endif
884   _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
885   _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); }
886   _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); }
887   _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) {
888     __rehash_unique(static_cast<size_type>(__math::ceil(__n / max_load_factor())));
889   }
890   _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) {
891     __rehash_multi(static_cast<size_type>(__math::ceil(__n / max_load_factor())));
892   }
894   _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); }
896   _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
897   _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
898   _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
899   _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
901   template <class _Key>
902   _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const {
903     _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
904         bucket_count() > 0, "unordered container::bucket(key) called when bucket_count() == 0");
905     return std::__constrain_hash(hash_function()(__k), bucket_count());
906   }
908   template <class _Key>
909   _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __x);
910   template <class _Key>
911   _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;
913   typedef __hash_node_destructor<__node_allocator> _Dp;
914   typedef unique_ptr<__node, _Dp> __node_holder;
916   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
917   _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
918   template <class _Key>
919   _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
920   template <class _Key>
921   _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
922   _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
924   template <class _Key>
925   _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
926   template <class _Key>
927   _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
929   template <class _Key>
930   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);
931   template <class _Key>
932   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;
934   template <class _Key>
935   _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);
936   template <class _Key>
937   _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;
939   _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)
940 #if _LIBCPP_STD_VER <= 11
941       _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
942                  (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
943                   __is_nothrow_swappable_v<__pointer_allocator>) &&
944                  (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));
945 #else
946       _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>);
947 #endif
949   _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return max_size(); }
950   _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;
951   _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT {
952     size_type __bc = bucket_count();
953     return __bc != 0 ? (float)size() / __bc : 0.f;
954   }
955   _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT {
956     // While passing a non-positive load factor is undefined behavior, in practice the result will be benign (the
957     // call will be equivalent to `max_load_factor(load_factor())`, which is also the case for passing a valid value
958     // less than the current `load_factor`).
959     _LIBCPP_ASSERT_PEDANTIC(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0");
960     max_load_factor() = std::max(__mlf, load_factor());
961   }
963   _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) {
964     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
965         __n < bucket_count(), "unordered container::begin(n) called with n >= bucket_count()");
966     return local_iterator(__bucket_list_[__n], __n, bucket_count());
967   }
969   _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) {
970     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
971         __n < bucket_count(), "unordered container::end(n) called with n >= bucket_count()");
972     return local_iterator(nullptr, __n, bucket_count());
973   }
975   _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const {
976     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
977         __n < bucket_count(), "unordered container::cbegin(n) called with n >= bucket_count()");
978     return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
979   }
981   _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const {
982     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
983         __n < bucket_count(), "unordered container::cend(n) called with n >= bucket_count()");
984     return const_local_iterator(nullptr, __n, bucket_count());
985   }
987 private:
988   template <bool _UniqueKeys>
989   _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);
990   template <bool _UniqueKeys>
991   _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);
993   template <class... _Args>
994   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
996   template <class _First, class... _Rest>
997   _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
999   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
1000     __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
1001   }
1002   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);
1003   _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {}
1005   _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);
1006   _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)
1007       _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1008                      is_nothrow_move_assignable<key_equal>::value);
1009   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_(
1010       !__node_traits::propagate_on_container_move_assignment::value ||
1011       (is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value)) {
1012     __move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1013   }
1014   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_(
1015       is_nothrow_move_assignable<__pointer_allocator>::value&& is_nothrow_move_assignable<__node_allocator>::value) {
1016     __bucket_list_.get_deleter().__alloc() = std::move(__u.__bucket_list_.get_deleter().__alloc());
1017     __node_alloc()                         = std::move(__u.__node_alloc());
1018   }
1019   _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1021   _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT;
1022   _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
1024   template <class, class, class, class, class>
1025   friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1026   template <class, class, class, class, class>
1027   friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1030 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1031 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() _NOEXCEPT_(
1032     is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
1033         is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
1034             is_nothrow_default_constructible<key_equal>::value)
1035     : __size_(0), __max_load_factor_(1.0f) {}
1037 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1038 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, const key_equal& __eql)
1039     : __bucket_list_(nullptr, __bucket_list_deleter()),
1040       __first_node_(),
1041       __node_alloc_(),
1042       __size_(0),
1043       __hasher_(__hf),
1044       __max_load_factor_(1.0f),
1045       __key_eq_(__eql) {}
1047 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1048 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(
1049     const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1050     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1051       __node_alloc_(__node_allocator(__a)),
1052       __size_(0),
1053       __hasher_(__hf),
1054       __max_load_factor_(1.0f),
1055       __key_eq_(__eql) {}
1057 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1058 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1059     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1060       __node_alloc_(__node_allocator(__a)),
1061       __size_(0),
1062       __max_load_factor_(1.0f) {}
1064 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1065 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1066     : __bucket_list_(nullptr,
1067                      __bucket_list_deleter(allocator_traits<__pointer_allocator>::select_on_container_copy_construction(
1068                                                __u.__bucket_list_.get_deleter().__alloc()),
1069                                            0)),
1070       __node_alloc_(allocator_traits<__node_allocator>::select_on_container_copy_construction(__u.__node_alloc())),
1071       __size_(0),
1072       __hasher_(__u.hash_function()),
1073       __max_load_factor_(__u.__max_load_factor_),
1074       __key_eq_(__u.__key_eq_) {}
1076 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1077 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, const allocator_type& __a)
1078     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1079       __node_alloc_(__node_allocator(__a)),
1080       __size_(0),
1081       __hasher_(__u.hash_function()),
1082       __max_load_factor_(__u.__max_load_factor_),
1083       __key_eq_(__u.__key_eq_) {}
1085 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1086 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) _NOEXCEPT_(
1087     is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
1088         is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
1089             is_nothrow_move_constructible<key_equal>::value)
1090     : __bucket_list_(std::move(__u.__bucket_list_)),
1091       __first_node_(std::move(__u.__first_node_)),
1092       __node_alloc_(std::move(__u.__node_alloc_)),
1093       __size_(std::move(__u.__size_)),
1094       __hasher_(std::move(__u.__hasher_)),
1095       __max_load_factor_(__u.__max_load_factor_),
1096       __key_eq_(std::move(__u.__key_eq_)) {
1097   if (size() > 0) {
1098     __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
1099     __u.__first_node_.__next_                                                              = nullptr;
1100     __u.size()                                                                             = 0;
1101   }
1104 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1105 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a)
1106     : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1107       __node_alloc_(__node_allocator(__a)),
1108       __size_(0),
1109       __hasher_(std::move(__u.__hasher_)),
1110       __max_load_factor_(__u.__max_load_factor_),
1111       __key_eq_(std::move(__u.__key_eq_)) {
1112   if (__a == allocator_type(__u.__node_alloc())) {
1113     __bucket_list_.reset(__u.__bucket_list_.release());
1114     __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
1115     __u.__bucket_list_.get_deleter().size() = 0;
1116     if (__u.size() > 0) {
1117       __first_node_.__next_     = __u.__first_node_.__next_;
1118       __u.__first_node_.__next_ = nullptr;
1119       __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
1120       size()                                                                                 = __u.size();
1121       __u.size()                                                                             = 0;
1122     }
1123   }
1126 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1127 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {
1128 #if defined(_LIBCPP_CXX03_LANG)
1129   static_assert(is_copy_constructible<key_equal>::value, "Predicate must be copy-constructible.");
1130   static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");
1131 #endif
1133   __deallocate_node(__first_node_.__next_);
1136 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1137 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(const __hash_table& __u, true_type) {
1138   if (__node_alloc() != __u.__node_alloc()) {
1139     clear();
1140     __bucket_list_.reset();
1141     __bucket_list_.get_deleter().size() = 0;
1142   }
1143   __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1144   __node_alloc()                         = __u.__node_alloc();
1147 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1148 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) {
1149   if (this != std::addressof(__u)) {
1150     __copy_assign_alloc(__u);
1151     hash_function()   = __u.hash_function();
1152     key_eq()          = __u.key_eq();
1153     max_load_factor() = __u.max_load_factor();
1154     __assign_multi(__u.begin(), __u.end());
1155   }
1156   return *this;
1159 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1160 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT {
1161   __node_allocator& __na = __node_alloc();
1162   while (__np != nullptr) {
1163     __next_pointer __next    = __np->__next_;
1164     __node_pointer __real_np = __np->__upcast();
1165     __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__get_value()));
1166     std::__destroy_at(std::addressof(*__real_np));
1167     __node_traits::deallocate(__na, __real_np, 1);
1168     __np = __next;
1169   }
1172 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1173 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1174 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {
1175   size_type __bc = bucket_count();
1176   for (size_type __i = 0; __i < __bc; ++__i)
1177     __bucket_list_[__i] = nullptr;
1178   size()                 = 0;
1179   __next_pointer __cache = __first_node_.__next_;
1180   __first_node_.__next_  = nullptr;
1181   return __cache;
1184 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1185 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, true_type)
1186     _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1187                    is_nothrow_move_assignable<key_equal>::value) {
1188   clear();
1189   __bucket_list_.reset(__u.__bucket_list_.release());
1190   __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
1191   __u.__bucket_list_.get_deleter().size() = 0;
1192   __move_assign_alloc(__u);
1193   size()                = __u.size();
1194   hash_function()       = std::move(__u.hash_function());
1195   max_load_factor()     = __u.max_load_factor();
1196   key_eq()              = std::move(__u.key_eq());
1197   __first_node_.__next_ = __u.__first_node_.__next_;
1198   if (size() > 0) {
1199     __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
1200     __u.__first_node_.__next_                                                              = nullptr;
1201     __u.size()                                                                             = 0;
1202   }
1205 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1206 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, false_type) {
1207   if (__node_alloc() == __u.__node_alloc())
1208     __move_assign(__u, true_type());
1209   else {
1210     hash_function()   = std::move(__u.hash_function());
1211     key_eq()          = std::move(__u.key_eq());
1212     max_load_factor() = __u.max_load_factor();
1213     if (bucket_count() != 0) {
1214       __next_pointer __cache = __detach();
1215 #if _LIBCPP_HAS_EXCEPTIONS
1216       try {
1217 #endif // _LIBCPP_HAS_EXCEPTIONS
1218         const_iterator __i = __u.begin();
1219         while (__cache != nullptr && __u.size() != 0) {
1220           __cache->__upcast()->__get_value() = std::move(__u.remove(__i++)->__get_value());
1221           __next_pointer __next              = __cache->__next_;
1222           __node_insert_multi(__cache->__upcast());
1223           __cache = __next;
1224         }
1225 #if _LIBCPP_HAS_EXCEPTIONS
1226       } catch (...) {
1227         __deallocate_node(__cache);
1228         throw;
1229       }
1230 #endif // _LIBCPP_HAS_EXCEPTIONS
1231       __deallocate_node(__cache);
1232     }
1233     const_iterator __i = __u.begin();
1234     while (__u.size() != 0) {
1235       __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__get_value()));
1236       __node_insert_multi(__h.get());
1237       __h.release();
1238     }
1239   }
1242 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1243 inline __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1244 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) _NOEXCEPT_(
1245     __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<__node_allocator>::value&&
1246         is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value) {
1247   __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1248   return *this;
1251 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1252 template <class _InputIterator>
1253 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, _InputIterator __last) {
1254   typedef iterator_traits<_InputIterator> _ITraits;
1255   typedef typename _ITraits::value_type _ItValueType;
1256   static_assert(is_same<_ItValueType, __container_value_type>::value,
1257                 "__assign_unique may only be called with the containers value type");
1259   if (bucket_count() != 0) {
1260     __next_pointer __cache = __detach();
1261 #if _LIBCPP_HAS_EXCEPTIONS
1262     try {
1263 #endif // _LIBCPP_HAS_EXCEPTIONS
1264       for (; __cache != nullptr && __first != __last; ++__first) {
1265         __cache->__upcast()->__get_value() = *__first;
1266         __next_pointer __next              = __cache->__next_;
1267         __node_insert_unique(__cache->__upcast());
1268         __cache = __next;
1269       }
1270 #if _LIBCPP_HAS_EXCEPTIONS
1271     } catch (...) {
1272       __deallocate_node(__cache);
1273       throw;
1274     }
1275 #endif // _LIBCPP_HAS_EXCEPTIONS
1276     __deallocate_node(__cache);
1277   }
1278   for (; __first != __last; ++__first)
1279     __insert_unique(*__first);
1282 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1283 template <class _InputIterator>
1284 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, _InputIterator __last) {
1285   typedef iterator_traits<_InputIterator> _ITraits;
1286   typedef typename _ITraits::value_type _ItValueType;
1287   static_assert(
1288       (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value),
1289       "__assign_multi may only be called with the containers value type"
1290       " or the nodes value type");
1291   if (bucket_count() != 0) {
1292     __next_pointer __cache = __detach();
1293 #if _LIBCPP_HAS_EXCEPTIONS
1294     try {
1295 #endif // _LIBCPP_HAS_EXCEPTIONS
1296       for (; __cache != nullptr && __first != __last; ++__first) {
1297         __cache->__upcast()->__get_value() = *__first;
1298         __next_pointer __next              = __cache->__next_;
1299         __node_insert_multi(__cache->__upcast());
1300         __cache = __next;
1301       }
1302 #if _LIBCPP_HAS_EXCEPTIONS
1303     } catch (...) {
1304       __deallocate_node(__cache);
1305       throw;
1306     }
1307 #endif // _LIBCPP_HAS_EXCEPTIONS
1308     __deallocate_node(__cache);
1309   }
1310   for (; __first != __last; ++__first)
1311     __insert_multi(_NodeTypes::__get_value(*__first));
1314 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1315 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1316 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT {
1317   return iterator(__first_node_.__next_);
1320 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1321 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1322 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT {
1323   return iterator(nullptr);
1326 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1327 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1328 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT {
1329   return const_iterator(__first_node_.__next_);
1332 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1333 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1334 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {
1335   return const_iterator(nullptr);
1338 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1339 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {
1340   if (size() > 0) {
1341     __deallocate_node(__first_node_.__next_);
1342     __first_node_.__next_ = nullptr;
1343     size_type __bc        = bucket_count();
1344     for (size_type __i = 0; __i < __bc; ++__i)
1345       __bucket_list_[__i] = nullptr;
1346     size() = 0;
1347   }
1350 // Prepare the container for an insertion of the value __value with the hash
1351 // __hash. This does a lookup into the container to see if __value is already
1352 // present, and performs a rehash if necessary. Returns a pointer to the
1353 // existing element if it exists, otherwise nullptr.
1355 // Note that this function does forward exceptions if key_eq() throws, and never
1356 // mutates __value or actually inserts into the map.
1357 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1358 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1359 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {
1360   size_type __bc = bucket_count();
1362   if (__bc != 0) {
1363     size_t __chash         = std::__constrain_hash(__hash, __bc);
1364     __next_pointer __ndptr = __bucket_list_[__chash];
1365     if (__ndptr != nullptr) {
1366       for (__ndptr = __ndptr->__next_;
1367            __ndptr != nullptr &&
1368            (__ndptr->__hash() == __hash || std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);
1369            __ndptr = __ndptr->__next_) {
1370         if ((__ndptr->__hash() == __hash) && key_eq()(__ndptr->__upcast()->__get_value(), __value))
1371           return __ndptr;
1372       }
1373     }
1374   }
1375   if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1376     __rehash_unique(std::max<size_type>(
1377         2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1378   }
1379   return nullptr;
1382 // Insert the node __nd into the container by pushing it into the right bucket,
1383 // and updating size(). Assumes that __nd->__hash is up-to-date, and that
1384 // rehashing has already occurred and that no element with the same key exists
1385 // in the map.
1386 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1387 _LIBCPP_HIDE_FROM_ABI void
1388 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {
1389   size_type __bc = bucket_count();
1390   size_t __chash = std::__constrain_hash(__nd->__hash(), __bc);
1391   // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1392   __next_pointer __pn = __bucket_list_[__chash];
1393   if (__pn == nullptr) {
1394     __pn          = __first_node_.__ptr();
1395     __nd->__next_ = __pn->__next_;
1396     __pn->__next_ = __nd->__ptr();
1397     // fix up __bucket_list_
1398     __bucket_list_[__chash] = __pn;
1399     if (__nd->__next_ != nullptr)
1400       __bucket_list_[std::__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
1401   } else {
1402     __nd->__next_ = __pn->__next_;
1403     __pn->__next_ = __nd->__ptr();
1404   }
1405   ++size();
1408 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1409 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1410 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) {
1411   __nd->__hash_                  = hash_function()(__nd->__get_value());
1412   __next_pointer __existing_node = __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value());
1414   // Insert the node, unless it already exists in the container.
1415   bool __inserted = false;
1416   if (__existing_node == nullptr) {
1417     __node_insert_unique_perform(__nd);
1418     __existing_node = __nd->__ptr();
1419     __inserted      = true;
1420   }
1421   return pair<iterator, bool>(iterator(__existing_node), __inserted);
1424 // Prepare the container for an insertion of the value __cp_val with the hash
1425 // __cp_hash. This does a lookup into the container to see if __cp_value is
1426 // already present, and performs a rehash if necessary. Returns a pointer to the
1427 // last occurrence of __cp_val in the map.
1429 // Note that this function does forward exceptions if key_eq() throws, and never
1430 // mutates __value or actually inserts into the map.
1431 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1432 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1433 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {
1434   size_type __bc = bucket_count();
1435   if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1436     __rehash_multi(std::max<size_type>(
1437         2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1438     __bc = bucket_count();
1439   }
1440   size_t __chash      = std::__constrain_hash(__cp_hash, __bc);
1441   __next_pointer __pn = __bucket_list_[__chash];
1442   if (__pn != nullptr) {
1443     for (bool __found = false;
1444          __pn->__next_ != nullptr && std::__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
1445          __pn = __pn->__next_) {
1446       //      __found    key_eq()     action
1447       //      false       false       loop
1448       //      true        true        loop
1449       //      false       true        set __found to true
1450       //      true        false       break
1451       if (__found !=
1452           (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) {
1453         if (!__found)
1454           __found = true;
1455         else
1456           break;
1457       }
1458     }
1459   }
1460   return __pn;
1463 // Insert the node __cp into the container after __pn (which is the last node in
1464 // the bucket that compares equal to __cp). Rehashing, and checking for
1465 // uniqueness has already been performed (in __node_insert_multi_prepare), so
1466 // all we need to do is update the bucket and size(). Assumes that __cp->__hash
1467 // is up-to-date.
1468 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1469 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
1470     __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {
1471   size_type __bc = bucket_count();
1472   size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
1473   if (__pn == nullptr) {
1474     __pn          = __first_node_.__ptr();
1475     __cp->__next_ = __pn->__next_;
1476     __pn->__next_ = __cp->__ptr();
1477     // fix up __bucket_list_
1478     __bucket_list_[__chash] = __pn;
1479     if (__cp->__next_ != nullptr)
1480       __bucket_list_[std::__constrain_hash(__cp->__next_->__hash(), __bc)] = __cp->__ptr();
1481   } else {
1482     __cp->__next_ = __pn->__next_;
1483     __pn->__next_ = __cp->__ptr();
1484     if (__cp->__next_ != nullptr) {
1485       size_t __nhash = std::__constrain_hash(__cp->__next_->__hash(), __bc);
1486       if (__nhash != __chash)
1487         __bucket_list_[__nhash] = __cp->__ptr();
1488     }
1489   }
1490   ++size();
1493 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1494 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1495 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) {
1496   __cp->__hash_       = hash_function()(__cp->__get_value());
1497   __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value());
1498   __node_insert_multi_perform(__cp, __pn);
1500   return iterator(__cp->__ptr());
1503 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1504 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1505 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {
1506   if (__p != end() && key_eq()(*__p, __cp->__get_value())) {
1507     __next_pointer __np = __p.__node_;
1508     __cp->__hash_       = __np->__hash();
1509     size_type __bc      = bucket_count();
1510     if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1511       __rehash_multi(std::max<size_type>(
1512           2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1513       __bc = bucket_count();
1514     }
1515     size_t __chash      = std::__constrain_hash(__cp->__hash_, __bc);
1516     __next_pointer __pp = __bucket_list_[__chash];
1517     while (__pp->__next_ != __np)
1518       __pp = __pp->__next_;
1519     __cp->__next_ = __np;
1520     __pp->__next_ = static_cast<__next_pointer>(__cp);
1521     ++size();
1522     return iterator(static_cast<__next_pointer>(__cp));
1523   }
1524   return __node_insert_multi(__cp);
1527 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1528 template <class _Key, class... _Args>
1529 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1530 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
1531   size_t __hash   = hash_function()(__k);
1532   size_type __bc  = bucket_count();
1533   bool __inserted = false;
1534   __next_pointer __nd;
1535   size_t __chash;
1536   if (__bc != 0) {
1537     __chash = std::__constrain_hash(__hash, __bc);
1538     __nd    = __bucket_list_[__chash];
1539     if (__nd != nullptr) {
1540       for (__nd = __nd->__next_;
1541            __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1542            __nd = __nd->__next_) {
1543         if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1544           goto __done;
1545       }
1546     }
1547   }
1548   {
1549     __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
1550     if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1551       __rehash_unique(std::max<size_type>(
1552           2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1553       __bc    = bucket_count();
1554       __chash = std::__constrain_hash(__hash, __bc);
1555     }
1556     // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1557     __next_pointer __pn = __bucket_list_[__chash];
1558     if (__pn == nullptr) {
1559       __pn          = __first_node_.__ptr();
1560       __h->__next_  = __pn->__next_;
1561       __pn->__next_ = __h.get()->__ptr();
1562       // fix up __bucket_list_
1563       __bucket_list_[__chash] = __pn;
1564       if (__h->__next_ != nullptr)
1565         __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
1566     } else {
1567       __h->__next_  = __pn->__next_;
1568       __pn->__next_ = static_cast<__next_pointer>(__h.get());
1569     }
1570     __nd = static_cast<__next_pointer>(__h.release());
1571     // increment size
1572     ++size();
1573     __inserted = true;
1574   }
1575 __done:
1576   return pair<iterator, bool>(iterator(__nd), __inserted);
1579 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1580 template <class... _Args>
1581 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1582 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
1583   __node_holder __h        = __construct_node(std::forward<_Args>(__args)...);
1584   pair<iterator, bool> __r = __node_insert_unique(__h.get());
1585   if (__r.second)
1586     __h.release();
1587   return __r;
1590 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1591 template <class... _Args>
1592 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1593 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
1594   __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1595   iterator __r      = __node_insert_multi(__h.get());
1596   __h.release();
1597   return __r;
1600 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1601 template <class... _Args>
1602 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1603 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
1604   __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1605   iterator __r      = __node_insert_multi(__p, __h.get());
1606   __h.release();
1607   return __r;
1610 #if _LIBCPP_STD_VER >= 17
1611 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1612 template <class _NodeHandle, class _InsertReturnType>
1613 _LIBCPP_HIDE_FROM_ABI _InsertReturnType
1614 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(_NodeHandle&& __nh) {
1615   if (__nh.empty())
1616     return _InsertReturnType{end(), false, _NodeHandle()};
1617   pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1618   if (__result.second)
1619     __nh.__release_ptr();
1620   return _InsertReturnType{__result.first, __result.second, std::move(__nh)};
1623 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1624 template <class _NodeHandle>
1625 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1626 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {
1627   if (__nh.empty())
1628     return end();
1629   pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1630   if (__result.second)
1631     __nh.__release_ptr();
1632   return __result.first;
1635 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1636 template <class _NodeHandle>
1637 _LIBCPP_HIDE_FROM_ABI _NodeHandle
1638 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(key_type const& __key) {
1639   iterator __i = find(__key);
1640   if (__i == end())
1641     return _NodeHandle();
1642   return __node_handle_extract<_NodeHandle>(__i);
1645 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1646 template <class _NodeHandle>
1647 _LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(const_iterator __p) {
1648   allocator_type __alloc(__node_alloc());
1649   return _NodeHandle(remove(__p).release(), __alloc);
1652 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1653 template <class _Table>
1654 _LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(_Table& __source) {
1655   static_assert(is_same<__node, typename _Table::__node>::value, "");
1657   for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1658     __node_pointer __src_ptr       = __it.__node_->__upcast();
1659     size_t __hash                  = hash_function()(__src_ptr->__get_value());
1660     __next_pointer __existing_node = __node_insert_unique_prepare(__hash, __src_ptr->__get_value());
1661     auto __prev_iter               = __it++;
1662     if (__existing_node == nullptr) {
1663       (void)__source.remove(__prev_iter).release();
1664       __src_ptr->__hash_ = __hash;
1665       __node_insert_unique_perform(__src_ptr);
1666     }
1667   }
1670 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1671 template <class _NodeHandle>
1672 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1673 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(_NodeHandle&& __nh) {
1674   if (__nh.empty())
1675     return end();
1676   iterator __result = __node_insert_multi(__nh.__ptr_);
1677   __nh.__release_ptr();
1678   return __result;
1681 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1682 template <class _NodeHandle>
1683 _LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1684 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {
1685   if (__nh.empty())
1686     return end();
1687   iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
1688   __nh.__release_ptr();
1689   return __result;
1692 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1693 template <class _Table>
1694 _LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(_Table& __source) {
1695   static_assert(is_same<typename _Table::__node, __node>::value, "");
1697   for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1698     __node_pointer __src_ptr = __it.__node_->__upcast();
1699     size_t __src_hash        = hash_function()(__src_ptr->__get_value());
1700     __next_pointer __pn      = __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value());
1701     (void)__source.remove(__it++).release();
1702     __src_ptr->__hash_ = __src_hash;
1703     __node_insert_multi_perform(__src_ptr, __pn);
1704   }
1706 #endif // _LIBCPP_STD_VER >= 17
1708 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1709 template <bool _UniqueKeys>
1710 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
1711   if (__n == 1)
1712     __n = 2;
1713   else if (__n & (__n - 1))
1714     __n = std::__next_prime(__n);
1715   size_type __bc = bucket_count();
1716   if (__n > __bc)
1717     __do_rehash<_UniqueKeys>(__n);
1718   else if (__n < __bc) {
1719     __n = std::max<size_type>(
1720         __n,
1721         std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(__math::ceil(float(size()) / max_load_factor())))
1722                                     : std::__next_prime(size_t(__math::ceil(float(size()) / max_load_factor()))));
1723     if (__n < __bc)
1724       __do_rehash<_UniqueKeys>(__n);
1725   }
1728 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1729 template <bool _UniqueKeys>
1730 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc) {
1731   __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1732   __bucket_list_.reset(__nbc > 0 ? __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1733   __bucket_list_.get_deleter().size() = __nbc;
1734   if (__nbc > 0) {
1735     for (size_type __i = 0; __i < __nbc; ++__i)
1736       __bucket_list_[__i] = nullptr;
1737     __next_pointer __pp = __first_node_.__ptr();
1738     __next_pointer __cp = __pp->__next_;
1739     if (__cp != nullptr) {
1740       size_type __chash       = std::__constrain_hash(__cp->__hash(), __nbc);
1741       __bucket_list_[__chash] = __pp;
1742       size_type __phash       = __chash;
1743       for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {
1744         __chash = std::__constrain_hash(__cp->__hash(), __nbc);
1745         if (__chash == __phash)
1746           __pp = __cp;
1747         else {
1748           if (__bucket_list_[__chash] == nullptr) {
1749             __bucket_list_[__chash] = __pp;
1750             __pp                    = __cp;
1751             __phash                 = __chash;
1752           } else {
1753             __next_pointer __np = __cp;
1754             if _LIBCPP_CONSTEXPR_SINCE_CXX17 (!_UniqueKeys) {
1755               for (; __np->__next_ != nullptr &&
1756                      key_eq()(__cp->__upcast()->__get_value(), __np->__next_->__upcast()->__get_value());
1757                    __np = __np->__next_)
1758                 ;
1759             }
1760             __pp->__next_                    = __np->__next_;
1761             __np->__next_                    = __bucket_list_[__chash]->__next_;
1762             __bucket_list_[__chash]->__next_ = __cp;
1763           }
1764         }
1765       }
1766     }
1767   }
1770 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1771 template <class _Key>
1772 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1773 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) {
1774   size_t __hash  = hash_function()(__k);
1775   size_type __bc = bucket_count();
1776   if (__bc != 0) {
1777     size_t __chash      = std::__constrain_hash(__hash, __bc);
1778     __next_pointer __nd = __bucket_list_[__chash];
1779     if (__nd != nullptr) {
1780       for (__nd = __nd->__next_;
1781            __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1782            __nd = __nd->__next_) {
1783         if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1784           return iterator(__nd);
1785       }
1786     }
1787   }
1788   return end();
1791 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1792 template <class _Key>
1793 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1794 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const {
1795   size_t __hash  = hash_function()(__k);
1796   size_type __bc = bucket_count();
1797   if (__bc != 0) {
1798     size_t __chash      = std::__constrain_hash(__hash, __bc);
1799     __next_pointer __nd = __bucket_list_[__chash];
1800     if (__nd != nullptr) {
1801       for (__nd = __nd->__next_;
1802            __nd != nullptr && (__hash == __nd->__hash() || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1803            __nd = __nd->__next_) {
1804         if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1805           return const_iterator(__nd);
1806       }
1807     }
1808   }
1809   return end();
1812 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1813 template <class... _Args>
1814 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1815 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
1816   static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
1817   __node_allocator& __na = __node_alloc();
1818   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1820   // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
1821   // held inside the node, since we need to use the allocator's construct() method for that.
1822   //
1823   // We don't use the allocator's construct() method to construct the node itself since the
1824   // Cpp17FooInsertable named requirements don't require the allocator's construct() method
1825   // to work on anything other than the value_type.
1826   std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ 0);
1828   // Now construct the value_type using the allocator's construct() method.
1829   __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_Args>(__args)...);
1830   __h.get_deleter().__value_constructed = true;
1832   __h->__hash_ = hash_function()(__h->__get_value());
1833   return __h;
1836 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1837 template <class _First, class... _Rest>
1838 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1839 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
1840   static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
1841   __node_allocator& __na = __node_alloc();
1842   __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1843   std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
1844   __node_traits::construct(
1845       __na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
1846   __h.get_deleter().__value_constructed = true;
1847   return __h;
1850 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1851 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1852 __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;
1862 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1863 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1864 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
1865   for (const_iterator __p = __first; __first != __last; __p = __first) {
1866     ++__first;
1867     erase(__p);
1868   }
1869   __next_pointer __np = __last.__node_;
1870   return iterator(__np);
1873 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1874 template <class _Key>
1875 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1876 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) {
1877   iterator __i = find(__k);
1878   if (__i == end())
1879     return 0;
1880   erase(__i);
1881   return 1;
1884 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1885 template <class _Key>
1886 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1887 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) {
1888   size_type __r = 0;
1889   iterator __i  = find(__k);
1890   if (__i != end()) {
1891     iterator __e = end();
1892     do {
1893       erase(__i++);
1894       ++__r;
1895     } while (__i != __e && key_eq()(*__i, __k));
1896   }
1897   return __r;
1900 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1901 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1902 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT {
1903   // current node
1904   __next_pointer __cn = __p.__node_;
1905   size_type __bc      = bucket_count();
1906   size_t __chash      = std::__constrain_hash(__cn->__hash(), __bc);
1907   // find previous node
1908   __next_pointer __pn = __bucket_list_[__chash];
1909   for (; __pn->__next_ != __cn; __pn = __pn->__next_)
1910     ;
1911   // Fix up __bucket_list_
1912   // if __pn is not in same bucket (before begin is not in same bucket) &&
1913   //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
1914   if (__pn == __first_node_.__ptr() || std::__constrain_hash(__pn->__hash(), __bc) != __chash) {
1915     if (__cn->__next_ == nullptr || std::__constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
1916       __bucket_list_[__chash] = nullptr;
1917   }
1918   // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
1919   if (__cn->__next_ != nullptr) {
1920     size_t __nhash = std::__constrain_hash(__cn->__next_->__hash(), __bc);
1921     if (__nhash != __chash)
1922       __bucket_list_[__nhash] = __pn;
1923   }
1924   // remove __cn
1925   __pn->__next_ = __cn->__next_;
1926   __cn->__next_ = nullptr;
1927   --size();
1928   return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
1931 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1932 template <class _Key>
1933 inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1934 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const {
1935   return static_cast<size_type>(find(__k) != end());
1938 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1939 template <class _Key>
1940 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1941 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const {
1942   size_type __r      = 0;
1943   const_iterator __i = find(__k);
1944   if (__i != end()) {
1945     const_iterator __e = end();
1946     do {
1947       ++__i;
1948       ++__r;
1949     } while (__i != __e && key_eq()(*__i, __k));
1950   }
1951   return __r;
1954 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1955 template <class _Key>
1956 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1957      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1958 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) {
1959   iterator __i = find(__k);
1960   iterator __j = __i;
1961   if (__i != end())
1962     ++__j;
1963   return pair<iterator, iterator>(__i, __j);
1966 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1967 template <class _Key>
1968 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1969      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1970 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) const {
1971   const_iterator __i = find(__k);
1972   const_iterator __j = __i;
1973   if (__i != end())
1974     ++__j;
1975   return pair<const_iterator, const_iterator>(__i, __j);
1978 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1979 template <class _Key>
1980 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1981      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1982 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) {
1983   iterator __i = find(__k);
1984   iterator __j = __i;
1985   if (__i != end()) {
1986     iterator __e = end();
1987     do {
1988       ++__j;
1989     } while (__j != __e && key_eq()(*__j, __k));
1990   }
1991   return pair<iterator, iterator>(__i, __j);
1994 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1995 template <class _Key>
1996 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1997      typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1998 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) const {
1999   const_iterator __i = find(__k);
2000   const_iterator __j = __i;
2001   if (__i != end()) {
2002     const_iterator __e = end();
2003     do {
2004       ++__j;
2005     } while (__j != __e && key_eq()(*__j, __k));
2006   }
2007   return pair<const_iterator, const_iterator>(__i, __j);
2010 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2011 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2012 #if _LIBCPP_STD_VER <= 11
2013     _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
2014                (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
2015                 __is_nothrow_swappable_v<__pointer_allocator>) &&
2016                (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))
2017 #else
2018     _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>)
2019 #endif
2021   _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2022       __node_traits::propagate_on_container_swap::value || this->__node_alloc() == __u.__node_alloc(),
2023       "unordered container::swap: Either propagate_on_container_swap "
2024       "must be true or the allocators must compare equal");
2025   {
2026     __node_pointer_pointer __npp = __bucket_list_.release();
2027     __bucket_list_.reset(__u.__bucket_list_.release());
2028     __u.__bucket_list_.reset(__npp);
2029   }
2030   std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2031   std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc());
2032   std::__swap_allocator(__node_alloc(), __u.__node_alloc());
2033   std::swap(__first_node_.__next_, __u.__first_node_.__next_);
2034   using std::swap;
2035   swap(__size_, __u.__size_);
2036   swap(__hasher_, __u.__hasher_);
2037   swap(__max_load_factor_, __u.__max_load_factor_);
2038   swap(__key_eq_, __u.__key_eq_);
2039   if (size() > 0)
2040     __bucket_list_[std::__constrain_hash(__first_node_.__next_->__hash(), bucket_count())] = __first_node_.__ptr();
2041   if (__u.size() > 0)
2042     __u.__bucket_list_[std::__constrain_hash(__u.__first_node_.__next_->__hash(), __u.bucket_count())] =
2043         __u.__first_node_.__ptr();
2046 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2047 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2048 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const {
2049   _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
2050       __n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");
2051   __next_pointer __np = __bucket_list_[__n];
2052   size_type __bc      = bucket_count();
2053   size_type __r       = 0;
2054   if (__np != nullptr) {
2055     for (__np = __np->__next_; __np != nullptr && std::__constrain_hash(__np->__hash(), __bc) == __n;
2056          __np = __np->__next_, (void)++__r)
2057       ;
2058   }
2059   return __r;
2062 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2063 inline _LIBCPP_HIDE_FROM_ABI void
2064 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2065     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2066   __x.swap(__y);
2069 _LIBCPP_END_NAMESPACE_STD
2071 _LIBCPP_POP_MACROS
2073 #endif // _LIBCPP___HASH_TABLE