31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
39 namespace std _GLIBCXX_VISIBILITY(default)
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
43 template<
typename _Key,
typename _Value,
typename _Alloc,
44 typename _ExtractKey,
typename _Equal,
45 typename _H1,
typename _H2,
typename _Hash,
46 typename _RehashPolicy,
typename _Traits>
56 template<
typename _Key,
typename _Value,
57 typename _ExtractKey,
typename _Equal,
58 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
63 template<
class _Iterator>
65 __distance_fw(_Iterator __first, _Iterator __last,
67 {
return __first != __last ? 1 : 0; }
69 template<
class _Iterator>
71 __distance_fw(_Iterator __first, _Iterator __last,
75 template<
class _Iterator>
77 __distance_fw(_Iterator __first, _Iterator __last)
78 {
return __distance_fw(__first, __last,
83 template<
typename _Tp>
85 operator()(_Tp&& __x)
const
86 {
return std::forward<_Tp>(__x); }
91 template<
typename _Tp>
93 operator()(_Tp&& __x)
const
94 -> decltype(std::get<0>(std::forward<_Tp>(__x)))
95 {
return std::get<0>(std::forward<_Tp>(__x)); }
98 template<
typename _NodeAlloc>
103 template<
typename _NodeAlloc>
104 struct _ReuseOrAllocNode
107 using __node_alloc_type = _NodeAlloc;
110 typename __hashtable_alloc::__node_alloc_traits;
111 using __node_type =
typename __hashtable_alloc::__node_type;
114 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
115 : _M_nodes(__nodes), _M_h(__h) { }
116 _ReuseOrAllocNode(
const _ReuseOrAllocNode&) =
delete;
119 { _M_h._M_deallocate_nodes(_M_nodes); }
121 template<
typename _Arg>
123 operator()(_Arg&& __arg)
const
127 __node_type* __node = _M_nodes;
128 _M_nodes = _M_nodes->_M_next();
129 __node->_M_nxt =
nullptr;
130 auto& __a = _M_h._M_node_allocator();
131 __node_alloc_traits::destroy(__a, __node->_M_valptr());
134 __node_alloc_traits::construct(__a, __node->_M_valptr(),
135 std::forward<_Arg>(__arg));
139 _M_h._M_deallocate_node_ptr(__node);
140 __throw_exception_again;
144 return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
148 mutable __node_type* _M_nodes;
149 __hashtable_alloc& _M_h;
154 template<
typename _NodeAlloc>
158 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
159 using __node_type =
typename __hashtable_alloc::__node_type;
162 _AllocNode(__hashtable_alloc& __h)
165 template<
typename _Arg>
167 operator()(_Arg&& __arg)
const
168 {
return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
171 __hashtable_alloc& _M_h;
199 template<
bool _Cache_hash_code,
bool _Constant_iterators,
bool _Unique_keys>
229 template<
typename _Value>
232 typedef _Value value_type;
234 __gnu_cxx::__aligned_buffer<_Value> _M_storage;
238 {
return _M_storage._M_ptr(); }
241 _M_valptr()
const noexcept
242 {
return _M_storage._M_ptr(); }
246 {
return *_M_valptr(); }
249 _M_v()
const noexcept
250 {
return *_M_valptr(); }
256 template<
typename _Value,
bool _Cache_hash_code>
264 template<
typename _Value>
267 std::size_t _M_hash_code;
270 _M_next()
const noexcept
271 {
return static_cast<_Hash_node*>(this->_M_nxt); }
279 template<
typename _Value>
283 _M_next()
const noexcept
284 {
return static_cast<_Hash_node*>(this->_M_nxt); }
288 template<
typename _Value,
bool _Cache_hash_code>
300 { _M_cur = _M_cur->_M_next(); }
303 template<
typename _Value,
bool _Cache_hash_code>
308 {
return __x._M_cur == __y._M_cur; }
310 template<
typename _Value,
bool _Cache_hash_code>
312 operator!=(
const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
313 const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
315 {
return __x._M_cur != __y._M_cur; }
318 template<
typename _Value,
bool __constant_iterators,
bool __cache>
327 typedef _Value value_type;
328 typedef std::ptrdiff_t difference_type;
332 const _Value*, _Value*>::type;
335 const _Value&, _Value&>::type;
345 operator*()
const noexcept
346 {
return this->_M_cur->_M_v(); }
349 operator->()
const noexcept
350 {
return this->_M_cur->_M_valptr(); }
353 operator++() noexcept
360 operator++(
int) noexcept
369 template<
typename _Value,
bool __constant_iterators,
bool __cache>
378 typedef _Value value_type;
379 typedef std::ptrdiff_t difference_type;
382 typedef const _Value* pointer;
383 typedef const _Value& reference;
393 __cache>& __x) noexcept
397 operator*()
const noexcept
398 {
return this->_M_cur->_M_v(); }
401 operator->()
const noexcept
402 {
return this->_M_cur->_M_valptr(); }
405 operator++() noexcept
412 operator++(
int) noexcept
427 typedef std::size_t first_argument_type;
428 typedef std::size_t second_argument_type;
429 typedef std::size_t result_type;
432 operator()(first_argument_type __num,
433 second_argument_type __den)
const noexcept
434 {
return __num % __den; }
451 : _M_max_load_factor(__z), _M_next_resize(0) { }
454 max_load_factor()
const noexcept
455 {
return _M_max_load_factor; }
459 _M_next_bkt(std::size_t __n)
const;
463 _M_bkt_for_elements(std::size_t __n)
const
464 {
return __builtin_ceill(__n / (
long double)_M_max_load_factor); }
471 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
472 std::size_t __n_ins)
const;
474 typedef std::size_t _State;
478 {
return _M_next_resize; }
482 { _M_next_resize = 0; }
485 _M_reset(_State __state)
486 { _M_next_resize = __state; }
488 static const std::size_t _S_growth_factor = 2;
490 float _M_max_load_factor;
491 mutable std::size_t _M_next_resize;
497 typedef std::size_t first_argument_type;
498 typedef std::size_t second_argument_type;
499 typedef std::size_t result_type;
502 operator()(first_argument_type __num,
503 second_argument_type __den)
const noexcept
504 {
return __num & (__den - 1); }
514 const unsigned __lz =
sizeof(size_t) >
sizeof(
long)
515 ? __builtin_clzll(__n - 1ull)
516 : __builtin_clzl(__n - 1ul);
528 : _M_max_load_factor(__z), _M_next_resize(0) { }
531 max_load_factor()
const noexcept
532 {
return _M_max_load_factor; }
537 _M_next_bkt(std::size_t __n) noexcept
545 const auto __max_width = std::min<size_t>(
sizeof(
size_t), 8);
546 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
547 std::size_t __res =
__clp2(__n);
557 if (__res == __max_bkt)
564 = __builtin_floorl(__res * (
long double)_M_max_load_factor);
571 _M_bkt_for_elements(std::size_t __n)
const noexcept
572 {
return __builtin_ceill(__n / (
long double)_M_max_load_factor); }
579 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
580 std::size_t __n_ins) noexcept
582 if (__n_elt + __n_ins > _M_next_resize)
587 long double __min_bkts
588 = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
589 / (
long double)_M_max_load_factor;
590 if (__min_bkts >= __n_bkt)
592 _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1,
593 __n_bkt * _S_growth_factor)) };
596 = __builtin_floorl(__n_bkt * (
long double)_M_max_load_factor);
603 typedef std::size_t _State;
606 _M_state()
const noexcept
607 {
return _M_next_resize; }
611 { _M_next_resize = 0; }
614 _M_reset(_State __state) noexcept
615 { _M_next_resize = __state; }
617 static const std::size_t _S_growth_factor = 2;
619 float _M_max_load_factor;
620 std::size_t _M_next_resize;
641 template<
typename _Key,
typename _Value,
typename _Alloc,
642 typename _ExtractKey,
typename _Equal,
643 typename _H1,
typename _H2,
typename _Hash,
644 typename _RehashPolicy,
typename _Traits,
645 bool _Unique_keys = _Traits::__unique_keys::value>
649 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
650 typename _H1,
typename _H2,
typename _Hash,
651 typename _RehashPolicy,
typename _Traits>
652 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
653 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
659 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
660 typename _H1,
typename _H2,
typename _Hash,
661 typename _RehashPolicy,
typename _Traits>
662 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
663 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
668 _Equal, _H1, _H2, _Hash,
673 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
675 using __hash_code =
typename __hashtable_base::__hash_code;
676 using __node_type =
typename __hashtable_base::__node_type;
679 using key_type =
typename __hashtable_base::key_type;
684 operator[](
const key_type& __k);
687 operator[](key_type&& __k);
692 at(
const key_type& __k);
695 at(
const key_type& __k)
const;
698 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
699 typename _H1,
typename _H2,
typename _Hash,
700 typename _RehashPolicy,
typename _Traits>
702 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
703 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
704 operator[](
const key_type& __k)
707 __hashtable* __h = static_cast<__hashtable*>(
this);
708 __hash_code __code = __h->_M_hash_code(__k);
709 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
710 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
711 return __node->_M_v().second;
713 typename __hashtable::_Scoped_node __node {
720 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
721 __node._M_node =
nullptr;
722 return __pos->second;
725 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
726 typename _H1,
typename _H2,
typename _Hash,
727 typename _RehashPolicy,
typename _Traits>
729 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
730 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
731 operator[](key_type&& __k)
734 __hashtable* __h = static_cast<__hashtable*>(
this);
735 __hash_code __code = __h->_M_hash_code(__k);
736 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
737 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
738 return __node->_M_v().second;
740 typename __hashtable::_Scoped_node __node {
747 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
748 __node._M_node =
nullptr;
749 return __pos->second;
752 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
753 typename _H1,
typename _H2,
typename _Hash,
754 typename _RehashPolicy,
typename _Traits>
756 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
757 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
758 at(
const key_type& __k)
761 __hashtable* __h = static_cast<__hashtable*>(
this);
762 __hash_code __code = __h->_M_hash_code(__k);
763 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
764 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
767 __throw_out_of_range(__N(
"_Map_base::at"));
768 return __p->_M_v().second;
771 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
772 typename _H1,
typename _H2,
typename _Hash,
773 typename _RehashPolicy,
typename _Traits>
775 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
776 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
777 at(
const key_type& __k)
const
778 ->
const mapped_type&
780 const __hashtable* __h = static_cast<const __hashtable*>(
this);
781 __hash_code __code = __h->_M_hash_code(__k);
782 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
783 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
786 __throw_out_of_range(__N(
"_Map_base::at"));
787 return __p->_M_v().second;
795 template<
typename _Key,
typename _Value,
typename _Alloc,
796 typename _ExtractKey,
typename _Equal,
797 typename _H1,
typename _H2,
typename _Hash,
798 typename _RehashPolicy,
typename _Traits>
803 _Equal, _H1, _H2, _Hash,
804 _RehashPolicy, _Traits>;
807 _Equal, _H1, _H2, _Hash,
810 using value_type =
typename __hashtable_base::value_type;
813 using size_type =
typename __hashtable_base::size_type;
815 using __unique_keys =
typename __hashtable_base::__unique_keys;
816 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
818 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
819 using __node_gen_type = _AllocNode<__node_alloc_type>;
822 _M_conjure_hashtable()
823 {
return *(static_cast<__hashtable*>(
this)); }
825 template<
typename _InputIterator,
typename _NodeGetter>
827 _M_insert_range(_InputIterator __first, _InputIterator __last,
830 template<
typename _InputIterator,
typename _NodeGetter>
832 _M_insert_range(_InputIterator __first, _InputIterator __last,
837 insert(
const value_type& __v)
840 __node_gen_type __node_gen(__h);
841 return __h._M_insert(__v, __node_gen, __unique_keys());
845 insert(const_iterator __hint,
const value_type& __v)
848 __node_gen_type __node_gen(__h);
849 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
854 { this->insert(__l.begin(), __l.end()); }
856 template<
typename _InputIterator>
858 insert(_InputIterator __first, _InputIterator __last)
861 __node_gen_type __node_gen(__h);
862 return _M_insert_range(__first, __last, __node_gen, __unique_keys());
866 template<
typename _Key,
typename _Value,
typename _Alloc,
867 typename _ExtractKey,
typename _Equal,
868 typename _H1,
typename _H2,
typename _Hash,
869 typename _RehashPolicy,
typename _Traits>
870 template<
typename _InputIterator,
typename _NodeGetter>
872 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
873 _RehashPolicy, _Traits>::
874 _M_insert_range(_InputIterator __first, _InputIterator __last,
875 const _NodeGetter& __node_gen,
true_type)
877 size_type __n_elt = __detail::__distance_fw(__first, __last);
881 __hashtable& __h = _M_conjure_hashtable();
882 for (; __first != __last; ++__first)
884 if (__h._M_insert(*__first, __node_gen, __unique_keys(),
887 else if (__n_elt != 1)
892 template<
typename _Key,
typename _Value,
typename _Alloc,
893 typename _ExtractKey,
typename _Equal,
894 typename _H1,
typename _H2,
typename _Hash,
895 typename _RehashPolicy,
typename _Traits>
896 template<
typename _InputIterator,
typename _NodeGetter>
898 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
899 _RehashPolicy, _Traits>::
900 _M_insert_range(_InputIterator __first, _InputIterator __last,
903 using __rehash_type =
typename __hashtable::__rehash_type;
904 using __rehash_state =
typename __hashtable::__rehash_state;
907 size_type __n_elt = __detail::__distance_fw(__first, __last);
911 __hashtable& __h = _M_conjure_hashtable();
912 __rehash_type& __rehash = __h._M_rehash_policy;
913 const __rehash_state& __saved_state = __rehash._M_state();
914 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
915 __h._M_element_count,
918 if (__do_rehash.first)
919 __h._M_rehash(__do_rehash.second, __saved_state);
921 for (; __first != __last; ++__first)
922 __h._M_insert(*__first, __node_gen, __unique_keys());
931 template<
typename _Key,
typename _Value,
typename _Alloc,
932 typename _ExtractKey,
typename _Equal,
933 typename _H1,
typename _H2,
typename _Hash,
934 typename _RehashPolicy,
typename _Traits,
935 bool _Constant_iterators = _Traits::__constant_iterators::value>
939 template<
typename _Key,
typename _Value,
typename _Alloc,
940 typename _ExtractKey,
typename _Equal,
941 typename _H1,
typename _H2,
typename _Hash,
942 typename _RehashPolicy,
typename _Traits>
943 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
944 _RehashPolicy, _Traits, true>
945 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
946 _H1, _H2, _Hash, _RehashPolicy, _Traits>
949 _Equal, _H1, _H2, _Hash,
950 _RehashPolicy, _Traits>;
953 _Equal, _H1, _H2, _Hash,
956 using value_type =
typename __base_type::value_type;
957 using iterator =
typename __base_type::iterator;
958 using const_iterator =
typename __base_type::const_iterator;
960 using __unique_keys =
typename __base_type::__unique_keys;
961 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
963 using __node_gen_type =
typename __base_type::__node_gen_type;
965 using __base_type::insert;
968 insert(value_type&& __v)
971 __node_gen_type __node_gen(__h);
972 return __h._M_insert(
std::move(__v), __node_gen, __unique_keys());
976 insert(const_iterator __hint, value_type&& __v)
979 __node_gen_type __node_gen(__h);
980 return __h._M_insert(__hint,
std::move(__v), __node_gen,
986 template<
typename _Key,
typename _Value,
typename _Alloc,
987 typename _ExtractKey,
typename _Equal,
988 typename _H1,
typename _H2,
typename _Hash,
989 typename _RehashPolicy,
typename _Traits>
990 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
991 _RehashPolicy, _Traits, false>
992 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
993 _H1, _H2, _Hash, _RehashPolicy, _Traits>
996 _Equal, _H1, _H2, _Hash,
997 _RehashPolicy, _Traits>;
998 using value_type =
typename __base_type::value_type;
999 using iterator =
typename __base_type::iterator;
1000 using const_iterator =
typename __base_type::const_iterator;
1002 using __unique_keys =
typename __base_type::__unique_keys;
1004 using __ireturn_type =
typename __base_type::__ireturn_type;
1006 using __base_type::insert;
1008 template<
typename _Pair>
1011 template<
typename _Pair>
1014 template<
typename _Pair>
1017 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1022 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1025 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1027 insert(const_iterator __hint, _Pair&& __v)
1030 return __h._M_emplace(__hint, __unique_keys(),
1031 std::forward<_Pair>(__v));
1035 template<
typename _Policy>
1036 using __has_load_factor =
typename _Policy::__has_load_factor;
1044 template<
typename _Key,
typename _Value,
typename _Alloc,
1045 typename _ExtractKey,
typename _Equal,
1046 typename _H1,
typename _H2,
typename _Hash,
1047 typename _RehashPolicy,
typename _Traits,
1049 __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1053 template<
typename _Key,
typename _Value,
typename _Alloc,
1054 typename _ExtractKey,
typename _Equal,
1055 typename _H1,
typename _H2,
typename _Hash,
1056 typename _RehashPolicy,
typename _Traits>
1058 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1064 template<
typename _Key,
typename _Value,
typename _Alloc,
1065 typename _ExtractKey,
typename _Equal,
1066 typename _H1,
typename _H2,
typename _Hash,
1067 typename _RehashPolicy,
typename _Traits>
1069 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1073 _Equal, _H1, _H2, _Hash,
1074 _RehashPolicy, _Traits>;
1077 max_load_factor()
const noexcept
1079 const __hashtable* __this = static_cast<const __hashtable*>(
this);
1080 return __this->__rehash_policy().max_load_factor();
1084 max_load_factor(
float __z)
1086 __hashtable* __this = static_cast<__hashtable*>(
this);
1087 __this->__rehash_policy(_RehashPolicy(__z));
1091 reserve(std::size_t __n)
1093 __hashtable* __this = static_cast<__hashtable*>(
this);
1094 __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1104 template<
int _Nm,
typename _Tp,
1105 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1109 template<
int _Nm,
typename _Tp>
1115 template<
typename _OtherTp>
1117 : _Tp(std::forward<_OtherTp>(__tp))
1120 const _Tp& _M_cget()
const {
return static_cast<const _Tp&>(*
this); }
1121 _Tp& _M_get() {
return static_cast<_Tp&>(*
this); }
1125 template<
int _Nm,
typename _Tp>
1130 template<
typename _OtherTp>
1132 : _M_tp(std::forward<_OtherTp>(__tp))
1135 const _Tp& _M_cget()
const {
return _M_tp; }
1136 _Tp& _M_get() {
return _M_tp; }
1148 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1149 typename _H1,
typename _H2,
typename _Hash,
1150 bool __cache_hash_code>
1173 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1174 typename _H1,
typename _H2,
typename _Hash,
1175 bool __cache_hash_code>
1180 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1181 typename _H1,
typename _H2,
typename _Hash>
1191 typedef void* __hash_code;
1203 _M_hash_code(
const _Key& __key)
const
1207 _M_bucket_index(
const _Key& __k, __hash_code,
1208 std::size_t __bkt_count)
const
1209 {
return _M_ranged_hash()(__k, __bkt_count); }
1212 _M_bucket_index(
const __node_type* __p, std::size_t __bkt_count)
const
1213 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1215 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); }
1228 std::swap(__ebo_extract_key::_M_get(),
1229 __x.__ebo_extract_key::_M_get());
1230 std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get());
1234 _M_extract()
const {
return __ebo_extract_key::_M_cget(); }
1237 _M_ranged_hash()
const {
return __ebo_hash::_M_cget(); }
1246 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1247 typename _H1,
typename _H2,
typename _Hash>
1248 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1253 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1254 typename _H1,
typename _H2>
1274 hash_function()
const
1278 typedef std::size_t __hash_code;
1286 const _H1& __h1,
const _H2& __h2,
1291 _M_hash_code(
const _Key& __k)
const
1293 static_assert(__is_invocable<const _H1&, const _Key&>{},
1294 "hash function must be invocable with an argument of key type");
1295 return _M_h1()(__k);
1299 _M_bucket_index(
const _Key&, __hash_code __c,
1300 std::size_t __bkt_count)
const
1301 {
return _M_h2()(__c, __bkt_count); }
1304 _M_bucket_index(
const __node_type* __p, std::size_t __bkt_count)
const
1305 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1306 && noexcept(declval<const _H2&>()((__hash_code)0,
1308 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); }
1321 std::swap(__ebo_extract_key::_M_get(),
1322 __x.__ebo_extract_key::_M_get());
1323 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1324 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1328 _M_extract()
const {
return __ebo_extract_key::_M_cget(); }
1331 _M_h1()
const {
return __ebo_h1::_M_cget(); }
1334 _M_h2()
const {
return __ebo_h2::_M_cget(); }
1340 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1341 typename _H1,
typename _H2>
1361 hash_function()
const
1365 typedef std::size_t __hash_code;
1371 const _H1& __h1,
const _H2& __h2,
1376 _M_hash_code(
const _Key& __k)
const
1378 static_assert(__is_invocable<const _H1&, const _Key&>{},
1379 "hash function must be invocable with an argument of key type");
1380 return _M_h1()(__k);
1384 _M_bucket_index(
const _Key&, __hash_code __c,
1385 std::size_t __bkt_count)
const
1386 {
return _M_h2()(__c, __bkt_count); }
1389 _M_bucket_index(
const __node_type* __p, std::size_t __bkt_count)
const
1390 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1392 {
return _M_h2()(__p->_M_hash_code, __bkt_count); }
1395 _M_store_code(
__node_type* __n, __hash_code __c)
const
1396 { __n->_M_hash_code = __c; }
1400 { __to->_M_hash_code = __from->_M_hash_code; }
1405 std::swap(__ebo_extract_key::_M_get(),
1406 __x.__ebo_extract_key::_M_get());
1407 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1408 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1412 _M_extract()
const {
return __ebo_extract_key::_M_cget(); }
1415 _M_h1()
const {
return __ebo_h1::_M_cget(); }
1418 _M_h2()
const {
return __ebo_h2::_M_cget(); }
1422 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1423 typename _H1,
typename _H2,
typename _Hash>
1425 _H1, _H2, _Hash, true>
1431 _H1, _H2, _Hash,
true>;
1436 std::size_t __bkt, std::size_t __bkt_count)
1438 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1443 _M_cur = _M_cur->_M_next();
1447 = __base_type::_M_get()(_M_cur->_M_hash_code,
1449 if (__bkt != _M_bucket)
1455 std::size_t _M_bucket;
1456 std::size_t _M_bucket_count;
1460 _M_curr()
const {
return _M_cur; }
1463 _M_get_bucket()
const {
return _M_bucket; }
1470 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1471 struct _Hash_code_storage
1473 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1476 _M_h() {
return _M_storage._M_ptr(); }
1479 _M_h()
const {
return _M_storage._M_ptr(); }
1483 template<
typename _Tp>
1484 struct _Hash_code_storage<_Tp, true>
1491 _M_h() {
return reinterpret_cast<_Tp*>(
this); }
1494 _M_h()
const {
return reinterpret_cast<const _Tp*>(
this); }
1497 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1498 typename _H1,
typename _H2,
typename _Hash>
1499 using __hash_code_for_local_iter
1500 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1501 _H1, _H2, _Hash,
false>>;
1504 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1505 typename _H1,
typename _H2,
typename _Hash>
1506 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1507 _H1, _H2, _Hash, false>
1508 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1511 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1512 _H1, _H2, _Hash,
false>;
1514 _Local_iterator_base() : _M_bucket_count(-1) { }
1516 _Local_iterator_base(
const __hash_code_base&
__base,
1517 _Hash_node<_Value, false>* __p,
1518 std::size_t __bkt, std::size_t __bkt_count)
1519 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1522 ~_Local_iterator_base()
1524 if (_M_bucket_count != -1)
1528 _Local_iterator_base(
const _Local_iterator_base& __iter)
1529 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1530 _M_bucket_count(__iter._M_bucket_count)
1532 if (_M_bucket_count != -1)
1533 _M_init(*__iter._M_h());
1536 _Local_iterator_base&
1537 operator=(
const _Local_iterator_base& __iter)
1539 if (_M_bucket_count != -1)
1541 _M_cur = __iter._M_cur;
1542 _M_bucket = __iter._M_bucket;
1543 _M_bucket_count = __iter._M_bucket_count;
1544 if (_M_bucket_count != -1)
1545 _M_init(*__iter._M_h());
1552 _M_cur = _M_cur->_M_next();
1555 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1557 if (__bkt != _M_bucket)
1562 _Hash_node<_Value, false>* _M_cur;
1563 std::size_t _M_bucket;
1564 std::size_t _M_bucket_count;
1567 _M_init(
const __hash_code_base&
__base)
1568 { ::new(this->_M_h()) __hash_code_base(
__base); }
1571 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1575 _M_curr()
const {
return _M_cur; }
1578 _M_get_bucket()
const {
return _M_bucket; }
1581 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1582 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1584 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1585 _H1, _H2, _Hash, __cache>& __x,
1586 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1587 _H1, _H2, _Hash, __cache>& __y)
1588 {
return __x._M_curr() == __y._M_curr(); }
1590 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1591 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1593 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1594 _H1, _H2, _Hash, __cache>& __x,
1595 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1596 _H1, _H2, _Hash, __cache>& __y)
1597 {
return __x._M_curr() != __y._M_curr(); }
1600 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1601 typename _H1,
typename _H2,
typename _Hash,
1602 bool __constant_iterators,
bool __cache>
1605 _H1, _H2, _Hash, __cache>
1609 _H1, _H2, _Hash, __cache>;
1610 using __hash_code_base =
typename __base_type::__hash_code_base;
1612 typedef _Value value_type;
1614 const _Value*, _Value*>::type
1617 const _Value&, _Value&>::type
1619 typedef std::ptrdiff_t difference_type;
1626 std::size_t __bkt, std::size_t __bkt_count)
1632 {
return this->_M_cur->_M_v(); }
1636 {
return this->_M_cur->_M_valptr(); }
1655 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1656 typename _H1,
typename _H2,
typename _Hash,
1657 bool __constant_iterators,
bool __cache>
1660 _H1, _H2, _Hash, __cache>
1664 _H1, _H2, _Hash, __cache>;
1665 using __hash_code_base =
typename __base_type::__hash_code_base;
1668 typedef _Value value_type;
1669 typedef const _Value* pointer;
1670 typedef const _Value& reference;
1671 typedef std::ptrdiff_t difference_type;
1678 std::size_t __bkt, std::size_t __bkt_count)
1684 __constant_iterators,
1691 {
return this->_M_cur->_M_v(); }
1695 {
return this->_M_cur->_M_valptr(); }
1723 template<
typename _Key,
typename _Value,
1724 typename _ExtractKey,
typename _Equal,
1725 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1728 _Traits::__hash_cached::value>,
1732 typedef _Key key_type;
1733 typedef _Value value_type;
1734 typedef _Equal key_equal;
1735 typedef std::size_t size_type;
1736 typedef std::ptrdiff_t difference_type;
1738 using __traits_type = _Traits;
1739 using __hash_cached =
typename __traits_type::__hash_cached;
1740 using __constant_iterators =
typename __traits_type::__constant_iterators;
1741 using __unique_keys =
typename __traits_type::__unique_keys;
1745 __hash_cached::value>;
1747 using __hash_code =
typename __hash_code_base::__hash_code;
1748 using __node_type =
typename __hash_code_base::__node_type;
1751 __constant_iterators::value,
1752 __hash_cached::value>;
1755 __constant_iterators::value,
1756 __hash_cached::value>;
1759 _ExtractKey, _H1, _H2, _Hash,
1760 __constant_iterators::value,
1761 __hash_cached::value>;
1765 _ExtractKey, _H1, _H2, _Hash,
1766 __constant_iterators::value,
1767 __hash_cached::value>;
1775 template<
typename _NodeT>
1776 struct _Equal_hash_code
1779 _S_equals(__hash_code,
const _NodeT&)
1783 template<
typename _Ptr2>
1784 struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
1787 _S_equals(__hash_code __c,
const _Hash_node<_Ptr2, true>& __n)
1788 {
return __c == __n._M_hash_code; }
1792 _Hashtable_base() =
default;
1793 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1794 const _Hash& __hash,
const _Equal& __eq)
1795 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1799 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const
1801 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1802 "key equality predicate must be invocable with two arguments of "
1804 return _Equal_hash_code<__node_type>::_S_equals(__c, *__n)
1805 && _M_eq()(__k, this->_M_extract()(__n->_M_v()));
1809 _M_swap(_Hashtable_base& __x)
1811 __hash_code_base::_M_swap(__x);
1812 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1816 _M_eq()
const {
return _EqualEBO::_M_cget(); }
1827 template<
typename _Key,
typename _Value,
typename _Alloc,
1828 typename _ExtractKey,
typename _Equal,
1829 typename _H1,
typename _H2,
typename _Hash,
1830 typename _RehashPolicy,
typename _Traits,
1831 bool _Unique_keys = _Traits::__unique_keys::value>
1835 template<
typename _Key,
typename _Value,
typename _Alloc,
1836 typename _ExtractKey,
typename _Equal,
1837 typename _H1,
typename _H2,
typename _Hash,
1838 typename _RehashPolicy,
typename _Traits>
1840 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1843 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1849 template<
typename _Key,
typename _Value,
typename _Alloc,
1850 typename _ExtractKey,
typename _Equal,
1851 typename _H1,
typename _H2,
typename _Hash,
1852 typename _RehashPolicy,
typename _Traits>
1854 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1855 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1856 _M_equal(
const __hashtable& __other)
const
1858 using __node_base =
typename __hashtable::__node_base;
1859 using __node_type =
typename __hashtable::__node_type;
1860 const __hashtable* __this = static_cast<const __hashtable*>(
this);
1861 if (__this->size() != __other.size())
1864 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1866 std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
1867 __node_base* __prev_n = __other._M_buckets[__ybkt];
1871 for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
1872 __n = __n->_M_next())
1874 if (__n->_M_v() == *__itx)
1878 || __other._M_bucket_index(__n->_M_next()) != __ybkt)
1887 template<
typename _Key,
typename _Value,
typename _Alloc,
1888 typename _ExtractKey,
typename _Equal,
1889 typename _H1,
typename _H2,
typename _Hash,
1890 typename _RehashPolicy,
typename _Traits>
1892 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1895 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1901 template<
typename _Key,
typename _Value,
typename _Alloc,
1902 typename _ExtractKey,
typename _Equal,
1903 typename _H1,
typename _H2,
typename _Hash,
1904 typename _RehashPolicy,
typename _Traits>
1906 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1907 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1908 _M_equal(
const __hashtable& __other)
const
1910 using __node_base =
typename __hashtable::__node_base;
1911 using __node_type =
typename __hashtable::__node_type;
1912 const __hashtable* __this = static_cast<const __hashtable*>(
this);
1913 if (__this->size() != __other.size())
1916 for (
auto __itx = __this->begin(); __itx != __this->end();)
1918 std::size_t __x_count = 1;
1919 auto __itx_end = __itx;
1920 for (++__itx_end; __itx_end != __this->end()
1921 && __this->key_eq()(_ExtractKey()(*__itx),
1922 _ExtractKey()(*__itx_end));
1926 std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
1927 __node_base* __y_prev_n = __other._M_buckets[__ybkt];
1931 __node_type* __y_n = static_cast<__node_type*>(__y_prev_n->_M_nxt);
1932 for (;; __y_n = __y_n->_M_next())
1934 if (__this->key_eq()(_ExtractKey()(__y_n->_M_v()),
1935 _ExtractKey()(*__itx)))
1939 || __other._M_bucket_index(__y_n->_M_next()) != __ybkt)
1943 typename __hashtable::const_iterator __ity(__y_n);
1944 for (
auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
1945 if (--__x_count == 0)
1951 if (!std::is_permutation(__itx, __itx_end, __ity))
1963 template<
typename _NodeAlloc>
1964 struct _Hashtable_alloc :
private _Hashtable_ebo_helper<0, _NodeAlloc>
1967 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
1969 using __node_type =
typename _NodeAlloc::value_type;
1970 using __node_alloc_type = _NodeAlloc;
1974 using __value_alloc_traits =
typename __node_alloc_traits::template
1975 rebind_traits<typename __node_type::value_type>;
1977 using __node_base = __detail::_Hash_node_base;
1978 using __bucket_type = __node_base*;
1979 using __bucket_alloc_type =
1980 __alloc_rebind<__node_alloc_type, __bucket_type>;
1983 _Hashtable_alloc() =
default;
1984 _Hashtable_alloc(
const _Hashtable_alloc&) =
default;
1985 _Hashtable_alloc(_Hashtable_alloc&&) =
default;
1987 template<
typename _Alloc>
1988 _Hashtable_alloc(_Alloc&& __a)
1989 : __ebo_node_alloc(
std::
forward<_Alloc>(__a))
1994 {
return __ebo_node_alloc::_M_get(); }
1996 const __node_alloc_type&
1997 _M_node_allocator()
const
1998 {
return __ebo_node_alloc::_M_cget(); }
2001 template<
typename... _Args>
2003 _M_allocate_node(_Args&&... __args);
2007 _M_deallocate_node(__node_type* __n);
2011 _M_deallocate_node_ptr(__node_type* __n);
2016 _M_deallocate_nodes(__node_type* __n);
2019 _M_allocate_buckets(std::size_t __bkt_count);
2022 _M_deallocate_buckets(__bucket_type*, std::size_t __bkt_count);
2027 template<
typename _NodeAlloc>
2028 template<
typename... _Args>
2030 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
2033 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2034 __node_type* __n = std::__to_address(__nptr);
2037 ::new ((
void*)__n) __node_type;
2038 __node_alloc_traits::construct(_M_node_allocator(),
2040 std::forward<_Args>(__args)...);
2045 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2046 __throw_exception_again;
2050 template<
typename _NodeAlloc>
2052 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2054 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2055 _M_deallocate_node_ptr(__n);
2058 template<
typename _NodeAlloc>
2060 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n)
2062 typedef typename __node_alloc_traits::pointer _Ptr;
2064 __n->~__node_type();
2065 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2068 template<
typename _NodeAlloc>
2070 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
2074 __node_type* __tmp = __n;
2075 __n = __n->_M_next();
2076 _M_deallocate_node(__tmp);
2080 template<
typename _NodeAlloc>
2081 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2082 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
2084 __bucket_alloc_type __alloc(_M_node_allocator());
2086 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __bkt_count);
2087 __bucket_type* __p = std::__to_address(__ptr);
2088 __builtin_memset(__p, 0, __bkt_count *
sizeof(__bucket_type));
2092 template<
typename _NodeAlloc>
2094 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2095 std::size_t __bkt_count)
2097 typedef typename __bucket_alloc_traits::pointer _Ptr;
2099 __bucket_alloc_type __alloc(_M_node_allocator());
2100 __bucket_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
2105 _GLIBCXX_END_NAMESPACE_VERSION
2108 #endif // _HASHTABLE_POLICY_H