libstdc++
hashtable_policy.h
Go to the documentation of this file.
00001 // Internal policy header for unordered_set and unordered_map -*- C++ -*-
00002 
00003 // Copyright (C) 2010, 2011, 2012 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_policy.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly.
00028  *  @headername{unordered_map,unordered_set}
00029  */
00030 
00031 #ifndef _HASHTABLE_POLICY_H
00032 #define _HASHTABLE_POLICY_H 1
00033 
00034 namespace std _GLIBCXX_VISIBILITY(default)
00035 {
00036 namespace __detail
00037 {
00038 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00039 
00040   // Helper function: return distance(first, last) for forward
00041   // iterators, or 0 for input iterators.
00042   template<class _Iterator>
00043     inline typename std::iterator_traits<_Iterator>::difference_type
00044     __distance_fw(_Iterator __first, _Iterator __last,
00045           std::input_iterator_tag)
00046     { return 0; }
00047 
00048   template<class _Iterator>
00049     inline typename std::iterator_traits<_Iterator>::difference_type
00050     __distance_fw(_Iterator __first, _Iterator __last,
00051           std::forward_iterator_tag)
00052     { return std::distance(__first, __last); }
00053 
00054   template<class _Iterator>
00055     inline typename std::iterator_traits<_Iterator>::difference_type
00056     __distance_fw(_Iterator __first, _Iterator __last)
00057     {
00058       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
00059       return __distance_fw(__first, __last, _Tag());
00060     }
00061 
00062   // Helper type used to detect when the hash functor is noexcept qualified or
00063   // not
00064   template <typename _Key, typename _Hash>
00065     struct __is_noexcept_hash : std::integral_constant<bool,
00066     noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
00067     {};
00068 
00069   // Auxiliary types used for all instantiations of _Hashtable: nodes
00070   // and iterators.
00071 
00072   // Nodes, used to wrap elements stored in the hash table.  A policy
00073   // template parameter of class template _Hashtable controls whether
00074   // nodes also store a hash code. In some cases (e.g. strings) this
00075   // may be a performance win.
00076   struct _Hash_node_base
00077   {
00078     _Hash_node_base* _M_nxt;
00079 
00080     _Hash_node_base()
00081       : _M_nxt() { }
00082     _Hash_node_base(_Hash_node_base* __next)
00083       : _M_nxt(__next) { }
00084   };
00085 
00086   template<typename _Value, bool __cache_hash_code>
00087     struct _Hash_node;
00088 
00089   template<typename _Value>
00090     struct _Hash_node<_Value, true> : _Hash_node_base
00091     {
00092       _Value       _M_v;
00093       std::size_t  _M_hash_code;
00094 
00095       template<typename... _Args>
00096     _Hash_node(_Args&&... __args)
00097     : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
00098 
00099       _Hash_node* _M_next() const
00100       { return static_cast<_Hash_node*>(_M_nxt); }
00101     };
00102 
00103   template<typename _Value>
00104     struct _Hash_node<_Value, false> : _Hash_node_base
00105     {
00106       _Value       _M_v;
00107 
00108       template<typename... _Args>
00109     _Hash_node(_Args&&... __args)
00110     : _M_v(std::forward<_Args>(__args)...) { }
00111 
00112       _Hash_node* _M_next() const
00113       { return static_cast<_Hash_node*>(_M_nxt); }
00114     };
00115 
00116   // Node iterators, used to iterate through all the hashtable.
00117   template<typename _Value, bool __cache>
00118     struct _Node_iterator_base
00119     {
00120       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
00121       : _M_cur(__p) { }
00122 
00123       void
00124       _M_incr()
00125       { _M_cur = _M_cur->_M_next(); }
00126 
00127       _Hash_node<_Value, __cache>*  _M_cur;
00128     };
00129 
00130   template<typename _Value, bool __cache>
00131     inline bool
00132     operator==(const _Node_iterator_base<_Value, __cache>& __x,
00133            const _Node_iterator_base<_Value, __cache>& __y)
00134     { return __x._M_cur == __y._M_cur; }
00135 
00136   template<typename _Value, bool __cache>
00137     inline bool
00138     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
00139            const _Node_iterator_base<_Value, __cache>& __y)
00140     { return __x._M_cur != __y._M_cur; }
00141 
00142   template<typename _Value, bool __constant_iterators, bool __cache>
00143     struct _Node_iterator
00144     : public _Node_iterator_base<_Value, __cache>
00145     {
00146       typedef _Value                                   value_type;
00147       typedef typename std::conditional<__constant_iterators,
00148                     const _Value*, _Value*>::type
00149                                pointer;
00150       typedef typename std::conditional<__constant_iterators,
00151                     const _Value&, _Value&>::type
00152                                reference;
00153       typedef std::ptrdiff_t                           difference_type;
00154       typedef std::forward_iterator_tag                iterator_category;
00155 
00156       _Node_iterator()
00157       : _Node_iterator_base<_Value, __cache>(0) { }
00158 
00159       explicit
00160       _Node_iterator(_Hash_node<_Value, __cache>* __p)
00161       : _Node_iterator_base<_Value, __cache>(__p) { }
00162 
00163       reference
00164       operator*() const
00165       { return this->_M_cur->_M_v; }
00166 
00167       pointer
00168       operator->() const
00169       { return std::__addressof(this->_M_cur->_M_v); }
00170 
00171       _Node_iterator&
00172       operator++()
00173       {
00174     this->_M_incr();
00175     return *this;
00176       }
00177 
00178       _Node_iterator
00179       operator++(int)
00180       {
00181     _Node_iterator __tmp(*this);
00182     this->_M_incr();
00183     return __tmp;
00184       }
00185     };
00186 
00187   template<typename _Value, bool __constant_iterators, bool __cache>
00188     struct _Node_const_iterator
00189     : public _Node_iterator_base<_Value, __cache>
00190     {
00191       typedef _Value                                   value_type;
00192       typedef const _Value*                            pointer;
00193       typedef const _Value&                            reference;
00194       typedef std::ptrdiff_t                           difference_type;
00195       typedef std::forward_iterator_tag                iterator_category;
00196 
00197       _Node_const_iterator()
00198       : _Node_iterator_base<_Value, __cache>(0) { }
00199 
00200       explicit
00201       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
00202       : _Node_iterator_base<_Value, __cache>(__p) { }
00203 
00204       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00205                __cache>& __x)
00206       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
00207 
00208       reference
00209       operator*() const
00210       { return this->_M_cur->_M_v; }
00211 
00212       pointer
00213       operator->() const
00214       { return std::__addressof(this->_M_cur->_M_v); }
00215 
00216       _Node_const_iterator&
00217       operator++()
00218       {
00219     this->_M_incr();
00220     return *this;
00221       }
00222 
00223       _Node_const_iterator
00224       operator++(int)
00225       {
00226     _Node_const_iterator __tmp(*this);
00227     this->_M_incr();
00228     return __tmp;
00229       }
00230     };
00231 
00232   // Many of class template _Hashtable's template parameters are policy
00233   // classes.  These are defaults for the policies.
00234 
00235   // Default range hashing function: use division to fold a large number
00236   // into the range [0, N).
00237   struct _Mod_range_hashing
00238   {
00239     typedef std::size_t first_argument_type;
00240     typedef std::size_t second_argument_type;
00241     typedef std::size_t result_type;
00242 
00243     result_type
00244     operator()(first_argument_type __num, second_argument_type __den) const
00245     { return __num % __den; }
00246   };
00247 
00248   // Default ranged hash function H.  In principle it should be a
00249   // function object composed from objects of type H1 and H2 such that
00250   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
00251   // h1 and h2.  So instead we'll just use a tag to tell class template
00252   // hashtable to do that composition.
00253   struct _Default_ranged_hash { };
00254 
00255   // Default value for rehash policy.  Bucket size is (usually) the
00256   // smallest prime that keeps the load factor small enough.
00257   struct _Prime_rehash_policy
00258   {
00259     _Prime_rehash_policy(float __z = 1.0)
00260     : _M_max_load_factor(__z), _M_prev_resize(0), _M_next_resize(0) { }
00261 
00262     float
00263     max_load_factor() const noexcept
00264     { return _M_max_load_factor; }
00265 
00266     // Return a bucket size no smaller than n.
00267     std::size_t
00268     _M_next_bkt(std::size_t __n) const;
00269 
00270     // Return a bucket count appropriate for n elements
00271     std::size_t
00272     _M_bkt_for_elements(std::size_t __n) const;
00273 
00274     // __n_bkt is current bucket count, __n_elt is current element count,
00275     // and __n_ins is number of elements to be inserted.  Do we need to
00276     // increase bucket count?  If so, return make_pair(true, n), where n
00277     // is the new bucket count.  If not, return make_pair(false, 0).
00278     std::pair<bool, std::size_t>
00279     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00280            std::size_t __n_ins) const;
00281 
00282     typedef std::pair<std::size_t, std::size_t> _State;
00283 
00284     _State
00285     _M_state() const
00286     { return std::make_pair(_M_prev_resize, _M_next_resize); }
00287 
00288     void
00289     _M_reset(const _State& __state)
00290     {
00291       _M_prev_resize = __state.first;
00292       _M_next_resize = __state.second;
00293     }
00294 
00295     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
00296 
00297     static const std::size_t _S_growth_factor = 2;
00298 
00299     float                _M_max_load_factor;
00300     mutable std::size_t  _M_prev_resize;
00301     mutable std::size_t  _M_next_resize;
00302   };
00303 
00304   extern const unsigned long __prime_list[];
00305 
00306   // XXX This is a hack.  There's no good reason for any of
00307   // _Prime_rehash_policy's member functions to be inline.
00308 
00309   // Return a prime no smaller than n.
00310   inline std::size_t
00311   _Prime_rehash_policy::
00312   _M_next_bkt(std::size_t __n) const
00313   {
00314     // Optimize lookups involving the first elements of __prime_list.
00315     // (useful to speed-up, eg, constructors)
00316     static const unsigned char __fast_bkt[12]
00317       = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
00318 
00319     const std::size_t __grown_n = __n * _S_growth_factor;
00320     if (__grown_n <= 11)
00321       {
00322     _M_prev_resize = 0;
00323     _M_next_resize
00324       = __builtin_ceil(__fast_bkt[__grown_n]
00325                * (long double)_M_max_load_factor);
00326     return __fast_bkt[__grown_n];
00327       }
00328 
00329     const unsigned long* __next_bkt
00330       = std::lower_bound(__prime_list + 5, __prime_list + _S_n_primes,
00331              __grown_n);
00332     const unsigned long* __prev_bkt
00333       = std::lower_bound(__prime_list + 1, __next_bkt, __n / _S_growth_factor);
00334 
00335     _M_prev_resize
00336       = __builtin_floor(*(__prev_bkt - 1) * (long double)_M_max_load_factor);
00337     _M_next_resize
00338       = __builtin_ceil(*__next_bkt * (long double)_M_max_load_factor);
00339     return *__next_bkt;
00340   }
00341 
00342   // Return the smallest prime p such that alpha p >= n, where alpha
00343   // is the load factor.
00344   inline std::size_t
00345   _Prime_rehash_policy::
00346   _M_bkt_for_elements(std::size_t __n) const
00347   { return _M_next_bkt(__builtin_ceil(__n / (long double)_M_max_load_factor)); }
00348 
00349   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
00350   // If p > __n_bkt, return make_pair(true, p); otherwise return
00351   // make_pair(false, 0).  In principle this isn't very different from
00352   // _M_bkt_for_elements.
00353 
00354   // The only tricky part is that we're caching the element count at
00355   // which we need to rehash, so we don't have to do a floating-point
00356   // multiply for every insertion.
00357 
00358   inline std::pair<bool, std::size_t>
00359   _Prime_rehash_policy::
00360   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00361          std::size_t __n_ins) const
00362   {
00363     if (__n_elt + __n_ins >= _M_next_resize)
00364       {
00365     long double __min_bkts = (__n_elt + __n_ins)
00366                  / (long double)_M_max_load_factor;
00367     if (__min_bkts >= __n_bkt)
00368       return std::make_pair(true,
00369                 _M_next_bkt(__builtin_floor(__min_bkts) + 1));
00370     else
00371       {
00372         _M_next_resize
00373           = __builtin_floor(__n_bkt * (long double)_M_max_load_factor);
00374         return std::make_pair(false, 0);
00375       }
00376       }
00377     else if (__n_elt + __n_ins < _M_prev_resize)
00378       {
00379     long double __min_bkts = (__n_elt + __n_ins)
00380                  / (long double)_M_max_load_factor;
00381     return std::make_pair(true,
00382                   _M_next_bkt(__builtin_floor(__min_bkts) + 1));
00383       }
00384     else
00385       return std::make_pair(false, 0);
00386   }
00387 
00388   // Base classes for std::_Hashtable.  We define these base classes
00389   // because in some cases we want to do different things depending
00390   // on the value of a policy class.  In some cases the policy class
00391   // affects which member functions and nested typedefs are defined;
00392   // we handle that by specializing base class templates.  Several of
00393   // the base class templates need to access other members of class
00394   // template _Hashtable, so we use the "curiously recurring template
00395   // pattern" for them.
00396 
00397   // class template _Map_base.  If the hashtable has a value type of
00398   // the form pair<T1, T2> and a key extraction policy that returns the
00399   // first part of the pair, the hashtable gets a mapped_type typedef.
00400   // If it satisfies those criteria and also has unique keys, then it
00401   // also gets an operator[].
00402   template<typename _Key, typename _Value, typename _Ex, bool __unique,
00403        typename _Hashtable>
00404     struct _Map_base { };
00405 
00406   template<typename _Key, typename _Pair, typename _Hashtable>
00407     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
00408     {
00409       typedef typename _Pair::second_type mapped_type;
00410     };
00411 
00412   template<typename _Key, typename _Pair, typename _Hashtable>
00413     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
00414     {
00415       typedef typename _Pair::second_type mapped_type;
00416 
00417       mapped_type&
00418       operator[](const _Key& __k);
00419 
00420       mapped_type&
00421       operator[](_Key&& __k);
00422 
00423       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00424       // DR 761. unordered_map needs an at() member function.
00425       mapped_type&
00426       at(const _Key& __k);
00427 
00428       const mapped_type&
00429       at(const _Key& __k) const;
00430     };
00431 
00432   template<typename _Key, typename _Pair, typename _Hashtable>
00433     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00434                true, _Hashtable>::mapped_type&
00435     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00436     operator[](const _Key& __k)
00437     {
00438       _Hashtable* __h = static_cast<_Hashtable*>(this);
00439       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00440       std::size_t __n = __h->_M_bucket_index(__k, __code);
00441 
00442       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
00443       if (!__p)
00444     return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
00445                      __n, __code)->second;
00446       return (__p->_M_v).second;
00447     }
00448 
00449   template<typename _Key, typename _Pair, typename _Hashtable>
00450     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00451                true, _Hashtable>::mapped_type&
00452     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00453     operator[](_Key&& __k)
00454     {
00455       _Hashtable* __h = static_cast<_Hashtable*>(this);
00456       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00457       std::size_t __n = __h->_M_bucket_index(__k, __code);
00458 
00459       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
00460       if (!__p)
00461     return __h->_M_insert_bucket(std::make_pair(std::move(__k),
00462                             mapped_type()),
00463                      __n, __code)->second;
00464       return (__p->_M_v).second;
00465     }
00466 
00467   template<typename _Key, typename _Pair, typename _Hashtable>
00468     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00469                true, _Hashtable>::mapped_type&
00470     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00471     at(const _Key& __k)
00472     {
00473       _Hashtable* __h = static_cast<_Hashtable*>(this);
00474       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00475       std::size_t __n = __h->_M_bucket_index(__k, __code);
00476 
00477       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
00478       if (!__p)
00479     __throw_out_of_range(__N("_Map_base::at"));
00480       return (__p->_M_v).second;
00481     }
00482 
00483   template<typename _Key, typename _Pair, typename _Hashtable>
00484     const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00485                  true, _Hashtable>::mapped_type&
00486     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00487     at(const _Key& __k) const
00488     {
00489       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
00490       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00491       std::size_t __n = __h->_M_bucket_index(__k, __code);
00492 
00493       typename _Hashtable::_Node* __p = __h->_M_find_node(__n, __k, __code);
00494       if (!__p)
00495     __throw_out_of_range(__N("_Map_base::at"));
00496       return (__p->_M_v).second;
00497     }
00498 
00499   // class template _Rehash_base.  Give hashtable the max_load_factor
00500   // functions and reserve iff the rehash policy is _Prime_rehash_policy.
00501   template<typename _RehashPolicy, typename _Hashtable>
00502     struct _Rehash_base { };
00503 
00504   template<typename _Hashtable>
00505     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
00506     {
00507       float
00508       max_load_factor() const noexcept
00509       {
00510     const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00511     return __this->__rehash_policy().max_load_factor();
00512       }
00513 
00514       void
00515       max_load_factor(float __z)
00516       {
00517     _Hashtable* __this = static_cast<_Hashtable*>(this);
00518     __this->__rehash_policy(_Prime_rehash_policy(__z));
00519       }
00520 
00521       void
00522       reserve(std::size_t __n)
00523       {
00524     _Hashtable* __this = static_cast<_Hashtable*>(this);
00525     __this->rehash(__builtin_ceil(__n / max_load_factor()));
00526       }
00527     };
00528 
00529   // Helper class using EBO when it is not forbidden, type is not final,
00530   // and when it worth it, type is empty.
00531   template<int _Nm, typename _Tp,
00532        bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
00533     struct _Hashtable_ebo_helper;
00534 
00535   // Specialization using EBO.
00536   template<int _Nm, typename _Tp>
00537     struct _Hashtable_ebo_helper<_Nm, _Tp, true>
00538     // See PR53067.
00539     : public _Tp
00540     {
00541       _Hashtable_ebo_helper() = default;
00542       _Hashtable_ebo_helper(const _Tp& __tp) : _Tp(__tp)
00543       { }
00544 
00545       static const _Tp&
00546       _S_cget(const _Hashtable_ebo_helper& __eboh)
00547       { return static_cast<const _Tp&>(__eboh); }
00548 
00549       static _Tp&
00550       _S_get(_Hashtable_ebo_helper& __eboh)
00551       { return static_cast<_Tp&>(__eboh); }
00552     };
00553 
00554   // Specialization not using EBO.
00555   template<int _Nm, typename _Tp>
00556     struct _Hashtable_ebo_helper<_Nm, _Tp, false>
00557     {
00558       _Hashtable_ebo_helper() = default;
00559       _Hashtable_ebo_helper(const _Tp& __tp) : _M_tp(__tp)
00560       { }
00561 
00562       static const _Tp&
00563       _S_cget(const _Hashtable_ebo_helper& __eboh)
00564       { return __eboh._M_tp; }
00565 
00566       static _Tp&
00567       _S_get(_Hashtable_ebo_helper& __eboh)
00568       { return __eboh._M_tp; }
00569 
00570     private:
00571       _Tp _M_tp;
00572     };
00573 
00574   // Class template _Hash_code_base.  Encapsulates two policy issues that
00575   // aren't quite orthogonal.
00576   //   (1) the difference between using a ranged hash function and using
00577   //       the combination of a hash function and a range-hashing function.
00578   //       In the former case we don't have such things as hash codes, so
00579   //       we have a dummy type as placeholder.
00580   //   (2) Whether or not we cache hash codes.  Caching hash codes is
00581   //       meaningless if we have a ranged hash function.
00582   // We also put the key extraction objects here, for convenience.
00583   //
00584   // Each specialization derives from one or more of the template parameters to
00585   // benefit from Ebo. This is important as this type is inherited in some cases
00586   // by the _Local_iterator_base type used to implement local_iterator and
00587   // const_local_iterator. As with any iterator type we prefer to make it as
00588   // small as possible.
00589 
00590   // Primary template: unused except as a hook for specializations.
00591   template<typename _Key, typename _Value, typename _ExtractKey,
00592        typename _H1, typename _H2, typename _Hash,
00593        bool __cache_hash_code>
00594     struct _Hash_code_base;
00595 
00596   // Specialization: ranged hash function, no caching hash codes.  H1
00597   // and H2 are provided but ignored.  We define a dummy hash code type.
00598   template<typename _Key, typename _Value, typename _ExtractKey, 
00599        typename _H1, typename _H2, typename _Hash>
00600     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>
00601     // See PR53067.
00602     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
00603       public  _Hashtable_ebo_helper<1, _Hash>
00604     {
00605     private:
00606       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
00607       typedef _Hashtable_ebo_helper<1, _Hash> _EboHash;
00608 
00609     protected:
00610       // We need the default constructor for the local iterators.
00611       _Hash_code_base() = default;
00612       _Hash_code_base(const _ExtractKey& __ex,
00613               const _H1&, const _H2&, const _Hash& __h)
00614     : _EboExtractKey(__ex), _EboHash(__h) { }
00615 
00616       typedef void* _Hash_code_type;
00617 
00618       _Hash_code_type
00619       _M_hash_code(const _Key& __key) const
00620       { return 0; }
00621 
00622       std::size_t
00623       _M_bucket_index(const _Key& __k, _Hash_code_type,
00624               std::size_t __n) const
00625       { return _M_ranged_hash()(__k, __n); }
00626 
00627       std::size_t
00628       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00629               std::size_t __n) const
00630       { return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
00631 
00632       void
00633       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00634       { }
00635 
00636       void
00637       _M_copy_code(_Hash_node<_Value, false>*,
00638            const _Hash_node<_Value, false>*) const
00639       { }
00640 
00641       void
00642       _M_swap(_Hash_code_base& __x)
00643       {
00644     std::swap(_M_extract(), __x._M_extract());
00645     std::swap(_M_ranged_hash(), __x._M_ranged_hash());
00646       }
00647 
00648     protected:
00649       const _ExtractKey&
00650       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
00651       _ExtractKey&
00652       _M_extract() { return _EboExtractKey::_S_get(*this); }
00653       const _Hash&
00654       _M_ranged_hash() const { return _EboHash::_S_cget(*this); }
00655       _Hash&
00656       _M_ranged_hash() { return _EboHash::_S_get(*this); }
00657     };
00658 
00659   // No specialization for ranged hash function while caching hash codes.
00660   // That combination is meaningless, and trying to do it is an error.
00661 
00662   // Specialization: ranged hash function, cache hash codes.  This
00663   // combination is meaningless, so we provide only a declaration
00664   // and no definition.
00665   template<typename _Key, typename _Value, typename _ExtractKey,
00666        typename _H1, typename _H2, typename _Hash>
00667     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
00668 
00669   // Specialization: hash function and range-hashing function, no
00670   // caching of hash codes.
00671   // Provides typedef and accessor required by TR1.
00672   template<typename _Key, typename _Value, typename _ExtractKey,
00673        typename _H1, typename _H2>
00674     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
00675                _Default_ranged_hash, false>
00676     // See PR53067.
00677     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
00678       public  _Hashtable_ebo_helper<1, _H1>,
00679       public  _Hashtable_ebo_helper<2, _H2>
00680     {
00681     private:
00682       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
00683       typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
00684       typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
00685 
00686     public:
00687       typedef _H1 hasher;
00688 
00689       hasher
00690       hash_function() const
00691       { return _M_h1(); }
00692 
00693     protected:
00694       // We need the default constructor for the local iterators.
00695       _Hash_code_base() = default;
00696       _Hash_code_base(const _ExtractKey& __ex,
00697               const _H1& __h1, const _H2& __h2,
00698               const _Default_ranged_hash&)
00699       : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
00700 
00701       typedef std::size_t _Hash_code_type;
00702 
00703       _Hash_code_type
00704       _M_hash_code(const _Key& __k) const
00705       { return _M_h1()(__k); }
00706 
00707       std::size_t
00708       _M_bucket_index(const _Key&, _Hash_code_type __c,
00709               std::size_t __n) const
00710       { return _M_h2()(__c, __n); }
00711 
00712       std::size_t
00713       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00714               std::size_t __n) const
00715       { return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
00716 
00717       void
00718       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00719       { }
00720 
00721       void
00722       _M_copy_code(_Hash_node<_Value, false>*,
00723            const _Hash_node<_Value, false>*) const
00724       { }
00725 
00726       void
00727       _M_swap(_Hash_code_base& __x)
00728       {
00729     std::swap(_M_extract(), __x._M_extract());
00730     std::swap(_M_h1(), __x._M_h1());
00731     std::swap(_M_h2(), __x._M_h2());
00732       }
00733 
00734     protected:
00735       const _ExtractKey&
00736       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
00737       _ExtractKey&
00738       _M_extract() { return _EboExtractKey::_S_get(*this); }
00739       const _H1&
00740       _M_h1() const { return _EboH1::_S_cget(*this); }
00741       _H1&
00742       _M_h1() { return _EboH1::_S_get(*this); }
00743       const _H2&
00744       _M_h2() const { return _EboH2::_S_cget(*this); }
00745       _H2&
00746       _M_h2() { return _EboH2::_S_get(*this); }
00747     };
00748 
00749   // Specialization: hash function and range-hashing function,
00750   // caching hash codes.  H is provided but ignored.  Provides
00751   // typedef and accessor required by TR1.
00752   template<typename _Key, typename _Value, typename _ExtractKey,
00753        typename _H1, typename _H2>
00754     struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2,
00755                _Default_ranged_hash, true>
00756     // See PR53067.
00757     : public  _Hashtable_ebo_helper<0, _ExtractKey>,
00758       public  _Hashtable_ebo_helper<1, _H1>,
00759       public  _Hashtable_ebo_helper<2, _H2>
00760     {
00761     private:
00762       typedef _Hashtable_ebo_helper<0, _ExtractKey> _EboExtractKey;
00763       typedef _Hashtable_ebo_helper<1, _H1> _EboH1;
00764       typedef _Hashtable_ebo_helper<2, _H2> _EboH2;
00765 
00766     public:
00767       typedef _H1 hasher;
00768 
00769       hasher
00770       hash_function() const
00771       { return _M_h1(); }
00772 
00773     protected:
00774       _Hash_code_base(const _ExtractKey& __ex,
00775               const _H1& __h1, const _H2& __h2,
00776               const _Default_ranged_hash&)
00777       : _EboExtractKey(__ex), _EboH1(__h1), _EboH2(__h2) { }
00778 
00779       typedef std::size_t _Hash_code_type;
00780 
00781       _Hash_code_type
00782       _M_hash_code(const _Key& __k) const
00783       { return _M_h1()(__k); }
00784 
00785       std::size_t
00786       _M_bucket_index(const _Key&, _Hash_code_type __c,
00787               std::size_t __n) const
00788       { return _M_h2()(__c, __n); }
00789 
00790       std::size_t
00791       _M_bucket_index(const _Hash_node<_Value, true>* __p,
00792               std::size_t __n) const
00793       { return _M_h2()(__p->_M_hash_code, __n); }
00794 
00795       void
00796       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
00797       { __n->_M_hash_code = __c; }
00798 
00799       void
00800       _M_copy_code(_Hash_node<_Value, true>* __to,
00801            const _Hash_node<_Value, true>* __from) const
00802       { __to->_M_hash_code = __from->_M_hash_code; }
00803 
00804       void
00805       _M_swap(_Hash_code_base& __x)
00806       {
00807     std::swap(_M_extract(), __x._M_extract());
00808     std::swap(_M_h1(), __x._M_h1());
00809     std::swap(_M_h2(), __x._M_h2());
00810       }
00811 
00812     protected:
00813       const _ExtractKey&
00814       _M_extract() const { return _EboExtractKey::_S_cget(*this); }
00815       _ExtractKey&
00816       _M_extract() { return _EboExtractKey::_S_get(*this); }
00817       const _H1&
00818       _M_h1() const { return _EboH1::_S_cget(*this); }
00819       _H1&
00820       _M_h1() { return _EboH1::_S_get(*this); }
00821       const _H2&
00822       _M_h2() const { return _EboH2::_S_cget(*this); }
00823       _H2&
00824       _M_h2() { return _EboH2::_S_get(*this); }
00825     };
00826 
00827   template <typename _Key, typename _Value, typename _ExtractKey,
00828         typename _Equal, typename _HashCodeType,
00829         bool __cache_hash_code>
00830   struct _Equal_helper;
00831 
00832   template<typename _Key, typename _Value, typename _ExtractKey,
00833        typename _Equal, typename _HashCodeType>
00834   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, true>
00835   {
00836     static bool
00837     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
00838           const _Key& __k, _HashCodeType __c,
00839           _Hash_node<_Value, true>* __n)
00840     { return __c == __n->_M_hash_code
00841          && __eq(__k, __extract(__n->_M_v)); }
00842   };
00843 
00844   template<typename _Key, typename _Value, typename _ExtractKey,
00845        typename _Equal, typename _HashCodeType>
00846   struct _Equal_helper<_Key, _Value, _ExtractKey, _Equal, _HashCodeType, false>
00847   {
00848     static bool
00849     _S_equals(const _Equal& __eq, const _ExtractKey& __extract,
00850           const _Key& __k, _HashCodeType,
00851           _Hash_node<_Value, false>* __n)
00852     { return __eq(__k, __extract(__n->_M_v)); }
00853   };
00854 
00855   // Helper class adding management of _Equal functor to _Hash_code_base
00856   // type.
00857   template<typename _Key, typename _Value,
00858        typename _ExtractKey, typename _Equal,
00859        typename _H1, typename _H2, typename _Hash,
00860        bool __cache_hash_code>
00861   struct _Hashtable_base
00862   // See PR53067.
00863   : public  _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
00864                 __cache_hash_code>,
00865     public _Hashtable_ebo_helper<0, _Equal>
00866   {
00867   private:
00868     typedef _Hashtable_ebo_helper<0, _Equal> _EboEqual;
00869 
00870   protected:
00871     typedef _Hash_code_base<_Key, _Value, _ExtractKey,
00872                 _H1, _H2, _Hash, __cache_hash_code> _HCBase;
00873     typedef typename _HCBase::_Hash_code_type _Hash_code_type;
00874 
00875     _Hashtable_base(const _ExtractKey& __ex,
00876             const _H1& __h1, const _H2& __h2,
00877             const _Hash& __hash, const _Equal& __eq)
00878       : _HCBase(__ex, __h1, __h2, __hash), _EboEqual(__eq) { }
00879 
00880     bool
00881     _M_equals(const _Key& __k, _Hash_code_type __c,
00882           _Hash_node<_Value, __cache_hash_code>* __n) const
00883     {
00884       typedef _Equal_helper<_Key, _Value, _ExtractKey,
00885                _Equal, _Hash_code_type,
00886                __cache_hash_code> _EqualHelper;
00887       return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
00888                      __k, __c, __n);
00889     }
00890 
00891     void
00892     _M_swap(_Hashtable_base& __x)
00893     {
00894       _HCBase::_M_swap(__x);
00895       std::swap(_M_eq(), __x._M_eq());
00896     }
00897 
00898   protected:
00899     const _Equal&
00900     _M_eq() const { return _EboEqual::_S_cget(*this); }
00901     _Equal&
00902     _M_eq() { return _EboEqual::_S_get(*this); }
00903   };
00904 
00905   // Local iterators, used to iterate within a bucket but not between
00906   // buckets.
00907   template<typename _Key, typename _Value, typename _ExtractKey,
00908        typename _H1, typename _H2, typename _Hash,
00909        bool __cache_hash_code>
00910     struct _Local_iterator_base;
00911 
00912   template<typename _Key, typename _Value, typename _ExtractKey,
00913        typename _H1, typename _H2, typename _Hash>
00914     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
00915                 _H1, _H2, _Hash, true>
00916     // See PR53067.
00917     : public _H2
00918     {
00919       _Local_iterator_base() = default;
00920       _Local_iterator_base(_Hash_node<_Value, true>* __p,
00921                std::size_t __bkt, std::size_t __bkt_count)
00922       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
00923 
00924       void
00925       _M_incr()
00926       {
00927     _M_cur = _M_cur->_M_next();
00928     if (_M_cur)
00929       {
00930         std::size_t __bkt = _M_h2()(_M_cur->_M_hash_code, _M_bucket_count);
00931         if (__bkt != _M_bucket)
00932           _M_cur = nullptr;
00933       }
00934       }
00935 
00936       const _H2& _M_h2() const
00937       { return *this; }
00938 
00939       _Hash_node<_Value, true>*  _M_cur;
00940       std::size_t _M_bucket;
00941       std::size_t _M_bucket_count;
00942     };
00943 
00944   template<typename _Key, typename _Value, typename _ExtractKey,
00945        typename _H1, typename _H2, typename _Hash>
00946     struct _Local_iterator_base<_Key, _Value, _ExtractKey,
00947                 _H1, _H2, _Hash, false>
00948     // See PR53067.
00949     : public _Hash_code_base<_Key, _Value, _ExtractKey,
00950                  _H1, _H2, _Hash, false>
00951     {
00952       _Local_iterator_base() = default;
00953       _Local_iterator_base(_Hash_node<_Value, false>* __p,
00954                std::size_t __bkt, std::size_t __bkt_count)
00955       : _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
00956 
00957       void
00958       _M_incr()
00959       {
00960     _M_cur = _M_cur->_M_next();
00961     if (_M_cur)
00962       {
00963         std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
00964         if (__bkt != _M_bucket)
00965           _M_cur = nullptr;
00966       }
00967       }
00968 
00969       _Hash_node<_Value, false>*  _M_cur;
00970       std::size_t _M_bucket;
00971       std::size_t _M_bucket_count;
00972     };
00973 
00974   template<typename _Key, typename _Value, typename _ExtractKey,
00975        typename _H1, typename _H2, typename _Hash, bool __cache>
00976     inline bool
00977     operator==(const _Local_iterator_base<_Key, _Value, _ExtractKey,
00978                       _H1, _H2, _Hash, __cache>& __x,
00979            const _Local_iterator_base<_Key, _Value, _ExtractKey,
00980                       _H1, _H2, _Hash, __cache>& __y)
00981     { return __x._M_cur == __y._M_cur; }
00982 
00983   template<typename _Key, typename _Value, typename _ExtractKey,
00984        typename _H1, typename _H2, typename _Hash, bool __cache>
00985     inline bool
00986     operator!=(const _Local_iterator_base<_Key, _Value, _ExtractKey,
00987                       _H1, _H2, _Hash, __cache>& __x,
00988            const _Local_iterator_base<_Key, _Value, _ExtractKey,
00989                       _H1, _H2, _Hash, __cache>& __y)
00990     { return __x._M_cur != __y._M_cur; }
00991 
00992   template<typename _Key, typename _Value, typename _ExtractKey,
00993        typename _H1, typename _H2, typename _Hash,
00994        bool __constant_iterators, bool __cache>
00995     struct _Local_iterator
00996     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
00997                   _H1, _H2, _Hash, __cache>
00998     {
00999       typedef _Value                                   value_type;
01000       typedef typename std::conditional<__constant_iterators,
01001                     const _Value*, _Value*>::type
01002                                pointer;
01003       typedef typename std::conditional<__constant_iterators,
01004                     const _Value&, _Value&>::type
01005                                reference;
01006       typedef std::ptrdiff_t                           difference_type;
01007       typedef std::forward_iterator_tag                iterator_category;
01008 
01009       _Local_iterator() = default;
01010 
01011       explicit
01012       _Local_iterator(_Hash_node<_Value, __cache>* __p,
01013               std::size_t __bkt, std::size_t __bkt_count)
01014       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
01015                  __cache>(__p, __bkt, __bkt_count)
01016       { }
01017 
01018       reference
01019       operator*() const
01020       { return this->_M_cur->_M_v; }
01021 
01022       pointer
01023       operator->() const
01024       { return std::__addressof(this->_M_cur->_M_v); }
01025 
01026       _Local_iterator&
01027       operator++()
01028       {
01029     this->_M_incr();
01030     return *this;
01031       }
01032 
01033       _Local_iterator
01034       operator++(int)
01035       {
01036     _Local_iterator __tmp(*this);
01037     this->_M_incr();
01038     return __tmp;
01039       }
01040     };
01041 
01042   template<typename _Key, typename _Value, typename _ExtractKey,
01043        typename _H1, typename _H2, typename _Hash,
01044        bool __constant_iterators, bool __cache>
01045     struct _Local_const_iterator
01046     : public _Local_iterator_base<_Key, _Value, _ExtractKey,
01047                   _H1, _H2, _Hash, __cache>
01048     {
01049       typedef _Value                                   value_type;
01050       typedef const _Value*                            pointer;
01051       typedef const _Value&                            reference;
01052       typedef std::ptrdiff_t                           difference_type;
01053       typedef std::forward_iterator_tag                iterator_category;
01054 
01055       _Local_const_iterator() = default;
01056 
01057       explicit
01058       _Local_const_iterator(_Hash_node<_Value, __cache>* __p,
01059                 std::size_t __bkt, std::size_t __bkt_count)
01060       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
01061                  __cache>(__p, __bkt, __bkt_count)
01062       { }
01063 
01064       _Local_const_iterator(const _Local_iterator<_Key, _Value, _ExtractKey,
01065                           _H1, _H2, _Hash,
01066                           __constant_iterators,
01067                           __cache>& __x)
01068       : _Local_iterator_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash,
01069                  __cache>(__x._M_cur, __x._M_bucket,
01070                       __x._M_bucket_count)
01071       { }
01072 
01073       reference
01074       operator*() const
01075       { return this->_M_cur->_M_v; }
01076 
01077       pointer
01078       operator->() const
01079       { return std::__addressof(this->_M_cur->_M_v); }
01080 
01081       _Local_const_iterator&
01082       operator++()
01083       {
01084     this->_M_incr();
01085     return *this;
01086       }
01087 
01088       _Local_const_iterator
01089       operator++(int)
01090       {
01091     _Local_const_iterator __tmp(*this);
01092     this->_M_incr();
01093     return __tmp;
01094       }
01095     };
01096 
01097 
01098   // Class template _Equality_base.  This is for implementing equality
01099   // comparison for unordered containers, per N3068, by John Lakos and
01100   // Pablo Halpern.  Algorithmically, we follow closely the reference
01101   // implementations therein.
01102   template<typename _ExtractKey, bool __unique_keys,
01103        typename _Hashtable>
01104     struct _Equality_base;
01105 
01106   template<typename _ExtractKey, typename _Hashtable>
01107     struct _Equality_base<_ExtractKey, true, _Hashtable>
01108     {
01109       bool _M_equal(const _Hashtable&) const;
01110     };
01111 
01112   template<typename _ExtractKey, typename _Hashtable>
01113     bool
01114     _Equality_base<_ExtractKey, true, _Hashtable>::
01115     _M_equal(const _Hashtable& __other) const
01116     {
01117       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
01118 
01119       if (__this->size() != __other.size())
01120     return false;
01121 
01122       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
01123     {
01124       const auto __ity = __other.find(_ExtractKey()(*__itx));
01125       if (__ity == __other.end() || !bool(*__ity == *__itx))
01126         return false;
01127     }
01128       return true;
01129     }
01130 
01131   template<typename _ExtractKey, typename _Hashtable>
01132     struct _Equality_base<_ExtractKey, false, _Hashtable>
01133     {
01134       bool _M_equal(const _Hashtable&) const;
01135 
01136     private:
01137       template<typename _Uiterator>
01138     static bool
01139     _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
01140     };
01141 
01142   // See std::is_permutation in N3068.
01143   template<typename _ExtractKey, typename _Hashtable>
01144     template<typename _Uiterator>
01145       bool
01146       _Equality_base<_ExtractKey, false, _Hashtable>::
01147       _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
01148             _Uiterator __first2)
01149       {
01150     for (; __first1 != __last1; ++__first1, ++__first2)
01151       if (!(*__first1 == *__first2))
01152         break;
01153 
01154     if (__first1 == __last1)
01155       return true;
01156 
01157     _Uiterator __last2 = __first2;
01158     std::advance(__last2, std::distance(__first1, __last1));
01159 
01160     for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
01161       {
01162         _Uiterator __tmp =  __first1;
01163         while (__tmp != __it1 && !bool(*__tmp == *__it1))
01164           ++__tmp;
01165 
01166         // We've seen this one before.
01167         if (__tmp != __it1)
01168           continue;
01169 
01170         std::ptrdiff_t __n2 = 0;
01171         for (__tmp = __first2; __tmp != __last2; ++__tmp)
01172           if (*__tmp == *__it1)
01173         ++__n2;
01174 
01175         if (!__n2)
01176           return false;
01177 
01178         std::ptrdiff_t __n1 = 0;
01179         for (__tmp = __it1; __tmp != __last1; ++__tmp)
01180           if (*__tmp == *__it1)
01181         ++__n1;
01182 
01183         if (__n1 != __n2)
01184           return false;
01185       }
01186     return true;
01187       }
01188 
01189   template<typename _ExtractKey, typename _Hashtable>
01190     bool
01191     _Equality_base<_ExtractKey, false, _Hashtable>::
01192     _M_equal(const _Hashtable& __other) const
01193     {
01194       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
01195 
01196       if (__this->size() != __other.size())
01197     return false;
01198 
01199       for (auto __itx = __this->begin(); __itx != __this->end();)
01200     {
01201       const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
01202       const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
01203 
01204       if (std::distance(__xrange.first, __xrange.second)
01205           != std::distance(__yrange.first, __yrange.second))
01206         return false;
01207 
01208       if (!_S_is_permutation(__xrange.first,
01209                  __xrange.second,
01210                  __yrange.first))
01211         return false;
01212 
01213       __itx = __xrange.second;
01214     }
01215       return true;
01216     }
01217 
01218 _GLIBCXX_END_NAMESPACE_VERSION
01219 } // namespace __detail
01220 } // namespace std
01221 
01222 #endif // _HASHTABLE_POLICY_H