libstdc++
bits/hashtable.h
Go to the documentation of this file.
00001 // hashtable.h header -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file bits/hashtable.h
00027  *  This is an internal header file, included by other library headers.
00028  *  Do not attempt to use it directly. @headername{unordered_map, unordered_set}
00029  */
00030 
00031 #ifndef _HASHTABLE_H
00032 #define _HASHTABLE_H 1
00033 
00034 #pragma GCC system_header
00035 
00036 #include <bits/hashtable_policy.h>
00037 
00038 namespace std _GLIBCXX_VISIBILITY(default)
00039 {
00040 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00041 
00042   // Class template _Hashtable, class definition.
00043 
00044   // Meaning of class template _Hashtable's template parameters
00045 
00046   // _Key and _Value: arbitrary CopyConstructible types.
00047 
00048   // _Allocator: an allocator type ([lib.allocator.requirements]) whose
00049   // value type is Value.  As a conforming extension, we allow for
00050   // value type != Value.
00051 
00052   // _ExtractKey: function object that takes an object of type Value
00053   // and returns a value of type _Key.
00054 
00055   // _Equal: function object that takes two objects of type k and returns
00056   // a bool-like value that is true if the two objects are considered equal.
00057 
00058   // _H1: the hash function.  A unary function object with argument type
00059   // Key and result type size_t.  Return values should be distributed
00060   // over the entire range [0, numeric_limits<size_t>:::max()].
00061 
00062   // _H2: the range-hashing function (in the terminology of Tavori and
00063   // Dreizin).  A binary function object whose argument types and result
00064   // type are all size_t.  Given arguments r and N, the return value is
00065   // in the range [0, N).
00066 
00067   // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
00068   // whose argument types are _Key and size_t and whose result type is
00069   // size_t.  Given arguments k and N, the return value is in the range
00070   // [0, N).  Default: hash(k, N) = h2(h1(k), N).  If _Hash is anything other
00071   // than the default, _H1 and _H2 are ignored.
00072 
00073   // _RehashPolicy: Policy class with three members, all of which govern
00074   // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
00075   // than n.  _M_bkt_for_elements(n) returns a bucket count appropriate
00076   // for an element count of n.  _M_need_rehash(n_bkt, n_elt, n_ins)
00077   // determines whether, if the current bucket count is n_bkt and the
00078   // current element count is n_elt, we need to increase the bucket
00079   // count.  If so, returns make_pair(true, n), where n is the new
00080   // bucket count.  If not, returns make_pair(false, <anything>).
00081 
00082   // __cache_hash_code: bool.  true if we store the value of the hash
00083   // function along with the value.  This is a time-space tradeoff.
00084   // Storing it may improve lookup speed by reducing the number of times
00085   // we need to call the Equal function.
00086 
00087   // __constant_iterators: bool.  true if iterator and const_iterator are
00088   // both constant iterator types.  This is true for unordered_set and
00089   // unordered_multiset, false for unordered_map and unordered_multimap.
00090 
00091   // __unique_keys: bool.  true if the return value of _Hashtable::count(k)
00092   // is always at most one, false if it may be an arbitrary number.  This
00093   // true for unordered_set and unordered_map, false for unordered_multiset
00094   // and unordered_multimap.
00095   /**
00096    * Here's _Hashtable data structure, each _Hashtable has:
00097    * - _Bucket[]       _M_buckets
00098    * - _Hash_node_base _M_before_begin
00099    * - size_type       _M_bucket_count
00100    * - size_type       _M_element_count
00101    *
00102    * with _Bucket being _Hash_node* and _Hash_node constaining:
00103    * - _Hash_node*   _M_next
00104    * - Tp            _M_value
00105    * - size_t        _M_code if cache_hash_code is true
00106    *
00107    * In terms of Standard containers the hastable is like the aggregation of:
00108    * - std::forward_list<_Node> containing the elements
00109    * - std::vector<std::forward_list<_Node>::iterator> representing the buckets
00110    *
00111    * The non-empty buckets contain the node before the first bucket node. This
00112    * design allow to implement something like a std::forward_list::insert_after
00113    * on container insertion and std::forward_list::erase_after on container
00114    * erase calls. _M_before_begin is equivalent to
00115    * std::foward_list::before_begin. Empty buckets are containing nullptr.
00116    * Note that one of the non-empty bucket contains &_M_before_begin which is
00117    * not a derefenrenceable node so the node pointers in buckets shall never be
00118    * derefenrenced, only its next node can be.
00119    * 
00120    * Walk through a bucket nodes require a check on the hash code to see if the
00121    * node is still in the bucket. Such a design impose a quite efficient hash
00122    * functor and is one of the reasons it is highly advise to set
00123    * __cache_hash_code to true.
00124    *
00125    * The container iterators are simply built from nodes. This way incrementing
00126    * the iterator is perfectly efficient independent of how many empty buckets
00127    * there are in the container.
00128    *
00129    * On insert we compute element hash code and thanks to it find the bucket
00130    * index. If the element must be inserted on an empty bucket we add it at the
00131    * beginning of the singly linked list and make the bucket point to
00132    * _M_before_begin. The bucket that used to point to _M_before_begin, if any,
00133    * is updated to point to its new before begin node.
00134    *
00135    * On erase, the simple iterator design impose to use the hash functor to get
00136    * the index of the bucket to update. For this reason, when __cache_hash_code
00137    * is set to false, there is a static assertion that the hash functor cannot
00138    * throw.
00139    */
00140 
00141   template<typename _Key, typename _Value, typename _Allocator,
00142        typename _ExtractKey, typename _Equal,
00143        typename _H1, typename _H2, typename _Hash,
00144        typename _RehashPolicy,
00145        bool __cache_hash_code,
00146        bool __constant_iterators,
00147        bool __unique_keys>
00148     class _Hashtable
00149     : public __detail::_Rehash_base<_RehashPolicy,
00150                     _Hashtable<_Key, _Value, _Allocator,
00151                            _ExtractKey,
00152                            _Equal, _H1, _H2, _Hash,
00153                            _RehashPolicy,
00154                            __cache_hash_code,
00155                            __constant_iterators,
00156                            __unique_keys> >,
00157       public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
00158                        _H1, _H2, _Hash, __cache_hash_code>,
00159       public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
00160                  _Hashtable<_Key, _Value, _Allocator,
00161                         _ExtractKey,
00162                         _Equal, _H1, _H2, _Hash,
00163                         _RehashPolicy,
00164                         __cache_hash_code,
00165                         __constant_iterators,
00166                         __unique_keys> >,
00167       public __detail::_Equality_base<_ExtractKey, __unique_keys,
00168                       _Hashtable<_Key, _Value, _Allocator,
00169                          _ExtractKey,
00170                          _Equal, _H1, _H2, _Hash,
00171                          _RehashPolicy,
00172                          __cache_hash_code,
00173                          __constant_iterators,
00174                          __unique_keys> >
00175     {
00176       template<typename _Cond>
00177     using __if_hash_code_cached
00178       = __or_<__not_<integral_constant<bool, __cache_hash_code>>, _Cond>;
00179 
00180       template<typename _Cond>
00181     using __if_hash_code_not_cached
00182       = __or_<integral_constant<bool, __cache_hash_code>, _Cond>;
00183 
00184       // When hash codes are not cached the hash functor shall not throw
00185       // because it is used in methods (erase, swap...) that shall not throw.
00186       static_assert(__if_hash_code_not_cached<__detail::__is_noexcept_hash<_Key,
00187                                 _H1>>::value,
00188             "Cache the hash code or qualify your hash functor with noexcept");
00189 
00190       // Following two static assertions are necessary to guarantee that
00191       // swapping two hashtable instances won't invalidate associated local
00192       // iterators.
00193 
00194       // When hash codes are cached local iterator only uses H2 which must then
00195       // be empty.
00196       static_assert(__if_hash_code_cached<is_empty<_H2>>::value,
00197         "Functor used to map hash code to bucket index must be empty");
00198 
00199       typedef __detail::_Hash_code_base<_Key, _Value, _ExtractKey,
00200                     _H1, _H2, _Hash,
00201                         __cache_hash_code> _HCBase;
00202 
00203       // When hash codes are not cached local iterator is going to use _HCBase
00204       // above to compute node bucket index so it has to be empty.
00205       static_assert(__if_hash_code_not_cached<is_empty<_HCBase>>::value,
00206         "Cache the hash code or make functors involved in hash code"
00207         " and bucket index computation empty");
00208 
00209     public:
00210       typedef _Allocator                                  allocator_type;
00211       typedef _Value                                      value_type;
00212       typedef _Key                                        key_type;
00213       typedef _Equal                                      key_equal;
00214       // mapped_type, if present, comes from _Map_base.
00215       // hasher, if present, comes from _Hash_code_base.
00216       typedef typename _Allocator::pointer                pointer;
00217       typedef typename _Allocator::const_pointer          const_pointer;
00218       typedef typename _Allocator::reference              reference;
00219       typedef typename _Allocator::const_reference        const_reference;
00220 
00221       typedef std::size_t                                 size_type;
00222       typedef std::ptrdiff_t                              difference_type;
00223       typedef __detail::_Local_iterator<key_type, value_type, _ExtractKey,
00224                     _H1, _H2, _Hash,
00225                     __constant_iterators,
00226                     __cache_hash_code>
00227                               local_iterator;
00228       typedef __detail::_Local_const_iterator<key_type, value_type, _ExtractKey,
00229                           _H1, _H2, _Hash,
00230                           __constant_iterators,
00231                           __cache_hash_code>
00232                               const_local_iterator;
00233       typedef __detail::_Node_iterator<value_type, __constant_iterators,
00234                        __cache_hash_code>
00235                               iterator;
00236       typedef __detail::_Node_const_iterator<value_type,
00237                          __constant_iterators,
00238                          __cache_hash_code>
00239                               const_iterator;
00240 
00241       template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
00242            typename _Hashtable2>
00243     friend struct __detail::_Map_base;
00244 
00245     private:
00246       typedef typename _RehashPolicy::_State _RehashPolicyState;
00247       typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
00248       typedef typename _Allocator::template rebind<_Node>::other
00249                             _Node_allocator_type;
00250       typedef __detail::_Hash_node_base _BaseNode;
00251       typedef _BaseNode* _Bucket;
00252       typedef typename _Allocator::template rebind<_Bucket>::other
00253                             _Bucket_allocator_type;
00254 
00255       typedef typename _Allocator::template rebind<_Value>::other
00256                             _Value_allocator_type;
00257 
00258       _Node_allocator_type  _M_node_allocator;
00259       _Bucket*          _M_buckets;
00260       size_type         _M_bucket_count;
00261       _BaseNode         _M_before_begin;
00262       size_type         _M_element_count;
00263       _RehashPolicy     _M_rehash_policy;
00264 
00265       template<typename... _Args>
00266     _Node*
00267     _M_allocate_node(_Args&&... __args);
00268 
00269       void
00270       _M_deallocate_node(_Node* __n);
00271 
00272       // Deallocate the linked list of nodes pointed to by __n
00273       void
00274       _M_deallocate_nodes(_Node* __n);
00275 
00276       _Bucket*
00277       _M_allocate_buckets(size_type __n);
00278 
00279       void
00280       _M_deallocate_buckets(_Bucket*, size_type __n);
00281 
00282       // Gets bucket begin, deals with the fact that non-empty buckets contain
00283       // their before begin node.
00284       _Node*
00285       _M_bucket_begin(size_type __bkt) const;
00286 
00287       _Node*
00288       _M_begin() const
00289       { return static_cast<_Node*>(_M_before_begin._M_nxt); }
00290 
00291     public:
00292       // Constructor, destructor, assignment, swap
00293       _Hashtable(size_type __bucket_hint,
00294          const _H1&, const _H2&, const _Hash&,
00295          const _Equal&, const _ExtractKey&,
00296          const allocator_type&);
00297 
00298       template<typename _InputIterator>
00299     _Hashtable(_InputIterator __first, _InputIterator __last,
00300            size_type __bucket_hint,
00301            const _H1&, const _H2&, const _Hash&,
00302            const _Equal&, const _ExtractKey&,
00303            const allocator_type&);
00304 
00305       _Hashtable(const _Hashtable&);
00306 
00307       _Hashtable(_Hashtable&&);
00308 
00309       _Hashtable&
00310       operator=(const _Hashtable& __ht)
00311       {
00312     _Hashtable __tmp(__ht);
00313     this->swap(__tmp);
00314     return *this;
00315       }
00316 
00317       _Hashtable&
00318       operator=(_Hashtable&& __ht)
00319       {
00320     // NB: DR 1204.
00321     // NB: DR 675.
00322     this->clear();
00323     this->swap(__ht);
00324     return *this;
00325       }
00326 
00327       ~_Hashtable() noexcept;
00328 
00329       void swap(_Hashtable&);
00330 
00331       // Basic container operations
00332       iterator
00333       begin() noexcept
00334       { return iterator(_M_begin()); }
00335 
00336       const_iterator
00337       begin() const noexcept
00338       { return const_iterator(_M_begin()); }
00339 
00340       iterator
00341       end() noexcept
00342       { return iterator(nullptr); }
00343 
00344       const_iterator
00345       end() const noexcept
00346       { return const_iterator(nullptr); }
00347 
00348       const_iterator
00349       cbegin() const noexcept
00350       { return const_iterator(_M_begin()); }
00351 
00352       const_iterator
00353       cend() const noexcept
00354       { return const_iterator(nullptr); }
00355 
00356       size_type
00357       size() const noexcept
00358       { return _M_element_count; }
00359 
00360       bool
00361       empty() const noexcept
00362       { return size() == 0; }
00363 
00364       allocator_type
00365       get_allocator() const noexcept
00366       { return allocator_type(_M_node_allocator); }
00367 
00368       size_type
00369       max_size() const noexcept
00370       { return _M_node_allocator.max_size(); }
00371 
00372       // Observers
00373       key_equal
00374       key_eq() const
00375       { return this->_M_eq(); }
00376 
00377       // hash_function, if present, comes from _Hash_code_base.
00378 
00379       // Bucket operations
00380       size_type
00381       bucket_count() const noexcept
00382       { return _M_bucket_count; }
00383 
00384       size_type
00385       max_bucket_count() const noexcept
00386       { return max_size(); }
00387 
00388       size_type
00389       bucket_size(size_type __n) const
00390       { return std::distance(begin(__n), end(__n)); }
00391 
00392       size_type
00393       bucket(const key_type& __k) const
00394       { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
00395 
00396       local_iterator
00397       begin(size_type __n)
00398       { return local_iterator(_M_bucket_begin(__n), __n,
00399                   _M_bucket_count); }
00400 
00401       local_iterator
00402       end(size_type __n)
00403       { return local_iterator(nullptr, __n, _M_bucket_count); }
00404 
00405       const_local_iterator
00406       begin(size_type __n) const
00407       { return const_local_iterator(_M_bucket_begin(__n), __n,
00408                     _M_bucket_count); }
00409 
00410       const_local_iterator
00411       end(size_type __n) const
00412       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
00413 
00414       // DR 691.
00415       const_local_iterator
00416       cbegin(size_type __n) const
00417       { return const_local_iterator(_M_bucket_begin(__n), __n,
00418                     _M_bucket_count); }
00419 
00420       const_local_iterator
00421       cend(size_type __n) const
00422       { return const_local_iterator(nullptr, __n, _M_bucket_count); }
00423 
00424       float
00425       load_factor() const noexcept
00426       {
00427     return static_cast<float>(size()) / static_cast<float>(bucket_count());
00428       }
00429 
00430       // max_load_factor, if present, comes from _Rehash_base.
00431 
00432       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
00433       // useful if _RehashPolicy is something other than the default.
00434       const _RehashPolicy&
00435       __rehash_policy() const
00436       { return _M_rehash_policy; }
00437 
00438       void
00439       __rehash_policy(const _RehashPolicy&);
00440 
00441       // Lookup.
00442       iterator
00443       find(const key_type& __k);
00444 
00445       const_iterator
00446       find(const key_type& __k) const;
00447 
00448       size_type
00449       count(const key_type& __k) const;
00450 
00451       std::pair<iterator, iterator>
00452       equal_range(const key_type& __k);
00453 
00454       std::pair<const_iterator, const_iterator>
00455       equal_range(const key_type& __k) const;
00456 
00457     private:
00458       // Bucket index computation helpers.
00459       size_type
00460       _M_bucket_index(_Node* __n) const
00461       { return _HCBase::_M_bucket_index(__n, _M_bucket_count); }
00462 
00463       size_type
00464       _M_bucket_index(const key_type& __k,
00465               typename _Hashtable::_Hash_code_type __c) const
00466       { return _HCBase::_M_bucket_index(__k, __c, _M_bucket_count); }
00467 
00468       // Find and insert helper functions and types
00469       // Find the node before the one matching the criteria.
00470       _BaseNode*
00471       _M_find_before_node(size_type, const key_type&,
00472               typename _Hashtable::_Hash_code_type) const;
00473 
00474       _Node*
00475       _M_find_node(size_type __bkt, const key_type& __key,
00476            typename _Hashtable::_Hash_code_type __c) const
00477       {
00478     _BaseNode* __before_n = _M_find_before_node(__bkt, __key, __c);
00479     if (__before_n)
00480       return static_cast<_Node*>(__before_n->_M_nxt);
00481     return nullptr;
00482       }
00483 
00484       // Insert a node at the beginning of a bucket.
00485       void
00486       _M_insert_bucket_begin(size_type, _Node*);
00487 
00488       // Remove the bucket first node
00489       void
00490       _M_remove_bucket_begin(size_type __bkt, _Node* __next_n,
00491                  size_type __next_bkt);
00492 
00493       // Get the node before __n in the bucket __bkt
00494       _BaseNode*
00495       _M_get_previous_node(size_type __bkt, _BaseNode* __n);
00496 
00497       template<typename _Arg>
00498     iterator
00499     _M_insert_bucket(_Arg&&, size_type,
00500              typename _Hashtable::_Hash_code_type);
00501 
00502       typedef typename std::conditional<__unique_keys,
00503                     std::pair<iterator, bool>,
00504                     iterator>::type
00505     _Insert_Return_Type;
00506 
00507       typedef typename std::conditional<__unique_keys,
00508                     std::_Select1st<_Insert_Return_Type>,
00509                     std::_Identity<_Insert_Return_Type>
00510                    >::type
00511     _Insert_Conv_Type;
00512 
00513     protected:
00514       template<typename... _Args>
00515     std::pair<iterator, bool>
00516     _M_emplace(std::true_type, _Args&&... __args);
00517 
00518       template<typename... _Args>
00519     iterator
00520     _M_emplace(std::false_type, _Args&&... __args);
00521 
00522       template<typename _Arg>
00523     std::pair<iterator, bool>
00524     _M_insert(_Arg&&, std::true_type);
00525 
00526       template<typename _Arg>
00527     iterator
00528     _M_insert(_Arg&&, std::false_type);
00529 
00530     public:
00531       // Emplace, insert and erase
00532       template<typename... _Args>
00533     _Insert_Return_Type
00534     emplace(_Args&&... __args)
00535     { return _M_emplace(integral_constant<bool, __unique_keys>(),
00536                 std::forward<_Args>(__args)...); }
00537 
00538       template<typename... _Args>
00539     iterator
00540     emplace_hint(const_iterator, _Args&&... __args)
00541     { return _Insert_Conv_Type()(emplace(std::forward<_Args>(__args)...)); }
00542 
00543       _Insert_Return_Type
00544       insert(const value_type& __v)
00545       { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
00546 
00547       iterator
00548       insert(const_iterator, const value_type& __v)
00549       { return _Insert_Conv_Type()(insert(__v)); }
00550 
00551       template<typename _Pair, typename = typename
00552     std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
00553                   std::is_constructible<value_type,
00554                             _Pair&&>>::value>::type>
00555     _Insert_Return_Type
00556     insert(_Pair&& __v)
00557     { return _M_insert(std::forward<_Pair>(__v),
00558                integral_constant<bool, __unique_keys>()); }
00559 
00560       template<typename _Pair, typename = typename
00561         std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
00562                   std::is_constructible<value_type,
00563                             _Pair&&>>::value>::type>
00564     iterator
00565     insert(const_iterator, _Pair&& __v)
00566     { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
00567 
00568       template<typename _InputIterator>
00569     void
00570     insert(_InputIterator __first, _InputIterator __last);
00571 
00572       void
00573       insert(initializer_list<value_type> __l)
00574       { this->insert(__l.begin(), __l.end()); }
00575 
00576       iterator
00577       erase(const_iterator);
00578 
00579       // LWG 2059.
00580       iterator
00581       erase(iterator __it)
00582       { return erase(const_iterator(__it)); }
00583 
00584       size_type
00585       erase(const key_type&);
00586 
00587       iterator
00588       erase(const_iterator, const_iterator);
00589 
00590       void
00591       clear() noexcept;
00592 
00593       // Set number of buckets to be appropriate for container of n element.
00594       void rehash(size_type __n);
00595 
00596       // DR 1189.
00597       // reserve, if present, comes from _Rehash_base.
00598 
00599     private:
00600       // Helper rehash method used when keys are unique.
00601       void _M_rehash_aux(size_type __n, std::true_type);
00602 
00603       // Helper rehash method used when keys can be non-unique.
00604       void _M_rehash_aux(size_type __n, std::false_type);
00605 
00606       // Unconditionally change size of bucket array to n, restore hash policy
00607       // state to __state on exception.
00608       void _M_rehash(size_type __n, const _RehashPolicyState& __state);
00609     };
00610 
00611 
00612   // Definitions of class template _Hashtable's out-of-line member functions.
00613   template<typename _Key, typename _Value,
00614        typename _Allocator, typename _ExtractKey, typename _Equal,
00615        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00616        bool __chc, bool __cit, bool __uk>
00617     template<typename... _Args>
00618       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00619               _H1, _H2, _Hash, _RehashPolicy,
00620               __chc, __cit, __uk>::_Node*
00621       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00622          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00623       _M_allocate_node(_Args&&... __args)
00624       {
00625     _Node* __n = _M_node_allocator.allocate(1);
00626     __try
00627       {
00628         _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
00629         return __n;
00630       }
00631     __catch(...)
00632       {
00633         _M_node_allocator.deallocate(__n, 1);
00634         __throw_exception_again;
00635       }
00636       }
00637 
00638   template<typename _Key, typename _Value,
00639        typename _Allocator, typename _ExtractKey, typename _Equal,
00640        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00641        bool __chc, bool __cit, bool __uk>
00642     void
00643     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00644            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00645     _M_deallocate_node(_Node* __n)
00646     {
00647       _M_node_allocator.destroy(__n);
00648       _M_node_allocator.deallocate(__n, 1);
00649     }
00650 
00651   template<typename _Key, typename _Value,
00652        typename _Allocator, typename _ExtractKey, typename _Equal,
00653        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00654        bool __chc, bool __cit, bool __uk>
00655     void
00656     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00657            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00658     _M_deallocate_nodes(_Node* __n)
00659     {
00660       while (__n)
00661     {
00662       _Node* __tmp = __n;
00663       __n = __n->_M_next();
00664       _M_deallocate_node(__tmp);
00665     }
00666     }
00667 
00668   template<typename _Key, typename _Value,
00669        typename _Allocator, typename _ExtractKey, typename _Equal,
00670        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00671        bool __chc, bool __cit, bool __uk>
00672     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00673             _H1, _H2, _Hash, _RehashPolicy,
00674             __chc, __cit, __uk>::_Bucket*
00675     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00676            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00677     _M_allocate_buckets(size_type __n)
00678     {
00679       _Bucket_allocator_type __alloc(_M_node_allocator);
00680 
00681       _Bucket* __p = __alloc.allocate(__n);
00682       __builtin_memset(__p, 0, __n * sizeof(_Bucket));
00683       return __p;
00684     }
00685 
00686   template<typename _Key, typename _Value,
00687        typename _Allocator, typename _ExtractKey, typename _Equal,
00688        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00689        bool __chc, bool __cit, bool __uk>
00690     void
00691     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00692            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00693     _M_deallocate_buckets(_Bucket* __p, size_type __n)
00694     {
00695       _Bucket_allocator_type __alloc(_M_node_allocator);
00696       __alloc.deallocate(__p, __n);
00697     }
00698 
00699   template<typename _Key, typename _Value,
00700        typename _Allocator, typename _ExtractKey, typename _Equal,
00701        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00702        bool __chc, bool __cit, bool __uk>
00703     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
00704             _Equal, _H1, _H2, _Hash, _RehashPolicy,
00705             __chc, __cit, __uk>::_Node*
00706     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00707            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00708     _M_bucket_begin(size_type __bkt) const
00709     {
00710       _BaseNode* __n = _M_buckets[__bkt];
00711       return __n ? static_cast<_Node*>(__n->_M_nxt) : nullptr;
00712     }
00713 
00714   template<typename _Key, typename _Value,
00715        typename _Allocator, typename _ExtractKey, typename _Equal,
00716        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00717        bool __chc, bool __cit, bool __uk>
00718     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00719            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00720     _Hashtable(size_type __bucket_hint,
00721            const _H1& __h1, const _H2& __h2, const _Hash& __h,
00722            const _Equal& __eq, const _ExtractKey& __exk,
00723            const allocator_type& __a)
00724     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
00725       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
00726                 _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
00727                             __eq),
00728       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
00729       _M_node_allocator(__a),
00730       _M_bucket_count(0),
00731       _M_element_count(0),
00732       _M_rehash_policy()
00733     {
00734       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
00735       // We don't want the rehash policy to ask for the hashtable to shrink
00736       // on the first insertion so we need to reset its previous resize level.
00737       _M_rehash_policy._M_prev_resize = 0;
00738       _M_buckets = _M_allocate_buckets(_M_bucket_count);
00739     }
00740 
00741   template<typename _Key, typename _Value,
00742        typename _Allocator, typename _ExtractKey, typename _Equal,
00743        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00744        bool __chc, bool __cit, bool __uk>
00745     template<typename _InputIterator>
00746       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00747          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00748       _Hashtable(_InputIterator __f, _InputIterator __l,
00749          size_type __bucket_hint,
00750          const _H1& __h1, const _H2& __h2, const _Hash& __h,
00751          const _Equal& __eq, const _ExtractKey& __exk,
00752          const allocator_type& __a)
00753       : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
00754     __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
00755                   _H1, _H2, _Hash, __chc>(__exk, __h1, __h2, __h,
00756                               __eq),
00757     __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
00758     _M_node_allocator(__a),
00759     _M_bucket_count(0),
00760     _M_element_count(0),
00761     _M_rehash_policy()
00762       {
00763     _M_bucket_count =
00764       _M_rehash_policy._M_bkt_for_elements(__detail::__distance_fw(__f,
00765                                        __l));
00766     if (_M_bucket_count <= __bucket_hint)
00767       _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
00768 
00769         // We don't want the rehash policy to ask for the hashtable to shrink
00770         // on the first insertion so we need to reset its previous resize
00771     // level.
00772     _M_rehash_policy._M_prev_resize = 0;
00773     _M_buckets = _M_allocate_buckets(_M_bucket_count);
00774     __try
00775       {
00776         for (; __f != __l; ++__f)
00777           this->insert(*__f);
00778       }
00779     __catch(...)
00780       {
00781         clear();
00782         _M_deallocate_buckets(_M_buckets, _M_bucket_count);
00783         __throw_exception_again;
00784       }
00785       }
00786 
00787   template<typename _Key, typename _Value,
00788        typename _Allocator, typename _ExtractKey, typename _Equal,
00789        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00790        bool __chc, bool __cit, bool __uk>
00791     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00792            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00793     _Hashtable(const _Hashtable& __ht)
00794     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
00795       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
00796                 _H1, _H2, _Hash, __chc>(__ht),
00797       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
00798       _M_node_allocator(__ht._M_node_allocator),
00799       _M_bucket_count(__ht._M_bucket_count),
00800       _M_element_count(__ht._M_element_count),
00801       _M_rehash_policy(__ht._M_rehash_policy)
00802     {
00803       _M_buckets = _M_allocate_buckets(_M_bucket_count);
00804       __try
00805     {
00806       if (!__ht._M_before_begin._M_nxt)
00807         return;
00808 
00809       // First deal with the special first node pointed to by
00810       // _M_before_begin.
00811       const _Node* __ht_n = __ht._M_begin();
00812       _Node* __this_n = _M_allocate_node(__ht_n->_M_v);
00813       this->_M_copy_code(__this_n, __ht_n);
00814       _M_before_begin._M_nxt = __this_n;
00815       _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
00816 
00817       // Then deal with other nodes.
00818       _BaseNode* __prev_n = __this_n;
00819       for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
00820         {
00821           __this_n = _M_allocate_node(__ht_n->_M_v);
00822           __prev_n->_M_nxt = __this_n;
00823           this->_M_copy_code(__this_n, __ht_n);
00824           size_type __bkt = _M_bucket_index(__this_n);
00825           if (!_M_buckets[__bkt])
00826         _M_buckets[__bkt] = __prev_n;
00827           __prev_n = __this_n;
00828         }
00829     }
00830       __catch(...)
00831     {
00832       clear();
00833       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
00834       __throw_exception_again;
00835     }
00836     }
00837 
00838   template<typename _Key, typename _Value,
00839        typename _Allocator, typename _ExtractKey, typename _Equal,
00840        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00841        bool __chc, bool __cit, bool __uk>
00842     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00843            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00844     _Hashtable(_Hashtable&& __ht)
00845     : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
00846       __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
00847                 _H1, _H2, _Hash, __chc>(__ht),
00848       __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
00849       _M_node_allocator(std::move(__ht._M_node_allocator)),
00850       _M_buckets(__ht._M_buckets),
00851       _M_bucket_count(__ht._M_bucket_count),
00852       _M_before_begin(__ht._M_before_begin._M_nxt),
00853       _M_element_count(__ht._M_element_count),
00854       _M_rehash_policy(__ht._M_rehash_policy)
00855     {
00856       // Update, if necessary, bucket pointing to before begin that hasn't move.
00857       if (_M_begin())
00858     _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
00859       __ht._M_rehash_policy = _RehashPolicy();
00860       __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
00861       __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
00862       __ht._M_before_begin._M_nxt = nullptr;
00863       __ht._M_element_count = 0;
00864     }
00865 
00866   template<typename _Key, typename _Value,
00867        typename _Allocator, typename _ExtractKey, typename _Equal,
00868        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00869        bool __chc, bool __cit, bool __uk>
00870     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00871            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00872     ~_Hashtable() noexcept
00873     {
00874       clear();
00875       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
00876     }
00877 
00878   template<typename _Key, typename _Value,
00879        typename _Allocator, typename _ExtractKey, typename _Equal,
00880        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00881        bool __chc, bool __cit, bool __uk>
00882     void
00883     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00884            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00885     swap(_Hashtable& __x)
00886     {
00887       // The only base class with member variables is hash_code_base.  We
00888       // define _Hash_code_base::_M_swap because different specializations
00889       // have different members.
00890       this->_M_swap(__x);
00891 
00892       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00893       // 431. Swapping containers with unequal allocators.
00894       std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
00895                             __x._M_node_allocator);
00896 
00897       std::swap(_M_rehash_policy, __x._M_rehash_policy);
00898       std::swap(_M_buckets, __x._M_buckets);
00899       std::swap(_M_bucket_count, __x._M_bucket_count);
00900       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
00901       std::swap(_M_element_count, __x._M_element_count);
00902       // Fix buckets containing the _M_before_begin pointers that can't be
00903       // swapped.
00904       if (_M_begin())
00905     _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
00906       if (__x._M_begin())
00907     __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
00908       = &(__x._M_before_begin);
00909     }
00910 
00911   template<typename _Key, typename _Value,
00912        typename _Allocator, typename _ExtractKey, typename _Equal,
00913        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00914        bool __chc, bool __cit, bool __uk>
00915     void
00916     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00917            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00918     __rehash_policy(const _RehashPolicy& __pol)
00919     {
00920       size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
00921       if (__n_bkt != _M_bucket_count)
00922     _M_rehash(__n_bkt, _M_rehash_policy._M_state());
00923       _M_rehash_policy = __pol;
00924     }
00925 
00926   template<typename _Key, typename _Value,
00927        typename _Allocator, typename _ExtractKey, typename _Equal,
00928        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00929        bool __chc, bool __cit, bool __uk>
00930     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00931             _H1, _H2, _Hash, _RehashPolicy,
00932             __chc, __cit, __uk>::iterator
00933     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00934            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00935     find(const key_type& __k)
00936     {
00937       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00938       std::size_t __n = _M_bucket_index(__k, __code);
00939       _Node* __p = _M_find_node(__n, __k, __code);
00940       return __p ? iterator(__p) : this->end();
00941     }
00942 
00943   template<typename _Key, typename _Value,
00944        typename _Allocator, typename _ExtractKey, typename _Equal,
00945        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00946        bool __chc, bool __cit, bool __uk>
00947     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00948             _H1, _H2, _Hash, _RehashPolicy,
00949             __chc, __cit, __uk>::const_iterator
00950     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00951            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00952     find(const key_type& __k) const
00953     {
00954       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00955       std::size_t __n = _M_bucket_index(__k, __code);
00956       _Node* __p = _M_find_node(__n, __k, __code);
00957       return __p ? const_iterator(__p) : this->end();
00958     }
00959 
00960   template<typename _Key, typename _Value,
00961        typename _Allocator, typename _ExtractKey, typename _Equal,
00962        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00963        bool __chc, bool __cit, bool __uk>
00964     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00965             _H1, _H2, _Hash, _RehashPolicy,
00966             __chc, __cit, __uk>::size_type
00967     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
00968            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
00969     count(const key_type& __k) const
00970     {
00971       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
00972       std::size_t __n = _M_bucket_index(__k, __code);
00973       _Node* __p = _M_bucket_begin(__n);
00974       if (!__p)
00975     return 0;
00976 
00977       std::size_t __result = 0;
00978       for (;; __p = __p->_M_next())
00979     {
00980       if (this->_M_equals(__k, __code, __p))
00981         ++__result;
00982       else if (__result)
00983         // All equivalent values are next to each other, if we found a not
00984         // equivalent value after an equivalent one it means that we won't
00985         // find anymore an equivalent value.
00986         break;
00987       if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
00988         break;
00989     }
00990       return __result;
00991     }
00992 
00993   template<typename _Key, typename _Value,
00994        typename _Allocator, typename _ExtractKey, typename _Equal,
00995        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00996        bool __chc, bool __cit, bool __uk>
00997     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
00998                   _ExtractKey, _Equal, _H1,
00999                   _H2, _Hash, _RehashPolicy,
01000                   __chc, __cit, __uk>::iterator,
01001           typename _Hashtable<_Key, _Value, _Allocator,
01002                   _ExtractKey, _Equal, _H1,
01003                   _H2, _Hash, _RehashPolicy,
01004                   __chc, __cit, __uk>::iterator>
01005     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01006            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01007     equal_range(const key_type& __k)
01008     {
01009       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
01010       std::size_t __n = _M_bucket_index(__k, __code);
01011       _Node* __p = _M_find_node(__n, __k, __code);
01012 
01013       if (__p)
01014     {
01015       _Node* __p1 = __p->_M_next();
01016       while (__p1 && _M_bucket_index(__p1) == __n
01017          && this->_M_equals(__k, __code, __p1))
01018         __p1 = __p1->_M_next();
01019 
01020       return std::make_pair(iterator(__p), iterator(__p1));
01021     }
01022       else
01023     return std::make_pair(this->end(), this->end());
01024     }
01025 
01026   template<typename _Key, typename _Value,
01027        typename _Allocator, typename _ExtractKey, typename _Equal,
01028        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01029        bool __chc, bool __cit, bool __uk>
01030     std::pair<typename _Hashtable<_Key, _Value, _Allocator,
01031                   _ExtractKey, _Equal, _H1,
01032                   _H2, _Hash, _RehashPolicy,
01033                   __chc, __cit, __uk>::const_iterator,
01034           typename _Hashtable<_Key, _Value, _Allocator,
01035                   _ExtractKey, _Equal, _H1,
01036                   _H2, _Hash, _RehashPolicy,
01037                   __chc, __cit, __uk>::const_iterator>
01038     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01039            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01040     equal_range(const key_type& __k) const
01041     {
01042       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
01043       std::size_t __n = _M_bucket_index(__k, __code);
01044       _Node* __p = _M_find_node(__n, __k, __code);
01045 
01046       if (__p)
01047     {
01048       _Node* __p1 = __p->_M_next();
01049       while (__p1 && _M_bucket_index(__p1) == __n
01050          && this->_M_equals(__k, __code, __p1))
01051         __p1 = __p1->_M_next();
01052 
01053       return std::make_pair(const_iterator(__p), const_iterator(__p1));
01054     }
01055       else
01056     return std::make_pair(this->end(), this->end());
01057     }
01058 
01059   // Find the node whose key compares equal to k in the bucket n. Return nullptr
01060   // if no node is found.
01061   template<typename _Key, typename _Value,
01062        typename _Allocator, typename _ExtractKey, typename _Equal,
01063        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01064        bool __chc, bool __cit, bool __uk>
01065     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
01066             _Equal, _H1, _H2, _Hash, _RehashPolicy,
01067             __chc, __cit, __uk>::_BaseNode*
01068     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01069            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01070     _M_find_before_node(size_type __n, const key_type& __k,
01071             typename _Hashtable::_Hash_code_type __code) const
01072     {
01073       _BaseNode* __prev_p = _M_buckets[__n];
01074       if (!__prev_p)
01075     return nullptr;
01076       _Node* __p = static_cast<_Node*>(__prev_p->_M_nxt);
01077       for (;; __p = __p->_M_next())
01078     {
01079       if (this->_M_equals(__k, __code, __p))
01080         return __prev_p;
01081       if (!(__p->_M_nxt) || _M_bucket_index(__p->_M_next()) != __n)
01082         break;
01083       __prev_p = __p;
01084     }
01085       return nullptr;
01086     }
01087 
01088   template<typename _Key, typename _Value,
01089        typename _Allocator, typename _ExtractKey, typename _Equal,
01090        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01091        bool __chc, bool __cit, bool __uk>
01092     void
01093     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01094            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01095     _M_insert_bucket_begin(size_type __bkt, _Node* __new_node)
01096     {
01097       if (_M_buckets[__bkt])
01098     {
01099       // Bucket is not empty, we just need to insert the new node after the
01100       // bucket before begin.
01101       __new_node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
01102       _M_buckets[__bkt]->_M_nxt = __new_node;
01103     }
01104       else
01105     {
01106       // The bucket is empty, the new node is inserted at the beginning of
01107       // the singly linked list and the bucket will contain _M_before_begin
01108       // pointer.
01109       __new_node->_M_nxt = _M_before_begin._M_nxt;
01110       _M_before_begin._M_nxt = __new_node;
01111       if (__new_node->_M_nxt)
01112         // We must update former begin bucket that is pointing to
01113         // _M_before_begin.
01114         _M_buckets[_M_bucket_index(__new_node->_M_next())] = __new_node;
01115       _M_buckets[__bkt] = &_M_before_begin;
01116     }
01117     }
01118 
01119   template<typename _Key, typename _Value,
01120        typename _Allocator, typename _ExtractKey, typename _Equal,
01121        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01122        bool __chc, bool __cit, bool __uk>
01123     void
01124     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01125            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01126     _M_remove_bucket_begin(size_type __bkt, _Node* __next, size_type __next_bkt)
01127     {
01128       if (!__next || __next_bkt != __bkt)
01129     {
01130       // Bucket is now empty
01131       // First update next bucket if any
01132       if (__next)
01133         _M_buckets[__next_bkt] = _M_buckets[__bkt];
01134       // Second update before begin node if necessary
01135       if (&_M_before_begin == _M_buckets[__bkt])
01136         _M_before_begin._M_nxt = __next;
01137       _M_buckets[__bkt] = nullptr;
01138     }
01139     }
01140 
01141   template<typename _Key, typename _Value,
01142        typename _Allocator, typename _ExtractKey, typename _Equal,
01143        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01144        bool __chc, bool __cit, bool __uk>
01145     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
01146             _Equal, _H1, _H2, _Hash, _RehashPolicy,
01147             __chc, __cit, __uk>::_BaseNode*
01148     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01149            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01150     _M_get_previous_node(size_type __bkt, _BaseNode* __n)
01151     {
01152       _BaseNode* __prev_n = _M_buckets[__bkt];
01153       while (__prev_n->_M_nxt != __n)
01154     __prev_n = __prev_n->_M_nxt;
01155       return __prev_n;
01156     }
01157 
01158   template<typename _Key, typename _Value,
01159        typename _Allocator, typename _ExtractKey, typename _Equal,
01160        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01161        bool __chc, bool __cit, bool __uk>
01162     template<typename... _Args>
01163       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
01164                     _ExtractKey, _Equal, _H1,
01165                     _H2, _Hash, _RehashPolicy,
01166                     __chc, __cit, __uk>::iterator, bool>
01167       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01168          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01169       _M_emplace(std::true_type, _Args&&... __args)
01170       {
01171     // First build the node to get access to the hash code
01172     _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
01173     __try
01174       {
01175         const key_type& __k = this->_M_extract()(__new_node->_M_v);
01176         typename _Hashtable::_Hash_code_type __code
01177           = this->_M_hash_code(__k);
01178         size_type __bkt = _M_bucket_index(__k, __code);
01179 
01180         if (_Node* __p = _M_find_node(__bkt, __k, __code))
01181           {
01182         // There is already an equivalent node, no insertion
01183         _M_deallocate_node(__new_node);
01184         return std::make_pair(iterator(__p), false);
01185           }
01186 
01187         // We are going to insert this node
01188         this->_M_store_code(__new_node, __code);
01189         const _RehashPolicyState& __saved_state
01190           = _M_rehash_policy._M_state();
01191         std::pair<bool, std::size_t> __do_rehash
01192           = _M_rehash_policy._M_need_rehash(_M_bucket_count,
01193                         _M_element_count, 1);
01194 
01195         if (__do_rehash.first)
01196           {
01197         _M_rehash(__do_rehash.second, __saved_state);
01198         __bkt = _M_bucket_index(__k, __code);
01199           }
01200 
01201         _M_insert_bucket_begin(__bkt, __new_node);
01202         ++_M_element_count;
01203         return std::make_pair(iterator(__new_node), true);
01204       }
01205     __catch(...)
01206       {
01207         _M_deallocate_node(__new_node);
01208         __throw_exception_again;
01209       }
01210       }
01211 
01212   template<typename _Key, typename _Value,
01213        typename _Allocator, typename _ExtractKey, typename _Equal,
01214        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01215        bool __chc, bool __cit, bool __uk>
01216     template<typename... _Args>
01217       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01218               _H1, _H2, _Hash, _RehashPolicy,
01219               __chc, __cit, __uk>::iterator
01220       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01221          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01222       _M_emplace(std::false_type, _Args&&... __args)
01223       {
01224     const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
01225     std::pair<bool, std::size_t> __do_rehash
01226       = _M_rehash_policy._M_need_rehash(_M_bucket_count,
01227                         _M_element_count, 1);
01228 
01229     // First build the node to get its hash code.
01230     _Node* __new_node = _M_allocate_node(std::forward<_Args>(__args)...);
01231     __try
01232       {
01233         const key_type& __k = this->_M_extract()(__new_node->_M_v);
01234         typename _Hashtable::_Hash_code_type __code
01235           = this->_M_hash_code(__k);
01236         this->_M_store_code(__new_node, __code);
01237 
01238         // Second, do rehash if necessary.
01239         if (__do_rehash.first)
01240         _M_rehash(__do_rehash.second, __saved_state);
01241 
01242         // Third, find the node before an equivalent one.
01243         size_type __bkt = _M_bucket_index(__k, __code);
01244         _BaseNode* __prev = _M_find_before_node(__bkt, __k, __code);
01245         
01246         if (__prev)
01247           {
01248         // Insert after the node before the equivalent one.
01249         __new_node->_M_nxt = __prev->_M_nxt;
01250         __prev->_M_nxt = __new_node;
01251           }
01252         else
01253           // The inserted node has no equivalent in the hashtable. We must
01254           // insert the new node at the beginning of the bucket to preserve
01255           // equivalent elements relative positions.
01256           _M_insert_bucket_begin(__bkt, __new_node);
01257         ++_M_element_count;
01258         return iterator(__new_node);
01259       }
01260     __catch(...)
01261       {
01262         _M_deallocate_node(__new_node);
01263         __throw_exception_again;
01264       }
01265       }
01266 
01267   // Insert v in bucket n (assumes no element with its key already present).
01268   template<typename _Key, typename _Value,
01269        typename _Allocator, typename _ExtractKey, typename _Equal,
01270        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01271        bool __chc, bool __cit, bool __uk>
01272     template<typename _Arg>
01273       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01274               _H1, _H2, _Hash, _RehashPolicy,
01275               __chc, __cit, __uk>::iterator
01276       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01277          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01278       _M_insert_bucket(_Arg&& __v, size_type __n,
01279                typename _Hashtable::_Hash_code_type __code)
01280       {
01281     const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
01282     std::pair<bool, std::size_t> __do_rehash
01283       = _M_rehash_policy._M_need_rehash(_M_bucket_count,
01284                         _M_element_count, 1);
01285 
01286     if (__do_rehash.first)
01287       {
01288         const key_type& __k = this->_M_extract()(__v);
01289         __n = _HCBase::_M_bucket_index(__k, __code, __do_rehash.second);
01290       }
01291 
01292     _Node* __new_node = nullptr;
01293     __try
01294       {
01295         // Allocate the new node before doing the rehash so that we
01296         // don't do a rehash if the allocation throws.
01297         __new_node = _M_allocate_node(std::forward<_Arg>(__v));
01298         this->_M_store_code(__new_node, __code);
01299         if (__do_rehash.first)
01300           _M_rehash(__do_rehash.second, __saved_state);
01301 
01302         _M_insert_bucket_begin(__n, __new_node);
01303         ++_M_element_count;
01304         return iterator(__new_node);
01305       }
01306     __catch(...)
01307       {
01308         if (!__new_node)
01309           _M_rehash_policy._M_reset(__saved_state);
01310         else
01311           _M_deallocate_node(__new_node);
01312         __throw_exception_again;
01313       }
01314       }
01315 
01316   // Insert v if no element with its key is already present.
01317   template<typename _Key, typename _Value,
01318        typename _Allocator, typename _ExtractKey, typename _Equal,
01319        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01320        bool __chc, bool __cit, bool __uk>
01321     template<typename _Arg>
01322       std::pair<typename _Hashtable<_Key, _Value, _Allocator,
01323                     _ExtractKey, _Equal, _H1,
01324                     _H2, _Hash, _RehashPolicy,
01325                     __chc, __cit, __uk>::iterator, bool>
01326       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01327          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01328       _M_insert(_Arg&& __v, std::true_type)
01329       {
01330     const key_type& __k = this->_M_extract()(__v);
01331     typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
01332     size_type __n = _M_bucket_index(__k, __code);
01333 
01334     if (_Node* __p = _M_find_node(__n, __k, __code))
01335       return std::make_pair(iterator(__p), false);
01336     return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
01337                   __n, __code), true);
01338       }
01339 
01340   // Insert v unconditionally.
01341   template<typename _Key, typename _Value,
01342        typename _Allocator, typename _ExtractKey, typename _Equal,
01343        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01344        bool __chc, bool __cit, bool __uk>
01345     template<typename _Arg>
01346       typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01347               _H1, _H2, _Hash, _RehashPolicy,
01348               __chc, __cit, __uk>::iterator
01349       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01350          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01351       _M_insert(_Arg&& __v, std::false_type)
01352       {
01353     const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
01354     std::pair<bool, std::size_t> __do_rehash
01355       = _M_rehash_policy._M_need_rehash(_M_bucket_count,
01356                         _M_element_count, 1);
01357 
01358     // First compute the hash code so that we don't do anything if it throws.
01359     typename _Hashtable::_Hash_code_type __code
01360       = this->_M_hash_code(this->_M_extract()(__v));
01361 
01362     _Node* __new_node = nullptr;
01363     __try
01364       {
01365         // Second allocate new node so that we don't rehash if it throws.
01366         __new_node = _M_allocate_node(std::forward<_Arg>(__v));
01367         this->_M_store_code(__new_node, __code);
01368         if (__do_rehash.first)
01369         _M_rehash(__do_rehash.second, __saved_state);
01370 
01371         // Third, find the node before an equivalent one.
01372         size_type __bkt = _M_bucket_index(__new_node);
01373         _BaseNode* __prev
01374           = _M_find_before_node(__bkt, this->_M_extract()(__new_node->_M_v),
01375                     __code);
01376         if (__prev)
01377           {
01378         // Insert after the node before the equivalent one.
01379         __new_node->_M_nxt = __prev->_M_nxt;
01380         __prev->_M_nxt = __new_node;
01381           }
01382         else
01383           // The inserted node has no equivalent in the hashtable. We must
01384           // insert the new node at the beginning of the bucket to preserve
01385           // equivalent elements relative positions.
01386           _M_insert_bucket_begin(__bkt, __new_node);
01387         ++_M_element_count;
01388         return iterator(__new_node);
01389       }
01390     __catch(...)
01391       {
01392         if (!__new_node)
01393           _M_rehash_policy._M_reset(__saved_state);
01394         else
01395           _M_deallocate_node(__new_node);
01396         __throw_exception_again;
01397       }
01398       }
01399 
01400   template<typename _Key, typename _Value,
01401        typename _Allocator, typename _ExtractKey, typename _Equal,
01402        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01403        bool __chc, bool __cit, bool __uk>
01404     template<typename _InputIterator>
01405       void
01406       _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01407          _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01408       insert(_InputIterator __first, _InputIterator __last)
01409       {
01410     size_type __n_elt = __detail::__distance_fw(__first, __last);
01411     const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
01412     std::pair<bool, std::size_t> __do_rehash
01413       = _M_rehash_policy._M_need_rehash(_M_bucket_count,
01414                         _M_element_count, __n_elt);
01415     if (__do_rehash.first)
01416       _M_rehash(__do_rehash.second, __saved_state);
01417 
01418     for (; __first != __last; ++__first)
01419       this->insert(*__first);
01420       }
01421 
01422   template<typename _Key, typename _Value,
01423        typename _Allocator, typename _ExtractKey, typename _Equal,
01424        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01425        bool __chc, bool __cit, bool __uk>
01426     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01427             _H1, _H2, _Hash, _RehashPolicy,
01428             __chc, __cit, __uk>::iterator
01429     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01430            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01431     erase(const_iterator __it)
01432     {
01433       _Node* __n = __it._M_cur;
01434       std::size_t __bkt = _M_bucket_index(__n);
01435 
01436       // Look for previous node to unlink it from the erased one, this is why
01437       // we need buckets to contain the before begin to make this research fast.
01438       _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
01439       if (__n == _M_bucket_begin(__bkt))
01440     _M_remove_bucket_begin(__bkt, __n->_M_next(),
01441        __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
01442       else if (__n->_M_nxt)
01443     {
01444       size_type __next_bkt = _M_bucket_index(__n->_M_next());
01445       if (__next_bkt != __bkt)
01446         _M_buckets[__next_bkt] = __prev_n;
01447     }
01448 
01449       __prev_n->_M_nxt = __n->_M_nxt;
01450       iterator __result(__n->_M_next());
01451       _M_deallocate_node(__n);
01452       --_M_element_count;
01453 
01454       return __result;
01455     }
01456 
01457   template<typename _Key, typename _Value,
01458        typename _Allocator, typename _ExtractKey, typename _Equal,
01459        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01460        bool __chc, bool __cit, bool __uk>
01461     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01462             _H1, _H2, _Hash, _RehashPolicy,
01463             __chc, __cit, __uk>::size_type
01464     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01465            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01466     erase(const key_type& __k)
01467     {
01468       typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
01469       std::size_t __bkt = _M_bucket_index(__k, __code);
01470       // Look for the node before the first matching node.
01471       _BaseNode* __prev_n = _M_find_before_node(__bkt, __k, __code);
01472       if (!__prev_n)
01473     return 0;
01474       _Node* __n = static_cast<_Node*>(__prev_n->_M_nxt);
01475       bool __is_bucket_begin = _M_buckets[__bkt] == __prev_n;
01476 
01477       // We found a matching node, start deallocation loop from it
01478       std::size_t __next_bkt = __bkt;
01479       _Node* __next_n = __n;
01480       size_type __result = 0;
01481       _Node* __saved_n = nullptr;
01482       do
01483     {
01484       _Node* __p = __next_n;
01485       __next_n = __p->_M_next();
01486       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01487       // 526. Is it undefined if a function in the standard changes
01488       // in parameters?
01489       if (std::__addressof(this->_M_extract()(__p->_M_v))
01490           != std::__addressof(__k))
01491         _M_deallocate_node(__p);
01492       else
01493         __saved_n = __p;
01494       --_M_element_count;
01495       ++__result;
01496       if (!__next_n)
01497         break;
01498       __next_bkt = _M_bucket_index(__next_n);
01499     }
01500       while (__next_bkt == __bkt && this->_M_equals(__k, __code, __next_n));
01501 
01502       if (__saved_n)
01503     _M_deallocate_node(__saved_n);
01504       if (__is_bucket_begin)
01505     _M_remove_bucket_begin(__bkt, __next_n, __next_bkt);
01506       else if (__next_n && __next_bkt != __bkt)
01507     _M_buckets[__next_bkt] = __prev_n;
01508       if (__prev_n)
01509     __prev_n->_M_nxt = __next_n;
01510       return __result;
01511     }
01512 
01513   template<typename _Key, typename _Value,
01514        typename _Allocator, typename _ExtractKey, typename _Equal,
01515        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01516        bool __chc, bool __cit, bool __uk>
01517     typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01518             _H1, _H2, _Hash, _RehashPolicy,
01519             __chc, __cit, __uk>::iterator
01520     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01521            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01522     erase(const_iterator __first, const_iterator __last)
01523     {
01524       _Node* __n = __first._M_cur;
01525       _Node* __last_n = __last._M_cur;
01526       if (__n == __last_n)
01527     return iterator(__n);
01528 
01529       std::size_t __bkt = _M_bucket_index(__n);
01530 
01531       _BaseNode* __prev_n = _M_get_previous_node(__bkt, __n);
01532       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
01533       std::size_t __n_bkt = __bkt;
01534       for (;;)
01535     {
01536       do
01537         {
01538           _Node* __tmp = __n;
01539           __n = __n->_M_next();
01540           _M_deallocate_node(__tmp);
01541           --_M_element_count;
01542           if (!__n)
01543         break;
01544           __n_bkt = _M_bucket_index(__n);
01545         }
01546       while (__n != __last_n && __n_bkt == __bkt);
01547       if (__is_bucket_begin)
01548         _M_remove_bucket_begin(__bkt, __n, __n_bkt);
01549       if (__n == __last_n)
01550         break;
01551       __is_bucket_begin = true;
01552       __bkt = __n_bkt;
01553     }
01554 
01555       if (__n && (__n_bkt != __bkt || __is_bucket_begin))
01556     _M_buckets[__n_bkt] = __prev_n;
01557       __prev_n->_M_nxt = __n;
01558       return iterator(__n);
01559     }
01560 
01561   template<typename _Key, typename _Value,
01562        typename _Allocator, typename _ExtractKey, typename _Equal,
01563        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01564        bool __chc, bool __cit, bool __uk>
01565     void
01566     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01567            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01568     clear() noexcept
01569     {
01570       _M_deallocate_nodes(_M_begin());
01571       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(_Bucket));
01572       _M_element_count = 0;
01573       _M_before_begin._M_nxt = nullptr;
01574     }
01575 
01576   template<typename _Key, typename _Value,
01577        typename _Allocator, typename _ExtractKey, typename _Equal,
01578        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01579        bool __chc, bool __cit, bool __uk>
01580     void
01581     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01582            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01583     rehash(size_type __n)
01584     {
01585       const _RehashPolicyState& __saved_state = _M_rehash_policy._M_state();
01586       std::size_t __buckets
01587     = _M_rehash_policy._M_bkt_for_elements(_M_element_count + 1);
01588       if (__buckets <= __n)
01589     __buckets = _M_rehash_policy._M_next_bkt(__n);
01590 
01591       if (__buckets != _M_bucket_count)
01592     {
01593       _M_rehash(__buckets, __saved_state);
01594       
01595       // We don't want the rehash policy to ask for the hashtable to shrink
01596       // on the next insertion so we need to reset its previous resize
01597       // level.
01598       _M_rehash_policy._M_prev_resize = 0;
01599     }
01600     }
01601 
01602   template<typename _Key, typename _Value,
01603        typename _Allocator, typename _ExtractKey, typename _Equal,
01604        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01605        bool __chc, bool __cit, bool __uk>
01606     void
01607     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01608            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01609     _M_rehash(size_type __n, const _RehashPolicyState& __state)
01610     {
01611       __try
01612     {
01613       _M_rehash_aux(__n, integral_constant<bool, __uk>());
01614     }
01615       __catch(...)
01616     {
01617       // A failure here means that buckets allocation failed.  We only
01618       // have to restore hash policy previous state.
01619       _M_rehash_policy._M_reset(__state);
01620       __throw_exception_again;
01621     }
01622     }
01623 
01624   // Rehash when there is no equivalent elements.
01625   template<typename _Key, typename _Value,
01626        typename _Allocator, typename _ExtractKey, typename _Equal,
01627        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01628        bool __chc, bool __cit, bool __uk>
01629     void
01630     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01631            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01632     _M_rehash_aux(size_type __n, std::true_type)
01633     {
01634       _Bucket* __new_buckets = _M_allocate_buckets(__n);
01635       _Node* __p = _M_begin();
01636       _M_before_begin._M_nxt = nullptr;
01637       std::size_t __bbegin_bkt;
01638       while (__p)
01639     {
01640       _Node* __next = __p->_M_next();
01641       std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
01642       if (!__new_buckets[__bkt])
01643         {
01644           __p->_M_nxt = _M_before_begin._M_nxt;
01645           _M_before_begin._M_nxt = __p;
01646           __new_buckets[__bkt] = &_M_before_begin;
01647           if (__p->_M_nxt)
01648         __new_buckets[__bbegin_bkt] = __p;
01649           __bbegin_bkt = __bkt;
01650         }
01651       else
01652         {
01653           __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
01654           __new_buckets[__bkt]->_M_nxt = __p;
01655         }
01656       __p = __next;
01657     }
01658       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
01659       _M_bucket_count = __n;
01660       _M_buckets = __new_buckets;
01661     }
01662 
01663   // Rehash when there can be equivalent elements, preserve their relative
01664   // order.
01665   template<typename _Key, typename _Value,
01666        typename _Allocator, typename _ExtractKey, typename _Equal,
01667        typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01668        bool __chc, bool __cit, bool __uk>
01669     void
01670     _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
01671            _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
01672     _M_rehash_aux(size_type __n, std::false_type)
01673     {
01674       _Bucket* __new_buckets = _M_allocate_buckets(__n);
01675 
01676       _Node* __p = _M_begin();
01677       _M_before_begin._M_nxt = nullptr;
01678       std::size_t __bbegin_bkt;
01679       std::size_t __prev_bkt;
01680       _Node* __prev_p = nullptr;
01681       bool __check_bucket = false;
01682 
01683       while (__p)
01684     {
01685       _Node* __next = __p->_M_next();
01686       std::size_t __bkt = _HCBase::_M_bucket_index(__p, __n);
01687 
01688       if (__prev_p && __prev_bkt == __bkt)
01689         {
01690           // Previous insert was already in this bucket, we insert after
01691           // the previously inserted one to preserve equivalent elements
01692           // relative order.
01693           __p->_M_nxt = __prev_p->_M_nxt;
01694           __prev_p->_M_nxt = __p;
01695           
01696           // Inserting after a node in a bucket require to check that we
01697           // haven't change the bucket last node, in this case next
01698           // bucket containing its before begin node must be updated. We
01699           // schedule a check as soon as we move out of the sequence of
01700           // equivalent nodes to limit the number of checks.
01701           __check_bucket = true;
01702         }
01703       else
01704         {
01705           if (__check_bucket)
01706         {
01707           // Check if we shall update the next bucket because of insertions
01708           // into __prev_bkt bucket.
01709           if (__prev_p->_M_nxt)
01710             {
01711               std::size_t __next_bkt
01712             = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
01713               if (__next_bkt != __prev_bkt)
01714             __new_buckets[__next_bkt] = __prev_p;
01715             }
01716           __check_bucket = false;
01717         }
01718           if (!__new_buckets[__bkt])
01719         {
01720           __p->_M_nxt = _M_before_begin._M_nxt;
01721           _M_before_begin._M_nxt = __p;
01722           __new_buckets[__bkt] = &_M_before_begin;
01723           if (__p->_M_nxt)
01724             __new_buckets[__bbegin_bkt] = __p;
01725           __bbegin_bkt = __bkt;
01726         }
01727           else
01728         {
01729           __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
01730           __new_buckets[__bkt]->_M_nxt = __p;
01731         }
01732         }
01733 
01734       __prev_p = __p;
01735       __prev_bkt = __bkt;
01736       __p = __next;
01737     }
01738 
01739       if (__check_bucket && __prev_p->_M_nxt)
01740     {
01741       std::size_t __next_bkt
01742         = _HCBase::_M_bucket_index(__prev_p->_M_next(), __n);
01743       if (__next_bkt != __prev_bkt)
01744         __new_buckets[__next_bkt] = __prev_p;
01745     }
01746 
01747       _M_deallocate_buckets(_M_buckets, _M_bucket_count);
01748       _M_bucket_count = __n;
01749       _M_buckets = __new_buckets;
01750     }
01751 
01752 _GLIBCXX_END_NAMESPACE_VERSION
01753 } // namespace std
01754 
01755 #endif // _HASHTABLE_H