// TR1 functional header -*- C++ -*-
-// Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+// Copyright (C) 2004, 2005, 2006 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
// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// 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
#ifndef _TR1_FUNCTIONAL
#define _TR1_FUNCTIONAL 1
+#pragma GCC system_header
+
#include "../functional"
#include <typeinfo>
#include <tr1/type_traits>
-#include <bits/cpp_type_traits.h>
+#include <ext/type_traits.h>
#include <string> // for std::tr1::hash
#include <cstdlib> // for std::abort
+#include <cmath> // for std::frexp
#include <tr1/tuple>
namespace std
{
-namespace tr1
-{
+_GLIBCXX_BEGIN_NAMESPACE(tr1)
+
template<typename _MemberPointer>
class _Mem_fn;
*/
template<typename _Functor>
struct _Weak_result_type_impl
- : _Maybe_get_result_type<_Has_result_type<_Functor>::value, _Functor>
+ : _Maybe_get_result_type<_Has_result_type<_Functor>::value, _Functor>
{
};
// Not a unary_function or binary_function, so try a weak result type
template<typename _Tp>
struct _Reference_wrapper_base_impl<false, false, _Tp>
- : _Weak_result_type<_Tp>
+ : _Weak_result_type<_Tp>
{ };
// unary_function but not binary_function
template<typename _Tp>
struct _Reference_wrapper_base_impl<true, false, _Tp>
- : unary_function<typename _Tp::argument_type,
- typename _Tp::result_type>
+ : unary_function<typename _Tp::argument_type,
+ typename _Tp::result_type>
{ };
// binary_function but not unary_function
template<typename _Tp>
struct _Reference_wrapper_base_impl<false, true, _Tp>
- : binary_function<typename _Tp::first_argument_type,
- typename _Tp::second_argument_type,
- typename _Tp::result_type>
+ : binary_function<typename _Tp::first_argument_type,
+ typename _Tp::second_argument_type,
+ typename _Tp::result_type>
{ };
// both unary_function and binary_function. import result_type to
// avoid conflicts.
template<typename _Tp>
struct _Reference_wrapper_base_impl<true, true, _Tp>
- : unary_function<typename _Tp::argument_type,
- typename _Tp::result_type>,
- binary_function<typename _Tp::first_argument_type,
- typename _Tp::second_argument_type,
- typename _Tp::result_type>
+ : unary_function<typename _Tp::argument_type,
+ typename _Tp::result_type>,
+ binary_function<typename _Tp::first_argument_type,
+ typename _Tp::second_argument_type,
+ typename _Tp::result_type>
{
typedef typename _Tp::result_type result_type;
};
*/
template<typename _Tp>
struct _Reference_wrapper_base
- : _Reference_wrapper_base_impl<
- _Derives_from_unary_function<_Tp>::value,
- _Derives_from_binary_function<_Tp>::value,
- _Tp>
+ : _Reference_wrapper_base_impl<
+ _Derives_from_unary_function<_Tp>::value,
+ _Derives_from_binary_function<_Tp>::value,
+ _Tp>
{ };
// - a function type (unary)
template<typename _Res, typename _T1>
struct _Reference_wrapper_base<_Res(_T1)>
- : unary_function<_T1, _Res>
+ : unary_function<_T1, _Res>
{ };
// - a function type (binary)
template<typename _Res, typename _T1, typename _T2>
struct _Reference_wrapper_base<_Res(_T1, _T2)>
- : binary_function<_T1, _T2, _Res>
+ : binary_function<_T1, _T2, _Res>
{ };
// - a function pointer type (unary)
template<typename _Res, typename _T1>
struct _Reference_wrapper_base<_Res(*)(_T1)>
- : unary_function<_T1, _Res>
+ : unary_function<_T1, _Res>
{ };
// - a function pointer type (binary)
template<typename _Res, typename _T1, typename _T2>
struct _Reference_wrapper_base<_Res(*)(_T1, _T2)>
- : binary_function<_T1, _T2, _Res>
+ : binary_function<_T1, _T2, _Res>
{ };
// - a pointer to member function type (unary, no qualifiers)
template<typename _Res, typename _T1>
struct _Reference_wrapper_base<_Res (_T1::*)()>
- : unary_function<_T1*, _Res>
+ : unary_function<_T1*, _Res>
{ };
// - a pointer to member function type (binary, no qualifiers)
template<typename _Res, typename _T1, typename _T2>
struct _Reference_wrapper_base<_Res (_T1::*)(_T2)>
- : binary_function<_T1*, _T2, _Res>
+ : binary_function<_T1*, _T2, _Res>
{ };
// - a pointer to member function type (unary, const)
template<typename _Res, typename _T1>
struct _Reference_wrapper_base<_Res (_T1::*)() const>
- : unary_function<const _T1*, _Res>
+ : unary_function<const _T1*, _Res>
{ };
// - a pointer to member function type (binary, const)
template<typename _Res, typename _T1, typename _T2>
struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const>
- : binary_function<const _T1*, _T2, _Res>
+ : binary_function<const _T1*, _T2, _Res>
{ };
// - a pointer to member function type (unary, volatile)
template<typename _Res, typename _T1>
struct _Reference_wrapper_base<_Res (_T1::*)() volatile>
- : unary_function<volatile _T1*, _Res>
+ : unary_function<volatile _T1*, _Res>
{ };
// - a pointer to member function type (binary, volatile)
template<typename _Res, typename _T1, typename _T2>
struct _Reference_wrapper_base<_Res (_T1::*)(_T2) volatile>
- : binary_function<volatile _T1*, _T2, _Res>
+ : binary_function<volatile _T1*, _T2, _Res>
{ };
// - a pointer to member function type (unary, const volatile)
template<typename _Res, typename _T1>
struct _Reference_wrapper_base<_Res (_T1::*)() const volatile>
- : unary_function<const volatile _T1*, _Res>
+ : unary_function<const volatile _T1*, _Res>
{ };
// - a pointer to member function type (binary, const volatile)
template<typename _Res, typename _T1, typename _T2>
struct _Reference_wrapper_base<_Res (_T1::*)(_T2) const volatile>
- : binary_function<const volatile _T1*, _T2, _Res>
+ : binary_function<const volatile _T1*, _T2, _Res>
{ };
template<typename _Tp>
// Denotes a reference should be taken to a variable.
template<typename _Tp>
- reference_wrapper<_Tp>
+ inline reference_wrapper<_Tp>
ref(_Tp& __t)
{ return reference_wrapper<_Tp>(__t); }
// Denotes a const reference should be taken to a variable.
template<typename _Tp>
- reference_wrapper<const _Tp>
+ inline reference_wrapper<const _Tp>
cref(const _Tp& __t)
{ return reference_wrapper<const _Tp>(__t); }
template<typename _Tp>
- reference_wrapper<_Tp> ref(reference_wrapper<_Tp> __t)
+ inline reference_wrapper<_Tp>
+ ref(reference_wrapper<_Tp> __t)
{ return ref(__t.get()); }
template<typename _Tp>
- reference_wrapper<const _Tp> cref(reference_wrapper<_Tp> __t)
+ inline reference_wrapper<const _Tp>
+ cref(reference_wrapper<_Tp> __t)
{ return cref(__t.get()); }
template<typename _Tp, bool>
public:
template<typename _Tp>
struct _Result_type
- : _Mem_fn_const_or_non<
- _Res,
- (sizeof(__sfinae_types::__two)
- == sizeof(__check_const<_Tp>(__get_ref<_Tp>(), (_Tp*)0)))>
+ : _Mem_fn_const_or_non<
+ _Res,
+ (sizeof(__sfinae_types::__two)
+ == sizeof(__check_const<_Tp>(__get_ref<_Tp>(), (_Tp*)0)))>
{ };
template<typename _Signature>
template<typename _CVMem, typename _Tp>
struct result<_CVMem(_Tp)>
- : public _Result_type<_Tp> { };
+ : public _Result_type<_Tp> { };
template<typename _CVMem, typename _Tp>
struct result<_CVMem(_Tp&)>
- : public _Result_type<_Tp> { };
+ : public _Result_type<_Tp> { };
explicit _Mem_fn(_Res _Class::*__pm) : __pm(__pm) { }
#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);
- 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(unsigned short);
- tr1_hashtable_define_trivial_hash(unsigned int);
- tr1_hashtable_define_trivial_hash(unsigned long);
-
- tr1_hashtable_define_trivial_hash(float);
- 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);
- }
+ // 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(unsigned short);
+ _TR1_hashtable_define_trivial_hash(unsigned int);
+ _TR1_hashtable_define_trivial_hash(unsigned 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); }
};
- // ??? We can probably find a better hash function than this (i.e. one
- // that vectorizes better and that produces a more uniform distribution).
+ // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
+ // (used by the next specializations of std::tr1::hash<>)
- // 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.
+ // 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 hash<std::string>
+ 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>
{
- std::size_t operator()(const std::string& s) const
+ static std::size_t
+ hash(const char* __first, std::size_t __length)
{
- std::size_t result = 0;
- for (std::string::const_iterator i = s.begin(); i != s.end(); ++i)
- result = (result * 131) + *i;
- return result;
+ 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 <>
+ template<>
struct hash<std::wstring>
+ : public std::unary_function<std::wstring, std::size_t>
{
- std::size_t operator()(const std::wstring& s) const
+ 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;
+ 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
OSDN Git Service
