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 ? __h : __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 __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 _LIBCPP_HIDE_FROM_ABI void
682 __copy_construct(__next_pointer __other_iter, __next_pointer __own_iter, size_t __current_chash) {
683 auto __bucket_count = bucket_count();
684
685 for (; __other_iter; __other_iter = __other_iter->__next_) {
686 __node_holder __new_node = __construct_node_hash(__other_iter->__hash(), __other_iter->__upcast()->__get_value());
687
688 size_t __new_chash = std::__constrain_hash(h: __new_node->__hash(), bc: __bucket_count);
689 if (__new_chash != __current_chash) {
690 __bucket_list_[__new_chash] = __own_iter;
691 __current_chash = __new_chash;
692 }
693
694 __own_iter->__next_ = static_cast<__next_pointer>(__new_node.release());
695 __own_iter = __own_iter->__next_;
696 }
697 }
698
699 _LIBCPP_HIDE_FROM_ABI void __copy_construct(__next_pointer __other_iter) {
700 __next_pointer __own_iter = __first_node_.__ptr();
701 // If copying a node throws, the nodes that have already been constructed and linked into the
702 // list have to be deallocated. When this is called from the copy constructor the enclosing
703 // __hash_table is not fully constructed yet, so its destructor would not run to release them.
704 // This is also reached from operator= when assigning into an empty table; there the table
705 // stays alive, so we must leave it in a valid empty state: besides releasing the nodes we
706 // clear the bucket pointers, which were made to point into the now-deallocated node list.
707 auto __guard = std::__make_exception_guard([&] {
708 __deallocate_node_list(np: __first_node_.__next_);
709 __first_node_.__next_ = nullptr;
710 std::fill_n(__bucket_list_.get(), bucket_count(), nullptr);
711 });
712 {
713 __node_holder __new_node = __construct_node_hash(__other_iter->__hash(), __other_iter->__upcast()->__get_value());
714 __own_iter->__next_ = static_cast<__next_pointer>(__new_node.release());
715 }
716
717 size_t __current_chash = std::__constrain_hash(h: __own_iter->__next_->__hash(), bc: bucket_count());
718 __bucket_list_[__current_chash] = __own_iter;
719 __other_iter = __other_iter->__next_;
720 __own_iter = __own_iter->__next_;
721 __copy_construct(__other_iter, __own_iter, __current_chash);
722 __guard.__complete();
723 }
724
725public:
726 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; }
727
728 _LIBCPP_HIDE_FROM_ABI hasher& hash_function() _NOEXCEPT { return __hasher_; }
729 _LIBCPP_HIDE_FROM_ABI const hasher& hash_function() const _NOEXCEPT { return __hasher_; }
730
731 _LIBCPP_HIDE_FROM_ABI float& max_load_factor() _NOEXCEPT { return __max_load_factor_; }
732 _LIBCPP_HIDE_FROM_ABI float max_load_factor() const _NOEXCEPT { return __max_load_factor_; }
733
734 _LIBCPP_HIDE_FROM_ABI key_equal& key_eq() _NOEXCEPT { return __key_eq_; }
735 _LIBCPP_HIDE_FROM_ABI const key_equal& key_eq() const _NOEXCEPT { return __key_eq_; }
736
737 _LIBCPP_HIDE_FROM_ABI __node_allocator& __node_alloc() _NOEXCEPT { return __node_alloc_; }
738 _LIBCPP_HIDE_FROM_ABI const __node_allocator& __node_alloc() const _NOEXCEPT { return __node_alloc_; }
739
740public:
741 typedef __hash_iterator<__node_pointer> iterator;
742 typedef __hash_const_iterator<__node_pointer> const_iterator;
743 typedef __hash_local_iterator<__node_pointer> local_iterator;
744 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
745
746 _LIBCPP_HIDE_FROM_ABI __hash_table() _NOEXCEPT_(
747 is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
748 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
749 is_nothrow_default_constructible<key_equal>::value);
750 _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql);
751 _LIBCPP_HIDE_FROM_ABI __hash_table(const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
752 _LIBCPP_HIDE_FROM_ABI explicit __hash_table(const allocator_type& __a);
753 _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u);
754 _LIBCPP_HIDE_FROM_ABI __hash_table(const __hash_table& __u, const allocator_type& __a);
755 _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u) _NOEXCEPT_(
756 is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
757 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
758 is_nothrow_move_constructible<key_equal>::value);
759 _LIBCPP_HIDE_FROM_ABI __hash_table(__hash_table&& __u, const allocator_type& __a);
760 _LIBCPP_HIDE_FROM_ABI ~__hash_table();
761
762 _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(const __hash_table& __u);
763 _LIBCPP_HIDE_FROM_ABI __hash_table& operator=(__hash_table&& __u)
764 _NOEXCEPT_(is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value &&
765 ((__node_traits::propagate_on_container_move_assignment::value &&
766 is_nothrow_move_assignable<__node_allocator>::value) ||
767 allocator_traits<__node_allocator>::is_always_equal::value));
768 template <class _InputIterator>
769 _LIBCPP_HIDE_FROM_ABI void __assign_unique(_InputIterator __first, _InputIterator __last);
770 template <class _InputIterator>
771 _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
772
773 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT {
774 return std::min<size_type>(__node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());
775 }
776
777private:
778 _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val);
779 _LIBCPP_HIDE_FROM_ABI void __node_insert_multi_perform(__node_pointer __cp, __next_pointer __pn) _NOEXCEPT;
780
781 _LIBCPP_HIDE_FROM_ABI __next_pointer __node_insert_unique_prepare(size_t __nd_hash, value_type& __nd_val);
782 _LIBCPP_HIDE_FROM_ABI void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
783
784public:
785 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
786 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
787 _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
788
789 template <class... _Args>
790 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> __emplace_unique(_Args&&... __args) {
791 return std::__try_key_extraction<key_type>(
792 [this](const key_type& __key, _Args&&... __args2) {
793 size_t __hash = hash_function()(__key);
794 size_type __bc = bucket_count();
795 bool __inserted = false;
796 __next_pointer __nd;
797 size_t __chash;
798 if (__bc != 0) {
799 __chash = std::__constrain_hash(h: __hash, __bc);
800 __nd = __bucket_list_[__chash];
801 if (__nd != nullptr) {
802 for (__nd = __nd->__next_;
803 __nd != nullptr &&
804 (__nd->__hash() == __hash || std::__constrain_hash(h: __nd->__hash(), __bc) == __chash);
805 __nd = __nd->__next_) {
806 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __key))
807 goto __done;
808 }
809 }
810 }
811 {
812 __node_holder __h = __construct_node_hash(__hash, std::forward<_Args>(__args2)...);
813 if (size() + 1 > __bc * max_load_factor()) {
814 __rehash_unique(n: std::max<size_type>(2 * __bc + !std::__is_hash_power2(__bc),
815 size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
816 __bc = bucket_count();
817 __chash = std::__constrain_hash(h: __hash, __bc);
818 }
819 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
820 __next_pointer __pn = __bucket_list_[__chash];
821 if (__pn == nullptr) {
822 __pn = __first_node_.__ptr();
823 __h->__next_ = __pn->__next_;
824 __pn->__next_ = __h.get()->__ptr();
825 // fix up __bucket_list_
826 __bucket_list_[__chash] = __pn;
827 if (__h->__next_ != nullptr)
828 __bucket_list_[std::__constrain_hash(h: __h->__next_->__hash(), __bc)] = __h.get()->__ptr();
829 } else {
830 __h->__next_ = __pn->__next_;
831 __pn->__next_ = static_cast<__next_pointer>(__h.get());
832 }
833 __nd = static_cast<__next_pointer>(__h.release());
834 // increment size
835 ++size();
836 __inserted = true;
837 }
838 __done:
839 return pair<iterator, bool>(iterator(__nd), __inserted);
840 },
841 [this](_Args&&... __args2) {
842 __node_holder __h = __construct_node(std::forward<_Args>(__args2)...);
843 pair<iterator, bool> __r = __node_insert_unique(nd: __h.get());
844 if (__r.second)
845 __h.release();
846 return __r;
847 },
848 std::forward<_Args>(__args)...);
849 }
850
851 template <class... _Args>
852 _LIBCPP_HIDE_FROM_ABI iterator __emplace_multi(_Args&&... __args);
853 template <class... _Args>
854 _LIBCPP_HIDE_FROM_ABI iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
855
856 template <class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>
857 _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(value_type&& __value) {
858 __node_holder __h = __construct_node(const_cast<key_type&&>(__value.first), std::move(__value.second));
859 __node_insert_unique(nd: __h.get());
860 __h.release();
861 }
862
863 template <class _ValueT = _Tp, __enable_if_t<!__is_hash_value_type<_ValueT>::value, int> = 0>
864 _LIBCPP_HIDE_FROM_ABI void __insert_unique_from_orphaned_node(value_type&& __value) {
865 __node_holder __h = __construct_node(std::move(__value));
866 __node_insert_unique(nd: __h.get());
867 __h.release();
868 }
869
870 template <class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>
871 _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(value_type&& __value) {
872 __node_holder __h = __construct_node(const_cast<key_type&&>(__value.first), std::move(__value.second));
873 __node_insert_multi(__h.get());
874 __h.release();
875 }
876
877 template <class _ValueT = _Tp, __enable_if_t<!__is_hash_value_type<_ValueT>::value, int> = 0>
878 _LIBCPP_HIDE_FROM_ABI void __insert_multi_from_orphaned_node(value_type&& __value) {
879 __node_holder __h = __construct_node(std::move(__value));
880 __node_insert_multi(__h.get());
881 __h.release();
882 }
883
884#if _LIBCPP_STD_VER >= 17
885 template <class _NodeHandle, class _InsertReturnType>
886 _LIBCPP_HIDE_FROM_ABI _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
887 template <class _NodeHandle>
888 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_unique(const_iterator __hint, _NodeHandle&& __nh);
889 template <class _Table>
890 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_unique(_Table& __source);
891
892 template <class _NodeHandle>
893 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(_NodeHandle&& __nh);
894 template <class _NodeHandle>
895 _LIBCPP_HIDE_FROM_ABI iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
896 template <class _Table>
897 _LIBCPP_HIDE_FROM_ABI void __node_handle_merge_multi(_Table& __source);
898
899 template <class _NodeHandle>
900 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(key_type const& __key);
901 template <class _NodeHandle>
902 _LIBCPP_HIDE_FROM_ABI _NodeHandle __node_handle_extract(const_iterator __it);
903#endif
904
905 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT;
906 _LIBCPP_HIDE_FROM_ABI void __rehash_unique(size_type __n) { __rehash<true>(__n); }
907 _LIBCPP_HIDE_FROM_ABI void __rehash_multi(size_type __n) { __rehash<false>(__n); }
908 _LIBCPP_HIDE_FROM_ABI void __reserve_unique(size_type __n) {
909 __rehash_unique(n: static_cast<size_type>(__math::ceil(__n / max_load_factor())));
910 }
911 _LIBCPP_HIDE_FROM_ABI void __reserve_multi(size_type __n) {
912 __rehash_multi(n: static_cast<size_type>(__math::ceil(__n / max_load_factor())));
913 }
914
915 _LIBCPP_HIDE_FROM_ABI size_type bucket_count() const _NOEXCEPT { return __bucket_list_.get_deleter().size(); }
916
917 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
918 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
919 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
920 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
921
922 template <class _Key>
923 _LIBCPP_HIDE_FROM_ABI size_type bucket(const _Key& __k) const {
924 _LIBCPP_ASSERT_ARGUMENT_WITHIN_DOMAIN(
925 bucket_count() > 0, "unordered container::bucket(key) called when bucket_count() == 0");
926 return std::__constrain_hash(h: hash_function()(__k), bc: bucket_count());
927 }
928
929 template <class _Key>
930 _LIBCPP_HIDE_FROM_ABI iterator find(const _Key& __x);
931 template <class _Key>
932 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _Key& __x) const;
933
934 typedef __hash_node_destructor<__node_allocator> _Dp;
935 typedef unique_ptr<__node, _Dp> __node_holder;
936
937 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p);
938 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
939 template <class _Key>
940 _LIBCPP_HIDE_FROM_ABI size_type __erase_unique(const _Key& __k);
941 template <class _Key>
942 _LIBCPP_HIDE_FROM_ABI size_type __erase_multi(const _Key& __k);
943 _LIBCPP_HIDE_FROM_ABI __node_holder remove(const_iterator __p) _NOEXCEPT;
944
945 template <class _Key>
946 _LIBCPP_HIDE_FROM_ABI size_type __count_unique(const _Key& __k) const;
947 template <class _Key>
948 _LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
949
950 template <class _Key>
951 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_unique(const _Key& __k);
952 template <class _Key>
953 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const;
954
955 template <class _Key>
956 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> __equal_range_multi(const _Key& __k);
957 template <class _Key>
958 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const;
959
960 _LIBCPP_HIDE_FROM_ABI void swap(__hash_table& __u)
961#if _LIBCPP_STD_VER <= 11
962 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
963 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
964 __is_nothrow_swappable_v<__pointer_allocator>) &&
965 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>));
966#else
967 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>);
968#endif
969
970 _LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const _NOEXCEPT { return max_size(); }
971 _LIBCPP_HIDE_FROM_ABI size_type bucket_size(size_type __n) const;
972 _LIBCPP_HIDE_FROM_ABI float load_factor() const _NOEXCEPT {
973 size_type __bc = bucket_count();
974 return __bc != 0 ? (float)size() / __bc : 0.f;
975 }
976 _LIBCPP_HIDE_FROM_ABI void max_load_factor(float __mlf) _NOEXCEPT {
977 // While passing a non-positive load factor is undefined behavior, in practice the result will be benign (the
978 // call will be equivalent to `max_load_factor(load_factor())`, which is also the case for passing a valid value
979 // less than the current `load_factor`).
980 _LIBCPP_ASSERT_PEDANTIC(__mlf > 0, "unordered container::max_load_factor(lf) called with lf <= 0");
981 max_load_factor() = std::max(__mlf, load_factor());
982 }
983
984 _LIBCPP_HIDE_FROM_ABI local_iterator begin(size_type __n) {
985 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
986 __n < bucket_count(), "unordered container::begin(n) called with n >= bucket_count()");
987 return local_iterator(__bucket_list_[__n], __n, bucket_count());
988 }
989
990 _LIBCPP_HIDE_FROM_ABI local_iterator end(size_type __n) {
991 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
992 __n < bucket_count(), "unordered container::end(n) called with n >= bucket_count()");
993 return local_iterator(nullptr, __n, bucket_count());
994 }
995
996 _LIBCPP_HIDE_FROM_ABI const_local_iterator cbegin(size_type __n) const {
997 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
998 __n < bucket_count(), "unordered container::cbegin(n) called with n >= bucket_count()");
999 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1000 }
1001
1002 _LIBCPP_HIDE_FROM_ABI const_local_iterator cend(size_type __n) const {
1003 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1004 __n < bucket_count(), "unordered container::cend(n) called with n >= bucket_count()");
1005 return const_local_iterator(nullptr, __n, bucket_count());
1006 }
1007
1008private:
1009 template <bool _UniqueKeys>
1010 _LIBCPP_HIDE_FROM_ABI void __rehash(size_type __n);
1011 template <bool _UniqueKeys>
1012 _LIBCPP_HIDE_FROM_ABI void __do_rehash(size_type __n);
1013
1014 template <class... _Args>
1015 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node(_Args&&... __args);
1016
1017 template <class... _Args>
1018 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_hash(size_t __hash, _Args&&... __args);
1019
1020 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u) {
1021 __copy_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());
1022 }
1023 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table& __u, true_type);
1024 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const __hash_table&, false_type) {}
1025
1026 _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, false_type);
1027 _LIBCPP_HIDE_FROM_ABI void __move_assign(__hash_table& __u, true_type)
1028 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1029 is_nothrow_move_assignable<key_equal>::value);
1030 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u) _NOEXCEPT_(
1031 !__node_traits::propagate_on_container_move_assignment::value ||
1032 (is_nothrow_move_assignable<__pointer_allocator>::value && is_nothrow_move_assignable<__node_allocator>::value)) {
1033 __move_assign_alloc(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1034 }
1035 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table& __u, true_type) _NOEXCEPT_(
1036 is_nothrow_move_assignable<__pointer_allocator>::value&& is_nothrow_move_assignable<__node_allocator>::value) {
1037 __bucket_list_.get_deleter().__alloc() = std::move(__u.__bucket_list_.get_deleter().__alloc());
1038 __node_alloc() = std::move(__u.__node_alloc());
1039 }
1040 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1041
1042 _LIBCPP_HIDE_FROM_ABI void __deallocate_node(__node_pointer __nd) _NOEXCEPT {
1043 auto& __alloc = __node_alloc();
1044 __node_traits::destroy(__alloc, std::addressof(__nd->__get_value()));
1045 std::__destroy_at(std::__to_address(__nd));
1046 __node_traits::deallocate(__alloc, __nd, 1);
1047 }
1048
1049 _LIBCPP_HIDE_FROM_ABI void __deallocate_node_list(__next_pointer __np) _NOEXCEPT {
1050 while (__np != nullptr) {
1051 __next_pointer __next = __np->__next_;
1052 __deallocate_node(nd: __np->__upcast());
1053 __np = __next;
1054 }
1055 }
1056
1057 _LIBCPP_HIDE_FROM_ABI __next_pointer __detach() _NOEXCEPT;
1058
1059 template <class _From, class _ValueT = _Tp, __enable_if_t<__is_hash_value_type<_ValueT>::value, int> = 0>
1060 _LIBCPP_HIDE_FROM_ABI void __assign_value(__get_hash_node_value_type_t<_Tp>& __lhs, _From&& __rhs) {
1061 // This is technically UB, since the object was constructed as `const`.
1062 // Clang doesn't optimize on this currently though.
1063 const_cast<key_type&>(__lhs.first) = const_cast<__copy_cvref_t<_From, key_type>&&>(__rhs.first);
1064 __lhs.second = std::forward<_From>(__rhs).second;
1065 }
1066
1067 template <class _From, class _ValueT = _Tp, __enable_if_t<!__is_hash_value_type<_ValueT>::value, int> = 0>
1068 _LIBCPP_HIDE_FROM_ABI void __assign_value(_Tp& __lhs, _From&& __rhs) {
1069 __lhs = std::forward<_From>(__rhs);
1070 }
1071
1072 template <class, class, class, class, class>
1073 friend class unordered_map;
1074 template <class, class, class, class, class>
1075 friend class unordered_multimap;
1076};
1077
1078template <class _Tp, class _Hash, class _Equal, class _Alloc>
1079inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table() _NOEXCEPT_(
1080 is_nothrow_default_constructible<__bucket_list>::value&& is_nothrow_default_constructible<__first_node>::value&&
1081 is_nothrow_default_constructible<__node_allocator>::value&& is_nothrow_default_constructible<hasher>::value&&
1082 is_nothrow_default_constructible<key_equal>::value)
1083 : __size_(0), __max_load_factor_(1.0f) {}
1084
1085template <class _Tp, class _Hash, class _Equal, class _Alloc>
1086inline __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf, const key_equal& __eql)
1087 : __bucket_list_(nullptr, __bucket_list_deleter()),
1088 __first_node_(),
1089 __node_alloc_(),
1090 __size_(0),
1091 __hasher_(__hf),
1092 __max_load_factor_(1.0f),
1093 __key_eq_(__eql) {}
1094
1095template <class _Tp, class _Hash, class _Equal, class _Alloc>
1096__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(
1097 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1098 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1099 __node_alloc_(__node_allocator(__a)),
1100 __size_(0),
1101 __hasher_(__hf),
1102 __max_load_factor_(1.0f),
1103 __key_eq_(__eql) {}
1104
1105template <class _Tp, class _Hash, class _Equal, class _Alloc>
1106__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1107 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1108 __node_alloc_(__node_allocator(__a)),
1109 __size_(0),
1110 __max_load_factor_(1.0f) {}
1111
1112template <class _Tp, class _Hash, class _Equal, class _Alloc>
1113__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __other)
1114 : __bucket_list_(nullptr,
1115 __bucket_list_deleter(__pointer_alloc_traits::select_on_container_copy_construction(
1116 __other.__bucket_list_.get_deleter().__alloc()),
1117 0)),
1118 __node_alloc_(__node_traits::select_on_container_copy_construction(__other.__node_alloc())),
1119 __size_(0),
1120 __hasher_(__other.hash_function()),
1121 __max_load_factor_(__other.__max_load_factor_),
1122 __key_eq_(__other.__key_eq_) {
1123 if (__other.size() == 0)
1124 return;
1125
1126 auto& __bucket_list_del = __bucket_list_.get_deleter();
1127 auto __bucket_count = __other.bucket_count();
1128 __bucket_list_.reset(__pointer_alloc_traits::allocate(__bucket_list_del.__alloc(), __bucket_count));
1129 __bucket_list_del.size() = __bucket_count;
1130
1131 std::fill_n(__bucket_list_.get(), __bucket_count, nullptr);
1132
1133 __copy_construct(__other.__first_node_.__next_);
1134 __size_ = __other.size();
1135}
1136
1137template <class _Tp, class _Hash, class _Equal, class _Alloc>
1138__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u, 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 __hasher_(__u.hash_function()),
1143 __max_load_factor_(__u.__max_load_factor_),
1144 __key_eq_(__u.__key_eq_) {}
1145
1146template <class _Tp, class _Hash, class _Equal, class _Alloc>
1147__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u) _NOEXCEPT_(
1148 is_nothrow_move_constructible<__bucket_list>::value&& is_nothrow_move_constructible<__first_node>::value&&
1149 is_nothrow_move_constructible<__node_allocator>::value&& is_nothrow_move_constructible<hasher>::value&&
1150 is_nothrow_move_constructible<key_equal>::value)
1151 : __bucket_list_(std::move(__u.__bucket_list_)),
1152 __first_node_(std::move(__u.__first_node_)),
1153 __node_alloc_(std::move(__u.__node_alloc_)),
1154 __size_(std::move(__u.__size_)),
1155 __hasher_(std::move(__u.__hasher_)),
1156 __max_load_factor_(__u.__max_load_factor_),
1157 __key_eq_(std::move(__u.__key_eq_)) {
1158 if (size() > 0) {
1159 __bucket_list_[std::__constrain_hash(h: __first_node_.__next_->__hash(), bc: bucket_count())] = __first_node_.__ptr();
1160 __u.__first_node_.__next_ = nullptr;
1161 __u.size() = 0;
1162 }
1163}
1164
1165template <class _Tp, class _Hash, class _Equal, class _Alloc>
1166__hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u, const allocator_type& __a)
1167 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1168 __node_alloc_(__node_allocator(__a)),
1169 __size_(0),
1170 __hasher_(std::move(__u.__hasher_)),
1171 __max_load_factor_(__u.__max_load_factor_),
1172 __key_eq_(std::move(__u.__key_eq_)) {
1173 if (__a == allocator_type(__u.__node_alloc())) {
1174 __bucket_list_.reset(__u.__bucket_list_.release());
1175 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1176 __u.__bucket_list_.get_deleter().size() = 0;
1177 if (__u.size() > 0) {
1178 __first_node_.__next_ = __u.__first_node_.__next_;
1179 __u.__first_node_.__next_ = nullptr;
1180 __bucket_list_[std::__constrain_hash(h: __first_node_.__next_->__hash(), bc: bucket_count())] = __first_node_.__ptr();
1181 size() = __u.size();
1182 __u.size() = 0;
1183 }
1184 }
1185}
1186
1187template <class _Tp, class _Hash, class _Equal, class _Alloc>
1188__hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table() {
1189#if defined(_LIBCPP_CXX03_LANG)
1190 static_assert(is_copy_constructible<key_equal>::value, "Predicate must be copy-constructible.");
1191 static_assert(is_copy_constructible<hasher>::value, "Hasher must be copy-constructible.");
1192#endif
1193
1194 __deallocate_node_list(np: __first_node_.__next_);
1195}
1196
1197template <class _Tp, class _Hash, class _Equal, class _Alloc>
1198void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(const __hash_table& __u, true_type) {
1199 if (__node_alloc() != __u.__node_alloc()) {
1200 clear();
1201 __bucket_list_.reset();
1202 __bucket_list_.get_deleter().size() = 0;
1203 }
1204 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1205 __node_alloc() = __u.__node_alloc();
1206}
1207
1208template <class _Tp, class _Hash, class _Equal, class _Alloc>
1209__hash_table<_Tp, _Hash, _Equal, _Alloc>&
1210__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __other) {
1211 if (this == std::addressof(__other))
1212 return *this;
1213
1214 __copy_assign_alloc(__other);
1215 hash_function() = __other.hash_function();
1216 key_eq() = __other.key_eq();
1217 max_load_factor() = __other.max_load_factor();
1218
1219 if (__other.size() == 0) {
1220 clear();
1221 return *this;
1222 }
1223
1224 auto __bucket_count = __other.bucket_count();
1225 if (__bucket_count != bucket_count()) {
1226 auto& __bucket_list_del = __bucket_list_.get_deleter();
1227 __bucket_list_.reset(__pointer_alloc_traits::allocate(__bucket_list_del.__alloc(), __bucket_count));
1228 __bucket_list_del.size() = __bucket_count;
1229 }
1230 std::fill_n(__bucket_list_.get(), __bucket_count, nullptr);
1231
1232 if (!__first_node_.__next_) {
1233 __copy_construct(__other.__first_node_.__next_);
1234 __size_ = __other.size();
1235 return *this;
1236 }
1237
1238 __next_pointer __other_iter = __other.__first_node_.__next_;
1239 __next_pointer __own_iter = __first_node_.__ptr();
1240 {
1241 __node_pointer __next = __own_iter->__next_->__upcast();
1242 __assign_value(__next->__get_value(), __other_iter->__upcast()->__get_value());
1243 __next->__hash_ = __other_iter->__hash();
1244 }
1245 size_t __current_chash = std::__constrain_hash(h: __own_iter->__next_->__hash(), bc: __bucket_count);
1246 __bucket_list_[__current_chash] = __own_iter;
1247 __other_iter = __other_iter->__next_;
1248 __own_iter = __own_iter->__next_;
1249
1250 // Go through the nodes of the incoming hash table and copy then into the destination hash table, reusing as many
1251 // existing nodes as posssible in the destination.
1252 while (__other_iter && __own_iter->__next_) {
1253 __node_pointer __next = __own_iter->__next_->__upcast();
1254 __assign_value(__next->__get_value(), __other_iter->__upcast()->__get_value());
1255 __next->__hash_ = __other_iter->__hash();
1256
1257 size_t __new_chash = std::__constrain_hash(h: __next->__hash_, bc: __bucket_count);
1258 if (__new_chash != __current_chash) {
1259 __bucket_list_[__new_chash] = __own_iter;
1260 __current_chash = __new_chash;
1261 }
1262
1263 __other_iter = __other_iter->__next_;
1264 __own_iter = __own_iter->__next_;
1265 }
1266
1267 // At this point we either have consumed the whole incoming hash table, or we don't have any more nodes to reuse in
1268 // the destination. Either continue with constructing new nodes, or deallocate the left over nodes.
1269 if (__own_iter->__next_) {
1270 __deallocate_node_list(np: __own_iter->__next_);
1271 __own_iter->__next_ = nullptr;
1272 } else {
1273 __copy_construct(__other_iter, __own_iter, __current_chash);
1274 }
1275
1276 __size_ = __other.size();
1277
1278 return *this;
1279}
1280
1281template <class _Tp, class _Hash, class _Equal, class _Alloc>
1282typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1283__hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT {
1284 size_type __bc = bucket_count();
1285 for (size_type __i = 0; __i < __bc; ++__i)
1286 __bucket_list_[__i] = nullptr;
1287 size() = 0;
1288 __next_pointer __cache = __first_node_.__next_;
1289 __first_node_.__next_ = nullptr;
1290 return __cache;
1291}
1292
1293template <class _Tp, class _Hash, class _Equal, class _Alloc>
1294void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, true_type)
1295 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value&& is_nothrow_move_assignable<hasher>::value&&
1296 is_nothrow_move_assignable<key_equal>::value) {
1297 clear();
1298 __bucket_list_.reset(__u.__bucket_list_.release());
1299 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1300 __u.__bucket_list_.get_deleter().size() = 0;
1301 __move_assign_alloc(__u);
1302 size() = __u.size();
1303 hash_function() = std::move(__u.hash_function());
1304 max_load_factor() = __u.max_load_factor();
1305 key_eq() = std::move(__u.key_eq());
1306 __first_node_.__next_ = __u.__first_node_.__next_;
1307 if (size() > 0) {
1308 __bucket_list_[std::__constrain_hash(h: __first_node_.__next_->__hash(), bc: bucket_count())] = __first_node_.__ptr();
1309 __u.__first_node_.__next_ = nullptr;
1310 __u.size() = 0;
1311 }
1312}
1313
1314template <class _Tp, class _Hash, class _Equal, class _Alloc>
1315void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(__hash_table& __u, false_type) {
1316 if (__node_alloc() == __u.__node_alloc())
1317 __move_assign(__u, true_type());
1318 else {
1319 hash_function() = std::move(__u.hash_function());
1320 key_eq() = std::move(__u.key_eq());
1321 max_load_factor() = __u.max_load_factor();
1322 if (bucket_count() != 0) {
1323 __next_pointer __cache = __detach();
1324 auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(np: __cache); });
1325 const_iterator __i = __u.begin();
1326 while (__cache != nullptr && __u.size() != 0) {
1327 __assign_value(__cache->__upcast()->__get_value(), std::move(__u.remove(p: __i++)->__get_value()));
1328 __next_pointer __next = __cache->__next_;
1329 __node_insert_multi(__cache->__upcast());
1330 __cache = __next;
1331 }
1332 }
1333 const_iterator __i = __u.begin();
1334 while (__u.size() != 0)
1335 __insert_multi_from_orphaned_node(std::move(__u.remove(p: __i++)->__get_value()));
1336 }
1337}
1338
1339template <class _Tp, class _Hash, class _Equal, class _Alloc>
1340inline __hash_table<_Tp, _Hash, _Equal, _Alloc>& __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1341 _NOEXCEPT_(is_nothrow_move_assignable<hasher>::value&& is_nothrow_move_assignable<key_equal>::value &&
1342 ((__node_traits::propagate_on_container_move_assignment::value &&
1343 is_nothrow_move_assignable<__node_allocator>::value) ||
1344 allocator_traits<__node_allocator>::is_always_equal::value)) {
1345 __move_assign(__u, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());
1346 return *this;
1347}
1348
1349template <class _Tp, class _Hash, class _Equal, class _Alloc>
1350template <class _InputIterator>
1351void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first, _InputIterator __last) {
1352 typedef iterator_traits<_InputIterator> _ITraits;
1353 typedef typename _ITraits::value_type _ItValueType;
1354 static_assert(
1355 is_same<_ItValueType, value_type>::value, "__assign_unique may only be called with the containers value type");
1356
1357 if (bucket_count() != 0) {
1358 __next_pointer __cache = __detach();
1359 auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(np: __cache); });
1360 for (; __cache != nullptr && __first != __last; ++__first) {
1361 __assign_value(__cache->__upcast()->__get_value(), *__first);
1362 __next_pointer __next = __cache->__next_;
1363 __node_insert_unique(nd: __cache->__upcast());
1364 __cache = __next;
1365 }
1366 }
1367 for (; __first != __last; ++__first)
1368 __emplace_unique(*__first);
1369}
1370
1371template <class _Tp, class _Hash, class _Equal, class _Alloc>
1372template <class _InputIterator>
1373void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first, _InputIterator __last) {
1374 typedef iterator_traits<_InputIterator> _ITraits;
1375 typedef typename _ITraits::value_type _ItValueType;
1376 static_assert(is_same<_ItValueType, value_type>::value,
1377 "__assign_multi may only be called with the containers value type or the nodes value type");
1378 if (bucket_count() != 0) {
1379 __next_pointer __cache = __detach();
1380 auto __guard = std::__make_scope_guard([&] { __deallocate_node_list(np: __cache); });
1381 for (; __cache != nullptr && __first != __last; ++__first) {
1382 __assign_value(__cache->__upcast()->__get_value(), *__first);
1383 __next_pointer __next = __cache->__next_;
1384 __node_insert_multi(__cache->__upcast());
1385 __cache = __next;
1386 }
1387 }
1388 for (; __first != __last; ++__first)
1389 __emplace_multi(*__first);
1390}
1391
1392template <class _Tp, class _Hash, class _Equal, class _Alloc>
1393inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1394__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT {
1395 return iterator(__first_node_.__next_);
1396}
1397
1398template <class _Tp, class _Hash, class _Equal, class _Alloc>
1399inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1400__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT {
1401 return iterator(nullptr);
1402}
1403
1404template <class _Tp, class _Hash, class _Equal, class _Alloc>
1405inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1406__hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT {
1407 return const_iterator(__first_node_.__next_);
1408}
1409
1410template <class _Tp, class _Hash, class _Equal, class _Alloc>
1411inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1412__hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT {
1413 return const_iterator(nullptr);
1414}
1415
1416template <class _Tp, class _Hash, class _Equal, class _Alloc>
1417void __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT {
1418 if (size() > 0) {
1419 __deallocate_node_list(np: __first_node_.__next_);
1420 __first_node_.__next_ = nullptr;
1421 size_type __bc = bucket_count();
1422 for (size_type __i = 0; __i < __bc; ++__i)
1423 __bucket_list_[__i] = nullptr;
1424 size() = 0;
1425 }
1426}
1427
1428// Prepare the container for an insertion of the value __value with the hash
1429// __hash. This does a lookup into the container to see if __value is already
1430// present, and performs a rehash if necessary. Returns a pointer to the
1431// existing element if it exists, otherwise nullptr.
1432//
1433// Note that this function does forward exceptions if key_eq() throws, and never
1434// mutates __value or actually inserts into the map.
1435template <class _Tp, class _Hash, class _Equal, class _Alloc>
1436_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1437__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(size_t __hash, value_type& __value) {
1438 size_type __bc = bucket_count();
1439
1440 if (__bc != 0) {
1441 size_t __chash = std::__constrain_hash(h: __hash, __bc);
1442 __next_pointer __ndptr = __bucket_list_[__chash];
1443 if (__ndptr != nullptr) {
1444 for (__ndptr = __ndptr->__next_;
1445 __ndptr != nullptr &&
1446 (__ndptr->__hash() == __hash || std::__constrain_hash(h: __ndptr->__hash(), __bc) == __chash);
1447 __ndptr = __ndptr->__next_) {
1448 if ((__ndptr->__hash() == __hash) && key_eq()(__ndptr->__upcast()->__get_value(), __value))
1449 return __ndptr;
1450 }
1451 }
1452 }
1453 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1454 __rehash_unique(n: std::max<size_type>(
1455 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1456 }
1457 return nullptr;
1458}
1459
1460// Insert the node __nd into the container by pushing it into the right bucket,
1461// and updating size(). Assumes that __nd->__hash is up-to-date, and that
1462// rehashing has already occurred and that no element with the same key exists
1463// in the map.
1464template <class _Tp, class _Hash, class _Equal, class _Alloc>
1465_LIBCPP_HIDE_FROM_ABI void
1466__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(__node_pointer __nd) _NOEXCEPT {
1467 size_type __bc = bucket_count();
1468 size_t __chash = std::__constrain_hash(h: __nd->__hash(), __bc);
1469 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1470 __next_pointer __pn = __bucket_list_[__chash];
1471 if (__pn == nullptr) {
1472 __pn = __first_node_.__ptr();
1473 __nd->__next_ = __pn->__next_;
1474 __pn->__next_ = __nd->__ptr();
1475 // fix up __bucket_list_
1476 __bucket_list_[__chash] = __pn;
1477 if (__nd->__next_ != nullptr)
1478 __bucket_list_[std::__constrain_hash(h: __nd->__next_->__hash(), __bc)] = __nd->__ptr();
1479 } else {
1480 __nd->__next_ = __pn->__next_;
1481 __pn->__next_ = __nd->__ptr();
1482 }
1483 ++size();
1484}
1485
1486template <class _Tp, class _Hash, class _Equal, class _Alloc>
1487pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1488__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd) {
1489 __nd->__hash_ = hash_function()(__nd->__get_value());
1490 __next_pointer __existing_node = __node_insert_unique_prepare(hash: __nd->__hash(), value&: __nd->__get_value());
1491
1492 // Insert the node, unless it already exists in the container.
1493 bool __inserted = false;
1494 if (__existing_node == nullptr) {
1495 __node_insert_unique_perform(__nd);
1496 __existing_node = __nd->__ptr();
1497 __inserted = true;
1498 }
1499 return pair<iterator, bool>(iterator(__existing_node), __inserted);
1500}
1501
1502// Prepare the container for an insertion of the value __cp_val with the hash
1503// __cp_hash. This does a lookup into the container to see if __cp_value is
1504// already present, and performs a rehash if necessary. Returns a pointer to the
1505// last occurrence of __cp_val in the map.
1506//
1507// Note that this function does forward exceptions if key_eq() throws, and never
1508// mutates __value or actually inserts into the map.
1509template <class _Tp, class _Hash, class _Equal, class _Alloc>
1510typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
1511__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(size_t __cp_hash, value_type& __cp_val) {
1512 size_type __bc = bucket_count();
1513 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1514 __rehash_multi(n: std::max<size_type>(
1515 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1516 __bc = bucket_count();
1517 }
1518 size_t __chash = std::__constrain_hash(h: __cp_hash, __bc);
1519 __next_pointer __pn = __bucket_list_[__chash];
1520 if (__pn != nullptr) {
1521 for (bool __found = false;
1522 __pn->__next_ != nullptr && std::__constrain_hash(h: __pn->__next_->__hash(), __bc) == __chash;
1523 __pn = __pn->__next_) {
1524 // __found key_eq() action
1525 // false false loop
1526 // true true loop
1527 // false true set __found to true
1528 // true false break
1529 if (__found !=
1530 (__pn->__next_->__hash() == __cp_hash && key_eq()(__pn->__next_->__upcast()->__get_value(), __cp_val))) {
1531 if (!__found)
1532 __found = true;
1533 else
1534 break;
1535 }
1536 }
1537 }
1538 return __pn;
1539}
1540
1541// Insert the node __cp into the container after __pn (which is the last node in
1542// the bucket that compares equal to __cp). Rehashing, and checking for
1543// uniqueness has already been performed (in __node_insert_multi_prepare), so
1544// all we need to do is update the bucket and size(). Assumes that __cp->__hash
1545// is up-to-date.
1546template <class _Tp, class _Hash, class _Equal, class _Alloc>
1547void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
1548 __node_pointer __cp, __next_pointer __pn) _NOEXCEPT {
1549 size_type __bc = bucket_count();
1550 size_t __chash = std::__constrain_hash(h: __cp->__hash_, __bc);
1551 if (__pn == nullptr) {
1552 __pn = __first_node_.__ptr();
1553 __cp->__next_ = __pn->__next_;
1554 __pn->__next_ = __cp->__ptr();
1555 // fix up __bucket_list_
1556 __bucket_list_[__chash] = __pn;
1557 if (__cp->__next_ != nullptr)
1558 __bucket_list_[std::__constrain_hash(h: __cp->__next_->__hash(), __bc)] = __cp->__ptr();
1559 } else {
1560 __cp->__next_ = __pn->__next_;
1561 __pn->__next_ = __cp->__ptr();
1562 if (__cp->__next_ != nullptr) {
1563 size_t __nhash = std::__constrain_hash(h: __cp->__next_->__hash(), __bc);
1564 if (__nhash != __chash)
1565 __bucket_list_[__nhash] = __cp->__ptr();
1566 }
1567 }
1568 ++size();
1569}
1570
1571template <class _Tp, class _Hash, class _Equal, class _Alloc>
1572typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1573__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp) {
1574 __cp->__hash_ = hash_function()(__cp->__get_value());
1575 __next_pointer __pn = __node_insert_multi_prepare(cp_hash: __cp->__hash(), cp_val&: __cp->__get_value());
1576 __node_insert_multi_perform(__cp, __pn);
1577
1578 return iterator(__cp->__ptr());
1579}
1580
1581template <class _Tp, class _Hash, class _Equal, class _Alloc>
1582typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1583__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(const_iterator __p, __node_pointer __cp) {
1584 if (__p != end() && key_eq()(*__p, __cp->__get_value())) {
1585 __next_pointer __np = __p.__node_;
1586 __cp->__hash_ = __np->__hash();
1587 size_type __bc = bucket_count();
1588 if (size() + 1 > __bc * max_load_factor() || __bc == 0) {
1589 __rehash_multi(n: std::max<size_type>(
1590 2 * __bc + !std::__is_hash_power2(__bc), size_type(__math::ceil(float(size() + 1) / max_load_factor()))));
1591 __bc = bucket_count();
1592 }
1593 size_t __chash = std::__constrain_hash(h: __cp->__hash_, __bc);
1594 __next_pointer __pp = __bucket_list_[__chash];
1595 while (__pp->__next_ != __np)
1596 __pp = __pp->__next_;
1597 __cp->__next_ = __np;
1598 __pp->__next_ = static_cast<__next_pointer>(__cp);
1599 ++size();
1600 return iterator(static_cast<__next_pointer>(__cp));
1601 }
1602 return __node_insert_multi(__cp);
1603}
1604
1605template <class _Tp, class _Hash, class _Equal, class _Alloc>
1606template <class... _Args>
1607typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1608__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args) {
1609 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1610 iterator __r = __node_insert_multi(__h.get());
1611 __h.release();
1612 return __r;
1613}
1614
1615template <class _Tp, class _Hash, class _Equal, class _Alloc>
1616template <class... _Args>
1617typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1618__hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(const_iterator __p, _Args&&... __args) {
1619 __node_holder __h = __construct_node(std::forward<_Args>(__args)...);
1620 iterator __r = __node_insert_multi(__p, __h.get());
1621 __h.release();
1622 return __r;
1623}
1624
1625#if _LIBCPP_STD_VER >= 17
1626template <class _Tp, class _Hash, class _Equal, class _Alloc>
1627template <class _NodeHandle, class _InsertReturnType>
1628_LIBCPP_HIDE_FROM_ABI _InsertReturnType
1629__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(_NodeHandle&& __nh) {
1630 if (__nh.empty())
1631 return _InsertReturnType{end(), false, _NodeHandle()};
1632 pair<iterator, bool> __result = __node_insert_unique(nd: __nh.__ptr_);
1633 if (__result.second)
1634 __nh.__release_ptr();
1635 return _InsertReturnType{__result.first, __result.second, std::move(__nh)};
1636}
1637
1638template <class _Tp, class _Hash, class _Equal, class _Alloc>
1639template <class _NodeHandle>
1640_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1641__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(const_iterator, _NodeHandle&& __nh) {
1642 if (__nh.empty())
1643 return end();
1644 pair<iterator, bool> __result = __node_insert_unique(nd: __nh.__ptr_);
1645 if (__result.second)
1646 __nh.__release_ptr();
1647 return __result.first;
1648}
1649
1650template <class _Tp, class _Hash, class _Equal, class _Alloc>
1651template <class _NodeHandle>
1652_LIBCPP_HIDE_FROM_ABI _NodeHandle
1653__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(key_type const& __key) {
1654 iterator __i = find(__key);
1655 if (__i == end())
1656 return _NodeHandle();
1657 return __node_handle_extract<_NodeHandle>(__i);
1658}
1659
1660template <class _Tp, class _Hash, class _Equal, class _Alloc>
1661template <class _NodeHandle>
1662_LIBCPP_HIDE_FROM_ABI _NodeHandle __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(const_iterator __p) {
1663 allocator_type __alloc(__node_alloc());
1664 return _NodeHandle(remove(__p).release(), __alloc);
1665}
1666
1667template <class _Tp, class _Hash, class _Equal, class _Alloc>
1668template <class _Table>
1669_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(_Table& __source) {
1670 static_assert(is_same<__node, typename _Table::__node>::value, "");
1671
1672 for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1673 __node_pointer __src_ptr = __it.__node_->__upcast();
1674 size_t __hash = hash_function()(__src_ptr->__get_value());
1675 __next_pointer __existing_node = __node_insert_unique_prepare(__hash, value&: __src_ptr->__get_value());
1676 auto __prev_iter = __it++;
1677 if (__existing_node == nullptr) {
1678 (void)__source.remove(__prev_iter).release();
1679 __src_ptr->__hash_ = __hash;
1680 __node_insert_unique_perform(nd: __src_ptr);
1681 }
1682 }
1683}
1684
1685template <class _Tp, class _Hash, class _Equal, class _Alloc>
1686template <class _NodeHandle>
1687_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1688__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(_NodeHandle&& __nh) {
1689 if (__nh.empty())
1690 return end();
1691 iterator __result = __node_insert_multi(__nh.__ptr_);
1692 __nh.__release_ptr();
1693 return __result;
1694}
1695
1696template <class _Tp, class _Hash, class _Equal, class _Alloc>
1697template <class _NodeHandle>
1698_LIBCPP_HIDE_FROM_ABI typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1699__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh) {
1700 if (__nh.empty())
1701 return end();
1702 iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
1703 __nh.__release_ptr();
1704 return __result;
1705}
1706
1707template <class _Tp, class _Hash, class _Equal, class _Alloc>
1708template <class _Table>
1709_LIBCPP_HIDE_FROM_ABI void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(_Table& __source) {
1710 static_assert(is_same<typename _Table::__node, __node>::value, "");
1711
1712 for (typename _Table::iterator __it = __source.begin(); __it != __source.end();) {
1713 __node_pointer __src_ptr = __it.__node_->__upcast();
1714 size_t __src_hash = hash_function()(__src_ptr->__get_value());
1715 __next_pointer __pn = __node_insert_multi_prepare(cp_hash: __src_hash, cp_val&: __src_ptr->__get_value());
1716 (void)__source.remove(__it++).release();
1717 __src_ptr->__hash_ = __src_hash;
1718 __node_insert_multi_perform(cp: __src_ptr, __pn);
1719 }
1720}
1721#endif // _LIBCPP_STD_VER >= 17
1722
1723template <class _Tp, class _Hash, class _Equal, class _Alloc>
1724template <bool _UniqueKeys>
1725void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __n) _LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK {
1726 if (__n == 1)
1727 __n = 2;
1728 else if (__n & (__n - 1))
1729 __n = std::__next_prime(__n);
1730 size_type __bc = bucket_count();
1731 if (__n > __bc)
1732 __do_rehash<_UniqueKeys>(__n);
1733 else if (__n < __bc) {
1734 __n = std::max<size_type>(
1735 __n,
1736 std::__is_hash_power2(__bc) ? std::__next_hash_pow2(n: size_t(__math::ceil(float(size()) / max_load_factor())))
1737 : std::__next_prime(n: size_t(__math::ceil(float(size()) / max_load_factor()))));
1738 if (__n < __bc)
1739 __do_rehash<_UniqueKeys>(__n);
1740 }
1741}
1742
1743template <class _Tp, class _Hash, class _Equal, class _Alloc>
1744template <bool _UniqueKeys>
1745void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__do_rehash(size_type __bucket_count) {
1746 __pointer_allocator& __ptr_alloc = __bucket_list_.get_deleter().__alloc();
1747 __bucket_list_.reset(__bucket_count > 0 ? __pointer_alloc_traits::allocate(__ptr_alloc, __bucket_count) : nullptr);
1748 __bucket_list_.get_deleter().size() = __bucket_count;
1749
1750 if (__bucket_count == 0)
1751 return;
1752
1753 for (size_type __i = 0; __i < __bucket_count; ++__i)
1754 __bucket_list_[__i] = nullptr;
1755 __next_pointer __pp = __first_node_.__ptr();
1756 __next_pointer __cp = __pp->__next_;
1757
1758 if (!__cp)
1759 return;
1760
1761 size_type __chash = std::__constrain_hash(h: __cp->__hash(), bc: __bucket_count);
1762 __bucket_list_[__chash] = __pp;
1763 size_type __phash = __chash;
1764 for (__pp = __cp, void(), __cp = __cp->__next_; __cp != nullptr; __cp = __pp->__next_) {
1765 __chash = std::__constrain_hash(h: __cp->__hash(), bc: __bucket_count);
1766 if (__chash == __phash)
1767 __pp = __cp;
1768 else {
1769 if (__bucket_list_[__chash] == nullptr) {
1770 __bucket_list_[__chash] = __pp;
1771 __pp = __cp;
1772 __phash = __chash;
1773 } else {
1774 __next_pointer __np = __cp;
1775 if _LIBCPP_CONSTEXPR (!_UniqueKeys) {
1776 for (; __np->__next_ != nullptr &&
1777 key_eq()(__cp->__upcast()->__get_value(), __np->__next_->__upcast()->__get_value());
1778 __np = __np->__next_)
1779 ;
1780 }
1781 __pp->__next_ = __np->__next_;
1782 __np->__next_ = __bucket_list_[__chash]->__next_;
1783 __bucket_list_[__chash]->__next_ = __cp;
1784 }
1785 }
1786 }
1787}
1788
1789template <class _Tp, class _Hash, class _Equal, class _Alloc>
1790template <class _Key>
1791typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1792__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) {
1793 size_type __bc = bucket_count();
1794 if (__bc != 0 && size() != 0) {
1795 size_t __hash = hash_function()(__k);
1796 size_t __chash = std::__constrain_hash(h: __hash, __bc);
1797 __next_pointer __nd = __bucket_list_[__chash];
1798 if (__nd != nullptr) {
1799 for (__nd = __nd->__next_;
1800 __nd != nullptr && (__nd->__hash() == __hash || std::__constrain_hash(h: __nd->__hash(), __bc) == __chash);
1801 __nd = __nd->__next_) {
1802 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1803 return iterator(__nd);
1804 }
1805 }
1806 }
1807 return end();
1808}
1809
1810template <class _Tp, class _Hash, class _Equal, class _Alloc>
1811template <class _Key>
1812typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1813__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const {
1814 size_type __bc = bucket_count();
1815 if (__bc != 0 && size() != 0) {
1816 size_t __hash = hash_function()(__k);
1817 size_t __chash = std::__constrain_hash(h: __hash, __bc);
1818 __next_pointer __nd = __bucket_list_[__chash];
1819 if (__nd != nullptr) {
1820 for (__nd = __nd->__next_;
1821 __nd != nullptr && (__hash == __nd->__hash() || std::__constrain_hash(h: __nd->__hash(), __bc) == __chash);
1822 __nd = __nd->__next_) {
1823 if ((__nd->__hash() == __hash) && key_eq()(__nd->__upcast()->__get_value(), __k))
1824 return const_iterator(__nd);
1825 }
1826 }
1827 }
1828 return end();
1829}
1830
1831template <class _Tp, class _Hash, class _Equal, class _Alloc>
1832template <class... _Args>
1833typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1834__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&&... __args) {
1835 static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
1836 __node_allocator& __na = __node_alloc();
1837 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1838
1839 // Begin the lifetime of the node itself and the value_type contained within.
1840 //
1841 // We don't use the allocator's construct() method to construct the node itself since the
1842 // Cpp17FooInsertable named requirements don't require the allocator's construct() method
1843 // to work on anything other than the value_type.
1844 std::__construct_at(std::addressof(*__h), /* hash = */ 0, __na, std::forward<_Args>(__args)...);
1845
1846 __h.get_deleter().__value_constructed = true;
1847
1848 __h->__hash_ = hash_function()(__h->__get_value());
1849 return __h;
1850}
1851
1852template <class _Tp, class _Hash, class _Equal, class _Alloc>
1853template <class... _Args>
1854typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1855__hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node_hash(size_t __hash, _Args&&... __args) {
1856 static_assert(!__is_hash_value_type<_Args...>::value, "Construct cannot be called with a hash value type");
1857 __node_allocator& __na = __node_alloc();
1858 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1859 std::__construct_at(std::addressof(*__h), /* hash = */ __hash, __na, std::forward<_Args>(__args)...);
1860 __h.get_deleter().__value_constructed = true;
1861 return __h;
1862}
1863
1864template <class _Tp, class _Hash, class _Equal, class _Alloc>
1865typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1866__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p) {
1867 __next_pointer __np = __p.__node_;
1868 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1869 __p != end(), "unordered container::erase(iterator) called with a non-dereferenceable iterator");
1870 iterator __r(__np);
1871 ++__r;
1872 remove(__p);
1873 return __r;
1874}
1875
1876template <class _Tp, class _Hash, class _Equal, class _Alloc>
1877typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1878__hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first, const_iterator __last) {
1879 if (__first == __last)
1880 return iterator(__last.__node_);
1881
1882 // current node
1883 __next_pointer __current = __first.__node_;
1884 size_type __bucket_count = bucket_count();
1885 size_t __chash = std::__constrain_hash(h: __current->__hash(), bc: __bucket_count);
1886 // find previous node
1887 __next_pointer __before_first = __bucket_list_[__chash];
1888 for (; __before_first->__next_ != __current; __before_first = __before_first->__next_)
1889 ;
1890
1891 __next_pointer __last_node = __last.__node_;
1892
1893 // If __before_first is in the same bucket (i.e. the first element we erase is not the first in the bucket), clear
1894 // this bucket first without re-linking it
1895 if (__before_first != __first_node_.__ptr() &&
1896 std::__constrain_hash(h: __before_first->__hash(), bc: __bucket_count) == __chash) {
1897 while (__current != __last_node) {
1898 auto __next = __current->__next_;
1899 __deallocate_node(nd: __current->__upcast());
1900 __current = __next;
1901 --__size_;
1902
1903 if (__next) {
1904 if (auto __next_chash = std::__constrain_hash(h: __next->__hash(), bc: __bucket_count); __next_chash != __chash) {
1905 __bucket_list_[__next_chash] = __before_first;
1906 __chash = __next_chash;
1907 break;
1908 }
1909 }
1910 }
1911 }
1912
1913 while (__current != __last_node) {
1914 auto __next = __current->__next_;
1915 __deallocate_node(nd: __current->__upcast());
1916 __current = __next;
1917 --__size_;
1918
1919 // When switching buckets, set the old bucket to be empty and update the next bucket to have __before_first as its
1920 // before-first element
1921 if (__next) {
1922 if (auto __next_chash = std::__constrain_hash(h: __next->__hash(), bc: __bucket_count); __next_chash != __chash) {
1923 __bucket_list_[__chash] = nullptr;
1924 __bucket_list_[__next_chash] = __before_first;
1925 __chash = __next_chash;
1926 }
1927 } else { // When __next is a nullptr we've fully erased the last bucket. Update the bucket list accordingly.
1928 __bucket_list_[__chash] = nullptr;
1929 }
1930 }
1931
1932 // re-link __before_first with __last
1933 __before_first->__next_ = __current;
1934
1935 return iterator(__last.__node_);
1936}
1937
1938template <class _Tp, class _Hash, class _Equal, class _Alloc>
1939template <class _Key>
1940typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1941__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k) {
1942 iterator __i = find(__k);
1943 if (__i == end())
1944 return 0;
1945 erase(__i);
1946 return 1;
1947}
1948
1949template <class _Tp, class _Hash, class _Equal, class _Alloc>
1950template <class _Key>
1951typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1952__hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k) {
1953 size_type __r = 0;
1954 iterator __i = find(__k);
1955 if (__i != end()) {
1956 iterator __e = end();
1957 do {
1958 erase(__i++);
1959 ++__r;
1960 } while (__i != __e && key_eq()(*__i, __k));
1961 }
1962 return __r;
1963}
1964
1965template <class _Tp, class _Hash, class _Equal, class _Alloc>
1966typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
1967__hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT {
1968 // current node
1969 __next_pointer __cn = __p.__node_;
1970 size_type __bc = bucket_count();
1971 size_t __chash = std::__constrain_hash(h: __cn->__hash(), __bc);
1972 // find previous node
1973 __next_pointer __pn = __bucket_list_[__chash];
1974 for (; __pn->__next_ != __cn; __pn = __pn->__next_)
1975 ;
1976 // Fix up __bucket_list_
1977 // if __pn is not in same bucket (before begin is not in same bucket) &&
1978 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
1979 if (__pn == __first_node_.__ptr() || std::__constrain_hash(h: __pn->__hash(), __bc) != __chash) {
1980 if (__cn->__next_ == nullptr || std::__constrain_hash(h: __cn->__next_->__hash(), __bc) != __chash)
1981 __bucket_list_[__chash] = nullptr;
1982 }
1983 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
1984 if (__cn->__next_ != nullptr) {
1985 size_t __nhash = std::__constrain_hash(h: __cn->__next_->__hash(), __bc);
1986 if (__nhash != __chash)
1987 __bucket_list_[__nhash] = __pn;
1988 }
1989 // remove __cn
1990 __pn->__next_ = __cn->__next_;
1991 __cn->__next_ = nullptr;
1992 --size();
1993 return __node_holder(__cn->__upcast(), _Dp(__node_alloc(), true));
1994}
1995
1996template <class _Tp, class _Hash, class _Equal, class _Alloc>
1997template <class _Key>
1998inline typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
1999__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const {
2000 return static_cast<size_type>(find(__k) != end());
2001}
2002
2003template <class _Tp, class _Hash, class _Equal, class _Alloc>
2004template <class _Key>
2005typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2006__hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const {
2007 size_type __r = 0;
2008 const_iterator __i = find(__k);
2009 if (__i != end()) {
2010 const_iterator __e = end();
2011 do {
2012 ++__i;
2013 ++__r;
2014 } while (__i != __e && key_eq()(*__i, __k));
2015 }
2016 return __r;
2017}
2018
2019template <class _Tp, class _Hash, class _Equal, class _Alloc>
2020template <class _Key>
2021pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2022 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2023__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) {
2024 iterator __i = find(__k);
2025 iterator __j = __i;
2026 if (__i != end())
2027 ++__j;
2028 return pair<iterator, iterator>(__i, __j);
2029}
2030
2031template <class _Tp, class _Hash, class _Equal, class _Alloc>
2032template <class _Key>
2033pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2034 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2035__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(const _Key& __k) const {
2036 const_iterator __i = find(__k);
2037 const_iterator __j = __i;
2038 if (__i != end())
2039 ++__j;
2040 return pair<const_iterator, const_iterator>(__i, __j);
2041}
2042
2043template <class _Tp, class _Hash, class _Equal, class _Alloc>
2044template <class _Key>
2045pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2046 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2047__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) {
2048 iterator __i = find(__k);
2049 iterator __j = __i;
2050 if (__i != end()) {
2051 iterator __e = end();
2052 do {
2053 ++__j;
2054 } while (__j != __e && key_eq()(*__j, __k));
2055 }
2056 return pair<iterator, iterator>(__i, __j);
2057}
2058
2059template <class _Tp, class _Hash, class _Equal, class _Alloc>
2060template <class _Key>
2061pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2062 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2063__hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(const _Key& __k) const {
2064 const_iterator __i = find(__k);
2065 const_iterator __j = __i;
2066 if (__i != end()) {
2067 const_iterator __e = end();
2068 do {
2069 ++__j;
2070 } while (__j != __e && key_eq()(*__j, __k));
2071 }
2072 return pair<const_iterator, const_iterator>(__i, __j);
2073}
2074
2075template <class _Tp, class _Hash, class _Equal, class _Alloc>
2076void __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2077#if _LIBCPP_STD_VER <= 11
2078 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal> &&
2079 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
2080 __is_nothrow_swappable_v<__pointer_allocator>) &&
2081 (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__node_allocator>))
2082#else
2083 _NOEXCEPT_(__is_nothrow_swappable_v<hasher>&& __is_nothrow_swappable_v<key_equal>)
2084#endif
2085{
2086 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
2087 __node_traits::propagate_on_container_swap::value || this->__node_alloc() == __u.__node_alloc(),
2088 "unordered container::swap: Either propagate_on_container_swap "
2089 "must be true or the allocators must compare equal");
2090 {
2091 __node_pointer_pointer __npp = __bucket_list_.release();
2092 __bucket_list_.reset(__u.__bucket_list_.release());
2093 __u.__bucket_list_.reset(__npp);
2094 }
2095 std::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2096 std::__swap_allocator(__bucket_list_.get_deleter().__alloc(), __u.__bucket_list_.get_deleter().__alloc());
2097 std::__swap_allocator(__node_alloc(), __u.__node_alloc());
2098 std::swap(__first_node_.__next_, __u.__first_node_.__next_);
2099 using std::swap;
2100 swap(__size_, __u.__size_);
2101 swap(__hasher_, __u.__hasher_);
2102 swap(__max_load_factor_, __u.__max_load_factor_);
2103 swap(__key_eq_, __u.__key_eq_);
2104 if (size() > 0)
2105 __bucket_list_[std::__constrain_hash(h: __first_node_.__next_->__hash(), bc: bucket_count())] = __first_node_.__ptr();
2106 if (__u.size() > 0)
2107 __u.__bucket_list_[std::__constrain_hash(h: __u.__first_node_.__next_->__hash(), bc: __u.bucket_count())] =
2108 __u.__first_node_.__ptr();
2109}
2110
2111template <class _Tp, class _Hash, class _Equal, class _Alloc>
2112typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2113__hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const {
2114 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
2115 __n < bucket_count(), "unordered container::bucket_size(n) called with n >= bucket_count()");
2116 __next_pointer __np = __bucket_list_[__n];
2117 size_type __bc = bucket_count();
2118 size_type __r = 0;
2119 if (__np != nullptr) {
2120 for (__np = __np->__next_; __np != nullptr && std::__constrain_hash(h: __np->__hash(), __bc) == __n;
2121 __np = __np->__next_, (void)++__r)
2122 ;
2123 }
2124 return __r;
2125}
2126
2127template <class _Tp, class _Hash, class _Equal, class _Alloc>
2128inline _LIBCPP_HIDE_FROM_ABI void
2129swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x, __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2130 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2131 __x.swap(__y);
2132}
2133
2134_LIBCPP_END_NAMESPACE_STD
2135
2136_LIBCPP_POP_MACROS
2137
2138#endif // _LIBCPP___HASH_TABLE
2139