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