1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
26 /** @file bits/hashtable.h
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
32 #define _HASHTABLE_H 1
34 #pragma GCC system_header
36 #include <bits/hashtable_policy.h>
38 namespace std _GLIBCXX_VISIBILITY(default)
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42 // 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 constaining:
103 * - _Hash_node* _M_next
105 * - size_t _M_code if cache_hash_code is true
107 * In terms of Standard containers the hastable 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 bucket node. This
112 * design allow to implement something like a std::forward_list::insert_after
113 * on container insertion and std::forward_list::erase_after on container
114 * erase calls. _M_before_begin is equivalent to
115 * std::foward_list::before_begin. Empty buckets are containing nullptr.
116 * Note that one of the non-empty bucket contains &_M_before_begin which is
117 * not a derefenrenceable node so the node pointers in buckets shall never be
118 * derefenrenced, only its next node can be.
120 * Walk through a bucket nodes require a check on the hash code to see if the
121 * node is still in the bucket. Such a design impose a quite efficient hash
122 * functor and is one of the reasons it is highly advise to set
123 * __cache_hash_code to true.
125 * The container iterators are simply built from nodes. This way incrementing
126 * the iterator is perfectly efficient independent of how many empty buckets
127 * there are in the container.
129 * On insert we compute element hash code and thanks to it find the bucket
130 * index. If the element must be inserted on an empty bucket we add it at the
131 * beginning of the singly linked list and make the bucket point to
132 * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
133 * is updated to point to its new before begin node.
135 * On erase, the simple iterator design impose to use the hash functor to get
136 * the index of the bucket to update. For this reason, when __cache_hash_code
137 * is set to false, there is a static assertion that the hash functor cannot
141 template<typename _Key, typename _Value, typename _Allocator,
142 typename _ExtractKey, typename _Equal,
143 typename _H1, typename _H2, typename _Hash,
144 typename _RehashPolicy,
145 bool __cache_hash_code,
146 bool __constant_iterators,
149 : public __detail::_Rehash_base<_RehashPolicy,
150 _Hashtable<_Key, _Value, _Allocator,
152 _Equal, _H1, _H2, _Hash,
155 __constant_iterators,
157 public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
158 _H1, _H2, _Hash, __cache_hash_code>,
159 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
160 _Hashtable<_Key, _Value, _Allocator,
162 _Equal, _H1, _H2, _Hash,
165 __constant_iterators,
167 public __detail::_Equality_base<_ExtractKey, __unique_keys,
168 _Hashtable<_Key, _Value, _Allocator,
170 _Equal, _H1, _H2, _Hash,
173 __constant_iterators,
176 template<typename _Cond>
177 using __if_hash_code_cached
178 = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
180 template<typename _Cond>
181 using __if_hash_code_not_cached
182 = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
184 // When hash codes are not cached the hash functor shall not throw
185 // because it is used in methods (erase, swap...) that shall not throw.
186 static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
188 "Cache the hash code or qualify your hash functor with noexcept");
190 // Following two static assertions are necessary to guarantee that
191 // swapping two hashtable instances won't invalidate associated local
194 // When hash codes are cached local iterator only uses H2 which must then
196 static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
197 "Functor used to map hash code to bucket index must be empty");
199 typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
201 __cache_hash_code> _HCBase;
203 // When hash codes are not cached local iterator is going to use _HCBase
204 // above to compute node bucket index so it has to be empty.
205 static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
206 "Cache the hash code or make functors involved in hash code"
207 " and bucket index computation empty");
210 typedef _Allocator allocator_type;
211 typedef _Value value_type;
212 typedef _Key key_type;
213 typedef _Equal key_equal;
214 // mapped_type, if present, comes from _Map_base.
215 // hasher, if present, comes from _Hash_code_base.
216 typedef typename _Allocator::pointer pointer;
217 typedef typename _Allocator::const_pointer const_pointer;
218 typedef typename _Allocator::reference reference;
219 typedef typename _Allocator::const_reference const_reference;
221 typedef std::size_t size_type;
222 typedef std::ptrdiff_t difference_type;
223 typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
225 __constant_iterators,
228 typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
230 __constant_iterators,
232 const_local_iterator;
233 typedef __detail::_Node_iterator<value_type, __constant_iterators,
236 typedef __detail::_Node_const_iterator<value_type,
237 __constant_iterators,
241 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
242 typename _Hashtable2>
243 friend struct __detail::_Map_base;
246 typedef typename _RehashPolicy::_State _RehashPolicyState;
247 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
248 typedef typename _Allocator::template rebind<_Node>::other
249 _Node_allocator_type;
250 typedef __detail::_Hash_node_base _BaseNode;
251 typedef _BaseNode* _Bucket;
252 typedef typename _Allocator::template rebind<_Bucket>::other
253 _Bucket_allocator_type;
255 typedef typename _Allocator::template rebind<_Value>::other
256 _Value_allocator_type;
258 _Node_allocator_type _M_node_allocator;
260 size_type _M_bucket_count;
261 _BaseNode _M_before_begin;
262 size_type _M_element_count;
263 _RehashPolicy _M_rehash_policy;
265 template<typename... _Args>
267 _M_allocate_node(_Args&&... __args);
270 _M_deallocate_node(_Node* __n);
272 // Deallocate the linked list of nodes pointed to by __n
274 _M_deallocate_nodes(_Node* __n);
277 _M_allocate_buckets(size_type __n);
280 _M_deallocate_buckets(_Bucket*, size_type __n);
282 // Gets bucket begin, deals with the fact that non-empty buckets contain
283 // their before begin node.
285 _M_bucket_begin(size_type __bkt) const;
289 { return static_cast<_Node*>(_M_before_begin._M_nxt); }
292 // Constructor, destructor, assignment, swap
293 _Hashtable(size_type __bucket_hint,
294 const _H1&, const _H2&, const _Hash&,
295 const _Equal&, const _ExtractKey&,
296 const allocator_type&);
298 template<typename _InputIterator>
299 _Hashtable(_InputIterator __first, _InputIterator __last,
300 size_type __bucket_hint,
301 const _H1&, const _H2&, const _Hash&,
302 const _Equal&, const _ExtractKey&,
303 const allocator_type&);
305 _Hashtable(const _Hashtable&);
307 _Hashtable(_Hashtable&&);
310 operator=(const _Hashtable& __ht)
312 _Hashtable __tmp(__ht);
318 operator=(_Hashtable&& __ht)
327 ~_Hashtable() noexcept;
329 void swap(_Hashtable&);
331 // Basic container operations
334 { return iterator(_M_begin()); }
337 begin() const noexcept
338 { return const_iterator(_M_begin()); }
342 { return iterator(nullptr); }
346 { return const_iterator(nullptr); }
349 cbegin() const noexcept
350 { return const_iterator(_M_begin()); }
353 cend() const noexcept
354 { return const_iterator(nullptr); }
357 size() const noexcept
358 { return _M_element_count; }
361 empty() const noexcept
362 { return size() == 0; }
365 get_allocator() const noexcept
366 { return allocator_type(_M_node_allocator); }
369 max_size() const noexcept
370 { return _M_node_allocator.max_size(); }
375 { return this->_M_eq(); }
377 // hash_function, if present, comes from _Hash_code_base.
381 bucket_count() const noexcept
382 { return _M_bucket_count; }
385 max_bucket_count() const noexcept
386 { return max_size(); }
389 bucket_size(size_type __n) const
390 { return std::distance(begin(__n), end(__n)); }
393 bucket(const key_type& __k) const
394 { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
398 { return local_iterator(_M_bucket_begin(__n), __n,
403 { return local_iterator(nullptr, __n, _M_bucket_count); }
406 begin(size_type __n) const
407 { return const_local_iterator(_M_bucket_begin(__n), __n,
411 end(size_type __n) const
412 { return const_local_iterator(nullptr, __n, _M_bucket_count); }
416 cbegin(size_type __n) const
417 { return const_local_iterator(_M_bucket_begin(__n), __n,
421 cend(size_type __n) const
422 { return const_local_iterator(nullptr, __n, _M_bucket_count); }
425 load_factor() const noexcept
427 return static_cast<float>(size()) / static_cast<float>(bucket_count());
430 // max_load_factor, if present, comes from _Rehash_base.
432 // Generalization of max_load_factor. Extension, not found in TR1. Only
433 // useful if _RehashPolicy is something other than the default.
435 __rehash_policy() const
436 { return _M_rehash_policy; }
439 __rehash_policy(const _RehashPolicy&);
443 find(const key_type& __k);
446 find(const key_type& __k) const;
449 count(const key_type& __k) const;
451 std::pair<iterator, iterator>
452 equal_range(const key_type& __k);
454 std::pair<const_iterator, const_iterator>
455 equal_range(const key_type& __k) const;
458 // Bucket index computation helpers.
460 _M_bucket_index(_Node* __n) const
461 { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
464 _M_bucket_index(const key_type& __k,
465 typename _Hashtable::_Hash_code_type __c) const
466 { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
468 // Find and insert helper functions and types
469 // Find the node before the one matching the criteria.
471 _M_find_before_node(size_type, const key_type&,
472 typename _Hashtable::_Hash_code_type) const;
475 _M_find_node(size_type __bkt, const key_type& __key,
476 typename _Hashtable::_Hash_code_type __c) const
478 _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
480 return static_cast<_Node*>(__before_n->_M_nxt);
484 // Insert a node at the beginning of a bucket.
486 _M_insert_bucket_begin(size_type, _Node*);
488 // Remove the bucket first node
490 _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
491 size_type __next_bkt);
493 // Get the node before __n in the bucket __bkt
495 _M_get_previous_node(size_type __bkt, _BaseNode* __n);
497 template<typename _Arg>
499 _M_insert_bucket(_Arg&&, size_type,
500 typename _Hashtable::_Hash_code_type);
502 typedef typename std::conditional<__unique_keys,
503 std::pair<iterator, bool>,
507 typedef typename std::conditional<__unique_keys,
508 std::_Select1st<_Insert_Return_Type>,
509 std::_Identity<_Insert_Return_Type>
514 template<typename... _Args>
515 std::pair<iterator, bool>
516 _M_emplace(std::true_type, _Args&&... __args);
518 template<typename... _Args>
520 _M_emplace(std::false_type, _Args&&... __args);
522 template<typename _Arg>
523 std::pair<iterator, bool>
524 _M_insert(_Arg&&, std::true_type);
526 template<typename _Arg>
528 _M_insert(_Arg&&, std::false_type);
531 // Emplace, insert and erase
532 template<typename... _Args>
534 emplace(_Args&&... __args)
535 { return _M_emplace(integral_constant<bool, __unique_keys>(),
536 std::forward<_Args>(__args)...); }
538 template<typename... _Args>
540 emplace_hint(const_iterator, _Args&&... __args)
541 { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
544 insert(const value_type& __v)
545 { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
548 insert(const_iterator, const value_type& __v)
549 { return _Insert_Conv_Type()(insert(__v)); }
551 template<typename _Pair, typename = typename
552 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
553 std::is_constructible<value_type,
554 _Pair&&>>::value>::type>
557 { return _M_insert(std::forward<_Pair>(__v),
558 integral_constant<bool, __unique_keys>()); }
560 template<typename _Pair, typename = typename
561 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
562 std::is_constructible<value_type,
563 _Pair&&>>::value>::type>
565 insert(const_iterator, _Pair&& __v)
566 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
568 template<typename _InputIterator>
570 insert(_InputIterator __first, _InputIterator __last);
573 insert(initializer_list<value_type> __l)
574 { this->insert(__l.begin(), __l.end()); }
577 erase(const_iterator);
582 { return erase(const_iterator(__it)); }
585 erase(const key_type&);
588 erase(const_iterator, const_iterator);
593 // Set number of buckets to be appropriate for container of n element.
594 void rehash(size_type __n);
597 // reserve, if present, comes from _Rehash_base.
600 // Helper rehash method used when keys are unique.
601 void _M_rehash_aux(size_type __n, std::true_type);
603 // Helper rehash method used when keys can be non-unique.
604 void _M_rehash_aux(size_type __n, std::false_type);
606 // Unconditionally change size of bucket array to n, restore hash policy
607 // state to __state on exception.
608 void _M_rehash(size_type __n, const _RehashPolicyState& __state);
612 // Definitions of class template _Hashtable's out-of-line member functions.
613 template<typename _Key, typename _Value,
614 typename _Allocator, typename _ExtractKey, typename _Equal,
615 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
616 bool __chc, bool __cit, bool __uk>
617 template<typename... _Args>
618 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
619 _H1, _H2, _Hash, _RehashPolicy,
620 __chc, __cit, __uk>::_Node*
621 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
622 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
623 _M_allocate_node(_Args&&... __args)
625 _Node* __n = _M_node_allocator.allocate(1);
628 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
633 _M_node_allocator.deallocate(__n, 1);
634 __throw_exception_again;
638 template<typename _Key, typename _Value,
639 typename _Allocator, typename _ExtractKey, typename _Equal,
640 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
641 bool __chc, bool __cit, bool __uk>
643 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
644 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
645 _M_deallocate_node(_Node* __n)
647 _M_node_allocator.destroy(__n);
648 _M_node_allocator.deallocate(__n, 1);
651 template<typename _Key, typename _Value,
652 typename _Allocator, typename _ExtractKey, typename _Equal,
653 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
654 bool __chc, bool __cit, bool __uk>
656 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
657 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
658 _M_deallocate_nodes(_Node* __n)
663 __n = __n->_M_next();
664 _M_deallocate_node(__tmp);
668 template<typename _Key, typename _Value,
669 typename _Allocator, typename _ExtractKey, typename _Equal,
670 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
671 bool __chc, bool __cit, bool __uk>
672 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
673 _H1, _H2, _Hash, _RehashPolicy,
674 __chc, __cit, __uk>::_Bucket*
675 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
676 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
677 _M_allocate_buckets(size_type __n)
679 _Bucket_allocator_type __alloc(_M_node_allocator);
681 _Bucket* __p = __alloc.allocate(__n);
682 __builtin_memset(__p, 0, __n * sizeof(_Bucket));
686 template<typename _Key, typename _Value,
687 typename _Allocator, typename _ExtractKey, typename _Equal,
688 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
689 bool __chc, bool __cit, bool __uk>
691 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
692 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
693 _M_deallocate_buckets(_Bucket* __p, size_type __n)
695 _Bucket_allocator_type __alloc(_M_node_allocator);
696 __alloc.deallocate(__p, __n);
699 template<typename _Key, typename _Value,
700 typename _Allocator, typename _ExtractKey, typename _Equal,
701 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
702 bool __chc, bool __cit, bool __uk>
703 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
704 _Equal, _H1, _H2, _Hash, _RehashPolicy,
705 __chc, __cit, __uk>::_Node*
706 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
707 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
708 _M_bucket_begin(size_type __bkt) const
710 _BaseNode* __n = _M_buckets[__bkt];
711 return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
714 template<typename _Key, typename _Value,
715 typename _Allocator, typename _ExtractKey, typename _Equal,
716 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
717 bool __chc, bool __cit, bool __uk>
718 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
719 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
720 _Hashtable(size_type __bucket_hint,
721 const _H1& __h1, const _H2& __h2, const _Hash& __h,
722 const _Equal& __eq, const _ExtractKey& __exk,
723 const allocator_type& __a)
724 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
725 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
726 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
728 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
729 _M_node_allocator(__a),
734 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
735 // We don't want the rehash policy to ask for the hashtable to shrink
736 // on the first insertion so we need to reset its previous resize level.
737 _M_rehash_policy._M_prev_resize = 0;
738 _M_buckets = _M_allocate_buckets(_M_bucket_count);
741 template<typename _Key, typename _Value,
742 typename _Allocator, typename _ExtractKey, typename _Equal,
743 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
744 bool __chc, bool __cit, bool __uk>
745 template<typename _InputIterator>
746 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
747 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
748 _Hashtable(_InputIterator __f, _InputIterator __l,
749 size_type __bucket_hint,
750 const _H1& __h1, const _H2& __h2, const _Hash& __h,
751 const _Equal& __eq, const _ExtractKey& __exk,
752 const allocator_type& __a)
753 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
754 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
755 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
757 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
758 _M_node_allocator(__a),
764 _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
766 if (_M_bucket_count <= __bucket_hint)
767 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
769 // We don't want the rehash policy to ask for the hashtable to shrink
770 // on the first insertion so we need to reset its previous resize
772 _M_rehash_policy._M_prev_resize = 0;
773 _M_buckets = _M_allocate_buckets(_M_bucket_count);
776 for (; __f != __l; ++__f)
782 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
783 __throw_exception_again;
787 template<typename _Key, typename _Value,
788 typename _Allocator, typename _ExtractKey, typename _Equal,
789 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
790 bool __chc, bool __cit, bool __uk>
791 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
792 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
793 _Hashtable(const _Hashtable& __ht)
794 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
795 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
796 _H1, _H2, _Hash, __chc>(__ht),
797 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
798 _M_node_allocator(__ht._M_node_allocator),
799 _M_bucket_count(__ht._M_bucket_count),
800 _M_element_count(__ht._M_element_count),
801 _M_rehash_policy(__ht._M_rehash_policy)
803 _M_buckets = _M_allocate_buckets(_M_bucket_count);
806 if (!__ht._M_before_begin._M_nxt)
809 // First deal with the special first node pointed to by
811 const _Node* __ht_n = __ht._M_begin();
812 _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
813 this->_M_copy_code(__this_n, __ht_n);
814 _M_before_begin._M_nxt = __this_n;
815 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
817 // Then deal with other nodes.
818 _BaseNode* __prev_n = __this_n;
819 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
821 __this_n = _M_allocate_node(__ht_n->_M_v);
822 __prev_n->_M_nxt = __this_n;
823 this->_M_copy_code(__this_n, __ht_n);
824 size_type __bkt = _M_bucket_index(__this_n);
825 if (!_M_buckets[__bkt])
826 _M_buckets[__bkt] = __prev_n;
833 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
834 __throw_exception_again;
838 template<typename _Key, typename _Value,
839 typename _Allocator, typename _ExtractKey, typename _Equal,
840 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
841 bool __chc, bool __cit, bool __uk>
842 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
843 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
844 _Hashtable(_Hashtable&& __ht)
845 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
846 __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
847 _H1, _H2, _Hash, __chc>(__ht),
848 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
849 _M_node_allocator(std::move(__ht._M_node_allocator)),
850 _M_buckets(__ht._M_buckets),
851 _M_bucket_count(__ht._M_bucket_count),
852 _M_before_begin(__ht._M_before_begin._M_nxt),
853 _M_element_count(__ht._M_element_count),
854 _M_rehash_policy(__ht._M_rehash_policy)
856 // Update, if necessary, bucket pointing to before begin that hasn't move.
858 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
859 __ht._M_rehash_policy = _RehashPolicy();
860 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
861 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
862 __ht._M_before_begin._M_nxt = nullptr;
863 __ht._M_element_count = 0;
866 template<typename _Key, typename _Value,
867 typename _Allocator, typename _ExtractKey, typename _Equal,
868 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
869 bool __chc, bool __cit, bool __uk>
870 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
871 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
872 ~_Hashtable() noexcept
875 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
878 template<typename _Key, typename _Value,
879 typename _Allocator, typename _ExtractKey, typename _Equal,
880 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
881 bool __chc, bool __cit, bool __uk>
883 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
884 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
885 swap(_Hashtable& __x)
887 // The only base class with member variables is hash_code_base. We
888 // define _Hash_code_base::_M_swap because different specializations
889 // have different members.
892 // _GLIBCXX_RESOLVE_LIB_DEFECTS
893 // 431. Swapping containers with unequal allocators.
894 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
895 __x._M_node_allocator);
897 std::swap(_M_rehash_policy, __x._M_rehash_policy);
898 std::swap(_M_buckets, __x._M_buckets);
899 std::swap(_M_bucket_count, __x._M_bucket_count);
900 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
901 std::swap(_M_element_count, __x._M_element_count);
902 // Fix buckets containing the _M_before_begin pointers that can't be
905 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
907 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
908 = &(__x._M_before_begin);
911 template<typename _Key, typename _Value,
912 typename _Allocator, typename _ExtractKey, typename _Equal,
913 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
914 bool __chc, bool __cit, bool __uk>
916 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
917 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
918 __rehash_policy(const _RehashPolicy& __pol)
920 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
921 if (__n_bkt != _M_bucket_count)
922 _M_rehash(__n_bkt, _M_rehash_policy._M_state());
923 _M_rehash_policy = __pol;
926 template<typename _Key, typename _Value,
927 typename _Allocator, typename _ExtractKey, typename _Equal,
928 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
929 bool __chc, bool __cit, bool __uk>
930 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
931 _H1, _H2, _Hash, _RehashPolicy,
932 __chc, __cit, __uk>::iterator
933 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
934 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
935 find(const key_type& __k)
937 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
938 std::size_t __n = _M_bucket_index(__k, __code);
939 _Node* __p = _M_find_node(__n, __k, __code);
940 return __p ? iterator(__p) : this->end();
943 template<typename _Key, typename _Value,
944 typename _Allocator, typename _ExtractKey, typename _Equal,
945 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
946 bool __chc, bool __cit, bool __uk>
947 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
948 _H1, _H2, _Hash, _RehashPolicy,
949 __chc, __cit, __uk>::const_iterator
950 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
951 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
952 find(const key_type& __k) const
954 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
955 std::size_t __n = _M_bucket_index(__k, __code);
956 _Node* __p = _M_find_node(__n, __k, __code);
957 return __p ? const_iterator(__p) : this->end();
960 template<typename _Key, typename _Value,
961 typename _Allocator, typename _ExtractKey, typename _Equal,
962 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
963 bool __chc, bool __cit, bool __uk>
964 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
965 _H1, _H2, _Hash, _RehashPolicy,
966 __chc, __cit, __uk>::size_type
967 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
968 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
969 count(const key_type& __k) const
971 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
972 std::size_t __n = _M_bucket_index(__k, __code);
973 _Node* __p = _M_bucket_begin(__n);
977 std::size_t __result = 0;
978 for (;; __p = __p->_M_next())
980 if (this->_M_equals(__k, __code, __p))
983 // All equivalent values are next to each other, if we found a not
984 // equivalent value after an equivalent one it means that we won't
985 // find anymore an equivalent value.
987 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
993 template<typename _Key, typename _Value,
994 typename _Allocator, typename _ExtractKey, typename _Equal,
995 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
996 bool __chc, bool __cit, bool __uk>
997 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
998 _ExtractKey, _Equal, _H1,
999 _H2, _Hash, _RehashPolicy,
1000 __chc, __cit, __uk>::iterator,
1001 typename _Hashtable<_Key, _Value, _Allocator,
1002 _ExtractKey, _Equal, _H1,
1003 _H2, _Hash, _RehashPolicy,
1004 __chc, __cit, __uk>::iterator>
1005 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1006 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1007 equal_range(const key_type& __k)
1009 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1010 std::size_t __n = _M_bucket_index(__k, __code);
1011 _Node* __p = _M_find_node(__n, __k, __code);
1015 _Node* __p1 = __p->_M_next();
1016 while (__p1 && _M_bucket_index(__p1) == __n
1017 && this->_M_equals(__k, __code, __p1))
1018 __p1 = __p1->_M_next();
1020 return std::make_pair(iterator(__p), iterator(__p1));
1023 return std::make_pair(this->end(), this->end());
1026 template<typename _Key, typename _Value,
1027 typename _Allocator, typename _ExtractKey, typename _Equal,
1028 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1029 bool __chc, bool __cit, bool __uk>
1030 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1031 _ExtractKey, _Equal, _H1,
1032 _H2, _Hash, _RehashPolicy,
1033 __chc, __cit, __uk>::const_iterator,
1034 typename _Hashtable<_Key, _Value, _Allocator,
1035 _ExtractKey, _Equal, _H1,
1036 _H2, _Hash, _RehashPolicy,
1037 __chc, __cit, __uk>::const_iterator>
1038 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1039 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1040 equal_range(const key_type& __k) const
1042 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1043 std::size_t __n = _M_bucket_index(__k, __code);
1044 _Node* __p = _M_find_node(__n, __k, __code);
1048 _Node* __p1 = __p->_M_next();
1049 while (__p1 && _M_bucket_index(__p1) == __n
1050 && this->_M_equals(__k, __code, __p1))
1051 __p1 = __p1->_M_next();
1053 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1056 return std::make_pair(this->end(), this->end());
1059 // Find the node whose key compares equal to k in the bucket n. Return nullptr
1060 // if no node is found.
1061 template<typename _Key, typename _Value,
1062 typename _Allocator, typename _ExtractKey, typename _Equal,
1063 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1064 bool __chc, bool __cit, bool __uk>
1065 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1066 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1067 __chc, __cit, __uk>::_BaseNode*
1068 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1069 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1070 _M_find_before_node(size_type __n, const key_type& __k,
1071 typename _Hashtable::_Hash_code_type __code) const
1073 _BaseNode* __prev_p = _M_buckets[__n];
1076 _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
1077 for (;; __p = __p->_M_next())
1079 if (this->_M_equals(__k, __code, __p))
1081 if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1088 template<typename _Key, typename _Value,
1089 typename _Allocator, typename _ExtractKey, typename _Equal,
1090 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1091 bool __chc, bool __cit, bool __uk>
1093 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1094 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1095 _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1097 if (_M_buckets[__bkt])
1099 // Bucket is not empty, we just need to insert the new node after the
1100 // bucket before begin.
1101 __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1102 _M_buckets[__bkt]->_M_nxt = __new_node;
1106 // The bucket is empty, the new node is inserted at the beginning of
1107 // the singly linked list and the bucket will contain _M_before_begin
1109 __new_node->_M_nxt = _M_before_begin._M_nxt;
1110 _M_before_begin._M_nxt = __new_node;
1111 if (__new_node->_M_nxt)
1112 // We must update former begin bucket that is pointing to
1114 _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1115 _M_buckets[__bkt] = &_M_before_begin;
1119 template<typename _Key, typename _Value,
1120 typename _Allocator, typename _ExtractKey, typename _Equal,
1121 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1122 bool __chc, bool __cit, bool __uk>
1124 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1125 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1126 _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1128 if (!__next || __next_bkt != __bkt)
1130 // Bucket is now empty
1131 // First update next bucket if any
1133 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1134 // Second update before begin node if necessary
1135 if (&_M_before_begin == _M_buckets[__bkt])
1136 _M_before_begin._M_nxt = __next;
1137 _M_buckets[__bkt] = nullptr;
1141 template<typename _Key, typename _Value,
1142 typename _Allocator, typename _ExtractKey, typename _Equal,
1143 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1144 bool __chc, bool __cit, bool __uk>
1145 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1146 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1147 __chc, __cit, __uk>::_BaseNode*
1148 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1149 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1150 _M_get_previous_node(size_type __bkt, _BaseNode* __n)
1152 _BaseNode* __prev_n = _M_buckets[__bkt];
1153 while (__prev_n->_M_nxt != __n)
1154 __prev_n = __prev_n->_M_nxt;
1158 template<typename _Key, typename _Value,
1159 typename _Allocator, typename _ExtractKey, typename _Equal,
1160 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1161 bool __chc, bool __cit, bool __uk>
1162 template<typename... _Args>
1163 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1164 _ExtractKey, _Equal, _H1,
1165 _H2, _Hash, _RehashPolicy,
1166 __chc, __cit, __uk>::iterator, bool>
1167 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1168 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1169 _M_emplace(std::true_type, _Args&&... __args)
1171 // First build the node to get access to the hash code
1172 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1175 const key_type& __k = this->_M_extract()(__new_node->_M_v);
1176 typename _Hashtable::_Hash_code_type __code
1177 = this->_M_hash_code(__k);
1178 size_type __bkt = _M_bucket_index(__k, __code);
1180 if (_Node* __p = _M_find_node(__bkt, __k, __code))
1182 // There is already an equivalent node, no insertion
1183 _M_deallocate_node(__new_node);
1184 return std::make_pair(iterator(__p), false);
1187 // We are going to insert this node
1188 this->_M_store_code(__new_node, __code);
1189 const _RehashPolicyState& __saved_state
1190 = _M_rehash_policy._M_state();
1191 std::pair<bool, std::size_t> __do_rehash
1192 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1193 _M_element_count, 1);
1195 if (__do_rehash.first)
1197 _M_rehash(__do_rehash.second, __saved_state);
1198 __bkt = _M_bucket_index(__k, __code);
1201 _M_insert_bucket_begin(__bkt, __new_node);
1203 return std::make_pair(iterator(__new_node), true);
1207 _M_deallocate_node(__new_node);
1208 __throw_exception_again;
1212 template<typename _Key, typename _Value,
1213 typename _Allocator, typename _ExtractKey, typename _Equal,
1214 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1215 bool __chc, bool __cit, bool __uk>
1216 template<typename... _Args>
1217 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1218 _H1, _H2, _Hash, _RehashPolicy,
1219 __chc, __cit, __uk>::iterator
1220 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1221 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1222 _M_emplace(std::false_type, _Args&&... __args)
1224 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1225 std::pair<bool, std::size_t> __do_rehash
1226 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1227 _M_element_count, 1);
1229 // First build the node to get its hash code.
1230 _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1233 const key_type& __k = this->_M_extract()(__new_node->_M_v);
1234 typename _Hashtable::_Hash_code_type __code
1235 = this->_M_hash_code(__k);
1236 this->_M_store_code(__new_node, __code);
1238 // Second, do rehash if necessary.
1239 if (__do_rehash.first)
1240 _M_rehash(__do_rehash.second, __saved_state);
1242 // Third, find the node before an equivalent one.
1243 size_type __bkt = _M_bucket_index(__k, __code);
1244 _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
1248 // Insert after the node before the equivalent one.
1249 __new_node->_M_nxt = __prev->_M_nxt;
1250 __prev->_M_nxt = __new_node;
1253 // The inserted node has no equivalent in the hashtable. We must
1254 // insert the new node at the beginning of the bucket to preserve
1255 // equivalent elements relative positions.
1256 _M_insert_bucket_begin(__bkt, __new_node);
1258 return iterator(__new_node);
1262 _M_deallocate_node(__new_node);
1263 __throw_exception_again;
1267 // Insert v in bucket n (assumes no element with its key already present).
1268 template<typename _Key, typename _Value,
1269 typename _Allocator, typename _ExtractKey, typename _Equal,
1270 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1271 bool __chc, bool __cit, bool __uk>
1272 template<typename _Arg>
1273 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1274 _H1, _H2, _Hash, _RehashPolicy,
1275 __chc, __cit, __uk>::iterator
1276 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1277 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1278 _M_insert_bucket(_Arg&& __v, size_type __n,
1279 typename _Hashtable::_Hash_code_type __code)
1281 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1282 std::pair<bool, std::size_t> __do_rehash
1283 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1284 _M_element_count, 1);
1286 if (__do_rehash.first)
1288 const key_type& __k = this->_M_extract()(__v);
1289 __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1292 _Node* __new_node = nullptr;
1295 // Allocate the new node before doing the rehash so that we
1296 // don't do a rehash if the allocation throws.
1297 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1298 this->_M_store_code(__new_node, __code);
1299 if (__do_rehash.first)
1300 _M_rehash(__do_rehash.second, __saved_state);
1302 _M_insert_bucket_begin(__n, __new_node);
1304 return iterator(__new_node);
1309 _M_rehash_policy._M_reset(__saved_state);
1311 _M_deallocate_node(__new_node);
1312 __throw_exception_again;
1316 // Insert v if no element with its key is already present.
1317 template<typename _Key, typename _Value,
1318 typename _Allocator, typename _ExtractKey, typename _Equal,
1319 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1320 bool __chc, bool __cit, bool __uk>
1321 template<typename _Arg>
1322 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1323 _ExtractKey, _Equal, _H1,
1324 _H2, _Hash, _RehashPolicy,
1325 __chc, __cit, __uk>::iterator, bool>
1326 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1327 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1328 _M_insert(_Arg&& __v, std::true_type)
1330 const key_type& __k = this->_M_extract()(__v);
1331 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1332 size_type __n = _M_bucket_index(__k, __code);
1334 if (_Node* __p = _M_find_node(__n, __k, __code))
1335 return std::make_pair(iterator(__p), false);
1336 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
1337 __n, __code), true);
1340 // Insert v unconditionally.
1341 template<typename _Key, typename _Value,
1342 typename _Allocator, typename _ExtractKey, typename _Equal,
1343 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1344 bool __chc, bool __cit, bool __uk>
1345 template<typename _Arg>
1346 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1347 _H1, _H2, _Hash, _RehashPolicy,
1348 __chc, __cit, __uk>::iterator
1349 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1350 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1351 _M_insert(_Arg&& __v, std::false_type)
1353 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1354 std::pair<bool, std::size_t> __do_rehash
1355 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1356 _M_element_count, 1);
1358 // First compute the hash code so that we don't do anything if it throws.
1359 typename _Hashtable::_Hash_code_type __code
1360 = this->_M_hash_code(this->_M_extract()(__v));
1362 _Node* __new_node = nullptr;
1365 // Second allocate new node so that we don't rehash if it throws.
1366 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1367 this->_M_store_code(__new_node, __code);
1368 if (__do_rehash.first)
1369 _M_rehash(__do_rehash.second, __saved_state);
1371 // Third, find the node before an equivalent one.
1372 size_type __bkt = _M_bucket_index(__new_node);
1374 = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1378 // Insert after the node before the equivalent one.
1379 __new_node->_M_nxt = __prev->_M_nxt;
1380 __prev->_M_nxt = __new_node;
1383 // The inserted node has no equivalent in the hashtable. We must
1384 // insert the new node at the beginning of the bucket to preserve
1385 // equivalent elements relative positions.
1386 _M_insert_bucket_begin(__bkt, __new_node);
1388 return iterator(__new_node);
1393 _M_rehash_policy._M_reset(__saved_state);
1395 _M_deallocate_node(__new_node);
1396 __throw_exception_again;
1400 template<typename _Key, typename _Value,
1401 typename _Allocator, typename _ExtractKey, typename _Equal,
1402 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1403 bool __chc, bool __cit, bool __uk>
1404 template<typename _InputIterator>
1406 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1407 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1408 insert(_InputIterator __first, _InputIterator __last)
1410 size_type __n_elt = __detail::__distance_fw(__first, __last);
1411 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1412 std::pair<bool, std::size_t> __do_rehash
1413 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1414 _M_element_count, __n_elt);
1415 if (__do_rehash.first)
1416 _M_rehash(__do_rehash.second, __saved_state);
1418 for (; __first != __last; ++__first)
1419 this->insert(*__first);
1422 template<typename _Key, typename _Value,
1423 typename _Allocator, typename _ExtractKey, typename _Equal,
1424 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1425 bool __chc, bool __cit, bool __uk>
1426 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1427 _H1, _H2, _Hash, _RehashPolicy,
1428 __chc, __cit, __uk>::iterator
1429 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1430 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1431 erase(const_iterator __it)
1433 _Node* __n = __it._M_cur;
1434 std::size_t __bkt = _M_bucket_index(__n);
1436 // Look for previous node to unlink it from the erased one, this is why
1437 // we need buckets to contain the before begin to make this research fast.
1438 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1439 if (__n == _M_bucket_begin(__bkt))
1440 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1441 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1442 else if (__n->_M_nxt)
1444 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1445 if (__next_bkt != __bkt)
1446 _M_buckets[__next_bkt] = __prev_n;
1449 __prev_n->_M_nxt = __n->_M_nxt;
1450 iterator __result(__n->_M_next());
1451 _M_deallocate_node(__n);
1457 template<typename _Key, typename _Value,
1458 typename _Allocator, typename _ExtractKey, typename _Equal,
1459 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1460 bool __chc, bool __cit, bool __uk>
1461 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1462 _H1, _H2, _Hash, _RehashPolicy,
1463 __chc, __cit, __uk>::size_type
1464 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1465 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1466 erase(const key_type& __k)
1468 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1469 std::size_t __bkt = _M_bucket_index(__k, __code);
1470 // Look for the node before the first matching node.
1471 _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
1474 _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
1475 bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1477 // We found a matching node, start deallocation loop from it
1478 std::size_t __next_bkt = __bkt;
1479 _Node* __next_n = __n;
1480 size_type __result = 0;
1481 _Node* __saved_n = nullptr;
1484 _Node* __p = __next_n;
1485 __next_n = __p->_M_next();
1486 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1487 // 526. Is it undefined if a function in the standard changes
1489 if (std::__addressof(this->_M_extract()(__p->_M_v))
1490 != std::__addressof(__k))
1491 _M_deallocate_node(__p);
1498 __next_bkt = _M_bucket_index(__next_n);
1500 while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1503 _M_deallocate_node(__saved_n);
1504 if (__is_bucket_begin)
1505 _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1506 else if (__next_n && __next_bkt != __bkt)
1507 _M_buckets[__next_bkt] = __prev_n;
1509 __prev_n->_M_nxt = __next_n;
1513 template<typename _Key, typename _Value,
1514 typename _Allocator, typename _ExtractKey, typename _Equal,
1515 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1516 bool __chc, bool __cit, bool __uk>
1517 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1518 _H1, _H2, _Hash, _RehashPolicy,
1519 __chc, __cit, __uk>::iterator
1520 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1521 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1522 erase(const_iterator __first, const_iterator __last)
1524 _Node* __n = __first._M_cur;
1525 _Node* __last_n = __last._M_cur;
1526 if (__n == __last_n)
1527 return iterator(__n);
1529 std::size_t __bkt = _M_bucket_index(__n);
1531 _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1532 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1533 std::size_t __n_bkt = __bkt;
1539 __n = __n->_M_next();
1540 _M_deallocate_node(__tmp);
1544 __n_bkt = _M_bucket_index(__n);
1546 while (__n != __last_n && __n_bkt == __bkt);
1547 if (__is_bucket_begin)
1548 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1549 if (__n == __last_n)
1551 __is_bucket_begin = true;
1555 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1556 _M_buckets[__n_bkt] = __prev_n;
1557 __prev_n->_M_nxt = __n;
1558 return iterator(__n);
1561 template<typename _Key, typename _Value,
1562 typename _Allocator, typename _ExtractKey, typename _Equal,
1563 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1564 bool __chc, bool __cit, bool __uk>
1566 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1567 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1570 _M_deallocate_nodes(_M_begin());
1571 __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
1572 _M_element_count = 0;
1573 _M_before_begin._M_nxt = nullptr;
1576 template<typename _Key, typename _Value,
1577 typename _Allocator, typename _ExtractKey, typename _Equal,
1578 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1579 bool __chc, bool __cit, bool __uk>
1581 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1582 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1583 rehash(size_type __n)
1585 const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1586 std::size_t __buckets
1587 = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
1588 if (__buckets <= __n)
1589 __buckets = _M_rehash_policy._M_next_bkt(__n);
1591 if (__buckets != _M_bucket_count)
1593 _M_rehash(__buckets, __saved_state);
1595 // We don't want the rehash policy to ask for the hashtable to shrink
1596 // on the next insertion so we need to reset its previous resize
1598 _M_rehash_policy._M_prev_resize = 0;
1602 template<typename _Key, typename _Value,
1603 typename _Allocator, typename _ExtractKey, typename _Equal,
1604 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1605 bool __chc, bool __cit, bool __uk>
1607 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1608 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1609 _M_rehash(size_type __n, const _RehashPolicyState& __state)
1613 _M_rehash_aux(__n, integral_constant<bool, __uk>());
1617 // A failure here means that buckets allocation failed. We only
1618 // have to restore hash policy previous state.
1619 _M_rehash_policy._M_reset(__state);
1620 __throw_exception_again;
1624 // Rehash when there is no equivalent elements.
1625 template<typename _Key, typename _Value,
1626 typename _Allocator, typename _ExtractKey, typename _Equal,
1627 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1628 bool __chc, bool __cit, bool __uk>
1630 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1631 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1632 _M_rehash_aux(size_type __n, std::true_type)
1634 _Bucket* __new_buckets = _M_allocate_buckets(__n);
1635 _Node* __p = _M_begin();
1636 _M_before_begin._M_nxt = nullptr;
1637 std::size_t __bbegin_bkt;
1640 _Node* __next = __p->_M_next();
1641 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1642 if (!__new_buckets[__bkt])
1644 __p->_M_nxt = _M_before_begin._M_nxt;
1645 _M_before_begin._M_nxt = __p;
1646 __new_buckets[__bkt] = &_M_before_begin;
1648 __new_buckets[__bbegin_bkt] = __p;
1649 __bbegin_bkt = __bkt;
1653 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1654 __new_buckets[__bkt]->_M_nxt = __p;
1658 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1659 _M_bucket_count = __n;
1660 _M_buckets = __new_buckets;
1663 // Rehash when there can be equivalent elements, preserve their relative
1665 template<typename _Key, typename _Value,
1666 typename _Allocator, typename _ExtractKey, typename _Equal,
1667 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1668 bool __chc, bool __cit, bool __uk>
1670 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1671 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1672 _M_rehash_aux(size_type __n, std::false_type)
1674 _Bucket* __new_buckets = _M_allocate_buckets(__n);
1676 _Node* __p = _M_begin();
1677 _M_before_begin._M_nxt = nullptr;
1678 std::size_t __bbegin_bkt;
1679 std::size_t __prev_bkt;
1680 _Node* __prev_p = nullptr;
1681 bool __check_bucket = false;
1685 _Node* __next = __p->_M_next();
1686 std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1688 if (__prev_p && __prev_bkt == __bkt)
1690 // Previous insert was already in this bucket, we insert after
1691 // the previously inserted one to preserve equivalent elements
1693 __p->_M_nxt = __prev_p->_M_nxt;
1694 __prev_p->_M_nxt = __p;
1696 // Inserting after a node in a bucket require to check that we
1697 // haven't change the bucket last node, in this case next
1698 // bucket containing its before begin node must be updated. We
1699 // schedule a check as soon as we move out of the sequence of
1700 // equivalent nodes to limit the number of checks.
1701 __check_bucket = true;
1707 // Check if we shall update the next bucket because of insertions
1708 // into __prev_bkt bucket.
1709 if (__prev_p->_M_nxt)
1711 std::size_t __next_bkt
1712 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1713 if (__next_bkt != __prev_bkt)
1714 __new_buckets[__next_bkt] = __prev_p;
1716 __check_bucket = false;
1718 if (!__new_buckets[__bkt])
1720 __p->_M_nxt = _M_before_begin._M_nxt;
1721 _M_before_begin._M_nxt = __p;
1722 __new_buckets[__bkt] = &_M_before_begin;
1724 __new_buckets[__bbegin_bkt] = __p;
1725 __bbegin_bkt = __bkt;
1729 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1730 __new_buckets[__bkt]->_M_nxt = __p;
1739 if (__check_bucket && __prev_p->_M_nxt)
1741 std::size_t __next_bkt
1742 = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1743 if (__next_bkt != __prev_bkt)
1744 __new_buckets[__next_bkt] = __prev_p;
1747 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1748 _M_bucket_count = __n;
1749 _M_buckets = __new_buckets;
1752 _GLIBCXX_END_NAMESPACE_VERSION
1755 #endif // _HASHTABLE_H