hashtable_policy.h

Go to the documentation of this file.
00001 // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /** @file tr1/hashtable_policy.h
00031  *  This is a TR1 C++ Library header. 
00032  */
00033 
00034 #ifndef _TR1_HASHTABLE_POLICY_H
00035 #define _TR1_HASHTABLE_POLICY_H 1
00036 
00037 #include <functional> // _Identity, _Select1st
00038 #include <tr1/utility>
00039 #include <ext/type_traits.h>
00040 
00041 namespace std
00042 { 
00043 _GLIBCXX_BEGIN_NAMESPACE(tr1)
00044 namespace __detail
00045 {
00046   // Helper function: return distance(first, last) for forward
00047   // iterators, or 0 for input iterators.
00048   template<class _Iterator>
00049     inline typename std::iterator_traits<_Iterator>::difference_type
00050     __distance_fw(_Iterator __first, _Iterator __last,
00051           std::input_iterator_tag)
00052     { return 0; }
00053 
00054   template<class _Iterator>
00055     inline typename std::iterator_traits<_Iterator>::difference_type
00056     __distance_fw(_Iterator __first, _Iterator __last,
00057           std::forward_iterator_tag)
00058     { return std::distance(__first, __last); }
00059 
00060   template<class _Iterator>
00061     inline typename std::iterator_traits<_Iterator>::difference_type
00062     __distance_fw(_Iterator __first, _Iterator __last)
00063     {
00064       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
00065       return __distance_fw(__first, __last, _Tag());
00066     }
00067 
00068   // XXX This is a hack.  _Prime_rehash_policy's member functions, and
00069   // certainly the list of primes, should be defined in a .cc file.
00070   // We're temporarily putting them in a header because we don't have a
00071   // place to put TR1 .cc files yet.  There's no good reason for any of
00072   // _Prime_rehash_policy's member functions to be inline, and there's
00073   // certainly no good reason for _Primes<> to exist at all.  
00074   struct _LessThan
00075   {
00076     template<typename _Tp, typename _Up>
00077       bool
00078       operator()(_Tp __x, _Up __y)
00079       { return __x < __y; }
00080   };
00081 
00082   template<int __ulongsize = sizeof(unsigned long)>
00083     struct _Primes
00084     {
00085       static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48;
00086       static const unsigned long __primes[256 + 48 + 1];
00087     };
00088 
00089   template<int __ulongsize>
00090     const int _Primes<__ulongsize>::__n_primes;
00091 
00092   template<int __ulongsize>
00093     const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] =
00094     {
00095       2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
00096       37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
00097       83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
00098       157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
00099       277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
00100       503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
00101       953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
00102       1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
00103       3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
00104       5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
00105       11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
00106       19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
00107       33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
00108       57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
00109       99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
00110       159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
00111       256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
00112       410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
00113       658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
00114       1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
00115       1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
00116       2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
00117       4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
00118       6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
00119       11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
00120       16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
00121       24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
00122       36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
00123       54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
00124       80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
00125       118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
00126       176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
00127       260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
00128       386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
00129       573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
00130       849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
00131       1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
00132       1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
00133       2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
00134       3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
00135       4294967291ul,
00136       // Sentinel, so we don't have to test the result of lower_bound,
00137       // or, on 64-bit machines, rest of the table.
00138       __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull,
00139       (unsigned long)8589934583ull,
00140       (unsigned long)12884901857ull, (unsigned long)17179869143ull,
00141       (unsigned long)25769803693ull, (unsigned long)34359738337ull,
00142       (unsigned long)51539607367ull, (unsigned long)68719476731ull,
00143       (unsigned long)103079215087ull, (unsigned long)137438953447ull,
00144       (unsigned long)206158430123ull, (unsigned long)274877906899ull,
00145       (unsigned long)412316860387ull, (unsigned long)549755813881ull,
00146       (unsigned long)824633720731ull, (unsigned long)1099511627689ull,
00147       (unsigned long)1649267441579ull, (unsigned long)2199023255531ull,
00148       (unsigned long)3298534883309ull, (unsigned long)4398046511093ull,
00149       (unsigned long)6597069766607ull, (unsigned long)8796093022151ull,
00150       (unsigned long)13194139533241ull, (unsigned long)17592186044399ull,
00151       (unsigned long)26388279066581ull, (unsigned long)35184372088777ull,
00152       (unsigned long)52776558133177ull, (unsigned long)70368744177643ull,
00153       (unsigned long)105553116266399ull, (unsigned long)140737488355213ull,
00154       (unsigned long)211106232532861ull, (unsigned long)281474976710597ull,
00155       (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull,
00156       (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull,
00157       (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull,
00158       (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull,
00159       (unsigned long)144115188075855859ull,
00160       (unsigned long)288230376151711717ull,
00161       (unsigned long)576460752303423433ull,
00162       (unsigned long)1152921504606846883ull,
00163       (unsigned long)2305843009213693951ull,
00164       (unsigned long)4611686018427387847ull,
00165       (unsigned long)9223372036854775783ull,
00166       (unsigned long)18446744073709551557ull,
00167       (unsigned long)18446744073709551557ull
00168     };
00169 
00170   // Auxiliary types used for all instantiations of _Hashtable: nodes
00171   // and iterators.
00172   
00173   // Nodes, used to wrap elements stored in the hash table.  A policy
00174   // template parameter of class template _Hashtable controls whether
00175   // nodes also store a hash code. In some cases (e.g. strings) this
00176   // may be a performance win.
00177   template<typename _Value, bool __cache_hash_code>
00178     struct _Hash_node;
00179 
00180   template<typename _Value>
00181     struct _Hash_node<_Value, true>
00182     {
00183       _Value       _M_v;
00184       std::size_t  _M_hash_code;
00185       _Hash_node*  _M_next;
00186     };
00187 
00188   template<typename _Value>
00189     struct _Hash_node<_Value, false>
00190     {
00191       _Value       _M_v;
00192       _Hash_node*  _M_next;
00193     };
00194 
00195   // Local iterators, used to iterate within a bucket but not between
00196   // buckets.
00197   template<typename _Value, bool __cache>
00198     struct _Node_iterator_base
00199     {
00200       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
00201       : _M_cur(__p) { }
00202       
00203       void
00204       _M_incr()
00205       { _M_cur = _M_cur->_M_next; }
00206 
00207       _Hash_node<_Value, __cache>*  _M_cur;
00208     };
00209 
00210   template<typename _Value, bool __cache>
00211     inline bool
00212     operator==(const _Node_iterator_base<_Value, __cache>& __x,
00213            const _Node_iterator_base<_Value, __cache>& __y)
00214     { return __x._M_cur == __y._M_cur; }
00215 
00216   template<typename _Value, bool __cache>
00217     inline bool
00218     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
00219            const _Node_iterator_base<_Value, __cache>& __y)
00220     { return __x._M_cur != __y._M_cur; }
00221 
00222   template<typename _Value, bool __constant_iterators, bool __cache>
00223     struct _Node_iterator
00224     : public _Node_iterator_base<_Value, __cache>
00225     {
00226       typedef _Value                                   value_type;
00227       typedef typename
00228       __gnu_cxx::__conditional_type<__constant_iterators,
00229                     const _Value*, _Value*>::__type
00230                                                        pointer;
00231       typedef typename
00232       __gnu_cxx::__conditional_type<__constant_iterators,
00233                     const _Value&, _Value&>::__type
00234                                                        reference;
00235       typedef std::ptrdiff_t                           difference_type;
00236       typedef std::forward_iterator_tag                iterator_category;
00237 
00238       _Node_iterator()
00239       : _Node_iterator_base<_Value, __cache>(0) { }
00240 
00241       explicit
00242       _Node_iterator(_Hash_node<_Value, __cache>* __p)
00243       : _Node_iterator_base<_Value, __cache>(__p) { }
00244 
00245       reference
00246       operator*() const
00247       { return this->_M_cur->_M_v; }
00248   
00249       pointer
00250       operator->() const
00251       { return &this->_M_cur->_M_v; }
00252 
00253       _Node_iterator&
00254       operator++()
00255       { 
00256     this->_M_incr();
00257     return *this; 
00258       }
00259   
00260       _Node_iterator
00261       operator++(int)
00262       { 
00263     _Node_iterator __tmp(*this);
00264     this->_M_incr();
00265     return __tmp;
00266       }
00267     };
00268 
00269   template<typename _Value, bool __constant_iterators, bool __cache>
00270     struct _Node_const_iterator
00271     : public _Node_iterator_base<_Value, __cache>
00272     {
00273       typedef _Value                                   value_type;
00274       typedef const _Value*                            pointer;
00275       typedef const _Value&                            reference;
00276       typedef std::ptrdiff_t                           difference_type;
00277       typedef std::forward_iterator_tag                iterator_category;
00278 
00279       _Node_const_iterator()
00280       : _Node_iterator_base<_Value, __cache>(0) { }
00281 
00282       explicit
00283       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
00284       : _Node_iterator_base<_Value, __cache>(__p) { }
00285 
00286       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00287                __cache>& __x)
00288       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
00289 
00290       reference
00291       operator*() const
00292       { return this->_M_cur->_M_v; }
00293   
00294       pointer
00295       operator->() const
00296       { return &this->_M_cur->_M_v; }
00297 
00298       _Node_const_iterator&
00299       operator++()
00300       { 
00301     this->_M_incr();
00302     return *this; 
00303       }
00304   
00305       _Node_const_iterator
00306       operator++(int)
00307       { 
00308     _Node_const_iterator __tmp(*this);
00309     this->_M_incr();
00310     return __tmp;
00311       }
00312     };
00313 
00314   template<typename _Value, bool __cache>
00315     struct _Hashtable_iterator_base
00316     {
00317       _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
00318                    _Hash_node<_Value, __cache>** __bucket)
00319       : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
00320 
00321       void
00322       _M_incr()
00323       {
00324     _M_cur_node = _M_cur_node->_M_next;
00325     if (!_M_cur_node)
00326       _M_incr_bucket();
00327       }
00328 
00329       void
00330       _M_incr_bucket();
00331 
00332       _Hash_node<_Value, __cache>*   _M_cur_node;
00333       _Hash_node<_Value, __cache>**  _M_cur_bucket;
00334     };
00335 
00336   // Global iterators, used for arbitrary iteration within a hash
00337   // table.  Larger and more expensive than local iterators.
00338   template<typename _Value, bool __cache>
00339     void
00340     _Hashtable_iterator_base<_Value, __cache>::
00341     _M_incr_bucket()
00342     {
00343       ++_M_cur_bucket;
00344 
00345       // This loop requires the bucket array to have a non-null sentinel.
00346       while (!*_M_cur_bucket)
00347     ++_M_cur_bucket;
00348       _M_cur_node = *_M_cur_bucket;
00349     }
00350 
00351   template<typename _Value, bool __cache>
00352     inline bool
00353     operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
00354            const _Hashtable_iterator_base<_Value, __cache>& __y)
00355     { return __x._M_cur_node == __y._M_cur_node; }
00356 
00357   template<typename _Value, bool __cache>
00358     inline bool
00359     operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
00360            const _Hashtable_iterator_base<_Value, __cache>& __y)
00361     { return __x._M_cur_node != __y._M_cur_node; }
00362 
00363   template<typename _Value, bool __constant_iterators, bool __cache>
00364     struct _Hashtable_iterator
00365     : public _Hashtable_iterator_base<_Value, __cache>
00366     {
00367       typedef _Value                                   value_type;
00368       typedef typename
00369       __gnu_cxx::__conditional_type<__constant_iterators,
00370                     const _Value*, _Value*>::__type
00371                                                        pointer;
00372       typedef typename
00373       __gnu_cxx::__conditional_type<__constant_iterators,
00374                     const _Value&, _Value&>::__type
00375                                                        reference;
00376       typedef std::ptrdiff_t                           difference_type;
00377       typedef std::forward_iterator_tag                iterator_category;
00378 
00379       _Hashtable_iterator()
00380       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00381 
00382       _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
00383               _Hash_node<_Value, __cache>** __b)
00384       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00385 
00386       explicit
00387       _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
00388       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00389 
00390       reference
00391       operator*() const
00392       { return this->_M_cur_node->_M_v; }
00393   
00394       pointer
00395       operator->() const
00396       { return &this->_M_cur_node->_M_v; }
00397 
00398       _Hashtable_iterator&
00399       operator++()
00400       { 
00401     this->_M_incr();
00402     return *this;
00403       }
00404   
00405       _Hashtable_iterator
00406       operator++(int)
00407       { 
00408     _Hashtable_iterator __tmp(*this);
00409     this->_M_incr();
00410     return __tmp;
00411       }
00412     };
00413 
00414   template<typename _Value, bool __constant_iterators, bool __cache>
00415     struct _Hashtable_const_iterator
00416     : public _Hashtable_iterator_base<_Value, __cache>
00417     {
00418       typedef _Value                                   value_type;
00419       typedef const _Value*                            pointer;
00420       typedef const _Value&                            reference;
00421       typedef std::ptrdiff_t                           difference_type;
00422       typedef std::forward_iterator_tag                iterator_category;
00423 
00424       _Hashtable_const_iterator()
00425       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00426 
00427       _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
00428                 _Hash_node<_Value, __cache>** __b)
00429       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00430 
00431       explicit
00432       _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
00433       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00434 
00435       _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
00436                 __constant_iterators, __cache>& __x)
00437       : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
00438                           __x._M_cur_bucket) { }
00439 
00440       reference
00441       operator*() const
00442       { return this->_M_cur_node->_M_v; }
00443   
00444       pointer
00445       operator->() const
00446       { return &this->_M_cur_node->_M_v; }
00447 
00448       _Hashtable_const_iterator&
00449       operator++()
00450       { 
00451     this->_M_incr();
00452     return *this;
00453       }
00454   
00455       _Hashtable_const_iterator
00456       operator++(int)
00457       { 
00458     _Hashtable_const_iterator __tmp(*this);
00459     this->_M_incr();
00460     return __tmp;
00461       }
00462     };
00463 
00464 
00465   // Many of class template _Hashtable's template parameters are policy
00466   // classes.  These are defaults for the policies.
00467 
00468   // Default range hashing function: use division to fold a large number
00469   // into the range [0, N).
00470   struct _Mod_range_hashing
00471   {
00472     typedef std::size_t first_argument_type;
00473     typedef std::size_t second_argument_type;
00474     typedef std::size_t result_type;
00475 
00476     result_type
00477     operator()(first_argument_type __num, second_argument_type __den) const
00478     { return __num % __den; }
00479   };
00480 
00481   // Default ranged hash function H.  In principle it should be a
00482   // function object composed from objects of type H1 and H2 such that
00483   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
00484   // h1 and h2.  So instead we'll just use a tag to tell class template
00485   // hashtable to do that composition.
00486   struct _Default_ranged_hash { };
00487 
00488   // Default value for rehash policy.  Bucket size is (usually) the
00489   // smallest prime that keeps the load factor small enough.
00490   struct _Prime_rehash_policy
00491   {
00492     _Prime_rehash_policy(float __z = 1.0);
00493 
00494     float
00495     max_load_factor() const;
00496 
00497     // Return a bucket size no smaller than n.
00498     std::size_t
00499     _M_next_bkt(std::size_t __n) const;
00500     
00501     // Return a bucket count appropriate for n elements
00502     std::size_t
00503     _M_bkt_for_elements(std::size_t __n) const;
00504     
00505     // __n_bkt is current bucket count, __n_elt is current element count,
00506     // and __n_ins is number of elements to be inserted.  Do we need to
00507     // increase bucket count?  If so, return make_pair(true, n), where n
00508     // is the new bucket count.  If not, return make_pair(false, 0).
00509     std::pair<bool, std::size_t>
00510     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00511            std::size_t __n_ins) const;
00512     
00513     float                _M_max_load_factor;
00514     float                _M_growth_factor;
00515     mutable std::size_t  _M_next_resize;
00516   };
00517 
00518   inline
00519   _Prime_rehash_policy::
00520   _Prime_rehash_policy(float __z)
00521   : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0)
00522   { }
00523 
00524   inline float
00525   _Prime_rehash_policy::
00526   max_load_factor() const
00527   { return _M_max_load_factor; }
00528 
00529   // Return a prime no smaller than n.
00530   inline std::size_t
00531   _Prime_rehash_policy::
00532   _M_next_bkt(std::size_t __n) const
00533   {
00534     const unsigned long* const __last = (_Primes<>::__primes
00535                      + _Primes<>::__n_primes);
00536     const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
00537                         __n);
00538     _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
00539                             * _M_max_load_factor));
00540     return *__p;
00541   }
00542 
00543   // Return the smallest prime p such that alpha p >= n, where alpha
00544   // is the load factor.
00545   inline std::size_t
00546   _Prime_rehash_policy::
00547   _M_bkt_for_elements(std::size_t __n) const
00548   {
00549     const unsigned long* const __last = (_Primes<>::__primes
00550                      + _Primes<>::__n_primes);
00551     const float __min_bkts = __n / _M_max_load_factor;
00552     const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
00553                         __min_bkts, _LessThan());
00554     _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
00555                             * _M_max_load_factor));
00556     return *__p;
00557   }
00558 
00559   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
00560   // If p > __n_bkt, return make_pair(true, p); otherwise return
00561   // make_pair(false, 0).  In principle this isn't very different from 
00562   // _M_bkt_for_elements.
00563   
00564   // The only tricky part is that we're caching the element count at
00565   // which we need to rehash, so we don't have to do a floating-point
00566   // multiply for every insertion.
00567   
00568   inline std::pair<bool, std::size_t>
00569   _Prime_rehash_policy::
00570   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00571          std::size_t __n_ins) const
00572   {
00573     if (__n_elt + __n_ins > _M_next_resize)
00574       {
00575     float __min_bkts = ((float(__n_ins) + float(__n_elt))
00576                 / _M_max_load_factor);
00577     if (__min_bkts > __n_bkt)
00578       {
00579         __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
00580         const unsigned long* const __last = (_Primes<>::__primes
00581                          + _Primes<>::__n_primes);
00582         const unsigned long* __p = std::lower_bound(_Primes<>::__primes,
00583                             __last, __min_bkts,
00584                             _LessThan());
00585         _M_next_resize = 
00586           static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor));
00587         return std::make_pair(true, *__p);
00588       }
00589     else 
00590       {
00591         _M_next_resize =
00592           static_cast<std::size_t>(std::ceil(__n_bkt
00593                          * _M_max_load_factor));
00594         return std::make_pair(false, 0);
00595       }
00596       }
00597     else
00598       return std::make_pair(false, 0);
00599   }
00600 
00601   // Base classes for std::tr1::_Hashtable.  We define these base
00602   // classes because in some cases we want to do different things
00603   // depending on the value of a policy class.  In some cases the
00604   // policy class affects which member functions and nested typedefs
00605   // are defined; we handle that by specializing base class templates.
00606   // Several of the base class templates need to access other members
00607   // of class template _Hashtable, so we use the "curiously recurring
00608   // template pattern" for them.
00609 
00610   // class template _Map_base.  If the hashtable has a value type of the
00611   // form pair<T1, T2> and a key extraction policy that returns the
00612   // first part of the pair, the hashtable gets a mapped_type typedef.
00613   // If it satisfies those criteria and also has unique keys, then it
00614   // also gets an operator[].  
00615   template<typename _Key, typename _Value, typename _Ex, bool __unique,
00616        typename _Hashtable>
00617     struct _Map_base { };
00618       
00619   template<typename _Key, typename _Pair, typename _Hashtable>
00620     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
00621     {
00622       typedef typename _Pair::second_type mapped_type;
00623     };
00624 
00625   template<typename _Key, typename _Pair, typename _Hashtable>
00626   struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
00627     {
00628       typedef typename _Pair::second_type mapped_type;
00629       
00630       mapped_type&
00631       operator[](const _Key& __k);
00632     };
00633 
00634   template<typename _Key, typename _Pair, typename _Hashtable>
00635     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00636                true, _Hashtable>::mapped_type&
00637     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00638     operator[](const _Key& __k)
00639     {
00640       _Hashtable* __h = static_cast<_Hashtable*>(this);
00641       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00642       std::size_t __n = __h->_M_bucket_index(__k, __code,
00643                          __h->_M_bucket_count);
00644 
00645       typename _Hashtable::_Node* __p =
00646     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00647       if (!__p)
00648     return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
00649                      __n, __code)->second;
00650       return (__p->_M_v).second;
00651     }
00652 
00653   // class template _Rehash_base.  Give hashtable the max_load_factor
00654   // functions iff the rehash policy is _Prime_rehash_policy.
00655   template<typename _RehashPolicy, typename _Hashtable>
00656     struct _Rehash_base { };
00657 
00658   template<typename _Hashtable>
00659     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
00660     {
00661       float
00662       max_load_factor() const
00663       {
00664     const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00665     return __this->__rehash_policy().max_load_factor();
00666       }
00667 
00668       void
00669       max_load_factor(float __z)
00670       {
00671     _Hashtable* __this = static_cast<_Hashtable*>(this);
00672     __this->__rehash_policy(_Prime_rehash_policy(__z));
00673       }
00674     };
00675 
00676   // Class template _Hash_code_base.  Encapsulates two policy issues that
00677   // aren't quite orthogonal.
00678   //   (1) the difference between using a ranged hash function and using
00679   //       the combination of a hash function and a range-hashing function.
00680   //       In the former case we don't have such things as hash codes, so
00681   //       we have a dummy type as placeholder.
00682   //   (2) Whether or not we cache hash codes.  Caching hash codes is
00683   //       meaningless if we have a ranged hash function.
00684   // We also put the key extraction and equality comparison function 
00685   // objects here, for convenience.
00686   
00687   // Primary template: unused except as a hook for specializations.  
00688   template<typename _Key, typename _Value,
00689        typename _ExtractKey, typename _Equal,
00690        typename _H1, typename _H2, typename _Hash,
00691        bool __cache_hash_code>
00692     struct _Hash_code_base;
00693 
00694   // Specialization: ranged hash function, no caching hash codes.  H1
00695   // and H2 are provided but ignored.  We define a dummy hash code type.
00696   template<typename _Key, typename _Value,
00697        typename _ExtractKey, typename _Equal,
00698        typename _H1, typename _H2, typename _Hash>
00699     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00700                _Hash, false>
00701     {
00702     protected:
00703       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00704               const _H1&, const _H2&, const _Hash& __h)
00705       : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
00706 
00707       typedef void* _Hash_code_type;
00708   
00709       _Hash_code_type
00710       _M_hash_code(const _Key& __key) const
00711       { return 0; }
00712   
00713       std::size_t
00714       _M_bucket_index(const _Key& __k, _Hash_code_type,
00715               std::size_t __n) const
00716       { return _M_ranged_hash(__k, __n); }
00717 
00718       std::size_t
00719       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00720               std::size_t __n) const
00721       { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
00722   
00723       bool
00724       _M_compare(const _Key& __k, _Hash_code_type,
00725          _Hash_node<_Value, false>* __n) const
00726       { return _M_eq(__k, _M_extract(__n->_M_v)); }
00727 
00728       void
00729       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00730       { }
00731 
00732       void
00733       _M_copy_code(_Hash_node<_Value, false>*,
00734            const _Hash_node<_Value, false>*) const
00735       { }
00736       
00737       void
00738       _M_swap(_Hash_code_base& __x)
00739       {
00740     std::swap(_M_extract, __x._M_extract);
00741     std::swap(_M_eq, __x._M_eq);
00742     std::swap(_M_ranged_hash, __x._M_ranged_hash);
00743       }
00744 
00745     protected:
00746       _ExtractKey  _M_extract;
00747       _Equal       _M_eq;
00748       _Hash        _M_ranged_hash;
00749     };
00750 
00751 
00752   // No specialization for ranged hash function while caching hash codes.
00753   // That combination is meaningless, and trying to do it is an error.
00754   
00755   
00756   // Specialization: ranged hash function, cache hash codes.  This
00757   // combination is meaningless, so we provide only a declaration
00758   // and no definition.  
00759   template<typename _Key, typename _Value,
00760        typename _ExtractKey, typename _Equal,
00761        typename _H1, typename _H2, typename _Hash>
00762     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00763                _Hash, true>;
00764 
00765   // Specialization: hash function and range-hashing function, no
00766   // caching of hash codes.  H is provided but ignored.  Provides
00767   // typedef and accessor required by TR1.  
00768   template<typename _Key, typename _Value,
00769        typename _ExtractKey, typename _Equal,
00770        typename _H1, typename _H2>
00771     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00772                _Default_ranged_hash, false>
00773     {
00774       typedef _H1 hasher;
00775 
00776       hasher
00777       hash_function() const
00778       { return _M_h1; }
00779 
00780     protected:
00781       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00782               const _H1& __h1, const _H2& __h2,
00783               const _Default_ranged_hash&)
00784       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00785 
00786       typedef std::size_t _Hash_code_type;
00787 
00788       _Hash_code_type
00789       _M_hash_code(const _Key& __k) const
00790       { return _M_h1(__k); }
00791       
00792       std::size_t
00793       _M_bucket_index(const _Key&, _Hash_code_type __c,
00794               std::size_t __n) const
00795       { return _M_h2(__c, __n); }
00796 
00797       std::size_t
00798       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00799               std::size_t __n) const
00800       { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
00801 
00802       bool
00803       _M_compare(const _Key& __k, _Hash_code_type,
00804          _Hash_node<_Value, false>* __n) const
00805       { return _M_eq(__k, _M_extract(__n->_M_v)); }
00806 
00807       void
00808       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00809       { }
00810 
00811       void
00812       _M_copy_code(_Hash_node<_Value, false>*,
00813            const _Hash_node<_Value, false>*) const
00814       { }
00815 
00816       void
00817       _M_swap(_Hash_code_base& __x)
00818       {
00819     std::swap(_M_extract, __x._M_extract);
00820     std::swap(_M_eq, __x._M_eq);
00821     std::swap(_M_h1, __x._M_h1);
00822     std::swap(_M_h2, __x._M_h2);
00823       }
00824 
00825     protected:
00826       _ExtractKey  _M_extract;
00827       _Equal       _M_eq;
00828       _H1          _M_h1;
00829       _H2          _M_h2;
00830     };
00831 
00832   // Specialization: hash function and range-hashing function, 
00833   // caching hash codes.  H is provided but ignored.  Provides
00834   // typedef and accessor required by TR1.
00835   template<typename _Key, typename _Value,
00836        typename _ExtractKey, typename _Equal,
00837        typename _H1, typename _H2>
00838     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00839                _Default_ranged_hash, true>
00840     {
00841       typedef _H1 hasher;
00842       
00843       hasher
00844       hash_function() const
00845       { return _M_h1; }
00846 
00847     protected:
00848       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00849               const _H1& __h1, const _H2& __h2,
00850               const _Default_ranged_hash&)
00851       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00852 
00853       typedef std::size_t _Hash_code_type;
00854   
00855       _Hash_code_type
00856       _M_hash_code(const _Key& __k) const
00857       { return _M_h1(__k); }
00858   
00859       std::size_t
00860       _M_bucket_index(const _Key&, _Hash_code_type __c,
00861               std::size_t __n) const
00862       { return _M_h2(__c, __n); }
00863 
00864       std::size_t
00865       _M_bucket_index(const _Hash_node<_Value, true>* __p,
00866               std::size_t __n) const
00867       { return _M_h2(__p->_M_hash_code, __n); }
00868 
00869       bool
00870       _M_compare(const _Key& __k, _Hash_code_type __c,
00871          _Hash_node<_Value, true>* __n) const
00872       { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
00873 
00874       void
00875       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
00876       { __n->_M_hash_code = __c; }
00877 
00878       void
00879       _M_copy_code(_Hash_node<_Value, true>* __to,
00880            const _Hash_node<_Value, true>* __from) const
00881       { __to->_M_hash_code = __from->_M_hash_code; }
00882 
00883       void
00884       _M_swap(_Hash_code_base& __x)
00885       {
00886     std::swap(_M_extract, __x._M_extract);
00887     std::swap(_M_eq, __x._M_eq);
00888     std::swap(_M_h1, __x._M_h1);
00889     std::swap(_M_h2, __x._M_h2);
00890       }
00891       
00892     protected:
00893       _ExtractKey  _M_extract;
00894       _Equal       _M_eq;
00895       _H1          _M_h1;
00896       _H2          _M_h2;
00897     };
00898 } // namespace __detail
00899 _GLIBCXX_END_NAMESPACE
00900 } // namespace std::tr1
00901 
00902 #endif // _TR1_HASHTABLE_POLICY_H
00903 

Generated on Thu Nov 1 13:11:58 2007 for libstdc++ by  doxygen 1.5.1