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 make local_iterator default
46 // constructible and assignable.
47 is_default_constructible
<_Hash
>,
48 is_copy_assignable
<_Hash
>,
49 // Mandatory to have erase not throwing.
50 __detail::__is_noexcept_hash
<_Tp
, _Hash
>>>;
53 * Primary class template _Hashtable.
55 * @ingroup hashtable-detail
57 * @tparam _Value CopyConstructible type.
59 * @tparam _Key CopyConstructible type.
61 * @tparam _Alloc An allocator type
62 * ([lib.allocator.requirements]) whose _Alloc::value_type is
63 * _Value. As a conforming extension, we allow for
64 * _Alloc::value_type != _Value.
66 * @tparam _ExtractKey Function object that takes an object of type
67 * _Value and returns a value of type _Key.
69 * @tparam _Equal Function object that takes two objects of type k
70 * and returns a bool-like value that is true if the two objects
71 * are considered equal.
73 * @tparam _H1 The hash function. A unary function object with
74 * argument type _Key and result type size_t. Return values should
75 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
77 * @tparam _H2 The range-hashing function (in the terminology of
78 * Tavori and Dreizin). A binary function object whose argument
79 * types and result type are all size_t. Given arguments r and N,
80 * the return value is in the range [0, N).
82 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
83 * binary function whose argument types are _Key and size_t and
84 * whose result type is size_t. Given arguments k and N, the
85 * return value is in the range [0, N). Default: hash(k, N) =
86 * h2(h1(k), N). If _Hash is anything other than the default, _H1
87 * and _H2 are ignored.
89 * @tparam _RehashPolicy Policy class with three members, all of
90 * which govern the bucket count. _M_next_bkt(n) returns a bucket
91 * count no smaller than n. _M_bkt_for_elements(n) returns a
92 * bucket count appropriate for an element count of n.
93 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
94 * current bucket count is n_bkt and the current element count is
95 * n_elt, we need to increase the bucket count. If so, returns
96 * make_pair(true, n), where n is the new bucket count. If not,
97 * returns make_pair(false, <anything>)
99 * @tparam _Traits Compile-time class with three boolean
100 * std::integral_constant members: __cache_hash_code, __constant_iterators,
103 * Each _Hashtable data structure has:
105 * - _Bucket[] _M_buckets
106 * - _Hash_node_base _M_before_begin
107 * - size_type _M_bucket_count
108 * - size_type _M_element_count
110 * with _Bucket being _Hash_node* and _Hash_node containing:
112 * - _Hash_node* _M_next
114 * - size_t _M_hash_code if cache_hash_code is true
116 * In terms of Standard containers the hashtable is like the aggregation of:
118 * - std::forward_list<_Node> containing the elements
119 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
121 * The non-empty buckets contain the node before the first node in the
122 * bucket. This design makes it possible to implement something like a
123 * std::forward_list::insert_after on container insertion and
124 * std::forward_list::erase_after on container erase
125 * calls. _M_before_begin is equivalent to
126 * std::forward_list::before_begin. Empty buckets contain
127 * nullptr. Note that one of the non-empty buckets contains
128 * &_M_before_begin which is not a dereferenceable node so the
129 * node pointer in a bucket shall never be dereferenced, only its
132 * Walking through a bucket's nodes requires a check on the hash code to
133 * see if each node is still in the bucket. Such a design assumes a
134 * quite efficient hash functor and is one of the reasons it is
135 * highly advisable to set __cache_hash_code to true.
137 * The container iterators are simply built from nodes. This way
138 * incrementing the iterator is perfectly efficient independent of
139 * how many empty buckets there are in the container.
141 * On insert we compute the element's hash code and use it to find the
142 * bucket index. If the element must be inserted in an empty bucket
143 * we add it at the beginning of the singly linked list and make the
144 * bucket point to _M_before_begin. The bucket that used to point to
145 * _M_before_begin, if any, is updated to point to its new before
148 * On erase, the simple iterator design requires using the hash
149 * functor to get the index of the bucket to update. For this
150 * reason, when __cache_hash_code is set to false the hash functor must
151 * not throw and this is enforced by a static assertion.
153 * Functionality is implemented by decomposition into base classes,
154 * where the derived _Hashtable class is used in _Map_base,
155 * _Insert, _Rehash_base, and _Equality base classes to access the
156 * "this" pointer. _Hashtable_base is used in the base classes as a
157 * non-recursive, fully-completed-type so that detailed nested type
158 * information, such as iterator type and node type, can be
159 * used. This is similar to the "Curiously Recurring Template
160 * Pattern" (CRTP) technique, but uses a reconstructed, not
161 * explicitly passed, template pattern.
163 * Base class templates are:
164 * - __detail::_Hashtable_base
165 * - __detail::_Map_base
166 * - __detail::_Insert
167 * - __detail::_Rehash_base
168 * - __detail::_Equality
170 template<typename _Key
, typename _Value
, typename _Alloc
,
171 typename _ExtractKey
, typename _Equal
,
172 typename _H1
, typename _H2
, typename _Hash
,
173 typename _RehashPolicy
, typename _Traits
>
175 : public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
176 _H1
, _H2
, _Hash
, _Traits
>,
177 public __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
178 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
179 public __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
180 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
181 public __detail::_Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
182 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
183 public __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
184 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
185 private __detail::_Hashtable_alloc
<
186 typename __alloctr_rebind
<_Alloc
,
187 __detail::_Hash_node
<_Value
,
188 _Traits::__hash_cached::value
> >::__type
>
190 using __traits_type
= _Traits
;
191 using __hash_cached
= typename
__traits_type::__hash_cached
;
192 using __node_type
= __detail::_Hash_node
<_Value
, __hash_cached::value
>;
193 using __node_alloc_type
=
194 typename __alloctr_rebind
<_Alloc
, __node_type
>::__type
;
196 using __hashtable_alloc
= __detail::_Hashtable_alloc
<__node_alloc_type
>;
198 using __value_alloc_traits
=
199 typename
__hashtable_alloc::__value_alloc_traits
;
200 using __node_alloc_traits
=
201 typename
__hashtable_alloc::__node_alloc_traits
;
202 using __node_base
= typename
__hashtable_alloc::__node_base
;
203 using __bucket_type
= typename
__hashtable_alloc::__bucket_type
;
206 typedef _Key key_type
;
207 typedef _Value value_type
;
208 typedef _Alloc allocator_type
;
209 typedef _Equal key_equal
;
211 // mapped_type, if present, comes from _Map_base.
212 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
213 typedef typename
__value_alloc_traits::pointer pointer
;
214 typedef typename
__value_alloc_traits::const_pointer const_pointer
;
215 typedef value_type
& reference
;
216 typedef const value_type
& const_reference
;
219 using __rehash_type
= _RehashPolicy
;
220 using __rehash_state
= typename
__rehash_type::_State
;
222 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
223 using __unique_keys
= typename
__traits_type::__unique_keys
;
225 using __key_extract
= typename
std::conditional
<
226 __constant_iterators::value
,
228 __detail::_Select1st
>::type
;
230 using __hashtable_base
= __detail::
231 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
232 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
234 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
235 using __hash_code
= typename
__hashtable_base::__hash_code
;
236 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
238 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
239 _Equal
, _H1
, _H2
, _Hash
,
240 _RehashPolicy
, _Traits
>;
242 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
245 _RehashPolicy
, _Traits
>;
247 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
248 _Equal
, _H1
, _H2
, _Hash
,
249 _RehashPolicy
, _Traits
>;
251 using __reuse_or_alloc_node_type
=
252 __detail::_ReuseOrAllocNode
<__node_alloc_type
>;
254 // Metaprogramming for picking apart hash caching.
255 template<typename _Cond
>
256 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
258 template<typename _Cond
>
259 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
261 // Compile-time diagnostics.
263 // _Hash_code_base has everything protected, so use this derived type to
265 struct __hash_code_base_access
: __hash_code_base
266 { using __hash_code_base::_M_bucket_index
; };
268 // Getting a bucket index from a node shall not throw because it is used
269 // in methods (erase, swap...) that shall not throw.
270 static_assert(noexcept(declval
<const __hash_code_base_access
&>()
271 ._M_bucket_index((const __node_type
*)nullptr,
273 "Cache the hash code or qualify your functors involved"
274 " in hash code and bucket index computation with noexcept");
276 // Following two static assertions are necessary to guarantee
277 // that local_iterator will be default constructible.
279 // When hash codes are cached local iterator inherits from H2 functor
280 // which must then be default constructible.
281 static_assert(__if_hash_cached
<is_default_constructible
<_H2
>>::value
,
282 "Functor used to map hash code to bucket index"
283 " must be default constructible");
285 // When hash codes are not cached local iterator inherits from
286 // __hash_code_base above to compute node bucket index so it has to be
287 // default constructible.
288 static_assert(__if_hash_not_cached
<
289 is_default_constructible
<__hash_code_base_access
>>::value
,
290 "Cache the hash code or make functors involved in hash code"
291 " and bucket index computation default constructible");
293 // When hash codes are not cached local iterator inherits from
294 // __hash_code_base above to compute node bucket index so it has to be
296 static_assert(__if_hash_not_cached
<
297 is_copy_assignable
<__hash_code_base
>>::value
,
298 "Cache the hash code or make functors involved in hash code"
299 " and bucket index computation copy assignable");
301 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
302 typename _ExtractKeya
, typename _Equala
,
303 typename _H1a
, typename _H2a
, typename _Hasha
,
304 typename _RehashPolicya
, typename _Traitsa
,
306 friend struct __detail::_Map_base
;
308 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
309 typename _ExtractKeya
, typename _Equala
,
310 typename _H1a
, typename _H2a
, typename _Hasha
,
311 typename _RehashPolicya
, typename _Traitsa
>
312 friend struct __detail::_Insert_base
;
314 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
315 typename _ExtractKeya
, typename _Equala
,
316 typename _H1a
, typename _H2a
, typename _Hasha
,
317 typename _RehashPolicya
, typename _Traitsa
,
318 bool _Constant_iteratorsa
, bool _Unique_keysa
>
319 friend struct __detail::_Insert
;
322 using size_type
= typename
__hashtable_base::size_type
;
323 using difference_type
= typename
__hashtable_base::difference_type
;
325 using iterator
= typename
__hashtable_base::iterator
;
326 using const_iterator
= typename
__hashtable_base::const_iterator
;
328 using local_iterator
= typename
__hashtable_base::local_iterator
;
329 using const_local_iterator
= typename
__hashtable_base::
330 const_local_iterator
;
333 __bucket_type
* _M_buckets
;
334 size_type _M_bucket_count
;
335 __node_base _M_before_begin
;
336 size_type _M_element_count
;
337 _RehashPolicy _M_rehash_policy
;
340 _M_base_alloc() { return *this; }
342 using __hashtable_alloc::_M_deallocate_buckets
;
345 _M_deallocate_buckets()
346 { this->_M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
348 // Gets bucket begin, deals with the fact that non-empty buckets contain
349 // their before begin node.
351 _M_bucket_begin(size_type __bkt
) const;
355 { return static_cast<__node_type
*>(_M_before_begin
._M_nxt
); }
357 template<typename _NodeGenerator
>
359 _M_assign(const _Hashtable
&, const _NodeGenerator
&);
362 _M_move_assign(_Hashtable
&&, std::true_type
);
365 _M_move_assign(_Hashtable
&&, std::false_type
);
371 // Constructor, destructor, assignment, swap
372 _Hashtable(size_type __bucket_hint
,
373 const _H1
&, const _H2
&, const _Hash
&,
374 const _Equal
&, const _ExtractKey
&,
375 const allocator_type
&);
377 template<typename _InputIterator
>
378 _Hashtable(_InputIterator __first
, _InputIterator __last
,
379 size_type __bucket_hint
,
380 const _H1
&, const _H2
&, const _Hash
&,
381 const _Equal
&, const _ExtractKey
&,
382 const allocator_type
&);
384 _Hashtable(const _Hashtable
&);
386 _Hashtable(_Hashtable
&&) noexcept
;
388 _Hashtable(const _Hashtable
&, const allocator_type
&);
390 _Hashtable(_Hashtable
&&, const allocator_type
&);
392 // Use delegating constructors.
394 _Hashtable(const allocator_type
& __a
)
395 : _Hashtable(10, _H1(), __detail::_Mod_range_hashing(),
396 __detail::_Default_ranged_hash(), key_equal(),
397 __key_extract(), __a
)
401 _Hashtable(size_type __n
= 10,
402 const _H1
& __hf
= _H1(),
403 const key_equal
& __eql
= key_equal(),
404 const allocator_type
& __a
= allocator_type())
405 : _Hashtable(__n
, __hf
, __detail::_Mod_range_hashing(),
406 __detail::_Default_ranged_hash(), __eql
,
407 __key_extract(), __a
)
410 template<typename _InputIterator
>
411 _Hashtable(_InputIterator __f
, _InputIterator __l
,
413 const _H1
& __hf
= _H1(),
414 const key_equal
& __eql
= key_equal(),
415 const allocator_type
& __a
= allocator_type())
416 : _Hashtable(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
417 __detail::_Default_ranged_hash(), __eql
,
418 __key_extract(), __a
)
421 _Hashtable(initializer_list
<value_type
> __l
,
423 const _H1
& __hf
= _H1(),
424 const key_equal
& __eql
= key_equal(),
425 const allocator_type
& __a
= allocator_type())
426 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
,
427 __detail::_Mod_range_hashing(),
428 __detail::_Default_ranged_hash(), __eql
,
429 __key_extract(), __a
)
433 operator=(const _Hashtable
& __ht
);
436 operator=(_Hashtable
&& __ht
)
437 noexcept(__node_alloc_traits::_S_nothrow_move())
439 constexpr bool __move_storage
=
440 __node_alloc_traits::_S_propagate_on_move_assign()
441 || __node_alloc_traits::_S_always_equal();
442 _M_move_assign(std::move(__ht
),
443 integral_constant
<bool, __move_storage
>());
448 operator=(initializer_list
<value_type
> __l
)
450 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
451 _M_before_begin
._M_nxt
= nullptr;
453 this->_M_insert_range(__l
.begin(), __l
.end(), __roan
);
457 ~_Hashtable() noexcept
;
461 noexcept(__node_alloc_traits::_S_nothrow_swap());
463 // Basic container operations
466 { return iterator(_M_begin()); }
469 begin() const noexcept
470 { return const_iterator(_M_begin()); }
474 { return iterator(nullptr); }
478 { return const_iterator(nullptr); }
481 cbegin() const noexcept
482 { return const_iterator(_M_begin()); }
485 cend() const noexcept
486 { return const_iterator(nullptr); }
489 size() const noexcept
490 { return _M_element_count
; }
493 empty() const noexcept
494 { return size() == 0; }
497 get_allocator() const noexcept
498 { return allocator_type(this->_M_node_allocator()); }
501 max_size() const noexcept
502 { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
507 { return this->_M_eq(); }
509 // hash_function, if present, comes from _Hash_code_base.
513 bucket_count() const noexcept
514 { return _M_bucket_count
; }
517 max_bucket_count() const noexcept
518 { return max_size(); }
521 bucket_size(size_type __n
) const
522 { return std::distance(begin(__n
), end(__n
)); }
525 bucket(const key_type
& __k
) const
526 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
531 return local_iterator(*this, _M_bucket_begin(__n
),
532 __n
, _M_bucket_count
);
537 { return local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
540 begin(size_type __n
) const
542 return const_local_iterator(*this, _M_bucket_begin(__n
),
543 __n
, _M_bucket_count
);
547 end(size_type __n
) const
548 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
552 cbegin(size_type __n
) const
554 return const_local_iterator(*this, _M_bucket_begin(__n
),
555 __n
, _M_bucket_count
);
559 cend(size_type __n
) const
560 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
563 load_factor() const noexcept
565 return static_cast<float>(size()) / static_cast<float>(bucket_count());
568 // max_load_factor, if present, comes from _Rehash_base.
570 // Generalization of max_load_factor. Extension, not found in
571 // TR1. Only useful if _RehashPolicy is something other than
574 __rehash_policy() const
575 { return _M_rehash_policy
; }
578 __rehash_policy(const _RehashPolicy
&);
582 find(const key_type
& __k
);
585 find(const key_type
& __k
) const;
588 count(const key_type
& __k
) const;
590 std::pair
<iterator
, iterator
>
591 equal_range(const key_type
& __k
);
593 std::pair
<const_iterator
, const_iterator
>
594 equal_range(const key_type
& __k
) const;
597 // Bucket index computation helpers.
599 _M_bucket_index(__node_type
* __n
) const noexcept
600 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
603 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
604 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
606 // Find and insert helper functions and types
607 // Find the node before the one matching the criteria.
609 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
612 _M_find_node(size_type __bkt
, const key_type
& __key
,
613 __hash_code __c
) const
615 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
617 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
621 // Insert a node at the beginning of a bucket.
623 _M_insert_bucket_begin(size_type
, __node_type
*);
625 // Remove the bucket first node
627 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
628 size_type __next_bkt
);
630 // Get the node before __n in the bucket __bkt
632 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
634 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
635 // no element with its key already present). Take ownership of the node,
636 // deallocate it on exception.
638 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
641 // Insert node with hash code __code. Take ownership of the node,
642 // deallocate it on exception.
644 _M_insert_multi_node(__node_type
* __hint
,
645 __hash_code __code
, __node_type
* __n
);
647 template<typename
... _Args
>
648 std::pair
<iterator
, bool>
649 _M_emplace(std::true_type
, _Args
&&... __args
);
651 template<typename
... _Args
>
653 _M_emplace(std::false_type __uk
, _Args
&&... __args
)
654 { return _M_emplace(cend(), __uk
, std::forward
<_Args
>(__args
)...); }
656 // Emplace with hint, useless when keys are unique.
657 template<typename
... _Args
>
659 _M_emplace(const_iterator
, std::true_type __uk
, _Args
&&... __args
)
660 { return _M_emplace(__uk
, std::forward
<_Args
>(__args
)...).first
; }
662 template<typename
... _Args
>
664 _M_emplace(const_iterator
, std::false_type
, _Args
&&... __args
);
666 template<typename _Arg
, typename _NodeGenerator
>
667 std::pair
<iterator
, bool>
668 _M_insert(_Arg
&&, const _NodeGenerator
&, std::true_type
);
670 template<typename _Arg
, typename _NodeGenerator
>
672 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
673 std::false_type __uk
)
675 return _M_insert(cend(), std::forward
<_Arg
>(__arg
), __node_gen
,
679 // Insert with hint, not used when keys are unique.
680 template<typename _Arg
, typename _NodeGenerator
>
682 _M_insert(const_iterator
, _Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
686 _M_insert(std::forward
<_Arg
>(__arg
), __node_gen
, __uk
).first
;
689 // Insert with hint when keys are not unique.
690 template<typename _Arg
, typename _NodeGenerator
>
692 _M_insert(const_iterator
, _Arg
&&, const _NodeGenerator
&, std::false_type
);
695 _M_erase(std::true_type
, const key_type
&);
698 _M_erase(std::false_type
, const key_type
&);
701 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
705 template<typename
... _Args
>
707 emplace(_Args
&&... __args
)
708 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
710 template<typename
... _Args
>
712 emplace_hint(const_iterator __hint
, _Args
&&... __args
)
714 return _M_emplace(__hint
, __unique_keys(),
715 std::forward
<_Args
>(__args
)...);
718 // Insert member functions via inheritance.
722 erase(const_iterator
);
727 { return erase(const_iterator(__it
)); }
730 erase(const key_type
& __k
)
732 if (__builtin_expect(_M_bucket_count
== 0, false))
734 return _M_erase(__unique_keys(), __k
);
738 erase(const_iterator
, const_iterator
);
743 // Set number of buckets to be appropriate for container of n element.
744 void rehash(size_type __n
);
747 // reserve, if present, comes from _Rehash_base.
750 // Helper rehash method used when keys are unique.
751 void _M_rehash_aux(size_type __n
, std::true_type
);
753 // Helper rehash method used when keys can be non-unique.
754 void _M_rehash_aux(size_type __n
, std::false_type
);
756 // Unconditionally change size of bucket array to n, restore
757 // hash policy state to __state on exception.
758 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
762 // Definitions of class template _Hashtable's out-of-line member functions.
763 template<typename _Key
, typename _Value
,
764 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
765 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
767 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
768 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
769 _Traits
>::__node_type
*
770 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
771 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
772 _M_bucket_begin(size_type __bkt
) const
774 __node_base
* __n
= _M_buckets
[__bkt
];
775 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
778 template<typename _Key
, typename _Value
,
779 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
780 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
782 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
783 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
784 _Hashtable(size_type __bucket_hint
,
785 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
786 const _Equal
& __eq
, const _ExtractKey
& __exk
,
787 const allocator_type
& __a
)
788 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
791 __hashtable_alloc(__node_alloc_type(__a
)),
795 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
796 _M_buckets
= this->_M_allocate_buckets(_M_bucket_count
);
799 template<typename _Key
, typename _Value
,
800 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
801 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
803 template<typename _InputIterator
>
804 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
805 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
806 _Hashtable(_InputIterator __f
, _InputIterator __l
,
807 size_type __bucket_hint
,
808 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
809 const _Equal
& __eq
, const _ExtractKey
& __exk
,
810 const allocator_type
& __a
)
811 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
814 __hashtable_alloc(__node_alloc_type(__a
)),
818 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
820 _M_rehash_policy
._M_next_bkt(
821 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
824 _M_buckets
= this->_M_allocate_buckets(_M_bucket_count
);
827 for (; __f
!= __l
; ++__f
)
833 _M_deallocate_buckets();
834 __throw_exception_again
;
838 template<typename _Key
, typename _Value
,
839 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
840 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
842 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
843 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>&
844 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
845 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::operator=(
846 const _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
847 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>& __ht
)
852 if (__node_alloc_traits::_S_propagate_on_copy_assign())
854 auto& __this_alloc
= this->_M_node_allocator();
855 auto& __that_alloc
= __ht
._M_node_allocator();
856 if (!__node_alloc_traits::_S_always_equal()
857 && __this_alloc
!= __that_alloc
)
859 // Replacement allocator cannot free existing storage.
860 this->_M_deallocate_nodes(_M_begin());
861 if (__builtin_expect(_M_bucket_count
!= 0, true))
862 _M_deallocate_buckets();
864 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
865 __hashtable_base::operator=(__ht
);
866 _M_bucket_count
= __ht
._M_bucket_count
;
867 _M_element_count
= __ht
._M_element_count
;
868 _M_rehash_policy
= __ht
._M_rehash_policy
;
872 [this](const __node_type
* __n
)
873 { return this->_M_allocate_node(__n
->_M_v()); });
877 // _M_assign took care of deallocating all memory. Now we
878 // must make sure this instance remains in a usable state.
880 __throw_exception_again
;
884 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
887 // Reuse allocated buckets and nodes.
888 __bucket_type
* __former_buckets
= nullptr;
889 std::size_t __former_bucket_count
= _M_bucket_count
;
890 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
892 if (_M_bucket_count
!= __ht
._M_bucket_count
)
894 __former_buckets
= _M_buckets
;
895 _M_buckets
= this->_M_allocate_buckets(__ht
._M_bucket_count
);
896 _M_bucket_count
= __ht
._M_bucket_count
;
899 __builtin_memset(_M_buckets
, 0,
900 _M_bucket_count
* sizeof(__bucket_type
));
904 __hashtable_base::operator=(__ht
);
905 _M_element_count
= __ht
._M_element_count
;
906 _M_rehash_policy
= __ht
._M_rehash_policy
;
907 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
908 _M_before_begin
._M_nxt
= nullptr;
910 [&__roan
](const __node_type
* __n
)
911 { return __roan(__n
->_M_v()); });
912 if (__former_buckets
)
913 this->_M_deallocate_buckets(__former_buckets
,
914 __former_bucket_count
);
918 if (__former_buckets
)
920 // Restore previous buckets.
921 _M_deallocate_buckets();
922 _M_rehash_policy
._M_reset(__former_state
);
923 _M_buckets
= __former_buckets
;
924 _M_bucket_count
= __former_bucket_count
;
926 __builtin_memset(_M_buckets
, 0,
927 _M_bucket_count
* sizeof(__bucket_type
));
928 __throw_exception_again
;
933 template<typename _Key
, typename _Value
,
934 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
935 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
937 template<typename _NodeGenerator
>
939 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
940 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
941 _M_assign(const _Hashtable
& __ht
, const _NodeGenerator
& __node_gen
)
943 __bucket_type
* __buckets
= nullptr;
945 _M_buckets
= __buckets
= this->_M_allocate_buckets(_M_bucket_count
);
949 if (!__ht
._M_before_begin
._M_nxt
)
952 // First deal with the special first node pointed to by
954 __node_type
* __ht_n
= __ht
._M_begin();
955 __node_type
* __this_n
= __node_gen(__ht_n
);
956 this->_M_copy_code(__this_n
, __ht_n
);
957 _M_before_begin
._M_nxt
= __this_n
;
958 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin
;
960 // Then deal with other nodes.
961 __node_base
* __prev_n
= __this_n
;
962 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
964 __this_n
= __node_gen(__ht_n
);
965 __prev_n
->_M_nxt
= __this_n
;
966 this->_M_copy_code(__this_n
, __ht_n
);
967 size_type __bkt
= _M_bucket_index(__this_n
);
968 if (!_M_buckets
[__bkt
])
969 _M_buckets
[__bkt
] = __prev_n
;
977 _M_deallocate_buckets();
978 __throw_exception_again
;
982 template<typename _Key
, typename _Value
,
983 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
984 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
987 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
988 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
991 _M_rehash_policy
._M_reset();
993 _M_buckets
= nullptr;
994 _M_before_begin
._M_nxt
= nullptr;
995 _M_element_count
= 0;
998 template<typename _Key
, typename _Value
,
999 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1000 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1003 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1004 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1005 _M_move_assign(_Hashtable
&& __ht
, std::true_type
)
1007 this->_M_deallocate_nodes(_M_begin());
1008 if (__builtin_expect(_M_bucket_count
!= 0, true))
1009 _M_deallocate_buckets();
1011 __hashtable_base::operator=(std::move(__ht
));
1012 _M_rehash_policy
= __ht
._M_rehash_policy
;
1013 _M_buckets
= __ht
._M_buckets
;
1014 _M_bucket_count
= __ht
._M_bucket_count
;
1015 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1016 _M_element_count
= __ht
._M_element_count
;
1017 std::__alloc_on_move(this->_M_node_allocator(), __ht
._M_node_allocator());
1019 // Fix buckets containing the _M_before_begin pointers that can't be
1022 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1026 template<typename _Key
, typename _Value
,
1027 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1028 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1031 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1032 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1033 _M_move_assign(_Hashtable
&& __ht
, std::false_type
)
1035 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1036 _M_move_assign(std::move(__ht
), std::true_type());
1039 // Can't move memory, move elements then.
1040 __bucket_type
* __former_buckets
= nullptr;
1041 size_type __former_bucket_count
= _M_bucket_count
;
1042 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1044 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1046 __former_buckets
= _M_buckets
;
1047 _M_buckets
= this->_M_allocate_buckets(__ht
._M_bucket_count
);
1048 _M_bucket_count
= __ht
._M_bucket_count
;
1051 __builtin_memset(_M_buckets
, 0,
1052 _M_bucket_count
* sizeof(__bucket_type
));
1056 __hashtable_base::operator=(std::move(__ht
));
1057 _M_element_count
= __ht
._M_element_count
;
1058 _M_rehash_policy
= __ht
._M_rehash_policy
;
1059 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
1060 _M_before_begin
._M_nxt
= nullptr;
1062 [&__roan
](__node_type
* __n
)
1063 { return __roan(std::move_if_noexcept(__n
->_M_v())); });
1068 if (__former_buckets
)
1070 _M_deallocate_buckets();
1071 _M_rehash_policy
._M_reset(__former_state
);
1072 _M_buckets
= __former_buckets
;
1073 _M_bucket_count
= __former_bucket_count
;
1075 __builtin_memset(_M_buckets
, 0,
1076 _M_bucket_count
* sizeof(__bucket_type
));
1077 __throw_exception_again
;
1082 template<typename _Key
, typename _Value
,
1083 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1084 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1086 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1087 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1088 _Hashtable(const _Hashtable
& __ht
)
1089 : __hashtable_base(__ht
),
1091 __rehash_base(__ht
),
1093 __node_alloc_traits::_S_select_on_copy(__ht
._M_node_allocator())),
1095 _M_bucket_count(__ht
._M_bucket_count
),
1096 _M_element_count(__ht
._M_element_count
),
1097 _M_rehash_policy(__ht
._M_rehash_policy
)
1100 [this](const __node_type
* __n
)
1101 { return this->_M_allocate_node(__n
->_M_v()); });
1104 template<typename _Key
, typename _Value
,
1105 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1106 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1108 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1109 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1110 _Hashtable(_Hashtable
&& __ht
) noexcept
1111 : __hashtable_base(__ht
),
1113 __rehash_base(__ht
),
1114 __hashtable_alloc(std::move(__ht
._M_base_alloc())),
1115 _M_buckets(__ht
._M_buckets
),
1116 _M_bucket_count(__ht
._M_bucket_count
),
1117 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
1118 _M_element_count(__ht
._M_element_count
),
1119 _M_rehash_policy(__ht
._M_rehash_policy
)
1121 // Update, if necessary, bucket pointing to before begin that hasn't
1124 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1128 template<typename _Key
, typename _Value
,
1129 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1130 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1132 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1133 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1134 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1135 : __hashtable_base(__ht
),
1137 __rehash_base(__ht
),
1138 __hashtable_alloc(__node_alloc_type(__a
)),
1140 _M_bucket_count(__ht
._M_bucket_count
),
1141 _M_element_count(__ht
._M_element_count
),
1142 _M_rehash_policy(__ht
._M_rehash_policy
)
1145 [this](const __node_type
* __n
)
1146 { return this->_M_allocate_node(__n
->_M_v()); });
1149 template<typename _Key
, typename _Value
,
1150 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1151 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1153 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1154 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1155 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
1156 : __hashtable_base(__ht
),
1158 __rehash_base(__ht
),
1159 __hashtable_alloc(__node_alloc_type(__a
)),
1161 _M_bucket_count(__ht
._M_bucket_count
),
1162 _M_element_count(__ht
._M_element_count
),
1163 _M_rehash_policy(__ht
._M_rehash_policy
)
1165 if (__ht
._M_node_allocator() == this->_M_node_allocator())
1167 _M_buckets
= __ht
._M_buckets
;
1168 _M_before_begin
._M_nxt
= __ht
._M_before_begin
._M_nxt
;
1169 // Update, if necessary, bucket pointing to before begin that hasn't
1172 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1178 [this](__node_type
* __n
)
1180 return this->_M_allocate_node(
1181 std::move_if_noexcept(__n
->_M_v()));
1187 template<typename _Key
, typename _Value
,
1188 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1189 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1191 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1192 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1193 ~_Hashtable() noexcept
1197 _M_deallocate_buckets();
1200 template<typename _Key
, typename _Value
,
1201 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1202 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1205 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1206 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1207 swap(_Hashtable
& __x
)
1208 noexcept(__node_alloc_traits::_S_nothrow_swap())
1210 // The only base class with member variables is hash_code_base.
1211 // We define _Hash_code_base::_M_swap because different
1212 // specializations have different members.
1215 std::__alloc_on_swap(this->_M_node_allocator(), __x
._M_node_allocator());
1216 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1217 std::swap(_M_buckets
, __x
._M_buckets
);
1218 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1219 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
1220 std::swap(_M_element_count
, __x
._M_element_count
);
1222 // Fix buckets containing the _M_before_begin pointers that can't be
1225 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
1227 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
1228 = &__x
._M_before_begin
;
1231 template<typename _Key
, typename _Value
,
1232 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1233 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1236 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1237 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1238 __rehash_policy(const _RehashPolicy
& __pol
)
1240 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
1241 __n_bkt
= __pol
._M_next_bkt(__n_bkt
);
1242 if (__n_bkt
!= _M_bucket_count
)
1243 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
1244 _M_rehash_policy
= __pol
;
1247 template<typename _Key
, typename _Value
,
1248 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1249 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1251 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1252 _H1
, _H2
, _Hash
, _RehashPolicy
,
1254 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1255 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1256 find(const key_type
& __k
)
1258 if (__builtin_expect(_M_bucket_count
== 0, false))
1261 __hash_code __code
= this->_M_hash_code(__k
);
1262 std::size_t __n
= _M_bucket_index(__k
, __code
);
1263 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1264 return __p
? iterator(__p
) : end();
1267 template<typename _Key
, typename _Value
,
1268 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1269 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1271 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1272 _H1
, _H2
, _Hash
, _RehashPolicy
,
1273 _Traits
>::const_iterator
1274 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1275 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1276 find(const key_type
& __k
) const
1278 if (__builtin_expect(_M_bucket_count
== 0, false))
1281 __hash_code __code
= this->_M_hash_code(__k
);
1282 std::size_t __n
= _M_bucket_index(__k
, __code
);
1283 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1284 return __p
? const_iterator(__p
) : end();
1287 template<typename _Key
, typename _Value
,
1288 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1289 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1291 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1292 _H1
, _H2
, _Hash
, _RehashPolicy
,
1294 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1295 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1296 count(const key_type
& __k
) const
1298 if (__builtin_expect(_M_bucket_count
== 0, false))
1301 __hash_code __code
= this->_M_hash_code(__k
);
1302 std::size_t __n
= _M_bucket_index(__k
, __code
);
1303 __node_type
* __p
= _M_bucket_begin(__n
);
1307 std::size_t __result
= 0;
1308 for (;; __p
= __p
->_M_next())
1310 if (this->_M_equals(__k
, __code
, __p
))
1313 // All equivalent values are next to each other, if we
1314 // found a non-equivalent value after an equivalent one it
1315 // means that we won't find any more equivalent values.
1317 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1323 template<typename _Key
, typename _Value
,
1324 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1325 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1327 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1328 _ExtractKey
, _Equal
, _H1
,
1329 _H2
, _Hash
, _RehashPolicy
,
1331 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1332 _ExtractKey
, _Equal
, _H1
,
1333 _H2
, _Hash
, _RehashPolicy
,
1335 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1336 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1337 equal_range(const key_type
& __k
)
1339 if (__builtin_expect(_M_bucket_count
== 0, false))
1340 return std::make_pair(end(), end());
1342 __hash_code __code
= this->_M_hash_code(__k
);
1343 std::size_t __n
= _M_bucket_index(__k
, __code
);
1344 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1348 __node_type
* __p1
= __p
->_M_next();
1349 while (__p1
&& _M_bucket_index(__p1
) == __n
1350 && this->_M_equals(__k
, __code
, __p1
))
1351 __p1
= __p1
->_M_next();
1353 return std::make_pair(iterator(__p
), iterator(__p1
));
1356 return std::make_pair(end(), end());
1359 template<typename _Key
, typename _Value
,
1360 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1361 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1363 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1364 _ExtractKey
, _Equal
, _H1
,
1365 _H2
, _Hash
, _RehashPolicy
,
1366 _Traits
>::const_iterator
,
1367 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1368 _ExtractKey
, _Equal
, _H1
,
1369 _H2
, _Hash
, _RehashPolicy
,
1370 _Traits
>::const_iterator
>
1371 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1372 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1373 equal_range(const key_type
& __k
) const
1375 if (__builtin_expect(_M_bucket_count
== 0, false))
1376 return std::make_pair(end(), end());
1378 __hash_code __code
= this->_M_hash_code(__k
);
1379 std::size_t __n
= _M_bucket_index(__k
, __code
);
1380 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1384 __node_type
* __p1
= __p
->_M_next();
1385 while (__p1
&& _M_bucket_index(__p1
) == __n
1386 && this->_M_equals(__k
, __code
, __p1
))
1387 __p1
= __p1
->_M_next();
1389 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1392 return std::make_pair(end(), end());
1395 // Find the node whose key compares equal to k in the bucket n.
1396 // Return nullptr if no node is found.
1397 template<typename _Key
, typename _Value
,
1398 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1399 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1401 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1402 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1403 _Traits
>::__node_base
*
1404 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1405 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1406 _M_find_before_node(size_type __n
, const key_type
& __k
,
1407 __hash_code __code
) const
1409 __node_base
* __prev_p
= _M_buckets
[__n
];
1413 for (__node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);;
1414 __p
= __p
->_M_next())
1416 if (this->_M_equals(__k
, __code
, __p
))
1419 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1426 template<typename _Key
, typename _Value
,
1427 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1428 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1431 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1432 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1433 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1435 if (_M_buckets
[__bkt
])
1437 // Bucket is not empty, we just need to insert the new node
1438 // after the bucket before begin.
1439 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1440 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1444 // The bucket is empty, the new node is inserted at the
1445 // beginning of the singly-linked list and the bucket will
1446 // contain _M_before_begin pointer.
1447 __node
->_M_nxt
= _M_before_begin
._M_nxt
;
1448 _M_before_begin
._M_nxt
= __node
;
1450 // We must update former begin bucket that is pointing to
1452 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1453 _M_buckets
[__bkt
] = &_M_before_begin
;
1457 template<typename _Key
, typename _Value
,
1458 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1459 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1462 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1463 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1464 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1465 size_type __next_bkt
)
1467 if (!__next
|| __next_bkt
!= __bkt
)
1469 // Bucket is now empty
1470 // First update next bucket if any
1472 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1474 // Second update before begin node if necessary
1475 if (&_M_before_begin
== _M_buckets
[__bkt
])
1476 _M_before_begin
._M_nxt
= __next
;
1477 _M_buckets
[__bkt
] = nullptr;
1481 template<typename _Key
, typename _Value
,
1482 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1483 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1485 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1486 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1487 _Traits
>::__node_base
*
1488 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1489 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1490 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1492 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1493 while (__prev_n
->_M_nxt
!= __n
)
1494 __prev_n
= __prev_n
->_M_nxt
;
1498 template<typename _Key
, typename _Value
,
1499 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1500 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1502 template<typename
... _Args
>
1503 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1504 _ExtractKey
, _Equal
, _H1
,
1505 _H2
, _Hash
, _RehashPolicy
,
1506 _Traits
>::iterator
, bool>
1507 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1508 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1509 _M_emplace(std::true_type
, _Args
&&... __args
)
1511 // First build the node to get access to the hash code
1512 __node_type
* __node
= this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1513 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1517 __code
= this->_M_hash_code(__k
);
1521 this->_M_deallocate_node(__node
);
1522 __throw_exception_again
;
1525 size_type __bkt
= _M_bucket_index(__k
, __code
);
1526 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1528 // There is already an equivalent node, no insertion
1529 this->_M_deallocate_node(__node
);
1530 return std::make_pair(iterator(__p
), false);
1534 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1538 template<typename _Key
, typename _Value
,
1539 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1540 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1542 template<typename
... _Args
>
1543 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1544 _H1
, _H2
, _Hash
, _RehashPolicy
,
1546 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1547 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1548 _M_emplace(const_iterator __hint
, std::false_type
, _Args
&&... __args
)
1550 // First build the node to get its hash code.
1551 __node_type
* __node
=
1552 this->_M_allocate_node(std::forward
<_Args
>(__args
)...);
1557 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v()));
1561 this->_M_deallocate_node(__node
);
1562 __throw_exception_again
;
1565 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1568 template<typename _Key
, typename _Value
,
1569 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1570 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1572 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1573 _H1
, _H2
, _Hash
, _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
)
1580 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1581 std::pair
<bool, std::size_t> __do_rehash
1582 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1586 if (__do_rehash
.first
)
1588 _M_rehash(__do_rehash
.second
, __saved_state
);
1589 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v()), __code
);
1592 this->_M_store_code(__node
, __code
);
1594 // Always insert at the beginning of the bucket.
1595 _M_insert_bucket_begin(__bkt
, __node
);
1597 return iterator(__node
);
1601 this->_M_deallocate_node(__node
);
1602 __throw_exception_again
;
1606 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1607 // already present). Take ownership of the node, deallocate it on exception.
1608 template<typename _Key
, typename _Value
,
1609 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1610 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1612 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1613 _H1
, _H2
, _Hash
, _RehashPolicy
,
1615 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1616 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1617 _M_insert_multi_node(__node_type
* __hint
, __hash_code __code
,
1618 __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
>
1678 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1679 _ExtractKey
, _Equal
, _H1
,
1680 _H2
, _Hash
, _RehashPolicy
,
1681 _Traits
>::iterator
, bool>
1682 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1683 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1684 _M_insert(_Arg
&& __v
, const _NodeGenerator
& __node_gen
, std::true_type
)
1686 const key_type
& __k
= this->_M_extract()(__v
);
1687 __hash_code __code
= this->_M_hash_code(__k
);
1688 size_type __bkt
= _M_bucket_index(__k
, __code
);
1690 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1692 return std::make_pair(iterator(__n
), false);
1694 __n
= __node_gen(std::forward
<_Arg
>(__v
));
1695 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __n
), true);
1698 // Insert v unconditionally.
1699 template<typename _Key
, typename _Value
,
1700 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1701 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1703 template<typename _Arg
, typename _NodeGenerator
>
1704 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1705 _H1
, _H2
, _Hash
, _RehashPolicy
,
1707 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1708 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1709 _M_insert(const_iterator __hint
, _Arg
&& __v
,
1710 const _NodeGenerator
& __node_gen
,
1713 // First compute the hash code so that we don't do anything if it
1715 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1717 // Second allocate new node so that we don't rehash if it throws.
1718 __node_type
* __node
= __node_gen(std::forward
<_Arg
>(__v
));
1720 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1723 template<typename _Key
, typename _Value
,
1724 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1725 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1727 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1728 _H1
, _H2
, _Hash
, _RehashPolicy
,
1730 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1731 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1732 erase(const_iterator __it
)
1734 __node_type
* __n
= __it
._M_cur
;
1735 std::size_t __bkt
= _M_bucket_index(__n
);
1737 // Look for previous node to unlink it from the erased one, this
1738 // is why we need buckets to contain the before begin to make
1739 // this search fast.
1740 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1741 return _M_erase(__bkt
, __prev_n
, __n
);
1744 template<typename _Key
, typename _Value
,
1745 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1746 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1748 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1749 _H1
, _H2
, _Hash
, _RehashPolicy
,
1751 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1752 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1753 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1755 if (__prev_n
== _M_buckets
[__bkt
])
1756 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1757 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1758 else if (__n
->_M_nxt
)
1760 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1761 if (__next_bkt
!= __bkt
)
1762 _M_buckets
[__next_bkt
] = __prev_n
;
1765 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1766 iterator
__result(__n
->_M_next());
1767 this->_M_deallocate_node(__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::true_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 // We found a matching node, erase it.
1793 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1794 _M_erase(__bkt
, __prev_n
, __n
);
1798 template<typename _Key
, typename _Value
,
1799 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1800 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1802 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1803 _H1
, _H2
, _Hash
, _RehashPolicy
,
1805 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1806 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1807 _M_erase(std::false_type
, const key_type
& __k
)
1809 __hash_code __code
= this->_M_hash_code(__k
);
1810 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1812 // Look for the node before the first matching node.
1813 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1817 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1818 // 526. Is it undefined if a function in the standard changes
1820 // We use one loop to find all matching nodes and another to deallocate
1821 // them so that the key stays valid during the first loop. It might be
1822 // invalidated indirectly when destroying nodes.
1823 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1824 __node_type
* __n_last
= __n
;
1825 std::size_t __n_last_bkt
= __bkt
;
1828 __n_last
= __n_last
->_M_next();
1831 __n_last_bkt
= _M_bucket_index(__n_last
);
1833 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1835 // Deallocate nodes.
1836 size_type __result
= 0;
1839 __node_type
* __p
= __n
->_M_next();
1840 this->_M_deallocate_node(__n
);
1845 while (__n
!= __n_last
);
1847 if (__prev_n
== _M_buckets
[__bkt
])
1848 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1849 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1850 _M_buckets
[__n_last_bkt
] = __prev_n
;
1851 __prev_n
->_M_nxt
= __n_last
;
1855 template<typename _Key
, typename _Value
,
1856 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1857 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1859 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1860 _H1
, _H2
, _Hash
, _RehashPolicy
,
1862 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1863 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1864 erase(const_iterator __first
, const_iterator __last
)
1866 __node_type
* __n
= __first
._M_cur
;
1867 __node_type
* __last_n
= __last
._M_cur
;
1868 if (__n
== __last_n
)
1869 return iterator(__n
);
1871 std::size_t __bkt
= _M_bucket_index(__n
);
1873 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1874 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1875 std::size_t __n_bkt
= __bkt
;
1880 __node_type
* __tmp
= __n
;
1881 __n
= __n
->_M_next();
1882 this->_M_deallocate_node(__tmp
);
1886 __n_bkt
= _M_bucket_index(__n
);
1888 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1889 if (__is_bucket_begin
)
1890 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1891 if (__n
== __last_n
)
1893 __is_bucket_begin
= true;
1897 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
1898 _M_buckets
[__n_bkt
] = __prev_n
;
1899 __prev_n
->_M_nxt
= __n
;
1900 return iterator(__n
);
1903 template<typename _Key
, typename _Value
,
1904 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1905 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1908 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1909 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1912 this->_M_deallocate_nodes(_M_begin());
1913 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
1914 _M_element_count
= 0;
1915 _M_before_begin
._M_nxt
= nullptr;
1918 template<typename _Key
, typename _Value
,
1919 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1920 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1923 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1924 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1925 rehash(size_type __n
)
1927 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1928 std::size_t __buckets
1929 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
1931 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
1933 if (__buckets
!= _M_bucket_count
)
1934 _M_rehash(__buckets
, __saved_state
);
1936 // No rehash, restore previous state to keep a consistent state.
1937 _M_rehash_policy
._M_reset(__saved_state
);
1940 template<typename _Key
, typename _Value
,
1941 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1942 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1945 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1946 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1947 _M_rehash(size_type __n
, const __rehash_state
& __state
)
1951 _M_rehash_aux(__n
, __unique_keys());
1955 // A failure here means that buckets allocation failed. We only
1956 // have to restore hash policy previous state.
1957 _M_rehash_policy
._M_reset(__state
);
1958 __throw_exception_again
;
1962 // Rehash when there is no equivalent elements.
1963 template<typename _Key
, typename _Value
,
1964 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1965 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1968 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1969 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1970 _M_rehash_aux(size_type __n
, std::true_type
)
1972 __bucket_type
* __new_buckets
= this->_M_allocate_buckets(__n
);
1973 __node_type
* __p
= _M_begin();
1974 _M_before_begin
._M_nxt
= nullptr;
1975 std::size_t __bbegin_bkt
= 0;
1978 __node_type
* __next
= __p
->_M_next();
1979 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1980 if (!__new_buckets
[__bkt
])
1982 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
1983 _M_before_begin
._M_nxt
= __p
;
1984 __new_buckets
[__bkt
] = &_M_before_begin
;
1986 __new_buckets
[__bbegin_bkt
] = __p
;
1987 __bbegin_bkt
= __bkt
;
1991 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1992 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1997 if (__builtin_expect(_M_bucket_count
!= 0, true))
1998 _M_deallocate_buckets();
1999 _M_bucket_count
= __n
;
2000 _M_buckets
= __new_buckets
;
2003 // Rehash when there can be equivalent elements, preserve their relative
2005 template<typename _Key
, typename _Value
,
2006 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2007 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2010 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2011 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2012 _M_rehash_aux(size_type __n
, std::false_type
)
2014 __bucket_type
* __new_buckets
= this->_M_allocate_buckets(__n
);
2016 __node_type
* __p
= _M_begin();
2017 _M_before_begin
._M_nxt
= nullptr;
2018 std::size_t __bbegin_bkt
= 0;
2019 std::size_t __prev_bkt
= 0;
2020 __node_type
* __prev_p
= nullptr;
2021 bool __check_bucket
= false;
2025 __node_type
* __next
= __p
->_M_next();
2026 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2028 if (__prev_p
&& __prev_bkt
== __bkt
)
2030 // Previous insert was already in this bucket, we insert after
2031 // the previously inserted one to preserve equivalent elements
2033 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2034 __prev_p
->_M_nxt
= __p
;
2036 // Inserting after a node in a bucket require to check that we
2037 // haven't change the bucket last node, in this case next
2038 // bucket containing its before begin node must be updated. We
2039 // schedule a check as soon as we move out of the sequence of
2040 // equivalent nodes to limit the number of checks.
2041 __check_bucket
= true;
2047 // Check if we shall update the next bucket because of
2048 // insertions into __prev_bkt bucket.
2049 if (__prev_p
->_M_nxt
)
2051 std::size_t __next_bkt
2052 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
2054 if (__next_bkt
!= __prev_bkt
)
2055 __new_buckets
[__next_bkt
] = __prev_p
;
2057 __check_bucket
= false;
2060 if (!__new_buckets
[__bkt
])
2062 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
2063 _M_before_begin
._M_nxt
= __p
;
2064 __new_buckets
[__bkt
] = &_M_before_begin
;
2066 __new_buckets
[__bbegin_bkt
] = __p
;
2067 __bbegin_bkt
= __bkt
;
2071 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2072 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2080 if (__check_bucket
&& __prev_p
->_M_nxt
)
2082 std::size_t __next_bkt
2083 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
2084 if (__next_bkt
!= __prev_bkt
)
2085 __new_buckets
[__next_bkt
] = __prev_p
;
2088 if (__builtin_expect(_M_bucket_count
!= 0, true))
2089 _M_deallocate_buckets();
2090 _M_bucket_count
= __n
;
2091 _M_buckets
= __new_buckets
;
2094 _GLIBCXX_END_NAMESPACE_VERSION
2097 #endif // _HASHTABLE_H