1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2012 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
>
42 using __cache_default
= __not_
<__and_
<is_integral
<_Tp
>,
44 integral_constant
<bool, !__is_final(_Hash
)>,
45 __detail::__is_noexcept_hash
<_Tp
, _Hash
> >>;
48 * Primary class template _Hashtable.
50 * @ingroup hashtable-detail
52 * @tparam _Value CopyConstructible type.
54 * @tparam _Key CopyConstructible type.
56 * @tparam _Alloc An allocator type
57 * ([lib.allocator.requirements]) whose _Alloc::value_type is
58 * _Value. As a conforming extension, we allow for
59 * _Alloc::value_type != _Value.
61 * @tparam _ExtractKey Function object that takes an object of type
62 * _Value and returns a value of type _Key.
64 * @tparam _Equal Function object that takes two objects of type k
65 * and returns a bool-like value that is true if the two objects
66 * are considered equal.
68 * @tparam _H1 The hash function. A unary function object with
69 * argument type _Key and result type size_t. Return values should
70 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
72 * @tparam _H2 The range-hashing function (in the terminology of
73 * Tavori and Dreizin). A binary function object whose argument
74 * types and result type are all size_t. Given arguments r and N,
75 * the return value is in the range [0, N).
77 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
78 * binary function whose argument types are _Key and size_t and
79 * whose result type is size_t. Given arguments k and N, the
80 * return value is in the range [0, N). Default: hash(k, N) =
81 * h2(h1(k), N). If _Hash is anything other than the default, _H1
82 * and _H2 are ignored.
84 * @tparam _RehashPolicy Policy class with three members, all of
85 * which govern the bucket count. _M_next_bkt(n) returns a bucket
86 * count no smaller than n. _M_bkt_for_elements(n) returns a
87 * bucket count appropriate for an element count of n.
88 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
89 * current bucket count is n_bkt and the current element count is
90 * n_elt, we need to increase the bucket count. If so, returns
91 * make_pair(true, n), where n is the new bucket count. If not,
92 * returns make_pair(false, <anything>)
94 * @tparam _Traits Compile-time class with three boolean
95 * std::integral_constant members: __cache_hash_code, __constant_iterators,
98 * Each _Hashtable data structure has:
100 * - _Bucket[] _M_buckets
101 * - _Hash_node_base _M_bbegin
102 * - size_type _M_bucket_count
103 * - size_type _M_element_count
105 * with _Bucket being _Hash_node* and _Hash_node containing:
107 * - _Hash_node* _M_next
109 * - size_t _M_hash_code if cache_hash_code is true
111 * In terms of Standard containers the hashtable is like the aggregation of:
113 * - std::forward_list<_Node> containing the elements
114 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
116 * The non-empty buckets contain the node before the first node in the
117 * bucket. This design makes it possible to implement something like a
118 * std::forward_list::insert_after on container insertion and
119 * std::forward_list::erase_after on container erase
120 * calls. _M_before_begin is equivalent to
121 * std::forward_list::before_begin. Empty buckets contain
122 * nullptr. Note that one of the non-empty buckets contains
123 * &_M_before_begin which is not a dereferenceable node so the
124 * node pointer in a bucket shall never be dereferenced, only its
127 * Walking through a bucket's nodes requires a check on the hash code to
128 * see if each node is still in the bucket. Such a design assumes a
129 * quite efficient hash functor and is one of the reasons it is
130 * highly advisable to set __cache_hash_code to true.
132 * The container iterators are simply built from nodes. This way
133 * incrementing the iterator is perfectly efficient independent of
134 * how many empty buckets there are in the container.
136 * On insert we compute the element's hash code and use it to find the
137 * bucket index. If the element must be inserted in an empty bucket
138 * we add it at the beginning of the singly linked list and make the
139 * bucket point to _M_before_begin. The bucket that used to point to
140 * _M_before_begin, if any, is updated to point to its new before
143 * On erase, the simple iterator design requires using the hash
144 * functor to get the index of the bucket to update. For this
145 * reason, when __cache_hash_code is set to false the hash functor must
146 * not throw and this is enforced by a static assertion.
148 * Functionality is implemented by decomposition into base classes,
149 * where the derived _Hashtable class is used in _Map_base,
150 * _Insert, _Rehash_base, and _Equality base classes to access the
151 * "this" pointer. _Hashtable_base is used in the base classes as a
152 * non-recursive, fully-completed-type so that detailed nested type
153 * information, such as iterator type and node type, can be
154 * used. This is similar to the "Curiously Recurring Template
155 * Pattern" (CRTP) technique, but uses a reconstructed, not
156 * explicitly passed, template pattern.
158 * Base class templates are:
159 * - __detail::_Hashtable_base
160 * - __detail::_Map_base
161 * - __detail::_Insert
162 * - __detail::_Rehash_base
163 * - __detail::_Equality
165 template<typename _Key
, typename _Value
, typename _Alloc
,
166 typename _ExtractKey
, typename _Equal
,
167 typename _H1
, typename _H2
, typename _Hash
,
168 typename _RehashPolicy
, typename _Traits
>
170 : public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
171 _H1
, _H2
, _Hash
, _Traits
>,
172 public __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
173 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
174 public __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
175 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
176 public __detail::_Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
177 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
178 public __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
179 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
182 typedef _Key key_type
;
183 typedef _Value value_type
;
184 typedef _Alloc allocator_type
;
185 typedef _Equal key_equal
;
187 // mapped_type, if present, comes from _Map_base.
188 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
189 typedef typename
_Alloc::pointer pointer
;
190 typedef typename
_Alloc::const_pointer const_pointer
;
191 typedef typename
_Alloc::reference reference
;
192 typedef typename
_Alloc::const_reference const_reference
;
195 using __rehash_type
= _RehashPolicy
;
196 using __rehash_state
= typename
__rehash_type::_State
;
198 using __traits_type
= _Traits
;
199 using __hash_cached
= typename
__traits_type::__hash_cached
;
200 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
201 using __unique_keys
= typename
__traits_type::__unique_keys
;
203 using __key_extract
= typename
std::conditional
<
204 __constant_iterators::value
,
206 __detail::_Select1st
>::type
;
208 using __hashtable_base
= __detail::
209 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
210 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
212 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
213 using __hash_code
= typename
__hashtable_base::__hash_code
;
214 using __node_type
= typename
__hashtable_base::__node_type
;
215 using __node_base
= typename
__hashtable_base::__node_base
;
216 using __bucket_type
= typename
__hashtable_base::__bucket_type
;
217 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
218 using __iconv_type
= typename
__hashtable_base::__iconv_type
;
220 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
221 _Equal
, _H1
, _H2
, _Hash
,
222 _RehashPolicy
, _Traits
>;
224 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
227 _RehashPolicy
, _Traits
>;
229 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
230 _Equal
, _H1
, _H2
, _Hash
,
231 _RehashPolicy
, _Traits
>;
233 // Metaprogramming for picking apart hash caching.
234 using __hash_noexcept
= __detail::__is_noexcept_hash
<_Key
, _H1
>;
236 template<typename _Cond
>
237 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
239 template<typename _Cond
>
240 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
242 // Compile-time diagnostics.
244 // When hash codes are not cached the hash functor shall not
245 // throw because it is used in methods (erase, swap...) that
247 static_assert(__if_hash_not_cached
<__hash_noexcept
>::value
,
248 "Cache the hash code"
249 " or qualify your hash functor with noexcept");
251 // Following two static assertions are necessary to guarantee
252 // that swapping two hashtable instances won't invalidate
253 // associated local iterators.
255 // When hash codes are cached local iterator only uses H2 which
256 // must then be empty.
257 static_assert(__if_hash_cached
<is_empty
<_H2
>>::value
,
258 "Functor used to map hash code to bucket index"
261 // When hash codes are not cached local iterator is going to use
262 // __hash_code_base above to compute node bucket index so it has
264 static_assert(__if_hash_not_cached
<is_empty
<__hash_code_base
>>::value
,
265 "Cache the hash code or make functors involved in hash code"
266 " and bucket index computation empty");
269 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
270 typename _ExtractKeya
, typename _Equala
,
271 typename _H1a
, typename _H2a
, typename _Hasha
,
272 typename _RehashPolicya
, typename _Traitsa
,
274 friend struct __detail::_Map_base
;
276 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
277 typename _ExtractKeya
, typename _Equala
,
278 typename _H1a
, typename _H2a
, typename _Hasha
,
279 typename _RehashPolicya
, typename _Traitsa
>
280 friend struct __detail::_Insert_base
;
282 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
283 typename _ExtractKeya
, typename _Equala
,
284 typename _H1a
, typename _H2a
, typename _Hasha
,
285 typename _RehashPolicya
, typename _Traitsa
,
286 bool _Constant_iteratorsa
, bool _Unique_keysa
>
287 friend struct __detail::_Insert
;
289 using size_type
= typename
__hashtable_base::size_type
;
290 using difference_type
= typename
__hashtable_base::difference_type
;
292 using iterator
= typename
__hashtable_base::iterator
;
293 using const_iterator
= typename
__hashtable_base::const_iterator
;
295 using local_iterator
= typename
__hashtable_base::local_iterator
;
296 using const_local_iterator
= typename
__hashtable_base::
297 const_local_iterator
;
300 typedef typename
_Alloc::template rebind
<__node_type
>::other
301 _Node_allocator_type
;
302 typedef typename
_Alloc::template rebind
<__bucket_type
>::other
303 _Bucket_allocator_type
;
305 using __before_begin
= __detail::_Before_begin
<_Node_allocator_type
>;
307 __bucket_type
* _M_buckets
;
308 size_type _M_bucket_count
;
309 __before_begin _M_bbegin
;
310 size_type _M_element_count
;
311 _RehashPolicy _M_rehash_policy
;
313 _Node_allocator_type
&
315 { return _M_bbegin
; }
317 const _Node_allocator_type
&
318 _M_node_allocator() const
319 { return _M_bbegin
; }
323 { return _M_bbegin
._M_node
; }
326 _M_before_begin() const
327 { return _M_bbegin
._M_node
; }
329 template<typename
... _Args
>
331 _M_allocate_node(_Args
&&... __args
);
334 _M_deallocate_node(__node_type
* __n
);
336 // Deallocate the linked list of nodes pointed to by __n
338 _M_deallocate_nodes(__node_type
* __n
);
341 _M_allocate_buckets(size_type __n
);
344 _M_deallocate_buckets(__bucket_type
*, size_type __n
);
346 // Gets bucket begin, deals with the fact that non-empty buckets contain
347 // their before begin node.
349 _M_bucket_begin(size_type __bkt
) const;
353 { return static_cast<__node_type
*>(_M_before_begin()._M_nxt
); }
356 // Constructor, destructor, assignment, swap
357 _Hashtable(size_type __bucket_hint
,
358 const _H1
&, const _H2
&, const _Hash
&,
359 const _Equal
&, const _ExtractKey
&,
360 const allocator_type
&);
362 template<typename _InputIterator
>
363 _Hashtable(_InputIterator __first
, _InputIterator __last
,
364 size_type __bucket_hint
,
365 const _H1
&, const _H2
&, const _Hash
&,
366 const _Equal
&, const _ExtractKey
&,
367 const allocator_type
&);
369 _Hashtable(const _Hashtable
&);
371 _Hashtable(_Hashtable
&&);
373 // Use delegating constructors.
375 _Hashtable(size_type __n
= 10,
376 const _H1
& __hf
= _H1(),
377 const key_equal
& __eql
= key_equal(),
378 const allocator_type
& __a
= allocator_type())
379 : _Hashtable(__n
, __hf
, __detail::_Mod_range_hashing(),
380 __detail::_Default_ranged_hash(), __eql
,
381 __key_extract(), __a
)
384 template<typename _InputIterator
>
385 _Hashtable(_InputIterator __f
, _InputIterator __l
,
387 const _H1
& __hf
= _H1(),
388 const key_equal
& __eql
= key_equal(),
389 const allocator_type
& __a
= allocator_type())
390 : _Hashtable(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
391 __detail::_Default_ranged_hash(), __eql
,
392 __key_extract(), __a
)
395 _Hashtable(initializer_list
<value_type
> __l
,
397 const _H1
& __hf
= _H1(),
398 const key_equal
& __eql
= key_equal(),
399 const allocator_type
& __a
= allocator_type())
400 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
,
401 __detail::_Mod_range_hashing(),
402 __detail::_Default_ranged_hash(), __eql
,
403 __key_extract(), __a
)
407 operator=(const _Hashtable
& __ht
)
409 _Hashtable
__tmp(__ht
);
415 operator=(_Hashtable
&& __ht
)
425 operator=(initializer_list
<value_type
> __l
)
428 this->insert(__l
.begin(), __l
.end());
432 ~_Hashtable() noexcept
;
434 void swap(_Hashtable
&);
436 // Basic container operations
439 { return iterator(_M_begin()); }
442 begin() const noexcept
443 { return const_iterator(_M_begin()); }
447 { return iterator(nullptr); }
451 { return const_iterator(nullptr); }
454 cbegin() const noexcept
455 { return const_iterator(_M_begin()); }
458 cend() const noexcept
459 { return const_iterator(nullptr); }
462 size() const noexcept
463 { return _M_element_count
; }
466 empty() const noexcept
467 { return size() == 0; }
470 get_allocator() const noexcept
471 { return allocator_type(_M_node_allocator()); }
474 max_size() const noexcept
475 { return _M_node_allocator().max_size(); }
480 { return this->_M_eq(); }
482 // hash_function, if present, comes from _Hash_code_base.
486 bucket_count() const noexcept
487 { return _M_bucket_count
; }
490 max_bucket_count() const noexcept
491 { return max_size(); }
494 bucket_size(size_type __n
) const
495 { return std::distance(begin(__n
), end(__n
)); }
498 bucket(const key_type
& __k
) const
499 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
503 { return local_iterator(_M_bucket_begin(__n
), __n
, _M_bucket_count
); }
507 { return local_iterator(nullptr, __n
, _M_bucket_count
); }
510 begin(size_type __n
) const
511 { return const_local_iterator(_M_bucket_begin(__n
), __n
,
515 end(size_type __n
) const
516 { return const_local_iterator(nullptr, __n
, _M_bucket_count
); }
520 cbegin(size_type __n
) const
521 { return const_local_iterator(_M_bucket_begin(__n
), __n
,
525 cend(size_type __n
) const
526 { return const_local_iterator(nullptr, __n
, _M_bucket_count
); }
529 load_factor() const noexcept
531 return static_cast<float>(size()) / static_cast<float>(bucket_count());
534 // max_load_factor, if present, comes from _Rehash_base.
536 // Generalization of max_load_factor. Extension, not found in
537 // TR1. Only useful if _RehashPolicy is something other than
540 __rehash_policy() const
541 { return _M_rehash_policy
; }
544 __rehash_policy(const _RehashPolicy
&);
548 find(const key_type
& __k
);
551 find(const key_type
& __k
) const;
554 count(const key_type
& __k
) const;
556 std::pair
<iterator
, iterator
>
557 equal_range(const key_type
& __k
);
559 std::pair
<const_iterator
, const_iterator
>
560 equal_range(const key_type
& __k
) const;
563 // Bucket index computation helpers.
565 _M_bucket_index(__node_type
* __n
) const
566 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
569 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
570 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
572 // Find and insert helper functions and types
573 // Find the node before the one matching the criteria.
575 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
578 _M_find_node(size_type __bkt
, const key_type
& __key
,
579 __hash_code __c
) const
581 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
583 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
587 // Insert a node at the beginning of a bucket.
589 _M_insert_bucket_begin(size_type
, __node_type
*);
591 // Remove the bucket first node
593 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
594 size_type __next_bkt
);
596 // Get the node before __n in the bucket __bkt
598 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
600 // Insert node with hash code __code, in bucket bkt if no rehash (assumes
601 // no element with its key already present). Take ownership of the node,
602 // deallocate it on exception.
604 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
607 // Insert node with hash code __code. Take ownership of the node,
608 // deallocate it on exception.
610 _M_insert_multi_node(__hash_code __code
, __node_type
* __n
);
612 template<typename
... _Args
>
613 std::pair
<iterator
, bool>
614 _M_emplace(std::true_type
, _Args
&&... __args
);
616 template<typename
... _Args
>
618 _M_emplace(std::false_type
, _Args
&&... __args
);
620 template<typename _Arg
>
621 std::pair
<iterator
, bool>
622 _M_insert(_Arg
&&, std::true_type
);
624 template<typename _Arg
>
626 _M_insert(_Arg
&&, std::false_type
);
629 _M_erase(std::true_type
, const key_type
&);
632 _M_erase(std::false_type
, const key_type
&);
635 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
);
639 template<typename
... _Args
>
641 emplace(_Args
&&... __args
)
642 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
644 template<typename
... _Args
>
646 emplace_hint(const_iterator
, _Args
&&... __args
)
647 { return __iconv_type()(emplace(std::forward
<_Args
>(__args
)...)); }
649 // Insert member functions via inheritance.
653 erase(const_iterator
);
658 { return erase(const_iterator(__it
)); }
661 erase(const key_type
& __k
)
662 { return _M_erase(__unique_keys(), __k
); }
665 erase(const_iterator
, const_iterator
);
670 // Set number of buckets to be appropriate for container of n element.
671 void rehash(size_type __n
);
674 // reserve, if present, comes from _Rehash_base.
677 // Helper rehash method used when keys are unique.
678 void _M_rehash_aux(size_type __n
, std::true_type
);
680 // Helper rehash method used when keys can be non-unique.
681 void _M_rehash_aux(size_type __n
, std::false_type
);
683 // Unconditionally change size of bucket array to n, restore
684 // hash policy state to __state on exception.
685 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
689 // Definitions of class template _Hashtable's out-of-line member functions.
690 template<typename _Key
, typename _Value
,
691 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
692 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
694 template<typename
... _Args
>
695 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
696 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__node_type
*
697 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
698 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
699 _M_allocate_node(_Args
&&... __args
)
701 __node_type
* __n
= _M_node_allocator().allocate(1);
704 _M_node_allocator().construct(__n
, std::forward
<_Args
>(__args
)...);
709 _M_node_allocator().deallocate(__n
, 1);
710 __throw_exception_again
;
714 template<typename _Key
, typename _Value
,
715 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
716 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
719 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
720 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
721 _M_deallocate_node(__node_type
* __n
)
723 _M_node_allocator().destroy(__n
);
724 _M_node_allocator().deallocate(__n
, 1);
727 template<typename _Key
, typename _Value
,
728 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
729 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
732 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
733 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
734 _M_deallocate_nodes(__node_type
* __n
)
738 __node_type
* __tmp
= __n
;
739 __n
= __n
->_M_next();
740 _M_deallocate_node(__tmp
);
744 template<typename _Key
, typename _Value
,
745 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
746 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
748 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
749 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__bucket_type
*
750 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
751 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
752 _M_allocate_buckets(size_type __n
)
754 _Bucket_allocator_type
__alloc(_M_node_allocator());
756 __bucket_type
* __p
= __alloc
.allocate(__n
);
757 __builtin_memset(__p
, 0, __n
* sizeof(__bucket_type
));
761 template<typename _Key
, typename _Value
,
762 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
763 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
766 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
767 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
768 _M_deallocate_buckets(__bucket_type
* __p
, size_type __n
)
770 _Bucket_allocator_type
__alloc(_M_node_allocator());
771 __alloc
.deallocate(__p
, __n
);
774 template<typename _Key
, typename _Value
,
775 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
776 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
778 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
779 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
780 _Traits
>::__node_type
*
781 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
782 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
783 _M_bucket_begin(size_type __bkt
) const
785 __node_base
* __n
= _M_buckets
[__bkt
];
786 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
789 template<typename _Key
, typename _Value
,
790 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
791 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
793 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
794 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
795 _Hashtable(size_type __bucket_hint
,
796 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
797 const _Equal
& __eq
, const _ExtractKey
& __exk
,
798 const allocator_type
& __a
)
799 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
807 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
808 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
811 template<typename _Key
, typename _Value
,
812 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
813 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
815 template<typename _InputIterator
>
816 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
817 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
818 _Hashtable(_InputIterator __f
, _InputIterator __l
,
819 size_type __bucket_hint
,
820 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
821 const _Equal
& __eq
, const _ExtractKey
& __exk
,
822 const allocator_type
& __a
)
823 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
831 auto __nb_elems
= __detail::__distance_fw(__f
, __l
);
833 _M_rehash_policy
._M_next_bkt(
834 std::max(_M_rehash_policy
._M_bkt_for_elements(__nb_elems
),
837 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
840 for (; __f
!= __l
; ++__f
)
846 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
847 __throw_exception_again
;
851 template<typename _Key
, typename _Value
,
852 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
853 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
855 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
856 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
857 _Hashtable(const _Hashtable
& __ht
)
858 : __hashtable_base(__ht
),
861 _M_bucket_count(__ht
._M_bucket_count
),
862 _M_bbegin(__ht
._M_bbegin
),
863 _M_element_count(__ht
._M_element_count
),
864 _M_rehash_policy(__ht
._M_rehash_policy
)
866 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
869 if (!__ht
._M_before_begin()._M_nxt
)
872 // First deal with the special first node pointed to by
874 const __node_type
* __ht_n
= __ht
._M_begin();
875 __node_type
* __this_n
= _M_allocate_node(__ht_n
->_M_v
);
876 this->_M_copy_code(__this_n
, __ht_n
);
877 _M_before_begin()._M_nxt
= __this_n
;
878 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin();
880 // Then deal with other nodes.
881 __node_base
* __prev_n
= __this_n
;
882 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
884 __this_n
= _M_allocate_node(__ht_n
->_M_v
);
885 __prev_n
->_M_nxt
= __this_n
;
886 this->_M_copy_code(__this_n
, __ht_n
);
887 size_type __bkt
= _M_bucket_index(__this_n
);
888 if (!_M_buckets
[__bkt
])
889 _M_buckets
[__bkt
] = __prev_n
;
896 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
897 __throw_exception_again
;
901 template<typename _Key
, typename _Value
,
902 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
903 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
905 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
906 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
907 _Hashtable(_Hashtable
&& __ht
)
908 : __hashtable_base(__ht
),
911 _M_buckets(__ht
._M_buckets
),
912 _M_bucket_count(__ht
._M_bucket_count
),
913 _M_bbegin(std::move(__ht
._M_bbegin
)),
914 _M_element_count(__ht
._M_element_count
),
915 _M_rehash_policy(__ht
._M_rehash_policy
)
917 // Update, if necessary, bucket pointing to before begin that hasn't moved.
919 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
920 __ht
._M_rehash_policy
= _RehashPolicy();
921 __ht
._M_bucket_count
= __ht
._M_rehash_policy
._M_next_bkt(0);
922 __ht
._M_buckets
= __ht
._M_allocate_buckets(__ht
._M_bucket_count
);
923 __ht
._M_before_begin()._M_nxt
= nullptr;
924 __ht
._M_element_count
= 0;
927 template<typename _Key
, typename _Value
,
928 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
929 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
931 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
932 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
933 ~_Hashtable() noexcept
936 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
939 template<typename _Key
, typename _Value
,
940 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
941 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
944 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
945 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
946 swap(_Hashtable
& __x
)
948 // The only base class with member variables is hash_code_base.
949 // We define _Hash_code_base::_M_swap because different
950 // specializations have different members.
953 // _GLIBCXX_RESOLVE_LIB_DEFECTS
954 // 431. Swapping containers with unequal allocators.
955 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator(),
956 __x
._M_node_allocator());
958 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
959 std::swap(_M_buckets
, __x
._M_buckets
);
960 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
961 std::swap(_M_before_begin()._M_nxt
, __x
._M_before_begin()._M_nxt
);
962 std::swap(_M_element_count
, __x
._M_element_count
);
964 // Fix buckets containing the _M_before_begin pointers that
967 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin();
969 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
970 = &(__x
._M_before_begin());
973 template<typename _Key
, typename _Value
,
974 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
975 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
978 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
979 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
980 __rehash_policy(const _RehashPolicy
& __pol
)
982 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
983 __n_bkt
= __pol
._M_next_bkt(__n_bkt
);
984 if (__n_bkt
!= _M_bucket_count
)
985 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
986 _M_rehash_policy
= __pol
;
989 template<typename _Key
, typename _Value
,
990 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
991 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
993 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
994 _H1
, _H2
, _Hash
, _RehashPolicy
,
996 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
997 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
998 find(const key_type
& __k
)
1000 __hash_code __code
= this->_M_hash_code(__k
);
1001 std::size_t __n
= _M_bucket_index(__k
, __code
);
1002 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1003 return __p
? iterator(__p
) : this->end();
1006 template<typename _Key
, typename _Value
,
1007 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1008 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1010 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1011 _H1
, _H2
, _Hash
, _RehashPolicy
,
1012 _Traits
>::const_iterator
1013 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1014 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1015 find(const key_type
& __k
) const
1017 __hash_code __code
= this->_M_hash_code(__k
);
1018 std::size_t __n
= _M_bucket_index(__k
, __code
);
1019 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1020 return __p
? const_iterator(__p
) : this->end();
1023 template<typename _Key
, typename _Value
,
1024 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1025 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1027 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1028 _H1
, _H2
, _Hash
, _RehashPolicy
,
1030 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1031 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1032 count(const key_type
& __k
) const
1034 __hash_code __code
= this->_M_hash_code(__k
);
1035 std::size_t __n
= _M_bucket_index(__k
, __code
);
1036 __node_type
* __p
= _M_bucket_begin(__n
);
1040 std::size_t __result
= 0;
1041 for (;; __p
= __p
->_M_next())
1043 if (this->_M_equals(__k
, __code
, __p
))
1046 // All equivalent values are next to each other, if we
1047 // found a non-equivalent value after an equivalent one it
1048 // means that we won't find any more equivalent values.
1050 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1056 template<typename _Key
, typename _Value
,
1057 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1058 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1060 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1061 _ExtractKey
, _Equal
, _H1
,
1062 _H2
, _Hash
, _RehashPolicy
,
1064 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1065 _ExtractKey
, _Equal
, _H1
,
1066 _H2
, _Hash
, _RehashPolicy
,
1068 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1069 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1070 equal_range(const key_type
& __k
)
1072 __hash_code __code
= this->_M_hash_code(__k
);
1073 std::size_t __n
= _M_bucket_index(__k
, __code
);
1074 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1078 __node_type
* __p1
= __p
->_M_next();
1079 while (__p1
&& _M_bucket_index(__p1
) == __n
1080 && this->_M_equals(__k
, __code
, __p1
))
1081 __p1
= __p1
->_M_next();
1083 return std::make_pair(iterator(__p
), iterator(__p1
));
1086 return std::make_pair(this->end(), this->end());
1089 template<typename _Key
, typename _Value
,
1090 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1091 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1093 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1094 _ExtractKey
, _Equal
, _H1
,
1095 _H2
, _Hash
, _RehashPolicy
,
1096 _Traits
>::const_iterator
,
1097 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1098 _ExtractKey
, _Equal
, _H1
,
1099 _H2
, _Hash
, _RehashPolicy
,
1100 _Traits
>::const_iterator
>
1101 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1102 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1103 equal_range(const key_type
& __k
) const
1105 __hash_code __code
= this->_M_hash_code(__k
);
1106 std::size_t __n
= _M_bucket_index(__k
, __code
);
1107 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1111 __node_type
* __p1
= __p
->_M_next();
1112 while (__p1
&& _M_bucket_index(__p1
) == __n
1113 && this->_M_equals(__k
, __code
, __p1
))
1114 __p1
= __p1
->_M_next();
1116 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1119 return std::make_pair(this->end(), this->end());
1122 // Find the node whose key compares equal to k in the bucket n.
1123 // Return nullptr if no node is found.
1124 template<typename _Key
, typename _Value
,
1125 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1126 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1128 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1129 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1130 _Traits
>::__node_base
*
1131 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1132 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1133 _M_find_before_node(size_type __n
, const key_type
& __k
,
1134 __hash_code __code
) const
1136 __node_base
* __prev_p
= _M_buckets
[__n
];
1139 __node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);
1140 for (;; __p
= __p
->_M_next())
1142 if (this->_M_equals(__k
, __code
, __p
))
1144 if (!(__p
->_M_nxt
) || _M_bucket_index(__p
->_M_next()) != __n
)
1151 template<typename _Key
, typename _Value
,
1152 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1153 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1156 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1157 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1158 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1160 if (_M_buckets
[__bkt
])
1162 // Bucket is not empty, we just need to insert the new node
1163 // after the bucket before begin.
1164 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1165 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1169 // The bucket is empty, the new node is inserted at the
1170 // beginning of the singly-linked list and the bucket will
1171 // contain _M_before_begin pointer.
1172 __node
->_M_nxt
= _M_before_begin()._M_nxt
;
1173 _M_before_begin()._M_nxt
= __node
;
1175 // We must update former begin bucket that is pointing to
1177 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1178 _M_buckets
[__bkt
] = &_M_before_begin();
1182 template<typename _Key
, typename _Value
,
1183 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1184 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1187 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1188 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1189 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1190 size_type __next_bkt
)
1192 if (!__next
|| __next_bkt
!= __bkt
)
1194 // Bucket is now empty
1195 // First update next bucket if any
1197 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1199 // Second update before begin node if necessary
1200 if (&_M_before_begin() == _M_buckets
[__bkt
])
1201 _M_before_begin()._M_nxt
= __next
;
1202 _M_buckets
[__bkt
] = nullptr;
1206 template<typename _Key
, typename _Value
,
1207 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1208 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1210 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1211 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1212 _Traits
>::__node_base
*
1213 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1214 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1215 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1217 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1218 while (__prev_n
->_M_nxt
!= __n
)
1219 __prev_n
= __prev_n
->_M_nxt
;
1223 template<typename _Key
, typename _Value
,
1224 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1225 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1227 template<typename
... _Args
>
1228 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1229 _ExtractKey
, _Equal
, _H1
,
1230 _H2
, _Hash
, _RehashPolicy
,
1231 _Traits
>::iterator
, bool>
1232 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1233 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1234 _M_emplace(std::true_type
, _Args
&&... __args
)
1236 // First build the node to get access to the hash code
1237 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1238 const key_type
& __k
= this->_M_extract()(__node
->_M_v
);
1242 __code
= this->_M_hash_code(__k
);
1246 _M_deallocate_node(__node
);
1247 __throw_exception_again
;
1250 size_type __bkt
= _M_bucket_index(__k
, __code
);
1251 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1253 // There is already an equivalent node, no insertion
1254 _M_deallocate_node(__node
);
1255 return std::make_pair(iterator(__p
), false);
1259 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __node
),
1263 template<typename _Key
, typename _Value
,
1264 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1265 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1267 template<typename
... _Args
>
1268 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1269 _H1
, _H2
, _Hash
, _RehashPolicy
,
1271 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1272 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1273 _M_emplace(std::false_type
, _Args
&&... __args
)
1275 // First build the node to get its hash code.
1276 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1281 __code
= this->_M_hash_code(this->_M_extract()(__node
->_M_v
));
1285 _M_deallocate_node(__node
);
1286 __throw_exception_again
;
1289 return _M_insert_multi_node(__code
, __node
);
1292 template<typename _Key
, typename _Value
,
1293 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1294 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1296 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1297 _H1
, _H2
, _Hash
, _RehashPolicy
,
1299 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1300 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1301 _M_insert_unique_node(size_type __bkt
, __hash_code __code
,
1302 __node_type
* __node
)
1304 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1305 std::pair
<bool, std::size_t> __do_rehash
1306 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1310 if (__do_rehash
.first
)
1312 _M_rehash(__do_rehash
.second
, __saved_state
);
1313 __bkt
= _M_bucket_index(this->_M_extract()(__node
->_M_v
), __code
);
1316 this->_M_store_code(__node
, __code
);
1318 // Always insert at the begining of the bucket.
1319 _M_insert_bucket_begin(__bkt
, __node
);
1321 return iterator(__node
);
1325 _M_deallocate_node(__node
);
1326 __throw_exception_again
;
1330 // Insert node, in bucket bkt if no rehash (assumes no element with its key
1331 // already present). Take ownership of the node, deallocate it on exception.
1332 template<typename _Key
, typename _Value
,
1333 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1334 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1336 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1337 _H1
, _H2
, _Hash
, _RehashPolicy
,
1339 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1340 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1341 _M_insert_multi_node(__hash_code __code
, __node_type
* __node
)
1343 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1344 std::pair
<bool, std::size_t> __do_rehash
1345 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
, _M_element_count
, 1);
1349 if (__do_rehash
.first
)
1350 _M_rehash(__do_rehash
.second
, __saved_state
);
1352 this->_M_store_code(__node
, __code
);
1353 const key_type
& __k
= this->_M_extract()(__node
->_M_v
);
1354 size_type __bkt
= _M_bucket_index(__k
, __code
);
1356 // Find the node before an equivalent one.
1357 __node_base
* __prev
= _M_find_before_node(__bkt
, __k
, __code
);
1360 // Insert after the node before the equivalent one.
1361 __node
->_M_nxt
= __prev
->_M_nxt
;
1362 __prev
->_M_nxt
= __node
;
1365 // The inserted node has no equivalent in the
1366 // hashtable. We must insert the new node at the
1367 // beginning of the bucket to preserve equivalent
1368 // elements' relative positions.
1369 _M_insert_bucket_begin(__bkt
, __node
);
1371 return iterator(__node
);
1375 _M_deallocate_node(__node
);
1376 __throw_exception_again
;
1380 // Insert v if no element with its key is already present.
1381 template<typename _Key
, typename _Value
,
1382 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1383 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1385 template<typename _Arg
>
1386 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1387 _ExtractKey
, _Equal
, _H1
,
1388 _H2
, _Hash
, _RehashPolicy
,
1389 _Traits
>::iterator
, bool>
1390 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1391 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1392 _M_insert(_Arg
&& __v
, std::true_type
)
1394 const key_type
& __k
= this->_M_extract()(__v
);
1395 __hash_code __code
= this->_M_hash_code(__k
);
1396 size_type __bkt
= _M_bucket_index(__k
, __code
);
1398 __node_type
* __n
= _M_find_node(__bkt
, __k
, __code
);
1400 return std::make_pair(iterator(__n
), false);
1402 __n
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1403 return std::make_pair(_M_insert_unique_node(__bkt
, __code
, __n
), true);
1406 // Insert v unconditionally.
1407 template<typename _Key
, typename _Value
,
1408 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1409 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1411 template<typename _Arg
>
1412 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1413 _H1
, _H2
, _Hash
, _RehashPolicy
,
1415 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1416 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1417 _M_insert(_Arg
&& __v
, std::false_type
)
1419 // First compute the hash code so that we don't do anything if it
1421 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1423 // Second allocate new node so that we don't rehash if it throws.
1424 __node_type
* __node
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1426 return _M_insert_multi_node(__code
, __node
);
1429 template<typename _Key
, typename _Value
,
1430 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1431 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1433 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1434 _H1
, _H2
, _Hash
, _RehashPolicy
,
1436 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1437 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1438 erase(const_iterator __it
)
1440 __node_type
* __n
= __it
._M_cur
;
1441 std::size_t __bkt
= _M_bucket_index(__n
);
1443 // Look for previous node to unlink it from the erased one, this
1444 // is why we need buckets to contain the before begin to make
1445 // this search fast.
1446 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1447 return _M_erase(__bkt
, __prev_n
, __n
);
1450 template<typename _Key
, typename _Value
,
1451 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1452 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1454 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1455 _H1
, _H2
, _Hash
, _RehashPolicy
,
1457 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1458 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1459 _M_erase(size_type __bkt
, __node_base
* __prev_n
, __node_type
* __n
)
1461 if (__prev_n
== _M_buckets
[__bkt
])
1462 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1463 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1464 else if (__n
->_M_nxt
)
1466 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1467 if (__next_bkt
!= __bkt
)
1468 _M_buckets
[__next_bkt
] = __prev_n
;
1471 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1472 iterator
__result(__n
->_M_next());
1473 _M_deallocate_node(__n
);
1479 template<typename _Key
, typename _Value
,
1480 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1481 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1483 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1484 _H1
, _H2
, _Hash
, _RehashPolicy
,
1486 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1487 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1488 _M_erase(std::true_type
, const key_type
& __k
)
1490 __hash_code __code
= this->_M_hash_code(__k
);
1491 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1493 // Look for the node before the first matching node.
1494 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1498 // We found a matching node, erase it.
1499 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1500 _M_erase(__bkt
, __prev_n
, __n
);
1504 template<typename _Key
, typename _Value
,
1505 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1506 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1508 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1509 _H1
, _H2
, _Hash
, _RehashPolicy
,
1511 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1512 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1513 _M_erase(std::false_type
, const key_type
& __k
)
1515 __hash_code __code
= this->_M_hash_code(__k
);
1516 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1518 // Look for the node before the first matching node.
1519 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1523 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1524 // 526. Is it undefined if a function in the standard changes
1526 // We use one loop to find all matching nodes and another to deallocate
1527 // them so that the key stays valid during the first loop. It might be
1528 // invalidated indirectly when destroying nodes.
1529 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1530 __node_type
* __n_last
= __n
;
1531 std::size_t __n_last_bkt
= __bkt
;
1534 __n_last
= __n_last
->_M_next();
1537 __n_last_bkt
= _M_bucket_index(__n_last
);
1539 while (__n_last_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __n_last
));
1541 // Deallocate nodes.
1542 size_type __result
= 0;
1545 __node_type
* __p
= __n
->_M_next();
1546 _M_deallocate_node(__n
);
1551 while (__n
!= __n_last
);
1553 if (__prev_n
== _M_buckets
[__bkt
])
1554 _M_remove_bucket_begin(__bkt
, __n_last
, __n_last_bkt
);
1555 else if (__n_last
&& __n_last_bkt
!= __bkt
)
1556 _M_buckets
[__n_last_bkt
] = __prev_n
;
1557 __prev_n
->_M_nxt
= __n_last
;
1561 template<typename _Key
, typename _Value
,
1562 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1563 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1565 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1566 _H1
, _H2
, _Hash
, _RehashPolicy
,
1568 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1569 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1570 erase(const_iterator __first
, const_iterator __last
)
1572 __node_type
* __n
= __first
._M_cur
;
1573 __node_type
* __last_n
= __last
._M_cur
;
1574 if (__n
== __last_n
)
1575 return iterator(__n
);
1577 std::size_t __bkt
= _M_bucket_index(__n
);
1579 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1580 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1581 std::size_t __n_bkt
= __bkt
;
1586 __node_type
* __tmp
= __n
;
1587 __n
= __n
->_M_next();
1588 _M_deallocate_node(__tmp
);
1592 __n_bkt
= _M_bucket_index(__n
);
1594 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1595 if (__is_bucket_begin
)
1596 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1597 if (__n
== __last_n
)
1599 __is_bucket_begin
= true;
1603 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
1604 _M_buckets
[__n_bkt
] = __prev_n
;
1605 __prev_n
->_M_nxt
= __n
;
1606 return iterator(__n
);
1609 template<typename _Key
, typename _Value
,
1610 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1611 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1614 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1615 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1618 _M_deallocate_nodes(_M_begin());
1619 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
1620 _M_element_count
= 0;
1621 _M_before_begin()._M_nxt
= nullptr;
1624 template<typename _Key
, typename _Value
,
1625 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1626 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1629 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1630 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1631 rehash(size_type __n
)
1633 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1634 std::size_t __buckets
1635 = std::max(_M_rehash_policy
._M_bkt_for_elements(_M_element_count
+ 1),
1637 __buckets
= _M_rehash_policy
._M_next_bkt(__buckets
);
1639 if (__buckets
!= _M_bucket_count
)
1640 _M_rehash(__buckets
, __saved_state
);
1642 // No rehash, restore previous state to keep a consistent state.
1643 _M_rehash_policy
._M_reset(__saved_state
);
1646 template<typename _Key
, typename _Value
,
1647 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1648 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1651 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1652 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1653 _M_rehash(size_type __n
, const __rehash_state
& __state
)
1657 _M_rehash_aux(__n
, __unique_keys());
1661 // A failure here means that buckets allocation failed. We only
1662 // have to restore hash policy previous state.
1663 _M_rehash_policy
._M_reset(__state
);
1664 __throw_exception_again
;
1668 // Rehash when there is no equivalent elements.
1669 template<typename _Key
, typename _Value
,
1670 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1671 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1674 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1675 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1676 _M_rehash_aux(size_type __n
, std::true_type
)
1678 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
1679 __node_type
* __p
= _M_begin();
1680 _M_before_begin()._M_nxt
= nullptr;
1681 std::size_t __bbegin_bkt
= 0;
1684 __node_type
* __next
= __p
->_M_next();
1685 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1686 if (!__new_buckets
[__bkt
])
1688 __p
->_M_nxt
= _M_before_begin()._M_nxt
;
1689 _M_before_begin()._M_nxt
= __p
;
1690 __new_buckets
[__bkt
] = &_M_before_begin();
1692 __new_buckets
[__bbegin_bkt
] = __p
;
1693 __bbegin_bkt
= __bkt
;
1697 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1698 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1702 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1703 _M_bucket_count
= __n
;
1704 _M_buckets
= __new_buckets
;
1707 // Rehash when there can be equivalent elements, preserve their relative
1709 template<typename _Key
, typename _Value
,
1710 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1711 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1714 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1715 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1716 _M_rehash_aux(size_type __n
, std::false_type
)
1718 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
1720 __node_type
* __p
= _M_begin();
1721 _M_before_begin()._M_nxt
= nullptr;
1722 std::size_t __bbegin_bkt
= 0;
1723 std::size_t __prev_bkt
= 0;
1724 __node_type
* __prev_p
= nullptr;
1725 bool __check_bucket
= false;
1729 __node_type
* __next
= __p
->_M_next();
1730 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1732 if (__prev_p
&& __prev_bkt
== __bkt
)
1734 // Previous insert was already in this bucket, we insert after
1735 // the previously inserted one to preserve equivalent elements
1737 __p
->_M_nxt
= __prev_p
->_M_nxt
;
1738 __prev_p
->_M_nxt
= __p
;
1740 // Inserting after a node in a bucket require to check that we
1741 // haven't change the bucket last node, in this case next
1742 // bucket containing its before begin node must be updated. We
1743 // schedule a check as soon as we move out of the sequence of
1744 // equivalent nodes to limit the number of checks.
1745 __check_bucket
= true;
1751 // Check if we shall update the next bucket because of
1752 // insertions into __prev_bkt bucket.
1753 if (__prev_p
->_M_nxt
)
1755 std::size_t __next_bkt
1756 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
1758 if (__next_bkt
!= __prev_bkt
)
1759 __new_buckets
[__next_bkt
] = __prev_p
;
1761 __check_bucket
= false;
1764 if (!__new_buckets
[__bkt
])
1766 __p
->_M_nxt
= _M_before_begin()._M_nxt
;
1767 _M_before_begin()._M_nxt
= __p
;
1768 __new_buckets
[__bkt
] = &_M_before_begin();
1770 __new_buckets
[__bbegin_bkt
] = __p
;
1771 __bbegin_bkt
= __bkt
;
1775 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1776 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1784 if (__check_bucket
&& __prev_p
->_M_nxt
)
1786 std::size_t __next_bkt
1787 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
1788 if (__next_bkt
!= __prev_bkt
)
1789 __new_buckets
[__next_bkt
] = __prev_p
;
1792 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1793 _M_bucket_count
= __n
;
1794 _M_buckets
= __new_buckets
;
1797 _GLIBCXX_END_NAMESPACE_VERSION
1800 #endif // _HASHTABLE_H