LCOV - code coverage report
Current view: top level - usr/include/c++/7/bits - hashtable.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 128 181 70.7 %
Date: 2020-10-15 20:26:03 Functions: 37 44 84.1 %

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

Generated by: LCOV version 1.13