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