32 #define _HASHTABLE_H 1
34 #pragma GCC system_header
38 namespace std _GLIBCXX_VISIBILITY(default)
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
141 template<
typename _Key,
typename _Value,
typename _Allocator,
142 typename _ExtractKey,
typename _Equal,
143 typename _H1,
typename _H2,
typename _Hash,
144 typename _RehashPolicy,
145 bool __cache_hash_code,
146 bool __constant_iterators,
149 :
public __detail::_Rehash_base<_RehashPolicy,
150 _Hashtable<_Key, _Value, _Allocator,
152 _Equal, _H1, _H2, _Hash,
155 __constant_iterators,
157 public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
158 _H1, _H2, _Hash, __cache_hash_code>,
159 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
160 _Hashtable<_Key, _Value, _Allocator,
162 _Equal, _H1, _H2, _Hash,
165 __constant_iterators,
167 public __detail::_Equality_base<_ExtractKey, __unique_keys,
168 _Hashtable<_Key, _Value, _Allocator,
170 _Equal, _H1, _H2, _Hash,
173 __constant_iterators,
176 template<
typename _Cond>
177 using __if_hash_code_cached
178 = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
180 template<
typename _Cond>
181 using __if_hash_code_not_cached
182 = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
186 static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
188 "Cache the hash code or qualify your hash functor with noexcept");
197 "Functor used to map hash code to bucket index must be empty");
199 typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
201 __cache_hash_code> _HCBase;
206 "Cache the hash code or make functors involved in hash code"
207 " and bucket index computation empty");
210 typedef _Allocator allocator_type;
211 typedef _Value value_type;
212 typedef _Key key_type;
213 typedef _Equal key_equal;
216 typedef typename _Allocator::pointer pointer;
217 typedef typename _Allocator::const_pointer const_pointer;
218 typedef typename _Allocator::reference reference;
219 typedef typename _Allocator::const_reference const_reference;
221 typedef std::size_t size_type;
222 typedef std::ptrdiff_t difference_type;
223 typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
225 __constant_iterators,
228 typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
230 __constant_iterators,
232 const_local_iterator;
233 typedef __detail::_Node_iterator<value_type, __constant_iterators,
236 typedef __detail::_Node_const_iterator<value_type,
237 __constant_iterators,
241 template<
typename _Key2,
typename _Value2,
typename _Ex2,
bool __unique2,
242 typename _Hashtable2>
243 friend struct __detail::_Map_base;
246 typedef typename _RehashPolicy::_State _RehashPolicyState;
247 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
248 typedef typename _Allocator::template rebind<_Node>::other
249 _Node_allocator_type;
250 typedef __detail::_Hash_node_base _BaseNode;
251 typedef _BaseNode* _Bucket;
252 typedef typename _Allocator::template rebind<_Bucket>::other
253 _Bucket_allocator_type;
255 typedef typename _Allocator::template rebind<_Value>::other
256 _Value_allocator_type;
258 _Node_allocator_type _M_node_allocator;
260 size_type _M_bucket_count;
261 _BaseNode _M_before_begin;
262 size_type _M_element_count;
263 _RehashPolicy _M_rehash_policy;
265 template<
typename... _Args>
267 _M_allocate_node(_Args&&... __args);
270 _M_deallocate_node(_Node* __n);
274 _M_deallocate_nodes(_Node* __n);
277 _M_allocate_buckets(size_type __n);
280 _M_deallocate_buckets(_Bucket*, size_type __n);
285 _M_bucket_begin(size_type __bkt)
const;
289 {
return static_cast<_Node*
>(_M_before_begin._M_nxt); }
294 const _H1&,
const _H2&,
const _Hash&,
295 const _Equal&,
const _ExtractKey&,
296 const allocator_type&);
298 template<
typename _InputIterator>
299 _Hashtable(_InputIterator __first, _InputIterator __last,
300 size_type __bucket_hint,
301 const _H1&,
const _H2&,
const _Hash&,
302 const _Equal&,
const _ExtractKey&,
303 const allocator_type&);
334 {
return iterator(_M_begin()); }
337 begin()
const noexcept
338 {
return const_iterator(_M_begin()); }
342 {
return iterator(
nullptr); }
346 {
return const_iterator(
nullptr); }
349 cbegin()
const noexcept
350 {
return const_iterator(_M_begin()); }
353 cend()
const noexcept
354 {
return const_iterator(
nullptr); }
357 size()
const noexcept
358 {
return _M_element_count; }
361 empty()
const noexcept
362 {
return size() == 0; }
365 get_allocator()
const noexcept
366 {
return allocator_type(_M_node_allocator); }
369 max_size()
const noexcept
370 {
return _M_node_allocator.max_size(); }
375 {
return this->_M_eq(); }
381 bucket_count()
const noexcept
382 {
return _M_bucket_count; }
385 max_bucket_count()
const noexcept
386 {
return max_size(); }
389 bucket_size(size_type __n)
const
393 bucket(
const key_type& __k)
const
394 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
398 {
return local_iterator(_M_bucket_begin(__n), __n,
403 {
return local_iterator(
nullptr, __n, _M_bucket_count); }
406 begin(size_type __n)
const
407 {
return const_local_iterator(_M_bucket_begin(__n), __n,
411 end(size_type __n)
const
412 {
return const_local_iterator(
nullptr, __n, _M_bucket_count); }
416 cbegin(size_type __n)
const
417 {
return const_local_iterator(_M_bucket_begin(__n), __n,
421 cend(size_type __n)
const
422 {
return const_local_iterator(
nullptr, __n, _M_bucket_count); }
425 load_factor()
const noexcept
427 return static_cast<float>(
size()) / static_cast<float>(bucket_count());
435 __rehash_policy()
const
436 {
return _M_rehash_policy; }
439 __rehash_policy(
const _RehashPolicy&);
443 find(
const key_type& __k);
446 find(
const key_type& __k)
const;
449 count(
const key_type& __k)
const;
452 equal_range(
const key_type& __k);
455 equal_range(
const key_type& __k)
const;
460 _M_bucket_index(_Node* __n)
const
461 {
return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
464 _M_bucket_index(
const key_type& __k,
465 typename _Hashtable::_Hash_code_type __c)
const
466 {
return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
471 _M_find_before_node(size_type,
const key_type&,
472 typename _Hashtable::_Hash_code_type)
const;
475 _M_find_node(size_type __bkt,
const key_type& __key,
476 typename _Hashtable::_Hash_code_type __c)
const
478 _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
480 return static_cast<_Node*
>(__before_n->_M_nxt);
486 _M_insert_bucket_begin(size_type, _Node*);
490 _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
491 size_type __next_bkt);
495 _M_get_previous_node(size_type __bkt, _BaseNode* __n);
497 template<
typename _Arg>
499 _M_insert_bucket(_Arg&&, size_type,
500 typename _Hashtable::_Hash_code_type);
508 std::_Select1st<_Insert_Return_Type>,
509 std::_Identity<_Insert_Return_Type>
514 template<
typename... _Args>
518 template<
typename... _Args>
522 template<
typename _Arg>
526 template<
typename _Arg>
532 template<
typename... _Args>
534 emplace(_Args&&... __args)
536 std::forward<_Args>(__args)...); }
538 template<
typename... _Args>
540 emplace_hint(const_iterator, _Args&&... __args)
544 insert(
const value_type& __v)
548 insert(const_iterator,
const value_type& __v)
551 template<
typename _Pair,
typename =
typename
554 value_type>>::value>::type>
557 {
return _M_insert(std::forward<_Pair>(__v),
560 template<
typename _Pair,
typename =
typename
563 value_type>>::value>::type>
565 insert(const_iterator, _Pair&& __v)
568 template<
typename _InputIterator>
570 insert(_InputIterator __first, _InputIterator __last);
574 { this->insert(__l.begin(), __l.end()); }
577 erase(const_iterator);
582 {
return erase(const_iterator(__it)); }
585 erase(
const key_type&);
588 erase(const_iterator, const_iterator);
594 void rehash(size_type __n);
608 void _M_rehash(size_type __n,
const _RehashPolicyState& __state);
613 template<
typename _Key,
typename _Value,
614 typename _Allocator,
typename _ExtractKey,
typename _Equal,
615 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
616 bool __chc,
bool __cit,
bool __uk>
617 template<
typename... _Args>
618 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
619 _H1, _H2, _Hash, _RehashPolicy,
620 __chc, __cit, __uk>::_Node*
621 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
622 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
623 _M_allocate_node(_Args&&... __args)
625 _Node* __n = _M_node_allocator.allocate(1);
628 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
633 _M_node_allocator.deallocate(__n, 1);
634 __throw_exception_again;
638 template<
typename _Key,
typename _Value,
639 typename _Allocator,
typename _ExtractKey,
typename _Equal,
640 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
641 bool __chc,
bool __cit,
bool __uk>
643 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
644 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
645 _M_deallocate_node(_Node* __n)
647 _M_node_allocator.destroy(__n);
648 _M_node_allocator.deallocate(__n, 1);
651 template<
typename _Key,
typename _Value,
652 typename _Allocator,
typename _ExtractKey,
typename _Equal,
653 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
654 bool __chc,
bool __cit,
bool __uk>
656 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
657 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
658 _M_deallocate_nodes(_Node* __n)
663 __n = __n->_M_next();
664 _M_deallocate_node(__tmp);
668 template<
typename _Key,
typename _Value,
669 typename _Allocator,
typename _ExtractKey,
typename _Equal,
670 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
671 bool __chc,
bool __cit,
bool __uk>
672 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
673 _H1, _H2, _Hash, _RehashPolicy,
674 __chc, __cit, __uk>::_Bucket*
675 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
676 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
677 _M_allocate_buckets(size_type __n)
679 _Bucket_allocator_type __alloc(_M_node_allocator);
681 _Bucket* __p = __alloc.allocate(__n);
682 __builtin_memset(__p, 0, __n *
sizeof(_Bucket));
686 template<
typename _Key,
typename _Value,
687 typename _Allocator,
typename _ExtractKey,
typename _Equal,
688 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
689 bool __chc,
bool __cit,
bool __uk>
691 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
692 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
693 _M_deallocate_buckets(_Bucket* __p, size_type __n)
695 _Bucket_allocator_type __alloc(_M_node_allocator);
696 __alloc.deallocate(__p, __n);
699 template<
typename _Key,
typename _Value,
700 typename _Allocator,
typename _ExtractKey,
typename _Equal,
701 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
702 bool __chc,
bool __cit,
bool __uk>
703 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
704 _Equal, _H1, _H2, _Hash, _RehashPolicy,
705 __chc, __cit, __uk>::_Node*
706 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
707 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
708 _M_bucket_begin(size_type __bkt)
const
710 _BaseNode* __n = _M_buckets[__bkt];
711 return __n ?
static_cast<_Node*
>(__n->_M_nxt) :
nullptr;
714 template<
typename _Key,
typename _Value,
715 typename _Allocator,
typename _ExtractKey,
typename _Equal,
716 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
717 bool __chc,
bool __cit,
bool __uk>
718 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
719 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
720 _Hashtable(size_type __bucket_hint,
721 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
722 const _Equal& __eq,
const _ExtractKey& __exk,
723 const allocator_type& __a)
724 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
725 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
726 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
728 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
729 _M_node_allocator(__a),
734 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
737 _M_rehash_policy._M_prev_resize = 0;
738 _M_buckets = _M_allocate_buckets(_M_bucket_count);
741 template<
typename _Key,
typename _Value,
742 typename _Allocator,
typename _ExtractKey,
typename _Equal,
743 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
744 bool __chc,
bool __cit,
bool __uk>
745 template<
typename _InputIterator>
746 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
747 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
748 _Hashtable(_InputIterator __f, _InputIterator __l,
749 size_type __bucket_hint,
750 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
751 const _Equal& __eq,
const _ExtractKey& __exk,
752 const allocator_type& __a)
753 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
754 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
755 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
757 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
758 _M_node_allocator(__a),
763 _M_bucket_count =
std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
765 _M_bkt_for_elements(__detail::
771 _M_rehash_policy._M_prev_resize = 0;
772 _M_buckets = _M_allocate_buckets(_M_bucket_count);
775 for (; __f != __l; ++__f)
781 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
782 __throw_exception_again;
786 template<
typename _Key,
typename _Value,
787 typename _Allocator,
typename _ExtractKey,
typename _Equal,
788 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
789 bool __chc,
bool __cit,
bool __uk>
790 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
791 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
792 _Hashtable(
const _Hashtable& __ht)
793 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
794 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
795 _H1, _H2, _Hash, __chc>(__ht),
796 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
797 _M_node_allocator(__ht._M_node_allocator),
798 _M_bucket_count(__ht._M_bucket_count),
799 _M_element_count(__ht._M_element_count),
800 _M_rehash_policy(__ht._M_rehash_policy)
802 _M_buckets = _M_allocate_buckets(_M_bucket_count);
805 if (!__ht._M_before_begin._M_nxt)
810 const _Node* __ht_n = __ht._M_begin();
811 _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
812 this->_M_copy_code(__this_n, __ht_n);
813 _M_before_begin._M_nxt = __this_n;
814 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
817 _BaseNode* __prev_n = __this_n;
818 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
820 __this_n = _M_allocate_node(__ht_n->_M_v);
821 __prev_n->_M_nxt = __this_n;
822 this->_M_copy_code(__this_n, __ht_n);
823 size_type __bkt = _M_bucket_index(__this_n);
824 if (!_M_buckets[__bkt])
825 _M_buckets[__bkt] = __prev_n;
832 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
833 __throw_exception_again;
837 template<
typename _Key,
typename _Value,
838 typename _Allocator,
typename _ExtractKey,
typename _Equal,
839 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
840 bool __chc,
bool __cit,
bool __uk>
841 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
842 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
843 _Hashtable(_Hashtable&& __ht)
844 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
845 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
846 _H1, _H2, _Hash, __chc>(__ht),
847 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
848 _M_node_allocator(std::move(__ht._M_node_allocator)),
849 _M_buckets(__ht._M_buckets),
850 _M_bucket_count(__ht._M_bucket_count),
851 _M_before_begin(__ht._M_before_begin._M_nxt),
852 _M_element_count(__ht._M_element_count),
853 _M_rehash_policy(__ht._M_rehash_policy)
857 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
858 __ht._M_rehash_policy = _RehashPolicy();
859 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
860 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
861 __ht._M_before_begin._M_nxt =
nullptr;
862 __ht._M_element_count = 0;
865 template<
typename _Key,
typename _Value,
866 typename _Allocator,
typename _ExtractKey,
typename _Equal,
867 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
868 bool __chc,
bool __cit,
bool __uk>
869 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
870 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
871 ~_Hashtable() noexcept
874 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
877 template<
typename _Key,
typename _Value,
878 typename _Allocator,
typename _ExtractKey,
typename _Equal,
879 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
880 bool __chc,
bool __cit,
bool __uk>
882 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
883 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
884 swap(_Hashtable& __x)
893 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
894 __x._M_node_allocator);
896 std::swap(_M_rehash_policy, __x._M_rehash_policy);
897 std::swap(_M_buckets, __x._M_buckets);
898 std::swap(_M_bucket_count, __x._M_bucket_count);
899 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
900 std::swap(_M_element_count, __x._M_element_count);
904 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
906 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
907 = &(__x._M_before_begin);
910 template<
typename _Key,
typename _Value,
911 typename _Allocator,
typename _ExtractKey,
typename _Equal,
912 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
913 bool __chc,
bool __cit,
bool __uk>
915 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
916 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
917 __rehash_policy(
const _RehashPolicy& __pol)
919 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
920 if (__n_bkt != _M_bucket_count)
921 _M_rehash(__n_bkt, _M_rehash_policy._M_state());
922 _M_rehash_policy = __pol;
925 template<
typename _Key,
typename _Value,
926 typename _Allocator,
typename _ExtractKey,
typename _Equal,
927 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
928 bool __chc,
bool __cit,
bool __uk>
929 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
930 _H1, _H2, _Hash, _RehashPolicy,
931 __chc, __cit, __uk>::iterator
932 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
933 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
934 find(
const key_type& __k)
936 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
937 std::size_t __n = _M_bucket_index(__k, __code);
938 _Node* __p = _M_find_node(__n, __k, __code);
939 return __p ? iterator(__p) : this->
end();
942 template<
typename _Key,
typename _Value,
943 typename _Allocator,
typename _ExtractKey,
typename _Equal,
944 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
945 bool __chc,
bool __cit,
bool __uk>
946 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
947 _H1, _H2, _Hash, _RehashPolicy,
948 __chc, __cit, __uk>::const_iterator
949 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
950 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
951 find(
const key_type& __k)
const
953 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
954 std::size_t __n = _M_bucket_index(__k, __code);
955 _Node* __p = _M_find_node(__n, __k, __code);
956 return __p ? const_iterator(__p) : this->
end();
959 template<
typename _Key,
typename _Value,
960 typename _Allocator,
typename _ExtractKey,
typename _Equal,
961 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
962 bool __chc,
bool __cit,
bool __uk>
963 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
964 _H1, _H2, _Hash, _RehashPolicy,
965 __chc, __cit, __uk>::size_type
966 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
967 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>
::
968 count(
const key_type& __k)
const
970 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
971 std::size_t __n = _M_bucket_index(__k, __code);
972 _Node* __p = _M_bucket_begin(__n);
976 std::size_t __result = 0;
977 for (;; __p = __p->_M_next())
979 if (this->_M_equals(__k, __code, __p))
986 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
992 template<
typename _Key,
typename _Value,
993 typename _Allocator,
typename _ExtractKey,
typename _Equal,
994 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
995 bool __chc,
bool __cit,
bool __uk>
996 std::pair<
typename _Hashtable<_Key, _Value, _Allocator,
997 _ExtractKey, _Equal, _H1,
998 _H2, _Hash, _RehashPolicy,
999 __chc, __cit, __uk>::iterator,
1000 typename _Hashtable<_Key, _Value, _Allocator,
1001 _ExtractKey, _Equal, _H1,
1002 _H2, _Hash, _RehashPolicy,
1003 __chc, __cit, __uk>::iterator>
1004 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1005 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1006 equal_range(
const key_type& __k)
1008 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1009 std::size_t __n = _M_bucket_index(__k, __code);
1010 _Node* __p = _M_find_node(__n, __k, __code);
1014 _Node* __p1 = __p->_M_next();
1015 while (__p1 && _M_bucket_index(__p1) == __n
1016 && this->_M_equals(__k, __code, __p1))
1017 __p1 = __p1->_M_next();
1025 template<
typename _Key,
typename _Value,
1026 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1027 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1028 bool __chc,
bool __cit,
bool __uk>
1029 std::pair<
typename _Hashtable<_Key, _Value, _Allocator,
1030 _ExtractKey, _Equal, _H1,
1031 _H2, _Hash, _RehashPolicy,
1032 __chc, __cit, __uk>::const_iterator,
1033 typename _Hashtable<_Key, _Value, _Allocator,
1034 _ExtractKey, _Equal, _H1,
1035 _H2, _Hash, _RehashPolicy,
1036 __chc, __cit, __uk>::const_iterator>
1037 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1038 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1039 equal_range(
const key_type& __k)
const
1041 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1042 std::size_t __n = _M_bucket_index(__k, __code);
1043 _Node* __p = _M_find_node(__n, __k, __code);
1047 _Node* __p1 = __p->_M_next();
1048 while (__p1 && _M_bucket_index(__p1) == __n
1049 && this->_M_equals(__k, __code, __p1))
1050 __p1 = __p1->_M_next();
1052 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1060 template<
typename _Key,
typename _Value,
1061 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1062 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1063 bool __chc,
bool __cit,
bool __uk>
1064 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1065 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1066 __chc, __cit, __uk>::_BaseNode*
1067 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1068 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1069 _M_find_before_node(size_type __n,
const key_type& __k,
1070 typename _Hashtable::_Hash_code_type __code)
const
1072 _BaseNode* __prev_p = _M_buckets[__n];
1075 _Node* __p =
static_cast<_Node*
>(__prev_p->_M_nxt);
1076 for (;; __p = __p->_M_next())
1078 if (this->_M_equals(__k, __code, __p))
1080 if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1087 template<
typename _Key,
typename _Value,
1088 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1089 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1090 bool __chc,
bool __cit,
bool __uk>
1092 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1093 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1094 _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1096 if (_M_buckets[__bkt])
1100 __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1101 _M_buckets[__bkt]->_M_nxt = __new_node;
1108 __new_node->_M_nxt = _M_before_begin._M_nxt;
1109 _M_before_begin._M_nxt = __new_node;
1110 if (__new_node->_M_nxt)
1113 _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1114 _M_buckets[__bkt] = &_M_before_begin;
1118 template<
typename _Key,
typename _Value,
1119 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1120 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1121 bool __chc,
bool __cit,
bool __uk>
1123 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1124 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1125 _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1127 if (!__next || __next_bkt != __bkt)
1132 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1134 if (&_M_before_begin == _M_buckets[__bkt])
1135 _M_before_begin._M_nxt = __next;
1136 _M_buckets[__bkt] =
nullptr;
1140 template<
typename _Key,
typename _Value,
1141 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1142 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1143 bool __chc,
bool __cit,
bool __uk>
1144 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1145 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1146 __chc, __cit, __uk>::_BaseNode*
1147 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1148 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1149 _M_get_previous_node(size_type __bkt, _BaseNode* __n)
1151 _BaseNode* __prev_n = _M_buckets[__bkt];
1152 while (__prev_n->_M_nxt != __n)
1153 __prev_n = __prev_n->_M_nxt;
1157 template<
typename _Key,
typename _Value,
1158 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1159 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1160 bool __chc,
bool __cit,
bool __uk>
1161 template<
typename... _Args>
1162 std::pair<
typename _Hashtable<_Key, _Value, _Allocator,
1163 _ExtractKey, _Equal, _H1,
1164 _H2, _Hash, _RehashPolicy,
1165 __chc, __cit, __uk>::iterator,
bool>
1166 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1167 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1171 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1174 const key_type& __k = this->_M_extract()(__new_node->_M_v);
1175 typename _Hashtable::_Hash_code_type __code
1176 = this->_M_hash_code(__k);
1177 size_type __bkt = _M_bucket_index(__k, __code);
1179 if (_Node* __p = _M_find_node(__bkt, __k, __code))
1182 _M_deallocate_node(__new_node);
1187 this->_M_store_code(__new_node, __code);
1188 const _RehashPolicyState& __saved_state
1189 = _M_rehash_policy._M_state();
1191 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1192 _M_element_count, 1);
1194 if (__do_rehash.
first)
1196 _M_rehash(__do_rehash.
second, __saved_state);
1197 __bkt = _M_bucket_index(__k, __code);
1200 _M_insert_bucket_begin(__bkt, __new_node);
1206 _M_deallocate_node(__new_node);
1207 __throw_exception_again;
1211 template<
typename _Key,
typename _Value,
1212 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1213 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1214 bool __chc,
bool __cit,
bool __uk>
1215 template<
typename... _Args>
1216 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1217 _H1, _H2, _Hash, _RehashPolicy,
1218 __chc, __cit, __uk>::iterator
1219 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1220 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1223 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1225 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1226 _M_element_count, 1);
1229 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1232 const key_type& __k = this->_M_extract()(__new_node->_M_v);
1233 typename _Hashtable::_Hash_code_type __code
1234 = this->_M_hash_code(__k);
1235 this->_M_store_code(__new_node, __code);
1238 if (__do_rehash.
first)
1239 _M_rehash(__do_rehash.
second, __saved_state);
1242 size_type __bkt = _M_bucket_index(__k, __code);
1243 _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
1248 __new_node->_M_nxt = __prev->_M_nxt;
1249 __prev->_M_nxt = __new_node;
1255 _M_insert_bucket_begin(__bkt, __new_node);
1257 return iterator(__new_node);
1261 _M_deallocate_node(__new_node);
1262 __throw_exception_again;
1267 template<
typename _Key,
typename _Value,
1268 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1269 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1270 bool __chc,
bool __cit,
bool __uk>
1271 template<
typename _Arg>
1272 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1273 _H1, _H2, _Hash, _RehashPolicy,
1274 __chc, __cit, __uk>::iterator
1275 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1276 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1277 _M_insert_bucket(_Arg&& __v, size_type __n,
1278 typename _Hashtable::_Hash_code_type __code)
1280 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1282 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1283 _M_element_count, 1);
1285 if (__do_rehash.
first)
1287 const key_type& __k = this->_M_extract()(__v);
1288 __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.
second);
1291 _Node* __new_node =
nullptr;
1296 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1297 this->_M_store_code(__new_node, __code);
1298 if (__do_rehash.
first)
1299 _M_rehash(__do_rehash.
second, __saved_state);
1301 _M_insert_bucket_begin(__n, __new_node);
1303 return iterator(__new_node);
1308 _M_rehash_policy._M_reset(__saved_state);
1310 _M_deallocate_node(__new_node);
1311 __throw_exception_again;
1316 template<
typename _Key,
typename _Value,
1317 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1318 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1319 bool __chc,
bool __cit,
bool __uk>
1320 template<
typename _Arg>
1321 std::pair<
typename _Hashtable<_Key, _Value, _Allocator,
1322 _ExtractKey, _Equal, _H1,
1323 _H2, _Hash, _RehashPolicy,
1324 __chc, __cit, __uk>::iterator,
bool>
1325 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1326 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1329 const key_type& __k = this->_M_extract()(__v);
1330 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1331 size_type __n = _M_bucket_index(__k, __code);
1333 if (_Node* __p = _M_find_node(__n, __k, __code))
1336 __n, __code),
true);
1340 template<
typename _Key,
typename _Value,
1341 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1342 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1343 bool __chc,
bool __cit,
bool __uk>
1344 template<
typename _Arg>
1345 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1346 _H1, _H2, _Hash, _RehashPolicy,
1347 __chc, __cit, __uk>::iterator
1348 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1349 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1352 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1354 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1355 _M_element_count, 1);
1358 typename _Hashtable::_Hash_code_type __code
1359 = this->_M_hash_code(this->_M_extract()(__v));
1361 _Node* __new_node =
nullptr;
1365 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1366 this->_M_store_code(__new_node, __code);
1367 if (__do_rehash.
first)
1368 _M_rehash(__do_rehash.
second, __saved_state);
1371 size_type __bkt = _M_bucket_index(__new_node);
1373 = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1378 __new_node->_M_nxt = __prev->_M_nxt;
1379 __prev->_M_nxt = __new_node;
1385 _M_insert_bucket_begin(__bkt, __new_node);
1387 return iterator(__new_node);
1392 _M_rehash_policy._M_reset(__saved_state);
1394 _M_deallocate_node(__new_node);
1395 __throw_exception_again;
1399 template<
typename _Key,
typename _Value,
1400 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1401 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1402 bool __chc,
bool __cit,
bool __uk>
1403 template<
typename _InputIterator>
1405 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1406 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1407 insert(_InputIterator __first, _InputIterator __last)
1409 size_type __n_elt = __detail::__distance_fw(__first, __last);
1410 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1412 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1413 _M_element_count, __n_elt);
1414 if (__do_rehash.
first)
1415 _M_rehash(__do_rehash.
second, __saved_state);
1417 for (; __first != __last; ++__first)
1418 this->insert(*__first);
1421 template<
typename _Key,
typename _Value,
1422 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1423 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1424 bool __chc,
bool __cit,
bool __uk>
1425 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1426 _H1, _H2, _Hash, _RehashPolicy,
1427 __chc, __cit, __uk>::iterator
1428 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1429 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1430 erase(const_iterator __it)
1432 _Node* __n = __it._M_cur;
1433 std::size_t __bkt = _M_bucket_index(__n);
1437 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1438 if (__n == _M_bucket_begin(__bkt))
1439 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1440 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1441 else if (__n->_M_nxt)
1443 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1444 if (__next_bkt != __bkt)
1445 _M_buckets[__next_bkt] = __prev_n;
1448 __prev_n->_M_nxt = __n->_M_nxt;
1449 iterator __result(__n->_M_next());
1450 _M_deallocate_node(__n);
1456 template<
typename _Key,
typename _Value,
1457 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1458 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1459 bool __chc,
bool __cit,
bool __uk>
1460 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1461 _H1, _H2, _Hash, _RehashPolicy,
1462 __chc, __cit, __uk>::size_type
1463 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1464 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1465 erase(
const key_type& __k)
1467 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1468 std::size_t __bkt = _M_bucket_index(__k, __code);
1470 _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
1473 _Node* __n =
static_cast<_Node*
>(__prev_n->_M_nxt);
1474 bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1477 std::size_t __next_bkt = __bkt;
1478 _Node* __next_n = __n;
1479 size_type __result = 0;
1480 _Node* __saved_n =
nullptr;
1483 _Node* __p = __next_n;
1484 __next_n = __p->_M_next();
1490 _M_deallocate_node(__p);
1497 __next_bkt = _M_bucket_index(__next_n);
1499 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1502 _M_deallocate_node(__saved_n);
1503 if (__is_bucket_begin)
1504 _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1505 else if (__next_n && __next_bkt != __bkt)
1506 _M_buckets[__next_bkt] = __prev_n;
1508 __prev_n->_M_nxt = __next_n;
1512 template<
typename _Key,
typename _Value,
1513 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1514 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1515 bool __chc,
bool __cit,
bool __uk>
1516 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1517 _H1, _H2, _Hash, _RehashPolicy,
1518 __chc, __cit, __uk>::iterator
1519 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1520 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1521 erase(const_iterator __first, const_iterator __last)
1523 _Node* __n = __first._M_cur;
1524 _Node* __last_n = __last._M_cur;
1525 if (__n == __last_n)
1526 return iterator(__n);
1528 std::size_t __bkt = _M_bucket_index(__n);
1530 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1531 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1532 std::size_t __n_bkt = __bkt;
1538 __n = __n->_M_next();
1539 _M_deallocate_node(__tmp);
1543 __n_bkt = _M_bucket_index(__n);
1545 while (__n != __last_n && __n_bkt == __bkt);
1546 if (__is_bucket_begin)
1547 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1548 if (__n == __last_n)
1550 __is_bucket_begin =
true;
1554 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1555 _M_buckets[__n_bkt] = __prev_n;
1556 __prev_n->_M_nxt = __n;
1557 return iterator(__n);
1560 template<
typename _Key,
typename _Value,
1561 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1562 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1563 bool __chc,
bool __cit,
bool __uk>
1565 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1566 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1569 _M_deallocate_nodes(_M_begin());
1570 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(_Bucket));
1571 _M_element_count = 0;
1572 _M_before_begin._M_nxt =
nullptr;
1575 template<
typename _Key,
typename _Value,
1576 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1577 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1578 bool __chc,
bool __cit,
bool __uk>
1580 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1581 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1582 rehash(size_type __n)
1584 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1585 _M_rehash(
std::max(_M_rehash_policy._M_next_bkt(__n),
1586 _M_rehash_policy._M_bkt_for_elements(_M_element_count
1591 template<
typename _Key,
typename _Value,
1592 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1593 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1594 bool __chc,
bool __cit,
bool __uk>
1596 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1597 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1598 _M_rehash(size_type __n,
const _RehashPolicyState& __state)
1602 _M_rehash_aux(__n, integral_constant<bool, __uk>());
1608 _M_rehash_policy._M_reset(__state);
1609 __throw_exception_again;
1614 template<
typename _Key,
typename _Value,
1615 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1616 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1617 bool __chc,
bool __cit,
bool __uk>
1619 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1620 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1623 _Bucket* __new_buckets = _M_allocate_buckets(__n);
1624 _Node* __p = _M_begin();
1625 _M_before_begin._M_nxt =
nullptr;
1626 std::size_t __bbegin_bkt;
1629 _Node* __next = __p->_M_next();
1630 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1631 if (!__new_buckets[__bkt])
1633 __p->_M_nxt = _M_before_begin._M_nxt;
1634 _M_before_begin._M_nxt = __p;
1635 __new_buckets[__bkt] = &_M_before_begin;
1637 __new_buckets[__bbegin_bkt] = __p;
1638 __bbegin_bkt = __bkt;
1642 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1643 __new_buckets[__bkt]->_M_nxt = __p;
1647 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1648 _M_bucket_count = __n;
1649 _M_buckets = __new_buckets;
1654 template<
typename _Key,
typename _Value,
1655 typename _Allocator,
typename _ExtractKey,
typename _Equal,
1656 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1657 bool __chc,
bool __cit,
bool __uk>
1659 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1660 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1663 _Bucket* __new_buckets = _M_allocate_buckets(__n);
1665 _Node* __p = _M_begin();
1666 _M_before_begin._M_nxt =
nullptr;
1667 std::size_t __bbegin_bkt;
1668 std::size_t __prev_bkt;
1669 _Node* __prev_p =
nullptr;
1670 bool __check_bucket =
false;
1674 _Node* __next = __p->_M_next();
1675 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1677 if (__prev_p && __prev_bkt == __bkt)
1682 __p->_M_nxt = __prev_p->_M_nxt;
1683 __prev_p->_M_nxt = __p;
1690 __check_bucket =
true;
1698 if (__prev_p->_M_nxt)
1700 std::size_t __next_bkt
1701 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1702 if (__next_bkt != __prev_bkt)
1703 __new_buckets[__next_bkt] = __prev_p;
1705 __check_bucket =
false;
1707 if (!__new_buckets[__bkt])
1709 __p->_M_nxt = _M_before_begin._M_nxt;
1710 _M_before_begin._M_nxt = __p;
1711 __new_buckets[__bkt] = &_M_before_begin;
1713 __new_buckets[__bbegin_bkt] = __p;
1714 __bbegin_bkt = __bkt;
1718 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1719 __new_buckets[__bkt]->_M_nxt = __p;
1728 if (__check_bucket && __prev_p->_M_nxt)
1730 std::size_t __next_bkt
1731 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1732 if (__next_bkt != __prev_bkt)
1733 __new_buckets[__next_bkt] = __prev_p;
1736 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1737 _M_bucket_count = __n;
1738 _M_buckets = __new_buckets;
1741 _GLIBCXX_END_NAMESPACE_VERSION
1744 #endif // _HASHTABLE_H