1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2024 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/hashtable.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
35 #include <bits/hashtable_policy.h>
36 #include <bits/enable_special_members.h>
37 #include <bits/stl_algobase.h> // fill_n
38 #include <bits/stl_function.h> // __has_is_transparent_t
39 #if __cplusplus > 201402L
40 # include <bits/node_handle.h>
43 namespace std
_GLIBCXX_VISIBILITY(default)
45 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46 /// @cond undocumented
48 template<typename _Tp
, typename _Hash
>
50 = __not_
<__and_
<// Do not cache for fast hasher.
51 __is_fast_hash
<_Hash
>,
52 // Mandatory to have erase not throwing.
53 __is_nothrow_invocable
<const _Hash
&, const _Tp
&>>>;
55 // Helper to conditionally delete the default constructor.
56 // The _Hash_node_base type is used to distinguish this specialization
57 // from any other potentially-overlapping subobjects of the hashtable.
58 template<typename _Equal
, typename _Hash
, typename _Allocator
>
59 using _Hashtable_enable_default_ctor
60 = _Enable_default_constructor
<__and_
<is_default_constructible
<_Equal
>,
61 is_default_constructible
<_Hash
>,
62 is_default_constructible
<_Allocator
>>{},
63 __detail::_Hash_node_base
>;
66 * Primary class template _Hashtable.
68 * @ingroup hashtable-detail
70 * @tparam _Value CopyConstructible type.
72 * @tparam _Key CopyConstructible type.
74 * @tparam _Alloc An allocator type
75 * ([lib.allocator.requirements]) whose _Alloc::value_type is
76 * _Value. As a conforming extension, we allow for
77 * _Alloc::value_type != _Value.
79 * @tparam _ExtractKey Function object that takes an object of type
80 * _Value and returns a value of type _Key.
82 * @tparam _Equal Function object that takes two objects of type k
83 * and returns a bool-like value that is true if the two objects
84 * are considered equal.
86 * @tparam _Hash The hash function. A unary function object with
87 * argument type _Key and result type size_t. Return values should
88 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
90 * @tparam _RangeHash The range-hashing function (in the terminology of
91 * Tavori and Dreizin). A binary function object whose argument
92 * types and result type are all size_t. Given arguments r and N,
93 * the return value is in the range [0, N).
95 * @tparam _Unused Not used.
97 * @tparam _RehashPolicy Policy class with three members, all of
98 * which govern the bucket count. _M_next_bkt(n) returns a bucket
99 * count no smaller than n. _M_bkt_for_elements(n) returns a
100 * bucket count appropriate for an element count of n.
101 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
102 * current bucket count is n_bkt and the current element count is
103 * n_elt, we need to increase the bucket count for n_ins insertions.
104 * If so, returns make_pair(true, n), where n is the new bucket count. If
105 * not, returns make_pair(false, <anything>)
107 * @tparam _Traits Compile-time class with three boolean
108 * std::integral_constant members: __cache_hash_code, __constant_iterators,
111 * Each _Hashtable data structure has:
113 * - _Bucket[] _M_buckets
114 * - _Hash_node_base _M_before_begin
115 * - size_type _M_bucket_count
116 * - size_type _M_element_count
118 * with _Bucket being _Hash_node_base* and _Hash_node containing:
120 * - _Hash_node* _M_next
122 * - size_t _M_hash_code if cache_hash_code is true
124 * In terms of Standard containers the hashtable is like the aggregation of:
126 * - std::forward_list<_Node> containing the elements
127 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
129 * The non-empty buckets contain the node before the first node in the
130 * bucket. This design makes it possible to implement something like a
131 * std::forward_list::insert_after on container insertion and
132 * std::forward_list::erase_after on container erase
133 * calls. _M_before_begin is equivalent to
134 * std::forward_list::before_begin. Empty buckets contain
135 * nullptr. Note that one of the non-empty buckets contains
136 * &_M_before_begin which is not a dereferenceable node so the
137 * node pointer in a bucket shall never be dereferenced, only its
140 * Walking through a bucket's nodes requires a check on the hash code to
141 * see if each node is still in the bucket. Such a design assumes a
142 * quite efficient hash functor and is one of the reasons it is
143 * highly advisable to set __cache_hash_code to true.
145 * The container iterators are simply built from nodes. This way
146 * incrementing the iterator is perfectly efficient independent of
147 * how many empty buckets there are in the container.
149 * On insert we compute the element's hash code and use it to find the
150 * bucket index. If the element must be inserted in an empty bucket
151 * we add it at the beginning of the singly linked list and make the
152 * bucket point to _M_before_begin. The bucket that used to point to
153 * _M_before_begin, if any, is updated to point to its new before
156 * Note that all equivalent values, if any, are next to each other, if
157 * we find a non-equivalent value after an equivalent one it means that
158 * we won't find any new equivalent value.
160 * On erase, the simple iterator design requires using the hash
161 * functor to get the index of the bucket to update. For this
162 * reason, when __cache_hash_code is set to false the hash functor must
163 * not throw and this is enforced by a static assertion.
165 * Functionality is implemented by decomposition into base classes,
166 * where the derived _Hashtable class is used in _Map_base,
167 * _Insert, _Rehash_base, and _Equality base classes to access the
168 * "this" pointer. _Hashtable_base is used in the base classes as a
169 * non-recursive, fully-completed-type so that detailed nested type
170 * information, such as iterator type and node type, can be
171 * used. This is similar to the "Curiously Recurring Template
172 * Pattern" (CRTP) technique, but uses a reconstructed, not
173 * explicitly passed, template pattern.
175 * Base class templates are:
176 * - __detail::_Hashtable_base
177 * - __detail::_Map_base
178 * - __detail::_Insert
179 * - __detail::_Rehash_base
180 * - __detail::_Equality
182 template<typename _Key
, typename _Value
, typename _Alloc
,
183 typename _ExtractKey
, typename _Equal
,
184 typename _Hash
, typename _RangeHash
, typename _Unused
,
185 typename _RehashPolicy
, typename _Traits
>
187 : public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
188 _Hash
, _RangeHash
, _Unused
, _Traits
>,
189 public __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
190 _Hash
, _RangeHash
, _Unused
,
191 _RehashPolicy
, _Traits
>,
192 public __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
193 _Hash
, _RangeHash
, _Unused
,
194 _RehashPolicy
, _Traits
>,
195 public __detail::_Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
196 _Hash
, _RangeHash
, _Unused
,
197 _RehashPolicy
, _Traits
>,
198 public __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
199 _Hash
, _RangeHash
, _Unused
,
200 _RehashPolicy
, _Traits
>,
201 private __detail::_Hashtable_alloc
<
202 __alloc_rebind
<_Alloc
,
203 __detail::_Hash_node
<_Value
,
204 _Traits::__hash_cached::value
>>>,
205 private _Hashtable_enable_default_ctor
<_Equal
, _Hash
, _Alloc
>
207 static_assert(is_same
<typename remove_cv
<_Value
>::type
, _Value
>::value
,
208 "unordered container must have a non-const, non-volatile value_type");
209 #if __cplusplus > 201703L || defined __STRICT_ANSI__
210 static_assert(is_same
<typename
_Alloc::value_type
, _Value
>{},
211 "unordered container must have the same value_type as its allocator");
213 static_assert(is_copy_constructible
<_Hash
>::value
,
214 "hash function must be copy constructible");
216 using __traits_type
= _Traits
;
217 using __hash_cached
= typename
__traits_type::__hash_cached
;
218 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
219 using __node_type
= __detail::_Hash_node
<_Value
, __hash_cached::value
>;
220 using __node_alloc_type
= __alloc_rebind
<_Alloc
, __node_type
>;
222 using __hashtable_alloc
= __detail::_Hashtable_alloc
<__node_alloc_type
>;
224 using __node_value_type
=
225 __detail::_Hash_node_value
<_Value
, __hash_cached::value
>;
226 using __node_ptr
= typename
__hashtable_alloc::__node_ptr
;
227 using __value_alloc_traits
=
228 typename
__hashtable_alloc::__value_alloc_traits
;
229 using __node_alloc_traits
=
230 typename
__hashtable_alloc::__node_alloc_traits
;
231 using __node_base
= typename
__hashtable_alloc::__node_base
;
232 using __node_base_ptr
= typename
__hashtable_alloc::__node_base_ptr
;
233 using __buckets_ptr
= typename
__hashtable_alloc::__buckets_ptr
;
235 using __insert_base
= __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
,
238 _RehashPolicy
, _Traits
>;
239 using __enable_default_ctor
240 = _Hashtable_enable_default_ctor
<_Equal
, _Hash
, _Alloc
>;
241 using __rehash_guard_t
242 = __detail::_RehashStateGuard
<_RehashPolicy
>;
245 typedef _Key key_type
;
246 typedef _Value value_type
;
247 typedef _Alloc allocator_type
;
248 typedef _Equal key_equal
;
250 // mapped_type, if present, comes from _Map_base.
251 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
252 typedef typename
__value_alloc_traits::pointer pointer
;
253 typedef typename
__value_alloc_traits::const_pointer const_pointer
;
254 typedef value_type
& reference
;
255 typedef const value_type
& const_reference
;
257 using iterator
= typename
__insert_base::iterator
;
259 using const_iterator
= typename
__insert_base::const_iterator
;
261 using local_iterator
= __detail::_Local_iterator
<key_type
, _Value
,
262 _ExtractKey
, _Hash
, _RangeHash
, _Unused
,
263 __constant_iterators::value
,
264 __hash_cached::value
>;
266 using const_local_iterator
= __detail::_Local_const_iterator
<
268 _ExtractKey
, _Hash
, _RangeHash
, _Unused
,
269 __constant_iterators::value
, __hash_cached::value
>;
272 using __rehash_type
= _RehashPolicy
;
274 using __unique_keys
= typename
__traits_type::__unique_keys
;
276 using __hashtable_base
= __detail::
277 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
278 _Equal
, _Hash
, _RangeHash
, _Unused
, _Traits
>;
280 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
281 using __hash_code
= typename
__hashtable_base::__hash_code
;
282 using __ireturn_type
= typename
__insert_base::__ireturn_type
;
284 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
285 _Equal
, _Hash
, _RangeHash
, _Unused
,
286 _RehashPolicy
, _Traits
>;
288 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
290 _Hash
, _RangeHash
, _Unused
,
291 _RehashPolicy
, _Traits
>;
293 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
294 _Equal
, _Hash
, _RangeHash
, _Unused
,
295 _RehashPolicy
, _Traits
>;
297 using __reuse_or_alloc_node_gen_t
=
298 __detail::_ReuseOrAllocNode
<__node_alloc_type
>;
299 using __alloc_node_gen_t
=
300 __detail::_AllocNode
<__node_alloc_type
>;
301 using __node_builder_t
=
302 __detail::_NodeBuilder
<_ExtractKey
>;
304 // Simple RAII type for managing a node containing an element
307 // Take ownership of a node with a constructed element.
308 _Scoped_node(__node_ptr __n
, __hashtable_alloc
* __h
)
309 : _M_h(__h
), _M_node(__n
) { }
311 // Allocate a node and construct an element within it.
312 template<typename
... _Args
>
313 _Scoped_node(__hashtable_alloc
* __h
, _Args
&&... __args
)
315 _M_node(__h
->_M_allocate_node(std::forward
<_Args
>(__args
)...))
318 // Destroy element and deallocate node.
319 ~_Scoped_node() { if (_M_node
) _M_h
->_M_deallocate_node(_M_node
); };
321 _Scoped_node(const _Scoped_node
&) = delete;
322 _Scoped_node
& operator=(const _Scoped_node
&) = delete;
324 __hashtable_alloc
* _M_h
;
328 template<typename _Ht
>
330 __conditional_t
<std::is_lvalue_reference
<_Ht
>::value
,
331 const value_type
&, value_type
&&>
332 __fwd_value_for(value_type
& __val
) noexcept
333 { return std::move(__val
); }
335 // Compile-time diagnostics.
337 // _Hash_code_base has everything protected, so use this derived type to
339 struct __hash_code_base_access
: __hash_code_base
340 { using __hash_code_base::_M_bucket_index
; };
342 // To get bucket index we need _RangeHash not to throw.
343 static_assert(is_nothrow_default_constructible
<_RangeHash
>::value
,
344 "Functor used to map hash code to bucket index"
345 " must be nothrow default constructible");
346 static_assert(noexcept(
347 std::declval
<const _RangeHash
&>()((std::size_t)0, (std::size_t)0)),
348 "Functor used to map hash code to bucket index must be"
351 // To compute bucket index we also need _ExtratKey not to throw.
352 static_assert(is_nothrow_default_constructible
<_ExtractKey
>::value
,
353 "_ExtractKey must be nothrow default constructible");
354 static_assert(noexcept(
355 std::declval
<const _ExtractKey
&>()(std::declval
<_Value
>())),
356 "_ExtractKey functor must be noexcept invocable");
358 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
359 typename _ExtractKeya
, typename _Equala
,
360 typename _Hasha
, typename _RangeHasha
, typename _Unuseda
,
361 typename _RehashPolicya
, typename _Traitsa
,
363 friend struct __detail::_Map_base
;
365 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
366 typename _ExtractKeya
, typename _Equala
,
367 typename _Hasha
, typename _RangeHasha
, typename _Unuseda
,
368 typename _RehashPolicya
, typename _Traitsa
>
369 friend struct __detail::_Insert_base
;
371 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
372 typename _ExtractKeya
, typename _Equala
,
373 typename _Hasha
, typename _RangeHasha
, typename _Unuseda
,
374 typename _RehashPolicya
, typename _Traitsa
,
375 bool _Constant_iteratorsa
>
376 friend struct __detail::_Insert
;
378 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
379 typename _ExtractKeya
, typename _Equala
,
380 typename _Hasha
, typename _RangeHasha
, typename _Unuseda
,
381 typename _RehashPolicya
, typename _Traitsa
,
383 friend struct __detail::_Equality
;
386 using size_type
= typename
__hashtable_base::size_type
;
387 using difference_type
= typename
__hashtable_base::difference_type
;
389 #if __cplusplus > 201402L
390 using node_type
= _Node_handle
<_Key
, _Value
, __node_alloc_type
>;
391 using insert_return_type
= _Node_insert_return
<iterator
, node_type
>;
395 __buckets_ptr _M_buckets
= &_M_single_bucket
;
396 size_type _M_bucket_count
= 1;
397 __node_base _M_before_begin
;
398 size_type _M_element_count
= 0;
399 _RehashPolicy _M_rehash_policy
;
401 // A single bucket used when only need for 1 bucket. Especially
402 // interesting in move semantic to leave hashtable with only 1 bucket
403 // which is not allocated so that we can have those operations noexcept
405 // Note that we can't leave hashtable with 0 bucket without adding
406 // numerous checks in the code to avoid 0 modulus.
407 __node_base_ptr _M_single_bucket
= nullptr;
412 if (auto __begin
= _M_begin())
413 _M_buckets
[_M_bucket_index(*__begin
)] = &_M_before_begin
;
417 _M_update_bbegin(__node_ptr __n
)
419 _M_before_begin
._M_nxt
= __n
;
424 _M_uses_single_bucket(__buckets_ptr __bkts
) const
425 { return __builtin_expect(__bkts
== &_M_single_bucket
, false); }
428 _M_uses_single_bucket() const
429 { return _M_uses_single_bucket(_M_buckets
); }
431 static constexpr size_t
432 __small_size_threshold() noexcept
435 __detail::_Hashtable_hash_traits
<_Hash
>::__small_size_threshold();
439 _M_base_alloc() { return *this; }
442 _M_allocate_buckets(size_type __bkt_count
)
444 if (__builtin_expect(__bkt_count
== 1, false))
446 _M_single_bucket
= nullptr;
447 return &_M_single_bucket
;
450 return __hashtable_alloc::_M_allocate_buckets(__bkt_count
);
454 _M_deallocate_buckets(__buckets_ptr __bkts
, size_type __bkt_count
)
456 if (_M_uses_single_bucket(__bkts
))
459 __hashtable_alloc::_M_deallocate_buckets(__bkts
, __bkt_count
);
463 _M_deallocate_buckets()
464 { _M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
466 // Gets bucket begin, deals with the fact that non-empty buckets contain
467 // their before begin node.
469 _M_bucket_begin(size_type __bkt
) const
471 __node_base_ptr __n
= _M_buckets
[__bkt
];
472 return __n
? static_cast<__node_ptr
>(__n
->_M_nxt
) : nullptr;
477 { return static_cast<__node_ptr
>(_M_before_begin
._M_nxt
); }
479 // Assign *this using another _Hashtable instance. Whether elements
480 // are copied or moved depends on the _Ht reference.
481 template<typename _Ht
>
483 _M_assign_elements(_Ht
&&);
485 template<typename _Ht
, typename _NodeGenerator
>
487 _M_assign(_Ht
&&, const _NodeGenerator
&);
490 _M_move_assign(_Hashtable
&&, true_type
);
493 _M_move_assign(_Hashtable
&&, false_type
);
498 _Hashtable(const _Hash
& __h
, const _Equal
& __eq
,
499 const allocator_type
& __a
)
500 : __hashtable_base(__h
, __eq
),
501 __hashtable_alloc(__node_alloc_type(__a
)),
502 __enable_default_ctor(_Enable_default_constructor_tag
{})
505 template<bool _No_realloc
= true>
506 static constexpr bool
509 #if __cplusplus <= 201402L
510 return __and_
<__bool_constant
<_No_realloc
>,
511 is_nothrow_copy_constructible
<_Hash
>,
512 is_nothrow_copy_constructible
<_Equal
>>::value
;
514 if constexpr (_No_realloc
)
515 if constexpr (is_nothrow_copy_constructible
<_Hash
>())
516 return is_nothrow_copy_constructible
<_Equal
>();
521 _Hashtable(_Hashtable
&& __ht
, __node_alloc_type
&& __a
,
522 true_type
/* alloc always equal */)
523 noexcept(_S_nothrow_move());
525 _Hashtable(_Hashtable
&&, __node_alloc_type
&&,
526 false_type
/* alloc always equal */);
528 template<typename _InputIterator
>
529 _Hashtable(_InputIterator __first
, _InputIterator __last
,
530 size_type __bkt_count_hint
,
531 const _Hash
&, const _Equal
&, const allocator_type
&,
534 template<typename _InputIterator
>
535 _Hashtable(_InputIterator __first
, _InputIterator __last
,
536 size_type __bkt_count_hint
,
537 const _Hash
&, const _Equal
&, const allocator_type
&,
541 // Constructor, destructor, assignment, swap
542 _Hashtable() = default;
544 _Hashtable(const _Hashtable
&);
546 _Hashtable(const _Hashtable
&, const allocator_type
&);
549 _Hashtable(size_type __bkt_count_hint
,
550 const _Hash
& __hf
= _Hash(),
551 const key_equal
& __eql
= key_equal(),
552 const allocator_type
& __a
= allocator_type());
554 // Use delegating constructors.
555 _Hashtable(_Hashtable
&& __ht
)
556 noexcept(_S_nothrow_move())
557 : _Hashtable(std::move(__ht
), std::move(__ht
._M_node_allocator()),
561 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
562 noexcept(_S_nothrow_move
<__node_alloc_traits::_S_always_equal()>())
563 : _Hashtable(std::move(__ht
), __node_alloc_type(__a
),
564 typename
__node_alloc_traits::is_always_equal
{})
568 _Hashtable(const allocator_type
& __a
)
569 : __hashtable_alloc(__node_alloc_type(__a
)),
570 __enable_default_ctor(_Enable_default_constructor_tag
{})
573 template<typename _InputIterator
>
574 _Hashtable(_InputIterator __f
, _InputIterator __l
,
575 size_type __bkt_count_hint
= 0,
576 const _Hash
& __hf
= _Hash(),
577 const key_equal
& __eql
= key_equal(),
578 const allocator_type
& __a
= allocator_type())
579 : _Hashtable(__f
, __l
, __bkt_count_hint
, __hf
, __eql
, __a
,
583 _Hashtable(initializer_list
<value_type
> __l
,
584 size_type __bkt_count_hint
= 0,
585 const _Hash
& __hf
= _Hash(),
586 const key_equal
& __eql
= key_equal(),
587 const allocator_type
& __a
= allocator_type())
588 : _Hashtable(__l
.begin(), __l
.end(), __bkt_count_hint
,
589 __hf
, __eql
, __a
, __unique_keys
{})
593 operator=(const _Hashtable
& __ht
);
596 operator=(_Hashtable
&& __ht
)
597 noexcept(__node_alloc_traits::_S_nothrow_move()
598 && is_nothrow_move_assignable
<_Hash
>::value
599 && is_nothrow_move_assignable
<_Equal
>::value
)
601 constexpr bool __move_storage
=
602 __node_alloc_traits::_S_propagate_on_move_assign()
603 || __node_alloc_traits::_S_always_equal();
604 _M_move_assign(std::move(__ht
), __bool_constant
<__move_storage
>());
609 operator=(initializer_list
<value_type
> __l
)
611 __reuse_or_alloc_node_gen_t
__roan(_M_begin(), *this);
612 _M_before_begin
._M_nxt
= nullptr;
615 // We consider that all elements of __l are going to be inserted.
616 auto __l_bkt_count
= _M_rehash_policy
._M_bkt_for_elements(__l
.size());
618 // Do not shrink to keep potential user reservation.
619 if (_M_bucket_count
< __l_bkt_count
)
620 rehash(__l_bkt_count
);
622 this->_M_insert_range(__l
.begin(), __l
.end(), __roan
, __unique_keys
{});
626 ~_Hashtable() noexcept
;
630 noexcept(__and_
<__is_nothrow_swappable
<_Hash
>,
631 __is_nothrow_swappable
<_Equal
>>::value
);
633 // Basic container operations
636 { return iterator(_M_begin()); }
639 begin() const noexcept
640 { return const_iterator(_M_begin()); }
644 { return iterator(nullptr); }
648 { return const_iterator(nullptr); }
651 cbegin() const noexcept
652 { return const_iterator(_M_begin()); }
655 cend() const noexcept
656 { return const_iterator(nullptr); }
659 size() const noexcept
660 { return _M_element_count
; }
662 _GLIBCXX_NODISCARD
bool
663 empty() const noexcept
664 { return size() == 0; }
667 get_allocator() const noexcept
668 { return allocator_type(this->_M_node_allocator()); }
671 max_size() const noexcept
672 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
677 { return this->_M_eq(); }
679 // hash_function, if present, comes from _Hash_code_base.
683 bucket_count() const noexcept
684 { return _M_bucket_count
; }
687 max_bucket_count() const noexcept
688 { return max_size(); }
691 bucket_size(size_type __bkt
) const
692 { return std::distance(begin(__bkt
), end(__bkt
)); }
695 bucket(const key_type
& __k
) const
696 { return _M_bucket_index(this->_M_hash_code(__k
)); }
699 begin(size_type __bkt
)
701 return local_iterator(*this, _M_bucket_begin(__bkt
),
702 __bkt
, _M_bucket_count
);
707 { return local_iterator(*this, nullptr, __bkt
, _M_bucket_count
); }
710 begin(size_type __bkt
) const
712 return const_local_iterator(*this, _M_bucket_begin(__bkt
),
713 __bkt
, _M_bucket_count
);
717 end(size_type __bkt
) const
718 { return const_local_iterator(*this, nullptr, __bkt
, _M_bucket_count
); }
722 cbegin(size_type __bkt
) const
724 return const_local_iterator(*this, _M_bucket_begin(__bkt
),
725 __bkt
, _M_bucket_count
);
729 cend(size_type __bkt
) const
730 { return const_local_iterator(*this, nullptr, __bkt
, _M_bucket_count
); }
733 load_factor() const noexcept
735 return static_cast<float>(size()) / static_cast<float>(bucket_count());
738 // max_load_factor, if present, comes from _Rehash_base.
740 // Generalization of max_load_factor. Extension, not found in
741 // TR1. Only useful if _RehashPolicy is something other than
744 __rehash_policy() const
745 { return _M_rehash_policy
; }
748 __rehash_policy(const _RehashPolicy
& __pol
)
749 { _M_rehash_policy
= __pol
; }
753 find(const key_type
& __k
);
756 find(const key_type
& __k
) const;
759 count(const key_type
& __k
) const;
761 std::pair
<iterator
, iterator
>
762 equal_range(const key_type
& __k
);
764 std::pair
<const_iterator
, const_iterator
>
765 equal_range(const key_type
& __k
) const;
767 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
768 template<typename _Kt
,
769 typename
= __has_is_transparent_t
<_Hash
, _Kt
>,
770 typename
= __has_is_transparent_t
<_Equal
, _Kt
>>
772 _M_find_tr(const _Kt
& __k
);
774 template<typename _Kt
,
775 typename
= __has_is_transparent_t
<_Hash
, _Kt
>,
776 typename
= __has_is_transparent_t
<_Equal
, _Kt
>>
778 _M_find_tr(const _Kt
& __k
) const;
780 template<typename _Kt
,
781 typename
= __has_is_transparent_t
<_Hash
, _Kt
>,
782 typename
= __has_is_transparent_t
<_Equal
, _Kt
>>
784 _M_count_tr(const _Kt
& __k
) const;
786 template<typename _Kt
,
787 typename
= __has_is_transparent_t
<_Hash
, _Kt
>,
788 typename
= __has_is_transparent_t
<_Equal
, _Kt
>>
789 pair
<iterator
, iterator
>
790 _M_equal_range_tr(const _Kt
& __k
);
792 template<typename _Kt
,
793 typename
= __has_is_transparent_t
<_Hash
, _Kt
>,
794 typename
= __has_is_transparent_t
<_Equal
, _Kt
>>
795 pair
<const_iterator
, const_iterator
>
796 _M_equal_range_tr(const _Kt
& __k
) const;
797 #endif // __glibcxx_generic_unordered_lookup
800 // Bucket index computation helpers.
802 _M_bucket_index(const __node_value_type
& __n
) const noexcept
803 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
806 _M_bucket_index(__hash_code __c
) const
807 { return __hash_code_base::_M_bucket_index(__c
, _M_bucket_count
); }
810 _M_find_before_node(const key_type
&);
812 // Find and insert helper functions and types
813 // Find the node before the one matching the criteria.
815 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
817 template<typename _Kt
>
819 _M_find_before_node_tr(size_type
, const _Kt
&, __hash_code
) const;
822 _M_find_node(size_type __bkt
, const key_type
& __key
,
823 __hash_code __c
) const
825 __node_base_ptr __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
827 return static_cast<__node_ptr
>(__before_n
->_M_nxt
);
831 template<typename _Kt
>
833 _M_find_node_tr(size_type __bkt
, const _Kt
& __key
,
834 __hash_code __c
) const
836 auto __before_n
= _M_find_before_node_tr(__bkt
, __key
, __c
);
838 return static_cast<__node_ptr
>(__before_n
->_M_nxt
);
842 // Insert a node at the beginning of a bucket.
844 _M_insert_bucket_begin(size_type __bkt
, __node_ptr __node
)
846 if (_M_buckets
[__bkt
])
848 // Bucket is not empty, we just need to insert the new node
849 // after the bucket before begin.
850 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
851 _M_buckets
[__bkt
]->_M_nxt
= __node
;
855 // The bucket is empty, the new node is inserted at the
856 // beginning of the singly-linked list and the bucket will
857 // contain _M_before_begin pointer.
858 __node
->_M_nxt
= _M_before_begin
._M_nxt
;
859 _M_before_begin
._M_nxt
= __node
;
862 // We must update former begin bucket that is pointing to
864 _M_buckets
[_M_bucket_index(*__node
->_M_next())] = __node
;
866 _M_buckets
[__bkt
] = &_M_before_begin
;
870 // Remove the bucket first node
872 _M_remove_bucket_begin(size_type __bkt
, __node_ptr __next_n
,
873 size_type __next_bkt
)
876 _M_buckets
[__bkt
] = nullptr;
877 else if (__next_bkt
!= __bkt
)
879 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
880 _M_buckets
[__bkt
] = nullptr;
884 // Get the node before __n in the bucket __bkt
886 _M_get_previous_node(size_type __bkt
, __node_ptr __n
);
888 pair
<__node_ptr
, __hash_code
>
889 _M_compute_hash_code(__node_ptr __hint
, const key_type
& __k
) const;
891 // Insert node __n with hash code __code, in bucket __bkt if no
892 // rehash (assumes no element with same key already present).
893 // Takes ownership of __n if insertion succeeds, throws otherwise.
895 _M_insert_unique_node(size_type __bkt
, __hash_code
,
896 __node_ptr __n
, size_type __n_elt
= 1);
898 // Insert node __n with key __k and hash code __code.
899 // Takes ownership of __n if insertion succeeds, throws otherwise.
901 _M_insert_multi_node(__node_ptr __hint
,
902 __hash_code __code
, __node_ptr __n
);
904 template<typename
... _Args
>
905 std::pair
<iterator
, bool>
906 _M_emplace(true_type __uks
, _Args
&&... __args
);
908 template<typename
... _Args
>
910 _M_emplace(false_type __uks
, _Args
&&... __args
)
911 { return _M_emplace(cend(), __uks
, std::forward
<_Args
>(__args
)...); }
913 // Emplace with hint, useless when keys are unique.
914 template<typename
... _Args
>
916 _M_emplace(const_iterator
, true_type __uks
, _Args
&&... __args
)
917 { return _M_emplace(__uks
, std::forward
<_Args
>(__args
)...).first
; }
919 template<typename
... _Args
>
921 _M_emplace(const_iterator
, false_type __uks
, _Args
&&... __args
);
923 template<typename _Kt
, typename _Arg
, typename _NodeGenerator
>
924 std::pair
<iterator
, bool>
925 _M_insert_unique(_Kt
&&, _Arg
&&, const _NodeGenerator
&);
927 template<typename _Kt
>
928 static __conditional_t
<
929 __and_
<__is_nothrow_invocable
<_Hash
&, const key_type
&>,
930 __not_
<__is_nothrow_invocable
<_Hash
&, _Kt
>>>::value
,
932 _S_forward_key(_Kt
&& __k
)
933 { return std::forward
<_Kt
>(__k
); }
935 static const key_type
&
936 _S_forward_key(const key_type
& __k
)
940 _S_forward_key(key_type
&& __k
)
941 { return std::move(__k
); }
943 template<typename _Arg
, typename _NodeGenerator
>
944 std::pair
<iterator
, bool>
945 _M_insert_unique_aux(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
)
947 return _M_insert_unique(
948 _S_forward_key(_ExtractKey
{}(std::forward
<_Arg
>(__arg
))),
949 std::forward
<_Arg
>(__arg
), __node_gen
);
952 template<typename _Arg
, typename _NodeGenerator
>
953 std::pair
<iterator
, bool>
954 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
955 true_type
/* __uks */)
958 = __detail::_ConvertToValueType
<_ExtractKey
, value_type
>;
959 return _M_insert_unique_aux(
960 __to_value
{}(std::forward
<_Arg
>(__arg
)), __node_gen
);
963 template<typename _Arg
, typename _NodeGenerator
>
965 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
969 = __detail::_ConvertToValueType
<_ExtractKey
, value_type
>;
970 return _M_insert(cend(),
971 __to_value
{}(std::forward
<_Arg
>(__arg
)), __node_gen
, __uks
);
974 // Insert with hint, not used when keys are unique.
975 template<typename _Arg
, typename _NodeGenerator
>
977 _M_insert(const_iterator
, _Arg
&& __arg
,
978 const _NodeGenerator
& __node_gen
, true_type __uks
)
981 _M_insert(std::forward
<_Arg
>(__arg
), __node_gen
, __uks
).first
;
984 // Insert with hint when keys are not unique.
985 template<typename _Arg
, typename _NodeGenerator
>
987 _M_insert(const_iterator
, _Arg
&&,
988 const _NodeGenerator
&, false_type __uks
);
991 _M_erase(true_type __uks
, const key_type
&);
994 _M_erase(false_type __uks
, const key_type
&);
997 _M_erase(size_type __bkt
, __node_base_ptr __prev_n
, __node_ptr __n
);
1001 template<typename
... _Args
>
1003 emplace(_Args
&&... __args
)
1004 { return _M_emplace(__unique_keys
{}, std::forward
<_Args
>(__args
)...); }
1006 template<typename
... _Args
>
1008 emplace_hint(const_iterator __hint
, _Args
&&... __args
)
1010 return _M_emplace(__hint
, __unique_keys
{},
1011 std::forward
<_Args
>(__args
)...);
1014 // Insert member functions via inheritance.
1018 erase(const_iterator
);
1022 erase(iterator __it
)
1023 { return erase(const_iterator(__it
)); }
1026 erase(const key_type
& __k
)
1027 { return _M_erase(__unique_keys
{}, __k
); }
1030 erase(const_iterator
, const_iterator
);
1035 // Set number of buckets keeping it appropriate for container's number
1037 void rehash(size_type __bkt_count
);
1040 // reserve, if present, comes from _Rehash_base.
1042 #if __glibcxx_node_extract // >= C++17
1043 /// Re-insert an extracted node into a container with unique keys.
1045 _M_reinsert_node(node_type
&& __nh
)
1047 insert_return_type __ret
;
1049 __ret
.position
= end();
1052 __glibcxx_assert(get_allocator() == __nh
.get_allocator());
1054 __node_ptr __n
= nullptr;
1055 const key_type
& __k
= __nh
._M_key();
1056 const size_type __size
= size();
1057 if (__size
<= __small_size_threshold())
1059 for (__n
= _M_begin(); __n
; __n
= __n
->_M_next())
1060 if (this->_M_key_equals(__k
, *__n
))
1068 __code
= this->_M_hash_code(__k
);
1069 __bkt
= _M_bucket_index(__code
);
1070 if (__size
> __small_size_threshold())
1071 __n
= _M_find_node(__bkt
, __k
, __code
);
1076 __ret
.node
= std::move(__nh
);
1077 __ret
.position
= iterator(__n
);
1078 __ret
.inserted
= false;
1083 = _M_insert_unique_node(__bkt
, __code
, __nh
._M_ptr
);
1085 __ret
.inserted
= true;
1091 /// Re-insert an extracted node into a container with equivalent keys.
1093 _M_reinsert_node_multi(const_iterator __hint
, node_type
&& __nh
)
1098 __glibcxx_assert(get_allocator() == __nh
.get_allocator());
1100 const key_type
& __k
= __nh
._M_key();
1101 auto __code
= this->_M_hash_code(__k
);
1103 = _M_insert_multi_node(__hint
._M_cur
, __code
, __nh
._M_ptr
);
1110 _M_extract_node(size_t __bkt
, __node_base_ptr __prev_n
)
1112 __node_ptr __n
= static_cast<__node_ptr
>(__prev_n
->_M_nxt
);
1113 if (__prev_n
== _M_buckets
[__bkt
])
1114 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1115 __n
->_M_nxt
? _M_bucket_index(*__n
->_M_next()) : 0);
1116 else if (__n
->_M_nxt
)
1118 size_type __next_bkt
= _M_bucket_index(*__n
->_M_next());
1119 if (__next_bkt
!= __bkt
)
1120 _M_buckets
[__next_bkt
] = __prev_n
;
1123 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1124 __n
->_M_nxt
= nullptr;
1126 return { __n
, this->_M_node_allocator() };
1129 // Only use the possibly cached node's hash code if its hash function
1130 // _H2 matches _Hash and is stateless. Otherwise recompute it using _Hash.
1131 template<typename _H2
>
1133 _M_src_hash_code(const _H2
&, const key_type
& __k
,
1134 const __node_value_type
& __src_n
) const
1136 if constexpr (std::is_same_v
<_H2
, _Hash
>)
1137 if constexpr (std::is_empty_v
<_Hash
>)
1138 return this->_M_hash_code(__src_n
);
1140 return this->_M_hash_code(__k
);
1146 extract(const_iterator __pos
)
1148 size_t __bkt
= _M_bucket_index(*__pos
._M_cur
);
1149 return _M_extract_node(__bkt
,
1150 _M_get_previous_node(__bkt
, __pos
._M_cur
));
1155 extract(const _Key
& __k
)
1158 __hash_code __code
= this->_M_hash_code(__k
);
1159 std::size_t __bkt
= _M_bucket_index(__code
);
1160 if (__node_base_ptr __prev_node
= _M_find_before_node(__bkt
, __k
, __code
))
1161 __nh
= _M_extract_node(__bkt
, __prev_node
);
1165 /// Merge from a compatible container into one with unique keys.
1166 template<typename _Compatible_Hashtable
>
1168 _M_merge_unique(_Compatible_Hashtable
& __src
)
1170 static_assert(is_same_v
<typename
_Compatible_Hashtable::node_type
,
1171 node_type
>, "Node types are compatible");
1172 __glibcxx_assert(get_allocator() == __src
.get_allocator());
1174 auto __n_elt
= __src
.size();
1175 for (auto __i
= __src
.cbegin(), __end
= __src
.cend(); __i
!= __end
;)
1178 const size_type __size
= size();
1179 const key_type
& __k
= _ExtractKey
{}(*__pos
);
1180 if (__size
<= __small_size_threshold())
1182 bool __found
= false;
1183 for (auto __n
= _M_begin(); __n
; __n
= __n
->_M_next())
1184 if (this->_M_key_equals(__k
, *__n
))
1199 = _M_src_hash_code(__src
.hash_function(), __k
, *__pos
._M_cur
);
1200 size_type __bkt
= _M_bucket_index(__code
);
1201 if (__size
<= __small_size_threshold()
1202 || _M_find_node(__bkt
, __k
, __code
) == nullptr)
1204 auto __nh
= __src
.extract(__pos
);
1205 _M_insert_unique_node(__bkt
, __code
, __nh
._M_ptr
, __n_elt
);
1209 else if (__n_elt
!= 1)
1214 /// Merge from a compatible container into one with equivalent keys.
1215 template<typename _Compatible_Hashtable
>
1217 _M_merge_multi(_Compatible_Hashtable
& __src
)
1219 static_assert(is_same_v
<typename
_Compatible_Hashtable::node_type
,
1220 node_type
>, "Node types are compatible");
1221 __glibcxx_assert(get_allocator() == __src
.get_allocator());
1223 __node_ptr __hint
= nullptr;
1224 this->reserve(size() + __src
.size());
1225 for (auto __i
= __src
.cbegin(), __end
= __src
.cend(); __i
!= __end
;)
1228 const key_type
& __k
= _ExtractKey
{}(*__pos
);
1230 = _M_src_hash_code(__src
.hash_function(), __k
, *__pos
._M_cur
);
1231 auto __nh
= __src
.extract(__pos
);
1232 __hint
= _M_insert_multi_node(__hint
, __code
, __nh
._M_ptr
)._M_cur
;
1236 #endif // C++17 __glibcxx_node_extract
1239 // Helper rehash method used when keys are unique.
1240 void _M_rehash(size_type __bkt_count
, true_type __uks
);
1242 // Helper rehash method used when keys can be non-unique.
1243 void _M_rehash(size_type __bkt_count
, false_type __uks
);
1246 // Definitions of class template _Hashtable's out-of-line member functions.
1247 template<typename _Key
, typename _Value
, typename _Alloc
,
1248 typename _ExtractKey
, typename _Equal
,
1249 typename _Hash
, typename _RangeHash
, typename _Unused
,
1250 typename _RehashPolicy
, typename _Traits
>
1251 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1252 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1253 _Hashtable(size_type __bkt_count_hint
,
1254 const _Hash
& __h
, const _Equal
& __eq
, const allocator_type
& __a
)
1255 : _Hashtable(__h
, __eq
, __a
)
1257 auto __bkt_count
= _M_rehash_policy
._M_next_bkt(__bkt_count_hint
);
1258 if (__bkt_count
> _M_bucket_count
)
1260 _M_buckets
= _M_allocate_buckets(__bkt_count
);
1261 _M_bucket_count
= __bkt_count
;
1265 template<typename _Key
, typename _Value
, typename _Alloc
,
1266 typename _ExtractKey
, typename _Equal
,
1267 typename _Hash
, typename _RangeHash
, typename _Unused
,
1268 typename _RehashPolicy
, typename _Traits
>
1269 template<typename _InputIterator
>
1270 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1271 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1272 _Hashtable(_InputIterator __f
, _InputIterator __l
,
1273 size_type __bkt_count_hint
,
1274 const _Hash
& __h
, const _Equal
& __eq
,
1275 const allocator_type
& __a
, true_type
/* __uks */)
1276 : _Hashtable(__bkt_count_hint
, __h
, __eq
, __a
)
1277 { this->insert(__f
, __l
); }
1279 template<typename _Key
, typename _Value
, typename _Alloc
,
1280 typename _ExtractKey
, typename _Equal
,
1281 typename _Hash
, typename _RangeHash
, typename _Unused
,
1282 typename _RehashPolicy
, typename _Traits
>
1283 template<typename _InputIterator
>
1284 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1285 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1286 _Hashtable(_InputIterator __f
, _InputIterator __l
,
1287 size_type __bkt_count_hint
,
1288 const _Hash
& __h
, const _Equal
& __eq
,
1289 const allocator_type
& __a
, false_type __uks
)
1290 : _Hashtable(__h
, __eq
, __a
)
1292 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
1294 _M_rehash_policy
._M_next_bkt(
1295 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
1298 if (__bkt_count
> _M_bucket_count
)
1300 _M_buckets
= _M_allocate_buckets(__bkt_count
);
1301 _M_bucket_count
= __bkt_count
;
1304 __alloc_node_gen_t
__node_gen(*this);
1305 for (; __f
!= __l
; ++__f
)
1306 _M_insert(*__f
, __node_gen
, __uks
);
1309 template<typename _Key
, typename _Value
, typename _Alloc
,
1310 typename _ExtractKey
, typename _Equal
,
1311 typename _Hash
, typename _RangeHash
, typename _Unused
,
1312 typename _RehashPolicy
, typename _Traits
>
1314 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1315 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1316 operator=(const _Hashtable
& __ht
)
1322 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1324 auto& __this_alloc
= this->_M_node_allocator();
1325 auto& __that_alloc
= __ht
._M_node_allocator();
1326 if (!__node_alloc_traits::_S_always_equal()
1327 && __this_alloc
!= __that_alloc
)
1329 // Replacement allocator cannot free existing storage.
1330 this->_M_deallocate_nodes(_M_begin());
1331 _M_before_begin
._M_nxt
= nullptr;
1332 _M_deallocate_buckets();
1333 _M_buckets
= nullptr;
1334 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1335 __hashtable_base::operator=(__ht
);
1336 _M_bucket_count
= __ht
._M_bucket_count
;
1337 _M_element_count
= __ht
._M_element_count
;
1338 _M_rehash_policy
= __ht
._M_rehash_policy
;
1339 __alloc_node_gen_t
__alloc_node_gen(*this);
1342 _M_assign(__ht
, __alloc_node_gen
);
1346 // _M_assign took care of deallocating all memory. Now we
1347 // must make sure this instance remains in a usable state.
1349 __throw_exception_again
;
1353 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1356 // Reuse allocated buckets and nodes.
1357 _M_assign_elements(__ht
);
1361 template<typename _Key
, typename _Value
, typename _Alloc
,
1362 typename _ExtractKey
, typename _Equal
,
1363 typename _Hash
, typename _RangeHash
, typename _Unused
,
1364 typename _RehashPolicy
, typename _Traits
>
1365 template<typename _Ht
>
1367 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1368 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1369 _M_assign_elements(_Ht
&& __ht
)
1371 __buckets_ptr __former_buckets
= nullptr;
1372 std::size_t __former_bucket_count
= _M_bucket_count
;
1373 __rehash_guard_t
__rehash_guard(_M_rehash_policy
);
1375 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1377 __former_buckets
= _M_buckets
;
1378 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
1379 _M_bucket_count
= __ht
._M_bucket_count
;
1382 std::fill_n(_M_buckets
, _M_bucket_count
, nullptr);
1386 __hashtable_base::operator=(std::forward
<_Ht
>(__ht
));
1387 _M_element_count
= __ht
._M_element_count
;
1388 _M_rehash_policy
= __ht
._M_rehash_policy
;
1389 __reuse_or_alloc_node_gen_t
__roan(_M_begin(), *this);
1390 _M_before_begin
._M_nxt
= nullptr;
1391 _M_assign(std::forward
<_Ht
>(__ht
), __roan
);
1392 if (__former_buckets
)
1393 _M_deallocate_buckets(__former_buckets
, __former_bucket_count
);
1394 __rehash_guard
._M_guarded_obj
= nullptr;
1398 if (__former_buckets
)
1400 // Restore previous buckets.
1401 _M_deallocate_buckets();
1402 _M_buckets
= __former_buckets
;
1403 _M_bucket_count
= __former_bucket_count
;
1405 std::fill_n(_M_buckets
, _M_bucket_count
, nullptr);
1406 __throw_exception_again
;
1410 template<typename _Key
, typename _Value
, typename _Alloc
,
1411 typename _ExtractKey
, typename _Equal
,
1412 typename _Hash
, typename _RangeHash
, typename _Unused
,
1413 typename _RehashPolicy
, typename _Traits
>
1414 template<typename _Ht
, typename _NodeGenerator
>
1416 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1417 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1418 _M_assign(_Ht
&& __ht
, const _NodeGenerator
& __node_gen
)
1420 __buckets_ptr __buckets
= nullptr;
1422 _M_buckets
= __buckets
= _M_allocate_buckets(_M_bucket_count
);
1426 if (!__ht
._M_before_begin
._M_nxt
)
1429 // First deal with the special first node pointed to by
1431 __node_ptr __ht_n
= __ht
._M_begin();
1433 = __node_gen(__fwd_value_for
<_Ht
>(__ht_n
->_M_v()));
1434 this->_M_copy_code(*__this_n
, *__ht_n
);
1435 _M_update_bbegin(__this_n
);
1437 // Then deal with other nodes.
1438 __node_ptr __prev_n
= __this_n
;
1439 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
1441 __this_n
= __node_gen(__fwd_value_for
<_Ht
>(__ht_n
->_M_v()));
1442 __prev_n
->_M_nxt
= __this_n
;
1443 this->_M_copy_code(*__this_n
, *__ht_n
);
1444 size_type __bkt
= _M_bucket_index(*__this_n
);
1445 if (!_M_buckets
[__bkt
])
1446 _M_buckets
[__bkt
] = __prev_n
;
1447 __prev_n
= __this_n
;
1454 _M_deallocate_buckets();
1455 __throw_exception_again
;
1459 template<typename _Key
, typename _Value
, typename _Alloc
,
1460 typename _ExtractKey
, typename _Equal
,
1461 typename _Hash
, typename _RangeHash
, typename _Unused
,
1462 typename _RehashPolicy
, typename _Traits
>
1464 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1465 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1468 _M_rehash_policy
._M_reset();
1469 _M_bucket_count
= 1;
1470 _M_single_bucket
= nullptr;
1471 _M_buckets
= &_M_single_bucket
;
1472 _M_before_begin
._M_nxt
= nullptr;
1473 _M_element_count
= 0;
1476 template<typename _Key
, typename _Value
, typename _Alloc
,
1477 typename _ExtractKey
, typename _Equal
,
1478 typename _Hash
, typename _RangeHash
, typename _Unused
,
1479 typename _RehashPolicy
, typename _Traits
>
1481 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1482 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1483 _M_move_assign(_Hashtable
&& __ht
, true_type
)
1485 if (__builtin_expect(std::__addressof(__ht
) == this, false))
1488 this->_M_deallocate_nodes(_M_begin());
1489 _M_deallocate_buckets();
1490 __hashtable_base::operator=(std::move(__ht
));
1491 _M_rehash_policy
= __ht
._M_rehash_policy
;
1492 if (!__ht
._M_uses_single_bucket())
1493 _M_buckets
= __ht
._M_buckets
;
1496 _M_buckets
= &_M_single_bucket
;
1497 _M_single_bucket
= __ht
._M_single_bucket
;
1500 _M_bucket_count
= __ht
._M_bucket_count
;
1501 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1502 _M_element_count
= __ht
._M_element_count
;
1503 std::__alloc_on_move(this->_M_node_allocator(), __ht
._M_node_allocator());
1505 // Fix bucket containing the _M_before_begin pointer that can't be moved.
1510 template<typename _Key
, typename _Value
, typename _Alloc
,
1511 typename _ExtractKey
, typename _Equal
,
1512 typename _Hash
, typename _RangeHash
, typename _Unused
,
1513 typename _RehashPolicy
, typename _Traits
>
1515 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1516 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1517 _M_move_assign(_Hashtable
&& __ht
, false_type
)
1519 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1520 _M_move_assign(std::move(__ht
), true_type
{});
1523 // Can't move memory, move elements then.
1524 _M_assign_elements(std::move(__ht
));
1529 template<typename _Key
, typename _Value
, typename _Alloc
,
1530 typename _ExtractKey
, typename _Equal
,
1531 typename _Hash
, typename _RangeHash
, typename _Unused
,
1532 typename _RehashPolicy
, typename _Traits
>
1533 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1534 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1535 _Hashtable(const _Hashtable
& __ht
)
1536 : __hashtable_base(__ht
),
1538 __rehash_base(__ht
),
1540 __node_alloc_traits::_S_select_on_copy(__ht
._M_node_allocator())),
1541 __enable_default_ctor(__ht
),
1542 _M_buckets(nullptr),
1543 _M_bucket_count(__ht
._M_bucket_count
),
1544 _M_element_count(__ht
._M_element_count
),
1545 _M_rehash_policy(__ht
._M_rehash_policy
)
1547 __alloc_node_gen_t
__alloc_node_gen(*this);
1548 _M_assign(__ht
, __alloc_node_gen
);
1551 template<typename _Key
, typename _Value
, typename _Alloc
,
1552 typename _ExtractKey
, typename _Equal
,
1553 typename _Hash
, typename _RangeHash
, typename _Unused
,
1554 typename _RehashPolicy
, typename _Traits
>
1555 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1556 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1557 _Hashtable(_Hashtable
&& __ht
, __node_alloc_type
&& __a
,
1558 true_type
/* alloc always equal */)
1559 noexcept(_S_nothrow_move())
1560 : __hashtable_base(__ht
),
1562 __rehash_base(__ht
),
1563 __hashtable_alloc(std::move(__a
)),
1564 __enable_default_ctor(__ht
),
1565 _M_buckets(__ht
._M_buckets
),
1566 _M_bucket_count(__ht
._M_bucket_count
),
1567 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
1568 _M_element_count(__ht
._M_element_count
),
1569 _M_rehash_policy(__ht
._M_rehash_policy
)
1571 // Update buckets if __ht is using its single bucket.
1572 if (__ht
._M_uses_single_bucket())
1574 _M_buckets
= &_M_single_bucket
;
1575 _M_single_bucket
= __ht
._M_single_bucket
;
1578 // Fix bucket containing the _M_before_begin pointer that can't be moved.
1584 template<typename _Key
, typename _Value
, typename _Alloc
,
1585 typename _ExtractKey
, typename _Equal
,
1586 typename _Hash
, typename _RangeHash
, typename _Unused
,
1587 typename _RehashPolicy
, typename _Traits
>
1588 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1589 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1590 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1591 : __hashtable_base(__ht
),
1593 __rehash_base(__ht
),
1594 __hashtable_alloc(__node_alloc_type(__a
)),
1595 __enable_default_ctor(__ht
),
1597 _M_bucket_count(__ht
._M_bucket_count
),
1598 _M_element_count(__ht
._M_element_count
),
1599 _M_rehash_policy(__ht
._M_rehash_policy
)
1601 __alloc_node_gen_t
__alloc_node_gen(*this);
1602 _M_assign(__ht
, __alloc_node_gen
);
1605 template<typename _Key
, typename _Value
, typename _Alloc
,
1606 typename _ExtractKey
, typename _Equal
,
1607 typename _Hash
, typename _RangeHash
, typename _Unused
,
1608 typename _RehashPolicy
, typename _Traits
>
1609 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1610 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1611 _Hashtable(_Hashtable
&& __ht
, __node_alloc_type
&& __a
,
1612 false_type
/* alloc always equal */)
1613 : __hashtable_base(__ht
),
1615 __rehash_base(__ht
),
1616 __hashtable_alloc(std::move(__a
)),
1617 __enable_default_ctor(__ht
),
1618 _M_buckets(nullptr),
1619 _M_bucket_count(__ht
._M_bucket_count
),
1620 _M_element_count(__ht
._M_element_count
),
1621 _M_rehash_policy(__ht
._M_rehash_policy
)
1623 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1625 if (__ht
._M_uses_single_bucket())
1627 _M_buckets
= &_M_single_bucket
;
1628 _M_single_bucket
= __ht
._M_single_bucket
;
1631 _M_buckets
= __ht
._M_buckets
;
1633 // Fix bucket containing the _M_before_begin pointer that can't be
1635 _M_update_bbegin(__ht
._M_begin());
1641 __alloc_node_gen_t
__alloc_gen(*this);
1643 using _Fwd_Ht
= __conditional_t
<
1644 __move_if_noexcept_cond
<value_type
>::value
,
1645 const _Hashtable
&, _Hashtable
&&>;
1646 _M_assign(std::forward
<_Fwd_Ht
>(__ht
), __alloc_gen
);
1651 template<typename _Key
, typename _Value
, typename _Alloc
,
1652 typename _ExtractKey
, typename _Equal
,
1653 typename _Hash
, typename _RangeHash
, typename _Unused
,
1654 typename _RehashPolicy
, typename _Traits
>
1655 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1656 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1657 ~_Hashtable() noexcept
1659 // Getting a bucket index from a node shall not throw because it is used
1660 // in methods (erase, swap...) that shall not throw. Need a complete
1661 // type to check this, so do it in the destructor not at class scope.
1662 static_assert(noexcept(declval
<const __hash_code_base_access
&>()
1663 ._M_bucket_index(declval
<const __node_value_type
&>(),
1665 "Cache the hash code or qualify your functors involved"
1666 " in hash code and bucket index computation with noexcept");
1668 this->_M_deallocate_nodes(_M_begin());
1669 _M_deallocate_buckets();
1672 template<typename _Key
, typename _Value
, typename _Alloc
,
1673 typename _ExtractKey
, typename _Equal
,
1674 typename _Hash
, typename _RangeHash
, typename _Unused
,
1675 typename _RehashPolicy
, typename _Traits
>
1677 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1678 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1679 swap(_Hashtable
& __x
)
1680 noexcept(__and_
<__is_nothrow_swappable
<_Hash
>,
1681 __is_nothrow_swappable
<_Equal
>>::value
)
1683 // The only base class with member variables is hash_code_base.
1684 // We define _Hash_code_base::_M_swap because different
1685 // specializations have different members.
1688 std::__alloc_on_swap(this->_M_node_allocator(), __x
._M_node_allocator());
1689 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1691 // Deal properly with potentially moved instances.
1692 if (this->_M_uses_single_bucket())
1694 if (!__x
._M_uses_single_bucket())
1696 _M_buckets
= __x
._M_buckets
;
1697 __x
._M_buckets
= &__x
._M_single_bucket
;
1700 else if (__x
._M_uses_single_bucket())
1702 __x
._M_buckets
= _M_buckets
;
1703 _M_buckets
= &_M_single_bucket
;
1706 std::swap(_M_buckets
, __x
._M_buckets
);
1708 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1709 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
1710 std::swap(_M_element_count
, __x
._M_element_count
);
1711 std::swap(_M_single_bucket
, __x
._M_single_bucket
);
1713 // Fix buckets containing the _M_before_begin pointers that can't be
1716 __x
._M_update_bbegin();
1719 template<typename _Key
, typename _Value
, typename _Alloc
,
1720 typename _ExtractKey
, typename _Equal
,
1721 typename _Hash
, typename _RangeHash
, typename _Unused
,
1722 typename _RehashPolicy
, typename _Traits
>
1724 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1725 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1726 find(const key_type
& __k
)
1729 if (size() <= __small_size_threshold())
1731 for (auto __it
= _M_begin(); __it
; __it
= __it
->_M_next())
1732 if (this->_M_key_equals(__k
, *__it
))
1733 return iterator(__it
);
1737 __hash_code __code
= this->_M_hash_code(__k
);
1738 std::size_t __bkt
= _M_bucket_index(__code
);
1739 return iterator(_M_find_node(__bkt
, __k
, __code
));
1742 template<typename _Key
, typename _Value
, typename _Alloc
,
1743 typename _ExtractKey
, typename _Equal
,
1744 typename _Hash
, typename _RangeHash
, typename _Unused
,
1745 typename _RehashPolicy
, typename _Traits
>
1747 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1748 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1749 find(const key_type
& __k
) const
1752 if (size() <= __small_size_threshold())
1754 for (auto __it
= _M_begin(); __it
; __it
= __it
->_M_next())
1755 if (this->_M_key_equals(__k
, *__it
))
1756 return const_iterator(__it
);
1760 __hash_code __code
= this->_M_hash_code(__k
);
1761 std::size_t __bkt
= _M_bucket_index(__code
);
1762 return const_iterator(_M_find_node(__bkt
, __k
, __code
));
1765 #if __cplusplus > 201703L
1766 template<typename _Key
, typename _Value
, typename _Alloc
,
1767 typename _ExtractKey
, typename _Equal
,
1768 typename _Hash
, typename _RangeHash
, typename _Unused
,
1769 typename _RehashPolicy
, typename _Traits
>
1770 template<typename _Kt
, typename
, typename
>
1772 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1773 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1774 _M_find_tr(const _Kt
& __k
)
1777 if (size() <= __small_size_threshold())
1779 for (auto __n
= _M_begin(); __n
; __n
= __n
->_M_next())
1780 if (this->_M_key_equals_tr(__k
, *__n
))
1781 return iterator(__n
);
1785 __hash_code __code
= this->_M_hash_code_tr(__k
);
1786 std::size_t __bkt
= _M_bucket_index(__code
);
1787 return iterator(_M_find_node_tr(__bkt
, __k
, __code
));
1790 template<typename _Key
, typename _Value
, typename _Alloc
,
1791 typename _ExtractKey
, typename _Equal
,
1792 typename _Hash
, typename _RangeHash
, typename _Unused
,
1793 typename _RehashPolicy
, typename _Traits
>
1794 template<typename _Kt
, typename
, typename
>
1796 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1797 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1798 _M_find_tr(const _Kt
& __k
) const
1801 if (size() <= __small_size_threshold())
1803 for (auto __n
= _M_begin(); __n
; __n
= __n
->_M_next())
1804 if (this->_M_key_equals_tr(__k
, *__n
))
1805 return const_iterator(__n
);
1809 __hash_code __code
= this->_M_hash_code_tr(__k
);
1810 std::size_t __bkt
= _M_bucket_index(__code
);
1811 return const_iterator(_M_find_node_tr(__bkt
, __k
, __code
));
1815 template<typename _Key
, typename _Value
, typename _Alloc
,
1816 typename _ExtractKey
, typename _Equal
,
1817 typename _Hash
, typename _RangeHash
, typename _Unused
,
1818 typename _RehashPolicy
, typename _Traits
>
1820 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1821 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1822 count(const key_type
& __k
) const
1825 auto __it
= find(__k
);
1829 if (__unique_keys::value
)
1832 size_type __result
= 1;
1833 for (auto __ref
= __it
++;
1834 __it
._M_cur
&& this->_M_node_equals(*__ref
._M_cur
, *__it
._M_cur
);
1841 #if __cplusplus > 201703L
1842 template<typename _Key
, typename _Value
, typename _Alloc
,
1843 typename _ExtractKey
, typename _Equal
,
1844 typename _Hash
, typename _RangeHash
, typename _Unused
,
1845 typename _RehashPolicy
, typename _Traits
>
1846 template<typename _Kt
, typename
, typename
>
1848 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1849 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1850 _M_count_tr(const _Kt
& __k
) const
1853 if (size() <= __small_size_threshold())
1855 size_type __result
= 0;
1856 for (auto __n
= _M_begin(); __n
; __n
= __n
->_M_next())
1858 if (this->_M_key_equals_tr(__k
, *__n
))
1871 __hash_code __code
= this->_M_hash_code_tr(__k
);
1872 std::size_t __bkt
= _M_bucket_index(__code
);
1873 auto __n
= _M_find_node_tr(__bkt
, __k
, __code
);
1878 size_type __result
= 1;
1880 __it
._M_cur
&& this->_M_equals_tr(__k
, __code
, *__it
._M_cur
);
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 equal_range(const key_type
& __k
)
1896 -> pair
<iterator
, iterator
>
1898 auto __ite
= find(__k
);
1900 return { __ite
, __ite
};
1902 auto __beg
= __ite
++;
1903 if (__unique_keys::value
)
1904 return { __beg
, __ite
};
1906 while (__ite
._M_cur
&& this->_M_node_equals(*__beg
._M_cur
, *__ite
._M_cur
))
1909 return { __beg
, __ite
};
1912 template<typename _Key
, typename _Value
, typename _Alloc
,
1913 typename _ExtractKey
, typename _Equal
,
1914 typename _Hash
, typename _RangeHash
, typename _Unused
,
1915 typename _RehashPolicy
, typename _Traits
>
1917 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1918 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1919 equal_range(const key_type
& __k
) const
1920 -> pair
<const_iterator
, const_iterator
>
1922 auto __ite
= find(__k
);
1924 return { __ite
, __ite
};
1926 auto __beg
= __ite
++;
1927 if (__unique_keys::value
)
1928 return { __beg
, __ite
};
1930 while (__ite
._M_cur
&& this->_M_node_equals(*__beg
._M_cur
, *__ite
._M_cur
))
1933 return { __beg
, __ite
};
1936 #if __cplusplus > 201703L
1937 template<typename _Key
, typename _Value
, typename _Alloc
,
1938 typename _ExtractKey
, typename _Equal
,
1939 typename _Hash
, typename _RangeHash
, typename _Unused
,
1940 typename _RehashPolicy
, typename _Traits
>
1941 template<typename _Kt
, typename
, typename
>
1943 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1944 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1945 _M_equal_range_tr(const _Kt
& __k
)
1946 -> pair
<iterator
, iterator
>
1948 if (size() <= __small_size_threshold())
1950 __node_ptr __n
, __beg
= nullptr;
1951 for (__n
= _M_begin(); __n
; __n
= __n
->_M_next())
1953 if (this->_M_key_equals_tr(__k
, *__n
))
1964 return { iterator(__beg
), iterator(__n
) };
1967 __hash_code __code
= this->_M_hash_code_tr(__k
);
1968 std::size_t __bkt
= _M_bucket_index(__code
);
1969 auto __n
= _M_find_node_tr(__bkt
, __k
, __code
);
1970 iterator
__ite(__n
);
1972 return { __ite
, __ite
};
1974 auto __beg
= __ite
++;
1975 while (__ite
._M_cur
&& this->_M_equals_tr(__k
, __code
, *__ite
._M_cur
))
1978 return { __beg
, __ite
};
1981 template<typename _Key
, typename _Value
, typename _Alloc
,
1982 typename _ExtractKey
, typename _Equal
,
1983 typename _Hash
, typename _RangeHash
, typename _Unused
,
1984 typename _RehashPolicy
, typename _Traits
>
1985 template<typename _Kt
, typename
, typename
>
1987 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1988 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
1989 _M_equal_range_tr(const _Kt
& __k
) const
1990 -> pair
<const_iterator
, const_iterator
>
1992 if (size() <= __small_size_threshold())
1994 __node_ptr __n
, __beg
= nullptr;
1995 for (__n
= _M_begin(); __n
; __n
= __n
->_M_next())
1997 if (this->_M_key_equals_tr(__k
, *__n
))
2008 return { const_iterator(__beg
), const_iterator(__n
) };
2011 __hash_code __code
= this->_M_hash_code_tr(__k
);
2012 std::size_t __bkt
= _M_bucket_index(__code
);
2013 auto __n
= _M_find_node_tr(__bkt
, __k
, __code
);
2014 const_iterator
__ite(__n
);
2016 return { __ite
, __ite
};
2018 auto __beg
= __ite
++;
2019 while (__ite
._M_cur
&& this->_M_equals_tr(__k
, __code
, *__ite
._M_cur
))
2022 return { __beg
, __ite
};
2026 // Find the node before the one whose key compares equal to k.
2027 // Return nullptr if no node is found.
2028 template<typename _Key
, typename _Value
, typename _Alloc
,
2029 typename _ExtractKey
, typename _Equal
,
2030 typename _Hash
, typename _RangeHash
, typename _Unused
,
2031 typename _RehashPolicy
, typename _Traits
>
2033 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2034 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2035 _M_find_before_node(const key_type
& __k
)
2038 __node_base_ptr __prev_p
= &_M_before_begin
;
2039 if (!__prev_p
->_M_nxt
)
2042 for (__node_ptr __p
= static_cast<__node_ptr
>(__prev_p
->_M_nxt
);
2044 __p
= __p
->_M_next())
2046 if (this->_M_key_equals(__k
, *__p
))
2055 // Find the node before the one whose key compares equal to k in the bucket
2056 // bkt. Return nullptr if no node is found.
2057 template<typename _Key
, typename _Value
, typename _Alloc
,
2058 typename _ExtractKey
, typename _Equal
,
2059 typename _Hash
, typename _RangeHash
, typename _Unused
,
2060 typename _RehashPolicy
, typename _Traits
>
2062 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2063 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2064 _M_find_before_node(size_type __bkt
, const key_type
& __k
,
2065 __hash_code __code
) const
2068 __node_base_ptr __prev_p
= _M_buckets
[__bkt
];
2072 for (__node_ptr __p
= static_cast<__node_ptr
>(__prev_p
->_M_nxt
);;
2073 __p
= __p
->_M_next())
2075 if (this->_M_equals(__k
, __code
, *__p
))
2078 if (!__p
->_M_nxt
|| _M_bucket_index(*__p
->_M_next()) != __bkt
)
2086 template<typename _Key
, typename _Value
, typename _Alloc
,
2087 typename _ExtractKey
, typename _Equal
,
2088 typename _Hash
, typename _RangeHash
, typename _Unused
,
2089 typename _RehashPolicy
, typename _Traits
>
2090 template<typename _Kt
>
2092 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2093 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2094 _M_find_before_node_tr(size_type __bkt
, const _Kt
& __k
,
2095 __hash_code __code
) const
2098 __node_base_ptr __prev_p
= _M_buckets
[__bkt
];
2102 for (__node_ptr __p
= static_cast<__node_ptr
>(__prev_p
->_M_nxt
);;
2103 __p
= __p
->_M_next())
2105 if (this->_M_equals_tr(__k
, __code
, *__p
))
2108 if (!__p
->_M_nxt
|| _M_bucket_index(*__p
->_M_next()) != __bkt
)
2116 template<typename _Key
, typename _Value
, typename _Alloc
,
2117 typename _ExtractKey
, typename _Equal
,
2118 typename _Hash
, typename _RangeHash
, typename _Unused
,
2119 typename _RehashPolicy
, typename _Traits
>
2121 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2122 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2123 _M_get_previous_node(size_type __bkt
, __node_ptr __n
)
2126 __node_base_ptr __prev_n
= _M_buckets
[__bkt
];
2127 while (__prev_n
->_M_nxt
!= __n
)
2128 __prev_n
= __prev_n
->_M_nxt
;
2132 template<typename _Key
, typename _Value
, typename _Alloc
,
2133 typename _ExtractKey
, typename _Equal
,
2134 typename _Hash
, typename _RangeHash
, typename _Unused
,
2135 typename _RehashPolicy
, typename _Traits
>
2136 template<typename
... _Args
>
2138 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2139 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2140 _M_emplace(true_type
/* __uks */, _Args
&&... __args
)
2141 -> pair
<iterator
, bool>
2143 // First build the node to get access to the hash code
2144 _Scoped_node __node
{ this, std::forward
<_Args
>(__args
)... };
2145 const key_type
& __k
= _ExtractKey
{}(__node
._M_node
->_M_v());
2146 const size_type __size
= size();
2147 if (__size
<= __small_size_threshold())
2149 for (auto __it
= _M_begin(); __it
; __it
= __it
->_M_next())
2150 if (this->_M_key_equals(__k
, *__it
))
2151 // There is already an equivalent node, no insertion
2152 return { iterator(__it
), false };
2155 __hash_code __code
= this->_M_hash_code(__k
);
2156 size_type __bkt
= _M_bucket_index(__code
);
2157 if (__size
> __small_size_threshold())
2158 if (__node_ptr __p
= _M_find_node(__bkt
, __k
, __code
))
2159 // There is already an equivalent node, no insertion
2160 return { iterator(__p
), false };
2163 auto __pos
= _M_insert_unique_node(__bkt
, __code
, __node
._M_node
);
2164 __node
._M_node
= nullptr;
2165 return { __pos
, true };
2168 template<typename _Key
, typename _Value
, typename _Alloc
,
2169 typename _ExtractKey
, typename _Equal
,
2170 typename _Hash
, typename _RangeHash
, typename _Unused
,
2171 typename _RehashPolicy
, typename _Traits
>
2172 template<typename
... _Args
>
2174 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2175 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2176 _M_emplace(const_iterator __hint
, false_type
/* __uks */,
2180 // First build the node to get its hash code.
2181 _Scoped_node __node
{ this, std::forward
<_Args
>(__args
)... };
2182 const key_type
& __k
= _ExtractKey
{}(__node
._M_node
->_M_v());
2184 auto __res
= this->_M_compute_hash_code(__hint
._M_cur
, __k
);
2186 = _M_insert_multi_node(__res
.first
, __res
.second
, __node
._M_node
);
2187 __node
._M_node
= nullptr;
2191 template<typename _Key
, typename _Value
, typename _Alloc
,
2192 typename _ExtractKey
, typename _Equal
,
2193 typename _Hash
, typename _RangeHash
, typename _Unused
,
2194 typename _RehashPolicy
, typename _Traits
>
2196 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2197 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2198 _M_compute_hash_code(__node_ptr __hint
, const key_type
& __k
) const
2199 -> pair
<__node_ptr
, __hash_code
>
2201 if (size() <= __small_size_threshold())
2205 for (auto __it
= __hint
; __it
; __it
= __it
->_M_next())
2206 if (this->_M_key_equals(__k
, *__it
))
2207 return { __it
, this->_M_hash_code(*__it
) };
2210 for (auto __it
= _M_begin(); __it
!= __hint
; __it
= __it
->_M_next())
2211 if (this->_M_key_equals(__k
, *__it
))
2212 return { __it
, this->_M_hash_code(*__it
) };
2217 return { __hint
, this->_M_hash_code(__k
) };
2220 template<typename _Key
, typename _Value
, typename _Alloc
,
2221 typename _ExtractKey
, typename _Equal
,
2222 typename _Hash
, typename _RangeHash
, typename _Unused
,
2223 typename _RehashPolicy
, typename _Traits
>
2225 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2226 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2227 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
2228 __node_ptr __node
, size_type __n_elt
)
2231 __rehash_guard_t
__rehash_guard(_M_rehash_policy
);
2232 std::pair
<bool, std::size_t> __do_rehash
2233 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
,
2236 if (__do_rehash
.first
)
2238 _M_rehash(__do_rehash
.second
, true_type
{});
2239 __bkt
= _M_bucket_index(__code
);
2242 __rehash_guard
._M_guarded_obj
= nullptr;
2243 this->_M_store_code(*__node
, __code
);
2245 // Always insert at the beginning of the bucket.
2246 _M_insert_bucket_begin(__bkt
, __node
);
2248 return iterator(__node
);
2251 template<typename _Key
, typename _Value
, typename _Alloc
,
2252 typename _ExtractKey
, typename _Equal
,
2253 typename _Hash
, typename _RangeHash
, typename _Unused
,
2254 typename _RehashPolicy
, typename _Traits
>
2256 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2257 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2258 _M_insert_multi_node(__node_ptr __hint
,
2259 __hash_code __code
, __node_ptr __node
)
2262 __rehash_guard_t
__rehash_guard(_M_rehash_policy
);
2263 std::pair
<bool, std::size_t> __do_rehash
2264 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
2266 if (__do_rehash
.first
)
2267 _M_rehash(__do_rehash
.second
, false_type
{});
2269 __rehash_guard
._M_guarded_obj
= nullptr;
2270 this->_M_store_code(*__node
, __code
);
2271 const key_type
& __k
= _ExtractKey
{}(__node
->_M_v());
2272 size_type __bkt
= _M_bucket_index(__code
);
2274 // Find the node before an equivalent one or use hint if it exists and
2275 // if it is equivalent.
2276 __node_base_ptr __prev
2277 = __builtin_expect(__hint
!= nullptr, false)
2278 && this->_M_equals(__k
, __code
, *__hint
)
2280 : _M_find_before_node(__bkt
, __k
, __code
);
2284 // Insert after the node before the equivalent one.
2285 __node
->_M_nxt
= __prev
->_M_nxt
;
2286 __prev
->_M_nxt
= __node
;
2287 if (__builtin_expect(__prev
== __hint
, false))
2288 // hint might be the last bucket node, in this case we need to
2289 // update next bucket.
2291 && !this->_M_equals(__k
, __code
, *__node
->_M_next()))
2293 size_type __next_bkt
= _M_bucket_index(*__node
->_M_next());
2294 if (__next_bkt
!= __bkt
)
2295 _M_buckets
[__next_bkt
] = __node
;
2299 // The inserted node has no equivalent in the hashtable. We must
2300 // insert the new node at the beginning of the bucket to preserve
2301 // equivalent elements' relative positions.
2302 _M_insert_bucket_begin(__bkt
, __node
);
2304 return iterator(__node
);
2307 // Insert v if no element with its key is already present.
2308 template<typename _Key
, typename _Value
, typename _Alloc
,
2309 typename _ExtractKey
, typename _Equal
,
2310 typename _Hash
, typename _RangeHash
, typename _Unused
,
2311 typename _RehashPolicy
, typename _Traits
>
2312 template<typename _Kt
, typename _Arg
, typename _NodeGenerator
>
2314 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2315 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2316 _M_insert_unique(_Kt
&& __k
, _Arg
&& __v
,
2317 const _NodeGenerator
& __node_gen
)
2318 -> pair
<iterator
, bool>
2320 const size_type __size
= size();
2321 if (__size
<= __small_size_threshold())
2322 for (auto __it
= _M_begin(); __it
; __it
= __it
->_M_next())
2323 if (this->_M_key_equals_tr(__k
, *__it
))
2324 return { iterator(__it
), false };
2326 __hash_code __code
= this->_M_hash_code_tr(__k
);
2327 size_type __bkt
= _M_bucket_index(__code
);
2329 if (__size
> __small_size_threshold())
2330 if (__node_ptr __node
= _M_find_node_tr(__bkt
, __k
, __code
))
2331 return { iterator(__node
), false };
2333 _Scoped_node __node
{
2334 __node_builder_t::_S_build(std::forward
<_Kt
>(__k
),
2335 std::forward
<_Arg
>(__v
),
2340 = _M_insert_unique_node(__bkt
, __code
, __node
._M_node
);
2341 __node
._M_node
= nullptr;
2342 return { __pos
, true };
2345 // Insert v unconditionally.
2346 template<typename _Key
, typename _Value
, typename _Alloc
,
2347 typename _ExtractKey
, typename _Equal
,
2348 typename _Hash
, typename _RangeHash
, typename _Unused
,
2349 typename _RehashPolicy
, typename _Traits
>
2350 template<typename _Arg
, typename _NodeGenerator
>
2352 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2353 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2354 _M_insert(const_iterator __hint
, _Arg
&& __v
,
2355 const _NodeGenerator
& __node_gen
,
2356 false_type
/* __uks */)
2359 // First allocate new node so that we don't do anything if it throws.
2360 _Scoped_node __node
{ __node_gen(std::forward
<_Arg
>(__v
)), this };
2362 // Second compute the hash code so that we don't rehash if it throws.
2363 auto __res
= this->_M_compute_hash_code(
2364 __hint
._M_cur
, _ExtractKey
{}(__node
._M_node
->_M_v()));
2367 = _M_insert_multi_node(__res
.first
, __res
.second
, __node
._M_node
);
2368 __node
._M_node
= nullptr;
2372 template<typename _Key
, typename _Value
, typename _Alloc
,
2373 typename _ExtractKey
, typename _Equal
,
2374 typename _Hash
, typename _RangeHash
, typename _Unused
,
2375 typename _RehashPolicy
, typename _Traits
>
2377 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2378 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2379 erase(const_iterator __it
)
2382 __node_ptr __n
= __it
._M_cur
;
2383 std::size_t __bkt
= _M_bucket_index(*__n
);
2385 // Look for previous node to unlink it from the erased one, this
2386 // is why we need buckets to contain the before begin to make
2387 // this search fast.
2388 __node_base_ptr __prev_n
= _M_get_previous_node(__bkt
, __n
);
2389 return _M_erase(__bkt
, __prev_n
, __n
);
2392 template<typename _Key
, typename _Value
, typename _Alloc
,
2393 typename _ExtractKey
, typename _Equal
,
2394 typename _Hash
, typename _RangeHash
, typename _Unused
,
2395 typename _RehashPolicy
, typename _Traits
>
2397 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2398 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2399 _M_erase(size_type __bkt
, __node_base_ptr __prev_n
, __node_ptr __n
)
2402 if (__prev_n
== _M_buckets
[__bkt
])
2403 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
2404 __n
->_M_nxt
? _M_bucket_index(*__n
->_M_next()) : 0);
2405 else if (__n
->_M_nxt
)
2407 size_type __next_bkt
= _M_bucket_index(*__n
->_M_next());
2408 if (__next_bkt
!= __bkt
)
2409 _M_buckets
[__next_bkt
] = __prev_n
;
2412 __prev_n
->_M_nxt
= __n
->_M_nxt
;
2413 iterator
__result(__n
->_M_next());
2414 this->_M_deallocate_node(__n
);
2420 template<typename _Key
, typename _Value
, typename _Alloc
,
2421 typename _ExtractKey
, typename _Equal
,
2422 typename _Hash
, typename _RangeHash
, typename _Unused
,
2423 typename _RehashPolicy
, typename _Traits
>
2425 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2426 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2427 _M_erase(true_type
/* __uks */, const key_type
& __k
)
2430 __node_base_ptr __prev_n
;
2433 if (size() <= __small_size_threshold())
2435 __prev_n
= _M_find_before_node(__k
);
2439 // We found a matching node, erase it.
2440 __n
= static_cast<__node_ptr
>(__prev_n
->_M_nxt
);
2441 __bkt
= _M_bucket_index(*__n
);
2445 __hash_code __code
= this->_M_hash_code(__k
);
2446 __bkt
= _M_bucket_index(__code
);
2448 // Look for the node before the first matching node.
2449 __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
2453 // We found a matching node, erase it.
2454 __n
= static_cast<__node_ptr
>(__prev_n
->_M_nxt
);
2457 _M_erase(__bkt
, __prev_n
, __n
);
2461 template<typename _Key
, typename _Value
, typename _Alloc
,
2462 typename _ExtractKey
, typename _Equal
,
2463 typename _Hash
, typename _RangeHash
, typename _Unused
,
2464 typename _RehashPolicy
, typename _Traits
>
2466 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2467 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2468 _M_erase(false_type
/* __uks */, const key_type
& __k
)
2472 __node_base_ptr __prev_n
;
2474 if (size() <= __small_size_threshold())
2476 __prev_n
= _M_find_before_node(__k
);
2480 // We found a matching node, erase it.
2481 __n
= static_cast<__node_ptr
>(__prev_n
->_M_nxt
);
2482 __bkt
= _M_bucket_index(*__n
);
2486 __hash_code __code
= this->_M_hash_code(__k
);
2487 __bkt
= _M_bucket_index(__code
);
2489 // Look for the node before the first matching node.
2490 __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
2494 __n
= static_cast<__node_ptr
>(__prev_n
->_M_nxt
);
2497 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2498 // 526. Is it undefined if a function in the standard changes
2500 // We use one loop to find all matching nodes and another to deallocate
2501 // them so that the key stays valid during the first loop. It might be
2502 // invalidated indirectly when destroying nodes.
2503 __node_ptr __n_last
= __n
->_M_next();
2504 while (__n_last
&& this->_M_node_equals(*__n
, *__n_last
))
2505 __n_last
= __n_last
->_M_next();
2507 std::size_t __n_last_bkt
= __n_last
? _M_bucket_index(*__n_last
) : __bkt
;
2509 // Deallocate nodes.
2510 size_type __result
= 0;
2513 __node_ptr __p
= __n
->_M_next();
2514 this->_M_deallocate_node(__n
);
2518 while (__n
!= __n_last
);
2520 _M_element_count
-= __result
;
2521 if (__prev_n
== _M_buckets
[__bkt
])
2522 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
2523 else if (__n_last_bkt
!= __bkt
)
2524 _M_buckets
[__n_last_bkt
] = __prev_n
;
2525 __prev_n
->_M_nxt
= __n_last
;
2529 template<typename _Key
, typename _Value
, typename _Alloc
,
2530 typename _ExtractKey
, typename _Equal
,
2531 typename _Hash
, typename _RangeHash
, typename _Unused
,
2532 typename _RehashPolicy
, typename _Traits
>
2534 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2535 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2536 erase(const_iterator __first
, const_iterator __last
)
2539 __node_ptr __n
= __first
._M_cur
;
2540 __node_ptr __last_n
= __last
._M_cur
;
2541 if (__n
== __last_n
)
2542 return iterator(__n
);
2544 std::size_t __bkt
= _M_bucket_index(*__n
);
2546 __node_base_ptr __prev_n
= _M_get_previous_node(__bkt
, __n
);
2547 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
2548 std::size_t __n_bkt
= __bkt
;
2553 __node_ptr __tmp
= __n
;
2554 __n
= __n
->_M_next();
2555 this->_M_deallocate_node(__tmp
);
2559 __n_bkt
= _M_bucket_index(*__n
);
2561 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
2562 if (__is_bucket_begin
)
2563 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
2564 if (__n
== __last_n
)
2566 __is_bucket_begin
= true;
2570 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
2571 _M_buckets
[__n_bkt
] = __prev_n
;
2572 __prev_n
->_M_nxt
= __n
;
2573 return iterator(__n
);
2576 template<typename _Key
, typename _Value
, typename _Alloc
,
2577 typename _ExtractKey
, typename _Equal
,
2578 typename _Hash
, typename _RangeHash
, typename _Unused
,
2579 typename _RehashPolicy
, typename _Traits
>
2581 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2582 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2585 this->_M_deallocate_nodes(_M_begin());
2586 std::fill_n(_M_buckets
, _M_bucket_count
, nullptr);
2587 _M_element_count
= 0;
2588 _M_before_begin
._M_nxt
= nullptr;
2591 template<typename _Key
, typename _Value
, typename _Alloc
,
2592 typename _ExtractKey
, typename _Equal
,
2593 typename _Hash
, typename _RangeHash
, typename _Unused
,
2594 typename _RehashPolicy
, typename _Traits
>
2596 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2597 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2598 rehash(size_type __bkt_count
)
2600 __rehash_guard_t
__rehash_guard(_M_rehash_policy
);
2602 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
2604 __bkt_count
= _M_rehash_policy
._M_next_bkt(__bkt_count
);
2606 if (__bkt_count
!= _M_bucket_count
)
2608 _M_rehash(__bkt_count
, __unique_keys
{});
2609 __rehash_guard
._M_guarded_obj
= nullptr;
2613 // Rehash when there is no equivalent elements.
2614 template<typename _Key
, typename _Value
, typename _Alloc
,
2615 typename _ExtractKey
, typename _Equal
,
2616 typename _Hash
, typename _RangeHash
, typename _Unused
,
2617 typename _RehashPolicy
, typename _Traits
>
2619 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2620 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2621 _M_rehash(size_type __bkt_count
, true_type
/* __uks */)
2623 __buckets_ptr __new_buckets
= _M_allocate_buckets(__bkt_count
);
2624 __node_ptr __p
= _M_begin();
2625 _M_before_begin
._M_nxt
= nullptr;
2626 std::size_t __bbegin_bkt
= 0;
2629 __node_ptr __next
= __p
->_M_next();
2631 = __hash_code_base::_M_bucket_index(*__p
, __bkt_count
);
2632 if (!__new_buckets
[__bkt
])
2634 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2635 _M_before_begin
._M_nxt
= __p
;
2636 __new_buckets
[__bkt
] = &_M_before_begin
;
2638 __new_buckets
[__bbegin_bkt
] = __p
;
2639 __bbegin_bkt
= __bkt
;
2643 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2644 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2650 _M_deallocate_buckets();
2651 _M_bucket_count
= __bkt_count
;
2652 _M_buckets
= __new_buckets
;
2655 // Rehash when there can be equivalent elements, preserve their relative
2657 template<typename _Key
, typename _Value
, typename _Alloc
,
2658 typename _ExtractKey
, typename _Equal
,
2659 typename _Hash
, typename _RangeHash
, typename _Unused
,
2660 typename _RehashPolicy
, typename _Traits
>
2662 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2663 _Hash
, _RangeHash
, _Unused
, _RehashPolicy
, _Traits
>::
2664 _M_rehash(size_type __bkt_count
, false_type
/* __uks */)
2666 __buckets_ptr __new_buckets
= _M_allocate_buckets(__bkt_count
);
2667 __node_ptr __p
= _M_begin();
2668 _M_before_begin
._M_nxt
= nullptr;
2669 std::size_t __bbegin_bkt
= 0;
2670 std::size_t __prev_bkt
= 0;
2671 __node_ptr __prev_p
= nullptr;
2672 bool __check_bucket
= false;
2676 __node_ptr __next
= __p
->_M_next();
2678 = __hash_code_base::_M_bucket_index(*__p
, __bkt_count
);
2680 if (__prev_p
&& __prev_bkt
== __bkt
)
2682 // Previous insert was already in this bucket, we insert after
2683 // the previously inserted one to preserve equivalent elements
2685 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2686 __prev_p
->_M_nxt
= __p
;
2688 // Inserting after a node in a bucket require to check that we
2689 // haven't change the bucket last node, in this case next
2690 // bucket containing its before begin node must be updated. We
2691 // schedule a check as soon as we move out of the sequence of
2692 // equivalent nodes to limit the number of checks.
2693 __check_bucket
= true;
2699 // Check if we shall update the next bucket because of
2700 // insertions into __prev_bkt bucket.
2701 if (__prev_p
->_M_nxt
)
2703 std::size_t __next_bkt
2704 = __hash_code_base::_M_bucket_index(
2705 *__prev_p
->_M_next(), __bkt_count
);
2706 if (__next_bkt
!= __prev_bkt
)
2707 __new_buckets
[__next_bkt
] = __prev_p
;
2709 __check_bucket
= false;
2712 if (!__new_buckets
[__bkt
])
2714 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2715 _M_before_begin
._M_nxt
= __p
;
2716 __new_buckets
[__bkt
] = &_M_before_begin
;
2718 __new_buckets
[__bbegin_bkt
] = __p
;
2719 __bbegin_bkt
= __bkt
;
2723 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2724 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2732 if (__check_bucket
&& __prev_p
->_M_nxt
)
2734 std::size_t __next_bkt
2735 = __hash_code_base::_M_bucket_index(*__prev_p
->_M_next(),
2737 if (__next_bkt
!= __prev_bkt
)
2738 __new_buckets
[__next_bkt
] = __prev_p
;
2741 _M_deallocate_buckets();
2742 _M_bucket_count
= __bkt_count
;
2743 _M_buckets
= __new_buckets
;
2746 #if __cplusplus > 201402L
2747 template<typename
, typename
, typename
> class _Hash_merge_helper
{ };
2750 #if __cpp_deduction_guides >= 201606
2751 // Used to constrain deduction guides
2752 template<typename _Hash
>
2753 using _RequireNotAllocatorOrIntegral
2754 = __enable_if_t
<!__or_
<is_integral
<_Hash
>, __is_allocator
<_Hash
>>::value
>;
2758 _GLIBCXX_END_NAMESPACE_VERSION
2761 #endif // _HASHTABLE_H