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>
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>
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 __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)
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)
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>>
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)
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 1299 {
return _M_h1()(__k); }
1302 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const 1303 {
return _M_h2()(__c, __n); }
1306 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const 1307 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1308 && noexcept(declval<const _H2&>()((__hash_code)0,
1310 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1323 std::swap(_M_extract(), __x._M_extract());
1324 std::swap(_M_h1(), __x._M_h1());
1325 std::swap(_M_h2(), __x._M_h2());
1329 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1332 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1335 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1338 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1341 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1344 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1350 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1351 typename _H1,
typename _H2>
1371 hash_function()
const 1375 typedef std::size_t __hash_code;
1381 const _H1& __h1,
const _H2& __h2,
1386 _M_hash_code(
const _Key& __k)
const 1387 {
return _M_h1()(__k); }
1390 _M_bucket_index(
const _Key&, __hash_code __c,
1391 std::size_t __n)
const 1392 {
return _M_h2()(__c, __n); }
1395 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const 1396 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1398 {
return _M_h2()(__p->_M_hash_code, __n); }
1401 _M_store_code(
__node_type* __n, __hash_code __c)
const 1402 { __n->_M_hash_code = __c; }
1406 { __to->_M_hash_code = __from->_M_hash_code; }
1411 std::swap(_M_extract(), __x._M_extract());
1412 std::swap(_M_h1(), __x._M_h1());
1413 std::swap(_M_h2(), __x._M_h2());
1417 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1420 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1423 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1426 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1429 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1432 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1439 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1440 typename _Equal,
typename _HashCodeType,
1441 bool __cache_hash_code>
1445 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1446 typename _Equal,
typename _HashCodeType>
1450 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1452 {
return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1456 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1457 typename _Equal,
typename _HashCodeType>
1461 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1463 {
return __eq(__k, __extract(__n->_M_v())); }
1468 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1469 typename _H1,
typename _H2,
typename _Hash>
1471 _H1, _H2, _Hash, true>
1477 _H1, _H2, _Hash,
true>;
1482 std::size_t __bkt, std::size_t __bkt_count)
1484 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1489 _M_cur = _M_cur->_M_next();
1493 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1495 if (__bkt != _M_bucket)
1501 std::size_t _M_bucket;
1502 std::size_t _M_bucket_count;
1506 _M_curr()
const {
return _M_cur; }
1509 _M_get_bucket()
const {
return _M_bucket; }
1516 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1517 struct _Hash_code_storage
1519 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1522 _M_h() {
return _M_storage._M_ptr(); }
1525 _M_h()
const {
return _M_storage._M_ptr(); }
1529 template<
typename _Tp>
1530 struct _Hash_code_storage<_Tp, true>
1537 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1540 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1543 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1544 typename _H1,
typename _H2,
typename _Hash>
1545 using __hash_code_for_local_iter
1546 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1547 _H1, _H2, _Hash,
false>>;
1550 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1551 typename _H1,
typename _H2,
typename _Hash>
1552 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1553 _H1, _H2, _Hash, false>
1554 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1557 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1558 _H1, _H2, _Hash,
false>;
1560 _Local_iterator_base() : _M_bucket_count(-1) { }
1562 _Local_iterator_base(
const __hash_code_base& __base,
1563 _Hash_node<_Value, false>* __p,
1564 std::size_t __bkt, std::size_t __bkt_count)
1565 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1566 { _M_init(__base); }
1568 ~_Local_iterator_base()
1570 if (_M_bucket_count != -1)
1574 _Local_iterator_base(
const _Local_iterator_base& __iter)
1575 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1576 _M_bucket_count(__iter._M_bucket_count)
1578 if (_M_bucket_count != -1)
1579 _M_init(*__iter._M_h());
1582 _Local_iterator_base&
1583 operator=(
const _Local_iterator_base& __iter)
1585 if (_M_bucket_count != -1)
1587 _M_cur = __iter._M_cur;
1588 _M_bucket = __iter._M_bucket;
1589 _M_bucket_count = __iter._M_bucket_count;
1590 if (_M_bucket_count != -1)
1591 _M_init(*__iter._M_h());
1598 _M_cur = _M_cur->_M_next();
1601 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1603 if (__bkt != _M_bucket)
1608 _Hash_node<_Value, false>* _M_cur;
1609 std::size_t _M_bucket;
1610 std::size_t _M_bucket_count;
1613 _M_init(
const __hash_code_base& __base)
1614 { ::new(this->_M_h()) __hash_code_base(__base); }
1617 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1621 _M_curr()
const {
return _M_cur; }
1624 _M_get_bucket()
const {
return _M_bucket; }
1627 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1628 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1630 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1631 _H1, _H2, _Hash, __cache>& __x,
1632 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1633 _H1, _H2, _Hash, __cache>& __y)
1634 {
return __x._M_curr() == __y._M_curr(); }
1636 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1637 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1639 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1640 _H1, _H2, _Hash, __cache>& __x,
1641 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1642 _H1, _H2, _Hash, __cache>& __y)
1643 {
return __x._M_curr() != __y._M_curr(); }
1646 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1647 typename _H1,
typename _H2,
typename _Hash,
1648 bool __constant_iterators,
bool __cache>
1651 _H1, _H2, _Hash, __cache>
1655 _H1, _H2, _Hash, __cache>;
1656 using __hash_code_base =
typename __base_type::__hash_code_base;
1658 typedef _Value value_type;
1660 const _Value*, _Value*>::type
1663 const _Value&, _Value&>::type
1665 typedef std::ptrdiff_t difference_type;
1672 std::size_t __bkt, std::size_t __bkt_count)
1678 {
return this->_M_cur->_M_v(); }
1682 {
return this->_M_cur->_M_valptr(); }
1701 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1702 typename _H1,
typename _H2,
typename _Hash,
1703 bool __constant_iterators,
bool __cache>
1706 _H1, _H2, _Hash, __cache>
1710 _H1, _H2, _Hash, __cache>;
1711 using __hash_code_base =
typename __base_type::__hash_code_base;
1714 typedef _Value value_type;
1715 typedef const _Value* pointer;
1716 typedef const _Value& reference;
1717 typedef std::ptrdiff_t difference_type;
1724 std::size_t __bkt, std::size_t __bkt_count)
1730 __constant_iterators,
1737 {
return this->_M_cur->_M_v(); }
1741 {
return this->_M_cur->_M_valptr(); }
1769 template<
typename _Key,
typename _Value,
1770 typename _ExtractKey,
typename _Equal,
1771 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1774 _Traits::__hash_cached::value>,
1778 typedef _Key key_type;
1779 typedef _Value value_type;
1780 typedef _Equal key_equal;
1781 typedef std::size_t size_type;
1782 typedef std::ptrdiff_t difference_type;
1784 using __traits_type = _Traits;
1785 using __hash_cached =
typename __traits_type::__hash_cached;
1786 using __constant_iterators =
typename __traits_type::__constant_iterators;
1787 using __unique_keys =
typename __traits_type::__unique_keys;
1791 __hash_cached::value>;
1793 using __hash_code =
typename __hash_code_base::__hash_code;
1794 using __node_type =
typename __hash_code_base::__node_type;
1797 __constant_iterators::value,
1798 __hash_cached::value>;
1801 __constant_iterators::value,
1802 __hash_cached::value>;
1805 _ExtractKey, _H1, _H2, _Hash,
1806 __constant_iterators::value,
1807 __hash_cached::value>;
1811 _ExtractKey, _H1, _H2, _Hash,
1812 __constant_iterators::value,
1813 __hash_cached::value>;
1820 using _EqualHelper =
_Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1821 __hash_code, __hash_cached::value>;
1825 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1826 const _Hash& __hash,
const _Equal& __eq)
1827 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1831 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const 1833 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1838 _M_swap(_Hashtable_base& __x)
1840 __hash_code_base::_M_swap(__x);
1841 std::swap(_M_eq(), __x._M_eq());
1845 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1848 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1859 template<
typename _Uiterator>
1861 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1865 template<
typename _Uiterator>
1868 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1869 _Uiterator __first2)
1871 for (; __first1 != __last1; ++__first1, ++__first2)
1872 if (!(*__first1 == *__first2))
1875 if (__first1 == __last1)
1878 _Uiterator __last2 = __first2;
1881 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1883 _Uiterator __tmp = __first1;
1884 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1891 std::ptrdiff_t __n2 = 0;
1892 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1893 if (*__tmp == *__it1)
1899 std::ptrdiff_t __n1 = 0;
1900 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1901 if (*__tmp == *__it1)
1918 template<
typename _Key,
typename _Value,
typename _Alloc,
1919 typename _ExtractKey,
typename _Equal,
1920 typename _H1,
typename _H2,
typename _Hash,
1921 typename _RehashPolicy,
typename _Traits,
1922 bool _Unique_keys = _Traits::__unique_keys::value>
1926 template<
typename _Key,
typename _Value,
typename _Alloc,
1927 typename _ExtractKey,
typename _Equal,
1928 typename _H1,
typename _H2,
typename _Hash,
1929 typename _RehashPolicy,
typename _Traits>
1931 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1934 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1940 template<
typename _Key,
typename _Value,
typename _Alloc,
1941 typename _ExtractKey,
typename _Equal,
1942 typename _H1,
typename _H2,
typename _Hash,
1943 typename _RehashPolicy,
typename _Traits>
1945 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1946 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1947 _M_equal(
const __hashtable& __other)
const 1949 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1951 if (__this->size() != __other.size())
1954 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1956 const auto __ity = __other.find(_ExtractKey()(*__itx));
1957 if (__ity == __other.end() || !bool(*__ity == *__itx))
1964 template<
typename _Key,
typename _Value,
typename _Alloc,
1965 typename _ExtractKey,
typename _Equal,
1966 typename _H1,
typename _H2,
typename _Hash,
1967 typename _RehashPolicy,
typename _Traits>
1969 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1973 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1979 template<
typename _Key,
typename _Value,
typename _Alloc,
1980 typename _ExtractKey,
typename _Equal,
1981 typename _H1,
typename _H2,
typename _Hash,
1982 typename _RehashPolicy,
typename _Traits>
1984 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1985 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1986 _M_equal(
const __hashtable& __other)
const 1988 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1990 if (__this->size() != __other.size())
1993 for (
auto __itx = __this->begin(); __itx != __this->end();)
1995 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1996 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
2002 if (!_S_is_permutation(__xrange.first, __xrange.second,
2006 __itx = __xrange.second;
2015 template<
typename _NodeAlloc>
2016 struct _Hashtable_alloc :
private _Hashtable_ebo_helper<0, _NodeAlloc>
2019 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
2021 using __node_type =
typename _NodeAlloc::value_type;
2022 using __node_alloc_type = _NodeAlloc;
2026 using __value_alloc_traits =
typename __node_alloc_traits::template
2027 rebind_traits<typename __node_type::value_type>;
2029 using __node_base = __detail::_Hash_node_base;
2030 using __bucket_type = __node_base*;
2031 using __bucket_alloc_type =
2032 __alloc_rebind<__node_alloc_type, __bucket_type>;
2035 _Hashtable_alloc() =
default;
2036 _Hashtable_alloc(
const _Hashtable_alloc&) =
default;
2037 _Hashtable_alloc(_Hashtable_alloc&&) =
default;
2039 template<
typename _Alloc>
2040 _Hashtable_alloc(_Alloc&& __a)
2041 : __ebo_node_alloc(
std::
forward<_Alloc>(__a))
2046 {
return __ebo_node_alloc::_S_get(*
this); }
2048 const __node_alloc_type&
2049 _M_node_allocator()
const 2050 {
return __ebo_node_alloc::_S_cget(*
this); }
2052 template<
typename... _Args>
2054 _M_allocate_node(_Args&&... __args);
2057 _M_deallocate_node(__node_type* __n);
2061 _M_deallocate_nodes(__node_type* __n);
2064 _M_allocate_buckets(std::size_t __n);
2067 _M_deallocate_buckets(__bucket_type*, std::size_t __n);
2072 template<
typename _NodeAlloc>
2073 template<
typename... _Args>
2074 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
2075 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
2077 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2078 __node_type* __n = std::__to_address(__nptr);
2081 ::new ((
void*)__n) __node_type;
2082 __node_alloc_traits::construct(_M_node_allocator(),
2084 std::forward<_Args>(__args)...);
2089 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2090 __throw_exception_again;
2094 template<
typename _NodeAlloc>
2096 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2098 typedef typename __node_alloc_traits::pointer _Ptr;
2100 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2101 __n->~__node_type();
2102 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2105 template<
typename _NodeAlloc>
2107 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
2111 __node_type* __tmp = __n;
2112 __n = __n->_M_next();
2113 _M_deallocate_node(__tmp);
2117 template<
typename _NodeAlloc>
2118 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
2119 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n)
2121 __bucket_alloc_type __alloc(_M_node_allocator());
2123 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
2124 __bucket_type* __p = std::__to_address(__ptr);
2125 __builtin_memset(__p, 0, __n *
sizeof(__bucket_type));
2129 template<
typename _NodeAlloc>
2131 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2134 typedef typename __bucket_alloc_traits::pointer _Ptr;
2136 __bucket_alloc_type __alloc(_M_node_allocator());
2137 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
2142 _GLIBCXX_END_NAMESPACE_VERSION
2145 #endif // _HASHTABLE_POLICY_H
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Primary class template, tuple.
_GLIBCXX14_CONSTEXPR std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2.
Define a member typedef type only if a boolean constant is true.
Define a member typedef type to one of two argument types.
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.
Uniform interface to all allocator types.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Node const_iterators, used to iterate through all the hashtable.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
ISO C++ entities toplevel namespace is std.
Uniform interface to C++98 and C++11 allocators.
Rehash policy providing power of 2 bucket numbers. Avoids modulo operations.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Node iterators, used to iterate through all the hashtable.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Struct holding two objects of arbitrary type.
Forward iterators support a superset of input iterator operations.
Range hashing function assuming that second arg is a power of 2.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
Default range hashing function: use division to fold a large number into the range [0...
Uniform interface to all pointer-like types.
Base class for node iterators.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.