1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2016 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>
37 namespace std
_GLIBCXX_VISIBILITY(default)
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 template<typename _Tp
, typename _Hash
>
43 = __not_
<__and_
<// Do not cache for fast hasher.
44 __is_fast_hash
<_Hash
>,
45 // Mandatory to have erase not throwing.
46 __detail::__is_noexcept_hash
<_Tp
, _Hash
>>>;
49 * Primary class template _Hashtable.
51 * @ingroup hashtable-detail
53 * @tparam _Value CopyConstructible type.
55 * @tparam _Key CopyConstructible type.
57 * @tparam _Alloc An allocator type
58 * ([lib.allocator.requirements]) whose _Alloc::value_type is
59 * _Value. As a conforming extension, we allow for
60 * _Alloc::value_type != _Value.
62 * @tparam _ExtractKey Function object that takes an object of type
63 * _Value and returns a value of type _Key.
65 * @tparam _Equal Function object that takes two objects of type k
66 * and returns a bool-like value that is true if the two objects
67 * are considered equal.
69 * @tparam _H1 The hash function. A unary function object with
70 * argument type _Key and result type size_t. Return values should
71 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
73 * @tparam _H2 The range-hashing function (in the terminology of
74 * Tavori and Dreizin). A binary function object whose argument
75 * types and result type are all size_t. Given arguments r and N,
76 * the return value is in the range [0, N).
78 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
79 * binary function whose argument types are _Key and size_t and
80 * whose result type is size_t. Given arguments k and N, the
81 * return value is in the range [0, N). Default: hash(k, N) =
82 * h2(h1(k), N). If _Hash is anything other than the default, _H1
83 * and _H2 are ignored.
85 * @tparam _RehashPolicy Policy class with three members, all of
86 * which govern the bucket count. _M_next_bkt(n) returns a bucket
87 * count no smaller than n. _M_bkt_for_elements(n) returns a
88 * bucket count appropriate for an element count of n.
89 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
90 * current bucket count is n_bkt and the current element count is
91 * n_elt, we need to increase the bucket count. If so, returns
92 * make_pair(true, n), where n is the new bucket count. If not,
93 * returns make_pair(false, <anything>)
95 * @tparam _Traits Compile-time class with three boolean
96 * std::integral_constant members: __cache_hash_code, __constant_iterators,
99 * Each _Hashtable data structure has:
101 * - _Bucket[] _M_buckets
102 * - _Hash_node_base _M_before_begin
103 * - size_type _M_bucket_count
104 * - size_type _M_element_count
106 * with _Bucket being _Hash_node* and _Hash_node containing:
108 * - _Hash_node* _M_next
110 * - size_t _M_hash_code if cache_hash_code is true
112 * In terms of Standard containers the hashtable is like the aggregation of:
114 * - std::forward_list<_Node> containing the elements
115 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
117 * The non-empty buckets contain the node before the first node in the
118 * bucket. This design makes it possible to implement something like a
119 * std::forward_list::insert_after on container insertion and
120 * std::forward_list::erase_after on container erase
121 * calls. _M_before_begin is equivalent to
122 * std::forward_list::before_begin. Empty buckets contain
123 * nullptr. Note that one of the non-empty buckets contains
124 * &_M_before_begin which is not a dereferenceable node so the
125 * node pointer in a bucket shall never be dereferenced, only its
128 * Walking through a bucket's nodes requires a check on the hash code to
129 * see if each node is still in the bucket. Such a design assumes a
130 * quite efficient hash functor and is one of the reasons it is
131 * highly advisable to set __cache_hash_code to true.
133 * The container iterators are simply built from nodes. This way
134 * incrementing the iterator is perfectly efficient independent of
135 * how many empty buckets there are in the container.
137 * On insert we compute the element's hash code and use it to find the
138 * bucket index. If the element must be inserted in an empty bucket
139 * we add it at the beginning of the singly linked list and make the
140 * bucket point to _M_before_begin. The bucket that used to point to
141 * _M_before_begin, if any, is updated to point to its new before
144 * On erase, the simple iterator design requires using the hash
145 * functor to get the index of the bucket to update. For this
146 * reason, when __cache_hash_code is set to false the hash functor must
147 * not throw and this is enforced by a static assertion.
149 * Functionality is implemented by decomposition into base classes,
150 * where the derived _Hashtable class is used in _Map_base,
151 * _Insert, _Rehash_base, and _Equality base classes to access the
152 * "this" pointer. _Hashtable_base is used in the base classes as a
153 * non-recursive, fully-completed-type so that detailed nested type
154 * information, such as iterator type and node type, can be
155 * used. This is similar to the "Curiously Recurring Template
156 * Pattern" (CRTP) technique, but uses a reconstructed, not
157 * explicitly passed, template pattern.
159 * Base class templates are:
160 * - __detail::_Hashtable_base
161 * - __detail::_Map_base
162 * - __detail::_Insert
163 * - __detail::_Rehash_base
164 * - __detail::_Equality
166 template<typename _Key
, typename _Value
, typename _Alloc
,
167 typename _ExtractKey
, typename _Equal
,
168 typename _H1
, typename _H2
, typename _Hash
,
169 typename _RehashPolicy
, typename _Traits
>
171 : public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
172 _H1
, _H2
, _Hash
, _Traits
>,
173 public __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
174 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
175 public __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
176 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
177 public __detail::_Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
178 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
179 public __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
180 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
181 private __detail::_Hashtable_alloc
<
182 __alloc_rebind
<_Alloc
,
183 __detail::_Hash_node
<_Value
,
184 _Traits::__hash_cached::value
>>>
186 using __traits_type
= _Traits
;
187 using __hash_cached
= typename
__traits_type::__hash_cached
;
188 using __node_type
= __detail::_Hash_node
<_Value
, __hash_cached::value
>;
189 using __node_alloc_type
= __alloc_rebind
<_Alloc
, __node_type
>;
191 using __hashtable_alloc
= __detail::_Hashtable_alloc
<__node_alloc_type
>;
193 using __value_alloc_traits
=
194 typename
__hashtable_alloc::__value_alloc_traits
;
195 using __node_alloc_traits
=
196 typename
__hashtable_alloc::__node_alloc_traits
;
197 using __node_base
= typename
__hashtable_alloc::__node_base
;
198 using __bucket_type
= typename
__hashtable_alloc::__bucket_type
;
201 typedef _Key key_type
;
202 typedef _Value value_type
;
203 typedef _Alloc allocator_type
;
204 typedef _Equal key_equal
;
206 // mapped_type, if present, comes from _Map_base.
207 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
208 typedef typename
__value_alloc_traits::pointer pointer
;
209 typedef typename
__value_alloc_traits::const_pointer const_pointer
;
210 typedef value_type
& reference
;
211 typedef const value_type
& const_reference
;
214 using __rehash_type
= _RehashPolicy
;
215 using __rehash_state
= typename
__rehash_type::_State
;
217 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
218 using __unique_keys
= typename
__traits_type::__unique_keys
;
220 using __key_extract
= typename
std::conditional
<
221 __constant_iterators::value
,
223 __detail::_Select1st
>::type
;
225 using __hashtable_base
= __detail::
226 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
227 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
229 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
230 using __hash_code
= typename
__hashtable_base::__hash_code
;
231 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
233 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
234 _Equal
, _H1
, _H2
, _Hash
,
235 _RehashPolicy
, _Traits
>;
237 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
240 _RehashPolicy
, _Traits
>;
242 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
243 _Equal
, _H1
, _H2
, _Hash
,
244 _RehashPolicy
, _Traits
>;
246 using __reuse_or_alloc_node_type
=
247 __detail::_ReuseOrAllocNode
<__node_alloc_type
>;
249 // Metaprogramming for picking apart hash caching.
250 template<typename _Cond
>
251 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
253 template<typename _Cond
>
254 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
256 // Compile-time diagnostics.
258 // _Hash_code_base has everything protected, so use this derived type to
260 struct __hash_code_base_access
: __hash_code_base
261 { using __hash_code_base::_M_bucket_index
; };
263 // Getting a bucket index from a node shall not throw because it is used
264 // in methods (erase, swap...) that shall not throw.
265 static_assert(noexcept(declval
<const __hash_code_base_access
&>()
266 ._M_bucket_index((const __node_type
*)nullptr,
268 "Cache the hash code or qualify your functors involved"
269 " in hash code and bucket index computation with noexcept");
271 // Following two static assertions are necessary to guarantee
272 // that local_iterator will be default constructible.
274 // When hash codes are cached local iterator inherits from H2 functor
275 // which must then be default constructible.
276 static_assert(__if_hash_cached
<is_default_constructible
<_H2
>>::value
,
277 "Functor used to map hash code to bucket index"
278 " must be default constructible");
280 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
281 typename _ExtractKeya
, typename _Equala
,
282 typename _H1a
, typename _H2a
, typename _Hasha
,
283 typename _RehashPolicya
, typename _Traitsa
,
285 friend struct __detail::_Map_base
;
287 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
288 typename _ExtractKeya
, typename _Equala
,
289 typename _H1a
, typename _H2a
, typename _Hasha
,
290 typename _RehashPolicya
, typename _Traitsa
>
291 friend struct __detail::_Insert_base
;
293 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
294 typename _ExtractKeya
, typename _Equala
,
295 typename _H1a
, typename _H2a
, typename _Hasha
,
296 typename _RehashPolicya
, typename _Traitsa
,
297 bool _Constant_iteratorsa
, bool _Unique_keysa
>
298 friend struct __detail::_Insert
;
301 using size_type
= typename
__hashtable_base::size_type
;
302 using difference_type
= typename
__hashtable_base::difference_type
;
304 using iterator
= typename
__hashtable_base::iterator
;
305 using const_iterator
= typename
__hashtable_base::const_iterator
;
307 using local_iterator
= typename
__hashtable_base::local_iterator
;
308 using const_local_iterator
= typename
__hashtable_base::
309 const_local_iterator
;
312 __bucket_type
* _M_buckets
= &_M_single_bucket
;
313 size_type _M_bucket_count
= 1;
314 __node_base _M_before_begin
;
315 size_type _M_element_count
= 0;
316 _RehashPolicy _M_rehash_policy
;
318 // A single bucket used when only need for 1 bucket. Especially
319 // interesting in move semantic to leave hashtable with only 1 buckets
320 // which is not allocated so that we can have those operations noexcept
322 // Note that we can't leave hashtable with 0 bucket without adding
323 // numerous checks in the code to avoid 0 modulus.
324 __bucket_type _M_single_bucket
= nullptr;
327 _M_uses_single_bucket(__bucket_type
* __bkts
) const
328 { return __builtin_expect(__bkts
== &_M_single_bucket
, false); }
331 _M_uses_single_bucket() const
332 { return _M_uses_single_bucket(_M_buckets
); }
335 _M_base_alloc() { return *this; }
338 _M_allocate_buckets(size_type __n
)
340 if (__builtin_expect(__n
== 1, false))
342 _M_single_bucket
= nullptr;
343 return &_M_single_bucket
;
346 return __hashtable_alloc::_M_allocate_buckets(__n
);
350 _M_deallocate_buckets(__bucket_type
* __bkts
, size_type __n
)
352 if (_M_uses_single_bucket(__bkts
))
355 __hashtable_alloc::_M_deallocate_buckets(__bkts
, __n
);
359 _M_deallocate_buckets()
360 { _M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
362 // Gets bucket begin, deals with the fact that non-empty buckets contain
363 // their before begin node.
365 _M_bucket_begin(size_type __bkt
) const;
369 { return static_cast<__node_type
*>(_M_before_begin
._M_nxt
); }
371 template<typename _NodeGenerator
>
373 _M_assign(const _Hashtable
&, const _NodeGenerator
&);
376 _M_move_assign(_Hashtable
&&, std::true_type
);
379 _M_move_assign(_Hashtable
&&, std::false_type
);
384 _Hashtable(const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
385 const _Equal
& __eq
, const _ExtractKey
& __exk
,
386 const allocator_type
& __a
)
387 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
388 __hashtable_alloc(__node_alloc_type(__a
))
392 // Constructor, destructor, assignment, swap
393 _Hashtable() = default;
394 _Hashtable(size_type __bucket_hint
,
395 const _H1
&, const _H2
&, const _Hash
&,
396 const _Equal
&, const _ExtractKey
&,
397 const allocator_type
&);
399 template<typename _InputIterator
>
400 _Hashtable(_InputIterator __first
, _InputIterator __last
,
401 size_type __bucket_hint
,
402 const _H1
&, const _H2
&, const _Hash
&,
403 const _Equal
&, const _ExtractKey
&,
404 const allocator_type
&);
406 _Hashtable(const _Hashtable
&);
408 _Hashtable(_Hashtable
&&) noexcept
;
410 _Hashtable(const _Hashtable
&, const allocator_type
&);
412 _Hashtable(_Hashtable
&&, const allocator_type
&);
414 // Use delegating constructors.
416 _Hashtable(const allocator_type
& __a
)
417 : __hashtable_alloc(__node_alloc_type(__a
))
421 _Hashtable(size_type __n
,
422 const _H1
& __hf
= _H1(),
423 const key_equal
& __eql
= key_equal(),
424 const allocator_type
& __a
= allocator_type())
425 : _Hashtable(__n
, __hf
, _H2(), _Hash(), __eql
,
426 __key_extract(), __a
)
429 template<typename _InputIterator
>
430 _Hashtable(_InputIterator __f
, _InputIterator __l
,
432 const _H1
& __hf
= _H1(),
433 const key_equal
& __eql
= key_equal(),
434 const allocator_type
& __a
= allocator_type())
435 : _Hashtable(__f
, __l
, __n
, __hf
, _H2(), _Hash(), __eql
,
436 __key_extract(), __a
)
439 _Hashtable(initializer_list
<value_type
> __l
,
441 const _H1
& __hf
= _H1(),
442 const key_equal
& __eql
= key_equal(),
443 const allocator_type
& __a
= allocator_type())
444 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
, _H2(), _Hash(), __eql
,
445 __key_extract(), __a
)
449 operator=(const _Hashtable
& __ht
);
452 operator=(_Hashtable
&& __ht
)
453 noexcept(__node_alloc_traits::_S_nothrow_move()
454 && is_nothrow_move_assignable
<_H1
>::value
455 && is_nothrow_move_assignable
<_Equal
>::value
)
457 constexpr bool __move_storage
=
458 __node_alloc_traits::_S_propagate_on_move_assign()
459 || __node_alloc_traits::_S_always_equal();
460 _M_move_assign(std::move(__ht
), __bool_constant
<__move_storage
>());
465 operator=(initializer_list
<value_type
> __l
)
467 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
468 _M_before_begin
._M_nxt
= nullptr;
470 this->_M_insert_range(__l
.begin(), __l
.end(), __roan
);
474 ~_Hashtable() noexcept
;
478 noexcept(__is_nothrow_swappable
<_H1
>::value
479 && __is_nothrow_swappable
<_Equal
>::value
);
481 // Basic container operations
484 { return iterator(_M_begin()); }
487 begin() const noexcept
488 { return const_iterator(_M_begin()); }
492 { return iterator(nullptr); }
496 { return const_iterator(nullptr); }
499 cbegin() const noexcept
500 { return const_iterator(_M_begin()); }
503 cend() const noexcept
504 { return const_iterator(nullptr); }
507 size() const noexcept
508 { return _M_element_count
; }
511 empty() const noexcept
512 { return size() == 0; }
515 get_allocator() const noexcept
516 { return allocator_type(this->_M_node_allocator()); }
519 max_size() const noexcept
520 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
525 { return this->_M_eq(); }
527 // hash_function, if present, comes from _Hash_code_base.
531 bucket_count() const noexcept
532 { return _M_bucket_count
; }
535 max_bucket_count() const noexcept
536 { return max_size(); }
539 bucket_size(size_type __n
) const
540 { return std::distance(begin(__n
), end(__n
)); }
543 bucket(const key_type
& __k
) const
544 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
549 return local_iterator(*this, _M_bucket_begin(__n
),
550 __n
, _M_bucket_count
);
555 { return local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
558 begin(size_type __n
) const
560 return const_local_iterator(*this, _M_bucket_begin(__n
),
561 __n
, _M_bucket_count
);
565 end(size_type __n
) const
566 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
570 cbegin(size_type __n
) const
572 return const_local_iterator(*this, _M_bucket_begin(__n
),
573 __n
, _M_bucket_count
);
577 cend(size_type __n
) const
578 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
581 load_factor() const noexcept
583 return static_cast<float>(size()) / static_cast<float>(bucket_count());
586 // max_load_factor, if present, comes from _Rehash_base.
588 // Generalization of max_load_factor. Extension, not found in
589 // TR1. Only useful if _RehashPolicy is something other than
592 __rehash_policy() const
593 { return _M_rehash_policy
; }
596 __rehash_policy(const _RehashPolicy
& __pol
)
597 { _M_rehash_policy
= __pol
; }
601 find(const key_type
& __k
);
604 find(const key_type
& __k
) const;
607 count(const key_type
& __k
) const;
609 std::pair
<iterator
, iterator
>
610 equal_range(const key_type
& __k
);
612 std::pair
<const_iterator
, const_iterator
>
613 equal_range(const key_type
& __k
) const;
616 // Bucket index computation helpers.
618 _M_bucket_index(__node_type
* __n
) const noexcept
619 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
622 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
623 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
625 // Find and insert helper functions and types
626 // Find the node before the one matching the criteria.
628 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
631 _M_find_node(size_type __bkt
, const key_type
& __key
,
632 __hash_code __c
) const
634 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
636 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
640 // Insert a node at the beginning of a bucket.
642 _M_insert_bucket_begin(size_type
, __node_type
*);
644 // Remove the bucket first node
646 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
647 size_type __next_bkt
);
649 // Get the node before __n in the bucket __bkt
651 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
653 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
654 // no element with its key already present). Take ownership of the node,
655 // deallocate it on exception.
657 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
660 // Insert node with hash code __code. Take ownership of the node,
661 // deallocate it on exception.
663 _M_insert_multi_node(__node_type
* __hint
,
664 __hash_code __code
, __node_type
* __n
);
666 template<bool _Uniq
, typename
... _Args
>
667 typename enable_if
<_Uniq
, std::pair
<iterator
, bool>>::type
668 _M_emplace(__bool_constant
<_Uniq
>, _Args
&&... __args
);
670 template<bool _Uniq
, typename
... _Args
>
671 typename enable_if
<!_Uniq
, iterator
>::type
672 _M_emplace(__bool_constant
<_Uniq
> __uk
, _Args
&&... __args
)
674 return _M_emplace_hint(cend(), __uk
, std::forward
<_Args
>(__args
)...);
677 // Emplace with hint, useless when keys are unique.
678 template<typename
... _Args
>
680 _M_emplace_hint(const_iterator
, std::true_type __uk
, _Args
&&... __args
)
681 { return _M_emplace(__uk
, std::forward
<_Args
>(__args
)...).first
; }
683 template<typename
... _Args
>
685 _M_emplace_hint(const_iterator
, std::false_type
, _Args
&&... __args
);
687 template<typename _Arg
, typename _NodeGenerator
>
688 std::pair
<iterator
, bool>
689 _M_insert(_Arg
&&, const _NodeGenerator
&, std::true_type
);
691 template<typename _Arg
, typename _NodeGenerator
>
693 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
694 std::false_type __uk
)
696 return _M_insert(cend(), std::forward
<_Arg
>(__arg
), __node_gen
,
700 // Insert with hint, not used when keys are unique.
701 template<typename _Arg
, typename _NodeGenerator
>
703 _M_insert(const_iterator
, _Arg
&& __arg
,
704 const _NodeGenerator
& __node_gen
, std::true_type __uk
)
707 _M_insert(std::forward
<_Arg
>(__arg
), __node_gen
, __uk
).first
;
710 // Insert with hint when keys are not unique.
711 template<typename _Arg
, typename _NodeGenerator
>
713 _M_insert(const_iterator
, _Arg
&&,
714 const _NodeGenerator
&, std::false_type
);
717 _M_erase(const key_type
&, std::true_type
);
720 _M_erase(const key_type
&, std::false_type
);
723 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
727 template<typename
... _Args
>
729 emplace(_Args
&&... __args
)
730 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
732 template<typename
... _Args
>
734 emplace_hint(const_iterator __hint
, _Args
&&... __args
)
736 return _M_emplace_hint(__hint
, __unique_keys(),
737 std::forward
<_Args
>(__args
)...);
740 // Insert member functions via inheritance.
744 erase(const_iterator
);
749 { return erase(const_iterator(__it
)); }
752 erase(const key_type
& __k
)
753 { return _M_erase(__k
, __unique_keys()); }
756 erase(const_iterator
, const_iterator
);
761 // Set number of buckets to be appropriate for container of n element.
762 void rehash(size_type __n
);
765 // reserve, if present, comes from _Rehash_base.
768 // Helper rehash method used when keys are unique.
769 void _M_rehash_aux(size_type __n
, std::true_type
);
771 // Helper rehash method used when keys can be non-unique.
772 void _M_rehash_aux(size_type __n
, std::false_type
);
774 // Unconditionally change size of bucket array to n, restore
775 // hash policy state to __state on exception.
776 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
780 // Definitions of class template _Hashtable's out-of-line member functions.
781 template<typename _Key
, typename _Value
,
782 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
783 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
786 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
787 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
788 _M_bucket_begin(size_type __bkt
) const
791 __node_base
* __n
= _M_buckets
[__bkt
];
792 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
795 template<typename _Key
, typename _Value
,
796 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
797 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
799 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
800 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
801 _Hashtable(size_type __bucket_hint
,
802 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
803 const _Equal
& __eq
, const _ExtractKey
& __exk
,
804 const allocator_type
& __a
)
805 : _Hashtable(__h1
, __h2
, __h
, __eq
, __exk
, __a
)
807 auto __bkt
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
808 if (__bkt
> _M_bucket_count
)
810 _M_buckets
= _M_allocate_buckets(__bkt
);
811 _M_bucket_count
= __bkt
;
815 template<typename _Key
, typename _Value
,
816 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
817 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
819 template<typename _InputIterator
>
820 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
821 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
822 _Hashtable(_InputIterator __f
, _InputIterator __l
,
823 size_type __bucket_hint
,
824 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
825 const _Equal
& __eq
, const _ExtractKey
& __exk
,
826 const allocator_type
& __a
)
827 : _Hashtable(__h1
, __h2
, __h
, __eq
, __exk
, __a
)
829 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
831 _M_rehash_policy
._M_next_bkt(
832 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
835 if (__bkt_count
> _M_bucket_count
)
837 _M_buckets
= _M_allocate_buckets(__bkt_count
);
838 _M_bucket_count
= __bkt_count
;
843 for (; __f
!= __l
; ++__f
)
849 _M_deallocate_buckets();
850 __throw_exception_again
;
854 template<typename _Key
, typename _Value
,
855 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
856 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
859 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
860 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
861 operator=(const _Hashtable
& __ht
)
867 if (__node_alloc_traits::_S_propagate_on_copy_assign())
869 auto& __this_alloc
= this->_M_node_allocator();
870 auto& __that_alloc
= __ht
._M_node_allocator();
871 if (!__node_alloc_traits::_S_always_equal()
872 && __this_alloc
!= __that_alloc
)
874 // Replacement allocator cannot free existing storage.
875 this->_M_deallocate_nodes(_M_begin());
876 _M_before_begin
._M_nxt
= nullptr;
877 _M_deallocate_buckets();
878 _M_buckets
= nullptr;
879 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
880 __hashtable_base::operator=(__ht
);
881 _M_bucket_count
= __ht
._M_bucket_count
;
882 _M_element_count
= __ht
._M_element_count
;
883 _M_rehash_policy
= __ht
._M_rehash_policy
;
887 [this](const __node_type
* __n
)
888 { return this->_M_allocate_node(__n
->_M_v()); });
892 // _M_assign took care of deallocating all memory. Now we
893 // must make sure this instance remains in a usable state.
895 __throw_exception_again
;
899 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
902 // Reuse allocated buckets and nodes.
903 __bucket_type
* __former_buckets
= nullptr;
904 std::size_t __former_bucket_count
= _M_bucket_count
;
905 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
907 if (_M_bucket_count
!= __ht
._M_bucket_count
)
909 __former_buckets
= _M_buckets
;
910 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
911 _M_bucket_count
= __ht
._M_bucket_count
;
914 __builtin_memset(_M_buckets
, 0,
915 _M_bucket_count
* sizeof(__bucket_type
));
919 __hashtable_base::operator=(__ht
);
920 _M_element_count
= __ht
._M_element_count
;
921 _M_rehash_policy
= __ht
._M_rehash_policy
;
922 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
923 _M_before_begin
._M_nxt
= nullptr;
925 [&__roan
](const __node_type
* __n
)
926 { return __roan(__n
->_M_v()); });
927 if (__former_buckets
)
928 _M_deallocate_buckets(__former_buckets
, __former_bucket_count
);
932 if (__former_buckets
)
934 // Restore previous buckets.
935 _M_deallocate_buckets();
936 _M_rehash_policy
._M_reset(__former_state
);
937 _M_buckets
= __former_buckets
;
938 _M_bucket_count
= __former_bucket_count
;
940 __builtin_memset(_M_buckets
, 0,
941 _M_bucket_count
* sizeof(__bucket_type
));
942 __throw_exception_again
;
947 template<typename _Key
, typename _Value
,
948 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
949 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
951 template<typename _NodeGenerator
>
953 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
954 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
955 _M_assign(const _Hashtable
& __ht
, const _NodeGenerator
& __node_gen
)
957 __bucket_type
* __buckets
= nullptr;
959 _M_buckets
= __buckets
= _M_allocate_buckets(_M_bucket_count
);
963 if (!__ht
._M_before_begin
._M_nxt
)
966 // First deal with the special first node pointed to by
968 __node_type
* __ht_n
= __ht
._M_begin();
969 __node_type
* __this_n
= __node_gen(__ht_n
);
970 this->_M_copy_code(__this_n
, __ht_n
);
971 _M_before_begin
._M_nxt
= __this_n
;
972 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin
;
974 // Then deal with other nodes.
975 __node_base
* __prev_n
= __this_n
;
976 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
978 __this_n
= __node_gen(__ht_n
);
979 __prev_n
->_M_nxt
= __this_n
;
980 this->_M_copy_code(__this_n
, __ht_n
);
981 size_type __bkt
= _M_bucket_index(__this_n
);
982 if (!_M_buckets
[__bkt
])
983 _M_buckets
[__bkt
] = __prev_n
;
991 _M_deallocate_buckets();
992 __throw_exception_again
;
996 template<typename _Key
, typename _Value
,
997 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
998 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1001 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1002 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1005 _M_rehash_policy
._M_reset();
1006 _M_bucket_count
= 1;
1007 _M_single_bucket
= nullptr;
1008 _M_buckets
= &_M_single_bucket
;
1009 _M_before_begin
._M_nxt
= nullptr;
1010 _M_element_count
= 0;
1013 template<typename _Key
, typename _Value
,
1014 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1015 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1018 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1019 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1020 _M_move_assign(_Hashtable
&& __ht
, std::true_type
)
1022 this->_M_deallocate_nodes(_M_begin());
1023 _M_deallocate_buckets();
1024 __hashtable_base::operator=(std::move(__ht
));
1025 _M_rehash_policy
= __ht
._M_rehash_policy
;
1026 if (!__ht
._M_uses_single_bucket())
1027 _M_buckets
= __ht
._M_buckets
;
1030 _M_buckets
= &_M_single_bucket
;
1031 _M_single_bucket
= __ht
._M_single_bucket
;
1033 _M_bucket_count
= __ht
._M_bucket_count
;
1034 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1035 _M_element_count
= __ht
._M_element_count
;
1036 std::__alloc_on_move(this->_M_node_allocator(), __ht
._M_node_allocator());
1038 // Fix buckets containing the _M_before_begin pointers that can't be
1041 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1045 template<typename _Key
, typename _Value
,
1046 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1047 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1050 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1051 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1052 _M_move_assign(_Hashtable
&& __ht
, std::false_type
)
1054 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1055 _M_move_assign(std::move(__ht
), std::true_type());
1058 // Can't move memory, move elements then.
1059 __bucket_type
* __former_buckets
= nullptr;
1060 size_type __former_bucket_count
= _M_bucket_count
;
1061 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1063 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1065 __former_buckets
= _M_buckets
;
1066 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
1067 _M_bucket_count
= __ht
._M_bucket_count
;
1070 __builtin_memset(_M_buckets
, 0,
1071 _M_bucket_count
* sizeof(__bucket_type
));
1075 __hashtable_base::operator=(std::move(__ht
));
1076 _M_element_count
= __ht
._M_element_count
;
1077 _M_rehash_policy
= __ht
._M_rehash_policy
;
1078 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
1079 _M_before_begin
._M_nxt
= nullptr;
1081 [&__roan
](__node_type
* __n
)
1082 { return __roan(std::move_if_noexcept(__n
->_M_v())); });
1087 if (__former_buckets
)
1089 _M_deallocate_buckets();
1090 _M_rehash_policy
._M_reset(__former_state
);
1091 _M_buckets
= __former_buckets
;
1092 _M_bucket_count
= __former_bucket_count
;
1094 __builtin_memset(_M_buckets
, 0,
1095 _M_bucket_count
* sizeof(__bucket_type
));
1096 __throw_exception_again
;
1101 template<typename _Key
, typename _Value
,
1102 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1103 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1105 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1106 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1107 _Hashtable(const _Hashtable
& __ht
)
1108 : __hashtable_base(__ht
),
1110 __rehash_base(__ht
),
1112 __node_alloc_traits::_S_select_on_copy(__ht
._M_node_allocator())),
1113 _M_buckets(nullptr),
1114 _M_bucket_count(__ht
._M_bucket_count
),
1115 _M_element_count(__ht
._M_element_count
),
1116 _M_rehash_policy(__ht
._M_rehash_policy
)
1119 [this](const __node_type
* __n
)
1120 { return this->_M_allocate_node(__n
->_M_v()); });
1123 template<typename _Key
, typename _Value
,
1124 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1125 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1127 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1128 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1129 _Hashtable(_Hashtable
&& __ht
) noexcept
1130 : __hashtable_base(__ht
),
1132 __rehash_base(__ht
),
1133 __hashtable_alloc(std::move(__ht
._M_base_alloc())),
1134 _M_buckets(__ht
._M_buckets
),
1135 _M_bucket_count(__ht
._M_bucket_count
),
1136 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
1137 _M_element_count(__ht
._M_element_count
),
1138 _M_rehash_policy(__ht
._M_rehash_policy
)
1140 // Update, if necessary, buckets if __ht is using its single bucket.
1141 if (__ht
._M_uses_single_bucket())
1143 _M_buckets
= &_M_single_bucket
;
1144 _M_single_bucket
= __ht
._M_single_bucket
;
1147 // Update, if necessary, bucket pointing to before begin that hasn't
1150 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1155 template<typename _Key
, typename _Value
,
1156 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1157 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1159 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1160 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1161 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1162 : __hashtable_base(__ht
),
1164 __rehash_base(__ht
),
1165 __hashtable_alloc(__node_alloc_type(__a
)),
1167 _M_bucket_count(__ht
._M_bucket_count
),
1168 _M_element_count(__ht
._M_element_count
),
1169 _M_rehash_policy(__ht
._M_rehash_policy
)
1172 [this](const __node_type
* __n
)
1173 { return this->_M_allocate_node(__n
->_M_v()); });
1176 template<typename _Key
, typename _Value
,
1177 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1178 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1180 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1181 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1182 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
1183 : __hashtable_base(__ht
),
1185 __rehash_base(__ht
),
1186 __hashtable_alloc(__node_alloc_type(__a
)),
1187 _M_buckets(nullptr),
1188 _M_bucket_count(__ht
._M_bucket_count
),
1189 _M_element_count(__ht
._M_element_count
),
1190 _M_rehash_policy(__ht
._M_rehash_policy
)
1192 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1194 if (__ht
._M_uses_single_bucket())
1196 _M_buckets
= &_M_single_bucket
;
1197 _M_single_bucket
= __ht
._M_single_bucket
;
1200 _M_buckets
= __ht
._M_buckets
;
1202 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1203 // Update, if necessary, bucket pointing to before begin that hasn't
1206 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1212 [this](__node_type
* __n
)
1214 return this->_M_allocate_node(
1215 std::move_if_noexcept(__n
->_M_v()));
1221 template<typename _Key
, typename _Value
,
1222 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1223 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1225 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1226 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1227 ~_Hashtable() noexcept
1230 _M_deallocate_buckets();
1233 template<typename _Key
, typename _Value
,
1234 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1235 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1238 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1239 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1240 swap(_Hashtable
& __x
)
1241 noexcept(__is_nothrow_swappable
<_H1
>::value
1242 && __is_nothrow_swappable
<_Equal
>::value
)
1244 // The only base class with member variables is hash_code_base.
1245 // We define _Hash_code_base::_M_swap because different
1246 // specializations have different members.
1249 std::__alloc_on_swap(this->_M_node_allocator(), __x
._M_node_allocator());
1250 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1252 // Deal properly with potentially moved instances.
1253 if (this->_M_uses_single_bucket())
1255 if (!__x
._M_uses_single_bucket())
1257 _M_buckets
= __x
._M_buckets
;
1258 __x
._M_buckets
= &__x
._M_single_bucket
;
1261 else if (__x
._M_uses_single_bucket())
1263 __x
._M_buckets
= _M_buckets
;
1264 _M_buckets
= &_M_single_bucket
;
1267 std::swap(_M_buckets
, __x
._M_buckets
);
1269 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1270 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
1271 std::swap(_M_element_count
, __x
._M_element_count
);
1272 std::swap(_M_single_bucket
, __x
._M_single_bucket
);
1274 // Fix buckets containing the _M_before_begin pointers that can't be
1277 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1280 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
1281 = &__x
._M_before_begin
;
1284 template<typename _Key
, typename _Value
,
1285 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1286 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1289 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1290 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1291 find(const key_type
& __k
)
1294 __hash_code __code
= this->_M_hash_code(__k
);
1295 std::size_t __n
= _M_bucket_index(__k
, __code
);
1296 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1297 return __p
? iterator(__p
) : end();
1300 template<typename _Key
, typename _Value
,
1301 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1302 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1305 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1306 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1307 find(const key_type
& __k
) const
1310 __hash_code __code
= this->_M_hash_code(__k
);
1311 std::size_t __n
= _M_bucket_index(__k
, __code
);
1312 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1313 return __p
? const_iterator(__p
) : end();
1316 template<typename _Key
, typename _Value
,
1317 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1318 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1321 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1322 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1323 count(const key_type
& __k
) const
1326 __hash_code __code
= this->_M_hash_code(__k
);
1327 std::size_t __n
= _M_bucket_index(__k
, __code
);
1328 __node_type
* __p
= _M_bucket_begin(__n
);
1332 std::size_t __result
= 0;
1333 for (;; __p
= __p
->_M_next())
1335 if (this->_M_equals(__k
, __code
, __p
))
1338 // All equivalent values are next to each other, if we
1339 // found a non-equivalent value after an equivalent one it
1340 // means that we won't find any new equivalent value.
1342 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1348 template<typename _Key
, typename _Value
,
1349 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1350 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1353 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1354 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1355 equal_range(const key_type
& __k
)
1356 -> pair
<iterator
, iterator
>
1358 __hash_code __code
= this->_M_hash_code(__k
);
1359 std::size_t __n
= _M_bucket_index(__k
, __code
);
1360 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1364 __node_type
* __p1
= __p
->_M_next();
1365 while (__p1
&& _M_bucket_index(__p1
) == __n
1366 && this->_M_equals(__k
, __code
, __p1
))
1367 __p1
= __p1
->_M_next();
1369 return std::make_pair(iterator(__p
), iterator(__p1
));
1372 return std::make_pair(end(), end());
1375 template<typename _Key
, typename _Value
,
1376 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1377 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1380 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1381 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1382 equal_range(const key_type
& __k
) const
1383 -> pair
<const_iterator
, const_iterator
>
1385 __hash_code __code
= this->_M_hash_code(__k
);
1386 std::size_t __n
= _M_bucket_index(__k
, __code
);
1387 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1391 __node_type
* __p1
= __p
->_M_next();
1392 while (__p1
&& _M_bucket_index(__p1
) == __n
1393 && this->_M_equals(__k
, __code
, __p1
))
1394 __p1
= __p1
->_M_next();
1396 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1399 return std::make_pair(end(), end());
1402 // Find the node whose key compares equal to k in the bucket n.
1403 // Return nullptr if no node is found.
1404 template<typename _Key
, typename _Value
,
1405 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1406 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1409 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1410 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1411 _M_find_before_node(size_type __n
, const key_type
& __k
,
1412 __hash_code __code
) const
1415 __node_base
* __prev_p
= _M_buckets
[__n
];
1419 for (__node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);;
1420 __p
= __p
->_M_next())
1422 if (this->_M_equals(__k
, __code
, __p
))
1425 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1432 template<typename _Key
, typename _Value
,
1433 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1434 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1437 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1438 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1439 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1441 if (_M_buckets
[__bkt
])
1443 // Bucket is not empty, we just need to insert the new node
1444 // after the bucket before begin.
1445 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1446 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1450 // The bucket is empty, the new node is inserted at the
1451 // beginning of the singly-linked list and the bucket will
1452 // contain _M_before_begin pointer.
1453 __node
->_M_nxt
= _M_before_begin
._M_nxt
;
1454 _M_before_begin
._M_nxt
= __node
;
1456 // We must update former begin bucket that is pointing to
1458 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1459 _M_buckets
[__bkt
] = &_M_before_begin
;
1463 template<typename _Key
, typename _Value
,
1464 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1465 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1468 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1469 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1470 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1471 size_type __next_bkt
)
1473 if (!__next
|| __next_bkt
!= __bkt
)
1475 // Bucket is now empty
1476 // First update next bucket if any
1478 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1480 // Second update before begin node if necessary
1481 if (&_M_before_begin
== _M_buckets
[__bkt
])
1482 _M_before_begin
._M_nxt
= __next
;
1483 _M_buckets
[__bkt
] = nullptr;
1487 template<typename _Key
, typename _Value
,
1488 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1489 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1492 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1493 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1494 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1497 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1498 while (__prev_n
->_M_nxt
!= __n
)
1499 __prev_n
= __prev_n
->_M_nxt
;
1503 template<typename _Key
, typename _Value
,
1504 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1505 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1507 template<bool _Uniq
, typename
... _Args
>
1509 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1510 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1511 _M_emplace(__bool_constant
<_Uniq
>, _Args
&&... __args
)
1512 -> typename enable_if
<_Uniq
, pair
<iterator
, bool>>::type
1514 // First build the node to get access to the hash code
1515 __node_type
* __node
= this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1516 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1520 __code
= this->_M_hash_code(__k
);
1524 this->_M_deallocate_node(__node
);
1525 __throw_exception_again
;
1528 size_type __bkt
= _M_bucket_index(__k
, __code
);
1529 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1531 // There is already an equivalent node, no insertion
1532 this->_M_deallocate_node(__node
);
1533 return std::make_pair(iterator(__p
), false);
1537 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1541 template<typename _Key
, typename _Value
,
1542 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1543 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1545 template<typename
... _Args
>
1547 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1548 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1549 _M_emplace_hint(const_iterator __hint
, std::false_type
, _Args
&&... __args
)
1552 // First build the node to get its hash code.
1553 __node_type
* __node
=
1554 this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1559 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v()));
1563 this->_M_deallocate_node(__node
);
1564 __throw_exception_again
;
1567 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1570 template<typename _Key
, typename _Value
,
1571 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1572 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1575 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1576 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1577 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
1578 __node_type
* __node
)
1581 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1582 std::pair
<bool, std::size_t> __do_rehash
1583 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1587 if (__do_rehash
.first
)
1589 _M_rehash(__do_rehash
.second
, __saved_state
);
1590 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v()), __code
);
1593 this->_M_store_code(__node
, __code
);
1595 // Always insert at the beginning of the bucket.
1596 _M_insert_bucket_begin(__bkt
, __node
);
1598 return iterator(__node
);
1602 this->_M_deallocate_node(__node
);
1603 __throw_exception_again
;
1607 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1608 // already present). Take ownership of the node, deallocate it on exception.
1609 template<typename _Key
, typename _Value
,
1610 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1611 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1614 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1615 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1616 _M_insert_multi_node(__node_type
* __hint
, __hash_code __code
,
1617 __node_type
* __node
)
1620 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1621 std::pair
<bool, std::size_t> __do_rehash
1622 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1626 if (__do_rehash
.first
)
1627 _M_rehash(__do_rehash
.second
, __saved_state
);
1629 this->_M_store_code(__node
, __code
);
1630 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1631 size_type __bkt
= _M_bucket_index(__k
, __code
);
1633 // Find the node before an equivalent one or use hint if it exists and
1634 // if it is equivalent.
1636 = __builtin_expect(__hint
!= nullptr, false)
1637 && this->_M_equals(__k
, __code
, __hint
)
1639 : _M_find_before_node(__bkt
, __k
, __code
);
1642 // Insert after the node before the equivalent one.
1643 __node
->_M_nxt
= __prev
->_M_nxt
;
1644 __prev
->_M_nxt
= __node
;
1645 if (__builtin_expect(__prev
== __hint
, false))
1646 // hint might be the last bucket node, in this case we need to
1647 // update next bucket.
1649 && !this->_M_equals(__k
, __code
, __node
->_M_next()))
1651 size_type __next_bkt
= _M_bucket_index(__node
->_M_next());
1652 if (__next_bkt
!= __bkt
)
1653 _M_buckets
[__next_bkt
] = __node
;
1657 // The inserted node has no equivalent in the
1658 // hashtable. We must insert the new node at the
1659 // beginning of the bucket to preserve equivalent
1660 // elements' relative positions.
1661 _M_insert_bucket_begin(__bkt
, __node
);
1663 return iterator(__node
);
1667 this->_M_deallocate_node(__node
);
1668 __throw_exception_again
;
1672 // Insert v if no element with its key is already present.
1673 template<typename _Key
, typename _Value
,
1674 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1675 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1677 template<typename _Arg
, typename _NodeGenerator
>
1679 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1680 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1681 _M_insert(_Arg
&& __v
, const _NodeGenerator
& __node_gen
, std::true_type
)
1682 -> pair
<iterator
, bool>
1684 const key_type
& __k
= this->_M_extract()(__v
);
1685 __hash_code __code
= this->_M_hash_code(__k
);
1686 size_type __bkt
= _M_bucket_index(__k
, __code
);
1688 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1690 return std::make_pair(iterator(__n
), false);
1692 __n
= __node_gen(std::forward
<_Arg
>(__v
));
1693 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __n
), true);
1696 // Insert v unconditionally.
1697 template<typename _Key
, typename _Value
,
1698 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1699 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1701 template<typename _Arg
, typename _NodeGenerator
>
1703 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1704 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1705 _M_insert(const_iterator __hint
, _Arg
&& __v
,
1706 const _NodeGenerator
& __node_gen
, std::false_type
)
1709 // First compute the hash code so that we don't do anything if it
1711 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1713 // Second allocate new node so that we don't rehash if it throws.
1714 __node_type
* __node
= __node_gen(std::forward
<_Arg
>(__v
));
1716 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1719 template<typename _Key
, typename _Value
,
1720 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1721 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1724 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1725 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1726 erase(const_iterator __it
)
1729 __node_type
* __n
= __it
._M_cur
;
1730 std::size_t __bkt
= _M_bucket_index(__n
);
1732 // Look for previous node to unlink it from the erased one, this
1733 // is why we need buckets to contain the before begin to make
1734 // this search fast.
1735 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1736 return _M_erase(__bkt
, __prev_n
, __n
);
1739 template<typename _Key
, typename _Value
,
1740 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1741 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1744 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1745 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1746 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1749 if (__prev_n
== _M_buckets
[__bkt
])
1750 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1751 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1752 else if (__n
->_M_nxt
)
1754 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1755 if (__next_bkt
!= __bkt
)
1756 _M_buckets
[__next_bkt
] = __prev_n
;
1759 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1760 iterator
__result(__n
->_M_next());
1761 this->_M_deallocate_node(__n
);
1767 template<typename _Key
, typename _Value
,
1768 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1769 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1772 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1773 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1774 _M_erase(const key_type
& __k
, std::true_type
)
1777 __hash_code __code
= this->_M_hash_code(__k
);
1778 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1780 // Look for the node before the first matching node.
1781 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1785 // We found a matching node, erase it.
1786 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1787 _M_erase(__bkt
, __prev_n
, __n
);
1791 template<typename _Key
, typename _Value
,
1792 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1793 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1796 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1797 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1798 _M_erase(const key_type
& __k
, std::false_type
)
1801 __hash_code __code
= this->_M_hash_code(__k
);
1802 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1804 // Look for the node before the first matching node.
1805 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1809 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1810 // 526. Is it undefined if a function in the standard changes
1812 // We use one loop to find all matching nodes and another to deallocate
1813 // them so that the key stays valid during the first loop. It might be
1814 // invalidated indirectly when destroying nodes.
1815 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1816 __node_type
* __n_last
= __n
;
1817 std::size_t __n_last_bkt
= __bkt
;
1820 __n_last
= __n_last
->_M_next();
1823 __n_last_bkt
= _M_bucket_index(__n_last
);
1825 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1827 // Deallocate nodes.
1828 size_type __result
= 0;
1831 __node_type
* __p
= __n
->_M_next();
1832 this->_M_deallocate_node(__n
);
1837 while (__n
!= __n_last
);
1839 if (__prev_n
== _M_buckets
[__bkt
])
1840 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1841 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1842 _M_buckets
[__n_last_bkt
] = __prev_n
;
1843 __prev_n
->_M_nxt
= __n_last
;
1847 template<typename _Key
, typename _Value
,
1848 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1849 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1852 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1853 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1854 erase(const_iterator __first
, const_iterator __last
)
1857 __node_type
* __n
= __first
._M_cur
;
1858 __node_type
* __last_n
= __last
._M_cur
;
1859 if (__n
== __last_n
)
1860 return iterator(__n
);
1862 std::size_t __bkt
= _M_bucket_index(__n
);
1864 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1865 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1866 std::size_t __n_bkt
= __bkt
;
1871 __node_type
* __tmp
= __n
;
1872 __n
= __n
->_M_next();
1873 this->_M_deallocate_node(__tmp
);
1877 __n_bkt
= _M_bucket_index(__n
);
1879 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1880 if (__is_bucket_begin
)
1881 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1882 if (__n
== __last_n
)
1884 __is_bucket_begin
= true;
1888 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
1889 _M_buckets
[__n_bkt
] = __prev_n
;
1890 __prev_n
->_M_nxt
= __n
;
1891 return iterator(__n
);
1894 template<typename _Key
, typename _Value
,
1895 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1896 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1899 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1900 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1903 this->_M_deallocate_nodes(_M_begin());
1904 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
1905 _M_element_count
= 0;
1906 _M_before_begin
._M_nxt
= nullptr;
1909 template<typename _Key
, typename _Value
,
1910 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1911 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1914 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1915 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1916 rehash(size_type __n
)
1918 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1919 std::size_t __buckets
1920 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
1922 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
1924 if (__buckets
!= _M_bucket_count
)
1925 _M_rehash(__buckets
, __saved_state
);
1927 // No rehash, restore previous state to keep a consistent state.
1928 _M_rehash_policy
._M_reset(__saved_state
);
1931 template<typename _Key
, typename _Value
,
1932 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1933 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1936 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1937 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1938 _M_rehash(size_type __n
, const __rehash_state
& __state
)
1942 _M_rehash_aux(__n
, __unique_keys());
1946 // A failure here means that buckets allocation failed. We only
1947 // have to restore hash policy previous state.
1948 _M_rehash_policy
._M_reset(__state
);
1949 __throw_exception_again
;
1953 // Rehash when there is no equivalent elements.
1954 template<typename _Key
, typename _Value
,
1955 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1956 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1959 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1960 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1961 _M_rehash_aux(size_type __n
, std::true_type
)
1963 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
1964 __node_type
* __p
= _M_begin();
1965 _M_before_begin
._M_nxt
= nullptr;
1966 std::size_t __bbegin_bkt
= 0;
1969 __node_type
* __next
= __p
->_M_next();
1970 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1971 if (!__new_buckets
[__bkt
])
1973 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
1974 _M_before_begin
._M_nxt
= __p
;
1975 __new_buckets
[__bkt
] = &_M_before_begin
;
1977 __new_buckets
[__bbegin_bkt
] = __p
;
1978 __bbegin_bkt
= __bkt
;
1982 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1983 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1988 _M_deallocate_buckets();
1989 _M_bucket_count
= __n
;
1990 _M_buckets
= __new_buckets
;
1993 // Rehash when there can be equivalent elements, preserve their relative
1995 template<typename _Key
, typename _Value
,
1996 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1997 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2000 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2001 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2002 _M_rehash_aux(size_type __n
, std::false_type
)
2004 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2006 __node_type
* __p
= _M_begin();
2007 _M_before_begin
._M_nxt
= nullptr;
2008 std::size_t __bbegin_bkt
= 0;
2009 std::size_t __prev_bkt
= 0;
2010 __node_type
* __prev_p
= nullptr;
2011 bool __check_bucket
= false;
2015 __node_type
* __next
= __p
->_M_next();
2016 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2018 if (__prev_p
&& __prev_bkt
== __bkt
)
2020 // Previous insert was already in this bucket, we insert after
2021 // the previously inserted one to preserve equivalent elements
2023 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2024 __prev_p
->_M_nxt
= __p
;
2026 // Inserting after a node in a bucket require to check that we
2027 // haven't change the bucket last node, in this case next
2028 // bucket containing its before begin node must be updated. We
2029 // schedule a check as soon as we move out of the sequence of
2030 // equivalent nodes to limit the number of checks.
2031 __check_bucket
= true;
2037 // Check if we shall update the next bucket because of
2038 // insertions into __prev_bkt bucket.
2039 if (__prev_p
->_M_nxt
)
2041 std::size_t __next_bkt
2042 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
2044 if (__next_bkt
!= __prev_bkt
)
2045 __new_buckets
[__next_bkt
] = __prev_p
;
2047 __check_bucket
= false;
2050 if (!__new_buckets
[__bkt
])
2052 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2053 _M_before_begin
._M_nxt
= __p
;
2054 __new_buckets
[__bkt
] = &_M_before_begin
;
2056 __new_buckets
[__bbegin_bkt
] = __p
;
2057 __bbegin_bkt
= __bkt
;
2061 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2062 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2070 if (__check_bucket
&& __prev_p
->_M_nxt
)
2072 std::size_t __next_bkt
2073 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
2074 if (__next_bkt
!= __prev_bkt
)
2075 __new_buckets
[__next_bkt
] = __prev_p
;
2078 _M_deallocate_buckets();
2079 _M_bucket_count
= __n
;
2080 _M_buckets
= __new_buckets
;
2083 _GLIBCXX_END_NAMESPACE_VERSION
2086 #endif // _HASHTABLE_H