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         __try
00977           {
00978             for (; __f != __l; ++__f)
00979               this->insert(*__f);
00980           }
00981         __catch(...)
00982           {
00983             clear();
00984             _M_deallocate_buckets();
00985             __throw_exception_again;
00986           }
00987       }
00988 
00989   template<typename _Key, typename _Value,
00990            typename _Alloc, typename _ExtractKey, typename _Equal,
00991            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
00992            typename _Traits>
00993     auto
00994     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
00995                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
00996     operator=(const _Hashtable& __ht)
00997     -> _Hashtable&
00998     {
00999       if (&__ht == this)
01000         return *this;
01001 
01002       if (__node_alloc_traits::_S_propagate_on_copy_assign())
01003         {
01004           auto& __this_alloc = this->_M_node_allocator();
01005           auto& __that_alloc = __ht._M_node_allocator();
01006           if (!__node_alloc_traits::_S_always_equal()
01007               && __this_alloc != __that_alloc)
01008             {
01009               // Replacement allocator cannot free existing storage.
01010               this->_M_deallocate_nodes(_M_begin());
01011               _M_before_begin._M_nxt = nullptr;
01012               _M_deallocate_buckets();
01013               _M_buckets = nullptr;
01014               std::__alloc_on_copy(__this_alloc, __that_alloc);
01015               __hashtable_base::operator=(__ht);
01016               _M_bucket_count = __ht._M_bucket_count;
01017               _M_element_count = __ht._M_element_count;
01018               _M_rehash_policy = __ht._M_rehash_policy;
01019               __try
01020                 {
01021                   _M_assign(__ht,
01022                             [this](const __node_type* __n)
01023                             { return this->_M_allocate_node(__n->_M_v()); });
01024                 }
01025               __catch(...)
01026                 {
01027                   // _M_assign took care of deallocating all memory. Now we
01028                   // must make sure this instance remains in a usable state.
01029                   _M_reset();
01030                   __throw_exception_again;
01031                 }
01032               return *this;
01033             }
01034           std::__alloc_on_copy(__this_alloc, __that_alloc);
01035         }
01036 
01037       // Reuse allocated buckets and nodes.
01038       __bucket_type* __former_buckets = nullptr;
01039       std::size_t __former_bucket_count = _M_bucket_count;
01040       const __rehash_state& __former_state = _M_rehash_policy._M_state();
01041 
01042       if (_M_bucket_count != __ht._M_bucket_count)
01043         {
01044           __former_buckets = _M_buckets;
01045           _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
01046           _M_bucket_count = __ht._M_bucket_count;
01047         }
01048       else
01049         __builtin_memset(_M_buckets, 0,
01050                          _M_bucket_count * sizeof(__bucket_type));
01051 
01052       __try
01053         {
01054           __hashtable_base::operator=(__ht);
01055           _M_element_count = __ht._M_element_count;
01056           _M_rehash_policy = __ht._M_rehash_policy;
01057           __reuse_or_alloc_node_type __roan(_M_begin(), *this);
01058           _M_before_begin._M_nxt = nullptr;
01059           _M_assign(__ht,
01060                     [&__roan](const __node_type* __n)
01061                     { return __roan(__n->_M_v()); });
01062           if (__former_buckets)
01063             _M_deallocate_buckets(__former_buckets, __former_bucket_count);
01064         }
01065       __catch(...)
01066         {
01067           if (__former_buckets)
01068             {
01069               // Restore previous buckets.
01070               _M_deallocate_buckets();
01071               _M_rehash_policy._M_reset(__former_state);
01072               _M_buckets = __former_buckets;
01073               _M_bucket_count = __former_bucket_count;
01074             }
01075           __builtin_memset(_M_buckets, 0,
01076                            _M_bucket_count * sizeof(__bucket_type));
01077           __throw_exception_again;
01078         }
01079       return *this;
01080     }
01081 
01082   template<typename _Key, typename _Value,
01083            typename _Alloc, typename _ExtractKey, typename _Equal,
01084            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01085            typename _Traits>
01086     template<typename _NodeGenerator>
01087       void
01088       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01089                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01090       _M_assign(const _Hashtable& __ht, const _NodeGenerator& __node_gen)
01091       {
01092         __bucket_type* __buckets = nullptr;
01093         if (!_M_buckets)
01094           _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
01095 
01096         __try
01097           {
01098             if (!__ht._M_before_begin._M_nxt)
01099               return;
01100 
01101             // First deal with the special first node pointed to by
01102             // _M_before_begin.
01103             __node_type* __ht_n = __ht._M_begin();
01104             __node_type* __this_n = __node_gen(__ht_n);
01105             this->_M_copy_code(__this_n, __ht_n);
01106             _M_before_begin._M_nxt = __this_n;
01107             _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
01108 
01109             // Then deal with other nodes.
01110             __node_base* __prev_n = __this_n;
01111             for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
01112               {
01113                 __this_n = __node_gen(__ht_n);
01114                 __prev_n->_M_nxt = __this_n;
01115                 this->_M_copy_code(__this_n, __ht_n);
01116                 size_type __bkt = _M_bucket_index(__this_n);
01117                 if (!_M_buckets[__bkt])
01118                   _M_buckets[__bkt] = __prev_n;
01119                 __prev_n = __this_n;
01120               }
01121           }
01122         __catch(...)
01123           {
01124             clear();
01125             if (__buckets)
01126               _M_deallocate_buckets();
01127             __throw_exception_again;
01128           }
01129       }
01130 
01131   template<typename _Key, typename _Value,
01132            typename _Alloc, typename _ExtractKey, typename _Equal,
01133            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01134            typename _Traits>
01135     void
01136     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01137                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01138     _M_reset() noexcept
01139     {
01140       _M_rehash_policy._M_reset();
01141       _M_bucket_count = 1;
01142       _M_single_bucket = nullptr;
01143       _M_buckets = &_M_single_bucket;
01144       _M_before_begin._M_nxt = nullptr;
01145       _M_element_count = 0;
01146     }
01147 
01148   template<typename _Key, typename _Value,
01149            typename _Alloc, typename _ExtractKey, typename _Equal,
01150            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01151            typename _Traits>
01152     void
01153     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01154                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01155     _M_move_assign(_Hashtable&& __ht, std::true_type)
01156     {
01157       this->_M_deallocate_nodes(_M_begin());
01158       _M_deallocate_buckets();
01159       __hashtable_base::operator=(std::move(__ht));
01160       _M_rehash_policy = __ht._M_rehash_policy;
01161       if (!__ht._M_uses_single_bucket())
01162         _M_buckets = __ht._M_buckets;
01163       else
01164         {
01165           _M_buckets = &_M_single_bucket;
01166           _M_single_bucket = __ht._M_single_bucket;
01167         }
01168       _M_bucket_count = __ht._M_bucket_count;
01169       _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
01170       _M_element_count = __ht._M_element_count;
01171       std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
01172 
01173       // Fix buckets containing the _M_before_begin pointers that can't be
01174       // moved.
01175       if (_M_begin())
01176         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
01177       __ht._M_reset();
01178     }
01179 
01180   template<typename _Key, typename _Value,
01181            typename _Alloc, typename _ExtractKey, typename _Equal,
01182            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01183            typename _Traits>
01184     void
01185     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01186                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01187     _M_move_assign(_Hashtable&& __ht, std::false_type)
01188     {
01189       if (__ht._M_node_allocator() == this->_M_node_allocator())
01190         _M_move_assign(std::move(__ht), std::true_type());
01191       else
01192         {
01193           // Can't move memory, move elements then.
01194           __bucket_type* __former_buckets = nullptr;
01195           size_type __former_bucket_count = _M_bucket_count;
01196           const __rehash_state& __former_state = _M_rehash_policy._M_state();
01197 
01198           if (_M_bucket_count != __ht._M_bucket_count)
01199             {
01200               __former_buckets = _M_buckets;
01201               _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
01202               _M_bucket_count = __ht._M_bucket_count;
01203             }
01204           else
01205             __builtin_memset(_M_buckets, 0,
01206                              _M_bucket_count * sizeof(__bucket_type));
01207 
01208           __try
01209             {
01210               __hashtable_base::operator=(std::move(__ht));
01211               _M_element_count = __ht._M_element_count;
01212               _M_rehash_policy = __ht._M_rehash_policy;
01213               __reuse_or_alloc_node_type __roan(_M_begin(), *this);
01214               _M_before_begin._M_nxt = nullptr;
01215               _M_assign(__ht,
01216                         [&__roan](__node_type* __n)
01217                         { return __roan(std::move_if_noexcept(__n->_M_v())); });
01218               __ht.clear();
01219             }
01220           __catch(...)
01221             {
01222               if (__former_buckets)
01223                 {
01224                   _M_deallocate_buckets();
01225                   _M_rehash_policy._M_reset(__former_state);
01226                   _M_buckets = __former_buckets;
01227                   _M_bucket_count = __former_bucket_count;
01228                 }
01229               __builtin_memset(_M_buckets, 0,
01230                                _M_bucket_count * sizeof(__bucket_type));
01231               __throw_exception_again;
01232             }
01233         }
01234     }
01235 
01236   template<typename _Key, typename _Value,
01237            typename _Alloc, typename _ExtractKey, typename _Equal,
01238            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01239            typename _Traits>
01240     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01241                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01242     _Hashtable(const _Hashtable& __ht)
01243     : __hashtable_base(__ht),
01244       __map_base(__ht),
01245       __rehash_base(__ht),
01246       __hashtable_alloc(
01247         __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
01248       _M_buckets(nullptr),
01249       _M_bucket_count(__ht._M_bucket_count),
01250       _M_element_count(__ht._M_element_count),
01251       _M_rehash_policy(__ht._M_rehash_policy)
01252     {
01253       _M_assign(__ht,
01254                 [this](const __node_type* __n)
01255                 { return this->_M_allocate_node(__n->_M_v()); });
01256     }
01257 
01258   template<typename _Key, typename _Value,
01259            typename _Alloc, typename _ExtractKey, typename _Equal,
01260            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01261            typename _Traits>
01262     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01263                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01264     _Hashtable(_Hashtable&& __ht) noexcept
01265     : __hashtable_base(__ht),
01266       __map_base(__ht),
01267       __rehash_base(__ht),
01268       __hashtable_alloc(std::move(__ht._M_base_alloc())),
01269       _M_buckets(__ht._M_buckets),
01270       _M_bucket_count(__ht._M_bucket_count),
01271       _M_before_begin(__ht._M_before_begin._M_nxt),
01272       _M_element_count(__ht._M_element_count),
01273       _M_rehash_policy(__ht._M_rehash_policy)
01274     {
01275       // Update, if necessary, buckets if __ht is using its single bucket.
01276       if (__ht._M_uses_single_bucket())
01277         {
01278           _M_buckets = &_M_single_bucket;
01279           _M_single_bucket = __ht._M_single_bucket;
01280         }
01281 
01282       // Update, if necessary, bucket pointing to before begin that hasn't
01283       // moved.
01284       if (_M_begin())
01285         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
01286 
01287       __ht._M_reset();
01288     }
01289 
01290   template<typename _Key, typename _Value,
01291            typename _Alloc, typename _ExtractKey, typename _Equal,
01292            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01293            typename _Traits>
01294     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01295                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01296     _Hashtable(const _Hashtable& __ht, const allocator_type& __a)
01297     : __hashtable_base(__ht),
01298       __map_base(__ht),
01299       __rehash_base(__ht),
01300       __hashtable_alloc(__node_alloc_type(__a)),
01301       _M_buckets(),
01302       _M_bucket_count(__ht._M_bucket_count),
01303       _M_element_count(__ht._M_element_count),
01304       _M_rehash_policy(__ht._M_rehash_policy)
01305     {
01306       _M_assign(__ht,
01307                 [this](const __node_type* __n)
01308                 { return this->_M_allocate_node(__n->_M_v()); });
01309     }
01310 
01311   template<typename _Key, typename _Value,
01312            typename _Alloc, typename _ExtractKey, typename _Equal,
01313            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01314            typename _Traits>
01315     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01316                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01317     _Hashtable(_Hashtable&& __ht, const allocator_type& __a)
01318     : __hashtable_base(__ht),
01319       __map_base(__ht),
01320       __rehash_base(__ht),
01321       __hashtable_alloc(__node_alloc_type(__a)),
01322       _M_buckets(nullptr),
01323       _M_bucket_count(__ht._M_bucket_count),
01324       _M_element_count(__ht._M_element_count),
01325       _M_rehash_policy(__ht._M_rehash_policy)
01326     {
01327       if (__ht._M_node_allocator() == this->_M_node_allocator())
01328         {
01329           if (__ht._M_uses_single_bucket())
01330             {
01331               _M_buckets = &_M_single_bucket;
01332               _M_single_bucket = __ht._M_single_bucket;
01333             }
01334           else
01335             _M_buckets = __ht._M_buckets;
01336 
01337           _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
01338           // Update, if necessary, bucket pointing to before begin that hasn't
01339           // moved.
01340           if (_M_begin())
01341             _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
01342           __ht._M_reset();
01343         }
01344       else
01345         {
01346           _M_assign(__ht,
01347                     [this](__node_type* __n)
01348                     {
01349                       return this->_M_allocate_node(
01350                                         std::move_if_noexcept(__n->_M_v()));
01351                     });
01352           __ht.clear();
01353         }
01354     }
01355 
01356   template<typename _Key, typename _Value,
01357            typename _Alloc, typename _ExtractKey, typename _Equal,
01358            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01359            typename _Traits>
01360     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01361                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01362     ~_Hashtable() noexcept
01363     {
01364       clear();
01365       _M_deallocate_buckets();
01366     }
01367 
01368   template<typename _Key, typename _Value,
01369            typename _Alloc, typename _ExtractKey, typename _Equal,
01370            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01371            typename _Traits>
01372     void
01373     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01374                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01375     swap(_Hashtable& __x)
01376     noexcept(__and_<__is_nothrow_swappable<_H1>,
01377                         __is_nothrow_swappable<_Equal>>::value)
01378     {
01379       // The only base class with member variables is hash_code_base.
01380       // We define _Hash_code_base::_M_swap because different
01381       // specializations have different members.
01382       this->_M_swap(__x);
01383 
01384       std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
01385       std::swap(_M_rehash_policy, __x._M_rehash_policy);
01386 
01387       // Deal properly with potentially moved instances.
01388       if (this->_M_uses_single_bucket())
01389         {
01390           if (!__x._M_uses_single_bucket())
01391             {
01392               _M_buckets = __x._M_buckets;
01393               __x._M_buckets = &__x._M_single_bucket;
01394             }
01395         }
01396       else if (__x._M_uses_single_bucket())
01397         {
01398           __x._M_buckets = _M_buckets;
01399           _M_buckets = &_M_single_bucket;
01400         }       
01401       else
01402         std::swap(_M_buckets, __x._M_buckets);
01403 
01404       std::swap(_M_bucket_count, __x._M_bucket_count);
01405       std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
01406       std::swap(_M_element_count, __x._M_element_count);
01407       std::swap(_M_single_bucket, __x._M_single_bucket);
01408 
01409       // Fix buckets containing the _M_before_begin pointers that can't be
01410       // swapped.
01411       if (_M_begin())
01412         _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
01413 
01414       if (__x._M_begin())
01415         __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
01416           = &__x._M_before_begin;
01417     }
01418 
01419   template<typename _Key, typename _Value,
01420            typename _Alloc, typename _ExtractKey, typename _Equal,
01421            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01422            typename _Traits>
01423     auto
01424     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01425                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01426     find(const key_type& __k)
01427     -> iterator
01428     {
01429       __hash_code __code = this->_M_hash_code(__k);
01430       std::size_t __n = _M_bucket_index(__k, __code);
01431       __node_type* __p = _M_find_node(__n, __k, __code);
01432       return __p ? iterator(__p) : end();
01433     }
01434 
01435   template<typename _Key, typename _Value,
01436            typename _Alloc, typename _ExtractKey, typename _Equal,
01437            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01438            typename _Traits>
01439     auto
01440     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01441                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01442     find(const key_type& __k) const
01443     -> const_iterator
01444     {
01445       __hash_code __code = this->_M_hash_code(__k);
01446       std::size_t __n = _M_bucket_index(__k, __code);
01447       __node_type* __p = _M_find_node(__n, __k, __code);
01448       return __p ? const_iterator(__p) : end();
01449     }
01450 
01451   template<typename _Key, typename _Value,
01452            typename _Alloc, typename _ExtractKey, typename _Equal,
01453            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01454            typename _Traits>
01455     auto
01456     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01457                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01458     count(const key_type& __k) const
01459     -> size_type
01460     {
01461       __hash_code __code = this->_M_hash_code(__k);
01462       std::size_t __n = _M_bucket_index(__k, __code);
01463       __node_type* __p = _M_bucket_begin(__n);
01464       if (!__p)
01465         return 0;
01466 
01467       std::size_t __result = 0;
01468       for (;; __p = __p->_M_next())
01469         {
01470           if (this->_M_equals(__k, __code, __p))
01471             ++__result;
01472           else if (__result)
01473             // All equivalent values are next to each other, if we
01474             // found a non-equivalent value after an equivalent one it
01475             // means that we won't find any new equivalent value.
01476             break;
01477           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
01478             break;
01479         }
01480       return __result;
01481     }
01482 
01483   template<typename _Key, typename _Value,
01484            typename _Alloc, typename _ExtractKey, typename _Equal,
01485            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01486            typename _Traits>
01487     auto
01488     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01489                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01490     equal_range(const key_type& __k)
01491     -> pair<iterator, iterator>
01492     {
01493       __hash_code __code = this->_M_hash_code(__k);
01494       std::size_t __n = _M_bucket_index(__k, __code);
01495       __node_type* __p = _M_find_node(__n, __k, __code);
01496 
01497       if (__p)
01498         {
01499           __node_type* __p1 = __p->_M_next();
01500           while (__p1 && _M_bucket_index(__p1) == __n
01501                  && this->_M_equals(__k, __code, __p1))
01502             __p1 = __p1->_M_next();
01503 
01504           return std::make_pair(iterator(__p), iterator(__p1));
01505         }
01506       else
01507         return std::make_pair(end(), end());
01508     }
01509 
01510   template<typename _Key, typename _Value,
01511            typename _Alloc, typename _ExtractKey, typename _Equal,
01512            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01513            typename _Traits>
01514     auto
01515     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01516                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01517     equal_range(const key_type& __k) const
01518     -> pair<const_iterator, const_iterator>
01519     {
01520       __hash_code __code = this->_M_hash_code(__k);
01521       std::size_t __n = _M_bucket_index(__k, __code);
01522       __node_type* __p = _M_find_node(__n, __k, __code);
01523 
01524       if (__p)
01525         {
01526           __node_type* __p1 = __p->_M_next();
01527           while (__p1 && _M_bucket_index(__p1) == __n
01528                  && this->_M_equals(__k, __code, __p1))
01529             __p1 = __p1->_M_next();
01530 
01531           return std::make_pair(const_iterator(__p), const_iterator(__p1));
01532         }
01533       else
01534         return std::make_pair(end(), end());
01535     }
01536 
01537   // Find the node whose key compares equal to k in the bucket n.
01538   // Return nullptr if no node is found.
01539   template<typename _Key, typename _Value,
01540            typename _Alloc, typename _ExtractKey, typename _Equal,
01541            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01542            typename _Traits>
01543     auto
01544     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01545                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01546     _M_find_before_node(size_type __n, const key_type& __k,
01547                         __hash_code __code) const
01548     -> __node_base*
01549     {
01550       __node_base* __prev_p = _M_buckets[__n];
01551       if (!__prev_p)
01552         return nullptr;
01553 
01554       for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
01555            __p = __p->_M_next())
01556         {
01557           if (this->_M_equals(__k, __code, __p))
01558             return __prev_p;
01559 
01560           if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
01561             break;
01562           __prev_p = __p;
01563         }
01564       return nullptr;
01565     }
01566 
01567   template<typename _Key, typename _Value,
01568            typename _Alloc, typename _ExtractKey, typename _Equal,
01569            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01570            typename _Traits>
01571     void
01572     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01573                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01574     _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
01575     {
01576       if (_M_buckets[__bkt])
01577         {
01578           // Bucket is not empty, we just need to insert the new node
01579           // after the bucket before begin.
01580           __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
01581           _M_buckets[__bkt]->_M_nxt = __node;
01582         }
01583       else
01584         {
01585           // The bucket is empty, the new node is inserted at the
01586           // beginning of the singly-linked list and the bucket will
01587           // contain _M_before_begin pointer.
01588           __node->_M_nxt = _M_before_begin._M_nxt;
01589           _M_before_begin._M_nxt = __node;
01590           if (__node->_M_nxt)
01591             // We must update former begin bucket that is pointing to
01592             // _M_before_begin.
01593             _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
01594           _M_buckets[__bkt] = &_M_before_begin;
01595         }
01596     }
01597 
01598   template<typename _Key, typename _Value,
01599            typename _Alloc, typename _ExtractKey, typename _Equal,
01600            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01601            typename _Traits>
01602     void
01603     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01604                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01605     _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
01606                            size_type __next_bkt)
01607     {
01608       if (!__next || __next_bkt != __bkt)
01609         {
01610           // Bucket is now empty
01611           // First update next bucket if any
01612           if (__next)
01613             _M_buckets[__next_bkt] = _M_buckets[__bkt];
01614 
01615           // Second update before begin node if necessary
01616           if (&_M_before_begin == _M_buckets[__bkt])
01617             _M_before_begin._M_nxt = __next;
01618           _M_buckets[__bkt] = nullptr;
01619         }
01620     }
01621 
01622   template<typename _Key, typename _Value,
01623            typename _Alloc, typename _ExtractKey, typename _Equal,
01624            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01625            typename _Traits>
01626     auto
01627     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01628                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01629     _M_get_previous_node(size_type __bkt, __node_base* __n)
01630     -> __node_base*
01631     {
01632       __node_base* __prev_n = _M_buckets[__bkt];
01633       while (__prev_n->_M_nxt != __n)
01634         __prev_n = __prev_n->_M_nxt;
01635       return __prev_n;
01636     }
01637 
01638   template<typename _Key, typename _Value,
01639            typename _Alloc, typename _ExtractKey, typename _Equal,
01640            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01641            typename _Traits>
01642     template<typename... _Args>
01643       auto
01644       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01645                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01646       _M_emplace(std::true_type, _Args&&... __args)
01647       -> pair<iterator, bool>
01648       {
01649         // First build the node to get access to the hash code
01650         __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
01651         const key_type& __k = this->_M_extract()(__node->_M_v());
01652         __hash_code __code;
01653         __try
01654           {
01655             __code = this->_M_hash_code(__k);
01656           }
01657         __catch(...)
01658           {
01659             this->_M_deallocate_node(__node);
01660             __throw_exception_again;
01661           }
01662 
01663         size_type __bkt = _M_bucket_index(__k, __code);
01664         if (__node_type* __p = _M_find_node(__bkt, __k, __code))
01665           {
01666             // There is already an equivalent node, no insertion
01667             this->_M_deallocate_node(__node);
01668             return std::make_pair(iterator(__p), false);
01669           }
01670 
01671         // Insert the node
01672         return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
01673                               true);
01674       }
01675 
01676   template<typename _Key, typename _Value,
01677            typename _Alloc, typename _ExtractKey, typename _Equal,
01678            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01679            typename _Traits>
01680     template<typename... _Args>
01681       auto
01682       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01683                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01684       _M_emplace(const_iterator __hint, std::false_type, _Args&&... __args)
01685       -> iterator
01686       {
01687         // First build the node to get its hash code.
01688         __node_type* __node =
01689           this->_M_allocate_node(std::forward<_Args>(__args)...);
01690 
01691         __hash_code __code;
01692         __try
01693           {
01694             __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
01695           }
01696         __catch(...)
01697           {
01698             this->_M_deallocate_node(__node);
01699             __throw_exception_again;
01700           }
01701 
01702         return _M_insert_multi_node(__hint._M_cur, __code, __node);
01703       }
01704 
01705   template<typename _Key, typename _Value,
01706            typename _Alloc, typename _ExtractKey, typename _Equal,
01707            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01708            typename _Traits>
01709     auto
01710     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01711                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01712     _M_insert_unique_node(size_type __bkt, __hash_code __code,
01713                           __node_type* __node)
01714     -> iterator
01715     {
01716       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
01717       std::pair<bool, std::size_t> __do_rehash
01718         = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
01719 
01720       __try
01721         {
01722           if (__do_rehash.first)
01723             {
01724               _M_rehash(__do_rehash.second, __saved_state);
01725               __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
01726             }
01727 
01728           this->_M_store_code(__node, __code);
01729 
01730           // Always insert at the beginning of the bucket.
01731           _M_insert_bucket_begin(__bkt, __node);
01732           ++_M_element_count;
01733           return iterator(__node);
01734         }
01735       __catch(...)
01736         {
01737           this->_M_deallocate_node(__node);
01738           __throw_exception_again;
01739         }
01740     }
01741 
01742   // Insert node, in bucket bkt if no rehash (assumes no element with its key
01743   // already present). Take ownership of the node, deallocate it on exception.
01744   template<typename _Key, typename _Value,
01745            typename _Alloc, typename _ExtractKey, typename _Equal,
01746            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01747            typename _Traits>
01748     auto
01749     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01750                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01751     _M_insert_multi_node(__node_type* __hint, __hash_code __code,
01752                          __node_type* __node)
01753     -> iterator
01754     {
01755       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
01756       std::pair<bool, std::size_t> __do_rehash
01757         = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
01758 
01759       __try
01760         {
01761           if (__do_rehash.first)
01762             _M_rehash(__do_rehash.second, __saved_state);
01763 
01764           this->_M_store_code(__node, __code);
01765           const key_type& __k = this->_M_extract()(__node->_M_v());
01766           size_type __bkt = _M_bucket_index(__k, __code);
01767 
01768           // Find the node before an equivalent one or use hint if it exists and
01769           // if it is equivalent.
01770           __node_base* __prev
01771             = __builtin_expect(__hint != nullptr, false)
01772               && this->_M_equals(__k, __code, __hint)
01773                 ? __hint
01774                 : _M_find_before_node(__bkt, __k, __code);
01775           if (__prev)
01776             {
01777               // Insert after the node before the equivalent one.
01778               __node->_M_nxt = __prev->_M_nxt;
01779               __prev->_M_nxt = __node;
01780               if (__builtin_expect(__prev == __hint, false))
01781                 // hint might be the last bucket node, in this case we need to
01782                 // update next bucket.
01783                 if (__node->_M_nxt
01784                     && !this->_M_equals(__k, __code, __node->_M_next()))
01785                   {
01786                     size_type __next_bkt = _M_bucket_index(__node->_M_next());
01787                     if (__next_bkt != __bkt)
01788                       _M_buckets[__next_bkt] = __node;
01789                   }
01790             }
01791           else
01792             // The inserted node has no equivalent in the
01793             // hashtable. We must insert the new node at the
01794             // beginning of the bucket to preserve equivalent
01795             // elements' relative positions.
01796             _M_insert_bucket_begin(__bkt, __node);
01797           ++_M_element_count;
01798           return iterator(__node);
01799         }
01800       __catch(...)
01801         {
01802           this->_M_deallocate_node(__node);
01803           __throw_exception_again;
01804         }
01805     }
01806 
01807   // Insert v if no element with its key is already present.
01808   template<typename _Key, typename _Value,
01809            typename _Alloc, typename _ExtractKey, typename _Equal,
01810            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01811            typename _Traits>
01812     template<typename _Arg, typename _NodeGenerator>
01813       auto
01814       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01815                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01816       _M_insert(_Arg&& __v, const _NodeGenerator& __node_gen, std::true_type)
01817       -> pair<iterator, bool>
01818       {
01819         const key_type& __k = this->_M_extract()(__v);
01820         __hash_code __code = this->_M_hash_code(__k);
01821         size_type __bkt = _M_bucket_index(__k, __code);
01822 
01823         __node_type* __n = _M_find_node(__bkt, __k, __code);
01824         if (__n)
01825           return std::make_pair(iterator(__n), false);
01826 
01827         __n = __node_gen(std::forward<_Arg>(__v));
01828         return std::make_pair(_M_insert_unique_node(__bkt, __code, __n), true);
01829       }
01830 
01831   // Insert v unconditionally.
01832   template<typename _Key, typename _Value,
01833            typename _Alloc, typename _ExtractKey, typename _Equal,
01834            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01835            typename _Traits>
01836     template<typename _Arg, typename _NodeGenerator>
01837       auto
01838       _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01839                  _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01840       _M_insert(const_iterator __hint, _Arg&& __v,
01841                 const _NodeGenerator& __node_gen, std::false_type)
01842       -> iterator
01843       {
01844         // First compute the hash code so that we don't do anything if it
01845         // throws.
01846         __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
01847 
01848         // Second allocate new node so that we don't rehash if it throws.
01849         __node_type* __node = __node_gen(std::forward<_Arg>(__v));
01850 
01851         return _M_insert_multi_node(__hint._M_cur, __code, __node);
01852       }
01853 
01854   template<typename _Key, typename _Value,
01855            typename _Alloc, typename _ExtractKey, typename _Equal,
01856            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01857            typename _Traits>
01858     auto
01859     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01860                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01861     erase(const_iterator __it)
01862     -> iterator
01863     {
01864       __node_type* __n = __it._M_cur;
01865       std::size_t __bkt = _M_bucket_index(__n);
01866 
01867       // Look for previous node to unlink it from the erased one, this
01868       // is why we need buckets to contain the before begin to make
01869       // this search fast.
01870       __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
01871       return _M_erase(__bkt, __prev_n, __n);
01872     }
01873 
01874   template<typename _Key, typename _Value,
01875            typename _Alloc, typename _ExtractKey, typename _Equal,
01876            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01877            typename _Traits>
01878     auto
01879     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01880                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01881     _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
01882     -> iterator
01883     {
01884       if (__prev_n == _M_buckets[__bkt])
01885         _M_remove_bucket_begin(__bkt, __n->_M_next(),
01886            __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
01887       else if (__n->_M_nxt)
01888         {
01889           size_type __next_bkt = _M_bucket_index(__n->_M_next());
01890           if (__next_bkt != __bkt)
01891             _M_buckets[__next_bkt] = __prev_n;
01892         }
01893 
01894       __prev_n->_M_nxt = __n->_M_nxt;
01895       iterator __result(__n->_M_next());
01896       this->_M_deallocate_node(__n);
01897       --_M_element_count;
01898 
01899       return __result;
01900     }
01901 
01902   template<typename _Key, typename _Value,
01903            typename _Alloc, typename _ExtractKey, typename _Equal,
01904            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01905            typename _Traits>
01906     auto
01907     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01908                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01909     _M_erase(std::true_type, const key_type& __k)
01910     -> size_type
01911     {
01912       __hash_code __code = this->_M_hash_code(__k);
01913       std::size_t __bkt = _M_bucket_index(__k, __code);
01914 
01915       // Look for the node before the first matching node.
01916       __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
01917       if (!__prev_n)
01918         return 0;
01919 
01920       // We found a matching node, erase it.
01921       __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
01922       _M_erase(__bkt, __prev_n, __n);
01923       return 1;
01924     }
01925 
01926   template<typename _Key, typename _Value,
01927            typename _Alloc, typename _ExtractKey, typename _Equal,
01928            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01929            typename _Traits>
01930     auto
01931     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01932                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01933     _M_erase(std::false_type, const key_type& __k)
01934     -> size_type
01935     {
01936       __hash_code __code = this->_M_hash_code(__k);
01937       std::size_t __bkt = _M_bucket_index(__k, __code);
01938 
01939       // Look for the node before the first matching node.
01940       __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
01941       if (!__prev_n)
01942         return 0;
01943 
01944       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01945       // 526. Is it undefined if a function in the standard changes
01946       // in parameters?
01947       // We use one loop to find all matching nodes and another to deallocate
01948       // them so that the key stays valid during the first loop. It might be
01949       // invalidated indirectly when destroying nodes.
01950       __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
01951       __node_type* __n_last = __n;
01952       std::size_t __n_last_bkt = __bkt;
01953       do
01954         {
01955           __n_last = __n_last->_M_next();
01956           if (!__n_last)
01957             break;
01958           __n_last_bkt = _M_bucket_index(__n_last);
01959         }
01960       while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
01961 
01962       // Deallocate nodes.
01963       size_type __result = 0;
01964       do
01965         {
01966           __node_type* __p = __n->_M_next();
01967           this->_M_deallocate_node(__n);
01968           __n = __p;
01969           ++__result;
01970           --_M_element_count;
01971         }
01972       while (__n != __n_last);
01973 
01974       if (__prev_n == _M_buckets[__bkt])
01975         _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
01976       else if (__n_last && __n_last_bkt != __bkt)
01977         _M_buckets[__n_last_bkt] = __prev_n;
01978       __prev_n->_M_nxt = __n_last;
01979       return __result;
01980     }
01981 
01982   template<typename _Key, typename _Value,
01983            typename _Alloc, typename _ExtractKey, typename _Equal,
01984            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
01985            typename _Traits>
01986     auto
01987     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
01988                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
01989     erase(const_iterator __first, const_iterator __last)
01990     -> iterator
01991     {
01992       __node_type* __n = __first._M_cur;
01993       __node_type* __last_n = __last._M_cur;
01994       if (__n == __last_n)
01995         return iterator(__n);
01996 
01997       std::size_t __bkt = _M_bucket_index(__n);
01998 
01999       __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
02000       bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
02001       std::size_t __n_bkt = __bkt;
02002       for (;;)
02003         {
02004           do
02005             {
02006               __node_type* __tmp = __n;
02007               __n = __n->_M_next();
02008               this->_M_deallocate_node(__tmp);
02009               --_M_element_count;
02010               if (!__n)
02011                 break;
02012               __n_bkt = _M_bucket_index(__n);
02013             }
02014           while (__n != __last_n && __n_bkt == __bkt);
02015           if (__is_bucket_begin)
02016             _M_remove_bucket_begin(__bkt, __n, __n_bkt);
02017           if (__n == __last_n)
02018             break;
02019           __is_bucket_begin = true;
02020           __bkt = __n_bkt;
02021         }
02022 
02023       if (__n && (__n_bkt != __bkt || __is_bucket_begin))
02024         _M_buckets[__n_bkt] = __prev_n;
02025       __prev_n->_M_nxt = __n;
02026       return iterator(__n);
02027     }
02028 
02029   template<typename _Key, typename _Value,
02030            typename _Alloc, typename _ExtractKey, typename _Equal,
02031            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
02032            typename _Traits>
02033     void
02034     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
02035                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
02036     clear() noexcept
02037     {
02038       this->_M_deallocate_nodes(_M_begin());
02039       __builtin_memset(_M_buckets, 0, _M_bucket_count * sizeof(__bucket_type));
02040       _M_element_count = 0;
02041       _M_before_begin._M_nxt = nullptr;
02042     }
02043 
02044   template<typename _Key, typename _Value,
02045            typename _Alloc, typename _ExtractKey, typename _Equal,
02046            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
02047            typename _Traits>
02048     void
02049     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
02050                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
02051     rehash(size_type __n)
02052     {
02053       const __rehash_state& __saved_state = _M_rehash_policy._M_state();
02054       std::size_t __buckets
02055         = std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
02056                    __n);
02057       __buckets = _M_rehash_policy._M_next_bkt(__buckets);
02058 
02059       if (__buckets != _M_bucket_count)
02060         _M_rehash(__buckets, __saved_state);
02061       else
02062         // No rehash, restore previous state to keep a consistent state.
02063         _M_rehash_policy._M_reset(__saved_state);
02064     }
02065 
02066   template<typename _Key, typename _Value,
02067            typename _Alloc, typename _ExtractKey, typename _Equal,
02068            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
02069            typename _Traits>
02070     void
02071     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
02072                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
02073     _M_rehash(size_type __n, const __rehash_state& __state)
02074     {
02075       __try
02076         {
02077           _M_rehash_aux(__n, __unique_keys());
02078         }
02079       __catch(...)
02080         {
02081           // A failure here means that buckets allocation failed.  We only
02082           // have to restore hash policy previous state.
02083           _M_rehash_policy._M_reset(__state);
02084           __throw_exception_again;
02085         }
02086     }
02087 
02088   // Rehash when there is no equivalent elements.
02089   template<typename _Key, typename _Value,
02090            typename _Alloc, typename _ExtractKey, typename _Equal,
02091            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
02092            typename _Traits>
02093     void
02094     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
02095                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
02096     _M_rehash_aux(size_type __n, std::true_type)
02097     {
02098       __bucket_type* __new_buckets = _M_allocate_buckets(__n);
02099       __node_type* __p = _M_begin();
02100       _M_before_begin._M_nxt = nullptr;
02101       std::size_t __bbegin_bkt = 0;
02102       while (__p)
02103         {
02104           __node_type* __next = __p->_M_next();
02105           std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
02106           if (!__new_buckets[__bkt])
02107             {
02108               __p->_M_nxt = _M_before_begin._M_nxt;
02109               _M_before_begin._M_nxt = __p;
02110               __new_buckets[__bkt] = &_M_before_begin;
02111               if (__p->_M_nxt)
02112                 __new_buckets[__bbegin_bkt] = __p;
02113               __bbegin_bkt = __bkt;
02114             }
02115           else
02116             {
02117               __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
02118               __new_buckets[__bkt]->_M_nxt = __p;
02119             }
02120           __p = __next;
02121         }
02122 
02123       _M_deallocate_buckets();
02124       _M_bucket_count = __n;
02125       _M_buckets = __new_buckets;
02126     }
02127 
02128   // Rehash when there can be equivalent elements, preserve their relative
02129   // order.
02130   template<typename _Key, typename _Value,
02131            typename _Alloc, typename _ExtractKey, typename _Equal,
02132            typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
02133            typename _Traits>
02134     void
02135     _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
02136                _H1, _H2, _Hash, _RehashPolicy, _Traits>::
02137     _M_rehash_aux(size_type __n, std::false_type)
02138     {
02139       __bucket_type* __new_buckets = _M_allocate_buckets(__n);
02140 
02141       __node_type* __p = _M_begin();
02142       _M_before_begin._M_nxt = nullptr;
02143       std::size_t __bbegin_bkt = 0;
02144       std::size_t __prev_bkt = 0;
02145       __node_type* __prev_p = nullptr;
02146       bool __check_bucket = false;
02147 
02148       while (__p)
02149         {
02150           __node_type* __next = __p->_M_next();
02151           std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
02152 
02153           if (__prev_p && __prev_bkt == __bkt)
02154             {
02155               // Previous insert was already in this bucket, we insert after
02156               // the previously inserted one to preserve equivalent elements
02157               // relative order.
02158               __p->_M_nxt = __prev_p->_M_nxt;
02159               __prev_p->_M_nxt = __p;
02160 
02161               // Inserting after a node in a bucket require to check that we
02162               // haven't change the bucket last node, in this case next
02163               // bucket containing its before begin node must be updated. We
02164               // schedule a check as soon as we move out of the sequence of
02165               // equivalent nodes to limit the number of checks.
02166               __check_bucket = true;
02167             }
02168           else
02169             {
02170               if (__check_bucket)
02171                 {
02172                   // Check if we shall update the next bucket because of
02173                   // insertions into __prev_bkt bucket.
02174                   if (__prev_p->_M_nxt)
02175                     {
02176                       std::size_t __next_bkt
02177                         = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
02178                                                             __n);
02179                       if (__next_bkt != __prev_bkt)
02180                         __new_buckets[__next_bkt] = __prev_p;
02181                     }
02182                   __check_bucket = false;
02183                 }
02184 
02185               if (!__new_buckets[__bkt])
02186                 {
02187                   __p->_M_nxt = _M_before_begin._M_nxt;
02188                   _M_before_begin._M_nxt = __p;
02189                   __new_buckets[__bkt] = &_M_before_begin;
02190                   if (__p->_M_nxt)
02191                     __new_buckets[__bbegin_bkt] = __p;
02192                   __bbegin_bkt = __bkt;
02193                 }
02194               else
02195                 {
02196                   __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
02197                   __new_buckets[__bkt]->_M_nxt = __p;
02198                 }
02199             }
02200           __prev_p = __p;
02201           __prev_bkt = __bkt;
02202           __p = __next;
02203         }
02204 
02205       if (__check_bucket && __prev_p->_M_nxt)
02206         {
02207           std::size_t __next_bkt
02208             = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
02209           if (__next_bkt != __prev_bkt)
02210             __new_buckets[__next_bkt] = __prev_p;
02211         }
02212 
02213       _M_deallocate_buckets();
02214       _M_bucket_count = __n;
02215       _M_buckets = __new_buckets;
02216     }
02217 
02218 #if __cplusplus > 201402L
02219   template<typename, typename, typename> class _Hash_merge_helper { };
02220 #endif // C++17
02221 
02222 _GLIBCXX_END_NAMESPACE_VERSION
02223 } // namespace std
02224 
02225 #endif // _HASHTABLE_H