31 #ifndef _HASHTABLE_POLICY_H 32 #define _HASHTABLE_POLICY_H 1 36 namespace std _GLIBCXX_VISIBILITY(default)
38 _GLIBCXX_BEGIN_NAMESPACE_VERSION
40 template<
typename _Key,
typename _Value,
typename _Alloc,
41 typename _ExtractKey,
typename _Equal,
42 typename _H1,
typename _H2,
typename _Hash,
43 typename _RehashPolicy,
typename _Traits>
46 _GLIBCXX_END_NAMESPACE_VERSION
50 _GLIBCXX_BEGIN_NAMESPACE_VERSION
57 template<
typename _Key,
typename _Value,
58 typename _ExtractKey,
typename _Equal,
59 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
64 template<
class _Iterator>
65 inline typename std::iterator_traits<_Iterator>::difference_type
66 __distance_fw(_Iterator __first, _Iterator __last,
70 template<
class _Iterator>
71 inline typename std::iterator_traits<_Iterator>::difference_type
72 __distance_fw(_Iterator __first, _Iterator __last,
76 template<
class _Iterator>
77 inline typename std::iterator_traits<_Iterator>::difference_type
78 __distance_fw(_Iterator __first, _Iterator __last)
80 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
81 return __distance_fw(__first, __last, _Tag());
85 template <
typename _Key,
typename _Hash>
87 noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
92 template<
typename _Tp>
94 operator()(_Tp&& __x)
const 95 {
return std::forward<_Tp>(__x); }
100 template<
typename _Tp>
102 operator()(_Tp&& __x)
const 103 -> decltype(std::get<0>(std::forward<_Tp>(__x)))
104 {
return std::get<0>(std::forward<_Tp>(__x)); }
107 template<
typename _NodeAlloc>
112 template<
typename _NodeAlloc>
113 struct _ReuseOrAllocNode
116 using __node_alloc_type = _NodeAlloc;
118 using __value_alloc_type =
typename __hashtable_alloc::__value_alloc_type;
120 typename __hashtable_alloc::__value_alloc_traits;
122 typename __hashtable_alloc::__node_alloc_traits;
123 using __node_type =
typename __hashtable_alloc::__node_type;
126 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
127 : _M_nodes(__nodes), _M_h(__h) { }
128 _ReuseOrAllocNode(
const _ReuseOrAllocNode&) =
delete;
131 { _M_h._M_deallocate_nodes(_M_nodes); }
133 template<
typename _Arg>
135 operator()(_Arg&& __arg)
const 139 __node_type* __node = _M_nodes;
140 _M_nodes = _M_nodes->_M_next();
141 __node->_M_nxt =
nullptr;
142 __value_alloc_type __a(_M_h._M_node_allocator());
143 __value_alloc_traits::destroy(__a, __node->_M_valptr());
146 __value_alloc_traits::construct(__a, __node->_M_valptr(),
147 std::forward<_Arg>(__arg));
151 __node->~__node_type();
152 __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
154 __throw_exception_again;
158 return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
162 mutable __node_type* _M_nodes;
163 __hashtable_alloc& _M_h;
168 template<
typename _NodeAlloc>
173 using __node_type =
typename __hashtable_alloc::__node_type;
176 _AllocNode(__hashtable_alloc& __h)
179 template<
typename _Arg>
181 operator()(_Arg&& __arg)
const 182 {
return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
185 __hashtable_alloc& _M_h;
213 template<
bool _Cache_hash_code,
bool _Constant_iterators,
bool _Unique_keys>
243 template<
typename _Value>
246 typedef _Value value_type;
248 __gnu_cxx::__aligned_buffer<_Value> _M_storage;
252 {
return _M_storage._M_ptr(); }
255 _M_valptr()
const noexcept
256 {
return _M_storage._M_ptr(); }
260 {
return *_M_valptr(); }
263 _M_v()
const noexcept
264 {
return *_M_valptr(); }
270 template<
typename _Value,
bool _Cache_hash_code>
278 template<
typename _Value>
281 std::size_t _M_hash_code;
284 _M_next()
const noexcept
285 {
return static_cast<_Hash_node*
>(this->_M_nxt); }
293 template<
typename _Value>
297 _M_next()
const noexcept
298 {
return static_cast<_Hash_node*
>(this->_M_nxt); }
302 template<
typename _Value,
bool _Cache_hash_code>
314 { _M_cur = _M_cur->_M_next(); }
317 template<
typename _Value,
bool _Cache_hash_code>
322 {
return __x._M_cur == __y._M_cur; }
324 template<
typename _Value,
bool _Cache_hash_code>
329 {
return __x._M_cur != __y._M_cur; }
332 template<
typename _Value,
bool __constant_iterators,
bool __cache>
341 typedef _Value value_type;
342 typedef std::ptrdiff_t difference_type;
345 using pointer =
typename std::conditional<__constant_iterators,
346 const _Value*, _Value*>::type;
348 using reference =
typename std::conditional<__constant_iterators,
349 const _Value&, _Value&>::type;
360 {
return this->_M_cur->_M_v(); }
363 operator->()
const noexcept
364 {
return this->_M_cur->_M_valptr(); }
367 operator++() noexcept
374 operator++(
int) noexcept
383 template<
typename _Value,
bool __constant_iterators,
bool __cache>
392 typedef _Value value_type;
393 typedef std::ptrdiff_t difference_type;
396 typedef const _Value* pointer;
397 typedef const _Value& reference;
407 __cache>& __x) noexcept
412 {
return this->_M_cur->_M_v(); }
415 operator->()
const noexcept
416 {
return this->_M_cur->_M_valptr(); }
419 operator++() noexcept
426 operator++(
int) noexcept
441 typedef std::size_t first_argument_type;
442 typedef std::size_t second_argument_type;
443 typedef std::size_t result_type;
446 operator()(first_argument_type __num,
447 second_argument_type __den)
const noexcept
448 {
return __num % __den; }
465 : _M_max_load_factor(__z), _M_next_resize(0) { }
468 max_load_factor()
const noexcept
469 {
return _M_max_load_factor; }
473 _M_next_bkt(std::size_t __n)
const;
477 _M_bkt_for_elements(std::size_t __n)
const 478 {
return __builtin_ceil(__n / (
long double)_M_max_load_factor); }
485 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
486 std::size_t __n_ins)
const;
488 typedef std::size_t _State;
492 {
return _M_next_resize; }
496 { _M_next_resize = 0; }
499 _M_reset(_State __state)
500 { _M_next_resize = __state; }
502 static const std::size_t _S_growth_factor = 2;
504 float _M_max_load_factor;
505 mutable std::size_t _M_next_resize;
511 typedef std::size_t first_argument_type;
512 typedef std::size_t second_argument_type;
513 typedef std::size_t result_type;
516 operator()(first_argument_type __num,
517 second_argument_type __den)
const noexcept
518 {
return __num & (__den - 1); }
526 #if __SIZEOF_SIZE_T__ >= 8 527 std::uint_fast64_t __x = __n;
529 std::uint_fast32_t __x = __n;
533 __x = __x | (__x >> 1);
534 __x = __x | (__x >> 2);
535 __x = __x | (__x >> 4);
536 __x = __x | (__x >> 8);
537 __x = __x | (__x >>16);
538 #if __SIZEOF_SIZE_T__ >= 8 539 __x = __x | (__x >>32);
551 : _M_max_load_factor(__z), _M_next_resize(0) { }
554 max_load_factor()
const noexcept
555 {
return _M_max_load_factor; }
560 _M_next_bkt(std::size_t __n) noexcept
562 const auto __max_width = std::min<size_t>(
sizeof(size_t), 8);
563 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
564 std::size_t __res =
__clp2(__n);
572 if (__res == __max_bkt)
576 _M_next_resize = std::size_t(-1);
579 = __builtin_ceil(__res * (
long double)_M_max_load_factor);
586 _M_bkt_for_elements(std::size_t __n)
const noexcept
587 {
return __builtin_ceil(__n / (
long double)_M_max_load_factor); }
594 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
595 std::size_t __n_ins) noexcept
597 if (__n_elt + __n_ins >= _M_next_resize)
599 long double __min_bkts = (__n_elt + __n_ins)
600 / (
long double)_M_max_load_factor;
601 if (__min_bkts >= __n_bkt)
603 _M_next_bkt(std::max<std::size_t>(__builtin_floor(__min_bkts) + 1,
604 __n_bkt * _S_growth_factor)));
607 = __builtin_floor(__n_bkt * (
long double)_M_max_load_factor);
614 typedef std::size_t _State;
617 _M_state()
const noexcept
618 {
return _M_next_resize; }
622 { _M_next_resize = 0; }
625 _M_reset(_State __state) noexcept
626 { _M_next_resize = __state; }
628 static const std::size_t _S_growth_factor = 2;
630 float _M_max_load_factor;
631 std::size_t _M_next_resize;
652 template<
typename _Key,
typename _Value,
typename _Alloc,
653 typename _ExtractKey,
typename _Equal,
654 typename _H1,
typename _H2,
typename _Hash,
655 typename _RehashPolicy,
typename _Traits,
656 bool _Unique_keys = _Traits::__unique_keys::value>
660 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
661 typename _H1,
typename _H2,
typename _Hash,
662 typename _RehashPolicy,
typename _Traits>
663 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
664 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
670 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
671 typename _H1,
typename _H2,
typename _Hash,
672 typename _RehashPolicy,
typename _Traits>
673 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
674 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
679 _Equal, _H1, _H2, _Hash,
684 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
686 using __hash_code =
typename __hashtable_base::__hash_code;
687 using __node_type =
typename __hashtable_base::__node_type;
690 using key_type =
typename __hashtable_base::key_type;
695 operator[](
const key_type& __k);
698 operator[](key_type&& __k);
703 at(
const key_type& __k);
706 at(
const key_type& __k)
const;
709 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
710 typename _H1,
typename _H2,
typename _Hash,
711 typename _RehashPolicy,
typename _Traits>
713 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
714 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
715 operator[](
const key_type& __k)
719 __hash_code __code = __h->_M_hash_code(__k);
720 std::size_t __n = __h->_M_bucket_index(__k, __code);
721 __node_type* __p = __h->_M_find_node(__n, __k, __code);
728 return __h->_M_insert_unique_node(__n, __code, __p)->second;
731 return __p->_M_v().second;
734 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
735 typename _H1,
typename _H2,
typename _Hash,
736 typename _RehashPolicy,
typename _Traits>
738 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
739 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
740 operator[](key_type&& __k)
744 __hash_code __code = __h->_M_hash_code(__k);
745 std::size_t __n = __h->_M_bucket_index(__k, __code);
746 __node_type* __p = __h->_M_find_node(__n, __k, __code);
751 std::forward_as_tuple(std::move(__k)),
753 return __h->_M_insert_unique_node(__n, __code, __p)->second;
756 return __p->_M_v().second;
759 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
760 typename _H1,
typename _H2,
typename _Hash,
761 typename _RehashPolicy,
typename _Traits>
763 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
764 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
765 at(
const key_type& __k)
769 __hash_code __code = __h->_M_hash_code(__k);
770 std::size_t __n = __h->_M_bucket_index(__k, __code);
771 __node_type* __p = __h->_M_find_node(__n, __k, __code);
774 __throw_out_of_range(__N(
"_Map_base::at"));
775 return __p->_M_v().second;
778 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
779 typename _H1,
typename _H2,
typename _Hash,
780 typename _RehashPolicy,
typename _Traits>
782 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
783 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
784 at(
const key_type& __k)
const 785 ->
const mapped_type&
788 __hash_code __code = __h->_M_hash_code(__k);
789 std::size_t __n = __h->_M_bucket_index(__k, __code);
790 __node_type* __p = __h->_M_find_node(__n, __k, __code);
793 __throw_out_of_range(__N(
"_Map_base::at"));
794 return __p->_M_v().second;
802 template<
typename _Key,
typename _Value,
typename _Alloc,
803 typename _ExtractKey,
typename _Equal,
804 typename _H1,
typename _H2,
typename _Hash,
805 typename _RehashPolicy,
typename _Traits>
810 _Equal, _H1, _H2, _Hash,
811 _RehashPolicy, _Traits>;
814 _Equal, _H1, _H2, _Hash,
817 using value_type =
typename __hashtable_base::value_type;
820 using size_type =
typename __hashtable_base::size_type;
822 using __unique_keys =
typename __hashtable_base::__unique_keys;
823 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
825 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
826 using __node_gen_type = _AllocNode<__node_alloc_type>;
829 _M_conjure_hashtable()
832 template<
typename _InputIterator,
typename _NodeGetter>
834 _M_insert_range(_InputIterator __first, _InputIterator __last,
839 insert(
const value_type& __v)
842 __node_gen_type __node_gen(__h);
843 return __h._M_insert(__v, __node_gen, __unique_keys());
847 insert(const_iterator __hint,
const value_type& __v)
850 __node_gen_type __node_gen(__h);
851 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
856 { this->insert(__l.begin(), __l.end()); }
858 template<
typename _InputIterator>
860 insert(_InputIterator __first, _InputIterator __last)
863 __node_gen_type __node_gen(__h);
864 return _M_insert_range(__first, __last, __node_gen);
868 template<
typename _Key,
typename _Value,
typename _Alloc,
869 typename _ExtractKey,
typename _Equal,
870 typename _H1,
typename _H2,
typename _Hash,
871 typename _RehashPolicy,
typename _Traits>
872 template<
typename _InputIterator,
typename _NodeGetter>
874 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
875 _RehashPolicy, _Traits>::
876 _M_insert_range(_InputIterator __first, _InputIterator __last,
877 const _NodeGetter& __node_gen)
879 using __rehash_type =
typename __hashtable::__rehash_type;
880 using __rehash_state =
typename __hashtable::__rehash_state;
883 size_type __n_elt = __detail::__distance_fw(__first, __last);
886 __rehash_type& __rehash = __h._M_rehash_policy;
887 const __rehash_state& __saved_state = __rehash._M_state();
888 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
889 __h._M_element_count,
892 if (__do_rehash.first)
893 __h._M_rehash(__do_rehash.second, __saved_state);
895 for (; __first != __last; ++__first)
896 __h._M_insert(*__first, __node_gen, __unique_keys());
905 template<
typename _Key,
typename _Value,
typename _Alloc,
906 typename _ExtractKey,
typename _Equal,
907 typename _H1,
typename _H2,
typename _Hash,
908 typename _RehashPolicy,
typename _Traits,
909 bool _Constant_iterators = _Traits::__constant_iterators::value>
913 template<
typename _Key,
typename _Value,
typename _Alloc,
914 typename _ExtractKey,
typename _Equal,
915 typename _H1,
typename _H2,
typename _Hash,
916 typename _RehashPolicy,
typename _Traits>
917 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
918 _RehashPolicy, _Traits, true>
919 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
920 _H1, _H2, _Hash, _RehashPolicy, _Traits>
923 _Equal, _H1, _H2, _Hash,
924 _RehashPolicy, _Traits>;
927 _Equal, _H1, _H2, _Hash,
930 using value_type =
typename __base_type::value_type;
931 using iterator =
typename __base_type::iterator;
932 using const_iterator =
typename __base_type::const_iterator;
934 using __unique_keys =
typename __base_type::__unique_keys;
935 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
937 using __node_gen_type =
typename __base_type::__node_gen_type;
939 using __base_type::insert;
942 insert(value_type&& __v)
945 __node_gen_type __node_gen(__h);
946 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
950 insert(const_iterator __hint, value_type&& __v)
953 __node_gen_type __node_gen(__h);
954 return __h._M_insert(__hint, std::move(__v), __node_gen,
960 template<
typename _Key,
typename _Value,
typename _Alloc,
961 typename _ExtractKey,
typename _Equal,
962 typename _H1,
typename _H2,
typename _Hash,
963 typename _RehashPolicy,
typename _Traits>
964 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
965 _RehashPolicy, _Traits, false>
966 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
967 _H1, _H2, _Hash, _RehashPolicy, _Traits>
970 _Equal, _H1, _H2, _Hash,
971 _RehashPolicy, _Traits>;
972 using value_type =
typename __base_type::value_type;
973 using iterator =
typename __base_type::iterator;
974 using const_iterator =
typename __base_type::const_iterator;
976 using __unique_keys =
typename __base_type::__unique_keys;
978 using __ireturn_type =
typename __base_type::__ireturn_type;
980 using __base_type::insert;
982 template<
typename _Pair>
983 using __is_cons = std::is_constructible<value_type, _Pair&&>;
985 template<
typename _Pair>
986 using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
988 template<
typename _Pair>
989 using _IFconsp =
typename _IFcons<_Pair>::type;
991 template<
typename _Pair,
typename = _IFconsp<_Pair>>
996 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
999 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1001 insert(const_iterator __hint, _Pair&& __v)
1004 return __h._M_emplace(__hint, __unique_keys(),
1005 std::forward<_Pair>(__v));
1009 template<
typename _Policy>
1010 using __has_load_factor =
typename _Policy::__has_load_factor;
1018 template<
typename _Key,
typename _Value,
typename _Alloc,
1019 typename _ExtractKey,
typename _Equal,
1020 typename _H1,
typename _H2,
typename _Hash,
1021 typename _RehashPolicy,
typename _Traits,
1023 __detected_or_t<std::false_type, __has_load_factor, _RehashPolicy>>
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 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1038 template<
typename _Key,
typename _Value,
typename _Alloc,
1039 typename _ExtractKey,
typename _Equal,
1040 typename _H1,
typename _H2,
typename _Hash,
1041 typename _RehashPolicy,
typename _Traits>
1043 _H1, _H2, _Hash, _RehashPolicy, _Traits,
1047 _Equal, _H1, _H2, _Hash,
1048 _RehashPolicy, _Traits>;
1051 max_load_factor()
const noexcept
1053 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1054 return __this->__rehash_policy().max_load_factor();
1058 max_load_factor(
float __z)
1060 __hashtable* __this =
static_cast<__hashtable*
>(
this);
1061 __this->__rehash_policy(_RehashPolicy(__z));
1065 reserve(std::size_t __n)
1067 __hashtable* __this =
static_cast<__hashtable*
>(
this);
1068 __this->rehash(__builtin_ceil(__n / max_load_factor()));
1078 template<
int _Nm,
typename _Tp,
1079 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1083 template<
int _Nm,
typename _Tp>
1089 template<
typename _OtherTp>
1091 : _Tp(std::forward<_OtherTp>(__tp))
1096 {
return static_cast<const _Tp&
>(__eboh); }
1100 {
return static_cast<_Tp&
>(__eboh); }
1104 template<
int _Nm,
typename _Tp>
1109 template<
typename _OtherTp>
1111 : _M_tp(std::forward<_OtherTp>(__tp))
1116 {
return __eboh._M_tp; }
1120 {
return __eboh._M_tp; }
1132 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1133 typename _H1,
typename _H2,
typename _Hash,
1134 bool __cache_hash_code>
1157 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1158 typename _H1,
typename _H2,
typename _Hash,
1159 bool __cache_hash_code>
1164 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1165 typename _H1,
typename _H2,
typename _Hash>
1175 typedef void* __hash_code;
1187 _M_hash_code(
const _Key& __key)
const 1191 _M_bucket_index(
const _Key& __k, __hash_code, std::size_t __n)
const 1192 {
return _M_ranged_hash()(__k, __n); }
1195 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const 1196 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1198 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1201 _M_store_code(__node_type*, __hash_code)
const 1205 _M_copy_code(__node_type*,
const __node_type*)
const 1211 std::swap(_M_extract(), __x._M_extract());
1212 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1216 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1219 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1222 _M_ranged_hash()
const {
return __ebo_hash::_S_cget(*
this); }
1225 _M_ranged_hash() {
return __ebo_hash::_S_get(*
this); }
1234 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1235 typename _H1,
typename _H2,
typename _Hash>
1236 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1241 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1242 typename _H1,
typename _H2>
1256 _Default_ranged_hash, false>;
1262 hash_function()
const 1266 typedef std::size_t __hash_code;
1274 const _H1& __h1,
const _H2& __h2,
1275 const _Default_ranged_hash&)
1279 _M_hash_code(
const _Key& __k)
const 1280 {
return _M_h1()(__k); }
1283 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const 1284 {
return _M_h2()(__c, __n); }
1287 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const 1288 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1289 && noexcept(declval<const _H2&>()((__hash_code)0,
1291 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1294 _M_store_code(__node_type*, __hash_code)
const 1298 _M_copy_code(__node_type*,
const __node_type*)
const 1304 std::swap(_M_extract(), __x._M_extract());
1305 std::swap(_M_h1(), __x._M_h1());
1306 std::swap(_M_h2(), __x._M_h2());
1310 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1313 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1316 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1319 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1322 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1325 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1331 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1332 typename _H1,
typename _H2>
1342 _Default_ranged_hash, true>;
1352 hash_function()
const 1356 typedef std::size_t __hash_code;
1362 const _H1& __h1,
const _H2& __h2,
1363 const _Default_ranged_hash&)
1367 _M_hash_code(
const _Key& __k)
const 1368 {
return _M_h1()(__k); }
1371 _M_bucket_index(
const _Key&, __hash_code __c,
1372 std::size_t __n)
const 1373 {
return _M_h2()(__c, __n); }
1376 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const 1377 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1379 {
return _M_h2()(__p->_M_hash_code, __n); }
1382 _M_store_code(__node_type* __n, __hash_code __c)
const 1383 { __n->_M_hash_code = __c; }
1386 _M_copy_code(__node_type* __to,
const __node_type* __from)
const 1387 { __to->_M_hash_code = __from->_M_hash_code; }
1392 std::swap(_M_extract(), __x._M_extract());
1393 std::swap(_M_h1(), __x._M_h1());
1394 std::swap(_M_h2(), __x._M_h2());
1398 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1401 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1404 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1407 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1410 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1413 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1420 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1421 typename _Equal,
typename _HashCodeType,
1422 bool __cache_hash_code>
1426 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1427 typename _Equal,
typename _HashCodeType>
1431 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1433 {
return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1437 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1438 typename _Equal,
typename _HashCodeType>
1442 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1444 {
return __eq(__k, __extract(__n->_M_v())); }
1449 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1450 typename _H1,
typename _H2,
typename _Hash>
1452 _H1, _H2, _Hash, true>
1458 _H1, _H2, _Hash,
true>;
1463 std::size_t __bkt, std::size_t __bkt_count)
1465 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1470 _M_cur = _M_cur->_M_next();
1474 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1476 if (__bkt != _M_bucket)
1482 std::size_t _M_bucket;
1483 std::size_t _M_bucket_count;
1487 _M_curr()
const {
return _M_cur; }
1490 _M_get_bucket()
const {
return _M_bucket; }
1497 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1498 struct _Hash_code_storage
1500 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1503 _M_h() {
return _M_storage._M_ptr(); }
1506 _M_h()
const {
return _M_storage._M_ptr(); }
1510 template<
typename _Tp>
1511 struct _Hash_code_storage<_Tp, true>
1518 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1521 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1524 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1525 typename _H1,
typename _H2,
typename _Hash>
1526 using __hash_code_for_local_iter
1528 _H1, _H2, _Hash,
false>>;
1531 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1532 typename _H1,
typename _H2,
typename _Hash>
1534 _H1, _H2, _Hash, false>
1535 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1539 _H1, _H2, _Hash,
false>;
1545 std::size_t __bkt, std::size_t __bkt_count)
1546 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1547 { _M_init(__base); }
1551 if (_M_bucket_count != -1)
1556 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1557 _M_bucket_count(__iter._M_bucket_count)
1559 if (_M_bucket_count != -1)
1560 _M_init(*__iter._M_h());
1566 if (_M_bucket_count != -1)
1568 _M_cur = __iter._M_cur;
1569 _M_bucket = __iter._M_bucket;
1570 _M_bucket_count = __iter._M_bucket_count;
1571 if (_M_bucket_count != -1)
1572 _M_init(*__iter._M_h());
1579 _M_cur = _M_cur->_M_next();
1582 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1584 if (__bkt != _M_bucket)
1590 std::size_t _M_bucket;
1591 std::size_t _M_bucket_count;
1598 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1602 _M_curr()
const {
return _M_cur; }
1605 _M_get_bucket()
const {
return _M_bucket; }
1608 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1609 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1612 _H1, _H2, _Hash, __cache>& __x,
1614 _H1, _H2, _Hash, __cache>& __y)
1615 {
return __x._M_curr() == __y._M_curr(); }
1617 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1618 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1621 _H1, _H2, _Hash, __cache>& __x,
1623 _H1, _H2, _Hash, __cache>& __y)
1624 {
return __x._M_curr() != __y._M_curr(); }
1627 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1628 typename _H1,
typename _H2,
typename _Hash,
1629 bool __constant_iterators,
bool __cache>
1632 _H1, _H2, _Hash, __cache>
1636 _H1, _H2, _Hash, __cache>;
1637 using __hash_code_base =
typename __base_type::__hash_code_base;
1639 typedef _Value value_type;
1640 typedef typename std::conditional<__constant_iterators,
1641 const _Value*, _Value*>::type
1643 typedef typename std::conditional<__constant_iterators,
1644 const _Value&, _Value&>::type
1646 typedef std::ptrdiff_t difference_type;
1653 std::size_t __bkt, std::size_t __bkt_count)
1659 {
return this->_M_cur->_M_v(); }
1663 {
return this->_M_cur->_M_valptr(); }
1682 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1683 typename _H1,
typename _H2,
typename _Hash,
1684 bool __constant_iterators,
bool __cache>
1687 _H1, _H2, _Hash, __cache>
1691 _H1, _H2, _Hash, __cache>;
1692 using __hash_code_base =
typename __base_type::__hash_code_base;
1695 typedef _Value value_type;
1696 typedef const _Value* pointer;
1697 typedef const _Value& reference;
1698 typedef std::ptrdiff_t difference_type;
1705 std::size_t __bkt, std::size_t __bkt_count)
1711 __constant_iterators,
1718 {
return this->_M_cur->_M_v(); }
1722 {
return this->_M_cur->_M_valptr(); }
1750 template<
typename _Key,
typename _Value,
1751 typename _ExtractKey,
typename _Equal,
1752 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1755 _Traits::__hash_cached::value>,
1759 typedef _Key key_type;
1760 typedef _Value value_type;
1761 typedef _Equal key_equal;
1762 typedef std::size_t size_type;
1763 typedef std::ptrdiff_t difference_type;
1765 using __traits_type = _Traits;
1766 using __hash_cached =
typename __traits_type::__hash_cached;
1767 using __constant_iterators =
typename __traits_type::__constant_iterators;
1768 using __unique_keys =
typename __traits_type::__unique_keys;
1772 __hash_cached::value>;
1774 using __hash_code =
typename __hash_code_base::__hash_code;
1775 using __node_type =
typename __hash_code_base::__node_type;
1778 __constant_iterators::value,
1779 __hash_cached::value>;
1782 __constant_iterators::value,
1783 __hash_cached::value>;
1786 _ExtractKey, _H1, _H2, _Hash,
1787 __constant_iterators::value,
1788 __hash_cached::value>;
1792 _ExtractKey, _H1, _H2, _Hash,
1793 __constant_iterators::value,
1794 __hash_cached::value>;
1796 using __ireturn_type =
typename std::conditional<__unique_keys::value,
1801 using _EqualHelper =
_Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1802 __hash_code, __hash_cached::value>;
1806 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1807 const _Hash& __hash,
const _Equal& __eq)
1808 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1812 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const 1814 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1821 __hash_code_base::_M_swap(__x);
1822 std::swap(_M_eq(), __x._M_eq());
1826 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1829 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1840 template<
typename _Uiterator>
1842 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1846 template<
typename _Uiterator>
1849 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1850 _Uiterator __first2)
1852 for (; __first1 != __last1; ++__first1, ++__first2)
1853 if (!(*__first1 == *__first2))
1856 if (__first1 == __last1)
1859 _Uiterator __last2 = __first2;
1862 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1864 _Uiterator __tmp = __first1;
1865 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1872 std::ptrdiff_t __n2 = 0;
1873 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1874 if (*__tmp == *__it1)
1880 std::ptrdiff_t __n1 = 0;
1881 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1882 if (*__tmp == *__it1)
1899 template<
typename _Key,
typename _Value,
typename _Alloc,
1900 typename _ExtractKey,
typename _Equal,
1901 typename _H1,
typename _H2,
typename _Hash,
1902 typename _RehashPolicy,
typename _Traits,
1903 bool _Unique_keys = _Traits::__unique_keys::value>
1907 template<
typename _Key,
typename _Value,
typename _Alloc,
1908 typename _ExtractKey,
typename _Equal,
1909 typename _H1,
typename _H2,
typename _Hash,
1910 typename _RehashPolicy,
typename _Traits>
1912 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1915 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1918 _M_equal(
const __hashtable&)
const;
1921 template<
typename _Key,
typename _Value,
typename _Alloc,
1922 typename _ExtractKey,
typename _Equal,
1923 typename _H1,
typename _H2,
typename _Hash,
1924 typename _RehashPolicy,
typename _Traits>
1926 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1927 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1932 if (__this->size() != __other.size())
1935 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1937 const auto __ity = __other.find(_ExtractKey()(*__itx));
1938 if (__ity == __other.end() || !bool(*__ity == *__itx))
1945 template<
typename _Key,
typename _Value,
typename _Alloc,
1946 typename _ExtractKey,
typename _Equal,
1947 typename _H1,
typename _H2,
typename _Hash,
1948 typename _RehashPolicy,
typename _Traits>
1950 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1954 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1957 _M_equal(
const __hashtable&)
const;
1960 template<
typename _Key,
typename _Value,
typename _Alloc,
1961 typename _ExtractKey,
typename _Equal,
1962 typename _H1,
typename _H2,
typename _Hash,
1963 typename _RehashPolicy,
typename _Traits>
1965 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1966 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1971 if (__this->size() != __other.size())
1974 for (
auto __itx = __this->begin(); __itx != __this->end();)
1976 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1977 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1983 if (!_S_is_permutation(__xrange.first, __xrange.second,
1987 __itx = __xrange.second;
1996 template<
typename _NodeAlloc>
2002 using __node_type =
typename _NodeAlloc::value_type;
2003 using __node_alloc_type = _NodeAlloc;
2007 using __value_type =
typename __node_type::value_type;
2008 using __value_alloc_type =
2009 __alloc_rebind<__node_alloc_type, __value_type>;
2013 using __bucket_type = __node_base*;
2014 using __bucket_alloc_type =
2015 __alloc_rebind<__node_alloc_type, __bucket_type>;
2022 template<
typename _Alloc>
2024 : __ebo_node_alloc(std::forward<_Alloc>(__a))
2029 {
return __ebo_node_alloc::_S_get(*
this); }
2031 const __node_alloc_type&
2032 _M_node_allocator()
const 2033 {
return __ebo_node_alloc::_S_cget(*
this); }
2035 template<
typename... _Args>
2037 _M_allocate_node(_Args&&... __args);
2040 _M_deallocate_node(__node_type* __n);
2044 _M_deallocate_nodes(__node_type* __n);
2047 _M_allocate_buckets(std::size_t __n);
2050 _M_deallocate_buckets(__bucket_type*, std::size_t __n);
2055 template<
typename _NodeAlloc>
2056 template<
typename... _Args>
2057 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
2060 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
2064 __value_alloc_type __a(_M_node_allocator());
2065 ::new ((
void*)__n) __node_type;
2066 __value_alloc_traits::construct(__a, __n->_M_valptr(),
2067 std::forward<_Args>(__args)...);
2072 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
2073 __throw_exception_again;
2077 template<
typename _NodeAlloc>
2081 typedef typename __node_alloc_traits::pointer _Ptr;
2083 __value_alloc_type __a(_M_node_allocator());
2084 __value_alloc_traits::destroy(__a, __n->_M_valptr());
2085 __n->~__node_type();
2086 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
2089 template<
typename _NodeAlloc>
2095 __node_type* __tmp = __n;
2096 __n = __n->_M_next();
2097 _M_deallocate_node(__tmp);
2101 template<
typename _NodeAlloc>
2105 __bucket_alloc_type __alloc(_M_node_allocator());
2107 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
2109 __builtin_memset(__p, 0, __n *
sizeof(__bucket_type));
2113 template<
typename _NodeAlloc>
2118 typedef typename __bucket_alloc_traits::pointer _Ptr;
2120 __bucket_alloc_type __alloc(_M_node_allocator());
2121 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
2125 _GLIBCXX_END_NAMESPACE_VERSION
2129 #endif // _HASHTABLE_POLICY_H
_GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Uniform interface to C++98 and C++11 allocators.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
ISO C++ entities toplevel namespace is std.
Uniform interface to all allocator types.
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 iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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.
Range hashing function assuming that second arg is a power of 2.
Default range hashing function: use division to fold a large number into the range [0...
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Primary class template, tuple.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Rehash policy providing power of 2 bucket numbers. Avoids modulo operations.
_GLIBCXX14_CONSTEXPR std::size_t __clp2(std::size_t __n) noexcept
Compute closest power of 2.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Forward iterators support a superset of input iterator operations.
Uniform interface to all pointer-like types.
Base class for node iterators.
Struct holding two objects of arbitrary type.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
Node const_iterators, used to iterate through all the hashtable.