LCOV - code coverage report
Current view: top level - usr/include/c++/9/bits - hashtable.h (source / functions) Hit Total Coverage
Test: ROSE Lines: 17 18 94.4 %
Date: 2022-12-08 13:48:47 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // hashtable.h header -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2007-2019 Free Software Foundation, Inc.
       4             : //
       5             : // This file is part of the GNU ISO C++ Library.  This library is free
       6             : // software; you can redistribute it and/or modify it under the
       7             : // terms of the GNU General Public License as published by the
       8             : // Free Software Foundation; either version 3, or (at your option)
       9             : // any later version.
      10             : 
      11             : // This library is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : 
      16             : // Under Section 7 of GPL version 3, you are granted additional
      17             : // permissions described in the GCC Runtime Library Exception, version
      18             : // 3.1, as published by the Free Software Foundation.
      19             : 
      20             : // You should have received a copy of the GNU General Public License and
      21             : // a copy of the GCC Runtime Library Exception along with this program;
      22             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23             : // <http://www.gnu.org/licenses/>.
      24             : 
      25             : /** @file bits/hashtable.h
      26             :  *  This is an internal header file, included by other library headers.
      27             :  *  Do not attempt to use it directly. @headername{unordered_map, unordered_set}
      28             :  */
      29             : 
      30             : #ifndef _HASHTABLE_H
      31             : #define _HASHTABLE_H 1
      32             : 
      33             : #pragma GCC system_header
      34             : 
      35             : #include <bits/hashtable_policy.h>
      36             : #if __cplusplus > 201402L
      37             : # include <bits/node_handle.h>
      38             : #endif
      39             : 
      40             : namespace std _GLIBCXX_VISIBILITY(default)
      41             : {
      42             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
      43             : 
      44             :   template<typename _Tp, typename _Hash>
      45             :     using __cache_default
      46             :       =  __not_<__and_<// Do not cache for fast hasher.
      47             :                        __is_fast_hash<_Hash>,
      48             :                        // Mandatory to have erase not throwing.
      49             :                        __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
      50             : 
      51             :   /**
      52             :    *  Primary class template _Hashtable.
      53             :    *
      54             :    *  @ingroup hashtable-detail
      55             :    *
      56             :    *  @tparam _Value  CopyConstructible type.
      57             :    *
      58             :    *  @tparam _Key    CopyConstructible type.
      59             :    *
      60             :    *  @tparam _Alloc  An allocator type
      61             :    *  ([lib.allocator.requirements]) whose _Alloc::value_type is
      62             :    *  _Value.  As a conforming extension, we allow for
      63             :    *  _Alloc::value_type != _Value.
      64             :    *
      65             :    *  @tparam _ExtractKey  Function object that takes an object of type
      66             :    *  _Value and returns a value of type _Key.
      67             :    *
      68             :    *  @tparam _Equal  Function object that takes two objects of type k
      69             :    *  and returns a bool-like value that is true if the two objects
      70             :    *  are considered equal.
      71             :    *
      72             :    *  @tparam _H1  The hash function. A unary function object with
      73             :    *  argument type _Key and result type size_t. Return values should
      74             :    *  be distributed over the entire range [0, numeric_limits<size_t>:::max()].
      75             :    *
      76             :    *  @tparam _H2  The range-hashing function (in the terminology of
      77             :    *  Tavori and Dreizin).  A binary function object whose argument
      78             :    *  types and result type are all size_t.  Given arguments r and N,
      79             :    *  the return value is in the range [0, N).
      80             :    *
      81             :    *  @tparam _Hash  The ranged hash function (Tavori and Dreizin). A
      82             :    *  binary function whose argument types are _Key and size_t and
      83             :    *  whose result type is size_t.  Given arguments k and N, the
      84             :    *  return value is in the range [0, N).  Default: hash(k, N) =
      85             :    *  h2(h1(k), N).  If _Hash is anything other than the default, _H1
      86             :    *  and _H2 are ignored.
      87             :    *
      88             :    *  @tparam _RehashPolicy  Policy class with three members, all of
      89             :    *  which govern the bucket count. _M_next_bkt(n) returns a bucket
      90             :    *  count no smaller than n.  _M_bkt_for_elements(n) returns a
      91             :    *  bucket count appropriate for an element count of n.
      92             :    *  _M_need_rehash(n_bkt, n_elt, n_ins) determines whether, if the
      93             :    *  current bucket count is n_bkt and the current element count is
      94             :    *  n_elt, we need to increase the bucket count.  If so, returns
      95             :    *  make_pair(true, n), where n is the new bucket count.  If not,
      96             :    *  returns make_pair(false, <anything>)
      97             :    *
      98             :    *  @tparam _Traits  Compile-time class with three boolean
      99             :    *  std::integral_constant members:  __cache_hash_code, __constant_iterators,
     100             :    *   __unique_keys.
     101             :    *
     102             :    *  Each _Hashtable data structure has:
     103             :    *
     104             :    *  - _Bucket[]       _M_buckets
     105             :    *  - _Hash_node_base _M_before_begin
     106             :    *  - size_type       _M_bucket_count
     107             :    *  - size_type       _M_element_count
     108             :    *
     109             :    *  with _Bucket being _Hash_node* and _Hash_node containing:
     110             :    *
     111             :    *  - _Hash_node*   _M_next
     112             :    *  - Tp            _M_value
     113             :    *  - size_t        _M_hash_code if cache_hash_code is true
     114             :    *
     115             :    *  In terms of Standard containers the hashtable is like the aggregation of:
     116             :    *
     117             :    *  - std::forward_list<_Node> containing the elements
     118             :    *  - std::vector<std::forward_list<_Node>::iterator> representing the buckets
     119             :    *
     120             :    *  The non-empty buckets contain the node before the first node in the
     121             :    *  bucket. This design makes it possible to implement something like a
     122             :    *  std::forward_list::insert_after on container insertion and
     123             :    *  std::forward_list::erase_after on container erase
     124             :    *  calls. _M_before_begin is equivalent to
     125             :    *  std::forward_list::before_begin. Empty buckets contain
     126             :    *  nullptr.  Note that one of the non-empty buckets contains
     127             :    *  &_M_before_begin which is not a dereferenceable node so the
     128             :    *  node pointer in a bucket shall never be dereferenced, only its
     129             :    *  next node can be.
     130             :    *
     131             :    *  Walking through a bucket's nodes requires a check on the hash code to
     132             :    *  see if each node is still in the bucket. Such a design assumes a
     133             :    *  quite efficient hash functor and is one of the reasons it is
     134             :    *  highly advisable to set __cache_hash_code to true.
     135             :    *
     136             :    *  The container iterators are simply built from nodes. This way
     137             :    *  incrementing the iterator is perfectly efficient independent of
     138             :    *  how many empty buckets there are in the container.
     139             :    *
     140             :    *  On insert we compute the element's hash code and use it to find the
     141             :    *  bucket index. If the element must be inserted in an empty bucket
     142             :    *  we add it at the beginning of the singly linked list and make the
     143             :    *  bucket point to _M_before_begin. The bucket that used to point to
     144             :    *  _M_before_begin, if any, is updated to point to its new before
     145             :    *  begin node.
     146             :    *
     147             :    *  On erase, the simple iterator design requires using the hash
     148             :    *  functor to get the index of the bucket to update. For this
     149             :    *  reason, when __cache_hash_code is set to false the hash functor must
     150             :    *  not throw and this is enforced by a static assertion.
     151             :    *
     152             :    *  Functionality is implemented by decomposition into base classes,
     153             :    *  where the derived _Hashtable class is used in _Map_base,
     154             :    *  _Insert, _Rehash_base, and _Equality base classes to access the
     155             :    *  "this" pointer. _Hashtable_base is used in the base classes as a
     156             :    *  non-recursive, fully-completed-type so that detailed nested type
     157             :    *  information, such as iterator type and node type, can be
     158             :    *  used. This is similar to the "Curiously Recurring Template
     159             :    *  Pattern" (CRTP) technique, but uses a reconstructed, not
     160             :    *  explicitly passed, template pattern.
     161             :    *
     162             :    *  Base class templates are: 
     163             :    *    - __detail::_Hashtable_base
     164             :    *    - __detail::_Map_base
     165             :    *    - __detail::_Insert
     166             :    *    - __detail::_Rehash_base
     167             :    *    - __detail::_Equality
     168             :    */
     169             :   template<typename _Key, typename _Value, typename _Alloc,
     170             :            typename _ExtractKey, typename _Equal,
     171             :            typename _H1, typename _H2, typename _Hash,
     172             :            typename _RehashPolicy, typename _Traits>
     173             :     class _Hashtable
     174             :     : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
     175             :                                        _H1, _H2, _Hash, _Traits>,
     176             :       public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
     177             :                                  _H1, _H2, _Hash, _RehashPolicy, _Traits>,
     178             :       public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
     179             :                                _H1, _H2, _Hash, _RehashPolicy, _Traits>,
     180             :       public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
     181             :                                     _H1, _H2, _Hash, _RehashPolicy, _Traits>,
     182             :       public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
     183             :                                  _H1, _H2, _Hash, _RehashPolicy, _Traits>,
     184             :       private __detail::_Hashtable_alloc<
     185             :         __alloc_rebind<_Alloc,
     186             :                        __detail::_Hash_node<_Value,
     187             :                                             _Traits::__hash_cached::value>>>
     188             :     {
     189             :       static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
     190             :           "unordered container must have a non-const, non-volatile value_type");
     191             : #ifdef __STRICT_ANSI__
     192             :       static_assert(is_same<typename _Alloc::value_type, _Value>{},
     193             :           "unordered container must have the same value_type as its allocator");
     194             : #endif
     195             : 
     196             :       using __traits_type = _Traits;
     197             :       using __hash_cached = typename __traits_type::__hash_cached;
     198             :       using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
     199             :       using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
     200             : 
     201             :       using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
     202             : 
     203             :       using __value_alloc_traits =
     204             :         typename __hashtable_alloc::__value_alloc_traits;
     205             :       using __node_alloc_traits =
     206             :         typename __hashtable_alloc::__node_alloc_traits;
     207             :       using __node_base = typename __hashtable_alloc::__node_base;
     208             :       using __bucket_type = typename __hashtable_alloc::__bucket_type;
     209             : 
     210             :     public:
     211             :       typedef _Key                                              key_type;
     212             :       typedef _Value                                            value_type;
     213             :       typedef _Alloc                                            allocator_type;
     214             :       typedef _Equal                                            key_equal;
     215             : 
     216             :       // mapped_type, if present, comes from _Map_base.
     217             :       // hasher, if present, comes from _Hash_code_base/_Hashtable_base.
     218             :       typedef typename __value_alloc_traits::pointer            pointer;
     219             :       typedef typename __value_alloc_traits::const_pointer      const_pointer;
     220             :       typedef value_type&                                   reference;
     221             :       typedef const value_type&                                     const_reference;
     222             : 
     223             :     private:
     224             :       using __rehash_type = _RehashPolicy;
     225             :       using __rehash_state = typename __rehash_type::_State;
     226             : 
     227             :       using __constant_iterators = typename __traits_type::__constant_iterators;
     228             :       using __unique_keys = typename __traits_type::__unique_keys;
     229             : 
     230             :       using __key_extract = typename std::conditional<
     231             :                                              __constant_iterators::value,
     232             :                                              __detail::_Identity,
     233             :                                              __detail::_Select1st>::type;
     234             : 
     235             :       using __hashtable_base = __detail::
     236             :                                _Hashtable_base<_Key, _Value, _ExtractKey,
     237             :                                               _Equal, _H1, _H2, _Hash, _Traits>;
     238             : 
     239             :       using __hash_code_base =  typename __hashtable_base::__hash_code_base;
     240             :       using __hash_code =  typename __hashtable_base::__hash_code;
     241             :       using __ireturn_type = typename __hashtable_base::__ireturn_type;
     242             : 
     243             :       using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
     244             :                                              _Equal, _H1, _H2, _Hash,
     245             :                                              _RehashPolicy, _Traits>;
     246             : 
     247             :       using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
     248             :                                                    _ExtractKey, _Equal,
     249             :                                                    _H1, _H2, _Hash,
     250             :                                                    _RehashPolicy, _Traits>;
     251             : 
     252             :       using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
     253             :                                             _Equal, _H1, _H2, _Hash,
     254             :                                             _RehashPolicy, _Traits>;
     255             : 
     256             :       using __reuse_or_alloc_node_type =
     257             :         __detail::_ReuseOrAllocNode<__node_alloc_type>;
     258             : 
     259             :       // Metaprogramming for picking apart hash caching.
     260             :       template<typename _Cond>
     261             :         using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
     262             : 
     263             :       template<typename _Cond>
     264             :         using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
     265             : 
     266             :       // Compile-time diagnostics.
     267             : 
     268             :       // _Hash_code_base has everything protected, so use this derived type to
     269             :       // access it.
     270             :       struct __hash_code_base_access : __hash_code_base
     271             :       { using __hash_code_base::_M_bucket_index; };
     272             : 
     273             :       // Getting a bucket index from a node shall not throw because it is used
     274             :       // in methods (erase, swap...) that shall not throw.
     275             :       static_assert(noexcept(declval<const __hash_code_base_access&>()
     276             :                              ._M_bucket_index((const __node_type*)nullptr,
     277             :                                               (std::size_t)0)),
     278             :                     "Cache the hash code or qualify your functors involved"
     279             :                     " in hash code and bucket index computation with noexcept");
     280             : 
     281             :       // Following two static assertions are necessary to guarantee
     282             :       // that local_iterator will be default constructible.
     283             : 
     284             :       // When hash codes are cached local iterator inherits from H2 functor
     285             :       // which must then be default constructible.
     286             :       static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
     287             :                     "Functor used to map hash code to bucket index"
     288             :                     " must be default constructible");
     289             : 
     290             :       template<typename _Keya, typename _Valuea, typename _Alloca,
     291             :                typename _ExtractKeya, typename _Equala,
     292             :                typename _H1a, typename _H2a, typename _Hasha,
     293             :                typename _RehashPolicya, typename _Traitsa,
     294             :                bool _Unique_keysa>
     295             :         friend struct __detail::_Map_base;
     296             : 
     297             :       template<typename _Keya, typename _Valuea, typename _Alloca,
     298             :                typename _ExtractKeya, typename _Equala,
     299             :                typename _H1a, typename _H2a, typename _Hasha,
     300             :                typename _RehashPolicya, typename _Traitsa>
     301             :         friend struct __detail::_Insert_base;
     302             : 
     303             :       template<typename _Keya, typename _Valuea, typename _Alloca,
     304             :                typename _ExtractKeya, typename _Equala,
     305             :                typename _H1a, typename _H2a, typename _Hasha,
     306             :                typename _RehashPolicya, typename _Traitsa,
     307             :                bool _Constant_iteratorsa>
     308             :         friend struct __detail::_Insert;
     309             : 
     310             :     public:
     311             :       using size_type = typename __hashtable_base::size_type;
     312             :       using difference_type = typename __hashtable_base::difference_type;
     313             : 
     314             :       using iterator = typename __hashtable_base::iterator;
     315             :       using const_iterator = typename __hashtable_base::const_iterator;
     316             : 
     317             :       using local_iterator = typename __hashtable_base::local_iterator;
     318             :       using const_local_iterator = typename __hashtable_base::
     319             :                                    const_local_iterator;
     320             : 
     321             : #if __cplusplus > 201402L
     322             :       using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
     323             :       using insert_return_type = _Node_insert_return<iterator, node_type>;
     324             : #endif
     325             : 
     326             :     private:
     327             :       __bucket_type*            _M_buckets              = &_M_single_bucket;
     328             :       size_type                 _M_bucket_count         = 1;
     329             :       __node_base               _M_before_begin;
     330             :       size_type                 _M_element_count        = 0;
     331             :       _RehashPolicy             _M_rehash_policy;
     332             : 
     333             :       // A single bucket used when only need for 1 bucket. Especially
     334             :       // interesting in move semantic to leave hashtable with only 1 buckets
     335             :       // which is not allocated so that we can have those operations noexcept
     336             :       // qualified.
     337             :       // Note that we can't leave hashtable with 0 bucket without adding
     338             :       // numerous checks in the code to avoid 0 modulus.
     339             :       __bucket_type             _M_single_bucket        = nullptr;
     340             : 
     341             :       bool
     342         712 :       _M_uses_single_bucket(__bucket_type* __bkts) const
     343         712 :       { return __builtin_expect(__bkts == &_M_single_bucket, false); }
     344             : 
     345             :       bool
     346             :       _M_uses_single_bucket() const
     347             :       { return _M_uses_single_bucket(_M_buckets); }
     348             : 
     349             :       __hashtable_alloc&
     350             :       _M_base_alloc() { return *this; }
     351             : 
     352             :       __bucket_type*
     353             :       _M_allocate_buckets(size_type __n)
     354             :       {
     355             :         if (__builtin_expect(__n == 1, false))
     356             :           {
     357             :             _M_single_bucket = nullptr;
     358             :             return &_M_single_bucket;
     359             :           }
     360             : 
     361             :         return __hashtable_alloc::_M_allocate_buckets(__n);
     362             :       }
     363             : 
     364             :       void
     365         712 :       _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
     366             :       {
     367         712 :         if (_M_uses_single_bucket(__bkts))
     368             :           return;
     369             : 
     370           0 :         __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
     371             :       }
     372             : 
     373             :       void
     374         712 :       _M_deallocate_buckets()
     375        1424 :       { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
     376             : 
     377             :       // Gets bucket begin, deals with the fact that non-empty buckets contain
     378             :       // their before begin node.
     379             :       __node_type*
     380             :       _M_bucket_begin(size_type __bkt) const;
     381             : 
     382             :       __node_type*
     383         712 :       _M_begin() const
     384             :       { return static_cast<__node_type*>(_M_before_begin._M_nxt); }
     385             : 
     386             :       // Assign *this using another _Hashtable instance. Either elements
     387             :       // are copy or move depends on the _NodeGenerator.
     388             :       template<typename _Ht, typename _NodeGenerator>
     389             :         void
     390             :         _M_assign_elements(_Ht&&, const _NodeGenerator&);
     391             : 
     392             :       template<typename _NodeGenerator>
     393             :         void
     394             :         _M_assign(const _Hashtable&, const _NodeGenerator&);
     395             : 
     396             :       void
     397             :       _M_move_assign(_Hashtable&&, std::true_type);
     398             : 
     399             :       void
     400             :       _M_move_assign(_Hashtable&&, std::false_type);
     401             : 
     402             :       void
     403             :       _M_reset() noexcept;
     404             : 
     405             :       _Hashtable(const _H1& __h1, const _H2& __h2, const _Hash& __h,
     406             :                  const _Equal& __eq, const _ExtractKey& __exk,
     407             :                  const allocator_type& __a)
     408             :         : __hashtable_base(__exk, __h1, __h2, __h, __eq),
     409             :           __hashtable_alloc(__node_alloc_type(__a))
     410             :       { }
     411             : 
     412             :       template<bool _No_realloc = true>
     413             :         static constexpr bool
     414             :         _S_nothrow_move()
     415             :         {
     416             : #if __cplusplus <= 201402L
     417             :           return __and_<__bool_constant<_No_realloc>,
     418             :                         is_nothrow_copy_constructible<_H1>,
     419             :                         is_nothrow_copy_constructible<_Equal>>::value;
     420             : #else
     421             :           if constexpr (_No_realloc)
     422             :             if constexpr (is_nothrow_copy_constructible<_H1>())
     423             :               return is_nothrow_copy_constructible<_Equal>();
     424             :           return false;
     425             : #endif
     426             :         }
     427             : 
     428             :       _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
     429             :                  true_type /* alloc always equal */)
     430             :         noexcept(_S_nothrow_move());
     431             : 
     432             :       _Hashtable(_Hashtable&&, __node_alloc_type&&,
     433             :                  false_type /* alloc always equal */);
     434             : 
     435             : 
     436             :     public:
     437             :       // Constructor, destructor, assignment, swap
     438             :       _Hashtable() = default;
     439             :       _Hashtable(size_type __bucket_hint,
     440             :                  const _H1&, const _H2&, const _Hash&,
     441             :                  const _Equal&, const _ExtractKey&,
     442             :                  const allocator_type&);
     443             : 
     444             :       template<typename _InputIterator>
     445             :         _Hashtable(_InputIterator __first, _InputIterator __last,
     446             :                    size_type __bucket_hint,
     447             :                    const _H1&, const _H2&, const _Hash&,
     448             :                    const _Equal&, const _ExtractKey&,
     449             :                    const allocator_type&);
     450             : 
     451             :       _Hashtable(const _Hashtable&);
     452             : 
     453             :       _Hashtable(_Hashtable&& __ht)
     454             :         noexcept(_S_nothrow_move())
     455             :       : _Hashtable(std::move(__ht), std::move(__ht._M_node_allocator()),
     456             :                    true_type{})
     457             :       { }
     458             : 
     459             :       _Hashtable(const _Hashtable&, const allocator_type&);
     460             : 
     461             :       _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
     462             :         noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
     463             :       : _Hashtable(std::move(__ht), __node_alloc_type(__a),
     464             :                    typename __node_alloc_traits::is_always_equal{})
     465             :       { }
     466             : 
     467             :       // Use delegating constructors.
     468             :       explicit
     469             :       _Hashtable(const allocator_type& __a)
     470             :         : __hashtable_alloc(__node_alloc_type(__a))
     471             :       { }
     472             : 
     473             :       explicit
     474             :       _Hashtable(size_type __n,
     475             :                  const _H1& __hf = _H1(),
     476             :                  const key_equal& __eql = key_equal(),
     477             :                  const allocator_type& __a = allocator_type())
     478             :       : _Hashtable(__n, __hf, _H2(), _Hash(), __eql,
     479             :                    __key_extract(), __a)
     480             :       { }
     481             : 
     482             :       template<typename _InputIterator>
     483             :         _Hashtable(_InputIterator __f, _InputIterator __l,
     484             :                    size_type __n = 0,
     485             :                    const _H1& __hf = _H1(),
     486             :                    const key_equal& __eql = key_equal(),
     487             :                    const allocator_type& __a = allocator_type())
     488             :         : _Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
     489             :                      __key_extract(), __a)
     490             :         { }
     491             : 
     492             :       _Hashtable(initializer_list<value_type> __l,
     493             :                  size_type __n = 0,
     494             :                  const _H1& __hf = _H1(),
     495             :                  const key_equal& __eql = key_equal(),
     496             :                  const allocator_type& __a = allocator_type())
     497             :       : _Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
     498             :                    __key_extract(), __a)
     499             :       { }
     500             : 
     501             :       _Hashtable&
     502             :       operator=(const _Hashtable& __ht);
     503             : 
     504             :       _Hashtable&
     505             :       operator=(_Hashtable&& __ht)
     506             :       noexcept(__node_alloc_traits::_S_nothrow_move()
     507             :                && is_nothrow_move_assignable<_H1>::value
     508             :                && is_nothrow_move_assignable<_Equal>::value)
     509             :       {
     510             :         constexpr bool __move_storage =
     511             :           __node_alloc_traits::_S_propagate_on_move_assign()
     512             :           || __node_alloc_traits::_S_always_equal();
     513             :         _M_move_assign(std::move(__ht), __bool_constant<__move_storage>());
     514             :         return *this;
     515             :       }
     516             : 
     517             :       _Hashtable&
     518             :       operator=(initializer_list<value_type> __l)
     519             :       {
     520             :         __reuse_or_alloc_node_type __roan(_M_begin(), *this);
     521             :         _M_before_begin._M_nxt = nullptr;
     522             :         clear();
     523             :         this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
     524             :         return *this;
     525             :       }
     526             : 
     527             :       ~_Hashtable() noexcept;
     528             : 
     529             :       void
     530             :       swap(_Hashtable&)
     531             :       noexcept(__and_<__is_nothrow_swappable<_H1>,
     532             :                           __is_nothrow_swappable<_Equal>>::value);
     533             : 
     534             :       // Basic container operations
     535             :       iterator
     536             :       begin() noexcept
     537             :       { return iterator(_M_begin()); }
     538             : 
     539             :       const_iterator
     540             :       begin() const noexcept
     541             :       { return const_iterator(_M_begin()); }
     542             : 
     543             :       iterator
     544             :       end() noexcept
     545             :       { return iterator(nullptr); }
     546             : 
     547             :       const_iterator
     548             :       end() const noexcept
     549             :       { return const_iterator(nullptr); }
     550             : 
     551             :       const_iterator
     552             :       cbegin() const noexcept
     553             :       { return const_iterator(_M_begin()); }
     554             : 
     555             :       const_iterator
     556             :       cend() const noexcept
     557             :       { return const_iterator(nullptr); }
     558             : 
     559             :       size_type
     560             :       size() const noexcept
     561             :       { return _M_element_count; }
     562             : 
     563             :       _GLIBCXX_NODISCARD bool
     564             :       empty() const noexcept
     565             :       { return size() == 0; }
     566             : 
     567             :       allocator_type
     568             :       get_allocator() const noexcept
     569             :       { return allocator_type(this->_M_node_allocator()); }
     570             : 
     571             :       size_type
     572             :       max_size() const noexcept
     573             :       { return __node_alloc_traits::max_size(this->_M_node_allocator()); }
     574             : 
     575             :       // Observers
     576             :       key_equal
     577             :       key_eq() const
     578             :       { return this->_M_eq(); }
     579             : 
     580             :       // hash_function, if present, comes from _Hash_code_base.
     581             : 
     582             :       // Bucket operations
     583             :       size_type
     584             :       bucket_count() const noexcept
     585             :       { return _M_bucket_count; }
     586             : 
     587             :       size_type
     588             :       max_bucket_count() const noexcept
     589             :       { return max_size(); }
     590             : 
     591             :       size_type
     592             :       bucket_size(size_type __n) const
     593             :       { return std::distance(begin(__n), end(__n)); }
     594             : 
     595             :       size_type
     596             :       bucket(const key_type& __k) const
     597             :       { return _M_bucket_index(__k, this->_M_hash_code(__k)); }
     598             : 
     599             :       local_iterator
     600             :       begin(size_type __n)
     601             :       {
     602             :         return local_iterator(*this, _M_bucket_begin(__n),
     603             :                               __n, _M_bucket_count);
     604             :       }
     605             : 
     606             :       local_iterator
     607             :       end(size_type __n)
     608             :       { return local_iterator(*this, nullptr, __n, _M_bucket_count); }
     609             : 
     610             :       const_local_iterator
     611             :       begin(size_type __n) const
     612             :       {
     613             :         return const_local_iterator(*this, _M_bucket_begin(__n),
     614             :                                     __n, _M_bucket_count);
     615             :       }
     616             : 
     617             :       const_local_iterator
     618             :       end(size_type __n) const
     619             :       { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
     620             : 
     621             :       // DR 691.
     622             :       const_local_iterator
     623             :       cbegin(size_type __n) const
     624             :       {
     625             :         return const_local_iterator(*this, _M_bucket_begin(__n),
     626             :                                     __n, _M_bucket_count);
     627             :       }
     628             : 
     629             :       const_local_iterator
     630             :       cend(size_type __n) const
     631             :       { return const_local_iterator(*this, nullptr, __n, _M_bucket_count); }
     632             : 
     633             :       float
     634             :       load_factor() const noexcept
     635             :       {
     636             :         return static_cast<float>(size()) / static_cast<float>(bucket_count());
     637             :       }
     638             : 
     639             :       // max_load_factor, if present, comes from _Rehash_base.
     640             : 
     641             :       // Generalization of max_load_factor.  Extension, not found in
     642             :       // TR1.  Only useful if _RehashPolicy is something other than
     643             :       // the default.
     644             :       const _RehashPolicy&
     645             :       __rehash_policy() const
     646             :       { return _M_rehash_policy; }
     647             : 
     648             :       void
     649             :       __rehash_policy(const _RehashPolicy& __pol)
     650             :       { _M_rehash_policy = __pol; }
     651             : 
     652             :       // Lookup.
     653             :       iterator
     654             :       find(const key_type& __k);
     655             : 
     656             :       const_iterator
     657             :       find(const key_type& __k) const;
     658             : 
     659             :       size_type
     660             :       count(const key_type& __k) const;
     661             : 
     662             :       std::pair<iterator, iterator>
     663             :       equal_range(const key_type& __k);
     664             : 
     665             :       std::pair<const_iterator, const_iterator>
     666             :       equal_range(const key_type& __k) const;
     667             : 
     668             :     protected:
     669             :       // Bucket index computation helpers.
     670             :       size_type
     671             :       _M_bucket_index(__node_type* __n) const noexcept
     672             :       { return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
     673             : 
     674             :       size_type
     675             :       _M_bucket_index(const key_type& __k, __hash_code __c) const
     676             :       { return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
     677             : 
     678             :       // Find and insert helper functions and types
     679             :       // Find the node before the one matching the criteria.
     680             :       __node_base*
     681             :       _M_find_before_node(size_type, const key_type&, __hash_code) const;
     682             : 
     683             :       __node_type*
     684             :       _M_find_node(size_type __bkt, const key_type& __key,
     685             :                    __hash_code __c) const
     686             :       {
     687             :         __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
     688             :         if (__before_n)
     689             :           return static_cast<__node_type*>(__before_n->_M_nxt);
     690             :         return nullptr;
     691             :       }
     692             : 
     693             :       // Insert a node at the beginning of a bucket.
     694             :       void
     695             :       _M_insert_bucket_begin(size_type, __node_type*);
     696             : 
     697             :       // Remove the bucket first node
     698             :       void
     699             :       _M_remove_bucket_begin(size_type __bkt, __node_type* __next_n,
     700             :                              size_type __next_bkt);
     701             : 
     702             :       // Get the node before __n in the bucket __bkt
     703             :       __node_base*
     704             :       _M_get_previous_node(size_type __bkt, __node_base* __n);
     705             : 
     706             :       // Insert node with hash code __code, in bucket bkt if no rehash (assumes
     707             :       // no element with its key already present). Take ownership of the node,
     708             :       // deallocate it on exception.
     709             :       iterator
     710             :       _M_insert_unique_node(size_type __bkt, __hash_code __code,
     711             :                             __node_type* __n, size_type __n_elt = 1);
     712             : 
     713             :       // Insert node with hash code __code. Take ownership of the node,
     714             :       // deallocate it on exception.
     715             :       iterator
     716             :       _M_insert_multi_node(__node_type* __hint,
     717             :                            __hash_code __code, __node_type* __n);
     718             : 
     719             :       template<typename... _Args>
     720             :         std::pair<iterator, bool>
     721             :         _M_emplace(std::true_type, _Args&&... __args);
     722             : 
     723             :       template<typename... _Args>
     724             :         iterator
     725             :         _M_emplace(std::false_type __uk, _Args&&... __args)
     726             :         { return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
     727             : 
     728             :       // Emplace with hint, useless when keys are unique.
     729             :       template<typename... _Args>
     730             :         iterator
     731             :         _M_emplace(const_iterator, std::true_type __uk, _Args&&... __args)
     732             :         { return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
     733             : 
     734             :       template<typename... _Args>
     735             :         iterator
     736             :         _M_emplace(const_iterator, std::false_type, _Args&&... __args);
     737             : 
     738             :       template<typename _Arg, typename _NodeGenerator>
     739             :         std::pair<iterator, bool>
     740             :         _M_insert(_Arg&&, const _NodeGenerator&, true_type, size_type = 1);
     741             : 
     742             :       template<typename _Arg, typename _NodeGenerator>
     743             :         iterator
     744             :         _M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
     745             :                   false_type __uk)
     746             :         {
     747             :           return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
     748             :                            __uk);
     749             :         }
     750             : 
     751             :       // Insert with hint, not used when keys are unique.
     752             :       template<typename _Arg, typename _NodeGenerator>
     753             :         iterator
     754             :         _M_insert(const_iterator, _Arg&& __arg,
     755             :                   const _NodeGenerator& __node_gen, true_type __uk)
     756             :         {
     757             :           return
     758             :             _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).first;
     759             :         }
     760             : 
     761             :       // Insert with hint when keys are not unique.
     762             :       template<typename _Arg, typename _NodeGenerator>
     763             :         iterator
     764             :         _M_insert(const_iterator, _Arg&&,
     765             :                   const _NodeGenerator&, false_type);
     766             : 
     767             :       size_type
     768             :       _M_erase(std::true_type, const key_type&);
     769             : 
     770             :       size_type
     771             :       _M_erase(std::false_type, const key_type&);
     772             : 
     773             :       iterator
     774             :       _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n);
     775             : 
     776             :     public:
     777             :       // Emplace
     778             :       template<typename... _Args>
     779             :         __ireturn_type
     780             :         emplace(_Args&&... __args)
     781             :         { return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
     782             : 
     783             :       template<typename... _Args>
     784             :         iterator
     785             :         emplace_hint(const_iterator __hint, _Args&&... __args)
     786             :         {
     787             :           return _M_emplace(__hint, __unique_keys(),
     788             :                             std::forward<_Args>(__args)...);
     789             :         }
     790             : 
     791             :       // Insert member functions via inheritance.
     792             : 
     793             :       // Erase
     794             :       iterator
     795             :       erase(const_iterator);
     796             : 
     797             :       // LWG 2059.
     798             :       iterator
     799             :       erase(iterator __it)
     800             :       { return erase(const_iterator(__it)); }
     801             : 
     802             :       size_type
     803             :       erase(const key_type& __k)
     804             :       { return _M_erase(__unique_keys(), __k); }
     805             : 
     806             :       iterator
     807             :       erase(const_iterator, const_iterator);
     808             : 
     809             :       void
     810             :       clear() noexcept;
     811             : 
     812             :       // Set number of buckets to be appropriate for container of n element.
     813             :       void rehash(size_type __n);
     814             : 
     815             :       // DR 1189.
     816             :       // reserve, if present, comes from _Rehash_base.
     817             : 
     818             : #if __cplusplus > 201402L
     819             :       /// Re-insert an extracted node into a container with unique keys.
     820             :       insert_return_type
     821             :       _M_reinsert_node(node_type&& __nh)
     822             :       {
     823             :         insert_return_type __ret;
     824             :         if (__nh.empty())
     825             :           __ret.position = end();
     826             :         else
     827             :           {
     828             :             __glibcxx_assert(get_allocator() == __nh.get_allocator());
     829             : 
     830             :             const key_type& __k = __nh._M_key();
     831             :             __hash_code __code = this->_M_hash_code(__k);
     832             :             size_type __bkt = _M_bucket_index(__k, __code);
     833             :             if (__node_type* __n = _M_find_node(__bkt, __k, __code))
     834             :               {
     835             :                 __ret.node = std::move(__nh);
     836             :                 __ret.position = iterator(__n);
     837             :                 __ret.inserted = false;
     838             :               }
     839             :             else
     840             :               {
     841             :                 __ret.position
     842             :                   = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
     843             :                 __nh._M_ptr = nullptr;
     844             :                 __ret.inserted = true;
     845             :               }
     846             :           }
     847             :         return __ret;
     848             :       }
     849             : 
     850             :       /// Re-insert an extracted node into a container with equivalent keys.
     851             :       iterator
     852             :       _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
     853             :       {
     854             :         iterator __ret;
     855             :         if (__nh.empty())
     856             :           __ret = end();
     857             :         else
     858             :           {
     859             :             __glibcxx_assert(get_allocator() == __nh.get_allocator());
     860             : 
     861             :             auto __code = this->_M_hash_code(__nh._M_key());
     862             :             auto __node = std::exchange(__nh._M_ptr, nullptr);
     863             :             // FIXME: this deallocates the node on exception.
     864             :             __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
     865             :           }
     866             :         return __ret;
     867             :       }
     868             : 
     869             :       /// Extract a node.
     870             :       node_type
     871             :       extract(const_iterator __pos)
     872             :       {
     873             :         __node_type* __n = __pos._M_cur;
     874             :         size_t __bkt = _M_bucket_index(__n);
     875             : 
     876             :         // Look for previous node to unlink it from the erased one, this
     877             :         // is why we need buckets to contain the before begin to make
     878             :         // this search fast.
     879             :         __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
     880             : 
     881             :         if (__prev_n == _M_buckets[__bkt])
     882             :           _M_remove_bucket_begin(__bkt, __n->_M_next(),
     883             :              __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
     884             :         else if (__n->_M_nxt)
     885             :           {
     886             :             size_type __next_bkt = _M_bucket_index(__n->_M_next());
     887             :             if (__next_bkt != __bkt)
     888             :               _M_buckets[__next_bkt] = __prev_n;
     889             :           }
     890             : 
     891             :         __prev_n->_M_nxt = __n->_M_nxt;
     892             :         __n->_M_nxt = nullptr;
     893             :         --_M_element_count;
     894             :         return { __n, this->_M_node_allocator() };
     895             :       }
     896             : 
     897             :       /// Extract a node.
     898             :       node_type
     899             :       extract(const _Key& __k)
     900             :       {
     901             :         node_type __nh;
     902             :         auto __pos = find(__k);
     903             :         if (__pos != end())
     904             :           __nh = extract(const_iterator(__pos));
     905             :         return __nh;
     906             :       }
     907             : 
     908             :       /// Merge from a compatible container into one with unique keys.
     909             :       template<typename _Compatible_Hashtable>
     910             :         void
     911             :         _M_merge_unique(_Compatible_Hashtable& __src) noexcept
     912             :         {
     913             :           static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
     914             :               node_type>, "Node types are compatible");
     915             :           __glibcxx_assert(get_allocator() == __src.get_allocator());
     916             : 
     917             :           auto __n_elt = __src.size();
     918             :           for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
     919             :             {
     920             :               auto __pos = __i++;
     921             :               const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
     922             :               __hash_code __code = this->_M_hash_code(__k);
     923             :               size_type __bkt = _M_bucket_index(__k, __code);
     924             :               if (_M_find_node(__bkt, __k, __code) == nullptr)
     925             :                 {
     926             :                   auto __nh = __src.extract(__pos);
     927             :                   _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
     928             :                   __nh._M_ptr = nullptr;
     929             :                   __n_elt = 1;
     930             :                 }
     931             :               else if (__n_elt != 1)
     932             :                 --__n_elt;
     933             :             }
     934             :         }
     935             : 
     936             :       /// Merge from a compatible container into one with equivalent keys.
     937             :       template<typename _Compatible_Hashtable>
     938             :         void
     939             :         _M_merge_multi(_Compatible_Hashtable& __src) noexcept
     940             :         {
     941             :           static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
     942             :               node_type>, "Node types are compatible");
     943             :           __glibcxx_assert(get_allocator() == __src.get_allocator());
     944             : 
     945             :           this->reserve(size() + __src.size());
     946             :           for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
     947             :             _M_reinsert_node_multi(cend(), __src.extract(__i++));
     948             :         }
     949             : #endif // C++17
     950             : 
     951             :     private:
     952             :       // Helper rehash method used when keys are unique.
     953             :       void _M_rehash_aux(size_type __n, std::true_type);
     954             : 
     955             :       // Helper rehash method used when keys can be non-unique.
     956             :       void _M_rehash_aux(size_type __n, std::false_type);
     957             : 
     958             :       // Unconditionally change size of bucket array to n, restore
     959             :       // hash policy state to __state on exception.
     960             :       void _M_rehash(size_type __n, const __rehash_state& __state);
     961             :     };
     962             : 
     963             : 
     964             :   // Definitions of class template _Hashtable's out-of-line member functions.
     965             :   template<typename _Key, typename _Value,
     966             :            typename _Alloc, typename _ExtractKey, typename _Equal,
     967             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
     968             :            typename _Traits>
     969             :     auto
     970             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
     971             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     972             :     _M_bucket_begin(size_type __bkt) const
     973             :     -> __node_type*
     974             :     {
     975             :       __node_base* __n = _M_buckets[__bkt];
     976             :       return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr;
     977             :     }
     978             : 
     979             :   template<typename _Key, typename _Value,
     980             :            typename _Alloc, typename _ExtractKey, typename _Equal,
     981             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
     982             :            typename _Traits>
     983             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
     984             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
     985             :     _Hashtable(size_type __bucket_hint,
     986             :                const _H1& __h1, const _H2& __h2, const _Hash& __h,
     987             :                const _Equal& __eq, const _ExtractKey& __exk,
     988             :                const allocator_type& __a)
     989             :       : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
     990             :     {
     991             :       auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
     992             :       if (__bkt > _M_bucket_count)
     993             :         {
     994             :           _M_buckets = _M_allocate_buckets(__bkt);
     995             :           _M_bucket_count = __bkt;
     996             :         }
     997             :     }
     998             : 
     999             :   template<typename _Key, typename _Value,
    1000             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1001             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1002             :            typename _Traits>
    1003             :     template<typename _InputIterator>
    1004             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1005             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1006             :       _Hashtable(_InputIterator __f, _InputIterator __l,
    1007             :                  size_type __bucket_hint,
    1008             :                  const _H1& __h1, const _H2& __h2, const _Hash& __h,
    1009             :                  const _Equal& __eq, const _ExtractKey& __exk,
    1010             :                  const allocator_type& __a)
    1011             :         : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
    1012             :       {
    1013             :         auto __nb_elems = __detail::__distance_fw(__f, __l);
    1014             :         auto __bkt_count =
    1015             :           _M_rehash_policy._M_next_bkt(
    1016             :             std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
    1017             :                      __bucket_hint));
    1018             : 
    1019             :         if (__bkt_count > _M_bucket_count)
    1020             :           {
    1021             :             _M_buckets = _M_allocate_buckets(__bkt_count);
    1022             :             _M_bucket_count = __bkt_count;
    1023             :           }
    1024             : 
    1025             :         for (; __f != __l; ++__f)
    1026             :           this->insert(*__f);
    1027             :       }
    1028             : 
    1029             :   template<typename _Key, typename _Value,
    1030             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1031             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1032             :            typename _Traits>
    1033             :     auto
    1034             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1035             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1036             :     operator=(const _Hashtable& __ht)
    1037             :     -> _Hashtable&
    1038             :     {
    1039             :       if (&__ht == this)
    1040             :         return *this;
    1041             : 
    1042             :       if (__node_alloc_traits::_S_propagate_on_copy_assign())
    1043             :         {
    1044             :           auto& __this_alloc = this->_M_node_allocator();
    1045             :           auto& __that_alloc = __ht._M_node_allocator();
    1046             :           if (!__node_alloc_traits::_S_always_equal()
    1047             :               && __this_alloc != __that_alloc)
    1048             :             {
    1049             :               // Replacement allocator cannot free existing storage.
    1050             :               this->_M_deallocate_nodes(_M_begin());
    1051             :               _M_before_begin._M_nxt = nullptr;
    1052             :               _M_deallocate_buckets();
    1053             :               _M_buckets = nullptr;
    1054             :               std::__alloc_on_copy(__this_alloc, __that_alloc);
    1055             :               __hashtable_base::operator=(__ht);
    1056             :               _M_bucket_count = __ht._M_bucket_count;
    1057             :               _M_element_count = __ht._M_element_count;
    1058             :               _M_rehash_policy = __ht._M_rehash_policy;
    1059             :               __try
    1060             :                 {
    1061             :                   _M_assign(__ht,
    1062             :                             [this](const __node_type* __n)
    1063             :                             { return this->_M_allocate_node(__n->_M_v()); });
    1064             :                 }
    1065             :               __catch(...)
    1066             :                 {
    1067             :                   // _M_assign took care of deallocating all memory. Now we
    1068             :                   // must make sure this instance remains in a usable state.
    1069             :                   _M_reset();
    1070             :                   __throw_exception_again;
    1071             :                 }
    1072             :               return *this;
    1073             :             }
    1074             :           std::__alloc_on_copy(__this_alloc, __that_alloc);
    1075             :         }
    1076             : 
    1077             :       // Reuse allocated buckets and nodes.
    1078             :       _M_assign_elements(__ht,
    1079             :         [](const __reuse_or_alloc_node_type& __roan, const __node_type* __n)
    1080             :         { return __roan(__n->_M_v()); });
    1081             :       return *this;
    1082             :     }
    1083             : 
    1084             :   template<typename _Key, typename _Value,
    1085             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1086             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1087             :            typename _Traits>
    1088             :     template<typename _Ht, typename _NodeGenerator>
    1089             :       void
    1090             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1091             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1092             :       _M_assign_elements(_Ht&& __ht, const _NodeGenerator& __node_gen)
    1093             :       {
    1094             :         __bucket_type* __former_buckets = nullptr;
    1095             :         std::size_t __former_bucket_count = _M_bucket_count;
    1096             :         const __rehash_state& __former_state = _M_rehash_policy._M_state();
    1097             : 
    1098             :         if (_M_bucket_count != __ht._M_bucket_count)
    1099             :           {
    1100             :             __former_buckets = _M_buckets;
    1101             :             _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
    1102             :             _M_bucket_count = __ht._M_bucket_count;
    1103             :           }
    1104             :         else
    1105             :           __builtin_memset(_M_buckets, 0,
    1106             :                            _M_bucket_count * sizeof(__bucket_type));
    1107             : 
    1108             :         __try
    1109             :           {
    1110             :             __hashtable_base::operator=(std::forward<_Ht>(__ht));
    1111             :             _M_element_count = __ht._M_element_count;
    1112             :             _M_rehash_policy = __ht._M_rehash_policy;
    1113             :             __reuse_or_alloc_node_type __roan(_M_begin(), *this);
    1114             :             _M_before_begin._M_nxt = nullptr;
    1115             :             _M_assign(__ht,
    1116             :                       [&__node_gen, &__roan](__node_type* __n)
    1117             :                       { return __node_gen(__roan, __n); });
    1118             :             if (__former_buckets)
    1119             :               _M_deallocate_buckets(__former_buckets, __former_bucket_count);
    1120             :           }
    1121             :         __catch(...)
    1122             :           {
    1123             :             if (__former_buckets)
    1124             :               {
    1125             :                 // Restore previous buckets.
    1126             :                 _M_deallocate_buckets();
    1127             :                 _M_rehash_policy._M_reset(__former_state);
    1128             :                 _M_buckets = __former_buckets;
    1129             :                 _M_bucket_count = __former_bucket_count;
    1130             :               }
    1131             :             __builtin_memset(_M_buckets, 0,
    1132             :                              _M_bucket_count * sizeof(__bucket_type));
    1133             :             __throw_exception_again;
    1134             :           }
    1135             :       }
    1136             : 
    1137             :   template<typename _Key, typename _Value,
    1138             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1139             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1140             :            typename _Traits>
    1141             :     template<typename _NodeGenerator>
    1142             :       void
    1143             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1144             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1145             :       _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
    1146             :       {
    1147             :         __bucket_type* __buckets = nullptr;
    1148             :         if (!_M_buckets)
    1149             :           _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
    1150             : 
    1151             :         __try
    1152             :           {
    1153             :             if (!__ht._M_before_begin._M_nxt)
    1154             :               return;
    1155             : 
    1156             :             // First deal with the special first node pointed to by
    1157             :             // _M_before_begin.
    1158             :             __node_type* __ht_n = __ht._M_begin();
    1159             :             __node_type* __this_n = __node_gen(__ht_n);
    1160             :             this->_M_copy_code(__this_n, __ht_n);
    1161             :             _M_before_begin._M_nxt = __this_n;
    1162             :             _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
    1163             : 
    1164             :             // Then deal with other nodes.
    1165             :             __node_base* __prev_n = __this_n;
    1166             :             for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
    1167             :               {
    1168             :                 __this_n = __node_gen(__ht_n);
    1169             :                 __prev_n->_M_nxt = __this_n;
    1170             :                 this->_M_copy_code(__this_n, __ht_n);
    1171             :                 size_type __bkt = _M_bucket_index(__this_n);
    1172             :                 if (!_M_buckets[__bkt])
    1173             :                   _M_buckets[__bkt] = __prev_n;
    1174             :                 __prev_n = __this_n;
    1175             :               }
    1176             :           }
    1177             :         __catch(...)
    1178             :           {
    1179             :             clear();
    1180             :             if (__buckets)
    1181             :               _M_deallocate_buckets();
    1182             :             __throw_exception_again;
    1183             :           }
    1184             :       }
    1185             : 
    1186             :   template<typename _Key, typename _Value,
    1187             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1188             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1189             :            typename _Traits>
    1190             :     void
    1191             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1192             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1193             :     _M_reset() noexcept
    1194             :     {
    1195             :       _M_rehash_policy._M_reset();
    1196             :       _M_bucket_count = 1;
    1197             :       _M_single_bucket = nullptr;
    1198             :       _M_buckets = &_M_single_bucket;
    1199             :       _M_before_begin._M_nxt = nullptr;
    1200             :       _M_element_count = 0;
    1201             :     }
    1202             : 
    1203             :   template<typename _Key, typename _Value,
    1204             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1205             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1206             :            typename _Traits>
    1207             :     void
    1208             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1209             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1210             :     _M_move_assign(_Hashtable&& __ht, std::true_type)
    1211             :     {
    1212             :       this->_M_deallocate_nodes(_M_begin());
    1213             :       _M_deallocate_buckets();
    1214             :       __hashtable_base::operator=(std::move(__ht));
    1215             :       _M_rehash_policy = __ht._M_rehash_policy;
    1216             :       if (!__ht._M_uses_single_bucket())
    1217             :         _M_buckets = __ht._M_buckets;
    1218             :       else
    1219             :         {
    1220             :           _M_buckets = &_M_single_bucket;
    1221             :           _M_single_bucket = __ht._M_single_bucket;
    1222             :         }
    1223             :       _M_bucket_count = __ht._M_bucket_count;
    1224             :       _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
    1225             :       _M_element_count = __ht._M_element_count;
    1226             :       std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
    1227             : 
    1228             :       // Fix buckets containing the _M_before_begin pointers that can't be
    1229             :       // moved.
    1230             :       if (_M_begin())
    1231             :         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
    1232             :       __ht._M_reset();
    1233             :     }
    1234             : 
    1235             :   template<typename _Key, typename _Value,
    1236             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1237             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1238             :            typename _Traits>
    1239             :     void
    1240             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1241             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1242             :     _M_move_assign(_Hashtable&& __ht, std::false_type)
    1243             :     {
    1244             :       if (__ht._M_node_allocator() == this->_M_node_allocator())
    1245             :         _M_move_assign(std::move(__ht), std::true_type());
    1246             :       else
    1247             :         {
    1248             :           // Can't move memory, move elements then.
    1249             :           _M_assign_elements(std::move(__ht),
    1250             :                 [](const __reuse_or_alloc_node_type& __roan, __node_type* __n)
    1251             :                 { return __roan(std::move_if_noexcept(__n->_M_v())); });
    1252             :           __ht.clear();
    1253             :         }
    1254             :     }
    1255             : 
    1256             :   template<typename _Key, typename _Value,
    1257             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1258             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1259             :            typename _Traits>
    1260             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1261             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1262             :     _Hashtable(const _Hashtable& __ht)
    1263             :     : __hashtable_base(__ht),
    1264             :       __map_base(__ht),
    1265             :       __rehash_base(__ht),
    1266             :       __hashtable_alloc(
    1267             :         __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
    1268             :       _M_buckets(nullptr),
    1269             :       _M_bucket_count(__ht._M_bucket_count),
    1270             :       _M_element_count(__ht._M_element_count),
    1271             :       _M_rehash_policy(__ht._M_rehash_policy)
    1272             :     {
    1273             :       _M_assign(__ht,
    1274             :                 [this](const __node_type* __n)
    1275             :                 { return this->_M_allocate_node(__n->_M_v()); });
    1276             :     }
    1277             : 
    1278             :   template<typename _Key, typename _Value,
    1279             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1280             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1281             :            typename _Traits>
    1282             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1283             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1284             :     _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
    1285             :                true_type /* alloc always equal */)
    1286             :     noexcept(_S_nothrow_move())
    1287             :     : __hashtable_base(__ht),
    1288             :       __map_base(__ht),
    1289             :       __rehash_base(__ht),
    1290             :       __hashtable_alloc(std::move(__a)),
    1291             :       _M_buckets(__ht._M_buckets),
    1292             :       _M_bucket_count(__ht._M_bucket_count),
    1293             :       _M_before_begin(__ht._M_before_begin._M_nxt),
    1294             :       _M_element_count(__ht._M_element_count),
    1295             :       _M_rehash_policy(__ht._M_rehash_policy)
    1296             :     {
    1297             :       // Update buckets if __ht is using its single bucket.
    1298             :       if (__ht._M_uses_single_bucket())
    1299             :         {
    1300             :           _M_buckets = &_M_single_bucket;
    1301             :           _M_single_bucket = __ht._M_single_bucket;
    1302             :         }
    1303             : 
    1304             :       // Update, if necessary, bucket pointing to before begin that hasn't
    1305             :       // moved.
    1306             :       if (_M_begin())
    1307             :         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
    1308             : 
    1309             :       __ht._M_reset();
    1310             :     }
    1311             : 
    1312             :   template<typename _Key, typename _Value,
    1313             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1314             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1315             :            typename _Traits>
    1316             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1317             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1318             :     _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
    1319             :     : __hashtable_base(__ht),
    1320             :       __map_base(__ht),
    1321             :       __rehash_base(__ht),
    1322             :       __hashtable_alloc(__node_alloc_type(__a)),
    1323             :       _M_buckets(),
    1324             :       _M_bucket_count(__ht._M_bucket_count),
    1325             :       _M_element_count(__ht._M_element_count),
    1326             :       _M_rehash_policy(__ht._M_rehash_policy)
    1327             :     {
    1328             :       _M_assign(__ht,
    1329             :                 [this](const __node_type* __n)
    1330             :                 { return this->_M_allocate_node(__n->_M_v()); });
    1331             :     }
    1332             : 
    1333             :   template<typename _Key, typename _Value,
    1334             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1335             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1336             :            typename _Traits>
    1337             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1338             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1339             :     _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
    1340             :                false_type /* alloc always equal */)
    1341             :     : __hashtable_base(__ht),
    1342             :       __map_base(__ht),
    1343             :       __rehash_base(__ht),
    1344             :       __hashtable_alloc(std::move(__a)),
    1345             :       _M_buckets(nullptr),
    1346             :       _M_bucket_count(__ht._M_bucket_count),
    1347             :       _M_element_count(__ht._M_element_count),
    1348             :       _M_rehash_policy(__ht._M_rehash_policy)
    1349             :     {
    1350             :       if (__ht._M_node_allocator() == this->_M_node_allocator())
    1351             :         {
    1352             :           if (__ht._M_uses_single_bucket())
    1353             :             {
    1354             :               _M_buckets = &_M_single_bucket;
    1355             :               _M_single_bucket = __ht._M_single_bucket;
    1356             :             }
    1357             :           else
    1358             :             _M_buckets = __ht._M_buckets;
    1359             : 
    1360             :           _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
    1361             :           // Update, if necessary, bucket pointing to before begin that hasn't
    1362             :           // moved.
    1363             :           if (_M_begin())
    1364             :             _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
    1365             :           __ht._M_reset();
    1366             :         }
    1367             :       else
    1368             :         {
    1369             :           _M_assign(__ht,
    1370             :                     [this](__node_type* __n)
    1371             :                     {
    1372             :                       return this->_M_allocate_node(
    1373             :                                         std::move_if_noexcept(__n->_M_v()));
    1374             :                     });
    1375             :           __ht.clear();
    1376             :         }
    1377             :     }
    1378             : 
    1379             :   template<typename _Key, typename _Value,
    1380             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1381             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1382             :            typename _Traits>
    1383         712 :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1384             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1385             :     ~_Hashtable() noexcept
    1386             :     {
    1387         712 :       clear();
    1388         712 :       _M_deallocate_buckets();
    1389         712 :     }
    1390             : 
    1391             :   template<typename _Key, typename _Value,
    1392             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1393             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1394             :            typename _Traits>
    1395             :     void
    1396             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1397             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1398             :     swap(_Hashtable& __x)
    1399             :     noexcept(__and_<__is_nothrow_swappable<_H1>,
    1400             :                         __is_nothrow_swappable<_Equal>>::value)
    1401             :     {
    1402             :       // The only base class with member variables is hash_code_base.
    1403             :       // We define _Hash_code_base::_M_swap because different
    1404             :       // specializations have different members.
    1405             :       this->_M_swap(__x);
    1406             : 
    1407             :       std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
    1408             :       std::swap(_M_rehash_policy, __x._M_rehash_policy);
    1409             : 
    1410             :       // Deal properly with potentially moved instances.
    1411             :       if (this->_M_uses_single_bucket())
    1412             :         {
    1413             :           if (!__x._M_uses_single_bucket())
    1414             :             {
    1415             :               _M_buckets = __x._M_buckets;
    1416             :               __x._M_buckets = &__x._M_single_bucket;
    1417             :             }
    1418             :         }
    1419             :       else if (__x._M_uses_single_bucket())
    1420             :         {
    1421             :           __x._M_buckets = _M_buckets;
    1422             :           _M_buckets = &_M_single_bucket;
    1423             :         }       
    1424             :       else
    1425             :         std::swap(_M_buckets, __x._M_buckets);
    1426             : 
    1427             :       std::swap(_M_bucket_count, __x._M_bucket_count);
    1428             :       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
    1429             :       std::swap(_M_element_count, __x._M_element_count);
    1430             :       std::swap(_M_single_bucket, __x._M_single_bucket);
    1431             : 
    1432             :       // Fix buckets containing the _M_before_begin pointers that can't be
    1433             :       // swapped.
    1434             :       if (_M_begin())
    1435             :         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
    1436             : 
    1437             :       if (__x._M_begin())
    1438             :         __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
    1439             :           = &__x._M_before_begin;
    1440             :     }
    1441             : 
    1442             :   template<typename _Key, typename _Value,
    1443             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1444             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1445             :            typename _Traits>
    1446             :     auto
    1447             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1448             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1449             :     find(const key_type& __k)
    1450             :     -> iterator
    1451             :     {
    1452             :       __hash_code __code = this->_M_hash_code(__k);
    1453             :       std::size_t __n = _M_bucket_index(__k, __code);
    1454             :       __node_type* __p = _M_find_node(__n, __k, __code);
    1455             :       return __p ? iterator(__p) : end();
    1456             :     }
    1457             : 
    1458             :   template<typename _Key, typename _Value,
    1459             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1460             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1461             :            typename _Traits>
    1462             :     auto
    1463             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1464             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1465             :     find(const key_type& __k) const
    1466             :     -> const_iterator
    1467             :     {
    1468             :       __hash_code __code = this->_M_hash_code(__k);
    1469             :       std::size_t __n = _M_bucket_index(__k, __code);
    1470             :       __node_type* __p = _M_find_node(__n, __k, __code);
    1471             :       return __p ? const_iterator(__p) : end();
    1472             :     }
    1473             : 
    1474             :   template<typename _Key, typename _Value,
    1475             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1476             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1477             :            typename _Traits>
    1478             :     auto
    1479             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1480             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1481             :     count(const key_type& __k) const
    1482             :     -> size_type
    1483             :     {
    1484             :       __hash_code __code = this->_M_hash_code(__k);
    1485             :       std::size_t __n = _M_bucket_index(__k, __code);
    1486             :       __node_type* __p = _M_bucket_begin(__n);
    1487             :       if (!__p)
    1488             :         return 0;
    1489             : 
    1490             :       std::size_t __result = 0;
    1491             :       for (;; __p = __p->_M_next())
    1492             :         {
    1493             :           if (this->_M_equals(__k, __code, __p))
    1494             :             ++__result;
    1495             :           else if (__result)
    1496             :             // All equivalent values are next to each other, if we
    1497             :             // found a non-equivalent value after an equivalent one it
    1498             :             // means that we won't find any new equivalent value.
    1499             :             break;
    1500             :           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
    1501             :             break;
    1502             :         }
    1503             :       return __result;
    1504             :     }
    1505             : 
    1506             :   template<typename _Key, typename _Value,
    1507             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1508             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1509             :            typename _Traits>
    1510             :     auto
    1511             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1512             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1513             :     equal_range(const key_type& __k)
    1514             :     -> pair<iterator, iterator>
    1515             :     {
    1516             :       __hash_code __code = this->_M_hash_code(__k);
    1517             :       std::size_t __n = _M_bucket_index(__k, __code);
    1518             :       __node_type* __p = _M_find_node(__n, __k, __code);
    1519             : 
    1520             :       if (__p)
    1521             :         {
    1522             :           __node_type* __p1 = __p->_M_next();
    1523             :           while (__p1 && _M_bucket_index(__p1) == __n
    1524             :                  && this->_M_equals(__k, __code, __p1))
    1525             :             __p1 = __p1->_M_next();
    1526             : 
    1527             :           return std::make_pair(iterator(__p), iterator(__p1));
    1528             :         }
    1529             :       else
    1530             :         return std::make_pair(end(), end());
    1531             :     }
    1532             : 
    1533             :   template<typename _Key, typename _Value,
    1534             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1535             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1536             :            typename _Traits>
    1537             :     auto
    1538             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1539             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1540             :     equal_range(const key_type& __k) const
    1541             :     -> pair<const_iterator, const_iterator>
    1542             :     {
    1543             :       __hash_code __code = this->_M_hash_code(__k);
    1544             :       std::size_t __n = _M_bucket_index(__k, __code);
    1545             :       __node_type* __p = _M_find_node(__n, __k, __code);
    1546             : 
    1547             :       if (__p)
    1548             :         {
    1549             :           __node_type* __p1 = __p->_M_next();
    1550             :           while (__p1 && _M_bucket_index(__p1) == __n
    1551             :                  && this->_M_equals(__k, __code, __p1))
    1552             :             __p1 = __p1->_M_next();
    1553             : 
    1554             :           return std::make_pair(const_iterator(__p), const_iterator(__p1));
    1555             :         }
    1556             :       else
    1557             :         return std::make_pair(end(), end());
    1558             :     }
    1559             : 
    1560             :   // Find the node whose key compares equal to k in the bucket n.
    1561             :   // Return nullptr if no node is found.
    1562             :   template<typename _Key, typename _Value,
    1563             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1564             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1565             :            typename _Traits>
    1566             :     auto
    1567             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1568             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1569             :     _M_find_before_node(size_type __n, const key_type& __k,
    1570             :                         __hash_code __code) const
    1571             :     -> __node_base*
    1572             :     {
    1573             :       __node_base* __prev_p = _M_buckets[__n];
    1574             :       if (!__prev_p)
    1575             :         return nullptr;
    1576             : 
    1577             :       for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
    1578             :            __p = __p->_M_next())
    1579             :         {
    1580             :           if (this->_M_equals(__k, __code, __p))
    1581             :             return __prev_p;
    1582             : 
    1583             :           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
    1584             :             break;
    1585             :           __prev_p = __p;
    1586             :         }
    1587             :       return nullptr;
    1588             :     }
    1589             : 
    1590             :   template<typename _Key, typename _Value,
    1591             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1592             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1593             :            typename _Traits>
    1594             :     void
    1595             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1596             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1597             :     _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
    1598             :     {
    1599             :       if (_M_buckets[__bkt])
    1600             :         {
    1601             :           // Bucket is not empty, we just need to insert the new node
    1602             :           // after the bucket before begin.
    1603             :           __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
    1604             :           _M_buckets[__bkt]->_M_nxt = __node;
    1605             :         }
    1606             :       else
    1607             :         {
    1608             :           // The bucket is empty, the new node is inserted at the
    1609             :           // beginning of the singly-linked list and the bucket will
    1610             :           // contain _M_before_begin pointer.
    1611             :           __node->_M_nxt = _M_before_begin._M_nxt;
    1612             :           _M_before_begin._M_nxt = __node;
    1613             :           if (__node->_M_nxt)
    1614             :             // We must update former begin bucket that is pointing to
    1615             :             // _M_before_begin.
    1616             :             _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
    1617             :           _M_buckets[__bkt] = &_M_before_begin;
    1618             :         }
    1619             :     }
    1620             : 
    1621             :   template<typename _Key, typename _Value,
    1622             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1623             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1624             :            typename _Traits>
    1625             :     void
    1626             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1627             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1628             :     _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
    1629             :                            size_type __next_bkt)
    1630             :     {
    1631             :       if (!__next || __next_bkt != __bkt)
    1632             :         {
    1633             :           // Bucket is now empty
    1634             :           // First update next bucket if any
    1635             :           if (__next)
    1636             :             _M_buckets[__next_bkt] = _M_buckets[__bkt];
    1637             : 
    1638             :           // Second update before begin node if necessary
    1639             :           if (&_M_before_begin == _M_buckets[__bkt])
    1640             :             _M_before_begin._M_nxt = __next;
    1641             :           _M_buckets[__bkt] = nullptr;
    1642             :         }
    1643             :     }
    1644             : 
    1645             :   template<typename _Key, typename _Value,
    1646             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1647             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1648             :            typename _Traits>
    1649             :     auto
    1650             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1651             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1652             :     _M_get_previous_node(size_type __bkt, __node_base* __n)
    1653             :     -> __node_base*
    1654             :     {
    1655             :       __node_base* __prev_n = _M_buckets[__bkt];
    1656             :       while (__prev_n->_M_nxt != __n)
    1657             :         __prev_n = __prev_n->_M_nxt;
    1658             :       return __prev_n;
    1659             :     }
    1660             : 
    1661             :   template<typename _Key, typename _Value,
    1662             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1663             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1664             :            typename _Traits>
    1665             :     template<typename... _Args>
    1666             :       auto
    1667             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1668             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1669             :       _M_emplace(std::true_type, _Args&&... __args)
    1670             :       -> pair<iterator, bool>
    1671             :       {
    1672             :         // First build the node to get access to the hash code
    1673             :         __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
    1674             :         const key_type& __k = this->_M_extract()(__node->_M_v());
    1675             :         __hash_code __code;
    1676             :         __try
    1677             :           {
    1678             :             __code = this->_M_hash_code(__k);
    1679             :           }
    1680             :         __catch(...)
    1681             :           {
    1682             :             this->_M_deallocate_node(__node);
    1683             :             __throw_exception_again;
    1684             :           }
    1685             : 
    1686             :         size_type __bkt = _M_bucket_index(__k, __code);
    1687             :         if (__node_type* __p = _M_find_node(__bkt, __k, __code))
    1688             :           {
    1689             :             // There is already an equivalent node, no insertion
    1690             :             this->_M_deallocate_node(__node);
    1691             :             return std::make_pair(iterator(__p), false);
    1692             :           }
    1693             : 
    1694             :         // Insert the node
    1695             :         return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
    1696             :                               true);
    1697             :       }
    1698             : 
    1699             :   template<typename _Key, typename _Value,
    1700             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1701             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1702             :            typename _Traits>
    1703             :     template<typename... _Args>
    1704             :       auto
    1705             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1706             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1707             :       _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
    1708             :       -> iterator
    1709             :       {
    1710             :         // First build the node to get its hash code.
    1711             :         __node_type* __node =
    1712             :           this->_M_allocate_node(std::forward<_Args>(__args)...);
    1713             : 
    1714             :         __hash_code __code;
    1715             :         __try
    1716             :           {
    1717             :             __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
    1718             :           }
    1719             :         __catch(...)
    1720             :           {
    1721             :             this->_M_deallocate_node(__node);
    1722             :             __throw_exception_again;
    1723             :           }
    1724             : 
    1725             :         return _M_insert_multi_node(__hint._M_cur, __code, __node);
    1726             :       }
    1727             : 
    1728             :   template<typename _Key, typename _Value,
    1729             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1730             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1731             :            typename _Traits>
    1732             :     auto
    1733             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1734             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1735             :     _M_insert_unique_node(size_type __bkt, __hash_code __code,
    1736             :                           __node_type* __node, size_type __n_elt)
    1737             :     -> iterator
    1738             :     {
    1739             :       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
    1740             :       std::pair<bool, std::size_t> __do_rehash
    1741             :         = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
    1742             :                                           __n_elt);
    1743             : 
    1744             :       __try
    1745             :         {
    1746             :           if (__do_rehash.first)
    1747             :             {
    1748             :               _M_rehash(__do_rehash.second, __saved_state);
    1749             :               __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
    1750             :             }
    1751             : 
    1752             :           this->_M_store_code(__node, __code);
    1753             : 
    1754             :           // Always insert at the beginning of the bucket.
    1755             :           _M_insert_bucket_begin(__bkt, __node);
    1756             :           ++_M_element_count;
    1757             :           return iterator(__node);
    1758             :         }
    1759             :       __catch(...)
    1760             :         {
    1761             :           this->_M_deallocate_node(__node);
    1762             :           __throw_exception_again;
    1763             :         }
    1764             :     }
    1765             : 
    1766             :   // Insert node, in bucket bkt if no rehash (assumes no element with its key
    1767             :   // already present). Take ownership of the node, deallocate it on exception.
    1768             :   template<typename _Key, typename _Value,
    1769             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1770             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1771             :            typename _Traits>
    1772             :     auto
    1773             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1774             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1775             :     _M_insert_multi_node(__node_type* __hint, __hash_code __code,
    1776             :                          __node_type* __node)
    1777             :     -> iterator
    1778             :     {
    1779             :       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
    1780             :       std::pair<bool, std::size_t> __do_rehash
    1781             :         = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
    1782             : 
    1783             :       __try
    1784             :         {
    1785             :           if (__do_rehash.first)
    1786             :             _M_rehash(__do_rehash.second, __saved_state);
    1787             : 
    1788             :           this->_M_store_code(__node, __code);
    1789             :           const key_type& __k = this->_M_extract()(__node->_M_v());
    1790             :           size_type __bkt = _M_bucket_index(__k, __code);
    1791             : 
    1792             :           // Find the node before an equivalent one or use hint if it exists and
    1793             :           // if it is equivalent.
    1794             :           __node_base* __prev
    1795             :             = __builtin_expect(__hint != nullptr, false)
    1796             :               && this->_M_equals(__k, __code, __hint)
    1797             :                 ? __hint
    1798             :                 : _M_find_before_node(__bkt, __k, __code);
    1799             :           if (__prev)
    1800             :             {
    1801             :               // Insert after the node before the equivalent one.
    1802             :               __node->_M_nxt = __prev->_M_nxt;
    1803             :               __prev->_M_nxt = __node;
    1804             :               if (__builtin_expect(__prev == __hint, false))
    1805             :                 // hint might be the last bucket node, in this case we need to
    1806             :                 // update next bucket.
    1807             :                 if (__node->_M_nxt
    1808             :                     && !this->_M_equals(__k, __code, __node->_M_next()))
    1809             :                   {
    1810             :                     size_type __next_bkt = _M_bucket_index(__node->_M_next());
    1811             :                     if (__next_bkt != __bkt)
    1812             :                       _M_buckets[__next_bkt] = __node;
    1813             :                   }
    1814             :             }
    1815             :           else
    1816             :             // The inserted node has no equivalent in the
    1817             :             // hashtable. We must insert the new node at the
    1818             :             // beginning of the bucket to preserve equivalent
    1819             :             // elements' relative positions.
    1820             :             _M_insert_bucket_begin(__bkt, __node);
    1821             :           ++_M_element_count;
    1822             :           return iterator(__node);
    1823             :         }
    1824             :       __catch(...)
    1825             :         {
    1826             :           this->_M_deallocate_node(__node);
    1827             :           __throw_exception_again;
    1828             :         }
    1829             :     }
    1830             : 
    1831             :   // Insert v if no element with its key is already present.
    1832             :   template<typename _Key, typename _Value,
    1833             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1834             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1835             :            typename _Traits>
    1836             :     template<typename _Arg, typename _NodeGenerator>
    1837             :       auto
    1838             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1839             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1840             :       _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, true_type,
    1841             :                 size_type __n_elt)
    1842             :       -> pair<iterator, bool>
    1843             :       {
    1844             :         const key_type& __k = this->_M_extract()(__v);
    1845             :         __hash_code __code = this->_M_hash_code(__k);
    1846             :         size_type __bkt = _M_bucket_index(__k, __code);
    1847             : 
    1848             :         __node_type* __n = _M_find_node(__bkt, __k, __code);
    1849             :         if (__n)
    1850             :           return std::make_pair(iterator(__n), false);
    1851             : 
    1852             :         __n = __node_gen(std::forward<_Arg>(__v));
    1853             :         return { _M_insert_unique_node(__bkt, __code, __n, __n_elt), true };
    1854             :       }
    1855             : 
    1856             :   // Insert v unconditionally.
    1857             :   template<typename _Key, typename _Value,
    1858             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1859             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1860             :            typename _Traits>
    1861             :     template<typename _Arg, typename _NodeGenerator>
    1862             :       auto
    1863             :       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1864             :                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1865             :       _M_insert(const_iterator __hint, _Arg&& __v,
    1866             :                 const _NodeGenerator& __node_gen, false_type)
    1867             :       -> iterator
    1868             :       {
    1869             :         // First compute the hash code so that we don't do anything if it
    1870             :         // throws.
    1871             :         __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
    1872             : 
    1873             :         // Second allocate new node so that we don't rehash if it throws.
    1874             :         __node_type* __node = __node_gen(std::forward<_Arg>(__v));
    1875             : 
    1876             :         return _M_insert_multi_node(__hint._M_cur, __code, __node);
    1877             :       }
    1878             : 
    1879             :   template<typename _Key, typename _Value,
    1880             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1881             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1882             :            typename _Traits>
    1883             :     auto
    1884             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1885             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1886             :     erase(const_iterator __it)
    1887             :     -> iterator
    1888             :     {
    1889             :       __node_type* __n = __it._M_cur;
    1890             :       std::size_t __bkt = _M_bucket_index(__n);
    1891             : 
    1892             :       // Look for previous node to unlink it from the erased one, this
    1893             :       // is why we need buckets to contain the before begin to make
    1894             :       // this search fast.
    1895             :       __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
    1896             :       return _M_erase(__bkt, __prev_n, __n);
    1897             :     }
    1898             : 
    1899             :   template<typename _Key, typename _Value,
    1900             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1901             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1902             :            typename _Traits>
    1903             :     auto
    1904             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1905             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1906             :     _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
    1907             :     -> iterator
    1908             :     {
    1909             :       if (__prev_n == _M_buckets[__bkt])
    1910             :         _M_remove_bucket_begin(__bkt, __n->_M_next(),
    1911             :            __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
    1912             :       else if (__n->_M_nxt)
    1913             :         {
    1914             :           size_type __next_bkt = _M_bucket_index(__n->_M_next());
    1915             :           if (__next_bkt != __bkt)
    1916             :             _M_buckets[__next_bkt] = __prev_n;
    1917             :         }
    1918             : 
    1919             :       __prev_n->_M_nxt = __n->_M_nxt;
    1920             :       iterator __result(__n->_M_next());
    1921             :       this->_M_deallocate_node(__n);
    1922             :       --_M_element_count;
    1923             : 
    1924             :       return __result;
    1925             :     }
    1926             : 
    1927             :   template<typename _Key, typename _Value,
    1928             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1929             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1930             :            typename _Traits>
    1931             :     auto
    1932             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1933             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1934             :     _M_erase(std::true_type, const key_type& __k)
    1935             :     -> size_type
    1936             :     {
    1937             :       __hash_code __code = this->_M_hash_code(__k);
    1938             :       std::size_t __bkt = _M_bucket_index(__k, __code);
    1939             : 
    1940             :       // Look for the node before the first matching node.
    1941             :       __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
    1942             :       if (!__prev_n)
    1943             :         return 0;
    1944             : 
    1945             :       // We found a matching node, erase it.
    1946             :       __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
    1947             :       _M_erase(__bkt, __prev_n, __n);
    1948             :       return 1;
    1949             :     }
    1950             : 
    1951             :   template<typename _Key, typename _Value,
    1952             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    1953             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    1954             :            typename _Traits>
    1955             :     auto
    1956             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    1957             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    1958             :     _M_erase(std::false_type, const key_type& __k)
    1959             :     -> size_type
    1960             :     {
    1961             :       __hash_code __code = this->_M_hash_code(__k);
    1962             :       std::size_t __bkt = _M_bucket_index(__k, __code);
    1963             : 
    1964             :       // Look for the node before the first matching node.
    1965             :       __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
    1966             :       if (!__prev_n)
    1967             :         return 0;
    1968             : 
    1969             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1970             :       // 526. Is it undefined if a function in the standard changes
    1971             :       // in parameters?
    1972             :       // We use one loop to find all matching nodes and another to deallocate
    1973             :       // them so that the key stays valid during the first loop. It might be
    1974             :       // invalidated indirectly when destroying nodes.
    1975             :       __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
    1976             :       __node_type* __n_last = __n;
    1977             :       std::size_t __n_last_bkt = __bkt;
    1978             :       do
    1979             :         {
    1980             :           __n_last = __n_last->_M_next();
    1981             :           if (!__n_last)
    1982             :             break;
    1983             :           __n_last_bkt = _M_bucket_index(__n_last);
    1984             :         }
    1985             :       while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
    1986             : 
    1987             :       // Deallocate nodes.
    1988             :       size_type __result = 0;
    1989             :       do
    1990             :         {
    1991             :           __node_type* __p = __n->_M_next();
    1992             :           this->_M_deallocate_node(__n);
    1993             :           __n = __p;
    1994             :           ++__result;
    1995             :           --_M_element_count;
    1996             :         }
    1997             :       while (__n != __n_last);
    1998             : 
    1999             :       if (__prev_n == _M_buckets[__bkt])
    2000             :         _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
    2001             :       else if (__n_last && __n_last_bkt != __bkt)
    2002             :         _M_buckets[__n_last_bkt] = __prev_n;
    2003             :       __prev_n->_M_nxt = __n_last;
    2004             :       return __result;
    2005             :     }
    2006             : 
    2007             :   template<typename _Key, typename _Value,
    2008             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    2009             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    2010             :            typename _Traits>
    2011             :     auto
    2012             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    2013             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    2014             :     erase(const_iterator __first, const_iterator __last)
    2015             :     -> iterator
    2016             :     {
    2017             :       __node_type* __n = __first._M_cur;
    2018             :       __node_type* __last_n = __last._M_cur;
    2019             :       if (__n == __last_n)
    2020             :         return iterator(__n);
    2021             : 
    2022             :       std::size_t __bkt = _M_bucket_index(__n);
    2023             : 
    2024             :       __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
    2025             :       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
    2026             :       std::size_t __n_bkt = __bkt;
    2027             :       for (;;)
    2028             :         {
    2029             :           do
    2030             :             {
    2031             :               __node_type* __tmp = __n;
    2032             :               __n = __n->_M_next();
    2033             :               this->_M_deallocate_node(__tmp);
    2034             :               --_M_element_count;
    2035             :               if (!__n)
    2036             :                 break;
    2037             :               __n_bkt = _M_bucket_index(__n);
    2038             :             }
    2039             :           while (__n != __last_n && __n_bkt == __bkt);
    2040             :           if (__is_bucket_begin)
    2041             :             _M_remove_bucket_begin(__bkt, __n, __n_bkt);
    2042             :           if (__n == __last_n)
    2043             :             break;
    2044             :           __is_bucket_begin = true;
    2045             :           __bkt = __n_bkt;
    2046             :         }
    2047             : 
    2048             :       if (__n && (__n_bkt != __bkt || __is_bucket_begin))
    2049             :         _M_buckets[__n_bkt] = __prev_n;
    2050             :       __prev_n->_M_nxt = __n;
    2051             :       return iterator(__n);
    2052             :     }
    2053             : 
    2054             :   template<typename _Key, typename _Value,
    2055             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    2056             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    2057             :            typename _Traits>
    2058             :     void
    2059         712 :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    2060             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    2061             :     clear() noexcept
    2062             :     {
    2063         712 :       this->_M_deallocate_nodes(_M_begin());
    2064         712 :       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type));
    2065         712 :       _M_element_count = 0;
    2066         712 :       _M_before_begin._M_nxt = nullptr;
    2067         712 :     }
    2068             : 
    2069             :   template<typename _Key, typename _Value,
    2070             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    2071             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    2072             :            typename _Traits>
    2073             :     void
    2074             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    2075             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    2076             :     rehash(size_type __n)
    2077             :     {
    2078             :       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
    2079             :       std::size_t __buckets
    2080             :         = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
    2081             :                    __n);
    2082             :       __buckets = _M_rehash_policy._M_next_bkt(__buckets);
    2083             : 
    2084             :       if (__buckets != _M_bucket_count)
    2085             :         _M_rehash(__buckets, __saved_state);
    2086             :       else
    2087             :         // No rehash, restore previous state to keep a consistent state.
    2088             :         _M_rehash_policy._M_reset(__saved_state);
    2089             :     }
    2090             : 
    2091             :   template<typename _Key, typename _Value,
    2092             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    2093             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    2094             :            typename _Traits>
    2095             :     void
    2096             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    2097             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    2098             :     _M_rehash(size_type __n, const __rehash_state& __state)
    2099             :     {
    2100             :       __try
    2101             :         {
    2102             :           _M_rehash_aux(__n, __unique_keys());
    2103             :         }
    2104             :       __catch(...)
    2105             :         {
    2106             :           // A failure here means that buckets allocation failed.  We only
    2107             :           // have to restore hash policy previous state.
    2108             :           _M_rehash_policy._M_reset(__state);
    2109             :           __throw_exception_again;
    2110             :         }
    2111             :     }
    2112             : 
    2113             :   // Rehash when there is no equivalent elements.
    2114             :   template<typename _Key, typename _Value,
    2115             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    2116             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    2117             :            typename _Traits>
    2118             :     void
    2119             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    2120             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    2121             :     _M_rehash_aux(size_type __n, std::true_type)
    2122             :     {
    2123             :       __bucket_type* __new_buckets = _M_allocate_buckets(__n);
    2124             :       __node_type* __p = _M_begin();
    2125             :       _M_before_begin._M_nxt = nullptr;
    2126             :       std::size_t __bbegin_bkt = 0;
    2127             :       while (__p)
    2128             :         {
    2129             :           __node_type* __next = __p->_M_next();
    2130             :           std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
    2131             :           if (!__new_buckets[__bkt])
    2132             :             {
    2133             :               __p->_M_nxt = _M_before_begin._M_nxt;
    2134             :               _M_before_begin._M_nxt = __p;
    2135             :               __new_buckets[__bkt] = &_M_before_begin;
    2136             :               if (__p->_M_nxt)
    2137             :                 __new_buckets[__bbegin_bkt] = __p;
    2138             :               __bbegin_bkt = __bkt;
    2139             :             }
    2140             :           else
    2141             :             {
    2142             :               __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
    2143             :               __new_buckets[__bkt]->_M_nxt = __p;
    2144             :             }
    2145             :           __p = __next;
    2146             :         }
    2147             : 
    2148             :       _M_deallocate_buckets();
    2149             :       _M_bucket_count = __n;
    2150             :       _M_buckets = __new_buckets;
    2151             :     }
    2152             : 
    2153             :   // Rehash when there can be equivalent elements, preserve their relative
    2154             :   // order.
    2155             :   template<typename _Key, typename _Value,
    2156             :            typename _Alloc, typename _ExtractKey, typename _Equal,
    2157             :            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
    2158             :            typename _Traits>
    2159             :     void
    2160             :     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
    2161             :                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
    2162             :     _M_rehash_aux(size_type __n, std::false_type)
    2163             :     {
    2164             :       __bucket_type* __new_buckets = _M_allocate_buckets(__n);
    2165             : 
    2166             :       __node_type* __p = _M_begin();
    2167             :       _M_before_begin._M_nxt = nullptr;
    2168             :       std::size_t __bbegin_bkt = 0;
    2169             :       std::size_t __prev_bkt = 0;
    2170             :       __node_type* __prev_p = nullptr;
    2171             :       bool __check_bucket = false;
    2172             : 
    2173             :       while (__p)
    2174             :         {
    2175             :           __node_type* __next = __p->_M_next();
    2176             :           std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
    2177             : 
    2178             :           if (__prev_p && __prev_bkt == __bkt)
    2179             :             {
    2180             :               // Previous insert was already in this bucket, we insert after
    2181             :               // the previously inserted one to preserve equivalent elements
    2182             :               // relative order.
    2183             :               __p->_M_nxt = __prev_p->_M_nxt;
    2184             :               __prev_p->_M_nxt = __p;
    2185             : 
    2186             :               // Inserting after a node in a bucket require to check that we
    2187             :               // haven't change the bucket last node, in this case next
    2188             :               // bucket containing its before begin node must be updated. We
    2189             :               // schedule a check as soon as we move out of the sequence of
    2190             :               // equivalent nodes to limit the number of checks.
    2191             :               __check_bucket = true;
    2192             :             }
    2193             :           else
    2194             :             {
    2195             :               if (__check_bucket)
    2196             :                 {
    2197             :                   // Check if we shall update the next bucket because of
    2198             :                   // insertions into __prev_bkt bucket.
    2199             :                   if (__prev_p->_M_nxt)
    2200             :                     {
    2201             :                       std::size_t __next_bkt
    2202             :                         = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
    2203             :                                                             __n);
    2204             :                       if (__next_bkt != __prev_bkt)
    2205             :                         __new_buckets[__next_bkt] = __prev_p;
    2206             :                     }
    2207             :                   __check_bucket = false;
    2208             :                 }
    2209             : 
    2210             :               if (!__new_buckets[__bkt])
    2211             :                 {
    2212             :                   __p->_M_nxt = _M_before_begin._M_nxt;
    2213             :                   _M_before_begin._M_nxt = __p;
    2214             :                   __new_buckets[__bkt] = &_M_before_begin;
    2215             :                   if (__p->_M_nxt)
    2216             :                     __new_buckets[__bbegin_bkt] = __p;
    2217             :                   __bbegin_bkt = __bkt;
    2218             :                 }
    2219             :               else
    2220             :                 {
    2221             :                   __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
    2222             :                   __new_buckets[__bkt]->_M_nxt = __p;
    2223             :                 }
    2224             :             }
    2225             :           __prev_p = __p;
    2226             :           __prev_bkt = __bkt;
    2227             :           __p = __next;
    2228             :         }
    2229             : 
    2230             :       if (__check_bucket && __prev_p->_M_nxt)
    2231             :         {
    2232             :           std::size_t __next_bkt
    2233             :             = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
    2234             :           if (__next_bkt != __prev_bkt)
    2235             :             __new_buckets[__next_bkt] = __prev_p;
    2236             :         }
    2237             : 
    2238             :       _M_deallocate_buckets();
    2239             :       _M_bucket_count = __n;
    2240             :       _M_buckets = __new_buckets;
    2241             :     }
    2242             : 
    2243             : #if __cplusplus > 201402L
    2244             :   template<typename, typename, typename> class _Hash_merge_helper { };
    2245             : #endif // C++17
    2246             : 
    2247             : #if __cpp_deduction_guides >= 201606
    2248             :   // Used to constrain deduction guides
    2249             :   template<typename _Hash>
    2250             :     using _RequireNotAllocatorOrIntegral
    2251             :       = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
    2252             : #endif
    2253             : 
    2254             : _GLIBCXX_END_NAMESPACE_VERSION
    2255             : } // namespace std
    2256             : 
    2257             : #endif // _HASHTABLE_H

Generated by: LCOV version 1.14