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