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