31#ifndef _HASHTABLE_POLICY_H
32#define _HASHTABLE_POLICY_H 1
38namespace 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>
58 struct _Hashtable_base;
62 template<
class _Iterator>
63 inline typename std::iterator_traits<_Iterator>::difference_type
64 __distance_fw(_Iterator __first, _Iterator __last,
66 {
return __first != __last ? 1 : 0; }
68 template<
class _Iterator>
69 inline typename std::iterator_traits<_Iterator>::difference_type
70 __distance_fw(_Iterator __first, _Iterator __last,
74 template<
class _Iterator>
75 inline typename std::iterator_traits<_Iterator>::difference_type
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>
98 struct _Hashtable_alloc;
102 template<
typename _NodeAlloc>
103 struct _ReuseOrAllocNode
106 using __node_alloc_type = _NodeAlloc;
107 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
108 using __node_alloc_traits =
109 typename __hashtable_alloc::__node_alloc_traits;
110 using __node_type =
typename __hashtable_alloc::__node_type;
113 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
114 : _M_nodes(__nodes), _M_h(__h) { }
115 _ReuseOrAllocNode(
const _ReuseOrAllocNode&) =
delete;
118 { _M_h._M_deallocate_nodes(_M_nodes); }
120 template<
typename _Arg>
122 operator()(_Arg&& __arg)
const
126 __node_type* __node = _M_nodes;
127 _M_nodes = _M_nodes->_M_next();
128 __node->_M_nxt =
nullptr;
129 auto& __a = _M_h._M_node_allocator();
130 __node_alloc_traits::destroy(__a, __node->_M_valptr());
133 __node_alloc_traits::construct(__a, __node->_M_valptr(),
134 std::forward<_Arg>(__arg));
138 __node->~__node_type();
139 __node_alloc_traits::deallocate(__a, __node, 1);
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_ceil(__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); }
512#if __SIZEOF_SIZE_T__ >= 8
513 std::uint_fast64_t __x = __n;
515 std::uint_fast32_t __x = __n;
519 __x = __x | (__x >> 1);
520 __x = __x | (__x >> 2);
521 __x = __x | (__x >> 4);
522 __x = __x | (__x >> 8);
523 __x = __x | (__x >>16);
524#if __SIZEOF_SIZE_T__ >= 8
525 __x = __x | (__x >>32);
537 : _M_max_load_factor(__z), _M_next_resize(0) { }
540 max_load_factor()
const noexcept
541 {
return _M_max_load_factor; }
546 _M_next_bkt(std::size_t __n)
noexcept
548 const auto __max_width = std::min<size_t>(
sizeof(
size_t), 8);
549 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
550 std::size_t __res =
__clp2(__n);
558 if (__res == __max_bkt)
562 _M_next_resize = std::size_t(-1);
565 = __builtin_ceil(__res * (
long double)_M_max_load_factor);
572 _M_bkt_for_elements(std::size_t __n)
const noexcept
573 {
return __builtin_ceil(__n / (
long double)_M_max_load_factor); }
580 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
581 std::size_t __n_ins)
noexcept
583 if (__n_elt + __n_ins >= _M_next_resize)
585 long double __min_bkts = (__n_elt + __n_ins)
586 / (
long double)_M_max_load_factor;
587 if (__min_bkts >= __n_bkt)
589 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
590 __n_bkt * _S_growth_factor)));
593 = __builtin_floor(__n_bkt * (
long double)_M_max_load_factor);
600 typedef std::size_t _State;
603 _M_state()
const noexcept
604 {
return _M_next_resize; }
608 { _M_next_resize = 0; }
611 _M_reset(_State __state)
noexcept
612 { _M_next_resize = __state; }
614 static const std::size_t _S_growth_factor = 2;
616 float _M_max_load_factor;
617 std::size_t _M_next_resize;
638 template<
typename _Key,
typename _Value,
typename _Alloc,
639 typename _ExtractKey,
typename _Equal,
640 typename _H1,
typename _H2,
typename _Hash,
641 typename _RehashPolicy,
typename _Traits,
642 bool _Unique_keys = _Traits::__unique_keys::value>
646 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
647 typename _H1,
typename _H2,
typename _Hash,
648 typename _RehashPolicy,
typename _Traits>
649 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
650 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
656 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
657 typename _H1,
typename _H2,
typename _Hash,
658 typename _RehashPolicy,
typename _Traits>
659 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
660 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
665 _Equal, _H1, _H2, _Hash,
670 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
672 using __hash_code =
typename __hashtable_base::__hash_code;
673 using __node_type =
typename __hashtable_base::__node_type;
676 using key_type =
typename __hashtable_base::key_type;
681 operator[](
const key_type& __k);
684 operator[](key_type&& __k);
689 at(
const key_type& __k);
692 at(
const key_type& __k)
const;
695 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
696 typename _H1,
typename _H2,
typename _Hash,
697 typename _RehashPolicy,
typename _Traits>
699 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
700 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
701 operator[](
const key_type& __k)
704 __hashtable* __h =
static_cast<__hashtable*
>(
this);
705 __hash_code __code = __h->_M_hash_code(__k);
706 std::size_t __n = __h->_M_bucket_index(__k, __code);
707 __node_type* __p = __h->_M_find_node(__n, __k, __code);
714 return __h->_M_insert_unique_node(__n, __code, __p)->second;
717 return __p->_M_v().second;
720 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
721 typename _H1,
typename _H2,
typename _Hash,
722 typename _RehashPolicy,
typename _Traits>
724 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
725 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
726 operator[](key_type&& __k)
729 __hashtable* __h =
static_cast<__hashtable*
>(
this);
730 __hash_code __code = __h->_M_hash_code(__k);
731 std::size_t __n = __h->_M_bucket_index(__k, __code);
732 __node_type* __p = __h->_M_find_node(__n, __k, __code);
737 std::forward_as_tuple(std::move(__k)),
739 return __h->_M_insert_unique_node(__n, __code, __p)->second;
742 return __p->_M_v().second;
745 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
746 typename _H1,
typename _H2,
typename _Hash,
747 typename _RehashPolicy,
typename _Traits>
749 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
750 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
751 at(
const key_type& __k)
754 __hashtable* __h =
static_cast<__hashtable*
>(
this);
755 __hash_code __code = __h->_M_hash_code(__k);
756 std::size_t __n = __h->_M_bucket_index(__k, __code);
757 __node_type* __p = __h->_M_find_node(__n, __k, __code);
760 __throw_out_of_range(__N(
"_Map_base::at"));
761 return __p->_M_v().second;
764 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
765 typename _H1,
typename _H2,
typename _Hash,
766 typename _RehashPolicy,
typename _Traits>
768 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
769 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
770 at(
const key_type& __k)
const
771 ->
const mapped_type&
773 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
774 __hash_code __code = __h->_M_hash_code(__k);
775 std::size_t __n = __h->_M_bucket_index(__k, __code);
776 __node_type* __p = __h->_M_find_node(__n, __k, __code);
779 __throw_out_of_range(__N(
"_Map_base::at"));
780 return __p->_M_v().second;
788 template<
typename _Key,
typename _Value,
typename _Alloc,
789 typename _ExtractKey,
typename _Equal,
790 typename _H1,
typename _H2,
typename _Hash,
791 typename _RehashPolicy,
typename _Traits>
796 _Equal, _H1, _H2, _Hash,
797 _RehashPolicy, _Traits>;
800 _Equal, _H1, _H2, _Hash,
803 using value_type =
typename __hashtable_base::value_type;
806 using size_type =
typename __hashtable_base::size_type;
808 using __unique_keys =
typename __hashtable_base::__unique_keys;
809 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
811 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
812 using __node_gen_type = _AllocNode<__node_alloc_type>;
815 _M_conjure_hashtable()
818 template<
typename _InputIterator,
typename _NodeGetter>
820 _M_insert_range(_InputIterator __first, _InputIterator __last,
823 template<
typename _InputIterator,
typename _NodeGetter>
825 _M_insert_range(_InputIterator __first, _InputIterator __last,
830 insert(
const value_type& __v)
833 __node_gen_type __node_gen(__h);
834 return __h._M_insert(__v, __node_gen, __unique_keys());
838 insert(const_iterator __hint,
const value_type& __v)
841 __node_gen_type __node_gen(__h);
842 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
847 { this->insert(__l.begin(), __l.end()); }
849 template<
typename _InputIterator>
851 insert(_InputIterator __first, _InputIterator __last)
854 __node_gen_type __node_gen(__h);
855 return _M_insert_range(__first, __last, __node_gen, __unique_keys());
859 template<
typename _Key,
typename _Value,
typename _Alloc,
860 typename _ExtractKey,
typename _Equal,
861 typename _H1,
typename _H2,
typename _Hash,
862 typename _RehashPolicy,
typename _Traits>
863 template<
typename _InputIterator,
typename _NodeGetter>
865 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
866 _RehashPolicy, _Traits>::
867 _M_insert_range(_InputIterator __first, _InputIterator __last,
868 const _NodeGetter& __node_gen,
true_type)
870 size_type __n_elt = __detail::__distance_fw(__first, __last);
874 __hashtable& __h = _M_conjure_hashtable();
875 for (; __first != __last; ++__first)
877 if (__h._M_insert(*__first, __node_gen, __unique_keys(),
880 else if (__n_elt != 1)
885 template<
typename _Key,
typename _Value,
typename _Alloc,
886 typename _ExtractKey,
typename _Equal,
887 typename _H1,
typename _H2,
typename _Hash,
888 typename _RehashPolicy,
typename _Traits>
889 template<
typename _InputIterator,
typename _NodeGetter>
891 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
892 _RehashPolicy, _Traits>::
893 _M_insert_range(_InputIterator __first, _InputIterator __last,
896 using __rehash_type =
typename __hashtable::__rehash_type;
897 using __rehash_state =
typename __hashtable::__rehash_state;
900 size_type __n_elt = __detail::__distance_fw(__first, __last);
904 __hashtable& __h = _M_conjure_hashtable();
905 __rehash_type& __rehash = __h._M_rehash_policy;
906 const __rehash_state& __saved_state = __rehash._M_state();
907 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
908 __h._M_element_count,
911 if (__do_rehash.first)
912 __h._M_rehash(__do_rehash.second, __saved_state);
914 for (; __first != __last; ++__first)
915 __h._M_insert(*__first, __node_gen, __unique_keys());
924 template<
typename _Key,
typename _Value,
typename _Alloc,
925 typename _ExtractKey,
typename _Equal,
926 typename _H1,
typename _H2,
typename _Hash,
927 typename _RehashPolicy,
typename _Traits,
928 bool _Constant_iterators = _Traits::__constant_iterators::value>
932 template<
typename _Key,
typename _Value,
typename _Alloc,
933 typename _ExtractKey,
typename _Equal,
934 typename _H1,
typename _H2,
typename _Hash,
935 typename _RehashPolicy,
typename _Traits>
936 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
937 _RehashPolicy, _Traits, true>
938 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
939 _H1, _H2, _Hash, _RehashPolicy, _Traits>
942 _Equal, _H1, _H2, _Hash,
943 _RehashPolicy, _Traits>;
946 _Equal, _H1, _H2, _Hash,
949 using value_type =
typename __base_type::value_type;
950 using iterator =
typename __base_type::iterator;
951 using const_iterator =
typename __base_type::const_iterator;
953 using __unique_keys =
typename __base_type::__unique_keys;
954 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
956 using __node_gen_type =
typename __base_type::__node_gen_type;
958 using __base_type::insert;
961 insert(value_type&& __v)
963 __hashtable& __h = this->_M_conjure_hashtable();
964 __node_gen_type __node_gen(__h);
965 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
969 insert(const_iterator __hint, value_type&& __v)
971 __hashtable& __h = this->_M_conjure_hashtable();
972 __node_gen_type __node_gen(__h);
973 return __h._M_insert(__hint, std::move(__v), __node_gen,
979 template<
typename _Key,
typename _Value,
typename _Alloc,
980 typename _ExtractKey,
typename _Equal,
981 typename _H1,
typename _H2,
typename _Hash,
982 typename _RehashPolicy,
typename _Traits>
983 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
984 _RehashPolicy, _Traits, false>
985 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
986 _H1, _H2, _Hash, _RehashPolicy, _Traits>
989 _Equal, _H1, _H2, _Hash,
990 _RehashPolicy, _Traits>;
991 using value_type =
typename __base_type::value_type;
992 using iterator =
typename __base_type::iterator;
993 using const_iterator =
typename __base_type::const_iterator;
995 using __unique_keys =
typename __base_type::__unique_keys;
997 using __ireturn_type =
typename __base_type::__ireturn_type;
999 using __base_type::insert;
1001 template<
typename _Pair>
1004 template<
typename _Pair>
1007 template<
typename _Pair>
1010 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1014 __hashtable& __h = this->_M_conjure_hashtable();
1015 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1018 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1020 insert(const_iterator __hint, _Pair&& __v)
1022 __hashtable& __h = this->_M_conjure_hashtable();
1023 return __h._M_emplace(__hint, __unique_keys(),
1024 std::forward<_Pair>(__v));
1028 template<
typename _Policy>
1029 using __has_load_factor =
typename _Policy::__has_load_factor;
1037 template<
typename _Key,
typename _Value,
typename _Alloc,
1038 typename _ExtractKey,
typename _Equal,
1039 typename _H1,
typename _H2,
typename _Hash,
1040 typename _RehashPolicy,
typename _Traits,
1042 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
1046 template<
typename _Key,
typename _Value,
typename _Alloc,
1047 typename _ExtractKey,
typename _Equal,
1048 typename _H1,
typename _H2,
typename _Hash,
1049 typename _RehashPolicy,
typename _Traits>
1051 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1057 template<
typename _Key,
typename _Value,
typename _Alloc,
1058 typename _ExtractKey,
typename _Equal,
1059 typename _H1,
typename _H2,
typename _Hash,
1060 typename _RehashPolicy,
typename _Traits>
1062 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1066 _Equal, _H1, _H2, _Hash,
1067 _RehashPolicy, _Traits>;
1070 max_load_factor()
const noexcept
1073 return __this->__rehash_policy().max_load_factor();
1077 max_load_factor(
float __z)
1080 __this->__rehash_policy(_RehashPolicy(__z));
1084 reserve(std::size_t __n)
1087 __this->rehash(__builtin_ceil(__n / max_load_factor()));
1097 template<
int _Nm,
typename _Tp,
1098 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1102 template<
int _Nm,
typename _Tp>
1108 template<
typename _OtherTp>
1110 : _Tp(std::forward<_OtherTp>(__tp))
1115 {
return static_cast<const _Tp&
>(__eboh); }
1119 {
return static_cast<_Tp&
>(__eboh); }
1123 template<
int _Nm,
typename _Tp>
1128 template<
typename _OtherTp>
1130 : _M_tp(std::forward<_OtherTp>(__tp))
1135 {
return __eboh._M_tp; }
1139 {
return __eboh._M_tp; }
1151 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1152 typename _H1,
typename _H2,
typename _Hash,
1153 bool __cache_hash_code>
1176 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1177 typename _H1,
typename _H2,
typename _Hash,
1178 bool __cache_hash_code>
1183 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1184 typename _H1,
typename _H2,
typename _Hash>
1194 typedef void* __hash_code;
1206 _M_hash_code(
const _Key& __key)
const
1210 _M_bucket_index(
const _Key& __k, __hash_code, std::size_t __n)
const
1211 {
return _M_ranged_hash()(__k, __n); }
1214 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1215 noexcept(
noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1217 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1230 std::swap(_M_extract(), __x._M_extract());
1231 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1235 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1238 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1241 _M_ranged_hash()
const {
return __ebo_hash::_S_cget(*
this); }
1244 _M_ranged_hash() {
return __ebo_hash::_S_get(*
this); }
1253 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1254 typename _H1,
typename _H2,
typename _Hash>
1255 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1260 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1261 typename _H1,
typename _H2>
1281 hash_function()
const
1285 typedef std::size_t __hash_code;
1293 const _H1& __h1,
const _H2& __h2,
1298 _M_hash_code(
const _Key& __k)
const
1300 static_assert(__is_invocable<const _H1&, const _Key&>{},
1301 "hash function must be invocable with an argument of key type");
1302 return _M_h1()(__k);
1306 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const
1307 {
return _M_h2()(__c, __n); }
1310 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1311 noexcept(
noexcept(declval<const _H1&>()(declval<const _Key&>()))
1312 &&
noexcept(declval<const _H2&>()((__hash_code)0,
1314 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1327 std::swap(_M_extract(), __x._M_extract());
1328 std::swap(_M_h1(), __x._M_h1());
1329 std::swap(_M_h2(), __x._M_h2());
1333 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1336 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1339 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1342 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1345 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1348 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1354 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1355 typename _H1,
typename _H2>
1375 hash_function()
const
1379 typedef std::size_t __hash_code;
1385 const _H1& __h1,
const _H2& __h2,
1390 _M_hash_code(
const _Key& __k)
const
1392 static_assert(__is_invocable<const _H1&, const _Key&>{},
1393 "hash function must be invocable with an argument of key type");
1394 return _M_h1()(__k);
1398 _M_bucket_index(
const _Key&, __hash_code __c,
1399 std::size_t __n)
const
1400 {
return _M_h2()(__c, __n); }
1403 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1404 noexcept(
noexcept(declval<const _H2&>()((__hash_code)0,
1406 {
return _M_h2()(__p->_M_hash_code, __n); }
1409 _M_store_code(
__node_type* __n, __hash_code __c)
const
1410 { __n->_M_hash_code = __c; }
1414 { __to->_M_hash_code = __from->_M_hash_code; }
1419 std::swap(_M_extract(), __x._M_extract());
1420 std::swap(_M_h1(), __x._M_h1());
1421 std::swap(_M_h2(), __x._M_h2());
1425 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1428 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1431 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1434 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1437 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1440 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1447 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1448 typename _Equal,
typename _HashCodeType,
1449 bool __cache_hash_code>
1453 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1454 typename _Equal,
typename _HashCodeType>
1458 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1460 {
return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1464 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1465 typename _Equal,
typename _HashCodeType>
1469 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1471 {
return __eq(__k, __extract(__n->_M_v())); }
1476 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1477 typename _H1,
typename _H2,
typename _Hash>
1479 _H1, _H2, _Hash, true>
1485 _H1, _H2, _Hash,
true>;
1490 std::size_t __bkt, std::size_t __bkt_count)
1492 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1497 _M_cur = _M_cur->_M_next();
1501 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1503 if (__bkt != _M_bucket)
1509 std::size_t _M_bucket;
1510 std::size_t _M_bucket_count;
1514 _M_curr()
const {
return _M_cur; }
1517 _M_get_bucket()
const {
return _M_bucket; }
1524 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1525 struct _Hash_code_storage
1527 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1530 _M_h() {
return _M_storage._M_ptr(); }
1533 _M_h()
const {
return _M_storage._M_ptr(); }
1537 template<
typename _Tp>
1538 struct _Hash_code_storage<_Tp, true>
1545 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1548 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1551 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1552 typename _H1,
typename _H2,
typename _Hash>
1553 using __hash_code_for_local_iter
1554 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1555 _H1, _H2, _Hash,
false>>;
1558 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1559 typename _H1,
typename _H2,
typename _Hash>
1560 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1561 _H1, _H2, _Hash, false>
1562 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1565 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1566 _H1, _H2, _Hash,
false>;
1568 _Local_iterator_base() : _M_bucket_count(-1) { }
1570 _Local_iterator_base(
const __hash_code_base& __base,
1571 _Hash_node<_Value, false>* __p,
1572 std::size_t __bkt, std::size_t __bkt_count)
1573 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1574 { _M_init(__base); }
1576 ~_Local_iterator_base()
1578 if (_M_bucket_count != -1)
1582 _Local_iterator_base(
const _Local_iterator_base& __iter)
1583 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1584 _M_bucket_count(__iter._M_bucket_count)
1586 if (_M_bucket_count != -1)
1587 _M_init(*__iter._M_h());
1590 _Local_iterator_base&
1591 operator=(
const _Local_iterator_base& __iter)
1593 if (_M_bucket_count != -1)
1595 _M_cur = __iter._M_cur;
1596 _M_bucket = __iter._M_bucket;
1597 _M_bucket_count = __iter._M_bucket_count;
1598 if (_M_bucket_count != -1)
1599 _M_init(*__iter._M_h());
1606 _M_cur = _M_cur->_M_next();
1609 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1611 if (__bkt != _M_bucket)
1616 _Hash_node<_Value, false>* _M_cur;
1617 std::size_t _M_bucket;
1618 std::size_t _M_bucket_count;
1621 _M_init(
const __hash_code_base& __base)
1622 { ::new(this->_M_h()) __hash_code_base(__base); }
1625 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1629 _M_curr()
const {
return _M_cur; }
1632 _M_get_bucket()
const {
return _M_bucket; }
1635 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1636 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1638 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1639 _H1, _H2, _Hash, __cache>& __x,
1640 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1641 _H1, _H2, _Hash, __cache>& __y)
1642 {
return __x._M_curr() == __y._M_curr(); }
1644 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1645 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1647 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1648 _H1, _H2, _Hash, __cache>& __x,
1649 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1650 _H1, _H2, _Hash, __cache>& __y)
1651 {
return __x._M_curr() != __y._M_curr(); }
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;
1666 typedef _Value value_type;
1668 const _Value*, _Value*>::type
1671 const _Value&, _Value&>::type
1673 typedef std::ptrdiff_t difference_type;
1680 std::size_t __bkt, std::size_t __bkt_count)
1686 {
return this->_M_cur->_M_v(); }
1690 {
return this->_M_cur->_M_valptr(); }
1709 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1710 typename _H1,
typename _H2,
typename _Hash,
1711 bool __constant_iterators,
bool __cache>
1714 _H1, _H2, _Hash, __cache>
1718 _H1, _H2, _Hash, __cache>;
1719 using __hash_code_base =
typename __base_type::__hash_code_base;
1722 typedef _Value value_type;
1723 typedef const _Value* pointer;
1724 typedef const _Value& reference;
1725 typedef std::ptrdiff_t difference_type;
1732 std::size_t __bkt, std::size_t __bkt_count)
1738 __constant_iterators,
1745 {
return this->_M_cur->_M_v(); }
1749 {
return this->_M_cur->_M_valptr(); }
1777 template<
typename _Key,
typename _Value,
1778 typename _ExtractKey,
typename _Equal,
1779 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1782 _Traits::__hash_cached::value>,
1786 typedef _Key key_type;
1787 typedef _Value value_type;
1788 typedef _Equal key_equal;
1789 typedef std::size_t size_type;
1790 typedef std::ptrdiff_t difference_type;
1792 using __traits_type = _Traits;
1793 using __hash_cached =
typename __traits_type::__hash_cached;
1794 using __constant_iterators =
typename __traits_type::__constant_iterators;
1795 using __unique_keys =
typename __traits_type::__unique_keys;
1799 __hash_cached::value>;
1801 using __hash_code =
typename __hash_code_base::__hash_code;
1802 using __node_type =
typename __hash_code_base::__node_type;
1805 __constant_iterators::value,
1806 __hash_cached::value>;
1809 __constant_iterators::value,
1810 __hash_cached::value>;
1813 _ExtractKey, _H1, _H2, _Hash,
1814 __constant_iterators::value,
1815 __hash_cached::value>;
1819 _ExtractKey, _H1, _H2, _Hash,
1820 __constant_iterators::value,
1821 __hash_cached::value>;
1829 __hash_code, __hash_cached::value>;
1833 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1834 const _Hash& __hash,
const _Equal& __eq)
1839 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const
1841 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1842 "key equality predicate must be invocable with two arguments of "
1844 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1851 __hash_code_base::_M_swap(__x);
1852 std::swap(_M_eq(), __x._M_eq());
1856 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1859 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1870 template<
typename _Uiterator>
1872 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1876 template<
typename _Uiterator>
1879 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1880 _Uiterator __first2)
1882 for (; __first1 != __last1; ++__first1, ++__first2)
1883 if (!(*__first1 == *__first2))
1886 if (__first1 == __last1)
1889 _Uiterator __last2 = __first2;
1892 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1894 _Uiterator __tmp = __first1;
1895 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1902 std::ptrdiff_t __n2 = 0;
1903 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1904 if (*__tmp == *__it1)
1910 std::ptrdiff_t __n1 = 0;
1911 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1912 if (*__tmp == *__it1)
1929 template<
typename _Key,
typename _Value,
typename _Alloc,
1930 typename _ExtractKey,
typename _Equal,
1931 typename _H1,
typename _H2,
typename _Hash,
1932 typename _RehashPolicy,
typename _Traits,
1933 bool _Unique_keys = _Traits::__unique_keys::value>
1937 template<
typename _Key,
typename _Value,
typename _Alloc,
1938 typename _ExtractKey,
typename _Equal,
1939 typename _H1,
typename _H2,
typename _Hash,
1940 typename _RehashPolicy,
typename _Traits>
1942 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1945 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1951 template<
typename _Key,
typename _Value,
typename _Alloc,
1952 typename _ExtractKey,
typename _Equal,
1953 typename _H1,
typename _H2,
typename _Hash,
1954 typename _RehashPolicy,
typename _Traits>
1956 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1957 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1958 _M_equal(
const __hashtable& __other)
const
1960 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1962 if (__this->size() != __other.size())
1965 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1967 const auto __ity = __other.find(_ExtractKey()(*__itx));
1968 if (__ity == __other.end() || !bool(*__ity == *__itx))
1975 template<
typename _Key,
typename _Value,
typename _Alloc,
1976 typename _ExtractKey,
typename _Equal,
1977 typename _H1,
typename _H2,
typename _Hash,
1978 typename _RehashPolicy,
typename _Traits>
1980 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1984 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1990 template<
typename _Key,
typename _Value,
typename _Alloc,
1991 typename _ExtractKey,
typename _Equal,
1992 typename _H1,
typename _H2,
typename _Hash,
1993 typename _RehashPolicy,
typename _Traits>
1995 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1996 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1997 _M_equal(
const __hashtable& __other)
const
1999 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
2001 if (__this->size() != __other.size())
2004 for (
auto __itx = __this->begin(); __itx != __this->end();)
2006 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
2007 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
2013 if (!_S_is_permutation(__xrange.first, __xrange.second,
2017 __itx = __xrange.second;
2026 template<
typename _NodeAlloc>
2032 using __node_type =
typename _NodeAlloc::value_type;
2033 using __node_alloc_type = _NodeAlloc;
2037 using __value_alloc_traits =
typename __node_alloc_traits::template
2038 rebind_traits<typename __node_type::value_type>;
2042 using __bucket_alloc_type =
2043 __alloc_rebind<__node_alloc_type, __bucket_type>;
2050 template<
typename _Alloc>
2057 {
return __ebo_node_alloc::_S_get(*
this); }
2059 const __node_alloc_type&
2060 _M_node_allocator()
const
2061 {
return __ebo_node_alloc::_S_cget(*
this); }
2063 template<
typename... _Args>
2065 _M_allocate_node(_Args&&... __args);
2068 _M_deallocate_node(__node_type* __n);
2072 _M_deallocate_nodes(__node_type* __n);
2075 _M_allocate_buckets(std::size_t __n);
2083 template<
typename _NodeAlloc>
2084 template<
typename... _Args>
2085 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
2088 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2089 __node_type* __n = std::__to_address(__nptr);
2092 ::new ((
void*)__n) __node_type;
2093 __node_alloc_traits::construct(_M_node_allocator(),
2095 std::forward<_Args>(__args)...);
2100 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2101 __throw_exception_again;
2105 template<
typename _NodeAlloc>
2107 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2109 typedef typename __node_alloc_traits::pointer _Ptr;
2111 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2112 __n->~__node_type();
2113 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2116 template<
typename _NodeAlloc>
2118 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
2122 __node_type* __tmp = __n;
2123 __n = __n->_M_next();
2124 _M_deallocate_node(__tmp);
2128 template<
typename _NodeAlloc>
2129 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2130 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n)
2132 __bucket_alloc_type __alloc(_M_node_allocator());
2134 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
2135 __bucket_type* __p = std::__to_address(__ptr);
2136 __builtin_memset(__p, 0, __n *
sizeof(__bucket_type));
2140 template<
typename _NodeAlloc>
2142 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2145 typedef typename __bucket_alloc_traits::pointer _Ptr;
2147 __bucket_alloc_type __alloc(_M_node_allocator());
2148 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
2153_GLIBCXX_END_NAMESPACE_VERSION
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
_GLIBCXX14_CONSTEXPR std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Primary class template, tuple.
Define a member typedef type to one of two argument types.
Define a member typedef type only if a boolean constant is true.
Uniform interface to all allocator types.
Base class for node iterators.
Node iterators, used to iterate through all the hashtable.
Node const_iterators, used to iterate through all the hashtable.
Default range hashing function: use division to fold a large number into the range [0,...
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Range hashing function assuming that second arg is a power of 2.
Rehash policy providing power of 2 bucket numbers. Avoids modulo operations.
Uniform interface to all pointer-like types.
Forward iterators support a superset of input iterator operations.
Struct holding two objects of arbitrary type.
Uniform interface to C++98 and C++11 allocators.