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>
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,
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>
102 template<
typename _NodeAlloc>
103 struct _ReuseOrAllocNode
106 using __node_alloc_type = _NodeAlloc;
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{});
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);
1220 template<
typename _Kt>
1222 _M_hash_code_tr(
const _Kt& __k)
const 1224 static_assert(__is_invocable<const _Hash&, const _Kt&>{},
1225 "hash function must be invocable with an argument of key type");
1226 return _M_hash()(__k);
1230 _M_bucket_index(__hash_code __c, std::size_t __bkt_count)
const 1231 {
return _RangeHash{}(__c, __bkt_count); }
1234 _M_bucket_index(
const _Hash_node_value<_Value, false>& __n,
1235 std::size_t __bkt_count)
const 1236 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>()))
1237 && noexcept(declval<const _RangeHash&>()((__hash_code)0,
1240 return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
1245 _M_bucket_index(
const _Hash_node_value<_Value, true>& __n,
1246 std::size_t __bkt_count)
const 1247 noexcept( noexcept(declval<const _RangeHash&>()((__hash_code)0,
1249 {
return _RangeHash{}(__n._M_hash_code, __bkt_count); }
1262 { __n._M_hash_code = __c; }
1267 { __to._M_hash_code = __from._M_hash_code; }
1271 { std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); }
1274 _M_hash()
const {
return __ebo_hash::_M_cget(); }
1278 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1279 typename _Hash,
typename _RangeHash,
typename _Unused>
1281 _Hash, _RangeHash, _Unused, true>
1287 _Hash, _RangeHash, _Unused,
true>;
1292 std::size_t __bkt, std::size_t __bkt_count)
1299 __base_node_iter::_M_incr();
1303 = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
1304 if (__bkt != _M_bucket)
1305 this->_M_cur =
nullptr;
1309 std::size_t _M_bucket;
1310 std::size_t _M_bucket_count;
1314 _M_get_bucket()
const {
return _M_bucket; }
1321 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1322 struct _Hash_code_storage
1324 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1327 _M_h() {
return _M_storage._M_ptr(); }
1330 _M_h()
const {
return _M_storage._M_ptr(); }
1334 template<
typename _Tp>
1335 struct _Hash_code_storage<_Tp, true>
1342 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1345 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1348 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1349 typename _Hash,
typename _RangeHash,
typename _Unused>
1350 using __hash_code_for_local_iter
1351 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1352 _Hash, _RangeHash, _Unused,
false>>;
1355 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1356 typename _Hash,
typename _RangeHash,
typename _Unused>
1357 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1358 _Hash, _RangeHash, _Unused, false>
1359 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1361 , _Node_iterator_base<_Value, false>
1364 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1365 _Hash, _RangeHash, _Unused,
false>;
1366 using __node_iter_base = _Node_iterator_base<_Value, false>;
1368 _Local_iterator_base() : _M_bucket_count(-1) { }
1370 _Local_iterator_base(
const __hash_code_base&
__base,
1371 _Hash_node<_Value, false>* __p,
1372 std::size_t __bkt, std::size_t __bkt_count)
1373 : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1376 ~_Local_iterator_base()
1378 if (_M_bucket_count !=
size_t(-1))
1382 _Local_iterator_base(
const _Local_iterator_base& __iter)
1383 : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
1384 , _M_bucket_count(__iter._M_bucket_count)
1386 if (_M_bucket_count !=
size_t(-1))
1387 _M_init(*__iter._M_h());
1390 _Local_iterator_base&
1391 operator=(
const _Local_iterator_base& __iter)
1393 if (_M_bucket_count != -1)
1395 this->_M_cur = __iter._M_cur;
1396 _M_bucket = __iter._M_bucket;
1397 _M_bucket_count = __iter._M_bucket_count;
1398 if (_M_bucket_count != -1)
1399 _M_init(*__iter._M_h());
1406 __node_iter_base::_M_incr();
1409 std::size_t __bkt = this->_M_h()->_M_bucket_index(*this->_M_cur,
1411 if (__bkt != _M_bucket)
1412 this->_M_cur =
nullptr;
1416 std::size_t _M_bucket;
1417 std::size_t _M_bucket_count;
1420 _M_init(
const __hash_code_base&
__base)
1421 { ::new(this->_M_h()) __hash_code_base(
__base); }
1424 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1428 _M_get_bucket()
const {
return _M_bucket; }
1432 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1433 typename _Hash,
typename _RangeHash,
typename _Unused,
1434 bool __constant_iterators,
bool __cache>
1437 _Hash, _RangeHash, _Unused, __cache>
1441 _Hash, _RangeHash, _Unused, __cache>;
1442 using __hash_code_base =
typename __base_type::__hash_code_base;
1445 typedef _Value value_type;
1447 const value_type*, value_type*>::type
1450 const value_type&, value_type&>::type
1452 typedef std::ptrdiff_t difference_type;
1459 std::size_t __bkt, std::size_t __bkt_count)
1465 {
return this->_M_cur->_M_v(); }
1469 {
return this->_M_cur->_M_valptr(); }
1488 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1489 typename _Hash,
typename _RangeHash,
typename _Unused,
1490 bool __constant_iterators,
bool __cache>
1493 _Hash, _RangeHash, _Unused, __cache>
1497 _Hash, _RangeHash, _Unused, __cache>;
1498 using __hash_code_base =
typename __base_type::__hash_code_base;
1501 typedef _Value value_type;
1502 typedef const value_type* pointer;
1503 typedef const value_type& reference;
1504 typedef std::ptrdiff_t difference_type;
1511 std::size_t __bkt, std::size_t __bkt_count)
1516 _Hash, _RangeHash, _Unused,
1517 __constant_iterators,
1524 {
return this->_M_cur->_M_v(); }
1528 {
return this->_M_cur->_M_valptr(); }
1556 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1557 typename _Equal,
typename _Hash,
typename _RangeHash,
1558 typename _Unused,
typename _Traits>
1560 :
public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1561 _Unused, _Traits::__hash_cached::value>,
1565 typedef _Key key_type;
1566 typedef _Value value_type;
1567 typedef _Equal key_equal;
1568 typedef std::size_t size_type;
1569 typedef std::ptrdiff_t difference_type;
1571 using __traits_type = _Traits;
1572 using __hash_cached =
typename __traits_type::__hash_cached;
1575 _Hash, _RangeHash, _Unused,
1576 __hash_cached::value>;
1578 using __hash_code =
typename __hash_code_base::__hash_code;
1588 _S_node_equals(
const _Hash_node_code_cache<false>&,
1589 const _Hash_node_code_cache<false>&)
1593 _S_equals(__hash_code __c,
const _Hash_node_code_cache<true>& __n)
1594 {
return __c == __n._M_hash_code; }
1597 _S_node_equals(
const _Hash_node_code_cache<true>& __lhn,
1598 const _Hash_node_code_cache<true>& __rhn)
1599 {
return __lhn._M_hash_code == __rhn._M_hash_code; }
1602 _Hashtable_base() =
default;
1603 _Hashtable_base(
const _Hash& __hash,
const _Equal& __eq)
1604 : __hash_code_base(__hash), _EqualEBO(__eq)
1608 _M_equals(
const _Key& __k, __hash_code __c,
1609 const _Hash_node_value<_Value, __hash_cached::value>& __n)
const 1611 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1612 "key equality predicate must be invocable with two arguments of " 1614 return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1617 template<
typename _Kt>
1619 _M_equals_tr(
const _Kt& __k, __hash_code __c,
1620 const _Hash_node_value<_Value,
1621 __hash_cached::value>& __n)
const 1624 __is_invocable<const _Equal&, const _Kt&, const _Key&>{},
1625 "key equality predicate must be invocable with two arguments of " 1627 return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1632 const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
1633 const _Hash_node_value<_Value, __hash_cached::value>& __rhn)
const 1635 return _S_node_equals(__lhn, __rhn)
1636 && _M_eq()(_ExtractKey{}(__lhn._M_v()), _ExtractKey{}(__rhn._M_v()));
1640 _M_swap(_Hashtable_base& __x)
1642 __hash_code_base::_M_swap(__x);
1643 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1647 _M_eq()
const {
return _EqualEBO::_M_cget(); }
1658 template<
typename _Key,
typename _Value,
typename _Alloc,
1659 typename _ExtractKey,
typename _Equal,
1660 typename _Hash,
typename _RangeHash,
typename _Unused,
1661 typename _RehashPolicy,
typename _Traits,
1662 bool _Unique_keys = _Traits::__unique_keys::value>
1666 template<
typename _Key,
typename _Value,
typename _Alloc,
1667 typename _ExtractKey,
typename _Equal,
1668 typename _Hash,
typename _RangeHash,
typename _Unused,
1669 typename _RehashPolicy,
typename _Traits>
1671 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
1674 _Hash, _RangeHash, _Unused,
1675 _RehashPolicy, _Traits>;
1681 template<
typename _Key,
typename _Value,
typename _Alloc,
1682 typename _ExtractKey,
typename _Equal,
1683 typename _Hash,
typename _RangeHash,
typename _Unused,
1684 typename _RehashPolicy,
typename _Traits>
1686 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1687 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
1688 _M_equal(
const __hashtable& __other)
const 1690 using __node_type =
typename __hashtable::__node_type;
1691 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1692 if (__this->size() != __other.size())
1695 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1697 std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1698 auto __prev_n = __other._M_buckets[__ybkt];
1702 for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
1703 __n = __n->_M_next())
1705 if (__n->_M_v() == *__itx)
1709 || __other._M_bucket_index(*__n->_M_next()) != __ybkt)
1718 template<
typename _Key,
typename _Value,
typename _Alloc,
1719 typename _ExtractKey,
typename _Equal,
1720 typename _Hash,
typename _RangeHash,
typename _Unused,
1721 typename _RehashPolicy,
typename _Traits>
1723 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1726 _Hash, _RangeHash, _Unused,
1727 _RehashPolicy, _Traits>;
1733 template<
typename _Key,
typename _Value,
typename _Alloc,
1734 typename _ExtractKey,
typename _Equal,
1735 typename _Hash,
typename _RangeHash,
typename _Unused,
1736 typename _RehashPolicy,
typename _Traits>
1738 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1739 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
false>::
1740 _M_equal(
const __hashtable& __other)
const 1742 using __node_type =
typename __hashtable::__node_type;
1743 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1744 if (__this->size() != __other.size())
1747 for (
auto __itx = __this->begin(); __itx != __this->end();)
1749 std::size_t __x_count = 1;
1750 auto __itx_end = __itx;
1751 for (++__itx_end; __itx_end != __this->end()
1752 && __this->key_eq()(_ExtractKey{}(*__itx),
1753 _ExtractKey{}(*__itx_end));
1757 std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1758 auto __y_prev_n = __other._M_buckets[__ybkt];
1762 __node_type* __y_n =
static_cast<__node_type*
>(__y_prev_n->_M_nxt);
1765 if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()),
1766 _ExtractKey{}(*__itx)))
1769 auto __y_ref_n = __y_n;
1770 for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next())
1771 if (!__other._M_node_equals(*__y_ref_n, *__y_n))
1774 if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt)
1778 typename __hashtable::const_iterator __ity(__y_n);
1779 for (
auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
1780 if (--__x_count == 0)
1786 if (!std::is_permutation(__itx, __itx_end, __ity))
1798 template<
typename _NodeAlloc>
1799 struct _Hashtable_alloc :
private _Hashtable_ebo_helper<0, _NodeAlloc>
1802 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
1804 using __node_type =
typename _NodeAlloc::value_type;
1805 using __node_alloc_type = _NodeAlloc;
1809 using __value_alloc_traits =
typename __node_alloc_traits::template
1810 rebind_traits<typename __node_type::value_type>;
1812 using __node_ptr = __node_type*;
1813 using __node_base = _Hash_node_base;
1814 using __node_base_ptr = __node_base*;
1815 using __buckets_alloc_type =
1816 __alloc_rebind<__node_alloc_type, __node_base_ptr>;
1818 using __buckets_ptr = __node_base_ptr*;
1820 _Hashtable_alloc() =
default;
1821 _Hashtable_alloc(
const _Hashtable_alloc&) =
default;
1822 _Hashtable_alloc(_Hashtable_alloc&&) =
default;
1824 template<
typename _Alloc>
1825 _Hashtable_alloc(_Alloc&& __a)
1826 : __ebo_node_alloc(
std::
forward<_Alloc>(__a))
1831 {
return __ebo_node_alloc::_M_get(); }
1833 const __node_alloc_type&
1834 _M_node_allocator()
const 1835 {
return __ebo_node_alloc::_M_cget(); }
1838 template<
typename... _Args>
1840 _M_allocate_node(_Args&&... __args);
1844 _M_deallocate_node(__node_ptr __n);
1848 _M_deallocate_node_ptr(__node_ptr __n);
1853 _M_deallocate_nodes(__node_ptr __n);
1856 _M_allocate_buckets(std::size_t __bkt_count);
1859 _M_deallocate_buckets(__buckets_ptr, std::size_t __bkt_count);
1864 template<
typename _NodeAlloc>
1865 template<
typename... _Args>
1867 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
1870 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
1871 __node_ptr __n = std::__to_address(__nptr);
1874 ::new ((
void*)__n) __node_type;
1875 __node_alloc_traits::construct(_M_node_allocator(),
1877 std::forward<_Args>(__args)...);
1882 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
1883 __throw_exception_again;
1887 template<
typename _NodeAlloc>
1889 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n)
1891 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
1892 _M_deallocate_node_ptr(__n);
1895 template<
typename _NodeAlloc>
1897 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
1899 typedef typename __node_alloc_traits::pointer _Ptr;
1901 __n->~__node_type();
1902 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
1905 template<
typename _NodeAlloc>
1907 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n)
1911 __node_ptr __tmp = __n;
1912 __n = __n->_M_next();
1913 _M_deallocate_node(__tmp);
1917 template<
typename _NodeAlloc>
1919 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
1922 __buckets_alloc_type __alloc(_M_node_allocator());
1924 auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count);
1925 __buckets_ptr __p = std::__to_address(__ptr);
1926 __builtin_memset(__p, 0, __bkt_count *
sizeof(__node_base_ptr));
1930 template<
typename _NodeAlloc>
1932 _Hashtable_alloc<_NodeAlloc>::
1933 _M_deallocate_buckets(__buckets_ptr __bkts,
1934 std::size_t __bkt_count)
1936 typedef typename __buckets_alloc_traits::pointer _Ptr;
1938 __buckets_alloc_type __alloc(_M_node_allocator());
1939 __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
1944 _GLIBCXX_END_NAMESPACE_VERSION
1947 #endif // _HASHTABLE_POLICY_H
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
Traits class for iterators.
Node iterators, used to iterate through all the hashtable.
Uniform interface to all pointer-like types.
Define a member typedef type only if a boolean constant is true.
Range hashing function assuming that second arg is a power of 2.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Default range hashing function: use division to fold a large number into the range [0...
Base class for node iterators.
Struct holding two objects of arbitrary type.
Forward iterators support a superset of input iterator operations.
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
Define a member typedef type to one of two argument types.
Uniform interface to all allocator types.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Node const_iterators, used to iterate through all the hashtable.
element_type * operator->() const
Smart pointer dereferencing.
std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2 not less than __n.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
constexpr _Iterator __base(_Iterator __it)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
ISO C++ entities toplevel namespace is std.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
Uniform interface to C++98 and C++11 allocators.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Primary class template, tuple.
Rehash policy providing power of 2 bucket numbers. Avoids modulo operations.