This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[Patch] Export __prime_list


Hi,

I'd like to finally remove this hack too.

In principle, we could also export a single list, but seems a tad
cleaner to have separate copies in std::tr1::__detail and std::__detail
and allow for the latter to be different. Anyway, if there are strong
opinions, just let me know (for example, at some point I had a single
list in __gnu_cxx...)

Tested x86_64-linux.

Paolo.

///////////////////////
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.
Index: src/hashtable.cc
===================================================================
--- src/hashtable.cc	(revision 0)
+++ src/hashtable.cc	(revision 0)
@@ -0,0 +1,124 @@
+// std::__detail and std::tr1::__detail definitions -*- C++ -*-
+
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#  define _GLIBCXX_BEGIN_NAMESPACE_TR1 
+#  define _GLIBCXX_END_NAMESPACE_TR1 
+#else
+#  define _GLIBCXX_INCLUDE_AS_TR1
+#  define _GLIBCXX_BEGIN_NAMESPACE_TR1 namespace tr1 {
+#  define _GLIBCXX_END_NAMESPACE_TR1 }
+#endif
+
+namespace std
+{ 
+_GLIBCXX_BEGIN_NAMESPACE_TR1
+
+namespace __detail
+{
+  extern const unsigned long __prime_list[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.
+    sizeof(unsigned long) != 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    
+  };
+} // namespace __detail
+
+_GLIBCXX_END_NAMESPACE_TR1
+}
Index: src/hashtable_c++0x.cc
===================================================================
--- src/hashtable_c++0x.cc	(revision 0)
+++ src/hashtable_c++0x.cc	(revision 0)
@@ -0,0 +1,30 @@
+// std::__detail definitions -*- C++ -*-
+
+// Copyright (C) 2007 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include "hashtable.cc"
Index: src/Makefile.am
===================================================================
--- src/Makefile.am	(revision 130566)
+++ src/Makefile.am	(working copy)
@@ -146,6 +146,8 @@
 	hash.cc \
 	hash_c++0x.cc \
 	globals_io.cc \
+	hashtable.cc \
+	hashtable_c++0x.cc \	
 	ios.cc \
 	ios_failure.cc \
 	ios_init.cc \
@@ -229,6 +231,11 @@
 hash_c++0x.o: hash_c++0x.cc
 	$(CXXCOMPILE) -std=gnu++0x -c $<
 
+hashtable_c++0x.lo: hashtable_c++0x.cc
+	$(LTCXXCOMPILE) -std=gnu++0x -c $<
+hashtable_c++0x.o: hashtable_c++0x.cc
+	$(CXXCOMPILE) -std=gnu++0x -c $<
+
 if GLIBCXX_LDBL_COMPAT
 # Use special rules for compatibility-ldbl.cc compilation, as we need to
 # pass -mlong-double-64.
Index: include/tr1_impl/hashtable_policy.h
===================================================================
--- include/tr1_impl/hashtable_policy.h	(revision 130566)
+++ include/tr1_impl/hashtable_policy.h	(working copy)
@@ -60,99 +60,6 @@
       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 @@
   // 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 @@
     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 @@
   _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 @@
   // 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 @@
 	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);
 	  }
Index: config/abi/pre/gnu.ver
===================================================================
--- config/abi/pre/gnu.ver	(revision 130566)
+++ config/abi/pre/gnu.ver	(working copy)
@@ -789,6 +789,9 @@
     _ZNSt15basic_streambufI[cw]St11char_traitsI[cw]EE6stosscEv;
 
     _ZSt17__verify_grouping*;
+    
+    _ZNSt8__detail12__prime_listE;
+    _ZNSt3tr18__detail12__prime_listE;
 
 } GLIBCXX_3.4.9;
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]