1 /* 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 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 "wtf/HashFunctions.h" 25 #include "wtf/HashTableDeletedValueType.h" 26 #include "wtf/StdLibExtras.h" 27 #include "wtf/TypeTraits.h" 28 #include <utility> 29 #include <limits> 30 31 namespace WTF { 32 33 class String; 34 35 template<typename T> class OwnPtr; 36 template<typename T> class PassOwnPtr; 37 38 template<typename T> struct HashTraits; 39 40 template<bool isInteger, typename T> struct GenericHashTraitsBase; 41 42 template<typename T> struct GenericHashTraitsBase<false, T> { 43 // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory. 44 static const bool emptyValueIsZero = false; 45 46 // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check 47 // for the empty value when it can be done with the equality operator, but allows custom functions 48 // for cases like String that need them. 49 static const bool hasIsEmptyValueFunction = false; 50 51 // The needsDestruction flag is used to optimize destruction and rehashing. 52 static const bool needsDestruction = true; 53 54 // The starting table size. Can be overridden when we know beforehand that 55 // a hash table will have at least N entries. 56 #if defined(MEMORY_TOOL_REPLACES_ALLOCATOR) 57 static const unsigned minimumTableSize = 1; 58 #else 59 static const unsigned minimumTableSize = 8; 60 #endif 61 62 template<typename U = void> 63 struct NeedsTracingLazily { 64 static const bool value = NeedsTracing<T>::value; 65 }; 66 static const WeakHandlingFlag weakHandlingFlag = IsWeak<T>::value ? WeakHandlingInCollections : NoWeakHandlingInCollections; 67 template<typename Visitor> 68 static bool shouldRemoveFromCollection(Visitor*, T&) { return false; } 69 }; 70 71 // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned). 72 template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTraitsBase<false, T> { 73 static const bool emptyValueIsZero = true; 74 static const bool needsDestruction = false; 75 static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1); } 76 static bool isDeletedValue(T value) { return value == static_cast<T>(-1); } 77 }; 78 79 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { 80 typedef T TraitType; 81 typedef T EmptyValueType; 82 83 static T emptyValue() { return T(); } 84 85 // Type for functions that do not take ownership, such as contains. 86 typedef const T& PeekInType; 87 typedef T* IteratorGetType; 88 typedef const T* IteratorConstGetType; 89 typedef T& IteratorReferenceType; 90 typedef const T& IteratorConstReferenceType; 91 static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; } 92 static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; } 93 // Type for functions that take ownership, such as add. 94 // The store function either not be called or called once to store something passed in. 95 // The value passed to the store function will be PassInType. 96 typedef const T& PassInType; 97 static void store(const T& value, T& storage) { storage = value; } 98 99 // Type for return value of functions that transfer ownership, such as take. 100 typedef T PassOutType; 101 static const T& passOut(const T& value) { return value; } 102 103 // Type for return value of functions that do not transfer ownership, such as get. 104 // FIXME: We could change this type to const T& for better performance if we figured out 105 // a way to handle the return value from emptyValue, which is a temporary. 106 typedef T PeekOutType; 107 static const T& peek(const T& value) { return value; } 108 }; 109 110 template<typename T> struct HashTraits : GenericHashTraits<T> { }; 111 112 template<typename T> struct FloatHashTraits : GenericHashTraits<T> { 113 static const bool needsDestruction = false; 114 static T emptyValue() { return std::numeric_limits<T>::infinity(); } 115 static void constructDeletedValue(T& slot) { slot = -std::numeric_limits<T>::infinity(); } 116 static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); } 117 }; 118 119 template<> struct HashTraits<float> : FloatHashTraits<float> { }; 120 template<> struct HashTraits<double> : FloatHashTraits<double> { }; 121 122 // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1. 123 template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> { 124 static const bool emptyValueIsZero = false; 125 static const bool needsDestruction = false; 126 static T emptyValue() { return std::numeric_limits<T>::max(); } 127 static void constructDeletedValue(T& slot) { slot = std::numeric_limits<T>::max() - 1; } 128 static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; } 129 }; 130 131 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> { 132 static const bool emptyValueIsZero = true; 133 static const bool needsDestruction = false; 134 static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*>(-1); } 135 static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); } 136 }; 137 138 template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> { 139 static const bool emptyValueIsZero = true; 140 static void constructDeletedValue(T& slot) { new (NotNull, &slot) T(HashTableDeletedValue); } 141 static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); } 142 }; 143 144 template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<OwnPtr<P> > { 145 typedef std::nullptr_t EmptyValueType; 146 147 static EmptyValueType emptyValue() { return nullptr; } 148 149 static const bool hasIsEmptyValueFunction = true; 150 static bool isEmptyValue(const OwnPtr<P>& value) { return !value; } 151 152 typedef typename OwnPtr<P>::PtrType PeekInType; 153 154 typedef PassOwnPtr<P> PassInType; 155 static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = value; } 156 157 typedef PassOwnPtr<P> PassOutType; 158 static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release(); } 159 static PassOwnPtr<P> passOut(std::nullptr_t) { return nullptr; } 160 161 typedef typename OwnPtr<P>::PtrType PeekOutType; 162 static PeekOutType peek(const OwnPtr<P>& value) { return value.get(); } 163 static PeekOutType peek(std::nullptr_t) { return 0; } 164 }; 165 166 template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > { 167 typedef std::nullptr_t EmptyValueType; 168 static EmptyValueType emptyValue() { return nullptr; } 169 170 static const bool hasIsEmptyValueFunction = true; 171 static bool isEmptyValue(const RefPtr<P>& value) { return !value; } 172 173 typedef RefPtrValuePeeker<P> PeekInType; 174 typedef RefPtr<P>* IteratorGetType; 175 typedef const RefPtr<P>* IteratorConstGetType; 176 typedef RefPtr<P>& IteratorReferenceType; 177 typedef const RefPtr<P>& IteratorConstReferenceType; 178 static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; } 179 static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; } 180 181 typedef PassRefPtr<P> PassInType; 182 static void store(PassRefPtr<P> value, RefPtr<P>& storage) { storage = value; } 183 184 typedef PassRefPtr<P> PassOutType; 185 static PassOutType passOut(RefPtr<P>& value) { return value.release(); } 186 static PassOutType passOut(std::nullptr_t) { return nullptr; } 187 188 typedef P* PeekOutType; 189 static PeekOutType peek(const RefPtr<P>& value) { return value.get(); } 190 static PeekOutType peek(std::nullptr_t) { return 0; } 191 }; 192 193 template<typename T> struct HashTraits<RawPtr<T> > : HashTraits<T*> { }; 194 195 template<> struct HashTraits<String> : SimpleClassHashTraits<String> { 196 static const bool hasIsEmptyValueFunction = true; 197 static bool isEmptyValue(const String&); 198 }; 199 200 // This struct template is an implementation detail of the isHashTraitsEmptyValue function, 201 // which selects either the emptyValue function or the isEmptyValue function to check for empty values. 202 template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker; 203 template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> { 204 template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); } 205 }; 206 template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> { 207 template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); } 208 }; 209 template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value) 210 { 211 return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value); 212 } 213 214 template<typename FirstTraitsArg, typename SecondTraitsArg> 215 struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > { 216 typedef FirstTraitsArg FirstTraits; 217 typedef SecondTraitsArg SecondTraits; 218 typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType; 219 typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondTraits::EmptyValueType> EmptyValueType; 220 221 static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero; 222 static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); } 223 224 static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction; 225 226 static const unsigned minimumTableSize = FirstTraits::minimumTableSize; 227 228 static void constructDeletedValue(TraitType& slot) { FirstTraits::constructDeletedValue(slot.first); } 229 static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); } 230 }; 231 232 template<typename First, typename Second> 233 struct HashTraits<std::pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { }; 234 235 template<typename KeyTypeArg, typename ValueTypeArg> 236 struct KeyValuePair { 237 typedef KeyTypeArg KeyType; 238 239 KeyValuePair() 240 { 241 } 242 243 KeyValuePair(const KeyTypeArg& _key, const ValueTypeArg& _value) 244 : key(_key) 245 , value(_value) 246 { 247 } 248 249 template <typename OtherKeyType, typename OtherValueType> 250 KeyValuePair(const KeyValuePair<OtherKeyType, OtherValueType>& other) 251 : key(other.key) 252 , value(other.value) 253 { 254 } 255 256 KeyTypeArg key; 257 ValueTypeArg value; 258 }; 259 260 template<typename KeyTraitsArg, typename ValueTraitsArg> 261 struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTraitsArg::TraitType, typename ValueTraitsArg::TraitType> > { 262 typedef KeyTraitsArg KeyTraits; 263 typedef ValueTraitsArg ValueTraits; 264 typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType; 265 typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType; 266 267 static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero; 268 static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); } 269 270 static const bool needsDestruction = KeyTraits::needsDestruction || ValueTraits::needsDestruction; 271 template<typename U = void> 272 struct NeedsTracingLazily { 273 static const bool value = ShouldBeTraced<KeyTraits>::value || ShouldBeTraced<ValueTraits>::value; 274 }; 275 static const WeakHandlingFlag weakHandlingFlag = (KeyTraits::weakHandlingFlag == WeakHandlingInCollections || ValueTraits::weakHandlingFlag == WeakHandlingInCollections) ? WeakHandlingInCollections : NoWeakHandlingInCollections; 276 277 static const unsigned minimumTableSize = KeyTraits::minimumTableSize; 278 279 static void constructDeletedValue(TraitType& slot) { KeyTraits::constructDeletedValue(slot.key); } 280 static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); } 281 template<typename Visitor> 282 static bool shouldRemoveFromCollection(Visitor* visitor, TraitType& pair) 283 { 284 return KeyTraits::shouldRemoveFromCollection(visitor, pair.key) 285 || ValueTraits::shouldRemoveFromCollection(visitor, pair.value); 286 } 287 }; 288 289 template<typename Key, typename Value> 290 struct HashTraits<KeyValuePair<Key, Value> > : public KeyValuePairHashTraits<HashTraits<Key>, HashTraits<Value> > { }; 291 292 template<typename T> 293 struct NullableHashTraits : public HashTraits<T> { 294 static const bool emptyValueIsZero = false; 295 static T emptyValue() { return reinterpret_cast<T>(1); } 296 }; 297 298 } // namespace WTF 299 300 using WTF::HashTraits; 301 using WTF::PairHashTraits; 302 using WTF::NullableHashTraits; 303 using WTF::SimpleClassHashTraits; 304 305 #endif // WTF_HashTraits_h 306