1 // hashtable.h header -*- C++ -*-
2 
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013
4 // Free Software Foundation, Inc.
5 //
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)
10 // any later version.
11 
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.
16 
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.
20 
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/>.
25 
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}
29  */
30 
31 #ifndef _HASHTABLE_H
32 #define _HASHTABLE_H 1
33 
34 #pragma GCC system_header
35 
36 #include <bits/hashtable_policy.h>
37 
38 namespace std _GLIBCXX_VISIBILITY(default)
39 {
40 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 
42   // Class template _Hashtable, class definition.
43 
44   // Meaning of class template _Hashtable's template parameters
45 
46   // _Key and _Value: arbitrary CopyConstructible types.
47 
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.
51 
52   // _ExtractKey: function object that takes an object of type Value
53   // and returns a value of type _Key.
54 
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.
57 
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()].
61 
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).
66 
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.
72 
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>).
81 
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.
86 
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.
90 
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.
95   /**
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
101    *
102    * with _Bucket being _Hash_node* and _Hash_node containing:
103    * - _Hash_node*   _M_next
104    * - Tp            _M_value
105    * - size_t        _M_hash_code if cache_hash_code is true
106    *
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
110    *
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.
120    *
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.
125    *
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.
129    *
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.
135    *
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.
140    */
141 
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,
148 	   bool __unique_keys>
149     class _Hashtable
150     : public __detail::_Rehash_base<_RehashPolicy,
151 				    _Hashtable<_Key, _Value, _Allocator,
152 					       _ExtractKey,
153 					       _Equal, _H1, _H2, _Hash,
154 					       _RehashPolicy,
155 					       __cache_hash_code,
156 					       __constant_iterators,
157 					       __unique_keys> >,
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,
162 					    _ExtractKey,
163 					    _Equal, _H1, _H2, _Hash,
164 					    _RehashPolicy,
165 					    __cache_hash_code,
166 					    __constant_iterators,
167 					    __unique_keys> >,
168       public __detail::_Equality_base<_ExtractKey, __unique_keys,
169 				      _Hashtable<_Key, _Value, _Allocator,
170 						 _ExtractKey,
171 						 _Equal, _H1, _H2, _Hash,
172 						 _RehashPolicy,
173 						 __cache_hash_code,
174 						 __constant_iterators,
175 						 __unique_keys> >
176     {
177       template<typename _Cond>
178 	using __if_hash_code_cached
179 	  = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
180 
181       template<typename _Cond>
182 	using __if_hash_code_not_cached
183 	  = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
184 
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,
188 								_H1>>::value,
189       	    "Cache the hash code or qualify your hash functor with noexcept");
190 
191       // Following two static assertions are necessary to guarantee that
192       // swapping two hashtable instances won't invalidate associated local
193       // iterators.
194 
195       // When hash codes are cached local iterator only uses H2 which must then
196       // be empty.
197       static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
198 	    "Functor used to map hash code to bucket index must be empty");
199 
200       typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
201 					_H1, _H2, _Hash,
202 				       	__cache_hash_code> _HCBase;
203 
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");
209 
210     public:
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;
221 
222       typedef std::size_t                                 size_type;
223       typedef std::ptrdiff_t                              difference_type;
224       typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
225 					_H1, _H2, _Hash,
226 					__constant_iterators,
227 					__cache_hash_code>
228 							  local_iterator;
229       typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
230 					      _H1, _H2, _Hash,
231 					      __constant_iterators,
232 					      __cache_hash_code>
233 							  const_local_iterator;
234       typedef __detail::_Node_iterator<value_type, __constant_iterators,
235 				       __cache_hash_code>
236 							  iterator;
237       typedef __detail::_Node_const_iterator<value_type,
238 					     __constant_iterators,
239 					     __cache_hash_code>
240 							  const_iterator;
241 
242       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
243 	       typename _Hashtable2>
244 	friend struct __detail::_Map_base;
245 
246     private:
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;
255 
256       typedef typename _Allocator::template rebind<_Value>::other
257 							_Value_allocator_type;
258 
259       _Node_allocator_type	_M_node_allocator;
260       _Bucket*			_M_buckets;
261       size_type			_M_bucket_count;
262       _BaseNode			_M_before_begin;
263       size_type			_M_element_count;
264       _RehashPolicy		_M_rehash_policy;
265 
266       template<typename... _Args>
267 	_Node*
268 	_M_allocate_node(_Args&&... __args);
269 
270       void
271       _M_deallocate_node(_Node* __n);
272 
273       // Deallocate the linked list of nodes pointed to by __n
274       void
275       _M_deallocate_nodes(_Node* __n);
276 
277       _Bucket*
278       _M_allocate_buckets(size_type __n);
279 
280       void
281       _M_deallocate_buckets(_Bucket*, size_type __n);
282 
283       // Gets bucket begin, deals with the fact that non-empty buckets contain
284       // their before begin node.
285       _Node*
286       _M_bucket_begin(size_type __bkt) const;
287 
288       _Node*
289       _M_begin() const
290       { return static_cast<_Node*>(_M_before_begin._M_nxt); }
291 
292     public:
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&);
298 
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&);
305 
306       _Hashtable(const _Hashtable&);
307 
308       _Hashtable(_Hashtable&&);
309 
310       _Hashtable&
311       operator=(const _Hashtable& __ht)
312       {
313 	_Hashtable __tmp(__ht);
314 	this->swap(__tmp);
315 	return *this;
316       }
317 
318       _Hashtable&
319       operator=(_Hashtable&& __ht)
320       {
321 	// NB: DR 1204.
322 	// NB: DR 675.
323 	this->clear();
324 	this->swap(__ht);
325 	return *this;
326       }
327 
328       ~_Hashtable() noexcept;
329 
330       void swap(_Hashtable&);
331 
332       // Basic container operations
333       iterator
334       begin() noexcept
335       { return iterator(_M_begin()); }
336 
337       const_iterator
338       begin() const noexcept
339       { return const_iterator(_M_begin()); }
340 
341       iterator
342       end() noexcept
343       { return iterator(nullptr); }
344 
345       const_iterator
346       end() const noexcept
347       { return const_iterator(nullptr); }
348 
349       const_iterator
350       cbegin() const noexcept
351       { return const_iterator(_M_begin()); }
352 
353       const_iterator
354       cend() const noexcept
355       { return const_iterator(nullptr); }
356 
357       size_type
358       size() const noexcept
359       { return _M_element_count; }
360 
361       bool
362       empty() const noexcept
363       { return size() == 0; }
364 
365       allocator_type
366       get_allocator() const noexcept
367       { return allocator_type(_M_node_allocator); }
368 
369       size_type
370       max_size() const noexcept
371       { return _M_node_allocator.max_size(); }
372 
373       // Observers
374       key_equal
375       key_eq() const
376       { return this->_M_eq(); }
377 
378       // hash_function, if present, comes from _Hash_code_base.
379 
380       // Bucket operations
381       size_type
382       bucket_count() const noexcept
383       { return _M_bucket_count; }
384 
385       size_type
386       max_bucket_count() const noexcept
387       { return max_size(); }
388 
389       size_type
390       bucket_size(size_type __n) const
391       { return std::distance(begin(__n), end(__n)); }
392 
393       size_type
394       bucket(const key_type& __k) const
395       { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
396 
397       local_iterator
398       begin(size_type __n)
399       { return local_iterator(_M_bucket_begin(__n), __n,
400 			      _M_bucket_count); }
401 
402       local_iterator
403       end(size_type __n)
404       { return local_iterator(nullptr, __n, _M_bucket_count); }
405 
406       const_local_iterator
407       begin(size_type __n) const
408       { return const_local_iterator(_M_bucket_begin(__n), __n,
409 				    _M_bucket_count); }
410 
411       const_local_iterator
412       end(size_type __n) const
413       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
414 
415       // DR 691.
416       const_local_iterator
417       cbegin(size_type __n) const
418       { return const_local_iterator(_M_bucket_begin(__n), __n,
419 				    _M_bucket_count); }
420 
421       const_local_iterator
422       cend(size_type __n) const
423       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
424 
425       float
426       load_factor() const noexcept
427       {
428 	return static_cast<float>(size()) / static_cast<float>(bucket_count());
429       }
430 
431       // max_load_factor, if present, comes from _Rehash_base.
432 
433       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
434       // useful if _RehashPolicy is something other than the default.
435       const _RehashPolicy&
436       __rehash_policy() const
437       { return _M_rehash_policy; }
438 
439       void
440       __rehash_policy(const _RehashPolicy&);
441 
442       // Lookup.
443       iterator
444       find(const key_type& __k);
445 
446       const_iterator
447       find(const key_type& __k) const;
448 
449       size_type
450       count(const key_type& __k) const;
451 
452       std::pair<iterator, iterator>
453       equal_range(const key_type& __k);
454 
455       std::pair<const_iterator, const_iterator>
456       equal_range(const key_type& __k) const;
457 
458     private:
459       // Bucket index computation helpers.
460       size_type
461       _M_bucket_index(_Node* __n) const
462       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
463 
464       size_type
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); }
468 
469       // Find and insert helper functions and types
470       // Find the node before the one matching the criteria.
471       _BaseNode*
472       _M_find_before_node(size_type, const key_type&,
473 			  typename _Hashtable::_Hash_code_type) const;
474 
475       _Node*
476       _M_find_node(size_type __bkt, const key_type& __key,
477 		   typename _Hashtable::_Hash_code_type __c) const
478       {
479 	_BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
480 	if (__before_n)
481 	  return static_cast<_Node*>(__before_n->_M_nxt);
482 	return nullptr;
483       }
484 
485       // Insert a node at the beginning of a bucket.
486       void
487       _M_insert_bucket_begin(size_type, _Node*);
488 
489       // Remove the bucket first node
490       void
491       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
492 			     size_type __next_bkt);
493 
494       // Get the node before __n in the bucket __bkt
495       _BaseNode*
496       _M_get_previous_node(size_type __bkt, _BaseNode* __n);
497 
498       template<typename _Arg>
499 	iterator
500 	_M_insert_bucket(_Arg&&, size_type,
501 			 typename _Hashtable::_Hash_code_type);
502 
503       typedef typename std::conditional<__unique_keys,
504 					std::pair<iterator, bool>,
505 					iterator>::type
506 	_Insert_Return_Type;
507 
508       typedef typename std::conditional<__unique_keys,
509 					std::_Select1st<_Insert_Return_Type>,
510 					std::_Identity<_Insert_Return_Type>
511 				   >::type
512 	_Insert_Conv_Type;
513 
514     protected:
515       template<typename... _Args>
516 	std::pair<iterator, bool>
517 	_M_emplace(std::true_type, _Args&&... __args);
518 
519       template<typename... _Args>
520 	iterator
521 	_M_emplace(std::false_type, _Args&&... __args);
522 
523       template<typename _Arg>
524 	std::pair<iterator, bool>
525 	_M_insert(_Arg&&, std::true_type);
526 
527       template<typename _Arg>
528 	iterator
529 	_M_insert(_Arg&&, std::false_type);
530 
531     public:
532       // Emplace, insert and erase
533       template<typename... _Args>
534 	_Insert_Return_Type
535 	emplace(_Args&&... __args)
536 	{ return _M_emplace(integral_constant<bool, __unique_keys>(),
537 			    std::forward<_Args>(__args)...); }
538 
539       template<typename... _Args>
540 	iterator
541 	emplace_hint(const_iterator, _Args&&... __args)
542 	{ return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
543 
544       _Insert_Return_Type
545       insert(const value_type& __v)
546       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
547 
548       iterator
549       insert(const_iterator, const value_type& __v)
550       { return _Insert_Conv_Type()(insert(__v)); }
551 
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>
556 	_Insert_Return_Type
557 	insert(_Pair&& __v)
558 	{ return _M_insert(std::forward<_Pair>(__v),
559 			   integral_constant<bool, __unique_keys>()); }
560 
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>
565 	iterator
566 	insert(const_iterator, _Pair&& __v)
567 	{ return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
568 
569       template<typename _InputIterator>
570 	void
571 	insert(_InputIterator __first, _InputIterator __last);
572 
573       void
574       insert(initializer_list<value_type> __l)
575       { this->insert(__l.begin(), __l.end()); }
576 
577       iterator
578       erase(const_iterator);
579 
580       // LWG 2059.
581       iterator
582       erase(iterator __it)
583       { return erase(const_iterator(__it)); }
584 
585       size_type
586       erase(const key_type&);
587 
588       iterator
589       erase(const_iterator, const_iterator);
590 
591       void
592       clear() noexcept;
593 
594       // Set number of buckets to be appropriate for container of n element.
595       void rehash(size_type __n);
596 
597       // DR 1189.
598       // reserve, if present, comes from _Rehash_base.
599 
600     private:
601       // Helper rehash method used when keys are unique.
602       void _M_rehash_aux(size_type __n, std::true_type);
603 
604       // Helper rehash method used when keys can be non-unique.
605       void _M_rehash_aux(size_type __n, std::false_type);
606 
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);
610     };
611 
612 
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)
625       {
626 	_Node* __n = _M_node_allocator.allocate(1);
627 	__try
628 	  {
629 	    _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
630 	    return __n;
631 	  }
632 	__catch(...)
633 	  {
634 	    _M_node_allocator.deallocate(__n, 1);
635 	    __throw_exception_again;
636 	  }
637       }
638 
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>
643     void
644     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
645 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
646     _M_deallocate_node(_Node* __n)
647     {
648       _M_node_allocator.destroy(__n);
649       _M_node_allocator.deallocate(__n, 1);
650     }
651 
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>
656     void
657     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
658 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
659     _M_deallocate_nodes(_Node* __n)
660     {
661       while (__n)
662 	{
663 	  _Node* __tmp = __n;
664 	  __n = __n->_M_next();
665 	  _M_deallocate_node(__tmp);
666 	}
667     }
668 
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)
679     {
680       _Bucket_allocator_type __alloc(_M_node_allocator);
681 
682       _Bucket* __p = __alloc.allocate(__n);
683       __builtin_memset(__p, 0, __n * sizeof(_Bucket));
684       return __p;
685     }
686 
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>
691     void
692     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
693 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
694     _M_deallocate_buckets(_Bucket* __p, size_type __n)
695     {
696       _Bucket_allocator_type __alloc(_M_node_allocator);
697       __alloc.deallocate(__p, __n);
698     }
699 
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
710     {
711       _BaseNode* __n = _M_buckets[__bkt];
712       return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
713     }
714 
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,
728 							__eq),
729       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
730       _M_node_allocator(__a),
731       _M_bucket_count(0),
732       _M_element_count(0),
733       _M_rehash_policy()
734     {
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);
740     }
741 
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,
757 							  __eq),
758 	__detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
759 	_M_node_allocator(__a),
760 	_M_bucket_count(0),
761 	_M_element_count(0),
762 	_M_rehash_policy()
763       {
764 	_M_bucket_count =
765 	  _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
766 								       __l));
767 	if (_M_bucket_count <= __bucket_hint)
768 	  _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
769 
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
772 	// level.
773 	_M_rehash_policy._M_prev_resize = 0;
774 	_M_buckets = _M_allocate_buckets(_M_bucket_count);
775 	__try
776 	  {
777 	    for (; __f != __l; ++__f)
778 	      this->insert(*__f);
779 	  }
780 	__catch(...)
781 	  {
782 	    clear();
783 	    _M_deallocate_buckets(_M_buckets, _M_bucket_count);
784 	    __throw_exception_again;
785 	  }
786       }
787 
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)
803     {
804       _M_buckets = _M_allocate_buckets(_M_bucket_count);
805       __try
806 	{
807 	  if (!__ht._M_before_begin._M_nxt)
808 	    return;
809 
810 	  // First deal with the special first node pointed to by
811 	  // _M_before_begin.
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;
817 
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())
821 	    {
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;
828 	      __prev_n = __this_n;
829 	    }
830 	}
831       __catch(...)
832 	{
833 	  clear();
834 	  _M_deallocate_buckets(_M_buckets, _M_bucket_count);
835 	  __throw_exception_again;
836 	}
837     }
838 
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)
856     {
857       // Update, if necessary, bucket pointing to before begin that hasn't move.
858       if (_M_begin())
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;
865     }
866 
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
874     {
875       clear();
876       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
877     }
878 
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>
883     void
884     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
885 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
886     swap(_Hashtable& __x)
887     {
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.
891       this->_M_swap(__x);
892 
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);
897 
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
904       // swapped.
905       if (_M_begin())
906 	_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
907       if (__x._M_begin())
908 	__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
909 	  = &(__x._M_before_begin);
910     }
911 
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>
916     void
917     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
918 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
919     __rehash_policy(const _RehashPolicy& __pol)
920     {
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;
925     }
926 
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)
937     {
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();
942     }
943 
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
954     {
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();
959     }
960 
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
971     {
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);
975       if (!__p)
976 	return 0;
977 
978       std::size_t __result = 0;
979       for (;; __p = __p->_M_next())
980 	{
981 	  if (this->_M_equals(__k, __code, __p))
982 	    ++__result;
983 	  else if (__result)
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.
987 	    break;
988 	  if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
989 	    break;
990 	}
991       return __result;
992     }
993 
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)
1009     {
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);
1013 
1014       if (__p)
1015 	{
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();
1020 
1021 	  return std::make_pair(iterator(__p), iterator(__p1));
1022 	}
1023       else
1024 	return std::make_pair(this->end(), this->end());
1025     }
1026 
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
1042     {
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);
1046 
1047       if (__p)
1048 	{
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();
1053 
1054 	  return std::make_pair(const_iterator(__p), const_iterator(__p1));
1055 	}
1056       else
1057 	return std::make_pair(this->end(), this->end());
1058     }
1059 
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
1073     {
1074       _BaseNode* __prev_p = _M_buckets[__n];
1075       if (!__prev_p)
1076 	return nullptr;
1077       _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
1078       for (;; __p = __p->_M_next())
1079 	{
1080 	  if (this->_M_equals(__k, __code, __p))
1081 	    return __prev_p;
1082 	  if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1083 	    break;
1084 	  __prev_p = __p;
1085 	}
1086       return nullptr;
1087     }
1088 
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>
1093     void
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)
1097     {
1098       if (_M_buckets[__bkt])
1099 	{
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;
1104 	}
1105       else
1106 	{
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
1109 	  // pointer.
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
1114 	    // _M_before_begin.
1115 	    _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1116 	  _M_buckets[__bkt] = &_M_before_begin;
1117 	}
1118     }
1119 
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>
1124     void
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)
1128     {
1129       if (!__next || __next_bkt != __bkt)
1130 	{
1131 	  // Bucket is now empty
1132 	  // First update next bucket if any
1133 	  if (__next)
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;
1139 	}
1140     }
1141 
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)
1152     {
1153       _BaseNode* __prev_n = _M_buckets[__bkt];
1154       while (__prev_n->_M_nxt != __n)
1155 	__prev_n = __prev_n->_M_nxt;
1156       return __prev_n;
1157     }
1158 
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)
1171       {
1172 	// First build the node to get access to the hash code
1173 	_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1174 	__try
1175 	  {
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);
1180 
1181 	    if (_Node* __p = _M_find_node(__bkt, __k, __code))
1182 	      {
1183 		// There is already an equivalent node, no insertion
1184 		_M_deallocate_node(__new_node);
1185 		return std::make_pair(iterator(__p), false);
1186 	      }
1187 
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);
1195 
1196 	    if (__do_rehash.first)
1197 	      {
1198 		_M_rehash(__do_rehash.second, __saved_state);
1199 		__bkt = _M_bucket_index(__k, __code);
1200 	      }
1201 
1202 	    _M_insert_bucket_begin(__bkt, __new_node);
1203 	    ++_M_element_count;
1204 	    return std::make_pair(iterator(__new_node), true);
1205 	  }
1206 	__catch(...)
1207 	  {
1208 	    _M_deallocate_node(__new_node);
1209 	    __throw_exception_again;
1210 	  }
1211       }
1212 
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)
1224       {
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);
1229 
1230 	// First build the node to get its hash code.
1231 	_Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1232 	__try
1233 	  {
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);
1238 
1239 	    // Second, do rehash if necessary.
1240 	    if (__do_rehash.first)
1241 		_M_rehash(__do_rehash.second, __saved_state);
1242 
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);
1246 
1247 	    if (__prev)
1248 	      {
1249 		// Insert after the node before the equivalent one.
1250 		__new_node->_M_nxt = __prev->_M_nxt;
1251 		__prev->_M_nxt = __new_node;
1252 	      }
1253 	    else
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);
1258 	    ++_M_element_count;
1259 	    return iterator(__new_node);
1260 	  }
1261 	__catch(...)
1262 	  {
1263 	    _M_deallocate_node(__new_node);
1264 	    __throw_exception_again;
1265 	  }
1266       }
1267 
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)
1281       {
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);
1286 
1287 	if (__do_rehash.first)
1288 	  {
1289 	    const key_type& __k = this->_M_extract()(__v);
1290 	    __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1291 	  }
1292 
1293 	_Node* __new_node = nullptr;
1294 	__try
1295 	  {
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);
1302 
1303 	    _M_insert_bucket_begin(__n, __new_node);
1304 	    ++_M_element_count;
1305 	    return iterator(__new_node);
1306 	  }
1307 	__catch(...)
1308 	  {
1309 	    if (!__new_node)
1310 	      _M_rehash_policy._M_reset(__saved_state);
1311 	    else
1312 	      _M_deallocate_node(__new_node);
1313 	    __throw_exception_again;
1314 	  }
1315       }
1316 
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)
1330       {
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);
1334 
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);
1339       }
1340 
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)
1353       {
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);
1358 
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));
1362 
1363 	_Node* __new_node = nullptr;
1364 	__try
1365 	  {
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);
1371 
1372 	    // Third, find the node before an equivalent one.
1373 	    size_type __bkt = _M_bucket_index(__new_node);
1374 	    _BaseNode* __prev
1375 	      = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1376 				    __code);
1377 	    if (__prev)
1378 	      {
1379 		// Insert after the node before the equivalent one.
1380 		__new_node->_M_nxt = __prev->_M_nxt;
1381 		__prev->_M_nxt = __new_node;
1382 	      }
1383 	    else
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);
1388 	    ++_M_element_count;
1389 	    return iterator(__new_node);
1390 	  }
1391 	__catch(...)
1392 	  {
1393 	    if (!__new_node)
1394 	      _M_rehash_policy._M_reset(__saved_state);
1395 	    else
1396 	      _M_deallocate_node(__new_node);
1397 	    __throw_exception_again;
1398 	  }
1399       }
1400 
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>
1406       void
1407       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1408 		 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1409       insert(_InputIterator __first, _InputIterator __last)
1410       {
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);
1418 
1419 	for (; __first != __last; ++__first)
1420 	  this->insert(*__first);
1421       }
1422 
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)
1433     {
1434       _Node* __n = __it._M_cur;
1435       std::size_t __bkt = _M_bucket_index(__n);
1436 
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)
1444 	{
1445 	  size_type __next_bkt = _M_bucket_index(__n->_M_next());
1446 	  if (__next_bkt != __bkt)
1447 	    _M_buckets[__next_bkt] = __prev_n;
1448 	}
1449 
1450       __prev_n->_M_nxt = __n->_M_nxt;
1451       iterator __result(__n->_M_next());
1452       _M_deallocate_node(__n);
1453       --_M_element_count;
1454 
1455       return __result;
1456     }
1457 
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)
1468     {
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);
1473       if (!__prev_n)
1474 	return 0;
1475       _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
1476       bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1477 
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;
1483       do
1484 	{
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
1489 	  // in parameters?
1490 	  if (std::__addressof(this->_M_extract()(__p->_M_v))
1491 	      != std::__addressof(__k))
1492 	    _M_deallocate_node(__p);
1493 	  else
1494 	    __saved_n = __p;
1495 	  --_M_element_count;
1496 	  ++__result;
1497 	  if (!__next_n)
1498 	    break;
1499 	  __next_bkt = _M_bucket_index(__next_n);
1500 	}
1501       while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1502 
1503       if (__saved_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;
1509       if (__prev_n)
1510 	__prev_n->_M_nxt = __next_n;
1511       return __result;
1512     }
1513 
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)
1524     {
1525       _Node* __n = __first._M_cur;
1526       _Node* __last_n = __last._M_cur;
1527       if (__n == __last_n)
1528 	return iterator(__n);
1529 
1530       std::size_t __bkt = _M_bucket_index(__n);
1531 
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;
1535       for (;;)
1536 	{
1537 	  do
1538 	    {
1539 	      _Node* __tmp = __n;
1540 	      __n = __n->_M_next();
1541 	      _M_deallocate_node(__tmp);
1542 	      --_M_element_count;
1543 	      if (!__n)
1544 		break;
1545 	      __n_bkt = _M_bucket_index(__n);
1546 	    }
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)
1551 	    break;
1552 	  __is_bucket_begin = true;
1553 	  __bkt = __n_bkt;
1554 	}
1555 
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);
1560     }
1561 
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>
1566     void
1567     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1568 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1569     clear() noexcept
1570     {
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;
1575     }
1576 
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>
1581     void
1582     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1583 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1584     rehash(size_type __n)
1585     {
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);
1591 
1592       if (__buckets != _M_bucket_count)
1593 	{
1594 	  _M_rehash(__buckets, __saved_state);
1595 
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
1598 	  // level.
1599 	  _M_rehash_policy._M_prev_resize = 0;
1600 	}
1601       else
1602 	// No rehash, restore previous state to keep a consistent state.
1603 	_M_rehash_policy._M_reset(__saved_state);
1604     }
1605 
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>
1610     void
1611     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1612 	       _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1613     _M_rehash(size_type __n, const _RehashPolicyState& __state)
1614     {
1615       __try
1616 	{
1617 	  _M_rehash_aux(__n, integral_constant<bool, __uk>());
1618 	}
1619       __catch(...)
1620 	{
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;
1625 	}
1626     }
1627 
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>
1633     void
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)
1637     {
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;
1642       while (__p)
1643 	{
1644 	  _Node* __next = __p->_M_next();
1645 	  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1646 	  if (!__new_buckets[__bkt])
1647 	    {
1648 	      __p->_M_nxt = _M_before_begin._M_nxt;
1649 	      _M_before_begin._M_nxt = __p;
1650 	      __new_buckets[__bkt] = &_M_before_begin;
1651 	      if (__p->_M_nxt)
1652 		__new_buckets[__bbegin_bkt] = __p;
1653 	      __bbegin_bkt = __bkt;
1654 	    }
1655 	  else
1656 	    {
1657 	      __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1658 	      __new_buckets[__bkt]->_M_nxt = __p;
1659 	    }
1660 	  __p = __next;
1661 	}
1662       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1663       _M_bucket_count = __n;
1664       _M_buckets = __new_buckets;
1665     }
1666 
1667   // Rehash when there can be equivalent elements, preserve their relative
1668   // order.
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>
1673     void
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)
1677     {
1678       _Bucket* __new_buckets = _M_allocate_buckets(__n);
1679 
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;
1686 
1687       while (__p)
1688 	{
1689 	  _Node* __next = __p->_M_next();
1690 	  std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1691 
1692 	  if (__prev_p && __prev_bkt == __bkt)
1693 	    {
1694 	      // Previous insert was already in this bucket, we insert after
1695 	      // the previously inserted one to preserve equivalent elements
1696 	      // relative order.
1697 	      __p->_M_nxt = __prev_p->_M_nxt;
1698 	      __prev_p->_M_nxt = __p;
1699 
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;
1706 	    }
1707 	  else
1708 	    {
1709 	      if (__check_bucket)
1710 		{
1711 		  // Check if we shall update the next bucket because of
1712 		  // insertions into __prev_bkt bucket.
1713 		  if (__prev_p->_M_nxt)
1714 		    {
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;
1719 		    }
1720 		  __check_bucket = false;
1721 		}
1722 	      if (!__new_buckets[__bkt])
1723 		{
1724 		  __p->_M_nxt = _M_before_begin._M_nxt;
1725 		  _M_before_begin._M_nxt = __p;
1726 		  __new_buckets[__bkt] = &_M_before_begin;
1727 		  if (__p->_M_nxt)
1728 		    __new_buckets[__bbegin_bkt] = __p;
1729 		  __bbegin_bkt = __bkt;
1730 		}
1731 	      else
1732 		{
1733 		  __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1734 		  __new_buckets[__bkt]->_M_nxt = __p;
1735 		}
1736 	    }
1737 
1738 	  __prev_p = __p;
1739 	  __prev_bkt = __bkt;
1740 	  __p = __next;
1741 	}
1742 
1743       if (__check_bucket && __prev_p->_M_nxt)
1744 	{
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;
1749 	}
1750 
1751       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1752       _M_bucket_count = __n;
1753       _M_buckets = __new_buckets;
1754     }
1755 
1756 _GLIBCXX_END_NAMESPACE_VERSION
1757 } // namespace std
1758 
1759 #endif // _HASHTABLE_H
1760