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 _H1,
typename _H2,
typename _Hash,
45 typename _RehashPolicy,
typename _Traits>
55 template<
typename _Key,
typename _Value,
56 typename _ExtractKey,
typename _Equal,
57 typename _H1,
typename _H2,
typename _Hash,
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
85 {
return std::forward<_Tp>(__x); }
90 template<
typename _Tp>
92 operator()(_Tp&& __x)
const
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<
typename _Value,
bool _Cache_hash_code>
263 template<
typename _Value>
266 std::size_t _M_hash_code;
269 _M_next()
const noexcept
270 {
return static_cast<_Hash_node*>(this->_M_nxt); }
278 template<
typename _Value>
282 _M_next()
const noexcept
283 {
return static_cast<_Hash_node*>(this->_M_nxt); }
287 template<
typename _Value,
bool _Cache_hash_code>
299 { _M_cur = _M_cur->_M_next(); }
302 template<
typename _Value,
bool _Cache_hash_code>
307 {
return __x._M_cur == __y._M_cur; }
309 template<
typename _Value,
bool _Cache_hash_code>
311 operator!=(
const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
312 const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
314 {
return __x._M_cur != __y._M_cur; }
317 template<
typename _Value,
bool __constant_iterators,
bool __cache>
326 typedef _Value value_type;
327 typedef std::ptrdiff_t difference_type;
331 const _Value*, _Value*>::type;
334 const _Value&, _Value&>::type;
344 operator*()
const noexcept
345 {
return this->_M_cur->_M_v(); }
348 operator->()
const noexcept
349 {
return this->_M_cur->_M_valptr(); }
352 operator++() noexcept
359 operator++(
int) noexcept
368 template<
typename _Value,
bool __constant_iterators,
bool __cache>
377 typedef _Value value_type;
378 typedef std::ptrdiff_t difference_type;
381 typedef const _Value* pointer;
382 typedef const _Value& reference;
392 __cache>& __x) noexcept
396 operator*()
const noexcept
397 {
return this->_M_cur->_M_v(); }
400 operator->()
const noexcept
401 {
return this->_M_cur->_M_valptr(); }
404 operator++() noexcept
411 operator++(
int) noexcept
426 typedef std::size_t first_argument_type;
427 typedef std::size_t second_argument_type;
428 typedef std::size_t result_type;
431 operator()(first_argument_type __num,
432 second_argument_type __den)
const noexcept
433 {
return __num % __den; }
450 : _M_max_load_factor(__z), _M_next_resize(0) { }
453 max_load_factor()
const noexcept
454 {
return _M_max_load_factor; }
458 _M_next_bkt(std::size_t __n)
const;
462 _M_bkt_for_elements(std::size_t __n)
const
463 {
return __builtin_ceill(__n / (
long double)_M_max_load_factor); }
470 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
471 std::size_t __n_ins)
const;
473 typedef std::size_t _State;
477 {
return _M_next_resize; }
481 { _M_next_resize = 0; }
484 _M_reset(_State __state)
485 { _M_next_resize = __state; }
487 static const std::size_t _S_growth_factor = 2;
489 float _M_max_load_factor;
490 mutable std::size_t _M_next_resize;
496 typedef std::size_t first_argument_type;
497 typedef std::size_t second_argument_type;
498 typedef std::size_t result_type;
501 operator()(first_argument_type __num,
502 second_argument_type __den)
const noexcept
503 {
return __num & (__den - 1); }
513 const unsigned __lz =
sizeof(size_t) >
sizeof(
long)
514 ? __builtin_clzll(__n - 1ull)
515 : __builtin_clzl(__n - 1ul);
527 : _M_max_load_factor(__z), _M_next_resize(0) { }
530 max_load_factor()
const noexcept
531 {
return _M_max_load_factor; }
536 _M_next_bkt(std::size_t __n) noexcept
544 const auto __max_width = std::min<size_t>(
sizeof(
size_t), 8);
545 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
546 std::size_t __res =
__clp2(__n);
556 if (__res == __max_bkt)
563 = __builtin_floorl(__res * (
long double)_M_max_load_factor);
570 _M_bkt_for_elements(std::size_t __n)
const noexcept
571 {
return __builtin_ceill(__n / (
long double)_M_max_load_factor); }
578 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
579 std::size_t __n_ins) noexcept
581 if (__n_elt + __n_ins > _M_next_resize)
586 long double __min_bkts
587 = std::max<std::size_t>(__n_elt + __n_ins, _M_next_resize ? 0 : 11)
588 / (
long double)_M_max_load_factor;
589 if (__min_bkts >= __n_bkt)
591 _M_next_bkt(std::max<std::size_t>(__builtin_floorl(__min_bkts) + 1,
592 __n_bkt * _S_growth_factor)) };
595 = __builtin_floorl(__n_bkt * (
long double)_M_max_load_factor);
602 typedef std::size_t _State;
605 _M_state()
const noexcept
606 {
return _M_next_resize; }
610 { _M_next_resize = 0; }
613 _M_reset(_State __state) noexcept
614 { _M_next_resize = __state; }
616 static const std::size_t _S_growth_factor = 2;
618 float _M_max_load_factor;
619 std::size_t _M_next_resize;
640 template<
typename _Key,
typename _Value,
typename _Alloc,
641 typename _ExtractKey,
typename _Equal,
642 typename _H1,
typename _H2,
typename _Hash,
643 typename _RehashPolicy,
typename _Traits,
644 bool _Unique_keys = _Traits::__unique_keys::value>
648 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
649 typename _H1,
typename _H2,
typename _Hash,
650 typename _RehashPolicy,
typename _Traits>
651 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
652 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
658 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
659 typename _H1,
typename _H2,
typename _Hash,
660 typename _RehashPolicy,
typename _Traits>
661 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
662 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
667 _Equal, _H1, _H2, _Hash,
672 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
674 using __hash_code =
typename __hashtable_base::__hash_code;
675 using __node_type =
typename __hashtable_base::__node_type;
678 using key_type =
typename __hashtable_base::key_type;
683 operator[](
const key_type& __k);
686 operator[](key_type&& __k);
691 at(
const key_type& __k);
694 at(
const key_type& __k)
const;
697 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
698 typename _H1,
typename _H2,
typename _Hash,
699 typename _RehashPolicy,
typename _Traits>
701 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
702 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
703 operator[](
const key_type& __k)
706 __hashtable* __h = static_cast<__hashtable*>(
this);
707 __hash_code __code = __h->_M_hash_code(__k);
708 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
709 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
710 return __node->_M_v().second;
712 typename __hashtable::_Scoped_node __node {
719 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
720 __node._M_node =
nullptr;
721 return __pos->second;
724 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
725 typename _H1,
typename _H2,
typename _Hash,
726 typename _RehashPolicy,
typename _Traits>
728 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
729 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
730 operator[](key_type&& __k)
733 __hashtable* __h = static_cast<__hashtable*>(
this);
734 __hash_code __code = __h->_M_hash_code(__k);
735 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
736 if (__node_type* __node = __h->_M_find_node(__bkt, __k, __code))
737 return __node->_M_v().second;
739 typename __hashtable::_Scoped_node __node {
746 = __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
747 __node._M_node =
nullptr;
748 return __pos->second;
751 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
752 typename _H1,
typename _H2,
typename _Hash,
753 typename _RehashPolicy,
typename _Traits>
755 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
756 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
757 at(
const key_type& __k)
760 __hashtable* __h = static_cast<__hashtable*>(
this);
761 __hash_code __code = __h->_M_hash_code(__k);
762 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
763 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
766 __throw_out_of_range(__N(
"_Map_base::at"));
767 return __p->_M_v().second;
770 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
771 typename _H1,
typename _H2,
typename _Hash,
772 typename _RehashPolicy,
typename _Traits>
774 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
775 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
776 at(
const key_type& __k)
const
777 ->
const mapped_type&
779 const __hashtable* __h = static_cast<const __hashtable*>(
this);
780 __hash_code __code = __h->_M_hash_code(__k);
781 std::size_t __bkt = __h->_M_bucket_index(__k, __code);
782 __node_type* __p = __h->_M_find_node(__bkt, __k, __code);
785 __throw_out_of_range(__N(
"_Map_base::at"));
786 return __p->_M_v().second;
794 template<
typename _Key,
typename _Value,
typename _Alloc,
795 typename _ExtractKey,
typename _Equal,
796 typename _H1,
typename _H2,
typename _Hash,
797 typename _RehashPolicy,
typename _Traits>
802 _Equal, _H1, _H2, _Hash,
803 _RehashPolicy, _Traits>;
806 _Equal, _H1, _H2, _Hash,
809 using value_type =
typename __hashtable_base::value_type;
812 using size_type =
typename __hashtable_base::size_type;
814 using __unique_keys =
typename __hashtable_base::__unique_keys;
815 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
817 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
818 using __node_gen_type = _AllocNode<__node_alloc_type>;
821 _M_conjure_hashtable()
822 {
return *(static_cast<__hashtable*>(
this)); }
824 template<
typename _InputIterator,
typename _NodeGetter>
826 _M_insert_range(_InputIterator __first, _InputIterator __last,
829 template<
typename _InputIterator,
typename _NodeGetter>
831 _M_insert_range(_InputIterator __first, _InputIterator __last,
836 insert(
const value_type& __v)
839 __node_gen_type __node_gen(__h);
840 return __h._M_insert(__v, __node_gen, __unique_keys());
844 insert(const_iterator __hint,
const value_type& __v)
847 __node_gen_type __node_gen(__h);
848 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
853 { this->insert(__l.begin(), __l.end()); }
855 template<
typename _InputIterator>
857 insert(_InputIterator __first, _InputIterator __last)
860 __node_gen_type __node_gen(__h);
861 return _M_insert_range(__first, __last, __node_gen, __unique_keys());
865 template<
typename _Key,
typename _Value,
typename _Alloc,
866 typename _ExtractKey,
typename _Equal,
867 typename _H1,
typename _H2,
typename _Hash,
868 typename _RehashPolicy,
typename _Traits>
869 template<
typename _InputIterator,
typename _NodeGetter>
871 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
872 _RehashPolicy, _Traits>::
873 _M_insert_range(_InputIterator __first, _InputIterator __last,
874 const _NodeGetter& __node_gen,
true_type)
876 size_type __n_elt = __detail::__distance_fw(__first, __last);
880 __hashtable& __h = _M_conjure_hashtable();
881 for (; __first != __last; ++__first)
883 if (__h._M_insert(*__first, __node_gen, __unique_keys(),
886 else if (__n_elt != 1)
891 template<
typename _Key,
typename _Value,
typename _Alloc,
892 typename _ExtractKey,
typename _Equal,
893 typename _H1,
typename _H2,
typename _Hash,
894 typename _RehashPolicy,
typename _Traits>
895 template<
typename _InputIterator,
typename _NodeGetter>
897 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
898 _RehashPolicy, _Traits>::
899 _M_insert_range(_InputIterator __first, _InputIterator __last,
902 using __rehash_type =
typename __hashtable::__rehash_type;
903 using __rehash_state =
typename __hashtable::__rehash_state;
906 size_type __n_elt = __detail::__distance_fw(__first, __last);
910 __hashtable& __h = _M_conjure_hashtable();
911 __rehash_type& __rehash = __h._M_rehash_policy;
912 const __rehash_state& __saved_state = __rehash._M_state();
913 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
914 __h._M_element_count,
917 if (__do_rehash.first)
918 __h._M_rehash(__do_rehash.second, __saved_state);
920 for (; __first != __last; ++__first)
921 __h._M_insert(*__first, __node_gen, __unique_keys());
930 template<
typename _Key,
typename _Value,
typename _Alloc,
931 typename _ExtractKey,
typename _Equal,
932 typename _H1,
typename _H2,
typename _Hash,
933 typename _RehashPolicy,
typename _Traits,
934 bool _Constant_iterators = _Traits::__constant_iterators::value>
938 template<
typename _Key,
typename _Value,
typename _Alloc,
939 typename _ExtractKey,
typename _Equal,
940 typename _H1,
typename _H2,
typename _Hash,
941 typename _RehashPolicy,
typename _Traits>
942 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
943 _RehashPolicy, _Traits, true>
944 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
945 _H1, _H2, _Hash, _RehashPolicy, _Traits>
948 _Equal, _H1, _H2, _Hash,
949 _RehashPolicy, _Traits>;
952 _Equal, _H1, _H2, _Hash,
955 using value_type =
typename __base_type::value_type;
956 using iterator =
typename __base_type::iterator;
957 using const_iterator =
typename __base_type::const_iterator;
959 using __unique_keys =
typename __base_type::__unique_keys;
960 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
962 using __node_gen_type =
typename __base_type::__node_gen_type;
964 using __base_type::insert;
967 insert(value_type&& __v)
970 __node_gen_type __node_gen(__h);
971 return __h._M_insert(
std::move(__v), __node_gen, __unique_keys());
975 insert(const_iterator __hint, value_type&& __v)
978 __node_gen_type __node_gen(__h);
979 return __h._M_insert(__hint,
std::move(__v), __node_gen,
985 template<
typename _Key,
typename _Value,
typename _Alloc,
986 typename _ExtractKey,
typename _Equal,
987 typename _H1,
typename _H2,
typename _Hash,
988 typename _RehashPolicy,
typename _Traits>
989 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
990 _RehashPolicy, _Traits, false>
991 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
992 _H1, _H2, _Hash, _RehashPolicy, _Traits>
995 _Equal, _H1, _H2, _Hash,
996 _RehashPolicy, _Traits>;
997 using value_type =
typename __base_type::value_type;
998 using iterator =
typename __base_type::iterator;
999 using const_iterator =
typename __base_type::const_iterator;
1001 using __unique_keys =
typename __base_type::__unique_keys;
1003 using __ireturn_type =
typename __base_type::__ireturn_type;
1005 using __base_type::insert;
1007 template<
typename _Pair>
1010 template<
typename _Pair>
1013 template<
typename _Pair>
1016 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1021 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1024 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1026 insert(const_iterator __hint, _Pair&& __v)
1029 return __h._M_emplace(__hint, __unique_keys(),
1030 std::forward<_Pair>(__v));
1034 template<
typename _Policy>
1035 using __has_load_factor =
typename _Policy::__has_load_factor;
1043 template<
typename _Key,
typename _Value,
typename _Alloc,
1044 typename _ExtractKey,
typename _Equal,
1045 typename _H1,
typename _H2,
typename _Hash,
1046 typename _RehashPolicy,
typename _Traits,
1048 __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1052 template<
typename _Key,
typename _Value,
typename _Alloc,
1053 typename _ExtractKey,
typename _Equal,
1054 typename _H1,
typename _H2,
typename _Hash,
1055 typename _RehashPolicy,
typename _Traits>
1057 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1063 template<
typename _Key,
typename _Value,
typename _Alloc,
1064 typename _ExtractKey,
typename _Equal,
1065 typename _H1,
typename _H2,
typename _Hash,
1066 typename _RehashPolicy,
typename _Traits>
1068 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1072 _Equal, _H1, _H2, _Hash,
1073 _RehashPolicy, _Traits>;
1076 max_load_factor()
const noexcept
1078 const __hashtable* __this = static_cast<const __hashtable*>(
this);
1079 return __this->__rehash_policy().max_load_factor();
1083 max_load_factor(
float __z)
1085 __hashtable* __this = static_cast<__hashtable*>(
this);
1086 __this->__rehash_policy(_RehashPolicy(__z));
1090 reserve(std::size_t __n)
1092 __hashtable* __this = static_cast<__hashtable*>(
this);
1093 __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1103 template<
int _Nm,
typename _Tp,
1104 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1108 template<
int _Nm,
typename _Tp>
1114 template<
typename _OtherTp>
1116 : _Tp(std::forward<_OtherTp>(__tp))
1119 const _Tp& _M_cget()
const {
return static_cast<const _Tp&>(*
this); }
1120 _Tp& _M_get() {
return static_cast<_Tp&>(*
this); }
1124 template<
int _Nm,
typename _Tp>
1129 template<
typename _OtherTp>
1131 : _M_tp(std::forward<_OtherTp>(__tp))
1134 const _Tp& _M_cget()
const {
return _M_tp; }
1135 _Tp& _M_get() {
return _M_tp; }
1147 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1148 typename _H1,
typename _H2,
typename _Hash,
1149 bool __cache_hash_code>
1172 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1173 typename _H1,
typename _H2,
typename _Hash,
1174 bool __cache_hash_code>
1179 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1180 typename _H1,
typename _H2,
typename _Hash>
1190 typedef void* __hash_code;
1202 _M_hash_code(
const _Key& __key)
const
1206 _M_bucket_index(
const _Key& __k, __hash_code,
1207 std::size_t __bkt_count)
const
1208 {
return _M_ranged_hash()(__k, __bkt_count); }
1211 _M_bucket_index(
const __node_type* __p, std::size_t __bkt_count)
const
1212 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1214 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __bkt_count); }
1227 std::swap(__ebo_extract_key::_M_get(),
1228 __x.__ebo_extract_key::_M_get());
1229 std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get());
1233 _M_extract()
const {
return __ebo_extract_key::_M_cget(); }
1236 _M_ranged_hash()
const {
return __ebo_hash::_M_cget(); }
1245 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1246 typename _H1,
typename _H2,
typename _Hash>
1247 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1252 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1253 typename _H1,
typename _H2>
1273 hash_function()
const
1277 typedef std::size_t __hash_code;
1285 const _H1& __h1,
const _H2& __h2,
1290 _M_hash_code(
const _Key& __k)
const
1292 static_assert(__is_invocable<const _H1&, const _Key&>{},
1293 "hash function must be invocable with an argument of key type");
1294 return _M_h1()(__k);
1298 _M_bucket_index(
const _Key&, __hash_code __c,
1299 std::size_t __bkt_count)
const
1300 {
return _M_h2()(__c, __bkt_count); }
1303 _M_bucket_index(
const __node_type* __p, std::size_t __bkt_count)
const
1304 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1305 && noexcept(declval<const _H2&>()((__hash_code)0,
1307 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __bkt_count); }
1320 std::swap(__ebo_extract_key::_M_get(),
1321 __x.__ebo_extract_key::_M_get());
1322 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1323 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1327 _M_extract()
const {
return __ebo_extract_key::_M_cget(); }
1330 _M_h1()
const {
return __ebo_h1::_M_cget(); }
1333 _M_h2()
const {
return __ebo_h2::_M_cget(); }
1339 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1340 typename _H1,
typename _H2>
1360 hash_function()
const
1364 typedef std::size_t __hash_code;
1370 const _H1& __h1,
const _H2& __h2,
1375 _M_hash_code(
const _Key& __k)
const
1377 static_assert(__is_invocable<const _H1&, const _Key&>{},
1378 "hash function must be invocable with an argument of key type");
1379 return _M_h1()(__k);
1383 _M_bucket_index(
const _Key&, __hash_code __c,
1384 std::size_t __bkt_count)
const
1385 {
return _M_h2()(__c, __bkt_count); }
1388 _M_bucket_index(
const __node_type* __p, std::size_t __bkt_count)
const
1389 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1391 {
return _M_h2()(__p->_M_hash_code, __bkt_count); }
1394 _M_store_code(
__node_type* __n, __hash_code __c)
const
1395 { __n->_M_hash_code = __c; }
1399 { __to->_M_hash_code = __from->_M_hash_code; }
1404 std::swap(__ebo_extract_key::_M_get(),
1405 __x.__ebo_extract_key::_M_get());
1406 std::swap(__ebo_h1::_M_get(), __x.__ebo_h1::_M_get());
1407 std::swap(__ebo_h2::_M_get(), __x.__ebo_h2::_M_get());
1411 _M_extract()
const {
return __ebo_extract_key::_M_cget(); }
1414 _M_h1()
const {
return __ebo_h1::_M_cget(); }
1417 _M_h2()
const {
return __ebo_h2::_M_cget(); }
1421 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1422 typename _H1,
typename _H2,
typename _Hash>
1424 _H1, _H2, _Hash, true>
1430 _H1, _H2, _Hash,
true>;
1435 std::size_t __bkt, std::size_t __bkt_count)
1437 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1442 _M_cur = _M_cur->_M_next();
1446 = __base_type::_M_get()(_M_cur->_M_hash_code,
1448 if (__bkt != _M_bucket)
1454 std::size_t _M_bucket;
1455 std::size_t _M_bucket_count;
1459 _M_curr()
const {
return _M_cur; }
1462 _M_get_bucket()
const {
return _M_bucket; }
1469 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1470 struct _Hash_code_storage
1472 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1475 _M_h() {
return _M_storage._M_ptr(); }
1478 _M_h()
const {
return _M_storage._M_ptr(); }
1482 template<
typename _Tp>
1483 struct _Hash_code_storage<_Tp, true>
1490 _M_h() {
return reinterpret_cast<_Tp*>(
this); }
1493 _M_h()
const {
return reinterpret_cast<const _Tp*>(
this); }
1496 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1497 typename _H1,
typename _H2,
typename _Hash>
1498 using __hash_code_for_local_iter
1499 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1500 _H1, _H2, _Hash,
false>>;
1503 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1504 typename _H1,
typename _H2,
typename _Hash>
1505 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1506 _H1, _H2, _Hash, false>
1507 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1510 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1511 _H1, _H2, _Hash,
false>;
1513 _Local_iterator_base() : _M_bucket_count(-1) { }
1515 _Local_iterator_base(
const __hash_code_base&
__base,
1516 _Hash_node<_Value, false>* __p,
1517 std::size_t __bkt, std::size_t __bkt_count)
1518 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1521 ~_Local_iterator_base()
1523 if (_M_bucket_count != -1)
1527 _Local_iterator_base(
const _Local_iterator_base& __iter)
1528 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1529 _M_bucket_count(__iter._M_bucket_count)
1531 if (_M_bucket_count != -1)
1532 _M_init(*__iter._M_h());
1535 _Local_iterator_base&
1536 operator=(
const _Local_iterator_base& __iter)
1538 if (_M_bucket_count != -1)
1540 _M_cur = __iter._M_cur;
1541 _M_bucket = __iter._M_bucket;
1542 _M_bucket_count = __iter._M_bucket_count;
1543 if (_M_bucket_count != -1)
1544 _M_init(*__iter._M_h());
1551 _M_cur = _M_cur->_M_next();
1554 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1556 if (__bkt != _M_bucket)
1561 _Hash_node<_Value, false>* _M_cur;
1562 std::size_t _M_bucket;
1563 std::size_t _M_bucket_count;
1566 _M_init(
const __hash_code_base&
__base)
1567 { ::new(this->_M_h()) __hash_code_base(
__base); }
1570 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1574 _M_curr()
const {
return _M_cur; }
1577 _M_get_bucket()
const {
return _M_bucket; }
1580 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1581 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1583 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1584 _H1, _H2, _Hash, __cache>& __x,
1585 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1586 _H1, _H2, _Hash, __cache>& __y)
1587 {
return __x._M_curr() == __y._M_curr(); }
1589 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1590 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1592 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1593 _H1, _H2, _Hash, __cache>& __x,
1594 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1595 _H1, _H2, _Hash, __cache>& __y)
1596 {
return __x._M_curr() != __y._M_curr(); }
1599 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1600 typename _H1,
typename _H2,
typename _Hash,
1601 bool __constant_iterators,
bool __cache>
1604 _H1, _H2, _Hash, __cache>
1608 _H1, _H2, _Hash, __cache>;
1609 using __hash_code_base =
typename __base_type::__hash_code_base;
1611 typedef _Value value_type;
1613 const _Value*, _Value*>::type
1616 const _Value&, _Value&>::type
1618 typedef std::ptrdiff_t difference_type;
1625 std::size_t __bkt, std::size_t __bkt_count)
1631 {
return this->_M_cur->_M_v(); }
1635 {
return this->_M_cur->_M_valptr(); }
1654 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1655 typename _H1,
typename _H2,
typename _Hash,
1656 bool __constant_iterators,
bool __cache>
1659 _H1, _H2, _Hash, __cache>
1663 _H1, _H2, _Hash, __cache>;
1664 using __hash_code_base =
typename __base_type::__hash_code_base;
1667 typedef _Value value_type;
1668 typedef const _Value* pointer;
1669 typedef const _Value& reference;
1670 typedef std::ptrdiff_t difference_type;
1677 std::size_t __bkt, std::size_t __bkt_count)
1683 __constant_iterators,
1690 {
return this->_M_cur->_M_v(); }
1694 {
return this->_M_cur->_M_valptr(); }
1722 template<
typename _Key,
typename _Value,
1723 typename _ExtractKey,
typename _Equal,
1724 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1727 _Traits::__hash_cached::value>,
1731 typedef _Key key_type;
1732 typedef _Value value_type;
1733 typedef _Equal key_equal;
1734 typedef std::size_t size_type;
1735 typedef std::ptrdiff_t difference_type;
1737 using __traits_type = _Traits;
1738 using __hash_cached =
typename __traits_type::__hash_cached;
1739 using __constant_iterators =
typename __traits_type::__constant_iterators;
1740 using __unique_keys =
typename __traits_type::__unique_keys;
1744 __hash_cached::value>;
1746 using __hash_code =
typename __hash_code_base::__hash_code;
1747 using __node_type =
typename __hash_code_base::__node_type;
1750 __constant_iterators::value,
1751 __hash_cached::value>;
1754 __constant_iterators::value,
1755 __hash_cached::value>;
1758 _ExtractKey, _H1, _H2, _Hash,
1759 __constant_iterators::value,
1760 __hash_cached::value>;
1764 _ExtractKey, _H1, _H2, _Hash,
1765 __constant_iterators::value,
1766 __hash_cached::value>;
1774 template<
typename _NodeT>
1775 struct _Equal_hash_code
1778 _S_equals(__hash_code,
const _NodeT&)
1782 template<
typename _Ptr2>
1783 struct _Equal_hash_code<_Hash_node<_Ptr2, true>>
1786 _S_equals(__hash_code __c,
const _Hash_node<_Ptr2, true>& __n)
1787 {
return __c == __n._M_hash_code; }
1791 _Hashtable_base() =
default;
1792 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1793 const _Hash& __hash,
const _Equal& __eq)
1794 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1798 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const
1800 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1801 "key equality predicate must be invocable with two arguments of "
1803 return _Equal_hash_code<__node_type>::_S_equals(__c, *__n)
1804 && _M_eq()(__k, this->_M_extract()(__n->_M_v()));
1808 _M_swap(_Hashtable_base& __x)
1810 __hash_code_base::_M_swap(__x);
1811 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1815 _M_eq()
const {
return _EqualEBO::_M_cget(); }
1826 template<
typename _Uiterator>
1828 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1832 template<
typename _Uiterator>
1835 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1836 _Uiterator __first2)
1838 for (; __first1 != __last1; ++__first1, ++__first2)
1839 if (!(*__first1 == *__first2))
1842 if (__first1 == __last1)
1845 _Uiterator __last2 = __first2;
1848 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1850 _Uiterator __tmp = __first1;
1851 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1858 std::ptrdiff_t __n2 = 0;
1859 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1860 if (*__tmp == *__it1)
1866 std::ptrdiff_t __n1 = 0;
1867 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1868 if (*__tmp == *__it1)
1885 template<
typename _Key,
typename _Value,
typename _Alloc,
1886 typename _ExtractKey,
typename _Equal,
1887 typename _H1,
typename _H2,
typename _Hash,
1888 typename _RehashPolicy,
typename _Traits,
1889 bool _Unique_keys = _Traits::__unique_keys::value>
1893 template<
typename _Key,
typename _Value,
typename _Alloc,
1894 typename _ExtractKey,
typename _Equal,
1895 typename _H1,
typename _H2,
typename _Hash,
1896 typename _RehashPolicy,
typename _Traits>
1898 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1901 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1907 template<
typename _Key,
typename _Value,
typename _Alloc,
1908 typename _ExtractKey,
typename _Equal,
1909 typename _H1,
typename _H2,
typename _Hash,
1910 typename _RehashPolicy,
typename _Traits>
1912 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1913 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1914 _M_equal(
const __hashtable& __other)
const
1916 const __hashtable* __this = static_cast<const __hashtable*>(
this);
1918 if (__this->size() != __other.size())
1921 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1923 const auto __ity = __other.find(_ExtractKey()(*__itx));
1924 if (__ity == __other.end() || !bool(*__ity == *__itx))
1931 template<
typename _Key,
typename _Value,
typename _Alloc,
1932 typename _ExtractKey,
typename _Equal,
1933 typename _H1,
typename _H2,
typename _Hash,
1934 typename _RehashPolicy,
typename _Traits>
1936 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1940 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1946 template<
typename _Key,
typename _Value,
typename _Alloc,
1947 typename _ExtractKey,
typename _Equal,
1948 typename _H1,
typename _H2,
typename _Hash,
1949 typename _RehashPolicy,
typename _Traits>
1951 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1952 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1953 _M_equal(
const __hashtable& __other)
const
1955 const __hashtable* __this = static_cast<const __hashtable*>(
this);
1957 if (__this->size() != __other.size())
1960 for (
auto __itx = __this->begin(); __itx != __this->end();)
1962 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1963 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1969 if (!_S_is_permutation(__xrange.first, __xrange.second,
1973 __itx = __xrange.second;
1982 template<
typename _NodeAlloc>
1983 struct _Hashtable_alloc :
private _Hashtable_ebo_helper<0, _NodeAlloc>
1986 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
1988 using __node_type =
typename _NodeAlloc::value_type;
1989 using __node_alloc_type = _NodeAlloc;
1993 using __value_alloc_traits =
typename __node_alloc_traits::template
1994 rebind_traits<typename __node_type::value_type>;
1996 using __node_base = __detail::_Hash_node_base;
1997 using __bucket_type = __node_base*;
1998 using __bucket_alloc_type =
1999 __alloc_rebind<__node_alloc_type, __bucket_type>;
2002 _Hashtable_alloc() =
default;
2003 _Hashtable_alloc(
const _Hashtable_alloc&) =
default;
2004 _Hashtable_alloc(_Hashtable_alloc&&) =
default;
2006 template<
typename _Alloc>
2007 _Hashtable_alloc(_Alloc&& __a)
2008 : __ebo_node_alloc(
std::
forward<_Alloc>(__a))
2013 {
return __ebo_node_alloc::_M_get(); }
2015 const __node_alloc_type&
2016 _M_node_allocator()
const
2017 {
return __ebo_node_alloc::_M_cget(); }
2020 template<
typename... _Args>
2022 _M_allocate_node(_Args&&... __args);
2026 _M_deallocate_node(__node_type* __n);
2030 _M_deallocate_node_ptr(__node_type* __n);
2035 _M_deallocate_nodes(__node_type* __n);
2038 _M_allocate_buckets(std::size_t __bkt_count);
2041 _M_deallocate_buckets(__bucket_type*, std::size_t __bkt_count);
2046 template<
typename _NodeAlloc>
2047 template<
typename... _Args>
2049 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
2052 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2053 __node_type* __n = std::__to_address(__nptr);
2056 ::new ((
void*)__n) __node_type;
2057 __node_alloc_traits::construct(_M_node_allocator(),
2059 std::forward<_Args>(__args)...);
2064 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2065 __throw_exception_again;
2069 template<
typename _NodeAlloc>
2071 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2073 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2074 _M_deallocate_node_ptr(__n);
2077 template<
typename _NodeAlloc>
2079 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n)
2081 typedef typename __node_alloc_traits::pointer _Ptr;
2083 __n->~__node_type();
2084 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2087 template<
typename _NodeAlloc>
2089 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
2093 __node_type* __tmp = __n;
2094 __n = __n->_M_next();
2095 _M_deallocate_node(__tmp);
2099 template<
typename _NodeAlloc>
2100 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2101 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
2103 __bucket_alloc_type __alloc(_M_node_allocator());
2105 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __bkt_count);
2106 __bucket_type* __p = std::__to_address(__ptr);
2107 __builtin_memset(__p, 0, __bkt_count *
sizeof(__bucket_type));
2111 template<
typename _NodeAlloc>
2113 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2114 std::size_t __bkt_count)
2116 typedef typename __bucket_alloc_traits::pointer _Ptr;
2118 __bucket_alloc_type __alloc(_M_node_allocator());
2119 __bucket_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
2124 _GLIBCXX_END_NAMESPACE_VERSION
2127 #endif // _HASHTABLE_POLICY_H