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