llvm-project

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_constructible.h>
32
#include <__type_traits/is_nothrow_assignable.h>
33
#include <__type_traits/is_nothrow_constructible.h>
34
#include <__type_traits/is_pointer.h>
35
#include <__type_traits/is_reference.h>
36
#include <__type_traits/is_swappable.h>
37
#include <__type_traits/remove_const.h>
38
#include <__type_traits/remove_cvref.h>
39
#include <__utility/forward.h>
40
#include <__utility/move.h>
41
#include <__utility/pair.h>
42
#include <__utility/swap.h>
43
#include <cmath>
44
#include <cstring>
45
#include <initializer_list>
46
#include <new> // __launder
47

48
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
49
#  pragma GCC system_header
50
#endif
51

52
_LIBCPP_PUSH_MACROS
53
#include <__undef_macros>
54

55
_LIBCPP_BEGIN_NAMESPACE_STD
56

57
template <class _Key, class _Tp>
58
struct __hash_value_type;
59

60
template <class _Tp>
61
struct __is_hash_value_type_imp : false_type {};
62

63
template <class _Key, class _Value>
64
struct __is_hash_value_type_imp<__hash_value_type<_Key, _Value> > : true_type {};
65

66
template <class... _Args>
67
struct __is_hash_value_type : false_type {};
68

69
template <class _One>
70
struct __is_hash_value_type<_One> : __is_hash_value_type_imp<__remove_cvref_t<_One> > {};
71

72
_LIBCPP_EXPORTED_FROM_ABI size_t __next_prime(size_t __n);
73

74
template <class _NodePtr>
75
struct __hash_node_base {
76
  typedef typename pointer_traits<_NodePtr>::element_type __node_type;
77
  typedef __hash_node_base __first_node;
78
  typedef __rebind_pointer_t<_NodePtr, __first_node> __node_base_pointer;
79
  typedef _NodePtr __node_pointer;
80

81
#if defined(_LIBCPP_ABI_FIX_UNORDERED_NODE_POINTER_UB)
82
  typedef __node_base_pointer __next_pointer;
83
#else
84
  typedef __conditional_t<is_pointer<__node_pointer>::value, __node_base_pointer, __node_pointer> __next_pointer;
85
#endif
86

87
  __next_pointer __next_;
88

89
  _LIBCPP_HIDE_FROM_ABI __next_pointer __ptr() _NOEXCEPT {
90
    return static_cast<__next_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
91
  }
92

93
  _LIBCPP_HIDE_FROM_ABI __node_pointer __upcast() _NOEXCEPT {
94
    return static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(*this));
95
  }
96

97
  _LIBCPP_HIDE_FROM_ABI size_t __hash() const _NOEXCEPT { return static_cast<__node_type const&>(*this).__hash_; }
98

99
  _LIBCPP_HIDE_FROM_ABI __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
100
  _LIBCPP_HIDE_FROM_ABI explicit __hash_node_base(__next_pointer __next) _NOEXCEPT : __next_(__next) {}
101
};
102

103
template <class _Tp, class _VoidPtr>
104
struct __hash_node : public __hash_node_base< __rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > > {
105
  typedef _Tp __node_value_type;
106
  using _Base          = __hash_node_base<__rebind_pointer_t<_VoidPtr, __hash_node<_Tp, _VoidPtr> > >;
107
  using __next_pointer = typename _Base::__next_pointer;
108

109
  size_t __hash_;
110

111
  // We allow starting the lifetime of nodes without initializing the value held by the node,
112
  // since that is handled by the hash table itself in order to be allocator-aware.
113
#ifndef _LIBCPP_CXX03_LANG
114

115
private:
116
  union {
117
    _Tp __value_;
118
  };
119

120
public:
121
  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return __value_; }
122
#else
123

124
private:
125
  _ALIGNAS_TYPE(_Tp) char __buffer_[sizeof(_Tp)];
126

127
public:
128
  _LIBCPP_HIDE_FROM_ABI _Tp& __get_value() { return *std::__launder(reinterpret_cast<_Tp*>(&__buffer_)); }
129
#endif
130

131
  _LIBCPP_HIDE_FROM_ABI explicit __hash_node(__next_pointer __next, size_t __hash) : _Base(__next), __hash_(__hash) {}
132
  _LIBCPP_HIDE_FROM_ABI ~__hash_node() {}
133
};
134

135
inline _LIBCPP_HIDE_FROM_ABI bool __is_hash_power2(size_t __bc) { return __bc > 2 && !(__bc & (__bc - 1)); }
136

137
inline _LIBCPP_HIDE_FROM_ABI size_t __constrain_hash(size_t __h, size_t __bc) {
138
  return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : (__h < __bc ? __h : __h % __bc);
139
}
140

141
inline _LIBCPP_HIDE_FROM_ABI size_t __next_hash_pow2(size_t __n) {
142
  return __n < 2 ? __n : (size_t(1) << (numeric_limits<size_t>::digits - __libcpp_clz(__n - 1)));
143
}
144

145
template <class _Tp, class _Hash, class _Equal, class _Alloc>
146
class __hash_table;
147

148
template <class _NodePtr>
149
class _LIBCPP_TEMPLATE_VIS __hash_iterator;
150
template <class _ConstNodePtr>
151
class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
152
template <class _NodePtr>
153
class _LIBCPP_TEMPLATE_VIS __hash_local_iterator;
154
template <class _ConstNodePtr>
155
class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
156
template <class _HashIterator>
157
class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
158
template <class _HashIterator>
159
class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
160

161
template <class _Tp>
162
struct __hash_key_value_types {
163
  static_assert(!is_reference<_Tp>::value && !is_const<_Tp>::value, "");
164
  typedef _Tp key_type;
165
  typedef _Tp __node_value_type;
166
  typedef _Tp __container_value_type;
167
  static const bool __is_map = false;
168

169
  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(_Tp const& __v) { return __v; }
170
  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; }
171
  _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) { return std::addressof(__n); }
172
  _LIBCPP_HIDE_FROM_ABI static __container_value_type&& __move(__node_value_type& __v) { return std::move(__v); }
173
};
174

175
template <class _Key, class _Tp>
176
struct __hash_key_value_types<__hash_value_type<_Key, _Tp> > {
177
  typedef _Key key_type;
178
  typedef _Tp mapped_type;
179
  typedef __hash_value_type<_Key, _Tp> __node_value_type;
180
  typedef pair<const _Key, _Tp> __container_value_type;
181
  typedef __container_value_type __map_value_type;
182
  static const bool __is_map = true;
183

184
  _LIBCPP_HIDE_FROM_ABI static key_type const& __get_key(__container_value_type const& __v) { return __v.first; }
185

186
  template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __node_value_type>::value, int> = 0>
187
  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
188
    return __t.__get_value();
189
  }
190

191
  template <class _Up, __enable_if_t<__is_same_uncvref<_Up, __container_value_type>::value, int> = 0>
192
  _LIBCPP_HIDE_FROM_ABI static __container_value_type const& __get_value(_Up& __t) {
193
    return __t;
194
  }
195

196
  _LIBCPP_HIDE_FROM_ABI static __container_value_type* __get_ptr(__node_value_type& __n) {
197
    return std::addressof(__n.__get_value());
198
  }
199
  _LIBCPP_HIDE_FROM_ABI static pair<key_type&&, mapped_type&&> __move(__node_value_type& __v) { return __v.__move(); }
200
};
201

202
template <class _Tp, class _AllocPtr, class _KVTypes = __hash_key_value_types<_Tp>, bool = _KVTypes::__is_map>
203
struct __hash_map_pointer_types {};
204

205
template <class _Tp, class _AllocPtr, class _KVTypes>
206
struct __hash_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> {
207
  typedef typename _KVTypes::__map_value_type _Mv;
208
  typedef __rebind_pointer_t<_AllocPtr, _Mv> __map_value_type_pointer;
209
  typedef __rebind_pointer_t<_AllocPtr, const _Mv> __const_map_value_type_pointer;
210
};
211

212
template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>
213
struct __hash_node_types;
214

215
template <class _NodePtr, class _Tp, class _VoidPtr>
216
struct __hash_node_types<_NodePtr, __hash_node<_Tp, _VoidPtr> >
217
    : public __hash_key_value_types<_Tp>,
218
      __hash_map_pointer_types<_Tp, _VoidPtr>
219

220
{
221
  typedef __hash_key_value_types<_Tp> __base;
222

223
public:
224
  typedef ptrdiff_t difference_type;
225
  typedef size_t size_type;
226

227
  typedef __rebind_pointer_t<_NodePtr, void> __void_pointer;
228

229
  typedef typename pointer_traits<_NodePtr>::element_type __node_type;
230
  typedef _NodePtr __node_pointer;
231

232
  typedef __hash_node_base<__node_pointer> __node_base_type;
233
  typedef __rebind_pointer_t<_NodePtr, __node_base_type> __node_base_pointer;
234

235
  typedef typename __node_base_type::__next_pointer __next_pointer;
236

237
  typedef _Tp __node_value_type;
238
  typedef __rebind_pointer_t<_VoidPtr, __node_value_type> __node_value_type_pointer;
239
  typedef __rebind_pointer_t<_VoidPtr, const __node_value_type> __const_node_value_type_pointer;
240

241
private:
242
  static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const");
243
  static_assert(is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value,
244
                "_VoidPtr does not point to unqualified void type");
245
  static_assert(is_same<__rebind_pointer_t<_VoidPtr, __node_type>, _NodePtr>::value,
246
                "_VoidPtr does not rebind to _NodePtr.");
247
};
248

249
template <class _HashIterator>
250
struct __hash_node_types_from_iterator;
251
template <class _NodePtr>
252
struct __hash_node_types_from_iterator<__hash_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
253
template <class _NodePtr>
254
struct __hash_node_types_from_iterator<__hash_const_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
255
template <class _NodePtr>
256
struct __hash_node_types_from_iterator<__hash_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
257
template <class _NodePtr>
258
struct __hash_node_types_from_iterator<__hash_const_local_iterator<_NodePtr> > : __hash_node_types<_NodePtr> {};
259

260
template <class _NodeValueTp, class _VoidPtr>
261
struct __make_hash_node_types {
262
  typedef __hash_node<_NodeValueTp, _VoidPtr> _NodeTp;
263
  typedef __rebind_pointer_t<_VoidPtr, _NodeTp> _NodePtr;
264
  typedef __hash_node_types<_NodePtr> type;
265
};
266

267
template <class _NodePtr>
268
class _LIBCPP_TEMPLATE_VIS __hash_iterator {
269
  typedef __hash_node_types<_NodePtr> _NodeTypes;
270
  typedef _NodePtr __node_pointer;
271
  typedef typename _NodeTypes::__next_pointer __next_pointer;
272

273
  __next_pointer __node_;
274

275
public:
276
  typedef forward_iterator_tag iterator_category;
277
  typedef typename _NodeTypes::__node_value_type value_type;
278
  typedef typename _NodeTypes::difference_type difference_type;
279
  typedef value_type& reference;
280
  typedef typename _NodeTypes::__node_value_type_pointer pointer;
281

282
  _LIBCPP_HIDE_FROM_ABI __hash_iterator() _NOEXCEPT : __node_(nullptr) {}
283

284
  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
285
    _LIBCPP_ASSERT_NON_NULL(
286
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
287
    return __node_->__upcast()->__get_value();
288
  }
289

290
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
291
    _LIBCPP_ASSERT_NON_NULL(
292
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container iterator");
293
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
294
  }
295

296
  _LIBCPP_HIDE_FROM_ABI __hash_iterator& operator++() {
297
    _LIBCPP_ASSERT_NON_NULL(
298
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container iterator");
299
    __node_ = __node_->__next_;
300
    return *this;
301
  }
302

303
  _LIBCPP_HIDE_FROM_ABI __hash_iterator operator++(int) {
304
    __hash_iterator __t(*this);
305
    ++(*this);
306
    return __t;
307
  }
308

309
  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_iterator& __x, const __hash_iterator& __y) {
310
    return __x.__node_ == __y.__node_;
311
  }
312
  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y) {
313
    return !(__x == __y);
314
  }
315

316
private:
317
  _LIBCPP_HIDE_FROM_ABI explicit __hash_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
318

319
  template <class, class, class, class>
320
  friend class __hash_table;
321
  template <class>
322
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
323
  template <class>
324
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
325
  template <class, class, class, class, class>
326
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
327
  template <class, class, class, class, class>
328
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
329
};
330

331
template <class _NodePtr>
332
class _LIBCPP_TEMPLATE_VIS __hash_const_iterator {
333
  static_assert(!is_const<typename pointer_traits<_NodePtr>::element_type>::value, "");
334
  typedef __hash_node_types<_NodePtr> _NodeTypes;
335
  typedef _NodePtr __node_pointer;
336
  typedef typename _NodeTypes::__next_pointer __next_pointer;
337

338
  __next_pointer __node_;
339

340
public:
341
  typedef __hash_iterator<_NodePtr> __non_const_iterator;
342

343
  typedef forward_iterator_tag iterator_category;
344
  typedef typename _NodeTypes::__node_value_type value_type;
345
  typedef typename _NodeTypes::difference_type difference_type;
346
  typedef const value_type& reference;
347
  typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
348

349
  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator() _NOEXCEPT : __node_(nullptr) {}
350

351
  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT : __node_(__x.__node_) {}
352

353
  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
354
    _LIBCPP_ASSERT_NON_NULL(
355
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
356
    return __node_->__upcast()->__get_value();
357
  }
358
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
359
    _LIBCPP_ASSERT_NON_NULL(
360
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_iterator");
361
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
362
  }
363

364
  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator& operator++() {
365
    _LIBCPP_ASSERT_NON_NULL(
366
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_iterator");
367
    __node_ = __node_->__next_;
368
    return *this;
369
  }
370

371
  _LIBCPP_HIDE_FROM_ABI __hash_const_iterator operator++(int) {
372
    __hash_const_iterator __t(*this);
373
    ++(*this);
374
    return __t;
375
  }
376

377
  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
378
    return __x.__node_ == __y.__node_;
379
  }
380
  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y) {
381
    return !(__x == __y);
382
  }
383

384
private:
385
  _LIBCPP_HIDE_FROM_ABI explicit __hash_const_iterator(__next_pointer __node) _NOEXCEPT : __node_(__node) {}
386

387
  template <class, class, class, class>
388
  friend class __hash_table;
389
  template <class>
390
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
391
  template <class, class, class, class, class>
392
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
393
  template <class, class, class, class, class>
394
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
395
};
396

397
template <class _NodePtr>
398
class _LIBCPP_TEMPLATE_VIS __hash_local_iterator {
399
  typedef __hash_node_types<_NodePtr> _NodeTypes;
400
  typedef _NodePtr __node_pointer;
401
  typedef typename _NodeTypes::__next_pointer __next_pointer;
402

403
  __next_pointer __node_;
404
  size_t __bucket_;
405
  size_t __bucket_count_;
406

407
public:
408
  typedef forward_iterator_tag iterator_category;
409
  typedef typename _NodeTypes::__node_value_type value_type;
410
  typedef typename _NodeTypes::difference_type difference_type;
411
  typedef value_type& reference;
412
  typedef typename _NodeTypes::__node_value_type_pointer pointer;
413

414
  _LIBCPP_HIDE_FROM_ABI __hash_local_iterator() _NOEXCEPT : __node_(nullptr) {}
415

416
  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
417
    _LIBCPP_ASSERT_NON_NULL(
418
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
419
    return __node_->__upcast()->__get_value();
420
  }
421

422
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
423
    _LIBCPP_ASSERT_NON_NULL(
424
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container local_iterator");
425
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
426
  }
427

428
  _LIBCPP_HIDE_FROM_ABI __hash_local_iterator& operator++() {
429
    _LIBCPP_ASSERT_NON_NULL(
430
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container local_iterator");
431
    __node_ = __node_->__next_;
432
    if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
433
      __node_ = nullptr;
434
    return *this;
435
  }
436

437
  _LIBCPP_HIDE_FROM_ABI __hash_local_iterator operator++(int) {
438
    __hash_local_iterator __t(*this);
439
    ++(*this);
440
    return __t;
441
  }
442

443
  friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
444
    return __x.__node_ == __y.__node_;
445
  }
446
  friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y) {
447
    return !(__x == __y);
448
  }
449

450
private:
451
  _LIBCPP_HIDE_FROM_ABI explicit __hash_local_iterator(
452
      __next_pointer __node, size_t __bucket, size_t __bucket_count) _NOEXCEPT
453
      : __node_(__node),
454
        __bucket_(__bucket),
455
        __bucket_count_(__bucket_count) {
456
    if (__node_ != nullptr)
457
      __node_ = __node_->__next_;
458
  }
459

460
  template <class, class, class, class>
461
  friend class __hash_table;
462
  template <class>
463
  friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
464
  template <class>
465
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_iterator;
466
};
467

468
template <class _ConstNodePtr>
469
class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator {
470
  typedef __hash_node_types<_ConstNodePtr> _NodeTypes;
471
  typedef _ConstNodePtr __node_pointer;
472
  typedef typename _NodeTypes::__next_pointer __next_pointer;
473

474
  __next_pointer __node_;
475
  size_t __bucket_;
476
  size_t __bucket_count_;
477

478
  typedef pointer_traits<__node_pointer> __pointer_traits;
479
  typedef typename __pointer_traits::element_type __node;
480
  typedef __remove_const_t<__node> __non_const_node;
481
  typedef __rebind_pointer_t<__node_pointer, __non_const_node> __non_const_node_pointer;
482

483
public:
484
  typedef __hash_local_iterator<__non_const_node_pointer> __non_const_iterator;
485

486
  typedef forward_iterator_tag iterator_category;
487
  typedef typename _NodeTypes::__node_value_type value_type;
488
  typedef typename _NodeTypes::difference_type difference_type;
489
  typedef const value_type& reference;
490
  typedef typename _NodeTypes::__const_node_value_type_pointer pointer;
491

492
  _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator() _NOEXCEPT : __node_(nullptr) {}
493

494
  _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
495
      : __node_(__x.__node_),
496
        __bucket_(__x.__bucket_),
497
        __bucket_count_(__x.__bucket_count_) {}
498

499
  _LIBCPP_HIDE_FROM_ABI reference operator*() const {
500
    _LIBCPP_ASSERT_NON_NULL(
501
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
502
    return __node_->__upcast()->__get_value();
503
  }
504

505
  _LIBCPP_HIDE_FROM_ABI pointer operator->() const {
506
    _LIBCPP_ASSERT_NON_NULL(
507
        __node_ != nullptr, "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
508
    return pointer_traits<pointer>::pointer_to(__node_->__upcast()->__get_value());
509
  }
510

511
  _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator& operator++() {
512
    _LIBCPP_ASSERT_NON_NULL(
513
        __node_ != nullptr, "Attempted to increment a non-incrementable unordered container const_local_iterator");
514
    __node_ = __node_->__next_;
515
    if (__node_ != nullptr && std::__constrain_hash(__node_->__hash(), __bucket_count_) != __bucket_)
516
      __node_ = nullptr;
517
    return *this;
518
  }
519

520
  _LIBCPP_HIDE_FROM_ABI __hash_const_local_iterator operator++(int) {
521
    __hash_const_local_iterator __t(*this);
522
    ++(*this);
523
    return __t;
524
  }
525

526
  friend _LIBCPP_HIDE_FROM_ABI bool
527
  operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
528
    return __x.__node_ == __y.__node_;
529
  }
530
  friend _LIBCPP_HIDE_FROM_ABI bool
531
  operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y) {
532
    return !(__x == __y);
533
  }
534

535
private:
536
  _LIBCPP_HIDE_FROM_ABI explicit __hash_const_local_iterator(
537
      __next_pointer __node_ptr, size_t __bucket, size_t __bucket_count) _NOEXCEPT
538
      : __node_(__node_ptr),
539
        __bucket_(__bucket),
540
        __bucket_count_(__bucket_count) {
541
    if (__node_ != nullptr)
542
      __node_ = __node_->__next_;
543
  }
544

545
  template <class, class, class, class>
546
  friend class __hash_table;
547
  template <class>
548
  friend class _LIBCPP_TEMPLATE_VIS __hash_map_const_iterator;
549
};
550

551
template <class _Alloc>
552
class __bucket_list_deallocator {
553
  typedef _Alloc allocator_type;
554
  typedef allocator_traits<allocator_type> __alloc_traits;
555
  typedef typename __alloc_traits::size_type size_type;
556

557
  __compressed_pair<size_type, allocator_type> __data_;
558

559
public:
560
  typedef typename __alloc_traits::pointer pointer;
561

562
  _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
563
      : __data_(0, __default_init_tag()) {}
564

565
  _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(const allocator_type& __a, size_type __size)
566
      _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
567
      : __data_(__size, __a) {}
568

569
  _LIBCPP_HIDE_FROM_ABI __bucket_list_deallocator(__bucket_list_deallocator&& __x)
570
      _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
571
      : __data_(std::move(__x.__data_)) {
572
    __x.size() = 0;
573
  }
574

575
  _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __data_.first(); }
576
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __data_.first(); }
577

578
  _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return __data_.second(); }
579
  _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return __data_.second(); }
580

581
  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT { __alloc_traits::deallocate(__alloc(), __p, size()); }
582
};
583

584
template <class _Alloc>
585
class __hash_map_node_destructor;
586

587
template <class _Alloc>
588
class __hash_node_destructor {
589
  typedef _Alloc allocator_type;
590
  typedef allocator_traits<allocator_type> __alloc_traits;
591

592
public:
593
  typedef typename __alloc_traits::pointer pointer;
594

595
private:
596
  typedef __hash_node_types<pointer> _NodeTypes;
597

598
  allocator_type& __na_;
599

600
public:
601
  bool __value_constructed;
602

603
  _LIBCPP_HIDE_FROM_ABI __hash_node_destructor(__hash_node_destructor const&)            = default;
604
  _LIBCPP_HIDE_FROM_ABI __hash_node_destructor& operator=(const __hash_node_destructor&) = delete;
605

606
  _LIBCPP_HIDE_FROM_ABI explicit __hash_node_destructor(allocator_type& __na, bool __constructed = false) _NOEXCEPT
607
      : __na_(__na),
608
        __value_constructed(__constructed) {}
609

610
  _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
611
    if (__value_constructed) {
612
      __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__get_value()));
613
      std::__destroy_at(std::addressof(*__p));
614
    }
615
    if (__p)
616
      __alloc_traits::deallocate(__na_, __p, 1);
617
  }
618

619
  template <class>
620
  friend class __hash_map_node_destructor;
621
};
622

623
#if _LIBCPP_STD_VER >= 17
624
template <class _NodeType, class _Alloc>
625
struct __generic_container_node_destructor;
626

627
template <class _Tp, class _VoidPtr, class _Alloc>
628
struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc> : __hash_node_destructor<_Alloc> {
629
  using __hash_node_destructor<_Alloc>::__hash_node_destructor;
630
};
631
#endif
632

633
template <class _Key, class _Hash, class _Equal>
634
struct __enforce_unordered_container_requirements {
635
#ifndef _LIBCPP_CXX03_LANG
636
  static_assert(__check_hash_requirements<_Key, _Hash>::value,
637
                "the specified hash does not meet the Hash requirements");
638
  static_assert(is_copy_constructible<_Equal>::value, "the specified comparator is required to be copy constructible");
639
#endif
640
  typedef int type;
641
};
642

643
template <class _Key, class _Hash, class _Equal>
644
#ifndef _LIBCPP_CXX03_LANG
645
_LIBCPP_DIAGNOSE_WARNING(!__invokable<_Equal const&, _Key const&, _Key const&>::value,
646
                         "the specified comparator type does not provide a viable const call operator")
647
_LIBCPP_DIAGNOSE_WARNING(!__invokable<_Hash const&, _Key const&>::value,
648
                         "the specified hash functor does not provide a viable const call operator")
649
#endif
650
    typename __enforce_unordered_container_requirements<_Key, _Hash, _Equal>::type
651
    __diagnose_unordered_container_requirements(int);
652

653
// This dummy overload is used so that the compiler won't emit a spurious
654
// "no matching function for call to __diagnose_unordered_xxx" diagnostic
655
// when the overload above causes a hard error.
656
template <class _Key, class _Hash, class _Equal>
657
int __diagnose_unordered_container_requirements(void*);
658

659
template <class _Tp, class _Hash, class _Equal, class _Alloc>
660
class __hash_table {
661
public:
662
  typedef _Tp value_type;
663
  typedef _Hash hasher;
664
  typedef _Equal key_equal;
665
  typedef _Alloc allocator_type;
666

667
private:
668
  typedef allocator_traits<allocator_type> __alloc_traits;
669
  typedef typename __make_hash_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes;
670

671
public:
672
  typedef typename _NodeTypes::__node_value_type __node_value_type;
673
  typedef typename _NodeTypes::__container_value_type __container_value_type;
674
  typedef typename _NodeTypes::key_type key_type;
675
  typedef value_type& reference;
676
  typedef const value_type& const_reference;
677
  typedef typename __alloc_traits::pointer pointer;
678
  typedef typename __alloc_traits::const_pointer const_pointer;
679
#ifndef _LIBCPP_ABI_FIX_UNORDERED_CONTAINER_SIZE_TYPE
680
  typedef typename __alloc_traits::size_type size_type;
681
#else
682
  typedef typename _NodeTypes::size_type size_type;
683
#endif
684
  typedef typename _NodeTypes::difference_type difference_type;
685

686
public:
687
  // Create __node
688

689
  typedef typename _NodeTypes::__node_type __node;
690
  typedef __rebind_alloc<__alloc_traits, __node> __node_allocator;
691
  typedef allocator_traits<__node_allocator> __node_traits;
692
  typedef typename _NodeTypes::__void_pointer __void_pointer;
693
  typedef typename _NodeTypes::__node_pointer __node_pointer;
694
  typedef typename _NodeTypes::__node_pointer __node_const_pointer;
695
  typedef typename _NodeTypes::__node_base_type __first_node;
696
  typedef typename _NodeTypes::__node_base_pointer __node_base_pointer;
697
  typedef typename _NodeTypes::__next_pointer __next_pointer;
698

699
private:
700
  // check for sane allocator pointer rebinding semantics. Rebinding the
701
  // allocator for a new pointer type should be exactly the same as rebinding
702
  // the pointer using 'pointer_traits'.
703
  static_assert(is_same<__node_pointer, typename __node_traits::pointer>::value,
704
                "Allocator does not rebind pointers in a sane manner.");
705
  typedef __rebind_alloc<__node_traits, __first_node> __node_base_allocator;
706
  typedef allocator_traits<__node_base_allocator> __node_base_traits;
707
  static_assert(is_same<__node_base_pointer, typename __node_base_traits::pointer>::value,
708
                "Allocator does not rebind pointers in a sane manner.");
709

710
private:
711
  typedef __rebind_alloc<__node_traits, __next_pointer> __pointer_allocator;
712
  typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
713
  typedef unique_ptr<__next_pointer[], __bucket_list_deleter> __bucket_list;
714
  typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
715
  typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
716

717
  // --- Member data begin ---
718
  __bucket_list __bucket_list_;
719
  __compressed_pair<__first_node, __node_allocator> __p1_;
720
  __compressed_pair<size_type, hasher> __p2_;
721
  __compressed_pair<float, key_equal> __p3_;
722
  // --- Member data end ---
723

724
  _LIBCPP_HIDE_FROM_ABI size_type& size() _NOEXCEPT { return __p2_.first(); }
725

726
public:
727
  _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __p2_.first(); }
728

729
  _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT { return __p2_.second(); }
730
  _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT { return __p2_.second(); }
731

732
  _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT { return __p3_.first(); }
733
  _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __p3_.first(); }
734

735
  _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT { return __p3_.second(); }
736
  _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT { return __p3_.second(); }
737

738
  _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __p1_.second(); }
739
  _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __p1_.second(); }
740

741
public:
742
  typedef __hash_iterator<__node_pointer> iterator;
743
  typedef __hash_const_iterator<__node_pointer> const_iterator;
744
  typedef __hash_local_iterator<__node_pointer> local_iterator;
745
  typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
746

747
  _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_(
748
      is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
749
          is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
750
              is_nothrow_default_constructible<key_equal>::value);
751
  _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql);
752
  _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
753
  _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);
754
  _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);
755
  _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);
756
  _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u) _NOEXCEPT_(
757
      is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
758
          is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
759
              is_nothrow_move_constructible<key_equal>::value);
760
  _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);
761
  _LIBCPP_HIDE_FROM_ABI ~__hash_table();
762

763
  _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);
764
  _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u)
765
      _NOEXCEPT_(__node_traits::propagate_on_container_move_assignment::value&&
766
                     is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
767
                         is_nothrow_move_assignable<key_equal>::value);
768
  template <class _InputIterator>
769
  _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);
770
  template <class _InputIterator>
771
  _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
772

773
  _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
774
    return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());
775
  }
776

777
private:
778
  _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val);
779
  _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT;
780

781
  _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val);
782
  _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
783

784
public:
785
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
786
  _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
787
  _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
788

789
  template <class _Key, class... _Args>
790
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_key_args(_Key const& __k, _Args&&... __args);
791

792
  template <class... _Args>
793
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_impl(_Args&&... __args);
794

795
  template <class _Pp>
796
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Pp&& __x) {
797
    return __emplace_unique_extract_key(std::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>());
798
  }
799

800
  template <class _First,
801
            class _Second,
802
            __enable_if_t<__can_extract_map_key<_First, key_type, __container_value_type>::value, int> = 0>
803
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_First&& __f, _Second&& __s) {
804
    return __emplace_unique_key_args(__f, std::forward<_First>(__f), std::forward<_Second>(__s));
805
  }
806

807
  template <class... _Args>
808
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
809
    return __emplace_unique_impl(std::forward<_Args>(__args)...);
810
  }
811

812
  template <class _Pp>
813
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
814
    return __emplace_unique_impl(std::forward<_Pp>(__x));
815
  }
816
  template <class _Pp>
817
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
818
    return __emplace_unique_key_args(__x, std::forward<_Pp>(__x));
819
  }
820
  template <class _Pp>
821
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
822
    return __emplace_unique_key_args(__x.first, std::forward<_Pp>(__x));
823
  }
824

825
  template <class... _Args>
826
  _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
827
  template <class... _Args>
828
  _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
829

830
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(__container_value_type&& __x) {
831
    return __emplace_unique_key_args(_NodeTypes::__get_key(__x), std::move(__x));
832
  }
833

834
  template <class _Pp, __enable_if_t<!__is_same_uncvref<_Pp, __container_value_type>::value, int> = 0>
835
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(_Pp&& __x) {
836
    return __emplace_unique(std::forward<_Pp>(__x));
837
  }
838

839
  template <class _Pp>
840
  _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(_Pp&& __x) {
841
    return __emplace_multi(std::forward<_Pp>(__x));
842
  }
843

844
  template <class _Pp>
845
  _LIBCPP_HIDE_FROM_ABI iterator __insert_multi(const_iterator __p, _Pp&& __x) {
846
    return __emplace_hint_multi(__p, std::forward<_Pp>(__x));
847
  }
848

849
  _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
850
    return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
851
  }
852

853
#if _LIBCPP_STD_VER >= 17
854
  template <class _NodeHandle, class _InsertReturnType>
855
  _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
856
  template <class _NodeHandle>
857
  _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh);
858
  template <class _Table>
859
  _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source);
860

861
  template <class _NodeHandle>
862
  _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh);
863
  template <class _NodeHandle>
864
  _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
865
  template <class _Table>
866
  _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source);
867

868
  template <class _NodeHandle>
869
  _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key);
870
  template <class _NodeHandle>
871
  _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it);
872
#endif
873

874
  _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
875
  _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); }
876
  _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); }
877
  _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) {
878
    __rehash_unique(static_cast<size_type>(std::ceil(__n / max_load_factor())));
879
  }
880
  _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) {
881
    __rehash_multi(static_cast<size_type>(std::ceil(__n / max_load_factor())));
882
  }
883

884
  _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); }
885

886
  _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
887
  _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
888
  _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
889
  _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
890

891
  template <class _Key>
892
  _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const {
893
    _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
894
        bucket_count() > 0, "unordered container::bucket(key) called when bucket_count() == 0");
895
    return std::__constrain_hash(hash_function()(__k), bucket_count());
896
  }
897

898
  template <class _Key>
899
  _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __x);
900
  template <class _Key>
901
  _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;
902

903
  typedef __hash_node_destructor<__node_allocator> _Dp;
904
  typedef unique_ptr<__node, _Dp> __node_holder;
905

906
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
907
  _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
908
  template <class _Key>
909
  _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
910
  template <class _Key>
911
  _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
912
  _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
913

914
  template <class _Key>
915
  _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
916
  template <class _Key>
917
  _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
918

919
  template <class _Key>
920
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);
921
  template <class _Key>
922
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;
923

924
  template <class _Key>
925
  _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);
926
  template <class _Key>
927
  _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;
928

929
  _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)
930
#if _LIBCPP_STD_VER <= 11
931
      _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
932
                 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
933
                  __is_nothrow_swappable_v<__pointer_allocator>) &&
934
                 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));
935
#else
936
      _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>);
937
#endif
938

939
  _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return max_size(); }
940
  _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;
941
  _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT {
942
    size_type __bc = bucket_count();
943
    return __bc != 0 ? (float)size() / __bc : 0.f;
944
  }
945
  _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT {
946
    // While passing a non-positive load factor is undefined behavior, in practice the result will be benign (the
947
    // call will be equivalent to `max_load_factor(load_factor())`, which is also the case for passing a valid value
948
    // less than the current `load_factor`).
949
    _LIBCPP_ASSERT_PEDANTIC(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0");
950
    max_load_factor() = std::max(__mlf, load_factor());
951
  }
952

953
  _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) {
954
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
955
        __n < bucket_count(), "unordered container::begin(n) called with n >= bucket_count()");
956
    return local_iterator(__bucket_list_[__n], __n, bucket_count());
957
  }
958

959
  _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) {
960
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
961
        __n < bucket_count(), "unordered container::end(n) called with n >= bucket_count()");
962
    return local_iterator(nullptr, __n, bucket_count());
963
  }
964

965
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const {
966
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
967
        __n < bucket_count(), "unordered container::cbegin(n) called with n >= bucket_count()");
968
    return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
969
  }
970

971
  _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const {
972
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
973
        __n < bucket_count(), "unordered container::cend(n) called with n >= bucket_count()");
974
    return const_local_iterator(nullptr, __n, bucket_count());
975
  }
976

977
private:
978
  template <bool _UniqueKeys>
979
  _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);
980
  template <bool _UniqueKeys>
981
  _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);
982

983
  template <class... _Args>
984
  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
985

986
  template <class _First, class... _Rest>
987
  _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest);
988

989
  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
990
    __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
991
  }
992
  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);
993
  _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {}
994

995
  _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);
996
  _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)
997
      _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
998
                     is_nothrow_move_assignable<key_equal>::value);
999
  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_(
1000
      !__node_traits::propagate_on_container_move_assignment::value ||
1001
      (is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value)) {
1002
    __move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1003
  }
1004
  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_(
1005
      is_nothrow_move_assignable<__pointer_allocator>::value&& is_nothrow_move_assignable<__node_allocator>::value) {
1006
    __bucket_list_.get_deleter().__alloc() = std::move(__u.__bucket_list_.get_deleter().__alloc());
1007
    __node_alloc()                         = std::move(__u.__node_alloc());
1008
  }
1009
  _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1010

1011
  _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__next_pointer __np) _NOEXCEPT;
1012
  _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
1013

1014
  template <class, class, class, class, class>
1015
  friend class _LIBCPP_TEMPLATE_VIS unordered_map;
1016
  template <class, class, class, class, class>
1017
  friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
1018
};
1019

1020
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1021
inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() _NOEXCEPT_(
1022
    is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
1023
        is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
1024
            is_nothrow_default_constructible<key_equal>::value)
1025
    : __p2_(0, __default_init_tag()), __p3_(1.0f, __default_init_tag()) {}
1026

1027
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1028
inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, const key_equal& __eql)
1029
    : __bucket_list_(nullptr, __bucket_list_deleter()), __p1_(), __p2_(0, __hf), __p3_(1.0f, __eql) {}
1030

1031
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1032
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(
1033
    const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1034
    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1035
      __p1_(__default_init_tag(), __node_allocator(__a)),
1036
      __p2_(0, __hf),
1037
      __p3_(1.0f, __eql) {}
1038

1039
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1040
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1041
    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1042
      __p1_(__default_init_tag(), __node_allocator(__a)),
1043
      __p2_(0, __default_init_tag()),
1044
      __p3_(1.0f, __default_init_tag()) {}
1045

1046
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1047
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1048
    : __bucket_list_(nullptr,
1049
                     __bucket_list_deleter(allocator_traits<__pointer_allocator>::select_on_container_copy_construction(
1050
                                               __u.__bucket_list_.get_deleter().__alloc()),
1051
                                           0)),
1052
      __p1_(__default_init_tag(),
1053
            allocator_traits<__node_allocator>::select_on_container_copy_construction(__u.__node_alloc())),
1054
      __p2_(0, __u.hash_function()),
1055
      __p3_(__u.__p3_) {}
1056

1057
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1058
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, const allocator_type& __a)
1059
    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1060
      __p1_(__default_init_tag(), __node_allocator(__a)),
1061
      __p2_(0, __u.hash_function()),
1062
      __p3_(__u.__p3_) {}
1063

1064
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1065
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) _NOEXCEPT_(
1066
    is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
1067
        is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
1068
            is_nothrow_move_constructible<key_equal>::value)
1069
    : __bucket_list_(std::move(__u.__bucket_list_)),
1070
      __p1_(std::move(__u.__p1_)),
1071
      __p2_(std::move(__u.__p2_)),
1072
      __p3_(std::move(__u.__p3_)) {
1073
  if (size() > 0) {
1074
    __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
1075
    __u.__p1_.first().__next_                                                              = nullptr;
1076
    __u.size()                                                                             = 0;
1077
  }
1078
}
1079

1080
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1081
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a)
1082
    : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1083
      __p1_(__default_init_tag(), __node_allocator(__a)),
1084
      __p2_(0, std::move(__u.hash_function())),
1085
      __p3_(std::move(__u.__p3_)) {
1086
  if (__a == allocator_type(__u.__node_alloc())) {
1087
    __bucket_list_.reset(__u.__bucket_list_.release());
1088
    __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
1089
    __u.__bucket_list_.get_deleter().size() = 0;
1090
    if (__u.size() > 0) {
1091
      __p1_.first().__next_     = __u.__p1_.first().__next_;
1092
      __u.__p1_.first().__next_ = nullptr;
1093
      __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
1094
      size()                                                                                 = __u.size();
1095
      __u.size()                                                                             = 0;
1096
    }
1097
  }
1098
}
1099

1100
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1101
__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {
1102
#if defined(_LIBCPP_CXX03_LANG)
1103
  static_assert(is_copy_constructible<key_equal>::value, "Predicate must be copy-constructible.");
1104
  static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");
1105
#endif
1106

1107
  __deallocate_node(__p1_.first().__next_);
1108
}
1109

1110
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1111
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(const __hash_table& __u, true_type) {
1112
  if (__node_alloc() != __u.__node_alloc()) {
1113
    clear();
1114
    __bucket_list_.reset();
1115
    __bucket_list_.get_deleter().size() = 0;
1116
  }
1117
  __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1118
  __node_alloc()                         = __u.__node_alloc();
1119
}
1120

1121
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1122
__hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u) {
1123
  if (this != std::addressof(__u)) {
1124
    __copy_assign_alloc(__u);
1125
    hash_function()   = __u.hash_function();
1126
    key_eq()          = __u.key_eq();
1127
    max_load_factor() = __u.max_load_factor();
1128
    __assign_multi(__u.begin(), __u.end());
1129
  }
1130
  return *this;
1131
}
1132

1133
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1134
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) _NOEXCEPT {
1135
  __node_allocator& __na = __node_alloc();
1136
  while (__np != nullptr) {
1137
    __next_pointer __next    = __np->__next_;
1138
    __node_pointer __real_np = __np->__upcast();
1139
    __node_traits::destroy(__na, _NodeTypes::__get_ptr(__real_np->__get_value()));
1140
    std::__destroy_at(std::addressof(*__real_np));
1141
    __node_traits::deallocate(__na, __real_np, 1);
1142
    __np = __next;
1143
  }
1144
}
1145

1146
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1147
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1148
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {
1149
  size_type __bc = bucket_count();
1150
  for (size_type __i = 0; __i < __bc; ++__i)
1151
    __bucket_list_[__i] = nullptr;
1152
  size()                 = 0;
1153
  __next_pointer __cache = __p1_.first().__next_;
1154
  __p1_.first().__next_  = nullptr;
1155
  return __cache;
1156
}
1157

1158
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1159
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, true_type)
1160
    _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1161
                   is_nothrow_move_assignable<key_equal>::value) {
1162
  clear();
1163
  __bucket_list_.reset(__u.__bucket_list_.release());
1164
  __bucket_list_.get_deleter().size()     = __u.__bucket_list_.get_deleter().size();
1165
  __u.__bucket_list_.get_deleter().size() = 0;
1166
  __move_assign_alloc(__u);
1167
  size()                = __u.size();
1168
  hash_function()       = std::move(__u.hash_function());
1169
  max_load_factor()     = __u.max_load_factor();
1170
  key_eq()              = std::move(__u.key_eq());
1171
  __p1_.first().__next_ = __u.__p1_.first().__next_;
1172
  if (size() > 0) {
1173
    __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
1174
    __u.__p1_.first().__next_                                                              = nullptr;
1175
    __u.size()                                                                             = 0;
1176
  }
1177
}
1178

1179
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1180
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, false_type) {
1181
  if (__node_alloc() == __u.__node_alloc())
1182
    __move_assign(__u, true_type());
1183
  else {
1184
    hash_function()   = std::move(__u.hash_function());
1185
    key_eq()          = std::move(__u.key_eq());
1186
    max_load_factor() = __u.max_load_factor();
1187
    if (bucket_count() != 0) {
1188
      __next_pointer __cache = __detach();
1189
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1190
      try {
1191
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1192
        const_iterator __i = __u.begin();
1193
        while (__cache != nullptr && __u.size() != 0) {
1194
          __cache->__upcast()->__get_value() = std::move(__u.remove(__i++)->__get_value());
1195
          __next_pointer __next              = __cache->__next_;
1196
          __node_insert_multi(__cache->__upcast());
1197
          __cache = __next;
1198
        }
1199
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1200
      } catch (...) {
1201
        __deallocate_node(__cache);
1202
        throw;
1203
      }
1204
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1205
      __deallocate_node(__cache);
1206
    }
1207
    const_iterator __i = __u.begin();
1208
    while (__u.size() != 0) {
1209
      __node_holder __h = __construct_node(_NodeTypes::__move(__u.remove(__i++)->__get_value()));
1210
      __node_insert_multi(__h.get());
1211
      __h.release();
1212
    }
1213
  }
1214
}
1215

1216
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1217
inline __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1218
__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u) _NOEXCEPT_(
1219
    __node_traits::propagate_on_container_move_assignment::value&& is_nothrow_move_assignable<__node_allocator>::value&&
1220
        is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value) {
1221
  __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1222
  return *this;
1223
}
1224

1225
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1226
template <class _InputIterator>
1227
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, _InputIterator __last) {
1228
  typedef iterator_traits<_InputIterator> _ITraits;
1229
  typedef typename _ITraits::value_type _ItValueType;
1230
  static_assert(is_same<_ItValueType, __container_value_type>::value,
1231
                "__assign_unique may only be called with the containers value type");
1232

1233
  if (bucket_count() != 0) {
1234
    __next_pointer __cache = __detach();
1235
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1236
    try {
1237
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1238
      for (; __cache != nullptr && __first != __last; ++__first) {
1239
        __cache->__upcast()->__get_value() = *__first;
1240
        __next_pointer __next              = __cache->__next_;
1241
        __node_insert_unique(__cache->__upcast());
1242
        __cache = __next;
1243
      }
1244
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1245
    } catch (...) {
1246
      __deallocate_node(__cache);
1247
      throw;
1248
    }
1249
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1250
    __deallocate_node(__cache);
1251
  }
1252
  for (; __first != __last; ++__first)
1253
    __insert_unique(*__first);
1254
}
1255

1256
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1257
template <class _InputIterator>
1258
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, _InputIterator __last) {
1259
  typedef iterator_traits<_InputIterator> _ITraits;
1260
  typedef typename _ITraits::value_type _ItValueType;
1261
  static_assert(
1262
      (is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value),
1263
      "__assign_multi may only be called with the containers value type"
1264
      " or the nodes value type");
1265
  if (bucket_count() != 0) {
1266
    __next_pointer __cache = __detach();
1267
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1268
    try {
1269
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1270
      for (; __cache != nullptr && __first != __last; ++__first) {
1271
        __cache->__upcast()->__get_value() = *__first;
1272
        __next_pointer __next              = __cache->__next_;
1273
        __node_insert_multi(__cache->__upcast());
1274
        __cache = __next;
1275
      }
1276
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1277
    } catch (...) {
1278
      __deallocate_node(__cache);
1279
      throw;
1280
    }
1281
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1282
    __deallocate_node(__cache);
1283
  }
1284
  for (; __first != __last; ++__first)
1285
    __insert_multi(_NodeTypes::__get_value(*__first));
1286
}
1287

1288
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1289
inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1290
__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT {
1291
  return iterator(__p1_.first().__next_);
1292
}
1293

1294
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1295
inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1296
__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT {
1297
  return iterator(nullptr);
1298
}
1299

1300
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1301
inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1302
__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT {
1303
  return const_iterator(__p1_.first().__next_);
1304
}
1305

1306
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1307
inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1308
__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {
1309
  return const_iterator(nullptr);
1310
}
1311

1312
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1313
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {
1314
  if (size() > 0) {
1315
    __deallocate_node(__p1_.first().__next_);
1316
    __p1_.first().__next_ = nullptr;
1317
    size_type __bc        = bucket_count();
1318
    for (size_type __i = 0; __i < __bc; ++__i)
1319
      __bucket_list_[__i] = nullptr;
1320
    size() = 0;
1321
  }
1322
}
1323

1324
// Prepare the container for an insertion of the value __value with the hash
1325
// __hash. This does a lookup into the container to see if __value is already
1326
// present, and performs a rehash if necessary. Returns a pointer to the
1327
// existing element if it exists, otherwise nullptr.
1328
//
1329
// Note that this function does forward exceptions if key_eq() throws, and never
1330
// mutates __value or actually inserts into the map.
1331
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1332
_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1333
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {
1334
  size_type __bc = bucket_count();
1335

1336
  if (__bc != 0) {
1337
    size_t __chash         = std::__constrain_hash(__hash, __bc);
1338
    __next_pointer __ndptr = __bucket_list_[__chash];
1339
    if (__ndptr != nullptr) {
1340
      for (__ndptr = __ndptr->__next_;
1341
           __ndptr != nullptr &&
1342
           (__ndptr->__hash() == __hash || std::__constrain_hash(__ndptr->__hash(), __bc) == __chash);
1343
           __ndptr = __ndptr->__next_) {
1344
        if ((__ndptr->__hash() == __hash) && key_eq()(__ndptr->__upcast()->__get_value(), __value))
1345
          return __ndptr;
1346
      }
1347
    }
1348
  }
1349
  if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1350
    __rehash_unique(std::max<size_type>(
1351
        2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1352
  }
1353
  return nullptr;
1354
}
1355

1356
// Insert the node __nd into the container by pushing it into the right bucket,
1357
// and updating size(). Assumes that __nd->__hash is up-to-date, and that
1358
// rehashing has already occurred and that no element with the same key exists
1359
// in the map.
1360
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1361
_LIBCPP_HIDE_FROM_ABI void
1362
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {
1363
  size_type __bc = bucket_count();
1364
  size_t __chash = std::__constrain_hash(__nd->__hash(), __bc);
1365
  // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1366
  __next_pointer __pn = __bucket_list_[__chash];
1367
  if (__pn == nullptr) {
1368
    __pn          = __p1_.first().__ptr();
1369
    __nd->__next_ = __pn->__next_;
1370
    __pn->__next_ = __nd->__ptr();
1371
    // fix up __bucket_list_
1372
    __bucket_list_[__chash] = __pn;
1373
    if (__nd->__next_ != nullptr)
1374
      __bucket_list_[std::__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
1375
  } else {
1376
    __nd->__next_ = __pn->__next_;
1377
    __pn->__next_ = __nd->__ptr();
1378
  }
1379
  ++size();
1380
}
1381

1382
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1383
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1384
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) {
1385
  __nd->__hash_                  = hash_function()(__nd->__get_value());
1386
  __next_pointer __existing_node = __node_insert_unique_prepare(__nd->__hash(), __nd->__get_value());
1387

1388
  // Insert the node, unless it already exists in the container.
1389
  bool __inserted = false;
1390
  if (__existing_node == nullptr) {
1391
    __node_insert_unique_perform(__nd);
1392
    __existing_node = __nd->__ptr();
1393
    __inserted      = true;
1394
  }
1395
  return pair<iterator, bool>(iterator(__existing_node), __inserted);
1396
}
1397

1398
// Prepare the container for an insertion of the value __cp_val with the hash
1399
// __cp_hash. This does a lookup into the container to see if __cp_value is
1400
// already present, and performs a rehash if necessary. Returns a pointer to the
1401
// last occurrence of __cp_val in the map.
1402
//
1403
// Note that this function does forward exceptions if key_eq() throws, and never
1404
// mutates __value or actually inserts into the map.
1405
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1406
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1407
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {
1408
  size_type __bc = bucket_count();
1409
  if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1410
    __rehash_multi(std::max<size_type>(
1411
        2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1412
    __bc = bucket_count();
1413
  }
1414
  size_t __chash      = std::__constrain_hash(__cp_hash, __bc);
1415
  __next_pointer __pn = __bucket_list_[__chash];
1416
  if (__pn != nullptr) {
1417
    for (bool __found = false;
1418
         __pn->__next_ != nullptr && std::__constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
1419
         __pn = __pn->__next_) {
1420
      //      __found    key_eq()     action
1421
      //      false       false       loop
1422
      //      true        true        loop
1423
      //      false       true        set __found to true
1424
      //      true        false       break
1425
      if (__found !=
1426
          (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) {
1427
        if (!__found)
1428
          __found = true;
1429
        else
1430
          break;
1431
      }
1432
    }
1433
  }
1434
  return __pn;
1435
}
1436

1437
// Insert the node __cp into the container after __pn (which is the last node in
1438
// the bucket that compares equal to __cp). Rehashing, and checking for
1439
// uniqueness has already been performed (in __node_insert_multi_prepare), so
1440
// all we need to do is update the bucket and size(). Assumes that __cp->__hash
1441
// is up-to-date.
1442
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1443
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
1444
    __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {
1445
  size_type __bc = bucket_count();
1446
  size_t __chash = std::__constrain_hash(__cp->__hash_, __bc);
1447
  if (__pn == nullptr) {
1448
    __pn          = __p1_.first().__ptr();
1449
    __cp->__next_ = __pn->__next_;
1450
    __pn->__next_ = __cp->__ptr();
1451
    // fix up __bucket_list_
1452
    __bucket_list_[__chash] = __pn;
1453
    if (__cp->__next_ != nullptr)
1454
      __bucket_list_[std::__constrain_hash(__cp->__next_->__hash(), __bc)] = __cp->__ptr();
1455
  } else {
1456
    __cp->__next_ = __pn->__next_;
1457
    __pn->__next_ = __cp->__ptr();
1458
    if (__cp->__next_ != nullptr) {
1459
      size_t __nhash = std::__constrain_hash(__cp->__next_->__hash(), __bc);
1460
      if (__nhash != __chash)
1461
        __bucket_list_[__nhash] = __cp->__ptr();
1462
    }
1463
  }
1464
  ++size();
1465
}
1466

1467
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1468
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1469
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) {
1470
  __cp->__hash_       = hash_function()(__cp->__get_value());
1471
  __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__get_value());
1472
  __node_insert_multi_perform(__cp, __pn);
1473

1474
  return iterator(__cp->__ptr());
1475
}
1476

1477
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1478
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1479
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {
1480
  if (__p != end() && key_eq()(*__p, __cp->__get_value())) {
1481
    __next_pointer __np = __p.__node_;
1482
    __cp->__hash_       = __np->__hash();
1483
    size_type __bc      = bucket_count();
1484
    if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1485
      __rehash_multi(std::max<size_type>(
1486
          2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1487
      __bc = bucket_count();
1488
    }
1489
    size_t __chash      = std::__constrain_hash(__cp->__hash_, __bc);
1490
    __next_pointer __pp = __bucket_list_[__chash];
1491
    while (__pp->__next_ != __np)
1492
      __pp = __pp->__next_;
1493
    __cp->__next_ = __np;
1494
    __pp->__next_ = static_cast<__next_pointer>(__cp);
1495
    ++size();
1496
    return iterator(static_cast<__next_pointer>(__cp));
1497
  }
1498
  return __node_insert_multi(__cp);
1499
}
1500

1501
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1502
template <class _Key, class... _Args>
1503
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1504
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args) {
1505
  size_t __hash   = hash_function()(__k);
1506
  size_type __bc  = bucket_count();
1507
  bool __inserted = false;
1508
  __next_pointer __nd;
1509
  size_t __chash;
1510
  if (__bc != 0) {
1511
    __chash = std::__constrain_hash(__hash, __bc);
1512
    __nd    = __bucket_list_[__chash];
1513
    if (__nd != nullptr) {
1514
      for (__nd = __nd->__next_;
1515
           __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1516
           __nd = __nd->__next_) {
1517
        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1518
          goto __done;
1519
      }
1520
    }
1521
  }
1522
  {
1523
    __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args)...);
1524
    if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1525
      __rehash_unique(std::max<size_type>(
1526
          2 * __bc + !std::__is_hash_power2(__bc), size_type(std::ceil(float(size() + 1) / max_load_factor()))));
1527
      __bc    = bucket_count();
1528
      __chash = std::__constrain_hash(__hash, __bc);
1529
    }
1530
    // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1531
    __next_pointer __pn = __bucket_list_[__chash];
1532
    if (__pn == nullptr) {
1533
      __pn          = __p1_.first().__ptr();
1534
      __h->__next_  = __pn->__next_;
1535
      __pn->__next_ = __h.get()->__ptr();
1536
      // fix up __bucket_list_
1537
      __bucket_list_[__chash] = __pn;
1538
      if (__h->__next_ != nullptr)
1539
        __bucket_list_[std::__constrain_hash(__h->__next_->__hash(), __bc)] = __h.get()->__ptr();
1540
    } else {
1541
      __h->__next_  = __pn->__next_;
1542
      __pn->__next_ = static_cast<__next_pointer>(__h.get());
1543
    }
1544
    __nd = static_cast<__next_pointer>(__h.release());
1545
    // increment size
1546
    ++size();
1547
    __inserted = true;
1548
  }
1549
__done:
1550
  return pair<iterator, bool>(iterator(__nd), __inserted);
1551
}
1552

1553
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1554
template <class... _Args>
1555
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1556
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique_impl(_Args&&... __args) {
1557
  __node_holder __h        = __construct_node(std::forward<_Args>(__args)...);
1558
  pair<iterator, bool> __r = __node_insert_unique(__h.get());
1559
  if (__r.second)
1560
    __h.release();
1561
  return __r;
1562
}
1563

1564
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1565
template <class... _Args>
1566
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1567
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
1568
  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1569
  iterator __r      = __node_insert_multi(__h.get());
1570
  __h.release();
1571
  return __r;
1572
}
1573

1574
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1575
template <class... _Args>
1576
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1577
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
1578
  __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1579
  iterator __r      = __node_insert_multi(__p, __h.get());
1580
  __h.release();
1581
  return __r;
1582
}
1583

1584
#if _LIBCPP_STD_VER >= 17
1585
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1586
template <class _NodeHandle, class _InsertReturnType>
1587
_LIBCPP_HIDE_FROM_ABI _InsertReturnType
1588
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(_NodeHandle&& __nh) {
1589
  if (__nh.empty())
1590
    return _InsertReturnType{end(), false, _NodeHandle()};
1591
  pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1592
  if (__result.second)
1593
    __nh.__release_ptr();
1594
  return _InsertReturnType{__result.first, __result.second, std::move(__nh)};
1595
}
1596

1597
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1598
template <class _NodeHandle>
1599
_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1600
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {
1601
  if (__nh.empty())
1602
    return end();
1603
  pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
1604
  if (__result.second)
1605
    __nh.__release_ptr();
1606
  return __result.first;
1607
}
1608

1609
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1610
template <class _NodeHandle>
1611
_LIBCPP_HIDE_FROM_ABI _NodeHandle
1612
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(key_type const& __key) {
1613
  iterator __i = find(__key);
1614
  if (__i == end())
1615
    return _NodeHandle();
1616
  return __node_handle_extract<_NodeHandle>(__i);
1617
}
1618

1619
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1620
template <class _NodeHandle>
1621
_LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(const_iterator __p) {
1622
  allocator_type __alloc(__node_alloc());
1623
  return _NodeHandle(remove(__p).release(), __alloc);
1624
}
1625

1626
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1627
template <class _Table>
1628
_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(_Table& __source) {
1629
  static_assert(is_same<__node, typename _Table::__node>::value, "");
1630

1631
  for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1632
    __node_pointer __src_ptr       = __it.__node_->__upcast();
1633
    size_t __hash                  = hash_function()(__src_ptr->__get_value());
1634
    __next_pointer __existing_node = __node_insert_unique_prepare(__hash, __src_ptr->__get_value());
1635
    auto __prev_iter               = __it++;
1636
    if (__existing_node == nullptr) {
1637
      (void)__source.remove(__prev_iter).release();
1638
      __src_ptr->__hash_ = __hash;
1639
      __node_insert_unique_perform(__src_ptr);
1640
    }
1641
  }
1642
}
1643

1644
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1645
template <class _NodeHandle>
1646
_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1647
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(_NodeHandle&& __nh) {
1648
  if (__nh.empty())
1649
    return end();
1650
  iterator __result = __node_insert_multi(__nh.__ptr_);
1651
  __nh.__release_ptr();
1652
  return __result;
1653
}
1654

1655
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1656
template <class _NodeHandle>
1657
_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1658
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {
1659
  if (__nh.empty())
1660
    return end();
1661
  iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
1662
  __nh.__release_ptr();
1663
  return __result;
1664
}
1665

1666
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1667
template <class _Table>
1668
_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(_Table& __source) {
1669
  static_assert(is_same<typename _Table::__node, __node>::value, "");
1670

1671
  for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1672
    __node_pointer __src_ptr = __it.__node_->__upcast();
1673
    size_t __src_hash        = hash_function()(__src_ptr->__get_value());
1674
    __next_pointer __pn      = __node_insert_multi_prepare(__src_hash, __src_ptr->__get_value());
1675
    (void)__source.remove(__it++).release();
1676
    __src_ptr->__hash_ = __src_hash;
1677
    __node_insert_multi_perform(__src_ptr, __pn);
1678
  }
1679
}
1680
#endif // _LIBCPP_STD_VER >= 17
1681

1682
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1683
template <bool _UniqueKeys>
1684
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
1685
  if (__n == 1)
1686
    __n = 2;
1687
  else if (__n & (__n - 1))
1688
    __n = std::__next_prime(__n);
1689
  size_type __bc = bucket_count();
1690
  if (__n > __bc)
1691
    __do_rehash<_UniqueKeys>(__n);
1692
  else if (__n < __bc) {
1693
    __n = std::max<size_type>(
1694
        __n,
1695
        std::__is_hash_power2(__bc) ? std::__next_hash_pow2(size_t(std::ceil(float(size()) / max_load_factor())))
1696
                                    : std::__next_prime(size_t(std::ceil(float(size()) / max_load_factor()))));
1697
    if (__n < __bc)
1698
      __do_rehash<_UniqueKeys>(__n);
1699
  }
1700
}
1701

1702
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1703
template <bool _UniqueKeys>
1704
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __nbc) {
1705
  __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1706
  __bucket_list_.reset(__nbc > 0 ? __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1707
  __bucket_list_.get_deleter().size() = __nbc;
1708
  if (__nbc > 0) {
1709
    for (size_type __i = 0; __i < __nbc; ++__i)
1710
      __bucket_list_[__i] = nullptr;
1711
    __next_pointer __pp = __p1_.first().__ptr();
1712
    __next_pointer __cp = __pp->__next_;
1713
    if (__cp != nullptr) {
1714
      size_type __chash       = std::__constrain_hash(__cp->__hash(), __nbc);
1715
      __bucket_list_[__chash] = __pp;
1716
      size_type __phash       = __chash;
1717
      for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {
1718
        __chash = std::__constrain_hash(__cp->__hash(), __nbc);
1719
        if (__chash == __phash)
1720
          __pp = __cp;
1721
        else {
1722
          if (__bucket_list_[__chash] == nullptr) {
1723
            __bucket_list_[__chash] = __pp;
1724
            __pp                    = __cp;
1725
            __phash                 = __chash;
1726
          } else {
1727
            __next_pointer __np = __cp;
1728
            if _LIBCPP_CONSTEXPR_SINCE_CXX17 (!_UniqueKeys) {
1729
              for (; __np->__next_ != nullptr &&
1730
                     key_eq()(__cp->__upcast()->__get_value(), __np->__next_->__upcast()->__get_value());
1731
                   __np = __np->__next_)
1732
                ;
1733
            }
1734
            __pp->__next_                    = __np->__next_;
1735
            __np->__next_                    = __bucket_list_[__chash]->__next_;
1736
            __bucket_list_[__chash]->__next_ = __cp;
1737
          }
1738
        }
1739
      }
1740
    }
1741
  }
1742
}
1743

1744
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1745
template <class _Key>
1746
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1747
__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) {
1748
  size_t __hash  = hash_function()(__k);
1749
  size_type __bc = bucket_count();
1750
  if (__bc != 0) {
1751
    size_t __chash      = std::__constrain_hash(__hash, __bc);
1752
    __next_pointer __nd = __bucket_list_[__chash];
1753
    if (__nd != nullptr) {
1754
      for (__nd = __nd->__next_;
1755
           __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1756
           __nd = __nd->__next_) {
1757
        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1758
          return iterator(__nd);
1759
      }
1760
    }
1761
  }
1762
  return end();
1763
}
1764

1765
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1766
template <class _Key>
1767
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1768
__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const {
1769
  size_t __hash  = hash_function()(__k);
1770
  size_type __bc = bucket_count();
1771
  if (__bc != 0) {
1772
    size_t __chash      = std::__constrain_hash(__hash, __bc);
1773
    __next_pointer __nd = __bucket_list_[__chash];
1774
    if (__nd != nullptr) {
1775
      for (__nd = __nd->__next_;
1776
           __nd != nullptr && (__hash == __nd->__hash() || std::__constrain_hash(__nd->__hash(), __bc) == __chash);
1777
           __nd = __nd->__next_) {
1778
        if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1779
          return const_iterator(__nd);
1780
      }
1781
    }
1782
  }
1783
  return end();
1784
}
1785

1786
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1787
template <class... _Args>
1788
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1789
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
1790
  static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
1791
  __node_allocator& __na = __node_alloc();
1792
  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1793

1794
  // Begin the lifetime of the node itself. Note that this doesn't begin the lifetime of the value
1795
  // held inside the node, since we need to use the allocator's construct() method for that.
1796
  //
1797
  // We don't use the allocator's construct() method to construct the node itself since the
1798
  // Cpp17FooInsertable named requirements don't require the allocator's construct() method
1799
  // to work on anything other than the value_type.
1800
  std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ 0);
1801

1802
  // Now construct the value_type using the allocator's construct() method.
1803
  __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_Args>(__args)...);
1804
  __h.get_deleter().__value_constructed = true;
1805

1806
  __h->__hash_ = hash_function()(__h->__get_value());
1807
  return __h;
1808
}
1809

1810
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1811
template <class _First, class... _Rest>
1812
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1813
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _First&& __f, _Rest&&... __rest) {
1814
  static_assert(!__is_hash_value_type<_First, _Rest...>::value, "Construct cannot be called with a hash value type");
1815
  __node_allocator& __na = __node_alloc();
1816
  __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1817
  std::__construct_at(std::addressof(*__h), /* next = */ nullptr, /* hash = */ __hash);
1818
  __node_traits::construct(
1819
      __na, _NodeTypes::__get_ptr(__h->__get_value()), std::forward<_First>(__f), std::forward<_Rest>(__rest)...);
1820
  __h.get_deleter().__value_constructed = true;
1821
  return __h;
1822
}
1823

1824
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1825
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1826
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {
1827
  __next_pointer __np = __p.__node_;
1828
  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1829
      __p != end(), "unordered container::erase(iterator) called with a non-dereferenceable iterator");
1830
  iterator __r(__np);
1831
  ++__r;
1832
  remove(__p);
1833
  return __r;
1834
}
1835

1836
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1837
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1838
__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
1839
  for (const_iterator __p = __first; __first != __last; __p = __first) {
1840
    ++__first;
1841
    erase(__p);
1842
  }
1843
  __next_pointer __np = __last.__node_;
1844
  return iterator(__np);
1845
}
1846

1847
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1848
template <class _Key>
1849
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1850
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) {
1851
  iterator __i = find(__k);
1852
  if (__i == end())
1853
    return 0;
1854
  erase(__i);
1855
  return 1;
1856
}
1857

1858
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1859
template <class _Key>
1860
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1861
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) {
1862
  size_type __r = 0;
1863
  iterator __i  = find(__k);
1864
  if (__i != end()) {
1865
    iterator __e = end();
1866
    do {
1867
      erase(__i++);
1868
      ++__r;
1869
    } while (__i != __e && key_eq()(*__i, __k));
1870
  }
1871
  return __r;
1872
}
1873

1874
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1875
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1876
__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT {
1877
  // current node
1878
  __next_pointer __cn = __p.__node_;
1879
  size_type __bc      = bucket_count();
1880
  size_t __chash      = std::__constrain_hash(__cn->__hash(), __bc);
1881
  // find previous node
1882
  __next_pointer __pn = __bucket_list_[__chash];
1883
  for (; __pn->__next_ != __cn; __pn = __pn->__next_)
1884
    ;
1885
  // Fix up __bucket_list_
1886
  // if __pn is not in same bucket (before begin is not in same bucket) &&
1887
  //    if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
1888
  if (__pn == __p1_.first().__ptr() || std::__constrain_hash(__pn->__hash(), __bc) != __chash) {
1889
    if (__cn->__next_ == nullptr || std::__constrain_hash(__cn->__next_->__hash(), __bc) != __chash)
1890
      __bucket_list_[__chash] = nullptr;
1891
  }
1892
  // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
1893
  if (__cn->__next_ != nullptr) {
1894
    size_t __nhash = std::__constrain_hash(__cn->__next_->__hash(), __bc);
1895
    if (__nhash != __chash)
1896
      __bucket_list_[__nhash] = __pn;
1897
  }
1898
  // remove __cn
1899
  __pn->__next_ = __cn->__next_;
1900
  __cn->__next_ = nullptr;
1901
  --size();
1902
  return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
1903
}
1904

1905
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1906
template <class _Key>
1907
inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1908
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const {
1909
  return static_cast<size_type>(find(__k) != end());
1910
}
1911

1912
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1913
template <class _Key>
1914
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1915
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const {
1916
  size_type __r      = 0;
1917
  const_iterator __i = find(__k);
1918
  if (__i != end()) {
1919
    const_iterator __e = end();
1920
    do {
1921
      ++__i;
1922
      ++__r;
1923
    } while (__i != __e && key_eq()(*__i, __k));
1924
  }
1925
  return __r;
1926
}
1927

1928
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1929
template <class _Key>
1930
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1931
     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1932
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) {
1933
  iterator __i = find(__k);
1934
  iterator __j = __i;
1935
  if (__i != end())
1936
    ++__j;
1937
  return pair<iterator, iterator>(__i, __j);
1938
}
1939

1940
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1941
template <class _Key>
1942
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1943
     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1944
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) const {
1945
  const_iterator __i = find(__k);
1946
  const_iterator __j = __i;
1947
  if (__i != end())
1948
    ++__j;
1949
  return pair<const_iterator, const_iterator>(__i, __j);
1950
}
1951

1952
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1953
template <class _Key>
1954
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
1955
     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
1956
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) {
1957
  iterator __i = find(__k);
1958
  iterator __j = __i;
1959
  if (__i != end()) {
1960
    iterator __e = end();
1961
    do {
1962
      ++__j;
1963
    } while (__j != __e && key_eq()(*__j, __k));
1964
  }
1965
  return pair<iterator, iterator>(__i, __j);
1966
}
1967

1968
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1969
template <class _Key>
1970
pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
1971
     typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
1972
__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) const {
1973
  const_iterator __i = find(__k);
1974
  const_iterator __j = __i;
1975
  if (__i != end()) {
1976
    const_iterator __e = end();
1977
    do {
1978
      ++__j;
1979
    } while (__j != __e && key_eq()(*__j, __k));
1980
  }
1981
  return pair<const_iterator, const_iterator>(__i, __j);
1982
}
1983

1984
template <class _Tp, class _Hash, class _Equal, class _Alloc>
1985
void __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
1986
#if _LIBCPP_STD_VER <= 11
1987
    _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
1988
               (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
1989
                __is_nothrow_swappable_v<__pointer_allocator>) &&
1990
               (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))
1991
#else
1992
    _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>)
1993
#endif
1994
{
1995
  _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1996
      __node_traits::propagate_on_container_swap::value || this->__node_alloc() == __u.__node_alloc(),
1997
      "unordered container::swap: Either propagate_on_container_swap "
1998
      "must be true or the allocators must compare equal");
1999
  {
2000
    __node_pointer_pointer __npp = __bucket_list_.release();
2001
    __bucket_list_.reset(__u.__bucket_list_.release());
2002
    __u.__bucket_list_.reset(__npp);
2003
  }
2004
  std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2005
  std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc());
2006
  std::__swap_allocator(__node_alloc(), __u.__node_alloc());
2007
  std::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
2008
  __p2_.swap(__u.__p2_);
2009
  __p3_.swap(__u.__p3_);
2010
  if (size() > 0)
2011
    __bucket_list_[std::__constrain_hash(__p1_.first().__next_->__hash(), bucket_count())] = __p1_.first().__ptr();
2012
  if (__u.size() > 0)
2013
    __u.__bucket_list_[std::__constrain_hash(__u.__p1_.first().__next_->__hash(), __u.bucket_count())] =
2014
        __u.__p1_.first().__ptr();
2015
}
2016

2017
template <class _Tp, class _Hash, class _Equal, class _Alloc>
2018
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2019
__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const {
2020
  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
2021
      __n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");
2022
  __next_pointer __np = __bucket_list_[__n];
2023
  size_type __bc      = bucket_count();
2024
  size_type __r       = 0;
2025
  if (__np != nullptr) {
2026
    for (__np = __np->__next_; __np != nullptr && std::__constrain_hash(__np->__hash(), __bc) == __n;
2027
         __np = __np->__next_, (void)++__r)
2028
      ;
2029
  }
2030
  return __r;
2031
}
2032

2033
template <class _Tp, class _Hash, class _Equal, class _Alloc>
2034
inline _LIBCPP_HIDE_FROM_ABI void
2035
swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2036
    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2037
  __x.swap(__y);
2038
}
2039

2040
_LIBCPP_END_NAMESPACE_STD
2041

2042
_LIBCPP_POP_MACROS
2043

2044
#endif // _LIBCPP___HASH_TABLE
2045