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
;
229 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
230 _Equal
, _H1
, _H2
, _Hash
,
231 _RehashPolicy
, _Traits
>;
233 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
236 _RehashPolicy
, _Traits
>;
238 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
239 _Equal
, _H1
, _H2
, _Hash
,
240 _RehashPolicy
, _Traits
>;
242 using __reuse_or_alloc_node_type
=
243 __detail::_ReuseOrAllocNode
<_Key
, _Value
, _Alloc
,
244 _ExtractKey
, _Equal
, _H1
, _H2
, _Hash
,
245 _RehashPolicy
, _Traits
>;
247 // Metaprogramming for picking apart hash caching.
248 template<typename _Cond
>
249 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
251 template<typename _Cond
>
252 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
254 // Compile-time diagnostics.
256 // Getting a bucket index from a node shall not throw because it is used
257 // in methods (erase, swap...) that shall not throw.
258 static_assert(noexcept(declval
<const _Hashtable
&>()
259 ._M_bucket_index((const __node_type
*)nullptr,
261 "Cache the hash code or qualify your functors involved"
262 " in hash code and bucket index computation with noexcept");
264 // Following two static assertions are necessary to guarantee
265 // that local_iterator will be default constructible.
267 // When hash codes are cached local iterator inherits from H2 functor
268 // which must then be default constructible.
269 static_assert(__if_hash_cached
<is_default_constructible
<_H2
>>::value
,
270 "Functor used to map hash code to bucket index"
271 " must be default constructible");
273 // When hash codes are not cached local iterator inherits from
274 // __hash_code_base above to compute node bucket index so it has to be
275 // default constructible.
276 static_assert(__if_hash_not_cached
<
277 is_default_constructible
<
278 // We use _Hashtable_ebo_helper to access the protected
279 // default constructor.
280 __detail::_Hashtable_ebo_helper
<0, __hash_code_base
>>>::value
,
281 "Cache the hash code or make functors involved in hash code"
282 " and bucket index computation default constructible");
284 // When hash codes are not cached local iterator inherits from
285 // __hash_code_base above to compute node bucket index so it has to be
287 static_assert(__if_hash_not_cached
<
288 is_copy_assignable
<__hash_code_base
>>::value
,
289 "Cache the hash code or make functors involved in hash code"
290 " and bucket index computation copy assignable");
292 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
293 typename _ExtractKeya
, typename _Equala
,
294 typename _H1a
, typename _H2a
, typename _Hasha
,
295 typename _RehashPolicya
, typename _Traitsa
,
297 friend struct __detail::_Map_base
;
299 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
300 typename _ExtractKeya
, typename _Equala
,
301 typename _H1a
, typename _H2a
, typename _Hasha
,
302 typename _RehashPolicya
, typename _Traitsa
>
303 friend struct __detail::_Insert_base
;
305 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
306 typename _ExtractKeya
, typename _Equala
,
307 typename _H1a
, typename _H2a
, typename _Hasha
,
308 typename _RehashPolicya
, typename _Traitsa
,
309 bool _Constant_iteratorsa
, bool _Unique_keysa
>
310 friend struct __detail::_Insert
;
312 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
313 typename _ExtractKeya
, typename _Equala
,
314 typename _H1a
, typename _H2a
, typename _Hasha
,
315 typename _RehashPolicya
, typename _Traitsa
>
316 friend struct __detail::_ReuseOrAllocNode
;
318 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
319 typename _ExtractKeya
, typename _Equala
,
320 typename _H1a
, typename _H2a
, typename _Hasha
,
321 typename _RehashPolicya
, typename _Traitsa
>
322 friend struct __detail::_AllocNode
;
325 using size_type
= typename
__hashtable_base::size_type
;
326 using difference_type
= typename
__hashtable_base::difference_type
;
328 using iterator
= typename
__hashtable_base::iterator
;
329 using const_iterator
= typename
__hashtable_base::const_iterator
;
331 using local_iterator
= typename
__hashtable_base::local_iterator
;
332 using const_local_iterator
= typename
__hashtable_base::
333 const_local_iterator
;
336 typedef typename
_Alloc_traits::template rebind_alloc
<__node_type
>
338 // Use __gnu_cxx to benefit from _S_always_equal and al.
339 typedef __gnu_cxx::__alloc_traits
<_Node_alloc_type
> _Node_alloc_traits
;
342 typename
_Alloc_traits::template rebind_alloc
<__bucket_type
>
344 typedef std::allocator_traits
<_Bucket_alloc_type
> _Bucket_alloc_traits
;
346 using __before_begin
= __detail::_Before_begin
<_Node_alloc_type
>;
348 __bucket_type
* _M_buckets
;
349 size_type _M_bucket_count
;
350 __before_begin _M_bbegin
;
351 size_type _M_element_count
;
352 _RehashPolicy _M_rehash_policy
;
356 { return _M_bbegin
; }
358 const _Node_alloc_type
&
359 _M_node_allocator() const
360 { return _M_bbegin
; }
364 { return _M_bbegin
._M_node
; }
367 _M_before_begin() const
368 { return _M_bbegin
._M_node
; }
370 template<typename
... _Args
>
372 _M_allocate_node(_Args
&&... __args
);
375 _M_deallocate_node(__node_type
* __n
);
377 // Deallocate the linked list of nodes pointed to by __n
379 _M_deallocate_nodes(__node_type
* __n
);
382 _M_allocate_buckets(size_type __n
);
385 _M_deallocate_buckets(__bucket_type
*, size_type __n
);
388 _M_deallocate_buckets()
389 { _M_deallocate_buckets(_M_buckets
, _M_bucket_count
); }
391 // Gets bucket begin, deals with the fact that non-empty buckets contain
392 // their before begin node.
394 _M_bucket_begin(size_type __bkt
) const;
398 { return static_cast<__node_type
*>(_M_before_begin()._M_nxt
); }
400 template<typename _NodeGenerator
>
402 _M_assign(const _Hashtable
&, const _NodeGenerator
&);
405 _M_move_assign(_Hashtable
&&, std::true_type
);
408 _M_move_assign(_Hashtable
&&, std::false_type
);
414 // Constructor, destructor, assignment, swap
415 _Hashtable(size_type __bucket_hint
,
416 const _H1
&, const _H2
&, const _Hash
&,
417 const _Equal
&, const _ExtractKey
&,
418 const allocator_type
&);
420 template<typename _InputIterator
>
421 _Hashtable(_InputIterator __first
, _InputIterator __last
,
422 size_type __bucket_hint
,
423 const _H1
&, const _H2
&, const _Hash
&,
424 const _Equal
&, const _ExtractKey
&,
425 const allocator_type
&);
427 _Hashtable(const _Hashtable
&);
429 _Hashtable(_Hashtable
&&) noexcept
;
431 _Hashtable(const _Hashtable
&, const allocator_type
&);
433 _Hashtable(_Hashtable
&&, const allocator_type
&);
435 // Use delegating constructors.
437 _Hashtable(const allocator_type
& __a
)
438 : _Hashtable(10, _H1(), __detail::_Mod_range_hashing(),
439 __detail::_Default_ranged_hash(), key_equal(),
440 __key_extract(), __a
)
444 _Hashtable(size_type __n
= 10,
445 const _H1
& __hf
= _H1(),
446 const key_equal
& __eql
= key_equal(),
447 const allocator_type
& __a
= allocator_type())
448 : _Hashtable(__n
, __hf
, __detail::_Mod_range_hashing(),
449 __detail::_Default_ranged_hash(), __eql
,
450 __key_extract(), __a
)
453 template<typename _InputIterator
>
454 _Hashtable(_InputIterator __f
, _InputIterator __l
,
456 const _H1
& __hf
= _H1(),
457 const key_equal
& __eql
= key_equal(),
458 const allocator_type
& __a
= allocator_type())
459 : _Hashtable(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
460 __detail::_Default_ranged_hash(), __eql
,
461 __key_extract(), __a
)
464 _Hashtable(initializer_list
<value_type
> __l
,
466 const _H1
& __hf
= _H1(),
467 const key_equal
& __eql
= key_equal(),
468 const allocator_type
& __a
= allocator_type())
469 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
,
470 __detail::_Mod_range_hashing(),
471 __detail::_Default_ranged_hash(), __eql
,
472 __key_extract(), __a
)
476 operator=(const _Hashtable
& __ht
);
479 operator=(_Hashtable
&& __ht
)
480 noexcept(_Node_alloc_traits::_S_nothrow_move())
482 constexpr bool __move_storage
=
483 _Node_alloc_traits::_S_propagate_on_move_assign()
484 || _Node_alloc_traits::_S_always_equal();
485 _M_move_assign(std::move(__ht
),
486 integral_constant
<bool, __move_storage
>());
491 operator=(initializer_list
<value_type
> __l
)
493 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
494 _M_before_begin()._M_nxt
= nullptr;
496 this->_M_insert_range(__l
.begin(), __l
.end(), __roan
);
500 ~_Hashtable() noexcept
;
504 noexcept(_Node_alloc_traits::_S_nothrow_swap());
506 // Basic container operations
509 { return iterator(_M_begin()); }
512 begin() const noexcept
513 { return const_iterator(_M_begin()); }
517 { return iterator(nullptr); }
521 { return const_iterator(nullptr); }
524 cbegin() const noexcept
525 { return const_iterator(_M_begin()); }
528 cend() const noexcept
529 { return const_iterator(nullptr); }
532 size() const noexcept
533 { return _M_element_count
; }
536 empty() const noexcept
537 { return size() == 0; }
540 get_allocator() const noexcept
541 { return allocator_type(_M_node_allocator()); }
544 max_size() const noexcept
545 { return _Node_alloc_traits::max_size(_M_node_allocator()); }
550 { return this->_M_eq(); }
552 // hash_function, if present, comes from _Hash_code_base.
556 bucket_count() const noexcept
557 { return _M_bucket_count
; }
560 max_bucket_count() const noexcept
561 { return max_size(); }
564 bucket_size(size_type __n
) const
565 { return std::distance(begin(__n
), end(__n
)); }
568 bucket(const key_type
& __k
) const
569 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
574 return local_iterator(*this, _M_bucket_begin(__n
),
575 __n
, _M_bucket_count
);
580 { return local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
583 begin(size_type __n
) const
585 return const_local_iterator(*this, _M_bucket_begin(__n
),
586 __n
, _M_bucket_count
);
590 end(size_type __n
) const
591 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
595 cbegin(size_type __n
) const
597 return const_local_iterator(*this, _M_bucket_begin(__n
),
598 __n
, _M_bucket_count
);
602 cend(size_type __n
) const
603 { return const_local_iterator(*this, nullptr, __n
, _M_bucket_count
); }
606 load_factor() const noexcept
608 return static_cast<float>(size()) / static_cast<float>(bucket_count());
611 // max_load_factor, if present, comes from _Rehash_base.
613 // Generalization of max_load_factor. Extension, not found in
614 // TR1. Only useful if _RehashPolicy is something other than
617 __rehash_policy() const
618 { return _M_rehash_policy
; }
621 __rehash_policy(const _RehashPolicy
&);
625 find(const key_type
& __k
);
628 find(const key_type
& __k
) const;
631 count(const key_type
& __k
) const;
633 std::pair
<iterator
, iterator
>
634 equal_range(const key_type
& __k
);
636 std::pair
<const_iterator
, const_iterator
>
637 equal_range(const key_type
& __k
) const;
640 // Bucket index computation helpers.
642 _M_bucket_index(__node_type
* __n
) const noexcept
643 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
646 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
647 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
649 // Find and insert helper functions and types
650 // Find the node before the one matching the criteria.
652 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
655 _M_find_node(size_type __bkt
, const key_type
& __key
,
656 __hash_code __c
) const
658 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
660 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
664 // Insert a node at the beginning of a bucket.
666 _M_insert_bucket_begin(size_type
, __node_type
*);
668 // Remove the bucket first node
670 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
671 size_type __next_bkt
);
673 // Get the node before __n in the bucket __bkt
675 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
677 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
678 // no element with its key already present). Take ownership of the node,
679 // deallocate it on exception.
681 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
684 // Insert node with hash code __code. Take ownership of the node,
685 // deallocate it on exception.
687 _M_insert_multi_node(__node_type
* __hint
,
688 __hash_code __code
, __node_type
* __n
);
690 template<typename
... _Args
>
691 std::pair
<iterator
, bool>
692 _M_emplace(std::true_type
, _Args
&&... __args
);
694 template<typename
... _Args
>
696 _M_emplace(std::false_type __uk
, _Args
&&... __args
)
697 { return _M_emplace(cend(), __uk
, std::forward
<_Args
>(__args
)...); }
699 // Emplace with hint, useless when keys are unique.
700 template<typename
... _Args
>
702 _M_emplace(const_iterator
, std::true_type __uk
, _Args
&&... __args
)
703 { return _M_emplace(__uk
, std::forward
<_Args
>(__args
)...).first
; }
705 template<typename
... _Args
>
707 _M_emplace(const_iterator
, std::false_type
, _Args
&&... __args
);
709 template<typename _Arg
, typename _NodeGenerator
>
710 std::pair
<iterator
, bool>
711 _M_insert(_Arg
&&, const _NodeGenerator
&, std::true_type
);
713 template<typename _Arg
, typename _NodeGenerator
>
715 _M_insert(_Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
716 std::false_type __uk
)
718 return _M_insert(cend(), std::forward
<_Arg
>(__arg
), __node_gen
,
722 // Insert with hint, not used when keys are unique.
723 template<typename _Arg
, typename _NodeGenerator
>
725 _M_insert(const_iterator
, _Arg
&& __arg
, const _NodeGenerator
& __node_gen
,
729 _M_insert(std::forward
<_Arg
>(__arg
), __node_gen
, __uk
).first
;
732 // Insert with hint when keys are not unique.
733 template<typename _Arg
, typename _NodeGenerator
>
735 _M_insert(const_iterator
, _Arg
&&, const _NodeGenerator
&, std::false_type
);
738 _M_erase(std::true_type
, const key_type
&);
741 _M_erase(std::false_type
, const key_type
&);
744 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
748 template<typename
... _Args
>
750 emplace(_Args
&&... __args
)
751 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
753 template<typename
... _Args
>
755 emplace_hint(const_iterator __hint
, _Args
&&... __args
)
757 return _M_emplace(__hint
, __unique_keys(),
758 std::forward
<_Args
>(__args
)...);
761 // Insert member functions via inheritance.
765 erase(const_iterator
);
770 { return erase(const_iterator(__it
)); }
773 erase(const key_type
& __k
)
775 if (__builtin_expect(_M_bucket_count
== 0, false))
777 return _M_erase(__unique_keys(), __k
);
781 erase(const_iterator
, const_iterator
);
786 // Set number of buckets to be appropriate for container of n element.
787 void rehash(size_type __n
);
790 // reserve, if present, comes from _Rehash_base.
793 // Helper rehash method used when keys are unique.
794 void _M_rehash_aux(size_type __n
, std::true_type
);
796 // Helper rehash method used when keys can be non-unique.
797 void _M_rehash_aux(size_type __n
, std::false_type
);
799 // Unconditionally change size of bucket array to n, restore
800 // hash policy state to __state on exception.
801 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
805 // Definitions of class template _Hashtable's out-of-line member functions.
806 template<typename _Key
, typename _Value
,
807 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
808 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
810 template<typename
... _Args
>
811 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
812 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__node_type
*
813 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
814 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
815 _M_allocate_node(_Args
&&... __args
)
817 auto __nptr
= _Node_alloc_traits::allocate(_M_node_allocator(), 1);
818 __node_type
* __n
= std::__addressof(*__nptr
);
821 _Value_alloc_type
__a(_M_node_allocator());
822 ::new ((void*)__n
) __node_type();
823 _Value_alloc_traits::construct(__a
, __n
->_M_valptr(),
824 std::forward
<_Args
>(__args
)...);
829 _Node_alloc_traits::deallocate(_M_node_allocator(), __nptr
, 1);
830 __throw_exception_again
;
834 template<typename _Key
, typename _Value
,
835 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
836 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
839 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
840 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
841 _M_deallocate_node(__node_type
* __n
)
843 typedef typename
_Node_alloc_traits::pointer _Ptr
;
844 auto __ptr
= std::pointer_traits
<_Ptr
>::pointer_to(*__n
);
845 _Value_alloc_type
__a(_M_node_allocator());
846 _Value_alloc_traits::destroy(__a
, __n
->_M_valptr());
848 _Node_alloc_traits::deallocate(_M_node_allocator(), __ptr
, 1);
851 template<typename _Key
, typename _Value
,
852 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
853 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
856 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
857 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
858 _M_deallocate_nodes(__node_type
* __n
)
862 __node_type
* __tmp
= __n
;
863 __n
= __n
->_M_next();
864 _M_deallocate_node(__tmp
);
868 template<typename _Key
, typename _Value
,
869 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
870 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
872 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
873 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__bucket_type
*
874 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
875 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
876 _M_allocate_buckets(size_type __n
)
878 _Bucket_alloc_type
__alloc(_M_node_allocator());
880 auto __ptr
= _Bucket_alloc_traits::allocate(__alloc
, __n
);
881 __bucket_type
* __p
= std::__addressof(*__ptr
);
882 __builtin_memset(__p
, 0, __n
* sizeof(__bucket_type
));
886 template<typename _Key
, typename _Value
,
887 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
888 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
891 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
892 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
893 _M_deallocate_buckets(__bucket_type
* __bkts
, size_type __n
)
895 typedef typename
_Bucket_alloc_traits::pointer _Ptr
;
896 auto __ptr
= std::pointer_traits
<_Ptr
>::pointer_to(*__bkts
);
897 _Bucket_alloc_type
__alloc(_M_node_allocator());
898 _Bucket_alloc_traits::deallocate(__alloc
, __ptr
, __n
);
901 template<typename _Key
, typename _Value
,
902 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
903 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
905 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
906 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
907 _Traits
>::__node_type
*
908 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
909 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
910 _M_bucket_begin(size_type __bkt
) const
912 __node_base
* __n
= _M_buckets
[__bkt
];
913 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
916 template<typename _Key
, typename _Value
,
917 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
918 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
920 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
921 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
922 _Hashtable(size_type __bucket_hint
,
923 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
924 const _Equal
& __eq
, const _ExtractKey
& __exk
,
925 const allocator_type
& __a
)
926 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
933 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
934 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
937 template<typename _Key
, typename _Value
,
938 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
939 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
941 template<typename _InputIterator
>
942 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
943 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
944 _Hashtable(_InputIterator __f
, _InputIterator __l
,
945 size_type __bucket_hint
,
946 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
947 const _Equal
& __eq
, const _ExtractKey
& __exk
,
948 const allocator_type
& __a
)
949 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
956 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
958 _M_rehash_policy
._M_next_bkt(
959 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
962 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
965 for (; __f
!= __l
; ++__f
)
971 _M_deallocate_buckets();
972 __throw_exception_again
;
976 template<typename _Key
, typename _Value
,
977 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
978 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
980 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
981 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>&
982 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
983 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::operator=(
984 const _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
985 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>& __ht
)
990 if (_Node_alloc_traits::_S_propagate_on_copy_assign())
992 auto& __this_alloc
= this->_M_node_allocator();
993 auto& __that_alloc
= __ht
._M_node_allocator();
994 if (!_Node_alloc_traits::_S_always_equal()
995 && __this_alloc
!= __that_alloc
)
997 // Replacement allocator cannot free existing storage.
998 _M_deallocate_nodes(_M_begin());
999 if (__builtin_expect(_M_bucket_count
!= 0, true))
1000 _M_deallocate_buckets();
1002 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1003 __hashtable_base::operator=(__ht
);
1004 _M_bucket_count
= __ht
._M_bucket_count
;
1005 _M_element_count
= __ht
._M_element_count
;
1006 _M_rehash_policy
= __ht
._M_rehash_policy
;
1010 [this](const __node_type
* __n
)
1011 { return _M_allocate_node(__n
->_M_v()); });
1015 // _M_assign took care of deallocating all memory. Now we
1016 // must make sure this instance remains in a usable state.
1018 __throw_exception_again
;
1022 std::__alloc_on_copy(__this_alloc
, __that_alloc
);
1025 // Reuse allocated buckets and nodes.
1026 __bucket_type
* __former_buckets
= nullptr;
1027 std::size_t __former_bucket_count
= _M_bucket_count
;
1028 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1030 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1032 __former_buckets
= _M_buckets
;
1033 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
1034 _M_bucket_count
= __ht
._M_bucket_count
;
1037 __builtin_memset(_M_buckets
, 0,
1038 _M_bucket_count
* sizeof(__bucket_type
));
1042 __hashtable_base::operator=(__ht
);
1043 _M_element_count
= __ht
._M_element_count
;
1044 _M_rehash_policy
= __ht
._M_rehash_policy
;
1045 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
1046 _M_before_begin()._M_nxt
= nullptr;
1048 [&__roan
](const __node_type
* __n
)
1049 { return __roan(__n
->_M_v()); });
1050 if (__former_buckets
)
1051 _M_deallocate_buckets(__former_buckets
, __former_bucket_count
);
1055 if (__former_buckets
)
1057 // Restore previous buckets.
1058 _M_deallocate_buckets();
1059 _M_rehash_policy
._M_reset(__former_state
);
1060 _M_buckets
= __former_buckets
;
1061 _M_bucket_count
= __former_bucket_count
;
1063 __builtin_memset(_M_buckets
, 0,
1064 _M_bucket_count
* sizeof(__bucket_type
));
1065 __throw_exception_again
;
1070 template<typename _Key
, typename _Value
,
1071 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1072 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1074 template<typename _NodeGenerator
>
1076 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1077 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1078 _M_assign(const _Hashtable
& __ht
, const _NodeGenerator
& __node_gen
)
1080 __bucket_type
* __buckets
= nullptr;
1082 _M_buckets
= __buckets
= _M_allocate_buckets(_M_bucket_count
);
1086 if (!__ht
._M_before_begin()._M_nxt
)
1089 // First deal with the special first node pointed to by
1091 __node_type
* __ht_n
= __ht
._M_begin();
1092 __node_type
* __this_n
= __node_gen(__ht_n
);
1093 this->_M_copy_code(__this_n
, __ht_n
);
1094 _M_before_begin()._M_nxt
= __this_n
;
1095 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin();
1097 // Then deal with other nodes.
1098 __node_base
* __prev_n
= __this_n
;
1099 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
1101 __this_n
= __node_gen(__ht_n
);
1102 __prev_n
->_M_nxt
= __this_n
;
1103 this->_M_copy_code(__this_n
, __ht_n
);
1104 size_type __bkt
= _M_bucket_index(__this_n
);
1105 if (!_M_buckets
[__bkt
])
1106 _M_buckets
[__bkt
] = __prev_n
;
1107 __prev_n
= __this_n
;
1114 _M_deallocate_buckets();
1115 __throw_exception_again
;
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
>::
1128 _M_rehash_policy
._M_reset();
1129 _M_bucket_count
= 0;
1130 _M_buckets
= nullptr;
1131 _M_before_begin()._M_nxt
= nullptr;
1132 _M_element_count
= 0;
1135 template<typename _Key
, typename _Value
,
1136 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1137 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1140 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1141 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1142 _M_move_assign(_Hashtable
&& __ht
, std::true_type
)
1144 _M_deallocate_nodes(_M_begin());
1145 if (__builtin_expect(_M_bucket_count
!= 0, true))
1146 _M_deallocate_buckets();
1148 __hashtable_base::operator=(std::move(__ht
));
1149 _M_rehash_policy
= __ht
._M_rehash_policy
;
1150 _M_buckets
= __ht
._M_buckets
;
1151 _M_bucket_count
= __ht
._M_bucket_count
;
1152 _M_before_begin()._M_nxt
= __ht
._M_before_begin()._M_nxt
;
1153 _M_element_count
= __ht
._M_element_count
;
1154 std::__alloc_on_move(_M_node_allocator(), __ht
._M_node_allocator());
1156 // Fix buckets containing the _M_before_begin pointers that can't be
1159 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1163 template<typename _Key
, typename _Value
,
1164 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1165 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1168 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1169 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1170 _M_move_assign(_Hashtable
&& __ht
, std::false_type
)
1172 if (__ht
._M_node_allocator() == _M_node_allocator())
1173 _M_move_assign(std::move(__ht
), std::true_type());
1176 // Can't move memory, move elements then.
1177 __bucket_type
* __former_buckets
= nullptr;
1178 size_type __former_bucket_count
= _M_bucket_count
;
1179 const __rehash_state
& __former_state
= _M_rehash_policy
._M_state();
1181 if (_M_bucket_count
!= __ht
._M_bucket_count
)
1183 __former_buckets
= _M_buckets
;
1184 _M_buckets
= _M_allocate_buckets(__ht
._M_bucket_count
);
1185 _M_bucket_count
= __ht
._M_bucket_count
;
1188 __builtin_memset(_M_buckets
, 0,
1189 _M_bucket_count
* sizeof(__bucket_type
));
1193 __hashtable_base::operator=(std::move(__ht
));
1194 _M_element_count
= __ht
._M_element_count
;
1195 _M_rehash_policy
= __ht
._M_rehash_policy
;
1196 __reuse_or_alloc_node_type
__roan(_M_begin(), *this);
1197 _M_before_begin()._M_nxt
= nullptr;
1199 [&__roan
](__node_type
* __n
)
1200 { return __roan(std::move_if_noexcept(__n
->_M_v())); });
1205 if (__former_buckets
)
1207 _M_deallocate_buckets();
1208 _M_rehash_policy
._M_reset(__former_state
);
1209 _M_buckets
= __former_buckets
;
1210 _M_bucket_count
= __former_bucket_count
;
1212 __builtin_memset(_M_buckets
, 0,
1213 _M_bucket_count
* sizeof(__bucket_type
));
1214 __throw_exception_again
;
1219 template<typename _Key
, typename _Value
,
1220 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1221 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1223 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1224 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1225 _Hashtable(const _Hashtable
& __ht
)
1226 : __hashtable_base(__ht
),
1228 __rehash_base(__ht
),
1230 _M_bucket_count(__ht
._M_bucket_count
),
1231 _M_bbegin(_Node_alloc_traits::_S_select_on_copy(
1232 __ht
._M_node_allocator())),
1233 _M_element_count(__ht
._M_element_count
),
1234 _M_rehash_policy(__ht
._M_rehash_policy
)
1237 [this](const __node_type
* __n
)
1238 { return _M_allocate_node(__n
->_M_v()); });
1241 template<typename _Key
, typename _Value
,
1242 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1243 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1245 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1246 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1247 _Hashtable(_Hashtable
&& __ht
) noexcept
1248 : __hashtable_base(__ht
),
1250 __rehash_base(__ht
),
1251 _M_buckets(__ht
._M_buckets
),
1252 _M_bucket_count(__ht
._M_bucket_count
),
1253 _M_bbegin(std::move(__ht
._M_bbegin
)),
1254 _M_element_count(__ht
._M_element_count
),
1255 _M_rehash_policy(__ht
._M_rehash_policy
)
1257 // Update, if necessary, bucket pointing to before begin that hasn't
1260 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1264 template<typename _Key
, typename _Value
,
1265 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1266 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1268 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1269 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1270 _Hashtable(const _Hashtable
& __ht
, const allocator_type
& __a
)
1271 : __hashtable_base(__ht
),
1273 __rehash_base(__ht
),
1275 _M_bucket_count(__ht
._M_bucket_count
),
1276 _M_bbegin(_Node_alloc_type(__a
)),
1277 _M_element_count(__ht
._M_element_count
),
1278 _M_rehash_policy(__ht
._M_rehash_policy
)
1281 [this](const __node_type
* __n
)
1282 { return _M_allocate_node(__n
->_M_v()); });
1285 template<typename _Key
, typename _Value
,
1286 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1287 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1289 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1290 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1291 _Hashtable(_Hashtable
&& __ht
, const allocator_type
& __a
)
1292 : __hashtable_base(__ht
),
1294 __rehash_base(__ht
),
1296 _M_bucket_count(__ht
._M_bucket_count
),
1297 _M_bbegin(_Node_alloc_type(__a
)),
1298 _M_element_count(__ht
._M_element_count
),
1299 _M_rehash_policy(__ht
._M_rehash_policy
)
1301 if (__ht
._M_node_allocator() == _M_node_allocator())
1303 _M_buckets
= __ht
._M_buckets
;
1304 _M_before_begin()._M_nxt
= __ht
._M_before_begin()._M_nxt
;
1305 // Update, if necessary, bucket pointing to before begin that hasn't
1308 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1314 [this](__node_type
* __n
)
1316 return _M_allocate_node(
1317 std::move_if_noexcept(__n
->_M_v()));
1323 template<typename _Key
, typename _Value
,
1324 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1325 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1327 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1328 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1329 ~_Hashtable() noexcept
1333 _M_deallocate_buckets();
1336 template<typename _Key
, typename _Value
,
1337 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1338 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1341 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1342 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1343 swap(_Hashtable
& __x
)
1344 noexcept(_Node_alloc_traits::_S_nothrow_swap())
1346 // The only base class with member variables is hash_code_base.
1347 // We define _Hash_code_base::_M_swap because different
1348 // specializations have different members.
1351 std::__alloc_on_swap(_M_node_allocator(), __x
._M_node_allocator());
1352 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
1353 std::swap(_M_buckets
, __x
._M_buckets
);
1354 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
1355 std::swap(_M_before_begin()._M_nxt
, __x
._M_before_begin()._M_nxt
);
1356 std::swap(_M_element_count
, __x
._M_element_count
);
1358 // Fix buckets containing the _M_before_begin pointers that can't be
1361 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
1363 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
1364 = &(__x
._M_before_begin());
1367 template<typename _Key
, typename _Value
,
1368 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1369 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1372 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1373 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1374 __rehash_policy(const _RehashPolicy
& __pol
)
1376 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
1377 __n_bkt
= __pol
._M_next_bkt(__n_bkt
);
1378 if (__n_bkt
!= _M_bucket_count
)
1379 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
1380 _M_rehash_policy
= __pol
;
1383 template<typename _Key
, typename _Value
,
1384 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1385 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1387 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1388 _H1
, _H2
, _Hash
, _RehashPolicy
,
1390 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1391 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1392 find(const key_type
& __k
)
1394 if (__builtin_expect(_M_bucket_count
== 0, false))
1397 __hash_code __code
= this->_M_hash_code(__k
);
1398 std::size_t __n
= _M_bucket_index(__k
, __code
);
1399 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1400 return __p
? iterator(__p
) : end();
1403 template<typename _Key
, typename _Value
,
1404 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1405 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1407 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1408 _H1
, _H2
, _Hash
, _RehashPolicy
,
1409 _Traits
>::const_iterator
1410 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1411 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1412 find(const key_type
& __k
) const
1414 if (__builtin_expect(_M_bucket_count
== 0, false))
1417 __hash_code __code
= this->_M_hash_code(__k
);
1418 std::size_t __n
= _M_bucket_index(__k
, __code
);
1419 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1420 return __p
? const_iterator(__p
) : end();
1423 template<typename _Key
, typename _Value
,
1424 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1425 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1427 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1428 _H1
, _H2
, _Hash
, _RehashPolicy
,
1430 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1431 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1432 count(const key_type
& __k
) const
1434 if (__builtin_expect(_M_bucket_count
== 0, false))
1437 __hash_code __code
= this->_M_hash_code(__k
);
1438 std::size_t __n
= _M_bucket_index(__k
, __code
);
1439 __node_type
* __p
= _M_bucket_begin(__n
);
1443 std::size_t __result
= 0;
1444 for (;; __p
= __p
->_M_next())
1446 if (this->_M_equals(__k
, __code
, __p
))
1449 // All equivalent values are next to each other, if we
1450 // found a non-equivalent value after an equivalent one it
1451 // means that we won't find any more equivalent values.
1453 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1459 template<typename _Key
, typename _Value
,
1460 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1461 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1463 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1464 _ExtractKey
, _Equal
, _H1
,
1465 _H2
, _Hash
, _RehashPolicy
,
1467 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1468 _ExtractKey
, _Equal
, _H1
,
1469 _H2
, _Hash
, _RehashPolicy
,
1471 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1472 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1473 equal_range(const key_type
& __k
)
1475 if (__builtin_expect(_M_bucket_count
== 0, false))
1476 return std::make_pair(end(), end());
1478 __hash_code __code
= this->_M_hash_code(__k
);
1479 std::size_t __n
= _M_bucket_index(__k
, __code
);
1480 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1484 __node_type
* __p1
= __p
->_M_next();
1485 while (__p1
&& _M_bucket_index(__p1
) == __n
1486 && this->_M_equals(__k
, __code
, __p1
))
1487 __p1
= __p1
->_M_next();
1489 return std::make_pair(iterator(__p
), iterator(__p1
));
1492 return std::make_pair(end(), end());
1495 template<typename _Key
, typename _Value
,
1496 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1497 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1499 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1500 _ExtractKey
, _Equal
, _H1
,
1501 _H2
, _Hash
, _RehashPolicy
,
1502 _Traits
>::const_iterator
,
1503 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1504 _ExtractKey
, _Equal
, _H1
,
1505 _H2
, _Hash
, _RehashPolicy
,
1506 _Traits
>::const_iterator
>
1507 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1508 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1509 equal_range(const key_type
& __k
) const
1511 if (__builtin_expect(_M_bucket_count
== 0, false))
1512 return std::make_pair(end(), end());
1514 __hash_code __code
= this->_M_hash_code(__k
);
1515 std::size_t __n
= _M_bucket_index(__k
, __code
);
1516 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1520 __node_type
* __p1
= __p
->_M_next();
1521 while (__p1
&& _M_bucket_index(__p1
) == __n
1522 && this->_M_equals(__k
, __code
, __p1
))
1523 __p1
= __p1
->_M_next();
1525 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1528 return std::make_pair(end(), end());
1531 // Find the node whose key compares equal to k in the bucket n.
1532 // Return nullptr if no node is found.
1533 template<typename _Key
, typename _Value
,
1534 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1535 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1537 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1538 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1539 _Traits
>::__node_base
*
1540 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1541 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1542 _M_find_before_node(size_type __n
, const key_type
& __k
,
1543 __hash_code __code
) const
1545 __node_base
* __prev_p
= _M_buckets
[__n
];
1549 for (__node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);;
1550 __p
= __p
->_M_next())
1552 if (this->_M_equals(__k
, __code
, __p
))
1555 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1562 template<typename _Key
, typename _Value
,
1563 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1564 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1567 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1568 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1569 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1571 if (_M_buckets
[__bkt
])
1573 // Bucket is not empty, we just need to insert the new node
1574 // after the bucket before begin.
1575 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1576 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1580 // The bucket is empty, the new node is inserted at the
1581 // beginning of the singly-linked list and the bucket will
1582 // contain _M_before_begin pointer.
1583 __node
->_M_nxt
= _M_before_begin()._M_nxt
;
1584 _M_before_begin()._M_nxt
= __node
;
1586 // We must update former begin bucket that is pointing to
1588 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1589 _M_buckets
[__bkt
] = &_M_before_begin();
1593 template<typename _Key
, typename _Value
,
1594 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1595 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1598 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1599 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1600 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1601 size_type __next_bkt
)
1603 if (!__next
|| __next_bkt
!= __bkt
)
1605 // Bucket is now empty
1606 // First update next bucket if any
1608 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1610 // Second update before begin node if necessary
1611 if (&_M_before_begin() == _M_buckets
[__bkt
])
1612 _M_before_begin()._M_nxt
= __next
;
1613 _M_buckets
[__bkt
] = nullptr;
1617 template<typename _Key
, typename _Value
,
1618 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1619 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1621 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1622 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1623 _Traits
>::__node_base
*
1624 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1625 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1626 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1628 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1629 while (__prev_n
->_M_nxt
!= __n
)
1630 __prev_n
= __prev_n
->_M_nxt
;
1634 template<typename _Key
, typename _Value
,
1635 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1636 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1638 template<typename
... _Args
>
1639 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1640 _ExtractKey
, _Equal
, _H1
,
1641 _H2
, _Hash
, _RehashPolicy
,
1642 _Traits
>::iterator
, bool>
1643 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1644 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1645 _M_emplace(std::true_type
, _Args
&&... __args
)
1647 // First build the node to get access to the hash code
1648 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1649 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1653 __code
= this->_M_hash_code(__k
);
1657 _M_deallocate_node(__node
);
1658 __throw_exception_again
;
1661 size_type __bkt
= _M_bucket_index(__k
, __code
);
1662 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1664 // There is already an equivalent node, no insertion
1665 _M_deallocate_node(__node
);
1666 return std::make_pair(iterator(__p
), false);
1670 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1674 template<typename _Key
, typename _Value
,
1675 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1676 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1678 template<typename
... _Args
>
1679 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1680 _H1
, _H2
, _Hash
, _RehashPolicy
,
1682 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1683 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1684 _M_emplace(const_iterator __hint
, std::false_type
, _Args
&&... __args
)
1686 // First build the node to get its hash code.
1687 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1692 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v()));
1696 _M_deallocate_node(__node
);
1697 __throw_exception_again
;
1700 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1703 template<typename _Key
, typename _Value
,
1704 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1705 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1707 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1708 _H1
, _H2
, _Hash
, _RehashPolicy
,
1710 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1711 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1712 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
1713 __node_type
* __node
)
1715 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1716 std::pair
<bool, std::size_t> __do_rehash
1717 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1721 if (__do_rehash
.first
)
1723 _M_rehash(__do_rehash
.second
, __saved_state
);
1724 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v()), __code
);
1727 this->_M_store_code(__node
, __code
);
1729 // Always insert at the beginning of the bucket.
1730 _M_insert_bucket_begin(__bkt
, __node
);
1732 return iterator(__node
);
1736 _M_deallocate_node(__node
);
1737 __throw_exception_again
;
1741 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1742 // already present). Take ownership of the node, deallocate it on exception.
1743 template<typename _Key
, typename _Value
,
1744 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1745 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1747 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1748 _H1
, _H2
, _Hash
, _RehashPolicy
,
1750 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1751 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1752 _M_insert_multi_node(__node_type
* __hint
, __hash_code __code
,
1753 __node_type
* __node
)
1755 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1756 std::pair
<bool, std::size_t> __do_rehash
1757 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1761 if (__do_rehash
.first
)
1762 _M_rehash(__do_rehash
.second
, __saved_state
);
1764 this->_M_store_code(__node
, __code
);
1765 const key_type
& __k
= this->_M_extract()(__node
->_M_v());
1766 size_type __bkt
= _M_bucket_index(__k
, __code
);
1768 // Find the node before an equivalent one or use hint if it exists and
1769 // if it is equivalent.
1771 = __builtin_expect(__hint
!= nullptr, false)
1772 && this->_M_equals(__k
, __code
, __hint
)
1774 : _M_find_before_node(__bkt
, __k
, __code
);
1777 // Insert after the node before the equivalent one.
1778 __node
->_M_nxt
= __prev
->_M_nxt
;
1779 __prev
->_M_nxt
= __node
;
1780 if (__builtin_expect(__prev
== __hint
, false))
1781 // hint might be the last bucket node, in this case we need to
1782 // update next bucket.
1784 && !this->_M_equals(__k
, __code
, __node
->_M_next()))
1786 size_type __next_bkt
= _M_bucket_index(__node
->_M_next());
1787 if (__next_bkt
!= __bkt
)
1788 _M_buckets
[__next_bkt
] = __node
;
1792 // The inserted node has no equivalent in the
1793 // hashtable. We must insert the new node at the
1794 // beginning of the bucket to preserve equivalent
1795 // elements' relative positions.
1796 _M_insert_bucket_begin(__bkt
, __node
);
1798 return iterator(__node
);
1802 _M_deallocate_node(__node
);
1803 __throw_exception_again
;
1807 // Insert v if no element with its key is already present.
1808 template<typename _Key
, typename _Value
,
1809 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1810 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1812 template<typename _Arg
, typename _NodeGenerator
>
1813 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1814 _ExtractKey
, _Equal
, _H1
,
1815 _H2
, _Hash
, _RehashPolicy
,
1816 _Traits
>::iterator
, bool>
1817 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1818 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1819 _M_insert(_Arg
&& __v
, const _NodeGenerator
& __node_gen
, std::true_type
)
1821 const key_type
& __k
= this->_M_extract()(__v
);
1822 __hash_code __code
= this->_M_hash_code(__k
);
1823 size_type __bkt
= _M_bucket_index(__k
, __code
);
1825 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1827 return std::make_pair(iterator(__n
), false);
1829 __n
= __node_gen(std::forward
<_Arg
>(__v
));
1830 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __n
), true);
1833 // Insert v unconditionally.
1834 template<typename _Key
, typename _Value
,
1835 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1836 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1838 template<typename _Arg
, typename _NodeGenerator
>
1839 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1840 _H1
, _H2
, _Hash
, _RehashPolicy
,
1842 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1843 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1844 _M_insert(const_iterator __hint
, _Arg
&& __v
,
1845 const _NodeGenerator
& __node_gen
,
1848 // First compute the hash code so that we don't do anything if it
1850 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1852 // Second allocate new node so that we don't rehash if it throws.
1853 __node_type
* __node
= __node_gen(std::forward
<_Arg
>(__v
));
1855 return _M_insert_multi_node(__hint
._M_cur
, __code
, __node
);
1858 template<typename _Key
, typename _Value
,
1859 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1860 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1862 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1863 _H1
, _H2
, _Hash
, _RehashPolicy
,
1865 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1866 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1867 erase(const_iterator __it
)
1869 __node_type
* __n
= __it
._M_cur
;
1870 std::size_t __bkt
= _M_bucket_index(__n
);
1872 // Look for previous node to unlink it from the erased one, this
1873 // is why we need buckets to contain the before begin to make
1874 // this search fast.
1875 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1876 return _M_erase(__bkt
, __prev_n
, __n
);
1879 template<typename _Key
, typename _Value
,
1880 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1881 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1883 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1884 _H1
, _H2
, _Hash
, _RehashPolicy
,
1886 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1887 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1888 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1890 if (__prev_n
== _M_buckets
[__bkt
])
1891 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1892 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1893 else if (__n
->_M_nxt
)
1895 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1896 if (__next_bkt
!= __bkt
)
1897 _M_buckets
[__next_bkt
] = __prev_n
;
1900 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1901 iterator
__result(__n
->_M_next());
1902 _M_deallocate_node(__n
);
1908 template<typename _Key
, typename _Value
,
1909 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1910 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1912 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1913 _H1
, _H2
, _Hash
, _RehashPolicy
,
1915 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1916 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1917 _M_erase(std::true_type
, const key_type
& __k
)
1919 __hash_code __code
= this->_M_hash_code(__k
);
1920 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1922 // Look for the node before the first matching node.
1923 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1927 // We found a matching node, erase it.
1928 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1929 _M_erase(__bkt
, __prev_n
, __n
);
1933 template<typename _Key
, typename _Value
,
1934 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1935 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1937 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1938 _H1
, _H2
, _Hash
, _RehashPolicy
,
1940 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1941 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1942 _M_erase(std::false_type
, const key_type
& __k
)
1944 __hash_code __code
= this->_M_hash_code(__k
);
1945 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1947 // Look for the node before the first matching node.
1948 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1952 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1953 // 526. Is it undefined if a function in the standard changes
1955 // We use one loop to find all matching nodes and another to deallocate
1956 // them so that the key stays valid during the first loop. It might be
1957 // invalidated indirectly when destroying nodes.
1958 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1959 __node_type
* __n_last
= __n
;
1960 std::size_t __n_last_bkt
= __bkt
;
1963 __n_last
= __n_last
->_M_next();
1966 __n_last_bkt
= _M_bucket_index(__n_last
);
1968 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1970 // Deallocate nodes.
1971 size_type __result
= 0;
1974 __node_type
* __p
= __n
->_M_next();
1975 _M_deallocate_node(__n
);
1980 while (__n
!= __n_last
);
1982 if (__prev_n
== _M_buckets
[__bkt
])
1983 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1984 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1985 _M_buckets
[__n_last_bkt
] = __prev_n
;
1986 __prev_n
->_M_nxt
= __n_last
;
1990 template<typename _Key
, typename _Value
,
1991 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1992 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1994 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1995 _H1
, _H2
, _Hash
, _RehashPolicy
,
1997 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1998 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1999 erase(const_iterator __first
, const_iterator __last
)
2001 __node_type
* __n
= __first
._M_cur
;
2002 __node_type
* __last_n
= __last
._M_cur
;
2003 if (__n
== __last_n
)
2004 return iterator(__n
);
2006 std::size_t __bkt
= _M_bucket_index(__n
);
2008 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
2009 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
2010 std::size_t __n_bkt
= __bkt
;
2015 __node_type
* __tmp
= __n
;
2016 __n
= __n
->_M_next();
2017 _M_deallocate_node(__tmp
);
2021 __n_bkt
= _M_bucket_index(__n
);
2023 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
2024 if (__is_bucket_begin
)
2025 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
2026 if (__n
== __last_n
)
2028 __is_bucket_begin
= true;
2032 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
2033 _M_buckets
[__n_bkt
] = __prev_n
;
2034 __prev_n
->_M_nxt
= __n
;
2035 return iterator(__n
);
2038 template<typename _Key
, typename _Value
,
2039 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2040 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2043 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2044 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2047 _M_deallocate_nodes(_M_begin());
2048 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
2049 _M_element_count
= 0;
2050 _M_before_begin()._M_nxt
= nullptr;
2053 template<typename _Key
, typename _Value
,
2054 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2055 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2058 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2059 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2060 rehash(size_type __n
)
2062 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
2063 std::size_t __buckets
2064 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
2066 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
2068 if (__buckets
!= _M_bucket_count
)
2069 _M_rehash(__buckets
, __saved_state
);
2071 // No rehash, restore previous state to keep a consistent state.
2072 _M_rehash_policy
._M_reset(__saved_state
);
2075 template<typename _Key
, typename _Value
,
2076 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2077 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2080 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2081 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2082 _M_rehash(size_type __n
, const __rehash_state
& __state
)
2086 _M_rehash_aux(__n
, __unique_keys());
2090 // A failure here means that buckets allocation failed. We only
2091 // have to restore hash policy previous state.
2092 _M_rehash_policy
._M_reset(__state
);
2093 __throw_exception_again
;
2097 // Rehash when there is no equivalent elements.
2098 template<typename _Key
, typename _Value
,
2099 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2100 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2103 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2104 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2105 _M_rehash_aux(size_type __n
, std::true_type
)
2107 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2108 __node_type
* __p
= _M_begin();
2109 _M_before_begin()._M_nxt
= nullptr;
2110 std::size_t __bbegin_bkt
= 0;
2113 __node_type
* __next
= __p
->_M_next();
2114 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2115 if (!__new_buckets
[__bkt
])
2117 __p
->_M_nxt
= _M_before_begin()._M_nxt
;
2118 _M_before_begin()._M_nxt
= __p
;
2119 __new_buckets
[__bkt
] = &_M_before_begin();
2121 __new_buckets
[__bbegin_bkt
] = __p
;
2122 __bbegin_bkt
= __bkt
;
2126 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2127 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2132 if (__builtin_expect(_M_bucket_count
!= 0, true))
2133 _M_deallocate_buckets();
2134 _M_bucket_count
= __n
;
2135 _M_buckets
= __new_buckets
;
2138 // Rehash when there can be equivalent elements, preserve their relative
2140 template<typename _Key
, typename _Value
,
2141 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
2142 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
2145 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
2146 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
2147 _M_rehash_aux(size_type __n
, std::false_type
)
2149 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
2151 __node_type
* __p
= _M_begin();
2152 _M_before_begin()._M_nxt
= nullptr;
2153 std::size_t __bbegin_bkt
= 0;
2154 std::size_t __prev_bkt
= 0;
2155 __node_type
* __prev_p
= nullptr;
2156 bool __check_bucket
= false;
2160 __node_type
* __next
= __p
->_M_next();
2161 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
2163 if (__prev_p
&& __prev_bkt
== __bkt
)
2165 // Previous insert was already in this bucket, we insert after
2166 // the previously inserted one to preserve equivalent elements
2168 __p
->_M_nxt
= __prev_p
->_M_nxt
;
2169 __prev_p
->_M_nxt
= __p
;
2171 // Inserting after a node in a bucket require to check that we
2172 // haven't change the bucket last node, in this case next
2173 // bucket containing its before begin node must be updated. We
2174 // schedule a check as soon as we move out of the sequence of
2175 // equivalent nodes to limit the number of checks.
2176 __check_bucket
= true;
2182 // Check if we shall update the next bucket because of
2183 // insertions into __prev_bkt bucket.
2184 if (__prev_p
->_M_nxt
)
2186 std::size_t __next_bkt
2187 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
2189 if (__next_bkt
!= __prev_bkt
)
2190 __new_buckets
[__next_bkt
] = __prev_p
;
2192 __check_bucket
= false;
2195 if (!__new_buckets
[__bkt
])
2197 __p
->_M_nxt
= _M_before_begin()._M_nxt
;
2198 _M_before_begin()._M_nxt
= __p
;
2199 __new_buckets
[__bkt
] = &_M_before_begin();
2201 __new_buckets
[__bbegin_bkt
] = __p
;
2202 __bbegin_bkt
= __bkt
;
2206 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
2207 __new_buckets
[__bkt
]->_M_nxt
= __p
;
2215 if (__check_bucket
&& __prev_p
->_M_nxt
)
2217 std::size_t __next_bkt
2218 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
2219 if (__next_bkt
!= __prev_bkt
)
2220 __new_buckets
[__next_bkt
] = __prev_p
;
2223 if (__builtin_expect(_M_bucket_count
!= 0, true))
2224 _M_deallocate_buckets();
2225 _M_bucket_count
= __n
;
2226 _M_buckets
= __new_buckets
;
2229 _GLIBCXX_END_NAMESPACE_VERSION
2232 #endif // _HASHTABLE_H