OSDN Git Service

af645a6258b7843f446d73d5bdcd309131f436a2
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / bits / hashtable.h
1 // hashtable.h header -*- C++ -*-
2
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
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 constaining:
103    * - _Hash_node*   _M_next
104    * - Tp            _M_value
105    * - size_t        _M_code if cache_hash_code is true
106    *
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
110    *
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.
119    * 
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.
124    *
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.
128    *
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.
134    *
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
138    * throw.
139    */
140
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,
147            bool __unique_keys>
148     class _Hashtable
149     : public __detail::_Rehash_base<_RehashPolicy,
150                                     _Hashtable<_Key, _Value, _Allocator,
151                                                _ExtractKey,
152                                                _Equal, _H1, _H2, _Hash,
153                                                _RehashPolicy,
154                                                __cache_hash_code,
155                                                __constant_iterators,
156                                                __unique_keys> >,
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,
161                                             _ExtractKey,
162                                             _Equal, _H1, _H2, _Hash,
163                                             _RehashPolicy,
164                                             __cache_hash_code,
165                                             __constant_iterators,
166                                             __unique_keys> >,
167       public __detail::_Equality_base<_ExtractKey, __unique_keys,
168                                       _Hashtable<_Key, _Value, _Allocator,
169                                                  _ExtractKey,
170                                                  _Equal, _H1, _H2, _Hash,
171                                                  _RehashPolicy,
172                                                  __cache_hash_code,
173                                                  __constant_iterators,
174                                                  __unique_keys> >
175     {
176       template<typename _Cond>
177         using __if_hash_code_cached
178           = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
179
180       template<typename _Cond>
181         using __if_hash_code_not_cached
182           = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
183
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,
187                                                                 _H1>>::value,
188             "Cache the hash code or qualify your hash functor with noexcept");
189
190       // Following two static assertions are necessary to guarantee that
191       // swapping two hashtable instances won't invalidate associated local
192       // iterators.
193
194       // When hash codes are cached local iterator only uses H2 which must then
195       // be empty.
196       static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
197             "Functor used to map hash code to bucket index must be empty");
198
199       typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
200                                         _H1, _H2, _Hash,
201                                         __cache_hash_code> _HCBase;
202
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");
208
209     public:
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;
220
221       typedef std::size_t                                 size_type;
222       typedef std::ptrdiff_t                              difference_type;
223       typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
224                                         _H1, _H2, _Hash,
225                                         __constant_iterators,
226                                         __cache_hash_code>
227                                                           local_iterator;
228       typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
229                                               _H1, _H2, _Hash,
230                                               __constant_iterators,
231                                               __cache_hash_code>
232                                                           const_local_iterator;
233       typedef __detail::_Node_iterator<value_type, __constant_iterators,
234                                        __cache_hash_code>
235                                                           iterator;
236       typedef __detail::_Node_const_iterator<value_type,
237                                              __constant_iterators,
238                                              __cache_hash_code>
239                                                           const_iterator;
240
241       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
242                typename _Hashtable2>
243         friend struct __detail::_Map_base;
244
245     private:
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;
254
255       typedef typename _Allocator::template rebind<_Value>::other
256                                                         _Value_allocator_type;
257
258       _Node_allocator_type      _M_node_allocator;
259       _Bucket*                  _M_buckets;
260       size_type                 _M_bucket_count;
261       _BaseNode                 _M_before_begin;
262       size_type                 _M_element_count;
263       _RehashPolicy             _M_rehash_policy;
264
265       template<typename... _Args>
266         _Node*
267         _M_allocate_node(_Args&&... __args);
268
269       void
270       _M_deallocate_node(_Node* __n);
271
272       // Deallocate the linked list of nodes pointed to by __n
273       void
274       _M_deallocate_nodes(_Node* __n);
275
276       _Bucket*
277       _M_allocate_buckets(size_type __n);
278
279       void
280       _M_deallocate_buckets(_Bucket*, size_type __n);
281
282       // Gets bucket begin, deals with the fact that non-empty buckets contain
283       // their before begin node.
284       _Node*
285       _M_bucket_begin(size_type __bkt) const;
286
287       _Node*
288       _M_begin() const
289       { return static_cast<_Node*>(_M_before_begin._M_nxt); }
290
291     public:
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&);
297
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&);
304
305       _Hashtable(const _Hashtable&);
306
307       _Hashtable(_Hashtable&&);
308
309       _Hashtable&
310       operator=(const _Hashtable& __ht)
311       {
312         _Hashtable __tmp(__ht);
313         this->swap(__tmp);
314         return *this;
315       }
316
317       _Hashtable&
318       operator=(_Hashtable&& __ht)
319       {
320         // NB: DR 1204.
321         // NB: DR 675.
322         this->clear();
323         this->swap(__ht);
324         return *this;
325       }
326
327       ~_Hashtable() noexcept;
328
329       void swap(_Hashtable&);
330
331       // Basic container operations
332       iterator
333       begin() noexcept
334       { return iterator(_M_begin()); }
335
336       const_iterator
337       begin() const noexcept
338       { return const_iterator(_M_begin()); }
339
340       iterator
341       end() noexcept
342       { return iterator(nullptr); }
343
344       const_iterator
345       end() const noexcept
346       { return const_iterator(nullptr); }
347
348       const_iterator
349       cbegin() const noexcept
350       { return const_iterator(_M_begin()); }
351
352       const_iterator
353       cend() const noexcept
354       { return const_iterator(nullptr); }
355
356       size_type
357       size() const noexcept
358       { return _M_element_count; }
359
360       bool
361       empty() const noexcept
362       { return size() == 0; }
363
364       allocator_type
365       get_allocator() const noexcept
366       { return allocator_type(_M_node_allocator); }
367
368       size_type
369       max_size() const noexcept
370       { return _M_node_allocator.max_size(); }
371
372       // Observers
373       key_equal
374       key_eq() const
375       { return this->_M_eq(); }
376
377       // hash_function, if present, comes from _Hash_code_base.
378
379       // Bucket operations
380       size_type
381       bucket_count() const noexcept
382       { return _M_bucket_count; }
383
384       size_type
385       max_bucket_count() const noexcept
386       { return max_size(); }
387
388       size_type
389       bucket_size(size_type __n) const
390       { return std::distance(begin(__n), end(__n)); }
391
392       size_type
393       bucket(const key_type& __k) const
394       { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
395
396       local_iterator
397       begin(size_type __n)
398       { return local_iterator(_M_bucket_begin(__n), __n,
399                               _M_bucket_count); }
400
401       local_iterator
402       end(size_type __n)
403       { return local_iterator(nullptr, __n, _M_bucket_count); }
404
405       const_local_iterator
406       begin(size_type __n) const
407       { return const_local_iterator(_M_bucket_begin(__n), __n,
408                                     _M_bucket_count); }
409
410       const_local_iterator
411       end(size_type __n) const
412       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
413
414       // DR 691.
415       const_local_iterator
416       cbegin(size_type __n) const
417       { return const_local_iterator(_M_bucket_begin(__n), __n,
418                                     _M_bucket_count); }
419
420       const_local_iterator
421       cend(size_type __n) const
422       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
423
424       float
425       load_factor() const noexcept
426       {
427         return static_cast<float>(size()) / static_cast<float>(bucket_count());
428       }
429
430       // max_load_factor, if present, comes from _Rehash_base.
431
432       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
433       // useful if _RehashPolicy is something other than the default.
434       const _RehashPolicy&
435       __rehash_policy() const
436       { return _M_rehash_policy; }
437
438       void
439       __rehash_policy(const _RehashPolicy&);
440
441       // Lookup.
442       iterator
443       find(const key_type& __k);
444
445       const_iterator
446       find(const key_type& __k) const;
447
448       size_type
449       count(const key_type& __k) const;
450
451       std::pair<iterator, iterator>
452       equal_range(const key_type& __k);
453
454       std::pair<const_iterator, const_iterator>
455       equal_range(const key_type& __k) const;
456
457     private:
458       // Bucket index computation helpers.
459       size_type
460       _M_bucket_index(_Node* __n) const
461       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
462
463       size_type
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); }
467
468       // Find and insert helper functions and types
469       // Find the node before the one matching the criteria.
470       _BaseNode*
471       _M_find_before_node(size_type, const key_type&,
472                           typename _Hashtable::_Hash_code_type) const;
473
474       _Node*
475       _M_find_node(size_type __bkt, const key_type& __key,
476                    typename _Hashtable::_Hash_code_type __c) const
477       {
478         _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
479         if (__before_n)
480           return static_cast<_Node*>(__before_n->_M_nxt);
481         return nullptr;
482       }
483
484       // Insert a node at the beginning of a bucket.
485       void
486       _M_insert_bucket_begin(size_type, _Node*);
487
488       // Remove the bucket first node
489       void
490       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
491                              size_type __next_bkt);
492
493       // Get the node before __n in the bucket __bkt
494       _BaseNode*
495       _M_get_previous_node(size_type __bkt, _BaseNode* __n);
496
497       template<typename _Arg>
498         iterator
499         _M_insert_bucket(_Arg&&, size_type,
500                          typename _Hashtable::_Hash_code_type);
501
502       typedef typename std::conditional<__unique_keys,
503                                         std::pair<iterator, bool>,
504                                         iterator>::type
505         _Insert_Return_Type;
506
507       typedef typename std::conditional<__unique_keys,
508                                         std::_Select1st<_Insert_Return_Type>,
509                                         std::_Identity<_Insert_Return_Type>
510                                    >::type
511         _Insert_Conv_Type;
512
513     protected:
514       template<typename... _Args>
515         std::pair<iterator, bool>
516         _M_emplace(std::true_type, _Args&&... __args);
517
518       template<typename... _Args>
519         iterator
520         _M_emplace(std::false_type, _Args&&... __args);
521
522       template<typename _Arg>
523         std::pair<iterator, bool>
524         _M_insert(_Arg&&, std::true_type);
525
526       template<typename _Arg>
527         iterator
528         _M_insert(_Arg&&, std::false_type);
529
530     public:
531       // Emplace, insert and erase
532       template<typename... _Args>
533         _Insert_Return_Type
534         emplace(_Args&&... __args)
535         { return _M_emplace(integral_constant<bool, __unique_keys>(),
536                             std::forward<_Args>(__args)...); }
537
538       template<typename... _Args>
539         iterator
540         emplace_hint(const_iterator, _Args&&... __args)
541         { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
542
543       _Insert_Return_Type
544       insert(const value_type& __v)
545       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
546
547       iterator
548       insert(const_iterator, const value_type& __v)
549       { return _Insert_Conv_Type()(insert(__v)); }
550
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>
555         _Insert_Return_Type
556         insert(_Pair&& __v)
557         { return _M_insert(std::forward<_Pair>(__v),
558                            integral_constant<bool, __unique_keys>()); }
559
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>
564         iterator
565         insert(const_iterator, _Pair&& __v)
566         { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
567
568       template<typename _InputIterator>
569         void
570         insert(_InputIterator __first, _InputIterator __last);
571
572       void
573       insert(initializer_list<value_type> __l)
574       { this->insert(__l.begin(), __l.end()); }
575
576       iterator
577       erase(const_iterator);
578
579       // LWG 2059.
580       iterator
581       erase(iterator __it)
582       { return erase(const_iterator(__it)); }
583
584       size_type
585       erase(const key_type&);
586
587       iterator
588       erase(const_iterator, const_iterator);
589
590       void
591       clear() noexcept;
592
593       // Set number of buckets to be appropriate for container of n element.
594       void rehash(size_type __n);
595
596       // DR 1189.
597       // reserve, if present, comes from _Rehash_base.
598
599     private:
600       // Helper rehash method used when keys are unique.
601       void _M_rehash_aux(size_type __n, std::true_type);
602
603       // Helper rehash method used when keys can be non-unique.
604       void _M_rehash_aux(size_type __n, std::false_type);
605
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);
609     };
610
611
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)
624       {
625         _Node* __n = _M_node_allocator.allocate(1);
626         __try
627           {
628             _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
629             return __n;
630           }
631         __catch(...)
632           {
633             _M_node_allocator.deallocate(__n, 1);
634             __throw_exception_again;
635           }
636       }
637
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>
642     void
643     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
644                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
645     _M_deallocate_node(_Node* __n)
646     {
647       _M_node_allocator.destroy(__n);
648       _M_node_allocator.deallocate(__n, 1);
649     }
650
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>
655     void
656     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
657                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
658     _M_deallocate_nodes(_Node* __n)
659     {
660       while (__n)
661         {
662           _Node* __tmp = __n;
663           __n = __n->_M_next();
664           _M_deallocate_node(__tmp);
665         }
666     }
667
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)
678     {
679       _Bucket_allocator_type __alloc(_M_node_allocator);
680
681       _Bucket* __p = __alloc.allocate(__n);
682       __builtin_memset(__p, 0, __n * sizeof(_Bucket));
683       return __p;
684     }
685
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>
690     void
691     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
692                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
693     _M_deallocate_buckets(_Bucket* __p, size_type __n)
694     {
695       _Bucket_allocator_type __alloc(_M_node_allocator);
696       __alloc.deallocate(__p, __n);
697     }
698
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
709     {
710       _BaseNode* __n = _M_buckets[__bkt];
711       return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
712     }
713
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,
727                                                         __eq),
728       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
729       _M_node_allocator(__a),
730       _M_bucket_count(0),
731       _M_element_count(0),
732       _M_rehash_policy()
733     {
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);
739     }
740
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,
756                                                           __eq),
757         __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
758         _M_node_allocator(__a),
759         _M_bucket_count(0),
760         _M_element_count(0),
761         _M_rehash_policy()
762       {
763         _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
764                                    _M_rehash_policy.
765                                    _M_bkt_for_elements(__detail::
766                                                        __distance_fw(__f,
767                                                                      __l)));
768         // We don't want the rehash policy to ask for the hashtable to shrink
769         // on the first insertion so we need to reset its previous resize
770         // level.
771         _M_rehash_policy._M_prev_resize = 0;
772         _M_buckets = _M_allocate_buckets(_M_bucket_count);
773         __try
774           {
775             for (; __f != __l; ++__f)
776               this->insert(*__f);
777           }
778         __catch(...)
779           {
780             clear();
781             _M_deallocate_buckets(_M_buckets, _M_bucket_count);
782             __throw_exception_again;
783           }
784       }
785
786   template<typename _Key, typename _Value,
787            typename _Allocator, typename _ExtractKey, typename _Equal,
788            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
789            bool __chc, bool __cit, bool __uk>
790     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
791                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
792     _Hashtable(const _Hashtable& __ht)
793     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
794       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
795                                 _H1, _H2, _Hash, __chc>(__ht),
796       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
797       _M_node_allocator(__ht._M_node_allocator),
798       _M_bucket_count(__ht._M_bucket_count),
799       _M_element_count(__ht._M_element_count),
800       _M_rehash_policy(__ht._M_rehash_policy)
801     {
802       _M_buckets = _M_allocate_buckets(_M_bucket_count);
803       __try
804         {
805           if (!__ht._M_before_begin._M_nxt)
806             return;
807
808           // First deal with the special first node pointed to by
809           // _M_before_begin.
810           const _Node* __ht_n = __ht._M_begin();
811           _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
812           this->_M_copy_code(__this_n, __ht_n);
813           _M_before_begin._M_nxt = __this_n;
814           _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
815
816           // Then deal with other nodes.
817           _BaseNode* __prev_n = __this_n;
818           for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
819             {
820               __this_n = _M_allocate_node(__ht_n->_M_v);
821               __prev_n->_M_nxt = __this_n;
822               this->_M_copy_code(__this_n, __ht_n);
823               size_type __bkt = _M_bucket_index(__this_n);
824               if (!_M_buckets[__bkt])
825                 _M_buckets[__bkt] = __prev_n;
826               __prev_n = __this_n;
827             }
828         }
829       __catch(...)
830         {
831           clear();
832           _M_deallocate_buckets(_M_buckets, _M_bucket_count);
833           __throw_exception_again;
834         }
835     }
836
837   template<typename _Key, typename _Value,
838            typename _Allocator, typename _ExtractKey, typename _Equal,
839            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
840            bool __chc, bool __cit, bool __uk>
841     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
842                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
843     _Hashtable(_Hashtable&& __ht)
844     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
845       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
846                                 _H1, _H2, _Hash, __chc>(__ht),
847       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
848       _M_node_allocator(std::move(__ht._M_node_allocator)),
849       _M_buckets(__ht._M_buckets),
850       _M_bucket_count(__ht._M_bucket_count),
851       _M_before_begin(__ht._M_before_begin._M_nxt),
852       _M_element_count(__ht._M_element_count),
853       _M_rehash_policy(__ht._M_rehash_policy)
854     {
855       // Update, if necessary, bucket pointing to before begin that hasn't move.
856       if (_M_begin())
857         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
858       __ht._M_rehash_policy = _RehashPolicy();
859       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
860       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
861       __ht._M_before_begin._M_nxt = nullptr;
862       __ht._M_element_count = 0;
863     }
864
865   template<typename _Key, typename _Value,
866            typename _Allocator, typename _ExtractKey, typename _Equal,
867            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
868            bool __chc, bool __cit, bool __uk>
869     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
870                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
871     ~_Hashtable() noexcept
872     {
873       clear();
874       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
875     }
876
877   template<typename _Key, typename _Value,
878            typename _Allocator, typename _ExtractKey, typename _Equal,
879            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
880            bool __chc, bool __cit, bool __uk>
881     void
882     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
883                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
884     swap(_Hashtable& __x)
885     {
886       // The only base class with member variables is hash_code_base.  We
887       // define _Hash_code_base::_M_swap because different specializations
888       // have different members.
889       this->_M_swap(__x);
890
891       // _GLIBCXX_RESOLVE_LIB_DEFECTS
892       // 431. Swapping containers with unequal allocators.
893       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
894                                                         __x._M_node_allocator);
895
896       std::swap(_M_rehash_policy, __x._M_rehash_policy);
897       std::swap(_M_buckets, __x._M_buckets);
898       std::swap(_M_bucket_count, __x._M_bucket_count);
899       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
900       std::swap(_M_element_count, __x._M_element_count);
901       // Fix buckets containing the _M_before_begin pointers that can't be
902       // swapped.
903       if (_M_begin())
904         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
905       if (__x._M_begin())
906         __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
907           = &(__x._M_before_begin);
908     }
909
910   template<typename _Key, typename _Value,
911            typename _Allocator, typename _ExtractKey, typename _Equal,
912            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
913            bool __chc, bool __cit, bool __uk>
914     void
915     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
916                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
917     __rehash_policy(const _RehashPolicy& __pol)
918     {
919       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
920       if (__n_bkt != _M_bucket_count)
921         _M_rehash(__n_bkt, _M_rehash_policy._M_state());
922       _M_rehash_policy = __pol;
923     }
924
925   template<typename _Key, typename _Value,
926            typename _Allocator, typename _ExtractKey, typename _Equal,
927            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
928            bool __chc, bool __cit, bool __uk>
929     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
930                         _H1, _H2, _Hash, _RehashPolicy,
931                         __chc, __cit, __uk>::iterator
932     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
933                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
934     find(const key_type& __k)
935     {
936       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
937       std::size_t __n = _M_bucket_index(__k, __code);
938       _Node* __p = _M_find_node(__n, __k, __code);
939       return __p ? iterator(__p) : this->end();
940     }
941
942   template<typename _Key, typename _Value,
943            typename _Allocator, typename _ExtractKey, typename _Equal,
944            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
945            bool __chc, bool __cit, bool __uk>
946     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
947                         _H1, _H2, _Hash, _RehashPolicy,
948                         __chc, __cit, __uk>::const_iterator
949     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
950                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
951     find(const key_type& __k) const
952     {
953       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
954       std::size_t __n = _M_bucket_index(__k, __code);
955       _Node* __p = _M_find_node(__n, __k, __code);
956       return __p ? const_iterator(__p) : this->end();
957     }
958
959   template<typename _Key, typename _Value,
960            typename _Allocator, typename _ExtractKey, typename _Equal,
961            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
962            bool __chc, bool __cit, bool __uk>
963     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
964                         _H1, _H2, _Hash, _RehashPolicy,
965                         __chc, __cit, __uk>::size_type
966     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
967                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
968     count(const key_type& __k) const
969     {
970       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
971       std::size_t __n = _M_bucket_index(__k, __code);
972       _Node* __p = _M_bucket_begin(__n);
973       if (!__p)
974         return 0;
975
976       std::size_t __result = 0;
977       for (;; __p = __p->_M_next())
978         {
979           if (this->_M_equals(__k, __code, __p))
980             ++__result;
981           else if (__result)
982             // All equivalent values are next to each other, if we found a not
983             // equivalent value after an equivalent one it means that we won't
984             // find anymore an equivalent value.
985             break;
986           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
987             break;
988         }
989       return __result;
990     }
991
992   template<typename _Key, typename _Value,
993            typename _Allocator, typename _ExtractKey, typename _Equal,
994            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
995            bool __chc, bool __cit, bool __uk>
996     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
997                                   _ExtractKey, _Equal, _H1,
998                                   _H2, _Hash, _RehashPolicy,
999                                   __chc, __cit, __uk>::iterator,
1000               typename _Hashtable<_Key, _Value, _Allocator,
1001                                   _ExtractKey, _Equal, _H1,
1002                                   _H2, _Hash, _RehashPolicy,
1003                                   __chc, __cit, __uk>::iterator>
1004     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1005                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1006     equal_range(const key_type& __k)
1007     {
1008       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1009       std::size_t __n = _M_bucket_index(__k, __code);
1010       _Node* __p = _M_find_node(__n, __k, __code);
1011
1012       if (__p)
1013         {
1014           _Node* __p1 = __p->_M_next();
1015           while (__p1 && _M_bucket_index(__p1) == __n
1016                  && this->_M_equals(__k, __code, __p1))
1017             __p1 = __p1->_M_next();
1018
1019           return std::make_pair(iterator(__p), iterator(__p1));
1020         }
1021       else
1022         return std::make_pair(this->end(), this->end());
1023     }
1024
1025   template<typename _Key, typename _Value,
1026            typename _Allocator, typename _ExtractKey, typename _Equal,
1027            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1028            bool __chc, bool __cit, bool __uk>
1029     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1030                                   _ExtractKey, _Equal, _H1,
1031                                   _H2, _Hash, _RehashPolicy,
1032                                   __chc, __cit, __uk>::const_iterator,
1033               typename _Hashtable<_Key, _Value, _Allocator,
1034                                   _ExtractKey, _Equal, _H1,
1035                                   _H2, _Hash, _RehashPolicy,
1036                                   __chc, __cit, __uk>::const_iterator>
1037     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1038                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1039     equal_range(const key_type& __k) const
1040     {
1041       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1042       std::size_t __n = _M_bucket_index(__k, __code);
1043       _Node* __p = _M_find_node(__n, __k, __code);
1044
1045       if (__p)
1046         {
1047           _Node* __p1 = __p->_M_next();
1048           while (__p1 && _M_bucket_index(__p1) == __n
1049                  && this->_M_equals(__k, __code, __p1))
1050             __p1 = __p1->_M_next();
1051
1052           return std::make_pair(const_iterator(__p), const_iterator(__p1));
1053         }
1054       else
1055         return std::make_pair(this->end(), this->end());
1056     }
1057
1058   // Find the node whose key compares equal to k in the bucket n. Return nullptr
1059   // if no node is found.
1060   template<typename _Key, typename _Value,
1061            typename _Allocator, typename _ExtractKey, typename _Equal,
1062            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1063            bool __chc, bool __cit, bool __uk>
1064     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1065                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
1066                         __chc, __cit, __uk>::_BaseNode*
1067     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1068                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1069     _M_find_before_node(size_type __n, const key_type& __k,
1070                         typename _Hashtable::_Hash_code_type __code) const
1071     {
1072       _BaseNode* __prev_p = _M_buckets[__n];
1073       if (!__prev_p)
1074         return nullptr;
1075       _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
1076       for (;; __p = __p->_M_next())
1077         {
1078           if (this->_M_equals(__k, __code, __p))
1079             return __prev_p;
1080           if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
1081             break;
1082           __prev_p = __p;
1083         }
1084       return nullptr;
1085     }
1086
1087   template<typename _Key, typename _Value,
1088            typename _Allocator, typename _ExtractKey, typename _Equal,
1089            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1090            bool __chc, bool __cit, bool __uk>
1091     void
1092     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1093                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1094     _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
1095     {
1096       if (_M_buckets[__bkt])
1097         {
1098           // Bucket is not empty, we just need to insert the new node after the
1099           // bucket before begin.
1100           __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1101           _M_buckets[__bkt]->_M_nxt = __new_node;
1102         }
1103       else
1104         {
1105           // The bucket is empty, the new node is inserted at the beginning of
1106           // the singly linked list and the bucket will contain _M_before_begin
1107           // pointer.
1108           __new_node->_M_nxt = _M_before_begin._M_nxt;
1109           _M_before_begin._M_nxt = __new_node;
1110           if (__new_node->_M_nxt)
1111             // We must update former begin bucket that is pointing to
1112             // _M_before_begin.
1113             _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
1114           _M_buckets[__bkt] = &_M_before_begin;
1115         }
1116     }
1117
1118   template<typename _Key, typename _Value,
1119            typename _Allocator, typename _ExtractKey, typename _Equal,
1120            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1121            bool __chc, bool __cit, bool __uk>
1122     void
1123     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1124                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1125     _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
1126     {
1127       if (!__next || __next_bkt != __bkt)
1128         {
1129           // Bucket is now empty
1130           // First update next bucket if any
1131           if (__next)
1132             _M_buckets[__next_bkt] = _M_buckets[__bkt];
1133           // Second update before begin node if necessary
1134           if (&_M_before_begin == _M_buckets[__bkt])
1135             _M_before_begin._M_nxt = __next;
1136           _M_buckets[__bkt] = nullptr;
1137         }
1138     }
1139
1140   template<typename _Key, typename _Value,
1141            typename _Allocator, typename _ExtractKey, typename _Equal,
1142            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1143            bool __chc, bool __cit, bool __uk>
1144     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
1145                         _Equal, _H1, _H2, _Hash, _RehashPolicy,
1146                         __chc, __cit, __uk>::_BaseNode*
1147     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1148                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1149     _M_get_previous_node(size_type __bkt, _BaseNode* __n)
1150     {
1151       _BaseNode* __prev_n = _M_buckets[__bkt];
1152       while (__prev_n->_M_nxt != __n)
1153         __prev_n = __prev_n->_M_nxt;
1154       return __prev_n;
1155     }
1156
1157   template<typename _Key, typename _Value,
1158            typename _Allocator, typename _ExtractKey, typename _Equal,
1159            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1160            bool __chc, bool __cit, bool __uk>
1161     template<typename... _Args>
1162       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1163                                     _ExtractKey, _Equal, _H1,
1164                                     _H2, _Hash, _RehashPolicy,
1165                                     __chc, __cit, __uk>::iterator, bool>
1166       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1167                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1168       _M_emplace(std::true_type, _Args&&... __args)
1169       {
1170         // First build the node to get access to the hash code
1171         _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1172         __try
1173           {
1174             const key_type& __k = this->_M_extract()(__new_node->_M_v);
1175             typename _Hashtable::_Hash_code_type __code
1176               = this->_M_hash_code(__k);
1177             size_type __bkt = _M_bucket_index(__k, __code);
1178
1179             if (_Node* __p = _M_find_node(__bkt, __k, __code))
1180               {
1181                 // There is already an equivalent node, no insertion
1182                 _M_deallocate_node(__new_node);
1183                 return std::make_pair(iterator(__p), false);
1184               }
1185
1186             // We are going to insert this node
1187             this->_M_store_code(__new_node, __code);
1188             const _RehashPolicyState& __saved_state
1189               = _M_rehash_policy._M_state();
1190             std::pair<bool, std::size_t> __do_rehash
1191               = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1192                                                 _M_element_count, 1);
1193
1194             if (__do_rehash.first)
1195               {
1196                 _M_rehash(__do_rehash.second, __saved_state);
1197                 __bkt = _M_bucket_index(__k, __code);
1198               }
1199
1200             _M_insert_bucket_begin(__bkt, __new_node);
1201             ++_M_element_count;
1202             return std::make_pair(iterator(__new_node), true);
1203           }
1204         __catch(...)
1205           {
1206             _M_deallocate_node(__new_node);
1207             __throw_exception_again;
1208           }
1209       }
1210
1211   template<typename _Key, typename _Value,
1212            typename _Allocator, typename _ExtractKey, typename _Equal,
1213            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1214            bool __chc, bool __cit, bool __uk>
1215     template<typename... _Args>
1216       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1217                           _H1, _H2, _Hash, _RehashPolicy,
1218                           __chc, __cit, __uk>::iterator
1219       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1220                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1221       _M_emplace(std::false_type, _Args&&... __args)
1222       {
1223         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1224         std::pair<bool, std::size_t> __do_rehash
1225           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1226                                             _M_element_count, 1);
1227
1228         // First build the node to get its hash code.
1229         _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
1230         __try
1231           {
1232             const key_type& __k = this->_M_extract()(__new_node->_M_v);
1233             typename _Hashtable::_Hash_code_type __code
1234               = this->_M_hash_code(__k);
1235             this->_M_store_code(__new_node, __code);
1236
1237             // Second, do rehash if necessary.
1238             if (__do_rehash.first)
1239                 _M_rehash(__do_rehash.second, __saved_state);
1240
1241             // Third, find the node before an equivalent one.
1242             size_type __bkt = _M_bucket_index(__k, __code);
1243             _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
1244             
1245             if (__prev)
1246               {
1247                 // Insert after the node before the equivalent one.
1248                 __new_node->_M_nxt = __prev->_M_nxt;
1249                 __prev->_M_nxt = __new_node;
1250               }
1251             else
1252               // The inserted node has no equivalent in the hashtable. We must
1253               // insert the new node at the beginning of the bucket to preserve
1254               // equivalent elements relative positions.
1255               _M_insert_bucket_begin(__bkt, __new_node);
1256             ++_M_element_count;
1257             return iterator(__new_node);
1258           }
1259         __catch(...)
1260           {
1261             _M_deallocate_node(__new_node);
1262             __throw_exception_again;
1263           }
1264       }
1265
1266   // Insert v in bucket n (assumes no element with its key already present).
1267   template<typename _Key, typename _Value,
1268            typename _Allocator, typename _ExtractKey, typename _Equal,
1269            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1270            bool __chc, bool __cit, bool __uk>
1271     template<typename _Arg>
1272       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1273                           _H1, _H2, _Hash, _RehashPolicy,
1274                           __chc, __cit, __uk>::iterator
1275       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1276                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1277       _M_insert_bucket(_Arg&& __v, size_type __n,
1278                        typename _Hashtable::_Hash_code_type __code)
1279       {
1280         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1281         std::pair<bool, std::size_t> __do_rehash
1282           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1283                                             _M_element_count, 1);
1284
1285         if (__do_rehash.first)
1286           {
1287             const key_type& __k = this->_M_extract()(__v);
1288             __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
1289           }
1290
1291         _Node* __new_node = nullptr;
1292         __try
1293           {
1294             // Allocate the new node before doing the rehash so that we
1295             // don't do a rehash if the allocation throws.
1296             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1297             this->_M_store_code(__new_node, __code);
1298             if (__do_rehash.first)
1299               _M_rehash(__do_rehash.second, __saved_state);
1300
1301             _M_insert_bucket_begin(__n, __new_node);
1302             ++_M_element_count;
1303             return iterator(__new_node);
1304           }
1305         __catch(...)
1306           {
1307             if (!__new_node)
1308               _M_rehash_policy._M_reset(__saved_state);
1309             else
1310               _M_deallocate_node(__new_node);
1311             __throw_exception_again;
1312           }
1313       }
1314
1315   // Insert v if no element with its key is already present.
1316   template<typename _Key, typename _Value,
1317            typename _Allocator, typename _ExtractKey, typename _Equal,
1318            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1319            bool __chc, bool __cit, bool __uk>
1320     template<typename _Arg>
1321       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
1322                                     _ExtractKey, _Equal, _H1,
1323                                     _H2, _Hash, _RehashPolicy,
1324                                     __chc, __cit, __uk>::iterator, bool>
1325       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1326                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1327       _M_insert(_Arg&& __v, std::true_type)
1328       {
1329         const key_type& __k = this->_M_extract()(__v);
1330         typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1331         size_type __n = _M_bucket_index(__k, __code);
1332
1333         if (_Node* __p = _M_find_node(__n, __k, __code))
1334           return std::make_pair(iterator(__p), false);
1335         return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
1336                               __n, __code), true);
1337       }
1338
1339   // Insert v unconditionally.
1340   template<typename _Key, typename _Value,
1341            typename _Allocator, typename _ExtractKey, typename _Equal,
1342            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1343            bool __chc, bool __cit, bool __uk>
1344     template<typename _Arg>
1345       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1346                           _H1, _H2, _Hash, _RehashPolicy,
1347                           __chc, __cit, __uk>::iterator
1348       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1349                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1350       _M_insert(_Arg&& __v, std::false_type)
1351       {
1352         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1353         std::pair<bool, std::size_t> __do_rehash
1354           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1355                                             _M_element_count, 1);
1356
1357         // First compute the hash code so that we don't do anything if it throws.
1358         typename _Hashtable::_Hash_code_type __code
1359           = this->_M_hash_code(this->_M_extract()(__v));
1360
1361         _Node* __new_node = nullptr;
1362         __try
1363           {
1364             // Second allocate new node so that we don't rehash if it throws.
1365             __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1366             this->_M_store_code(__new_node, __code);
1367             if (__do_rehash.first)
1368                 _M_rehash(__do_rehash.second, __saved_state);
1369
1370             // Third, find the node before an equivalent one.
1371             size_type __bkt = _M_bucket_index(__new_node);
1372             _BaseNode* __prev
1373               = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
1374                                     __code);
1375             if (__prev)
1376               {
1377                 // Insert after the node before the equivalent one.
1378                 __new_node->_M_nxt = __prev->_M_nxt;
1379                 __prev->_M_nxt = __new_node;
1380               }
1381             else
1382               // The inserted node has no equivalent in the hashtable. We must
1383               // insert the new node at the beginning of the bucket to preserve
1384               // equivalent elements relative positions.
1385               _M_insert_bucket_begin(__bkt, __new_node);
1386             ++_M_element_count;
1387             return iterator(__new_node);
1388           }
1389         __catch(...)
1390           {
1391             if (!__new_node)
1392               _M_rehash_policy._M_reset(__saved_state);
1393             else
1394               _M_deallocate_node(__new_node);
1395             __throw_exception_again;
1396           }
1397       }
1398
1399   template<typename _Key, typename _Value,
1400            typename _Allocator, typename _ExtractKey, typename _Equal,
1401            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1402            bool __chc, bool __cit, bool __uk>
1403     template<typename _InputIterator>
1404       void
1405       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1406                  _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1407       insert(_InputIterator __first, _InputIterator __last)
1408       {
1409         size_type __n_elt = __detail::__distance_fw(__first, __last);
1410         const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1411         std::pair<bool, std::size_t> __do_rehash
1412           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1413                                             _M_element_count, __n_elt);
1414         if (__do_rehash.first)
1415           _M_rehash(__do_rehash.second, __saved_state);
1416
1417         for (; __first != __last; ++__first)
1418           this->insert(*__first);
1419       }
1420
1421   template<typename _Key, typename _Value,
1422            typename _Allocator, typename _ExtractKey, typename _Equal,
1423            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1424            bool __chc, bool __cit, bool __uk>
1425     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1426                         _H1, _H2, _Hash, _RehashPolicy,
1427                         __chc, __cit, __uk>::iterator
1428     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1429                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1430     erase(const_iterator __it)
1431     {
1432       _Node* __n = __it._M_cur;
1433       std::size_t __bkt = _M_bucket_index(__n);
1434
1435       // Look for previous node to unlink it from the erased one, this is why
1436       // we need buckets to contain the before begin to make this research fast.
1437       _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1438       if (__n == _M_bucket_begin(__bkt))
1439         _M_remove_bucket_begin(__bkt, __n->_M_next(),
1440            __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1441       else if (__n->_M_nxt)
1442         {
1443           size_type __next_bkt = _M_bucket_index(__n->_M_next());
1444           if (__next_bkt != __bkt)
1445             _M_buckets[__next_bkt] = __prev_n;
1446         }
1447
1448       __prev_n->_M_nxt = __n->_M_nxt;
1449       iterator __result(__n->_M_next());
1450       _M_deallocate_node(__n);
1451       --_M_element_count;
1452
1453       return __result;
1454     }
1455
1456   template<typename _Key, typename _Value,
1457            typename _Allocator, typename _ExtractKey, typename _Equal,
1458            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1459            bool __chc, bool __cit, bool __uk>
1460     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1461                         _H1, _H2, _Hash, _RehashPolicy,
1462                         __chc, __cit, __uk>::size_type
1463     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1464                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1465     erase(const key_type& __k)
1466     {
1467       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1468       std::size_t __bkt = _M_bucket_index(__k, __code);
1469       // Look for the node before the first matching node.
1470       _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
1471       if (!__prev_n)
1472         return 0;
1473       _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
1474       bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
1475
1476       // We found a matching node, start deallocation loop from it
1477       std::size_t __next_bkt = __bkt;
1478       _Node* __next_n = __n;
1479       size_type __result = 0;
1480       _Node* __saved_n = nullptr;
1481       do
1482         {
1483           _Node* __p = __next_n;
1484           __next_n = __p->_M_next();
1485           // _GLIBCXX_RESOLVE_LIB_DEFECTS
1486           // 526. Is it undefined if a function in the standard changes
1487           // in parameters?
1488           if (std::__addressof(this->_M_extract()(__p->_M_v))
1489               != std::__addressof(__k))
1490             _M_deallocate_node(__p);
1491           else
1492             __saved_n = __p;
1493           --_M_element_count;
1494           ++__result;
1495           if (!__next_n)
1496             break;
1497           __next_bkt = _M_bucket_index(__next_n);
1498         }
1499       while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
1500
1501       if (__saved_n)
1502         _M_deallocate_node(__saved_n);
1503       if (__is_bucket_begin)
1504         _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
1505       else if (__next_n && __next_bkt != __bkt)
1506         _M_buckets[__next_bkt] = __prev_n;
1507       if (__prev_n)
1508         __prev_n->_M_nxt = __next_n;
1509       return __result;
1510     }
1511
1512   template<typename _Key, typename _Value,
1513            typename _Allocator, typename _ExtractKey, typename _Equal,
1514            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1515            bool __chc, bool __cit, bool __uk>
1516     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1517                         _H1, _H2, _Hash, _RehashPolicy,
1518                         __chc, __cit, __uk>::iterator
1519     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1520                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1521     erase(const_iterator __first, const_iterator __last)
1522     {
1523       _Node* __n = __first._M_cur;
1524       _Node* __last_n = __last._M_cur;
1525       if (__n == __last_n)
1526         return iterator(__n);
1527
1528       std::size_t __bkt = _M_bucket_index(__n);
1529
1530       _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
1531       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1532       std::size_t __n_bkt = __bkt;
1533       for (;;)
1534         {
1535           do
1536             {
1537               _Node* __tmp = __n;
1538               __n = __n->_M_next();
1539               _M_deallocate_node(__tmp);
1540               --_M_element_count;
1541               if (!__n)
1542                 break;
1543               __n_bkt = _M_bucket_index(__n);
1544             }
1545           while (__n != __last_n && __n_bkt == __bkt);
1546           if (__is_bucket_begin)
1547             _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1548           if (__n == __last_n)
1549             break;
1550           __is_bucket_begin = true;
1551           __bkt = __n_bkt;
1552         }
1553
1554       if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1555         _M_buckets[__n_bkt] = __prev_n;
1556       __prev_n->_M_nxt = __n;
1557       return iterator(__n);
1558     }
1559
1560   template<typename _Key, typename _Value,
1561            typename _Allocator, typename _ExtractKey, typename _Equal,
1562            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1563            bool __chc, bool __cit, bool __uk>
1564     void
1565     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1566                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1567     clear() noexcept
1568     {
1569       _M_deallocate_nodes(_M_begin());
1570       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
1571       _M_element_count = 0;
1572       _M_before_begin._M_nxt = nullptr;
1573     }
1574
1575   template<typename _Key, typename _Value,
1576            typename _Allocator, typename _ExtractKey, typename _Equal,
1577            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1578            bool __chc, bool __cit, bool __uk>
1579     void
1580     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1581                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1582     rehash(size_type __n)
1583     {
1584       const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
1585       _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1586                          _M_rehash_policy._M_bkt_for_elements(_M_element_count
1587                                                               + 1)),
1588                 __saved_state);
1589     }
1590
1591   template<typename _Key, typename _Value,
1592            typename _Allocator, typename _ExtractKey, typename _Equal,
1593            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1594            bool __chc, bool __cit, bool __uk>
1595     void
1596     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1597                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1598     _M_rehash(size_type __n, const _RehashPolicyState& __state)
1599     {
1600       __try
1601         {
1602           _M_rehash_aux(__n, integral_constant<bool, __uk>());
1603         }
1604       __catch(...)
1605         {
1606           // A failure here means that buckets allocation failed.  We only
1607           // have to restore hash policy previous state.
1608           _M_rehash_policy._M_reset(__state);
1609           __throw_exception_again;
1610         }
1611     }
1612
1613   // Rehash when there is no equivalent elements.
1614   template<typename _Key, typename _Value,
1615            typename _Allocator, typename _ExtractKey, typename _Equal,
1616            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1617            bool __chc, bool __cit, bool __uk>
1618     void
1619     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1620                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1621     _M_rehash_aux(size_type __n, std::true_type)
1622     {
1623       _Bucket* __new_buckets = _M_allocate_buckets(__n);
1624       _Node* __p = _M_begin();
1625       _M_before_begin._M_nxt = nullptr;
1626       std::size_t __bbegin_bkt;
1627       while (__p)
1628         {
1629           _Node* __next = __p->_M_next();
1630           std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1631           if (!__new_buckets[__bkt])
1632             {
1633               __p->_M_nxt = _M_before_begin._M_nxt;
1634               _M_before_begin._M_nxt = __p;
1635               __new_buckets[__bkt] = &_M_before_begin;
1636               if (__p->_M_nxt)
1637                 __new_buckets[__bbegin_bkt] = __p;
1638               __bbegin_bkt = __bkt;
1639             }
1640           else
1641             {
1642               __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1643               __new_buckets[__bkt]->_M_nxt = __p;
1644             }
1645           __p = __next;
1646         }
1647       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1648       _M_bucket_count = __n;
1649       _M_buckets = __new_buckets;
1650     }
1651
1652   // Rehash when there can be equivalent elements, preserve their relative
1653   // order.
1654   template<typename _Key, typename _Value,
1655            typename _Allocator, typename _ExtractKey, typename _Equal,
1656            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1657            bool __chc, bool __cit, bool __uk>
1658     void
1659     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1660                _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1661     _M_rehash_aux(size_type __n, std::false_type)
1662     {
1663       _Bucket* __new_buckets = _M_allocate_buckets(__n);
1664
1665       _Node* __p = _M_begin();
1666       _M_before_begin._M_nxt = nullptr;
1667       std::size_t __bbegin_bkt;
1668       std::size_t __prev_bkt;
1669       _Node* __prev_p = nullptr;
1670       bool __check_bucket = false;
1671
1672       while (__p)
1673         {
1674           _Node* __next = __p->_M_next();
1675           std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
1676
1677           if (__prev_p && __prev_bkt == __bkt)
1678             {
1679               // Previous insert was already in this bucket, we insert after
1680               // the previously inserted one to preserve equivalent elements
1681               // relative order.
1682               __p->_M_nxt = __prev_p->_M_nxt;
1683               __prev_p->_M_nxt = __p;
1684               
1685               // Inserting after a node in a bucket require to check that we
1686               // haven't change the bucket last node, in this case next
1687               // bucket containing its before begin node must be updated. We
1688               // schedule a check as soon as we move out of the sequence of
1689               // equivalent nodes to limit the number of checks.
1690               __check_bucket = true;
1691             }
1692           else
1693             {
1694               if (__check_bucket)
1695                 {
1696                   // Check if we shall update the next bucket because of insertions
1697                   // into __prev_bkt bucket.
1698                   if (__prev_p->_M_nxt)
1699                     {
1700                       std::size_t __next_bkt
1701                         = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1702                       if (__next_bkt != __prev_bkt)
1703                         __new_buckets[__next_bkt] = __prev_p;
1704                     }
1705                   __check_bucket = false;
1706                 }
1707               if (!__new_buckets[__bkt])
1708                 {
1709                   __p->_M_nxt = _M_before_begin._M_nxt;
1710                   _M_before_begin._M_nxt = __p;
1711                   __new_buckets[__bkt] = &_M_before_begin;
1712                   if (__p->_M_nxt)
1713                     __new_buckets[__bbegin_bkt] = __p;
1714                   __bbegin_bkt = __bkt;
1715                 }
1716               else
1717                 {
1718                   __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1719                   __new_buckets[__bkt]->_M_nxt = __p;
1720                 }
1721             }
1722
1723           __prev_p = __p;
1724           __prev_bkt = __bkt;
1725           __p = __next;
1726         }
1727
1728       if (__check_bucket && __prev_p->_M_nxt)
1729         {
1730           std::size_t __next_bkt
1731             = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
1732           if (__next_bkt != __prev_bkt)
1733             __new_buckets[__next_bkt] = __prev_p;
1734         }
1735
1736       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1737       _M_bucket_count = __n;
1738       _M_buckets = __new_buckets;
1739     }
1740
1741 _GLIBCXX_END_NAMESPACE_VERSION
1742 } // namespace std
1743
1744 #endif // _HASHTABLE_H