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