1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013
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 // Class template _Hashtable, class definition.
44 // Meaning of class template _Hashtable's template parameters
46 // _Key and _Value: arbitrary CopyConstructible types.
48 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
49 // value type is Value. As a conforming extension, we allow for
50 // value type != Value.
52 // _ExtractKey: function object that takes an object of type Value
53 // and returns a value of type _Key.
55 // _Equal: function object that takes two objects of type k and returns
56 // a bool-like value that is true if the two objects are considered equal.
58 // _H1: the hash function. A unary function object with argument type
59 // Key and result type size_t. Return values should be distributed
60 // over the entire range [0, numeric_limits<size_t>:::max()].
62 // _H2: the range-hashing function (in the terminology of Tavori and
63 // Dreizin). A binary function object whose argument types and result
64 // type are all size_t. Given arguments r and N, the return value is
65 // in the range [0, N).
67 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
68 // whose argument types are _Key and size_t and whose result type is
69 // size_t. Given arguments k and N, the return value is in the range
70 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
71 // than the default, _H1 and _H2 are ignored.
73 // _RehashPolicy: Policy class with three members, all of which govern
74 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
75 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
76 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
77 // determines whether, if the current bucket count is n_bkt and the
78 // current element count is n_elt, we need to increase the bucket
79 // count. If so, returns make_pair(true, n), where n is the new
80 // bucket count. If not, returns make_pair(false, <anything>).
82 // __cache_hash_code: bool. true if we store the value of the hash
83 // function along with the value. This is a time-space tradeoff.
84 // Storing it may improve lookup speed by reducing the number of times
85 // we need to call the Equal function.
87 // __constant_iterators: bool. true if iterator and const_iterator are
88 // both constant iterator types. This is true for unordered_set and
89 // unordered_multiset, false for unordered_map and unordered_multimap.
91 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
92 // is always at most one, false if it may be an arbitrary number. This
93 // true for unordered_set and unordered_map, false for unordered_multiset
94 // and unordered_multimap.
96 * Here's _Hashtable data structure, each _Hashtable has:
97 * - _Bucket[] _M_buckets
98 * - _Hash_node_base _M_before_begin
99 * - size_type _M_bucket_count
100 * - size_type _M_element_count
102 * with _Bucket being _Hash_node* and _Hash_node containing:
103 * - _Hash_node* _M_next
105 * - size_t _M_hash_code if cache_hash_code is true
107 * In terms of Standard containers the hashtable is like the aggregation of:
108 * - std::forward_list<_Node> containing the elements
109 * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
111 * The non-empty buckets contain the node before the first node in the
112 * bucket. This design makes it possible to implement something like a
113 * std::forward_list::insert_after on container insertion and
114 * std::forward_list::erase_after on container erase calls.
115 * _M_before_begin is equivalent to std::foward_list::before_begin.
116 * Empty buckets contain nullptr.
117 * Note that one of the non-empty buckets contains &_M_before_begin which is
118 * not a dereferenceable node so the node pointer in a bucket shall never be
119 * dereferenced, only its next node can be.
121 * Walking through a bucket's nodes requires a check on the hash code to see
122 * if each node is still in the bucket. Such a design assumes a quite
123 * efficient hash functor and is one of the reasons it is
124 * highly advisable to set __cache_hash_code to true.
126 * The container iterators are simply built from nodes. This way incrementing
127 * the iterator is perfectly efficient independent of how many empty buckets
128 * there are in the container.
130 * On insert we compute the element's hash code and use it to it find the
131 * bucket index. If the element must be inserted in an empty bucket we add
132 * it at the beginning of the singly linked list and make the bucket point to
133 * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
134 * is updated to point to its new before begin node.
136 * On erase, the simple iterator design requires using the hash functor to
137 * get the index of the bucket to update. For this reason, when
138 * __cache_hash_code is set to false, the hash functor must not throw
139 * and this is enforced by a statied assertion.
142 template<typename _Key, typename _Value, typename _Allocator,
143 typename _ExtractKey, typename _Equal,
144 typename _H1, typename _H2, typename _Hash,
145 typename _RehashPolicy,
146 bool __cache_hash_code,
147 bool __constant_iterators,
150 : public __detail::_Rehash_base<_RehashPolicy,
151 _Hashtable<_Key, _Value, _Allocator,
153 _Equal, _H1, _H2, _Hash,
156 __constant_iterators,
158 public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
159 _H1, _H2, _Hash, __cache_hash_code>,
160 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
161 _Hashtable<_Key, _Value, _Allocator,
163 _Equal, _H1, _H2, _Hash,
166 __constant_iterators,
168 public __detail::_Equality_base<_ExtractKey, __unique_keys,
169 _Hashtable<_Key, _Value, _Allocator,
171 _Equal, _H1, _H2, _Hash,
174 __constant_iterators,
177 template<typename _Cond>
178 using __if_hash_code_cached
179 = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
181 template<typename _Cond>
182 using __if_hash_code_not_cached
183 = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
185 // When hash codes are not cached the hash functor shall not throw
186 // because it is used in methods (erase, swap...) that shall not throw.
187 static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
189 "Cache the hash code or qualify your hash functor with noexcept");
191 // Following two static assertions are necessary to guarantee that
192 // swapping two hashtable instances won't invalidate associated local
195 // When hash codes are cached local iterator only uses H2 which must then
197 static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
198 "Functor used to map hash code to bucket index must be empty");
200 typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
202 __cache_hash_code> _HCBase;
204 // When hash codes are not cached local iterator is going to use _HCBase
205 // above to compute node bucket index so it has to be empty.
206 static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
207 "Cache the hash code or make functors involved in hash code"
208 " and bucket index computation empty");
211 typedef _Allocator allocator_type;
212 typedef _Value value_type;
213 typedef _Key key_type;
214 typedef _Equal key_equal;
215 // mapped_type, if present, comes from _Map_base.
216 // hasher, if present, comes from _Hash_code_base.
217 typedef typename _Allocator::pointer pointer;
218 typedef typename _Allocator::const_pointer const_pointer;
219 typedef typename _Allocator::reference reference;
220 typedef typename _Allocator::const_reference const_reference;
222 typedef std::size_t size_type;
223 typedef std::ptrdiff_t difference_type;
224 typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
226 __constant_iterators,
229 typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
231 __constant_iterators,
233 const_local_iterator;
234 typedef __detail::_Node_iterator<value_type, __constant_iterators,
237 typedef __detail::_Node_const_iterator<value_type,
238 __constant_iterators,
242 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
243 typename _Hashtable2>
244 friend struct __detail::_Map_base;
247 typedef typename _RehashPolicy::_State _RehashPolicyState;
248 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
249 typedef typename _Allocator::template rebind<_Node>::other
250 _Node_allocator_type;
251 typedef __detail::_Hash_node_base _BaseNode;
252 typedef _BaseNode* _Bucket;
253 typedef typename _Allocator::template rebind<_Bucket>::other
254 _Bucket_allocator_type;
256 typedef typename _Allocator::template rebind<_Value>::other
257 _Value_allocator_type;
259 _Node_allocator_type _M_node_allocator;
261 size_type _M_bucket_count;
262 _BaseNode _M_before_begin;
263 size_type _M_element_count;
264 _RehashPolicy _M_rehash_policy;
266 template<typename... _Args>
268 _M_allocate_node(_Args&&... __args);
271 _M_deallocate_node(_Node* __n);
273 // Deallocate the linked list of nodes pointed to by __n
275 _M_deallocate_nodes(_Node* __n);
278 _M_allocate_buckets(size_type __n);
281 _M_deallocate_buckets(_Bucket*, size_type __n);
283 // Gets bucket begin, deals with the fact that non-empty buckets contain
284 // their before begin node.
286 _M_bucket_begin(size_type __bkt) const;
290 { return static_cast<_Node*>(_M_before_begin._M_nxt); }
293 // Constructor, destructor, assignment, swap
294 _Hashtable(size_type __bucket_hint,
295 const _H1&, const _H2&, const _Hash&,
296 const _Equal&, const _ExtractKey&,
297 const allocator_type&);
299 template<typename _InputIterator>
300 _Hashtable(_InputIterator __first, _InputIterator __last,
301 size_type __bucket_hint,
302 const _H1&, const _H2&, const _Hash&,
303 const _Equal&, const _ExtractKey&,
304 const allocator_type&);
306 _Hashtable(const _Hashtable&);
308 _Hashtable(_Hashtable&&);
311 operator=(const _Hashtable& __ht)
313 _Hashtable __tmp(__ht);
319 operator=(_Hashtable&& __ht)
328 ~_Hashtable() noexcept;
330 void swap(_Hashtable&);
332 // Basic container operations
335 { return iterator(_M_begin()); }
338 begin() const noexcept
339 { return const_iterator(_M_begin()); }
343 { return iterator(nullptr); }
347 { return const_iterator(nullptr); }
350 cbegin() const noexcept
351 { return const_iterator(_M_begin()); }
354 cend() const noexcept
355 { return const_iterator(nullptr); }
358 size() const noexcept
359 { return _M_element_count; }
362 empty() const noexcept
363 { return size() == 0; }
366 get_allocator() const noexcept
367 { return allocator_type(_M_node_allocator); }
370 max_size() const noexcept
371 { return _M_node_allocator.max_size(); }
376 { return this->_M_eq(); }
378 // hash_function, if present, comes from _Hash_code_base.
382 bucket_count() const noexcept
383 { return _M_bucket_count; }
386 max_bucket_count() const noexcept
387 { return max_size(); }
390 bucket_size(size_type __n) const
391 { return std::distance(begin(__n), end(__n)); }
394 bucket(const key_type& __k) const
395 { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
399 { return local_iterator(_M_bucket_begin(__n), __n,
404 { return local_iterator(nullptr, __n, _M_bucket_count); }
407 begin(size_type __n) const
408 { return const_local_iterator(_M_bucket_begin(__n), __n,
412 end(size_type __n) const
413 { return const_local_iterator(nullptr, __n, _M_bucket_count); }
417 cbegin(size_type __n) const
418 { return const_local_iterator(_M_bucket_begin(__n), __n,
422 cend(size_type __n) const
423 { return const_local_iterator(nullptr, __n, _M_bucket_count); }
426 load_factor() const noexcept
428 return static_cast<float>(size()) / static_cast<float>(bucket_count());
431 // max_load_factor, if present, comes from _Rehash_base.
433 // Generalization of max_load_factor. Extension, not found in TR1. Only
434 // useful if _RehashPolicy is something other than the default.
436 __rehash_policy() const
437 { return _M_rehash_policy; }
440 __rehash_policy(const _RehashPolicy&);
444 find(const key_type& __k);
447 find(const key_type& __k) const;
450 count(const key_type& __k) const;
452 std::pair<iterator, iterator>
453 equal_range(const key_type& __k);
455 std::pair<const_iterator, const_iterator>
456 equal_range(const key_type& __k) const;
459 // Bucket index computation helpers.
461 _M_bucket_index(_Node* __n) const
462 { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
465 _M_bucket_index(const key_type& __k,
466 typename _Hashtable::_Hash_code_type __c) const
467 { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
469 // Find and insert helper functions and types
470 // Find the node before the one matching the criteria.
472 _M_find_before_node(size_type, const key_type&,
473 typename _Hashtable::_Hash_code_type) const;
476 _M_find_node(size_type __bkt, const key_type& __key,
477 typename _Hashtable::_Hash_code_type __c) const
479 _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
481 return static_cast<_Node*>(__before_n->_M_nxt);
485 // Insert a node at the beginning of a bucket.
487 _M_insert_bucket_begin(size_type, _Node*);
489 // Remove the bucket first node
491 _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
492 size_type __next_bkt);
494 // Get the node before __n in the bucket __bkt
496 _M_get_previous_node(size_type __bkt, _BaseNode* __n);
498 template<typename _Arg>
500 _M_insert_bucket(_Arg&&, size_type,
501 typename _Hashtable::_Hash_code_type);
503 typedef typename std::conditional<__unique_keys,
504 std::pair<iterator, bool>,
508 typedef typename std::conditional<__unique_keys,
509 std::_Select1st<_Insert_Return_Type>,
510 std::_Identity<_Insert_Return_Type>
515 template<typename... _Args>
516 std::pair<iterator, bool>
517 _M_emplace(std::true_type, _Args&&... __args);
519 template<typename... _Args>
521 _M_emplace(std::false_type, _Args&&... __args);
523 template<typename _Arg>
524 std::pair<iterator, bool>
525 _M_insert(_Arg&&, std::true_type);
527 template<typename _Arg>
529 _M_insert(_Arg&&, std::false_type);
532 // Emplace, insert and erase
533 template<typename... _Args>
535 emplace(_Args&&... __args)
536 { return _M_emplace(integral_constant<bool, __unique_keys>(),
537 std::forward<_Args>(__args)...); }
539 template<typename... _Args>
541 emplace_hint(const_iterator, _Args&&... __args)
542 { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
545 insert(const value_type& __v)
546 { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
549 insert(const_iterator, const value_type& __v)
550 { return _Insert_Conv_Type()(insert(__v)); }
552 template<typename _Pair, typename = typename
553 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
554 std::is_constructible<value_type,
555 _Pair&&>>::value>::type>
558 { return _M_insert(std::forward<_Pair>(__v),
559 integral_constant<bool, __unique_keys>()); }
561 template<typename _Pair, typename = typename
562 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
563 std::is_constructible<value_type,
564 _Pair&&>>::value>::type>
566 insert(const_iterator, _Pair&& __v)
567 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
569 template<typename _InputIterator>
571 insert(_InputIterator __first, _InputIterator __last);
574 insert(initializer_list<value_type> __l)
575 { this->insert(__l.begin(), __l.end()); }
578 erase(const_iterator);
583 { return erase(const_iterator(__it)); }
586 erase(const key_type&);
589 erase(const_iterator, const_iterator);
594 // Set number of buckets to be appropriate for container of n element.
595 void rehash(size_type __n);
598 // reserve, if present, comes from _Rehash_base.
601 // Helper rehash method used when keys are unique.
602 void _M_rehash_aux(size_type __n, std::true_type);
604 // Helper rehash method used when keys can be non-unique.
605 void _M_rehash_aux(size_type __n, std::false_type);
607 // Unconditionally change size of bucket array to n, restore hash policy
608 // state to __state on exception.
609 void _M_rehash(size_type __n, const _RehashPolicyState& __state);
613 // Definitions of class template _Hashtable's out-of-line member functions.
614 template<typename _Key, typename _Value,
615 typename _Allocator, typename _ExtractKey, typename _Equal,
616 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
617 bool __chc, bool __cit, bool __uk>
618 template<typename... _Args>
619 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
620 _H1, _H2, _Hash, _RehashPolicy,
621 __chc, __cit, __uk>::_Node*
622 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
623 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
624 _M_allocate_node(_Args&&... __args)
626 _Node* __n = _M_node_allocator.allocate(1);
629 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
634 _M_node_allocator.deallocate(__n, 1);
635 __throw_exception_again;
639 template<typename _Key, typename _Value,
640 typename _Allocator, typename _ExtractKey, typename _Equal,
641 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
642 bool __chc, bool __cit, bool __uk>
644 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
645 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
646 _M_deallocate_node(_Node* __n)
648 _M_node_allocator.destroy(__n);
649 _M_node_allocator.deallocate(__n, 1);
652 template<typename _Key, typename _Value,
653 typename _Allocator, typename _ExtractKey, typename _Equal,
654 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
655 bool __chc, bool __cit, bool __uk>
657 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
658 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
659 _M_deallocate_nodes(_Node* __n)
664 __n = __n->_M_next();
665 _M_deallocate_node(__tmp);
669 template<typename _Key, typename _Value,
670 typename _Allocator, typename _ExtractKey, typename _Equal,
671 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
672 bool __chc, bool __cit, bool __uk>
673 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
674 _H1, _H2, _Hash, _RehashPolicy,
675 __chc, __cit, __uk>::_Bucket*
676 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
677 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
678 _M_allocate_buckets(size_type __n)
680 _Bucket_allocator_type __alloc(_M_node_allocator);
682 _Bucket* __p = __alloc.allocate(__n);
683 __builtin_memset(__p, 0, __n * sizeof(_Bucket));
687 template<typename _Key, typename _Value,
688 typename _Allocator, typename _ExtractKey, typename _Equal,
689 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
690 bool __chc, bool __cit, bool __uk>
692 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
693 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
694 _M_deallocate_buckets(_Bucket* __p, size_type __n)
696 _Bucket_allocator_type __alloc(_M_node_allocator);
697 __alloc.deallocate(__p, __n);
700 template<typename _Key, typename _Value,
701 typename _Allocator, typename _ExtractKey, typename _Equal,
702 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
703 bool __chc, bool __cit, bool __uk>
704 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
705 _Equal, _H1, _H2, _Hash, _RehashPolicy,
706 __chc, __cit, __uk>::_Node*
707 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
708 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
709 _M_bucket_begin(size_type __bkt) const
711 _BaseNode* __n = _M_buckets[__bkt];
712 return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
715 template<typename _Key, typename _Value,
716 typename _Allocator, typename _ExtractKey, typename _Equal,
717 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
718 bool __chc, bool __cit, bool __uk>
719 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
720 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
721 _Hashtable(size_type __bucket_hint,
722 const _H1& __h1, const _H2& __h2, const _Hash& __h,
723 const _Equal& __eq, const _ExtractKey& __exk,
724 const allocator_type& __a)
725 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
726 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
727 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
729 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
730 _M_node_allocator(__a),
735 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
736 // We don't want the rehash policy to ask for the hashtable to shrink
737 // on the first insertion so we need to reset its previous resize level.
738 _M_rehash_policy._M_prev_resize = 0;
739 _M_buckets = _M_allocate_buckets(_M_bucket_count);
742 template<typename _Key, typename _Value,
743 typename _Allocator, typename _ExtractKey, typename _Equal,
744 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
745 bool __chc, bool __cit, bool __uk>
746 template<typename _InputIterator>
747 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
748 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
749 _Hashtable(_InputIterator __f, _InputIterator __l,
750 size_type __bucket_hint,
751 const _H1& __h1, const _H2& __h2, const _Hash& __h,
752 const _Equal& __eq, const _ExtractKey& __exk,
753 const allocator_type& __a)
754 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
755 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
756 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
758 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
759 _M_node_allocator(__a),
765 _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
767 if (_M_bucket_count <= __bucket_hint)
768 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
770 // We don't want the rehash policy to ask for the hashtable to shrink
771 // on the first insertion so we need to reset its previous resize
773 _M_rehash_policy._M_prev_resize = 0;
774 _M_buckets = _M_allocate_buckets(_M_bucket_count);
777 for (; __f != __l; ++__f)
783 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
784 __throw_exception_again;
788 template<typename _Key, typename _Value,
789 typename _Allocator, typename _ExtractKey, typename _Equal,
790 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
791 bool __chc, bool __cit, bool __uk>
792 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
793 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
794 _Hashtable(const _Hashtable& __ht)
795 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
796 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
797 _H1, _H2, _Hash, __chc>(__ht),
798 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
799 _M_node_allocator(__ht._M_node_allocator),
800 _M_bucket_count(__ht._M_bucket_count),
801 _M_element_count(__ht._M_element_count),
802 _M_rehash_policy(__ht._M_rehash_policy)
804 _M_buckets = _M_allocate_buckets(_M_bucket_count);
807 if (!__ht._M_before_begin._M_nxt)
810 // First deal with the special first node pointed to by
812 const _Node* __ht_n = __ht._M_begin();
813 _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
814 this->_M_copy_code(__this_n, __ht_n);
815 _M_before_begin._M_nxt = __this_n;
816 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
818 // Then deal with other nodes.
819 _BaseNode* __prev_n = __this_n;
820 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
822 __this_n = _M_allocate_node(__ht_n->_M_v);
823 __prev_n->_M_nxt = __this_n;
824 this->_M_copy_code(__this_n, __ht_n);
825 size_type __bkt = _M_bucket_index(__this_n);
826 if (!_M_buckets[__bkt])
827 _M_buckets[__bkt] = __prev_n;
834 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
835 __throw_exception_again;
839 template<typename _Key, typename _Value,
840 typename _Allocator, typename _ExtractKey, typename _Equal,
841 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
842 bool __chc, bool __cit, bool __uk>
843 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
844 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
845 _Hashtable(_Hashtable&& __ht)
846 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
847 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
848 _H1, _H2, _Hash, __chc>(__ht),
849 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
850 _M_node_allocator(std::move(__ht._M_node_allocator)),
851 _M_buckets(__ht._M_buckets),
852 _M_bucket_count(__ht._M_bucket_count),
853 _M_before_begin(__ht._M_before_begin._M_nxt),
854 _M_element_count(__ht._M_element_count),
855 _M_rehash_policy(__ht._M_rehash_policy)
857 // Update, if necessary, bucket pointing to before begin that hasn't move.
859 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
860 __ht._M_rehash_policy = _RehashPolicy();
861 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
862 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
863 __ht._M_before_begin._M_nxt = nullptr;
864 __ht._M_element_count = 0;
867 template<typename _Key, typename _Value,
868 typename _Allocator, typename _ExtractKey, typename _Equal,
869 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
870 bool __chc, bool __cit, bool __uk>
871 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
872 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
873 ~_Hashtable() noexcept
876 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
879 template<typename _Key, typename _Value,
880 typename _Allocator, typename _ExtractKey, typename _Equal,
881 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
882 bool __chc, bool __cit, bool __uk>
884 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
885 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
886 swap(_Hashtable& __x)
888 // The only base class with member variables is hash_code_base. We
889 // define _Hash_code_base::_M_swap because different specializations
890 // have different members.
893 // _GLIBCXX_RESOLVE_LIB_DEFECTS
894 // 431. Swapping containers with unequal allocators.
895 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
896 __x._M_node_allocator);
898 std::swap(_M_rehash_policy, __x._M_rehash_policy);
899 std::swap(_M_buckets, __x._M_buckets);
900 std::swap(_M_bucket_count, __x._M_bucket_count);
901 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
902 std::swap(_M_element_count, __x._M_element_count);
903 // Fix buckets containing the _M_before_begin pointers that can't be
906 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
908 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
909 = &(__x._M_before_begin);
912 template<typename _Key, typename _Value,
913 typename _Allocator, typename _ExtractKey, typename _Equal,
914 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
915 bool __chc, bool __cit, bool __uk>
917 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
918 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
919 __rehash_policy(const _RehashPolicy& __pol)
921 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
922 if (__n_bkt != _M_bucket_count)
923 _M_rehash(__n_bkt, _M_rehash_policy._M_state());
924 _M_rehash_policy = __pol;
927 template<typename _Key, typename _Value,
928 typename _Allocator, typename _ExtractKey, typename _Equal,
929 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
930 bool __chc, bool __cit, bool __uk>
931 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
932 _H1, _H2, _Hash, _RehashPolicy,
933 __chc, __cit, __uk>::iterator
934 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
935 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
936 find(const key_type& __k)
938 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
939 std::size_t __n = _M_bucket_index(__k, __code);
940 _Node* __p = _M_find_node(__n, __k, __code);
941 return __p ? iterator(__p) : this->end();
944 template<typename _Key, typename _Value,
945 typename _Allocator, typename _ExtractKey, typename _Equal,
946 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
947 bool __chc, bool __cit, bool __uk>
948 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
949 _H1, _H2, _Hash, _RehashPolicy,
950 __chc, __cit, __uk>::const_iterator
951 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
952 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
953 find(const key_type& __k) const
955 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
956 std::size_t __n = _M_bucket_index(__k, __code);
957 _Node* __p = _M_find_node(__n, __k, __code);
958 return __p ? const_iterator(__p) : this->end();
961 template<typename _Key, typename _Value,
962 typename _Allocator, typename _ExtractKey, typename _Equal,
963 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
964 bool __chc, bool __cit, bool __uk>
965 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
966 _H1, _H2, _Hash, _RehashPolicy,
967 __chc, __cit, __uk>::size_type
968 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
969 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
970 count(const key_type& __k) const
972 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
973 std::size_t __n = _M_bucket_index(__k, __code);
974 _Node* __p = _M_bucket_begin(__n);
978 std::size_t __result = 0;
979 for (;; __p = __p->_M_next())
981 if (this->_M_equals(__k, __code, __p))
984 // All equivalent values are next to each other, if we found a not
985 // equivalent value after an equivalent one it means that we won't
986 // find any more equivalent values.
988 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
994 template<typename _Key, typename _Value,
995 typename _Allocator, typename _ExtractKey, typename _Equal,
996 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
997 bool __chc, bool __cit, bool __uk>
998 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
999 _ExtractKey, _Equal, _H1,
1000 _H2, _Hash, _RehashPolicy,
1001 __chc, __cit, __uk>::iterator,
1002 typename _Hashtable<_Key, _Value, _Allocator,
1003 _ExtractKey, _Equal, _H1,
1004 _H2, _Hash, _RehashPolicy,
1005 __chc, __cit, __uk>::iterator>
1006 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1007 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1008 equal_range(const key_type& __k)
1010 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1011 std::size_t __n = _M_bucket_index(__k, __code);
1012 _Node* __p = _M_find_node(__n, __k, __code);
1016 _Node* __p1 = __p->_M_next();
1017 while (__p1 && _M_bucket_index(__p1) == __n
1018 && this->_M_equals(__k, __code, __p1))
1019 __p1 = __p1->_M_next();
1021 return std::make_pair(iterator(__p), iterator(__p1));
1024 return std::make_pair(this->end(), this->end());
1027 template<typename _Key, typename _Value,
1028 typename _Allocator, typename _ExtractKey, typename _Equal,
1029 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1030 bool __chc, bool __cit, bool __uk>
1031 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1032 _ExtractKey, _Equal, _H1,
1033 _H2, _Hash, _RehashPolicy,
1034 __chc, __cit, __uk>::const_iterator,
1035 typename _Hashtable<_Key, _Value, _Allocator,
1036 _ExtractKey, _Equal, _H1,
1037 _H2, _Hash, _RehashPolicy,
1038 __chc, __cit, __uk>::const_iterator>
1039 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1040 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1041 equal_range(const key_type& __k) const
1043 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1044 std::size_t __n = _M_bucket_index(__k, __code);
1045 _Node* __p = _M_find_node(__n, __k, __code);
1049 _Node* __p1 = __p->_M_next();
1050 while (__p1 && _M_bucket_index(__p1) == __n
1051 && this->_M_equals(__k, __code, __p1))
1052 __p1 = __p1->_M_next();
1054 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1057 return std::make_pair(this->end(), this->end());
1060 // Find the node whose key compares equal to k in the bucket n. Return nullptr
1061 // if no node is found.
1062 template<typename _Key, typename _Value,
1063 typename _Allocator, typename _ExtractKey, typename _Equal,
1064 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1065 bool __chc, bool __cit, bool __uk>
1066 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1067 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1068 __chc, __cit, __uk>::_BaseNode*
1069 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1070 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1071 _M_find_before_node(size_type __n, const key_type& __k,
1072 typename _Hashtable::_Hash_code_type __code) const
1074 _BaseNode* __prev_p = _M_buckets[__n];
1077 _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
1078 for (;; __p = __p->_M_next())
1080 if (this->_M_equals(__k, __code, __p))
1082 if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1089 template<typename _Key, typename _Value,
1090 typename _Allocator, typename _ExtractKey, typename _Equal,
1091 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1092 bool __chc, bool __cit, bool __uk>
1094 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1095 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1096 _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1098 if (_M_buckets[__bkt])
1100 // Bucket is not empty, we just need to insert the new node after the
1101 // bucket before begin.
1102 __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1103 _M_buckets[__bkt]->_M_nxt = __new_node;
1107 // The bucket is empty, the new node is inserted at the beginning of
1108 // the singly-linked list and the bucket will contain _M_before_begin
1110 __new_node->_M_nxt = _M_before_begin._M_nxt;
1111 _M_before_begin._M_nxt = __new_node;
1112 if (__new_node->_M_nxt)
1113 // We must update former begin bucket that is pointing to
1115 _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1116 _M_buckets[__bkt] = &_M_before_begin;
1120 template<typename _Key, typename _Value,
1121 typename _Allocator, typename _ExtractKey, typename _Equal,
1122 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1123 bool __chc, bool __cit, bool __uk>
1125 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1126 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1127 _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1129 if (!__next || __next_bkt != __bkt)
1131 // Bucket is now empty
1132 // First update next bucket if any
1134 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1135 // Second update before begin node if necessary
1136 if (&_M_before_begin == _M_buckets[__bkt])
1137 _M_before_begin._M_nxt = __next;
1138 _M_buckets[__bkt] = nullptr;
1142 template<typename _Key, typename _Value,
1143 typename _Allocator, typename _ExtractKey, typename _Equal,
1144 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1145 bool __chc, bool __cit, bool __uk>
1146 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1147 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1148 __chc, __cit, __uk>::_BaseNode*
1149 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1150 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1151 _M_get_previous_node(size_type __bkt, _BaseNode* __n)
1153 _BaseNode* __prev_n = _M_buckets[__bkt];
1154 while (__prev_n->_M_nxt != __n)
1155 __prev_n = __prev_n->_M_nxt;
1159 template<typename _Key, typename _Value,
1160 typename _Allocator, typename _ExtractKey, typename _Equal,
1161 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1162 bool __chc, bool __cit, bool __uk>
1163 template<typename... _Args>
1164 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1165 _ExtractKey, _Equal, _H1,
1166 _H2, _Hash, _RehashPolicy,
1167 __chc, __cit, __uk>::iterator, bool>
1168 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1169 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1170 _M_emplace(std::true_type, _Args&&... __args)
1172 // First build the node to get access to the hash code
1173 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1176 const key_type& __k = this->_M_extract()(__new_node->_M_v);
1177 typename _Hashtable::_Hash_code_type __code
1178 = this->_M_hash_code(__k);
1179 size_type __bkt = _M_bucket_index(__k, __code);
1181 if (_Node* __p = _M_find_node(__bkt, __k, __code))
1183 // There is already an equivalent node, no insertion
1184 _M_deallocate_node(__new_node);
1185 return std::make_pair(iterator(__p), false);
1188 // We are going to insert this node
1189 this->_M_store_code(__new_node, __code);
1190 const _RehashPolicyState& __saved_state
1191 = _M_rehash_policy._M_state();
1192 std::pair<bool, std::size_t> __do_rehash
1193 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1194 _M_element_count, 1);
1196 if (__do_rehash.first)
1198 _M_rehash(__do_rehash.second, __saved_state);
1199 __bkt = _M_bucket_index(__k, __code);
1202 _M_insert_bucket_begin(__bkt, __new_node);
1204 return std::make_pair(iterator(__new_node), true);
1208 _M_deallocate_node(__new_node);
1209 __throw_exception_again;
1213 template<typename _Key, typename _Value,
1214 typename _Allocator, typename _ExtractKey, typename _Equal,
1215 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1216 bool __chc, bool __cit, bool __uk>
1217 template<typename... _Args>
1218 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1219 _H1, _H2, _Hash, _RehashPolicy,
1220 __chc, __cit, __uk>::iterator
1221 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1222 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1223 _M_emplace(std::false_type, _Args&&... __args)
1225 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1226 std::pair<bool, std::size_t> __do_rehash
1227 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1228 _M_element_count, 1);
1230 // First build the node to get its hash code.
1231 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1234 const key_type& __k = this->_M_extract()(__new_node->_M_v);
1235 typename _Hashtable::_Hash_code_type __code
1236 = this->_M_hash_code(__k);
1237 this->_M_store_code(__new_node, __code);
1239 // Second, do rehash if necessary.
1240 if (__do_rehash.first)
1241 _M_rehash(__do_rehash.second, __saved_state);
1243 // Third, find the node before an equivalent one.
1244 size_type __bkt = _M_bucket_index(__k, __code);
1245 _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
1249 // Insert after the node before the equivalent one.
1250 __new_node->_M_nxt = __prev->_M_nxt;
1251 __prev->_M_nxt = __new_node;
1254 // The inserted node has no equivalent in the hashtable. We must
1255 // insert the new node at the beginning of the bucket to preserve
1256 // equivalent elements' relative positions.
1257 _M_insert_bucket_begin(__bkt, __new_node);
1259 return iterator(__new_node);
1263 _M_deallocate_node(__new_node);
1264 __throw_exception_again;
1268 // Insert v in bucket n (assumes no element with its key already present).
1269 template<typename _Key, typename _Value,
1270 typename _Allocator, typename _ExtractKey, typename _Equal,
1271 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1272 bool __chc, bool __cit, bool __uk>
1273 template<typename _Arg>
1274 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1275 _H1, _H2, _Hash, _RehashPolicy,
1276 __chc, __cit, __uk>::iterator
1277 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1278 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1279 _M_insert_bucket(_Arg&& __v, size_type __n,
1280 typename _Hashtable::_Hash_code_type __code)
1282 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1283 std::pair<bool, std::size_t> __do_rehash
1284 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1285 _M_element_count, 1);
1287 if (__do_rehash.first)
1289 const key_type& __k = this->_M_extract()(__v);
1290 __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1293 _Node* __new_node = nullptr;
1296 // Allocate the new node before doing the rehash so that we
1297 // don't do a rehash if the allocation throws.
1298 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1299 this->_M_store_code(__new_node, __code);
1300 if (__do_rehash.first)
1301 _M_rehash(__do_rehash.second, __saved_state);
1303 _M_insert_bucket_begin(__n, __new_node);
1305 return iterator(__new_node);
1310 _M_rehash_policy._M_reset(__saved_state);
1312 _M_deallocate_node(__new_node);
1313 __throw_exception_again;
1317 // Insert v if no element with its key is already present.
1318 template<typename _Key, typename _Value,
1319 typename _Allocator, typename _ExtractKey, typename _Equal,
1320 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1321 bool __chc, bool __cit, bool __uk>
1322 template<typename _Arg>
1323 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1324 _ExtractKey, _Equal, _H1,
1325 _H2, _Hash, _RehashPolicy,
1326 __chc, __cit, __uk>::iterator, bool>
1327 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1328 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1329 _M_insert(_Arg&& __v, std::true_type)
1331 const key_type& __k = this->_M_extract()(__v);
1332 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1333 size_type __n = _M_bucket_index(__k, __code);
1335 if (_Node* __p = _M_find_node(__n, __k, __code))
1336 return std::make_pair(iterator(__p), false);
1337 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
1338 __n, __code), true);
1341 // Insert v unconditionally.
1342 template<typename _Key, typename _Value,
1343 typename _Allocator, typename _ExtractKey, typename _Equal,
1344 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1345 bool __chc, bool __cit, bool __uk>
1346 template<typename _Arg>
1347 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1348 _H1, _H2, _Hash, _RehashPolicy,
1349 __chc, __cit, __uk>::iterator
1350 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1351 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1352 _M_insert(_Arg&& __v, std::false_type)
1354 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1355 std::pair<bool, std::size_t> __do_rehash
1356 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1357 _M_element_count, 1);
1359 // First compute the hash code so that we don't do anything if it throws.
1360 typename _Hashtable::_Hash_code_type __code
1361 = this->_M_hash_code(this->_M_extract()(__v));
1363 _Node* __new_node = nullptr;
1366 // Second allocate new node so that we don't rehash if it throws.
1367 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1368 this->_M_store_code(__new_node, __code);
1369 if (__do_rehash.first)
1370 _M_rehash(__do_rehash.second, __saved_state);
1372 // Third, find the node before an equivalent one.
1373 size_type __bkt = _M_bucket_index(__new_node);
1375 = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1379 // Insert after the node before the equivalent one.
1380 __new_node->_M_nxt = __prev->_M_nxt;
1381 __prev->_M_nxt = __new_node;
1384 // The inserted node has no equivalent in the hashtable. We must
1385 // insert the new node at the beginning of the bucket to preserve
1386 // equivalent elements relative positions.
1387 _M_insert_bucket_begin(__bkt, __new_node);
1389 return iterator(__new_node);
1394 _M_rehash_policy._M_reset(__saved_state);
1396 _M_deallocate_node(__new_node);
1397 __throw_exception_again;
1401 template<typename _Key, typename _Value,
1402 typename _Allocator, typename _ExtractKey, typename _Equal,
1403 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1404 bool __chc, bool __cit, bool __uk>
1405 template<typename _InputIterator>
1407 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1408 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1409 insert(_InputIterator __first, _InputIterator __last)
1411 size_type __n_elt = __detail::__distance_fw(__first, __last);
1412 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1413 std::pair<bool, std::size_t> __do_rehash
1414 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1415 _M_element_count, __n_elt);
1416 if (__do_rehash.first)
1417 _M_rehash(__do_rehash.second, __saved_state);
1419 for (; __first != __last; ++__first)
1420 this->insert(*__first);
1423 template<typename _Key, typename _Value,
1424 typename _Allocator, typename _ExtractKey, typename _Equal,
1425 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1426 bool __chc, bool __cit, bool __uk>
1427 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1428 _H1, _H2, _Hash, _RehashPolicy,
1429 __chc, __cit, __uk>::iterator
1430 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1431 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1432 erase(const_iterator __it)
1434 _Node* __n = __it._M_cur;
1435 std::size_t __bkt = _M_bucket_index(__n);
1437 // Look for previous node to unlink it from the erased one, this is why
1438 // we need buckets to contain the before begin to make this search fast.
1439 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1440 if (__n == _M_bucket_begin(__bkt))
1441 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1442 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1443 else if (__n->_M_nxt)
1445 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1446 if (__next_bkt != __bkt)
1447 _M_buckets[__next_bkt] = __prev_n;
1450 __prev_n->_M_nxt = __n->_M_nxt;
1451 iterator __result(__n->_M_next());
1452 _M_deallocate_node(__n);
1458 template<typename _Key, typename _Value,
1459 typename _Allocator, typename _ExtractKey, typename _Equal,
1460 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1461 bool __chc, bool __cit, bool __uk>
1462 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1463 _H1, _H2, _Hash, _RehashPolicy,
1464 __chc, __cit, __uk>::size_type
1465 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1466 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1467 erase(const key_type& __k)
1469 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1470 std::size_t __bkt = _M_bucket_index(__k, __code);
1471 // Look for the node before the first matching node.
1472 _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
1475 _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
1476 bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1478 // We found a matching node, start deallocation loop from it
1479 std::size_t __next_bkt = __bkt;
1480 _Node* __next_n = __n;
1481 size_type __result = 0;
1482 _Node* __saved_n = nullptr;
1485 _Node* __p = __next_n;
1486 __next_n = __p->_M_next();
1487 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1488 // 526. Is it undefined if a function in the standard changes
1490 if (std::__addressof(this->_M_extract()(__p->_M_v))
1491 != std::__addressof(__k))
1492 _M_deallocate_node(__p);
1499 __next_bkt = _M_bucket_index(__next_n);
1501 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1504 _M_deallocate_node(__saved_n);
1505 if (__is_bucket_begin)
1506 _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1507 else if (__next_n && __next_bkt != __bkt)
1508 _M_buckets[__next_bkt] = __prev_n;
1510 __prev_n->_M_nxt = __next_n;
1514 template<typename _Key, typename _Value,
1515 typename _Allocator, typename _ExtractKey, typename _Equal,
1516 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1517 bool __chc, bool __cit, bool __uk>
1518 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1519 _H1, _H2, _Hash, _RehashPolicy,
1520 __chc, __cit, __uk>::iterator
1521 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1522 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1523 erase(const_iterator __first, const_iterator __last)
1525 _Node* __n = __first._M_cur;
1526 _Node* __last_n = __last._M_cur;
1527 if (__n == __last_n)
1528 return iterator(__n);
1530 std::size_t __bkt = _M_bucket_index(__n);
1532 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1533 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1534 std::size_t __n_bkt = __bkt;
1540 __n = __n->_M_next();
1541 _M_deallocate_node(__tmp);
1545 __n_bkt = _M_bucket_index(__n);
1547 while (__n != __last_n && __n_bkt == __bkt);
1548 if (__is_bucket_begin)
1549 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1550 if (__n == __last_n)
1552 __is_bucket_begin = true;
1556 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1557 _M_buckets[__n_bkt] = __prev_n;
1558 __prev_n->_M_nxt = __n;
1559 return iterator(__n);
1562 template<typename _Key, typename _Value,
1563 typename _Allocator, typename _ExtractKey, typename _Equal,
1564 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1565 bool __chc, bool __cit, bool __uk>
1567 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1568 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1571 _M_deallocate_nodes(_M_begin());
1572 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
1573 _M_element_count = 0;
1574 _M_before_begin._M_nxt = nullptr;
1577 template<typename _Key, typename _Value,
1578 typename _Allocator, typename _ExtractKey, typename _Equal,
1579 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1580 bool __chc, bool __cit, bool __uk>
1582 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1583 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1584 rehash(size_type __n)
1586 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1587 std::size_t __buckets
1588 = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
1589 if (__buckets <= __n)
1590 __buckets = _M_rehash_policy._M_next_bkt(__n);
1592 if (__buckets != _M_bucket_count)
1594 _M_rehash(__buckets, __saved_state);
1596 // We don't want the rehash policy to ask for the hashtable to shrink
1597 // on the next insertion so we need to reset its previous resize
1599 _M_rehash_policy._M_prev_resize = 0;
1602 // No rehash, restore previous state to keep a consistent state.
1603 _M_rehash_policy._M_reset(__saved_state);
1606 template<typename _Key, typename _Value,
1607 typename _Allocator, typename _ExtractKey, typename _Equal,
1608 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1609 bool __chc, bool __cit, bool __uk>
1611 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1612 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1613 _M_rehash(size_type __n, const _RehashPolicyState& __state)
1617 _M_rehash_aux(__n, integral_constant<bool, __uk>());
1621 // A failure here means that buckets allocation failed. We only
1622 // have to restore hash policy previous state.
1623 _M_rehash_policy._M_reset(__state);
1624 __throw_exception_again;
1628 // Rehash when there is no equivalent elements.
1629 template<typename _Key, typename _Value,
1630 typename _Allocator, typename _ExtractKey, typename _Equal,
1631 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1632 bool __chc, bool __cit, bool __uk>
1634 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1635 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1636 _M_rehash_aux(size_type __n, std::true_type)
1638 _Bucket* __new_buckets = _M_allocate_buckets(__n);
1639 _Node* __p = _M_begin();
1640 _M_before_begin._M_nxt = nullptr;
1641 std::size_t __bbegin_bkt = 0;
1644 _Node* __next = __p->_M_next();
1645 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1646 if (!__new_buckets[__bkt])
1648 __p->_M_nxt = _M_before_begin._M_nxt;
1649 _M_before_begin._M_nxt = __p;
1650 __new_buckets[__bkt] = &_M_before_begin;
1652 __new_buckets[__bbegin_bkt] = __p;
1653 __bbegin_bkt = __bkt;
1657 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1658 __new_buckets[__bkt]->_M_nxt = __p;
1662 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1663 _M_bucket_count = __n;
1664 _M_buckets = __new_buckets;
1667 // Rehash when there can be equivalent elements, preserve their relative
1669 template<typename _Key, typename _Value,
1670 typename _Allocator, typename _ExtractKey, typename _Equal,
1671 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1672 bool __chc, bool __cit, bool __uk>
1674 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1675 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1676 _M_rehash_aux(size_type __n, std::false_type)
1678 _Bucket* __new_buckets = _M_allocate_buckets(__n);
1680 _Node* __p = _M_begin();
1681 _M_before_begin._M_nxt = nullptr;
1682 std::size_t __bbegin_bkt = 0;
1683 std::size_t __prev_bkt = 0;
1684 _Node* __prev_p = nullptr;
1685 bool __check_bucket = false;
1689 _Node* __next = __p->_M_next();
1690 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1692 if (__prev_p && __prev_bkt == __bkt)
1694 // Previous insert was already in this bucket, we insert after
1695 // the previously inserted one to preserve equivalent elements
1697 __p->_M_nxt = __prev_p->_M_nxt;
1698 __prev_p->_M_nxt = __p;
1700 // Inserting after a node in a bucket require to check that we
1701 // haven't change the bucket last node, in this case next
1702 // bucket containing its before begin node must be updated. We
1703 // schedule a check as soon as we move out of the sequence of
1704 // equivalent nodes to limit the number of checks.
1705 __check_bucket = true;
1711 // Check if we shall update the next bucket because of
1712 // insertions into __prev_bkt bucket.
1713 if (__prev_p->_M_nxt)
1715 std::size_t __next_bkt
1716 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1717 if (__next_bkt != __prev_bkt)
1718 __new_buckets[__next_bkt] = __prev_p;
1720 __check_bucket = false;
1722 if (!__new_buckets[__bkt])
1724 __p->_M_nxt = _M_before_begin._M_nxt;
1725 _M_before_begin._M_nxt = __p;
1726 __new_buckets[__bkt] = &_M_before_begin;
1728 __new_buckets[__bbegin_bkt] = __p;
1729 __bbegin_bkt = __bkt;
1733 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1734 __new_buckets[__bkt]->_M_nxt = __p;
1743 if (__check_bucket && __prev_p->_M_nxt)
1745 std::size_t __next_bkt
1746 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1747 if (__next_bkt != __prev_bkt)
1748 __new_buckets[__next_bkt] = __prev_p;
1751 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1752 _M_bucket_count = __n;
1753 _M_buckets = __new_buckets;
1756 _GLIBCXX_END_NAMESPACE_VERSION
1759 #endif // _HASHTABLE_H