31#ifndef _HASHTABLE_POLICY_H
32#define _HASHTABLE_POLICY_H 1
38namespace std _GLIBCXX_VISIBILITY(default)
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
43 template<
typename _Key,
typename _Value,
typename _Alloc,
44 typename _ExtractKey,
typename _Equal,
45 typename _Hash,
typename _RangeHash,
typename _Unused,
46 typename _RehashPolicy,
typename _Traits>
56 template<
typename _Key,
typename _Value,
typename _ExtractKey,
57 typename _Equal,
typename _Hash,
typename _RangeHash,
58 typename _Unused,
typename _Traits>
59 struct _Hashtable_base;
63 template<
class _Iterator>
65 __distance_fw(_Iterator __first, _Iterator __last,
67 {
return __first != __last ? 1 : 0; }
69 template<
class _Iterator>
71 __distance_fw(_Iterator __first, _Iterator __last,
75 template<
class _Iterator>
77 __distance_fw(_Iterator __first, _Iterator __last)
78 {
return __distance_fw(__first, __last,
83 template<
typename _Tp>
85 operator()(_Tp&& __x)
const noexcept
91 template<
typename _Tp>
93 operator()(_Tp&& __x)
const noexcept
98 template<
typename _NodeAlloc>
99 struct _Hashtable_alloc;
103 template<
typename _NodeAlloc>
104 struct _ReuseOrAllocNode
107 using __node_alloc_type = _NodeAlloc;
108 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
109 using __node_alloc_traits =
110 typename __hashtable_alloc::__node_alloc_traits;
111 using __node_type =
typename __hashtable_alloc::__node_type;
114 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
115 : _M_nodes(__nodes), _M_h(__h) { }
116 _ReuseOrAllocNode(
const _ReuseOrAllocNode&) =
delete;
119 { _M_h._M_deallocate_nodes(_M_nodes); }
121 template<
typename _Arg>
123 operator()(_Arg&& __arg)
const
127 __node_type* __node = _M_nodes;
128 _M_nodes = _M_nodes->_M_next();
129 __node->_M_nxt =
nullptr;
130 auto& __a = _M_h._M_node_allocator();
131 __node_alloc_traits::destroy(__a, __node->_M_valptr());
134 __node_alloc_traits::construct(__a, __node->_M_valptr(),
139 _M_h._M_deallocate_node_ptr(__node);
140 __throw_exception_again;
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
171 __hashtable_alloc& _M_h;
199 template<
bool _Cache_hash_code,
bool _Constant_iterators,
bool _Unique_keys>
200 struct _Hashtable_traits
202 using __hash_cached = __bool_constant<_Cache_hash_code>;
203 using __constant_iterators = __bool_constant<_Constant_iterators>;
204 using __unique_keys = __bool_constant<_Unique_keys>;
215 struct _Hash_node_base
217 _Hash_node_base* _M_nxt;
219 _Hash_node_base() noexcept : _M_nxt() { }
221 _Hash_node_base(_Hash_node_base* __next) noexcept : _M_nxt(__next) { }
229 template<
typename _Value>
230 struct _Hash_node_value_base
232 typedef _Value value_type;
234 __gnu_cxx::__aligned_buffer<_Value> _M_storage;
236 [[__gnu__::__always_inline__]]
239 {
return _M_storage._M_ptr(); }
241 [[__gnu__::__always_inline__]]
243 _M_valptr() const noexcept
244 {
return _M_storage._M_ptr(); }
246 [[__gnu__::__always_inline__]]
249 {
return *_M_valptr(); }
251 [[__gnu__::__always_inline__]]
253 _M_v() const noexcept
254 {
return *_M_valptr(); }
260 template<
bool _Cache_hash_code>
261 struct _Hash_node_code_cache
268 struct _Hash_node_code_cache<true>
269 { std::size_t _M_hash_code; };
271 template<
typename _Value,
bool _Cache_hash_code>
272 struct _Hash_node_value
273 : _Hash_node_value_base<_Value>
274 , _Hash_node_code_cache<_Cache_hash_code>
280 template<
typename _Value,
bool _Cache_hash_code>
283 , _Hash_node_value<_Value, _Cache_hash_code>
286 _M_next() const noexcept
287 {
return static_cast<_Hash_node*
>(this->_M_nxt); }
291 template<
typename _Value,
bool _Cache_hash_code>
292 struct _Node_iterator_base
294 using __node_type = _Hash_node<_Value, _Cache_hash_code>;
298 _Node_iterator_base() : _M_cur(nullptr) { }
299 _Node_iterator_base(__node_type* __p) noexcept
304 { _M_cur = _M_cur->_M_next(); }
307 operator==(
const _Node_iterator_base& __x,
const _Node_iterator_base& __y)
309 {
return __x._M_cur == __y._M_cur; }
311#if __cpp_impl_three_way_comparison < 201907L
313 operator!=(
const _Node_iterator_base& __x,
const _Node_iterator_base& __y)
315 {
return __x._M_cur != __y._M_cur; }
320 template<
typename _Value,
bool __constant_iterators,
bool __cache>
321 struct _Node_iterator
322 :
public _Node_iterator_base<_Value, __cache>
325 using __base_type = _Node_iterator_base<_Value, __cache>;
326 using __node_type =
typename __base_type::__node_type;
329 typedef _Value value_type;
334 const value_type*, value_type*>::type;
337 const value_type&, value_type&>::type;
339 _Node_iterator() =
default;
342 _Node_iterator(__node_type* __p) noexcept
343 : __base_type(__p) { }
347 {
return this->_M_cur->_M_v(); }
350 operator->() const noexcept
351 {
return this->_M_cur->_M_valptr(); }
354 operator++() noexcept
361 operator++(
int)
noexcept
363 _Node_iterator __tmp(*
this);
370 template<
typename _Value,
bool __constant_iterators,
bool __cache>
371 struct _Node_const_iterator
372 :
public _Node_iterator_base<_Value, __cache>
375 using __base_type = _Node_iterator_base<_Value, __cache>;
376 using __node_type =
typename __base_type::__node_type;
379 typedef _Value value_type;
383 typedef const value_type* pointer;
384 typedef const value_type& reference;
386 _Node_const_iterator() =
default;
389 _Node_const_iterator(__node_type* __p) noexcept
390 : __base_type(__p) { }
392 _Node_const_iterator(
const _Node_iterator<_Value, __constant_iterators,
393 __cache>& __x) noexcept
394 : __base_type(__x._M_cur) { }
398 {
return this->_M_cur->_M_v(); }
401 operator->() const noexcept
402 {
return this->_M_cur->_M_valptr(); }
404 _Node_const_iterator&
405 operator++() noexcept
412 operator++(
int)
noexcept
414 _Node_const_iterator __tmp(*
this);
425 struct _Mod_range_hashing
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; }
442 struct _Default_ranged_hash { };
446 struct _Prime_rehash_policy
450 _Prime_rehash_policy(
float __z = 1.0) noexcept
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 / (
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;
495 struct _Mask_range_hashing
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); }
509 __clp2(std::size_t __n)
noexcept
515 const unsigned __lz =
sizeof(size_t) >
sizeof(
long)
516 ? __builtin_clzll(__n - 1ull)
517 : __builtin_clzl(__n - 1ul);
519 return (
size_t(1) << (__int_traits<size_t>::__digits - __lz - 1)) << 1;
524 struct _Power2_rehash_policy
528 _Power2_rehash_policy(
float __z = 1.0) noexcept
529 : _M_max_load_factor(__z), _M_next_resize(0) { }
532 max_load_factor() const noexcept
533 {
return _M_max_load_factor; }
538 _M_next_bkt(std::size_t __n)
noexcept
547 const auto __max_bkt = size_t(1) << (__max_width * __CHAR_BIT__ - 1);
548 std::size_t __res = __clp2(__n);
558 if (__res == __max_bkt)
562 _M_next_resize = size_t(-1);
565 = __builtin_floor(__res * (
double)_M_max_load_factor);
572 _M_bkt_for_elements(std::size_t __n)
const noexcept
573 {
return __builtin_ceil(__n / (
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)
590 / (double)_M_max_load_factor;
591 if (__min_bkts >= __n_bkt)
594 __n_bkt * _S_growth_factor)) };
597 = __builtin_floor(__n_bkt * (
double)_M_max_load_factor);
604 typedef std::size_t _State;
607 _M_state() const noexcept
608 {
return _M_next_resize; }
612 { _M_next_resize = 0; }
615 _M_reset(_State __state)
noexcept
616 { _M_next_resize = __state; }
618 static const std::size_t _S_growth_factor = 2;
620 float _M_max_load_factor;
621 std::size_t _M_next_resize;
642 template<
typename _Key,
typename _Value,
typename _Alloc,
643 typename _ExtractKey,
typename _Equal,
644 typename _Hash,
typename _RangeHash,
typename _Unused,
645 typename _RehashPolicy,
typename _Traits,
646 bool _Unique_keys = _Traits::__unique_keys::value>
647 struct _Map_base { };
650 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
651 typename _Hash,
typename _RangeHash,
typename _Unused,
652 typename _RehashPolicy,
typename _Traits>
653 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
654 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
660 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
661 typename _Hash,
typename _RangeHash,
typename _Unused,
662 typename _RehashPolicy,
typename _Traits>
663 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
664 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
667 using __hashtable_base = _Hashtable_base<_Key, _Pair, _Select1st, _Equal,
668 _Hash, _RangeHash, _Unused,
671 using __hashtable = _Hashtable<_Key, _Pair, _Alloc, _Select1st, _Equal,
673 _Unused, _RehashPolicy, _Traits>;
675 using __hash_code =
typename __hashtable_base::__hash_code;
678 using key_type =
typename __hashtable_base::key_type;
682 operator[](
const key_type& __k);
685 operator[](key_type&& __k);
690 at(
const key_type& __k);
693 at(
const key_type& __k)
const;
696 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
697 typename _Hash,
typename _RangeHash,
typename _Unused,
698 typename _RehashPolicy,
typename _Traits>
700 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
701 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
702 operator[](
const key_type& __k)
705 __hashtable* __h =
static_cast<__hashtable*
>(
this);
706 __hash_code __code = __h->_M_hash_code(__k);
707 std::size_t __bkt = __h->_M_bucket_index(__code);
708 if (
auto __node = __h->_M_find_node(__bkt, __k, __code))
709 return __node->_M_v().second;
711 typename __hashtable::_Scoped_node __node {
718 = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
719 __node._M_node =
nullptr;
720 return __pos->second;
723 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
724 typename _Hash,
typename _RangeHash,
typename _Unused,
725 typename _RehashPolicy,
typename _Traits>
727 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
728 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
729 operator[](key_type&& __k)
732 __hashtable* __h =
static_cast<__hashtable*
>(
this);
733 __hash_code __code = __h->_M_hash_code(__k);
734 std::size_t __bkt = __h->_M_bucket_index(__code);
735 if (
auto __node = __h->_M_find_node(__bkt, __k, __code))
736 return __node->_M_v().second;
738 typename __hashtable::_Scoped_node __node {
745 = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
746 __node._M_node =
nullptr;
747 return __pos->second;
750 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
751 typename _Hash,
typename _RangeHash,
typename _Unused,
752 typename _RehashPolicy,
typename _Traits>
754 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
755 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
756 at(
const key_type& __k)
759 __hashtable* __h =
static_cast<__hashtable*
>(
this);
760 auto __ite = __h->find(__k);
763 __throw_out_of_range(__N(
"_Map_base::at"));
764 return __ite->second;
767 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
768 typename _Hash,
typename _RangeHash,
typename _Unused,
769 typename _RehashPolicy,
typename _Traits>
771 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
772 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
773 at(
const key_type& __k)
const
774 ->
const mapped_type&
776 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
777 auto __ite = __h->find(__k);
780 __throw_out_of_range(__N(
"_Map_base::at"));
781 return __ite->second;
789 template<
typename _Key,
typename _Value,
typename _Alloc,
790 typename _ExtractKey,
typename _Equal,
791 typename _Hash,
typename _RangeHash,
typename _Unused,
792 typename _RehashPolicy,
typename _Traits>
796 using __hashtable_base = _Hashtable_base<_Key, _Value, _ExtractKey,
797 _Equal, _Hash, _RangeHash,
800 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
802 _Unused, _RehashPolicy, _Traits>;
804 using __hash_cached =
typename _Traits::__hash_cached;
805 using __constant_iterators =
typename _Traits::__constant_iterators;
807 using __hashtable_alloc = _Hashtable_alloc<
808 __alloc_rebind<_Alloc, _Hash_node<_Value,
809 __hash_cached::value>>>;
811 using value_type =
typename __hashtable_base::value_type;
812 using size_type =
typename __hashtable_base::size_type;
814 using __unique_keys =
typename _Traits::__unique_keys;
815 using __node_alloc_type =
typename __hashtable_alloc::__node_alloc_type;
816 using __node_gen_type = _AllocNode<__node_alloc_type>;
819 _M_conjure_hashtable()
820 {
return *(
static_cast<__hashtable*
>(
this)); }
822 template<
typename _InputIterator,
typename _NodeGetter>
824 _M_insert_range(_InputIterator __first, _InputIterator __last,
825 const _NodeGetter&, true_type __uks);
827 template<
typename _InputIterator,
typename _NodeGetter>
829 _M_insert_range(_InputIterator __first, _InputIterator __last,
830 const _NodeGetter&, false_type __uks);
833 using iterator = _Node_iterator<_Value, __constant_iterators::value,
834 __hash_cached::value>;
836 using const_iterator = _Node_const_iterator<_Value, __constant_iterators::value,
837 __hash_cached::value>;
844 insert(
const value_type& __v)
846 __hashtable& __h = _M_conjure_hashtable();
847 __node_gen_type __node_gen(__h);
848 return __h._M_insert(__v, __node_gen, __unique_keys{});
852 insert(const_iterator __hint,
const value_type& __v)
854 __hashtable& __h = _M_conjure_hashtable();
855 __node_gen_type __node_gen(__h);
856 return __h._M_insert(__hint, __v, __node_gen, __unique_keys{});
859 template<
typename _KType,
typename... _Args>
861 try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
863 __hashtable& __h = _M_conjure_hashtable();
864 auto __code = __h._M_hash_code(__k);
865 std::size_t __bkt = __h._M_bucket_index(__code);
866 if (
auto __node = __h._M_find_node(__bkt, __k, __code))
867 return { iterator(__node),
false };
869 typename __hashtable::_Scoped_node __node {
876 = __h._M_insert_unique_node(__bkt, __code, __node._M_node);
877 __node._M_node =
nullptr;
878 return { __it,
true };
882 insert(initializer_list<value_type> __l)
883 { this->insert(__l.begin(), __l.end()); }
885 template<
typename _InputIterator>
887 insert(_InputIterator __first, _InputIterator __last)
889 __hashtable& __h = _M_conjure_hashtable();
890 __node_gen_type __node_gen(__h);
891 return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
895 template<
typename _Key,
typename _Value,
typename _Alloc,
896 typename _ExtractKey,
typename _Equal,
897 typename _Hash,
typename _RangeHash,
typename _Unused,
898 typename _RehashPolicy,
typename _Traits>
899 template<
typename _InputIterator,
typename _NodeGetter>
901 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
902 _Hash, _RangeHash, _Unused,
903 _RehashPolicy, _Traits>::
904 _M_insert_range(_InputIterator __first, _InputIterator __last,
905 const _NodeGetter& __node_gen,
true_type __uks)
907 __hashtable& __h = _M_conjure_hashtable();
908 for (; __first != __last; ++__first)
909 __h._M_insert(*__first, __node_gen, __uks);
912 template<
typename _Key,
typename _Value,
typename _Alloc,
913 typename _ExtractKey,
typename _Equal,
914 typename _Hash,
typename _RangeHash,
typename _Unused,
915 typename _RehashPolicy,
typename _Traits>
916 template<
typename _InputIterator,
typename _NodeGetter>
918 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
919 _Hash, _RangeHash, _Unused,
920 _RehashPolicy, _Traits>::
921 _M_insert_range(_InputIterator __first, _InputIterator __last,
922 const _NodeGetter& __node_gen,
false_type __uks)
924 using __rehash_type =
typename __hashtable::__rehash_type;
925 using __rehash_state =
typename __hashtable::__rehash_state;
928 size_type __n_elt = __detail::__distance_fw(__first, __last);
932 __hashtable& __h = _M_conjure_hashtable();
933 __rehash_type& __rehash = __h._M_rehash_policy;
934 const __rehash_state& __saved_state = __rehash._M_state();
935 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
936 __h._M_element_count,
939 if (__do_rehash.first)
940 __h._M_rehash(__do_rehash.second, __saved_state);
942 for (; __first != __last; ++__first)
943 __h._M_insert(*__first, __node_gen, __uks);
952 template<
typename _Key,
typename _Value,
typename _Alloc,
953 typename _ExtractKey,
typename _Equal,
954 typename _Hash,
typename _RangeHash,
typename _Unused,
955 typename _RehashPolicy,
typename _Traits,
956 bool _Constant_iterators = _Traits::__constant_iterators::value>
960 template<
typename _Key,
typename _Value,
typename _Alloc,
961 typename _ExtractKey,
typename _Equal,
962 typename _Hash,
typename _RangeHash,
typename _Unused,
963 typename _RehashPolicy,
typename _Traits>
964 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
965 _Hash, _RangeHash, _Unused,
966 _RehashPolicy, _Traits, true>
967 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
968 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
970 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
971 _Equal, _Hash, _RangeHash, _Unused,
972 _RehashPolicy, _Traits>;
974 using value_type =
typename __base_type::value_type;
975 using iterator =
typename __base_type::iterator;
976 using const_iterator =
typename __base_type::const_iterator;
977 using __ireturn_type =
typename __base_type::__ireturn_type;
979 using __unique_keys =
typename __base_type::__unique_keys;
980 using __hashtable =
typename __base_type::__hashtable;
981 using __node_gen_type =
typename __base_type::__node_gen_type;
983 using __base_type::insert;
986 insert(value_type&& __v)
988 __hashtable& __h = this->_M_conjure_hashtable();
989 __node_gen_type __node_gen(__h);
990 return __h._M_insert(
std::move(__v), __node_gen, __unique_keys{});
994 insert(const_iterator __hint, value_type&& __v)
996 __hashtable& __h = this->_M_conjure_hashtable();
997 __node_gen_type __node_gen(__h);
998 return __h._M_insert(__hint,
std::move(__v), __node_gen,
1004 template<
typename _Key,
typename _Value,
typename _Alloc,
1005 typename _ExtractKey,
typename _Equal,
1006 typename _Hash,
typename _RangeHash,
typename _Unused,
1007 typename _RehashPolicy,
typename _Traits>
1008 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1009 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1010 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1011 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
1013 using __base_type = _Insert_base<_Key, _Value, _Alloc, _ExtractKey,
1014 _Equal, _Hash, _RangeHash, _Unused,
1015 _RehashPolicy, _Traits>;
1016 using value_type =
typename __base_type::value_type;
1017 using iterator =
typename __base_type::iterator;
1018 using const_iterator =
typename __base_type::const_iterator;
1020 using __unique_keys =
typename __base_type::__unique_keys;
1021 using __hashtable =
typename __base_type::__hashtable;
1022 using __ireturn_type =
typename __base_type::__ireturn_type;
1024 using __base_type::insert;
1026 template<
typename _Pair>
1029 template<
typename _Pair>
1032 template<
typename _Pair>
1033 using _IFconsp =
typename _IFcons<_Pair>::type;
1035 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1039 __hashtable& __h = this->_M_conjure_hashtable();
1043 template<
typename _Pair,
typename = _IFconsp<_Pair>>
1045 insert(const_iterator __hint, _Pair&& __v)
1047 __hashtable& __h = this->_M_conjure_hashtable();
1048 return __h._M_emplace(__hint, __unique_keys{},
1053 template<
typename _Policy>
1054 using __has_load_factor =
typename _Policy::__has_load_factor;
1062 template<
typename _Key,
typename _Value,
typename _Alloc,
1063 typename _ExtractKey,
typename _Equal,
1064 typename _Hash,
typename _RangeHash,
typename _Unused,
1065 typename _RehashPolicy,
typename _Traits,
1067 __detected_or_t<false_type, __has_load_factor, _RehashPolicy>>
1068 struct _Rehash_base;
1071 template<
typename _Key,
typename _Value,
typename _Alloc,
1072 typename _ExtractKey,
typename _Equal,
1073 typename _Hash,
typename _RangeHash,
typename _Unused,
1074 typename _RehashPolicy,
typename _Traits>
1075 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1076 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
1082 template<
typename _Key,
typename _Value,
typename _Alloc,
1083 typename _ExtractKey,
typename _Equal,
1084 typename _Hash,
typename _RangeHash,
typename _Unused,
1085 typename _RehashPolicy,
typename _Traits>
1086 struct _Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1087 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
1090 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1091 _Equal, _Hash, _RangeHash, _Unused,
1092 _RehashPolicy, _Traits>;
1095 max_load_factor() const noexcept
1097 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1098 return __this->__rehash_policy().max_load_factor();
1102 max_load_factor(
float __z)
1104 __hashtable* __this =
static_cast<__hashtable*
>(
this);
1105 __this->__rehash_policy(_RehashPolicy(__z));
1109 reserve(std::size_t __n)
1111 __hashtable* __this =
static_cast<__hashtable*
>(
this);
1112 __this->rehash(__this->__rehash_policy()._M_bkt_for_elements(__n));
1122 template<
int _Nm,
typename _Tp,
1123 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
1124 struct _Hashtable_ebo_helper;
1127 template<
int _Nm,
typename _Tp>
1128 struct _Hashtable_ebo_helper<_Nm, _Tp, true>
1131 _Hashtable_ebo_helper() noexcept(noexcept(_Tp())) : _Tp() { }
1133 template<
typename _OtherTp>
1134 _Hashtable_ebo_helper(_OtherTp&& __tp)
1138 const _Tp& _M_cget()
const {
return static_cast<const _Tp&
>(*this); }
1139 _Tp& _M_get() {
return static_cast<_Tp&
>(*this); }
1143 template<
int _Nm,
typename _Tp>
1144 struct _Hashtable_ebo_helper<_Nm, _Tp, false>
1146 _Hashtable_ebo_helper() =
default;
1148 template<
typename _OtherTp>
1149 _Hashtable_ebo_helper(_OtherTp&& __tp)
1153 const _Tp& _M_cget()
const {
return _M_tp; }
1154 _Tp& _M_get() {
return _M_tp; }
1166 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1167 typename _Hash,
typename _RangeHash,
typename _Unused,
1168 bool __cache_hash_code>
1169 struct _Local_iterator_base;
1189 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1190 typename _Hash,
typename _RangeHash,
typename _Unused,
1191 bool __cache_hash_code>
1192 struct _Hash_code_base
1193 :
private _Hashtable_ebo_helper<1, _Hash>
1196 using __ebo_hash = _Hashtable_ebo_helper<1, _Hash>;
1199 friend struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1200 _Hash, _RangeHash, _Unused, false>;
1203 typedef _Hash hasher;
1206 hash_function()
const
1207 {
return _M_hash(); }
1210 typedef std::size_t __hash_code;
1214 _Hash_code_base() =
default;
1216 _Hash_code_base(
const _Hash& __hash) : __ebo_hash(__hash) { }
1219 _M_hash_code(
const _Key& __k)
const
1221 static_assert(__is_invocable<const _Hash&, const _Key&>{},
1222 "hash function must be invocable with an argument of key type");
1223 return _M_hash()(__k);
1226 template<
typename _Kt>
1228 _M_hash_code_tr(
const _Kt& __k)
const
1230 static_assert(__is_invocable<const _Hash&, const _Kt&>{},
1231 "hash function must be invocable with an argument of key type");
1232 return _M_hash()(__k);
1236 _M_bucket_index(__hash_code __c, std::size_t __bkt_count)
const
1237 {
return _RangeHash{}(__c, __bkt_count); }
1240 _M_bucket_index(
const _Hash_node_value<_Value, false>& __n,
1241 std::size_t __bkt_count)
const
1242 noexcept(
noexcept(declval<const _Hash&>()(declval<const _Key&>()))
1243 &&
noexcept(declval<const _RangeHash&>()((__hash_code)0,
1246 return _RangeHash{}(_M_hash_code(_ExtractKey{}(__n._M_v())),
1251 _M_bucket_index(
const _Hash_node_value<_Value, true>& __n,
1252 std::size_t __bkt_count)
const
1253 noexcept(
noexcept(declval<const _RangeHash&>()((__hash_code)0,
1255 {
return _RangeHash{}(__n._M_hash_code, __bkt_count); }
1258 _M_store_code(_Hash_node_code_cache<false>&, __hash_code)
const
1262 _M_copy_code(_Hash_node_code_cache<false>&,
1263 const _Hash_node_code_cache<false>&)
const
1267 _M_store_code(_Hash_node_code_cache<true>& __n, __hash_code __c)
const
1268 { __n._M_hash_code = __c; }
1271 _M_copy_code(_Hash_node_code_cache<true>& __to,
1272 const _Hash_node_code_cache<true>& __from)
const
1273 { __to._M_hash_code = __from._M_hash_code; }
1276 _M_swap(_Hash_code_base& __x)
1277 {
std::swap(__ebo_hash::_M_get(), __x.__ebo_hash::_M_get()); }
1280 _M_hash()
const {
return __ebo_hash::_M_cget(); }
1284 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1285 typename _Hash,
typename _RangeHash,
typename _Unused>
1286 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1287 _Hash, _RangeHash, _Unused, true>
1288 :
public _Node_iterator_base<_Value, true>
1291 using __base_node_iter = _Node_iterator_base<_Value, true>;
1292 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1293 _Hash, _RangeHash, _Unused,
true>;
1295 _Local_iterator_base() =
default;
1296 _Local_iterator_base(
const __hash_code_base&,
1297 _Hash_node<_Value, true>* __p,
1298 std::size_t __bkt, std::size_t __bkt_count)
1299 : __base_node_iter(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1305 __base_node_iter::_M_incr();
1309 = _RangeHash{}(this->_M_cur->_M_hash_code, _M_bucket_count);
1310 if (__bkt != _M_bucket)
1311 this->_M_cur =
nullptr;
1315 std::size_t _M_bucket;
1316 std::size_t _M_bucket_count;
1320 _M_get_bucket()
const {
return _M_bucket; }
1327 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1328 struct _Hash_code_storage
1330 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1333 _M_h() {
return _M_storage._M_ptr(); }
1336 _M_h()
const {
return _M_storage._M_ptr(); }
1340 template<
typename _Tp>
1341 struct _Hash_code_storage<_Tp, true>
1348 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1351 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1354 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1355 typename _Hash,
typename _RangeHash,
typename _Unused>
1356 using __hash_code_for_local_iter
1357 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1358 _Hash, _RangeHash, _Unused,
false>>;
1361 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1362 typename _Hash,
typename _RangeHash,
typename _Unused>
1363 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1364 _Hash, _RangeHash, _Unused, false>
1365 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1367 , _Node_iterator_base<_Value, false>
1370 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1371 _Hash, _RangeHash, _Unused,
false>;
1372 using __node_iter_base = _Node_iterator_base<_Value, false>;
1374 _Local_iterator_base() : _M_bucket_count(-1) { }
1376 _Local_iterator_base(
const __hash_code_base& __base,
1377 _Hash_node<_Value, false>* __p,
1378 std::size_t __bkt, std::size_t __bkt_count)
1379 : __node_iter_base(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1380 { _M_init(__base); }
1382 ~_Local_iterator_base()
1384 if (_M_bucket_count !=
size_t(-1))
1388 _Local_iterator_base(
const _Local_iterator_base& __iter)
1389 : __node_iter_base(__iter._M_cur), _M_bucket(__iter._M_bucket)
1390 , _M_bucket_count(__iter._M_bucket_count)
1392 if (_M_bucket_count !=
size_t(-1))
1393 _M_init(*__iter._M_h());
1396 _Local_iterator_base&
1397 operator=(
const _Local_iterator_base& __iter)
1399 if (_M_bucket_count != -1)
1401 this->_M_cur = __iter._M_cur;
1402 _M_bucket = __iter._M_bucket;
1403 _M_bucket_count = __iter._M_bucket_count;
1404 if (_M_bucket_count != -1)
1405 _M_init(*__iter._M_h());
1412 __node_iter_base::_M_incr();
1415 std::size_t __bkt = this->_M_h()->_M_bucket_index(*this->_M_cur,
1417 if (__bkt != _M_bucket)
1418 this->_M_cur =
nullptr;
1422 std::size_t _M_bucket;
1423 std::size_t _M_bucket_count;
1426 _M_init(
const __hash_code_base& __base)
1427 { ::new(this->_M_h()) __hash_code_base(__base); }
1430 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1434 _M_get_bucket()
const {
return _M_bucket; }
1438 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1439 typename _Hash,
typename _RangeHash,
typename _Unused,
1440 bool __constant_iterators,
bool __cache>
1441 struct _Local_iterator
1442 :
public _Local_iterator_base<_Key, _Value, _ExtractKey,
1443 _Hash, _RangeHash, _Unused, __cache>
1446 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1447 _Hash, _RangeHash, _Unused, __cache>;
1448 using __hash_code_base =
typename __base_type::__hash_code_base;
1451 typedef _Value value_type;
1453 const value_type*, value_type*>::type
1456 const value_type&, value_type&>::type
1461 _Local_iterator() =
default;
1463 _Local_iterator(
const __hash_code_base& __base,
1464 _Hash_node<_Value, __cache>* __n,
1465 std::size_t __bkt, std::size_t __bkt_count)
1466 : __base_type(
__base, __n, __bkt, __bkt_count)
1471 {
return this->_M_cur->_M_v(); }
1475 {
return this->_M_cur->_M_valptr(); }
1487 _Local_iterator __tmp(*
this);
1494 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1495 typename _Hash,
typename _RangeHash,
typename _Unused,
1496 bool __constant_iterators,
bool __cache>
1497 struct _Local_const_iterator
1498 :
public _Local_iterator_base<_Key, _Value, _ExtractKey,
1499 _Hash, _RangeHash, _Unused, __cache>
1502 using __base_type = _Local_iterator_base<_Key, _Value, _ExtractKey,
1503 _Hash, _RangeHash, _Unused, __cache>;
1504 using __hash_code_base =
typename __base_type::__hash_code_base;
1507 typedef _Value value_type;
1508 typedef const value_type* pointer;
1509 typedef const value_type& reference;
1513 _Local_const_iterator() =
default;
1515 _Local_const_iterator(
const __hash_code_base& __base,
1516 _Hash_node<_Value, __cache>* __n,
1517 std::size_t __bkt, std::size_t __bkt_count)
1518 : __base_type(
__base, __n, __bkt, __bkt_count)
1521 _Local_const_iterator(
const _Local_iterator<_Key, _Value, _ExtractKey,
1522 _Hash, _RangeHash, _Unused,
1523 __constant_iterators,
1530 {
return this->_M_cur->_M_v(); }
1534 {
return this->_M_cur->_M_valptr(); }
1536 _Local_const_iterator&
1543 _Local_const_iterator
1546 _Local_const_iterator __tmp(*
this);
1562 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1563 typename _Equal,
typename _Hash,
typename _RangeHash,
1564 typename _Unused,
typename _Traits>
1565 struct _Hashtable_base
1566 :
public _Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHash,
1567 _Unused, _Traits::__hash_cached::value>,
1568 private _Hashtable_ebo_helper<0, _Equal>
1571 typedef _Key key_type;
1572 typedef _Value value_type;
1573 typedef _Equal key_equal;
1574 typedef std::size_t size_type;
1577 using __traits_type = _Traits;
1578 using __hash_cached =
typename __traits_type::__hash_cached;
1580 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1581 _Hash, _RangeHash, _Unused,
1582 __hash_cached::value>;
1584 using __hash_code =
typename __hash_code_base::__hash_code;
1587 using _EqualEBO = _Hashtable_ebo_helper<0, _Equal>;
1590 _S_equals(__hash_code,
const _Hash_node_code_cache<false>&)
1594 _S_node_equals(
const _Hash_node_code_cache<false>&,
1595 const _Hash_node_code_cache<false>&)
1599 _S_equals(__hash_code __c,
const _Hash_node_code_cache<true>& __n)
1600 {
return __c == __n._M_hash_code; }
1603 _S_node_equals(
const _Hash_node_code_cache<true>& __lhn,
1604 const _Hash_node_code_cache<true>& __rhn)
1605 {
return __lhn._M_hash_code == __rhn._M_hash_code; }
1608 _Hashtable_base() =
default;
1610 _Hashtable_base(
const _Hash& __hash,
const _Equal& __eq)
1611 : __hash_code_base(__hash), _EqualEBO(__eq)
1615 _M_equals(
const _Key& __k, __hash_code __c,
1616 const _Hash_node_value<_Value, __hash_cached::value>& __n)
const
1618 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1619 "key equality predicate must be invocable with two arguments of "
1621 return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1624 template<
typename _Kt>
1626 _M_equals_tr(
const _Kt& __k, __hash_code __c,
1627 const _Hash_node_value<_Value,
1628 __hash_cached::value>& __n)
const
1631 __is_invocable<const _Equal&, const _Kt&, const _Key&>{},
1632 "key equality predicate must be invocable with two arguments of "
1634 return _S_equals(__c, __n) && _M_eq()(__k, _ExtractKey{}(__n._M_v()));
1639 const _Hash_node_value<_Value, __hash_cached::value>& __lhn,
1640 const _Hash_node_value<_Value, __hash_cached::value>& __rhn)
const
1642 return _S_node_equals(__lhn, __rhn)
1643 && _M_eq()(_ExtractKey{}(__lhn._M_v()), _ExtractKey{}(__rhn._M_v()));
1647 _M_swap(_Hashtable_base& __x)
1649 __hash_code_base::_M_swap(__x);
1650 std::swap(_EqualEBO::_M_get(), __x._EqualEBO::_M_get());
1654 _M_eq()
const {
return _EqualEBO::_M_cget(); }
1665 template<
typename _Key,
typename _Value,
typename _Alloc,
1666 typename _ExtractKey,
typename _Equal,
1667 typename _Hash,
typename _RangeHash,
typename _Unused,
1668 typename _RehashPolicy,
typename _Traits,
1669 bool _Unique_keys = _Traits::__unique_keys::value>
1673 template<
typename _Key,
typename _Value,
typename _Alloc,
1674 typename _ExtractKey,
typename _Equal,
1675 typename _Hash,
typename _RangeHash,
typename _Unused,
1676 typename _RehashPolicy,
typename _Traits>
1677 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1678 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>
1680 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1681 _Hash, _RangeHash, _Unused,
1682 _RehashPolicy, _Traits>;
1685 _M_equal(
const __hashtable&)
const;
1688 template<
typename _Key,
typename _Value,
typename _Alloc,
1689 typename _ExtractKey,
typename _Equal,
1690 typename _Hash,
typename _RangeHash,
typename _Unused,
1691 typename _RehashPolicy,
typename _Traits>
1693 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1694 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
true>::
1695 _M_equal(
const __hashtable& __other)
const
1697 using __node_type =
typename __hashtable::__node_type;
1698 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1699 if (__this->size() != __other.size())
1702 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1704 std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1705 auto __prev_n = __other._M_buckets[__ybkt];
1709 for (__node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);;
1710 __n = __n->_M_next())
1712 if (__n->_M_v() == *__itx)
1716 || __other._M_bucket_index(*__n->_M_next()) != __ybkt)
1725 template<
typename _Key,
typename _Value,
typename _Alloc,
1726 typename _ExtractKey,
typename _Equal,
1727 typename _Hash,
typename _RangeHash,
typename _Unused,
1728 typename _RehashPolicy,
typename _Traits>
1729 struct _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1730 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, false>
1732 using __hashtable = _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1733 _Hash, _RangeHash, _Unused,
1734 _RehashPolicy, _Traits>;
1737 _M_equal(
const __hashtable&)
const;
1740 template<
typename _Key,
typename _Value,
typename _Alloc,
1741 typename _ExtractKey,
typename _Equal,
1742 typename _Hash,
typename _RangeHash,
typename _Unused,
1743 typename _RehashPolicy,
typename _Traits>
1745 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1746 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits,
false>::
1747 _M_equal(
const __hashtable& __other)
const
1749 using __node_type =
typename __hashtable::__node_type;
1750 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1751 if (__this->size() != __other.size())
1754 for (
auto __itx = __this->begin(); __itx != __this->end();)
1756 std::size_t __x_count = 1;
1757 auto __itx_end = __itx;
1758 for (++__itx_end; __itx_end != __this->end()
1759 && __this->key_eq()(_ExtractKey{}(*__itx),
1760 _ExtractKey{}(*__itx_end));
1764 std::size_t __ybkt = __other._M_bucket_index(*__itx._M_cur);
1765 auto __y_prev_n = __other._M_buckets[__ybkt];
1769 __node_type* __y_n =
static_cast<__node_type*
>(__y_prev_n->_M_nxt);
1772 if (__this->key_eq()(_ExtractKey{}(__y_n->_M_v()),
1773 _ExtractKey{}(*__itx)))
1776 auto __y_ref_n = __y_n;
1777 for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next())
1778 if (!__other._M_node_equals(*__y_ref_n, *__y_n))
1781 if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt)
1785 typename __hashtable::const_iterator __ity(__y_n);
1786 for (
auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
1787 if (--__x_count == 0)
1793 if (!std::is_permutation(__itx, __itx_end, __ity))
1805 template<
typename _NodeAlloc>
1806 struct _Hashtable_alloc :
private _Hashtable_ebo_helper<0, _NodeAlloc>
1809 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
1811 using __node_type =
typename _NodeAlloc::value_type;
1812 using __node_alloc_type = _NodeAlloc;
1816 using __value_alloc_traits =
typename __node_alloc_traits::template
1817 rebind_traits<typename __node_type::value_type>;
1819 using __node_ptr = __node_type*;
1820 using __node_base = _Hash_node_base;
1821 using __node_base_ptr = __node_base*;
1822 using __buckets_alloc_type =
1823 __alloc_rebind<__node_alloc_type, __node_base_ptr>;
1825 using __buckets_ptr = __node_base_ptr*;
1827 _Hashtable_alloc() =
default;
1828 _Hashtable_alloc(
const _Hashtable_alloc&) =
default;
1829 _Hashtable_alloc(_Hashtable_alloc&&) =
default;
1831 template<
typename _Alloc>
1832 _Hashtable_alloc(_Alloc&& __a)
1833 : __ebo_node_alloc(
std::
forward<_Alloc>(__a))
1838 {
return __ebo_node_alloc::_M_get(); }
1840 const __node_alloc_type&
1841 _M_node_allocator()
const
1842 {
return __ebo_node_alloc::_M_cget(); }
1845 template<
typename... _Args>
1847 _M_allocate_node(_Args&&... __args);
1851 _M_deallocate_node(__node_ptr __n);
1855 _M_deallocate_node_ptr(__node_ptr __n);
1860 _M_deallocate_nodes(__node_ptr __n);
1863 _M_allocate_buckets(std::size_t __bkt_count);
1866 _M_deallocate_buckets(__buckets_ptr, std::size_t __bkt_count);
1871 template<
typename _NodeAlloc>
1872 template<
typename... _Args>
1874 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
1877 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
1878 __node_ptr __n = std::__to_address(__nptr);
1881 ::new ((
void*)__n) __node_type;
1882 __node_alloc_traits::construct(_M_node_allocator(),
1889 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
1890 __throw_exception_again;
1894 template<
typename _NodeAlloc>
1896 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_ptr __n)
1898 __node_alloc_traits::destroy(_M_node_allocator(), __n->_M_valptr());
1899 _M_deallocate_node_ptr(__n);
1902 template<
typename _NodeAlloc>
1904 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node_ptr(__node_ptr __n)
1906 typedef typename __node_alloc_traits::pointer _Ptr;
1908 __n->~__node_type();
1909 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
1912 template<
typename _NodeAlloc>
1914 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_ptr __n)
1918 __node_ptr __tmp = __n;
1919 __n = __n->_M_next();
1920 _M_deallocate_node(__tmp);
1924 template<
typename _NodeAlloc>
1926 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __bkt_count)
1929 __buckets_alloc_type __alloc(_M_node_allocator());
1931 auto __ptr = __buckets_alloc_traits::allocate(__alloc, __bkt_count);
1932 __buckets_ptr __p = std::__to_address(__ptr);
1933 __builtin_memset(__p, 0, __bkt_count *
sizeof(__node_base_ptr));
1937 template<
typename _NodeAlloc>
1939 _Hashtable_alloc<_NodeAlloc>::
1940 _M_deallocate_buckets(__buckets_ptr __bkts,
1941 std::size_t __bkt_count)
1943 typedef typename __buckets_alloc_traits::pointer _Ptr;
1945 __buckets_alloc_type __alloc(_M_node_allocator());
1946 __buckets_alloc_traits::deallocate(__alloc, __ptr, __bkt_count);
1952_GLIBCXX_END_NAMESPACE_VERSION
constexpr duration< __common_rep_t< _Rep2, _Rep1 >, _Period > operator*(const _Rep1 &__s, const duration< _Rep2, _Period > &__d)
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 tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
std::forward_as_tuple
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
__numeric_traits_integer< _Tp > __int_traits
Convenience alias for __numeric_traits<integer-type>.
constexpr _Iterator __base(_Iterator __it)
Primary class template, tuple.
Define a member typedef type to one of two argument types.
Traits class for iterators.
Uniform interface to all pointer-like types.
Forward iterators support a superset of input iterator operations.
Uniform interface to C++98 and C++11 allocators.