From 41e56bf7d66af98e2db00489deffb3e6178dd5b2 Mon Sep 17 00:00:00 2001 From: Paolo Carlini Date: Tue, 20 Feb 2007 21:22:35 +0000 Subject: [PATCH] PR libstdc++/28080 (partial) 2007-02-20 Paolo Carlini 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 , 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. From-SVN: r122175 --- libstdc++-v3/ChangeLog | 16 ++ libstdc++-v3/include/Makefile.am | 3 +- libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/tr1/functional | 199 +----------------- libstdc++-v3/include/tr1/functional_hash.h | 232 +++++++++++++++++++++ libstdc++-v3/include/tr1/memory | 18 +- libstdc++-v3/include/tr1/random | 4 +- libstdc++-v3/include/tr1/unordered_map | 4 +- libstdc++-v3/include/tr1/unordered_set | 4 +- libstdc++-v3/include/tr1/utility | 10 +- 10 files changed, 274 insertions(+), 217 deletions(-) create mode 100644 libstdc++-v3/include/tr1/functional_hash.h diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 712ad78f04b..ba0a40b31f1 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,19 @@ +2007-02-20 Paolo Carlini + + 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 , + 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. + 2007-02-20 Benjamin Kosnik Directory layout flattening. diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 33533a87068..43c9f8ca3f8 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -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_headers = \ ${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 \ diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in index c3dd4a5d393..17e949b9166 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -774,6 +774,7 @@ tr1_headers = \ ${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 \ diff --git a/libstdc++-v3/include/tr1/functional b/libstdc++-v3/include/tr1/functional index 7ef93a4f2c8..f3cc78de751 100644 --- a/libstdc++-v3/include/tr1/functional +++ b/libstdc++-v3/include/tr1/functional @@ -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 #include #include -#include // for std::tr1::hash -#include // for std::abort -#include // for std::frexp +#include // for std::abort #include namespace std @@ -1093,7 +1091,6 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) _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 @@ _GLIBCXX_END_NAMESPACE #undef _GLIBCXX_JOIN2 #undef _GLIBCXX_JOIN - -namespace std -{ -_GLIBCXX_BEGIN_NAMESPACE(tr1) - - // Definition of default hash function std::tr1::hash<>. The types for - // which std::tr1::hash is defined is in clause 6.3.3. of the PDTR. - template - 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(__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 - struct hash<_Tp*> - : public std::unary_function<_Tp*, std::size_t> - { - std::size_t - operator()(_Tp* __p) const - { return reinterpret_cast(__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 - 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(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(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 - : public std::unary_function - { - 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 - : public std::unary_function - { - std::size_t - operator()(const std::wstring& __s) const - { - return _Fnv_hash<>::hash(reinterpret_cast(__s.data()), - __s.length() * sizeof(wchar_t)); - } - }; -#endif - - template<> - struct hash - : public std::unary_function - { - 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(&__fval), - sizeof(__fval)); - return __result; - } - }; - - template<> - struct hash - : public std::unary_function - { - 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(&__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 - : public std::unary_function - { - 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::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::max() - / std::numeric_limits::max_exponent); - - __result = __hibits + (std::size_t)__ldval + __coeff * __exponent; - - return __result; - } - }; - -_GLIBCXX_END_NAMESPACE -} +#include #endif diff --git a/libstdc++-v3/include/tr1/functional_hash.h b/libstdc++-v3/include/tr1/functional_hash.h new file mode 100644 index 00000000000..3e592b45ab7 --- /dev/null +++ b/libstdc++-v3/include/tr1/functional_hash.h @@ -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 +#include // for std::frexp + +namespace std +{ +_GLIBCXX_BEGIN_NAMESPACE(tr1) + + // Definition of default hash function std::tr1::hash<>. The types for + // which std::tr1::hash is defined is in clause 6.3.3. of the PDTR. + template + 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(__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 + struct hash<_Tp*> + : public std::unary_function<_Tp*, std::size_t> + { + std::size_t + operator()(_Tp* __p) const + { return reinterpret_cast(__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 + 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(2166136261UL); + for (; __length > 0; --__length) + { + __result ^= static_cast(*__first++); + __result *= static_cast(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(14695981039346656037ULL); + for (; __length > 0; --__length) + { + __result ^= static_cast(*__first++); + __result *= static_cast(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 + : public std::unary_function + { + 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 + : public std::unary_function + { + std::size_t + operator()(const std::wstring& __s) const + { + return _Fnv_hash<>::hash(reinterpret_cast(__s.data()), + __s.length() * sizeof(wchar_t)); + } + }; +#endif + + template<> + struct hash + : public std::unary_function + { + 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(&__fval), + sizeof(__fval)); + return __result; + } + }; + + template<> + struct hash + : public std::unary_function + { + 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(&__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 + : public std::unary_function + { + 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::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::max() + / std::numeric_limits::max_exponent); + + __result = __hibits + (std::size_t)__ldval + __coeff * __exponent; + + return __result; + } + }; + +_GLIBCXX_END_NAMESPACE +} + +#endif diff --git a/libstdc++-v3/include/tr1/memory b/libstdc++-v3/include/tr1/memory index 9de80dadfa9..0df7b9d7370 100644 --- a/libstdc++-v3/include/tr1/memory +++ b/libstdc++-v3/include/tr1/memory @@ -1,6 +1,6 @@ // -*- 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 // std::less -#include // std::exception -#include // std::bad_alloc -#include // std::type_info in get_deleter -#include // std::size_t -#include // std::swap -#include // std::basic_ostream -#include // std::abort +#include // std::less +#include // std::exception +#include // std::bad_alloc +#include // std::type_info in get_deleter +#include // std::size_t +#include // std::swap +#include // std::basic_ostream +#include // std::abort #include #include diff --git a/libstdc++-v3/include/tr1/random b/libstdc++-v3/include/tr1/random index 72ec79ded61..02a7ae7bc85 100644 --- a/libstdc++-v3/include/tr1/random +++ b/libstdc++-v3/include/tr1/random @@ -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 +#include #include #include #include diff --git a/libstdc++-v3/include/tr1/unordered_map b/libstdc++-v3/include/tr1/unordered_map index 88f39cee51a..d613d156ef1 100644 --- a/libstdc++-v3/include/tr1/unordered_map +++ b/libstdc++-v3/include/tr1/unordered_map @@ -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 -#include +#include namespace std { diff --git a/libstdc++-v3/include/tr1/unordered_set b/libstdc++-v3/include/tr1/unordered_set index 49829a6020e..a01b89b3af8 100644 --- a/libstdc++-v3/include/tr1/unordered_set +++ b/libstdc++-v3/include/tr1/unordered_set @@ -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 -#include +#include namespace std { diff --git a/libstdc++-v3/include/tr1/utility b/libstdc++-v3/include/tr1/utility index a719faa45e7..93e00eb3c94 100644 --- a/libstdc++-v3/include/tr1/utility +++ b/libstdc++-v3/include/tr1/utility @@ -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 @@ _GLIBCXX_BEGIN_NAMESPACE(tr1) }; template - 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 - 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 -- 2.30.2