31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
34 namespace std _GLIBCXX_VISIBILITY(default)
36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 template<
typename _Key,
typename _Value,
typename _Alloc,
39 typename _ExtractKey,
typename _Equal,
40 typename _H1,
typename _H2,
typename _Hash,
41 typename _RehashPolicy,
typename _Traits>
44 _GLIBCXX_END_NAMESPACE_VERSION
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
55 template<
typename _Key,
typename _Value,
56 typename _ExtractKey,
typename _Equal,
57 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
62 template<
class _Iterator>
63 inline typename std::iterator_traits<_Iterator>::difference_type
64 __distance_fw(_Iterator __first, _Iterator __last,
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)
78 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
79 return __distance_fw(__first, __last, _Tag());
83 template <
typename _Key,
typename _Hash>
85 noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
90 template<
typename _Tp>
92 operator()(_Tp&& __x)
const
93 {
return std::forward<_Tp>(__x); }
98 template<
typename _Tp>
100 operator()(_Tp&& __x) const
101 -> decltype(std::get<0>(std::
forward<_Tp>(__x)))
102 {
return std::get<0>(std::forward<_Tp>(__x)); }
105 template<
typename _NodeAlloc>
110 template<
typename _NodeAlloc>
111 struct _ReuseOrAllocNode
114 using __node_alloc_type = _NodeAlloc;
116 using __value_alloc_type =
typename __hashtable_alloc::__value_alloc_type;
118 typename __hashtable_alloc::__value_alloc_traits;
120 typename __hashtable_alloc::__node_alloc_traits;
121 using __node_type =
typename __hashtable_alloc::__node_type;
124 _ReuseOrAllocNode(__node_type* __nodes, __hashtable_alloc& __h)
125 : _M_nodes(__nodes), _M_h(__h) { }
126 _ReuseOrAllocNode(
const _ReuseOrAllocNode&) =
delete;
129 { _M_h._M_deallocate_nodes(_M_nodes); }
131 template<
typename _Arg>
133 operator()(_Arg&& __arg)
const
137 __node_type* __node = _M_nodes;
138 _M_nodes = _M_nodes->_M_next();
139 __node->_M_nxt =
nullptr;
140 __value_alloc_type __a(_M_h._M_node_allocator());
141 __value_alloc_traits::destroy(__a, __node->_M_valptr());
144 __value_alloc_traits::construct(__a, __node->_M_valptr(),
145 std::forward<_Arg>(__arg));
149 __node->~__node_type();
150 __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
152 __throw_exception_again;
156 return _M_h._M_allocate_node(std::forward<_Arg>(__arg));
160 mutable __node_type* _M_nodes;
161 __hashtable_alloc& _M_h;
166 template<
typename _NodeAlloc>
170 using __hashtable_alloc = _Hashtable_alloc<_NodeAlloc>;
171 using __node_type =
typename __hashtable_alloc::__node_type;
174 _AllocNode(__hashtable_alloc& __h)
177 template<
typename _Arg>
179 operator()(_Arg&& __arg)
const
180 {
return _M_h._M_allocate_node(std::forward<_Arg>(__arg)); }
183 __hashtable_alloc& _M_h;
211 template<
bool _Cache_hash_code,
bool _Constant_iterators,
bool _Unique_keys>
241 template<
typename _Value>
244 typedef _Value value_type;
246 __gnu_cxx::__aligned_buffer<_Value> _M_storage;
250 {
return _M_storage._M_ptr(); }
253 _M_valptr()
const noexcept
254 {
return _M_storage._M_ptr(); }
258 {
return *_M_valptr(); }
261 _M_v()
const noexcept
262 {
return *_M_valptr(); }
268 template<
typename _Value,
bool _Cache_hash_code>
276 template<
typename _Value>
279 std::size_t _M_hash_code;
282 _M_next()
const noexcept
283 {
return static_cast<_Hash_node*
>(this->_M_nxt); }
291 template<
typename _Value>
295 _M_next()
const noexcept
296 {
return static_cast<_Hash_node*
>(this->_M_nxt); }
300 template<
typename _Value,
bool _Cache_hash_code>
312 { _M_cur = _M_cur->_M_next(); }
315 template<
typename _Value,
bool _Cache_hash_code>
320 {
return __x._M_cur == __y._M_cur; }
322 template<
typename _Value,
bool _Cache_hash_code>
324 operator!=(
const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
325 const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
327 {
return __x._M_cur != __y._M_cur; }
330 template<
typename _Value,
bool __constant_iterators,
bool __cache>
339 typedef _Value value_type;
340 typedef std::ptrdiff_t difference_type;
343 using pointer =
typename std::conditional<__constant_iterators,
344 const _Value*, _Value*>::type;
346 using reference =
typename std::conditional<__constant_iterators,
347 const _Value&, _Value&>::type;
357 operator*()
const noexcept
358 {
return this->_M_cur->_M_v(); }
361 operator->()
const noexcept
362 {
return this->_M_cur->_M_valptr(); }
365 operator++() noexcept
372 operator++(
int) noexcept
381 template<
typename _Value,
bool __constant_iterators,
bool __cache>
390 typedef _Value value_type;
391 typedef std::ptrdiff_t difference_type;
394 typedef const _Value* pointer;
395 typedef const _Value& reference;
405 __cache>& __x) noexcept
409 operator*()
const noexcept
410 {
return this->_M_cur->_M_v(); }
413 operator->()
const noexcept
414 {
return this->_M_cur->_M_valptr(); }
417 operator++() noexcept
424 operator++(
int) noexcept
439 typedef std::size_t first_argument_type;
440 typedef std::size_t second_argument_type;
441 typedef std::size_t result_type;
444 operator()(first_argument_type __num,
445 second_argument_type __den)
const noexcept
446 {
return __num % __den; }
461 : _M_max_load_factor(__z), _M_next_resize(0) { }
464 max_load_factor()
const noexcept
465 {
return _M_max_load_factor; }
469 _M_next_bkt(std::size_t __n)
const;
473 _M_bkt_for_elements(std::size_t __n)
const
474 {
return __builtin_ceil(__n / (
long double)_M_max_load_factor); }
481 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
482 std::size_t __n_ins)
const;
484 typedef std::size_t _State;
488 {
return _M_next_resize; }
492 { _M_next_resize = 0; }
495 _M_reset(_State __state)
496 { _M_next_resize = __state; }
498 enum { _S_n_primes =
sizeof(
unsigned long) != 8 ? 256 : 256 + 48 };
500 static const std::size_t _S_growth_factor = 2;
502 float _M_max_load_factor;
503 mutable std::size_t _M_next_resize;
524 template<
typename _Key,
typename _Value,
typename _Alloc,
525 typename _ExtractKey,
typename _Equal,
526 typename _H1,
typename _H2,
typename _Hash,
527 typename _RehashPolicy,
typename _Traits,
528 bool _Unique_keys = _Traits::__unique_keys::value>
532 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
533 typename _H1,
typename _H2,
typename _Hash,
534 typename _RehashPolicy,
typename _Traits>
535 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
536 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
542 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
543 typename _H1,
typename _H2,
typename _Hash,
544 typename _RehashPolicy,
typename _Traits>
545 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
546 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
551 _Equal, _H1, _H2, _Hash,
556 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
558 using __hash_code =
typename __hashtable_base::__hash_code;
559 using __node_type =
typename __hashtable_base::__node_type;
562 using key_type =
typename __hashtable_base::key_type;
567 operator[](
const key_type& __k);
570 operator[](key_type&& __k);
575 at(
const key_type& __k);
578 at(
const key_type& __k)
const;
581 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
582 typename _H1,
typename _H2,
typename _Hash,
583 typename _RehashPolicy,
typename _Traits>
585 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
586 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
587 operator[](
const key_type& __k)
590 __hashtable* __h =
static_cast<__hashtable*
>(
this);
591 __hash_code __code = __h->_M_hash_code(__k);
592 std::size_t __n = __h->_M_bucket_index(__k, __code);
593 __node_type* __p = __h->_M_find_node(__n, __k, __code);
600 return __h->_M_insert_unique_node(__n, __code, __p)->second;
603 return __p->_M_v().second;
606 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
607 typename _H1,
typename _H2,
typename _Hash,
608 typename _RehashPolicy,
typename _Traits>
610 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
611 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
612 operator[](key_type&& __k)
615 __hashtable* __h =
static_cast<__hashtable*
>(
this);
616 __hash_code __code = __h->_M_hash_code(__k);
617 std::size_t __n = __h->_M_bucket_index(__k, __code);
618 __node_type* __p = __h->_M_find_node(__n, __k, __code);
623 std::forward_as_tuple(std::move(__k)),
625 return __h->_M_insert_unique_node(__n, __code, __p)->second;
628 return __p->_M_v().second;
631 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
632 typename _H1,
typename _H2,
typename _Hash,
633 typename _RehashPolicy,
typename _Traits>
635 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
636 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
637 at(
const key_type& __k)
640 __hashtable* __h =
static_cast<__hashtable*
>(
this);
641 __hash_code __code = __h->_M_hash_code(__k);
642 std::size_t __n = __h->_M_bucket_index(__k, __code);
643 __node_type* __p = __h->_M_find_node(__n, __k, __code);
646 __throw_out_of_range(__N(
"_Map_base::at"));
647 return __p->_M_v().second;
650 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
651 typename _H1,
typename _H2,
typename _Hash,
652 typename _RehashPolicy,
typename _Traits>
654 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
655 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
656 at(
const key_type& __k)
const
657 ->
const mapped_type&
659 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
660 __hash_code __code = __h->_M_hash_code(__k);
661 std::size_t __n = __h->_M_bucket_index(__k, __code);
662 __node_type* __p = __h->_M_find_node(__n, __k, __code);
665 __throw_out_of_range(__N(
"_Map_base::at"));
666 return __p->_M_v().second;
674 template<
typename _Key,
typename _Value,
typename _Alloc,
675 typename _ExtractKey,
typename _Equal,
676 typename _H1,
typename _H2,
typename _Hash,
677 typename _RehashPolicy,
typename _Traits>
682 _Equal, _H1, _H2, _Hash,
683 _RehashPolicy, _Traits>;
686 _Equal, _H1, _H2, _Hash,
689 using value_type =
typename __hashtable_base::value_type;
692 using size_type =
typename __hashtable_base::size_type;
694 using __unique_keys =
typename __hashtable_base::__unique_keys;
695 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
697 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
698 using __node_gen_type = _AllocNode<__node_alloc_type>;
701 _M_conjure_hashtable()
704 template<
typename _InputIterator,
typename _NodeGetter>
706 _M_insert_range(_InputIterator __first, _InputIterator __last,
711 insert(
const value_type& __v)
714 __node_gen_type __node_gen(__h);
715 return __h._M_insert(__v, __node_gen, __unique_keys());
719 insert(const_iterator __hint,
const value_type& __v)
722 __node_gen_type __node_gen(__h);
723 return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
728 { this->insert(__l.begin(), __l.end()); }
730 template<
typename _InputIterator>
732 insert(_InputIterator __first, _InputIterator __last)
735 __node_gen_type __node_gen(__h);
736 return _M_insert_range(__first, __last, __node_gen);
740 template<
typename _Key,
typename _Value,
typename _Alloc,
741 typename _ExtractKey,
typename _Equal,
742 typename _H1,
typename _H2,
typename _Hash,
743 typename _RehashPolicy,
typename _Traits>
744 template<
typename _InputIterator,
typename _NodeGetter>
746 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
747 _RehashPolicy, _Traits>::
748 _M_insert_range(_InputIterator __first, _InputIterator __last,
749 const _NodeGetter& __node_gen)
751 using __rehash_type =
typename __hashtable::__rehash_type;
752 using __rehash_state =
typename __hashtable::__rehash_state;
755 size_type __n_elt = __detail::__distance_fw(__first, __last);
757 __hashtable& __h = _M_conjure_hashtable();
758 __rehash_type& __rehash = __h._M_rehash_policy;
759 const __rehash_state& __saved_state = __rehash._M_state();
760 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
761 __h._M_element_count,
764 if (__do_rehash.first)
765 __h._M_rehash(__do_rehash.second, __saved_state);
767 for (; __first != __last; ++__first)
768 __h._M_insert(*__first, __node_gen, __unique_keys());
776 template<
typename _Key,
typename _Value,
typename _Alloc,
777 typename _ExtractKey,
typename _Equal,
778 typename _H1,
typename _H2,
typename _Hash,
779 typename _RehashPolicy,
typename _Traits,
780 bool _Constant_iterators = _Traits::__constant_iterators::value,
781 bool _Unique_keys = _Traits::__unique_keys::value>
785 template<
typename _Key,
typename _Value,
typename _Alloc,
786 typename _ExtractKey,
typename _Equal,
787 typename _H1,
typename _H2,
typename _Hash,
788 typename _RehashPolicy,
typename _Traits>
789 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
790 _RehashPolicy, _Traits, true, true>
791 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
792 _H1, _H2, _Hash, _RehashPolicy, _Traits>
795 _Equal, _H1, _H2, _Hash,
796 _RehashPolicy, _Traits>;
797 using value_type =
typename __base_type::value_type;
798 using iterator =
typename __base_type::iterator;
799 using const_iterator =
typename __base_type::const_iterator;
801 using __unique_keys =
typename __base_type::__unique_keys;
803 using __node_gen_type =
typename __base_type::__node_gen_type;
805 using __base_type::insert;
808 insert(value_type&& __v)
811 __node_gen_type __node_gen(__h);
812 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
816 insert(const_iterator __hint, value_type&& __v)
819 __node_gen_type __node_gen(__h);
820 return __h._M_insert(__hint, std::move(__v), __node_gen,
826 template<
typename _Key,
typename _Value,
typename _Alloc,
827 typename _ExtractKey,
typename _Equal,
828 typename _H1,
typename _H2,
typename _Hash,
829 typename _RehashPolicy,
typename _Traits>
830 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
831 _RehashPolicy, _Traits, true, false>
832 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
833 _H1, _H2, _Hash, _RehashPolicy, _Traits>
836 _Equal, _H1, _H2, _Hash,
837 _RehashPolicy, _Traits>;
838 using value_type =
typename __base_type::value_type;
839 using iterator =
typename __base_type::iterator;
840 using const_iterator =
typename __base_type::const_iterator;
842 using __unique_keys =
typename __base_type::__unique_keys;
844 using __node_gen_type =
typename __base_type::__node_gen_type;
846 using __base_type::insert;
849 insert(value_type&& __v)
852 __node_gen_type __node_gen(__h);
853 return __h._M_insert(std::move(__v), __node_gen, __unique_keys());
857 insert(const_iterator __hint, value_type&& __v)
860 __node_gen_type __node_gen(__h);
861 return __h._M_insert(__hint, std::move(__v), __node_gen,
867 template<
typename _Key,
typename _Value,
typename _Alloc,
868 typename _ExtractKey,
typename _Equal,
869 typename _H1,
typename _H2,
typename _Hash,
870 typename _RehashPolicy,
typename _Traits,
bool _Unique_keys>
871 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
872 _RehashPolicy, _Traits, false, _Unique_keys>
873 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
874 _H1, _H2, _Hash, _RehashPolicy, _Traits>
877 _Equal, _H1, _H2, _Hash,
878 _RehashPolicy, _Traits>;
879 using value_type =
typename __base_type::value_type;
880 using iterator =
typename __base_type::iterator;
881 using const_iterator =
typename __base_type::const_iterator;
883 using __unique_keys =
typename __base_type::__unique_keys;
885 using __ireturn_type =
typename __base_type::__ireturn_type;
887 using __base_type::insert;
889 template<
typename _Pair>
890 using __is_cons = std::is_constructible<value_type, _Pair&&>;
892 template<
typename _Pair>
893 using _IFcons = std::enable_if<__is_cons<_Pair>::value>;
895 template<
typename _Pair>
896 using _IFconsp =
typename _IFcons<_Pair>::type;
898 template<
typename _Pair,
typename = _IFconsp<_Pair>>
903 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
906 template<
typename _Pair,
typename = _IFconsp<_Pair>>
908 insert(const_iterator __hint, _Pair&& __v)
911 return __h._M_emplace(__hint, __unique_keys(),
912 std::forward<_Pair>(__v));
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>
929 template<
typename _Key,
typename _Value,
typename _Alloc,
930 typename _ExtractKey,
typename _Equal,
931 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
936 _Equal, _H1, _H2, _Hash,
940 max_load_factor()
const noexcept
943 return __this->__rehash_policy().max_load_factor();
947 max_load_factor(
float __z)
954 reserve(std::size_t __n)
957 __this->rehash(__builtin_ceil(__n / max_load_factor()));
967 template<
int _Nm,
typename _Tp,
968 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
972 template<
int _Nm,
typename _Tp>
978 template<
typename _OtherTp>
980 : _Tp(std::forward<_OtherTp>(__tp))
985 {
return static_cast<const _Tp&
>(__eboh); }
989 {
return static_cast<_Tp&
>(__eboh); }
993 template<
int _Nm,
typename _Tp>
998 template<
typename _OtherTp>
1000 : _M_tp(std::forward<_OtherTp>(__tp))
1005 {
return __eboh._M_tp; }
1009 {
return __eboh._M_tp; }
1021 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1022 typename _H1,
typename _H2,
typename _Hash,
1023 bool __cache_hash_code>
1046 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1047 typename _H1,
typename _H2,
typename _Hash,
1048 bool __cache_hash_code>
1053 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1054 typename _H1,
typename _H2,
typename _Hash>
1064 typedef void* __hash_code;
1076 _M_hash_code(
const _Key& __key)
const
1080 _M_bucket_index(
const _Key& __k, __hash_code, std::size_t __n)
const
1081 {
return _M_ranged_hash()(__k, __n); }
1084 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1085 noexcept( noexcept(declval<const _Hash&>()(declval<const _Key&>(),
1087 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1100 std::swap(_M_extract(), __x._M_extract());
1101 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1105 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1108 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1111 _M_ranged_hash()
const {
return __ebo_hash::_S_cget(*
this); }
1114 _M_ranged_hash() {
return __ebo_hash::_S_get(*
this); }
1123 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1124 typename _H1,
typename _H2,
typename _Hash>
1125 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
1130 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1131 typename _H1,
typename _H2>
1145 _Default_ranged_hash, false>;
1151 hash_function()
const
1155 typedef std::size_t __hash_code;
1163 const _H1& __h1,
const _H2& __h2,
1164 const _Default_ranged_hash&)
1168 _M_hash_code(
const _Key& __k)
const
1169 {
return _M_h1()(__k); }
1172 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const
1173 {
return _M_h2()(__c, __n); }
1176 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1177 noexcept( noexcept(declval<const _H1&>()(declval<const _Key&>()))
1178 && noexcept(declval<const _H2&>()((__hash_code)0,
1180 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1193 std::swap(_M_extract(), __x._M_extract());
1194 std::swap(_M_h1(), __x._M_h1());
1195 std::swap(_M_h2(), __x._M_h2());
1199 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1202 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1205 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1208 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1211 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1214 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1220 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1221 typename _H1,
typename _H2>
1231 _Default_ranged_hash, true>;
1241 hash_function()
const
1245 typedef std::size_t __hash_code;
1251 const _H1& __h1,
const _H2& __h2,
1252 const _Default_ranged_hash&)
1256 _M_hash_code(
const _Key& __k)
const
1257 {
return _M_h1()(__k); }
1260 _M_bucket_index(
const _Key&, __hash_code __c,
1261 std::size_t __n)
const
1262 {
return _M_h2()(__c, __n); }
1265 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1266 noexcept( noexcept(declval<const _H2&>()((__hash_code)0,
1268 {
return _M_h2()(__p->_M_hash_code, __n); }
1271 _M_store_code(
__node_type* __n, __hash_code __c)
const
1272 { __n->_M_hash_code = __c; }
1276 { __to->_M_hash_code = __from->_M_hash_code; }
1281 std::swap(_M_extract(), __x._M_extract());
1282 std::swap(_M_h1(), __x._M_h1());
1283 std::swap(_M_h2(), __x._M_h2());
1287 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1290 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1293 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1296 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1299 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1302 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1309 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1310 typename _Equal,
typename _HashCodeType,
1311 bool __cache_hash_code>
1315 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1316 typename _Equal,
typename _HashCodeType>
1320 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1322 {
return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v())); }
1326 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1327 typename _Equal,
typename _HashCodeType>
1331 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1333 {
return __eq(__k, __extract(__n->_M_v())); }
1338 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1339 typename _H1,
typename _H2,
typename _Hash>
1341 _H1, _H2, _Hash, true>
1347 _H1, _H2, _Hash,
true>;
1352 std::size_t __bkt, std::size_t __bkt_count)
1354 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1359 _M_cur = _M_cur->_M_next();
1363 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1365 if (__bkt != _M_bucket)
1371 std::size_t _M_bucket;
1372 std::size_t _M_bucket_count;
1376 _M_curr()
const {
return _M_cur; }
1379 _M_get_bucket()
const {
return _M_bucket; }
1386 template<typename _Tp, bool _IsEmpty = std::is_empty<_Tp>::value>
1387 struct _Hash_code_storage
1389 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1392 _M_h() {
return _M_storage._M_ptr(); }
1395 _M_h()
const {
return _M_storage._M_ptr(); }
1399 template<
typename _Tp>
1400 struct _Hash_code_storage<_Tp, true>
1407 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1410 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1413 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1414 typename _H1,
typename _H2,
typename _Hash>
1415 using __hash_code_for_local_iter
1416 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1417 _H1, _H2, _Hash,
false>>;
1420 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1421 typename _H1,
typename _H2,
typename _Hash>
1422 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1423 _H1, _H2, _Hash, false>
1424 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1427 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1428 _H1, _H2, _Hash,
false>;
1430 _Local_iterator_base() : _M_bucket_count(-1) { }
1432 _Local_iterator_base(
const __hash_code_base&
__base,
1433 _Hash_node<_Value, false>* __p,
1434 std::size_t __bkt, std::size_t __bkt_count)
1435 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1436 { _M_init(__base); }
1438 ~_Local_iterator_base()
1440 if (_M_bucket_count != -1)
1444 _Local_iterator_base(
const _Local_iterator_base& __iter)
1445 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1446 _M_bucket_count(__iter._M_bucket_count)
1448 if (_M_bucket_count != -1)
1449 _M_init(*__iter._M_h());
1452 _Local_iterator_base&
1453 operator=(
const _Local_iterator_base& __iter)
1455 if (_M_bucket_count != -1)
1457 _M_cur = __iter._M_cur;
1458 _M_bucket = __iter._M_bucket;
1459 _M_bucket_count = __iter._M_bucket_count;
1460 if (_M_bucket_count != -1)
1461 _M_init(*__iter._M_h());
1468 _M_cur = _M_cur->_M_next();
1471 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1473 if (__bkt != _M_bucket)
1478 _Hash_node<_Value, false>* _M_cur;
1479 std::size_t _M_bucket;
1480 std::size_t _M_bucket_count;
1483 _M_init(
const __hash_code_base&
__base)
1484 { ::new(this->_M_h()) __hash_code_base(__base); }
1487 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1491 _M_curr()
const {
return _M_cur; }
1494 _M_get_bucket()
const {
return _M_bucket; }
1497 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1498 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1500 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1501 _H1, _H2, _Hash, __cache>& __x,
1502 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1503 _H1, _H2, _Hash, __cache>& __y)
1504 {
return __x._M_curr() == __y._M_curr(); }
1506 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1507 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1509 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1510 _H1, _H2, _Hash, __cache>& __x,
1511 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1512 _H1, _H2, _Hash, __cache>& __y)
1513 {
return __x._M_curr() != __y._M_curr(); }
1516 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1517 typename _H1,
typename _H2,
typename _Hash,
1518 bool __constant_iterators,
bool __cache>
1521 _H1, _H2, _Hash, __cache>
1525 _H1, _H2, _Hash, __cache>;
1526 using __hash_code_base =
typename __base_type::__hash_code_base;
1528 typedef _Value value_type;
1529 typedef typename std::conditional<__constant_iterators,
1530 const _Value*, _Value*>::type
1532 typedef typename std::conditional<__constant_iterators,
1533 const _Value&, _Value&>::type
1535 typedef std::ptrdiff_t difference_type;
1542 std::size_t __bkt, std::size_t __bkt_count)
1548 {
return this->_M_cur->_M_v(); }
1552 {
return this->_M_cur->_M_valptr(); }
1571 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1572 typename _H1,
typename _H2,
typename _Hash,
1573 bool __constant_iterators,
bool __cache>
1576 _H1, _H2, _Hash, __cache>
1580 _H1, _H2, _Hash, __cache>;
1581 using __hash_code_base =
typename __base_type::__hash_code_base;
1584 typedef _Value value_type;
1585 typedef const _Value* pointer;
1586 typedef const _Value& reference;
1587 typedef std::ptrdiff_t difference_type;
1594 std::size_t __bkt, std::size_t __bkt_count)
1600 __constant_iterators,
1607 {
return this->_M_cur->_M_v(); }
1611 {
return this->_M_cur->_M_valptr(); }
1639 template<
typename _Key,
typename _Value,
1640 typename _ExtractKey,
typename _Equal,
1641 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1644 _Traits::__hash_cached::value>,
1648 typedef _Key key_type;
1649 typedef _Value value_type;
1650 typedef _Equal key_equal;
1651 typedef std::size_t size_type;
1652 typedef std::ptrdiff_t difference_type;
1654 using __traits_type = _Traits;
1655 using __hash_cached =
typename __traits_type::__hash_cached;
1656 using __constant_iterators =
typename __traits_type::__constant_iterators;
1657 using __unique_keys =
typename __traits_type::__unique_keys;
1661 __hash_cached::value>;
1663 using __hash_code =
typename __hash_code_base::__hash_code;
1664 using __node_type =
typename __hash_code_base::__node_type;
1667 __constant_iterators::value,
1668 __hash_cached::value>;
1671 __constant_iterators::value,
1672 __hash_cached::value>;
1675 _ExtractKey, _H1, _H2, _Hash,
1676 __constant_iterators::value,
1677 __hash_cached::value>;
1681 _ExtractKey, _H1, _H2, _Hash,
1682 __constant_iterators::value,
1683 __hash_cached::value>;
1685 using __ireturn_type =
typename std::conditional<__unique_keys::value,
1690 using _EqualHelper =
_Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1691 __hash_code, __hash_cached::value>;
1695 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1696 const _Hash& __hash,
const _Equal& __eq)
1697 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1701 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const
1703 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1708 _M_swap(_Hashtable_base& __x)
1710 __hash_code_base::_M_swap(__x);
1711 std::swap(_M_eq(), __x._M_eq());
1715 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1718 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1729 template<
typename _Uiterator>
1731 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1735 template<
typename _Uiterator>
1738 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1739 _Uiterator __first2)
1741 for (; __first1 != __last1; ++__first1, ++__first2)
1742 if (!(*__first1 == *__first2))
1745 if (__first1 == __last1)
1748 _Uiterator __last2 = __first2;
1751 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1753 _Uiterator __tmp = __first1;
1754 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1761 std::ptrdiff_t __n2 = 0;
1762 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1763 if (*__tmp == *__it1)
1769 std::ptrdiff_t __n1 = 0;
1770 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1771 if (*__tmp == *__it1)
1788 template<
typename _Key,
typename _Value,
typename _Alloc,
1789 typename _ExtractKey,
typename _Equal,
1790 typename _H1,
typename _H2,
typename _Hash,
1791 typename _RehashPolicy,
typename _Traits,
1792 bool _Unique_keys = _Traits::__unique_keys::value>
1796 template<
typename _Key,
typename _Value,
typename _Alloc,
1797 typename _ExtractKey,
typename _Equal,
1798 typename _H1,
typename _H2,
typename _Hash,
1799 typename _RehashPolicy,
typename _Traits>
1801 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1804 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1810 template<
typename _Key,
typename _Value,
typename _Alloc,
1811 typename _ExtractKey,
typename _Equal,
1812 typename _H1,
typename _H2,
typename _Hash,
1813 typename _RehashPolicy,
typename _Traits>
1815 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1816 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1817 _M_equal(
const __hashtable& __other)
const
1819 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1821 if (__this->size() != __other.size())
1824 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1826 const auto __ity = __other.find(_ExtractKey()(*__itx));
1827 if (__ity == __other.end() || !bool(*__ity == *__itx))
1834 template<
typename _Key,
typename _Value,
typename _Alloc,
1835 typename _ExtractKey,
typename _Equal,
1836 typename _H1,
typename _H2,
typename _Hash,
1837 typename _RehashPolicy,
typename _Traits>
1839 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1843 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1849 template<
typename _Key,
typename _Value,
typename _Alloc,
1850 typename _ExtractKey,
typename _Equal,
1851 typename _H1,
typename _H2,
typename _Hash,
1852 typename _RehashPolicy,
typename _Traits>
1854 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1855 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1856 _M_equal(
const __hashtable& __other)
const
1858 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1860 if (__this->size() != __other.size())
1863 for (
auto __itx = __this->begin(); __itx != __this->end();)
1865 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1866 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1872 if (!_S_is_permutation(__xrange.first, __xrange.second,
1876 __itx = __xrange.second;
1885 template<
typename _NodeAlloc>
1886 struct _Hashtable_alloc :
private _Hashtable_ebo_helper<0, _NodeAlloc>
1889 using __ebo_node_alloc = _Hashtable_ebo_helper<0, _NodeAlloc>;
1891 using __node_type =
typename _NodeAlloc::value_type;
1892 using __node_alloc_type = _NodeAlloc;
1896 using __value_type =
typename __node_type::value_type;
1897 using __value_alloc_type =
1898 __alloc_rebind<__node_alloc_type, __value_type>;
1901 using __node_base = __detail::_Hash_node_base;
1902 using __bucket_type = __node_base*;
1903 using __bucket_alloc_type =
1904 __alloc_rebind<__node_alloc_type, __bucket_type>;
1907 _Hashtable_alloc() =
default;
1908 _Hashtable_alloc(
const _Hashtable_alloc&) =
default;
1909 _Hashtable_alloc(_Hashtable_alloc&&) =
default;
1911 template<
typename _Alloc>
1912 _Hashtable_alloc(_Alloc&& __a)
1913 : __ebo_node_alloc(std::
forward<_Alloc>(__a))
1918 {
return __ebo_node_alloc::_S_get(*
this); }
1920 const __node_alloc_type&
1921 _M_node_allocator()
const
1922 {
return __ebo_node_alloc::_S_cget(*
this); }
1924 template<
typename... _Args>
1926 _M_allocate_node(_Args&&... __args);
1929 _M_deallocate_node(__node_type* __n);
1933 _M_deallocate_nodes(__node_type* __n);
1936 _M_allocate_buckets(std::size_t __n);
1939 _M_deallocate_buckets(__bucket_type*, std::size_t __n);
1944 template<
typename _NodeAlloc>
1945 template<
typename... _Args>
1946 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
1947 _Hashtable_alloc<_NodeAlloc>::_M_allocate_node(_Args&&... __args)
1949 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
1953 __value_alloc_type __a(_M_node_allocator());
1954 ::new ((
void*)__n) __node_type;
1955 __value_alloc_traits::construct(__a, __n->_M_valptr(),
1956 std::
forward<_Args>(__args)...);
1961 __node_alloc_traits::deallocate(_M_node_allocator(), __nptr, 1);
1962 __throw_exception_again;
1966 template<
typename _NodeAlloc>
1968 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
1970 typedef typename __node_alloc_traits::pointer _Ptr;
1972 __value_alloc_type __a(_M_node_allocator());
1973 __value_alloc_traits::destroy(__a, __n->_M_valptr());
1974 __n->~__node_type();
1975 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
1978 template<
typename _NodeAlloc>
1980 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
1984 __node_type* __tmp = __n;
1985 __n = __n->_M_next();
1986 _M_deallocate_node(__tmp);
1990 template<
typename _NodeAlloc>
1991 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
1992 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n)
1994 __bucket_alloc_type __alloc(_M_node_allocator());
1996 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
1998 __builtin_memset(__p, 0, __n *
sizeof(__bucket_type));
2002 template<
typename _NodeAlloc>
2004 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2007 typedef typename __bucket_alloc_traits::pointer _Ptr;
2009 __bucket_alloc_type __alloc(_M_node_allocator());
2010 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
2014 _GLIBCXX_END_NAMESPACE_VERSION
2018 #endif // _HASHTABLE_POLICY_H
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Uniform interface to all pointer-like types.
Forward iterators support a superset of input iterator operations.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr piecewise_construct_t piecewise_construct
piecewise_construct
Uniform interface to C++98 and C++0x allocators.
Default range hashing function: use division to fold a large number into the range [0...
Struct holding two objects of arbitrary type.
complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Uniform interface to all allocator types.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Node iterators, used to iterate through all the hashtable.
Base class for node iterators.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Node const_iterators, used to iterate through all the hashtable.
Primary class template, tuple.