This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] libstdc++/28080, more
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Mon, 19 Feb 2007 20:08:03 +0100
- Subject: [Patch] libstdc++/28080, more
Hi,
the below continues the work: besides the straightforward tr1/random and
tr1/memory bits (usual idea of avoiding the whole, big <algorithm>, when
possible), I'm also splitting out from <tr1/functional> the hash
functions to functional_hash.h: this allows to include only the latter
in tr1/unordered_map and unordered_set and the compilation of those
headers alone becomes about 3 times faster, because we avoid all the
preprocessor metaprogramming (the preprocessed headers are also less
than half the size).
Hoping for variadic templates to go in mainline relatively soon (after
Oxford?), the latter changes, very safe anyway, seem particularly
important for the 4_2-branch, and I mean to commit there too.
Tested without PCHs too, x86/x86_64-linux.
Paolo.
///////////////
2007-02-20 Paolo Carlini <pcarlini@suse.de>
PR libstdc++/28080 (partial)
* include/tr1/functional: Split out hash bits to...
* include/tr1/functional_hash.h: ...here.
* include/Makefile.am: Add.
* include/tr1/unordered_set: Include the latter instead.
* include/tr1/unordered_map: Likewise.
* include/tr1/random: Do not include the whole <algorithm>,
stl_algobase.h is enough.
* include/tr1/memory: Likewise.
* include/Makefile.in: Regenerate.
* include/tr1/utility (get(std::pair<>&), get(const std::pair<>&)):
Mark inline.
Index: include/tr1/functional_hash.h
===================================================================
--- include/tr1/functional_hash.h (revision 0)
+++ include/tr1/functional_hash.h (revision 0)
@@ -0,0 +1,232 @@
+// TR1 functional -*- 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.
+
+/** @file tr1/functional_hash.h
+ * This is an internal header file, included by other library headers.
+ * You should not attempt to use it directly.
+ */
+
+#ifndef _TR1_FUNCTIONAL_HASH_H
+#define _TR1_FUNCTIONAL_HASH_H 1
+
+#include <string>
+#include <cmath> // for std::frexp
+
+namespace std
+{
+_GLIBCXX_BEGIN_NAMESPACE(tr1)
+
+ // Definition of default hash function std::tr1::hash<>. The types for
+ // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
+ template<typename T>
+ struct hash;
+
+#define _TR1_hashtable_define_trivial_hash(_Tp) \
+ template<> \
+ struct hash<_Tp> \
+ : public std::unary_function<_Tp, std::size_t> \
+ { \
+ std::size_t \
+ operator()(_Tp __val) const \
+ { return static_cast<std::size_t>(__val); } \
+ }
+
+ _TR1_hashtable_define_trivial_hash(bool);
+ _TR1_hashtable_define_trivial_hash(char);
+ _TR1_hashtable_define_trivial_hash(signed char);
+ _TR1_hashtable_define_trivial_hash(unsigned char);
+ _TR1_hashtable_define_trivial_hash(wchar_t);
+ _TR1_hashtable_define_trivial_hash(short);
+ _TR1_hashtable_define_trivial_hash(int);
+ _TR1_hashtable_define_trivial_hash(long);
+ _TR1_hashtable_define_trivial_hash(long long);
+ _TR1_hashtable_define_trivial_hash(unsigned short);
+ _TR1_hashtable_define_trivial_hash(unsigned int);
+ _TR1_hashtable_define_trivial_hash(unsigned long);
+ _TR1_hashtable_define_trivial_hash(unsigned long long);
+
+#undef _TR1_hashtable_define_trivial_hash
+
+ template<typename _Tp>
+ struct hash<_Tp*>
+ : public std::unary_function<_Tp*, std::size_t>
+ {
+ std::size_t
+ operator()(_Tp* __p) const
+ { return reinterpret_cast<std::size_t>(__p); }
+ };
+
+ // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
+ // (used by the next specializations of std::tr1::hash<>)
+
+ // Dummy generic implementation (for sizeof(size_t) != 4, 8).
+ template<std::size_t = sizeof(std::size_t)>
+ struct _Fnv_hash
+ {
+ static std::size_t
+ hash(const char* __first, std::size_t __length)
+ {
+ std::size_t __result = 0;
+ for (; __length > 0; --__length)
+ __result = (__result * 131) + *__first++;
+ return __result;
+ }
+ };
+
+ template<>
+ struct _Fnv_hash<4>
+ {
+ static std::size_t
+ hash(const char* __first, std::size_t __length)
+ {
+ std::size_t __result = static_cast<std::size_t>(2166136261UL);
+ for (; __length > 0; --__length)
+ {
+ __result ^= static_cast<std::size_t>(*__first++);
+ __result *= static_cast<std::size_t>(16777619UL);
+ }
+ return __result;
+ }
+ };
+
+ template<>
+ struct _Fnv_hash<8>
+ {
+ static std::size_t
+ hash(const char* __first, std::size_t __length)
+ {
+ std::size_t __result =
+ static_cast<std::size_t>(14695981039346656037ULL);
+ for (; __length > 0; --__length)
+ {
+ __result ^= static_cast<std::size_t>(*__first++);
+ __result *= static_cast<std::size_t>(1099511628211ULL);
+ }
+ return __result;
+ }
+ };
+
+ // XXX String and floating point hashes probably shouldn't be inline
+ // member functions, since are nontrivial. Once we have the framework
+ // for TR1 .cc files, these should go in one.
+ template<>
+ struct hash<std::string>
+ : public std::unary_function<std::string, std::size_t>
+ {
+ std::size_t
+ operator()(const std::string& __s) const
+ { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
+ };
+
+#ifdef _GLIBCXX_USE_WCHAR_T
+ template<>
+ struct hash<std::wstring>
+ : public std::unary_function<std::wstring, std::size_t>
+ {
+ std::size_t
+ operator()(const std::wstring& __s) const
+ {
+ return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
+ __s.length() * sizeof(wchar_t));
+ }
+ };
+#endif
+
+ template<>
+ struct hash<float>
+ : public std::unary_function<float, std::size_t>
+ {
+ std::size_t
+ operator()(float __fval) const
+ {
+ std::size_t __result = 0;
+
+ // 0 and -0 both hash to zero.
+ if (__fval != 0.0f)
+ __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
+ sizeof(__fval));
+ return __result;
+ }
+ };
+
+ template<>
+ struct hash<double>
+ : public std::unary_function<double, std::size_t>
+ {
+ std::size_t
+ operator()(double __dval) const
+ {
+ std::size_t __result = 0;
+
+ // 0 and -0 both hash to zero.
+ if (__dval != 0.0)
+ __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
+ sizeof(__dval));
+ return __result;
+ }
+ };
+
+ // For long double, careful with random padding bits (e.g., on x86,
+ // 10 bytes -> 12 bytes) and resort to frexp.
+ template<>
+ struct hash<long double>
+ : public std::unary_function<long double, std::size_t>
+ {
+ std::size_t
+ operator()(long double __ldval) const
+ {
+ std::size_t __result = 0;
+
+ int __exponent;
+ __ldval = std::frexp(__ldval, &__exponent);
+ __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
+
+ const long double __mult =
+ std::numeric_limits<std::size_t>::max() + 1.0l;
+ __ldval *= __mult;
+
+ // Try to use all the bits of the mantissa (really necessary only
+ // on 32-bit targets, at least for 80-bit floating point formats).
+ const std::size_t __hibits = (std::size_t)__ldval;
+ __ldval = (__ldval - (long double)__hibits) * __mult;
+
+ const std::size_t __coeff =
+ (std::numeric_limits<std::size_t>::max()
+ / std::numeric_limits<long double>::max_exponent);
+
+ __result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
+
+ return __result;
+ }
+ };
+
+_GLIBCXX_END_NAMESPACE
+}
+
+#endif
Index: include/tr1/utility
===================================================================
--- include/tr1/utility (revision 122127)
+++ include/tr1/utility (working copy)
@@ -1,6 +1,6 @@
// TR1 utility -*- C++ -*-
-// Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2004, 2005, 2006, 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
@@ -87,13 +87,13 @@
};
template<int _Int, class _Tp1, class _Tp2>
- typename tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type&
- get(pair<_Tp1, _Tp2>& __in)
+ inline typename tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type&
+ get(std::pair<_Tp1, _Tp2>& __in)
{ return __pair_get<_Int>::__get(__in); }
template<int _Int, class _Tp1, class _Tp2>
- const typename tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type&
- get(const pair<_Tp1, _Tp2>& __in)
+ inline const typename tuple_element<_Int, std::pair<_Tp1, _Tp2> >::type&
+ get(const std::pair<_Tp1, _Tp2>& __in)
{ return __pair_get<_Int>::__const_get(__in); }
_GLIBCXX_END_NAMESPACE
Index: include/tr1/memory
===================================================================
--- include/tr1/memory (revision 122127)
+++ include/tr1/memory (working copy)
@@ -1,6 +1,6 @@
// <tr1/memory> -*- C++ -*-
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 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
@@ -36,14 +36,14 @@
#define _TR1_MEMORY 1
#include "../memory"
-#include <functional> // std::less
-#include <exception> // std::exception
-#include <new> // std::bad_alloc
-#include <typeinfo> // std::type_info in get_deleter
-#include <cstddef> // std::size_t
-#include <algorithm> // std::swap
-#include <iosfwd> // std::basic_ostream
-#include <cstdlib> // std::abort
+#include <functional> // std::less
+#include <exception> // std::exception
+#include <new> // std::bad_alloc
+#include <typeinfo> // std::type_info in get_deleter
+#include <cstddef> // std::size_t
+#include <bits/stl_algobase.h> // std::swap
+#include <iosfwd> // std::basic_ostream
+#include <cstdlib> // std::abort
#include <ext/atomicity.h>
#include <ext/concurrence.h>
Index: include/tr1/random
===================================================================
--- include/tr1/random (revision 122127)
+++ include/tr1/random (working copy)
@@ -1,6 +1,6 @@
// random number generation -*- C++ -*-
-// Copyright (C) 2006 Free Software Foundation, Inc.
+// Copyright (C) 2006, 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
@@ -35,7 +35,7 @@
#ifndef _TR1_RANDOM
#define _TR1_RANDOM 1
-#include <algorithm>
+#include <bits/stl_algobase.h>
#include <bits/concept_check.h>
#include <cmath>
#include <debug/debug.h>
Index: include/tr1/unordered_map
===================================================================
--- include/tr1/unordered_map (revision 122127)
+++ include/tr1/unordered_map (working copy)
@@ -1,6 +1,6 @@
// TR1 unordered_map -*- C++ -*-
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 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
@@ -35,7 +35,7 @@
#define _TR1_UNORDERED_MAP 1
#include <tr1/hashtable>
-#include <tr1/functional>
+#include <tr1/functional_hash.h>
namespace std
{
Index: include/tr1/functional
===================================================================
--- include/tr1/functional (revision 122127)
+++ include/tr1/functional (working copy)
@@ -1,6 +1,6 @@
// TR1 functional header -*- C++ -*-
-// Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2004, 2005, 2006, 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
@@ -40,9 +40,7 @@
#include <typeinfo>
#include <tr1/type_traits>
#include <ext/type_traits.h>
-#include <string> // for std::tr1::hash
-#include <cstdlib> // for std::abort
-#include <cmath> // for std::frexp
+#include <cstdlib> // for std::abort
#include <tr1/tuple>
namespace std
@@ -1093,7 +1091,6 @@
_GLIBCXX_END_NAMESPACE
}
-
#define _GLIBCXX_JOIN(X,Y) _GLIBCXX_JOIN2( X , Y )
#define _GLIBCXX_JOIN2(X,Y) _GLIBCXX_JOIN3(X,Y)
#define _GLIBCXX_JOIN3(X,Y) X##Y
@@ -1104,196 +1101,6 @@
#undef _GLIBCXX_JOIN2
#undef _GLIBCXX_JOIN
+#include <tr1/functional_hash.h>
-namespace std
-{
-_GLIBCXX_BEGIN_NAMESPACE(tr1)
-
- // Definition of default hash function std::tr1::hash<>. The types for
- // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
- template<typename T>
- struct hash;
-
-#define _TR1_hashtable_define_trivial_hash(_Tp) \
- template<> \
- struct hash<_Tp> \
- : public std::unary_function<_Tp, std::size_t> \
- { \
- std::size_t \
- operator()(_Tp __val) const \
- { return static_cast<std::size_t>(__val); } \
- }
-
- _TR1_hashtable_define_trivial_hash(bool);
- _TR1_hashtable_define_trivial_hash(char);
- _TR1_hashtable_define_trivial_hash(signed char);
- _TR1_hashtable_define_trivial_hash(unsigned char);
- _TR1_hashtable_define_trivial_hash(wchar_t);
- _TR1_hashtable_define_trivial_hash(short);
- _TR1_hashtable_define_trivial_hash(int);
- _TR1_hashtable_define_trivial_hash(long);
- _TR1_hashtable_define_trivial_hash(long long);
- _TR1_hashtable_define_trivial_hash(unsigned short);
- _TR1_hashtable_define_trivial_hash(unsigned int);
- _TR1_hashtable_define_trivial_hash(unsigned long);
- _TR1_hashtable_define_trivial_hash(unsigned long long);
-
-#undef _TR1_hashtable_define_trivial_hash
-
- template<typename _Tp>
- struct hash<_Tp*>
- : public std::unary_function<_Tp*, std::size_t>
- {
- std::size_t
- operator()(_Tp* __p) const
- { return reinterpret_cast<std::size_t>(__p); }
- };
-
- // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
- // (used by the next specializations of std::tr1::hash<>)
-
- // Dummy generic implementation (for sizeof(size_t) != 4, 8).
- template<std::size_t = sizeof(std::size_t)>
- struct _Fnv_hash
- {
- static std::size_t
- hash(const char* __first, std::size_t __length)
- {
- std::size_t __result = 0;
- for (; __length > 0; --__length)
- __result = (__result * 131) + *__first++;
- return __result;
- }
- };
-
- template<>
- struct _Fnv_hash<4>
- {
- static std::size_t
- hash(const char* __first, std::size_t __length)
- {
- std::size_t __result = static_cast<std::size_t>(2166136261UL);
- for (; __length > 0; --__length)
- {
- __result ^= (std::size_t)*__first++;
- __result *= 16777619UL;
- }
- return __result;
- }
- };
-
- template<>
- struct _Fnv_hash<8>
- {
- static std::size_t
- hash(const char* __first, std::size_t __length)
- {
- std::size_t __result =
- static_cast<std::size_t>(14695981039346656037ULL);
- for (; __length > 0; --__length)
- {
- __result ^= (std::size_t)*__first++;
- __result *= 1099511628211ULL;
- }
- return __result;
- }
- };
-
- // XXX String and floating point hashes probably shouldn't be inline
- // member functions, since are nontrivial. Once we have the framework
- // for TR1 .cc files, these should go in one.
- template<>
- struct hash<std::string>
- : public std::unary_function<std::string, std::size_t>
- {
- std::size_t
- operator()(const std::string& __s) const
- { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
- };
-
-#ifdef _GLIBCXX_USE_WCHAR_T
- template<>
- struct hash<std::wstring>
- : public std::unary_function<std::wstring, std::size_t>
- {
- std::size_t
- operator()(const std::wstring& __s) const
- {
- return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
- __s.length() * sizeof(wchar_t));
- }
- };
#endif
-
- template<>
- struct hash<float>
- : public std::unary_function<float, std::size_t>
- {
- std::size_t
- operator()(float __fval) const
- {
- std::size_t __result = 0;
-
- // 0 and -0 both hash to zero.
- if (__fval != 0.0f)
- __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
- sizeof(__fval));
- return __result;
- }
- };
-
- template<>
- struct hash<double>
- : public std::unary_function<double, std::size_t>
- {
- std::size_t
- operator()(double __dval) const
- {
- std::size_t __result = 0;
-
- // 0 and -0 both hash to zero.
- if (__dval != 0.0)
- __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
- sizeof(__dval));
- return __result;
- }
- };
-
- // For long double, careful with random padding bits (e.g., on x86,
- // 10 bytes -> 12 bytes) and resort to frexp.
- template<>
- struct hash<long double>
- : public std::unary_function<long double, std::size_t>
- {
- std::size_t
- operator()(long double __ldval) const
- {
- std::size_t __result = 0;
-
- int __exponent;
- __ldval = std::frexp(__ldval, &__exponent);
- __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
-
- const long double __mult =
- std::numeric_limits<std::size_t>::max() + 1.0l;
- __ldval *= __mult;
-
- // Try to use all the bits of the mantissa (really necessary only
- // on 32-bit targets, at least for 80-bit floating point formats).
- const std::size_t __hibits = (std::size_t)__ldval;
- __ldval = (__ldval - (long double)__hibits) * __mult;
-
- const std::size_t __coeff =
- (std::numeric_limits<std::size_t>::max()
- / std::numeric_limits<long double>::max_exponent);
-
- __result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
-
- return __result;
- }
- };
-
-_GLIBCXX_END_NAMESPACE
-}
-
-#endif
Index: include/tr1/unordered_set
===================================================================
--- include/tr1/unordered_set (revision 122127)
+++ include/tr1/unordered_set (working copy)
@@ -1,6 +1,6 @@
// TR1 unordered_set -*- C++ -*-
-// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
+// Copyright (C) 2005, 2006, 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
@@ -35,7 +35,7 @@
#define _TR1_UNORDERED_SET 1
#include <tr1/hashtable>
-#include <tr1/functional>
+#include <tr1/functional_hash.h>
namespace std
{
Index: include/Makefile.am
===================================================================
--- include/Makefile.am (revision 122127)
+++ include/Makefile.am (working copy)
@@ -1,6 +1,6 @@
## Makefile for the include subdirectory of the GNU C++ Standard library.
##
-## Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
+## Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
## Free Software Foundation, Inc.
##
## This file is part of the libstdc++ version 3 distribution.
@@ -549,6 +549,7 @@
${tr1_srcdir}/fenv.h \
${tr1_srcdir}/float.h \
${tr1_srcdir}/functional \
+ ${tr1_srcdir}/functional_hash.h \
${tr1_srcdir}/functional_iterate.h \
${tr1_srcdir}/hashtable \
${tr1_srcdir}/hashtable_policy.h \