31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
36 #if __cplusplus > 201402L
40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 template<
typename _Tp,
typename _Hash>
47 __is_fast_hash<_Hash>,
49 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
169 template<
typename _Key,
typename _Value,
typename _Alloc,
170 typename _ExtractKey,
typename _Equal,
171 typename _H1,
typename _H2,
typename _Hash,
172 typename _RehashPolicy,
typename _Traits>
175 _H1, _H2, _Hash, _Traits>,
177 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
179 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
181 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
183 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
185 __alloc_rebind<_Alloc,
186 __detail::_Hash_node<_Value,
187 _Traits::__hash_cached::value>>>
189 static_assert(
is_same<
typename remove_cv<_Value>::type, _Value>::value,
190 "unordered container must have a non-const, non-volatile value_type");
191 #if __cplusplus > 201703L || defined __STRICT_ANSI__
193 "unordered container must have the same value_type as its allocator");
196 using __traits_type = _Traits;
197 using __hash_cached =
typename __traits_type::__hash_cached;
199 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
203 using __value_alloc_traits =
204 typename __hashtable_alloc::__value_alloc_traits;
205 using __node_alloc_traits =
211 typedef _Key key_type;
212 typedef _Value value_type;
213 typedef _Alloc allocator_type;
214 typedef _Equal key_equal;
218 typedef typename __value_alloc_traits::pointer pointer;
219 typedef typename __value_alloc_traits::const_pointer const_pointer;
220 typedef value_type& reference;
221 typedef const value_type& const_reference;
224 using __rehash_type = _RehashPolicy;
225 using __rehash_state =
typename __rehash_type::_State;
227 using __constant_iterators =
typename __traits_type::__constant_iterators;
228 using __unique_keys =
typename __traits_type::__unique_keys;
231 __constant_iterators::value,
233 __detail::_Select1st>::type;
236 _Hashtable_base<_Key, _Value, _ExtractKey,
237 _Equal, _H1, _H2, _Hash, _Traits>;
240 using __hash_code =
typename __hashtable_base::__hash_code;
241 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
244 _Equal, _H1, _H2, _Hash,
245 _RehashPolicy, _Traits>;
250 _RehashPolicy, _Traits>;
253 _Equal, _H1, _H2, _Hash,
254 _RehashPolicy, _Traits>;
256 using __reuse_or_alloc_node_gen_t =
257 __detail::_ReuseOrAllocNode<__node_alloc_type>;
258 using __alloc_node_gen_t =
259 __detail::_AllocNode<__node_alloc_type>;
266 : _M_h(__h), _M_node(__n) { }
269 template<
typename... _Args>
272 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
276 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
278 _Scoped_node(
const _Scoped_node&) =
delete;
279 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
285 template<
typename _Ht>
288 const value_type&, value_type&&>::type
289 __fwd_value_for(value_type& __val) noexcept
293 template<
typename _Cond>
294 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
296 template<
typename _Cond>
297 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
303 struct __hash_code_base_access : __hash_code_base
304 {
using __hash_code_base::_M_bucket_index; };
308 static_assert(noexcept(declval<const __hash_code_base_access&>()
311 "Cache the hash code or qualify your functors involved"
312 " in hash code and bucket index computation with noexcept");
317 "Functor used to map hash code to bucket index"
318 " must be default constructible");
320 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
321 typename _ExtractKeya,
typename _Equala,
322 typename _H1a,
typename _H2a,
typename _Hasha,
323 typename _RehashPolicya,
typename _Traitsa,
327 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
328 typename _ExtractKeya,
typename _Equala,
329 typename _H1a,
typename _H2a,
typename _Hasha,
330 typename _RehashPolicya,
typename _Traitsa>
333 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
334 typename _ExtractKeya,
typename _Equala,
335 typename _H1a,
typename _H2a,
typename _Hasha,
336 typename _RehashPolicya,
typename _Traitsa,
337 bool _Constant_iteratorsa>
340 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
341 typename _ExtractKeya,
typename _Equala,
342 typename _H1a,
typename _H2a,
typename _Hasha,
343 typename _RehashPolicya,
typename _Traitsa,
348 using size_type =
typename __hashtable_base::size_type;
349 using difference_type =
typename __hashtable_base::difference_type;
355 using const_local_iterator =
typename __hashtable_base::
356 const_local_iterator;
358 #if __cplusplus > 201402L
359 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
360 using insert_return_type = _Node_insert_return<iterator, node_type>;
364 __bucket_type* _M_buckets = &_M_single_bucket;
365 size_type _M_bucket_count = 1;
366 __node_base _M_before_begin;
367 size_type _M_element_count = 0;
368 _RehashPolicy _M_rehash_policy;
376 __bucket_type _M_single_bucket =
nullptr;
379 _M_uses_single_bucket(__bucket_type* __bkts)
const
380 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
383 _M_uses_single_bucket()
const
384 {
return _M_uses_single_bucket(_M_buckets); }
387 _M_base_alloc() {
return *
this; }
390 _M_allocate_buckets(size_type __bkt_count)
392 if (__builtin_expect(__bkt_count == 1,
false))
394 _M_single_bucket =
nullptr;
395 return &_M_single_bucket;
398 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
402 _M_deallocate_buckets(__bucket_type* __bkts, size_type __bkt_count)
404 if (_M_uses_single_bucket(__bkts))
407 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
411 _M_deallocate_buckets()
412 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
417 _M_bucket_begin(size_type __bkt)
const;
421 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
425 template<
typename _Ht>
427 _M_assign_elements(_Ht&&);
429 template<
typename _Ht,
typename _NodeGenerator>
431 _M_assign(_Ht&&,
const _NodeGenerator&);
442 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
443 const _Equal& __eq,
const _ExtractKey& __exk,
444 const allocator_type& __a)
449 template<
bool _No_realloc = true>
450 static constexpr
bool
453 #if __cplusplus <= 201402L
454 return __and_<__bool_constant<_No_realloc>,
458 if constexpr (_No_realloc)
467 noexcept(_S_nothrow_move());
477 const _H1&,
const _H2&,
const _Hash&,
478 const _Equal&,
const _ExtractKey&,
479 const allocator_type&);
481 template<
typename _InputIterator>
482 _Hashtable(_InputIterator __first, _InputIterator __last,
483 size_type __bkt_count_hint,
484 const _H1&,
const _H2&,
const _Hash&,
485 const _Equal&,
const _ExtractKey&,
486 const allocator_type&);
491 noexcept(_S_nothrow_move())
499 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
501 typename __node_alloc_traits::is_always_equal{})
512 const _H1& __hf = _H1(),
513 const key_equal& __eql = key_equal(),
514 const allocator_type& __a = allocator_type())
515 :
_Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql,
516 __key_extract(), __a)
519 template<
typename _InputIterator>
520 _Hashtable(_InputIterator __f, _InputIterator __l,
521 size_type __bkt_count_hint = 0,
522 const _H1& __hf = _H1(),
523 const key_equal& __eql = key_equal(),
524 const allocator_type& __a = allocator_type())
525 :
_Hashtable(__f, __l, __bkt_count_hint, __hf, _H2(), _Hash(), __eql,
526 __key_extract(), __a)
530 size_type __bkt_count_hint = 0,
531 const _H1& __hf = _H1(),
532 const key_equal& __eql = key_equal(),
533 const allocator_type& __a = allocator_type())
534 :
_Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
535 __hf, _H2(), _Hash(), __eql,
536 __key_extract(), __a)
544 noexcept(__node_alloc_traits::_S_nothrow_move()
548 constexpr
bool __move_storage =
549 __node_alloc_traits::_S_propagate_on_move_assign()
550 || __node_alloc_traits::_S_always_equal();
558 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
559 _M_before_begin._M_nxt =
nullptr;
561 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
569 noexcept(__and_<__is_nothrow_swappable<_H1>,
570 __is_nothrow_swappable<_Equal>>::value);
575 {
return iterator(_M_begin()); }
578 begin()
const noexcept
579 {
return const_iterator(_M_begin()); }
583 {
return iterator(
nullptr); }
587 {
return const_iterator(
nullptr); }
591 {
return const_iterator(_M_begin()); }
594 cend()
const noexcept
595 {
return const_iterator(
nullptr); }
598 size()
const noexcept
599 {
return _M_element_count; }
601 _GLIBCXX_NODISCARD
bool
602 empty()
const noexcept
603 {
return size() == 0; }
606 get_allocator()
const noexcept
607 {
return allocator_type(this->_M_node_allocator()); }
610 max_size()
const noexcept
611 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
616 {
return this->_M_eq(); }
622 bucket_count()
const noexcept
623 {
return _M_bucket_count; }
626 max_bucket_count()
const noexcept
627 {
return max_size(); }
630 bucket_size(size_type __bkt)
const
634 bucket(
const key_type& __k)
const
635 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
638 begin(size_type __bkt)
640 return local_iterator(*
this, _M_bucket_begin(__bkt),
641 __bkt, _M_bucket_count);
646 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
649 begin(size_type __bkt)
const
651 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
652 __bkt, _M_bucket_count);
656 end(size_type __bkt)
const
657 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
661 cbegin(size_type __bkt)
const
663 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
664 __bkt, _M_bucket_count);
668 cend(size_type __bkt)
const
669 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
672 load_factor()
const noexcept
674 return static_cast<float>(size()) /
static_cast<float>(bucket_count());
683 __rehash_policy()
const
684 {
return _M_rehash_policy; }
687 __rehash_policy(
const _RehashPolicy& __pol)
688 { _M_rehash_policy = __pol; }
692 find(
const key_type& __k);
695 find(
const key_type& __k)
const;
698 count(
const key_type& __k)
const;
701 equal_range(
const key_type& __k);
704 equal_range(
const key_type& __k)
const;
710 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
713 _M_bucket_index(
const key_type& __k, __hash_code __c)
const
714 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
719 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
722 _M_find_node(size_type __bkt,
const key_type& __key,
723 __hash_code __c)
const
725 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
727 return static_cast<__node_type*
>(__before_n->_M_nxt);
737 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
738 size_type __next_bkt);
742 _M_get_previous_node(size_type __bkt, __node_base* __n);
748 _M_insert_unique_node(
const key_type& __k, size_type __bkt,
750 size_type __n_elt = 1);
755 _M_insert_multi_node(
__node_type* __hint,
const key_type& __k,
758 template<
typename... _Args>
760 _M_emplace(
true_type, _Args&&... __args);
762 template<
typename... _Args>
764 _M_emplace(
false_type __uk, _Args&&... __args)
765 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
768 template<
typename... _Args>
770 _M_emplace(const_iterator,
true_type __uk, _Args&&... __args)
771 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
773 template<
typename... _Args>
775 _M_emplace(const_iterator,
false_type, _Args&&... __args);
777 template<
typename _Arg,
typename _NodeGenerator>
779 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type, size_type = 1);
781 template<
typename _Arg,
typename _NodeGenerator>
783 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
786 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
791 template<
typename _Arg,
typename _NodeGenerator>
793 _M_insert(const_iterator, _Arg&& __arg,
794 const _NodeGenerator& __node_gen,
true_type __uk)
797 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
801 template<
typename _Arg,
typename _NodeGenerator>
803 _M_insert(const_iterator, _Arg&&,
813 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
817 template<
typename... _Args>
819 emplace(_Args&&... __args)
820 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
822 template<
typename... _Args>
824 emplace_hint(const_iterator __hint, _Args&&... __args)
826 return _M_emplace(__hint, __unique_keys(),
827 std::forward<_Args>(__args)...);
834 erase(const_iterator);
839 {
return erase(const_iterator(__it)); }
842 erase(
const key_type& __k)
843 {
return _M_erase(__unique_keys(), __k); }
846 erase(const_iterator, const_iterator);
853 void rehash(size_type __bkt_count);
858 #if __cplusplus > 201402L
861 _M_reinsert_node(node_type&& __nh)
863 insert_return_type __ret;
865 __ret.position =
end();
868 __glibcxx_assert(get_allocator() == __nh.get_allocator());
870 const key_type& __k = __nh._M_key();
871 __hash_code __code = this->_M_hash_code(__k);
872 size_type __bkt = _M_bucket_index(__k, __code);
873 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
876 __ret.position = iterator(__n);
877 __ret.inserted =
false;
882 = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
883 __nh._M_ptr =
nullptr;
884 __ret.inserted =
true;
892 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
897 __glibcxx_assert(get_allocator() == __nh.get_allocator());
899 const key_type& __k = __nh._M_key();
900 auto __code = this->_M_hash_code(__k);
902 = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
903 __nh._M_ptr =
nullptr;
909 _M_extract_node(
size_t __bkt, __node_base* __prev_n)
912 if (__prev_n == _M_buckets[__bkt])
913 _M_remove_bucket_begin(__bkt, __n->_M_next(),
914 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
915 else if (__n->_M_nxt)
917 size_type __next_bkt = _M_bucket_index(__n->_M_next());
918 if (__next_bkt != __bkt)
919 _M_buckets[__next_bkt] = __prev_n;
922 __prev_n->_M_nxt = __n->_M_nxt;
923 __n->_M_nxt =
nullptr;
925 return { __n, this->_M_node_allocator() };
931 extract(const_iterator __pos)
933 size_t __bkt = _M_bucket_index(__pos._M_cur);
934 return _M_extract_node(__bkt,
935 _M_get_previous_node(__bkt, __pos._M_cur));
940 extract(
const _Key& __k)
943 __hash_code __code = this->_M_hash_code(__k);
944 std::size_t __bkt = _M_bucket_index(__k, __code);
945 if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code))
946 __nh = _M_extract_node(__bkt, __prev_node);
951 template<
typename _Compatible_Hashtable>
953 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
955 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
956 node_type>,
"Node types are compatible");
957 __glibcxx_assert(get_allocator() == __src.get_allocator());
959 auto __n_elt = __src.size();
960 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
963 const key_type& __k = this->_M_extract()(*__pos);
964 __hash_code __code = this->_M_hash_code(__k);
965 size_type __bkt = _M_bucket_index(__k, __code);
966 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
968 auto __nh = __src.extract(__pos);
969 _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
971 __nh._M_ptr =
nullptr;
974 else if (__n_elt != 1)
980 template<
typename _Compatible_Hashtable>
982 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
984 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
985 node_type>,
"Node types are compatible");
986 __glibcxx_assert(get_allocator() == __src.get_allocator());
988 this->reserve(size() + __src.size());
989 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
990 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
996 void _M_rehash_aux(size_type __bkt_count,
true_type);
999 void _M_rehash_aux(size_type __bkt_count,
false_type);
1003 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1008 template<
typename _Key,
typename _Value,
1009 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1010 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1013 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1014 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1015 _M_bucket_begin(size_type __bkt)
const
1018 __node_base* __n = _M_buckets[__bkt];
1019 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
1022 template<
typename _Key,
typename _Value,
1023 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1024 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1026 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1027 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1028 _Hashtable(size_type __bkt_count_hint,
1029 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
1030 const _Equal& __eq,
const _ExtractKey& __exk,
1031 const allocator_type& __a)
1032 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
1034 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1035 if (__bkt_count > _M_bucket_count)
1037 _M_buckets = _M_allocate_buckets(__bkt_count);
1038 _M_bucket_count = __bkt_count;
1042 template<
typename _Key,
typename _Value,
1043 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1044 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1046 template<
typename _InputIterator>
1047 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1048 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1049 _Hashtable(_InputIterator __f, _InputIterator __l,
1050 size_type __bkt_count_hint,
1051 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
1052 const _Equal& __eq,
const _ExtractKey& __exk,
1053 const allocator_type& __a)
1054 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
1056 auto __nb_elems = __detail::__distance_fw(__f, __l);
1058 _M_rehash_policy._M_next_bkt(
1059 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1062 if (__bkt_count > _M_bucket_count)
1064 _M_buckets = _M_allocate_buckets(__bkt_count);
1065 _M_bucket_count = __bkt_count;
1068 for (; __f != __l; ++__f)
1072 template<
typename _Key,
typename _Value,
1073 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1074 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1077 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1078 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1079 operator=(
const _Hashtable& __ht)
1085 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1087 auto& __this_alloc = this->_M_node_allocator();
1088 auto& __that_alloc = __ht._M_node_allocator();
1089 if (!__node_alloc_traits::_S_always_equal()
1090 && __this_alloc != __that_alloc)
1093 this->_M_deallocate_nodes(_M_begin());
1094 _M_before_begin._M_nxt =
nullptr;
1095 _M_deallocate_buckets();
1096 _M_buckets =
nullptr;
1097 std::__alloc_on_copy(__this_alloc, __that_alloc);
1098 __hashtable_base::operator=(__ht);
1099 _M_bucket_count = __ht._M_bucket_count;
1100 _M_element_count = __ht._M_element_count;
1101 _M_rehash_policy = __ht._M_rehash_policy;
1102 __alloc_node_gen_t __alloc_node_gen(*
this);
1105 _M_assign(__ht, __alloc_node_gen);
1112 __throw_exception_again;
1116 std::__alloc_on_copy(__this_alloc, __that_alloc);
1120 _M_assign_elements(__ht);
1124 template<
typename _Key,
typename _Value,
1125 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1126 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1128 template<
typename _Ht>
1130 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1131 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1132 _M_assign_elements(_Ht&& __ht)
1134 __bucket_type* __former_buckets =
nullptr;
1135 std::size_t __former_bucket_count = _M_bucket_count;
1136 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1138 if (_M_bucket_count != __ht._M_bucket_count)
1140 __former_buckets = _M_buckets;
1141 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1142 _M_bucket_count = __ht._M_bucket_count;
1145 __builtin_memset(_M_buckets, 0,
1146 _M_bucket_count *
sizeof(__bucket_type));
1150 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1151 _M_element_count = __ht._M_element_count;
1152 _M_rehash_policy = __ht._M_rehash_policy;
1153 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1154 _M_before_begin._M_nxt =
nullptr;
1155 _M_assign(std::forward<_Ht>(__ht), __roan);
1156 if (__former_buckets)
1157 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1161 if (__former_buckets)
1164 _M_deallocate_buckets();
1165 _M_rehash_policy._M_reset(__former_state);
1166 _M_buckets = __former_buckets;
1167 _M_bucket_count = __former_bucket_count;
1169 __builtin_memset(_M_buckets, 0,
1170 _M_bucket_count *
sizeof(__bucket_type));
1171 __throw_exception_again;
1175 template<
typename _Key,
typename _Value,
1176 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1177 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1179 template<
typename _Ht,
typename _NodeGenerator>
1181 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1182 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1183 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1185 __bucket_type* __buckets =
nullptr;
1187 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1191 if (!__ht._M_before_begin._M_nxt)
1196 __node_type* __ht_n = __ht._M_begin();
1197 __node_type* __this_n
1198 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1199 this->_M_copy_code(__this_n, __ht_n);
1200 _M_before_begin._M_nxt = __this_n;
1201 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1204 __node_base* __prev_n = __this_n;
1205 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1207 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1208 __prev_n->_M_nxt = __this_n;
1209 this->_M_copy_code(__this_n, __ht_n);
1210 size_type __bkt = _M_bucket_index(__this_n);
1211 if (!_M_buckets[__bkt])
1212 _M_buckets[__bkt] = __prev_n;
1213 __prev_n = __this_n;
1220 _M_deallocate_buckets();
1221 __throw_exception_again;
1225 template<
typename _Key,
typename _Value,
1226 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1227 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1230 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1231 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1234 _M_rehash_policy._M_reset();
1235 _M_bucket_count = 1;
1236 _M_single_bucket =
nullptr;
1237 _M_buckets = &_M_single_bucket;
1238 _M_before_begin._M_nxt =
nullptr;
1239 _M_element_count = 0;
1242 template<
typename _Key,
typename _Value,
1243 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1244 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1247 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1248 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1249 _M_move_assign(_Hashtable&& __ht,
true_type)
1251 this->_M_deallocate_nodes(_M_begin());
1252 _M_deallocate_buckets();
1253 __hashtable_base::operator=(
std::move(__ht));
1254 _M_rehash_policy = __ht._M_rehash_policy;
1255 if (!__ht._M_uses_single_bucket())
1256 _M_buckets = __ht._M_buckets;
1259 _M_buckets = &_M_single_bucket;
1260 _M_single_bucket = __ht._M_single_bucket;
1262 _M_bucket_count = __ht._M_bucket_count;
1263 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1264 _M_element_count = __ht._M_element_count;
1265 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1270 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1274 template<
typename _Key,
typename _Value,
1275 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1276 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1279 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1280 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1281 _M_move_assign(_Hashtable&& __ht,
false_type)
1283 if (__ht._M_node_allocator() == this->_M_node_allocator())
1293 template<
typename _Key,
typename _Value,
1294 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1295 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1297 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1298 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1299 _Hashtable(
const _Hashtable& __ht)
1300 : __hashtable_base(__ht),
1302 __rehash_base(__ht),
1304 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1305 _M_buckets(nullptr),
1306 _M_bucket_count(__ht._M_bucket_count),
1307 _M_element_count(__ht._M_element_count),
1308 _M_rehash_policy(__ht._M_rehash_policy)
1310 __alloc_node_gen_t __alloc_node_gen(*
this);
1311 _M_assign(__ht, __alloc_node_gen);
1314 template<
typename _Key,
typename _Value,
1315 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1316 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1318 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1319 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1320 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1322 noexcept(_S_nothrow_move())
1323 : __hashtable_base(__ht),
1325 __rehash_base(__ht),
1326 __hashtable_alloc(
std::
move(__a)),
1327 _M_buckets(__ht._M_buckets),
1328 _M_bucket_count(__ht._M_bucket_count),
1329 _M_before_begin(__ht._M_before_begin._M_nxt),
1330 _M_element_count(__ht._M_element_count),
1331 _M_rehash_policy(__ht._M_rehash_policy)
1334 if (__ht._M_uses_single_bucket())
1336 _M_buckets = &_M_single_bucket;
1337 _M_single_bucket = __ht._M_single_bucket;
1343 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1348 template<
typename _Key,
typename _Value,
1349 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1350 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1352 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1353 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1354 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1355 : __hashtable_base(__ht),
1357 __rehash_base(__ht),
1358 __hashtable_alloc(__node_alloc_type(__a)),
1360 _M_bucket_count(__ht._M_bucket_count),
1361 _M_element_count(__ht._M_element_count),
1362 _M_rehash_policy(__ht._M_rehash_policy)
1364 __alloc_node_gen_t __alloc_node_gen(*
this);
1365 _M_assign(__ht, __alloc_node_gen);
1368 template<
typename _Key,
typename _Value,
1369 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1370 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1372 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1373 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1374 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1376 : __hashtable_base(__ht),
1378 __rehash_base(__ht),
1379 __hashtable_alloc(
std::
move(__a)),
1380 _M_buckets(nullptr),
1381 _M_bucket_count(__ht._M_bucket_count),
1382 _M_element_count(__ht._M_element_count),
1383 _M_rehash_policy(__ht._M_rehash_policy)
1385 if (__ht._M_node_allocator() == this->_M_node_allocator())
1387 if (__ht._M_uses_single_bucket())
1389 _M_buckets = &_M_single_bucket;
1390 _M_single_bucket = __ht._M_single_bucket;
1393 _M_buckets = __ht._M_buckets;
1395 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1399 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1404 __alloc_node_gen_t __alloc_gen(*
this);
1406 using _Fwd_Ht =
typename
1407 conditional<__move_if_noexcept_cond<value_type>::value,
1408 const _Hashtable&, _Hashtable&&>::type;
1409 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1414 template<
typename _Key,
typename _Value,
1415 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1416 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1418 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1419 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1420 ~_Hashtable() noexcept
1423 _M_deallocate_buckets();
1426 template<
typename _Key,
typename _Value,
1427 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1428 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1431 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1432 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1433 swap(_Hashtable& __x)
1434 noexcept(__and_<__is_nothrow_swappable<_H1>,
1435 __is_nothrow_swappable<_Equal>>::value)
1442 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1443 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1446 if (this->_M_uses_single_bucket())
1448 if (!__x._M_uses_single_bucket())
1450 _M_buckets = __x._M_buckets;
1451 __x._M_buckets = &__x._M_single_bucket;
1454 else if (__x._M_uses_single_bucket())
1456 __x._M_buckets = _M_buckets;
1457 _M_buckets = &_M_single_bucket;
1460 std::swap(_M_buckets, __x._M_buckets);
1462 std::swap(_M_bucket_count, __x._M_bucket_count);
1463 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1464 std::swap(_M_element_count, __x._M_element_count);
1465 std::swap(_M_single_bucket, __x._M_single_bucket);
1470 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1473 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1474 = &__x._M_before_begin;
1477 template<
typename _Key,
typename _Value,
1478 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1479 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1482 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1483 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1484 find(
const key_type& __k)
1487 __hash_code __code = this->_M_hash_code(__k);
1488 std::size_t __bkt = _M_bucket_index(__k, __code);
1489 __node_type* __p = _M_find_node(__bkt, __k, __code);
1490 return __p ? iterator(__p) :
end();
1493 template<
typename _Key,
typename _Value,
1494 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1495 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1498 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1499 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1500 find(
const key_type& __k)
const
1503 __hash_code __code = this->_M_hash_code(__k);
1504 std::size_t __bkt = _M_bucket_index(__k, __code);
1505 __node_type* __p = _M_find_node(__bkt, __k, __code);
1506 return __p ? const_iterator(__p) :
end();
1509 template<
typename _Key,
typename _Value,
1510 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1511 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1514 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1515 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1516 count(
const key_type& __k)
const
1519 __hash_code __code = this->_M_hash_code(__k);
1520 std::size_t __bkt = _M_bucket_index(__k, __code);
1521 __node_type* __p = _M_bucket_begin(__bkt);
1525 std::size_t __result = 0;
1526 for (;; __p = __p->_M_next())
1528 if (this->_M_equals(__k, __code, __p))
1535 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
1541 template<
typename _Key,
typename _Value,
1542 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1543 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1546 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1547 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1548 equal_range(
const key_type& __k)
1549 -> pair<iterator, iterator>
1551 __hash_code __code = this->_M_hash_code(__k);
1552 std::size_t __bkt = _M_bucket_index(__k, __code);
1553 __node_type* __p = _M_find_node(__bkt, __k, __code);
1557 __node_type* __p1 = __p->_M_next();
1558 while (__p1 && _M_bucket_index(__p1) == __bkt
1559 && this->_M_equals(__k, __code, __p1))
1560 __p1 = __p1->_M_next();
1562 return std::make_pair(iterator(__p), iterator(__p1));
1565 return std::make_pair(
end(),
end());
1568 template<
typename _Key,
typename _Value,
1569 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1570 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1573 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1574 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1575 equal_range(
const key_type& __k)
const
1576 -> pair<const_iterator, const_iterator>
1578 __hash_code __code = this->_M_hash_code(__k);
1579 std::size_t __bkt = _M_bucket_index(__k, __code);
1580 __node_type* __p = _M_find_node(__bkt, __k, __code);
1584 __node_type* __p1 = __p->_M_next();
1585 while (__p1 && _M_bucket_index(__p1) == __bkt
1586 && this->_M_equals(__k, __code, __p1))
1587 __p1 = __p1->_M_next();
1589 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1592 return std::make_pair(
end(),
end());
1597 template<
typename _Key,
typename _Value,
1598 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1599 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1602 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1603 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1604 _M_find_before_node(size_type __bkt,
const key_type& __k,
1605 __hash_code __code)
const
1608 __node_base* __prev_p = _M_buckets[__bkt];
1612 for (__node_type* __p =
static_cast<__node_type*
>(__prev_p->_M_nxt);;
1613 __p = __p->_M_next())
1615 if (this->_M_equals(__k, __code, __p))
1618 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
1625 template<
typename _Key,
typename _Value,
1626 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1627 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1630 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1631 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1632 _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
1634 if (_M_buckets[__bkt])
1638 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1639 _M_buckets[__bkt]->_M_nxt = __node;
1646 __node->_M_nxt = _M_before_begin._M_nxt;
1647 _M_before_begin._M_nxt = __node;
1651 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1652 _M_buckets[__bkt] = &_M_before_begin;
1656 template<
typename _Key,
typename _Value,
1657 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1658 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1661 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1662 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1663 _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
1664 size_type __next_bkt)
1666 if (!__next || __next_bkt != __bkt)
1671 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1674 if (&_M_before_begin == _M_buckets[__bkt])
1675 _M_before_begin._M_nxt = __next;
1676 _M_buckets[__bkt] =
nullptr;
1680 template<
typename _Key,
typename _Value,
1681 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1682 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1685 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1686 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1687 _M_get_previous_node(size_type __bkt, __node_base* __n)
1690 __node_base* __prev_n = _M_buckets[__bkt];
1691 while (__prev_n->_M_nxt != __n)
1692 __prev_n = __prev_n->_M_nxt;
1696 template<
typename _Key,
typename _Value,
1697 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1698 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1700 template<
typename... _Args>
1702 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1703 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1704 _M_emplace(
true_type, _Args&&... __args)
1705 -> pair<iterator, bool>
1708 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1709 const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
1710 __hash_code __code = this->_M_hash_code(__k);
1711 size_type __bkt = _M_bucket_index(__k, __code);
1712 if (__node_type* __p = _M_find_node(__bkt, __k, __code))
1714 return std::make_pair(iterator(__p),
false);
1717 auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
1718 __node._M_node =
nullptr;
1719 return { __pos,
true };
1722 template<
typename _Key,
typename _Value,
1723 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1724 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1726 template<
typename... _Args>
1728 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1729 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1730 _M_emplace(const_iterator __hint,
false_type, _Args&&... __args)
1734 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1735 const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
1737 __hash_code __code = this->_M_hash_code(__k);
1739 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
1740 __node._M_node =
nullptr;
1744 template<
typename _Key,
typename _Value,
1745 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1746 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1749 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1750 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1751 _M_insert_unique_node(
const key_type& __k, size_type __bkt,
1752 __hash_code __code, __node_type* __node,
1756 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1758 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1761 if (__do_rehash.
first)
1763 _M_rehash(__do_rehash.
second, __saved_state);
1764 __bkt = _M_bucket_index(__k, __code);
1767 this->_M_store_code(__node, __code);
1770 _M_insert_bucket_begin(__bkt, __node);
1772 return iterator(__node);
1775 template<
typename _Key,
typename _Value,
1776 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1777 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1780 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1781 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1782 _M_insert_multi_node(__node_type* __hint,
const key_type& __k,
1783 __hash_code __code, __node_type* __node)
1786 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1788 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1790 if (__do_rehash.
first)
1791 _M_rehash(__do_rehash.
second, __saved_state);
1793 this->_M_store_code(__node, __code);
1794 size_type __bkt = _M_bucket_index(__k, __code);
1799 = __builtin_expect(__hint !=
nullptr,
false)
1800 && this->_M_equals(__k, __code, __hint)
1802 : _M_find_before_node(__bkt, __k, __code);
1806 __node->_M_nxt = __prev->_M_nxt;
1807 __prev->_M_nxt = __node;
1808 if (__builtin_expect(__prev == __hint,
false))
1812 && !this->_M_equals(__k, __code, __node->_M_next()))
1814 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1815 if (__next_bkt != __bkt)
1816 _M_buckets[__next_bkt] = __node;
1823 _M_insert_bucket_begin(__bkt, __node);
1825 return iterator(__node);
1829 template<
typename _Key,
typename _Value,
1830 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1831 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1833 template<
typename _Arg,
typename _NodeGenerator>
1835 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1836 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1837 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
true_type,
1839 -> pair<iterator, bool>
1841 const key_type& __k = this->_M_extract()(__v);
1842 __hash_code __code = this->_M_hash_code(__k);
1843 size_type __bkt = _M_bucket_index(__k, __code);
1845 if (__node_type* __node = _M_find_node(__bkt, __k, __code))
1846 return { iterator(__node),
false };
1848 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
1850 = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
1851 __node._M_node =
nullptr;
1852 return { __pos,
true };
1856 template<
typename _Key,
typename _Value,
1857 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1858 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1860 template<
typename _Arg,
typename _NodeGenerator>
1862 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1863 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1864 _M_insert(const_iterator __hint, _Arg&& __v,
1865 const _NodeGenerator& __node_gen,
false_type)
1870 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1873 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
1874 const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
1876 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
1877 __node._M_node =
nullptr;
1881 template<
typename _Key,
typename _Value,
1882 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1883 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1886 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1887 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1888 erase(const_iterator __it)
1891 __node_type* __n = __it._M_cur;
1892 std::size_t __bkt = _M_bucket_index(__n);
1897 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1898 return _M_erase(__bkt, __prev_n, __n);
1901 template<
typename _Key,
typename _Value,
1902 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1903 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1906 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1907 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1908 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
1911 if (__prev_n == _M_buckets[__bkt])
1912 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1913 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1914 else if (__n->_M_nxt)
1916 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1917 if (__next_bkt != __bkt)
1918 _M_buckets[__next_bkt] = __prev_n;
1921 __prev_n->_M_nxt = __n->_M_nxt;
1922 iterator __result(__n->_M_next());
1923 this->_M_deallocate_node(__n);
1929 template<
typename _Key,
typename _Value,
1930 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1931 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1934 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1935 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1936 _M_erase(
true_type,
const key_type& __k)
1939 __hash_code __code = this->_M_hash_code(__k);
1940 std::size_t __bkt = _M_bucket_index(__k, __code);
1943 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1948 __node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);
1949 _M_erase(__bkt, __prev_n, __n);
1953 template<
typename _Key,
typename _Value,
1954 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1955 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1958 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1959 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1963 __hash_code __code = this->_M_hash_code(__k);
1964 std::size_t __bkt = _M_bucket_index(__k, __code);
1967 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1977 __node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);
1978 __node_type* __n_last = __n;
1979 std::size_t __n_last_bkt = __bkt;
1982 __n_last = __n_last->_M_next();
1985 __n_last_bkt = _M_bucket_index(__n_last);
1987 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1990 size_type __result = 0;
1993 __node_type* __p = __n->_M_next();
1994 this->_M_deallocate_node(__n);
1999 while (__n != __n_last);
2001 if (__prev_n == _M_buckets[__bkt])
2002 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2003 else if (__n_last && __n_last_bkt != __bkt)
2004 _M_buckets[__n_last_bkt] = __prev_n;
2005 __prev_n->_M_nxt = __n_last;
2009 template<
typename _Key,
typename _Value,
2010 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2011 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2014 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2015 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2016 erase(const_iterator __first, const_iterator __last)
2019 __node_type* __n = __first._M_cur;
2020 __node_type* __last_n = __last._M_cur;
2021 if (__n == __last_n)
2022 return iterator(__n);
2024 std::size_t __bkt = _M_bucket_index(__n);
2026 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
2027 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2028 std::size_t __n_bkt = __bkt;
2033 __node_type* __tmp = __n;
2034 __n = __n->_M_next();
2035 this->_M_deallocate_node(__tmp);
2039 __n_bkt = _M_bucket_index(__n);
2041 while (__n != __last_n && __n_bkt == __bkt);
2042 if (__is_bucket_begin)
2043 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2044 if (__n == __last_n)
2046 __is_bucket_begin =
true;
2050 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2051 _M_buckets[__n_bkt] = __prev_n;
2052 __prev_n->_M_nxt = __n;
2053 return iterator(__n);
2056 template<
typename _Key,
typename _Value,
2057 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2058 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2062 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2065 this->_M_deallocate_nodes(_M_begin());
2066 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2067 _M_element_count = 0;
2068 _M_before_begin._M_nxt =
nullptr;
2071 template<
typename _Key,
typename _Value,
2072 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2073 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2076 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2077 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2078 rehash(size_type __bkt_count)
2080 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2082 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2084 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2086 if (__bkt_count != _M_bucket_count)
2087 _M_rehash(__bkt_count, __saved_state);
2091 _M_rehash_policy._M_reset(__saved_state);
2094 template<
typename _Key,
typename _Value,
2095 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2096 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2099 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2100 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2101 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2105 _M_rehash_aux(__bkt_count, __unique_keys());
2111 _M_rehash_policy._M_reset(__state);
2112 __throw_exception_again;
2117 template<
typename _Key,
typename _Value,
2118 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2119 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2122 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2123 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2124 _M_rehash_aux(size_type __bkt_count,
true_type)
2126 __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
2127 __node_type* __p = _M_begin();
2128 _M_before_begin._M_nxt =
nullptr;
2129 std::size_t __bbegin_bkt = 0;
2132 __node_type* __next = __p->_M_next();
2134 = __hash_code_base::_M_bucket_index(__p, __bkt_count);
2135 if (!__new_buckets[__bkt])
2137 __p->_M_nxt = _M_before_begin._M_nxt;
2138 _M_before_begin._M_nxt = __p;
2139 __new_buckets[__bkt] = &_M_before_begin;
2141 __new_buckets[__bbegin_bkt] = __p;
2142 __bbegin_bkt = __bkt;
2146 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2147 __new_buckets[__bkt]->_M_nxt = __p;
2152 _M_deallocate_buckets();
2153 _M_bucket_count = __bkt_count;
2154 _M_buckets = __new_buckets;
2159 template<
typename _Key,
typename _Value,
2160 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2161 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2164 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2165 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2166 _M_rehash_aux(size_type __bkt_count,
false_type)
2168 __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
2170 __node_type* __p = _M_begin();
2171 _M_before_begin._M_nxt =
nullptr;
2172 std::size_t __bbegin_bkt = 0;
2173 std::size_t __prev_bkt = 0;
2174 __node_type* __prev_p =
nullptr;
2175 bool __check_bucket =
false;
2179 __node_type* __next = __p->_M_next();
2181 = __hash_code_base::_M_bucket_index(__p, __bkt_count);
2183 if (__prev_p && __prev_bkt == __bkt)
2188 __p->_M_nxt = __prev_p->_M_nxt;
2189 __prev_p->_M_nxt = __p;
2196 __check_bucket =
true;
2204 if (__prev_p->_M_nxt)
2206 std::size_t __next_bkt
2207 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2209 if (__next_bkt != __prev_bkt)
2210 __new_buckets[__next_bkt] = __prev_p;
2212 __check_bucket =
false;
2215 if (!__new_buckets[__bkt])
2217 __p->_M_nxt = _M_before_begin._M_nxt;
2218 _M_before_begin._M_nxt = __p;
2219 __new_buckets[__bkt] = &_M_before_begin;
2221 __new_buckets[__bbegin_bkt] = __p;
2222 __bbegin_bkt = __bkt;
2226 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2227 __new_buckets[__bkt]->_M_nxt = __p;
2235 if (__check_bucket && __prev_p->_M_nxt)
2237 std::size_t __next_bkt
2238 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2240 if (__next_bkt != __prev_bkt)
2241 __new_buckets[__next_bkt] = __prev_p;
2244 _M_deallocate_buckets();
2245 _M_bucket_count = __bkt_count;
2246 _M_buckets = __new_buckets;
2249 #if __cplusplus > 201402L
2250 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2253 #if __cpp_deduction_guides >= 201606
2255 template<
typename _Hash>
2256 using _RequireNotAllocatorOrIntegral
2257 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2260 _GLIBCXX_END_NAMESPACE_VERSION
2263 #endif // _HASHTABLE_H