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 "HashFunctions.h" 25 #include "TypeTraits.h" 26 #include <utility> 27 #include <limits> 28 29 namespace WTF { 30 31 class String; 32 33 using std::pair; 34 using std::make_pair; 35 36 template<typename T> struct HashTraits; 37 38 template<bool isInteger, typename T> struct GenericHashTraitsBase; 39 40 template<typename T> struct GenericHashTraitsBase<false, T> { 41 static const bool emptyValueIsZero = false; 42 static const bool needsDestruction = true; 43 }; 44 45 // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned). 46 template<typename T> struct GenericHashTraitsBase<true, T> { 47 static const bool emptyValueIsZero = true; 48 static const bool needsDestruction = false; 49 static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); } 50 static bool isDeletedValue(T value) { return value == static_cast<T>(-1); } 51 }; 52 53 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { 54 typedef T TraitType; 55 static T emptyValue() { return T(); } 56 }; 57 58 template<typename T> struct HashTraits : GenericHashTraits<T> { }; 59 60 template<typename T> struct FloatHashTraits : GenericHashTraits<T> { 61 static const bool needsDestruction = false; 62 static T emptyValue() { return std::numeric_limits<T>::infinity(); } 63 static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); } 64 static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); } 65 }; 66 67 template<> struct HashTraits<float> : FloatHashTraits<float> { }; 68 template<> struct HashTraits<double> : FloatHashTraits<double> { }; 69 70 // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1. 71 template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> { 72 static const bool emptyValueIsZero = false; 73 static const bool needsDestruction = false; 74 static T emptyValue() { return std::numeric_limits<T>::max(); } 75 static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; } 76 static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; } 77 }; 78 79 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> { 80 static const bool emptyValueIsZero = true; 81 static const bool needsDestruction = false; 82 static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); } 83 static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); } 84 }; 85 86 template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> { 87 static const bool emptyValueIsZero = true; 88 static void constructDeletedValue(T& slot) { new (&slot) T(HashTableDeletedValue); } 89 static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); } 90 }; 91 92 template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > { }; 93 template<> struct HashTraits<String> : SimpleClassHashTraits<String> { }; 94 95 // special traits for pairs, helpful for their use in HashMap implementation 96 97 template<typename FirstTraitsArg, typename SecondTraitsArg> 98 struct PairHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > { 99 typedef FirstTraitsArg FirstTraits; 100 typedef SecondTraitsArg SecondTraits; 101 typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType; 102 103 static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero; 104 static TraitType emptyValue() { return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); } 105 106 static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction; 107 108 static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); } 109 static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); } 110 }; 111 112 template<typename First, typename Second> 113 struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { }; 114 115 } // namespace WTF 116 117 using WTF::HashTraits; 118 using WTF::PairHashTraits; 119 120 #endif // WTF_HashTraits_h 121