1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 /** @file bits/hashtable.h
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
32 #define _HASHTABLE_H 1
34 #pragma GCC system_header
36 #include <bits/hashtable_policy.h>
38 namespace std
_GLIBCXX_VISIBILITY(default)
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42 template<typename _Tp
, typename _Hash
>
43 using __cache_default
= __not_
<__and_
<is_integral
<_Tp
>,
45 integral_constant
<bool, !__is_final(_Hash
)>,
46 __detail::__is_noexcept_hash
<_Tp
, _Hash
> >>;
49 * Primary class template _Hashtable.
51 * @ingroup hashtable-detail
53 * @tparam _Value CopyConstructible type.
55 * @tparam _Key CopyConstructible type.
57 * @tparam _Alloc An allocator type
58 * ([lib.allocator.requirements]) whose _Alloc::value_type is
59 * _Value. As a conforming extension, we allow for
60 * _Alloc::value_type != _Value.
62 * @tparam _ExtractKey Function object that takes an object of type
63 * _Value and returns a value of type _Key.
65 * @tparam _Equal Function object that takes two objects of type k
66 * and returns a bool-like value that is true if the two objects
67 * are considered equal.
69 * @tparam _H1 The hash function. A unary function object with
70 * argument type _Key and result type size_t. Return values should
71 * be distributed over the entire range [0, numeric_limits<size_t>:::max()].
73 * @tparam _H2 The range-hashing function (in the terminology of
74 * Tavori and Dreizin). A binary function object whose argument
75 * types and result type are all size_t. Given arguments r and N,
76 * the return value is in the range [0, N).
78 * @tparam _Hash The ranged hash function (Tavori and Dreizin). A
79 * binary function whose argument types are _Key and size_t and
80 * whose result type is size_t. Given arguments k and N, the
81 * return value is in the range [0, N). Default: hash(k, N) =
82 * h2(h1(k), N). If _Hash is anything other than the default, _H1
83 * and _H2 are ignored.
85 * @tparam _RehashPolicy Policy class with three members, all of
86 * which govern the bucket count. _M_next_bkt(n) returns a bucket
87 * count no smaller than n. _M_bkt_for_elements(n) returns a
88 * bucket count appropriate for an element count of n.
89 * _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
90 * current bucket count is n_bkt and the current element count is
91 * n_elt, we need to increase the bucket count. If so, returns
92 * make_pair(true, n), where n is the new bucket count. If not,
93 * returns make_pair(false, <anything>)
95 * @tparam _Traits Compile-time class with three boolean
96 * std::integral_constant members: __cache_hash_code, __constant_iterators,
99 * Each _Hashtable data structure has:
101 * - _Bucket[] _M_buckets
102 * - _Hash_node_base _M_before_begin
103 * - size_type _M_bucket_count
104 * - size_type _M_element_count
106 * with _Bucket being _Hash_node* and _Hash_node constaining:
108 * - _Hash_node* _M_next
110 * - size_t _M_code if cache_hash_code is true
112 * In terms of Standard containers the hastable is like the aggregation of:
114 * - std::forward_list<_Node> containing the elements
115 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
117 * The non-empty buckets contain the node before the first bucket
118 * node. This design allow to implement something like a
119 * std::forward_list::insert_after on container insertion and
120 * std::forward_list::erase_after on container erase
121 * calls. _M_before_begin is equivalent to
122 * std::foward_list::before_begin. Empty buckets are containing
123 * nullptr. Note that one of the non-empty bucket contains
124 * &_M_before_begin which is not a derefenrenceable node so the
125 * node pointers in buckets shall never be derefenrenced, only its
128 * Walk through a bucket nodes require a check on the hash code to
129 * see if the node is still in the bucket. Such a design impose a
130 * quite efficient hash functor and is one of the reasons it is
131 * highly advise to set __cache_hash_code to true.
133 * The container iterators are simply built from nodes. This way
134 * incrementing the iterator is perfectly efficient independent of
135 * how many empty buckets there are in the container.
137 * On insert we compute element hash code and thanks to it find the
138 * bucket index. If the element must be inserted on an empty bucket
139 * we add it at the beginning of the singly linked list and make the
140 * bucket point to _M_before_begin. The bucket that used to point to
141 * _M_before_begin, if any, is updated to point to its new before
144 * On erase, the simple iterator design impose to use the hash
145 * functor to get the index of the bucket to update. For this
146 * reason, when __cache_hash_code is set to false, there is a static
147 * assertion that the hash functor cannot throw.
149 * Functionality is implemented by decomposition into base classes,
150 * where the derived _Hashtable class is used in _Map_base,
151 * _Insert, _Rehash_base, and _Equality base classes to access the
152 * "this" pointer. _Hashtable_base is used in the base classes as a
153 * non-recursive, fully-completed-type so that detailed nested type
154 * information, such as iterator type and node type, can be
155 * used. This is similar to the "Curiously Recurring Template
156 * Pattern" (CRTP) technique, but uses a reconstructed, not
157 * explicitly passed, template pattern.
159 * Base class templates are:
160 * - __detail::_Hashtable_base
161 * - __detail::_Map_base
162 * - __detail::_Insert
163 * - __detail::_Rehash_base
164 * - __detail::_Equality
166 template<typename _Key
, typename _Value
, typename _Alloc
,
167 typename _ExtractKey
, typename _Equal
,
168 typename _H1
, typename _H2
, typename _Hash
,
169 typename _RehashPolicy
, typename _Traits
>
171 : public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
172 _H1
, _H2
, _Hash
, _Traits
>,
173 public __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
174 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
175 public __detail::_Insert
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
176 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
177 public __detail::_Rehash_base
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
178 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>,
179 public __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
180 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>
183 typedef _Key key_type
;
184 typedef _Value value_type
;
185 typedef _Alloc allocator_type
;
186 typedef _Equal key_equal
;
188 // mapped_type, if present, comes from _Map_base.
189 // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
190 typedef typename
_Alloc::pointer pointer
;
191 typedef typename
_Alloc::const_pointer const_pointer
;
192 typedef typename
_Alloc::reference reference
;
193 typedef typename
_Alloc::const_reference const_reference
;
196 using __rehash_type
= _RehashPolicy
;
197 using __rehash_state
= typename
__rehash_type::_State
;
199 using __traits_type
= _Traits
;
200 using __hash_cached
= typename
__traits_type::__hash_cached
;
201 using __constant_iterators
= typename
__traits_type::__constant_iterators
;
202 using __unique_keys
= typename
__traits_type::__unique_keys
;
204 using __key_extract
= typename
std::conditional
<
205 __constant_iterators::value
,
206 std::_Identity
<value_type
>,
207 std::_Select1st
<value_type
>>::type
;
209 using __hashtable_base
= __detail::
210 _Hashtable_base
<_Key
, _Value
, _ExtractKey
,
211 _Equal
, _H1
, _H2
, _Hash
, _Traits
>;
213 using __hash_code_base
= typename
__hashtable_base::__hash_code_base
;
214 using __hash_code
= typename
__hashtable_base::__hash_code
;
215 using __node_type
= typename
__hashtable_base::__node_type
;
216 using __node_base
= typename
__hashtable_base::__node_base
;
217 using __bucket_type
= typename
__hashtable_base::__bucket_type
;
218 using __ireturn_type
= typename
__hashtable_base::__ireturn_type
;
219 using __iconv_type
= typename
__hashtable_base::__iconv_type
;
221 using __map_base
= __detail::_Map_base
<_Key
, _Value
, _Alloc
, _ExtractKey
,
222 _Equal
, _H1
, _H2
, _Hash
,
223 _RehashPolicy
, _Traits
>;
225 using __rehash_base
= __detail::_Rehash_base
<_Key
, _Value
, _Alloc
,
228 _RehashPolicy
, _Traits
>;
230 using __eq_base
= __detail::_Equality
<_Key
, _Value
, _Alloc
, _ExtractKey
,
231 _Equal
, _H1
, _H2
, _Hash
,
232 _RehashPolicy
, _Traits
>;
234 // Metaprogramming for picking apart hash caching.
235 using __hash_noexcept
= __detail::__is_noexcept_hash
<_Key
, _H1
>;
237 template<typename _Cond
>
238 using __if_hash_cached
= __or_
<__not_
<__hash_cached
>, _Cond
>;
240 template<typename _Cond
>
241 using __if_hash_not_cached
= __or_
<__hash_cached
, _Cond
>;
243 // Compile-time diagnostics.
245 // When hash codes are not cached the hash functor shall not
246 // throw because it is used in methods (erase, swap...) that
248 static_assert(__if_hash_not_cached
<__hash_noexcept
>::value
,
249 "Cache the hash code"
250 " or qualify your hash functor with noexcept");
252 // Following two static assertions are necessary to guarantee
253 // that swapping two hashtable instances won't invalidate
254 // associated local iterators.
256 // When hash codes are cached local iterator only uses H2 which
257 // must then be empty.
258 static_assert(__if_hash_cached
<is_empty
<_H2
>>::value
,
259 "Functor used to map hash code to bucket index"
262 // When hash codes are not cached local iterator is going to use
263 // __hash_code_base above to compute node bucket index so it has
265 static_assert(__if_hash_not_cached
<is_empty
<__hash_code_base
>>::value
,
266 "Cache the hash code or make functors involved in hash code"
267 " and bucket index computation empty");
270 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
271 typename _ExtractKeya
, typename _Equala
,
272 typename _H1a
, typename _H2a
, typename _Hasha
,
273 typename _RehashPolicya
, typename _Traitsa
,
275 friend struct __detail::_Map_base
;
277 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
278 typename _ExtractKeya
, typename _Equala
,
279 typename _H1a
, typename _H2a
, typename _Hasha
,
280 typename _RehashPolicya
, typename _Traitsa
>
281 friend struct __detail::_Insert_base
;
283 template<typename _Keya
, typename _Valuea
, typename _Alloca
,
284 typename _ExtractKeya
, typename _Equala
,
285 typename _H1a
, typename _H2a
, typename _Hasha
,
286 typename _RehashPolicya
, typename _Traitsa
,
287 bool _Constant_iteratorsa
, bool _Unique_keysa
>
288 friend struct __detail::_Insert
;
290 using size_type
= typename
__hashtable_base::size_type
;
291 using difference_type
= typename
__hashtable_base::difference_type
;
293 using iterator
= typename
__hashtable_base::iterator
;
294 using const_iterator
= typename
__hashtable_base::const_iterator
;
296 using local_iterator
= typename
__hashtable_base::local_iterator
;
297 using const_local_iterator
= typename
__hashtable_base::
298 const_local_iterator
;
301 typedef typename
_Alloc::template rebind
<__node_type
>::other
302 _Node_allocator_type
;
303 typedef typename
_Alloc::template rebind
<__bucket_type
>::other
304 _Bucket_allocator_type
;
305 typedef typename
_Alloc::template rebind
<value_type
>::other
306 _Value_allocator_type
;
309 _Node_allocator_type _M_node_allocator
;
310 __bucket_type
* _M_buckets
;
311 size_type _M_bucket_count
;
312 __node_base _M_before_begin
;
313 size_type _M_element_count
;
314 _RehashPolicy _M_rehash_policy
;
316 template<typename
... _Args
>
318 _M_allocate_node(_Args
&&... __args
);
321 _M_deallocate_node(__node_type
* __n
);
323 // Deallocate the linked list of nodes pointed to by __n
325 _M_deallocate_nodes(__node_type
* __n
);
328 _M_allocate_buckets(size_type __n
);
331 _M_deallocate_buckets(__bucket_type
*, size_type __n
);
333 // Gets bucket begin, deals with the fact that non-empty buckets contain
334 // their before begin node.
336 _M_bucket_begin(size_type __bkt
) const;
340 { return static_cast<__node_type
*>(_M_before_begin
._M_nxt
); }
343 // Constructor, destructor, assignment, swap
344 _Hashtable(size_type __bucket_hint
,
345 const _H1
&, const _H2
&, const _Hash
&,
346 const _Equal
&, const _ExtractKey
&,
347 const allocator_type
&);
349 template<typename _InputIterator
>
350 _Hashtable(_InputIterator __first
, _InputIterator __last
,
351 size_type __bucket_hint
,
352 const _H1
&, const _H2
&, const _Hash
&,
353 const _Equal
&, const _ExtractKey
&,
354 const allocator_type
&);
356 _Hashtable(const _Hashtable
&);
358 _Hashtable(_Hashtable
&&);
360 // Use delegating construtors.
362 _Hashtable(size_type __n
= 10,
363 const _H1
& __hf
= _H1(),
364 const key_equal
& __eql
= key_equal(),
365 const allocator_type
& __a
= allocator_type())
366 : _Hashtable(__n
, __hf
, __detail::_Mod_range_hashing(),
367 __detail::_Default_ranged_hash(), __eql
,
368 __key_extract(), __a
)
371 template<typename _InputIterator
>
372 _Hashtable(_InputIterator __f
, _InputIterator __l
,
374 const _H1
& __hf
= _H1(),
375 const key_equal
& __eql
= key_equal(),
376 const allocator_type
& __a
= allocator_type())
377 : _Hashtable(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
378 __detail::_Default_ranged_hash(), __eql
,
379 __key_extract(), __a
)
382 _Hashtable(initializer_list
<value_type
> __l
,
384 const _H1
& __hf
= _H1(),
385 const key_equal
& __eql
= key_equal(),
386 const allocator_type
& __a
= allocator_type())
387 : _Hashtable(__l
.begin(), __l
.end(), __n
, __hf
,
388 __detail::_Mod_range_hashing(),
389 __detail::_Default_ranged_hash(), __eql
,
390 __key_extract(), __a
)
394 operator=(const _Hashtable
& __ht
)
396 _Hashtable
__tmp(__ht
);
402 operator=(_Hashtable
&& __ht
)
412 operator=(initializer_list
<value_type
> __l
)
415 this->insert(__l
.begin(), __l
.end());
419 ~_Hashtable() noexcept
;
421 void swap(_Hashtable
&);
423 // Basic container operations
426 { return iterator(_M_begin()); }
429 begin() const noexcept
430 { return const_iterator(_M_begin()); }
434 { return iterator(nullptr); }
438 { return const_iterator(nullptr); }
441 cbegin() const noexcept
442 { return const_iterator(_M_begin()); }
445 cend() const noexcept
446 { return const_iterator(nullptr); }
449 size() const noexcept
450 { return _M_element_count
; }
453 empty() const noexcept
454 { return size() == 0; }
457 get_allocator() const noexcept
458 { return allocator_type(_M_node_allocator
); }
461 max_size() const noexcept
462 { return _M_node_allocator
.max_size(); }
467 { return this->_M_eq(); }
469 // hash_function, if present, comes from _Hash_code_base.
473 bucket_count() const noexcept
474 { return _M_bucket_count
; }
477 max_bucket_count() const noexcept
478 { return max_size(); }
481 bucket_size(size_type __n
) const
482 { return std::distance(begin(__n
), end(__n
)); }
485 bucket(const key_type
& __k
) const
486 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
490 { return local_iterator(_M_bucket_begin(__n
), __n
, _M_bucket_count
); }
494 { return local_iterator(nullptr, __n
, _M_bucket_count
); }
497 begin(size_type __n
) const
498 { return const_local_iterator(_M_bucket_begin(__n
), __n
,
502 end(size_type __n
) const
503 { return const_local_iterator(nullptr, __n
, _M_bucket_count
); }
507 cbegin(size_type __n
) const
508 { return const_local_iterator(_M_bucket_begin(__n
), __n
,
512 cend(size_type __n
) const
513 { return const_local_iterator(nullptr, __n
, _M_bucket_count
); }
516 load_factor() const noexcept
518 return static_cast<float>(size()) / static_cast<float>(bucket_count());
521 // max_load_factor, if present, comes from _Rehash_base.
523 // Generalization of max_load_factor. Extension, not found in
524 // TR1. Only useful if _RehashPolicy is something other than
527 __rehash_policy() const
528 { return _M_rehash_policy
; }
531 __rehash_policy(const _RehashPolicy
&);
535 find(const key_type
& __k
);
538 find(const key_type
& __k
) const;
541 count(const key_type
& __k
) const;
543 std::pair
<iterator
, iterator
>
544 equal_range(const key_type
& __k
);
546 std::pair
<const_iterator
, const_iterator
>
547 equal_range(const key_type
& __k
) const;
550 // Bucket index computation helpers.
552 _M_bucket_index(__node_type
* __n
) const
553 { return __hash_code_base::_M_bucket_index(__n
, _M_bucket_count
); }
556 _M_bucket_index(const key_type
& __k
, __hash_code __c
) const
557 { return __hash_code_base::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
559 // Find and insert helper functions and types
560 // Find the node before the one matching the criteria.
562 _M_find_before_node(size_type
, const key_type
&, __hash_code
) const;
565 _M_find_node(size_type __bkt
, const key_type
& __key
,
566 __hash_code __c
) const
568 __node_base
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
570 return static_cast<__node_type
*>(__before_n
->_M_nxt
);
574 // Insert a node at the beginning of a bucket.
576 _M_insert_bucket_begin(size_type
, __node_type
*);
578 // Remove the bucket first node
580 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next_n
,
581 size_type __next_bkt
);
583 // Get the node before __n in the bucket __bkt
585 _M_get_previous_node(size_type __bkt
, __node_base
* __n
);
587 template<typename _Arg
>
589 _M_insert_bucket(_Arg
&&, size_type
, __hash_code
);
592 template<typename
... _Args
>
593 std::pair
<iterator
, bool>
594 _M_emplace(std::true_type
, _Args
&&... __args
);
596 template<typename
... _Args
>
598 _M_emplace(std::false_type
, _Args
&&... __args
);
600 template<typename _Arg
>
601 std::pair
<iterator
, bool>
602 _M_insert(_Arg
&&, std::true_type
);
604 template<typename _Arg
>
606 _M_insert(_Arg
&&, std::false_type
);
610 template<typename
... _Args
>
612 emplace(_Args
&&... __args
)
613 { return _M_emplace(__unique_keys(), std::forward
<_Args
>(__args
)...); }
615 template<typename
... _Args
>
617 emplace_hint(const_iterator
, _Args
&&... __args
)
618 { return __iconv_type()(emplace(std::forward
<_Args
>(__args
)...)); }
620 // Insert member functions via inheritance.
624 erase(const_iterator
);
629 { return erase(const_iterator(__it
)); }
632 erase(const key_type
&);
635 erase(const_iterator
, const_iterator
);
640 // Set number of buckets to be appropriate for container of n element.
641 void rehash(size_type __n
);
644 // reserve, if present, comes from _Rehash_base.
647 // Helper rehash method used when keys are unique.
648 void _M_rehash_aux(size_type __n
, std::true_type
);
650 // Helper rehash method used when keys can be non-unique.
651 void _M_rehash_aux(size_type __n
, std::false_type
);
653 // Unconditionally change size of bucket array to n, restore
654 // hash policy state to __state on exception.
655 void _M_rehash(size_type __n
, const __rehash_state
& __state
);
659 // Definitions of class template _Hashtable's out-of-line member functions.
660 template<typename _Key
, typename _Value
,
661 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
662 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
664 template<typename
... _Args
>
665 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
666 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__node_type
*
667 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
668 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
669 _M_allocate_node(_Args
&&... __args
)
671 __node_type
* __n
= _M_node_allocator
.allocate(1);
674 _M_node_allocator
.construct(__n
, std::forward
<_Args
>(__args
)...);
679 _M_node_allocator
.deallocate(__n
, 1);
680 __throw_exception_again
;
684 template<typename _Key
, typename _Value
,
685 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
686 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
689 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
690 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
691 _M_deallocate_node(__node_type
* __n
)
693 _M_node_allocator
.destroy(__n
);
694 _M_node_allocator
.deallocate(__n
, 1);
697 template<typename _Key
, typename _Value
,
698 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
699 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
702 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
703 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
704 _M_deallocate_nodes(__node_type
* __n
)
708 __node_type
* __tmp
= __n
;
709 __n
= __n
->_M_next();
710 _M_deallocate_node(__tmp
);
714 template<typename _Key
, typename _Value
,
715 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
716 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
718 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
719 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::__bucket_type
*
720 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
721 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
722 _M_allocate_buckets(size_type __n
)
724 _Bucket_allocator_type
__alloc(_M_node_allocator
);
726 __bucket_type
* __p
= __alloc
.allocate(__n
);
727 __builtin_memset(__p
, 0, __n
* sizeof(__bucket_type
));
731 template<typename _Key
, typename _Value
,
732 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
733 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
736 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
737 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
738 _M_deallocate_buckets(__bucket_type
* __p
, size_type __n
)
740 _Bucket_allocator_type
__alloc(_M_node_allocator
);
741 __alloc
.deallocate(__p
, __n
);
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
,
749 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
750 _Traits
>::__node_type
*
751 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
752 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
753 _M_bucket_begin(size_type __bkt
) const
755 __node_base
* __n
= _M_buckets
[__bkt
];
756 return __n
? static_cast<__node_type
*>(__n
->_M_nxt
) : nullptr;
759 template<typename _Key
, typename _Value
,
760 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
761 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
763 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
764 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
765 _Hashtable(size_type __bucket_hint
,
766 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
767 const _Equal
& __eq
, const _ExtractKey
& __exk
,
768 const allocator_type
& __a
)
769 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
772 _M_node_allocator(__a
),
777 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
779 // We don't want the rehash policy to ask for the hashtable to
780 // shrink on the first insertion so we need to reset its
781 // previous resize level.
782 _M_rehash_policy
._M_prev_resize
= 0;
783 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
786 template<typename _Key
, typename _Value
,
787 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
788 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
790 template<typename _InputIterator
>
791 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
792 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
793 _Hashtable(_InputIterator __f
, _InputIterator __l
,
794 size_type __bucket_hint
,
795 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
796 const _Equal
& __eq
, const _ExtractKey
& __exk
,
797 const allocator_type
& __a
)
798 : __hashtable_base(__exk
, __h1
, __h2
, __h
, __eq
),
801 _M_node_allocator(__a
),
806 _M_bucket_count
= std::max(_M_rehash_policy
._M_next_bkt(__bucket_hint
),
808 _M_bkt_for_elements(__detail::
812 // We don't want the rehash policy to ask for the hashtable to
813 // shrink on the first insertion so we need to reset its
814 // previous resize level.
815 _M_rehash_policy
._M_prev_resize
= 0;
816 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
819 for (; __f
!= __l
; ++__f
)
825 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
826 __throw_exception_again
;
830 template<typename _Key
, typename _Value
,
831 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
832 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
834 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
835 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
836 _Hashtable(const _Hashtable
& __ht
)
837 : __hashtable_base(__ht
),
840 _M_node_allocator(__ht
._M_node_allocator
),
841 _M_bucket_count(__ht
._M_bucket_count
),
842 _M_element_count(__ht
._M_element_count
),
843 _M_rehash_policy(__ht
._M_rehash_policy
)
845 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
848 if (!__ht
._M_before_begin
._M_nxt
)
851 // First deal with the special first node pointed to by
853 const __node_type
* __ht_n
= __ht
._M_begin();
854 __node_type
* __this_n
= _M_allocate_node(__ht_n
->_M_v
);
855 this->_M_copy_code(__this_n
, __ht_n
);
856 _M_before_begin
._M_nxt
= __this_n
;
857 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin
;
859 // Then deal with other nodes.
860 __node_base
* __prev_n
= __this_n
;
861 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
863 __this_n
= _M_allocate_node(__ht_n
->_M_v
);
864 __prev_n
->_M_nxt
= __this_n
;
865 this->_M_copy_code(__this_n
, __ht_n
);
866 size_type __bkt
= _M_bucket_index(__this_n
);
867 if (!_M_buckets
[__bkt
])
868 _M_buckets
[__bkt
] = __prev_n
;
875 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
876 __throw_exception_again
;
880 template<typename _Key
, typename _Value
,
881 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
882 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
884 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
885 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
886 _Hashtable(_Hashtable
&& __ht
)
887 : __hashtable_base(__ht
),
890 _M_node_allocator(std::move(__ht
._M_node_allocator
)),
891 _M_buckets(__ht
._M_buckets
),
892 _M_bucket_count(__ht
._M_bucket_count
),
893 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
894 _M_element_count(__ht
._M_element_count
),
895 _M_rehash_policy(__ht
._M_rehash_policy
)
897 // Update, if necessary, bucket pointing to before begin that hasn't move.
899 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
900 __ht
._M_rehash_policy
= _RehashPolicy();
901 __ht
._M_bucket_count
= __ht
._M_rehash_policy
._M_next_bkt(0);
902 __ht
._M_buckets
= __ht
._M_allocate_buckets(__ht
._M_bucket_count
);
903 __ht
._M_before_begin
._M_nxt
= nullptr;
904 __ht
._M_element_count
= 0;
907 template<typename _Key
, typename _Value
,
908 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
909 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
911 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
912 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
913 ~_Hashtable() noexcept
916 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
919 template<typename _Key
, typename _Value
,
920 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
921 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
924 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
925 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
926 swap(_Hashtable
& __x
)
928 // The only base class with member variables is hash_code_base.
929 // We define _Hash_code_base::_M_swap because different
930 // specializations have different members.
933 // _GLIBCXX_RESOLVE_LIB_DEFECTS
934 // 431. Swapping containers with unequal allocators.
935 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator
,
936 __x
._M_node_allocator
);
938 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
939 std::swap(_M_buckets
, __x
._M_buckets
);
940 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
941 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
942 std::swap(_M_element_count
, __x
._M_element_count
);
944 // Fix buckets containing the _M_before_begin pointers that
947 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
949 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
950 = &(__x
._M_before_begin
);
953 template<typename _Key
, typename _Value
,
954 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
955 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
958 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
959 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
960 __rehash_policy(const _RehashPolicy
& __pol
)
962 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
963 if (__n_bkt
!= _M_bucket_count
)
964 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
965 _M_rehash_policy
= __pol
;
968 template<typename _Key
, typename _Value
,
969 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
970 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
972 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
973 _H1
, _H2
, _Hash
, _RehashPolicy
,
975 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
976 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
977 find(const key_type
& __k
)
979 __hash_code __code
= this->_M_hash_code(__k
);
980 std::size_t __n
= _M_bucket_index(__k
, __code
);
981 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
982 return __p
? iterator(__p
) : this->end();
985 template<typename _Key
, typename _Value
,
986 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
987 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
989 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
990 _H1
, _H2
, _Hash
, _RehashPolicy
,
991 _Traits
>::const_iterator
992 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
993 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
994 find(const key_type
& __k
) const
996 __hash_code __code
= this->_M_hash_code(__k
);
997 std::size_t __n
= _M_bucket_index(__k
, __code
);
998 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
999 return __p
? const_iterator(__p
) : this->end();
1002 template<typename _Key
, typename _Value
,
1003 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1004 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1006 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1007 _H1
, _H2
, _Hash
, _RehashPolicy
,
1009 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1010 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1011 count(const key_type
& __k
) const
1013 __hash_code __code
= this->_M_hash_code(__k
);
1014 std::size_t __n
= _M_bucket_index(__k
, __code
);
1015 __node_type
* __p
= _M_bucket_begin(__n
);
1019 std::size_t __result
= 0;
1020 for (;; __p
= __p
->_M_next())
1022 if (this->_M_equals(__k
, __code
, __p
))
1025 // All equivalent values are next to each other, if we
1026 // found a not equivalent value after an equivalent one it
1027 // means that we won't find anymore an equivalent value.
1029 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
1035 template<typename _Key
, typename _Value
,
1036 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1037 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1039 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1040 _ExtractKey
, _Equal
, _H1
,
1041 _H2
, _Hash
, _RehashPolicy
,
1043 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1044 _ExtractKey
, _Equal
, _H1
,
1045 _H2
, _Hash
, _RehashPolicy
,
1047 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1048 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1049 equal_range(const key_type
& __k
)
1051 __hash_code __code
= this->_M_hash_code(__k
);
1052 std::size_t __n
= _M_bucket_index(__k
, __code
);
1053 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1057 __node_type
* __p1
= __p
->_M_next();
1058 while (__p1
&& _M_bucket_index(__p1
) == __n
1059 && this->_M_equals(__k
, __code
, __p1
))
1060 __p1
= __p1
->_M_next();
1062 return std::make_pair(iterator(__p
), iterator(__p1
));
1065 return std::make_pair(this->end(), this->end());
1068 template<typename _Key
, typename _Value
,
1069 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1070 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1072 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1073 _ExtractKey
, _Equal
, _H1
,
1074 _H2
, _Hash
, _RehashPolicy
,
1075 _Traits
>::const_iterator
,
1076 typename _Hashtable
<_Key
, _Value
, _Alloc
,
1077 _ExtractKey
, _Equal
, _H1
,
1078 _H2
, _Hash
, _RehashPolicy
,
1079 _Traits
>::const_iterator
>
1080 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1081 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1082 equal_range(const key_type
& __k
) const
1084 __hash_code __code
= this->_M_hash_code(__k
);
1085 std::size_t __n
= _M_bucket_index(__k
, __code
);
1086 __node_type
* __p
= _M_find_node(__n
, __k
, __code
);
1090 __node_type
* __p1
= __p
->_M_next();
1091 while (__p1
&& _M_bucket_index(__p1
) == __n
1092 && this->_M_equals(__k
, __code
, __p1
))
1093 __p1
= __p1
->_M_next();
1095 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1098 return std::make_pair(this->end(), this->end());
1101 // Find the node whose key compares equal to k in the bucket n.
1102 // Return nullptr if no node is found.
1103 template<typename _Key
, typename _Value
,
1104 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1105 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1107 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1108 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1109 _Traits
>::__node_base
*
1110 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1111 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1112 _M_find_before_node(size_type __n
, const key_type
& __k
,
1113 __hash_code __code
) const
1115 __node_base
* __prev_p
= _M_buckets
[__n
];
1118 __node_type
* __p
= static_cast<__node_type
*>(__prev_p
->_M_nxt
);
1119 for (;; __p
= __p
->_M_next())
1121 if (this->_M_equals(__k
, __code
, __p
))
1123 if (!(__p
->_M_nxt
) || _M_bucket_index(__p
->_M_next()) != __n
)
1130 template<typename _Key
, typename _Value
,
1131 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1132 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1135 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1136 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1137 _M_insert_bucket_begin(size_type __bkt
, __node_type
* __node
)
1139 if (_M_buckets
[__bkt
])
1141 // Bucket is not empty, we just need to insert the new node
1142 // after the bucket before begin.
1143 __node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1144 _M_buckets
[__bkt
]->_M_nxt
= __node
;
1148 // The bucket is empty, the new node is inserted at the
1149 // beginning of the singly linked list and the bucket will
1150 // contain _M_before_begin pointer.
1151 __node
->_M_nxt
= _M_before_begin
._M_nxt
;
1152 _M_before_begin
._M_nxt
= __node
;
1154 // We must update former begin bucket that is pointing to
1156 _M_buckets
[_M_bucket_index(__node
->_M_next())] = __node
;
1157 _M_buckets
[__bkt
] = &_M_before_begin
;
1161 template<typename _Key
, typename _Value
,
1162 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1163 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1166 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1167 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1168 _M_remove_bucket_begin(size_type __bkt
, __node_type
* __next
,
1169 size_type __next_bkt
)
1171 if (!__next
|| __next_bkt
!= __bkt
)
1173 // Bucket is now empty
1174 // First update next bucket if any
1176 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1178 // Second update before begin node if necessary
1179 if (&_M_before_begin
== _M_buckets
[__bkt
])
1180 _M_before_begin
._M_nxt
= __next
;
1181 _M_buckets
[__bkt
] = nullptr;
1185 template<typename _Key
, typename _Value
,
1186 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1187 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1189 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
,
1190 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1191 _Traits
>::__node_base
*
1192 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1193 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1194 _M_get_previous_node(size_type __bkt
, __node_base
* __n
)
1196 __node_base
* __prev_n
= _M_buckets
[__bkt
];
1197 while (__prev_n
->_M_nxt
!= __n
)
1198 __prev_n
= __prev_n
->_M_nxt
;
1202 template<typename _Key
, typename _Value
,
1203 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1204 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1206 template<typename
... _Args
>
1207 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1208 _ExtractKey
, _Equal
, _H1
,
1209 _H2
, _Hash
, _RehashPolicy
,
1210 _Traits
>::iterator
, bool>
1211 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1212 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1213 _M_emplace(std::true_type
, _Args
&&... __args
)
1215 // First build the node to get access to the hash code
1216 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1219 const key_type
& __k
= this->_M_extract()(__node
->_M_v
);
1220 __hash_code __code
= this->_M_hash_code(__k
);
1221 size_type __bkt
= _M_bucket_index(__k
, __code
);
1223 if (__node_type
* __p
= _M_find_node(__bkt
, __k
, __code
))
1225 // There is already an equivalent node, no insertion
1226 _M_deallocate_node(__node
);
1227 return std::make_pair(iterator(__p
), false);
1230 // We are going to insert this node
1231 this->_M_store_code(__node
, __code
);
1232 const __rehash_state
& __saved_state
1233 = _M_rehash_policy
._M_state();
1234 std::pair
<bool, std::size_t> __do_rehash
1235 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1236 _M_element_count
, 1);
1238 if (__do_rehash
.first
)
1240 _M_rehash(__do_rehash
.second
, __saved_state
);
1241 __bkt
= _M_bucket_index(__k
, __code
);
1244 _M_insert_bucket_begin(__bkt
, __node
);
1246 return std::make_pair(iterator(__node
), true);
1250 _M_deallocate_node(__node
);
1251 __throw_exception_again
;
1255 template<typename _Key
, typename _Value
,
1256 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1257 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1259 template<typename
... _Args
>
1260 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1261 _H1
, _H2
, _Hash
, _RehashPolicy
,
1263 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1264 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1265 _M_emplace(std::false_type
, _Args
&&... __args
)
1267 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1268 std::pair
<bool, std::size_t> __do_rehash
1269 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1270 _M_element_count
, 1);
1272 // First build the node to get its hash code.
1273 __node_type
* __node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1276 const key_type
& __k
= this->_M_extract()(__node
->_M_v
);
1277 __hash_code __code
= this->_M_hash_code(__k
);
1278 this->_M_store_code(__node
, __code
);
1280 // Second, do rehash if necessary.
1281 if (__do_rehash
.first
)
1282 _M_rehash(__do_rehash
.second
, __saved_state
);
1284 // Third, find the node before an equivalent one.
1285 size_type __bkt
= _M_bucket_index(__k
, __code
);
1286 __node_base
* __prev
= _M_find_before_node(__bkt
, __k
, __code
);
1290 // Insert after the node before the equivalent one.
1291 __node
->_M_nxt
= __prev
->_M_nxt
;
1292 __prev
->_M_nxt
= __node
;
1295 // The inserted node has no equivalent in the
1296 // hashtable. We must insert the new node at the
1297 // beginning of the bucket to preserve equivalent
1298 // elements relative positions.
1299 _M_insert_bucket_begin(__bkt
, __node
);
1301 return iterator(__node
);
1305 _M_deallocate_node(__node
);
1306 __throw_exception_again
;
1310 // Insert v in bucket n (assumes no element with its key already present).
1311 template<typename _Key
, typename _Value
,
1312 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1313 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1315 template<typename _Arg
>
1316 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1317 _H1
, _H2
, _Hash
, _RehashPolicy
,
1319 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1320 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1321 _M_insert_bucket(_Arg
&& __v
, size_type __n
, __hash_code __code
)
1323 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1324 std::pair
<bool, std::size_t> __do_rehash
1325 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1326 _M_element_count
, 1);
1328 if (__do_rehash
.first
)
1330 const key_type
& __k
= this->_M_extract()(__v
);
1331 __n
= __hash_code_base::_M_bucket_index(__k
, __code
,
1332 __do_rehash
.second
);
1335 __node_type
* __node
= nullptr;
1338 // Allocate the new node before doing the rehash so that we
1339 // don't do a rehash if the allocation throws.
1340 __node
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1341 this->_M_store_code(__node
, __code
);
1342 if (__do_rehash
.first
)
1343 _M_rehash(__do_rehash
.second
, __saved_state
);
1345 _M_insert_bucket_begin(__n
, __node
);
1347 return iterator(__node
);
1352 _M_rehash_policy
._M_reset(__saved_state
);
1354 _M_deallocate_node(__node
);
1355 __throw_exception_again
;
1359 // Insert v if no element with its key is already present.
1360 template<typename _Key
, typename _Value
,
1361 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1362 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1364 template<typename _Arg
>
1365 std::pair
<typename _Hashtable
<_Key
, _Value
, _Alloc
,
1366 _ExtractKey
, _Equal
, _H1
,
1367 _H2
, _Hash
, _RehashPolicy
,
1368 _Traits
>::iterator
, bool>
1369 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1370 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1371 _M_insert(_Arg
&& __v
, std::true_type
)
1373 const key_type
& __k
= this->_M_extract()(__v
);
1374 __hash_code __code
= this->_M_hash_code(__k
);
1375 size_type __n
= _M_bucket_index(__k
, __code
);
1377 if (__node_type
* __p
= _M_find_node(__n
, __k
, __code
))
1378 return std::make_pair(iterator(__p
), false);
1379 return std::make_pair(_M_insert_bucket(std::forward
<_Arg
>(__v
),
1380 __n
, __code
), true);
1383 // Insert v unconditionally.
1384 template<typename _Key
, typename _Value
,
1385 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1386 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1388 template<typename _Arg
>
1389 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1390 _H1
, _H2
, _Hash
, _RehashPolicy
,
1392 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1393 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1394 _M_insert(_Arg
&& __v
, std::false_type
)
1396 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1397 std::pair
<bool, std::size_t> __do_rehash
1398 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1399 _M_element_count
, 1);
1401 // First compute the hash code so that we don't do anything if
1403 __hash_code __code
= this->_M_hash_code(this->_M_extract()(__v
));
1405 __node_type
* __node
= nullptr;
1408 // Second allocate new node so that we don't rehash if it throws.
1409 __node
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1410 this->_M_store_code(__node
, __code
);
1411 if (__do_rehash
.first
)
1412 _M_rehash(__do_rehash
.second
, __saved_state
);
1414 // Third, find the node before an equivalent one.
1415 size_type __bkt
= _M_bucket_index(__node
);
1417 = _M_find_before_node(__bkt
, this->_M_extract()(__node
->_M_v
),
1421 // Insert after the node before the equivalent one.
1422 __node
->_M_nxt
= __prev
->_M_nxt
;
1423 __prev
->_M_nxt
= __node
;
1426 // The inserted node has no equivalent in the
1427 // hashtable. We must insert the new node at the
1428 // beginning of the bucket to preserve equivalent
1429 // elements relative positions.
1430 _M_insert_bucket_begin(__bkt
, __node
);
1432 return iterator(__node
);
1437 _M_rehash_policy
._M_reset(__saved_state
);
1439 _M_deallocate_node(__node
);
1440 __throw_exception_again
;
1445 template<typename _Key
, typename _Value
,
1446 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1447 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1449 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1450 _H1
, _H2
, _Hash
, _RehashPolicy
,
1452 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1453 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1454 erase(const_iterator __it
)
1456 __node_type
* __n
= __it
._M_cur
;
1457 std::size_t __bkt
= _M_bucket_index(__n
);
1459 // Look for previous node to unlink it from the erased one, this
1460 // is why we need buckets to contain the before begin to make
1461 // this research fast.
1462 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1463 if (__n
== _M_bucket_begin(__bkt
))
1464 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1465 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1466 else if (__n
->_M_nxt
)
1468 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1469 if (__next_bkt
!= __bkt
)
1470 _M_buckets
[__next_bkt
] = __prev_n
;
1473 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1474 iterator
__result(__n
->_M_next());
1475 _M_deallocate_node(__n
);
1481 template<typename _Key
, typename _Value
,
1482 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1483 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1485 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1486 _H1
, _H2
, _Hash
, _RehashPolicy
,
1488 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1489 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1490 erase(const key_type
& __k
)
1492 __hash_code __code
= this->_M_hash_code(__k
);
1493 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1495 // Look for the node before the first matching node.
1496 __node_base
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1499 __node_type
* __n
= static_cast<__node_type
*>(__prev_n
->_M_nxt
);
1500 bool __is_bucket_begin
= _M_buckets
[__bkt
] == __prev_n
;
1502 // We found a matching node, start deallocation loop from it
1503 std::size_t __next_bkt
= __bkt
;
1504 __node_type
* __next_n
= __n
;
1505 size_type __result
= 0;
1506 __node_type
* __saved_n
= nullptr;
1509 __node_type
* __p
= __next_n
;
1510 __next_n
= __p
->_M_next();
1512 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1513 // 526. Is it undefined if a function in the standard changes
1515 if (std::__addressof(this->_M_extract()(__p
->_M_v
))
1516 != std::__addressof(__k
))
1517 _M_deallocate_node(__p
);
1524 __next_bkt
= _M_bucket_index(__next_n
);
1526 while (__next_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __next_n
));
1529 _M_deallocate_node(__saved_n
);
1530 if (__is_bucket_begin
)
1531 _M_remove_bucket_begin(__bkt
, __next_n
, __next_bkt
);
1532 else if (__next_n
&& __next_bkt
!= __bkt
)
1533 _M_buckets
[__next_bkt
] = __prev_n
;
1535 __prev_n
->_M_nxt
= __next_n
;
1539 template<typename _Key
, typename _Value
,
1540 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1541 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1543 typename _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1544 _H1
, _H2
, _Hash
, _RehashPolicy
,
1546 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1547 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1548 erase(const_iterator __first
, const_iterator __last
)
1550 __node_type
* __n
= __first
._M_cur
;
1551 __node_type
* __last_n
= __last
._M_cur
;
1552 if (__n
== __last_n
)
1553 return iterator(__n
);
1555 std::size_t __bkt
= _M_bucket_index(__n
);
1557 __node_base
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1558 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1559 std::size_t __n_bkt
= __bkt
;
1564 __node_type
* __tmp
= __n
;
1565 __n
= __n
->_M_next();
1566 _M_deallocate_node(__tmp
);
1570 __n_bkt
= _M_bucket_index(__n
);
1572 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1573 if (__is_bucket_begin
)
1574 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1575 if (__n
== __last_n
)
1577 __is_bucket_begin
= true;
1581 if (__n
&& (__n_bkt
!= __bkt
|| __is_bucket_begin
))
1582 _M_buckets
[__n_bkt
] = __prev_n
;
1583 __prev_n
->_M_nxt
= __n
;
1584 return iterator(__n
);
1587 template<typename _Key
, typename _Value
,
1588 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1589 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1592 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1593 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1596 _M_deallocate_nodes(_M_begin());
1597 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(__bucket_type
));
1598 _M_element_count
= 0;
1599 _M_before_begin
._M_nxt
= nullptr;
1602 template<typename _Key
, typename _Value
,
1603 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1604 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1607 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1608 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1609 rehash(size_type __n
)
1611 const __rehash_state
& __saved_state
= _M_rehash_policy
._M_state();
1612 _M_rehash(std::max(_M_rehash_policy
._M_next_bkt(__n
),
1613 _M_rehash_policy
._M_bkt_for_elements(_M_element_count
1618 template<typename _Key
, typename _Value
,
1619 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1620 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1623 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1624 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1625 _M_rehash(size_type __n
, const __rehash_state
& __state
)
1629 _M_rehash_aux(__n
, __unique_keys());
1633 // A failure here means that buckets allocation failed. We only
1634 // have to restore hash policy previous state.
1635 _M_rehash_policy
._M_reset(__state
);
1636 __throw_exception_again
;
1640 // Rehash when there is no equivalent elements.
1641 template<typename _Key
, typename _Value
,
1642 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1643 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1646 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1647 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1648 _M_rehash_aux(size_type __n
, std::true_type
)
1650 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
1651 __node_type
* __p
= _M_begin();
1652 _M_before_begin
._M_nxt
= nullptr;
1653 std::size_t __bbegin_bkt
;
1656 __node_type
* __next
= __p
->_M_next();
1657 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1658 if (!__new_buckets
[__bkt
])
1660 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
1661 _M_before_begin
._M_nxt
= __p
;
1662 __new_buckets
[__bkt
] = &_M_before_begin
;
1664 __new_buckets
[__bbegin_bkt
] = __p
;
1665 __bbegin_bkt
= __bkt
;
1669 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1670 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1674 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1675 _M_bucket_count
= __n
;
1676 _M_buckets
= __new_buckets
;
1679 // Rehash when there can be equivalent elements, preserve their relative
1681 template<typename _Key
, typename _Value
,
1682 typename _Alloc
, typename _ExtractKey
, typename _Equal
,
1683 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1686 _Hashtable
<_Key
, _Value
, _Alloc
, _ExtractKey
, _Equal
,
1687 _H1
, _H2
, _Hash
, _RehashPolicy
, _Traits
>::
1688 _M_rehash_aux(size_type __n
, std::false_type
)
1690 __bucket_type
* __new_buckets
= _M_allocate_buckets(__n
);
1692 __node_type
* __p
= _M_begin();
1693 _M_before_begin
._M_nxt
= nullptr;
1694 std::size_t __bbegin_bkt
;
1695 std::size_t __prev_bkt
;
1696 __node_type
* __prev_p
= nullptr;
1697 bool __check_bucket
= false;
1701 __node_type
* __next
= __p
->_M_next();
1702 std::size_t __bkt
= __hash_code_base::_M_bucket_index(__p
, __n
);
1704 if (__prev_p
&& __prev_bkt
== __bkt
)
1706 // Previous insert was already in this bucket, we insert after
1707 // the previously inserted one to preserve equivalent elements
1709 __p
->_M_nxt
= __prev_p
->_M_nxt
;
1710 __prev_p
->_M_nxt
= __p
;
1712 // Inserting after a node in a bucket require to check that we
1713 // haven't change the bucket last node, in this case next
1714 // bucket containing its before begin node must be updated. We
1715 // schedule a check as soon as we move out of the sequence of
1716 // equivalent nodes to limit the number of checks.
1717 __check_bucket
= true;
1723 // Check if we shall update the next bucket because of insertions
1724 // into __prev_bkt bucket.
1725 if (__prev_p
->_M_nxt
)
1727 std::size_t __next_bkt
1728 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(),
1730 if (__next_bkt
!= __prev_bkt
)
1731 __new_buckets
[__next_bkt
] = __prev_p
;
1733 __check_bucket
= false;
1736 if (!__new_buckets
[__bkt
])
1738 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
1739 _M_before_begin
._M_nxt
= __p
;
1740 __new_buckets
[__bkt
] = &_M_before_begin
;
1742 __new_buckets
[__bbegin_bkt
] = __p
;
1743 __bbegin_bkt
= __bkt
;
1747 __p
->_M_nxt
= __new_buckets
[__bkt
]->_M_nxt
;
1748 __new_buckets
[__bkt
]->_M_nxt
= __p
;
1756 if (__check_bucket
&& __prev_p
->_M_nxt
)
1758 std::size_t __next_bkt
1759 = __hash_code_base::_M_bucket_index(__prev_p
->_M_next(), __n
);
1760 if (__next_bkt
!= __prev_bkt
)
1761 __new_buckets
[__next_bkt
] = __prev_p
;
1764 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1765 _M_bucket_count
= __n
;
1766 _M_buckets
= __new_buckets
;
1769 _GLIBCXX_END_NAMESPACE_VERSION
1772 #endif // _HASHTABLE_H