contrib/libstdc++/include/tr1/hashtable_policy.h

   1 // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file tr1/hashtable_policy.h
  31  *  This is a TR1 C++ Library header.
  32  */
  33
  34 #ifndef _TR1_HASHTABLE_POLICY_H
  35 #define _TR1_HASHTABLE_POLICY_H 1
  36
  37 #include <functional> // _Identity, _Select1st
  38 #include <tr1/utility>
  39 #include <ext/type_traits.h>
  40
  41 namespace std
  42 {
  43 _GLIBCXX_BEGIN_NAMESPACE(tr1)
  44 namespace __detail
  45 {
  46   // Helper function: return distance(first, last) for forward
  47   // iterators, or 0 for input iterators.
  48   template<class _Iterator>
  49     inline typename std::iterator_traits<_Iterator>::difference_type
  50     __distance_fw(_Iterator __first, _Iterator __last,
  51                   std::input_iterator_tag)
  52     { return 0; }
  53
  54   template<class _Iterator>
  55     inline typename std::iterator_traits<_Iterator>::difference_type
  56     __distance_fw(_Iterator __first, _Iterator __last,
  57                   std::forward_iterator_tag)
  58     { return std::distance(__first, __last); }
  59
  60   template<class _Iterator>
  61     inline typename std::iterator_traits<_Iterator>::difference_type
  62     __distance_fw(_Iterator __first, _Iterator __last)
  63     {
  64       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
  65       return __distance_fw(__first, __last, _Tag());
  66     }
  67
  68   // XXX This is a hack.  _Prime_rehash_policy's member functions, and
  69   // certainly the list of primes, should be defined in a .cc file.
  70   // We're temporarily putting them in a header because we don't have a
  71   // place to put TR1 .cc files yet.  There's no good reason for any of
  72   // _Prime_rehash_policy's member functions to be inline, and there's
  73   // certainly no good reason for _Primes<> to exist at all.
  74   struct _LessThan
  75   {
  76     template<typename _Tp, typename _Up>
  77       bool
  78       operator()(_Tp __x, _Up __y)
  79       { return __x < __y; }
  80   };
  81
  82   template<int __ulongsize = sizeof(unsigned long)>
  83     struct _Primes
  84     {
  85       static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48;
  86       static const unsigned long __primes[256 + 48 + 1];
  87     };
  88
  89   template<int __ulongsize>
  90     const int _Primes<__ulongsize>::__n_primes;
  91
  92   template<int __ulongsize>
  93     const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] =
  94     {
  95       2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
  96       37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
  97       83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
  98       157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
  99       277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
 100       503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
 101       953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
 102       1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
 103       3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
 104       5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
 105       11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
 106       19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
 107       33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
 108       57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
 109       99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
 110       159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
 111       256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
 112       410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
 113       658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
 114       1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
 115       1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
 116       2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
 117       4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
 118       6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
 119       11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
 120       16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
 121       24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
 122       36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
 123       54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
 124       80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
 125       118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
 126       176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
 127       260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
 128       386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
 129       573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
 130       849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
 131       1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
 132       1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
 133       2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
 134       3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
 135       4294967291ul,
 136       // Sentinel, so we don't have to test the result of lower_bound,
 137       // or, on 64-bit machines, rest of the table.
 138       __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull,
 139       (unsigned long)8589934583ull,
 140       (unsigned long)12884901857ull, (unsigned long)17179869143ull,
 141       (unsigned long)25769803693ull, (unsigned long)34359738337ull,
 142       (unsigned long)51539607367ull, (unsigned long)68719476731ull,
 143       (unsigned long)103079215087ull, (unsigned long)137438953447ull,
 144       (unsigned long)206158430123ull, (unsigned long)274877906899ull,
 145       (unsigned long)412316860387ull, (unsigned long)549755813881ull,
 146       (unsigned long)824633720731ull, (unsigned long)1099511627689ull,
 147       (unsigned long)1649267441579ull, (unsigned long)2199023255531ull,
 148       (unsigned long)3298534883309ull, (unsigned long)4398046511093ull,
 149       (unsigned long)6597069766607ull, (unsigned long)8796093022151ull,
 150       (unsigned long)13194139533241ull, (unsigned long)17592186044399ull,
 151       (unsigned long)26388279066581ull, (unsigned long)35184372088777ull,
 152       (unsigned long)52776558133177ull, (unsigned long)70368744177643ull,
 153       (unsigned long)105553116266399ull, (unsigned long)140737488355213ull,
 154       (unsigned long)211106232532861ull, (unsigned long)281474976710597ull,
 155       (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull,
 156       (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull,
 157       (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull,
 158       (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull,
 159       (unsigned long)144115188075855859ull,
 160       (unsigned long)288230376151711717ull,
 161       (unsigned long)576460752303423433ull,
 162       (unsigned long)1152921504606846883ull,
 163       (unsigned long)2305843009213693951ull,
 164       (unsigned long)4611686018427387847ull,
 165       (unsigned long)9223372036854775783ull,
 166       (unsigned long)18446744073709551557ull,
 167       (unsigned long)18446744073709551557ull
 168     };
 169
 170   // Auxiliary types used for all instantiations of _Hashtable: nodes
 171   // and iterators.
 172
 173   // Nodes, used to wrap elements stored in the hash table.  A policy
 174   // template parameter of class template _Hashtable controls whether
 175   // nodes also store a hash code. In some cases (e.g. strings) this
 176   // may be a performance win.
 177   template<typename _Value, bool __cache_hash_code>
 178     struct _Hash_node;
 179
 180   template<typename _Value>
 181     struct _Hash_node<_Value, true>
 182     {
 183       _Value       _M_v;
 184       std::size_t  _M_hash_code;
 185       _Hash_node*  _M_next;
 186     };
 187
 188   template<typename _Value>
 189     struct _Hash_node<_Value, false>
 190     {
 191       _Value       _M_v;
 192       _Hash_node*  _M_next;
 193     };
 194
 195   // Local iterators, used to iterate within a bucket but not between
 196   // buckets.
 197   template<typename _Value, bool __cache>
 198     struct _Node_iterator_base
 199     {
 200       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
 201       : _M_cur(__p) { }
 202
 203       void
 204       _M_incr()
 205       { _M_cur = _M_cur->_M_next; }
 206
 207       _Hash_node<_Value, __cache>*  _M_cur;
 208     };
 209
 210   template<typename _Value, bool __cache>
 211     inline bool
 212     operator==(const _Node_iterator_base<_Value, __cache>& __x,
 213                const _Node_iterator_base<_Value, __cache>& __y)
 214     { return __x._M_cur == __y._M_cur; }
 215
 216   template<typename _Value, bool __cache>
 217     inline bool
 218     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
 219                const _Node_iterator_base<_Value, __cache>& __y)
 220     { return __x._M_cur != __y._M_cur; }
 221
 222   template<typename _Value, bool __constant_iterators, bool __cache>
 223     struct _Node_iterator
 224     : public _Node_iterator_base<_Value, __cache>
 225     {
 226       typedef _Value                                   value_type;
 227       typedef typename
 228       __gnu_cxx::__conditional_type<__constant_iterators,
 229                                     const _Value*, _Value*>::__type
 230                                                        pointer;
 231       typedef typename
 232       __gnu_cxx::__conditional_type<__constant_iterators,
 233                                     const _Value&, _Value&>::__type
 234                                                        reference;
 235       typedef std::ptrdiff_t                           difference_type;
 236       typedef std::forward_iterator_tag                iterator_category;
 237
 238       _Node_iterator()
 239       : _Node_iterator_base<_Value, __cache>(0) { }
 240
 241       explicit
 242       _Node_iterator(_Hash_node<_Value, __cache>* __p)
 243       : _Node_iterator_base<_Value, __cache>(__p) { }
 244
 245       reference
 246       operator*() const
 247       { return this->_M_cur->_M_v; }
 248
 249       pointer
 250       operator->() const
 251       { return &this->_M_cur->_M_v; }
 252
 253       _Node_iterator&
 254       operator++()
 255       {
 256         this->_M_incr();
 257         return *this;
 258       }
 259
 260       _Node_iterator
 261       operator++(int)
 262       {
 263         _Node_iterator __tmp(*this);
 264         this->_M_incr();
 265         return __tmp;
 266       }
 267     };
 268
 269   template<typename _Value, bool __constant_iterators, bool __cache>
 270     struct _Node_const_iterator
 271     : public _Node_iterator_base<_Value, __cache>
 272     {
 273       typedef _Value                                   value_type;
 274       typedef const _Value*                            pointer;
 275       typedef const _Value&                            reference;
 276       typedef std::ptrdiff_t                           difference_type;
 277       typedef std::forward_iterator_tag                iterator_category;
 278
 279       _Node_const_iterator()
 280       : _Node_iterator_base<_Value, __cache>(0) { }
 281
 282       explicit
 283       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
 284       : _Node_iterator_base<_Value, __cache>(__p) { }
 285
 286       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
 287                            __cache>& __x)
 288       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
 289
 290       reference
 291       operator*() const
 292       { return this->_M_cur->_M_v; }
 293
 294       pointer
 295       operator->() const
 296       { return &this->_M_cur->_M_v; }
 297
 298       _Node_const_iterator&
 299       operator++()
 300       {
 301         this->_M_incr();
 302         return *this;
 303       }
 304
 305       _Node_const_iterator
 306       operator++(int)
 307       {
 308         _Node_const_iterator __tmp(*this);
 309         this->_M_incr();
 310         return __tmp;
 311       }
 312     };
 313
 314   template<typename _Value, bool __cache>
 315     struct _Hashtable_iterator_base
 316     {
 317       _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
 318                                _Hash_node<_Value, __cache>** __bucket)
 319       : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
 320
 321       void
 322       _M_incr()
 323       {
 324         _M_cur_node = _M_cur_node->_M_next;
 325         if (!_M_cur_node)
 326           _M_incr_bucket();
 327       }
 328
 329       void
 330       _M_incr_bucket();
 331
 332       _Hash_node<_Value, __cache>*   _M_cur_node;
 333       _Hash_node<_Value, __cache>**  _M_cur_bucket;
 334     };
 335
 336   // Global iterators, used for arbitrary iteration within a hash
 337   // table.  Larger and more expensive than local iterators.
 338   template<typename _Value, bool __cache>
 339     void
 340     _Hashtable_iterator_base<_Value, __cache>::
 341     _M_incr_bucket()
 342     {
 343       ++_M_cur_bucket;
 344
 345       // This loop requires the bucket array to have a non-null sentinel.
 346       while (!*_M_cur_bucket)
 347         ++_M_cur_bucket;
 348       _M_cur_node = *_M_cur_bucket;
 349     }
 350
 351   template<typename _Value, bool __cache>
 352     inline bool
 353     operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
 354                const _Hashtable_iterator_base<_Value, __cache>& __y)
 355     { return __x._M_cur_node == __y._M_cur_node; }
 356
 357   template<typename _Value, bool __cache>
 358     inline bool
 359     operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
 360                const _Hashtable_iterator_base<_Value, __cache>& __y)
 361     { return __x._M_cur_node != __y._M_cur_node; }
 362
 363   template<typename _Value, bool __constant_iterators, bool __cache>
 364     struct _Hashtable_iterator
 365     : public _Hashtable_iterator_base<_Value, __cache>
 366     {
 367       typedef _Value                                   value_type;
 368       typedef typename
 369       __gnu_cxx::__conditional_type<__constant_iterators,
 370                                     const _Value*, _Value*>::__type
 371                                                        pointer;
 372       typedef typename
 373       __gnu_cxx::__conditional_type<__constant_iterators,
 374                                     const _Value&, _Value&>::__type
 375                                                        reference;
 376       typedef std::ptrdiff_t                           difference_type;
 377       typedef std::forward_iterator_tag                iterator_category;
 378
 379       _Hashtable_iterator()
 380       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
 381
 382       _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
 383                           _Hash_node<_Value, __cache>** __b)
 384       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
 385
 386       explicit
 387       _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
 388       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
 389
 390       reference
 391       operator*() const
 392       { return this->_M_cur_node->_M_v; }
 393
 394       pointer
 395       operator->() const
 396       { return &this->_M_cur_node->_M_v; }
 397
 398       _Hashtable_iterator&
 399       operator++()
 400       {
 401         this->_M_incr();
 402         return *this;
 403       }
 404
 405       _Hashtable_iterator
 406       operator++(int)
 407       {
 408         _Hashtable_iterator __tmp(*this);
 409         this->_M_incr();
 410         return __tmp;
 411       }
 412     };
 413
 414   template<typename _Value, bool __constant_iterators, bool __cache>
 415     struct _Hashtable_const_iterator
 416     : public _Hashtable_iterator_base<_Value, __cache>
 417     {
 418       typedef _Value                                   value_type;
 419       typedef const _Value*                            pointer;
 420       typedef const _Value&                            reference;
 421       typedef std::ptrdiff_t                           difference_type;
 422       typedef std::forward_iterator_tag                iterator_category;
 423
 424       _Hashtable_const_iterator()
 425       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
 426
 427       _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
 428                                 _Hash_node<_Value, __cache>** __b)
 429       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
 430
 431       explicit
 432       _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
 433       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
 434
 435       _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
 436                                 __constant_iterators, __cache>& __x)
 437       : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
 438                                                   __x._M_cur_bucket) { }
 439
 440       reference
 441       operator*() const
 442       { return this->_M_cur_node->_M_v; }
 443
 444       pointer
 445       operator->() const
 446       { return &this->_M_cur_node->_M_v; }
 447
 448       _Hashtable_const_iterator&
 449       operator++()
 450       {
 451         this->_M_incr();
 452         return *this;
 453       }
 454
 455       _Hashtable_const_iterator
 456       operator++(int)
 457       {
 458         _Hashtable_const_iterator __tmp(*this);
 459         this->_M_incr();
 460         return __tmp;
 461       }
 462     };
 463
 464
 465   // Many of class template _Hashtable's template parameters are policy
 466   // classes.  These are defaults for the policies.
 467
 468   // Default range hashing function: use division to fold a large number
 469   // into the range [0, N).
 470   struct _Mod_range_hashing
 471   {
 472     typedef std::size_t first_argument_type;
 473     typedef std::size_t second_argument_type;
 474     typedef std::size_t result_type;
 475
 476     result_type
 477     operator()(first_argument_type __num, second_argument_type __den) const
 478     { return __num % __den; }
 479   };
 480
 481   // Default ranged hash function H.  In principle it should be a
 482   // function object composed from objects of type H1 and H2 such that
 483   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
 484   // h1 and h2.  So instead we'll just use a tag to tell class template
 485   // hashtable to do that composition.
 486   struct _Default_ranged_hash { };
 487
 488   // Default value for rehash policy.  Bucket size is (usually) the
 489   // smallest prime that keeps the load factor small enough.
 490   struct _Prime_rehash_policy
 491   {
 492     _Prime_rehash_policy(float __z = 1.0);
 493
 494     float
 495     max_load_factor() const;
 496
 497     // Return a bucket size no smaller than n.
 498     std::size_t
 499     _M_next_bkt(std::size_t __n) const;
 500
 501     // Return a bucket count appropriate for n elements
 502     std::size_t
 503     _M_bkt_for_elements(std::size_t __n) const;
 504
 505     // __n_bkt is current bucket count, __n_elt is current element count,
 506     // and __n_ins is number of elements to be inserted.  Do we need to
 507     // increase bucket count?  If so, return make_pair(true, n), where n
 508     // is the new bucket count.  If not, return make_pair(false, 0).
 509     std::pair<bool, std::size_t>
 510     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 511                    std::size_t __n_ins) const;
 512
 513     float                _M_max_load_factor;
 514     float                _M_growth_factor;
 515     mutable std::size_t  _M_next_resize;
 516   };
 517
 518   inline
 519   _Prime_rehash_policy::
 520   _Prime_rehash_policy(float __z)
 521   : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0)
 522   { }
 523
 524   inline float
 525   _Prime_rehash_policy::
 526   max_load_factor() const
 527   { return _M_max_load_factor; }
 528
 529   // Return a prime no smaller than n.
 530   inline std::size_t
 531   _Prime_rehash_policy::
 532   _M_next_bkt(std::size_t __n) const
 533   {
 534     const unsigned long* const __last = (_Primes<>::__primes
 535                                          + _Primes<>::__n_primes);
 536     const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
 537                                                 __n);
 538     _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
 539                                                         * _M_max_load_factor));
 540     return *__p;
 541   }
 542
 543   // Return the smallest prime p such that alpha p >= n, where alpha
 544   // is the load factor.
 545   inline std::size_t
 546   _Prime_rehash_policy::
 547   _M_bkt_for_elements(std::size_t __n) const
 548   {
 549     const unsigned long* const __last = (_Primes<>::__primes
 550                                          + _Primes<>::__n_primes);
 551     const float __min_bkts = __n / _M_max_load_factor;
 552     const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
 553                                                 __min_bkts, _LessThan());
 554     _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
 555                                                         * _M_max_load_factor));
 556     return *__p;
 557   }
 558
 559   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
 560   // If p > __n_bkt, return make_pair(true, p); otherwise return
 561   // make_pair(false, 0).  In principle this isn't very different from
 562   // _M_bkt_for_elements.
 563
 564   // The only tricky part is that we're caching the element count at
 565   // which we need to rehash, so we don't have to do a floating-point
 566   // multiply for every insertion.
 567
 568   inline std::pair<bool, std::size_t>
 569   _Prime_rehash_policy::
 570   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
 571                  std::size_t __n_ins) const
 572   {
 573     if (__n_elt + __n_ins > _M_next_resize)
 574       {
 575         float __min_bkts = ((float(__n_ins) + float(__n_elt))
 576                             / _M_max_load_factor);
 577         if (__min_bkts > __n_bkt)
 578           {
 579             __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
 580             const unsigned long* const __last = (_Primes<>::__primes
 581                                                  + _Primes<>::__n_primes);
 582             const unsigned long* __p = std::lower_bound(_Primes<>::__primes,
 583                                                         __last, __min_bkts,
 584                                                         _LessThan());
 585             _M_next_resize =
 586               static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor));
 587             return std::make_pair(true, *__p);
 588           }
 589         else
 590           {
 591             _M_next_resize =
 592               static_cast<std::size_t>(std::ceil(__n_bkt
 593                                                  * _M_max_load_factor));
 594             return std::make_pair(false, 0);
 595           }
 596       }
 597     else
 598       return std::make_pair(false, 0);
 599   }
 600
 601   // Base classes for std::tr1::_Hashtable.  We define these base
 602   // classes because in some cases we want to do different things
 603   // depending on the value of a policy class.  In some cases the
 604   // policy class affects which member functions and nested typedefs
 605   // are defined; we handle that by specializing base class templates.
 606   // Several of the base class templates need to access other members
 607   // of class template _Hashtable, so we use the "curiously recurring
 608   // template pattern" for them.
 609
 610   // class template _Map_base.  If the hashtable has a value type of the
 611   // form pair<T1, T2> and a key extraction policy that returns the
 612   // first part of the pair, the hashtable gets a mapped_type typedef.
 613   // If it satisfies those criteria and also has unique keys, then it
 614   // also gets an operator[].
 615   template<typename _Key, typename _Value, typename _Ex, bool __unique,
 616            typename _Hashtable>
 617     struct _Map_base { };
 618
 619   template<typename _Key, typename _Pair, typename _Hashtable>
 620     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
 621     {
 622       typedef typename _Pair::second_type mapped_type;
 623     };
 624
 625   template<typename _Key, typename _Pair, typename _Hashtable>
 626   struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
 627     {
 628       typedef typename _Pair::second_type mapped_type;
 629
 630       mapped_type&
 631       operator[](const _Key& __k);
 632     };
 633
 634   template<typename _Key, typename _Pair, typename _Hashtable>
 635     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
 636                        true, _Hashtable>::mapped_type&
 637     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
 638     operator[](const _Key& __k)
 639     {
 640       _Hashtable* __h = static_cast<_Hashtable*>(this);
 641       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
 642       std::size_t __n = __h->_M_bucket_index(__k, __code,
 643                                              __h->_M_bucket_count);
 644
 645       typename _Hashtable::_Node* __p =
 646         __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
 647       if (!__p)
 648         return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
 649                                      __n, __code)->second;
 650       return (__p->_M_v).second;
 651     }
 652
 653   // class template _Rehash_base.  Give hashtable the max_load_factor
 654   // functions iff the rehash policy is _Prime_rehash_policy.
 655   template<typename _RehashPolicy, typename _Hashtable>
 656     struct _Rehash_base { };
 657
 658   template<typename _Hashtable>
 659     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
 660     {
 661       float
 662       max_load_factor() const
 663       {
 664         const _Hashtable* __this = static_cast<const _Hashtable*>(this);
 665         return __this->__rehash_policy().max_load_factor();
 666       }
 667
 668       void
 669       max_load_factor(float __z)
 670       {
 671         _Hashtable* __this = static_cast<_Hashtable*>(this);
 672         __this->__rehash_policy(_Prime_rehash_policy(__z));
 673       }
 674     };
 675
 676   // Class template _Hash_code_base.  Encapsulates two policy issues that
 677   // aren't quite orthogonal.
 678   //   (1) the difference between using a ranged hash function and using
 679   //       the combination of a hash function and a range-hashing function.
 680   //       In the former case we don't have such things as hash codes, so
 681   //       we have a dummy type as placeholder.
 682   //   (2) Whether or not we cache hash codes.  Caching hash codes is
 683   //       meaningless if we have a ranged hash function.
 684   // We also put the key extraction and equality comparison function
 685   // objects here, for convenience.
 686
 687   // Primary template: unused except as a hook for specializations.
 688   template<typename _Key, typename _Value,
 689            typename _ExtractKey, typename _Equal,
 690            typename _H1, typename _H2, typename _Hash,
 691            bool __cache_hash_code>
 692     struct _Hash_code_base;
 693
 694   // Specialization: ranged hash function, no caching hash codes.  H1
 695   // and H2 are provided but ignored.  We define a dummy hash code type.
 696   template<typename _Key, typename _Value,
 697            typename _ExtractKey, typename _Equal,
 698            typename _H1, typename _H2, typename _Hash>
 699     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
 700                            _Hash, false>
 701     {
 702     protected:
 703       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
 704                       const _H1&, const _H2&, const _Hash& __h)
 705       : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
 706
 707       typedef void* _Hash_code_type;
 708
 709       _Hash_code_type
 710       _M_hash_code(const _Key& __key) const
 711       { return 0; }
 712
 713       std::size_t
 714       _M_bucket_index(const _Key& __k, _Hash_code_type,
 715                       std::size_t __n) const
 716       { return _M_ranged_hash(__k, __n); }
 717
 718       std::size_t
 719       _M_bucket_index(const _Hash_node<_Value, false>* __p,
 720                       std::size_t __n) const
 721       { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
 722
 723       bool
 724       _M_compare(const _Key& __k, _Hash_code_type,
 725                  _Hash_node<_Value, false>* __n) const
 726       { return _M_eq(__k, _M_extract(__n->_M_v)); }
 727
 728       void
 729       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
 730       { }
 731
 732       void
 733       _M_copy_code(_Hash_node<_Value, false>*,
 734                    const _Hash_node<_Value, false>*) const
 735       { }
 736
 737       void
 738       _M_swap(_Hash_code_base& __x)
 739       {
 740         std::swap(_M_extract, __x._M_extract);
 741         std::swap(_M_eq, __x._M_eq);
 742         std::swap(_M_ranged_hash, __x._M_ranged_hash);
 743       }
 744
 745     protected:
 746       _ExtractKey  _M_extract;
 747       _Equal       _M_eq;
 748       _Hash        _M_ranged_hash;
 749     };
 750
 751
 752   // No specialization for ranged hash function while caching hash codes.
 753   // That combination is meaningless, and trying to do it is an error.
 754
 755
 756   // Specialization: ranged hash function, cache hash codes.  This
 757   // combination is meaningless, so we provide only a declaration
 758   // and no definition.
 759   template<typename _Key, typename _Value,
 760            typename _ExtractKey, typename _Equal,
 761            typename _H1, typename _H2, typename _Hash>
 762     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
 763                            _Hash, true>;
 764
 765   // Specialization: hash function and range-hashing function, no
 766   // caching of hash codes.  H is provided but ignored.  Provides
 767   // typedef and accessor required by TR1.
 768   template<typename _Key, typename _Value,
 769            typename _ExtractKey, typename _Equal,
 770            typename _H1, typename _H2>
 771     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
 772                            _Default_ranged_hash, false>
 773     {
 774       typedef _H1 hasher;
 775
 776       hasher
 777       hash_function() const
 778       { return _M_h1; }
 779
 780     protected:
 781       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
 782                       const _H1& __h1, const _H2& __h2,
 783                       const _Default_ranged_hash&)
 784       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
 785
 786       typedef std::size_t _Hash_code_type;
 787
 788       _Hash_code_type
 789       _M_hash_code(const _Key& __k) const
 790       { return _M_h1(__k); }
 791
 792       std::size_t
 793       _M_bucket_index(const _Key&, _Hash_code_type __c,
 794                       std::size_t __n) const
 795       { return _M_h2(__c, __n); }
 796
 797       std::size_t
 798       _M_bucket_index(const _Hash_node<_Value, false>* __p,
 799                       std::size_t __n) const
 800       { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
 801
 802       bool
 803       _M_compare(const _Key& __k, _Hash_code_type,
 804                  _Hash_node<_Value, false>* __n) const
 805       { return _M_eq(__k, _M_extract(__n->_M_v)); }
 806
 807       void
 808       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
 809       { }
 810
 811       void
 812       _M_copy_code(_Hash_node<_Value, false>*,
 813                    const _Hash_node<_Value, false>*) const
 814       { }
 815
 816       void
 817       _M_swap(_Hash_code_base& __x)
 818       {
 819         std::swap(_M_extract, __x._M_extract);
 820         std::swap(_M_eq, __x._M_eq);
 821         std::swap(_M_h1, __x._M_h1);
 822         std::swap(_M_h2, __x._M_h2);
 823       }
 824
 825     protected:
 826       _ExtractKey  _M_extract;
 827       _Equal       _M_eq;
 828       _H1          _M_h1;
 829       _H2          _M_h2;
 830     };
 831
 832   // Specialization: hash function and range-hashing function,
 833   // caching hash codes.  H is provided but ignored.  Provides
 834   // typedef and accessor required by TR1.
 835   template<typename _Key, typename _Value,
 836            typename _ExtractKey, typename _Equal,
 837            typename _H1, typename _H2>
 838     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
 839                            _Default_ranged_hash, true>
 840     {
 841       typedef _H1 hasher;
 842
 843       hasher
 844       hash_function() const
 845       { return _M_h1; }
 846
 847     protected:
 848       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
 849                       const _H1& __h1, const _H2& __h2,
 850                       const _Default_ranged_hash&)
 851       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
 852
 853       typedef std::size_t _Hash_code_type;
 854
 855       _Hash_code_type
 856       _M_hash_code(const _Key& __k) const
 857       { return _M_h1(__k); }
 858
 859       std::size_t
 860       _M_bucket_index(const _Key&, _Hash_code_type __c,
 861                       std::size_t __n) const
 862       { return _M_h2(__c, __n); }
 863
 864       std::size_t
 865       _M_bucket_index(const _Hash_node<_Value, true>* __p,
 866                       std::size_t __n) const
 867       { return _M_h2(__p->_M_hash_code, __n); }
 868
 869       bool
 870       _M_compare(const _Key& __k, _Hash_code_type __c,
 871                  _Hash_node<_Value, true>* __n) const
 872       { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
 873
 874       void
 875       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
 876       { __n->_M_hash_code = __c; }
 877
 878       void
 879       _M_copy_code(_Hash_node<_Value, true>* __to,
 880                    const _Hash_node<_Value, true>* __from) const
 881       { __to->_M_hash_code = __from->_M_hash_code; }
 882
 883       void
 884       _M_swap(_Hash_code_base& __x)
 885       {
 886         std::swap(_M_extract, __x._M_extract);
 887         std::swap(_M_eq, __x._M_eq);
 888         std::swap(_M_h1, __x._M_h1);
 889         std::swap(_M_h2, __x._M_h2);
 890       }
 891
 892     protected:
 893       _ExtractKey  _M_extract;
 894       _Equal       _M_eq;
 895       _H1          _M_h1;
 896       _H2          _M_h2;
 897     };
 898 } // namespace __detail
 899 _GLIBCXX_END_NAMESPACE
 900 } // namespace std::tr1
 901
 902 #endif // _TR1_HASHTABLE_POLICY_H
 903