1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 // Class template _Hashtable, class definition.
43 // Meaning of class template _Hashtable's template parameters
45 // _Key and _Value: arbitrary CopyConstructible types.
47 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
48 // value type is Value. As a conforming extension, we allow for
49 // value type != Value.
51 // _ExtractKey: function object that takes an object of type Value
52 // and returns a value of type _Key.
54 // _Equal: function object that takes two objects of type k and returns
55 // a bool-like value that is true if the two objects are considered equal.
57 // _H1: the hash function. A unary function object with argument type
58 // Key and result type size_t. Return values should be distributed
59 // over the entire range [0, numeric_limits<size_t>:::max()].
61 // _H2: the range-hashing function (in the terminology of Tavori and
62 // Dreizin). A binary function object whose argument types and result
63 // type are all size_t. Given arguments r and N, the return value is
64 // in the range [0, N).
66 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
67 // whose argument types are _Key and size_t and whose result type is
68 // size_t. Given arguments k and N, the return value is in the range
69 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
70 // than the default, _H1 and _H2 are ignored.
72 // _RehashPolicy: Policy class with three members, all of which govern
73 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
74 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
75 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
76 // determines whether, if the current bucket count is n_bkt and the
77 // current element count is n_elt, we need to increase the bucket
78 // count. If so, returns make_pair(true, n), where n is the new
79 // bucket count. If not, returns make_pair(false, <anything>).
81 // __cache_hash_code: bool. true if we store the value of the hash
82 // function along with the value. This is a time-space tradeoff.
83 // Storing it may improve lookup speed by reducing the number of times
84 // we need to call the Equal function.
86 // __constant_iterators: bool. true if iterator and const_iterator are
87 // both constant iterator types. This is true for unordered_set and
88 // unordered_multiset, false for unordered_map and unordered_multimap.
90 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
91 // is always at most one, false if it may be an arbitrary number. This
92 // true for unordered_set and unordered_map, false for unordered_multiset
93 // and unordered_multimap.
95 * Here's _Hashtable data structure, each _Hashtable has:
96 * - _Bucket[] _M_buckets
97 * - _Hash_node_base _M_before_begin
98 * - size_type _M_bucket_count
99 * - size_type _M_element_count
101 * with _Bucket being _Hash_node* and _Hash_node constaining:
102 * - _Hash_node* _M_next
104 * - size_t _M_code if cache_hash_code is true
106 * In terms of Standard containers the hastable is like the aggregation of:
107 * - std::forward_list<_Node> containing the elements
108 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
110 * The non-empty buckets contain the node before the first bucket node. This
111 * design allow to implement something like a std::forward_list::insert_after
112 * on container insertion and std::forward_list::erase_after on container
113 * erase calls. _M_before_begin is equivalent to
114 * std::foward_list::before_begin. Empty buckets are containing nullptr.
115 * Note that one of the non-empty bucket contains &_M_before_begin which is
116 * not a derefenrenceable node so the node pointers in buckets shall never be
117 * derefenrenced, only its next node can be.
119 * Walk through a bucket nodes require a check on the hash code to see if the
120 * node is still in the bucket. Such a design impose a quite efficient hash
121 * functor and is one of the reasons it is highly advise to set
122 * __cache_hash_code to true.
124 * The container iterators are simply built from nodes. This way incrementing
125 * the iterator is perfectly efficient independent of how many empty buckets
126 * there are in the container.
128 * On insert we compute element hash code and thanks to it find the bucket
129 * index. If the element must be inserted on an empty bucket we add it at the
130 * beginning of the singly linked list and make the bucket point to
131 * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
132 * is updated to point to its new before begin node.
134 * On erase, the simple iterator design impose to use the hash functor to get
135 * the index of the bucket to update. For this reason, when __cache_hash_code
136 * is set to false, there is a static assertion that the hash functor cannot
140 template<typename _Key
, typename _Value
, typename _Allocator
,
141 typename _ExtractKey
, typename _Equal
,
142 typename _H1
, typename _H2
, typename _Hash
,
143 typename _RehashPolicy
,
144 bool __cache_hash_code
,
145 bool __constant_iterators
,
148 : public __detail::_Rehash_base
<_RehashPolicy
,
149 _Hashtable
<_Key
, _Value
, _Allocator
,
151 _Equal
, _H1
, _H2
, _Hash
,
154 __constant_iterators
,
156 public __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
157 _H1
, _H2
, _Hash
, __cache_hash_code
>,
158 public __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __unique_keys
,
159 _Hashtable
<_Key
, _Value
, _Allocator
,
161 _Equal
, _H1
, _H2
, _Hash
,
164 __constant_iterators
,
166 public __detail::_Equality_base
<_ExtractKey
, __unique_keys
,
167 _Hashtable
<_Key
, _Value
, _Allocator
,
169 _Equal
, _H1
, _H2
, _Hash
,
172 __constant_iterators
,
175 template<typename _Cond
>
176 using __if_hash_code_cached
177 = __or_
<__not_
<integral_constant
<bool, __cache_hash_code
>>, _Cond
>;
179 template<typename _Cond
>
180 using __if_hash_code_not_cached
181 = __or_
<integral_constant
<bool, __cache_hash_code
>, _Cond
>;
183 // When hash codes are not cached the hash functor shall not throw
184 // because it is used in methods (erase, swap...) that shall not throw.
185 static_assert(__if_hash_code_not_cached
<__detail::__is_noexcept_hash
<_Key
,
187 "Cache the hash code or qualify your hash functor with noexcept");
189 // Following two static assertions are necessary to guarantee that
190 // swapping two hashtable instances won't invalidate associated local
193 // When hash codes are cached local iterator only uses H2 which must then
195 static_assert(__if_hash_code_cached
<is_empty
<_H2
>>::value
,
196 "Functor used to map hash code to bucket index must be empty");
198 typedef __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
,
200 __cache_hash_code
> _HCBase
;
202 // When hash codes are not cached local iterator is going to use _HCBase
203 // above to compute node bucket index so it has to be empty.
204 static_assert(__if_hash_code_not_cached
<is_empty
<_HCBase
>>::value
,
205 "Cache the hash code or make functors involved in hash code"
206 " and bucket index computation empty");
209 typedef _Allocator allocator_type
;
210 typedef _Value value_type
;
211 typedef _Key key_type
;
212 typedef _Equal key_equal
;
213 // mapped_type, if present, comes from _Map_base.
214 // hasher, if present, comes from _Hash_code_base.
215 typedef typename
_Allocator::pointer pointer
;
216 typedef typename
_Allocator::const_pointer const_pointer
;
217 typedef typename
_Allocator::reference reference
;
218 typedef typename
_Allocator::const_reference const_reference
;
220 typedef std::size_t size_type
;
221 typedef std::ptrdiff_t difference_type
;
222 typedef __detail::_Local_iterator
<key_type
, value_type
, _ExtractKey
,
224 __constant_iterators
,
227 typedef __detail::_Local_const_iterator
<key_type
, value_type
, _ExtractKey
,
229 __constant_iterators
,
231 const_local_iterator
;
232 typedef __detail::_Node_iterator
<value_type
, __constant_iterators
,
235 typedef __detail::_Node_const_iterator
<value_type
,
236 __constant_iterators
,
240 template<typename _Key2
, typename _Value2
, typename _Ex2
, bool __unique2
,
241 typename _Hashtable2
>
242 friend struct __detail::_Map_base
;
245 typedef typename
_RehashPolicy::_State _RehashPolicyState
;
246 typedef __detail::_Hash_node
<_Value
, __cache_hash_code
> _Node
;
247 typedef typename
_Allocator::template rebind
<_Node
>::other
248 _Node_allocator_type
;
249 typedef __detail::_Hash_node_base _BaseNode
;
250 typedef _BaseNode
* _Bucket
;
251 typedef typename
_Allocator::template rebind
<_Bucket
>::other
252 _Bucket_allocator_type
;
254 typedef typename
_Allocator::template rebind
<_Value
>::other
255 _Value_allocator_type
;
257 _Node_allocator_type _M_node_allocator
;
259 size_type _M_bucket_count
;
260 _BaseNode _M_before_begin
;
261 size_type _M_element_count
;
262 _RehashPolicy _M_rehash_policy
;
264 template<typename
... _Args
>
266 _M_allocate_node(_Args
&&... __args
);
269 _M_deallocate_node(_Node
* __n
);
271 // Deallocate the linked list of nodes pointed to by __n
273 _M_deallocate_nodes(_Node
* __n
);
276 _M_allocate_buckets(size_type __n
);
279 _M_deallocate_buckets(_Bucket
*, size_type __n
);
281 // Gets bucket begin, deals with the fact that non-empty buckets contain
282 // their before begin node.
284 _M_bucket_begin(size_type __bkt
) const;
288 { return static_cast<_Node
*>(_M_before_begin
._M_nxt
); }
291 // Constructor, destructor, assignment, swap
292 _Hashtable(size_type __bucket_hint
,
293 const _H1
&, const _H2
&, const _Hash
&,
294 const _Equal
&, const _ExtractKey
&,
295 const allocator_type
&);
297 template<typename _InputIterator
>
298 _Hashtable(_InputIterator __first
, _InputIterator __last
,
299 size_type __bucket_hint
,
300 const _H1
&, const _H2
&, const _Hash
&,
301 const _Equal
&, const _ExtractKey
&,
302 const allocator_type
&);
304 _Hashtable(const _Hashtable
&);
306 _Hashtable(_Hashtable
&&);
309 operator=(const _Hashtable
& __ht
)
311 _Hashtable
__tmp(__ht
);
317 operator=(_Hashtable
&& __ht
)
326 ~_Hashtable() noexcept
;
328 void swap(_Hashtable
&);
330 // Basic container operations
333 { return iterator(_M_begin()); }
336 begin() const noexcept
337 { return const_iterator(_M_begin()); }
341 { return iterator(nullptr); }
345 { return const_iterator(nullptr); }
348 cbegin() const noexcept
349 { return const_iterator(_M_begin()); }
352 cend() const noexcept
353 { return const_iterator(nullptr); }
356 size() const noexcept
357 { return _M_element_count
; }
360 empty() const noexcept
361 { return size() == 0; }
364 get_allocator() const noexcept
365 { return allocator_type(_M_node_allocator
); }
368 max_size() const noexcept
369 { return _M_node_allocator
.max_size(); }
374 { return this->_M_eq(); }
376 // hash_function, if present, comes from _Hash_code_base.
380 bucket_count() const noexcept
381 { return _M_bucket_count
; }
384 max_bucket_count() const noexcept
385 { return max_size(); }
388 bucket_size(size_type __n
) const
389 { return std::distance(begin(__n
), end(__n
)); }
392 bucket(const key_type
& __k
) const
393 { return _M_bucket_index(__k
, this->_M_hash_code(__k
)); }
397 { return local_iterator(_M_bucket_begin(__n
), __n
,
402 { return local_iterator(nullptr, __n
, _M_bucket_count
); }
405 begin(size_type __n
) const
406 { return const_local_iterator(_M_bucket_begin(__n
), __n
,
410 end(size_type __n
) const
411 { return const_local_iterator(nullptr, __n
, _M_bucket_count
); }
415 cbegin(size_type __n
) const
416 { return const_local_iterator(_M_bucket_begin(__n
), __n
,
420 cend(size_type __n
) const
421 { return const_local_iterator(nullptr, __n
, _M_bucket_count
); }
424 load_factor() const noexcept
426 return static_cast<float>(size()) / static_cast<float>(bucket_count());
429 // max_load_factor, if present, comes from _Rehash_base.
431 // Generalization of max_load_factor. Extension, not found in TR1. Only
432 // useful if _RehashPolicy is something other than the default.
434 __rehash_policy() const
435 { return _M_rehash_policy
; }
438 __rehash_policy(const _RehashPolicy
&);
442 find(const key_type
& __k
);
445 find(const key_type
& __k
) const;
448 count(const key_type
& __k
) const;
450 std::pair
<iterator
, iterator
>
451 equal_range(const key_type
& __k
);
453 std::pair
<const_iterator
, const_iterator
>
454 equal_range(const key_type
& __k
) const;
457 // Bucket index computation helpers.
459 _M_bucket_index(_Node
* __n
) const
460 { return _HCBase::_M_bucket_index(__n
, _M_bucket_count
); }
463 _M_bucket_index(const key_type
& __k
,
464 typename
_Hashtable::_Hash_code_type __c
) const
465 { return _HCBase::_M_bucket_index(__k
, __c
, _M_bucket_count
); }
467 // Find and insert helper functions and types
468 // Find the node before the one matching the criteria.
470 _M_find_before_node(size_type
, const key_type
&,
471 typename
_Hashtable::_Hash_code_type
) const;
474 _M_find_node(size_type __bkt
, const key_type
& __key
,
475 typename
_Hashtable::_Hash_code_type __c
) const
477 _BaseNode
* __before_n
= _M_find_before_node(__bkt
, __key
, __c
);
479 return static_cast<_Node
*>(__before_n
->_M_nxt
);
483 // Insert a node at the beginning of a bucket.
485 _M_insert_bucket_begin(size_type
, _Node
*);
487 // Remove the bucket first node
489 _M_remove_bucket_begin(size_type __bkt
, _Node
* __next_n
,
490 size_type __next_bkt
);
492 // Get the node before __n in the bucket __bkt
494 _M_get_previous_node(size_type __bkt
, _BaseNode
* __n
);
496 template<typename _Arg
>
498 _M_insert_bucket(_Arg
&&, size_type
,
499 typename
_Hashtable::_Hash_code_type
);
501 typedef typename
std::conditional
<__unique_keys
,
502 std::pair
<iterator
, bool>,
506 typedef typename
std::conditional
<__unique_keys
,
507 std::_Select1st
<_Insert_Return_Type
>,
508 std::_Identity
<_Insert_Return_Type
>
513 template<typename
... _Args
>
514 std::pair
<iterator
, bool>
515 _M_emplace(std::true_type
, _Args
&&... __args
);
517 template<typename
... _Args
>
519 _M_emplace(std::false_type
, _Args
&&... __args
);
521 template<typename _Arg
>
522 std::pair
<iterator
, bool>
523 _M_insert(_Arg
&&, std::true_type
);
525 template<typename _Arg
>
527 _M_insert(_Arg
&&, std::false_type
);
530 // Emplace, insert and erase
531 template<typename
... _Args
>
533 emplace(_Args
&&... __args
)
534 { return _M_emplace(integral_constant
<bool, __unique_keys
>(),
535 std::forward
<_Args
>(__args
)...); }
537 template<typename
... _Args
>
539 emplace_hint(const_iterator
, _Args
&&... __args
)
540 { return _Insert_Conv_Type()(emplace(std::forward
<_Args
>(__args
)...)); }
543 insert(const value_type
& __v
)
544 { return _M_insert(__v
, integral_constant
<bool, __unique_keys
>()); }
547 insert(const_iterator
, const value_type
& __v
)
548 { return _Insert_Conv_Type()(insert(__v
)); }
550 template<typename _Pair
, typename
= typename
551 std::enable_if
<__and_
<integral_constant
<bool, !__constant_iterators
>,
552 std::is_convertible
<_Pair
,
553 value_type
>>::value
>::type
>
556 { return _M_insert(std::forward
<_Pair
>(__v
),
557 integral_constant
<bool, __unique_keys
>()); }
559 template<typename _Pair
, typename
= typename
560 std::enable_if
<__and_
<integral_constant
<bool, !__constant_iterators
>,
561 std::is_convertible
<_Pair
,
562 value_type
>>::value
>::type
>
564 insert(const_iterator
, _Pair
&& __v
)
565 { return _Insert_Conv_Type()(insert(std::forward
<_Pair
>(__v
))); }
567 template<typename _InputIterator
>
569 insert(_InputIterator __first
, _InputIterator __last
);
572 insert(initializer_list
<value_type
> __l
)
573 { this->insert(__l
.begin(), __l
.end()); }
576 erase(const_iterator
);
581 { return erase(const_iterator(__it
)); }
584 erase(const key_type
&);
587 erase(const_iterator
, const_iterator
);
592 // Set number of buckets to be appropriate for container of n element.
593 void rehash(size_type __n
);
596 // reserve, if present, comes from _Rehash_base.
599 // Unconditionally change size of bucket array to n, restore hash policy
600 // state to __state on exception.
601 void _M_rehash(size_type __n
, const _RehashPolicyState
& __state
);
605 // Definitions of class template _Hashtable's out-of-line member functions.
606 template<typename _Key
, typename _Value
,
607 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
608 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
609 bool __chc
, bool __cit
, bool __uk
>
610 template<typename
... _Args
>
611 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
612 _H1
, _H2
, _Hash
, _RehashPolicy
,
613 __chc
, __cit
, __uk
>::_Node
*
614 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
615 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
616 _M_allocate_node(_Args
&&... __args
)
618 _Node
* __n
= _M_node_allocator
.allocate(1);
621 _M_node_allocator
.construct(__n
, std::forward
<_Args
>(__args
)...);
626 _M_node_allocator
.deallocate(__n
, 1);
627 __throw_exception_again
;
631 template<typename _Key
, typename _Value
,
632 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
633 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
634 bool __chc
, bool __cit
, bool __uk
>
636 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
637 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
638 _M_deallocate_node(_Node
* __n
)
640 _M_node_allocator
.destroy(__n
);
641 _M_node_allocator
.deallocate(__n
, 1);
644 template<typename _Key
, typename _Value
,
645 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
646 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
647 bool __chc
, bool __cit
, bool __uk
>
649 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
650 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
651 _M_deallocate_nodes(_Node
* __n
)
656 __n
= __n
->_M_next();
657 _M_deallocate_node(__tmp
);
661 template<typename _Key
, typename _Value
,
662 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
663 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
664 bool __chc
, bool __cit
, bool __uk
>
665 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
666 _H1
, _H2
, _Hash
, _RehashPolicy
,
667 __chc
, __cit
, __uk
>::_Bucket
*
668 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
669 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
670 _M_allocate_buckets(size_type __n
)
672 _Bucket_allocator_type
__alloc(_M_node_allocator
);
674 _Bucket
* __p
= __alloc
.allocate(__n
);
675 __builtin_memset(__p
, 0, __n
* sizeof(_Bucket
));
679 template<typename _Key
, typename _Value
,
680 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
681 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
682 bool __chc
, bool __cit
, bool __uk
>
684 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
685 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
686 _M_deallocate_buckets(_Bucket
* __p
, size_type __n
)
688 _Bucket_allocator_type
__alloc(_M_node_allocator
);
689 __alloc
.deallocate(__p
, __n
);
692 template<typename _Key
, typename _Value
,
693 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
694 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
695 bool __chc
, bool __cit
, bool __uk
>
696 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
697 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
698 __chc
, __cit
, __uk
>::_Node
*
699 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
700 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
701 _M_bucket_begin(size_type __bkt
) const
703 _BaseNode
* __n
= _M_buckets
[__bkt
];
704 return __n
? static_cast<_Node
*>(__n
->_M_nxt
) : nullptr;
707 template<typename _Key
, typename _Value
,
708 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
709 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
710 bool __chc
, bool __cit
, bool __uk
>
711 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
712 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
713 _Hashtable(size_type __bucket_hint
,
714 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
715 const _Equal
& __eq
, const _ExtractKey
& __exk
,
716 const allocator_type
& __a
)
717 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
718 __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
719 _H1
, _H2
, _Hash
, __chc
>(__exk
, __h1
, __h2
, __h
,
721 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
722 _M_node_allocator(__a
),
727 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
728 // We don't want the rehash policy to ask for the hashtable to shrink
729 // on the first insertion so we need to reset its previous resize level.
730 _M_rehash_policy
._M_prev_resize
= 0;
731 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
734 template<typename _Key
, typename _Value
,
735 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
736 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
737 bool __chc
, bool __cit
, bool __uk
>
738 template<typename _InputIterator
>
739 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
740 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
741 _Hashtable(_InputIterator __f
, _InputIterator __l
,
742 size_type __bucket_hint
,
743 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
744 const _Equal
& __eq
, const _ExtractKey
& __exk
,
745 const allocator_type
& __a
)
746 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
747 __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
748 _H1
, _H2
, _Hash
, __chc
>(__exk
, __h1
, __h2
, __h
,
750 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
751 _M_node_allocator(__a
),
756 _M_bucket_count
= std::max(_M_rehash_policy
._M_next_bkt(__bucket_hint
),
758 _M_bkt_for_elements(__detail::
761 // We don't want the rehash policy to ask for the hashtable to shrink
762 // on the first insertion so we need to reset its previous resize
764 _M_rehash_policy
._M_prev_resize
= 0;
765 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
768 for (; __f
!= __l
; ++__f
)
774 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
775 __throw_exception_again
;
779 template<typename _Key
, typename _Value
,
780 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
781 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
782 bool __chc
, bool __cit
, bool __uk
>
783 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
784 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
785 _Hashtable(const _Hashtable
& __ht
)
786 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
787 __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
788 _H1
, _H2
, _Hash
, __chc
>(__ht
),
789 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
790 _M_node_allocator(__ht
._M_node_allocator
),
791 _M_bucket_count(__ht
._M_bucket_count
),
792 _M_element_count(__ht
._M_element_count
),
793 _M_rehash_policy(__ht
._M_rehash_policy
)
795 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
798 if (!__ht
._M_before_begin
._M_nxt
)
801 // First deal with the special first node pointed to by
803 const _Node
* __ht_n
= __ht
._M_begin();
804 _Node
* __this_n
= _M_allocate_node(__ht_n
->_M_v
);
805 this->_M_copy_code(__this_n
, __ht_n
);
806 _M_before_begin
._M_nxt
= __this_n
;
807 _M_buckets
[_M_bucket_index(__this_n
)] = &_M_before_begin
;
809 // Then deal with other nodes.
810 _BaseNode
* __prev_n
= __this_n
;
811 for (__ht_n
= __ht_n
->_M_next(); __ht_n
; __ht_n
= __ht_n
->_M_next())
813 __this_n
= _M_allocate_node(__ht_n
->_M_v
);
814 __prev_n
->_M_nxt
= __this_n
;
815 this->_M_copy_code(__this_n
, __ht_n
);
816 size_type __bkt
= _M_bucket_index(__this_n
);
817 if (!_M_buckets
[__bkt
])
818 _M_buckets
[__bkt
] = __prev_n
;
825 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
826 __throw_exception_again
;
830 template<typename _Key
, typename _Value
,
831 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
832 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
833 bool __chc
, bool __cit
, bool __uk
>
834 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
835 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
836 _Hashtable(_Hashtable
&& __ht
)
837 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
838 __detail::_Hashtable_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
839 _H1
, _H2
, _Hash
, __chc
>(__ht
),
840 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
841 _M_node_allocator(std::move(__ht
._M_node_allocator
)),
842 _M_buckets(__ht
._M_buckets
),
843 _M_bucket_count(__ht
._M_bucket_count
),
844 _M_before_begin(__ht
._M_before_begin
._M_nxt
),
845 _M_element_count(__ht
._M_element_count
),
846 _M_rehash_policy(__ht
._M_rehash_policy
)
848 // Update, if necessary, bucket pointing to before begin that hasn't move.
850 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
851 __ht
._M_rehash_policy
= _RehashPolicy();
852 __ht
._M_bucket_count
= __ht
._M_rehash_policy
._M_next_bkt(0);
853 __ht
._M_buckets
= __ht
._M_allocate_buckets(__ht
._M_bucket_count
);
854 __ht
._M_before_begin
._M_nxt
= nullptr;
855 __ht
._M_element_count
= 0;
858 template<typename _Key
, typename _Value
,
859 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
860 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
861 bool __chc
, bool __cit
, bool __uk
>
862 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
863 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
864 ~_Hashtable() noexcept
867 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
870 template<typename _Key
, typename _Value
,
871 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
872 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
873 bool __chc
, bool __cit
, bool __uk
>
875 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
876 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
877 swap(_Hashtable
& __x
)
879 // The only base class with member variables is hash_code_base. We
880 // define _Hash_code_base::_M_swap because different specializations
881 // have different members.
884 // _GLIBCXX_RESOLVE_LIB_DEFECTS
885 // 431. Swapping containers with unequal allocators.
886 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator
,
887 __x
._M_node_allocator
);
889 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
890 std::swap(_M_buckets
, __x
._M_buckets
);
891 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
892 std::swap(_M_before_begin
._M_nxt
, __x
._M_before_begin
._M_nxt
);
893 std::swap(_M_element_count
, __x
._M_element_count
);
894 // Fix buckets containing the _M_before_begin pointers that can't be
897 _M_buckets
[_M_bucket_index(_M_begin())] = &_M_before_begin
;
899 __x
._M_buckets
[__x
._M_bucket_index(__x
._M_begin())]
900 = &(__x
._M_before_begin
);
903 template<typename _Key
, typename _Value
,
904 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
905 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
906 bool __chc
, bool __cit
, bool __uk
>
908 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
909 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
910 __rehash_policy(const _RehashPolicy
& __pol
)
912 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
913 if (__n_bkt
!= _M_bucket_count
)
914 _M_rehash(__n_bkt
, _M_rehash_policy
._M_state());
915 _M_rehash_policy
= __pol
;
918 template<typename _Key
, typename _Value
,
919 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
920 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
921 bool __chc
, bool __cit
, bool __uk
>
922 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
923 _H1
, _H2
, _Hash
, _RehashPolicy
,
924 __chc
, __cit
, __uk
>::iterator
925 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
926 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
927 find(const key_type
& __k
)
929 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
930 std::size_t __n
= _M_bucket_index(__k
, __code
);
931 _Node
* __p
= _M_find_node(__n
, __k
, __code
);
932 return __p
? iterator(__p
) : this->end();
935 template<typename _Key
, typename _Value
,
936 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
937 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
938 bool __chc
, bool __cit
, bool __uk
>
939 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
940 _H1
, _H2
, _Hash
, _RehashPolicy
,
941 __chc
, __cit
, __uk
>::const_iterator
942 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
943 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
944 find(const key_type
& __k
) const
946 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
947 std::size_t __n
= _M_bucket_index(__k
, __code
);
948 _Node
* __p
= _M_find_node(__n
, __k
, __code
);
949 return __p
? const_iterator(__p
) : this->end();
952 template<typename _Key
, typename _Value
,
953 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
954 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
955 bool __chc
, bool __cit
, bool __uk
>
956 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
957 _H1
, _H2
, _Hash
, _RehashPolicy
,
958 __chc
, __cit
, __uk
>::size_type
959 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
960 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
961 count(const key_type
& __k
) const
963 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
964 std::size_t __n
= _M_bucket_index(__k
, __code
);
965 _Node
* __p
= _M_bucket_begin(__n
);
969 std::size_t __result
= 0;
970 for (;; __p
= __p
->_M_next())
972 if (this->_M_equals(__k
, __code
, __p
))
975 // All equivalent values are next to each other, if we found a not
976 // equivalent value after an equivalent one it means that we won't
977 // find anymore an equivalent value.
979 if (!__p
->_M_nxt
|| _M_bucket_index(__p
->_M_next()) != __n
)
985 template<typename _Key
, typename _Value
,
986 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
987 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
988 bool __chc
, bool __cit
, bool __uk
>
989 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
990 _ExtractKey
, _Equal
, _H1
,
991 _H2
, _Hash
, _RehashPolicy
,
992 __chc
, __cit
, __uk
>::iterator
,
993 typename _Hashtable
<_Key
, _Value
, _Allocator
,
994 _ExtractKey
, _Equal
, _H1
,
995 _H2
, _Hash
, _RehashPolicy
,
996 __chc
, __cit
, __uk
>::iterator
>
997 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
998 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
999 equal_range(const key_type
& __k
)
1001 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1002 std::size_t __n
= _M_bucket_index(__k
, __code
);
1003 _Node
* __p
= _M_find_node(__n
, __k
, __code
);
1007 _Node
* __p1
= __p
->_M_next();
1008 while (__p1
&& _M_bucket_index(__p1
) == __n
1009 && this->_M_equals(__k
, __code
, __p1
))
1010 __p1
= __p1
->_M_next();
1012 return std::make_pair(iterator(__p
), iterator(__p1
));
1015 return std::make_pair(this->end(), this->end());
1018 template<typename _Key
, typename _Value
,
1019 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1020 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1021 bool __chc
, bool __cit
, bool __uk
>
1022 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
1023 _ExtractKey
, _Equal
, _H1
,
1024 _H2
, _Hash
, _RehashPolicy
,
1025 __chc
, __cit
, __uk
>::const_iterator
,
1026 typename _Hashtable
<_Key
, _Value
, _Allocator
,
1027 _ExtractKey
, _Equal
, _H1
,
1028 _H2
, _Hash
, _RehashPolicy
,
1029 __chc
, __cit
, __uk
>::const_iterator
>
1030 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1031 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1032 equal_range(const key_type
& __k
) const
1034 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1035 std::size_t __n
= _M_bucket_index(__k
, __code
);
1036 _Node
* __p
= _M_find_node(__n
, __k
, __code
);
1040 _Node
* __p1
= __p
->_M_next();
1041 while (__p1
&& _M_bucket_index(__p1
) == __n
1042 && this->_M_equals(__k
, __code
, __p1
))
1043 __p1
= __p1
->_M_next();
1045 return std::make_pair(const_iterator(__p
), const_iterator(__p1
));
1048 return std::make_pair(this->end(), this->end());
1051 // Find the node whose key compares equal to k in the bucket n. Return nullptr
1052 // if no node is found.
1053 template<typename _Key
, typename _Value
,
1054 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1055 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1056 bool __chc
, bool __cit
, bool __uk
>
1057 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
1058 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1059 __chc
, __cit
, __uk
>::_BaseNode
*
1060 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1061 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1062 _M_find_before_node(size_type __n
, const key_type
& __k
,
1063 typename
_Hashtable::_Hash_code_type __code
) const
1065 _BaseNode
* __prev_p
= _M_buckets
[__n
];
1068 _Node
* __p
= static_cast<_Node
*>(__prev_p
->_M_nxt
);
1069 for (;; __p
= __p
->_M_next())
1071 if (this->_M_equals(__k
, __code
, __p
))
1073 if (!(__p
->_M_nxt
) || _M_bucket_index(__p
->_M_next()) != __n
)
1080 template<typename _Key
, typename _Value
,
1081 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1082 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1083 bool __chc
, bool __cit
, bool __uk
>
1085 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1086 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1087 _M_insert_bucket_begin(size_type __bkt
, _Node
* __new_node
)
1089 if (_M_buckets
[__bkt
])
1091 // Bucket is not empty, we just need to insert the new node after the
1092 // bucket before begin.
1093 __new_node
->_M_nxt
= _M_buckets
[__bkt
]->_M_nxt
;
1094 _M_buckets
[__bkt
]->_M_nxt
= __new_node
;
1098 // The bucket is empty, the new node is inserted at the beginning of
1099 // the singly linked list and the bucket will contain _M_before_begin
1101 __new_node
->_M_nxt
= _M_before_begin
._M_nxt
;
1102 _M_before_begin
._M_nxt
= __new_node
;
1103 if (__new_node
->_M_nxt
)
1104 // We must update former begin bucket that is pointing to
1106 _M_buckets
[_M_bucket_index(__new_node
->_M_next())] = __new_node
;
1107 _M_buckets
[__bkt
] = &_M_before_begin
;
1111 template<typename _Key
, typename _Value
,
1112 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1113 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1114 bool __chc
, bool __cit
, bool __uk
>
1116 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1117 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1118 _M_remove_bucket_begin(size_type __bkt
, _Node
* __next
, size_type __next_bkt
)
1120 if (!__next
|| __next_bkt
!= __bkt
)
1122 // Bucket is now empty
1123 // First update next bucket if any
1125 _M_buckets
[__next_bkt
] = _M_buckets
[__bkt
];
1126 // Second update before begin node if necessary
1127 if (&_M_before_begin
== _M_buckets
[__bkt
])
1128 _M_before_begin
._M_nxt
= __next
;
1129 _M_buckets
[__bkt
] = nullptr;
1133 template<typename _Key
, typename _Value
,
1134 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1135 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1136 bool __chc
, bool __cit
, bool __uk
>
1137 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
1138 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
1139 __chc
, __cit
, __uk
>::_BaseNode
*
1140 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1141 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1142 _M_get_previous_node(size_type __bkt
, _BaseNode
* __n
)
1144 _BaseNode
* __prev_n
= _M_buckets
[__bkt
];
1145 while (__prev_n
->_M_nxt
!= __n
)
1146 __prev_n
= __prev_n
->_M_nxt
;
1150 template<typename _Key
, typename _Value
,
1151 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1152 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1153 bool __chc
, bool __cit
, bool __uk
>
1154 template<typename
... _Args
>
1155 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
1156 _ExtractKey
, _Equal
, _H1
,
1157 _H2
, _Hash
, _RehashPolicy
,
1158 __chc
, __cit
, __uk
>::iterator
, bool>
1159 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1160 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1161 _M_emplace(std::true_type
, _Args
&&... __args
)
1163 // First build the node to get access to the hash code
1164 _Node
* __new_node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1167 const key_type
& __k
= this->_M_extract()(__new_node
->_M_v
);
1168 typename
_Hashtable::_Hash_code_type __code
1169 = this->_M_hash_code(__k
);
1170 size_type __bkt
= _M_bucket_index(__k
, __code
);
1172 if (_Node
* __p
= _M_find_node(__bkt
, __k
, __code
))
1174 // There is already an equivalent node, no insertion
1175 _M_deallocate_node(__new_node
);
1176 return std::make_pair(iterator(__p
), false);
1179 // We are going to insert this node
1180 this->_M_store_code(__new_node
, __code
);
1181 const _RehashPolicyState
& __saved_state
1182 = _M_rehash_policy
._M_state();
1183 std::pair
<bool, std::size_t> __do_rehash
1184 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1185 _M_element_count
, 1);
1187 if (__do_rehash
.first
)
1189 _M_rehash(__do_rehash
.second
, __saved_state
);
1190 __bkt
= _M_bucket_index(__k
, __code
);
1193 _M_insert_bucket_begin(__bkt
, __new_node
);
1195 return std::make_pair(iterator(__new_node
), true);
1199 _M_deallocate_node(__new_node
);
1200 __throw_exception_again
;
1204 template<typename _Key
, typename _Value
,
1205 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1206 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1207 bool __chc
, bool __cit
, bool __uk
>
1208 template<typename
... _Args
>
1209 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1210 _H1
, _H2
, _Hash
, _RehashPolicy
,
1211 __chc
, __cit
, __uk
>::iterator
1212 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1213 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1214 _M_emplace(std::false_type
, _Args
&&... __args
)
1216 const _RehashPolicyState
& __saved_state
= _M_rehash_policy
._M_state();
1217 std::pair
<bool, std::size_t> __do_rehash
1218 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1219 _M_element_count
, 1);
1221 // First build the node to get its hash code.
1222 _Node
* __new_node
= _M_allocate_node(std::forward
<_Args
>(__args
)...);
1225 const key_type
& __k
= this->_M_extract()(__new_node
->_M_v
);
1226 typename
_Hashtable::_Hash_code_type __code
1227 = this->_M_hash_code(__k
);
1228 this->_M_store_code(__new_node
, __code
);
1230 // Second, do rehash if necessary.
1231 if (__do_rehash
.first
)
1232 _M_rehash(__do_rehash
.second
, __saved_state
);
1234 // Third, find the node before an equivalent one.
1235 size_type __bkt
= _M_bucket_index(__k
, __code
);
1236 _BaseNode
* __prev
= _M_find_before_node(__bkt
, __k
, __code
);
1240 // Insert after the node before the equivalent one.
1241 __new_node
->_M_nxt
= __prev
->_M_nxt
;
1242 __prev
->_M_nxt
= __new_node
;
1245 // The inserted node has no equivalent in the hashtable. We must
1246 // insert the new node at the beginning of the bucket to preserve
1247 // equivalent elements relative positions.
1248 _M_insert_bucket_begin(__bkt
, __new_node
);
1250 return iterator(__new_node
);
1254 _M_deallocate_node(__new_node
);
1255 __throw_exception_again
;
1259 // Insert v in bucket n (assumes no element with its key already present).
1260 template<typename _Key
, typename _Value
,
1261 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1262 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1263 bool __chc
, bool __cit
, bool __uk
>
1264 template<typename _Arg
>
1265 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1266 _H1
, _H2
, _Hash
, _RehashPolicy
,
1267 __chc
, __cit
, __uk
>::iterator
1268 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1269 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1270 _M_insert_bucket(_Arg
&& __v
, size_type __n
,
1271 typename
_Hashtable::_Hash_code_type __code
)
1273 const _RehashPolicyState
& __saved_state
= _M_rehash_policy
._M_state();
1274 std::pair
<bool, std::size_t> __do_rehash
1275 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1276 _M_element_count
, 1);
1278 if (__do_rehash
.first
)
1280 const key_type
& __k
= this->_M_extract()(__v
);
1281 __n
= _HCBase::_M_bucket_index(__k
, __code
, __do_rehash
.second
);
1284 _Node
* __new_node
= nullptr;
1287 // Allocate the new node before doing the rehash so that we
1288 // don't do a rehash if the allocation throws.
1289 __new_node
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1290 this->_M_store_code(__new_node
, __code
);
1291 if (__do_rehash
.first
)
1292 _M_rehash(__do_rehash
.second
, __saved_state
);
1294 _M_insert_bucket_begin(__n
, __new_node
);
1296 return iterator(__new_node
);
1301 _M_rehash_policy
._M_reset(__saved_state
);
1303 _M_deallocate_node(__new_node
);
1304 __throw_exception_again
;
1308 // Insert v if no element with its key is already present.
1309 template<typename _Key
, typename _Value
,
1310 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1311 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1312 bool __chc
, bool __cit
, bool __uk
>
1313 template<typename _Arg
>
1314 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
1315 _ExtractKey
, _Equal
, _H1
,
1316 _H2
, _Hash
, _RehashPolicy
,
1317 __chc
, __cit
, __uk
>::iterator
, bool>
1318 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1319 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1320 _M_insert(_Arg
&& __v
, std::true_type
)
1322 const key_type
& __k
= this->_M_extract()(__v
);
1323 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1324 size_type __n
= _M_bucket_index(__k
, __code
);
1326 if (_Node
* __p
= _M_find_node(__n
, __k
, __code
))
1327 return std::make_pair(iterator(__p
), false);
1328 return std::make_pair(_M_insert_bucket(std::forward
<_Arg
>(__v
),
1329 __n
, __code
), true);
1332 // Insert v unconditionally.
1333 template<typename _Key
, typename _Value
,
1334 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1335 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1336 bool __chc
, bool __cit
, bool __uk
>
1337 template<typename _Arg
>
1338 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1339 _H1
, _H2
, _Hash
, _RehashPolicy
,
1340 __chc
, __cit
, __uk
>::iterator
1341 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1342 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1343 _M_insert(_Arg
&& __v
, std::false_type
)
1345 const _RehashPolicyState
& __saved_state
= _M_rehash_policy
._M_state();
1346 std::pair
<bool, std::size_t> __do_rehash
1347 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1348 _M_element_count
, 1);
1350 // First compute the hash code so that we don't do anything if it throws.
1351 typename
_Hashtable::_Hash_code_type __code
1352 = this->_M_hash_code(this->_M_extract()(__v
));
1354 _Node
* __new_node
= nullptr;
1357 // Second allocate new node so that we don't rehash if it throws.
1358 __new_node
= _M_allocate_node(std::forward
<_Arg
>(__v
));
1359 this->_M_store_code(__new_node
, __code
);
1360 if (__do_rehash
.first
)
1361 _M_rehash(__do_rehash
.second
, __saved_state
);
1363 // Third, find the node before an equivalent one.
1364 size_type __bkt
= _M_bucket_index(__new_node
);
1366 = _M_find_before_node(__bkt
, this->_M_extract()(__new_node
->_M_v
),
1370 // Insert after the node before the equivalent one.
1371 __new_node
->_M_nxt
= __prev
->_M_nxt
;
1372 __prev
->_M_nxt
= __new_node
;
1375 // The inserted node has no equivalent in the hashtable. We must
1376 // insert the new node at the beginning of the bucket to preserve
1377 // equivalent elements relative positions.
1378 _M_insert_bucket_begin(__bkt
, __new_node
);
1380 return iterator(__new_node
);
1385 _M_rehash_policy
._M_reset(__saved_state
);
1387 _M_deallocate_node(__new_node
);
1388 __throw_exception_again
;
1392 template<typename _Key
, typename _Value
,
1393 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1394 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1395 bool __chc
, bool __cit
, bool __uk
>
1396 template<typename _InputIterator
>
1398 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1399 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1400 insert(_InputIterator __first
, _InputIterator __last
)
1402 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
1403 const _RehashPolicyState
& __saved_state
= _M_rehash_policy
._M_state();
1404 std::pair
<bool, std::size_t> __do_rehash
1405 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1406 _M_element_count
, __n_elt
);
1407 if (__do_rehash
.first
)
1408 _M_rehash(__do_rehash
.second
, __saved_state
);
1410 for (; __first
!= __last
; ++__first
)
1411 this->insert(*__first
);
1414 template<typename _Key
, typename _Value
,
1415 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1416 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1417 bool __chc
, bool __cit
, bool __uk
>
1418 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1419 _H1
, _H2
, _Hash
, _RehashPolicy
,
1420 __chc
, __cit
, __uk
>::iterator
1421 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1422 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1423 erase(const_iterator __it
)
1425 _Node
* __n
= __it
._M_cur
;
1426 std::size_t __bkt
= _M_bucket_index(__n
);
1428 // Look for previous node to unlink it from the erased one, this is why
1429 // we need buckets to contain the before begin to make this research fast.
1430 _BaseNode
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1431 if (__n
== _M_bucket_begin(__bkt
))
1432 _M_remove_bucket_begin(__bkt
, __n
->_M_next(),
1433 __n
->_M_nxt
? _M_bucket_index(__n
->_M_next()) : 0);
1434 else if (__n
->_M_nxt
)
1436 size_type __next_bkt
= _M_bucket_index(__n
->_M_next());
1437 if (__next_bkt
!= __bkt
)
1438 _M_buckets
[__next_bkt
] = __prev_n
;
1441 __prev_n
->_M_nxt
= __n
->_M_nxt
;
1442 iterator
__result(__n
->_M_next());
1443 _M_deallocate_node(__n
);
1449 template<typename _Key
, typename _Value
,
1450 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1451 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1452 bool __chc
, bool __cit
, bool __uk
>
1453 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1454 _H1
, _H2
, _Hash
, _RehashPolicy
,
1455 __chc
, __cit
, __uk
>::size_type
1456 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1457 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1458 erase(const key_type
& __k
)
1460 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1461 std::size_t __bkt
= _M_bucket_index(__k
, __code
);
1462 // Look for the node before the first matching node.
1463 _BaseNode
* __prev_n
= _M_find_before_node(__bkt
, __k
, __code
);
1466 _Node
* __n
= static_cast<_Node
*>(__prev_n
->_M_nxt
);
1467 bool __is_bucket_begin
= _M_buckets
[__bkt
] == __prev_n
;
1469 // We found a matching node, start deallocation loop from it
1470 std::size_t __next_bkt
= __bkt
;
1471 _Node
* __next_n
= __n
;
1472 size_type __result
= 0;
1473 _Node
* __saved_n
= nullptr;
1476 _Node
* __p
= __next_n
;
1477 __next_n
= __p
->_M_next();
1478 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1479 // 526. Is it undefined if a function in the standard changes
1481 if (std::__addressof(this->_M_extract()(__p
->_M_v
))
1482 != std::__addressof(__k
))
1483 _M_deallocate_node(__p
);
1490 __next_bkt
= _M_bucket_index(__next_n
);
1492 while (__next_bkt
== __bkt
&& this->_M_equals(__k
, __code
, __next_n
));
1495 _M_deallocate_node(__saved_n
);
1496 if (__is_bucket_begin
)
1497 _M_remove_bucket_begin(__bkt
, __next_n
, __next_bkt
);
1498 else if (__next_n
&& __next_bkt
!= __bkt
)
1499 _M_buckets
[__next_bkt
] = __prev_n
;
1501 __prev_n
->_M_nxt
= __next_n
;
1505 template<typename _Key
, typename _Value
,
1506 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1507 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1508 bool __chc
, bool __cit
, bool __uk
>
1509 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1510 _H1
, _H2
, _Hash
, _RehashPolicy
,
1511 __chc
, __cit
, __uk
>::iterator
1512 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1513 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1514 erase(const_iterator __first
, const_iterator __last
)
1516 _Node
* __n
= __first
._M_cur
;
1517 _Node
* __last_n
= __last
._M_cur
;
1518 if (__n
== __last_n
)
1519 return iterator(__n
);
1521 std::size_t __bkt
= _M_bucket_index(__n
);
1523 _BaseNode
* __prev_n
= _M_get_previous_node(__bkt
, __n
);
1524 bool __is_bucket_begin
= __n
== _M_bucket_begin(__bkt
);
1525 std::size_t __n_bkt
= __bkt
;
1531 __n
= __n
->_M_next();
1532 _M_deallocate_node(__tmp
);
1536 __n_bkt
= _M_bucket_index(__n
);
1538 while (__n
!= __last_n
&& __n_bkt
== __bkt
);
1539 if (__is_bucket_begin
)
1540 _M_remove_bucket_begin(__bkt
, __n
, __n_bkt
);
1541 if (__n
== __last_n
)
1543 __is_bucket_begin
= true;
1547 if (__n
&& __n_bkt
!= __bkt
)
1548 _M_buckets
[__n_bkt
] = __prev_n
;
1549 __prev_n
->_M_nxt
= __n
;
1550 return iterator(__n
);
1553 template<typename _Key
, typename _Value
,
1554 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1555 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1556 bool __chc
, bool __cit
, bool __uk
>
1558 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1559 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1562 _M_deallocate_nodes(_M_begin());
1563 __builtin_memset(_M_buckets
, 0, _M_bucket_count
* sizeof(_Bucket
));
1564 _M_element_count
= 0;
1565 _M_before_begin
._M_nxt
= nullptr;
1568 template<typename _Key
, typename _Value
,
1569 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1570 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1571 bool __chc
, bool __cit
, bool __uk
>
1573 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1574 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1575 rehash(size_type __n
)
1577 const _RehashPolicyState
& __saved_state
= _M_rehash_policy
._M_state();
1578 _M_rehash(std::max(_M_rehash_policy
._M_next_bkt(__n
),
1579 _M_rehash_policy
._M_bkt_for_elements(_M_element_count
1584 template<typename _Key
, typename _Value
,
1585 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1586 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1587 bool __chc
, bool __cit
, bool __uk
>
1589 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1590 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1591 _M_rehash(size_type __n
, const _RehashPolicyState
& __state
)
1595 _Bucket
* __new_buckets
= _M_allocate_buckets(__n
);
1596 _Node
* __p
= _M_begin();
1597 _M_before_begin
._M_nxt
= nullptr;
1598 std::size_t __cur_bbegin_bkt
;
1601 _Node
* __next
= __p
->_M_next();
1602 std::size_t __new_index
= _HCBase::_M_bucket_index(__p
, __n
);
1603 if (!__new_buckets
[__new_index
])
1605 __p
->_M_nxt
= _M_before_begin
._M_nxt
;
1606 _M_before_begin
._M_nxt
= __p
;
1607 __new_buckets
[__new_index
] = &_M_before_begin
;
1609 __new_buckets
[__cur_bbegin_bkt
] = __p
;
1610 __cur_bbegin_bkt
= __new_index
;
1614 __p
->_M_nxt
= __new_buckets
[__new_index
]->_M_nxt
;
1615 __new_buckets
[__new_index
]->_M_nxt
= __p
;
1619 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1620 _M_bucket_count
= __n
;
1621 _M_buckets
= __new_buckets
;
1625 // A failure here means that buckets allocation failed. We only
1626 // have to restore hash policy previous state.
1627 _M_rehash_policy
._M_reset(__state
);
1628 __throw_exception_again
;
1632 _GLIBCXX_END_NAMESPACE_VERSION
1635 #endif // _HASHTABLE_H