31#ifndef _HASHTABLE_POLICY_H
32#define _HASHTABLE_POLICY_H 1
34namespace 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>
58 struct _Hashtable_base;
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
98 template<
typename _Tp>
100 operator()(_Tp&& __x)
const
105 template<
typename _NodeAlloc>
106 struct _Hashtable_alloc;
110 template<
typename _NodeAlloc>
111 struct _ReuseOrAllocNode
114 using __node_alloc_type = _NodeAlloc;
115 using __hashtable_alloc = _Hashtable_alloc<__node_alloc_type>;
116 using __value_alloc_type =
typename __hashtable_alloc::__value_alloc_type;
117 using __value_alloc_traits =
118 typename __hashtable_alloc::__value_alloc_traits;
119 using __node_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(),
149 __node->~__node_type();
150 __node_alloc_traits::deallocate(_M_h._M_node_allocator(),
152 __throw_exception_again;
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
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>
327 {
return __x._M_cur !=
__y._M_cur; }
330 template<
typename _Value,
bool __constant_iterators,
bool __cache>
339 typedef _Value value_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;
394 typedef const _Value* pointer;
395 typedef const _Value& reference;
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
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
484 typedef std::size_t _State;
488 {
return _M_next_resize; }
492 { _M_next_resize = 0; }
498 static const std::size_t _S_growth_factor = 2;
500 float _M_max_load_factor;
501 mutable std::size_t _M_next_resize;
522 template<
typename _Key,
typename _Value,
typename _Alloc,
523 typename _ExtractKey,
typename _Equal,
525 typename _RehashPolicy,
typename _Traits,
530 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
532 typename _RehashPolicy,
typename _Traits>
540 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
542 typename _RehashPolicy,
typename _Traits>
556 using __hash_code =
typename __hashtable_base::__hash_code;
557 using __node_type =
typename __hashtable_base::__node_type;
560 using key_type =
typename __hashtable_base::key_type;
565 operator[](
const key_type&
__k);
568 operator[](key_type&&
__k);
573 at(
const key_type&
__k);
576 at(
const key_type&
__k)
const;
579 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
581 typename _RehashPolicy,
typename _Traits>
585 operator[](
const key_type&
__k)
588 __hashtable*
__h =
static_cast<__hashtable*
>(
this);
598 return __h->_M_insert_unique_node(__n,
__code, __p)->second;
601 return __p->_M_v().second;
604 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
605 typename _H1,
typename _H2,
typename _Hash,
606 typename _RehashPolicy,
typename _Traits>
608 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
609 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
610 operator[](key_type&& __k)
613 __hashtable* __h =
static_cast<__hashtable*
>(
this);
614 __hash_code __code = __h->_M_hash_code(__k);
615 std::size_t __n = __h->_M_bucket_index(__k, __code);
616 __node_type* __p = __h->_M_find_node(__n, __k, __code);
621 std::forward_as_tuple(std::move(__k)),
623 return __h->_M_insert_unique_node(__n, __code, __p)->second;
626 return __p->_M_v().second;
629 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
630 typename _H1,
typename _H2,
typename _Hash,
631 typename _RehashPolicy,
typename _Traits>
633 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
634 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
635 at(
const key_type& __k)
638 __hashtable* __h =
static_cast<__hashtable*
>(
this);
639 __hash_code __code = __h->_M_hash_code(__k);
640 std::size_t __n = __h->_M_bucket_index(__k, __code);
641 __node_type* __p = __h->_M_find_node(__n, __k, __code);
644 __throw_out_of_range(__N(
"_Map_base::at"));
645 return __p->_M_v().second;
648 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
649 typename _H1,
typename _H2,
typename _Hash,
650 typename _RehashPolicy,
typename _Traits>
652 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
653 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
654 at(
const key_type& __k)
const
655 ->
const mapped_type&
657 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
658 __hash_code __code = __h->_M_hash_code(__k);
659 std::size_t __n = __h->_M_bucket_index(__k, __code);
660 __node_type* __p = __h->_M_find_node(__n, __k, __code);
663 __throw_out_of_range(__N(
"_Map_base::at"));
664 return __p->_M_v().second;
672 template<
typename _Key,
typename _Value,
typename _Alloc,
673 typename _ExtractKey,
typename _Equal,
674 typename _H1,
typename _H2,
typename _Hash,
675 typename _RehashPolicy,
typename _Traits>
681 _RehashPolicy, _Traits>;
687 using value_type =
typename __hashtable_base::value_type;
690 using size_type =
typename __hashtable_base::size_type;
692 using __unique_keys =
typename __hashtable_base::__unique_keys;
693 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
699 _M_conjure_hashtable()
702 template<
typename _InputIterator,
typename _NodeGetter>
709 insert(
const value_type&
__v)
717 insert(const_iterator
__hint,
const value_type&
__v)
726 { this->insert(
__l.begin(),
__l.end()); }
728 template<
typename _InputIterator>
734 return _M_insert_range(__first, __last,
__node_gen);
738 template<
typename _Key,
typename _Value,
typename _Alloc,
739 typename _ExtractKey,
typename _Equal,
741 typename _RehashPolicy,
typename _Traits>
742 template<
typename _InputIterator,
typename _NodeGetter>
745 _RehashPolicy, _Traits>::
749 using __rehash_type =
typename __hashtable::__rehash_type;
750 using __rehash_state =
typename __hashtable::__rehash_state;
753 size_type
__n_elt = __detail::__distance_fw(__first, __last);
755 __hashtable&
__h = _M_conjure_hashtable();
759 __h._M_element_count,
765 for (; __first != __last; ++__first)
774 template<
typename _Key,
typename _Value,
typename _Alloc,
775 typename _ExtractKey,
typename _Equal,
777 typename _RehashPolicy,
typename _Traits,
783 template<
typename _Key,
typename _Value,
typename _Alloc,
784 typename _ExtractKey,
typename _Equal,
786 typename _RehashPolicy,
typename _Traits>
789 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
790 _H1, _H2, _Hash, _RehashPolicy, _Traits>
794 _RehashPolicy, _Traits>;
795 using value_type =
typename __base_type::value_type;
796 using iterator =
typename __base_type::iterator;
797 using const_iterator =
typename __base_type::const_iterator;
799 using __unique_keys =
typename __base_type::__unique_keys;
803 using __base_type::insert;
806 insert(value_type&&
__v)
808 __hashtable&
__h = this->_M_conjure_hashtable();
814 insert(const_iterator
__hint, value_type&&
__v)
816 __hashtable&
__h = this->_M_conjure_hashtable();
824 template<
typename _Key,
typename _Value,
typename _Alloc,
825 typename _ExtractKey,
typename _Equal,
827 typename _RehashPolicy,
typename _Traits>
830 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
831 _H1, _H2, _Hash, _RehashPolicy, _Traits>
835 _RehashPolicy, _Traits>;
836 using value_type =
typename __base_type::value_type;
837 using iterator =
typename __base_type::iterator;
838 using const_iterator =
typename __base_type::const_iterator;
840 using __unique_keys =
typename __base_type::__unique_keys;
844 using __base_type::insert;
847 insert(value_type&&
__v)
849 __hashtable&
__h = this->_M_conjure_hashtable();
855 insert(const_iterator
__hint, value_type&&
__v)
857 __hashtable&
__h = this->_M_conjure_hashtable();
865 template<
typename _Key,
typename _Value,
typename _Alloc,
866 typename _ExtractKey,
typename _Equal,
868 typename _RehashPolicy,
typename _Traits,
bool _Unique_keys>
871 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
872 _H1, _H2, _Hash, _RehashPolicy, _Traits>
876 _RehashPolicy, _Traits>;
877 using value_type =
typename __base_type::value_type;
878 using iterator =
typename __base_type::iterator;
879 using const_iterator =
typename __base_type::const_iterator;
881 using __unique_keys =
typename __base_type::__unique_keys;
883 using __ireturn_type =
typename __base_type::__ireturn_type;
885 using __base_type::insert;
887 template<
typename _Pair>
890 template<
typename _Pair>
893 template<
typename _Pair>
896 template<
typename _Pair,
typename = _IFconsp<_Pair>>
900 __hashtable&
__h = this->_M_conjure_hashtable();
904 template<
typename _Pair,
typename = _IFconsp<_Pair>>
908 __hashtable&
__h = this->_M_conjure_hashtable();
909 return __h._M_emplace(
__hint, __unique_keys(),
920 template<
typename _Key,
typename _Value,
typename _Alloc,
921 typename _ExtractKey,
typename _Equal,
923 typename _RehashPolicy,
typename _Traits>
927 template<
typename _Key,
typename _Value,
typename _Alloc,
928 typename _ExtractKey,
typename _Equal,
929 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
938 max_load_factor()
const noexcept
941 return __this->__rehash_policy().max_load_factor();
945 max_load_factor(
float __z)
952 reserve(std::size_t __n)
965 template<
int _Nm,
typename _Tp,
970 template<
int _Nm,
typename _Tp>
976 template<
typename _OtherTp>
983 {
return static_cast<const _Tp&
>(
__eboh); }
987 {
return static_cast<_Tp&
>(
__eboh); }
991 template<
int _Nm,
typename _Tp>
996 template<
typename _OtherTp>
1019 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1044 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1051 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1062 typedef void* __hash_code;
1078 _M_bucket_index(
const _Key&
__k, __hash_code, std::size_t __n)
const
1079 {
return _M_ranged_hash()(
__k, __n); }
1082 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1085 {
return _M_ranged_hash()(_M_extract()(__p->_M_v()), __n); }
1098 std::swap(_M_extract(), __x._M_extract());
1099 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
1103 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1106 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1109 _M_ranged_hash()
const {
return __ebo_hash::_S_cget(*
this); }
1112 _M_ranged_hash() {
return __ebo_hash::_S_get(*
this); }
1121 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1128 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1129 typename _H1,
typename _H2>
1149 hash_function()
const
1153 typedef std::size_t __hash_code;
1166 _M_hash_code(
const _Key&
__k)
const
1167 {
return _M_h1()(
__k); }
1170 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const
1171 {
return _M_h2()(__c, __n); }
1174 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1178 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v())), __n); }
1191 std::swap(_M_extract(), __x._M_extract());
1192 std::swap(_M_h1(), __x._M_h1());
1193 std::swap(_M_h2(), __x._M_h2());
1197 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1200 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1203 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1206 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1209 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1212 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1218 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1219 typename _H1,
typename _H2>
1239 hash_function()
const
1243 typedef std::size_t __hash_code;
1254 _M_hash_code(
const _Key&
__k)
const
1255 {
return _M_h1()(
__k); }
1258 _M_bucket_index(
const _Key&, __hash_code __c,
1259 std::size_t __n)
const
1260 {
return _M_h2()(__c, __n); }
1263 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1266 {
return _M_h2()(__p->_M_hash_code, __n); }
1269 _M_store_code(
__node_type* __n, __hash_code __c)
const
1270 { __n->_M_hash_code = __c; }
1274 {
__to->_M_hash_code =
__from->_M_hash_code; }
1279 std::swap(_M_extract(), __x._M_extract());
1280 std::swap(_M_h1(), __x._M_h1());
1281 std::swap(_M_h2(), __x._M_h2());
1285 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1288 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1291 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1294 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1297 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1300 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1307 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1313 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1318 _S_equals(
const _Equal& __eq,
const _ExtractKey&
__extract,
1320 {
return __c == __n->_M_hash_code && __eq(
__k,
__extract(__n->_M_v())); }
1324 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1329 _S_equals(
const _Equal& __eq,
const _ExtractKey&
__extract,
1336 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1357 _M_cur = _M_cur->_M_next();
1361 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1363 if (
__bkt != _M_bucket)
1369 std::size_t _M_bucket;
1370 std::size_t _M_bucket_count;
1374 _M_curr()
const {
return _M_cur; }
1377 _M_get_bucket()
const {
return _M_bucket; }
1385 struct _Hash_code_storage
1387 __gnu_cxx::__aligned_buffer<_Tp> _M_storage;
1390 _M_h() {
return _M_storage._M_ptr(); }
1393 _M_h()
const {
return _M_storage._M_ptr(); }
1397 template<
typename _Tp>
1398 struct _Hash_code_storage<_Tp, true>
1405 _M_h() {
return reinterpret_cast<_Tp*
>(
this); }
1408 _M_h()
const {
return reinterpret_cast<const _Tp*
>(
this); }
1411 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1412 typename _H1,
typename _H2,
typename _Hash>
1413 using __hash_code_for_local_iter
1414 = _Hash_code_storage<_Hash_code_base<_Key, _Value, _ExtractKey,
1415 _H1, _H2, _Hash,
false>>;
1418 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1419 typename _H1,
typename _H2,
typename _Hash>
1420 struct _Local_iterator_base<_Key, _Value, _ExtractKey,
1421 _H1, _H2, _Hash, false>
1422 : __hash_code_for_local_iter<_Key, _Value, _ExtractKey, _H1, _H2, _Hash>
1425 using __hash_code_base = _Hash_code_base<_Key, _Value, _ExtractKey,
1426 _H1, _H2, _Hash,
false>;
1428 _Local_iterator_base() : _M_bucket_count(-1) { }
1430 _Local_iterator_base(
const __hash_code_base& __base,
1431 _Hash_node<_Value, false>* __p,
1432 std::size_t __bkt, std::size_t __bkt_count)
1433 : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count)
1434 { _M_init(__base); }
1436 ~_Local_iterator_base()
1438 if (_M_bucket_count != -1)
1442 _Local_iterator_base(
const _Local_iterator_base& __iter)
1443 : _M_cur(__iter._M_cur), _M_bucket(__iter._M_bucket),
1444 _M_bucket_count(__iter._M_bucket_count)
1446 if (_M_bucket_count != -1)
1447 _M_init(*__iter._M_h());
1450 _Local_iterator_base&
1451 operator=(
const _Local_iterator_base& __iter)
1453 if (_M_bucket_count != -1)
1455 _M_cur = __iter._M_cur;
1456 _M_bucket = __iter._M_bucket;
1457 _M_bucket_count = __iter._M_bucket_count;
1458 if (_M_bucket_count != -1)
1459 _M_init(*__iter._M_h());
1466 _M_cur = _M_cur->_M_next();
1469 std::size_t __bkt = this->_M_h()->_M_bucket_index(_M_cur,
1471 if (__bkt != _M_bucket)
1476 _Hash_node<_Value, false>* _M_cur;
1477 std::size_t _M_bucket;
1478 std::size_t _M_bucket_count;
1481 _M_init(
const __hash_code_base& __base)
1482 { ::new(this->_M_h()) __hash_code_base(__base); }
1485 _M_destroy() { this->_M_h()->~__hash_code_base(); }
1489 _M_curr()
const {
return _M_cur; }
1492 _M_get_bucket()
const {
return _M_bucket; }
1495 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1496 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1498 operator==(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1499 _H1, _H2, _Hash, __cache>& __x,
1500 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1501 _H1, _H2, _Hash, __cache>& __y)
1502 {
return __x._M_curr() == __y._M_curr(); }
1504 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1505 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1507 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1508 _H1, _H2, _Hash, __cache>& __x,
1509 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1510 _H1, _H2, _Hash, __cache>& __y)
1511 {
return __x._M_curr() != __y._M_curr(); }
1514 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1515 typename _H1,
typename _H2,
typename _Hash,
1516 bool __constant_iterators,
bool __cache>
1519 _H1, _H2, _Hash, __cache>
1524 using __hash_code_base =
typename __base_type::__hash_code_base;
1526 typedef _Value value_type;
1527 typedef typename std::conditional<__constant_iterators,
1528 const _Value*, _Value*>::type
1530 typedef typename std::conditional<__constant_iterators,
1531 const _Value&, _Value&>::type
1546 {
return this->_M_cur->_M_v(); }
1550 {
return this->_M_cur->_M_valptr(); }
1569 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1571 bool __constant_iterators,
bool __cache>
1574 _H1, _H2, _Hash, __cache>
1579 using __hash_code_base =
typename __base_type::__hash_code_base;
1582 typedef _Value value_type;
1583 typedef const _Value* pointer;
1584 typedef const _Value& reference;
1598 __constant_iterators,
1605 {
return this->_M_cur->_M_v(); }
1609 {
return this->_M_cur->_M_valptr(); }
1637 template<
typename _Key,
typename _Value,
1638 typename _ExtractKey,
typename _Equal,
1639 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1642 _Traits::__hash_cached::value>,
1647 typedef _Value value_type;
1648 typedef _Equal key_equal;
1649 typedef std::size_t size_type;
1652 using __traits_type = _Traits;
1653 using __hash_cached =
typename __traits_type::__hash_cached;
1654 using __constant_iterators =
typename __traits_type::__constant_iterators;
1655 using __unique_keys =
typename __traits_type::__unique_keys;
1659 __hash_cached::value>;
1661 using __hash_code =
typename __hash_code_base::__hash_code;
1662 using __node_type =
typename __hash_code_base::__node_type;
1665 __constant_iterators::value,
1666 __hash_cached::value>;
1669 __constant_iterators::value,
1670 __hash_cached::value>;
1674 __constant_iterators::value,
1675 __hash_cached::value>;
1680 __constant_iterators::value,
1681 __hash_cached::value>;
1683 using __ireturn_type =
typename std::conditional<__unique_keys::value,
1689 __hash_code, __hash_cached::value>;
1699 _M_equals(
const _Key&
__k, __hash_code __c, __node_type* __n)
const
1701 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1708 __hash_code_base::_M_swap(__x);
1709 std::swap(_M_eq(), __x._M_eq());
1713 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1716 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1727 template<
typename _Uiterator>
1733 template<
typename _Uiterator>
1786 template<
typename _Key,
typename _Value,
typename _Alloc,
1787 typename _ExtractKey,
typename _Equal,
1788 typename _H1,
typename _H2,
typename _Hash,
1789 typename _RehashPolicy,
typename _Traits,
1790 bool _Unique_keys = _Traits::__unique_keys::value>
1794 template<
typename _Key,
typename _Value,
typename _Alloc,
1795 typename _ExtractKey,
typename _Equal,
1797 typename _RehashPolicy,
typename _Traits>
1808 template<
typename _Key,
typename _Value,
typename _Alloc,
1809 typename _ExtractKey,
typename _Equal,
1811 typename _RehashPolicy,
typename _Traits>
1815 _M_equal(
const __hashtable& __other)
const
1817 const __hashtable*
__this =
static_cast<const __hashtable*
>(
this);
1819 if (
__this->size() != __other.size())
1824 const auto __ity = __other.find(_ExtractKey()(*__itx));
1832 template<
typename _Key,
typename _Value,
typename _Alloc,
1833 typename _ExtractKey,
typename _Equal,
1834 typename _H1,
typename _H2,
typename _Hash,
1835 typename _RehashPolicy,
typename _Traits>
1847 template<
typename _Key,
typename _Value,
typename _Alloc,
1848 typename _ExtractKey,
typename _Equal,
1850 typename _RehashPolicy,
typename _Traits>
1854 _M_equal(
const __hashtable& __other)
const
1856 const __hashtable*
__this =
static_cast<const __hashtable*
>(
this);
1858 if (
__this->size() != __other.size())
1863 const auto __xrange =
__this->equal_range(_ExtractKey()(*__itx));
1864 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1883 template<
typename _NodeAlloc>
1889 using __node_type =
typename _NodeAlloc::value_type;
1894 using __value_type =
typename __node_type::value_type;
1909 template<
typename _Alloc>
1916 {
return __ebo_node_alloc::_S_get(*
this); }
1919 _M_node_allocator()
const
1920 {
return __ebo_node_alloc::_S_cget(*
this); }
1922 template<
typename...
_Args>
1927 _M_deallocate_node(__node_type* __n);
1931 _M_deallocate_nodes(__node_type* __n);
1934 _M_allocate_buckets(std::size_t __n);
1942 template<
typename _NodeAlloc>
1943 template<
typename...
_Args>
1944 typename _Hashtable_alloc<_NodeAlloc>::__node_type*
1947 auto __nptr = __node_alloc_traits::allocate(_M_node_allocator(), 1);
1951 __value_alloc_type __a(_M_node_allocator());
1952 ::new ((
void*)__n) __node_type;
1953 __value_alloc_traits::construct(__a, __n->_M_valptr(),
1959 __node_alloc_traits::deallocate(_M_node_allocator(),
__nptr, 1);
1960 __throw_exception_again;
1964 template<
typename _NodeAlloc>
1966 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_node(__node_type* __n)
1968 typedef typename __node_alloc_traits::pointer _Ptr;
1970 __value_alloc_type __a(_M_node_allocator());
1971 __value_alloc_traits::destroy(__a, __n->_M_valptr());
1972 __n->~__node_type();
1973 __node_alloc_traits::deallocate(_M_node_allocator(), __ptr, 1);
1976 template<
typename _NodeAlloc>
1978 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_nodes(__node_type* __n)
1982 __node_type* __tmp = __n;
1983 __n = __n->_M_next();
1984 _M_deallocate_node(__tmp);
1988 template<
typename _NodeAlloc>
1989 typename _Hashtable_alloc<_NodeAlloc>::__bucket_type*
1990 _Hashtable_alloc<_NodeAlloc>::_M_allocate_buckets(std::size_t __n)
1992 __bucket_alloc_type __alloc(_M_node_allocator());
1994 auto __ptr = __bucket_alloc_traits::allocate(__alloc, __n);
1996 __builtin_memset(__p, 0, __n *
sizeof(__bucket_type));
2000 template<
typename _NodeAlloc>
2002 _Hashtable_alloc<_NodeAlloc>::_M_deallocate_buckets(__bucket_type* __bkts,
2005 typedef typename __bucket_alloc_traits::pointer _Ptr;
2007 __bucket_alloc_type __alloc(_M_node_allocator());
2008 __bucket_alloc_traits::deallocate(__alloc, __ptr, __n);
2012_GLIBCXX_END_NAMESPACE_VERSION
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr piecewise_construct_t piecewise_construct
piecewise_construct
ISO C++ entities toplevel namespace is std.
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Primary class template, tuple.
Base class for node iterators.
Node iterators, used to iterate through all the hashtable.
Node const_iterators, used to iterate through all the hashtable.
Default range hashing function: use division to fold a large number into the range [0,...
Default ranged hash function H. In principle it should be a function object composed from objects of ...
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
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.