# 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