1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Library General Public 6 * License as published by the Free Software Foundation; either 7 * version 2 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Library General Public License for more details. 13 * 14 * You should have received a copy of the GNU Library General Public License 15 * along with this library; see the file COPYING.LIB. If not, write to 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 17 * Boston, MA 02110-1301, USA. 18 * 19 */ 20 21 #ifndef WTF_HashTraits_h 22 #define WTF_HashTraits_h 23 24 #include "Assertions.h" 25 #include "HashFunctions.h" 26 #include <utility> 27 #include <limits> 28 29 namespace WTF { 30 31 using std::pair; 32 using std::make_pair; 33 34 template<typename T> struct IsInteger { static const bool value = false; }; 35 template<> struct IsInteger<bool> { static const bool value = true; }; 36 template<> struct IsInteger<char> { static const bool value = true; }; 37 template<> struct IsInteger<signed char> { static const bool value = true; }; 38 template<> struct IsInteger<unsigned char> { static const bool value = true; }; 39 template<> struct IsInteger<short> { static const bool value = true; }; 40 template<> struct IsInteger<unsigned short> { static const bool value = true; }; 41 template<> struct IsInteger<int> { static const bool value = true; }; 42 template<> struct IsInteger<unsigned int> { static const bool value = true; }; 43 template<> struct IsInteger<long> { static const bool value = true; }; 44 template<> struct IsInteger<unsigned long> { static const bool value = true; }; 45 template<> struct IsInteger<long long> { static const bool value = true; }; 46 template<> struct IsInteger<unsigned long long> { static const bool value = true; }; 47 48 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) 49 template<> struct IsInteger<wchar_t> { static const bool value = true; }; 50 #endif 51 52 COMPILE_ASSERT(IsInteger<bool>::value, WTF_IsInteger_bool_true); 53 COMPILE_ASSERT(IsInteger<char>::value, WTF_IsInteger_char_true); 54 COMPILE_ASSERT(IsInteger<signed char>::value, WTF_IsInteger_signed_char_true); 55 COMPILE_ASSERT(IsInteger<unsigned char>::value, WTF_IsInteger_unsigned_char_true); 56 COMPILE_ASSERT(IsInteger<short>::value, WTF_IsInteger_short_true); 57 COMPILE_ASSERT(IsInteger<unsigned short>::value, WTF_IsInteger_unsigned_short_true); 58 COMPILE_ASSERT(IsInteger<int>::value, WTF_IsInteger_int_true); 59 COMPILE_ASSERT(IsInteger<unsigned int>::value, WTF_IsInteger_unsigned_int_true); 60 COMPILE_ASSERT(IsInteger<long>::value, WTF_IsInteger_long_true); 61 COMPILE_ASSERT(IsInteger<unsigned long>::value, WTF_IsInteger_unsigned_long_true); 62 COMPILE_ASSERT(IsInteger<long long>::value, WTF_IsInteger_long_long_true); 63 COMPILE_ASSERT(IsInteger<unsigned long long>::value, WTF_IsInteger_unsigned_long_long_true); 64 65 #if !COMPILER(MSVC) || defined(_NATIVE_WCHAR_T_DEFINED) 66 COMPILE_ASSERT(IsInteger<wchar_t>::value, WTF_IsInteger_wchar_t_true); 67 #endif 68 69 COMPILE_ASSERT(!IsInteger<char*>::value, WTF_IsInteger_char_pointer_false); 70 COMPILE_ASSERT(!IsInteger<const char* >::value, WTF_IsInteger_const_char_pointer_false); 71 COMPILE_ASSERT(!IsInteger<volatile char* >::value, WTF_IsInteger_volatile_char_pointer__false); 72 COMPILE_ASSERT(!IsInteger<double>::value, WTF_IsInteger_double_false); 73 COMPILE_ASSERT(!IsInteger<float>::value, WTF_IsInteger_float_false); 74 75 template<typename T> struct HashTraits; 76 77 template<bool isInteger, typename T> struct GenericHashTraitsBase; 78 79 template<typename T> struct GenericHashTraitsBase<false, T> { 80 static const bool emptyValueIsZero = false; 81 static const bool needsDestruction = true; 82 }; 83 84 // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned). 85 template<typename T> struct GenericHashTraitsBase<true, T> { 86 static const bool emptyValueIsZero = true; 87 static const bool needsDestruction = false; 88 static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); } 89 static bool isDeletedValue(T value) { return value == static_cast<T>(-1); } 90 }; 91 92 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { 93 typedef T TraitType; 94 static T emptyValue() { return T(); } 95 }; 96 97 template<typename T> struct HashTraits : GenericHashTraits<T> { }; 98 99 template<typename T> struct FloatHashTraits : GenericHashTraits<T> { 100 static const bool needsDestruction = false; 101 static T emptyValue() { return std::numeric_limits<T>::infinity(); } 102 static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); } 103 static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); } 104 }; 105 106 template<> struct HashTraits<float> : FloatHashTraits<float> { }; 107 template<> struct HashTraits<double> : FloatHashTraits<double> { }; 108 109 // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1. 110 template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> { 111 static const bool emptyValueIsZero = false; 112 static const bool needsDestruction = false; 113 static T emptyValue() { return std::numeric_limits<T>::max(); } 114 static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; } 115 static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; } 116 }; 117 118 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> { 119 static const bool emptyValueIsZero = true; 120 static const bool needsDestruction = false; 121 static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); } 122 static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); } 123 }; 124 125 template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > { 126 static const bool emptyValueIsZero = true; 127 static void constructDeletedValue(RefPtr<P>& slot) { new (&slot) RefPtr<P>(HashTableDeletedValue); } 128 static bool isDeletedValue(const RefPtr<P>& value) { return value.isHashTableDeletedValue(); } 129 }; 130 131 // special traits for pairs, helpful for their use in HashMap implementation 132 133 template<typename FirstTraitsArg, typename SecondTraitsArg> 134 struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > { 135 typedef FirstTraitsArg FirstTraits; 136 typedef SecondTraitsArg SecondTraits; 137 typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType; 138 139 static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero; 140 static TraitType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); } 141 142 static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction; 143 144 static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); } 145 static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); } 146 }; 147 148 template<typename First, typename Second> 149 struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { }; 150 151 } // namespace WTF 152 153 using WTF::HashTraits; 154 using WTF::PairHashTraits; 155 156 #endif // WTF_HashTraits_h 157