This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[Patch] libstdc++/21193 (string & wstring)
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Tue, 12 Jul 2005 20:10:48 +0200
- Subject: [Patch] libstdc++/21193 (string & wstring)
Hi,
the below is what I have for string & wstring. The most important
weakness I can see, at the moment, is that the patch is not -pedantic
safe, due to the LL constants: however, the problem seems not so serious
longer term, because eventually those specializations will belong to a
*.cc file. Also, I'm punting (falling back to the current placeholder
implementation) for sizeof(size_t) != 4,8: if needed, would be easy
adding more cases.
About the float, double, long double hashes, in the meanwhile figured
out that the most tricky one is definitely long double, when random
padding bits are very common (e.g. 10 byte -> 12 byte); Float and double
seem efficiently amenable to the treatment suggested by Gaby. For now,
I'm resorting to the frexp approach for long double. I hope to have
something pretty soon.
Tested x86/x86-64-linux. In case of doubts, speak soon... ;)
Paolo.
P.S. This work seems safe for 4.0.2 too.
//////////////
2005-07-13 Paolo Carlini <pcarlini@suse.de>
PR libstdc++/21193 (string & wstring)
* include/tr1/functional (hash<string>, hash<wstring>):
Reimplement using the FNV hash.
* include/tr1/functional: Trivial formatting fixes.
Index: functional
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/tr1/functional,v
retrieving revision 1.11
diff -p -r1.11 functional
*** functional 2 Apr 2005 02:02:28 -0000 1.11
--- functional 12 Jul 2005 17:41:57 -0000
*************** namespace tr1
*** 1090,1104 ****
#undef _GLIBCXX_JOIN2
#undef _GLIBCXX_JOIN
! // 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(T) \
! template <> struct hash<T> { \
! std::size_t operator()(T val) const { return static_cast<std::size_t>(val); } \
! } \
tr1_hashtable_define_trivial_hash(bool);
tr1_hashtable_define_trivial_hash(char);
--- 1090,1108 ----
#undef _GLIBCXX_JOIN2
#undef _GLIBCXX_JOIN
! // 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(T) \
! template<> \
! struct hash<T> \
! { \
! std::size_t \
! operator()(T val) const \
! { return static_cast<std::size_t>(val); } \
! }
tr1_hashtable_define_trivial_hash(bool);
tr1_hashtable_define_trivial_hash(char);
*************** namespace tr1
*** 1116,1159 ****
tr1_hashtable_define_trivial_hash(double);
tr1_hashtable_define_trivial_hash(long double);
! #undef tr1_hashtable_define_trivial_hash
! template <typename T>
! struct hash<T*> {
! std::size_t operator()(T* p) const {
! return reinterpret_cast<std::size_t>(p);
}
};
! // ??? We can probably find a better hash function than this (i.e. one
! // that vectorizes better and that produces a more uniform distribution).
// XXX String hash probably shouldn't be an inline member function,
// since it's nontrivial. Once we have the framework for TR1 .cc
// files, this should go in one.
!
! template <>
struct hash<std::string>
{
! std::size_t operator()(const std::string& s) const
! {
! std::size_t result = 0;
! for (std::string::const_iterator i = s.begin(); i != s.end(); ++i)
! result = (result * 131) + *i;
! return result;
! }
};
#ifdef _GLIBCXX_USE_WCHAR_T
! template <>
struct hash<std::wstring>
{
! std::size_t operator()(const std::wstring& s) const
{
! std::size_t result = 0;
! for (std::wstring::const_iterator i = s.begin(); i != s.end(); ++i)
! result = (result * 131) + *i;
! return result;
}
};
#endif
--- 1120,1204 ----
tr1_hashtable_define_trivial_hash(double);
tr1_hashtable_define_trivial_hash(long double);
! #undef tr1_hashtable_define_trivial_hash
!
! template<typename T>
! struct hash<T*>
! {
! std::size_t
! operator()(T* 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 = 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 = 14695981039346656037ULL;
! for (; length > 0; --length)
! {
! result ^= (std::size_t)*first++;
! result *= 1099511628211ULL;
! }
! return result;
! }
! };
// XXX String hash probably shouldn't be an inline member function,
// since it's nontrivial. Once we have the framework for TR1 .cc
// files, this should go in one.
! template<>
struct hash<std::string>
{
! 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>
{
! 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