31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
38 namespace std _GLIBCXX_VISIBILITY(default)
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42 template<
typename _Key,
typename _Value,
typename _Alloc,
43 typename _ExtractKey,
typename _Equal,
44 typename _Hash,
typename _RangeHash,
typename _Unused,
45 typename _RehashPolicy,
typename _Traits>
55 template<
typename _Key,
typename _Value,
typename _ExtractKey,
56 typename _Equal,
typename _Hash,
typename _RangeHash,
57 typename _Unused,
typename _Traits>
58 struct _Hashtable_base;
62 template<
class _Iterator>
64 __distance_fw(_Iterator __first, _Iterator __last,
66 {
return __first != __last ? 1 : 0; }
68 template<
class _Iterator>
70 __distance_fw(_Iterator __first, _Iterator __last,
72 {
return std::distance(__first, __last); }
74 template<
class _Iterator>
76 __distance_fw(_Iterator __first, _Iterator __last)
77 {
return __distance_fw(__first, __last,
82 template<
typename _Tp>
84 operator()(_Tp&& __x)
const noexcept
85 {
return std::forward<_Tp>(__x); }
90 template<
typename _Tp>
92 operator()(_Tp&& __x)
const noexcept
93 -> decltype(std::get<0>(std::forward<_Tp>(__x)))
94 {
return std::get<0>(std::forward<_Tp>(__x)); }
97 template<
typename _NodeAlloc>
98 struct _Hashtable_alloc;
102 template<
typename _NodeAlloc>
103 struct _ReuseOrAllocNode
106 using __node_alloc_type = _NodeAlloc;
107 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
108 using __node_alloc_traits =
109 typename __hashtable_alloc::__node_alloc_traits;
110 using __node_type =
typename __hashtable_alloc::__node_type;
113 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
114 : _M_nodes(__nodes), _M_h(__h) { }
115 _ReuseOrAllocNode(
const _ReuseOrAllocNode&) =
delete;
118 { _M_h._M_deallocate_nodes(_M_nodes); }
120 template<
typename _Arg>
122 operator()(_Arg&& __arg)
const
126 __node_type* __node = _M_nodes;
127 _M_nodes = _M_nodes->_M_next();
128 __node->_M_nxt =
nullptr;
129 auto& __a = _M_h._M_node_allocator();
130 __node_alloc_traits::destroy(__a, __node->_M_valptr());
133 __node_alloc_traits::construct(__a, __node->_M_valptr(),
134 std::forward<_Arg>(__arg));
138 _M_h._M_deallocate_node_ptr(__node);
139 __throw_exception_again;
143 return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
147 mutable __node_type* _M_nodes;
148 __hashtable_alloc& _M_h;
153 template<
typename _NodeAlloc>
157 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
158 using __node_type =
typename __hashtable_alloc::__node_type;
161 _AllocNode(__hashtable_alloc& __h)
164 template<
typename _Arg>
166 operator()(_Arg&& __arg)
const
167 {
return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
170 __hashtable_alloc& _M_h;
198 template<
bool _Cache_hash_code,
bool _Constant_iterators,
bool _Unique_keys>
228 template<
typename _Value>
231 typedef _Value value_type;
233 __gnu_cxx::__aligned_buffer<_Value> _M_storage;
237 {
return _M_storage._M_ptr(); }
240 _M_valptr()
const noexcept
241 {
return _M_storage._M_ptr(); }
245 {
return *_M_valptr(); }
248 _M_v()
const noexcept
249 {
return *_M_valptr(); }
255 template<
bool _Cache_hash_code>
264 { std::size_t _M_hash_code; };
266 template<
typename _Value,
bool _Cache_hash_code>
267 struct _Hash_node_value
275 template<
typename _Value,
bool _Cache_hash_code>
278 , _Hash_node_value<_Value, _Cache_hash_code>
281 _M_next()
const noexcept
282 {
return static_cast<_Hash_node*
>(this->_M_nxt); }
286 template<
typename _Value,
bool _Cache_hash_code>
299 { _M_cur = _M_cur->_M_next(); }
304 {
return __x._M_cur == __y._M_cur; }
306 #if __cpp_impl_three_way_comparison < 201907L
310 {
return __x._M_cur != __y._M_cur; }
315 template<
typename _Value,
bool __constant_iterators,
bool __cache>
324 typedef _Value value_type;
325 typedef std::ptrdiff_t difference_type;
329 const value_type*, value_type*>::type;
332 const value_type&, value_type&>::type;
341 operator*()
const noexcept
342 {
return this->_M_cur->_M_v(); }
345 operator->()
const noexcept
346 {
return this->_M_cur->_M_valptr(); }
349 operator++() noexcept
356 operator++(
int) noexcept
365 template<
typename _Value,
bool __constant_iterators,
bool __cache>
374 typedef _Value value_type;
375 typedef std::ptrdiff_t difference_type;
378 typedef const value_type* pointer;
379 typedef const value_type& reference;
388 __cache>& __x) noexcept
392 operator*()
const noexcept
393 {
return this->_M_cur->_M_v(); }
396 operator->()
const noexcept
397 {
return this->_M_cur->_M_valptr(); }
400 operator++() noexcept
407 operator++(
int) noexcept
422 typedef std::size_t first_argument_type;
423 typedef std::size_t second_argument_type;
424 typedef std::size_t result_type;
427 operator()(first_argument_type __num,
428 second_argument_type __den)
const noexcept
429 {
return __num % __den; }
446 : _M_max_load_factor(__z), _M_next_resize(0) { }
449 max_load_factor()
const noexcept
450 {
return _M_max_load_factor; }
454 _M_next_bkt(std::size_t __n)
const;
458 _M_bkt_for_elements(std::size_t __n)
const
459 {
return __builtin_ceil(__n / (
double)_M_max_load_factor); }
466 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
467 std::size_t __n_ins)
const;
469 typedef std::size_t _State;
473 {
return _M_next_resize; }
477 { _M_next_resize = 0; }
480 _M_reset(_State __state)
481 { _M_next_resize = __state; }
483 static const std::size_t _S_growth_factor = 2;
485 float _M_max_load_factor;
486 mutable std::size_t _M_next_resize;
492 typedef std::size_t first_argument_type;
493 typedef std::size_t second_argument_type;
494 typedef std::size_t result_type;
497 operator()(first_argument_type __num,
498 second_argument_type __den)
const noexcept
499 {
return __num & (__den - 1); }
510 const unsigned __lz =
sizeof(size_t) >
sizeof(
long)
511 ? __builtin_clzll(__n - 1ull)
512 : __builtin_clzl(__n - 1ul);
514 return (
size_t(1) << (__int_traits<size_t>::__digits - __lz - 1)) << 1;
524 : _M_max_load_factor(__z), _M_next_resize(0) { }
527 max_load_factor()
const noexcept
528 {
return _M_max_load_factor; }
533 _M_next_bkt(std::size_t __n) noexcept
541 const auto __max_width = std::min<size_t>(
sizeof(
size_t), 8);
542 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
543 std::size_t __res =
__clp2(__n);
553 if (__res == __max_bkt)
557 _M_next_resize = size_t(-1);
560 = __builtin_floor(__res * (
double)_M_max_load_factor);
567 _M_bkt_for_elements(std::size_t __n)
const noexcept
568 {
return __builtin_ceil(__n / (
double)_M_max_load_factor); }
575 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
576 std::size_t __n_ins) noexcept
578 if (__n_elt + __n_ins > _M_next_resize)
584 = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
585 / (double)_M_max_load_factor;
586 if (__min_bkts >= __n_bkt)
588 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
589 __n_bkt * _S_growth_factor)) };
592 = __builtin_floor(__n_bkt * (
double)_M_max_load_factor);
599 typedef std::size_t _State;
602 _M_state()
const noexcept
603 {
return _M_next_resize; }
607 { _M_next_resize = 0; }
610 _M_reset(_State __state) noexcept
611 { _M_next_resize = __state; }
613 static const std::size_t _S_growth_factor = 2;
615 float _M_max_load_factor;
616 std::size_t _M_next_resize;
637 template<
typename _Key,
typename _Value,
typename _Alloc,
638 typename _ExtractKey,
typename _Equal,
639 typename _Hash,
typename _RangeHash,
typename _Unused,
640 typename _RehashPolicy,
typename _Traits,
641 bool _Unique_keys = _Traits::__unique_keys::value>
645 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
646 typename _Hash,
typename _RangeHash,
typename _Unused,
647 typename _RehashPolicy,
typename _Traits>
648 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
649 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
655 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
656 typename _Hash,
typename _RangeHash,
typename _Unused,
657 typename _RehashPolicy,
typename _Traits>
658 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
659 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
663 _Hash, _RangeHash, _Unused,
668 _Unused, _RehashPolicy, _Traits>;
670 using __hash_code =
typename __hashtable_base::__hash_code;
673 using key_type =
typename __hashtable_base::key_type;
677 operator[](
const key_type& __k);
680 operator[](key_type&& __k);
685 at(
const key_type& __k);
688 at(
const key_type& __k)
const;
691 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
692 typename _Hash,
typename _RangeHash,
typename _Unused,
693 typename _RehashPolicy,
typename _Traits>
695 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
696 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
697 operator[](
const key_type& __k)
700 __hashtable* __h =
static_cast<__hashtable*
>(
this);
701 __hash_code __code = __h->_M_hash_code(__k);
702 std::size_t __bkt = __h->_M_bucket_index(__code);
703 if (
auto __node = __h->_M_find_node(__bkt, __k, __code))
704 return __node->_M_v().second;
706 typename __hashtable::_Scoped_node __node {
713 = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
714 __node._M_node =
nullptr;
715 return __pos->second;
718 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
719 typename _Hash,
typename _RangeHash,
typename _Unused,
720 typename _RehashPolicy,
typename _Traits>
722 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
723 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
724 operator[](key_type&& __k)
727 __hashtable* __h =
static_cast<__hashtable*
>(
this);
728 __hash_code __code = __h->_M_hash_code(__k);
729 std::size_t __bkt = __h->_M_bucket_index(__code);
730 if (
auto __node = __h->_M_find_node(__bkt, __k, __code))
731 return __node->_M_v().second;
733 typename __hashtable::_Scoped_node __node {
740 = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
741 __node._M_node =
nullptr;
742 return __pos->second;
745 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
746 typename _Hash,
typename _RangeHash,
typename _Unused,
747 typename _RehashPolicy,
typename _Traits>
749 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
750 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
751 at(
const key_type& __k)
754 __hashtable* __h =
static_cast<__hashtable*
>(
this);
755 auto __ite = __h->find(__k);
758 __throw_out_of_range(__N(
"_Map_base::at"));
759 return __ite->second;
762 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
763 typename _Hash,
typename _RangeHash,
typename _Unused,
764 typename _RehashPolicy,
typename _Traits>
766 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
767 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
768 at(
const key_type& __k)
const
769 ->
const mapped_type&
771 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
772 auto __ite = __h->find(__k);
775 __throw_out_of_range(__N(
"_Map_base::at"));
776 return __ite->second;
784 template<
typename _Key,
typename _Value,
typename _Alloc,
785 typename _ExtractKey,
typename _Equal,
786 typename _Hash,
typename _RangeHash,
typename _Unused,
787 typename _RehashPolicy,
typename _Traits>
792 _Equal, _Hash, _RangeHash,
797 _Unused, _RehashPolicy, _Traits>;
799 using __hash_cached =
typename _Traits::__hash_cached;
800 using __constant_iterators =
typename _Traits::__constant_iterators;
804 __hash_cached::value>>>;
806 using value_type =
typename __hashtable_base::value_type;
807 using size_type =
typename __hashtable_base::size_type;
809 using __unique_keys =
typename _Traits::__unique_keys;
810 using __node_alloc_type =
typename __hashtable_alloc::__node_alloc_type;
811 using __node_gen_type = _AllocNode<__node_alloc_type>;
814 _M_conjure_hashtable()
817 template<
typename _InputIterator,
typename _NodeGetter>
819 _M_insert_range(_InputIterator __first, _InputIterator __last,
822 template<
typename _InputIterator,
typename _NodeGetter>
824 _M_insert_range(_InputIterator __first, _InputIterator __last,
829 __hash_cached::value>;
832 __hash_cached::value>;
839 insert(
const value_type& __v)
842 __node_gen_type __node_gen(__h);
843 return __h._M_insert(__v, __node_gen, __unique_keys{});
850 __node_gen_type __node_gen(__h);
851 return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
854 template<
typename _KType,
typename... _Args>
859 auto __code = __h._M_hash_code(__k);
860 std::size_t __bkt = __h._M_bucket_index(__code);
861 if (
auto __node = __h._M_find_node(__bkt, __k, __code))
864 typename __hashtable::_Scoped_node __node {
871 = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
872 __node._M_node =
nullptr;
873 return { __it,
true };
878 { this->insert(__l.begin(), __l.end()); }
880 template<
typename _InputIterator>
882 insert(_InputIterator __first, _InputIterator __last)
885 __node_gen_type __node_gen(__h);
886 return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
890 template<
typename _Key,
typename _Value,
typename _Alloc,
891 typename _ExtractKey,
typename _Equal,
892 typename _Hash,
typename _RangeHash,
typename _Unused,
893 typename _RehashPolicy,
typename _Traits>
894 template<
typename _InputIterator,
typename _NodeGetter>
897 _Hash, _RangeHash, _Unused,
898 _RehashPolicy, _Traits>::
899 _M_insert_range(_InputIterator __first, _InputIterator __last,
900 const _NodeGetter& __node_gen,
true_type __uks)
902 __hashtable& __h = _M_conjure_hashtable();
903 for (; __first != __last; ++__first)
904 __h._M_insert(*__first, __node_gen, __uks);
907 template<
typename _Key,
typename _Value,
typename _Alloc,
908 typename _ExtractKey,
typename _Equal,
909 typename _Hash,
typename _RangeHash,
typename _Unused,
910 typename _RehashPolicy,
typename _Traits>
911 template<
typename _InputIterator,
typename _NodeGetter>
913 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
914 _Hash, _RangeHash, _Unused,
915 _RehashPolicy, _Traits>::
916 _M_insert_range(_InputIterator __first, _InputIterator __last,
917 const _NodeGetter& __node_gen,
false_type __uks)
919 using __rehash_type =
typename __hashtable::__rehash_type;
920 using __rehash_state =
typename __hashtable::__rehash_state;
923 size_type __n_elt = __detail::__distance_fw(__first, __last);
927 __hashtable& __h = _M_conjure_hashtable();
928 __rehash_type& __rehash = __h._M_rehash_policy;
929 const __rehash_state& __saved_state = __rehash._M_state();
930 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
931 __h._M_element_count,
934 if (__do_rehash.first)
935 __h._M_rehash(__do_rehash.second, __saved_state);
937 for (; __first != __last; ++__first)
938 __h._M_insert(*__first, __node_gen, __uks);
947 template<
typename _Key,
typename _Value,
typename _Alloc,
948 typename _ExtractKey,
typename _Equal,
949 typename _Hash,
typename _RangeHash,
typename _Unused,
950 typename _RehashPolicy,
typename _Traits,
951 bool _Constant_iterators = _Traits::__constant_iterators::value>
955 template<
typename _Key,
typename _Value,
typename _Alloc,
956 typename _ExtractKey,
typename _Equal,
957 typename _Hash,
typename _RangeHash,
typename _Unused,
958 typename _RehashPolicy,
typename _Traits>
959 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
960 _Hash, _RangeHash, _Unused,
961 _RehashPolicy, _Traits, true>
962 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
963 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
966 _Equal, _Hash, _RangeHash, _Unused,
967 _RehashPolicy, _Traits>;
969 using value_type =
typename __base_type::value_type;
972 using __ireturn_type =
typename __base_type::__ireturn_type;
974 using __unique_keys =
typename __base_type::__unique_keys;
976 using __node_gen_type =
typename __base_type::__node_gen_type;
978 using __base_type::insert;
981 insert(value_type&& __v)
984 __node_gen_type __node_gen(__h);
985 return __h._M_insert(
std::move(__v), __node_gen, __unique_keys{});
989 insert(const_iterator __hint, value_type&& __v)
992 __node_gen_type __node_gen(__h);
993 return __h._M_insert(__hint,
std::move(__v), __node_gen,
999 template<
typename _Key,
typename _Value,
typename _Alloc,
1000 typename _ExtractKey,
typename _Equal,
1001 typename _Hash,
typename _RangeHash,
typename _Unused,
1002 typename _RehashPolicy,
typename _Traits>
1003 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1004 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1005 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1006 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
1009 _Equal, _Hash, _RangeHash, _Unused,
1010 _RehashPolicy, _Traits>;
1011 using value_type =
typename __base_type::value_type;
1015 using __unique_keys =
typename __base_type::__unique_keys;
1017 using __ireturn_type =
typename __base_type::__ireturn_type;
1019 using __base_type::insert;
1021 template<
typename _Pair>
1024 template<
typename _Pair>
1027 template<
typename _Pair>
1030 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1035 return __h._M_emplace(__unique_keys{}, std::forward<_Pair>(__v));
1038 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1043 return __h._M_emplace(__hint, __unique_keys{},
1044 std::forward<_Pair>(__v));
1048 template<
typename _Policy>
1049 using __has_load_factor =
typename _Policy::__has_load_factor;
1057 template<
typename _Key,
typename _Value,
typename _Alloc,
1058 typename _ExtractKey,
typename _Equal,
1059 typename _Hash,
typename _RangeHash,
typename _Unused,
1060 typename _RehashPolicy,
typename _Traits,
1062 __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1066 template<
typename _Key,
typename _Value,
typename _Alloc,
1067 typename _ExtractKey,
typename _Equal,
1068 typename _Hash,
typename _RangeHash,
typename _Unused,
1069 typename _RehashPolicy,
typename _Traits>
1071 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
1077 template<
typename _Key,
typename _Value,
typename _Alloc,
1078 typename _ExtractKey,
typename _Equal,
1079 typename _Hash,
typename _RangeHash,
typename _Unused,
1080 typename _RehashPolicy,
typename _Traits>
1082 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
1086 _Equal, _Hash, _RangeHash, _Unused,
1087 _RehashPolicy, _Traits>;
1090 max_load_factor()
const noexcept
1093 return __this->__rehash_policy().max_load_factor();
1097 max_load_factor(
float __z)
1100 __this->__rehash_policy(_RehashPolicy(__z));
1104 reserve(std::size_t __n)
1107 __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1117 template<
int _Nm,
typename _Tp,
1118 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1122 template<
int _Nm,
typename _Tp>
1128 template<
typename _OtherTp>
1130 : _Tp(std::forward<_OtherTp>(__tp))
1133 const _Tp& _M_cget()
const {
return static_cast<const _Tp&
>(*this); }
1134 _Tp& _M_get() {
return static_cast<_Tp&
>(*this); }
1138 template<
int _Nm,
typename _Tp>
1143 template<
typename _OtherTp>
1145 : _M_tp(std::forward<_OtherTp>(__tp))
1148 const _Tp& _M_cget()
const {
return _M_tp; }
1149 _Tp& _M_get() {
return _M_tp; }
1161 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1162 typename _Hash,
typename _RangeHash,
typename _Unused,
1163 bool __cache_hash_code>
1184 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1185 typename _Hash,
typename _RangeHash,
typename _Unused,
1186 bool __cache_hash_code>
1195 _Hash, _RangeHash, _Unused, false>;
1198 typedef _Hash hasher;
1201 hash_function()
const
1202 {
return _M_hash(); }
1205 typedef std::size_t __hash_code;
1213 _M_hash_code(
const _Key& __k)
const
1215 static_assert(__is_invocable<const _Hash&, const _Key&>{},
1216 "hash function must be invocable with an argument of key type");
1217 return _M_hash()(__k);
1221 _M_bucket_index(__hash_code __c, std::size_t __bkt_count)
const
1222 {
return _RangeHash{}(__c, __bkt_count); }
1225 _M_bucket_index(
const _Hash_node_value<_Value, false>& __n,
1226 std::size_t __bkt_count)
const
1227 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
1228 && noexcept(declval<const _RangeHash&>()((__hash_code)0,
1231 return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
1236 _M_bucket_index(
const _Hash_node_value<_Value, true>& __n,
1237 std::size_t __bkt_count)
const
1238 noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0,
1240 {
return _RangeHash{}(__n._M_hash_code, __bkt_count); }
1253 { __n._M_hash_code = __c; }
1258 { __to._M_hash_code = __from._M_hash_code; }
1262 {
std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); }
1265 _M_hash()
const {
return __ebo_hash::_M_cget(); }
1269 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1270 typename _Hash,
typename _RangeHash,
typename _Unused>
1272 _Hash, _RangeHash, _Unused, true>
1278 _Hash, _RangeHash, _Unused,
true>;
1283 std::size_t __bkt, std::size_t __bkt_count)
1290 __base_node_iter::_M_incr();
1294 = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
1295 if (__bkt != _M_bucket)
1296 this->_M_cur =
nullptr;
1300 std::size_t _M_bucket;
1301 std::size_t _M_bucket_count;
1305 _M_get_bucket()
const {
return _M_bucket; }
1312 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1313 struct _Hash_code_storage
1315 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1318 _M_h() {
return _M_storage._M_ptr(); }
1321 _M_h()
const {
return _M_storage._M_ptr(); }
1325 template<
typename _Tp>
1326 struct _Hash_code_storage<_Tp, true>
1333 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1336 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1339 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1340 typename _Hash,
typename _RangeHash,
typename _Unused>
1341 using __hash_code_for_local_iter
1342 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1343 _Hash, _RangeHash, _Unused,
false>>;
1346 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1347 typename _Hash,
typename _RangeHash,
typename _Unused>
1348 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1349 _Hash, _RangeHash, _Unused, false>
1350 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1352 , _Node_iterator_base<_Value, false>
1355 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1356 _Hash, _RangeHash, _Unused,
false>;
1357 using __node_iter_base = _Node_iterator_base<_Value, false>;
1359 _Local_iterator_base() : _M_bucket_count(-1) { }
1361 _Local_iterator_base(
const __hash_code_base&
__base,
1362 _Hash_node<_Value, false>* __p,
1363 std::size_t __bkt, std::size_t __bkt_count)
1364 : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1367 ~_Local_iterator_base()
1369 if (_M_bucket_count !=
size_t(-1))
1373 _Local_iterator_base(
const _Local_iterator_base& __iter)
1374 : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
1375 , _M_bucket_count(__iter._M_bucket_count)
1377 if (_M_bucket_count !=
size_t(-1))
1378 _M_init(*__iter._M_h());
1381 _Local_iterator_base&
1382 operator=(
const _Local_iterator_base& __iter)
1384 if (_M_bucket_count != -1)
1386 this->_M_cur = __iter._M_cur;
1387 _M_bucket = __iter._M_bucket;
1388 _M_bucket_count = __iter._M_bucket_count;
1389 if (_M_bucket_count != -1)
1390 _M_init(*__iter._M_h());
1397 __node_iter_base::_M_incr();
1400 std::size_t __bkt = this->_M_h()->_M_bucket_index(*this->_M_cur,
1402 if (__bkt != _M_bucket)
1403 this->_M_cur =
nullptr;
1407 std::size_t _M_bucket;
1408 std::size_t _M_bucket_count;
1411 _M_init(
const __hash_code_base&
__base)
1412 { ::new(this->_M_h()) __hash_code_base(
__base); }
1415 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1419 _M_get_bucket()
const {
return _M_bucket; }
1423 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1424 typename _Hash,
typename _RangeHash,
typename _Unused,
1425 bool __constant_iterators,
bool __cache>
1428 _Hash, _RangeHash, _Unused, __cache>
1432 _Hash, _RangeHash, _Unused, __cache>;
1433 using __hash_code_base =
typename __base_type::__hash_code_base;
1436 typedef _Value value_type;
1438 const value_type*, value_type*>::type
1441 const value_type&, value_type&>::type
1443 typedef std::ptrdiff_t difference_type;
1450 std::size_t __bkt, std::size_t __bkt_count)
1456 {
return this->_M_cur->_M_v(); }
1460 {
return this->_M_cur->_M_valptr(); }
1479 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1480 typename _Hash,
typename _RangeHash,
typename _Unused,
1481 bool __constant_iterators,
bool __cache>
1484 _Hash, _RangeHash, _Unused, __cache>
1488 _Hash, _RangeHash, _Unused, __cache>;
1489 using __hash_code_base =
typename __base_type::__hash_code_base;
1492 typedef _Value value_type;
1493 typedef const value_type* pointer;
1494 typedef const value_type& reference;
1495 typedef std::ptrdiff_t difference_type;
1502 std::size_t __bkt, std::size_t __bkt_count)
1507 _Hash, _RangeHash, _Unused,
1508 __constant_iterators,
1515 {
return this->_M_cur->_M_v(); }
1519 {
return this->_M_cur->_M_valptr(); }
1547 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1548 typename _Equal,
typename _Hash,
typename _RangeHash,
1549 typename _Unused,
typename _Traits>
1551 :
public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1552 _Unused, _Traits::__hash_cached::value>,
1556 typedef _Key key_type;
1557 typedef _Value value_type;
1558 typedef _Equal key_equal;
1559 typedef std::size_t size_type;
1560 typedef std::ptrdiff_t difference_type;
1562 using __traits_type = _Traits;
1563 using __hash_cached =
typename __traits_type::__hash_cached;
1566 _Hash, _RangeHash, _Unused,
1567 __hash_cached::value>;
1569 using __hash_code =
typename __hash_code_base::__hash_code;
1585 {
return __c == __n._M_hash_code; }
1590 {
return __lhn._M_hash_code == __rhn._M_hash_code; }
1599 _M_equals(
const _Key& __k, __hash_code __c,
1600 const _Hash_node_value<_Value, __hash_cached::value>& __n)
const
1602 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1603 "key equality predicate must be invocable with two arguments of "
1605 return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1610 const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
1611 const _Hash_node_value<_Value, __hash_cached::value>& __rhn)
const
1613 return _S_node_equals(__lhn, __rhn)
1614 && _M_eq()(_ExtractKey{}(__lhn._M_v()), _ExtractKey{}(__rhn._M_v()));
1620 __hash_code_base::_M_swap(__x);
1621 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1625 _M_eq()
const {
return _EqualEBO::_M_cget(); }
1636 template<
typename _Key,
typename _Value,
typename _Alloc,
1637 typename _ExtractKey,
typename _Equal,
1638 typename _Hash,
typename _RangeHash,
typename _Unused,
1639 typename _RehashPolicy,
typename _Traits,
1640 bool _Unique_keys = _Traits::__unique_keys::value>
1644 template<
typename _Key,
typename _Value,
typename _Alloc,
1645 typename _ExtractKey,
typename _Equal,
1646 typename _Hash,
typename _RangeHash,
typename _Unused,
1647 typename _RehashPolicy,
typename _Traits>
1649 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
1652 _Hash, _RangeHash, _Unused,
1653 _RehashPolicy, _Traits>;
1659 template<
typename _Key,
typename _Value,
typename _Alloc,
1660 typename _ExtractKey,
typename _Equal,
1661 typename _Hash,
typename _RangeHash,
typename _Unused,
1662 typename _RehashPolicy,
typename _Traits>
1664 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1665 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
1666 _M_equal(
const __hashtable& __other)
const
1668 using __node_type =
typename __hashtable::__node_type;
1669 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1670 if (__this->size() != __other.size())
1673 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1675 std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1676 auto __prev_n = __other._M_buckets[__ybkt];
1680 for (__node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);;
1681 __n = __n->_M_next())
1683 if (__n->_M_v() == *__itx)
1687 || __other._M_bucket_index(*__n->_M_next()) != __ybkt)
1696 template<
typename _Key,
typename _Value,
typename _Alloc,
1697 typename _ExtractKey,
typename _Equal,
1698 typename _Hash,
typename _RangeHash,
typename _Unused,
1699 typename _RehashPolicy,
typename _Traits>
1701 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1704 _Hash, _RangeHash, _Unused,
1705 _RehashPolicy, _Traits>;
1711 template<
typename _Key,
typename _Value,
typename _Alloc,
1712 typename _ExtractKey,
typename _Equal,
1713 typename _Hash,
typename _RangeHash,
typename _Unused,
1714 typename _RehashPolicy,
typename _Traits>
1716 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1717 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
false>::
1718 _M_equal(
const __hashtable& __other)
const
1720 using __node_type =
typename __hashtable::__node_type;
1721 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1722 if (__this->size() != __other.size())
1725 for (
auto __itx = __this->begin(); __itx != __this->end();)
1727 std::size_t __x_count = 1;
1728 auto __itx_end = __itx;
1729 for (++__itx_end; __itx_end != __this->end()
1730 && __this->key_eq()(_ExtractKey{}(*__itx),
1731 _ExtractKey{}(*__itx_end));
1735 std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1736 auto __y_prev_n = __other._M_buckets[__ybkt];
1740 __node_type* __y_n =
static_cast<__node_type*
>(__y_prev_n->_M_nxt);
1743 if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()),
1744 _ExtractKey{}(*__itx)))
1747 auto __y_ref_n = __y_n;
1748 for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next())
1749 if (!__other._M_node_equals(*__y_ref_n, *__y_n))
1752 if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt)
1756 typename __hashtable::const_iterator __ity(__y_n);
1757 for (
auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
1758 if (--__x_count == 0)
1764 if (!std::is_permutation(__itx, __itx_end, __ity))
1776 template<
typename _NodeAlloc>
1782 using __node_type =
typename _NodeAlloc::value_type;
1783 using __node_alloc_type = _NodeAlloc;
1787 using __value_alloc_traits =
typename __node_alloc_traits::template
1788 rebind_traits<typename __node_type::value_type>;
1790 using __node_ptr = __node_type*;
1793 using __buckets_alloc_type =
1794 __alloc_rebind<__node_alloc_type, __node_base_ptr>;
1802 template<
typename _Alloc>
1809 {
return __ebo_node_alloc::_M_get(); }
1811 const __node_alloc_type&
1812 _M_node_allocator()
const
1813 {
return __ebo_node_alloc::_M_cget(); }
1816 template<
typename... _Args>
1818 _M_allocate_node(_Args&&... __args);
1822 _M_deallocate_node(__node_ptr __n);
1826 _M_deallocate_node_ptr(__node_ptr __n);
1831 _M_deallocate_nodes(__node_ptr __n);
1834 _M_allocate_buckets(std::size_t __bkt_count);
1837 _M_deallocate_buckets(
__buckets_ptr, std::size_t __bkt_count);
1842 template<
typename _NodeAlloc>
1843 template<
typename... _Args>
1848 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
1849 __node_ptr __n = std::__to_address(__nptr);
1852 ::new ((
void*)__n) __node_type;
1853 __node_alloc_traits::construct(_M_node_allocator(),
1855 std::forward<_Args>(__args)...);
1860 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
1861 __throw_exception_again;
1865 template<
typename _NodeAlloc>
1867 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n)
1869 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
1870 _M_deallocate_node_ptr(__n);
1873 template<
typename _NodeAlloc>
1875 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
1877 typedef typename __node_alloc_traits::pointer _Ptr;
1879 __n->~__node_type();
1880 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
1883 template<
typename _NodeAlloc>
1885 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n)
1889 __node_ptr __tmp = __n;
1890 __n = __n->_M_next();
1891 _M_deallocate_node(__tmp);
1895 template<
typename _NodeAlloc>
1897 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
1900 __buckets_alloc_type __alloc(_M_node_allocator());
1902 auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count);
1903 __buckets_ptr __p = std::__to_address(__ptr);
1904 __builtin_memset(__p, 0, __bkt_count *
sizeof(__node_base_ptr));
1908 template<
typename _NodeAlloc>
1910 _Hashtable_alloc<_NodeAlloc>::
1911 _M_deallocate_buckets(__buckets_ptr __bkts,
1912 std::size_t __bkt_count)
1914 typedef typename __buckets_alloc_traits::pointer _Ptr;
1916 __buckets_alloc_type __alloc(_M_node_allocator());
1917 __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
1922 _GLIBCXX_END_NAMESPACE_VERSION
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
element_type * operator->() const
Smart pointer dereferencing.
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2 not less than __n.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
constexpr _Iterator __base(_Iterator __it)
Primary class template, tuple.
Define a member typedef type to one of two argument types.
Define a member typedef type only if a boolean constant is true.
Uniform interface to all allocator types.
Traits class for iterators.
Base class for node iterators.
Node iterators, used to iterate through all the hashtable.
Node const_iterators, used to iterate through all the hashtable.
Default range hashing function: use division to fold a large number into the range [0,...
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Range hashing function assuming that second arg is a power of 2.
Rehash policy providing power of 2 bucket numbers. Avoids modulo operations.
Uniform interface to all pointer-like types.
Forward iterators support a superset of input iterator operations.
Struct holding two objects of arbitrary type.
Uniform interface to C++98 and C++11 allocators.