31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
37 #if __cplusplus > 201402L
41 namespace std _GLIBCXX_VISIBILITY(default)
43 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46 template<
typename _Tp,
typename _Hash>
49 __is_fast_hash<_Hash>,
51 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
56 template<
typename _Equal,
typename _Hash,
typename _Allocator>
57 using _Hashtable_enable_default_ctor
58 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
59 is_default_constructible<_Hash>,
60 is_default_constructible<_Allocator>>{},
61 __detail::_Hash_node_base>;
176 template<
typename _Key,
typename _Value,
typename _Alloc,
177 typename _ExtractKey,
typename _Equal,
178 typename _Hash,
typename _RangeHash,
typename _Unused,
179 typename _RehashPolicy,
typename _Traits>
181 :
public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
182 _Hash, _RangeHash, _Unused, _Traits>,
183 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
184 _Hash, _RangeHash, _Unused,
185 _RehashPolicy, _Traits>,
186 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
187 _Hash, _RangeHash, _Unused,
188 _RehashPolicy, _Traits>,
189 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
190 _Hash, _RangeHash, _Unused,
191 _RehashPolicy, _Traits>,
192 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
193 _Hash, _RangeHash, _Unused,
194 _RehashPolicy, _Traits>,
195 private __detail::_Hashtable_alloc<
196 __alloc_rebind<_Alloc,
197 __detail::_Hash_node<_Value,
198 _Traits::__hash_cached::value>>>,
199 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
201 static_assert(is_same<
typename remove_cv<_Value>::type, _Value>::value,
202 "unordered container must have a non-const, non-volatile value_type");
203 #if __cplusplus > 201703L || defined __STRICT_ANSI__
204 static_assert(is_same<typename _Alloc::value_type, _Value>{},
205 "unordered container must have the same value_type as its allocator");
208 using __traits_type = _Traits;
209 using __hash_cached =
typename __traits_type::__hash_cached;
210 using __constant_iterators =
typename __traits_type::__constant_iterators;
211 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
212 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
214 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
216 using __node_value_type =
217 __detail::_Hash_node_value<_Value, __hash_cached::value>;
218 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
219 using __value_alloc_traits =
220 typename __hashtable_alloc::__value_alloc_traits;
221 using __node_alloc_traits =
222 typename __hashtable_alloc::__node_alloc_traits;
223 using __node_base =
typename __hashtable_alloc::__node_base;
224 using __node_base_ptr =
typename __hashtable_alloc::__node_base_ptr;
225 using __buckets_ptr =
typename __hashtable_alloc::__buckets_ptr;
227 using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
230 _RehashPolicy, _Traits>;
231 using __enable_default_ctor
232 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
235 typedef _Key key_type;
236 typedef _Value value_type;
237 typedef _Alloc allocator_type;
238 typedef _Equal key_equal;
242 typedef typename __value_alloc_traits::pointer pointer;
243 typedef typename __value_alloc_traits::const_pointer const_pointer;
244 typedef value_type& reference;
245 typedef const value_type& const_reference;
247 using iterator =
typename __insert_base::iterator;
249 using const_iterator =
typename __insert_base::const_iterator;
251 using local_iterator = __detail::_Local_iterator<key_type, _Value,
252 _ExtractKey, _Hash, _RangeHash, _Unused,
253 __constant_iterators::value,
254 __hash_cached::value>;
256 using const_local_iterator = __detail::_Local_const_iterator<
258 _ExtractKey, _Hash, _RangeHash, _Unused,
259 __constant_iterators::value, __hash_cached::value>;
262 using __rehash_type = _RehashPolicy;
263 using __rehash_state =
typename __rehash_type::_State;
265 using __unique_keys =
typename __traits_type::__unique_keys;
267 using __hashtable_base = __detail::
268 _Hashtable_base<_Key, _Value, _ExtractKey,
269 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
271 using __hash_code_base =
typename __hashtable_base::__hash_code_base;
272 using __hash_code =
typename __hashtable_base::__hash_code;
273 using __ireturn_type =
typename __insert_base::__ireturn_type;
275 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
276 _Equal, _Hash, _RangeHash, _Unused,
277 _RehashPolicy, _Traits>;
279 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
281 _Hash, _RangeHash, _Unused,
282 _RehashPolicy, _Traits>;
284 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
285 _Equal, _Hash, _RangeHash, _Unused,
286 _RehashPolicy, _Traits>;
288 using __reuse_or_alloc_node_gen_t =
289 __detail::_ReuseOrAllocNode<__node_alloc_type>;
290 using __alloc_node_gen_t =
291 __detail::_AllocNode<__node_alloc_type>;
292 using __node_builder_t =
293 __detail::_NodeBuilder<_ExtractKey>;
299 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
300 : _M_h(__h), _M_node(__n) { }
303 template<
typename... _Args>
304 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
306 _M_node(__h->_M_allocate_node(
std::
forward<_Args>(__args)...))
310 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
312 _Scoped_node(
const _Scoped_node&) =
delete;
313 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
315 __hashtable_alloc* _M_h;
319 template<
typename _Ht>
321 __conditional_t<std::is_lvalue_reference<_Ht>::value,
322 const value_type&, value_type&&>
323 __fwd_value_for(value_type& __val) noexcept
330 struct __hash_code_base_access : __hash_code_base
331 {
using __hash_code_base::_M_bucket_index; };
334 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
335 "Functor used to map hash code to bucket index"
336 " must be nothrow default constructible");
337 static_assert(noexcept(
338 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
339 "Functor used to map hash code to bucket index must be"
343 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
344 "_ExtractKey must be nothrow default constructible");
345 static_assert(noexcept(
346 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
347 "_ExtractKey functor must be noexcept invocable");
349 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
350 typename _ExtractKeya,
typename _Equala,
351 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
352 typename _RehashPolicya,
typename _Traitsa,
354 friend struct __detail::_Map_base;
356 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
357 typename _ExtractKeya,
typename _Equala,
358 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
359 typename _RehashPolicya,
typename _Traitsa>
360 friend struct __detail::_Insert_base;
362 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
363 typename _ExtractKeya,
typename _Equala,
364 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
365 typename _RehashPolicya,
typename _Traitsa,
366 bool _Constant_iteratorsa>
367 friend struct __detail::_Insert;
369 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
370 typename _ExtractKeya,
typename _Equala,
371 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
372 typename _RehashPolicya,
typename _Traitsa,
374 friend struct __detail::_Equality;
377 using size_type =
typename __hashtable_base::size_type;
378 using difference_type =
typename __hashtable_base::difference_type;
380 #if __cplusplus > 201402L
381 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
382 using insert_return_type = _Node_insert_return<iterator, node_type>;
386 __buckets_ptr _M_buckets = &_M_single_bucket;
387 size_type _M_bucket_count = 1;
388 __node_base _M_before_begin;
389 size_type _M_element_count = 0;
390 _RehashPolicy _M_rehash_policy;
398 __node_base_ptr _M_single_bucket =
nullptr;
404 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
408 _M_update_bbegin(__node_ptr __n)
410 _M_before_begin._M_nxt = __n;
415 _M_uses_single_bucket(__buckets_ptr __bkts)
const
416 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
419 _M_uses_single_bucket()
const
420 {
return _M_uses_single_bucket(_M_buckets); }
422 static constexpr
size_t
423 __small_size_threshold() noexcept
426 __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
430 _M_base_alloc() {
return *
this; }
433 _M_allocate_buckets(size_type __bkt_count)
435 if (__builtin_expect(__bkt_count == 1,
false))
437 _M_single_bucket =
nullptr;
438 return &_M_single_bucket;
441 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
445 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
447 if (_M_uses_single_bucket(__bkts))
450 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
454 _M_deallocate_buckets()
455 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
460 _M_bucket_begin(size_type __bkt)
const;
464 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
468 template<
typename _Ht>
470 _M_assign_elements(_Ht&&);
472 template<
typename _Ht,
typename _NodeGenerator>
474 _M_assign(_Ht&&,
const _NodeGenerator&);
485 _Hashtable(const _Hash& __h, const _Equal& __eq,
486 const allocator_type& __a)
487 : __hashtable_base(__h, __eq),
488 __hashtable_alloc(__node_alloc_type(__a)),
489 __enable_default_ctor(_Enable_default_constructor_tag{})
492 template<
bool _No_realloc = true>
493 static constexpr
bool
496 #if __cplusplus <= 201402L
497 return __and_<__bool_constant<_No_realloc>,
498 is_nothrow_copy_constructible<_Hash>,
499 is_nothrow_copy_constructible<_Equal>>::value;
501 if constexpr (_No_realloc)
502 if constexpr (is_nothrow_copy_constructible<_Hash>())
503 return is_nothrow_copy_constructible<_Equal>();
508 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
510 noexcept(_S_nothrow_move());
512 _Hashtable(_Hashtable&&, __node_alloc_type&&,
515 template<
typename _InputIterator>
516 _Hashtable(_InputIterator __first, _InputIterator __last,
517 size_type __bkt_count_hint,
518 const _Hash&,
const _Equal&,
const allocator_type&,
521 template<
typename _InputIterator>
522 _Hashtable(_InputIterator __first, _InputIterator __last,
523 size_type __bkt_count_hint,
524 const _Hash&,
const _Equal&,
const allocator_type&,
529 _Hashtable() =
default;
531 _Hashtable(
const _Hashtable&);
533 _Hashtable(
const _Hashtable&,
const allocator_type&);
536 _Hashtable(size_type __bkt_count_hint,
537 const _Hash& __hf = _Hash(),
538 const key_equal& __eql = key_equal(),
539 const allocator_type& __a = allocator_type());
542 _Hashtable(_Hashtable&& __ht)
543 noexcept(_S_nothrow_move())
544 : _Hashtable(
std::
move(__ht),
std::
move(__ht._M_node_allocator()),
548 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
549 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
550 : _Hashtable(
std::
move(__ht), __node_alloc_type(__a),
551 typename __node_alloc_traits::is_always_equal{})
555 _Hashtable(
const allocator_type& __a)
556 : __hashtable_alloc(__node_alloc_type(__a)),
557 __enable_default_ctor(_Enable_default_constructor_tag{})
560 template<
typename _InputIterator>
561 _Hashtable(_InputIterator __f, _InputIterator __l,
562 size_type __bkt_count_hint = 0,
563 const _Hash& __hf = _Hash(),
564 const key_equal& __eql = key_equal(),
565 const allocator_type& __a = allocator_type())
566 : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
570 _Hashtable(initializer_list<value_type> __l,
571 size_type __bkt_count_hint = 0,
572 const _Hash& __hf = _Hash(),
573 const key_equal& __eql = key_equal(),
574 const allocator_type& __a = allocator_type())
575 : _Hashtable(__l.
begin(), __l.
end(), __bkt_count_hint,
576 __hf, __eql, __a, __unique_keys{})
580 operator=(
const _Hashtable& __ht);
583 operator=(_Hashtable&& __ht)
584 noexcept(__node_alloc_traits::_S_nothrow_move()
585 && is_nothrow_move_assignable<_Hash>::value
586 && is_nothrow_move_assignable<_Equal>::value)
588 constexpr
bool __move_storage =
589 __node_alloc_traits::_S_propagate_on_move_assign()
590 || __node_alloc_traits::_S_always_equal();
591 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
596 operator=(initializer_list<value_type> __l)
598 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
599 _M_before_begin._M_nxt =
nullptr;
603 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
606 if (_M_bucket_count < __l_bkt_count)
607 rehash(__l_bkt_count);
609 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
613 ~_Hashtable() noexcept;
617 noexcept(__and_<__is_nothrow_swappable<_Hash>,
618 __is_nothrow_swappable<_Equal>>::value);
623 {
return iterator(_M_begin()); }
626 begin() const noexcept
627 {
return const_iterator(_M_begin()); }
631 {
return iterator(
nullptr); }
635 {
return const_iterator(
nullptr); }
639 {
return const_iterator(_M_begin()); }
642 cend() const noexcept
643 {
return const_iterator(
nullptr); }
646 size() const noexcept
647 {
return _M_element_count; }
649 _GLIBCXX_NODISCARD
bool
650 empty() const noexcept
651 {
return size() == 0; }
654 get_allocator() const noexcept
655 {
return allocator_type(this->_M_node_allocator()); }
658 max_size() const noexcept
659 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
664 {
return this->_M_eq(); }
670 bucket_count() const noexcept
671 {
return _M_bucket_count; }
674 max_bucket_count() const noexcept
675 {
return max_size(); }
678 bucket_size(size_type __bkt)
const
682 bucket(
const key_type& __k)
const
683 {
return _M_bucket_index(this->_M_hash_code(__k)); }
686 begin(size_type __bkt)
688 return local_iterator(*
this, _M_bucket_begin(__bkt),
689 __bkt, _M_bucket_count);
694 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
697 begin(size_type __bkt)
const
699 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
700 __bkt, _M_bucket_count);
704 end(size_type __bkt)
const
705 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
709 cbegin(size_type __bkt)
const
711 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
712 __bkt, _M_bucket_count);
716 cend(size_type __bkt)
const
717 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
720 load_factor() const noexcept
722 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
731 __rehash_policy()
const
732 {
return _M_rehash_policy; }
735 __rehash_policy(
const _RehashPolicy& __pol)
736 { _M_rehash_policy = __pol; }
740 find(
const key_type& __k);
743 find(
const key_type& __k)
const;
746 count(
const key_type& __k)
const;
749 equal_range(
const key_type& __k);
752 equal_range(
const key_type& __k)
const;
754 #if __cplusplus >= 202002L
755 #define __cpp_lib_generic_unordered_lookup 201811L
757 template<
typename _Kt,
758 typename = __has_is_transparent_t<_Hash, _Kt>,
759 typename = __has_is_transparent_t<_Equal, _Kt>>
761 _M_find_tr(
const _Kt& __k);
763 template<
typename _Kt,
764 typename = __has_is_transparent_t<_Hash, _Kt>,
765 typename = __has_is_transparent_t<_Equal, _Kt>>
767 _M_find_tr(
const _Kt& __k)
const;
769 template<
typename _Kt,
770 typename = __has_is_transparent_t<_Hash, _Kt>,
771 typename = __has_is_transparent_t<_Equal, _Kt>>
773 _M_count_tr(
const _Kt& __k)
const;
775 template<
typename _Kt,
776 typename = __has_is_transparent_t<_Hash, _Kt>,
777 typename = __has_is_transparent_t<_Equal, _Kt>>
778 pair<iterator, iterator>
779 _M_equal_range_tr(
const _Kt& __k);
781 template<
typename _Kt,
782 typename = __has_is_transparent_t<_Hash, _Kt>,
783 typename = __has_is_transparent_t<_Equal, _Kt>>
784 pair<const_iterator, const_iterator>
785 _M_equal_range_tr(
const _Kt& __k)
const;
791 _M_bucket_index(
const __node_value_type& __n)
const noexcept
792 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
795 _M_bucket_index(__hash_code __c)
const
796 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
799 _M_find_before_node(
const key_type&);
804 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
806 template<
typename _Kt>
808 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
811 _M_find_node(size_type __bkt,
const key_type& __key,
812 __hash_code __c)
const
814 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
816 return static_cast<__node_ptr
>(__before_n->_M_nxt);
820 template<
typename _Kt>
822 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
823 __hash_code __c)
const
825 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
827 return static_cast<__node_ptr
>(__before_n->_M_nxt);
833 _M_insert_bucket_begin(size_type, __node_ptr);
837 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
838 size_type __next_bkt);
842 _M_get_previous_node(size_type __bkt, __node_ptr __n);
844 pair<const_iterator, __hash_code>
845 _M_compute_hash_code(const_iterator __hint,
const key_type& __k)
const;
851 _M_insert_unique_node(size_type __bkt, __hash_code,
852 __node_ptr __n, size_type __n_elt = 1);
857 _M_insert_multi_node(__node_ptr __hint,
858 __hash_code __code, __node_ptr __n);
860 template<
typename... _Args>
862 _M_emplace(
true_type __uks, _Args&&... __args);
864 template<
typename... _Args>
866 _M_emplace(
false_type __uks, _Args&&... __args)
867 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
870 template<
typename... _Args>
872 _M_emplace(const_iterator,
true_type __uks, _Args&&... __args)
873 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
875 template<
typename... _Args>
877 _M_emplace(const_iterator,
false_type __uks, _Args&&... __args);
879 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
881 _M_insert_unique(_Kt&&, _Arg&&,
const _NodeGenerator&);
883 template<
typename _Kt>
884 static __conditional_t<
885 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
886 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
888 _S_forward_key(_Kt&& __k)
889 {
return std::forward<_Kt>(__k); }
891 static const key_type&
892 _S_forward_key(
const key_type& __k)
896 _S_forward_key(key_type&& __k)
899 template<
typename _Arg,
typename _NodeGenerator>
901 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
904 return _M_insert_unique(
905 _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
906 std::forward<_Arg>(__arg), __node_gen);
909 template<
typename _Arg,
typename _NodeGenerator>
911 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
914 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
919 template<
typename _Arg,
typename _NodeGenerator>
921 _M_insert(const_iterator, _Arg&& __arg,
922 const _NodeGenerator& __node_gen,
true_type __uks)
925 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
929 template<
typename _Arg,
typename _NodeGenerator>
931 _M_insert(const_iterator, _Arg&&,
935 _M_erase(
true_type __uks,
const key_type&);
941 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
945 template<
typename... _Args>
947 emplace(_Args&&... __args)
948 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
950 template<
typename... _Args>
952 emplace_hint(const_iterator __hint, _Args&&... __args)
954 return _M_emplace(__hint, __unique_keys{},
955 std::forward<_Args>(__args)...);
962 erase(const_iterator);
967 {
return erase(const_iterator(__it)); }
970 erase(
const key_type& __k)
971 {
return _M_erase(__unique_keys{}, __k); }
974 erase(const_iterator, const_iterator);
981 void rehash(size_type __bkt_count);
986 #if __cplusplus > 201402L
989 _M_reinsert_node(node_type&& __nh)
991 insert_return_type __ret;
993 __ret.position =
end();
996 __glibcxx_assert(get_allocator() == __nh.get_allocator());
998 const key_type& __k = __nh._M_key();
999 __hash_code __code = this->_M_hash_code(__k);
1000 size_type __bkt = _M_bucket_index(__code);
1001 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
1004 __ret.position = iterator(__n);
1005 __ret.inserted =
false;
1010 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1011 __nh._M_ptr =
nullptr;
1012 __ret.inserted =
true;
1020 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1025 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1027 const key_type& __k = __nh._M_key();
1028 auto __code = this->_M_hash_code(__k);
1030 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1031 __nh._M_ptr =
nullptr;
1037 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1039 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1040 if (__prev_n == _M_buckets[__bkt])
1041 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1042 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1043 else if (__n->_M_nxt)
1045 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1046 if (__next_bkt != __bkt)
1047 _M_buckets[__next_bkt] = __prev_n;
1050 __prev_n->_M_nxt = __n->_M_nxt;
1051 __n->_M_nxt =
nullptr;
1053 return { __n, this->_M_node_allocator() };
1059 extract(const_iterator __pos)
1061 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1062 return _M_extract_node(__bkt,
1063 _M_get_previous_node(__bkt, __pos._M_cur));
1068 extract(
const _Key& __k)
1071 __hash_code __code = this->_M_hash_code(__k);
1072 std::size_t __bkt = _M_bucket_index(__code);
1073 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1074 __nh = _M_extract_node(__bkt, __prev_node);
1079 template<
typename _Compatible_Hashtable>
1081 _M_merge_unique(_Compatible_Hashtable& __src)
1083 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1084 node_type>,
"Node types are compatible");
1085 __glibcxx_assert(get_allocator() == __src.get_allocator());
1087 auto __n_elt = __src.size();
1088 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1091 const key_type& __k = _ExtractKey{}(*__pos);
1093 = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
1094 size_type __bkt = _M_bucket_index(__code);
1095 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1097 auto __nh = __src.extract(__pos);
1098 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1099 __nh._M_ptr =
nullptr;
1102 else if (__n_elt != 1)
1108 template<
typename _Compatible_Hashtable>
1110 _M_merge_multi(_Compatible_Hashtable& __src)
1112 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1113 node_type>,
"Node types are compatible");
1114 __glibcxx_assert(get_allocator() == __src.get_allocator());
1116 __node_ptr __hint =
nullptr;
1117 this->reserve(
size() + __src.size());
1118 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1122 = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
1123 auto __nh = __src.extract(__pos);
1124 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1125 __nh._M_ptr =
nullptr;
1132 void _M_rehash_aux(size_type __bkt_count,
true_type __uks);
1135 void _M_rehash_aux(size_type __bkt_count,
false_type __uks);
1139 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1143 template<
typename _Key,
typename _Value,
typename _Alloc,
1144 typename _ExtractKey,
typename _Equal,
1145 typename _Hash,
typename _RangeHash,
typename _Unused,
1146 typename _RehashPolicy,
typename _Traits>
1148 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1149 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1150 _M_bucket_begin(size_type __bkt)
const
1153 __node_base_ptr __n = _M_buckets[__bkt];
1154 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
1157 template<
typename _Key,
typename _Value,
typename _Alloc,
1158 typename _ExtractKey,
typename _Equal,
1159 typename _Hash,
typename _RangeHash,
typename _Unused,
1160 typename _RehashPolicy,
typename _Traits>
1161 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1162 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1163 _Hashtable(size_type __bkt_count_hint,
1164 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1165 : _Hashtable(__h, __eq, __a)
1167 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1168 if (__bkt_count > _M_bucket_count)
1170 _M_buckets = _M_allocate_buckets(__bkt_count);
1171 _M_bucket_count = __bkt_count;
1175 template<
typename _Key,
typename _Value,
typename _Alloc,
1176 typename _ExtractKey,
typename _Equal,
1177 typename _Hash,
typename _RangeHash,
typename _Unused,
1178 typename _RehashPolicy,
typename _Traits>
1179 template<
typename _InputIterator>
1180 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1181 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1182 _Hashtable(_InputIterator __f, _InputIterator __l,
1183 size_type __bkt_count_hint,
1184 const _Hash& __h,
const _Equal& __eq,
1186 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1188 for (; __f != __l; ++__f)
1192 template<
typename _Key,
typename _Value,
typename _Alloc,
1193 typename _ExtractKey,
typename _Equal,
1194 typename _Hash,
typename _RangeHash,
typename _Unused,
1195 typename _RehashPolicy,
typename _Traits>
1196 template<
typename _InputIterator>
1197 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1198 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1199 _Hashtable(_InputIterator __f, _InputIterator __l,
1200 size_type __bkt_count_hint,
1201 const _Hash& __h,
const _Equal& __eq,
1203 : _Hashtable(__h, __eq, __a)
1205 auto __nb_elems = __detail::__distance_fw(__f, __l);
1207 _M_rehash_policy._M_next_bkt(
1208 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1211 if (__bkt_count > _M_bucket_count)
1213 _M_buckets = _M_allocate_buckets(__bkt_count);
1214 _M_bucket_count = __bkt_count;
1217 for (; __f != __l; ++__f)
1221 template<
typename _Key,
typename _Value,
typename _Alloc,
1222 typename _ExtractKey,
typename _Equal,
1223 typename _Hash,
typename _RangeHash,
typename _Unused,
1224 typename _RehashPolicy,
typename _Traits>
1226 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1227 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1228 operator=(
const _Hashtable& __ht)
1234 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1236 auto& __this_alloc = this->_M_node_allocator();
1237 auto& __that_alloc = __ht._M_node_allocator();
1238 if (!__node_alloc_traits::_S_always_equal()
1239 && __this_alloc != __that_alloc)
1242 this->_M_deallocate_nodes(_M_begin());
1243 _M_before_begin._M_nxt =
nullptr;
1244 _M_deallocate_buckets();
1245 _M_buckets =
nullptr;
1246 std::__alloc_on_copy(__this_alloc, __that_alloc);
1247 __hashtable_base::operator=(__ht);
1248 _M_bucket_count = __ht._M_bucket_count;
1249 _M_element_count = __ht._M_element_count;
1250 _M_rehash_policy = __ht._M_rehash_policy;
1251 __alloc_node_gen_t __alloc_node_gen(*
this);
1254 _M_assign(__ht, __alloc_node_gen);
1261 __throw_exception_again;
1265 std::__alloc_on_copy(__this_alloc, __that_alloc);
1269 _M_assign_elements(__ht);
1273 template<
typename _Key,
typename _Value,
typename _Alloc,
1274 typename _ExtractKey,
typename _Equal,
1275 typename _Hash,
typename _RangeHash,
typename _Unused,
1276 typename _RehashPolicy,
typename _Traits>
1277 template<
typename _Ht>
1279 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1280 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1281 _M_assign_elements(_Ht&& __ht)
1283 __buckets_ptr __former_buckets =
nullptr;
1284 std::size_t __former_bucket_count = _M_bucket_count;
1285 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1287 if (_M_bucket_count != __ht._M_bucket_count)
1289 __former_buckets = _M_buckets;
1290 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1291 _M_bucket_count = __ht._M_bucket_count;
1294 __builtin_memset(_M_buckets, 0,
1295 _M_bucket_count *
sizeof(__node_base_ptr));
1299 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1300 _M_element_count = __ht._M_element_count;
1301 _M_rehash_policy = __ht._M_rehash_policy;
1302 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1303 _M_before_begin._M_nxt =
nullptr;
1304 _M_assign(std::forward<_Ht>(__ht), __roan);
1305 if (__former_buckets)
1306 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1310 if (__former_buckets)
1313 _M_deallocate_buckets();
1314 _M_rehash_policy._M_reset(__former_state);
1315 _M_buckets = __former_buckets;
1316 _M_bucket_count = __former_bucket_count;
1318 __builtin_memset(_M_buckets, 0,
1319 _M_bucket_count *
sizeof(__node_base_ptr));
1320 __throw_exception_again;
1324 template<
typename _Key,
typename _Value,
typename _Alloc,
1325 typename _ExtractKey,
typename _Equal,
1326 typename _Hash,
typename _RangeHash,
typename _Unused,
1327 typename _RehashPolicy,
typename _Traits>
1328 template<
typename _Ht,
typename _NodeGenerator>
1330 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1331 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1332 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1334 __buckets_ptr __buckets =
nullptr;
1336 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1340 if (!__ht._M_before_begin._M_nxt)
1345 __node_ptr __ht_n = __ht._M_begin();
1347 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1348 this->_M_copy_code(*__this_n, *__ht_n);
1349 _M_update_bbegin(__this_n);
1352 __node_ptr __prev_n = __this_n;
1353 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1355 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1356 __prev_n->_M_nxt = __this_n;
1357 this->_M_copy_code(*__this_n, *__ht_n);
1358 size_type __bkt = _M_bucket_index(*__this_n);
1359 if (!_M_buckets[__bkt])
1360 _M_buckets[__bkt] = __prev_n;
1361 __prev_n = __this_n;
1368 _M_deallocate_buckets();
1369 __throw_exception_again;
1373 template<
typename _Key,
typename _Value,
typename _Alloc,
1374 typename _ExtractKey,
typename _Equal,
1375 typename _Hash,
typename _RangeHash,
typename _Unused,
1376 typename _RehashPolicy,
typename _Traits>
1378 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1379 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1382 _M_rehash_policy._M_reset();
1383 _M_bucket_count = 1;
1384 _M_single_bucket =
nullptr;
1385 _M_buckets = &_M_single_bucket;
1386 _M_before_begin._M_nxt =
nullptr;
1387 _M_element_count = 0;
1390 template<
typename _Key,
typename _Value,
typename _Alloc,
1391 typename _ExtractKey,
typename _Equal,
1392 typename _Hash,
typename _RangeHash,
typename _Unused,
1393 typename _RehashPolicy,
typename _Traits>
1395 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1396 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1397 _M_move_assign(_Hashtable&& __ht,
true_type)
1402 this->_M_deallocate_nodes(_M_begin());
1403 _M_deallocate_buckets();
1404 __hashtable_base::operator=(
std::move(__ht));
1405 _M_rehash_policy = __ht._M_rehash_policy;
1406 if (!__ht._M_uses_single_bucket())
1407 _M_buckets = __ht._M_buckets;
1410 _M_buckets = &_M_single_bucket;
1411 _M_single_bucket = __ht._M_single_bucket;
1414 _M_bucket_count = __ht._M_bucket_count;
1415 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1416 _M_element_count = __ht._M_element_count;
1417 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1424 template<
typename _Key,
typename _Value,
typename _Alloc,
1425 typename _ExtractKey,
typename _Equal,
1426 typename _Hash,
typename _RangeHash,
typename _Unused,
1427 typename _RehashPolicy,
typename _Traits>
1429 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1430 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1431 _M_move_assign(_Hashtable&& __ht,
false_type)
1433 if (__ht._M_node_allocator() == this->_M_node_allocator())
1443 template<
typename _Key,
typename _Value,
typename _Alloc,
1444 typename _ExtractKey,
typename _Equal,
1445 typename _Hash,
typename _RangeHash,
typename _Unused,
1446 typename _RehashPolicy,
typename _Traits>
1447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1448 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1449 _Hashtable(
const _Hashtable& __ht)
1450 : __hashtable_base(__ht),
1452 __rehash_base(__ht),
1454 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1455 __enable_default_ctor(__ht),
1456 _M_buckets(nullptr),
1457 _M_bucket_count(__ht._M_bucket_count),
1458 _M_element_count(__ht._M_element_count),
1459 _M_rehash_policy(__ht._M_rehash_policy)
1461 __alloc_node_gen_t __alloc_node_gen(*
this);
1462 _M_assign(__ht, __alloc_node_gen);
1465 template<
typename _Key,
typename _Value,
typename _Alloc,
1466 typename _ExtractKey,
typename _Equal,
1467 typename _Hash,
typename _RangeHash,
typename _Unused,
1468 typename _RehashPolicy,
typename _Traits>
1469 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1470 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1471 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1473 noexcept(_S_nothrow_move())
1474 : __hashtable_base(__ht),
1476 __rehash_base(__ht),
1477 __hashtable_alloc(
std::move(__a)),
1478 __enable_default_ctor(__ht),
1479 _M_buckets(__ht._M_buckets),
1480 _M_bucket_count(__ht._M_bucket_count),
1481 _M_before_begin(__ht._M_before_begin._M_nxt),
1482 _M_element_count(__ht._M_element_count),
1483 _M_rehash_policy(__ht._M_rehash_policy)
1486 if (__ht._M_uses_single_bucket())
1488 _M_buckets = &_M_single_bucket;
1489 _M_single_bucket = __ht._M_single_bucket;
1498 template<
typename _Key,
typename _Value,
typename _Alloc,
1499 typename _ExtractKey,
typename _Equal,
1500 typename _Hash,
typename _RangeHash,
typename _Unused,
1501 typename _RehashPolicy,
typename _Traits>
1502 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1503 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1504 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1505 : __hashtable_base(__ht),
1507 __rehash_base(__ht),
1508 __hashtable_alloc(__node_alloc_type(__a)),
1509 __enable_default_ctor(__ht),
1511 _M_bucket_count(__ht._M_bucket_count),
1512 _M_element_count(__ht._M_element_count),
1513 _M_rehash_policy(__ht._M_rehash_policy)
1515 __alloc_node_gen_t __alloc_node_gen(*
this);
1516 _M_assign(__ht, __alloc_node_gen);
1519 template<
typename _Key,
typename _Value,
typename _Alloc,
1520 typename _ExtractKey,
typename _Equal,
1521 typename _Hash,
typename _RangeHash,
typename _Unused,
1522 typename _RehashPolicy,
typename _Traits>
1523 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1524 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1525 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1527 : __hashtable_base(__ht),
1529 __rehash_base(__ht),
1530 __hashtable_alloc(
std::move(__a)),
1531 __enable_default_ctor(__ht),
1532 _M_buckets(nullptr),
1533 _M_bucket_count(__ht._M_bucket_count),
1534 _M_element_count(__ht._M_element_count),
1535 _M_rehash_policy(__ht._M_rehash_policy)
1537 if (__ht._M_node_allocator() == this->_M_node_allocator())
1539 if (__ht._M_uses_single_bucket())
1541 _M_buckets = &_M_single_bucket;
1542 _M_single_bucket = __ht._M_single_bucket;
1545 _M_buckets = __ht._M_buckets;
1549 _M_update_bbegin(__ht._M_begin());
1555 __alloc_node_gen_t __alloc_gen(*
this);
1557 using _Fwd_Ht = __conditional_t<
1558 __move_if_noexcept_cond<value_type>::value,
1559 const _Hashtable&, _Hashtable&&>;
1560 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1565 template<
typename _Key,
typename _Value,
typename _Alloc,
1566 typename _ExtractKey,
typename _Equal,
1567 typename _Hash,
typename _RangeHash,
typename _Unused,
1568 typename _RehashPolicy,
typename _Traits>
1569 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1570 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1571 ~_Hashtable() noexcept
1576 static_assert(noexcept(declval<const __hash_code_base_access&>()
1577 ._M_bucket_index(declval<const __node_value_type&>(),
1579 "Cache the hash code or qualify your functors involved"
1580 " in hash code and bucket index computation with noexcept");
1583 _M_deallocate_buckets();
1586 template<
typename _Key,
typename _Value,
typename _Alloc,
1587 typename _ExtractKey,
typename _Equal,
1588 typename _Hash,
typename _RangeHash,
typename _Unused,
1589 typename _RehashPolicy,
typename _Traits>
1591 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1592 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1593 swap(_Hashtable& __x)
1594 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1595 __is_nothrow_swappable<_Equal>>::value)
1602 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1603 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1606 if (this->_M_uses_single_bucket())
1608 if (!__x._M_uses_single_bucket())
1610 _M_buckets = __x._M_buckets;
1611 __x._M_buckets = &__x._M_single_bucket;
1614 else if (__x._M_uses_single_bucket())
1616 __x._M_buckets = _M_buckets;
1617 _M_buckets = &_M_single_bucket;
1622 std::swap(_M_bucket_count, __x._M_bucket_count);
1623 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1624 std::swap(_M_element_count, __x._M_element_count);
1625 std::swap(_M_single_bucket, __x._M_single_bucket);
1630 __x._M_update_bbegin();
1633 template<
typename _Key,
typename _Value,
typename _Alloc,
1634 typename _ExtractKey,
typename _Equal,
1635 typename _Hash,
typename _RangeHash,
typename _Unused,
1636 typename _RehashPolicy,
typename _Traits>
1638 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1639 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1640 find(
const key_type& __k)
1643 if (size() <= __small_size_threshold())
1645 for (
auto __it = begin(); __it != end(); ++__it)
1646 if (this->_M_key_equals(__k, *__it._M_cur))
1651 __hash_code __code = this->_M_hash_code(__k);
1652 std::size_t __bkt = _M_bucket_index(__code);
1653 return iterator(_M_find_node(__bkt, __k, __code));
1656 template<
typename _Key,
typename _Value,
typename _Alloc,
1657 typename _ExtractKey,
typename _Equal,
1658 typename _Hash,
typename _RangeHash,
typename _Unused,
1659 typename _RehashPolicy,
typename _Traits>
1661 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1662 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1663 find(
const key_type& __k)
const
1666 if (size() <= __small_size_threshold())
1668 for (
auto __it = begin(); __it != end(); ++__it)
1669 if (this->_M_key_equals(__k, *__it._M_cur))
1674 __hash_code __code = this->_M_hash_code(__k);
1675 std::size_t __bkt = _M_bucket_index(__code);
1676 return const_iterator(_M_find_node(__bkt, __k, __code));
1679 #if __cplusplus > 201703L
1680 template<
typename _Key,
typename _Value,
typename _Alloc,
1681 typename _ExtractKey,
typename _Equal,
1682 typename _Hash,
typename _RangeHash,
typename _Unused,
1683 typename _RehashPolicy,
typename _Traits>
1684 template<
typename _Kt,
typename,
typename>
1686 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1687 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1688 _M_find_tr(
const _Kt& __k)
1691 __hash_code __code = this->_M_hash_code_tr(__k);
1692 std::size_t __bkt = _M_bucket_index(__code);
1693 return iterator(_M_find_node_tr(__bkt, __k, __code));
1696 template<
typename _Key,
typename _Value,
typename _Alloc,
1697 typename _ExtractKey,
typename _Equal,
1698 typename _Hash,
typename _RangeHash,
typename _Unused,
1699 typename _RehashPolicy,
typename _Traits>
1700 template<
typename _Kt,
typename,
typename>
1702 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1703 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1704 _M_find_tr(
const _Kt& __k)
const
1707 __hash_code __code = this->_M_hash_code_tr(__k);
1708 std::size_t __bkt = _M_bucket_index(__code);
1709 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1713 template<
typename _Key,
typename _Value,
typename _Alloc,
1714 typename _ExtractKey,
typename _Equal,
1715 typename _Hash,
typename _RangeHash,
typename _Unused,
1716 typename _RehashPolicy,
typename _Traits>
1718 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1719 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1720 count(
const key_type& __k)
const
1723 auto __it = find(__k);
1727 if (__unique_keys::value)
1733 size_type __result = 1;
1734 for (
auto __ref = __it++;
1735 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1742 #if __cplusplus > 201703L
1743 template<
typename _Key,
typename _Value,
typename _Alloc,
1744 typename _ExtractKey,
typename _Equal,
1745 typename _Hash,
typename _RangeHash,
typename _Unused,
1746 typename _RehashPolicy,
typename _Traits>
1747 template<
typename _Kt,
typename,
typename>
1749 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1750 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1751 _M_count_tr(
const _Kt& __k)
const
1754 __hash_code __code = this->_M_hash_code_tr(__k);
1755 std::size_t __bkt = _M_bucket_index(__code);
1756 auto __n = _M_find_node_tr(__bkt, __k, __code);
1764 size_type __result = 1;
1766 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1774 template<
typename _Key,
typename _Value,
typename _Alloc,
1775 typename _ExtractKey,
typename _Equal,
1776 typename _Hash,
typename _RangeHash,
typename _Unused,
1777 typename _RehashPolicy,
typename _Traits>
1779 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1780 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1781 equal_range(
const key_type& __k)
1782 -> pair<iterator, iterator>
1784 auto __ite = find(__k);
1786 return { __ite, __ite };
1788 auto __beg = __ite++;
1789 if (__unique_keys::value)
1790 return { __beg, __ite };
1795 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1798 return { __beg, __ite };
1801 template<
typename _Key,
typename _Value,
typename _Alloc,
1802 typename _ExtractKey,
typename _Equal,
1803 typename _Hash,
typename _RangeHash,
typename _Unused,
1804 typename _RehashPolicy,
typename _Traits>
1806 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1807 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1808 equal_range(
const key_type& __k)
const
1809 -> pair<const_iterator, const_iterator>
1811 auto __ite = find(__k);
1813 return { __ite, __ite };
1815 auto __beg = __ite++;
1816 if (__unique_keys::value)
1817 return { __beg, __ite };
1822 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1825 return { __beg, __ite };
1828 #if __cplusplus > 201703L
1829 template<
typename _Key,
typename _Value,
typename _Alloc,
1830 typename _ExtractKey,
typename _Equal,
1831 typename _Hash,
typename _RangeHash,
typename _Unused,
1832 typename _RehashPolicy,
typename _Traits>
1833 template<
typename _Kt,
typename,
typename>
1835 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1836 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1837 _M_equal_range_tr(
const _Kt& __k)
1838 -> pair<iterator, iterator>
1840 __hash_code __code = this->_M_hash_code_tr(__k);
1841 std::size_t __bkt = _M_bucket_index(__code);
1842 auto __n = _M_find_node_tr(__bkt, __k, __code);
1843 iterator __ite(__n);
1845 return { __ite, __ite };
1850 auto __beg = __ite++;
1851 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1854 return { __beg, __ite };
1857 template<
typename _Key,
typename _Value,
typename _Alloc,
1858 typename _ExtractKey,
typename _Equal,
1859 typename _Hash,
typename _RangeHash,
typename _Unused,
1860 typename _RehashPolicy,
typename _Traits>
1861 template<
typename _Kt,
typename,
typename>
1863 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1864 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1865 _M_equal_range_tr(
const _Kt& __k)
const
1866 -> pair<const_iterator, const_iterator>
1868 __hash_code __code = this->_M_hash_code_tr(__k);
1869 std::size_t __bkt = _M_bucket_index(__code);
1870 auto __n = _M_find_node_tr(__bkt, __k, __code);
1871 const_iterator __ite(__n);
1873 return { __ite, __ite };
1878 auto __beg = __ite++;
1879 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1882 return { __beg, __ite };
1888 template<
typename _Key,
typename _Value,
typename _Alloc,
1889 typename _ExtractKey,
typename _Equal,
1890 typename _Hash,
typename _RangeHash,
typename _Unused,
1891 typename _RehashPolicy,
typename _Traits>
1893 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1894 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1895 _M_find_before_node(
const key_type& __k)
1898 __node_base_ptr __prev_p = &_M_before_begin;
1899 if (!__prev_p->_M_nxt)
1902 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);
1904 __p = __p->_M_next())
1906 if (this->_M_key_equals(__k, *__p))
1917 template<
typename _Key,
typename _Value,
typename _Alloc,
1918 typename _ExtractKey,
typename _Equal,
1919 typename _Hash,
typename _RangeHash,
typename _Unused,
1920 typename _RehashPolicy,
typename _Traits>
1922 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1923 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1924 _M_find_before_node(size_type __bkt,
const key_type& __k,
1925 __hash_code __code)
const
1928 __node_base_ptr __prev_p = _M_buckets[__bkt];
1932 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1933 __p = __p->_M_next())
1935 if (this->_M_equals(__k, __code, *__p))
1938 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1946 template<
typename _Key,
typename _Value,
typename _Alloc,
1947 typename _ExtractKey,
typename _Equal,
1948 typename _Hash,
typename _RangeHash,
typename _Unused,
1949 typename _RehashPolicy,
typename _Traits>
1950 template<
typename _Kt>
1952 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1953 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1954 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1955 __hash_code __code)
const
1958 __node_base_ptr __prev_p = _M_buckets[__bkt];
1962 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1963 __p = __p->_M_next())
1965 if (this->_M_equals_tr(__k, __code, *__p))
1968 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1976 template<
typename _Key,
typename _Value,
typename _Alloc,
1977 typename _ExtractKey,
typename _Equal,
1978 typename _Hash,
typename _RangeHash,
typename _Unused,
1979 typename _RehashPolicy,
typename _Traits>
1981 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1982 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1983 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1985 if (_M_buckets[__bkt])
1989 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1990 _M_buckets[__bkt]->_M_nxt = __node;
1997 __node->_M_nxt = _M_before_begin._M_nxt;
1998 _M_before_begin._M_nxt = __node;
2003 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
2005 _M_buckets[__bkt] = &_M_before_begin;
2009 template<
typename _Key,
typename _Value,
typename _Alloc,
2010 typename _ExtractKey,
typename _Equal,
2011 typename _Hash,
typename _RangeHash,
typename _Unused,
2012 typename _RehashPolicy,
typename _Traits>
2014 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2015 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2016 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
2017 size_type __next_bkt)
2019 if (!__next || __next_bkt != __bkt)
2024 _M_buckets[__next_bkt] = _M_buckets[__bkt];
2027 if (&_M_before_begin == _M_buckets[__bkt])
2028 _M_before_begin._M_nxt = __next;
2029 _M_buckets[__bkt] =
nullptr;
2033 template<
typename _Key,
typename _Value,
typename _Alloc,
2034 typename _ExtractKey,
typename _Equal,
2035 typename _Hash,
typename _RangeHash,
typename _Unused,
2036 typename _RehashPolicy,
typename _Traits>
2038 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2039 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2040 _M_get_previous_node(size_type __bkt, __node_ptr __n)
2043 __node_base_ptr __prev_n = _M_buckets[__bkt];
2044 while (__prev_n->_M_nxt != __n)
2045 __prev_n = __prev_n->_M_nxt;
2049 template<
typename _Key,
typename _Value,
typename _Alloc,
2050 typename _ExtractKey,
typename _Equal,
2051 typename _Hash,
typename _RangeHash,
typename _Unused,
2052 typename _RehashPolicy,
typename _Traits>
2053 template<
typename... _Args>
2055 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2056 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2057 _M_emplace(
true_type , _Args&&... __args)
2058 -> pair<iterator, bool>
2061 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2062 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2063 if (size() <= __small_size_threshold())
2065 for (
auto __it = begin(); __it != end(); ++__it)
2066 if (this->_M_key_equals(__k, *__it._M_cur))
2068 return { __it,
false };
2071 __hash_code __code = this->_M_hash_code(__k);
2072 size_type __bkt = _M_bucket_index(__code);
2073 if (size() > __small_size_threshold())
2074 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2076 return { iterator(__p),
false };
2079 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2080 __node._M_node =
nullptr;
2081 return { __pos,
true };
2084 template<
typename _Key,
typename _Value,
typename _Alloc,
2085 typename _ExtractKey,
typename _Equal,
2086 typename _Hash,
typename _RangeHash,
typename _Unused,
2087 typename _RehashPolicy,
typename _Traits>
2088 template<
typename... _Args>
2090 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2091 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2092 _M_emplace(const_iterator __hint,
false_type ,
2097 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2098 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2100 auto __res = this->_M_compute_hash_code(__hint, __k);
2102 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2104 __node._M_node =
nullptr;
2108 template<
typename _Key,
typename _Value,
typename _Alloc,
2109 typename _ExtractKey,
typename _Equal,
2110 typename _Hash,
typename _RangeHash,
typename _Unused,
2111 typename _RehashPolicy,
typename _Traits>
2113 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2114 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2115 _M_compute_hash_code(const_iterator __hint,
const key_type& __k)
const
2116 -> pair<const_iterator, __hash_code>
2118 if (size() <= __small_size_threshold())
2120 if (__hint != cend())
2122 for (
auto __it = __hint; __it != cend(); ++__it)
2123 if (this->_M_key_equals(__k, *__it._M_cur))
2124 return { __it, this->_M_hash_code(*__it._M_cur) };
2127 for (
auto __it = cbegin(); __it != __hint; ++__it)
2128 if (this->_M_key_equals(__k, *__it._M_cur))
2129 return { __it, this->_M_hash_code(*__it._M_cur) };
2132 return { __hint, this->_M_hash_code(__k) };
2135 template<
typename _Key,
typename _Value,
typename _Alloc,
2136 typename _ExtractKey,
typename _Equal,
2137 typename _Hash,
typename _RangeHash,
typename _Unused,
2138 typename _RehashPolicy,
typename _Traits>
2140 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2141 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2142 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2143 __node_ptr __node, size_type __n_elt)
2146 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2148 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2151 if (__do_rehash.
first)
2153 _M_rehash(__do_rehash.
second, __saved_state);
2154 __bkt = _M_bucket_index(__code);
2157 this->_M_store_code(*__node, __code);
2160 _M_insert_bucket_begin(__bkt, __node);
2162 return iterator(__node);
2165 template<
typename _Key,
typename _Value,
typename _Alloc,
2166 typename _ExtractKey,
typename _Equal,
2167 typename _Hash,
typename _RangeHash,
typename _Unused,
2168 typename _RehashPolicy,
typename _Traits>
2170 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2171 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2172 _M_insert_multi_node(__node_ptr __hint,
2173 __hash_code __code, __node_ptr __node)
2176 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2178 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2180 if (__do_rehash.
first)
2181 _M_rehash(__do_rehash.
second, __saved_state);
2183 this->_M_store_code(*__node, __code);
2184 const key_type& __k = _ExtractKey{}(__node->_M_v());
2185 size_type __bkt = _M_bucket_index(__code);
2189 __node_base_ptr __prev
2190 = __builtin_expect(__hint !=
nullptr,
false)
2191 && this->_M_equals(__k, __code, *__hint)
2193 : _M_find_before_node(__bkt, __k, __code);
2198 __node->_M_nxt = __prev->_M_nxt;
2199 __prev->_M_nxt = __node;
2200 if (__builtin_expect(__prev == __hint,
false))
2204 && !this->_M_equals(__k, __code, *__node->_M_next()))
2206 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2207 if (__next_bkt != __bkt)
2208 _M_buckets[__next_bkt] = __node;
2215 _M_insert_bucket_begin(__bkt, __node);
2217 return iterator(__node);
2221 template<
typename _Key,
typename _Value,
typename _Alloc,
2222 typename _ExtractKey,
typename _Equal,
2223 typename _Hash,
typename _RangeHash,
typename _Unused,
2224 typename _RehashPolicy,
typename _Traits>
2225 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
2227 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2228 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2229 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2230 const _NodeGenerator& __node_gen)
2231 -> pair<iterator, bool>
2233 if (size() <= __small_size_threshold())
2234 for (
auto __it = begin(); __it != end(); ++__it)
2235 if (this->_M_key_equals_tr(__k, *__it._M_cur))
2236 return { __it,
false };
2238 __hash_code __code = this->_M_hash_code_tr(__k);
2239 size_type __bkt = _M_bucket_index(__code);
2241 if (size() > __small_size_threshold())
2242 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2243 return { iterator(__node),
false };
2245 _Scoped_node __node {
2246 __node_builder_t::_S_build(std::forward<_Kt>(__k),
2247 std::forward<_Arg>(__v),
2252 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2253 __node._M_node =
nullptr;
2254 return { __pos,
true };
2258 template<
typename _Key,
typename _Value,
typename _Alloc,
2259 typename _ExtractKey,
typename _Equal,
2260 typename _Hash,
typename _RangeHash,
typename _Unused,
2261 typename _RehashPolicy,
typename _Traits>
2262 template<
typename _Arg,
typename _NodeGenerator>
2264 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2265 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2266 _M_insert(const_iterator __hint, _Arg&& __v,
2267 const _NodeGenerator& __node_gen,
2272 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2275 auto __res = this->_M_compute_hash_code(
2276 __hint, _ExtractKey{}(__node._M_node->_M_v()));
2279 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2281 __node._M_node =
nullptr;
2285 template<
typename _Key,
typename _Value,
typename _Alloc,
2286 typename _ExtractKey,
typename _Equal,
2287 typename _Hash,
typename _RangeHash,
typename _Unused,
2288 typename _RehashPolicy,
typename _Traits>
2290 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2291 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2292 erase(const_iterator __it)
2295 __node_ptr __n = __it._M_cur;
2296 std::size_t __bkt = _M_bucket_index(*__n);
2301 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2302 return _M_erase(__bkt, __prev_n, __n);
2305 template<
typename _Key,
typename _Value,
typename _Alloc,
2306 typename _ExtractKey,
typename _Equal,
2307 typename _Hash,
typename _RangeHash,
typename _Unused,
2308 typename _RehashPolicy,
typename _Traits>
2310 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2311 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2312 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2315 if (__prev_n == _M_buckets[__bkt])
2316 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2317 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2318 else if (__n->_M_nxt)
2320 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2321 if (__next_bkt != __bkt)
2322 _M_buckets[__next_bkt] = __prev_n;
2325 __prev_n->_M_nxt = __n->_M_nxt;
2326 iterator __result(__n->_M_next());
2327 this->_M_deallocate_node(__n);
2333 template<
typename _Key,
typename _Value,
typename _Alloc,
2334 typename _ExtractKey,
typename _Equal,
2335 typename _Hash,
typename _RangeHash,
typename _Unused,
2336 typename _RehashPolicy,
typename _Traits>
2338 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2339 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2340 _M_erase(
true_type ,
const key_type& __k)
2343 __node_base_ptr __prev_n;
2346 if (size() <= __small_size_threshold())
2348 __prev_n = _M_find_before_node(__k);
2353 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2354 __bkt = _M_bucket_index(*__n);
2358 __hash_code __code = this->_M_hash_code(__k);
2359 __bkt = _M_bucket_index(__code);
2362 __prev_n = _M_find_before_node(__bkt, __k, __code);
2367 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2370 _M_erase(__bkt, __prev_n, __n);
2374 template<
typename _Key,
typename _Value,
typename _Alloc,
2375 typename _ExtractKey,
typename _Equal,
2376 typename _Hash,
typename _RangeHash,
typename _Unused,
2377 typename _RehashPolicy,
typename _Traits>
2379 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2380 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2385 __node_base_ptr __prev_n;
2387 if (size() <= __small_size_threshold())
2389 __prev_n = _M_find_before_node(__k);
2394 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2395 __bkt = _M_bucket_index(*__n);
2399 __hash_code __code = this->_M_hash_code(__k);
2400 __bkt = _M_bucket_index(__code);
2403 __prev_n = _M_find_before_node(__bkt, __k, __code);
2407 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2416 __node_ptr __n_last = __n->_M_next();
2417 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2418 __n_last = __n_last->_M_next();
2420 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2423 size_type __result = 0;
2426 __node_ptr __p = __n->_M_next();
2427 this->_M_deallocate_node(__n);
2431 while (__n != __n_last);
2433 _M_element_count -= __result;
2434 if (__prev_n == _M_buckets[__bkt])
2435 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2436 else if (__n_last_bkt != __bkt)
2437 _M_buckets[__n_last_bkt] = __prev_n;
2438 __prev_n->_M_nxt = __n_last;
2442 template<
typename _Key,
typename _Value,
typename _Alloc,
2443 typename _ExtractKey,
typename _Equal,
2444 typename _Hash,
typename _RangeHash,
typename _Unused,
2445 typename _RehashPolicy,
typename _Traits>
2447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2448 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2449 erase(const_iterator __first, const_iterator __last)
2452 __node_ptr __n = __first._M_cur;
2453 __node_ptr __last_n = __last._M_cur;
2454 if (__n == __last_n)
2455 return iterator(__n);
2457 std::size_t __bkt = _M_bucket_index(*__n);
2459 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2460 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2461 std::size_t __n_bkt = __bkt;
2466 __node_ptr __tmp = __n;
2467 __n = __n->_M_next();
2468 this->_M_deallocate_node(__tmp);
2472 __n_bkt = _M_bucket_index(*__n);
2474 while (__n != __last_n && __n_bkt == __bkt);
2475 if (__is_bucket_begin)
2476 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2477 if (__n == __last_n)
2479 __is_bucket_begin =
true;
2483 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2484 _M_buckets[__n_bkt] = __prev_n;
2485 __prev_n->_M_nxt = __n;
2486 return iterator(__n);
2489 template<
typename _Key,
typename _Value,
typename _Alloc,
2490 typename _ExtractKey,
typename _Equal,
2491 typename _Hash,
typename _RangeHash,
typename _Unused,
2492 typename _RehashPolicy,
typename _Traits>
2494 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2495 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2498 this->_M_deallocate_nodes(_M_begin());
2499 __builtin_memset(_M_buckets, 0,
2500 _M_bucket_count *
sizeof(__node_base_ptr));
2501 _M_element_count = 0;
2502 _M_before_begin._M_nxt =
nullptr;
2505 template<
typename _Key,
typename _Value,
typename _Alloc,
2506 typename _ExtractKey,
typename _Equal,
2507 typename _Hash,
typename _RangeHash,
typename _Unused,
2508 typename _RehashPolicy,
typename _Traits>
2510 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2511 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2512 rehash(size_type __bkt_count)
2514 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2516 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2518 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2520 if (__bkt_count != _M_bucket_count)
2521 _M_rehash(__bkt_count, __saved_state);
2525 _M_rehash_policy._M_reset(__saved_state);
2528 template<
typename _Key,
typename _Value,
typename _Alloc,
2529 typename _ExtractKey,
typename _Equal,
2530 typename _Hash,
typename _RangeHash,
typename _Unused,
2531 typename _RehashPolicy,
typename _Traits>
2533 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2534 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2535 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2539 _M_rehash_aux(__bkt_count, __unique_keys{});
2545 _M_rehash_policy._M_reset(__state);
2546 __throw_exception_again;
2551 template<
typename _Key,
typename _Value,
typename _Alloc,
2552 typename _ExtractKey,
typename _Equal,
2553 typename _Hash,
typename _RangeHash,
typename _Unused,
2554 typename _RehashPolicy,
typename _Traits>
2556 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2557 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2558 _M_rehash_aux(size_type __bkt_count,
true_type )
2560 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2561 __node_ptr __p = _M_begin();
2562 _M_before_begin._M_nxt =
nullptr;
2563 std::size_t __bbegin_bkt = 0;
2566 __node_ptr __next = __p->_M_next();
2568 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2569 if (!__new_buckets[__bkt])
2571 __p->_M_nxt = _M_before_begin._M_nxt;
2572 _M_before_begin._M_nxt = __p;
2573 __new_buckets[__bkt] = &_M_before_begin;
2575 __new_buckets[__bbegin_bkt] = __p;
2576 __bbegin_bkt = __bkt;
2580 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2581 __new_buckets[__bkt]->_M_nxt = __p;
2587 _M_deallocate_buckets();
2588 _M_bucket_count = __bkt_count;
2589 _M_buckets = __new_buckets;
2594 template<
typename _Key,
typename _Value,
typename _Alloc,
2595 typename _ExtractKey,
typename _Equal,
2596 typename _Hash,
typename _RangeHash,
typename _Unused,
2597 typename _RehashPolicy,
typename _Traits>
2599 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2600 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2601 _M_rehash_aux(size_type __bkt_count,
false_type )
2603 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2604 __node_ptr __p = _M_begin();
2605 _M_before_begin._M_nxt =
nullptr;
2606 std::size_t __bbegin_bkt = 0;
2607 std::size_t __prev_bkt = 0;
2608 __node_ptr __prev_p =
nullptr;
2609 bool __check_bucket =
false;
2613 __node_ptr __next = __p->_M_next();
2615 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2617 if (__prev_p && __prev_bkt == __bkt)
2622 __p->_M_nxt = __prev_p->_M_nxt;
2623 __prev_p->_M_nxt = __p;
2630 __check_bucket =
true;
2638 if (__prev_p->_M_nxt)
2640 std::size_t __next_bkt
2641 = __hash_code_base::_M_bucket_index(
2642 *__prev_p->_M_next(), __bkt_count);
2643 if (__next_bkt != __prev_bkt)
2644 __new_buckets[__next_bkt] = __prev_p;
2646 __check_bucket =
false;
2649 if (!__new_buckets[__bkt])
2651 __p->_M_nxt = _M_before_begin._M_nxt;
2652 _M_before_begin._M_nxt = __p;
2653 __new_buckets[__bkt] = &_M_before_begin;
2655 __new_buckets[__bbegin_bkt] = __p;
2656 __bbegin_bkt = __bkt;
2660 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2661 __new_buckets[__bkt]->_M_nxt = __p;
2669 if (__check_bucket && __prev_p->_M_nxt)
2671 std::size_t __next_bkt
2672 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2674 if (__next_bkt != __prev_bkt)
2675 __new_buckets[__next_bkt] = __prev_p;
2678 _M_deallocate_buckets();
2679 _M_bucket_count = __bkt_count;
2680 _M_buckets = __new_buckets;
2683 #if __cplusplus > 201402L
2684 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2687 #if __cpp_deduction_guides >= 201606
2689 template<
typename _Hash>
2690 using _RequireNotAllocatorOrIntegral
2691 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2695 _GLIBCXX_END_NAMESPACE_VERSION
2698 #endif // _HASHTABLE_H