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