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