2 //===----------------------------------------------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP__HASH_TABLE
12 #define _LIBCPP__HASH_TABLE
15 #include <initializer_list>
21 #include <__undef_min_max>
26 # define _LIBCPP_ASSERT(x, m) ((void)0)
29 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
30 #pragma GCC system_header
33 _LIBCPP_BEGIN_NAMESPACE_STD
36 size_t __next_prime(size_t __n);
38 template <class _NodePtr>
39 struct __hash_node_base
41 typedef __hash_node_base __first_node;
45 _LIBCPP_INLINE_VISIBILITY __hash_node_base() _NOEXCEPT : __next_(nullptr) {}
48 template <class _Tp, class _VoidPtr>
50 : public __hash_node_base
52 typename pointer_traits<_VoidPtr>::template
53 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
54 rebind<__hash_node<_Tp, _VoidPtr> >
56 rebind<__hash_node<_Tp, _VoidPtr> >::other
60 typedef _Tp value_type;
66 inline _LIBCPP_INLINE_VISIBILITY
68 __is_power2(size_t __bc)
70 return __bc > 2 && !(__bc & (__bc - 1));
73 inline _LIBCPP_INLINE_VISIBILITY
75 __constrain_hash(size_t __h, size_t __bc)
77 return !(__bc & (__bc - 1)) ? __h & (__bc - 1) : __h % __bc;
80 inline _LIBCPP_INLINE_VISIBILITY
82 __next_pow2(size_t __n)
84 return size_t(1) << (std::numeric_limits<size_t>::digits - __clz(__n-1));
87 template <class _Tp, class _Hash, class _Equal, class _Alloc> class __hash_table;
88 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
89 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
90 template <class _HashIterator> class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
91 template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
92 class _LIBCPP_TYPE_VIS_ONLY unordered_map;
94 template <class _NodePtr>
95 class _LIBCPP_TYPE_VIS_ONLY __hash_iterator
97 typedef _NodePtr __node_pointer;
99 __node_pointer __node_;
102 typedef forward_iterator_tag iterator_category;
103 typedef typename pointer_traits<__node_pointer>::element_type::value_type value_type;
104 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
105 typedef value_type& reference;
106 typedef typename pointer_traits<__node_pointer>::template
107 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
110 rebind<value_type>::other
114 _LIBCPP_INLINE_VISIBILITY __hash_iterator() _NOEXCEPT
115 #if _LIBCPP_STD_VER > 11
119 #if _LIBCPP_DEBUG_LEVEL >= 2
120 __get_db()->__insert_i(this);
124 #if _LIBCPP_DEBUG_LEVEL >= 2
126 _LIBCPP_INLINE_VISIBILITY
127 __hash_iterator(const __hash_iterator& __i)
128 : __node_(__i.__node_)
130 __get_db()->__iterator_copy(this, &__i);
133 _LIBCPP_INLINE_VISIBILITY
136 __get_db()->__erase_i(this);
139 _LIBCPP_INLINE_VISIBILITY
140 __hash_iterator& operator=(const __hash_iterator& __i)
144 __get_db()->__iterator_copy(this, &__i);
145 __node_ = __i.__node_;
150 #endif // _LIBCPP_DEBUG_LEVEL >= 2
152 _LIBCPP_INLINE_VISIBILITY
153 reference operator*() const
155 #if _LIBCPP_DEBUG_LEVEL >= 2
156 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
157 "Attempted to dereference a non-dereferenceable unordered container iterator");
159 return __node_->__value_;
161 _LIBCPP_INLINE_VISIBILITY
162 pointer operator->() const
164 #if _LIBCPP_DEBUG_LEVEL >= 2
165 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
166 "Attempted to dereference a non-dereferenceable unordered container iterator");
168 return pointer_traits<pointer>::pointer_to(__node_->__value_);
171 _LIBCPP_INLINE_VISIBILITY
172 __hash_iterator& operator++()
174 #if _LIBCPP_DEBUG_LEVEL >= 2
175 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
176 "Attempted to increment non-incrementable unordered container iterator");
178 __node_ = __node_->__next_;
182 _LIBCPP_INLINE_VISIBILITY
183 __hash_iterator operator++(int)
185 __hash_iterator __t(*this);
190 friend _LIBCPP_INLINE_VISIBILITY
191 bool operator==(const __hash_iterator& __x, const __hash_iterator& __y)
193 return __x.__node_ == __y.__node_;
195 friend _LIBCPP_INLINE_VISIBILITY
196 bool operator!=(const __hash_iterator& __x, const __hash_iterator& __y)
197 {return !(__x == __y);}
200 #if _LIBCPP_DEBUG_LEVEL >= 2
201 _LIBCPP_INLINE_VISIBILITY
202 __hash_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
205 __get_db()->__insert_ic(this, __c);
208 _LIBCPP_INLINE_VISIBILITY
209 __hash_iterator(__node_pointer __node) _NOEXCEPT
214 template <class, class, class, class> friend class __hash_table;
215 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator;
216 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
217 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
218 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
221 template <class _ConstNodePtr>
222 class _LIBCPP_TYPE_VIS_ONLY __hash_const_iterator
224 typedef _ConstNodePtr __node_pointer;
226 __node_pointer __node_;
228 typedef typename remove_const<
229 typename pointer_traits<__node_pointer>::element_type
233 typedef forward_iterator_tag iterator_category;
234 typedef typename __node::value_type value_type;
235 typedef typename pointer_traits<__node_pointer>::difference_type difference_type;
236 typedef const value_type& reference;
237 typedef typename pointer_traits<__node_pointer>::template
238 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
239 rebind<const value_type>
241 rebind<const value_type>::other
244 typedef typename pointer_traits<__node_pointer>::template
245 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
248 rebind<__node>::other
250 __non_const_node_pointer;
251 typedef __hash_iterator<__non_const_node_pointer> __non_const_iterator;
253 _LIBCPP_INLINE_VISIBILITY __hash_const_iterator() _NOEXCEPT
254 #if _LIBCPP_STD_VER > 11
258 #if _LIBCPP_DEBUG_LEVEL >= 2
259 __get_db()->__insert_i(this);
262 _LIBCPP_INLINE_VISIBILITY
263 __hash_const_iterator(const __non_const_iterator& __x) _NOEXCEPT
264 : __node_(__x.__node_)
266 #if _LIBCPP_DEBUG_LEVEL >= 2
267 __get_db()->__iterator_copy(this, &__x);
271 #if _LIBCPP_DEBUG_LEVEL >= 2
273 _LIBCPP_INLINE_VISIBILITY
274 __hash_const_iterator(const __hash_const_iterator& __i)
275 : __node_(__i.__node_)
277 __get_db()->__iterator_copy(this, &__i);
280 _LIBCPP_INLINE_VISIBILITY
281 ~__hash_const_iterator()
283 __get_db()->__erase_i(this);
286 _LIBCPP_INLINE_VISIBILITY
287 __hash_const_iterator& operator=(const __hash_const_iterator& __i)
291 __get_db()->__iterator_copy(this, &__i);
292 __node_ = __i.__node_;
297 #endif // _LIBCPP_DEBUG_LEVEL >= 2
299 _LIBCPP_INLINE_VISIBILITY
300 reference operator*() const
302 #if _LIBCPP_DEBUG_LEVEL >= 2
303 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
304 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
306 return __node_->__value_;
308 _LIBCPP_INLINE_VISIBILITY
309 pointer operator->() const
311 #if _LIBCPP_DEBUG_LEVEL >= 2
312 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
313 "Attempted to dereference a non-dereferenceable unordered container const_iterator");
315 return pointer_traits<pointer>::pointer_to(__node_->__value_);
318 _LIBCPP_INLINE_VISIBILITY
319 __hash_const_iterator& operator++()
321 #if _LIBCPP_DEBUG_LEVEL >= 2
322 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
323 "Attempted to increment non-incrementable unordered container const_iterator");
325 __node_ = __node_->__next_;
329 _LIBCPP_INLINE_VISIBILITY
330 __hash_const_iterator operator++(int)
332 __hash_const_iterator __t(*this);
337 friend _LIBCPP_INLINE_VISIBILITY
338 bool operator==(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
340 return __x.__node_ == __y.__node_;
342 friend _LIBCPP_INLINE_VISIBILITY
343 bool operator!=(const __hash_const_iterator& __x, const __hash_const_iterator& __y)
344 {return !(__x == __y);}
347 #if _LIBCPP_DEBUG_LEVEL >= 2
348 _LIBCPP_INLINE_VISIBILITY
349 __hash_const_iterator(__node_pointer __node, const void* __c) _NOEXCEPT
352 __get_db()->__insert_ic(this, __c);
355 _LIBCPP_INLINE_VISIBILITY
356 __hash_const_iterator(__node_pointer __node) _NOEXCEPT
361 template <class, class, class, class> friend class __hash_table;
362 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
363 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
364 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
367 template <class _ConstNodePtr> class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
369 template <class _NodePtr>
370 class _LIBCPP_TYPE_VIS_ONLY __hash_local_iterator
372 typedef _NodePtr __node_pointer;
374 __node_pointer __node_;
376 size_t __bucket_count_;
378 typedef pointer_traits<__node_pointer> __pointer_traits;
380 typedef forward_iterator_tag iterator_category;
381 typedef typename __pointer_traits::element_type::value_type value_type;
382 typedef typename __pointer_traits::difference_type difference_type;
383 typedef value_type& reference;
384 typedef typename __pointer_traits::template
385 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
388 rebind<value_type>::other
392 _LIBCPP_INLINE_VISIBILITY __hash_local_iterator() _NOEXCEPT
394 #if _LIBCPP_DEBUG_LEVEL >= 2
395 __get_db()->__insert_i(this);
399 #if _LIBCPP_DEBUG_LEVEL >= 2
401 _LIBCPP_INLINE_VISIBILITY
402 __hash_local_iterator(const __hash_local_iterator& __i)
403 : __node_(__i.__node_),
404 __bucket_(__i.__bucket_),
405 __bucket_count_(__i.__bucket_count_)
407 __get_db()->__iterator_copy(this, &__i);
410 _LIBCPP_INLINE_VISIBILITY
411 ~__hash_local_iterator()
413 __get_db()->__erase_i(this);
416 _LIBCPP_INLINE_VISIBILITY
417 __hash_local_iterator& operator=(const __hash_local_iterator& __i)
421 __get_db()->__iterator_copy(this, &__i);
422 __node_ = __i.__node_;
423 __bucket_ = __i.__bucket_;
424 __bucket_count_ = __i.__bucket_count_;
429 #endif // _LIBCPP_DEBUG_LEVEL >= 2
431 _LIBCPP_INLINE_VISIBILITY
432 reference operator*() const
434 #if _LIBCPP_DEBUG_LEVEL >= 2
435 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
436 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
438 return __node_->__value_;
440 _LIBCPP_INLINE_VISIBILITY
441 pointer operator->() const
443 #if _LIBCPP_DEBUG_LEVEL >= 2
444 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
445 "Attempted to dereference a non-dereferenceable unordered container local_iterator");
447 return pointer_traits<pointer>::pointer_to(__node_->__value_);
450 _LIBCPP_INLINE_VISIBILITY
451 __hash_local_iterator& operator++()
453 #if _LIBCPP_DEBUG_LEVEL >= 2
454 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
455 "Attempted to increment non-incrementable unordered container local_iterator");
457 __node_ = __node_->__next_;
458 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
463 _LIBCPP_INLINE_VISIBILITY
464 __hash_local_iterator operator++(int)
466 __hash_local_iterator __t(*this);
471 friend _LIBCPP_INLINE_VISIBILITY
472 bool operator==(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
474 return __x.__node_ == __y.__node_;
476 friend _LIBCPP_INLINE_VISIBILITY
477 bool operator!=(const __hash_local_iterator& __x, const __hash_local_iterator& __y)
478 {return !(__x == __y);}
481 #if _LIBCPP_DEBUG_LEVEL >= 2
482 _LIBCPP_INLINE_VISIBILITY
483 __hash_local_iterator(__node_pointer __node, size_t __bucket,
484 size_t __bucket_count, const void* __c) _NOEXCEPT
487 __bucket_count_(__bucket_count)
489 __get_db()->__insert_ic(this, __c);
490 if (__node_ != nullptr)
491 __node_ = __node_->__next_;
494 _LIBCPP_INLINE_VISIBILITY
495 __hash_local_iterator(__node_pointer __node, size_t __bucket,
496 size_t __bucket_count) _NOEXCEPT
499 __bucket_count_(__bucket_count)
501 if (__node_ != nullptr)
502 __node_ = __node_->__next_;
505 template <class, class, class, class> friend class __hash_table;
506 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator;
507 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_iterator;
510 template <class _ConstNodePtr>
511 class _LIBCPP_TYPE_VIS_ONLY __hash_const_local_iterator
513 typedef _ConstNodePtr __node_pointer;
515 __node_pointer __node_;
517 size_t __bucket_count_;
519 typedef pointer_traits<__node_pointer> __pointer_traits;
520 typedef typename __pointer_traits::element_type __node;
521 typedef typename remove_const<__node>::type __non_const_node;
522 typedef typename pointer_traits<__node_pointer>::template
523 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
524 rebind<__non_const_node>
526 rebind<__non_const_node>::other
528 __non_const_node_pointer;
529 typedef __hash_local_iterator<__non_const_node_pointer>
530 __non_const_iterator;
532 typedef forward_iterator_tag iterator_category;
533 typedef typename remove_const<
534 typename __pointer_traits::element_type::value_type
536 typedef typename __pointer_traits::difference_type difference_type;
537 typedef const value_type& reference;
538 typedef typename __pointer_traits::template
539 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
540 rebind<const value_type>
542 rebind<const value_type>::other
546 _LIBCPP_INLINE_VISIBILITY __hash_const_local_iterator() _NOEXCEPT
548 #if _LIBCPP_DEBUG_LEVEL >= 2
549 __get_db()->__insert_i(this);
553 _LIBCPP_INLINE_VISIBILITY
554 __hash_const_local_iterator(const __non_const_iterator& __x) _NOEXCEPT
555 : __node_(__x.__node_),
556 __bucket_(__x.__bucket_),
557 __bucket_count_(__x.__bucket_count_)
559 #if _LIBCPP_DEBUG_LEVEL >= 2
560 __get_db()->__iterator_copy(this, &__x);
564 #if _LIBCPP_DEBUG_LEVEL >= 2
566 _LIBCPP_INLINE_VISIBILITY
567 __hash_const_local_iterator(const __hash_const_local_iterator& __i)
568 : __node_(__i.__node_),
569 __bucket_(__i.__bucket_),
570 __bucket_count_(__i.__bucket_count_)
572 __get_db()->__iterator_copy(this, &__i);
575 _LIBCPP_INLINE_VISIBILITY
576 ~__hash_const_local_iterator()
578 __get_db()->__erase_i(this);
581 _LIBCPP_INLINE_VISIBILITY
582 __hash_const_local_iterator& operator=(const __hash_const_local_iterator& __i)
586 __get_db()->__iterator_copy(this, &__i);
587 __node_ = __i.__node_;
588 __bucket_ = __i.__bucket_;
589 __bucket_count_ = __i.__bucket_count_;
594 #endif // _LIBCPP_DEBUG_LEVEL >= 2
596 _LIBCPP_INLINE_VISIBILITY
597 reference operator*() const
599 #if _LIBCPP_DEBUG_LEVEL >= 2
600 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
601 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
603 return __node_->__value_;
605 _LIBCPP_INLINE_VISIBILITY
606 pointer operator->() const
608 #if _LIBCPP_DEBUG_LEVEL >= 2
609 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
610 "Attempted to dereference a non-dereferenceable unordered container const_local_iterator");
612 return pointer_traits<pointer>::pointer_to(__node_->__value_);
615 _LIBCPP_INLINE_VISIBILITY
616 __hash_const_local_iterator& operator++()
618 #if _LIBCPP_DEBUG_LEVEL >= 2
619 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
620 "Attempted to increment non-incrementable unordered container const_local_iterator");
622 __node_ = __node_->__next_;
623 if (__node_ != nullptr && __constrain_hash(__node_->__hash_, __bucket_count_) != __bucket_)
628 _LIBCPP_INLINE_VISIBILITY
629 __hash_const_local_iterator operator++(int)
631 __hash_const_local_iterator __t(*this);
636 friend _LIBCPP_INLINE_VISIBILITY
637 bool operator==(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
639 return __x.__node_ == __y.__node_;
641 friend _LIBCPP_INLINE_VISIBILITY
642 bool operator!=(const __hash_const_local_iterator& __x, const __hash_const_local_iterator& __y)
643 {return !(__x == __y);}
646 #if _LIBCPP_DEBUG_LEVEL >= 2
647 _LIBCPP_INLINE_VISIBILITY
648 __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
649 size_t __bucket_count, const void* __c) _NOEXCEPT
652 __bucket_count_(__bucket_count)
654 __get_db()->__insert_ic(this, __c);
655 if (__node_ != nullptr)
656 __node_ = __node_->__next_;
659 _LIBCPP_INLINE_VISIBILITY
660 __hash_const_local_iterator(__node_pointer __node, size_t __bucket,
661 size_t __bucket_count) _NOEXCEPT
664 __bucket_count_(__bucket_count)
666 if (__node_ != nullptr)
667 __node_ = __node_->__next_;
670 template <class, class, class, class> friend class __hash_table;
671 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __hash_map_const_iterator;
674 template <class _Alloc>
675 class __bucket_list_deallocator
677 typedef _Alloc allocator_type;
678 typedef allocator_traits<allocator_type> __alloc_traits;
679 typedef typename __alloc_traits::size_type size_type;
681 __compressed_pair<size_type, allocator_type> __data_;
683 typedef typename __alloc_traits::pointer pointer;
685 _LIBCPP_INLINE_VISIBILITY
686 __bucket_list_deallocator()
687 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
690 _LIBCPP_INLINE_VISIBILITY
691 __bucket_list_deallocator(const allocator_type& __a, size_type __size)
692 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
693 : __data_(__size, __a) {}
695 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
697 _LIBCPP_INLINE_VISIBILITY
698 __bucket_list_deallocator(__bucket_list_deallocator&& __x)
699 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
700 : __data_(_VSTD::move(__x.__data_))
705 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
707 _LIBCPP_INLINE_VISIBILITY
708 size_type& size() _NOEXCEPT {return __data_.first();}
709 _LIBCPP_INLINE_VISIBILITY
710 size_type size() const _NOEXCEPT {return __data_.first();}
712 _LIBCPP_INLINE_VISIBILITY
713 allocator_type& __alloc() _NOEXCEPT {return __data_.second();}
714 _LIBCPP_INLINE_VISIBILITY
715 const allocator_type& __alloc() const _NOEXCEPT {return __data_.second();}
717 _LIBCPP_INLINE_VISIBILITY
718 void operator()(pointer __p) _NOEXCEPT
720 __alloc_traits::deallocate(__alloc(), __p, size());
724 template <class _Alloc> class __hash_map_node_destructor;
726 template <class _Alloc>
727 class __hash_node_destructor
729 typedef _Alloc allocator_type;
730 typedef allocator_traits<allocator_type> __alloc_traits;
731 typedef typename __alloc_traits::value_type::value_type value_type;
733 typedef typename __alloc_traits::pointer pointer;
736 allocator_type& __na_;
738 __hash_node_destructor& operator=(const __hash_node_destructor&);
741 bool __value_constructed;
743 _LIBCPP_INLINE_VISIBILITY
744 explicit __hash_node_destructor(allocator_type& __na,
745 bool __constructed = false) _NOEXCEPT
747 __value_constructed(__constructed)
750 _LIBCPP_INLINE_VISIBILITY
751 void operator()(pointer __p) _NOEXCEPT
753 if (__value_constructed)
754 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_));
756 __alloc_traits::deallocate(__na_, __p, 1);
759 template <class> friend class __hash_map_node_destructor;
762 template <class _Tp, class _Hash, class _Equal, class _Alloc>
766 typedef _Tp value_type;
767 typedef _Hash hasher;
768 typedef _Equal key_equal;
769 typedef _Alloc allocator_type;
772 typedef allocator_traits<allocator_type> __alloc_traits;
774 typedef value_type& reference;
775 typedef const value_type& const_reference;
776 typedef typename __alloc_traits::pointer pointer;
777 typedef typename __alloc_traits::const_pointer const_pointer;
778 typedef typename __alloc_traits::size_type size_type;
779 typedef typename __alloc_traits::difference_type difference_type;
782 typedef __hash_node<value_type, typename __alloc_traits::void_pointer> __node;
783 typedef typename __alloc_traits::template
784 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
787 rebind_alloc<__node>::other
790 typedef allocator_traits<__node_allocator> __node_traits;
791 typedef typename __node_traits::pointer __node_pointer;
792 typedef typename __node_traits::pointer __node_const_pointer;
793 typedef __hash_node_base<__node_pointer> __first_node;
794 typedef typename pointer_traits<__node_pointer>::template
795 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
798 rebind<__first_node>::other
804 typedef typename __node_traits::template
805 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
806 rebind_alloc<__node_pointer>
808 rebind_alloc<__node_pointer>::other
811 typedef __bucket_list_deallocator<__pointer_allocator> __bucket_list_deleter;
812 typedef unique_ptr<__node_pointer[], __bucket_list_deleter> __bucket_list;
813 typedef allocator_traits<__pointer_allocator> __pointer_alloc_traits;
814 typedef typename __bucket_list_deleter::pointer __node_pointer_pointer;
816 // --- Member data begin ---
817 __bucket_list __bucket_list_;
818 __compressed_pair<__first_node, __node_allocator> __p1_;
819 __compressed_pair<size_type, hasher> __p2_;
820 __compressed_pair<float, key_equal> __p3_;
821 // --- Member data end ---
823 _LIBCPP_INLINE_VISIBILITY
824 size_type& size() _NOEXCEPT {return __p2_.first();}
826 _LIBCPP_INLINE_VISIBILITY
827 size_type size() const _NOEXCEPT {return __p2_.first();}
829 _LIBCPP_INLINE_VISIBILITY
830 hasher& hash_function() _NOEXCEPT {return __p2_.second();}
831 _LIBCPP_INLINE_VISIBILITY
832 const hasher& hash_function() const _NOEXCEPT {return __p2_.second();}
834 _LIBCPP_INLINE_VISIBILITY
835 float& max_load_factor() _NOEXCEPT {return __p3_.first();}
836 _LIBCPP_INLINE_VISIBILITY
837 float max_load_factor() const _NOEXCEPT {return __p3_.first();}
839 _LIBCPP_INLINE_VISIBILITY
840 key_equal& key_eq() _NOEXCEPT {return __p3_.second();}
841 _LIBCPP_INLINE_VISIBILITY
842 const key_equal& key_eq() const _NOEXCEPT {return __p3_.second();}
844 _LIBCPP_INLINE_VISIBILITY
845 __node_allocator& __node_alloc() _NOEXCEPT {return __p1_.second();}
846 _LIBCPP_INLINE_VISIBILITY
847 const __node_allocator& __node_alloc() const _NOEXCEPT
848 {return __p1_.second();}
851 typedef __hash_iterator<__node_pointer> iterator;
852 typedef __hash_const_iterator<__node_pointer> const_iterator;
853 typedef __hash_local_iterator<__node_pointer> local_iterator;
854 typedef __hash_const_local_iterator<__node_pointer> const_local_iterator;
858 is_nothrow_default_constructible<__bucket_list>::value &&
859 is_nothrow_default_constructible<__first_node>::value &&
860 is_nothrow_default_constructible<__node_allocator>::value &&
861 is_nothrow_default_constructible<hasher>::value &&
862 is_nothrow_default_constructible<key_equal>::value);
863 __hash_table(const hasher& __hf, const key_equal& __eql);
864 __hash_table(const hasher& __hf, const key_equal& __eql,
865 const allocator_type& __a);
866 explicit __hash_table(const allocator_type& __a);
867 __hash_table(const __hash_table& __u);
868 __hash_table(const __hash_table& __u, const allocator_type& __a);
869 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
870 __hash_table(__hash_table&& __u)
872 is_nothrow_move_constructible<__bucket_list>::value &&
873 is_nothrow_move_constructible<__first_node>::value &&
874 is_nothrow_move_constructible<__node_allocator>::value &&
875 is_nothrow_move_constructible<hasher>::value &&
876 is_nothrow_move_constructible<key_equal>::value);
877 __hash_table(__hash_table&& __u, const allocator_type& __a);
878 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
881 __hash_table& operator=(const __hash_table& __u);
882 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
883 __hash_table& operator=(__hash_table&& __u)
885 __node_traits::propagate_on_container_move_assignment::value &&
886 is_nothrow_move_assignable<__node_allocator>::value &&
887 is_nothrow_move_assignable<hasher>::value &&
888 is_nothrow_move_assignable<key_equal>::value);
890 template <class _InputIterator>
891 void __assign_unique(_InputIterator __first, _InputIterator __last);
892 template <class _InputIterator>
893 void __assign_multi(_InputIterator __first, _InputIterator __last);
895 _LIBCPP_INLINE_VISIBILITY
896 size_type max_size() const _NOEXCEPT
898 return allocator_traits<__pointer_allocator>::max_size(
899 __bucket_list_.get_deleter().__alloc());
902 pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
903 iterator __node_insert_multi(__node_pointer __nd);
904 iterator __node_insert_multi(const_iterator __p,
905 __node_pointer __nd);
907 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
908 template <class... _Args>
909 pair<iterator, bool> __emplace_unique(_Args&&... __args);
910 template <class... _Args>
911 iterator __emplace_multi(_Args&&... __args);
912 template <class... _Args>
913 iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args);
914 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
916 pair<iterator, bool> __insert_unique(const value_type& __x);
918 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
920 pair<iterator, bool> __insert_unique(_Pp&& __x);
921 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
923 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
925 iterator __insert_multi(_Pp&& __x);
927 iterator __insert_multi(const_iterator __p, _Pp&& __x);
928 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
929 iterator __insert_multi(const value_type& __x);
930 iterator __insert_multi(const_iterator __p, const value_type& __x);
931 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
933 void clear() _NOEXCEPT;
934 void rehash(size_type __n);
935 _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
936 {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
938 _LIBCPP_INLINE_VISIBILITY
939 size_type bucket_count() const _NOEXCEPT
941 return __bucket_list_.get_deleter().size();
944 iterator begin() _NOEXCEPT;
945 iterator end() _NOEXCEPT;
946 const_iterator begin() const _NOEXCEPT;
947 const_iterator end() const _NOEXCEPT;
949 template <class _Key>
950 _LIBCPP_INLINE_VISIBILITY
951 size_type bucket(const _Key& __k) const
953 _LIBCPP_ASSERT(bucket_count() > 0,
954 "unordered container::bucket(key) called when bucket_count() == 0");
955 return __constrain_hash(hash_function()(__k), bucket_count());
958 template <class _Key>
959 iterator find(const _Key& __x);
960 template <class _Key>
961 const_iterator find(const _Key& __x) const;
963 typedef __hash_node_destructor<__node_allocator> _Dp;
964 typedef unique_ptr<__node, _Dp> __node_holder;
966 iterator erase(const_iterator __p);
967 iterator erase(const_iterator __first, const_iterator __last);
968 template <class _Key>
969 size_type __erase_unique(const _Key& __k);
970 template <class _Key>
971 size_type __erase_multi(const _Key& __k);
972 __node_holder remove(const_iterator __p) _NOEXCEPT;
974 template <class _Key>
975 size_type __count_unique(const _Key& __k) const;
976 template <class _Key>
977 size_type __count_multi(const _Key& __k) const;
979 template <class _Key>
980 pair<iterator, iterator>
981 __equal_range_unique(const _Key& __k);
982 template <class _Key>
983 pair<const_iterator, const_iterator>
984 __equal_range_unique(const _Key& __k) const;
986 template <class _Key>
987 pair<iterator, iterator>
988 __equal_range_multi(const _Key& __k);
989 template <class _Key>
990 pair<const_iterator, const_iterator>
991 __equal_range_multi(const _Key& __k) const;
993 void swap(__hash_table& __u)
995 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
996 __is_nothrow_swappable<__pointer_allocator>::value) &&
997 (!__node_traits::propagate_on_container_swap::value ||
998 __is_nothrow_swappable<__node_allocator>::value) &&
999 __is_nothrow_swappable<hasher>::value &&
1000 __is_nothrow_swappable<key_equal>::value);
1002 _LIBCPP_INLINE_VISIBILITY
1003 size_type max_bucket_count() const _NOEXCEPT
1004 {return __pointer_alloc_traits::max_size(__bucket_list_.get_deleter().__alloc());}
1005 size_type bucket_size(size_type __n) const;
1006 _LIBCPP_INLINE_VISIBILITY float load_factor() const _NOEXCEPT
1008 size_type __bc = bucket_count();
1009 return __bc != 0 ? (float)size() / __bc : 0.f;
1011 _LIBCPP_INLINE_VISIBILITY void max_load_factor(float __mlf) _NOEXCEPT
1013 _LIBCPP_ASSERT(__mlf > 0,
1014 "unordered container::max_load_factor(lf) called with lf <= 0");
1015 max_load_factor() = _VSTD::max(__mlf, load_factor());
1018 _LIBCPP_INLINE_VISIBILITY
1020 begin(size_type __n)
1022 _LIBCPP_ASSERT(__n < bucket_count(),
1023 "unordered container::begin(n) called with n >= bucket_count()");
1024 #if _LIBCPP_DEBUG_LEVEL >= 2
1025 return local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1027 return local_iterator(__bucket_list_[__n], __n, bucket_count());
1031 _LIBCPP_INLINE_VISIBILITY
1035 _LIBCPP_ASSERT(__n < bucket_count(),
1036 "unordered container::end(n) called with n >= bucket_count()");
1037 #if _LIBCPP_DEBUG_LEVEL >= 2
1038 return local_iterator(nullptr, __n, bucket_count(), this);
1040 return local_iterator(nullptr, __n, bucket_count());
1044 _LIBCPP_INLINE_VISIBILITY
1045 const_local_iterator
1046 cbegin(size_type __n) const
1048 _LIBCPP_ASSERT(__n < bucket_count(),
1049 "unordered container::cbegin(n) called with n >= bucket_count()");
1050 #if _LIBCPP_DEBUG_LEVEL >= 2
1051 return const_local_iterator(__bucket_list_[__n], __n, bucket_count(), this);
1053 return const_local_iterator(__bucket_list_[__n], __n, bucket_count());
1057 _LIBCPP_INLINE_VISIBILITY
1058 const_local_iterator
1059 cend(size_type __n) const
1061 _LIBCPP_ASSERT(__n < bucket_count(),
1062 "unordered container::cend(n) called with n >= bucket_count()");
1063 #if _LIBCPP_DEBUG_LEVEL >= 2
1064 return const_local_iterator(nullptr, __n, bucket_count(), this);
1066 return const_local_iterator(nullptr, __n, bucket_count());
1070 #if _LIBCPP_DEBUG_LEVEL >= 2
1072 bool __dereferenceable(const const_iterator* __i) const;
1073 bool __decrementable(const const_iterator* __i) const;
1074 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1075 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1077 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1080 void __rehash(size_type __n);
1082 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1083 #ifndef _LIBCPP_HAS_NO_VARIADICS
1084 template <class ..._Args>
1085 __node_holder __construct_node(_Args&& ...__args);
1086 #endif // _LIBCPP_HAS_NO_VARIADICS
1087 __node_holder __construct_node(value_type&& __v, size_t __hash);
1088 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1089 __node_holder __construct_node(const value_type& __v);
1091 __node_holder __construct_node(const value_type& __v, size_t __hash);
1093 _LIBCPP_INLINE_VISIBILITY
1094 void __copy_assign_alloc(const __hash_table& __u)
1095 {__copy_assign_alloc(__u, integral_constant<bool,
1096 __node_traits::propagate_on_container_copy_assignment::value>());}
1097 void __copy_assign_alloc(const __hash_table& __u, true_type);
1098 _LIBCPP_INLINE_VISIBILITY
1099 void __copy_assign_alloc(const __hash_table&, false_type) {}
1101 void __move_assign(__hash_table& __u, false_type);
1102 void __move_assign(__hash_table& __u, true_type)
1104 is_nothrow_move_assignable<__node_allocator>::value &&
1105 is_nothrow_move_assignable<hasher>::value &&
1106 is_nothrow_move_assignable<key_equal>::value);
1107 _LIBCPP_INLINE_VISIBILITY
1108 void __move_assign_alloc(__hash_table& __u)
1110 !__node_traits::propagate_on_container_move_assignment::value ||
1111 (is_nothrow_move_assignable<__pointer_allocator>::value &&
1112 is_nothrow_move_assignable<__node_allocator>::value))
1113 {__move_assign_alloc(__u, integral_constant<bool,
1114 __node_traits::propagate_on_container_move_assignment::value>());}
1115 _LIBCPP_INLINE_VISIBILITY
1116 void __move_assign_alloc(__hash_table& __u, true_type)
1118 is_nothrow_move_assignable<__pointer_allocator>::value &&
1119 is_nothrow_move_assignable<__node_allocator>::value)
1121 __bucket_list_.get_deleter().__alloc() =
1122 _VSTD::move(__u.__bucket_list_.get_deleter().__alloc());
1123 __node_alloc() = _VSTD::move(__u.__node_alloc());
1125 _LIBCPP_INLINE_VISIBILITY
1126 void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
1128 template <class _Ap>
1129 _LIBCPP_INLINE_VISIBILITY
1132 __swap_alloc(_Ap& __x, _Ap& __y)
1134 !allocator_traits<_Ap>::propagate_on_container_swap::value ||
1135 __is_nothrow_swappable<_Ap>::value)
1137 __swap_alloc(__x, __y,
1138 integral_constant<bool,
1139 allocator_traits<_Ap>::propagate_on_container_swap::value
1143 template <class _Ap>
1144 _LIBCPP_INLINE_VISIBILITY
1147 __swap_alloc(_Ap& __x, _Ap& __y, true_type)
1148 _NOEXCEPT_(__is_nothrow_swappable<_Ap>::value)
1154 template <class _Ap>
1155 _LIBCPP_INLINE_VISIBILITY
1158 __swap_alloc(_Ap&, _Ap&, false_type) _NOEXCEPT {}
1160 void __deallocate(__node_pointer __np) _NOEXCEPT;
1161 __node_pointer __detach() _NOEXCEPT;
1163 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_map;
1164 template <class, class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY unordered_multimap;
1167 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1168 inline _LIBCPP_INLINE_VISIBILITY
1169 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
1171 is_nothrow_default_constructible<__bucket_list>::value &&
1172 is_nothrow_default_constructible<__first_node>::value &&
1173 is_nothrow_default_constructible<hasher>::value &&
1174 is_nothrow_default_constructible<key_equal>::value)
1180 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1181 inline _LIBCPP_INLINE_VISIBILITY
1182 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1183 const key_equal& __eql)
1184 : __bucket_list_(nullptr, __bucket_list_deleter()),
1191 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1192 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const hasher& __hf,
1193 const key_equal& __eql,
1194 const allocator_type& __a)
1195 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1196 __p1_(__node_allocator(__a)),
1202 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1203 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const allocator_type& __a)
1204 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1205 __p1_(__node_allocator(__a)),
1211 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1212 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u)
1213 : __bucket_list_(nullptr,
1214 __bucket_list_deleter(allocator_traits<__pointer_allocator>::
1215 select_on_container_copy_construction(
1216 __u.__bucket_list_.get_deleter().__alloc()), 0)),
1217 __p1_(allocator_traits<__node_allocator>::
1218 select_on_container_copy_construction(__u.__node_alloc())),
1219 __p2_(0, __u.hash_function()),
1224 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1225 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(const __hash_table& __u,
1226 const allocator_type& __a)
1227 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1228 __p1_(__node_allocator(__a)),
1229 __p2_(0, __u.hash_function()),
1234 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1236 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1237 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u)
1239 is_nothrow_move_constructible<__bucket_list>::value &&
1240 is_nothrow_move_constructible<__first_node>::value &&
1241 is_nothrow_move_constructible<hasher>::value &&
1242 is_nothrow_move_constructible<key_equal>::value)
1243 : __bucket_list_(_VSTD::move(__u.__bucket_list_)),
1244 __p1_(_VSTD::move(__u.__p1_)),
1245 __p2_(_VSTD::move(__u.__p2_)),
1246 __p3_(_VSTD::move(__u.__p3_))
1250 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1251 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1252 __u.__p1_.first().__next_ = nullptr;
1257 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1258 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table(__hash_table&& __u,
1259 const allocator_type& __a)
1260 : __bucket_list_(nullptr, __bucket_list_deleter(__pointer_allocator(__a), 0)),
1261 __p1_(__node_allocator(__a)),
1262 __p2_(0, _VSTD::move(__u.hash_function())),
1263 __p3_(_VSTD::move(__u.__p3_))
1265 if (__a == allocator_type(__u.__node_alloc()))
1267 __bucket_list_.reset(__u.__bucket_list_.release());
1268 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1269 __u.__bucket_list_.get_deleter().size() = 0;
1272 __p1_.first().__next_ = __u.__p1_.first().__next_;
1273 __u.__p1_.first().__next_ = nullptr;
1274 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1275 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1276 size() = __u.size();
1282 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1284 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1285 __hash_table<_Tp, _Hash, _Equal, _Alloc>::~__hash_table()
1287 __deallocate(__p1_.first().__next_);
1288 #if _LIBCPP_DEBUG_LEVEL >= 2
1289 __get_db()->__erase_c(this);
1293 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1295 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__copy_assign_alloc(
1296 const __hash_table& __u, true_type)
1298 if (__node_alloc() != __u.__node_alloc())
1301 __bucket_list_.reset();
1302 __bucket_list_.get_deleter().size() = 0;
1304 __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
1305 __node_alloc() = __u.__node_alloc();
1308 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1309 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1310 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
1314 __copy_assign_alloc(__u);
1315 hash_function() = __u.hash_function();
1316 key_eq() = __u.key_eq();
1317 max_load_factor() = __u.max_load_factor();
1318 __assign_multi(__u.begin(), __u.end());
1323 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1325 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate(__node_pointer __np)
1328 __node_allocator& __na = __node_alloc();
1329 while (__np != nullptr)
1331 __node_pointer __next = __np->__next_;
1332 #if _LIBCPP_DEBUG_LEVEL >= 2
1333 __c_node* __c = __get_db()->__find_c_and_lock(this);
1334 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1337 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1338 if (__i->__node_ == __np)
1340 (*__p)->__c_ = nullptr;
1341 if (--__c->end_ != __p)
1342 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1345 __get_db()->unlock();
1347 __node_traits::destroy(__na, _VSTD::addressof(__np->__value_));
1348 __node_traits::deallocate(__na, __np, 1);
1353 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1354 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_pointer
1355 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__detach() _NOEXCEPT
1357 size_type __bc = bucket_count();
1358 for (size_type __i = 0; __i < __bc; ++__i)
1359 __bucket_list_[__i] = nullptr;
1361 __node_pointer __cache = __p1_.first().__next_;
1362 __p1_.first().__next_ = nullptr;
1366 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1368 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1370 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1371 __hash_table& __u, true_type)
1373 is_nothrow_move_assignable<__node_allocator>::value &&
1374 is_nothrow_move_assignable<hasher>::value &&
1375 is_nothrow_move_assignable<key_equal>::value)
1378 __bucket_list_.reset(__u.__bucket_list_.release());
1379 __bucket_list_.get_deleter().size() = __u.__bucket_list_.get_deleter().size();
1380 __u.__bucket_list_.get_deleter().size() = 0;
1381 __move_assign_alloc(__u);
1382 size() = __u.size();
1383 hash_function() = _VSTD::move(__u.hash_function());
1384 max_load_factor() = __u.max_load_factor();
1385 key_eq() = _VSTD::move(__u.key_eq());
1386 __p1_.first().__next_ = __u.__p1_.first().__next_;
1389 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
1390 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1391 __u.__p1_.first().__next_ = nullptr;
1394 #if _LIBCPP_DEBUG_LEVEL >= 2
1395 __get_db()->swap(this, &__u);
1399 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1401 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__move_assign(
1402 __hash_table& __u, false_type)
1404 if (__node_alloc() == __u.__node_alloc())
1405 __move_assign(__u, true_type());
1408 hash_function() = _VSTD::move(__u.hash_function());
1409 key_eq() = _VSTD::move(__u.key_eq());
1410 max_load_factor() = __u.max_load_factor();
1411 if (bucket_count() != 0)
1413 __node_pointer __cache = __detach();
1414 #ifndef _LIBCPP_NO_EXCEPTIONS
1417 #endif // _LIBCPP_NO_EXCEPTIONS
1418 const_iterator __i = __u.begin();
1419 while (__cache != nullptr && __u.size() != 0)
1421 __cache->__value_ = _VSTD::move(__u.remove(__i++)->__value_);
1422 __node_pointer __next = __cache->__next_;
1423 __node_insert_multi(__cache);
1426 #ifndef _LIBCPP_NO_EXCEPTIONS
1430 __deallocate(__cache);
1433 #endif // _LIBCPP_NO_EXCEPTIONS
1434 __deallocate(__cache);
1436 const_iterator __i = __u.begin();
1437 while (__u.size() != 0)
1440 __construct_node(_VSTD::move(__u.remove(__i++)->__value_));
1441 __node_insert_multi(__h.get());
1447 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1448 inline _LIBCPP_INLINE_VISIBILITY
1449 __hash_table<_Tp, _Hash, _Equal, _Alloc>&
1450 __hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(__hash_table&& __u)
1452 __node_traits::propagate_on_container_move_assignment::value &&
1453 is_nothrow_move_assignable<__node_allocator>::value &&
1454 is_nothrow_move_assignable<hasher>::value &&
1455 is_nothrow_move_assignable<key_equal>::value)
1457 __move_assign(__u, integral_constant<bool,
1458 __node_traits::propagate_on_container_move_assignment::value>());
1462 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1464 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1465 template <class _InputIterator>
1467 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_unique(_InputIterator __first,
1468 _InputIterator __last)
1470 if (bucket_count() != 0)
1472 __node_pointer __cache = __detach();
1473 #ifndef _LIBCPP_NO_EXCEPTIONS
1476 #endif // _LIBCPP_NO_EXCEPTIONS
1477 for (; __cache != nullptr && __first != __last; ++__first)
1479 __cache->__value_ = *__first;
1480 __node_pointer __next = __cache->__next_;
1481 __node_insert_unique(__cache);
1484 #ifndef _LIBCPP_NO_EXCEPTIONS
1488 __deallocate(__cache);
1491 #endif // _LIBCPP_NO_EXCEPTIONS
1492 __deallocate(__cache);
1494 for (; __first != __last; ++__first)
1495 __insert_unique(*__first);
1498 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1499 template <class _InputIterator>
1501 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__assign_multi(_InputIterator __first,
1502 _InputIterator __last)
1504 if (bucket_count() != 0)
1506 __node_pointer __cache = __detach();
1507 #ifndef _LIBCPP_NO_EXCEPTIONS
1510 #endif // _LIBCPP_NO_EXCEPTIONS
1511 for (; __cache != nullptr && __first != __last; ++__first)
1513 __cache->__value_ = *__first;
1514 __node_pointer __next = __cache->__next_;
1515 __node_insert_multi(__cache);
1518 #ifndef _LIBCPP_NO_EXCEPTIONS
1522 __deallocate(__cache);
1525 #endif // _LIBCPP_NO_EXCEPTIONS
1526 __deallocate(__cache);
1528 for (; __first != __last; ++__first)
1529 __insert_multi(*__first);
1532 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1533 inline _LIBCPP_INLINE_VISIBILITY
1534 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1535 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() _NOEXCEPT
1537 #if _LIBCPP_DEBUG_LEVEL >= 2
1538 return iterator(__p1_.first().__next_, this);
1540 return iterator(__p1_.first().__next_);
1544 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1545 inline _LIBCPP_INLINE_VISIBILITY
1546 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1547 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() _NOEXCEPT
1549 #if _LIBCPP_DEBUG_LEVEL >= 2
1550 return iterator(nullptr, this);
1552 return iterator(nullptr);
1556 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1557 inline _LIBCPP_INLINE_VISIBILITY
1558 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1559 __hash_table<_Tp, _Hash, _Equal, _Alloc>::begin() const _NOEXCEPT
1561 #if _LIBCPP_DEBUG_LEVEL >= 2
1562 return const_iterator(__p1_.first().__next_, this);
1564 return const_iterator(__p1_.first().__next_);
1568 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1569 inline _LIBCPP_INLINE_VISIBILITY
1570 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
1571 __hash_table<_Tp, _Hash, _Equal, _Alloc>::end() const _NOEXCEPT
1573 #if _LIBCPP_DEBUG_LEVEL >= 2
1574 return const_iterator(nullptr, this);
1576 return const_iterator(nullptr);
1580 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1582 __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
1586 __deallocate(__p1_.first().__next_);
1587 __p1_.first().__next_ = nullptr;
1588 size_type __bc = bucket_count();
1589 for (size_type __i = 0; __i < __bc; ++__i)
1590 __bucket_list_[__i] = nullptr;
1595 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1596 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1597 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
1599 __nd->__hash_ = hash_function()(__nd->__value_);
1600 size_type __bc = bucket_count();
1601 bool __inserted = false;
1602 __node_pointer __ndptr;
1606 __chash = __constrain_hash(__nd->__hash_, __bc);
1607 __ndptr = __bucket_list_[__chash];
1608 if (__ndptr != nullptr)
1610 for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
1611 __constrain_hash(__ndptr->__hash_, __bc) == __chash;
1612 __ndptr = __ndptr->__next_)
1614 if (key_eq()(__ndptr->__value_, __nd->__value_))
1620 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1622 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1623 size_type(ceil(float(size() + 1) / max_load_factor()))));
1624 __bc = bucket_count();
1625 __chash = __constrain_hash(__nd->__hash_, __bc);
1627 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1628 __node_pointer __pn = __bucket_list_[__chash];
1629 if (__pn == nullptr)
1631 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1632 __nd->__next_ = __pn->__next_;
1633 __pn->__next_ = __nd;
1634 // fix up __bucket_list_
1635 __bucket_list_[__chash] = __pn;
1636 if (__nd->__next_ != nullptr)
1637 __bucket_list_[__constrain_hash(__nd->__next_->__hash_, __bc)] = __nd;
1641 __nd->__next_ = __pn->__next_;
1642 __pn->__next_ = __nd;
1650 #if _LIBCPP_DEBUG_LEVEL >= 2
1651 return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
1653 return pair<iterator, bool>(iterator(__ndptr), __inserted);
1657 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1658 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1659 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
1661 __cp->__hash_ = hash_function()(__cp->__value_);
1662 size_type __bc = bucket_count();
1663 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1665 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1666 size_type(ceil(float(size() + 1) / max_load_factor()))));
1667 __bc = bucket_count();
1669 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1670 __node_pointer __pn = __bucket_list_[__chash];
1671 if (__pn == nullptr)
1673 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1674 __cp->__next_ = __pn->__next_;
1675 __pn->__next_ = __cp;
1676 // fix up __bucket_list_
1677 __bucket_list_[__chash] = __pn;
1678 if (__cp->__next_ != nullptr)
1679 __bucket_list_[__constrain_hash(__cp->__next_->__hash_, __bc)] = __cp;
1683 for (bool __found = false; __pn->__next_ != nullptr &&
1684 __constrain_hash(__pn->__next_->__hash_, __bc) == __chash;
1685 __pn = __pn->__next_)
1687 // __found key_eq() action
1690 // false true set __found to true
1692 if (__found != (__pn->__next_->__hash_ == __cp->__hash_ &&
1693 key_eq()(__pn->__next_->__value_, __cp->__value_)))
1701 __cp->__next_ = __pn->__next_;
1702 __pn->__next_ = __cp;
1703 if (__cp->__next_ != nullptr)
1705 size_t __nhash = __constrain_hash(__cp->__next_->__hash_, __bc);
1706 if (__nhash != __chash)
1707 __bucket_list_[__nhash] = __cp;
1711 #if _LIBCPP_DEBUG_LEVEL >= 2
1712 return iterator(__cp, this);
1714 return iterator(__cp);
1718 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1719 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1720 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(
1721 const_iterator __p, __node_pointer __cp)
1723 #if _LIBCPP_DEBUG_LEVEL >= 2
1724 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1725 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1726 " referring to this unordered container");
1728 if (__p != end() && key_eq()(*__p, __cp->__value_))
1730 __node_pointer __np = __p.__node_;
1731 __cp->__hash_ = __np->__hash_;
1732 size_type __bc = bucket_count();
1733 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1735 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1736 size_type(ceil(float(size() + 1) / max_load_factor()))));
1737 __bc = bucket_count();
1739 size_t __chash = __constrain_hash(__cp->__hash_, __bc);
1740 __node_pointer __pp = __bucket_list_[__chash];
1741 while (__pp->__next_ != __np)
1742 __pp = __pp->__next_;
1743 __cp->__next_ = __np;
1744 __pp->__next_ = __cp;
1746 #if _LIBCPP_DEBUG_LEVEL >= 2
1747 return iterator(__cp, this);
1749 return iterator(__cp);
1752 return __node_insert_multi(__cp);
1755 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1756 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1757 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(const value_type& __x)
1759 size_t __hash = hash_function()(__x);
1760 size_type __bc = bucket_count();
1761 bool __inserted = false;
1762 __node_pointer __nd;
1766 __chash = __constrain_hash(__hash, __bc);
1767 __nd = __bucket_list_[__chash];
1768 if (__nd != nullptr)
1770 for (__nd = __nd->__next_; __nd != nullptr &&
1771 __constrain_hash(__nd->__hash_, __bc) == __chash;
1772 __nd = __nd->__next_)
1774 if (key_eq()(__nd->__value_, __x))
1780 __node_holder __h = __construct_node(__x, __hash);
1781 if (size()+1 > __bc * max_load_factor() || __bc == 0)
1783 rehash(_VSTD::max<size_type>(2 * __bc + !__is_power2(__bc),
1784 size_type(ceil(float(size() + 1) / max_load_factor()))));
1785 __bc = bucket_count();
1786 __chash = __constrain_hash(__hash, __bc);
1788 // insert_after __bucket_list_[__chash], or __first_node if bucket is null
1789 __node_pointer __pn = __bucket_list_[__chash];
1790 if (__pn == nullptr)
1792 __pn = static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
1793 __h->__next_ = __pn->__next_;
1794 __pn->__next_ = __h.get();
1795 // fix up __bucket_list_
1796 __bucket_list_[__chash] = __pn;
1797 if (__h->__next_ != nullptr)
1798 __bucket_list_[__constrain_hash(__h->__next_->__hash_, __bc)] = __h.get();
1802 __h->__next_ = __pn->__next_;
1803 __pn->__next_ = __h.get();
1805 __nd = __h.release();
1811 #if _LIBCPP_DEBUG_LEVEL >= 2
1812 return pair<iterator, bool>(iterator(__nd, this), __inserted);
1814 return pair<iterator, bool>(iterator(__nd), __inserted);
1818 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1819 #ifndef _LIBCPP_HAS_NO_VARIADICS
1821 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1822 template <class... _Args>
1823 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1824 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_unique(_Args&&... __args)
1826 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1827 pair<iterator, bool> __r = __node_insert_unique(__h.get());
1833 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1834 template <class... _Args>
1835 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1836 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_multi(_Args&&... __args)
1838 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1839 iterator __r = __node_insert_multi(__h.get());
1844 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1845 template <class... _Args>
1846 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1847 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__emplace_hint_multi(
1848 const_iterator __p, _Args&&... __args)
1850 #if _LIBCPP_DEBUG_LEVEL >= 2
1851 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1852 "unordered container::emplace_hint(const_iterator, args...) called with an iterator not"
1853 " referring to this unordered container");
1855 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1856 iterator __r = __node_insert_multi(__p, __h.get());
1861 #endif // _LIBCPP_HAS_NO_VARIADICS
1863 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1864 template <class _Pp>
1865 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
1866 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_unique(_Pp&& __x)
1868 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1869 pair<iterator, bool> __r = __node_insert_unique(__h.get());
1875 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1877 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1879 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1880 template <class _Pp>
1881 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1882 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(_Pp&& __x)
1884 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1885 iterator __r = __node_insert_multi(__h.get());
1890 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1891 template <class _Pp>
1892 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1893 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1896 #if _LIBCPP_DEBUG_LEVEL >= 2
1897 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1898 "unordered container::insert(const_iterator, rvalue) called with an iterator not"
1899 " referring to this unordered container");
1901 __node_holder __h = __construct_node(_VSTD::forward<_Pp>(__x));
1902 iterator __r = __node_insert_multi(__p, __h.get());
1907 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1909 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1910 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1911 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const value_type& __x)
1913 __node_holder __h = __construct_node(__x);
1914 iterator __r = __node_insert_multi(__h.get());
1919 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1920 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
1921 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__insert_multi(const_iterator __p,
1922 const value_type& __x)
1924 #if _LIBCPP_DEBUG_LEVEL >= 2
1925 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1926 "unordered container::insert(const_iterator, lvalue) called with an iterator not"
1927 " referring to this unordered container");
1929 __node_holder __h = __construct_node(__x);
1930 iterator __r = __node_insert_multi(__p, __h.get());
1935 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1937 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1939 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
1943 else if (__n & (__n - 1))
1944 __n = __next_prime(__n);
1945 size_type __bc = bucket_count();
1948 else if (__n < __bc)
1950 __n = _VSTD::max<size_type>
1953 __is_power2(__bc) ? __next_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
1954 __next_prime(size_t(ceil(float(size()) / max_load_factor())))
1961 template <class _Tp, class _Hash, class _Equal, class _Alloc>
1963 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__rehash(size_type __nbc)
1965 #if _LIBCPP_DEBUG_LEVEL >= 2
1966 __get_db()->__invalidate_all(this);
1967 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1968 __pointer_allocator& __npa = __bucket_list_.get_deleter().__alloc();
1969 __bucket_list_.reset(__nbc > 0 ?
1970 __pointer_alloc_traits::allocate(__npa, __nbc) : nullptr);
1971 __bucket_list_.get_deleter().size() = __nbc;
1974 for (size_type __i = 0; __i < __nbc; ++__i)
1975 __bucket_list_[__i] = nullptr;
1976 __node_pointer __pp(static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first())));
1977 __node_pointer __cp = __pp->__next_;
1978 if (__cp != nullptr)
1980 size_type __chash = __constrain_hash(__cp->__hash_, __nbc);
1981 __bucket_list_[__chash] = __pp;
1982 size_type __phash = __chash;
1983 for (__pp = __cp, __cp = __cp->__next_; __cp != nullptr;
1984 __cp = __pp->__next_)
1986 __chash = __constrain_hash(__cp->__hash_, __nbc);
1987 if (__chash == __phash)
1991 if (__bucket_list_[__chash] == nullptr)
1993 __bucket_list_[__chash] = __pp;
1999 __node_pointer __np = __cp;
2000 for (; __np->__next_ != nullptr &&
2001 key_eq()(__cp->__value_, __np->__next_->__value_);
2002 __np = __np->__next_)
2004 __pp->__next_ = __np->__next_;
2005 __np->__next_ = __bucket_list_[__chash]->__next_;
2006 __bucket_list_[__chash]->__next_ = __cp;
2015 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2016 template <class _Key>
2017 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2018 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
2020 size_t __hash = hash_function()(__k);
2021 size_type __bc = bucket_count();
2024 size_t __chash = __constrain_hash(__hash, __bc);
2025 __node_pointer __nd = __bucket_list_[__chash];
2026 if (__nd != nullptr)
2028 for (__nd = __nd->__next_; __nd != nullptr &&
2029 __constrain_hash(__nd->__hash_, __bc) == __chash;
2030 __nd = __nd->__next_)
2032 if (key_eq()(__nd->__value_, __k))
2033 #if _LIBCPP_DEBUG_LEVEL >= 2
2034 return iterator(__nd, this);
2036 return iterator(__nd);
2044 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2045 template <class _Key>
2046 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator
2047 __hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k) const
2049 size_t __hash = hash_function()(__k);
2050 size_type __bc = bucket_count();
2053 size_t __chash = __constrain_hash(__hash, __bc);
2054 __node_const_pointer __nd = __bucket_list_[__chash];
2055 if (__nd != nullptr)
2057 for (__nd = __nd->__next_; __nd != nullptr &&
2058 __constrain_hash(__nd->__hash_, __bc) == __chash;
2059 __nd = __nd->__next_)
2061 if (key_eq()(__nd->__value_, __k))
2062 #if _LIBCPP_DEBUG_LEVEL >= 2
2063 return const_iterator(__nd, this);
2065 return const_iterator(__nd);
2074 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2075 #ifndef _LIBCPP_HAS_NO_VARIADICS
2077 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2078 template <class ..._Args>
2079 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2080 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(_Args&& ...__args)
2082 __node_allocator& __na = __node_alloc();
2083 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2084 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_Args>(__args)...);
2085 __h.get_deleter().__value_constructed = true;
2086 __h->__hash_ = hash_function()(__h->__value_);
2087 __h->__next_ = nullptr;
2091 #endif // _LIBCPP_HAS_NO_VARIADICS
2093 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2094 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2095 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(value_type&& __v,
2098 __node_allocator& __na = __node_alloc();
2099 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2100 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::move(__v));
2101 __h.get_deleter().__value_constructed = true;
2102 __h->__hash_ = __hash;
2103 __h->__next_ = nullptr;
2107 #else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2109 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2110 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2111 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v)
2113 __node_allocator& __na = __node_alloc();
2114 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2115 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
2116 __h.get_deleter().__value_constructed = true;
2117 __h->__hash_ = hash_function()(__h->__value_);
2118 __h->__next_ = nullptr;
2119 return _VSTD::move(__h); // explicitly moved for C++03
2122 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2124 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2125 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2126 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__construct_node(const value_type& __v,
2129 __node_allocator& __na = __node_alloc();
2130 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
2131 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), __v);
2132 __h.get_deleter().__value_constructed = true;
2133 __h->__hash_ = __hash;
2134 __h->__next_ = nullptr;
2135 return _VSTD::move(__h); // explicitly moved for C++03
2138 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2139 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2140 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __p)
2142 __node_pointer __np = __p.__node_;
2143 #if _LIBCPP_DEBUG_LEVEL >= 2
2144 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
2145 "unordered container erase(iterator) called with an iterator not"
2146 " referring to this container");
2147 _LIBCPP_ASSERT(__p != end(),
2148 "unordered container erase(iterator) called with a non-dereferenceable iterator");
2149 iterator __r(__np, this);
2158 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2159 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
2160 __hash_table<_Tp, _Hash, _Equal, _Alloc>::erase(const_iterator __first,
2161 const_iterator __last)
2163 #if _LIBCPP_DEBUG_LEVEL >= 2
2164 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
2165 "unodered container::erase(iterator, iterator) called with an iterator not"
2166 " referring to this unodered container");
2167 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
2168 "unodered container::erase(iterator, iterator) called with an iterator not"
2169 " referring to this unodered container");
2171 for (const_iterator __p = __first; __first != __last; __p = __first)
2176 __node_pointer __np = __last.__node_;
2177 #if _LIBCPP_DEBUG_LEVEL >= 2
2178 return iterator (__np, this);
2180 return iterator (__np);
2184 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2185 template <class _Key>
2186 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2187 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_unique(const _Key& __k)
2189 iterator __i = find(__k);
2196 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2197 template <class _Key>
2198 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2199 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__erase_multi(const _Key& __k)
2202 iterator __i = find(__k);
2205 iterator __e = end();
2210 } while (__i != __e && key_eq()(*__i, __k));
2215 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2216 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_holder
2217 __hash_table<_Tp, _Hash, _Equal, _Alloc>::remove(const_iterator __p) _NOEXCEPT
2220 __node_pointer __cn = __p.__node_;
2221 size_type __bc = bucket_count();
2222 size_t __chash = __constrain_hash(__cn->__hash_, __bc);
2223 // find previous node
2224 __node_pointer __pn = __bucket_list_[__chash];
2225 for (; __pn->__next_ != __cn; __pn = __pn->__next_)
2227 // Fix up __bucket_list_
2228 // if __pn is not in same bucket (before begin is not in same bucket) &&
2229 // if __cn->__next_ is not in same bucket (nullptr is not in same bucket)
2230 if (__pn == static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()))
2231 || __constrain_hash(__pn->__hash_, __bc) != __chash)
2233 if (__cn->__next_ == nullptr || __constrain_hash(__cn->__next_->__hash_, __bc) != __chash)
2234 __bucket_list_[__chash] = nullptr;
2236 // if __cn->__next_ is not in same bucket (nullptr is in same bucket)
2237 if (__cn->__next_ != nullptr)
2239 size_t __nhash = __constrain_hash(__cn->__next_->__hash_, __bc);
2240 if (__nhash != __chash)
2241 __bucket_list_[__nhash] = __pn;
2244 __pn->__next_ = __cn->__next_;
2245 __cn->__next_ = nullptr;
2247 #if _LIBCPP_DEBUG_LEVEL >= 2
2248 __c_node* __c = __get_db()->__find_c_and_lock(this);
2249 for (__i_node** __p = __c->end_; __p != __c->beg_; )
2252 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2253 if (__i->__node_ == __cn)
2255 (*__p)->__c_ = nullptr;
2256 if (--__c->end_ != __p)
2257 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
2260 __get_db()->unlock();
2262 return __node_holder(__cn, _Dp(__node_alloc(), true));
2265 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2266 template <class _Key>
2267 inline _LIBCPP_INLINE_VISIBILITY
2268 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2269 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_unique(const _Key& __k) const
2271 return static_cast<size_type>(find(__k) != end());
2274 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2275 template <class _Key>
2276 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2277 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__count_multi(const _Key& __k) const
2280 const_iterator __i = find(__k);
2283 const_iterator __e = end();
2288 } while (__i != __e && key_eq()(*__i, __k));
2293 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2294 template <class _Key>
2295 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2296 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2297 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2300 iterator __i = find(__k);
2304 return pair<iterator, iterator>(__i, __j);
2307 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2308 template <class _Key>
2309 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2310 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2311 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_unique(
2312 const _Key& __k) const
2314 const_iterator __i = find(__k);
2315 const_iterator __j = __i;
2318 return pair<const_iterator, const_iterator>(__i, __j);
2321 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2322 template <class _Key>
2323 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator,
2324 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator>
2325 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2328 iterator __i = find(__k);
2332 iterator __e = end();
2336 } while (__j != __e && key_eq()(*__j, __k));
2338 return pair<iterator, iterator>(__i, __j);
2341 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2342 template <class _Key>
2343 pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator,
2344 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::const_iterator>
2345 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__equal_range_multi(
2346 const _Key& __k) const
2348 const_iterator __i = find(__k);
2349 const_iterator __j = __i;
2352 const_iterator __e = end();
2356 } while (__j != __e && key_eq()(*__j, __k));
2358 return pair<const_iterator, const_iterator>(__i, __j);
2361 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2363 __hash_table<_Tp, _Hash, _Equal, _Alloc>::swap(__hash_table& __u)
2365 (!allocator_traits<__pointer_allocator>::propagate_on_container_swap::value ||
2366 __is_nothrow_swappable<__pointer_allocator>::value) &&
2367 (!__node_traits::propagate_on_container_swap::value ||
2368 __is_nothrow_swappable<__node_allocator>::value) &&
2369 __is_nothrow_swappable<hasher>::value &&
2370 __is_nothrow_swappable<key_equal>::value)
2373 __node_pointer_pointer __npp = __bucket_list_.release();
2374 __bucket_list_.reset(__u.__bucket_list_.release());
2375 __u.__bucket_list_.reset(__npp);
2377 _VSTD::swap(__bucket_list_.get_deleter().size(), __u.__bucket_list_.get_deleter().size());
2378 __swap_alloc(__bucket_list_.get_deleter().__alloc(),
2379 __u.__bucket_list_.get_deleter().__alloc());
2380 __swap_alloc(__node_alloc(), __u.__node_alloc());
2381 _VSTD::swap(__p1_.first().__next_, __u.__p1_.first().__next_);
2382 __p2_.swap(__u.__p2_);
2383 __p3_.swap(__u.__p3_);
2385 __bucket_list_[__constrain_hash(__p1_.first().__next_->__hash_, bucket_count())] =
2386 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__p1_.first()));
2388 __u.__bucket_list_[__constrain_hash(__u.__p1_.first().__next_->__hash_, __u.bucket_count())] =
2389 static_cast<__node_pointer>(pointer_traits<__node_base_pointer>::pointer_to(__u.__p1_.first()));
2390 #if _LIBCPP_DEBUG_LEVEL >= 2
2391 __get_db()->swap(this, &__u);
2395 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2396 typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::size_type
2397 __hash_table<_Tp, _Hash, _Equal, _Alloc>::bucket_size(size_type __n) const
2399 _LIBCPP_ASSERT(__n < bucket_count(),
2400 "unordered container::bucket_size(n) called with n >= bucket_count()");
2401 __node_const_pointer __np = __bucket_list_[__n];
2402 size_type __bc = bucket_count();
2404 if (__np != nullptr)
2406 for (__np = __np->__next_; __np != nullptr &&
2407 __constrain_hash(__np->__hash_, __bc) == __n;
2408 __np = __np->__next_, ++__r)
2414 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2415 inline _LIBCPP_INLINE_VISIBILITY
2417 swap(__hash_table<_Tp, _Hash, _Equal, _Alloc>& __x,
2418 __hash_table<_Tp, _Hash, _Equal, _Alloc>& __y)
2419 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2424 #if _LIBCPP_DEBUG_LEVEL >= 2
2426 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2428 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__dereferenceable(const const_iterator* __i) const
2430 return __i->__node_ != nullptr;
2433 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2435 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__decrementable(const const_iterator*) const
2440 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2442 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__addable(const const_iterator*, ptrdiff_t) const
2447 template <class _Tp, class _Hash, class _Equal, class _Alloc>
2449 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__subscriptable(const const_iterator*, ptrdiff_t) const
2454 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2455 _LIBCPP_END_NAMESPACE_STD
2457 #endif // _LIBCPP__HASH_TABLE