2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
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.
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.
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.
21 #ifndef WTF_HashTraits_h
22 #define WTF_HashTraits_h
24 #include "wtf/HashFunctions.h"
25 #include "wtf/HashTableDeletedValueType.h"
26 #include "wtf/StdLibExtras.h"
27 #include "wtf/TypeTraits.h"
29 #include <string.h> // For memset.
36 template<typename T
> class OwnPtr
;
37 template<typename T
> class PassOwnPtr
;
39 template<typename T
> struct HashTraits
;
41 template<bool isInteger
, typename T
> struct GenericHashTraitsBase
;
43 enum ShouldWeakPointersBeMarkedStrongly
{
44 WeakPointersActStrong
,
48 template<typename T
> struct GenericHashTraitsBase
<false, T
> {
49 // The emptyValueIsZero flag is used to optimize allocation of empty hash tables with zeroed memory.
50 static const bool emptyValueIsZero
= false;
52 // The hasIsEmptyValueFunction flag allows the hash table to automatically generate code to check
53 // for the empty value when it can be done with the equality operator, but allows custom functions
54 // for cases like String that need them.
55 static const bool hasIsEmptyValueFunction
= false;
57 // The starting table size. Can be overridden when we know beforehand that
58 // a hash table will have at least N entries.
59 #if defined(MEMORY_SANITIZER_INITIAL_SIZE)
60 static const unsigned minimumTableSize
= 1;
62 static const unsigned minimumTableSize
= 8;
65 template<typename U
= void>
66 struct NeedsTracingLazily
{
67 static const bool value
= NeedsTracing
<T
>::value
;
69 static const WeakHandlingFlag weakHandlingFlag
= IsWeak
<T
>::value
? WeakHandlingInCollections
: NoWeakHandlingInCollections
;
72 // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
73 template<typename T
> struct GenericHashTraitsBase
<true, T
> : GenericHashTraitsBase
<false, T
> {
74 static const bool emptyValueIsZero
= true;
75 static void constructDeletedValue(T
& slot
, bool) { slot
= static_cast<T
>(-1); }
76 static bool isDeletedValue(T value
) { return value
== static_cast<T
>(-1); }
79 template<typename T
> struct GenericHashTraits
: GenericHashTraitsBase
<IsInteger
<T
>::value
, T
> {
81 typedef T EmptyValueType
;
83 static T
emptyValue() { return T(); }
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
; }
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
; }
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
; }
110 template<typename T
> struct HashTraits
: GenericHashTraits
<T
> { };
112 template<typename T
> struct FloatHashTraits
: GenericHashTraits
<T
> {
113 static T
emptyValue() { return std::numeric_limits
<T
>::infinity(); }
114 static void constructDeletedValue(T
& slot
, bool) { slot
= -std::numeric_limits
<T
>::infinity(); }
115 static bool isDeletedValue(T value
) { return value
== -std::numeric_limits
<T
>::infinity(); }
118 template<> struct HashTraits
<float> : FloatHashTraits
<float> { };
119 template<> struct HashTraits
<double> : FloatHashTraits
<double> { };
121 // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
122 template<typename T
> struct UnsignedWithZeroKeyHashTraits
: GenericHashTraits
<T
> {
123 static const bool emptyValueIsZero
= false;
124 static T
emptyValue() { return std::numeric_limits
<T
>::max(); }
125 static void constructDeletedValue(T
& slot
, bool) { slot
= std::numeric_limits
<T
>::max() - 1; }
126 static bool isDeletedValue(T value
) { return value
== std::numeric_limits
<T
>::max() - 1; }
129 template<typename P
> struct HashTraits
<P
*> : GenericHashTraits
<P
*> {
130 static const bool emptyValueIsZero
= true;
131 static void constructDeletedValue(P
*& slot
, bool) { slot
= reinterpret_cast<P
*>(-1); }
132 static bool isDeletedValue(P
* value
) { return value
== reinterpret_cast<P
*>(-1); }
135 template<typename T
> struct SimpleClassHashTraits
: GenericHashTraits
<T
> {
136 static const bool emptyValueIsZero
= true;
137 static void constructDeletedValue(T
& slot
, bool) { new (NotNull
, &slot
) T(HashTableDeletedValue
); }
138 static bool isDeletedValue(const T
& value
) { return value
.isHashTableDeletedValue(); }
141 template<typename P
> struct HashTraits
<OwnPtr
<P
>> : SimpleClassHashTraits
<OwnPtr
<P
>> {
142 typedef std::nullptr_t EmptyValueType
;
144 static EmptyValueType
emptyValue() { return nullptr; }
146 static const bool hasIsEmptyValueFunction
= true;
147 static bool isEmptyValue(const OwnPtr
<P
>& value
) { return !value
; }
149 typedef typename OwnPtr
<P
>::PtrType PeekInType
;
151 typedef PassOwnPtr
<P
> PassInType
;
152 static void store(PassOwnPtr
<P
> value
, OwnPtr
<P
>& storage
) { storage
= value
; }
154 typedef PassOwnPtr
<P
> PassOutType
;
155 static PassOwnPtr
<P
> passOut(OwnPtr
<P
>& value
) { return value
.release(); }
156 static PassOwnPtr
<P
> passOut(std::nullptr_t
) { return nullptr; }
158 typedef typename OwnPtr
<P
>::PtrType PeekOutType
;
159 static PeekOutType
peek(const OwnPtr
<P
>& value
) { return value
.get(); }
160 static PeekOutType
peek(std::nullptr_t
) { return 0; }
163 template<typename P
> struct HashTraits
<RefPtr
<P
>> : SimpleClassHashTraits
<RefPtr
<P
>> {
164 typedef std::nullptr_t EmptyValueType
;
165 static EmptyValueType
emptyValue() { return nullptr; }
167 static const bool hasIsEmptyValueFunction
= true;
168 static bool isEmptyValue(const RefPtr
<P
>& value
) { return !value
; }
170 typedef RefPtrValuePeeker
<P
> PeekInType
;
171 typedef RefPtr
<P
>* IteratorGetType
;
172 typedef const RefPtr
<P
>* IteratorConstGetType
;
173 typedef RefPtr
<P
>& IteratorReferenceType
;
174 typedef const RefPtr
<P
>& IteratorConstReferenceType
;
175 static IteratorReferenceType
getToReferenceConversion(IteratorGetType x
) { return *x
; }
176 static IteratorConstReferenceType
getToReferenceConstConversion(IteratorConstGetType x
) { return *x
; }
178 typedef PassRefPtr
<P
> PassInType
;
179 static void store(PassRefPtr
<P
> value
, RefPtr
<P
>& storage
) { storage
= value
; }
181 typedef PassRefPtr
<P
> PassOutType
;
182 static PassOutType
passOut(RefPtr
<P
>& value
) { return value
.release(); }
183 static PassOutType
passOut(std::nullptr_t
) { return nullptr; }
185 typedef P
* PeekOutType
;
186 static PeekOutType
peek(const RefPtr
<P
>& value
) { return value
.get(); }
187 static PeekOutType
peek(std::nullptr_t
) { return 0; }
190 template<typename T
> struct HashTraits
<RawPtr
<T
>> : HashTraits
<T
*> { };
192 template<> struct HashTraits
<String
> : SimpleClassHashTraits
<String
> {
193 static const bool hasIsEmptyValueFunction
= true;
194 static bool isEmptyValue(const String
&);
197 // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
198 // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
199 template<typename Traits
, bool hasEmptyValueFunction
> struct HashTraitsEmptyValueChecker
;
200 template<typename Traits
> struct HashTraitsEmptyValueChecker
<Traits
, true> {
201 template<typename T
> static bool isEmptyValue(const T
& value
) { return Traits::isEmptyValue(value
); }
203 template<typename Traits
> struct HashTraitsEmptyValueChecker
<Traits
, false> {
204 template<typename T
> static bool isEmptyValue(const T
& value
) { return value
== Traits::emptyValue(); }
206 template<typename Traits
, typename T
> inline bool isHashTraitsEmptyValue(const T
& value
)
208 return HashTraitsEmptyValueChecker
<Traits
, Traits::hasIsEmptyValueFunction
>::isEmptyValue(value
);
211 template<typename FirstTraitsArg
, typename SecondTraitsArg
>
212 struct PairHashTraits
: GenericHashTraits
<std::pair
<typename
FirstTraitsArg::TraitType
, typename
SecondTraitsArg::TraitType
>> {
213 typedef FirstTraitsArg FirstTraits
;
214 typedef SecondTraitsArg SecondTraits
;
215 typedef std::pair
<typename
FirstTraits::TraitType
, typename
SecondTraits::TraitType
> TraitType
;
216 typedef std::pair
<typename
FirstTraits::EmptyValueType
, typename
SecondTraits::EmptyValueType
> EmptyValueType
;
218 static const bool emptyValueIsZero
= FirstTraits::emptyValueIsZero
&& SecondTraits::emptyValueIsZero
;
219 static EmptyValueType
emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
221 static const unsigned minimumTableSize
= FirstTraits::minimumTableSize
;
223 static void constructDeletedValue(TraitType
& slot
, bool zeroValue
)
225 FirstTraits::constructDeletedValue(slot
.first
, zeroValue
);
226 // For GC collections the memory for the backing is zeroed when it
227 // is allocated, and the constructors may take advantage of that,
228 // especially if a GC occurs during insertion of an entry into the
229 // table. This slot is being marked deleted, but If the slot is
230 // reused at a later point, the same assumptions around memory
231 // zeroing must hold as they did at the initial allocation.
232 // Therefore we zero the value part of the slot here for GC
235 memset(reinterpret_cast<void*>(&slot
.second
), 0, sizeof(slot
.second
));
237 static bool isDeletedValue(const TraitType
& value
) { return FirstTraits::isDeletedValue(value
.first
); }
240 template<typename First
, typename Second
>
241 struct HashTraits
<std::pair
<First
, Second
>> : public PairHashTraits
<HashTraits
<First
>, HashTraits
<Second
>> { };
243 template<typename KeyTypeArg
, typename ValueTypeArg
>
244 struct KeyValuePair
{
245 typedef KeyTypeArg KeyType
;
247 KeyValuePair(const KeyTypeArg
& _key
, const ValueTypeArg
& _value
)
253 template <typename OtherKeyType
, typename OtherValueType
>
254 KeyValuePair(const KeyValuePair
<OtherKeyType
, OtherValueType
>& other
)
264 template<typename KeyTraitsArg
, typename ValueTraitsArg
>
265 struct KeyValuePairHashTraits
: GenericHashTraits
<KeyValuePair
<typename
KeyTraitsArg::TraitType
, typename
ValueTraitsArg::TraitType
>> {
266 typedef KeyTraitsArg KeyTraits
;
267 typedef ValueTraitsArg ValueTraits
;
268 typedef KeyValuePair
<typename
KeyTraits::TraitType
, typename
ValueTraits::TraitType
> TraitType
;
269 typedef KeyValuePair
<typename
KeyTraits::EmptyValueType
, typename
ValueTraits::EmptyValueType
> EmptyValueType
;
271 static const bool emptyValueIsZero
= KeyTraits::emptyValueIsZero
&& ValueTraits::emptyValueIsZero
;
272 static EmptyValueType
emptyValue() { return KeyValuePair
<typename
KeyTraits::EmptyValueType
, typename
ValueTraits::EmptyValueType
>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
274 template<typename U
= void>
275 struct NeedsTracingLazily
{
276 static const bool value
= ShouldBeTraced
<KeyTraits
>::value
|| ShouldBeTraced
<ValueTraits
>::value
;
278 static const WeakHandlingFlag weakHandlingFlag
= (KeyTraits::weakHandlingFlag
== WeakHandlingInCollections
|| ValueTraits::weakHandlingFlag
== WeakHandlingInCollections
) ? WeakHandlingInCollections
: NoWeakHandlingInCollections
;
280 static const unsigned minimumTableSize
= KeyTraits::minimumTableSize
;
282 static void constructDeletedValue(TraitType
& slot
, bool zeroValue
)
284 KeyTraits::constructDeletedValue(slot
.key
, zeroValue
);
285 // See similar code in this file for why we need to do this.
287 memset(reinterpret_cast<void*>(&slot
.value
), 0, sizeof(slot
.value
));
289 static bool isDeletedValue(const TraitType
& value
) { return KeyTraits::isDeletedValue(value
.key
); }
292 template<typename Key
, typename Value
>
293 struct HashTraits
<KeyValuePair
<Key
, Value
>> : public KeyValuePairHashTraits
<HashTraits
<Key
>, HashTraits
<Value
>> { };
296 struct NullableHashTraits
: public HashTraits
<T
> {
297 static const bool emptyValueIsZero
= false;
298 static T
emptyValue() { return reinterpret_cast<T
>(1); }
301 // This is for tracing inside collections that have special support for weak
302 // pointers. The trait has a trace method which returns true if there are weak
303 // pointers to things that have not (yet) been marked live. Returning true
304 // indicates that the entry in the collection may yet be removed by weak
305 // handling. Default implementation for non-weak types is to use the regular
306 // non-weak TraceTrait. Default implementation for types with weakness is to
307 // call traceInCollection on the type's trait.
308 template<WeakHandlingFlag weakHandlingFlag
, ShouldWeakPointersBeMarkedStrongly strongify
, typename T
, typename Traits
>
309 struct TraceInCollectionTrait
;
313 using WTF::HashTraits
;
314 using WTF::PairHashTraits
;
315 using WTF::NullableHashTraits
;
316 using WTF::SimpleClassHashTraits
;
318 #endif // WTF_HashTraits_h