1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2014 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 typename __alloctr_rebind
<_Alloc
,
183 __detail::_Hash_node
<_Value
,
184 _Traits::__hash_cached::value
> >::__type
>
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
=
190 typename __alloctr_rebind
<_Alloc
, __node_type
>::__type
;
192 using __hashtable_alloc
= __detail::_Hashtable_alloc
<__node_alloc_type
>;
194 using __value_alloc_traits
=
195 typename
__hashtable_alloc::__value_alloc_traits
;
196 using __node_alloc_traits
=
197 typename
__hashtable_alloc::__node_alloc_traits
;
198 using __node_base
= typename
__hashtable_alloc::__node_base
;
199 using __bucket_type
= typename
__hashtable_alloc::__bucket_type
;
202 typedef _Key key_type
;
203 typedef _Value value_type
;
204 typedef _Alloc allocator_type
;
205 typedef _Equal key_equal
;
207 // mapped_type, if present, comes from _Map_base.
208 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
209 typedef typename
__value_alloc_traits::pointer pointer
;
210 typedef typename
__value_alloc_traits::const_pointer const_pointer
;
211 typedef value_type
& reference
;
212 typedef const value_type
& const_reference
;
215 using __rehash_type
= _RehashPolicy
;
216 using __rehash_state
= typename
__rehash_type::_State
;
218 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
219 using __unique_keys
= typename
__traits_type::__unique_keys
;
221 using __key_extract
= typename
std::conditional
<
222 __constant_iterators::value
,
224 __detail::_Select1st
>::type
;
226 using __hashtable_base
= __detail::
227 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
228 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
230 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
231 using __hash_code
= typename
__hashtable_base::__hash_code
;
232 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
234 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
235 _Equal
, _H1
, _H2
, _Hash
,
236 _RehashPolicy
, _Traits
>;
238 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
241 _RehashPolicy
, _Traits
>;
243 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
244 _Equal
, _H1
, _H2
, _Hash
,
245 _RehashPolicy
, _Traits
>;
247 using __reuse_or_alloc_node_type
=
248 __detail::_ReuseOrAllocNode
<__node_alloc_type
>;
250 // Metaprogramming for picking apart hash caching.
251 template<typename _Cond
>
252 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
254 template<typename _Cond
>
255 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
257 // Compile-time diagnostics.
259 // _Hash_code_base has everything protected, so use this derived type to
261 struct __hash_code_base_access
: __hash_code_base
262 { using __hash_code_base::_M_bucket_index
; };
264 // Getting a bucket index from a node shall not throw because it is used
265 // in methods (erase, swap...) that shall not throw.
266 static_assert(noexcept(declval
<const __hash_code_base_access
&>()
267 ._M_bucket_index((const __node_type
*)nullptr,
269 "Cache the hash code or qualify your functors involved"
270 " in hash code and bucket index computation with noexcept");
272 // Following two static assertions are necessary to guarantee
273 // that local_iterator will be default constructible.
275 // When hash codes are cached local iterator inherits from H2 functor
276 // which must then be default constructible.
277 static_assert(__if_hash_cached
<is_default_constructible
<_H2
>>::value
,
278 "Functor used to map hash code to bucket index"
279 " must be default constructible");
281 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
282 typename _ExtractKeya
, typename _Equala
,
283 typename _H1a
, typename _H2a
, typename _Hasha
,
284 typename _RehashPolicya
, typename _Traitsa
,
286 friend struct __detail::_Map_base
;
288 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
289 typename _ExtractKeya
, typename _Equala
,
290 typename _H1a
, typename _H2a
, typename _Hasha
,
291 typename _RehashPolicya
, typename _Traitsa
>
292 friend struct __detail::_Insert_base
;
294 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
295 typename _ExtractKeya
, typename _Equala
,
296 typename _H1a
, typename _H2a
, typename _Hasha
,
297 typename _RehashPolicya
, typename _Traitsa
,
298 bool _Constant_iteratorsa
, bool _Unique_keysa
>
299 friend struct __detail::_Insert
;
302 using size_type
= typename
__hashtable_base::size_type
;
303 using difference_type
= typename
__hashtable_base::difference_type
;
305 using iterator
= typename
__hashtable_base::iterator
;
306 using const_iterator
= typename
__hashtable_base::const_iterator
;
308 using local_iterator
= typename
__hashtable_base::local_iterator
;
309 using const_local_iterator
= typename
__hashtable_base::
310 const_local_iterator
;
313 __bucket_type
* _M_buckets
;
314 size_type _M_bucket_count
;
315 __node_base _M_before_begin
;
316 size_type _M_element_count
;
317 _RehashPolicy _M_rehash_policy
;
320 _M_base_alloc() { return *this; }
322 using __hashtable_alloc::_M_deallocate_buckets
;
325 _M_deallocate_buckets()
326 { this->_M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
328 // Gets bucket begin, deals with the fact that non-empty buckets contain
329 // their before begin node.
331 _M_bucket_begin(size_type __bkt
) const;
335 { return static_cast<__node_type
*>(_M_before_begin
._M_nxt
); }
337 template<typename _NodeGenerator
>
339 _M_assign(const _Hashtable
&, const _NodeGenerator
&);
342 _M_move_assign(_Hashtable
&&, std::true_type
);
345 _M_move_assign(_Hashtable
&&, std::false_type
);
351 // Constructor, destructor, assignment, swap
352 _Hashtable(size_type __bucket_hint
,
353 const _H1
&, const _H2
&, const _Hash
&,
354 const _Equal
&, const _ExtractKey
&,
355 const allocator_type
&);
357 template<typename _InputIterator
>
358 _Hashtable(_InputIterator __first
, _InputIterator __last
,
359 size_type __bucket_hint
,
360 const _H1
&, const _H2
&, const _Hash
&,
361 const _Equal
&, const _ExtractKey
&,
362 const allocator_type
&);
364 _Hashtable(const _Hashtable
&);
366 _Hashtable(_Hashtable
&&) noexcept
;
368 _Hashtable(const _Hashtable
&, const allocator_type
&);
370 _Hashtable(_Hashtable
&&, const allocator_type
&);
372 // Use delegating constructors.
374 _Hashtable(const allocator_type
& __a
)
375 : _Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
376 __key_extract(), __a
)
380 _Hashtable(size_type __n
= 10,
381 const _H1
& __hf
= _H1(),
382 const key_equal
& __eql
= key_equal(),
383 const allocator_type
& __a
= allocator_type())
384 : _Hashtable(__n
, __hf
, _H2(), _Hash(), __eql
,
385 __key_extract(), __a
)
388 template<typename _InputIterator
>
389 _Hashtable(_InputIterator __f
, _InputIterator __l
,
391 const _H1
& __hf
= _H1(),
392 const key_equal
& __eql
= key_equal(),
393 const allocator_type
& __a
= allocator_type())
394 : _Hashtable(__f
, __l
, __n
, __hf
, _H2(), _Hash(), __eql
,
395 __key_extract(), __a
)
398 _Hashtable(initializer_list
<value_type
> __l
,
400 const _H1
& __hf
= _H1(),
401 const key_equal
& __eql
= key_equal(),
402 const allocator_type
& __a
= allocator_type())
403 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
, _H2(), _Hash(), __eql
,
404 __key_extract(), __a
)
408 operator=(const _Hashtable
& __ht
);
411 operator=(_Hashtable
&& __ht
)
412 noexcept(__node_alloc_traits::_S_nothrow_move())
414 constexpr bool __move_storage
=
415 __node_alloc_traits::_S_propagate_on_move_assign()
416 || __node_alloc_traits::_S_always_equal();
417 _M_move_assign(std::move(__ht
),
418 integral_constant
<bool, __move_storage
>());
423 operator=(initializer_list
<value_type
> __l
)
425 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
426 _M_before_begin
._M_nxt
= nullptr;
428 this->_M_insert_range(__l
.begin(), __l
.end(), __roan
);
432 ~_Hashtable() noexcept
;
436 noexcept(__node_alloc_traits::_S_nothrow_swap());
438 // Basic container operations
441 { return iterator(_M_begin()); }
444 begin() const noexcept
445 { return const_iterator(_M_begin()); }
449 { return iterator(nullptr); }
453 { return const_iterator(nullptr); }
456 cbegin() const noexcept
457 { return const_iterator(_M_begin()); }
460 cend() const noexcept
461 { return const_iterator(nullptr); }
464 size() const noexcept
465 { return _M_element_count
; }
468 empty() const noexcept
469 { return size() == 0; }
472 get_allocator() const noexcept
473 { return allocator_type(this->_M_node_allocator()); }
476 max_size() const noexcept
477 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
482 { return this->_M_eq(); }
484 // hash_function, if present, comes from _Hash_code_base.
488 bucket_count() const noexcept
489 { return _M_bucket_count
; }
492 max_bucket_count() const noexcept
493 { return max_size(); }
496 bucket_size(size_type __n
) const
497 { return std::distance(begin(__n
), end(__n
)); }
500 bucket(const key_type
& __k
) const
501 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
506 return local_iterator(*this, _M_bucket_begin(__n
),
507 __n
, _M_bucket_count
);
512 { return local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
515 begin(size_type __n
) const
517 return const_local_iterator(*this, _M_bucket_begin(__n
),
518 __n
, _M_bucket_count
);
522 end(size_type __n
) const
523 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
527 cbegin(size_type __n
) const
529 return const_local_iterator(*this, _M_bucket_begin(__n
),
530 __n
, _M_bucket_count
);
534 cend(size_type __n
) const
535 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
538 load_factor() const noexcept
540 return static_cast<float>(size()) / static_cast<float>(bucket_count());
543 // max_load_factor, if present, comes from _Rehash_base.
545 // Generalization of max_load_factor. Extension, not found in
546 // TR1. Only useful if _RehashPolicy is something other than
549 __rehash_policy() const
550 { return _M_rehash_policy
; }
553 __rehash_policy(const _RehashPolicy
&);
557 find(const key_type
& __k
);
560 find(const key_type
& __k
) const;
563 count(const key_type
& __k
) const;
565 std::pair
<iterator
, iterator
>
566 equal_range(const key_type
& __k
);
568 std::pair
<const_iterator
, const_iterator
>
569 equal_range(const key_type
& __k
) const;
572 // Bucket index computation helpers.
574 _M_bucket_index(__node_type
* __n
) const noexcept
575 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
578 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
579 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
581 // Find and insert helper functions and types
582 // Find the node before the one matching the criteria.
584 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
587 _M_find_node(size_type __bkt
, const key_type
& __key
,
588 __hash_code __c
) const
590 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
592 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
596 // Insert a node at the beginning of a bucket.
598 _M_insert_bucket_begin(size_type
, __node_type
*);
600 // Remove the bucket first node
602 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
603 size_type __next_bkt
);
605 // Get the node before __n in the bucket __bkt
607 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
609 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
610 // no element with its key already present). Take ownership of the node,
611 // deallocate it on exception.
613 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
616 // Insert node with hash code __code. Take ownership of the node,
617 // deallocate it on exception.
619 _M_insert_multi_node(__node_type
* __hint
,
620 __hash_code __code
, __node_type
* __n
);
622 template<typename
... _Args
>
623 std::pair
<iterator
, bool>
624 _M_emplace(std::true_type
, _Args
&&... __args
);
626 template<typename
... _Args
>
628 _M_emplace(std::false_type __uk
, _Args
&&... __args
)
629 { return _M_emplace(cend(), __uk
, std::forward
<_Args
>(__args
)...); }
631 // Emplace with hint, useless when keys are unique.
632 template<typename
... _Args
>
634 _M_emplace(const_iterator
, std::true_type __uk
, _Args
&&... __args
)
635 { return _M_emplace(__uk
, std::forward
<_Args
>(__args
)...).first
; }
637 template<typename
... _Args
>
639 _M_emplace(const_iterator
, std::false_type
, _Args
&&... __args
);
641 template<typename _Arg
, typename _NodeGenerator
>
642 std::pair
<iterator
, bool>
643 _M_insert(_Arg
&&, const _NodeGenerator
&, std::true_type
);
645 template<typename _Arg
, typename _NodeGenerator
>
647 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
648 std::false_type __uk
)
650 return _M_insert(cend(), std::forward
<_Arg
>(__arg
), __node_gen
,
654 // Insert with hint, not used when keys are unique.
655 template<typename _Arg
, typename _NodeGenerator
>
657 _M_insert(const_iterator
, _Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
661 _M_insert(std::forward
<_Arg
>(__arg
), __node_gen
, __uk
).first
;
664 // Insert with hint when keys are not unique.
665 template<typename _Arg
, typename _NodeGenerator
>
667 _M_insert(const_iterator
, _Arg
&&, const _NodeGenerator
&, std::false_type
);
670 _M_erase(std::true_type
, const key_type
&);
673 _M_erase(std::false_type
, const key_type
&);
676 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
680 template<typename
... _Args
>
682 emplace(_Args
&&... __args
)
683 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
685 template<typename
... _Args
>
687 emplace_hint(const_iterator __hint
, _Args
&&... __args
)
689 return _M_emplace(__hint
, __unique_keys(),
690 std::forward
<_Args
>(__args
)...);
693 // Insert member functions via inheritance.
697 erase(const_iterator
);
702 { return erase(const_iterator(__it
)); }
705 erase(const key_type
& __k
)
707 if (__builtin_expect(_M_bucket_count
== 0, false))
709 return _M_erase(__unique_keys(), __k
);
713 erase(const_iterator
, const_iterator
);
718 // Set number of buckets to be appropriate for container of n element.
719 void rehash(size_type __n
);
722 // reserve, if present, comes from _Rehash_base.
725 // Helper rehash method used when keys are unique.
726 void _M_rehash_aux(size_type __n
, std::true_type
);
728 // Helper rehash method used when keys can be non-unique.
729 void _M_rehash_aux(size_type __n
, std::false_type
);
731 // Unconditionally change size of bucket array to n, restore
732 // hash policy state to __state on exception.
733 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
737 // Definitions of class template _Hashtable's out-of-line member functions.
738 template<typename _Key
, typename _Value
,
739 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
740 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
742 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
743 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
744 _Traits
>::__node_type
*
745 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
746 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
747 _M_bucket_begin(size_type __bkt
) const
749 __node_base
* __n
= _M_buckets
[__bkt
];
750 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
753 template<typename _Key
, typename _Value
,
754 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
755 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
757 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
758 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
759 _Hashtable(size_type __bucket_hint
,
760 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
761 const _Equal
& __eq
, const _ExtractKey
& __exk
,
762 const allocator_type
& __a
)
763 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
766 __hashtable_alloc(__node_alloc_type(__a
)),
770 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
771 _M_buckets
= this->_M_allocate_buckets(_M_bucket_count
);
774 template<typename _Key
, typename _Value
,
775 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
776 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
778 template<typename _InputIterator
>
779 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
780 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
781 _Hashtable(_InputIterator __f
, _InputIterator __l
,
782 size_type __bucket_hint
,
783 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
784 const _Equal
& __eq
, const _ExtractKey
& __exk
,
785 const allocator_type
& __a
)
786 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
789 __hashtable_alloc(__node_alloc_type(__a
)),
793 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
795 _M_rehash_policy
._M_next_bkt(
796 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
799 _M_buckets
= this->_M_allocate_buckets(_M_bucket_count
);
802 for (; __f
!= __l
; ++__f
)
808 _M_deallocate_buckets();
809 __throw_exception_again
;
813 template<typename _Key
, typename _Value
,
814 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
815 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
817 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
818 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>&
819 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
820 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::operator=(
821 const _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
822 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>& __ht
)
827 if (__node_alloc_traits::_S_propagate_on_copy_assign())
829 auto& __this_alloc
= this->_M_node_allocator();
830 auto& __that_alloc
= __ht
._M_node_allocator();
831 if (!__node_alloc_traits::_S_always_equal()
832 && __this_alloc
!= __that_alloc
)
834 // Replacement allocator cannot free existing storage.
835 this->_M_deallocate_nodes(_M_begin());
836 if (__builtin_expect(_M_bucket_count
!= 0, true))
837 _M_deallocate_buckets();
839 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
840 __hashtable_base::operator=(__ht
);
841 _M_bucket_count
= __ht
._M_bucket_count
;
842 _M_element_count
= __ht
._M_element_count
;
843 _M_rehash_policy
= __ht
._M_rehash_policy
;
847 [this](const __node_type
* __n
)
848 { return this->_M_allocate_node(__n
->_M_v()); });
852 // _M_assign took care of deallocating all memory. Now we
853 // must make sure this instance remains in a usable state.
855 __throw_exception_again
;
859 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
862 // Reuse allocated buckets and nodes.
863 __bucket_type
* __former_buckets
= nullptr;
864 std::size_t __former_bucket_count
= _M_bucket_count
;
865 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
867 if (_M_bucket_count
!= __ht
._M_bucket_count
)
869 __former_buckets
= _M_buckets
;
870 _M_buckets
= this->_M_allocate_buckets(__ht
._M_bucket_count
);
871 _M_bucket_count
= __ht
._M_bucket_count
;
874 __builtin_memset(_M_buckets
, 0,
875 _M_bucket_count
* sizeof(__bucket_type
));
879 __hashtable_base::operator=(__ht
);
880 _M_element_count
= __ht
._M_element_count
;
881 _M_rehash_policy
= __ht
._M_rehash_policy
;
882 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
883 _M_before_begin
._M_nxt
= nullptr;
885 [&__roan
](const __node_type
* __n
)
886 { return __roan(__n
->_M_v()); });
887 if (__former_buckets
)
888 this->_M_deallocate_buckets(__former_buckets
,
889 __former_bucket_count
);
893 if (__former_buckets
)
895 // Restore previous buckets.
896 _M_deallocate_buckets();
897 _M_rehash_policy
._M_reset(__former_state
);
898 _M_buckets
= __former_buckets
;
899 _M_bucket_count
= __former_bucket_count
;
901 __builtin_memset(_M_buckets
, 0,
902 _M_bucket_count
* sizeof(__bucket_type
));
903 __throw_exception_again
;
908 template<typename _Key
, typename _Value
,
909 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
910 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
912 template<typename _NodeGenerator
>
914 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
915 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
916 _M_assign(const _Hashtable
& __ht
, const _NodeGenerator
& __node_gen
)
918 __bucket_type
* __buckets
= nullptr;
920 _M_buckets
= __buckets
= this->_M_allocate_buckets(_M_bucket_count
);
924 if (!__ht
._M_before_begin
._M_nxt
)
927 // First deal with the special first node pointed to by
929 __node_type
* __ht_n
= __ht
._M_begin();
930 __node_type
* __this_n
= __node_gen(__ht_n
);
931 this->_M_copy_code(__this_n
, __ht_n
);
932 _M_before_begin
._M_nxt
= __this_n
;
933 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin
;
935 // Then deal with other nodes.
936 __node_base
* __prev_n
= __this_n
;
937 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
939 __this_n
= __node_gen(__ht_n
);
940 __prev_n
->_M_nxt
= __this_n
;
941 this->_M_copy_code(__this_n
, __ht_n
);
942 size_type __bkt
= _M_bucket_index(__this_n
);
943 if (!_M_buckets
[__bkt
])
944 _M_buckets
[__bkt
] = __prev_n
;
952 _M_deallocate_buckets();
953 __throw_exception_again
;
957 template<typename _Key
, typename _Value
,
958 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
959 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
962 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
963 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
966 _M_rehash_policy
._M_reset();
968 _M_buckets
= nullptr;
969 _M_before_begin
._M_nxt
= nullptr;
970 _M_element_count
= 0;
973 template<typename _Key
, typename _Value
,
974 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
975 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
978 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
979 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
980 _M_move_assign(_Hashtable
&& __ht
, std::true_type
)
982 this->_M_deallocate_nodes(_M_begin());
983 if (__builtin_expect(_M_bucket_count
!= 0, true))
984 _M_deallocate_buckets();
986 __hashtable_base::operator=(std::move(__ht
));
987 _M_rehash_policy
= __ht
._M_rehash_policy
;
988 _M_buckets
= __ht
._M_buckets
;
989 _M_bucket_count
= __ht
._M_bucket_count
;
990 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
991 _M_element_count
= __ht
._M_element_count
;
992 std::__alloc_on_move(this->_M_node_allocator(), __ht
._M_node_allocator());
994 // Fix buckets containing the _M_before_begin pointers that can't be
997 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1001 template<typename _Key
, typename _Value
,
1002 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1003 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1006 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1007 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1008 _M_move_assign(_Hashtable
&& __ht
, std::false_type
)
1010 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1011 _M_move_assign(std::move(__ht
), std::true_type());
1014 // Can't move memory, move elements then.
1015 __bucket_type
* __former_buckets
= nullptr;
1016 size_type __former_bucket_count
= _M_bucket_count
;
1017 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1019 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1021 __former_buckets
= _M_buckets
;
1022 _M_buckets
= this->_M_allocate_buckets(__ht
._M_bucket_count
);
1023 _M_bucket_count
= __ht
._M_bucket_count
;
1026 __builtin_memset(_M_buckets
, 0,
1027 _M_bucket_count
* sizeof(__bucket_type
));
1031 __hashtable_base::operator=(std::move(__ht
));
1032 _M_element_count
= __ht
._M_element_count
;
1033 _M_rehash_policy
= __ht
._M_rehash_policy
;
1034 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
1035 _M_before_begin
._M_nxt
= nullptr;
1037 [&__roan
](__node_type
* __n
)
1038 { return __roan(std::move_if_noexcept(__n
->_M_v())); });
1043 if (__former_buckets
)
1045 _M_deallocate_buckets();
1046 _M_rehash_policy
._M_reset(__former_state
);
1047 _M_buckets
= __former_buckets
;
1048 _M_bucket_count
= __former_bucket_count
;
1050 __builtin_memset(_M_buckets
, 0,
1051 _M_bucket_count
* sizeof(__bucket_type
));
1052 __throw_exception_again
;
1057 template<typename _Key
, typename _Value
,
1058 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1059 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1061 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1062 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1063 _Hashtable(const _Hashtable
& __ht
)
1064 : __hashtable_base(__ht
),
1066 __rehash_base(__ht
),
1068 __node_alloc_traits::_S_select_on_copy(__ht
._M_node_allocator())),
1070 _M_bucket_count(__ht
._M_bucket_count
),
1071 _M_element_count(__ht
._M_element_count
),
1072 _M_rehash_policy(__ht
._M_rehash_policy
)
1075 [this](const __node_type
* __n
)
1076 { return this->_M_allocate_node(__n
->_M_v()); });
1079 template<typename _Key
, typename _Value
,
1080 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1081 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1083 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1084 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1085 _Hashtable(_Hashtable
&& __ht
) noexcept
1086 : __hashtable_base(__ht
),
1088 __rehash_base(__ht
),
1089 __hashtable_alloc(std::move(__ht
._M_base_alloc())),
1090 _M_buckets(__ht
._M_buckets
),
1091 _M_bucket_count(__ht
._M_bucket_count
),
1092 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
1093 _M_element_count(__ht
._M_element_count
),
1094 _M_rehash_policy(__ht
._M_rehash_policy
)
1096 // Update, if necessary, bucket pointing to before begin that hasn't
1099 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1103 template<typename _Key
, typename _Value
,
1104 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1105 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1107 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1108 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1109 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1110 : __hashtable_base(__ht
),
1112 __rehash_base(__ht
),
1113 __hashtable_alloc(__node_alloc_type(__a
)),
1115 _M_bucket_count(__ht
._M_bucket_count
),
1116 _M_element_count(__ht
._M_element_count
),
1117 _M_rehash_policy(__ht
._M_rehash_policy
)
1120 [this](const __node_type
* __n
)
1121 { return this->_M_allocate_node(__n
->_M_v()); });
1124 template<typename _Key
, typename _Value
,
1125 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1126 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1128 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1129 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1130 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
1131 : __hashtable_base(__ht
),
1133 __rehash_base(__ht
),
1134 __hashtable_alloc(__node_alloc_type(__a
)),
1136 _M_bucket_count(__ht
._M_bucket_count
),
1137 _M_element_count(__ht
._M_element_count
),
1138 _M_rehash_policy(__ht
._M_rehash_policy
)
1140 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1142 _M_buckets
= __ht
._M_buckets
;
1143 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1144 // Update, if necessary, bucket pointing to before begin that hasn't
1147 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1153 [this](__node_type
* __n
)
1155 return this->_M_allocate_node(
1156 std::move_if_noexcept(__n
->_M_v()));
1162 template<typename _Key
, typename _Value
,
1163 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1164 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1166 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1167 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1168 ~_Hashtable() noexcept
1172 _M_deallocate_buckets();
1175 template<typename _Key
, typename _Value
,
1176 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1177 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1180 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1181 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1182 swap(_Hashtable
& __x
)
1183 noexcept(__node_alloc_traits::_S_nothrow_swap())
1185 // The only base class with member variables is hash_code_base.
1186 // We define _Hash_code_base::_M_swap because different
1187 // specializations have different members.
1190 std::__alloc_on_swap(this->_M_node_allocator(), __x
._M_node_allocator());
1191 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1192 std::swap(_M_buckets
, __x
._M_buckets
);
1193 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1194 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
1195 std::swap(_M_element_count
, __x
._M_element_count
);
1197 // Fix buckets containing the _M_before_begin pointers that can't be
1200 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1202 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
1203 = &__x
._M_before_begin
;
1206 template<typename _Key
, typename _Value
,
1207 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1208 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1211 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1212 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1213 __rehash_policy(const _RehashPolicy
& __pol
)
1215 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
1216 __n_bkt
= __pol
._M_next_bkt(__n_bkt
);
1217 if (__n_bkt
!= _M_bucket_count
)
1218 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
1219 _M_rehash_policy
= __pol
;
1222 template<typename _Key
, typename _Value
,
1223 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1224 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1226 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1227 _H1
, _H2
, _Hash
, _RehashPolicy
,
1229 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1230 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1231 find(const key_type
& __k
)
1233 if (__builtin_expect(_M_bucket_count
== 0, false))
1236 __hash_code __code
= this->_M_hash_code(__k
);
1237 std::size_t __n
= _M_bucket_index(__k
, __code
);
1238 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1239 return __p
? iterator(__p
) : end();
1242 template<typename _Key
, typename _Value
,
1243 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1244 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1246 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1247 _H1
, _H2
, _Hash
, _RehashPolicy
,
1248 _Traits
>::const_iterator
1249 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1250 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1251 find(const key_type
& __k
) const
1253 if (__builtin_expect(_M_bucket_count
== 0, false))
1256 __hash_code __code
= this->_M_hash_code(__k
);
1257 std::size_t __n
= _M_bucket_index(__k
, __code
);
1258 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1259 return __p
? const_iterator(__p
) : end();
1262 template<typename _Key
, typename _Value
,
1263 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1264 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1266 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1267 _H1
, _H2
, _Hash
, _RehashPolicy
,
1269 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1270 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1271 count(const key_type
& __k
) const
1273 if (__builtin_expect(_M_bucket_count
== 0, false))
1276 __hash_code __code
= this->_M_hash_code(__k
);
1277 std::size_t __n
= _M_bucket_index(__k
, __code
);
1278 __node_type
* __p
= _M_bucket_begin(__n
);
1282 std::size_t __result
= 0;
1283 for (;; __p
= __p
->_M_next())
1285 if (this->_M_equals(__k
, __code
, __p
))
1288 // All equivalent values are next to each other, if we
1289 // found a non-equivalent value after an equivalent one it
1290 // means that we won't find any more equivalent values.
1292 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1298 template<typename _Key
, typename _Value
,
1299 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1300 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1302 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1303 _ExtractKey
, _Equal
, _H1
,
1304 _H2
, _Hash
, _RehashPolicy
,
1306 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1307 _ExtractKey
, _Equal
, _H1
,
1308 _H2
, _Hash
, _RehashPolicy
,
1310 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1311 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1312 equal_range(const key_type
& __k
)
1314 if (__builtin_expect(_M_bucket_count
== 0, false))
1315 return std::make_pair(end(), end());
1317 __hash_code __code
= this->_M_hash_code(__k
);
1318 std::size_t __n
= _M_bucket_index(__k
, __code
);
1319 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1323 __node_type
* __p1
= __p
->_M_next();
1324 while (__p1
&& _M_bucket_index(__p1
) == __n
1325 && this->_M_equals(__k
, __code
, __p1
))
1326 __p1
= __p1
->_M_next();
1328 return std::make_pair(iterator(__p
), iterator(__p1
));
1331 return std::make_pair(end(), end());
1334 template<typename _Key
, typename _Value
,
1335 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1336 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1338 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1339 _ExtractKey
, _Equal
, _H1
,
1340 _H2
, _Hash
, _RehashPolicy
,
1341 _Traits
>::const_iterator
,
1342 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1343 _ExtractKey
, _Equal
, _H1
,
1344 _H2
, _Hash
, _RehashPolicy
,
1345 _Traits
>::const_iterator
>
1346 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1347 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1348 equal_range(const key_type
& __k
) const
1350 if (__builtin_expect(_M_bucket_count
== 0, false))
1351 return std::make_pair(end(), end());
1353 __hash_code __code
= this->_M_hash_code(__k
);
1354 std::size_t __n
= _M_bucket_index(__k
, __code
);
1355 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1359 __node_type
* __p1
= __p
->_M_next();
1360 while (__p1
&& _M_bucket_index(__p1
) == __n
1361 && this->_M_equals(__k
, __code
, __p1
))
1362 __p1
= __p1
->_M_next();
1364 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1367 return std::make_pair(end(), end());
1370 // Find the node whose key compares equal to k in the bucket n.
1371 // Return nullptr if no node is found.
1372 template<typename _Key
, typename _Value
,
1373 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1374 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1376 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1377 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1378 _Traits
>::__node_base
*
1379 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1380 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1381 _M_find_before_node(size_type __n
, const key_type
& __k
,
1382 __hash_code __code
) const
1384 __node_base
* __prev_p
= _M_buckets
[__n
];
1388 for (__node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);;
1389 __p
= __p
->_M_next())
1391 if (this->_M_equals(__k
, __code
, __p
))
1394 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1401 template<typename _Key
, typename _Value
,
1402 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1403 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1406 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1407 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1408 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1410 if (_M_buckets
[__bkt
])
1412 // Bucket is not empty, we just need to insert the new node
1413 // after the bucket before begin.
1414 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1415 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1419 // The bucket is empty, the new node is inserted at the
1420 // beginning of the singly-linked list and the bucket will
1421 // contain _M_before_begin pointer.
1422 __node
->_M_nxt
= _M_before_begin
._M_nxt
;
1423 _M_before_begin
._M_nxt
= __node
;
1425 // We must update former begin bucket that is pointing to
1427 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1428 _M_buckets
[__bkt
] = &_M_before_begin
;
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_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1440 size_type __next_bkt
)
1442 if (!__next
|| __next_bkt
!= __bkt
)
1444 // Bucket is now empty
1445 // First update next bucket if any
1447 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1449 // Second update before begin node if necessary
1450 if (&_M_before_begin
== _M_buckets
[__bkt
])
1451 _M_before_begin
._M_nxt
= __next
;
1452 _M_buckets
[__bkt
] = nullptr;
1456 template<typename _Key
, typename _Value
,
1457 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1458 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1460 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1461 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1462 _Traits
>::__node_base
*
1463 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1464 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1465 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1467 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1468 while (__prev_n
->_M_nxt
!= __n
)
1469 __prev_n
= __prev_n
->_M_nxt
;
1473 template<typename _Key
, typename _Value
,
1474 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1475 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1477 template<typename
... _Args
>
1478 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1479 _ExtractKey
, _Equal
, _H1
,
1480 _H2
, _Hash
, _RehashPolicy
,
1481 _Traits
>::iterator
, bool>
1482 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1483 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1484 _M_emplace(std::true_type
, _Args
&&... __args
)
1486 // First build the node to get access to the hash code
1487 __node_type
* __node
= this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1488 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1492 __code
= this->_M_hash_code(__k
);
1496 this->_M_deallocate_node(__node
);
1497 __throw_exception_again
;
1500 size_type __bkt
= _M_bucket_index(__k
, __code
);
1501 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1503 // There is already an equivalent node, no insertion
1504 this->_M_deallocate_node(__node
);
1505 return std::make_pair(iterator(__p
), false);
1509 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1513 template<typename _Key
, typename _Value
,
1514 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1515 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1517 template<typename
... _Args
>
1518 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1519 _H1
, _H2
, _Hash
, _RehashPolicy
,
1521 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1522 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1523 _M_emplace(const_iterator __hint
, std::false_type
, _Args
&&... __args
)
1525 // First build the node to get its hash code.
1526 __node_type
* __node
=
1527 this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1532 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v()));
1536 this->_M_deallocate_node(__node
);
1537 __throw_exception_again
;
1540 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1543 template<typename _Key
, typename _Value
,
1544 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1545 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1547 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1548 _H1
, _H2
, _Hash
, _RehashPolicy
,
1550 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1551 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1552 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
1553 __node_type
* __node
)
1555 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1556 std::pair
<bool, std::size_t> __do_rehash
1557 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1561 if (__do_rehash
.first
)
1563 _M_rehash(__do_rehash
.second
, __saved_state
);
1564 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v()), __code
);
1567 this->_M_store_code(__node
, __code
);
1569 // Always insert at the beginning of the bucket.
1570 _M_insert_bucket_begin(__bkt
, __node
);
1572 return iterator(__node
);
1576 this->_M_deallocate_node(__node
);
1577 __throw_exception_again
;
1581 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1582 // already present). Take ownership of the node, deallocate it on exception.
1583 template<typename _Key
, typename _Value
,
1584 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1585 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1587 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1588 _H1
, _H2
, _Hash
, _RehashPolicy
,
1590 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1591 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1592 _M_insert_multi_node(__node_type
* __hint
, __hash_code __code
,
1593 __node_type
* __node
)
1595 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1596 std::pair
<bool, std::size_t> __do_rehash
1597 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1601 if (__do_rehash
.first
)
1602 _M_rehash(__do_rehash
.second
, __saved_state
);
1604 this->_M_store_code(__node
, __code
);
1605 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1606 size_type __bkt
= _M_bucket_index(__k
, __code
);
1608 // Find the node before an equivalent one or use hint if it exists and
1609 // if it is equivalent.
1611 = __builtin_expect(__hint
!= nullptr, false)
1612 && this->_M_equals(__k
, __code
, __hint
)
1614 : _M_find_before_node(__bkt
, __k
, __code
);
1617 // Insert after the node before the equivalent one.
1618 __node
->_M_nxt
= __prev
->_M_nxt
;
1619 __prev
->_M_nxt
= __node
;
1620 if (__builtin_expect(__prev
== __hint
, false))
1621 // hint might be the last bucket node, in this case we need to
1622 // update next bucket.
1624 && !this->_M_equals(__k
, __code
, __node
->_M_next()))
1626 size_type __next_bkt
= _M_bucket_index(__node
->_M_next());
1627 if (__next_bkt
!= __bkt
)
1628 _M_buckets
[__next_bkt
] = __node
;
1632 // The inserted node has no equivalent in the
1633 // hashtable. We must insert the new node at the
1634 // beginning of the bucket to preserve equivalent
1635 // elements' relative positions.
1636 _M_insert_bucket_begin(__bkt
, __node
);
1638 return iterator(__node
);
1642 this->_M_deallocate_node(__node
);
1643 __throw_exception_again
;
1647 // Insert v if no element with its key is already present.
1648 template<typename _Key
, typename _Value
,
1649 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1650 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1652 template<typename _Arg
, typename _NodeGenerator
>
1653 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1654 _ExtractKey
, _Equal
, _H1
,
1655 _H2
, _Hash
, _RehashPolicy
,
1656 _Traits
>::iterator
, bool>
1657 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1658 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1659 _M_insert(_Arg
&& __v
, const _NodeGenerator
& __node_gen
, std::true_type
)
1661 const key_type
& __k
= this->_M_extract()(__v
);
1662 __hash_code __code
= this->_M_hash_code(__k
);
1663 size_type __bkt
= _M_bucket_index(__k
, __code
);
1665 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1667 return std::make_pair(iterator(__n
), false);
1669 __n
= __node_gen(std::forward
<_Arg
>(__v
));
1670 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __n
), true);
1673 // Insert v unconditionally.
1674 template<typename _Key
, typename _Value
,
1675 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1676 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1678 template<typename _Arg
, typename _NodeGenerator
>
1679 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1680 _H1
, _H2
, _Hash
, _RehashPolicy
,
1682 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1683 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1684 _M_insert(const_iterator __hint
, _Arg
&& __v
,
1685 const _NodeGenerator
& __node_gen
,
1688 // First compute the hash code so that we don't do anything if it
1690 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1692 // Second allocate new node so that we don't rehash if it throws.
1693 __node_type
* __node
= __node_gen(std::forward
<_Arg
>(__v
));
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
,
1702 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1703 _H1
, _H2
, _Hash
, _RehashPolicy
,
1705 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1706 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1707 erase(const_iterator __it
)
1709 __node_type
* __n
= __it
._M_cur
;
1710 std::size_t __bkt
= _M_bucket_index(__n
);
1712 // Look for previous node to unlink it from the erased one, this
1713 // is why we need buckets to contain the before begin to make
1714 // this search fast.
1715 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1716 return _M_erase(__bkt
, __prev_n
, __n
);
1719 template<typename _Key
, typename _Value
,
1720 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1721 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1723 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1724 _H1
, _H2
, _Hash
, _RehashPolicy
,
1726 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1727 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1728 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1730 if (__prev_n
== _M_buckets
[__bkt
])
1731 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1732 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1733 else if (__n
->_M_nxt
)
1735 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1736 if (__next_bkt
!= __bkt
)
1737 _M_buckets
[__next_bkt
] = __prev_n
;
1740 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1741 iterator
__result(__n
->_M_next());
1742 this->_M_deallocate_node(__n
);
1748 template<typename _Key
, typename _Value
,
1749 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1750 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1752 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1753 _H1
, _H2
, _Hash
, _RehashPolicy
,
1755 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1756 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1757 _M_erase(std::true_type
, const key_type
& __k
)
1759 __hash_code __code
= this->_M_hash_code(__k
);
1760 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1762 // Look for the node before the first matching node.
1763 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1767 // We found a matching node, erase it.
1768 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1769 _M_erase(__bkt
, __prev_n
, __n
);
1773 template<typename _Key
, typename _Value
,
1774 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1775 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1777 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1778 _H1
, _H2
, _Hash
, _RehashPolicy
,
1780 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1781 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1782 _M_erase(std::false_type
, const key_type
& __k
)
1784 __hash_code __code
= this->_M_hash_code(__k
);
1785 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1787 // Look for the node before the first matching node.
1788 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1792 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1793 // 526. Is it undefined if a function in the standard changes
1795 // We use one loop to find all matching nodes and another to deallocate
1796 // them so that the key stays valid during the first loop. It might be
1797 // invalidated indirectly when destroying nodes.
1798 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1799 __node_type
* __n_last
= __n
;
1800 std::size_t __n_last_bkt
= __bkt
;
1803 __n_last
= __n_last
->_M_next();
1806 __n_last_bkt
= _M_bucket_index(__n_last
);
1808 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1810 // Deallocate nodes.
1811 size_type __result
= 0;
1814 __node_type
* __p
= __n
->_M_next();
1815 this->_M_deallocate_node(__n
);
1820 while (__n
!= __n_last
);
1822 if (__prev_n
== _M_buckets
[__bkt
])
1823 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1824 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1825 _M_buckets
[__n_last_bkt
] = __prev_n
;
1826 __prev_n
->_M_nxt
= __n_last
;
1830 template<typename _Key
, typename _Value
,
1831 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1832 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1834 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1835 _H1
, _H2
, _Hash
, _RehashPolicy
,
1837 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1838 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1839 erase(const_iterator __first
, const_iterator __last
)
1841 __node_type
* __n
= __first
._M_cur
;
1842 __node_type
* __last_n
= __last
._M_cur
;
1843 if (__n
== __last_n
)
1844 return iterator(__n
);
1846 std::size_t __bkt
= _M_bucket_index(__n
);
1848 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1849 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1850 std::size_t __n_bkt
= __bkt
;
1855 __node_type
* __tmp
= __n
;
1856 __n
= __n
->_M_next();
1857 this->_M_deallocate_node(__tmp
);
1861 __n_bkt
= _M_bucket_index(__n
);
1863 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1864 if (__is_bucket_begin
)
1865 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1866 if (__n
== __last_n
)
1868 __is_bucket_begin
= true;
1872 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
1873 _M_buckets
[__n_bkt
] = __prev_n
;
1874 __prev_n
->_M_nxt
= __n
;
1875 return iterator(__n
);
1878 template<typename _Key
, typename _Value
,
1879 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1880 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1883 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1884 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1887 this->_M_deallocate_nodes(_M_begin());
1888 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
1889 _M_element_count
= 0;
1890 _M_before_begin
._M_nxt
= nullptr;
1893 template<typename _Key
, typename _Value
,
1894 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1895 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1898 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1899 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1900 rehash(size_type __n
)
1902 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1903 std::size_t __buckets
1904 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
1906 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
1908 if (__buckets
!= _M_bucket_count
)
1909 _M_rehash(__buckets
, __saved_state
);
1911 // No rehash, restore previous state to keep a consistent state.
1912 _M_rehash_policy
._M_reset(__saved_state
);
1915 template<typename _Key
, typename _Value
,
1916 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1917 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1920 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1921 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1922 _M_rehash(size_type __n
, const __rehash_state
& __state
)
1926 _M_rehash_aux(__n
, __unique_keys());
1930 // A failure here means that buckets allocation failed. We only
1931 // have to restore hash policy previous state.
1932 _M_rehash_policy
._M_reset(__state
);
1933 __throw_exception_again
;
1937 // Rehash when there is no equivalent elements.
1938 template<typename _Key
, typename _Value
,
1939 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1940 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1943 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1944 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1945 _M_rehash_aux(size_type __n
, std::true_type
)
1947 __bucket_type
* __new_buckets
= this->_M_allocate_buckets(__n
);
1948 __node_type
* __p
= _M_begin();
1949 _M_before_begin
._M_nxt
= nullptr;
1950 std::size_t __bbegin_bkt
= 0;
1953 __node_type
* __next
= __p
->_M_next();
1954 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1955 if (!__new_buckets
[__bkt
])
1957 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
1958 _M_before_begin
._M_nxt
= __p
;
1959 __new_buckets
[__bkt
] = &_M_before_begin
;
1961 __new_buckets
[__bbegin_bkt
] = __p
;
1962 __bbegin_bkt
= __bkt
;
1966 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1967 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1972 if (__builtin_expect(_M_bucket_count
!= 0, true))
1973 _M_deallocate_buckets();
1974 _M_bucket_count
= __n
;
1975 _M_buckets
= __new_buckets
;
1978 // Rehash when there can be equivalent elements, preserve their relative
1980 template<typename _Key
, typename _Value
,
1981 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1982 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1985 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1986 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1987 _M_rehash_aux(size_type __n
, std::false_type
)
1989 __bucket_type
* __new_buckets
= this->_M_allocate_buckets(__n
);
1991 __node_type
* __p
= _M_begin();
1992 _M_before_begin
._M_nxt
= nullptr;
1993 std::size_t __bbegin_bkt
= 0;
1994 std::size_t __prev_bkt
= 0;
1995 __node_type
* __prev_p
= nullptr;
1996 bool __check_bucket
= false;
2000 __node_type
* __next
= __p
->_M_next();
2001 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2003 if (__prev_p
&& __prev_bkt
== __bkt
)
2005 // Previous insert was already in this bucket, we insert after
2006 // the previously inserted one to preserve equivalent elements
2008 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2009 __prev_p
->_M_nxt
= __p
;
2011 // Inserting after a node in a bucket require to check that we
2012 // haven't change the bucket last node, in this case next
2013 // bucket containing its before begin node must be updated. We
2014 // schedule a check as soon as we move out of the sequence of
2015 // equivalent nodes to limit the number of checks.
2016 __check_bucket
= true;
2022 // Check if we shall update the next bucket because of
2023 // insertions into __prev_bkt bucket.
2024 if (__prev_p
->_M_nxt
)
2026 std::size_t __next_bkt
2027 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
2029 if (__next_bkt
!= __prev_bkt
)
2030 __new_buckets
[__next_bkt
] = __prev_p
;
2032 __check_bucket
= false;
2035 if (!__new_buckets
[__bkt
])
2037 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2038 _M_before_begin
._M_nxt
= __p
;
2039 __new_buckets
[__bkt
] = &_M_before_begin
;
2041 __new_buckets
[__bbegin_bkt
] = __p
;
2042 __bbegin_bkt
= __bkt
;
2046 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2047 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2055 if (__check_bucket
&& __prev_p
->_M_nxt
)
2057 std::size_t __next_bkt
2058 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
2059 if (__next_bkt
!= __prev_bkt
)
2060 __new_buckets
[__next_bkt
] = __prev_p
;
2063 if (__builtin_expect(_M_bucket_count
!= 0, true))
2064 _M_deallocate_buckets();
2065 _M_bucket_count
= __n
;
2066 _M_buckets
= __new_buckets
;
2069 _GLIBCXX_END_NAMESPACE_VERSION
2072 #endif // _HASHTABLE_H