File indexing completed on 2024-05-12 15:43:39
0001 /* 0002 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 0003 * 0004 * This library is free software; you can redistribute it and/or 0005 * modify it under the terms of the GNU Library General Public 0006 * License as published by the Free Software Foundation; either 0007 * version 2 of the License, or (at your option) any later version. 0008 * 0009 * This library is distributed in the hope that it will be useful, 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 * Library General Public License for more details. 0013 * 0014 * You should have received a copy of the GNU Library General Public License 0015 * along with this library; see the file COPYING.LIB. If not, write to 0016 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 * Boston, MA 02110-1301, USA. 0018 * 0019 */ 0020 0021 #ifndef WTF_HashTraits_h 0022 #define WTF_HashTraits_h 0023 0024 #include <wtf/Assertions.h> 0025 #include <wtf/HashFunctions.h> 0026 #include <utility> 0027 #include <limits> 0028 0029 namespace WTF 0030 { 0031 0032 using std::pair; 0033 using std::make_pair; 0034 0035 template<typename T> struct IsInteger { 0036 static const bool value = false; 0037 }; 0038 template<> struct IsInteger<bool> { 0039 static const bool value = true; 0040 }; 0041 template<> struct IsInteger<char> { 0042 static const bool value = true; 0043 }; 0044 template<> struct IsInteger<signed char> { 0045 static const bool value = true; 0046 }; 0047 template<> struct IsInteger<unsigned char> { 0048 static const bool value = true; 0049 }; 0050 template<> struct IsInteger<short> { 0051 static const bool value = true; 0052 }; 0053 template<> struct IsInteger<unsigned short> { 0054 static const bool value = true; 0055 }; 0056 template<> struct IsInteger<int> { 0057 static const bool value = true; 0058 }; 0059 template<> struct IsInteger<unsigned int> { 0060 static const bool value = true; 0061 }; 0062 template<> struct IsInteger<long> { 0063 static const bool value = true; 0064 }; 0065 template<> struct IsInteger<unsigned long> { 0066 static const bool value = true; 0067 }; 0068 template<> struct IsInteger<long long> { 0069 static const bool value = true; 0070 }; 0071 template<> struct IsInteger<unsigned long long> { 0072 static const bool value = true; 0073 }; 0074 0075 #if !defined(WTF_COMPILER_MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) 0076 template<> struct IsInteger<wchar_t> { 0077 static const bool value = true; 0078 }; 0079 #endif 0080 0081 COMPILE_ASSERT(IsInteger<bool>::value, WTF_IsInteger_bool_true) 0082 COMPILE_ASSERT(IsInteger<char>::value, WTF_IsInteger_char_true) 0083 COMPILE_ASSERT(IsInteger<signed char>::value, WTF_IsInteger_signed_char_true) 0084 COMPILE_ASSERT(IsInteger<unsigned char>::value, WTF_IsInteger_unsigned_char_true) 0085 COMPILE_ASSERT(IsInteger<short>::value, WTF_IsInteger_short_true) 0086 COMPILE_ASSERT(IsInteger<unsigned short>::value, WTF_IsInteger_unsigned_short_true) 0087 COMPILE_ASSERT(IsInteger<int>::value, WTF_IsInteger_int_true) 0088 COMPILE_ASSERT(IsInteger<unsigned int>::value, WTF_IsInteger_unsigned_int_true) 0089 COMPILE_ASSERT(IsInteger<long>::value, WTF_IsInteger_long_true) 0090 COMPILE_ASSERT(IsInteger<unsigned long>::value, WTF_IsInteger_unsigned_long_true) 0091 COMPILE_ASSERT(IsInteger<long long>::value, WTF_IsInteger_long_long_true) 0092 COMPILE_ASSERT(IsInteger<unsigned long long>::value, WTF_IsInteger_unsigned_long_long_true) 0093 0094 #if !defined(WTF_COMPILER_MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) 0095 COMPILE_ASSERT(IsInteger<wchar_t>::value, WTF_IsInteger_wchar_t_true) 0096 #endif 0097 0098 COMPILE_ASSERT(!IsInteger<char *>::value, WTF_IsInteger_char_pointer_false) 0099 COMPILE_ASSERT(!IsInteger<const char * >::value, WTF_IsInteger_const_char_pointer_false) 0100 COMPILE_ASSERT(!IsInteger<volatile char * >::value, WTF_IsInteger_volatile_char_pointer__false) 0101 COMPILE_ASSERT(!IsInteger<double>::value, WTF_IsInteger_double_false) 0102 COMPILE_ASSERT(!IsInteger<float>::value, WTF_IsInteger_float_false) 0103 0104 template<typename T> struct HashTraits; 0105 0106 template<bool isInteger, typename T> struct GenericHashTraitsBase; 0107 0108 template<typename T> struct GenericHashTraitsBase<false, T> { 0109 static const bool emptyValueIsZero = false; 0110 static const bool needsDestruction = true; 0111 }; 0112 0113 // default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned) 0114 template<typename T> struct GenericHashTraitsBase<true, T> { 0115 static const bool emptyValueIsZero = true; 0116 static const bool needsDestruction = false; 0117 static void constructDeletedValue(T *slot) 0118 { 0119 *slot = static_cast<T>(-1); 0120 } 0121 static bool isDeletedValue(T value) 0122 { 0123 return value == static_cast<T>(-1); 0124 } 0125 }; 0126 0127 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { 0128 typedef T TraitType; 0129 static T emptyValue() 0130 { 0131 return T(); 0132 } 0133 }; 0134 0135 template<typename T> struct HashTraits : GenericHashTraits<T> { }; 0136 0137 template<typename T> struct FloatHashTraits : GenericHashTraits<T> { 0138 static const bool needsDestruction = false; 0139 static T emptyValue() 0140 { 0141 return std::numeric_limits<T>::infinity(); 0142 } 0143 static void constructDeletedValue(T *slot) 0144 { 0145 *slot = -std::numeric_limits<T>::infinity(); 0146 } 0147 static bool isDeletedValue(T value) 0148 { 0149 return value == -std::numeric_limits<T>::infinity(); 0150 } 0151 }; 0152 0153 template<> struct HashTraits<float> : FloatHashTraits<float> { }; 0154 template<> struct HashTraits<double> : FloatHashTraits<double> { }; 0155 0156 template<typename P> struct HashTraits<P *> : GenericHashTraits<P *> { 0157 static const bool emptyValueIsZero = true; 0158 static const bool needsDestruction = false; 0159 static void constructDeletedValue(P **slot) 0160 { 0161 *slot = reinterpret_cast<P *>(-1); 0162 } 0163 static bool isDeletedValue(P *value) 0164 { 0165 return value == reinterpret_cast<P *>(-1); 0166 } 0167 }; 0168 0169 template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > { 0170 static const bool emptyValueIsZero = true; 0171 static void constructDeletedValue(RefPtr<P> *slot) 0172 { 0173 new(slot) RefPtr<P>(HashTableDeletedValue); 0174 } 0175 static bool isDeletedValue(const RefPtr<P> &value) 0176 { 0177 return value.isHashTableDeletedValue(); 0178 } 0179 }; 0180 0181 // special traits for pairs, helpful for their use in HashMap implementation 0182 0183 template<typename FirstTraitsArg, typename SecondTraitsArg> 0184 struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > { 0185 typedef FirstTraitsArg FirstTraits; 0186 typedef SecondTraitsArg SecondTraits; 0187 typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType; 0188 0189 static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero; 0190 static TraitType emptyValue() 0191 { 0192 return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); 0193 } 0194 0195 static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction; 0196 0197 static void constructDeletedValue(TraitType *slot) 0198 { 0199 FirstTraits::constructDeletedValue(&slot->first); 0200 } 0201 static bool isDeletedValue(const TraitType &value) 0202 { 0203 return FirstTraits::isDeletedValue(value.first); 0204 } 0205 }; 0206 0207 template<typename First, typename Second> 0208 struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { }; 0209 0210 } // namespace WTF 0211 0212 using WTF::HashTraits; 0213 using WTF::PairHashTraits; 0214 0215 #endif // WTF_HashTraits_h