hashtable.cc: New.

2007-12-03  Paolo Carlini  <pcarlini@suse.de>

	* src/hashtable.cc: New.
	* src/hashtable_c++0x.cc: Likewise.
	* src/Makefile.am: Add.
	* src/Makefile.in: Regenerate.
	* include/tr1_impl/hashtable_policy.h (struct _Primes): Remove.
	(_Prime_rehash_policy::_M_next_bkt, _M_bkt_for_elements,
	_M_need_rehash): Adjust.
	* config/abi/pre/gnu.ver: Update exports.

	* src/hash.cc: Minor tweak.

From-SVN: r130585

1 files changed, 20 insertions, 119 deletions

diff --git a/libstdc++-v3/include/tr1_impl/hashtable_policy.h b/libstdc++-v3/include/tr1_impl/hashtable_policy.h
index 5c48504..a636125 100644
--- a/libstdc++-v3/include/tr1_impl/hashtable_policy.h
+++ b/libstdc++-v3/include/tr1_impl/hashtable_policy.h
@@ -60,99 +60,6 @@ namespace __detail
       return __distance_fw(__first, __last, _Tag());
     }
 
-  // XXX This is a hack.  _Prime_rehash_policy's member functions, and
-  // certainly the list of primes, should be defined in a .cc file.
-  // We're temporarily putting them in a header because we don't have a
-  // place to put TR1 .cc files yet.  There's no good reason for any of
-  // _Prime_rehash_policy's member functions to be inline, and there's
-  // certainly no good reason for _Primes<> to exist at all.  
-  template<int __ulongsize = sizeof(unsigned long)>
-    struct _Primes
-    {
-      static const int __n_primes = __ulongsize != 8 ? 256 : 256 + 48;
-      static const unsigned long __primes[256 + 48 + 1];
-    };
-
-  template<int __ulongsize>
-    const int _Primes<__ulongsize>::__n_primes;
-
-  template<int __ulongsize>
-    const unsigned long _Primes<__ulongsize>::__primes[256 + 48 + 1] =
-    {
-      2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
-      37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
-      83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
-      157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
-      277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
-      503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
-      953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
-      1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
-      3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
-      5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
-      11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
-      19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
-      33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
-      57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
-      99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
-      159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
-      256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
-      410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
-      658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
-      1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
-      1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
-      2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
-      4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
-      6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
-      11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
-      16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
-      24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
-      36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
-      54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
-      80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
-      118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
-      176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
-      260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
-      386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
-      573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
-      849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
-      1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
-      1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
-      2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
-      3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
-      4294967291ul,
-      // Sentinel, so we don't have to test the result of lower_bound,
-      // or, on 64-bit machines, rest of the table.
-      __ulongsize != 8 ? 4294967291ul : (unsigned long)6442450933ull,
-      (unsigned long)8589934583ull,
-      (unsigned long)12884901857ull, (unsigned long)17179869143ull,
-      (unsigned long)25769803693ull, (unsigned long)34359738337ull,
-      (unsigned long)51539607367ull, (unsigned long)68719476731ull,
-      (unsigned long)103079215087ull, (unsigned long)137438953447ull,
-      (unsigned long)206158430123ull, (unsigned long)274877906899ull,
-      (unsigned long)412316860387ull, (unsigned long)549755813881ull,
-      (unsigned long)824633720731ull, (unsigned long)1099511627689ull,
-      (unsigned long)1649267441579ull, (unsigned long)2199023255531ull,
-      (unsigned long)3298534883309ull, (unsigned long)4398046511093ull,
-      (unsigned long)6597069766607ull, (unsigned long)8796093022151ull,
-      (unsigned long)13194139533241ull, (unsigned long)17592186044399ull,
-      (unsigned long)26388279066581ull, (unsigned long)35184372088777ull,
-      (unsigned long)52776558133177ull, (unsigned long)70368744177643ull,
-      (unsigned long)105553116266399ull, (unsigned long)140737488355213ull,
-      (unsigned long)211106232532861ull, (unsigned long)281474976710597ull,
-      (unsigned long)562949953421231ull, (unsigned long)1125899906842597ull,
-      (unsigned long)2251799813685119ull, (unsigned long)4503599627370449ull,
-      (unsigned long)9007199254740881ull, (unsigned long)18014398509481951ull,
-      (unsigned long)36028797018963913ull, (unsigned long)72057594037927931ull,
-      (unsigned long)144115188075855859ull,
-      (unsigned long)288230376151711717ull,
-      (unsigned long)576460752303423433ull,
-      (unsigned long)1152921504606846883ull,
-      (unsigned long)2305843009213693951ull,
-      (unsigned long)4611686018427387847ull,
-      (unsigned long)9223372036854775783ull,
-      (unsigned long)18446744073709551557ull,
-      (unsigned long)18446744073709551557ull
-    };
 
   // Auxiliary types used for all instantiations of _Hashtable: nodes
   // and iterators.
@@ -476,10 +383,12 @@ namespace __detail
   // smallest prime that keeps the load factor small enough.
   struct _Prime_rehash_policy
   {
-    _Prime_rehash_policy(float __z = 1.0);
+    _Prime_rehash_policy(float __z = 1.0)
+    : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
 
     float
-    max_load_factor() const;
+    max_load_factor() const
+    { return _M_max_load_factor; }      
 
     // Return a bucket size no smaller than n.
     std::size_t
@@ -502,26 +411,19 @@ namespace __detail
     mutable std::size_t  _M_next_resize;
   };
 
-  inline
-  _Prime_rehash_policy::
-  _Prime_rehash_policy(float __z)
-  : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0)
-  { }
+  extern const unsigned long __prime_list[];
 
-  inline float
-  _Prime_rehash_policy::
-  max_load_factor() const
-  { return _M_max_load_factor; }
+  // XXX This is a hack.  There's no good reason for any of
+  // _Prime_rehash_policy's member functions to be inline.  
 
   // Return a prime no smaller than n.
   inline std::size_t
   _Prime_rehash_policy::
   _M_next_bkt(std::size_t __n) const
   {
-    const unsigned long* const __last = (_Primes<>::__primes
-					 + _Primes<>::__n_primes);
-    const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
-						__n);
+    const int __n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48; 
+    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+						+ __n_primes, __n);
     _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
 							* _M_max_load_factor));
     return *__p;
@@ -533,11 +435,10 @@ namespace __detail
   _Prime_rehash_policy::
   _M_bkt_for_elements(std::size_t __n) const
   {
-    const unsigned long* const __last = (_Primes<>::__primes
-					 + _Primes<>::__n_primes);
+    const int __n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48; 
     const float __min_bkts = __n / _M_max_load_factor;
-    const unsigned long* __p = std::lower_bound(_Primes<>::__primes, __last,
-						__min_bkts);
+    const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
+						+ __n_primes, __min_bkts);
     _M_next_resize = static_cast<std::size_t>(std::ceil(*__p
 							* _M_max_load_factor));
     return *__p;
@@ -547,11 +448,11 @@ namespace __detail
   // If p > __n_bkt, return make_pair(true, p); otherwise return
   // make_pair(false, 0).  In principle this isn't very different from 
   // _M_bkt_for_elements.
-  
+
   // The only tricky part is that we're caching the element count at
   // which we need to rehash, so we don't have to do a floating-point
   // multiply for every insertion.
-  
+
   inline std::pair<bool, std::size_t>
   _Prime_rehash_policy::
   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
@@ -564,11 +465,11 @@ namespace __detail
 	if (__min_bkts > __n_bkt)
 	  {
 	    __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
-	    const unsigned long* const __last = (_Primes<>::__primes
-						 + _Primes<>::__n_primes);
-	    const unsigned long* __p = std::lower_bound(_Primes<>::__primes,
-							__last, __min_bkts);
-	    _M_next_resize = 
+	    const int __n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48; 
+	    const unsigned long* __p =
+	      std::lower_bound(__prime_list, __prime_list + __n_primes,
+			       __min_bkts);
+	    _M_next_resize =
 	      static_cast<std::size_t>(std::ceil(*__p * _M_max_load_factor));
 	    return std::make_pair(true, *__p);
 	  }