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 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   // Auxiliary types used for all instantiations of _Hashtable: nodes
00063   // and iterators.
00064 
00065   // Nodes, used to wrap elements stored in the hash table.  A policy
00066   // template parameter of class template _Hashtable controls whether
00067   // nodes also store a hash code. In some cases (e.g. strings) this
00068   // may be a performance win.
00069   template<typename _Value, bool __cache_hash_code>
00070     struct _Hash_node;
00071 
00072   template<typename _Value>
00073     struct _Hash_node<_Value, true>
00074     {
00075       _Value       _M_v;
00076       std::size_t  _M_hash_code;
00077       _Hash_node*  _M_next;
00078 
00079       template<typename... _Args>
00080     _Hash_node(_Args&&... __args)
00081     : _M_v(std::forward<_Args>(__args)...),
00082       _M_hash_code(), _M_next() { }
00083     };
00084 
00085   template<typename _Value>
00086     struct _Hash_node<_Value, false>
00087     {
00088       _Value       _M_v;
00089       _Hash_node*  _M_next;
00090 
00091       template<typename... _Args>
00092     _Hash_node(_Args&&... __args)
00093     : _M_v(std::forward<_Args>(__args)...),
00094       _M_next() { }
00095     };
00096 
00097   // Local iterators, used to iterate within a bucket but not between
00098   // buckets.
00099   template<typename _Value, bool __cache>
00100     struct _Node_iterator_base
00101     {
00102       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
00103       : _M_cur(__p) { }
00104 
00105       void
00106       _M_incr()
00107       { _M_cur = _M_cur->_M_next; }
00108 
00109       _Hash_node<_Value, __cache>*  _M_cur;
00110     };
00111 
00112   template<typename _Value, bool __cache>
00113     inline bool
00114     operator==(const _Node_iterator_base<_Value, __cache>& __x,
00115            const _Node_iterator_base<_Value, __cache>& __y)
00116     { return __x._M_cur == __y._M_cur; }
00117 
00118   template<typename _Value, bool __cache>
00119     inline bool
00120     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
00121            const _Node_iterator_base<_Value, __cache>& __y)
00122     { return __x._M_cur != __y._M_cur; }
00123 
00124   template<typename _Value, bool __constant_iterators, bool __cache>
00125     struct _Node_iterator
00126     : public _Node_iterator_base<_Value, __cache>
00127     {
00128       typedef _Value                                   value_type;
00129       typedef typename std::conditional<__constant_iterators,
00130                     const _Value*, _Value*>::type
00131                                pointer;
00132       typedef typename std::conditional<__constant_iterators,
00133                     const _Value&, _Value&>::type
00134                                reference;
00135       typedef std::ptrdiff_t                           difference_type;
00136       typedef std::forward_iterator_tag                iterator_category;
00137 
00138       _Node_iterator()
00139       : _Node_iterator_base<_Value, __cache>(0) { }
00140 
00141       explicit
00142       _Node_iterator(_Hash_node<_Value, __cache>* __p)
00143       : _Node_iterator_base<_Value, __cache>(__p) { }
00144 
00145       reference
00146       operator*() const
00147       { return this->_M_cur->_M_v; }
00148 
00149       pointer
00150       operator->() const
00151       { return std::__addressof(this->_M_cur->_M_v); }
00152 
00153       _Node_iterator&
00154       operator++()
00155       {
00156     this->_M_incr();
00157     return *this;
00158       }
00159 
00160       _Node_iterator
00161       operator++(int)
00162       {
00163     _Node_iterator __tmp(*this);
00164     this->_M_incr();
00165     return __tmp;
00166       }
00167     };
00168 
00169   template<typename _Value, bool __constant_iterators, bool __cache>
00170     struct _Node_const_iterator
00171     : public _Node_iterator_base<_Value, __cache>
00172     {
00173       typedef _Value                                   value_type;
00174       typedef const _Value*                            pointer;
00175       typedef const _Value&                            reference;
00176       typedef std::ptrdiff_t                           difference_type;
00177       typedef std::forward_iterator_tag                iterator_category;
00178 
00179       _Node_const_iterator()
00180       : _Node_iterator_base<_Value, __cache>(0) { }
00181 
00182       explicit
00183       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
00184       : _Node_iterator_base<_Value, __cache>(__p) { }
00185 
00186       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00187                __cache>& __x)
00188       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
00189 
00190       reference
00191       operator*() const
00192       { return this->_M_cur->_M_v; }
00193 
00194       pointer
00195       operator->() const
00196       { return std::__addressof(this->_M_cur->_M_v); }
00197 
00198       _Node_const_iterator&
00199       operator++()
00200       {
00201     this->_M_incr();
00202     return *this;
00203       }
00204 
00205       _Node_const_iterator
00206       operator++(int)
00207       {
00208     _Node_const_iterator __tmp(*this);
00209     this->_M_incr();
00210     return __tmp;
00211       }
00212     };
00213 
00214   template<typename _Value, bool __cache>
00215     struct _Hashtable_iterator_base
00216     {
00217       _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
00218                    _Hash_node<_Value, __cache>** __bucket)
00219       : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
00220 
00221       void
00222       _M_incr()
00223       {
00224     _M_cur_node = _M_cur_node->_M_next;
00225     if (!_M_cur_node)
00226       _M_incr_bucket();
00227       }
00228 
00229       void
00230       _M_incr_bucket();
00231 
00232       _Hash_node<_Value, __cache>*   _M_cur_node;
00233       _Hash_node<_Value, __cache>**  _M_cur_bucket;
00234     };
00235 
00236   // Global iterators, used for arbitrary iteration within a hash
00237   // table.  Larger and more expensive than local iterators.
00238   template<typename _Value, bool __cache>
00239     void
00240     _Hashtable_iterator_base<_Value, __cache>::
00241     _M_incr_bucket()
00242     {
00243       ++_M_cur_bucket;
00244 
00245       // This loop requires the bucket array to have a non-null sentinel.
00246       while (!*_M_cur_bucket)
00247     ++_M_cur_bucket;
00248       _M_cur_node = *_M_cur_bucket;
00249     }
00250 
00251   template<typename _Value, bool __cache>
00252     inline bool
00253     operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
00254            const _Hashtable_iterator_base<_Value, __cache>& __y)
00255     { return __x._M_cur_node == __y._M_cur_node; }
00256 
00257   template<typename _Value, bool __cache>
00258     inline bool
00259     operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
00260            const _Hashtable_iterator_base<_Value, __cache>& __y)
00261     { return __x._M_cur_node != __y._M_cur_node; }
00262 
00263   template<typename _Value, bool __constant_iterators, bool __cache>
00264     struct _Hashtable_iterator
00265     : public _Hashtable_iterator_base<_Value, __cache>
00266     {
00267       typedef _Value                                   value_type;
00268       typedef typename std::conditional<__constant_iterators,
00269                     const _Value*, _Value*>::type
00270                                pointer;
00271       typedef typename std::conditional<__constant_iterators,
00272                     const _Value&, _Value&>::type
00273                                reference;
00274       typedef std::ptrdiff_t                           difference_type;
00275       typedef std::forward_iterator_tag                iterator_category;
00276 
00277       _Hashtable_iterator()
00278       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00279 
00280       _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
00281               _Hash_node<_Value, __cache>** __b)
00282       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00283 
00284       explicit
00285       _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
00286       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00287 
00288       reference
00289       operator*() const
00290       { return this->_M_cur_node->_M_v; }
00291 
00292       pointer
00293       operator->() const
00294       { return std::__addressof(this->_M_cur_node->_M_v); }
00295 
00296       _Hashtable_iterator&
00297       operator++()
00298       {
00299     this->_M_incr();
00300     return *this;
00301       }
00302 
00303       _Hashtable_iterator
00304       operator++(int)
00305       {
00306     _Hashtable_iterator __tmp(*this);
00307     this->_M_incr();
00308     return __tmp;
00309       }
00310     };
00311 
00312   template<typename _Value, bool __constant_iterators, bool __cache>
00313     struct _Hashtable_const_iterator
00314     : public _Hashtable_iterator_base<_Value, __cache>
00315     {
00316       typedef _Value                                   value_type;
00317       typedef const _Value*                            pointer;
00318       typedef const _Value&                            reference;
00319       typedef std::ptrdiff_t                           difference_type;
00320       typedef std::forward_iterator_tag                iterator_category;
00321 
00322       _Hashtable_const_iterator()
00323       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00324 
00325       _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
00326                 _Hash_node<_Value, __cache>** __b)
00327       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00328 
00329       explicit
00330       _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
00331       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00332 
00333       _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
00334                 __constant_iterators, __cache>& __x)
00335       : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
00336                           __x._M_cur_bucket) { }
00337 
00338       reference
00339       operator*() const
00340       { return this->_M_cur_node->_M_v; }
00341 
00342       pointer
00343       operator->() const
00344       { return std::__addressof(this->_M_cur_node->_M_v); }
00345 
00346       _Hashtable_const_iterator&
00347       operator++()
00348       {
00349     this->_M_incr();
00350     return *this;
00351       }
00352 
00353       _Hashtable_const_iterator
00354       operator++(int)
00355       {
00356     _Hashtable_const_iterator __tmp(*this);
00357     this->_M_incr();
00358     return __tmp;
00359       }
00360     };
00361 
00362 
00363   // Many of class template _Hashtable's template parameters are policy
00364   // classes.  These are defaults for the policies.
00365 
00366   // Default range hashing function: use division to fold a large number
00367   // into the range [0, N).
00368   struct _Mod_range_hashing
00369   {
00370     typedef std::size_t first_argument_type;
00371     typedef std::size_t second_argument_type;
00372     typedef std::size_t result_type;
00373 
00374     result_type
00375     operator()(first_argument_type __num, second_argument_type __den) const
00376     { return __num % __den; }
00377   };
00378 
00379   // Default ranged hash function H.  In principle it should be a
00380   // function object composed from objects of type H1 and H2 such that
00381   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
00382   // h1 and h2.  So instead we'll just use a tag to tell class template
00383   // hashtable to do that composition.
00384   struct _Default_ranged_hash { };
00385 
00386   // Default value for rehash policy.  Bucket size is (usually) the
00387   // smallest prime that keeps the load factor small enough.
00388   struct _Prime_rehash_policy
00389   {
00390     _Prime_rehash_policy(float __z = 1.0)
00391     : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
00392 
00393     float
00394     max_load_factor() const
00395     { return _M_max_load_factor; }
00396 
00397     // Return a bucket size no smaller than n.
00398     std::size_t
00399     _M_next_bkt(std::size_t __n) const;
00400 
00401     // Return a bucket count appropriate for n elements
00402     std::size_t
00403     _M_bkt_for_elements(std::size_t __n) const;
00404 
00405     // __n_bkt is current bucket count, __n_elt is current element count,
00406     // and __n_ins is number of elements to be inserted.  Do we need to
00407     // increase bucket count?  If so, return make_pair(true, n), where n
00408     // is the new bucket count.  If not, return make_pair(false, 0).
00409     std::pair<bool, std::size_t>
00410     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00411            std::size_t __n_ins) const;
00412 
00413     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
00414 
00415     float                _M_max_load_factor;
00416     float                _M_growth_factor;
00417     mutable std::size_t  _M_next_resize;
00418   };
00419 
00420   extern const unsigned long __prime_list[];
00421 
00422   // XXX This is a hack.  There's no good reason for any of
00423   // _Prime_rehash_policy's member functions to be inline.
00424 
00425   // Return a prime no smaller than n.
00426   inline std::size_t
00427   _Prime_rehash_policy::
00428   _M_next_bkt(std::size_t __n) const
00429   {
00430     const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
00431                         + _S_n_primes, __n);
00432     _M_next_resize =
00433       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
00434     return *__p;
00435   }
00436 
00437   // Return the smallest prime p such that alpha p >= n, where alpha
00438   // is the load factor.
00439   inline std::size_t
00440   _Prime_rehash_policy::
00441   _M_bkt_for_elements(std::size_t __n) const
00442   {
00443     const float __min_bkts = __n / _M_max_load_factor;
00444     const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
00445                         + _S_n_primes, __min_bkts);
00446     _M_next_resize =
00447       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
00448     return *__p;
00449   }
00450 
00451   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
00452   // If p > __n_bkt, return make_pair(true, p); otherwise return
00453   // make_pair(false, 0).  In principle this isn't very different from
00454   // _M_bkt_for_elements.
00455 
00456   // The only tricky part is that we're caching the element count at
00457   // which we need to rehash, so we don't have to do a floating-point
00458   // multiply for every insertion.
00459 
00460   inline std::pair<bool, std::size_t>
00461   _Prime_rehash_policy::
00462   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00463          std::size_t __n_ins) const
00464   {
00465     if (__n_elt + __n_ins > _M_next_resize)
00466       {
00467     float __min_bkts = ((float(__n_ins) + float(__n_elt))
00468                 / _M_max_load_factor);
00469     if (__min_bkts > __n_bkt)
00470       {
00471         __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
00472         const unsigned long* __p =
00473           std::lower_bound(__prime_list, __prime_list + _S_n_primes,
00474                    __min_bkts);
00475         _M_next_resize = static_cast<std::size_t>
00476           (__builtin_ceil(*__p * _M_max_load_factor));
00477         return std::make_pair(true, *__p);
00478       }
00479     else
00480       {
00481         _M_next_resize = static_cast<std::size_t>
00482           (__builtin_ceil(__n_bkt * _M_max_load_factor));
00483         return std::make_pair(false, 0);
00484       }
00485       }
00486     else
00487       return std::make_pair(false, 0);
00488   }
00489 
00490   // Base classes for std::_Hashtable.  We define these base classes
00491   // because in some cases we want to do different things depending
00492   // on the value of a policy class.  In some cases the policy class
00493   // affects which member functions and nested typedefs are defined;
00494   // we handle that by specializing base class templates.  Several of
00495   // the base class templates need to access other members of class
00496   // template _Hashtable, so we use the "curiously recurring template
00497   // pattern" for them.
00498 
00499   // class template _Map_base.  If the hashtable has a value type of
00500   // the form pair<T1, T2> and a key extraction policy that returns the
00501   // first part of the pair, the hashtable gets a mapped_type typedef.
00502   // If it satisfies those criteria and also has unique keys, then it
00503   // also gets an operator[].
00504   template<typename _Key, typename _Value, typename _Ex, bool __unique,
00505        typename _Hashtable>
00506     struct _Map_base { };
00507 
00508   template<typename _Key, typename _Pair, typename _Hashtable>
00509     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
00510     {
00511       typedef typename _Pair::second_type mapped_type;
00512     };
00513 
00514   template<typename _Key, typename _Pair, typename _Hashtable>
00515     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
00516     {
00517       typedef typename _Pair::second_type mapped_type;
00518 
00519       mapped_type&
00520       operator[](const _Key& __k);
00521 
00522       mapped_type&
00523       operator[](_Key&& __k);
00524 
00525       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00526       // DR 761. unordered_map needs an at() member function.
00527       mapped_type&
00528       at(const _Key& __k);
00529 
00530       const mapped_type&
00531       at(const _Key& __k) const;
00532     };
00533 
00534   template<typename _Key, typename _Pair, typename _Hashtable>
00535     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00536                true, _Hashtable>::mapped_type&
00537     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00538     operator[](const _Key& __k)
00539     {
00540       _Hashtable* __h = static_cast<_Hashtable*>(this);
00541       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00542       std::size_t __n = __h->_M_bucket_index(__k, __code,
00543                          __h->_M_bucket_count);
00544 
00545       typename _Hashtable::_Node* __p =
00546     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00547       if (!__p)
00548     return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
00549                      __n, __code)->second;
00550       return (__p->_M_v).second;
00551     }
00552 
00553   template<typename _Key, typename _Pair, typename _Hashtable>
00554     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00555                true, _Hashtable>::mapped_type&
00556     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00557     operator[](_Key&& __k)
00558     {
00559       _Hashtable* __h = static_cast<_Hashtable*>(this);
00560       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00561       std::size_t __n = __h->_M_bucket_index(__k, __code,
00562                          __h->_M_bucket_count);
00563 
00564       typename _Hashtable::_Node* __p =
00565     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00566       if (!__p)
00567     return __h->_M_insert_bucket(std::make_pair(std::move(__k),
00568                             mapped_type()),
00569                      __n, __code)->second;
00570       return (__p->_M_v).second;
00571     }
00572 
00573   template<typename _Key, typename _Pair, typename _Hashtable>
00574     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00575                true, _Hashtable>::mapped_type&
00576     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00577     at(const _Key& __k)
00578     {
00579       _Hashtable* __h = static_cast<_Hashtable*>(this);
00580       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00581       std::size_t __n = __h->_M_bucket_index(__k, __code,
00582                          __h->_M_bucket_count);
00583 
00584       typename _Hashtable::_Node* __p =
00585     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00586       if (!__p)
00587     __throw_out_of_range(__N("_Map_base::at"));
00588       return (__p->_M_v).second;
00589     }
00590 
00591   template<typename _Key, typename _Pair, typename _Hashtable>
00592     const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00593                  true, _Hashtable>::mapped_type&
00594     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00595     at(const _Key& __k) const
00596     {
00597       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
00598       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00599       std::size_t __n = __h->_M_bucket_index(__k, __code,
00600                          __h->_M_bucket_count);
00601 
00602       typename _Hashtable::_Node* __p =
00603     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00604       if (!__p)
00605     __throw_out_of_range(__N("_Map_base::at"));
00606       return (__p->_M_v).second;
00607     }
00608 
00609   // class template _Rehash_base.  Give hashtable the max_load_factor
00610   // functions and reserve iff the rehash policy is _Prime_rehash_policy.
00611   template<typename _RehashPolicy, typename _Hashtable>
00612     struct _Rehash_base { };
00613 
00614   template<typename _Hashtable>
00615     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
00616     {
00617       float
00618       max_load_factor() const
00619       {
00620     const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00621     return __this->__rehash_policy().max_load_factor();
00622       }
00623 
00624       void
00625       max_load_factor(float __z)
00626       {
00627     _Hashtable* __this = static_cast<_Hashtable*>(this);
00628     __this->__rehash_policy(_Prime_rehash_policy(__z));
00629       }
00630 
00631       void
00632       reserve(std::size_t __n)
00633       {
00634     _Hashtable* __this = static_cast<_Hashtable*>(this);
00635     __this->rehash(__builtin_ceil(__n / max_load_factor()));
00636       }
00637     };
00638 
00639   // Class template _Hash_code_base.  Encapsulates two policy issues that
00640   // aren't quite orthogonal.
00641   //   (1) the difference between using a ranged hash function and using
00642   //       the combination of a hash function and a range-hashing function.
00643   //       In the former case we don't have such things as hash codes, so
00644   //       we have a dummy type as placeholder.
00645   //   (2) Whether or not we cache hash codes.  Caching hash codes is
00646   //       meaningless if we have a ranged hash function.
00647   // We also put the key extraction and equality comparison function
00648   // objects here, for convenience.
00649 
00650   // Primary template: unused except as a hook for specializations.
00651   template<typename _Key, typename _Value,
00652        typename _ExtractKey, typename _Equal,
00653        typename _H1, typename _H2, typename _Hash,
00654        bool __cache_hash_code>
00655     struct _Hash_code_base;
00656 
00657   // Specialization: ranged hash function, no caching hash codes.  H1
00658   // and H2 are provided but ignored.  We define a dummy hash code type.
00659   template<typename _Key, typename _Value,
00660        typename _ExtractKey, typename _Equal,
00661        typename _H1, typename _H2, typename _Hash>
00662     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00663                _Hash, false>
00664     {
00665     protected:
00666       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00667               const _H1&, const _H2&, const _Hash& __h)
00668       : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
00669 
00670       typedef void* _Hash_code_type;
00671 
00672       _Hash_code_type
00673       _M_hash_code(const _Key& __key) const
00674       { return 0; }
00675 
00676       std::size_t
00677       _M_bucket_index(const _Key& __k, _Hash_code_type,
00678               std::size_t __n) const
00679       { return _M_ranged_hash(__k, __n); }
00680 
00681       std::size_t
00682       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00683               std::size_t __n) const
00684       { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
00685 
00686       bool
00687       _M_compare(const _Key& __k, _Hash_code_type,
00688          _Hash_node<_Value, false>* __n) const
00689       { return _M_eq(__k, _M_extract(__n->_M_v)); }
00690 
00691       void
00692       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00693       { }
00694 
00695       void
00696       _M_copy_code(_Hash_node<_Value, false>*,
00697            const _Hash_node<_Value, false>*) const
00698       { }
00699 
00700       void
00701       _M_swap(_Hash_code_base& __x)
00702       {
00703     std::swap(_M_extract, __x._M_extract);
00704     std::swap(_M_eq, __x._M_eq);
00705     std::swap(_M_ranged_hash, __x._M_ranged_hash);
00706       }
00707 
00708     protected:
00709       _ExtractKey  _M_extract;
00710       _Equal       _M_eq;
00711       _Hash        _M_ranged_hash;
00712     };
00713 
00714 
00715   // No specialization for ranged hash function while caching hash codes.
00716   // That combination is meaningless, and trying to do it is an error.
00717 
00718 
00719   // Specialization: ranged hash function, cache hash codes.  This
00720   // combination is meaningless, so we provide only a declaration
00721   // and no definition.
00722   template<typename _Key, typename _Value,
00723        typename _ExtractKey, typename _Equal,
00724        typename _H1, typename _H2, typename _Hash>
00725     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00726                _Hash, true>;
00727 
00728   // Specialization: hash function and range-hashing function, no
00729   // caching of hash codes.  H is provided but ignored.  Provides
00730   // typedef and accessor required by TR1.
00731   template<typename _Key, typename _Value,
00732        typename _ExtractKey, typename _Equal,
00733        typename _H1, typename _H2>
00734     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00735                _Default_ranged_hash, false>
00736     {
00737       typedef _H1 hasher;
00738 
00739       hasher
00740       hash_function() const
00741       { return _M_h1; }
00742 
00743     protected:
00744       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00745               const _H1& __h1, const _H2& __h2,
00746               const _Default_ranged_hash&)
00747       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00748 
00749       typedef std::size_t _Hash_code_type;
00750 
00751       _Hash_code_type
00752       _M_hash_code(const _Key& __k) const
00753       { return _M_h1(__k); }
00754 
00755       std::size_t
00756       _M_bucket_index(const _Key&, _Hash_code_type __c,
00757               std::size_t __n) const
00758       { return _M_h2(__c, __n); }
00759 
00760       std::size_t
00761       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00762               std::size_t __n) const
00763       { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
00764 
00765       bool
00766       _M_compare(const _Key& __k, _Hash_code_type,
00767          _Hash_node<_Value, false>* __n) const
00768       { return _M_eq(__k, _M_extract(__n->_M_v)); }
00769 
00770       void
00771       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00772       { }
00773 
00774       void
00775       _M_copy_code(_Hash_node<_Value, false>*,
00776            const _Hash_node<_Value, false>*) const
00777       { }
00778 
00779       void
00780       _M_swap(_Hash_code_base& __x)
00781       {
00782     std::swap(_M_extract, __x._M_extract);
00783     std::swap(_M_eq, __x._M_eq);
00784     std::swap(_M_h1, __x._M_h1);
00785     std::swap(_M_h2, __x._M_h2);
00786       }
00787 
00788     protected:
00789       _ExtractKey  _M_extract;
00790       _Equal       _M_eq;
00791       _H1          _M_h1;
00792       _H2          _M_h2;
00793     };
00794 
00795   // Specialization: hash function and range-hashing function,
00796   // caching hash codes.  H is provided but ignored.  Provides
00797   // typedef and accessor required by TR1.
00798   template<typename _Key, typename _Value,
00799        typename _ExtractKey, typename _Equal,
00800        typename _H1, typename _H2>
00801     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00802                _Default_ranged_hash, true>
00803     {
00804       typedef _H1 hasher;
00805 
00806       hasher
00807       hash_function() const
00808       { return _M_h1; }
00809 
00810     protected:
00811       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00812               const _H1& __h1, const _H2& __h2,
00813               const _Default_ranged_hash&)
00814       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00815 
00816       typedef std::size_t _Hash_code_type;
00817 
00818       _Hash_code_type
00819       _M_hash_code(const _Key& __k) const
00820       { return _M_h1(__k); }
00821 
00822       std::size_t
00823       _M_bucket_index(const _Key&, _Hash_code_type __c,
00824               std::size_t __n) const
00825       { return _M_h2(__c, __n); }
00826 
00827       std::size_t
00828       _M_bucket_index(const _Hash_node<_Value, true>* __p,
00829               std::size_t __n) const
00830       { return _M_h2(__p->_M_hash_code, __n); }
00831 
00832       bool
00833       _M_compare(const _Key& __k, _Hash_code_type __c,
00834          _Hash_node<_Value, true>* __n) const
00835       { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
00836 
00837       void
00838       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
00839       { __n->_M_hash_code = __c; }
00840 
00841       void
00842       _M_copy_code(_Hash_node<_Value, true>* __to,
00843            const _Hash_node<_Value, true>* __from) const
00844       { __to->_M_hash_code = __from->_M_hash_code; }
00845 
00846       void
00847       _M_swap(_Hash_code_base& __x)
00848       {
00849     std::swap(_M_extract, __x._M_extract);
00850     std::swap(_M_eq, __x._M_eq);
00851     std::swap(_M_h1, __x._M_h1);
00852     std::swap(_M_h2, __x._M_h2);
00853       }
00854 
00855     protected:
00856       _ExtractKey  _M_extract;
00857       _Equal       _M_eq;
00858       _H1          _M_h1;
00859       _H2          _M_h2;
00860     };
00861 
00862 
00863   // Class template _Equality_base.  This is for implementing equality
00864   // comparison for unordered containers, per N3068, by John Lakos and
00865   // Pablo Halpern.  Algorithmically, we follow closely the reference
00866   // implementations therein.
00867   template<typename _ExtractKey, bool __unique_keys,
00868        typename _Hashtable>
00869     struct _Equality_base;
00870 
00871   template<typename _ExtractKey, typename _Hashtable>
00872     struct _Equality_base<_ExtractKey, true, _Hashtable>
00873     {
00874       bool _M_equal(const _Hashtable&) const;
00875     };
00876 
00877   template<typename _ExtractKey, typename _Hashtable>
00878     bool
00879     _Equality_base<_ExtractKey, true, _Hashtable>::
00880     _M_equal(const _Hashtable& __other) const
00881     {
00882       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00883 
00884       if (__this->size() != __other.size())
00885     return false;
00886 
00887       for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
00888     {
00889       const auto __ity = __other.find(_ExtractKey()(*__itx));
00890       if (__ity == __other.end() || *__ity != *__itx)
00891         return false;
00892     }
00893       return true;
00894     }
00895 
00896   template<typename _ExtractKey, typename _Hashtable>
00897     struct _Equality_base<_ExtractKey, false, _Hashtable>
00898     {
00899       bool _M_equal(const _Hashtable&) const;
00900 
00901     private:
00902       template<typename _Uiterator>
00903     static bool
00904     _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
00905     };
00906 
00907   // See std::is_permutation in N3068.
00908   template<typename _ExtractKey, typename _Hashtable>
00909     template<typename _Uiterator>
00910       bool
00911       _Equality_base<_ExtractKey, false, _Hashtable>::
00912       _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
00913             _Uiterator __first2)
00914       {
00915     for (; __first1 != __last1; ++__first1, ++__first2)
00916       if (!(*__first1 == *__first2))
00917         break;
00918 
00919     if (__first1 == __last1)
00920       return true;
00921 
00922     _Uiterator __last2 = __first2;
00923     std::advance(__last2, std::distance(__first1, __last1));
00924 
00925     for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
00926       {
00927         _Uiterator __tmp =  __first1;
00928         while (__tmp != __it1 && !(*__tmp == *__it1))
00929           ++__tmp;
00930 
00931         // We've seen this one before.
00932         if (__tmp != __it1)
00933           continue;
00934 
00935         std::ptrdiff_t __n2 = 0;
00936         for (__tmp = __first2; __tmp != __last2; ++__tmp)
00937           if (*__tmp == *__it1)
00938         ++__n2;
00939 
00940         if (!__n2)
00941           return false;
00942 
00943         std::ptrdiff_t __n1 = 0;
00944         for (__tmp = __it1; __tmp != __last1; ++__tmp)
00945           if (*__tmp == *__it1)
00946         ++__n1;
00947 
00948         if (__n1 != __n2)
00949           return false;
00950       }
00951     return true;
00952       }
00953 
00954   template<typename _ExtractKey, typename _Hashtable>
00955     bool
00956     _Equality_base<_ExtractKey, false, _Hashtable>::
00957     _M_equal(const _Hashtable& __other) const
00958     {
00959       const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00960 
00961       if (__this->size() != __other.size())
00962     return false;
00963 
00964       for (auto __itx = __this->begin(); __itx != __this->end();)
00965     {
00966       const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
00967       const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
00968 
00969       if (std::distance(__xrange.first, __xrange.second)
00970           != std::distance(__yrange.first, __yrange.second))
00971         return false;
00972 
00973       if (!_S_is_permutation(__xrange.first,
00974                  __xrange.second,
00975                  __yrange.first))
00976         return false;
00977 
00978       __itx = __xrange.second;
00979     }
00980       return true;
00981     }
00982 
00983 _GLIBCXX_END_NAMESPACE_VERSION
00984 } // namespace __detail
00985 } // namespace std
00986 
00987 #endif // _HASHTABLE_POLICY_H