1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2013 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_bbegin
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
>
186 typedef std::allocator_traits
<_Alloc
> _Alloc_traits
;
187 typedef typename
_Alloc_traits::template rebind_alloc
<_Value
>
189 typedef __gnu_cxx::__alloc_traits
<_Value_alloc_type
> _Value_alloc_traits
;
192 typedef _Key key_type
;
193 typedef _Value value_type
;
194 typedef _Alloc allocator_type
;
195 typedef _Equal key_equal
;
197 // mapped_type, if present, comes from _Map_base.
198 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
199 typedef typename
_Value_alloc_traits::pointer pointer
;
200 typedef typename
_Value_alloc_traits::const_pointer const_pointer
;
201 typedef value_type
& reference
;
202 typedef const value_type
& const_reference
;
205 using __rehash_type
= _RehashPolicy
;
206 using __rehash_state
= typename
__rehash_type::_State
;
208 using __traits_type
= _Traits
;
209 using __hash_cached
= typename
__traits_type::__hash_cached
;
210 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
211 using __unique_keys
= typename
__traits_type::__unique_keys
;
213 using __key_extract
= typename
std::conditional
<
214 __constant_iterators::value
,
216 __detail::_Select1st
>::type
;
218 using __hashtable_base
= __detail::
219 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
220 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
222 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
223 using __hash_code
= typename
__hashtable_base::__hash_code
;
224 using __node_type
= typename
__hashtable_base::__node_type
;
225 using __node_base
= typename
__hashtable_base::__node_base
;
226 using __bucket_type
= typename
__hashtable_base::__bucket_type
;
227 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
228 using __iconv_type
= typename
__hashtable_base::__iconv_type
;
230 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
231 _Equal
, _H1
, _H2
, _Hash
,
232 _RehashPolicy
, _Traits
>;
234 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
237 _RehashPolicy
, _Traits
>;
239 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
240 _Equal
, _H1
, _H2
, _Hash
,
241 _RehashPolicy
, _Traits
>;
243 // Metaprogramming for picking apart hash caching.
244 template<typename _Cond
>
245 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
247 template<typename _Cond
>
248 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
250 // Compile-time diagnostics.
252 // Getting a bucket index from a node shall not throw because it is used
253 // in methods (erase, swap...) that shall not throw.
254 static_assert(noexcept(declval
<const _Hashtable
&>()
255 ._M_bucket_index((const __node_type
*)nullptr,
257 "Cache the hash code or qualify your functors involved"
258 " in hash code and bucket index computation with noexcept");
260 // Following two static assertions are necessary to guarantee
261 // that local_iterator will be default constructible.
263 // When hash codes are cached local iterator inherits from H2 functor
264 // which must then be default constructible.
265 static_assert(__if_hash_cached
<is_default_constructible
<_H2
>>::value
,
266 "Functor used to map hash code to bucket index"
267 " must be default constructible");
269 // When hash codes are not cached local iterator inherits from
270 // __hash_code_base above to compute node bucket index so it has to be
271 // default constructible.
272 static_assert(__if_hash_not_cached
<
273 is_default_constructible
<
274 // We use _Hashtable_ebo_helper to access the protected
275 // default constructor.
276 __detail::_Hashtable_ebo_helper
<0, __hash_code_base
>>>::value
,
277 "Cache the hash code or make functors involved in hash code"
278 " and bucket index computation default constructible");
280 // When hash codes are not cached local iterator inherits from
281 // __hash_code_base above to compute node bucket index so it has to be
283 static_assert(__if_hash_not_cached
<
284 is_copy_assignable
<__hash_code_base
>>::value
,
285 "Cache the hash code or make functors involved in hash code"
286 " and bucket index computation copy assignable");
289 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
290 typename _ExtractKeya
, typename _Equala
,
291 typename _H1a
, typename _H2a
, typename _Hasha
,
292 typename _RehashPolicya
, typename _Traitsa
,
294 friend struct __detail::_Map_base
;
296 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
297 typename _ExtractKeya
, typename _Equala
,
298 typename _H1a
, typename _H2a
, typename _Hasha
,
299 typename _RehashPolicya
, typename _Traitsa
>
300 friend struct __detail::_Insert_base
;
302 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
303 typename _ExtractKeya
, typename _Equala
,
304 typename _H1a
, typename _H2a
, typename _Hasha
,
305 typename _RehashPolicya
, typename _Traitsa
,
306 bool _Constant_iteratorsa
, bool _Unique_keysa
>
307 friend struct __detail::_Insert
;
309 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
310 typename _ExtractKeya
, typename _Equala
,
311 typename _H1a
, typename _H2a
, typename _Hasha
,
312 typename _RehashPolicya
, typename _Traitsa
,
313 bool _IsCopyAssignable
>
314 friend struct __detail::_ReuseOrAllocNode
;
316 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
317 typename _ExtractKeya
, typename _Equala
,
318 typename _H1a
, typename _H2a
, typename _Hasha
,
319 typename _RehashPolicya
, typename _Traitsa
,
320 bool _IsMoveAssignable
>
321 friend struct __detail::_MoveReuseOrAllocNode
;
323 using size_type
= typename
__hashtable_base::size_type
;
324 using difference_type
= typename
__hashtable_base::difference_type
;
326 using iterator
= typename
__hashtable_base::iterator
;
327 using const_iterator
= typename
__hashtable_base::const_iterator
;
329 using local_iterator
= typename
__hashtable_base::local_iterator
;
330 using const_local_iterator
= typename
__hashtable_base::
331 const_local_iterator
;
334 typedef typename
_Alloc_traits::template rebind_alloc
<__node_type
>
336 // Use __gnu_cxx to benefit from _S_always_equal and al.
337 typedef __gnu_cxx::__alloc_traits
<_Node_alloc_type
> _Node_alloc_traits
;
340 typename
_Alloc_traits::template rebind_alloc
<__bucket_type
>
342 typedef std::allocator_traits
<_Bucket_alloc_type
> _Bucket_alloc_traits
;
344 using __before_begin
= __detail::_Before_begin
<_Node_alloc_type
>;
346 __bucket_type
* _M_buckets
;
347 size_type _M_bucket_count
;
348 __before_begin _M_bbegin
;
349 size_type _M_element_count
;
350 _RehashPolicy _M_rehash_policy
;
354 { return _M_bbegin
; }
356 const _Node_alloc_type
&
357 _M_node_allocator() const
358 { return _M_bbegin
; }
362 { return _M_bbegin
._M_node
; }
365 _M_before_begin() const
366 { return _M_bbegin
._M_node
; }
368 template<typename
... _Args
>
370 _M_allocate_node(_Args
&&... __args
);
373 _M_deallocate_node(__node_type
* __n
);
375 // Deallocate the linked list of nodes pointed to by __n
377 _M_deallocate_nodes(__node_type
* __n
);
380 _M_allocate_buckets(size_type __n
);
383 _M_deallocate_buckets(__bucket_type
*, size_type __n
);
386 _M_deallocate_buckets()
387 { _M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
389 // Gets bucket begin, deals with the fact that non-empty buckets contain
390 // their before begin node.
392 _M_bucket_begin(size_type __bkt
) const;
396 { return static_cast<__node_type
*>(_M_before_begin()._M_nxt
); }
398 template<typename _UnaryOp
>
400 _M_assign(const _Hashtable
&, const _UnaryOp
&);
403 _M_move_assign(_Hashtable
&&, std::true_type
);
406 _M_move_assign(_Hashtable
&&, std::false_type
);
412 // Constructor, destructor, assignment, swap
413 _Hashtable(size_type __bucket_hint
,
414 const _H1
&, const _H2
&, const _Hash
&,
415 const _Equal
&, const _ExtractKey
&,
416 const allocator_type
&);
418 template<typename _InputIterator
>
419 _Hashtable(_InputIterator __first
, _InputIterator __last
,
420 size_type __bucket_hint
,
421 const _H1
&, const _H2
&, const _Hash
&,
422 const _Equal
&, const _ExtractKey
&,
423 const allocator_type
&);
425 _Hashtable(const _Hashtable
&);
427 _Hashtable(_Hashtable
&&) noexcept
;
429 _Hashtable(const _Hashtable
&, const allocator_type
&);
431 _Hashtable(_Hashtable
&&, const allocator_type
&);
433 // Use delegating constructors.
435 _Hashtable(const allocator_type
& __a
)
436 : _Hashtable(10, _H1(), __detail::_Mod_range_hashing(),
437 __detail::_Default_ranged_hash(), key_equal(),
438 __key_extract(), __a
)
442 _Hashtable(size_type __n
= 10,
443 const _H1
& __hf
= _H1(),
444 const key_equal
& __eql
= key_equal(),
445 const allocator_type
& __a
= allocator_type())
446 : _Hashtable(__n
, __hf
, __detail::_Mod_range_hashing(),
447 __detail::_Default_ranged_hash(), __eql
,
448 __key_extract(), __a
)
451 template<typename _InputIterator
>
452 _Hashtable(_InputIterator __f
, _InputIterator __l
,
454 const _H1
& __hf
= _H1(),
455 const key_equal
& __eql
= key_equal(),
456 const allocator_type
& __a
= allocator_type())
457 : _Hashtable(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
458 __detail::_Default_ranged_hash(), __eql
,
459 __key_extract(), __a
)
462 _Hashtable(initializer_list
<value_type
> __l
,
464 const _H1
& __hf
= _H1(),
465 const key_equal
& __eql
= key_equal(),
466 const allocator_type
& __a
= allocator_type())
467 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
,
468 __detail::_Mod_range_hashing(),
469 __detail::_Default_ranged_hash(), __eql
,
470 __key_extract(), __a
)
474 operator=(const _Hashtable
& __ht
);
477 operator=(_Hashtable
&& __ht
)
478 noexcept(_Node_alloc_traits::_S_nothrow_move())
480 constexpr bool __move_storage
=
481 _Node_alloc_traits::_S_propagate_on_move_assign()
482 || _Node_alloc_traits::_S_always_equal();
483 _M_move_assign(std::move(__ht
),
484 integral_constant
<bool, __move_storage
>());
489 operator=(initializer_list
<value_type
> __l
)
492 this->insert(__l
.begin(), __l
.end());
496 ~_Hashtable() noexcept
;
500 noexcept(_Node_alloc_traits::_S_nothrow_swap());
502 // Basic container operations
505 { return iterator(_M_begin()); }
508 begin() const noexcept
509 { return const_iterator(_M_begin()); }
513 { return iterator(nullptr); }
517 { return const_iterator(nullptr); }
520 cbegin() const noexcept
521 { return const_iterator(_M_begin()); }
524 cend() const noexcept
525 { return const_iterator(nullptr); }
528 size() const noexcept
529 { return _M_element_count
; }
532 empty() const noexcept
533 { return size() == 0; }
536 get_allocator() const noexcept
537 { return allocator_type(_M_node_allocator()); }
540 max_size() const noexcept
541 { return _Node_alloc_traits::max_size(_M_node_allocator()); }
546 { return this->_M_eq(); }
548 // hash_function, if present, comes from _Hash_code_base.
552 bucket_count() const noexcept
553 { return _M_bucket_count
; }
556 max_bucket_count() const noexcept
557 { return max_size(); }
560 bucket_size(size_type __n
) const
561 { return std::distance(begin(__n
), end(__n
)); }
564 bucket(const key_type
& __k
) const
565 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
570 return local_iterator(*this, _M_bucket_begin(__n
),
571 __n
, _M_bucket_count
);
576 { return local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
579 begin(size_type __n
) const
581 return const_local_iterator(*this, _M_bucket_begin(__n
),
582 __n
, _M_bucket_count
);
586 end(size_type __n
) const
587 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
591 cbegin(size_type __n
) const
593 return const_local_iterator(*this, _M_bucket_begin(__n
),
594 __n
, _M_bucket_count
);
598 cend(size_type __n
) const
599 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
602 load_factor() const noexcept
604 return static_cast<float>(size()) / static_cast<float>(bucket_count());
607 // max_load_factor, if present, comes from _Rehash_base.
609 // Generalization of max_load_factor. Extension, not found in
610 // TR1. Only useful if _RehashPolicy is something other than
613 __rehash_policy() const
614 { return _M_rehash_policy
; }
617 __rehash_policy(const _RehashPolicy
&);
621 find(const key_type
& __k
);
624 find(const key_type
& __k
) const;
627 count(const key_type
& __k
) const;
629 std::pair
<iterator
, iterator
>
630 equal_range(const key_type
& __k
);
632 std::pair
<const_iterator
, const_iterator
>
633 equal_range(const key_type
& __k
) const;
636 // Bucket index computation helpers.
638 _M_bucket_index(__node_type
* __n
) const noexcept
639 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
642 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
643 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
645 // Find and insert helper functions and types
646 // Find the node before the one matching the criteria.
648 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
651 _M_find_node(size_type __bkt
, const key_type
& __key
,
652 __hash_code __c
) const
654 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
656 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
660 // Insert a node at the beginning of a bucket.
662 _M_insert_bucket_begin(size_type
, __node_type
*);
664 // Remove the bucket first node
666 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
667 size_type __next_bkt
);
669 // Get the node before __n in the bucket __bkt
671 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
673 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
674 // no element with its key already present). Take ownership of the node,
675 // deallocate it on exception.
677 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
680 // Insert node with hash code __code. Take ownership of the node,
681 // deallocate it on exception.
683 _M_insert_multi_node(__hash_code __code
, __node_type
* __n
);
685 template<typename
... _Args
>
686 std::pair
<iterator
, bool>
687 _M_emplace(std::true_type
, _Args
&&... __args
);
689 template<typename
... _Args
>
691 _M_emplace(std::false_type
, _Args
&&... __args
);
693 template<typename _Arg
>
694 std::pair
<iterator
, bool>
695 _M_insert(_Arg
&&, std::true_type
);
697 template<typename _Arg
>
699 _M_insert(_Arg
&&, std::false_type
);
702 _M_erase(std::true_type
, const key_type
&);
705 _M_erase(std::false_type
, const key_type
&);
708 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
712 template<typename
... _Args
>
714 emplace(_Args
&&... __args
)
715 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
717 template<typename
... _Args
>
719 emplace_hint(const_iterator
, _Args
&&... __args
)
720 { return __iconv_type()(emplace(std::forward
<_Args
>(__args
)...)); }
722 // Insert member functions via inheritance.
726 erase(const_iterator
);
731 { return erase(const_iterator(__it
)); }
734 erase(const key_type
& __k
)
736 if (__builtin_expect(_M_bucket_count
== 0, false))
738 return _M_erase(__unique_keys(), __k
);
742 erase(const_iterator
, const_iterator
);
747 // Set number of buckets to be appropriate for container of n element.
748 void rehash(size_type __n
);
751 // reserve, if present, comes from _Rehash_base.
754 // Helper rehash method used when keys are unique.
755 void _M_rehash_aux(size_type __n
, std::true_type
);
757 // Helper rehash method used when keys can be non-unique.
758 void _M_rehash_aux(size_type __n
, std::false_type
);
760 // Unconditionally change size of bucket array to n, restore
761 // hash policy state to __state on exception.
762 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
766 // Definitions of class template _Hashtable's out-of-line member functions.
767 template<typename _Key
, typename _Value
,
768 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
769 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
771 template<typename
... _Args
>
772 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
773 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__node_type
*
774 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
775 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
776 _M_allocate_node(_Args
&&... __args
)
778 __node_type
* __n
= _Node_alloc_traits::allocate(_M_node_allocator(), 1);
781 _Value_alloc_type
__a(_M_node_allocator());
782 ::new ((void*)__n
) __node_type();
783 _Value_alloc_traits::construct(__a
, __n
->_M_valptr(),
784 std::forward
<_Args
>(__args
)...);
789 _Node_alloc_traits::deallocate(_M_node_allocator(), __n
, 1);
790 __throw_exception_again
;
794 template<typename _Key
, typename _Value
,
795 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
796 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
799 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
800 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
801 _M_deallocate_node(__node_type
* __n
)
803 _Value_alloc_type
__a(_M_node_allocator());
804 _Value_alloc_traits::destroy(__a
, __n
->_M_valptr());
806 _Node_alloc_traits::deallocate(_M_node_allocator(), __n
, 1);
809 template<typename _Key
, typename _Value
,
810 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
811 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
814 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
815 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
816 _M_deallocate_nodes(__node_type
* __n
)
820 __node_type
* __tmp
= __n
;
821 __n
= __n
->_M_next();
822 _M_deallocate_node(__tmp
);
826 template<typename _Key
, typename _Value
,
827 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
828 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
830 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
831 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__bucket_type
*
832 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
833 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
834 _M_allocate_buckets(size_type __n
)
836 _Bucket_alloc_type
__alloc(_M_node_allocator());
838 __bucket_type
* __p
= _Bucket_alloc_traits::allocate(__alloc
, __n
);
839 __builtin_memset(__p
, 0, __n
* sizeof(__bucket_type
));
843 template<typename _Key
, typename _Value
,
844 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
845 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
848 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
849 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
850 _M_deallocate_buckets(__bucket_type
* __bkts
, size_type __n
)
852 _Bucket_alloc_type
__alloc(_M_node_allocator());
853 _Bucket_alloc_traits::deallocate(__alloc
, __bkts
, __n
);
856 template<typename _Key
, typename _Value
,
857 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
858 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
860 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
861 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
862 _Traits
>::__node_type
*
863 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
864 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
865 _M_bucket_begin(size_type __bkt
) const
867 __node_base
* __n
= _M_buckets
[__bkt
];
868 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
871 template<typename _Key
, typename _Value
,
872 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
873 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
875 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
876 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
877 _Hashtable(size_type __bucket_hint
,
878 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
879 const _Equal
& __eq
, const _ExtractKey
& __exk
,
880 const allocator_type
& __a
)
881 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
888 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
889 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
892 template<typename _Key
, typename _Value
,
893 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
894 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
896 template<typename _InputIterator
>
897 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
898 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
899 _Hashtable(_InputIterator __f
, _InputIterator __l
,
900 size_type __bucket_hint
,
901 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
902 const _Equal
& __eq
, const _ExtractKey
& __exk
,
903 const allocator_type
& __a
)
904 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
911 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
913 _M_rehash_policy
._M_next_bkt(
914 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
917 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
920 for (; __f
!= __l
; ++__f
)
926 _M_deallocate_buckets();
927 __throw_exception_again
;
931 template<typename _Key
, typename _Value
,
932 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
933 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
935 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
936 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>&
937 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
938 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::operator=(
939 const _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
940 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>& __ht
)
945 if (_Node_alloc_traits::_S_propagate_on_copy_assign())
947 auto& __this_alloc
= this->_M_node_allocator();
948 auto& __that_alloc
= __ht
._M_node_allocator();
949 if (!_Node_alloc_traits::_S_always_equal()
950 && __this_alloc
!= __that_alloc
)
952 // Replacement allocator cannot free existing storage.
953 _M_deallocate_nodes(_M_begin());
954 if (__builtin_expect(_M_bucket_count
!= 0, true))
955 _M_deallocate_buckets();
957 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
958 __hashtable_base::operator=(__ht
);
959 _M_bucket_count
= __ht
._M_bucket_count
;
960 _M_element_count
= __ht
._M_element_count
;
961 _M_rehash_policy
= __ht
._M_rehash_policy
;
965 [this](const __node_type
* __n
)
966 { return _M_allocate_node(__n
->_M_v()); });
970 // _M_assign took care of deallocating all memory. Now we
971 // must make sure this instance remains in a usable state.
973 __throw_exception_again
;
977 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
980 // Reuse allocated buckets and nodes.
981 __bucket_type
* __former_buckets
= nullptr;
982 std::size_t __former_bucket_count
= _M_bucket_count
;
983 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
985 if (_M_bucket_count
!= __ht
._M_bucket_count
)
987 __former_buckets
= _M_buckets
;
988 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
989 _M_bucket_count
= __ht
._M_bucket_count
;
992 __builtin_memset(_M_buckets
, 0,
993 _M_bucket_count
* sizeof(__bucket_type
));
997 __hashtable_base::operator=(__ht
);
998 _M_element_count
= __ht
._M_element_count
;
999 _M_rehash_policy
= __ht
._M_rehash_policy
;
1000 __detail::_ReuseOrAllocNode
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1001 _Equal
, _H1
, _H2
, _Hash
,
1002 _RehashPolicy
, _Traits
>
1003 __roan(_M_begin(), *this);
1004 _M_before_begin()._M_nxt
= nullptr;
1005 _M_assign(__ht
, __roan
);
1006 if (__former_buckets
)
1007 _M_deallocate_buckets(__former_buckets
, __former_bucket_count
);
1011 if (__former_buckets
)
1013 // Restore previous buckets.
1014 _M_deallocate_buckets();
1015 _M_rehash_policy
._M_reset(__former_state
);
1016 _M_buckets
= __former_buckets
;
1017 _M_bucket_count
= __former_bucket_count
;
1019 __builtin_memset(_M_buckets
, 0,
1020 _M_bucket_count
* sizeof(__bucket_type
));
1021 __throw_exception_again
;
1026 template<typename _Key
, typename _Value
,
1027 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1028 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1030 template<typename _UnaryOp
>
1032 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1033 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1034 _M_assign(const _Hashtable
& __ht
, const _UnaryOp
& __node_getter
)
1036 __bucket_type
* __buckets
= nullptr;
1038 _M_buckets
= __buckets
= _M_allocate_buckets(_M_bucket_count
);
1042 if (!__ht
._M_before_begin()._M_nxt
)
1045 // First deal with the special first node pointed to by
1047 __node_type
* __ht_n
= __ht
._M_begin();
1048 __node_type
* __this_n
= __node_getter(__ht_n
);
1049 this->_M_copy_code(__this_n
, __ht_n
);
1050 _M_before_begin()._M_nxt
= __this_n
;
1051 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin();
1053 // Then deal with other nodes.
1054 __node_base
* __prev_n
= __this_n
;
1055 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
1057 __this_n
= __node_getter(__ht_n
);
1058 __prev_n
->_M_nxt
= __this_n
;
1059 this->_M_copy_code(__this_n
, __ht_n
);
1060 size_type __bkt
= _M_bucket_index(__this_n
);
1061 if (!_M_buckets
[__bkt
])
1062 _M_buckets
[__bkt
] = __prev_n
;
1063 __prev_n
= __this_n
;
1070 _M_deallocate_buckets();
1071 __throw_exception_again
;
1075 template<typename _Key
, typename _Value
,
1076 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1077 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1080 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1081 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1084 _M_rehash_policy
._M_reset();
1085 _M_bucket_count
= 0;
1086 _M_buckets
= nullptr;
1087 _M_before_begin()._M_nxt
= nullptr;
1088 _M_element_count
= 0;
1091 template<typename _Key
, typename _Value
,
1092 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1093 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1096 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1097 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1098 _M_move_assign(_Hashtable
&& __ht
, std::true_type
)
1100 _M_deallocate_nodes(_M_begin());
1101 if (__builtin_expect(_M_bucket_count
!= 0, true))
1102 _M_deallocate_buckets();
1104 __hashtable_base::operator=(std::move(__ht
));
1105 _M_rehash_policy
= __ht
._M_rehash_policy
;
1106 _M_buckets
= __ht
._M_buckets
;
1107 _M_bucket_count
= __ht
._M_bucket_count
;
1108 _M_before_begin()._M_nxt
= __ht
._M_before_begin()._M_nxt
;
1109 _M_element_count
= __ht
._M_element_count
;
1110 std::__alloc_on_move(_M_node_allocator(), __ht
._M_node_allocator());
1112 // Fix buckets containing the _M_before_begin pointers that can't be
1115 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1119 template<typename _Key
, typename _Value
,
1120 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1121 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1124 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1125 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1126 _M_move_assign(_Hashtable
&& __ht
, std::false_type
)
1128 if (__ht
._M_node_allocator() == _M_node_allocator())
1129 _M_move_assign(std::move(__ht
), std::true_type());
1132 // Can't move memory, move elements then.
1133 __bucket_type
* __former_buckets
= nullptr;
1134 size_type __former_bucket_count
= _M_bucket_count
;
1135 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1137 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1139 __former_buckets
= _M_buckets
;
1140 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
1141 _M_bucket_count
= __ht
._M_bucket_count
;
1144 __builtin_memset(_M_buckets
, 0,
1145 _M_bucket_count
* sizeof(__bucket_type
));
1149 __hashtable_base::operator=(std::move(__ht
));
1150 _M_element_count
= __ht
._M_element_count
;
1151 _M_rehash_policy
= __ht
._M_rehash_policy
;
1152 __detail::_MoveReuseOrAllocNode
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1153 _Equal
, _H1
, _H2
, _Hash
,
1154 _RehashPolicy
, _Traits
>
1155 __mroan(_M_begin(), *this);
1156 _M_before_begin()._M_nxt
= nullptr;
1157 _M_assign(__ht
, __mroan
);
1162 if (__former_buckets
)
1164 _M_deallocate_buckets();
1165 _M_rehash_policy
._M_reset(__former_state
);
1166 _M_buckets
= __former_buckets
;
1167 _M_bucket_count
= __former_bucket_count
;
1169 __builtin_memset(_M_buckets
, 0,
1170 _M_bucket_count
* sizeof(__bucket_type
));
1171 __throw_exception_again
;
1176 template<typename _Key
, typename _Value
,
1177 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1178 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1180 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1181 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1182 _Hashtable(const _Hashtable
& __ht
)
1183 : __hashtable_base(__ht
),
1185 __rehash_base(__ht
),
1187 _M_bucket_count(__ht
._M_bucket_count
),
1188 _M_bbegin(_Node_alloc_traits::_S_select_on_copy(
1189 __ht
._M_node_allocator())),
1190 _M_element_count(__ht
._M_element_count
),
1191 _M_rehash_policy(__ht
._M_rehash_policy
)
1194 [this](const __node_type
* __n
)
1195 { return _M_allocate_node(__n
->_M_v()); });
1198 template<typename _Key
, typename _Value
,
1199 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1200 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1202 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1203 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1204 _Hashtable(_Hashtable
&& __ht
) noexcept
1205 : __hashtable_base(__ht
),
1207 __rehash_base(__ht
),
1208 _M_buckets(__ht
._M_buckets
),
1209 _M_bucket_count(__ht
._M_bucket_count
),
1210 _M_bbegin(std::move(__ht
._M_bbegin
)),
1211 _M_element_count(__ht
._M_element_count
),
1212 _M_rehash_policy(__ht
._M_rehash_policy
)
1214 // Update, if necessary, bucket pointing to before begin that hasn't
1217 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1221 template<typename _Key
, typename _Value
,
1222 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1223 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1225 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1226 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1227 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1228 : __hashtable_base(__ht
),
1230 __rehash_base(__ht
),
1232 _M_bucket_count(__ht
._M_bucket_count
),
1233 _M_bbegin(_Node_alloc_type(__a
)),
1234 _M_element_count(__ht
._M_element_count
),
1235 _M_rehash_policy(__ht
._M_rehash_policy
)
1238 [this](const __node_type
* __n
)
1239 { return _M_allocate_node(__n
->_M_v()); });
1242 template<typename _Key
, typename _Value
,
1243 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1244 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1246 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1247 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1248 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
1249 : __hashtable_base(__ht
),
1251 __rehash_base(__ht
),
1253 _M_bucket_count(__ht
._M_bucket_count
),
1254 _M_bbegin(_Node_alloc_type(__a
)),
1255 _M_element_count(__ht
._M_element_count
),
1256 _M_rehash_policy(__ht
._M_rehash_policy
)
1258 if (__ht
._M_node_allocator() == _M_node_allocator())
1260 _M_buckets
= __ht
._M_buckets
;
1261 _M_before_begin()._M_nxt
= __ht
._M_before_begin()._M_nxt
;
1262 // Update, if necessary, bucket pointing to before begin that hasn't
1265 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1271 [this](__node_type
* __n
)
1273 return _M_allocate_node(
1274 std::move_if_noexcept(__n
->_M_v()));
1280 template<typename _Key
, typename _Value
,
1281 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1282 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1284 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1285 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1286 ~_Hashtable() noexcept
1290 _M_deallocate_buckets();
1293 template<typename _Key
, typename _Value
,
1294 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1295 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1298 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1299 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1300 swap(_Hashtable
& __x
)
1301 noexcept(_Node_alloc_traits::_S_nothrow_swap())
1303 // The only base class with member variables is hash_code_base.
1304 // We define _Hash_code_base::_M_swap because different
1305 // specializations have different members.
1308 std::__alloc_on_swap(_M_node_allocator(), __x
._M_node_allocator());
1309 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1310 std::swap(_M_buckets
, __x
._M_buckets
);
1311 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1312 std::swap(_M_before_begin()._M_nxt
, __x
._M_before_begin()._M_nxt
);
1313 std::swap(_M_element_count
, __x
._M_element_count
);
1315 // Fix buckets containing the _M_before_begin pointers that can't be
1318 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1320 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
1321 = &(__x
._M_before_begin());
1324 template<typename _Key
, typename _Value
,
1325 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1326 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1329 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1330 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1331 __rehash_policy(const _RehashPolicy
& __pol
)
1333 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
1334 __n_bkt
= __pol
._M_next_bkt(__n_bkt
);
1335 if (__n_bkt
!= _M_bucket_count
)
1336 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
1337 _M_rehash_policy
= __pol
;
1340 template<typename _Key
, typename _Value
,
1341 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1342 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1344 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1345 _H1
, _H2
, _Hash
, _RehashPolicy
,
1347 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1348 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1349 find(const key_type
& __k
)
1351 if (__builtin_expect(_M_bucket_count
== 0, false))
1354 __hash_code __code
= this->_M_hash_code(__k
);
1355 std::size_t __n
= _M_bucket_index(__k
, __code
);
1356 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1357 return __p
? iterator(__p
) : end();
1360 template<typename _Key
, typename _Value
,
1361 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1362 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1364 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1365 _H1
, _H2
, _Hash
, _RehashPolicy
,
1366 _Traits
>::const_iterator
1367 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1368 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1369 find(const key_type
& __k
) const
1371 if (__builtin_expect(_M_bucket_count
== 0, false))
1374 __hash_code __code
= this->_M_hash_code(__k
);
1375 std::size_t __n
= _M_bucket_index(__k
, __code
);
1376 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1377 return __p
? const_iterator(__p
) : end();
1380 template<typename _Key
, typename _Value
,
1381 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1382 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1384 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1385 _H1
, _H2
, _Hash
, _RehashPolicy
,
1387 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1388 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1389 count(const key_type
& __k
) const
1391 if (__builtin_expect(_M_bucket_count
== 0, false))
1394 __hash_code __code
= this->_M_hash_code(__k
);
1395 std::size_t __n
= _M_bucket_index(__k
, __code
);
1396 __node_type
* __p
= _M_bucket_begin(__n
);
1400 std::size_t __result
= 0;
1401 for (;; __p
= __p
->_M_next())
1403 if (this->_M_equals(__k
, __code
, __p
))
1406 // All equivalent values are next to each other, if we
1407 // found a non-equivalent value after an equivalent one it
1408 // means that we won't find any more equivalent values.
1410 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1416 template<typename _Key
, typename _Value
,
1417 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1418 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1420 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1421 _ExtractKey
, _Equal
, _H1
,
1422 _H2
, _Hash
, _RehashPolicy
,
1424 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1425 _ExtractKey
, _Equal
, _H1
,
1426 _H2
, _Hash
, _RehashPolicy
,
1428 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1429 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1430 equal_range(const key_type
& __k
)
1432 if (__builtin_expect(_M_bucket_count
== 0, false))
1433 return std::make_pair(end(), end());
1435 __hash_code __code
= this->_M_hash_code(__k
);
1436 std::size_t __n
= _M_bucket_index(__k
, __code
);
1437 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1441 __node_type
* __p1
= __p
->_M_next();
1442 while (__p1
&& _M_bucket_index(__p1
) == __n
1443 && this->_M_equals(__k
, __code
, __p1
))
1444 __p1
= __p1
->_M_next();
1446 return std::make_pair(iterator(__p
), iterator(__p1
));
1449 return std::make_pair(end(), end());
1452 template<typename _Key
, typename _Value
,
1453 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1454 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1456 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1457 _ExtractKey
, _Equal
, _H1
,
1458 _H2
, _Hash
, _RehashPolicy
,
1459 _Traits
>::const_iterator
,
1460 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1461 _ExtractKey
, _Equal
, _H1
,
1462 _H2
, _Hash
, _RehashPolicy
,
1463 _Traits
>::const_iterator
>
1464 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1465 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1466 equal_range(const key_type
& __k
) const
1468 if (__builtin_expect(_M_bucket_count
== 0, false))
1469 return std::make_pair(end(), end());
1471 __hash_code __code
= this->_M_hash_code(__k
);
1472 std::size_t __n
= _M_bucket_index(__k
, __code
);
1473 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1477 __node_type
* __p1
= __p
->_M_next();
1478 while (__p1
&& _M_bucket_index(__p1
) == __n
1479 && this->_M_equals(__k
, __code
, __p1
))
1480 __p1
= __p1
->_M_next();
1482 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1485 return std::make_pair(end(), end());
1488 // Find the node whose key compares equal to k in the bucket n.
1489 // Return nullptr if no node is found.
1490 template<typename _Key
, typename _Value
,
1491 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1492 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1494 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1495 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1496 _Traits
>::__node_base
*
1497 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1498 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1499 _M_find_before_node(size_type __n
, const key_type
& __k
,
1500 __hash_code __code
) const
1502 __node_base
* __prev_p
= _M_buckets
[__n
];
1505 __node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);
1506 for (;; __p
= __p
->_M_next())
1508 if (this->_M_equals(__k
, __code
, __p
))
1510 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1517 template<typename _Key
, typename _Value
,
1518 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1519 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1522 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1523 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1524 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1526 if (_M_buckets
[__bkt
])
1528 // Bucket is not empty, we just need to insert the new node
1529 // after the bucket before begin.
1530 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1531 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1535 // The bucket is empty, the new node is inserted at the
1536 // beginning of the singly-linked list and the bucket will
1537 // contain _M_before_begin pointer.
1538 __node
->_M_nxt
= _M_before_begin()._M_nxt
;
1539 _M_before_begin()._M_nxt
= __node
;
1541 // We must update former begin bucket that is pointing to
1543 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1544 _M_buckets
[__bkt
] = &_M_before_begin();
1548 template<typename _Key
, typename _Value
,
1549 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1550 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1553 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1554 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1555 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1556 size_type __next_bkt
)
1558 if (!__next
|| __next_bkt
!= __bkt
)
1560 // Bucket is now empty
1561 // First update next bucket if any
1563 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1565 // Second update before begin node if necessary
1566 if (&_M_before_begin() == _M_buckets
[__bkt
])
1567 _M_before_begin()._M_nxt
= __next
;
1568 _M_buckets
[__bkt
] = nullptr;
1572 template<typename _Key
, typename _Value
,
1573 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1574 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1576 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1577 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1578 _Traits
>::__node_base
*
1579 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1580 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1581 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1583 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1584 while (__prev_n
->_M_nxt
!= __n
)
1585 __prev_n
= __prev_n
->_M_nxt
;
1589 template<typename _Key
, typename _Value
,
1590 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1591 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1593 template<typename
... _Args
>
1594 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1595 _ExtractKey
, _Equal
, _H1
,
1596 _H2
, _Hash
, _RehashPolicy
,
1597 _Traits
>::iterator
, bool>
1598 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1599 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1600 _M_emplace(std::true_type
, _Args
&&... __args
)
1602 // First build the node to get access to the hash code
1603 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1604 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1608 __code
= this->_M_hash_code(__k
);
1612 _M_deallocate_node(__node
);
1613 __throw_exception_again
;
1616 size_type __bkt
= _M_bucket_index(__k
, __code
);
1617 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1619 // There is already an equivalent node, no insertion
1620 _M_deallocate_node(__node
);
1621 return std::make_pair(iterator(__p
), false);
1625 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1629 template<typename _Key
, typename _Value
,
1630 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1631 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1633 template<typename
... _Args
>
1634 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1635 _H1
, _H2
, _Hash
, _RehashPolicy
,
1637 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1638 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1639 _M_emplace(std::false_type
, _Args
&&... __args
)
1641 // First build the node to get its hash code.
1642 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1647 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v()));
1651 _M_deallocate_node(__node
);
1652 __throw_exception_again
;
1655 return _M_insert_multi_node(__code
, __node
);
1658 template<typename _Key
, typename _Value
,
1659 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1660 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1662 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1663 _H1
, _H2
, _Hash
, _RehashPolicy
,
1665 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1666 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1667 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
1668 __node_type
* __node
)
1670 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1671 std::pair
<bool, std::size_t> __do_rehash
1672 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1676 if (__do_rehash
.first
)
1678 _M_rehash(__do_rehash
.second
, __saved_state
);
1679 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v()), __code
);
1682 this->_M_store_code(__node
, __code
);
1684 // Always insert at the begining of the bucket.
1685 _M_insert_bucket_begin(__bkt
, __node
);
1687 return iterator(__node
);
1691 _M_deallocate_node(__node
);
1692 __throw_exception_again
;
1696 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1697 // already present). Take ownership of the node, deallocate it on exception.
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 _M_insert_multi_node(__hash_code __code
, __node_type
* __node
)
1709 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1710 std::pair
<bool, std::size_t> __do_rehash
1711 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1715 if (__do_rehash
.first
)
1716 _M_rehash(__do_rehash
.second
, __saved_state
);
1718 this->_M_store_code(__node
, __code
);
1719 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1720 size_type __bkt
= _M_bucket_index(__k
, __code
);
1722 // Find the node before an equivalent one.
1723 __node_base
* __prev
= _M_find_before_node(__bkt
, __k
, __code
);
1726 // Insert after the node before the equivalent one.
1727 __node
->_M_nxt
= __prev
->_M_nxt
;
1728 __prev
->_M_nxt
= __node
;
1731 // The inserted node has no equivalent in the
1732 // hashtable. We must insert the new node at the
1733 // beginning of the bucket to preserve equivalent
1734 // elements' relative positions.
1735 _M_insert_bucket_begin(__bkt
, __node
);
1737 return iterator(__node
);
1741 _M_deallocate_node(__node
);
1742 __throw_exception_again
;
1746 // Insert v if no element with its key is already present.
1747 template<typename _Key
, typename _Value
,
1748 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1749 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1751 template<typename _Arg
>
1752 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1753 _ExtractKey
, _Equal
, _H1
,
1754 _H2
, _Hash
, _RehashPolicy
,
1755 _Traits
>::iterator
, bool>
1756 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1757 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1758 _M_insert(_Arg
&& __v
, std::true_type
)
1760 const key_type
& __k
= this->_M_extract()(__v
);
1761 __hash_code __code
= this->_M_hash_code(__k
);
1762 size_type __bkt
= _M_bucket_index(__k
, __code
);
1764 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1766 return std::make_pair(iterator(__n
), false);
1768 __n
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1769 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __n
), true);
1772 // Insert v unconditionally.
1773 template<typename _Key
, typename _Value
,
1774 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1775 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1777 template<typename _Arg
>
1778 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1779 _H1
, _H2
, _Hash
, _RehashPolicy
,
1781 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1782 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1783 _M_insert(_Arg
&& __v
, std::false_type
)
1785 // First compute the hash code so that we don't do anything if it
1787 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1789 // Second allocate new node so that we don't rehash if it throws.
1790 __node_type
* __node
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1792 return _M_insert_multi_node(__code
, __node
);
1795 template<typename _Key
, typename _Value
,
1796 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1797 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1799 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1800 _H1
, _H2
, _Hash
, _RehashPolicy
,
1802 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1803 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1804 erase(const_iterator __it
)
1806 __node_type
* __n
= __it
._M_cur
;
1807 std::size_t __bkt
= _M_bucket_index(__n
);
1809 // Look for previous node to unlink it from the erased one, this
1810 // is why we need buckets to contain the before begin to make
1811 // this search fast.
1812 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1813 return _M_erase(__bkt
, __prev_n
, __n
);
1816 template<typename _Key
, typename _Value
,
1817 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1818 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1820 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1821 _H1
, _H2
, _Hash
, _RehashPolicy
,
1823 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1824 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1825 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1827 if (__prev_n
== _M_buckets
[__bkt
])
1828 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1829 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1830 else if (__n
->_M_nxt
)
1832 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1833 if (__next_bkt
!= __bkt
)
1834 _M_buckets
[__next_bkt
] = __prev_n
;
1837 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1838 iterator
__result(__n
->_M_next());
1839 _M_deallocate_node(__n
);
1845 template<typename _Key
, typename _Value
,
1846 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1847 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1849 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1850 _H1
, _H2
, _Hash
, _RehashPolicy
,
1852 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1853 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1854 _M_erase(std::true_type
, const key_type
& __k
)
1856 __hash_code __code
= this->_M_hash_code(__k
);
1857 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1859 // Look for the node before the first matching node.
1860 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1864 // We found a matching node, erase it.
1865 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1866 _M_erase(__bkt
, __prev_n
, __n
);
1870 template<typename _Key
, typename _Value
,
1871 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1872 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1874 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1875 _H1
, _H2
, _Hash
, _RehashPolicy
,
1877 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1878 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1879 _M_erase(std::false_type
, const key_type
& __k
)
1881 __hash_code __code
= this->_M_hash_code(__k
);
1882 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1884 // Look for the node before the first matching node.
1885 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1889 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1890 // 526. Is it undefined if a function in the standard changes
1892 // We use one loop to find all matching nodes and another to deallocate
1893 // them so that the key stays valid during the first loop. It might be
1894 // invalidated indirectly when destroying nodes.
1895 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1896 __node_type
* __n_last
= __n
;
1897 std::size_t __n_last_bkt
= __bkt
;
1900 __n_last
= __n_last
->_M_next();
1903 __n_last_bkt
= _M_bucket_index(__n_last
);
1905 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1907 // Deallocate nodes.
1908 size_type __result
= 0;
1911 __node_type
* __p
= __n
->_M_next();
1912 _M_deallocate_node(__n
);
1917 while (__n
!= __n_last
);
1919 if (__prev_n
== _M_buckets
[__bkt
])
1920 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1921 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1922 _M_buckets
[__n_last_bkt
] = __prev_n
;
1923 __prev_n
->_M_nxt
= __n_last
;
1927 template<typename _Key
, typename _Value
,
1928 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1929 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1931 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1932 _H1
, _H2
, _Hash
, _RehashPolicy
,
1934 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1935 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1936 erase(const_iterator __first
, const_iterator __last
)
1938 __node_type
* __n
= __first
._M_cur
;
1939 __node_type
* __last_n
= __last
._M_cur
;
1940 if (__n
== __last_n
)
1941 return iterator(__n
);
1943 std::size_t __bkt
= _M_bucket_index(__n
);
1945 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1946 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1947 std::size_t __n_bkt
= __bkt
;
1952 __node_type
* __tmp
= __n
;
1953 __n
= __n
->_M_next();
1954 _M_deallocate_node(__tmp
);
1958 __n_bkt
= _M_bucket_index(__n
);
1960 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1961 if (__is_bucket_begin
)
1962 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1963 if (__n
== __last_n
)
1965 __is_bucket_begin
= true;
1969 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
1970 _M_buckets
[__n_bkt
] = __prev_n
;
1971 __prev_n
->_M_nxt
= __n
;
1972 return iterator(__n
);
1975 template<typename _Key
, typename _Value
,
1976 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1977 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1980 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1981 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1984 _M_deallocate_nodes(_M_begin());
1985 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
1986 _M_element_count
= 0;
1987 _M_before_begin()._M_nxt
= nullptr;
1990 template<typename _Key
, typename _Value
,
1991 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1992 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1995 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1996 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1997 rehash(size_type __n
)
1999 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
2000 std::size_t __buckets
2001 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
2003 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
2005 if (__buckets
!= _M_bucket_count
)
2006 _M_rehash(__buckets
, __saved_state
);
2008 // No rehash, restore previous state to keep a consistent state.
2009 _M_rehash_policy
._M_reset(__saved_state
);
2012 template<typename _Key
, typename _Value
,
2013 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2014 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2017 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2018 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2019 _M_rehash(size_type __n
, const __rehash_state
& __state
)
2023 _M_rehash_aux(__n
, __unique_keys());
2027 // A failure here means that buckets allocation failed. We only
2028 // have to restore hash policy previous state.
2029 _M_rehash_policy
._M_reset(__state
);
2030 __throw_exception_again
;
2034 // Rehash when there is no equivalent elements.
2035 template<typename _Key
, typename _Value
,
2036 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2037 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2040 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2041 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2042 _M_rehash_aux(size_type __n
, std::true_type
)
2044 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2045 __node_type
* __p
= _M_begin();
2046 _M_before_begin()._M_nxt
= nullptr;
2047 std::size_t __bbegin_bkt
= 0;
2050 __node_type
* __next
= __p
->_M_next();
2051 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2052 if (!__new_buckets
[__bkt
])
2054 __p
->_M_nxt
= _M_before_begin()._M_nxt
;
2055 _M_before_begin()._M_nxt
= __p
;
2056 __new_buckets
[__bkt
] = &_M_before_begin();
2058 __new_buckets
[__bbegin_bkt
] = __p
;
2059 __bbegin_bkt
= __bkt
;
2063 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2064 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2069 if (__builtin_expect(_M_bucket_count
!= 0, true))
2070 _M_deallocate_buckets();
2071 _M_bucket_count
= __n
;
2072 _M_buckets
= __new_buckets
;
2075 // Rehash when there can be equivalent elements, preserve their relative
2077 template<typename _Key
, typename _Value
,
2078 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2079 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2082 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2083 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2084 _M_rehash_aux(size_type __n
, std::false_type
)
2086 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2088 __node_type
* __p
= _M_begin();
2089 _M_before_begin()._M_nxt
= nullptr;
2090 std::size_t __bbegin_bkt
= 0;
2091 std::size_t __prev_bkt
= 0;
2092 __node_type
* __prev_p
= nullptr;
2093 bool __check_bucket
= false;
2097 __node_type
* __next
= __p
->_M_next();
2098 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2100 if (__prev_p
&& __prev_bkt
== __bkt
)
2102 // Previous insert was already in this bucket, we insert after
2103 // the previously inserted one to preserve equivalent elements
2105 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2106 __prev_p
->_M_nxt
= __p
;
2108 // Inserting after a node in a bucket require to check that we
2109 // haven't change the bucket last node, in this case next
2110 // bucket containing its before begin node must be updated. We
2111 // schedule a check as soon as we move out of the sequence of
2112 // equivalent nodes to limit the number of checks.
2113 __check_bucket
= true;
2119 // Check if we shall update the next bucket because of
2120 // insertions into __prev_bkt bucket.
2121 if (__prev_p
->_M_nxt
)
2123 std::size_t __next_bkt
2124 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
2126 if (__next_bkt
!= __prev_bkt
)
2127 __new_buckets
[__next_bkt
] = __prev_p
;
2129 __check_bucket
= false;
2132 if (!__new_buckets
[__bkt
])
2134 __p
->_M_nxt
= _M_before_begin()._M_nxt
;
2135 _M_before_begin()._M_nxt
= __p
;
2136 __new_buckets
[__bkt
] = &_M_before_begin();
2138 __new_buckets
[__bbegin_bkt
] = __p
;
2139 __bbegin_bkt
= __bkt
;
2143 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2144 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2152 if (__check_bucket
&& __prev_p
->_M_nxt
)
2154 std::size_t __next_bkt
2155 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
2156 if (__next_bkt
!= __prev_bkt
)
2157 __new_buckets
[__next_bkt
] = __prev_p
;
2160 if (__builtin_expect(_M_bucket_count
!= 0, true))
2161 _M_deallocate_buckets();
2162 _M_bucket_count
= __n
;
2163 _M_buckets
= __new_buckets
;
2166 _GLIBCXX_END_NAMESPACE_VERSION
2169 #endif // _HASHTABLE_H