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