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