1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2019 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 #if __cplusplus > 201402L
37 # include <bits/node_handle.h>
40 namespace std
_GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 template<typename _Tp
, typename _Hash
>
46 = __not_
<__and_
<// Do not cache for fast hasher.
47 __is_fast_hash
<_Hash
>,
48 // Mandatory to have erase not throwing.
49 __is_nothrow_invocable
<const _Hash
&, const _Tp
&>>>;
52 * Primary class template _Hashtable.
54 * @ingroup hashtable-detail
56 * @tparam _Value CopyConstructible type.
58 * @tparam _Key CopyConstructible type.
60 * @tparam _Alloc An allocator type
61 * ([lib.allocator.requirements]) whose _Alloc::value_type is
62 * _Value. As a conforming extension, we allow for
63 * _Alloc::value_type != _Value.
65 * @tparam _ExtractKey Function object that takes an object of type
66 * _Value and returns a value of type _Key.
68 * @tparam _Equal Function object that takes two objects of type k
69 * and returns a bool-like value that is true if the two objects
70 * are considered equal.
72 * @tparam _H1 The hash function. A unary function object with
73 * argument type _Key and result type size_t. Return values should
74 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
76 * @tparam _H2 The range-hashing function (in the terminology of
77 * Tavori and Dreizin). A binary function object whose argument
78 * types and result type are all size_t. Given arguments r and N,
79 * the return value is in the range [0, N).
81 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
82 * binary function whose argument types are _Key and size_t and
83 * whose result type is size_t. Given arguments k and N, the
84 * return value is in the range [0, N). Default: hash(k, N) =
85 * h2(h1(k), N). If _Hash is anything other than the default, _H1
86 * and _H2 are ignored.
88 * @tparam _RehashPolicy Policy class with three members, all of
89 * which govern the bucket count. _M_next_bkt(n) returns a bucket
90 * count no smaller than n. _M_bkt_for_elements(n) returns a
91 * bucket count appropriate for an element count of n.
92 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
93 * current bucket count is n_bkt and the current element count is
94 * n_elt, we need to increase the bucket count. If so, returns
95 * make_pair(true, n), where n is the new bucket count. If not,
96 * returns make_pair(false, <anything>)
98 * @tparam _Traits Compile-time class with three boolean
99 * std::integral_constant members: __cache_hash_code, __constant_iterators,
102 * Each _Hashtable data structure has:
104 * - _Bucket[] _M_buckets
105 * - _Hash_node_base _M_before_begin
106 * - size_type _M_bucket_count
107 * - size_type _M_element_count
109 * with _Bucket being _Hash_node* and _Hash_node containing:
111 * - _Hash_node* _M_next
113 * - size_t _M_hash_code if cache_hash_code is true
115 * In terms of Standard containers the hashtable is like the aggregation of:
117 * - std::forward_list<_Node> containing the elements
118 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
120 * The non-empty buckets contain the node before the first node in the
121 * bucket. This design makes it possible to implement something like a
122 * std::forward_list::insert_after on container insertion and
123 * std::forward_list::erase_after on container erase
124 * calls. _M_before_begin is equivalent to
125 * std::forward_list::before_begin. Empty buckets contain
126 * nullptr. Note that one of the non-empty buckets contains
127 * &_M_before_begin which is not a dereferenceable node so the
128 * node pointer in a bucket shall never be dereferenced, only its
131 * Walking through a bucket's nodes requires a check on the hash code to
132 * see if each node is still in the bucket. Such a design assumes a
133 * quite efficient hash functor and is one of the reasons it is
134 * highly advisable to set __cache_hash_code to true.
136 * The container iterators are simply built from nodes. This way
137 * incrementing the iterator is perfectly efficient independent of
138 * how many empty buckets there are in the container.
140 * On insert we compute the element's hash code and use it to find the
141 * bucket index. If the element must be inserted in an empty bucket
142 * we add it at the beginning of the singly linked list and make the
143 * bucket point to _M_before_begin. The bucket that used to point to
144 * _M_before_begin, if any, is updated to point to its new before
147 * On erase, the simple iterator design requires using the hash
148 * functor to get the index of the bucket to update. For this
149 * reason, when __cache_hash_code is set to false the hash functor must
150 * not throw and this is enforced by a static assertion.
152 * Functionality is implemented by decomposition into base classes,
153 * where the derived _Hashtable class is used in _Map_base,
154 * _Insert, _Rehash_base, and _Equality base classes to access the
155 * "this" pointer. _Hashtable_base is used in the base classes as a
156 * non-recursive, fully-completed-type so that detailed nested type
157 * information, such as iterator type and node type, can be
158 * used. This is similar to the "Curiously Recurring Template
159 * Pattern" (CRTP) technique, but uses a reconstructed, not
160 * explicitly passed, template pattern.
162 * Base class templates are:
163 * - __detail::_Hashtable_base
164 * - __detail::_Map_base
165 * - __detail::_Insert
166 * - __detail::_Rehash_base
167 * - __detail::_Equality
169 template<typename _Key
, typename _Value
, typename _Alloc
,
170 typename _ExtractKey
, typename _Equal
,
171 typename _H1
, typename _H2
, typename _Hash
,
172 typename _RehashPolicy
, typename _Traits
>
174 : public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
175 _H1
, _H2
, _Hash
, _Traits
>,
176 public __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
177 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
178 public __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
179 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
180 public __detail::_Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
181 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
182 public __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
183 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
184 private __detail::_Hashtable_alloc
<
185 __alloc_rebind
<_Alloc
,
186 __detail::_Hash_node
<_Value
,
187 _Traits::__hash_cached::value
>>>
189 static_assert(is_same
<typename remove_cv
<_Value
>::type
, _Value
>::value
,
190 "unordered container must have a non-const, non-volatile value_type");
191 #ifdef __STRICT_ANSI__
192 static_assert(is_same
<typename
_Alloc::value_type
, _Value
>{},
193 "unordered container must have the same value_type as its allocator");
195 static_assert(__is_invocable
<const _H1
&, const _Key
&>{},
196 "hash function must be invocable with an argument of key type");
197 static_assert(__is_invocable
<const _Equal
&, const _Key
&, const _Key
&>{},
198 "key equality predicate must be invocable with two arguments of "
201 using __traits_type
= _Traits
;
202 using __hash_cached
= typename
__traits_type::__hash_cached
;
203 using __node_type
= __detail::_Hash_node
<_Value
, __hash_cached::value
>;
204 using __node_alloc_type
= __alloc_rebind
<_Alloc
, __node_type
>;
206 using __hashtable_alloc
= __detail::_Hashtable_alloc
<__node_alloc_type
>;
208 using __value_alloc_traits
=
209 typename
__hashtable_alloc::__value_alloc_traits
;
210 using __node_alloc_traits
=
211 typename
__hashtable_alloc::__node_alloc_traits
;
212 using __node_base
= typename
__hashtable_alloc::__node_base
;
213 using __bucket_type
= typename
__hashtable_alloc::__bucket_type
;
216 typedef _Key key_type
;
217 typedef _Value value_type
;
218 typedef _Alloc allocator_type
;
219 typedef _Equal key_equal
;
221 // mapped_type, if present, comes from _Map_base.
222 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
223 typedef typename
__value_alloc_traits::pointer pointer
;
224 typedef typename
__value_alloc_traits::const_pointer const_pointer
;
225 typedef value_type
& reference
;
226 typedef const value_type
& const_reference
;
229 using __rehash_type
= _RehashPolicy
;
230 using __rehash_state
= typename
__rehash_type::_State
;
232 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
233 using __unique_keys
= typename
__traits_type::__unique_keys
;
235 using __key_extract
= typename
std::conditional
<
236 __constant_iterators::value
,
238 __detail::_Select1st
>::type
;
240 using __hashtable_base
= __detail::
241 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
242 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
244 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
245 using __hash_code
= typename
__hashtable_base::__hash_code
;
246 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
248 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
249 _Equal
, _H1
, _H2
, _Hash
,
250 _RehashPolicy
, _Traits
>;
252 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
255 _RehashPolicy
, _Traits
>;
257 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
258 _Equal
, _H1
, _H2
, _Hash
,
259 _RehashPolicy
, _Traits
>;
261 using __reuse_or_alloc_node_type
=
262 __detail::_ReuseOrAllocNode
<__node_alloc_type
>;
264 // Metaprogramming for picking apart hash caching.
265 template<typename _Cond
>
266 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
268 template<typename _Cond
>
269 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
271 // Compile-time diagnostics.
273 // _Hash_code_base has everything protected, so use this derived type to
275 struct __hash_code_base_access
: __hash_code_base
276 { using __hash_code_base::_M_bucket_index
; };
278 // Getting a bucket index from a node shall not throw because it is used
279 // in methods (erase, swap...) that shall not throw.
280 static_assert(noexcept(declval
<const __hash_code_base_access
&>()
281 ._M_bucket_index((const __node_type
*)nullptr,
283 "Cache the hash code or qualify your functors involved"
284 " in hash code and bucket index computation with noexcept");
286 // Following two static assertions are necessary to guarantee
287 // that local_iterator will be default constructible.
289 // When hash codes are cached local iterator inherits from H2 functor
290 // which must then be default constructible.
291 static_assert(__if_hash_cached
<is_default_constructible
<_H2
>>::value
,
292 "Functor used to map hash code to bucket index"
293 " must be default constructible");
295 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
296 typename _ExtractKeya
, typename _Equala
,
297 typename _H1a
, typename _H2a
, typename _Hasha
,
298 typename _RehashPolicya
, typename _Traitsa
,
300 friend struct __detail::_Map_base
;
302 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
303 typename _ExtractKeya
, typename _Equala
,
304 typename _H1a
, typename _H2a
, typename _Hasha
,
305 typename _RehashPolicya
, typename _Traitsa
>
306 friend struct __detail::_Insert_base
;
308 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
309 typename _ExtractKeya
, typename _Equala
,
310 typename _H1a
, typename _H2a
, typename _Hasha
,
311 typename _RehashPolicya
, typename _Traitsa
,
312 bool _Constant_iteratorsa
>
313 friend struct __detail::_Insert
;
316 using size_type
= typename
__hashtable_base::size_type
;
317 using difference_type
= typename
__hashtable_base::difference_type
;
319 using iterator
= typename
__hashtable_base::iterator
;
320 using const_iterator
= typename
__hashtable_base::const_iterator
;
322 using local_iterator
= typename
__hashtable_base::local_iterator
;
323 using const_local_iterator
= typename
__hashtable_base::
324 const_local_iterator
;
326 #if __cplusplus > 201402L
327 using node_type
= _Node_handle
<_Key
, _Value
, __node_alloc_type
>;
328 using insert_return_type
= _Node_insert_return
<iterator
, node_type
>;
332 __bucket_type
* _M_buckets
= &_M_single_bucket
;
333 size_type _M_bucket_count
= 1;
334 __node_base _M_before_begin
;
335 size_type _M_element_count
= 0;
336 _RehashPolicy _M_rehash_policy
;
338 // A single bucket used when only need for 1 bucket. Especially
339 // interesting in move semantic to leave hashtable with only 1 buckets
340 // which is not allocated so that we can have those operations noexcept
342 // Note that we can't leave hashtable with 0 bucket without adding
343 // numerous checks in the code to avoid 0 modulus.
344 __bucket_type _M_single_bucket
= nullptr;
347 _M_uses_single_bucket(__bucket_type
* __bkts
) const
348 { return __builtin_expect(__bkts
== &_M_single_bucket
, false); }
351 _M_uses_single_bucket() const
352 { return _M_uses_single_bucket(_M_buckets
); }
355 _M_base_alloc() { return *this; }
358 _M_allocate_buckets(size_type __n
)
360 if (__builtin_expect(__n
== 1, false))
362 _M_single_bucket
= nullptr;
363 return &_M_single_bucket
;
366 return __hashtable_alloc::_M_allocate_buckets(__n
);
370 _M_deallocate_buckets(__bucket_type
* __bkts
, size_type __n
)
372 if (_M_uses_single_bucket(__bkts
))
375 __hashtable_alloc::_M_deallocate_buckets(__bkts
, __n
);
379 _M_deallocate_buckets()
380 { _M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
382 // Gets bucket begin, deals with the fact that non-empty buckets contain
383 // their before begin node.
385 _M_bucket_begin(size_type __bkt
) const;
389 { return static_cast<__node_type
*>(_M_before_begin
._M_nxt
); }
391 // Assign *this using another _Hashtable instance. Either elements
392 // are copy or move depends on the _NodeGenerator.
393 template<typename _Ht
, typename _NodeGenerator
>
395 _M_assign_elements(_Ht
&&, const _NodeGenerator
&);
397 template<typename _NodeGenerator
>
399 _M_assign(const _Hashtable
&, const _NodeGenerator
&);
402 _M_move_assign(_Hashtable
&&, std::true_type
);
405 _M_move_assign(_Hashtable
&&, std::false_type
);
410 _Hashtable(const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
411 const _Equal
& __eq
, const _ExtractKey
& __exk
,
412 const allocator_type
& __a
)
413 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
414 __hashtable_alloc(__node_alloc_type(__a
))
418 // Constructor, destructor, assignment, swap
419 _Hashtable() = default;
420 _Hashtable(size_type __bucket_hint
,
421 const _H1
&, const _H2
&, const _Hash
&,
422 const _Equal
&, const _ExtractKey
&,
423 const allocator_type
&);
425 template<typename _InputIterator
>
426 _Hashtable(_InputIterator __first
, _InputIterator __last
,
427 size_type __bucket_hint
,
428 const _H1
&, const _H2
&, const _Hash
&,
429 const _Equal
&, const _ExtractKey
&,
430 const allocator_type
&);
432 _Hashtable(const _Hashtable
&);
434 _Hashtable(_Hashtable
&&) noexcept
;
436 _Hashtable(const _Hashtable
&, const allocator_type
&);
438 _Hashtable(_Hashtable
&&, const allocator_type
&);
440 // Use delegating constructors.
442 _Hashtable(const allocator_type
& __a
)
443 : __hashtable_alloc(__node_alloc_type(__a
))
447 _Hashtable(size_type __n
,
448 const _H1
& __hf
= _H1(),
449 const key_equal
& __eql
= key_equal(),
450 const allocator_type
& __a
= allocator_type())
451 : _Hashtable(__n
, __hf
, _H2(), _Hash(), __eql
,
452 __key_extract(), __a
)
455 template<typename _InputIterator
>
456 _Hashtable(_InputIterator __f
, _InputIterator __l
,
458 const _H1
& __hf
= _H1(),
459 const key_equal
& __eql
= key_equal(),
460 const allocator_type
& __a
= allocator_type())
461 : _Hashtable(__f
, __l
, __n
, __hf
, _H2(), _Hash(), __eql
,
462 __key_extract(), __a
)
465 _Hashtable(initializer_list
<value_type
> __l
,
467 const _H1
& __hf
= _H1(),
468 const key_equal
& __eql
= key_equal(),
469 const allocator_type
& __a
= allocator_type())
470 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
, _H2(), _Hash(), __eql
,
471 __key_extract(), __a
)
475 operator=(const _Hashtable
& __ht
);
478 operator=(_Hashtable
&& __ht
)
479 noexcept(__node_alloc_traits::_S_nothrow_move()
480 && is_nothrow_move_assignable
<_H1
>::value
481 && is_nothrow_move_assignable
<_Equal
>::value
)
483 constexpr bool __move_storage
=
484 __node_alloc_traits::_S_propagate_on_move_assign()
485 || __node_alloc_traits::_S_always_equal();
486 _M_move_assign(std::move(__ht
), __bool_constant
<__move_storage
>());
491 operator=(initializer_list
<value_type
> __l
)
493 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
494 _M_before_begin
._M_nxt
= nullptr;
496 this->_M_insert_range(__l
.begin(), __l
.end(), __roan
, __unique_keys());
500 ~_Hashtable() noexcept
;
504 noexcept(__and_
<__is_nothrow_swappable
<_H1
>,
505 __is_nothrow_swappable
<_Equal
>>::value
);
507 // Basic container operations
510 { return iterator(_M_begin()); }
513 begin() const noexcept
514 { return const_iterator(_M_begin()); }
518 { return iterator(nullptr); }
522 { return const_iterator(nullptr); }
525 cbegin() const noexcept
526 { return const_iterator(_M_begin()); }
529 cend() const noexcept
530 { return const_iterator(nullptr); }
533 size() const noexcept
534 { return _M_element_count
; }
536 _GLIBCXX_NODISCARD
bool
537 empty() const noexcept
538 { return size() == 0; }
541 get_allocator() const noexcept
542 { return allocator_type(this->_M_node_allocator()); }
545 max_size() const noexcept
546 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
551 { return this->_M_eq(); }
553 // hash_function, if present, comes from _Hash_code_base.
557 bucket_count() const noexcept
558 { return _M_bucket_count
; }
561 max_bucket_count() const noexcept
562 { return max_size(); }
565 bucket_size(size_type __n
) const
566 { return std::distance(begin(__n
), end(__n
)); }
569 bucket(const key_type
& __k
) const
570 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
575 return local_iterator(*this, _M_bucket_begin(__n
),
576 __n
, _M_bucket_count
);
581 { return local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
584 begin(size_type __n
) const
586 return const_local_iterator(*this, _M_bucket_begin(__n
),
587 __n
, _M_bucket_count
);
591 end(size_type __n
) const
592 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
596 cbegin(size_type __n
) const
598 return const_local_iterator(*this, _M_bucket_begin(__n
),
599 __n
, _M_bucket_count
);
603 cend(size_type __n
) const
604 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
607 load_factor() const noexcept
609 return static_cast<float>(size()) / static_cast<float>(bucket_count());
612 // max_load_factor, if present, comes from _Rehash_base.
614 // Generalization of max_load_factor. Extension, not found in
615 // TR1. Only useful if _RehashPolicy is something other than
618 __rehash_policy() const
619 { return _M_rehash_policy
; }
622 __rehash_policy(const _RehashPolicy
& __pol
)
623 { _M_rehash_policy
= __pol
; }
627 find(const key_type
& __k
);
630 find(const key_type
& __k
) const;
633 count(const key_type
& __k
) const;
635 std::pair
<iterator
, iterator
>
636 equal_range(const key_type
& __k
);
638 std::pair
<const_iterator
, const_iterator
>
639 equal_range(const key_type
& __k
) const;
642 // Bucket index computation helpers.
644 _M_bucket_index(__node_type
* __n
) const noexcept
645 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
648 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
649 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
651 // Find and insert helper functions and types
652 // Find the node before the one matching the criteria.
654 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
657 _M_find_node(size_type __bkt
, const key_type
& __key
,
658 __hash_code __c
) const
660 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
662 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
666 // Insert a node at the beginning of a bucket.
668 _M_insert_bucket_begin(size_type
, __node_type
*);
670 // Remove the bucket first node
672 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
673 size_type __next_bkt
);
675 // Get the node before __n in the bucket __bkt
677 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
679 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
680 // no element with its key already present). Take ownership of the node,
681 // deallocate it on exception.
683 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
684 __node_type
* __n
, size_type __n_elt
= 1);
686 // Insert node with hash code __code. Take ownership of the node,
687 // deallocate it on exception.
689 _M_insert_multi_node(__node_type
* __hint
,
690 __hash_code __code
, __node_type
* __n
);
692 template<typename
... _Args
>
693 std::pair
<iterator
, bool>
694 _M_emplace(std::true_type
, _Args
&&... __args
);
696 template<typename
... _Args
>
698 _M_emplace(std::false_type __uk
, _Args
&&... __args
)
699 { return _M_emplace(cend(), __uk
, std::forward
<_Args
>(__args
)...); }
701 // Emplace with hint, useless when keys are unique.
702 template<typename
... _Args
>
704 _M_emplace(const_iterator
, std::true_type __uk
, _Args
&&... __args
)
705 { return _M_emplace(__uk
, std::forward
<_Args
>(__args
)...).first
; }
707 template<typename
... _Args
>
709 _M_emplace(const_iterator
, std::false_type
, _Args
&&... __args
);
711 template<typename _Arg
, typename _NodeGenerator
>
712 std::pair
<iterator
, bool>
713 _M_insert(_Arg
&&, const _NodeGenerator
&, true_type
, size_type
= 1);
715 template<typename _Arg
, typename _NodeGenerator
>
717 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
720 return _M_insert(cend(), std::forward
<_Arg
>(__arg
), __node_gen
,
724 // Insert with hint, not used when keys are unique.
725 template<typename _Arg
, typename _NodeGenerator
>
727 _M_insert(const_iterator
, _Arg
&& __arg
,
728 const _NodeGenerator
& __node_gen
, true_type __uk
)
731 _M_insert(std::forward
<_Arg
>(__arg
), __node_gen
, __uk
).first
;
734 // Insert with hint when keys are not unique.
735 template<typename _Arg
, typename _NodeGenerator
>
737 _M_insert(const_iterator
, _Arg
&&,
738 const _NodeGenerator
&, false_type
);
741 _M_erase(std::true_type
, const key_type
&);
744 _M_erase(std::false_type
, const key_type
&);
747 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
751 template<typename
... _Args
>
753 emplace(_Args
&&... __args
)
754 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
756 template<typename
... _Args
>
758 emplace_hint(const_iterator __hint
, _Args
&&... __args
)
760 return _M_emplace(__hint
, __unique_keys(),
761 std::forward
<_Args
>(__args
)...);
764 // Insert member functions via inheritance.
768 erase(const_iterator
);
773 { return erase(const_iterator(__it
)); }
776 erase(const key_type
& __k
)
777 { return _M_erase(__unique_keys(), __k
); }
780 erase(const_iterator
, const_iterator
);
785 // Set number of buckets to be appropriate for container of n element.
786 void rehash(size_type __n
);
789 // reserve, if present, comes from _Rehash_base.
791 #if __cplusplus > 201402L
792 /// Re-insert an extracted node into a container with unique keys.
794 _M_reinsert_node(node_type
&& __nh
)
796 insert_return_type __ret
;
798 __ret
.position
= end();
801 __glibcxx_assert(get_allocator() == __nh
.get_allocator());
803 const key_type
& __k
= __nh
._M_key();
804 __hash_code __code
= this->_M_hash_code(__k
);
805 size_type __bkt
= _M_bucket_index(__k
, __code
);
806 if (__node_type
* __n
= _M_find_node(__bkt
, __k
, __code
))
808 __ret
.node
= std::move(__nh
);
809 __ret
.position
= iterator(__n
);
810 __ret
.inserted
= false;
815 = _M_insert_unique_node(__bkt
, __code
, __nh
._M_ptr
);
816 __nh
._M_ptr
= nullptr;
817 __ret
.inserted
= true;
823 /// Re-insert an extracted node into a container with equivalent keys.
825 _M_reinsert_node_multi(const_iterator __hint
, node_type
&& __nh
)
832 __glibcxx_assert(get_allocator() == __nh
.get_allocator());
834 auto __code
= this->_M_hash_code(__nh
._M_key());
835 auto __node
= std::exchange(__nh
._M_ptr
, nullptr);
836 // FIXME: this deallocates the node on exception.
837 __ret
= _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
844 extract(const_iterator __pos
)
846 __node_type
* __n
= __pos
._M_cur
;
847 size_t __bkt
= _M_bucket_index(__n
);
849 // Look for previous node to unlink it from the erased one, this
850 // is why we need buckets to contain the before begin to make
852 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
854 if (__prev_n
== _M_buckets
[__bkt
])
855 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
856 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
857 else if (__n
->_M_nxt
)
859 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
860 if (__next_bkt
!= __bkt
)
861 _M_buckets
[__next_bkt
] = __prev_n
;
864 __prev_n
->_M_nxt
= __n
->_M_nxt
;
865 __n
->_M_nxt
= nullptr;
867 return { __n
, this->_M_node_allocator() };
872 extract(const _Key
& __k
)
875 auto __pos
= find(__k
);
877 __nh
= extract(const_iterator(__pos
));
881 /// Merge from a compatible container into one with unique keys.
882 template<typename _Compatible_Hashtable
>
884 _M_merge_unique(_Compatible_Hashtable
& __src
) noexcept
886 static_assert(is_same_v
<typename
_Compatible_Hashtable::node_type
,
887 node_type
>, "Node types are compatible");
888 __glibcxx_assert(get_allocator() == __src
.get_allocator());
890 auto __n_elt
= __src
.size();
891 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
894 const key_type
& __k
= this->_M_extract()(__pos
._M_cur
->_M_v());
895 __hash_code __code
= this->_M_hash_code(__k
);
896 size_type __bkt
= _M_bucket_index(__k
, __code
);
897 if (_M_find_node(__bkt
, __k
, __code
) == nullptr)
899 auto __nh
= __src
.extract(__pos
);
900 _M_insert_unique_node(__bkt
, __code
, __nh
._M_ptr
, __n_elt
);
901 __nh
._M_ptr
= nullptr;
904 else if (__n_elt
!= 1)
909 /// Merge from a compatible container into one with equivalent keys.
910 template<typename _Compatible_Hashtable
>
912 _M_merge_multi(_Compatible_Hashtable
& __src
) noexcept
914 static_assert(is_same_v
<typename
_Compatible_Hashtable::node_type
,
915 node_type
>, "Node types are compatible");
916 __glibcxx_assert(get_allocator() == __src
.get_allocator());
918 this->reserve(size() + __src
.size());
919 for (auto __i
= __src
.begin(), __end
= __src
.end(); __i
!= __end
;)
920 _M_reinsert_node_multi(cend(), __src
.extract(__i
++));
925 // Helper rehash method used when keys are unique.
926 void _M_rehash_aux(size_type __n
, std::true_type
);
928 // Helper rehash method used when keys can be non-unique.
929 void _M_rehash_aux(size_type __n
, std::false_type
);
931 // Unconditionally change size of bucket array to n, restore
932 // hash policy state to __state on exception.
933 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
937 // Definitions of class template _Hashtable's out-of-line member functions.
938 template<typename _Key
, typename _Value
,
939 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
940 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
943 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
944 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
945 _M_bucket_begin(size_type __bkt
) const
948 __node_base
* __n
= _M_buckets
[__bkt
];
949 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
952 template<typename _Key
, typename _Value
,
953 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
954 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
956 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
957 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
958 _Hashtable(size_type __bucket_hint
,
959 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
960 const _Equal
& __eq
, const _ExtractKey
& __exk
,
961 const allocator_type
& __a
)
962 : _Hashtable(__h1
, __h2
, __h
, __eq
, __exk
, __a
)
964 auto __bkt
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
965 if (__bkt
> _M_bucket_count
)
967 _M_buckets
= _M_allocate_buckets(__bkt
);
968 _M_bucket_count
= __bkt
;
972 template<typename _Key
, typename _Value
,
973 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
974 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
976 template<typename _InputIterator
>
977 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
978 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
979 _Hashtable(_InputIterator __f
, _InputIterator __l
,
980 size_type __bucket_hint
,
981 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
982 const _Equal
& __eq
, const _ExtractKey
& __exk
,
983 const allocator_type
& __a
)
984 : _Hashtable(__h1
, __h2
, __h
, __eq
, __exk
, __a
)
986 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
988 _M_rehash_policy
._M_next_bkt(
989 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
992 if (__bkt_count
> _M_bucket_count
)
994 _M_buckets
= _M_allocate_buckets(__bkt_count
);
995 _M_bucket_count
= __bkt_count
;
998 for (; __f
!= __l
; ++__f
)
1002 template<typename _Key
, typename _Value
,
1003 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1004 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1007 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1008 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1009 operator=(const _Hashtable
& __ht
)
1015 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1017 auto& __this_alloc
= this->_M_node_allocator();
1018 auto& __that_alloc
= __ht
._M_node_allocator();
1019 if (!__node_alloc_traits::_S_always_equal()
1020 && __this_alloc
!= __that_alloc
)
1022 // Replacement allocator cannot free existing storage.
1023 this->_M_deallocate_nodes(_M_begin());
1024 _M_before_begin
._M_nxt
= nullptr;
1025 _M_deallocate_buckets();
1026 _M_buckets
= nullptr;
1027 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1028 __hashtable_base::operator=(__ht
);
1029 _M_bucket_count
= __ht
._M_bucket_count
;
1030 _M_element_count
= __ht
._M_element_count
;
1031 _M_rehash_policy
= __ht
._M_rehash_policy
;
1035 [this](const __node_type
* __n
)
1036 { return this->_M_allocate_node(__n
->_M_v()); });
1040 // _M_assign took care of deallocating all memory. Now we
1041 // must make sure this instance remains in a usable state.
1043 __throw_exception_again
;
1047 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1050 // Reuse allocated buckets and nodes.
1051 _M_assign_elements(__ht
,
1052 [](const __reuse_or_alloc_node_type
& __roan
, const __node_type
* __n
)
1053 { return __roan(__n
->_M_v()); });
1057 template<typename _Key
, typename _Value
,
1058 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1059 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1061 template<typename _Ht
, typename _NodeGenerator
>
1063 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1064 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1065 _M_assign_elements(_Ht
&& __ht
, const _NodeGenerator
& __node_gen
)
1067 __bucket_type
* __former_buckets
= nullptr;
1068 std::size_t __former_bucket_count
= _M_bucket_count
;
1069 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1071 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1073 __former_buckets
= _M_buckets
;
1074 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
1075 _M_bucket_count
= __ht
._M_bucket_count
;
1078 __builtin_memset(_M_buckets
, 0,
1079 _M_bucket_count
* sizeof(__bucket_type
));
1083 __hashtable_base::operator=(std::forward
<_Ht
>(__ht
));
1084 _M_element_count
= __ht
._M_element_count
;
1085 _M_rehash_policy
= __ht
._M_rehash_policy
;
1086 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
1087 _M_before_begin
._M_nxt
= nullptr;
1089 [&__node_gen
, &__roan
](__node_type
* __n
)
1090 { return __node_gen(__roan
, __n
); });
1091 if (__former_buckets
)
1092 _M_deallocate_buckets(__former_buckets
, __former_bucket_count
);
1096 if (__former_buckets
)
1098 // Restore previous buckets.
1099 _M_deallocate_buckets();
1100 _M_rehash_policy
._M_reset(__former_state
);
1101 _M_buckets
= __former_buckets
;
1102 _M_bucket_count
= __former_bucket_count
;
1104 __builtin_memset(_M_buckets
, 0,
1105 _M_bucket_count
* sizeof(__bucket_type
));
1106 __throw_exception_again
;
1110 template<typename _Key
, typename _Value
,
1111 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1112 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1114 template<typename _NodeGenerator
>
1116 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1117 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1118 _M_assign(const _Hashtable
& __ht
, const _NodeGenerator
& __node_gen
)
1120 __bucket_type
* __buckets
= nullptr;
1122 _M_buckets
= __buckets
= _M_allocate_buckets(_M_bucket_count
);
1126 if (!__ht
._M_before_begin
._M_nxt
)
1129 // First deal with the special first node pointed to by
1131 __node_type
* __ht_n
= __ht
._M_begin();
1132 __node_type
* __this_n
= __node_gen(__ht_n
);
1133 this->_M_copy_code(__this_n
, __ht_n
);
1134 _M_before_begin
._M_nxt
= __this_n
;
1135 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin
;
1137 // Then deal with other nodes.
1138 __node_base
* __prev_n
= __this_n
;
1139 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
1141 __this_n
= __node_gen(__ht_n
);
1142 __prev_n
->_M_nxt
= __this_n
;
1143 this->_M_copy_code(__this_n
, __ht_n
);
1144 size_type __bkt
= _M_bucket_index(__this_n
);
1145 if (!_M_buckets
[__bkt
])
1146 _M_buckets
[__bkt
] = __prev_n
;
1147 __prev_n
= __this_n
;
1154 _M_deallocate_buckets();
1155 __throw_exception_again
;
1159 template<typename _Key
, typename _Value
,
1160 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1161 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1164 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1165 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1168 _M_rehash_policy
._M_reset();
1169 _M_bucket_count
= 1;
1170 _M_single_bucket
= nullptr;
1171 _M_buckets
= &_M_single_bucket
;
1172 _M_before_begin
._M_nxt
= nullptr;
1173 _M_element_count
= 0;
1176 template<typename _Key
, typename _Value
,
1177 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1178 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1181 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1182 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1183 _M_move_assign(_Hashtable
&& __ht
, std::true_type
)
1185 this->_M_deallocate_nodes(_M_begin());
1186 _M_deallocate_buckets();
1187 __hashtable_base::operator=(std::move(__ht
));
1188 _M_rehash_policy
= __ht
._M_rehash_policy
;
1189 if (!__ht
._M_uses_single_bucket())
1190 _M_buckets
= __ht
._M_buckets
;
1193 _M_buckets
= &_M_single_bucket
;
1194 _M_single_bucket
= __ht
._M_single_bucket
;
1196 _M_bucket_count
= __ht
._M_bucket_count
;
1197 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1198 _M_element_count
= __ht
._M_element_count
;
1199 std::__alloc_on_move(this->_M_node_allocator(), __ht
._M_node_allocator());
1201 // Fix buckets containing the _M_before_begin pointers that can't be
1204 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1208 template<typename _Key
, typename _Value
,
1209 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1210 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1213 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1214 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1215 _M_move_assign(_Hashtable
&& __ht
, std::false_type
)
1217 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1218 _M_move_assign(std::move(__ht
), std::true_type());
1221 // Can't move memory, move elements then.
1222 _M_assign_elements(std::move(__ht
),
1223 [](const __reuse_or_alloc_node_type
& __roan
, __node_type
* __n
)
1224 { return __roan(std::move_if_noexcept(__n
->_M_v())); });
1229 template<typename _Key
, typename _Value
,
1230 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1231 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1233 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1234 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1235 _Hashtable(const _Hashtable
& __ht
)
1236 : __hashtable_base(__ht
),
1238 __rehash_base(__ht
),
1240 __node_alloc_traits::_S_select_on_copy(__ht
._M_node_allocator())),
1241 _M_buckets(nullptr),
1242 _M_bucket_count(__ht
._M_bucket_count
),
1243 _M_element_count(__ht
._M_element_count
),
1244 _M_rehash_policy(__ht
._M_rehash_policy
)
1247 [this](const __node_type
* __n
)
1248 { return this->_M_allocate_node(__n
->_M_v()); });
1251 template<typename _Key
, typename _Value
,
1252 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1253 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1255 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1256 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1257 _Hashtable(_Hashtable
&& __ht
) noexcept
1258 : __hashtable_base(__ht
),
1260 __rehash_base(__ht
),
1261 __hashtable_alloc(std::move(__ht
._M_base_alloc())),
1262 _M_buckets(__ht
._M_buckets
),
1263 _M_bucket_count(__ht
._M_bucket_count
),
1264 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
1265 _M_element_count(__ht
._M_element_count
),
1266 _M_rehash_policy(__ht
._M_rehash_policy
)
1268 // Update, if necessary, buckets if __ht is using its single bucket.
1269 if (__ht
._M_uses_single_bucket())
1271 _M_buckets
= &_M_single_bucket
;
1272 _M_single_bucket
= __ht
._M_single_bucket
;
1275 // Update, if necessary, bucket pointing to before begin that hasn't
1278 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1283 template<typename _Key
, typename _Value
,
1284 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1285 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1287 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1288 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1289 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1290 : __hashtable_base(__ht
),
1292 __rehash_base(__ht
),
1293 __hashtable_alloc(__node_alloc_type(__a
)),
1295 _M_bucket_count(__ht
._M_bucket_count
),
1296 _M_element_count(__ht
._M_element_count
),
1297 _M_rehash_policy(__ht
._M_rehash_policy
)
1300 [this](const __node_type
* __n
)
1301 { return this->_M_allocate_node(__n
->_M_v()); });
1304 template<typename _Key
, typename _Value
,
1305 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1306 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1308 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1309 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1310 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
1311 : __hashtable_base(__ht
),
1313 __rehash_base(__ht
),
1314 __hashtable_alloc(__node_alloc_type(__a
)),
1315 _M_buckets(nullptr),
1316 _M_bucket_count(__ht
._M_bucket_count
),
1317 _M_element_count(__ht
._M_element_count
),
1318 _M_rehash_policy(__ht
._M_rehash_policy
)
1320 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1322 if (__ht
._M_uses_single_bucket())
1324 _M_buckets
= &_M_single_bucket
;
1325 _M_single_bucket
= __ht
._M_single_bucket
;
1328 _M_buckets
= __ht
._M_buckets
;
1330 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1331 // Update, if necessary, bucket pointing to before begin that hasn't
1334 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1340 [this](__node_type
* __n
)
1342 return this->_M_allocate_node(
1343 std::move_if_noexcept(__n
->_M_v()));
1349 template<typename _Key
, typename _Value
,
1350 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1351 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1353 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1354 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1355 ~_Hashtable() noexcept
1358 _M_deallocate_buckets();
1361 template<typename _Key
, typename _Value
,
1362 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1363 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1366 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1367 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1368 swap(_Hashtable
& __x
)
1369 noexcept(__and_
<__is_nothrow_swappable
<_H1
>,
1370 __is_nothrow_swappable
<_Equal
>>::value
)
1372 // The only base class with member variables is hash_code_base.
1373 // We define _Hash_code_base::_M_swap because different
1374 // specializations have different members.
1377 std::__alloc_on_swap(this->_M_node_allocator(), __x
._M_node_allocator());
1378 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1380 // Deal properly with potentially moved instances.
1381 if (this->_M_uses_single_bucket())
1383 if (!__x
._M_uses_single_bucket())
1385 _M_buckets
= __x
._M_buckets
;
1386 __x
._M_buckets
= &__x
._M_single_bucket
;
1389 else if (__x
._M_uses_single_bucket())
1391 __x
._M_buckets
= _M_buckets
;
1392 _M_buckets
= &_M_single_bucket
;
1395 std::swap(_M_buckets
, __x
._M_buckets
);
1397 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1398 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
1399 std::swap(_M_element_count
, __x
._M_element_count
);
1400 std::swap(_M_single_bucket
, __x
._M_single_bucket
);
1402 // Fix buckets containing the _M_before_begin pointers that can't be
1405 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1408 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
1409 = &__x
._M_before_begin
;
1412 template<typename _Key
, typename _Value
,
1413 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1414 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1417 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1418 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1419 find(const key_type
& __k
)
1422 __hash_code __code
= this->_M_hash_code(__k
);
1423 std::size_t __n
= _M_bucket_index(__k
, __code
);
1424 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1425 return __p
? iterator(__p
) : end();
1428 template<typename _Key
, typename _Value
,
1429 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1430 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1433 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1434 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1435 find(const key_type
& __k
) const
1438 __hash_code __code
= this->_M_hash_code(__k
);
1439 std::size_t __n
= _M_bucket_index(__k
, __code
);
1440 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1441 return __p
? const_iterator(__p
) : end();
1444 template<typename _Key
, typename _Value
,
1445 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1446 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1449 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1450 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1451 count(const key_type
& __k
) const
1454 __hash_code __code
= this->_M_hash_code(__k
);
1455 std::size_t __n
= _M_bucket_index(__k
, __code
);
1456 __node_type
* __p
= _M_bucket_begin(__n
);
1460 std::size_t __result
= 0;
1461 for (;; __p
= __p
->_M_next())
1463 if (this->_M_equals(__k
, __code
, __p
))
1466 // All equivalent values are next to each other, if we
1467 // found a non-equivalent value after an equivalent one it
1468 // means that we won't find any new equivalent value.
1470 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1476 template<typename _Key
, typename _Value
,
1477 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1478 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1481 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1482 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1483 equal_range(const key_type
& __k
)
1484 -> pair
<iterator
, iterator
>
1486 __hash_code __code
= this->_M_hash_code(__k
);
1487 std::size_t __n
= _M_bucket_index(__k
, __code
);
1488 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1492 __node_type
* __p1
= __p
->_M_next();
1493 while (__p1
&& _M_bucket_index(__p1
) == __n
1494 && this->_M_equals(__k
, __code
, __p1
))
1495 __p1
= __p1
->_M_next();
1497 return std::make_pair(iterator(__p
), iterator(__p1
));
1500 return std::make_pair(end(), end());
1503 template<typename _Key
, typename _Value
,
1504 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1505 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1508 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1509 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1510 equal_range(const key_type
& __k
) const
1511 -> pair
<const_iterator
, const_iterator
>
1513 __hash_code __code
= this->_M_hash_code(__k
);
1514 std::size_t __n
= _M_bucket_index(__k
, __code
);
1515 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1519 __node_type
* __p1
= __p
->_M_next();
1520 while (__p1
&& _M_bucket_index(__p1
) == __n
1521 && this->_M_equals(__k
, __code
, __p1
))
1522 __p1
= __p1
->_M_next();
1524 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1527 return std::make_pair(end(), end());
1530 // Find the node whose key compares equal to k in the bucket n.
1531 // Return nullptr if no node is found.
1532 template<typename _Key
, typename _Value
,
1533 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1534 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1537 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1538 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1539 _M_find_before_node(size_type __n
, const key_type
& __k
,
1540 __hash_code __code
) const
1543 __node_base
* __prev_p
= _M_buckets
[__n
];
1547 for (__node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);;
1548 __p
= __p
->_M_next())
1550 if (this->_M_equals(__k
, __code
, __p
))
1553 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1560 template<typename _Key
, typename _Value
,
1561 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1562 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1565 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1566 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1567 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1569 if (_M_buckets
[__bkt
])
1571 // Bucket is not empty, we just need to insert the new node
1572 // after the bucket before begin.
1573 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1574 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1578 // The bucket is empty, the new node is inserted at the
1579 // beginning of the singly-linked list and the bucket will
1580 // contain _M_before_begin pointer.
1581 __node
->_M_nxt
= _M_before_begin
._M_nxt
;
1582 _M_before_begin
._M_nxt
= __node
;
1584 // We must update former begin bucket that is pointing to
1586 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1587 _M_buckets
[__bkt
] = &_M_before_begin
;
1591 template<typename _Key
, typename _Value
,
1592 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1593 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1596 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1597 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1598 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1599 size_type __next_bkt
)
1601 if (!__next
|| __next_bkt
!= __bkt
)
1603 // Bucket is now empty
1604 // First update next bucket if any
1606 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1608 // Second update before begin node if necessary
1609 if (&_M_before_begin
== _M_buckets
[__bkt
])
1610 _M_before_begin
._M_nxt
= __next
;
1611 _M_buckets
[__bkt
] = nullptr;
1615 template<typename _Key
, typename _Value
,
1616 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1617 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1620 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1621 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1622 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1625 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1626 while (__prev_n
->_M_nxt
!= __n
)
1627 __prev_n
= __prev_n
->_M_nxt
;
1631 template<typename _Key
, typename _Value
,
1632 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1633 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1635 template<typename
... _Args
>
1637 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1638 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1639 _M_emplace(std::true_type
, _Args
&&... __args
)
1640 -> pair
<iterator
, bool>
1642 // First build the node to get access to the hash code
1643 __node_type
* __node
= this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1644 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1648 __code
= this->_M_hash_code(__k
);
1652 this->_M_deallocate_node(__node
);
1653 __throw_exception_again
;
1656 size_type __bkt
= _M_bucket_index(__k
, __code
);
1657 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1659 // There is already an equivalent node, no insertion
1660 this->_M_deallocate_node(__node
);
1661 return std::make_pair(iterator(__p
), false);
1665 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1669 template<typename _Key
, typename _Value
,
1670 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1671 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1673 template<typename
... _Args
>
1675 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1676 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1677 _M_emplace(const_iterator __hint
, std::false_type
, _Args
&&... __args
)
1680 // First build the node to get its hash code.
1681 __node_type
* __node
=
1682 this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1687 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v()));
1691 this->_M_deallocate_node(__node
);
1692 __throw_exception_again
;
1695 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1698 template<typename _Key
, typename _Value
,
1699 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1700 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1703 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1704 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1705 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
1706 __node_type
* __node
, size_type __n_elt
)
1709 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1710 std::pair
<bool, std::size_t> __do_rehash
1711 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
,
1716 if (__do_rehash
.first
)
1718 _M_rehash(__do_rehash
.second
, __saved_state
);
1719 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v()), __code
);
1722 this->_M_store_code(__node
, __code
);
1724 // Always insert at the beginning of the bucket.
1725 _M_insert_bucket_begin(__bkt
, __node
);
1727 return iterator(__node
);
1731 this->_M_deallocate_node(__node
);
1732 __throw_exception_again
;
1736 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1737 // already present). Take ownership of the node, deallocate it on exception.
1738 template<typename _Key
, typename _Value
,
1739 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1740 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1743 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1744 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1745 _M_insert_multi_node(__node_type
* __hint
, __hash_code __code
,
1746 __node_type
* __node
)
1749 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1750 std::pair
<bool, std::size_t> __do_rehash
1751 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1755 if (__do_rehash
.first
)
1756 _M_rehash(__do_rehash
.second
, __saved_state
);
1758 this->_M_store_code(__node
, __code
);
1759 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1760 size_type __bkt
= _M_bucket_index(__k
, __code
);
1762 // Find the node before an equivalent one or use hint if it exists and
1763 // if it is equivalent.
1765 = __builtin_expect(__hint
!= nullptr, false)
1766 && this->_M_equals(__k
, __code
, __hint
)
1768 : _M_find_before_node(__bkt
, __k
, __code
);
1771 // Insert after the node before the equivalent one.
1772 __node
->_M_nxt
= __prev
->_M_nxt
;
1773 __prev
->_M_nxt
= __node
;
1774 if (__builtin_expect(__prev
== __hint
, false))
1775 // hint might be the last bucket node, in this case we need to
1776 // update next bucket.
1778 && !this->_M_equals(__k
, __code
, __node
->_M_next()))
1780 size_type __next_bkt
= _M_bucket_index(__node
->_M_next());
1781 if (__next_bkt
!= __bkt
)
1782 _M_buckets
[__next_bkt
] = __node
;
1786 // The inserted node has no equivalent in the
1787 // hashtable. We must insert the new node at the
1788 // beginning of the bucket to preserve equivalent
1789 // elements' relative positions.
1790 _M_insert_bucket_begin(__bkt
, __node
);
1792 return iterator(__node
);
1796 this->_M_deallocate_node(__node
);
1797 __throw_exception_again
;
1801 // Insert v if no element with its key is already present.
1802 template<typename _Key
, typename _Value
,
1803 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1804 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1806 template<typename _Arg
, typename _NodeGenerator
>
1808 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1809 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1810 _M_insert(_Arg
&& __v
, const _NodeGenerator
& __node_gen
, true_type
,
1812 -> pair
<iterator
, bool>
1814 const key_type
& __k
= this->_M_extract()(__v
);
1815 __hash_code __code
= this->_M_hash_code(__k
);
1816 size_type __bkt
= _M_bucket_index(__k
, __code
);
1818 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1820 return std::make_pair(iterator(__n
), false);
1822 __n
= __node_gen(std::forward
<_Arg
>(__v
));
1823 return { _M_insert_unique_node(__bkt
, __code
, __n
, __n_elt
), true };
1826 // Insert v unconditionally.
1827 template<typename _Key
, typename _Value
,
1828 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1829 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1831 template<typename _Arg
, typename _NodeGenerator
>
1833 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1834 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1835 _M_insert(const_iterator __hint
, _Arg
&& __v
,
1836 const _NodeGenerator
& __node_gen
, false_type
)
1839 // First compute the hash code so that we don't do anything if it
1841 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1843 // Second allocate new node so that we don't rehash if it throws.
1844 __node_type
* __node
= __node_gen(std::forward
<_Arg
>(__v
));
1846 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1849 template<typename _Key
, typename _Value
,
1850 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1851 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1854 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1855 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1856 erase(const_iterator __it
)
1859 __node_type
* __n
= __it
._M_cur
;
1860 std::size_t __bkt
= _M_bucket_index(__n
);
1862 // Look for previous node to unlink it from the erased one, this
1863 // is why we need buckets to contain the before begin to make
1864 // this search fast.
1865 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1866 return _M_erase(__bkt
, __prev_n
, __n
);
1869 template<typename _Key
, typename _Value
,
1870 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1871 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1874 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1875 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1876 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1879 if (__prev_n
== _M_buckets
[__bkt
])
1880 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1881 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1882 else if (__n
->_M_nxt
)
1884 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1885 if (__next_bkt
!= __bkt
)
1886 _M_buckets
[__next_bkt
] = __prev_n
;
1889 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1890 iterator
__result(__n
->_M_next());
1891 this->_M_deallocate_node(__n
);
1897 template<typename _Key
, typename _Value
,
1898 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1899 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1902 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1903 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1904 _M_erase(std::true_type
, const key_type
& __k
)
1907 __hash_code __code
= this->_M_hash_code(__k
);
1908 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1910 // Look for the node before the first matching node.
1911 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1915 // We found a matching node, erase it.
1916 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1917 _M_erase(__bkt
, __prev_n
, __n
);
1921 template<typename _Key
, typename _Value
,
1922 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1923 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1926 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1927 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1928 _M_erase(std::false_type
, const key_type
& __k
)
1931 __hash_code __code
= this->_M_hash_code(__k
);
1932 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1934 // Look for the node before the first matching node.
1935 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1939 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1940 // 526. Is it undefined if a function in the standard changes
1942 // We use one loop to find all matching nodes and another to deallocate
1943 // them so that the key stays valid during the first loop. It might be
1944 // invalidated indirectly when destroying nodes.
1945 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1946 __node_type
* __n_last
= __n
;
1947 std::size_t __n_last_bkt
= __bkt
;
1950 __n_last
= __n_last
->_M_next();
1953 __n_last_bkt
= _M_bucket_index(__n_last
);
1955 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1957 // Deallocate nodes.
1958 size_type __result
= 0;
1961 __node_type
* __p
= __n
->_M_next();
1962 this->_M_deallocate_node(__n
);
1967 while (__n
!= __n_last
);
1969 if (__prev_n
== _M_buckets
[__bkt
])
1970 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1971 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1972 _M_buckets
[__n_last_bkt
] = __prev_n
;
1973 __prev_n
->_M_nxt
= __n_last
;
1977 template<typename _Key
, typename _Value
,
1978 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1979 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1982 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1983 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1984 erase(const_iterator __first
, const_iterator __last
)
1987 __node_type
* __n
= __first
._M_cur
;
1988 __node_type
* __last_n
= __last
._M_cur
;
1989 if (__n
== __last_n
)
1990 return iterator(__n
);
1992 std::size_t __bkt
= _M_bucket_index(__n
);
1994 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1995 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1996 std::size_t __n_bkt
= __bkt
;
2001 __node_type
* __tmp
= __n
;
2002 __n
= __n
->_M_next();
2003 this->_M_deallocate_node(__tmp
);
2007 __n_bkt
= _M_bucket_index(__n
);
2009 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
2010 if (__is_bucket_begin
)
2011 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
2012 if (__n
== __last_n
)
2014 __is_bucket_begin
= true;
2018 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
2019 _M_buckets
[__n_bkt
] = __prev_n
;
2020 __prev_n
->_M_nxt
= __n
;
2021 return iterator(__n
);
2024 template<typename _Key
, typename _Value
,
2025 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2026 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2029 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2030 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2033 this->_M_deallocate_nodes(_M_begin());
2034 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
2035 _M_element_count
= 0;
2036 _M_before_begin
._M_nxt
= nullptr;
2039 template<typename _Key
, typename _Value
,
2040 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2041 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2044 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2045 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2046 rehash(size_type __n
)
2048 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
2049 std::size_t __buckets
2050 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
2052 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
2054 if (__buckets
!= _M_bucket_count
)
2055 _M_rehash(__buckets
, __saved_state
);
2057 // No rehash, restore previous state to keep a consistent state.
2058 _M_rehash_policy
._M_reset(__saved_state
);
2061 template<typename _Key
, typename _Value
,
2062 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2063 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2066 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2067 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2068 _M_rehash(size_type __n
, const __rehash_state
& __state
)
2072 _M_rehash_aux(__n
, __unique_keys());
2076 // A failure here means that buckets allocation failed. We only
2077 // have to restore hash policy previous state.
2078 _M_rehash_policy
._M_reset(__state
);
2079 __throw_exception_again
;
2083 // Rehash when there is no equivalent elements.
2084 template<typename _Key
, typename _Value
,
2085 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2086 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2089 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2090 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2091 _M_rehash_aux(size_type __n
, std::true_type
)
2093 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2094 __node_type
* __p
= _M_begin();
2095 _M_before_begin
._M_nxt
= nullptr;
2096 std::size_t __bbegin_bkt
= 0;
2099 __node_type
* __next
= __p
->_M_next();
2100 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2101 if (!__new_buckets
[__bkt
])
2103 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2104 _M_before_begin
._M_nxt
= __p
;
2105 __new_buckets
[__bkt
] = &_M_before_begin
;
2107 __new_buckets
[__bbegin_bkt
] = __p
;
2108 __bbegin_bkt
= __bkt
;
2112 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2113 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2118 _M_deallocate_buckets();
2119 _M_bucket_count
= __n
;
2120 _M_buckets
= __new_buckets
;
2123 // Rehash when there can be equivalent elements, preserve their relative
2125 template<typename _Key
, typename _Value
,
2126 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2127 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2130 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2131 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2132 _M_rehash_aux(size_type __n
, std::false_type
)
2134 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2136 __node_type
* __p
= _M_begin();
2137 _M_before_begin
._M_nxt
= nullptr;
2138 std::size_t __bbegin_bkt
= 0;
2139 std::size_t __prev_bkt
= 0;
2140 __node_type
* __prev_p
= nullptr;
2141 bool __check_bucket
= false;
2145 __node_type
* __next
= __p
->_M_next();
2146 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2148 if (__prev_p
&& __prev_bkt
== __bkt
)
2150 // Previous insert was already in this bucket, we insert after
2151 // the previously inserted one to preserve equivalent elements
2153 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2154 __prev_p
->_M_nxt
= __p
;
2156 // Inserting after a node in a bucket require to check that we
2157 // haven't change the bucket last node, in this case next
2158 // bucket containing its before begin node must be updated. We
2159 // schedule a check as soon as we move out of the sequence of
2160 // equivalent nodes to limit the number of checks.
2161 __check_bucket
= true;
2167 // Check if we shall update the next bucket because of
2168 // insertions into __prev_bkt bucket.
2169 if (__prev_p
->_M_nxt
)
2171 std::size_t __next_bkt
2172 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
2174 if (__next_bkt
!= __prev_bkt
)
2175 __new_buckets
[__next_bkt
] = __prev_p
;
2177 __check_bucket
= false;
2180 if (!__new_buckets
[__bkt
])
2182 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2183 _M_before_begin
._M_nxt
= __p
;
2184 __new_buckets
[__bkt
] = &_M_before_begin
;
2186 __new_buckets
[__bbegin_bkt
] = __p
;
2187 __bbegin_bkt
= __bkt
;
2191 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2192 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2200 if (__check_bucket
&& __prev_p
->_M_nxt
)
2202 std::size_t __next_bkt
2203 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
2204 if (__next_bkt
!= __prev_bkt
)
2205 __new_buckets
[__next_bkt
] = __prev_p
;
2208 _M_deallocate_buckets();
2209 _M_bucket_count
= __n
;
2210 _M_buckets
= __new_buckets
;
2213 #if __cplusplus > 201402L
2214 template<typename
, typename
, typename
> class _Hash_merge_helper
{ };
2217 _GLIBCXX_END_NAMESPACE_VERSION
2220 #endif // _HASHTABLE_H