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 _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_ceil(__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
538 const auto __max_width = std::min<size_t>(
sizeof(
size_t), 8);
539 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
540 std::size_t __res =
__clp2(__n);
548 if (__res == __max_bkt)
552 _M_next_resize = std::size_t(-1);
555 = __builtin_ceil(__res * (
long double)_M_max_load_factor);
562 _M_bkt_for_elements(std::size_t __n)
const noexcept
563 {
return __builtin_ceil(__n / (
long double)_M_max_load_factor); }
570 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
571 std::size_t __n_ins)
noexcept
573 if (__n_elt + __n_ins >= _M_next_resize)
575 long double __min_bkts = (__n_elt + __n_ins)
576 / (
long double)_M_max_load_factor;
577 if (__min_bkts >= __n_bkt)
579 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
580 __n_bkt * _S_growth_factor)));
583 = __builtin_floor(__n_bkt * (
long double)_M_max_load_factor);
590 typedef std::size_t _State;
593 _M_state()
const noexcept
594 {
return _M_next_resize; }
598 { _M_next_resize = 0; }
601 _M_reset(_State __state)
noexcept
602 { _M_next_resize = __state; }
604 static const std::size_t _S_growth_factor = 2;
606 float _M_max_load_factor;
607 std::size_t _M_next_resize;
628 template<
typename _Key,
typename _Value,
typename _Alloc,
629 typename _ExtractKey,
typename _Equal,
630 typename _H1,
typename _H2,
typename _Hash,
631 typename _RehashPolicy,
typename _Traits,
632 bool _Unique_keys = _Traits::__unique_keys::value>
636 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
637 typename _H1,
typename _H2,
typename _Hash,
638 typename _RehashPolicy,
typename _Traits>
639 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
640 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
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, true>
655 _Equal, _H1, _H2, _Hash,
660 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
662 using __hash_code =
typename __hashtable_base::__hash_code;
663 using __node_type =
typename __hashtable_base::__node_type;
666 using key_type =
typename __hashtable_base::key_type;
671 operator[](
const key_type& __k);
674 operator[](key_type&& __k);
679 at(
const key_type& __k);
682 at(
const key_type& __k)
const;
685 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
686 typename _H1,
typename _H2,
typename _Hash,
687 typename _RehashPolicy,
typename _Traits>
689 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
690 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
691 operator[](
const key_type& __k)
694 __hashtable* __h =
static_cast<__hashtable*
>(
this);
695 __hash_code __code = __h->_M_hash_code(__k);
696 std::size_t __n = __h->_M_bucket_index(__k, __code);
697 __node_type* __p = __h->_M_find_node(__n, __k, __code);
704 return __h->_M_insert_unique_node(__n, __code, __p)->second;
707 return __p->_M_v().second;
710 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
711 typename _H1,
typename _H2,
typename _Hash,
712 typename _RehashPolicy,
typename _Traits>
714 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
715 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
716 operator[](key_type&& __k)
719 __hashtable* __h =
static_cast<__hashtable*
>(
this);
720 __hash_code __code = __h->_M_hash_code(__k);
721 std::size_t __n = __h->_M_bucket_index(__k, __code);
722 __node_type* __p = __h->_M_find_node(__n, __k, __code);
729 return __h->_M_insert_unique_node(__n, __code, __p)->second;
732 return __p->_M_v().second;
735 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
736 typename _H1,
typename _H2,
typename _Hash,
737 typename _RehashPolicy,
typename _Traits>
739 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
740 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
741 at(
const key_type& __k)
744 __hashtable* __h =
static_cast<__hashtable*
>(
this);
745 __hash_code __code = __h->_M_hash_code(__k);
746 std::size_t __n = __h->_M_bucket_index(__k, __code);
747 __node_type* __p = __h->_M_find_node(__n, __k, __code);
750 __throw_out_of_range(__N(
"_Map_base::at"));
751 return __p->_M_v().second;
754 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
755 typename _H1,
typename _H2,
typename _Hash,
756 typename _RehashPolicy,
typename _Traits>
758 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
759 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
760 at(
const key_type& __k)
const
761 ->
const mapped_type&
763 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
764 __hash_code __code = __h->_M_hash_code(__k);
765 std::size_t __n = __h->_M_bucket_index(__k, __code);
766 __node_type* __p = __h->_M_find_node(__n, __k, __code);
769 __throw_out_of_range(__N(
"_Map_base::at"));
770 return __p->_M_v().second;
778 template<
typename _Key,
typename _Value,
typename _Alloc,
779 typename _ExtractKey,
typename _Equal,
780 typename _H1,
typename _H2,
typename _Hash,
781 typename _RehashPolicy,
typename _Traits>
786 _Equal, _H1, _H2, _Hash,
787 _RehashPolicy, _Traits>;
790 _Equal, _H1, _H2, _Hash,
793 using value_type =
typename __hashtable_base::value_type;
796 using size_type =
typename __hashtable_base::size_type;
798 using __unique_keys =
typename __hashtable_base::__unique_keys;
799 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
801 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
802 using __node_gen_type = _AllocNode<__node_alloc_type>;
805 _M_conjure_hashtable()
808 template<
typename _InputIterator,
typename _NodeGetter>
810 _M_insert_range(_InputIterator __first, _InputIterator __last,
813 template<
typename _InputIterator,
typename _NodeGetter>
815 _M_insert_range(_InputIterator __first, _InputIterator __last,
820 insert(
const value_type& __v)
823 __node_gen_type __node_gen(__h);
824 return __h._M_insert(__v, __node_gen, __unique_keys());
828 insert(const_iterator __hint,
const value_type& __v)
831 __node_gen_type __node_gen(__h);
832 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
837 { this->insert(__l.begin(), __l.end()); }
839 template<
typename _InputIterator>
841 insert(_InputIterator __first, _InputIterator __last)
844 __node_gen_type __node_gen(__h);
845 return _M_insert_range(__first, __last, __node_gen, __unique_keys());
849 template<
typename _Key,
typename _Value,
typename _Alloc,
850 typename _ExtractKey,
typename _Equal,
851 typename _H1,
typename _H2,
typename _Hash,
852 typename _RehashPolicy,
typename _Traits>
853 template<
typename _InputIterator,
typename _NodeGetter>
855 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
856 _RehashPolicy, _Traits>::
857 _M_insert_range(_InputIterator __first, _InputIterator __last,
858 const _NodeGetter& __node_gen,
true_type)
860 size_type __n_elt = __detail::__distance_fw(__first, __last);
864 __hashtable& __h = _M_conjure_hashtable();
865 for (; __first != __last; ++__first)
867 if (__h._M_insert(*__first, __node_gen, __unique_keys(),
870 else if (__n_elt != 1)
875 template<
typename _Key,
typename _Value,
typename _Alloc,
876 typename _ExtractKey,
typename _Equal,
877 typename _H1,
typename _H2,
typename _Hash,
878 typename _RehashPolicy,
typename _Traits>
879 template<
typename _InputIterator,
typename _NodeGetter>
881 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
882 _RehashPolicy, _Traits>::
883 _M_insert_range(_InputIterator __first, _InputIterator __last,
886 using __rehash_type =
typename __hashtable::__rehash_type;
887 using __rehash_state =
typename __hashtable::__rehash_state;
890 size_type __n_elt = __detail::__distance_fw(__first, __last);
894 __hashtable& __h = _M_conjure_hashtable();
895 __rehash_type& __rehash = __h._M_rehash_policy;
896 const __rehash_state& __saved_state = __rehash._M_state();
897 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
898 __h._M_element_count,
901 if (__do_rehash.first)
902 __h._M_rehash(__do_rehash.second, __saved_state);
904 for (; __first != __last; ++__first)
905 __h._M_insert(*__first, __node_gen, __unique_keys());
914 template<
typename _Key,
typename _Value,
typename _Alloc,
915 typename _ExtractKey,
typename _Equal,
916 typename _H1,
typename _H2,
typename _Hash,
917 typename _RehashPolicy,
typename _Traits,
918 bool _Constant_iterators = _Traits::__constant_iterators::value>
922 template<
typename _Key,
typename _Value,
typename _Alloc,
923 typename _ExtractKey,
typename _Equal,
924 typename _H1,
typename _H2,
typename _Hash,
925 typename _RehashPolicy,
typename _Traits>
926 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
927 _RehashPolicy, _Traits, true>
928 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
929 _H1, _H2, _Hash, _RehashPolicy, _Traits>
932 _Equal, _H1, _H2, _Hash,
933 _RehashPolicy, _Traits>;
936 _Equal, _H1, _H2, _Hash,
939 using value_type =
typename __base_type::value_type;
940 using iterator =
typename __base_type::iterator;
941 using const_iterator =
typename __base_type::const_iterator;
943 using __unique_keys =
typename __base_type::__unique_keys;
944 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
946 using __node_gen_type =
typename __base_type::__node_gen_type;
948 using __base_type::insert;
951 insert(value_type&& __v)
954 __node_gen_type __node_gen(__h);
955 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
959 insert(const_iterator __hint, value_type&& __v)
962 __node_gen_type __node_gen(__h);
963 return __h._M_insert(__hint, std::move(__v), __node_gen,
969 template<
typename _Key,
typename _Value,
typename _Alloc,
970 typename _ExtractKey,
typename _Equal,
971 typename _H1,
typename _H2,
typename _Hash,
972 typename _RehashPolicy,
typename _Traits>
973 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
974 _RehashPolicy, _Traits, false>
975 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
976 _H1, _H2, _Hash, _RehashPolicy, _Traits>
979 _Equal, _H1, _H2, _Hash,
980 _RehashPolicy, _Traits>;
981 using value_type =
typename __base_type::value_type;
982 using iterator =
typename __base_type::iterator;
983 using const_iterator =
typename __base_type::const_iterator;
985 using __unique_keys =
typename __base_type::__unique_keys;
987 using __ireturn_type =
typename __base_type::__ireturn_type;
989 using __base_type::insert;
991 template<
typename _Pair>
994 template<
typename _Pair>
997 template<
typename _Pair>
1000 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1005 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
1008 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1010 insert(const_iterator __hint, _Pair&& __v)
1013 return __h._M_emplace(__hint, __unique_keys(),
1014 std::forward<_Pair>(__v));
1018 template<
typename _Policy>
1019 using __has_load_factor =
typename _Policy::__has_load_factor;
1027 template<
typename _Key,
typename _Value,
typename _Alloc,
1028 typename _ExtractKey,
typename _Equal,
1029 typename _H1,
typename _H2,
typename _Hash,
1030 typename _RehashPolicy,
typename _Traits,
1032 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
1036 template<
typename _Key,
typename _Value,
typename _Alloc,
1037 typename _ExtractKey,
typename _Equal,
1038 typename _H1,
typename _H2,
typename _Hash,
1039 typename _RehashPolicy,
typename _Traits>
1041 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1047 template<
typename _Key,
typename _Value,
typename _Alloc,
1048 typename _ExtractKey,
typename _Equal,
1049 typename _H1,
typename _H2,
typename _Hash,
1050 typename _RehashPolicy,
typename _Traits>
1052 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1056 _Equal, _H1, _H2, _Hash,
1057 _RehashPolicy, _Traits>;
1060 max_load_factor()
const noexcept
1063 return __this->__rehash_policy().max_load_factor();
1067 max_load_factor(
float __z)
1070 __this->__rehash_policy(_RehashPolicy(__z));
1074 reserve(std::size_t __n)
1077 __this->rehash(__builtin_ceil(__n / max_load_factor()));
1087 template<
int _Nm,
typename _Tp,
1088 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1092 template<
int _Nm,
typename _Tp>
1098 template<
typename _OtherTp>
1100 : _Tp(std::forward<_OtherTp>(__tp))
1105 {
return static_cast<const _Tp&
>(__eboh); }
1109 {
return static_cast<_Tp&
>(__eboh); }
1113 template<
int _Nm,
typename _Tp>
1118 template<
typename _OtherTp>
1120 : _M_tp(std::forward<_OtherTp>(__tp))
1125 {
return __eboh._M_tp; }
1129 {
return __eboh._M_tp; }
1141 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1142 typename _H1,
typename _H2,
typename _Hash,
1143 bool __cache_hash_code>
1166 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1167 typename _H1,
typename _H2,
typename _Hash,
1168 bool __cache_hash_code>
1173 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1174 typename _H1,
typename _H2,
typename _Hash>
1184 typedef void* __hash_code;
1196 _M_hash_code(
const _Key& __key)
const
1200 _M_bucket_index(
const _Key& __k, __hash_code, std::size_t __n)
const
1201 {
return _M_ranged_hash()(__k, __n); }
1204 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1205 noexcept(
noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1207 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1220 std::swap(_M_extract(), __x._M_extract());
1221 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1225 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1228 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1231 _M_ranged_hash()
const {
return __ebo_hash::_S_cget(*
this); }
1234 _M_ranged_hash() {
return __ebo_hash::_S_get(*
this); }
1243 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1244 typename _H1,
typename _H2,
typename _Hash>
1245 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1250 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1251 typename _H1,
typename _H2>
1271 hash_function()
const
1275 typedef std::size_t __hash_code;
1283 const _H1& __h1,
const _H2& __h2,
1288 _M_hash_code(
const _Key& __k)
const
1290 static_assert(__is_invocable<const _H1&, const _Key&>{},
1291 "hash function must be invocable with an argument of key type");
1292 return _M_h1()(__k);
1296 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const
1297 {
return _M_h2()(__c, __n); }
1300 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1301 noexcept(
noexcept(declval<const _H1&>()(declval<const _Key&>()))
1302 &&
noexcept(declval<const _H2&>()((__hash_code)0,
1304 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1317 std::swap(_M_extract(), __x._M_extract());
1318 std::swap(_M_h1(), __x._M_h1());
1319 std::swap(_M_h2(), __x._M_h2());
1323 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1326 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1329 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1332 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1335 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1338 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1344 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1345 typename _H1,
typename _H2>
1365 hash_function()
const
1369 typedef std::size_t __hash_code;
1375 const _H1& __h1,
const _H2& __h2,
1380 _M_hash_code(
const _Key& __k)
const
1382 static_assert(__is_invocable<const _H1&, const _Key&>{},
1383 "hash function must be invocable with an argument of key type");
1384 return _M_h1()(__k);
1388 _M_bucket_index(
const _Key&, __hash_code __c,
1389 std::size_t __n)
const
1390 {
return _M_h2()(__c, __n); }
1393 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1394 noexcept(
noexcept(declval<const _H2&>()((__hash_code)0,
1396 {
return _M_h2()(__p->_M_hash_code, __n); }
1399 _M_store_code(
__node_type* __n, __hash_code __c)
const
1400 { __n->_M_hash_code = __c; }
1404 { __to->_M_hash_code = __from->_M_hash_code; }
1409 std::swap(_M_extract(), __x._M_extract());
1410 std::swap(_M_h1(), __x._M_h1());
1411 std::swap(_M_h2(), __x._M_h2());
1415 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1418 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1421 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1424 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1427 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1430 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1437 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1438 typename _Equal,
typename _HashCodeType,
1439 bool __cache_hash_code>
1443 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1444 typename _Equal,
typename _HashCodeType>
1448 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1450 {
return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1454 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1455 typename _Equal,
typename _HashCodeType>
1459 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1461 {
return __eq(__k, __extract(__n->_M_v())); }
1466 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1467 typename _H1,
typename _H2,
typename _Hash>
1469 _H1, _H2, _Hash, true>
1475 _H1, _H2, _Hash,
true>;
1480 std::size_t __bkt, std::size_t __bkt_count)
1482 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1487 _M_cur = _M_cur->_M_next();
1491 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1493 if (__bkt != _M_bucket)
1499 std::size_t _M_bucket;
1500 std::size_t _M_bucket_count;
1504 _M_curr()
const {
return _M_cur; }
1507 _M_get_bucket()
const {
return _M_bucket; }
1514 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1515 struct _Hash_code_storage
1517 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1520 _M_h() {
return _M_storage._M_ptr(); }
1523 _M_h()
const {
return _M_storage._M_ptr(); }
1527 template<
typename _Tp>
1528 struct _Hash_code_storage<_Tp, true>
1535 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1538 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1541 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1542 typename _H1,
typename _H2,
typename _Hash>
1543 using __hash_code_for_local_iter
1544 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1545 _H1, _H2, _Hash,
false>>;
1548 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1549 typename _H1,
typename _H2,
typename _Hash>
1550 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1551 _H1, _H2, _Hash, false>
1552 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1555 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1556 _H1, _H2, _Hash,
false>;
1558 _Local_iterator_base() : _M_bucket_count(-1) { }
1560 _Local_iterator_base(
const __hash_code_base&
__base,
1561 _Hash_node<_Value, false>* __p,
1562 std::size_t __bkt, std::size_t __bkt_count)
1563 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1566 ~_Local_iterator_base()
1568 if (_M_bucket_count != -1)
1572 _Local_iterator_base(
const _Local_iterator_base& __iter)
1573 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1574 _M_bucket_count(__iter._M_bucket_count)
1576 if (_M_bucket_count != -1)
1577 _M_init(*__iter._M_h());
1580 _Local_iterator_base&
1581 operator=(
const _Local_iterator_base& __iter)
1583 if (_M_bucket_count != -1)
1585 _M_cur = __iter._M_cur;
1586 _M_bucket = __iter._M_bucket;
1587 _M_bucket_count = __iter._M_bucket_count;
1588 if (_M_bucket_count != -1)
1589 _M_init(*__iter._M_h());
1596 _M_cur = _M_cur->_M_next();
1599 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1601 if (__bkt != _M_bucket)
1606 _Hash_node<_Value, false>* _M_cur;
1607 std::size_t _M_bucket;
1608 std::size_t _M_bucket_count;
1611 _M_init(
const __hash_code_base&
__base)
1612 { ::new(this->_M_h()) __hash_code_base(
__base); }
1615 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1619 _M_curr()
const {
return _M_cur; }
1622 _M_get_bucket()
const {
return _M_bucket; }
1625 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1626 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1628 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1629 _H1, _H2, _Hash, __cache>& __x,
1630 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1631 _H1, _H2, _Hash, __cache>& __y)
1632 {
return __x._M_curr() == __y._M_curr(); }
1634 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1635 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1637 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1638 _H1, _H2, _Hash, __cache>& __x,
1639 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1640 _H1, _H2, _Hash, __cache>& __y)
1641 {
return __x._M_curr() != __y._M_curr(); }
1644 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1645 typename _H1,
typename _H2,
typename _Hash,
1646 bool __constant_iterators,
bool __cache>
1649 _H1, _H2, _Hash, __cache>
1653 _H1, _H2, _Hash, __cache>;
1654 using __hash_code_base =
typename __base_type::__hash_code_base;
1656 typedef _Value value_type;
1658 const _Value*, _Value*>::type
1661 const _Value&, _Value&>::type
1663 typedef std::ptrdiff_t difference_type;
1670 std::size_t __bkt, std::size_t __bkt_count)
1676 {
return this->_M_cur->_M_v(); }
1680 {
return this->_M_cur->_M_valptr(); }
1699 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1700 typename _H1,
typename _H2,
typename _Hash,
1701 bool __constant_iterators,
bool __cache>
1704 _H1, _H2, _Hash, __cache>
1708 _H1, _H2, _Hash, __cache>;
1709 using __hash_code_base =
typename __base_type::__hash_code_base;
1712 typedef _Value value_type;
1713 typedef const _Value* pointer;
1714 typedef const _Value& reference;
1715 typedef std::ptrdiff_t difference_type;
1722 std::size_t __bkt, std::size_t __bkt_count)
1728 __constant_iterators,
1735 {
return this->_M_cur->_M_v(); }
1739 {
return this->_M_cur->_M_valptr(); }
1767 template<
typename _Key,
typename _Value,
1768 typename _ExtractKey,
typename _Equal,
1769 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1772 _Traits::__hash_cached::value>,
1776 typedef _Key key_type;
1777 typedef _Value value_type;
1778 typedef _Equal key_equal;
1779 typedef std::size_t size_type;
1780 typedef std::ptrdiff_t difference_type;
1782 using __traits_type = _Traits;
1783 using __hash_cached =
typename __traits_type::__hash_cached;
1784 using __constant_iterators =
typename __traits_type::__constant_iterators;
1785 using __unique_keys =
typename __traits_type::__unique_keys;
1789 __hash_cached::value>;
1791 using __hash_code =
typename __hash_code_base::__hash_code;
1792 using __node_type =
typename __hash_code_base::__node_type;
1795 __constant_iterators::value,
1796 __hash_cached::value>;
1799 __constant_iterators::value,
1800 __hash_cached::value>;
1803 _ExtractKey, _H1, _H2, _Hash,
1804 __constant_iterators::value,
1805 __hash_cached::value>;
1809 _ExtractKey, _H1, _H2, _Hash,
1810 __constant_iterators::value,
1811 __hash_cached::value>;
1819 __hash_code, __hash_cached::value>;
1823 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1824 const _Hash& __hash,
const _Equal& __eq)
1829 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const
1831 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1832 "key equality predicate must be invocable with two arguments of "
1834 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1841 __hash_code_base::_M_swap(__x);
1842 std::swap(_M_eq(), __x._M_eq());
1846 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1849 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1860 template<
typename _Uiterator>
1862 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1866 template<
typename _Uiterator>
1869 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1870 _Uiterator __first2)
1872 for (; __first1 != __last1; ++__first1, ++__first2)
1873 if (!(*__first1 == *__first2))
1876 if (__first1 == __last1)
1879 _Uiterator __last2 = __first2;
1882 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1884 _Uiterator __tmp = __first1;
1885 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1892 std::ptrdiff_t __n2 = 0;
1893 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1894 if (*__tmp == *__it1)
1900 std::ptrdiff_t __n1 = 0;
1901 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1902 if (*__tmp == *__it1)
1919 template<
typename _Key,
typename _Value,
typename _Alloc,
1920 typename _ExtractKey,
typename _Equal,
1921 typename _H1,
typename _H2,
typename _Hash,
1922 typename _RehashPolicy,
typename _Traits,
1923 bool _Unique_keys = _Traits::__unique_keys::value>
1927 template<
typename _Key,
typename _Value,
typename _Alloc,
1928 typename _ExtractKey,
typename _Equal,
1929 typename _H1,
typename _H2,
typename _Hash,
1930 typename _RehashPolicy,
typename _Traits>
1932 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1935 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1941 template<
typename _Key,
typename _Value,
typename _Alloc,
1942 typename _ExtractKey,
typename _Equal,
1943 typename _H1,
typename _H2,
typename _Hash,
1944 typename _RehashPolicy,
typename _Traits>
1946 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1947 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1948 _M_equal(
const __hashtable& __other)
const
1950 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1952 if (__this->size() != __other.size())
1955 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1957 const auto __ity = __other.find(_ExtractKey()(*__itx));
1958 if (__ity == __other.end() || !bool(*__ity == *__itx))
1965 template<
typename _Key,
typename _Value,
typename _Alloc,
1966 typename _ExtractKey,
typename _Equal,
1967 typename _H1,
typename _H2,
typename _Hash,
1968 typename _RehashPolicy,
typename _Traits>
1970 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1974 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1980 template<
typename _Key,
typename _Value,
typename _Alloc,
1981 typename _ExtractKey,
typename _Equal,
1982 typename _H1,
typename _H2,
typename _Hash,
1983 typename _RehashPolicy,
typename _Traits>
1985 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1986 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1987 _M_equal(
const __hashtable& __other)
const
1989 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1991 if (__this->size() != __other.size())
1994 for (
auto __itx = __this->begin(); __itx != __this->end();)
1996 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1997 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
2003 if (!_S_is_permutation(__xrange.first, __xrange.second,
2007 __itx = __xrange.second;
2016 template<
typename _NodeAlloc>
2022 using __node_type =
typename _NodeAlloc::value_type;
2023 using __node_alloc_type = _NodeAlloc;
2027 using __value_alloc_traits =
typename __node_alloc_traits::template
2028 rebind_traits<typename __node_type::value_type>;
2032 using __bucket_alloc_type =
2033 __alloc_rebind<__node_alloc_type, __bucket_type>;
2040 template<
typename _Alloc>
2047 {
return __ebo_node_alloc::_S_get(*
this); }
2049 const __node_alloc_type&
2050 _M_node_allocator()
const
2051 {
return __ebo_node_alloc::_S_cget(*
this); }
2053 template<
typename... _Args>
2055 _M_allocate_node(_Args&&... __args);
2058 _M_deallocate_node(__node_type* __n);
2061 _M_deallocate_node_ptr(__node_type* __n);
2065 _M_deallocate_nodes(__node_type* __n);
2068 _M_allocate_buckets(std::size_t __n);
2076 template<
typename _NodeAlloc>
2077 template<
typename... _Args>
2078 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
2081 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2082 __node_type* __n = std::__to_address(__nptr);
2085 ::new ((
void*)__n) __node_type;
2086 __node_alloc_traits::construct(_M_node_allocator(),
2088 std::forward<_Args>(__args)...);
2093 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2094 __throw_exception_again;
2098 template<
typename _NodeAlloc>
2100 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
2102 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
2103 _M_deallocate_node_ptr(__n);
2106 template<
typename _NodeAlloc>
2108 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_type* __n)
2110 typedef typename __node_alloc_traits::pointer _Ptr;
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
_GLIBCXX20_CONSTEXPR complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
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.
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2 not less than __n.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_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.
_Iterator __base(_Iterator __it)
Properties of fundamental types.
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.