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 <limits>
29#include <string.h> // For memset.
30#include <utility>
31
32namespace WTF {
33
34    class String;
35
36    template<typename T> class OwnPtr;
37    template<typename T> class PassOwnPtr;
38
39    template<typename T> struct HashTraits;
40
41    template<bool isInteger, typename T> struct GenericHashTraitsBase;
42
43    enum ShouldWeakPointersBeMarkedStrongly {
44        WeakPointersActStrong,
45        WeakPointersActWeak
46    };
47
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;
51
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;
56
57        // The needsDestruction flag is used to optimize destruction and rehashing.
58        static const bool needsDestruction = true;
59
60        // The starting table size. Can be overridden when we know beforehand that
61        // a hash table will have at least N entries.
62#if defined(MEMORY_SANITIZER_INITIAL_SIZE)
63        static const unsigned minimumTableSize = 1;
64#else
65        static const unsigned minimumTableSize = 8;
66#endif
67
68        template<typename U = void>
69        struct NeedsTracingLazily {
70            static const bool value = NeedsTracing<T>::value;
71        };
72        static const WeakHandlingFlag weakHandlingFlag = IsWeak<T>::value ? WeakHandlingInCollections : NoWeakHandlingInCollections;
73    };
74
75    // Default integer traits disallow both 0 and -1 as keys (max value instead of -1 for unsigned).
76    template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTraitsBase<false, T> {
77        static const bool emptyValueIsZero = true;
78        static const bool needsDestruction = false;
79        static void constructDeletedValue(T& slot, bool) { slot = static_cast<T>(-1); }
80        static bool isDeletedValue(T value) { return value == static_cast<T>(-1); }
81    };
82
83    template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
84        typedef T TraitType;
85        typedef T EmptyValueType;
86
87        static T emptyValue() { return T(); }
88
89        // Type for functions that do not take ownership, such as contains.
90        typedef const T& PeekInType;
91        typedef T* IteratorGetType;
92        typedef const T* IteratorConstGetType;
93        typedef T& IteratorReferenceType;
94        typedef const T& IteratorConstReferenceType;
95        static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; }
96        static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; }
97        // Type for functions that take ownership, such as add.
98        // The store function either not be called or called once to store something passed in.
99        // The value passed to the store function will be PassInType.
100        typedef const T& PassInType;
101        static void store(const T& value, T& storage) { storage = value; }
102
103        // Type for return value of functions that transfer ownership, such as take.
104        typedef T PassOutType;
105        static const T& passOut(const T& value) { return value; }
106
107        // Type for return value of functions that do not transfer ownership, such as get.
108        // FIXME: We could change this type to const T& for better performance if we figured out
109        // a way to handle the return value from emptyValue, which is a temporary.
110        typedef T PeekOutType;
111        static const T& peek(const T& value) { return value; }
112    };
113
114    template<typename T> struct HashTraits : GenericHashTraits<T> { };
115
116    template<typename T> struct FloatHashTraits : GenericHashTraits<T> {
117        static const bool needsDestruction = false;
118        static T emptyValue() { return std::numeric_limits<T>::infinity(); }
119        static void constructDeletedValue(T& slot, bool) { slot = -std::numeric_limits<T>::infinity(); }
120        static bool isDeletedValue(T value) { return value == -std::numeric_limits<T>::infinity(); }
121    };
122
123    template<> struct HashTraits<float> : FloatHashTraits<float> { };
124    template<> struct HashTraits<double> : FloatHashTraits<double> { };
125
126    // Default unsigned traits disallow both 0 and max as keys -- use these traits to allow zero and disallow max - 1.
127    template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTraits<T> {
128        static const bool emptyValueIsZero = false;
129        static const bool needsDestruction = false;
130        static T emptyValue() { return std::numeric_limits<T>::max(); }
131        static void constructDeletedValue(T& slot, bool) { slot = std::numeric_limits<T>::max() - 1; }
132        static bool isDeletedValue(T value) { return value == std::numeric_limits<T>::max() - 1; }
133    };
134
135    template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
136        static const bool emptyValueIsZero = true;
137        static const bool needsDestruction = false;
138        static void constructDeletedValue(P*& slot, bool) { slot = reinterpret_cast<P*>(-1); }
139        static bool isDeletedValue(P* value) { return value == reinterpret_cast<P*>(-1); }
140    };
141
142    template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> {
143        static const bool emptyValueIsZero = true;
144        static void constructDeletedValue(T& slot, bool) { new (NotNull, &slot) T(HashTableDeletedValue); }
145        static bool isDeletedValue(const T& value) { return value.isHashTableDeletedValue(); }
146    };
147
148    template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<OwnPtr<P> > {
149        typedef std::nullptr_t EmptyValueType;
150
151        static EmptyValueType emptyValue() { return nullptr; }
152
153        static const bool hasIsEmptyValueFunction = true;
154        static bool isEmptyValue(const OwnPtr<P>& value) { return !value; }
155
156        typedef typename OwnPtr<P>::PtrType PeekInType;
157
158        typedef PassOwnPtr<P> PassInType;
159        static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = value; }
160
161        typedef PassOwnPtr<P> PassOutType;
162        static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release(); }
163        static PassOwnPtr<P> passOut(std::nullptr_t) { return nullptr; }
164
165        typedef typename OwnPtr<P>::PtrType PeekOutType;
166        static PeekOutType peek(const OwnPtr<P>& value) { return value.get(); }
167        static PeekOutType peek(std::nullptr_t) { return 0; }
168    };
169
170    template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<RefPtr<P> > {
171        typedef std::nullptr_t EmptyValueType;
172        static EmptyValueType emptyValue() { return nullptr; }
173
174        static const bool hasIsEmptyValueFunction = true;
175        static bool isEmptyValue(const RefPtr<P>& value) { return !value; }
176
177        typedef RefPtrValuePeeker<P> PeekInType;
178        typedef RefPtr<P>* IteratorGetType;
179        typedef const RefPtr<P>* IteratorConstGetType;
180        typedef RefPtr<P>& IteratorReferenceType;
181        typedef const RefPtr<P>& IteratorConstReferenceType;
182        static IteratorReferenceType getToReferenceConversion(IteratorGetType x) { return *x; }
183        static IteratorConstReferenceType getToReferenceConstConversion(IteratorConstGetType x) { return *x; }
184
185        typedef PassRefPtr<P> PassInType;
186        static void store(PassRefPtr<P> value, RefPtr<P>& storage) { storage = value; }
187
188        typedef PassRefPtr<P> PassOutType;
189        static PassOutType passOut(RefPtr<P>& value) { return value.release(); }
190        static PassOutType passOut(std::nullptr_t) { return nullptr; }
191
192        typedef P* PeekOutType;
193        static PeekOutType peek(const RefPtr<P>& value) { return value.get(); }
194        static PeekOutType peek(std::nullptr_t) { return 0; }
195    };
196
197    template<typename T> struct HashTraits<RawPtr<T> > : HashTraits<T*> { };
198
199    template<> struct HashTraits<String> : SimpleClassHashTraits<String> {
200        static const bool hasIsEmptyValueFunction = true;
201        static bool isEmptyValue(const String&);
202    };
203
204    // This struct template is an implementation detail of the isHashTraitsEmptyValue function,
205    // which selects either the emptyValue function or the isEmptyValue function to check for empty values.
206    template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmptyValueChecker;
207    template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> {
208        template<typename T> static bool isEmptyValue(const T& value) { return Traits::isEmptyValue(value); }
209    };
210    template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false> {
211        template<typename T> static bool isEmptyValue(const T& value) { return value == Traits::emptyValue(); }
212    };
213    template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(const T& value)
214    {
215        return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFunction>::isEmptyValue(value);
216    }
217
218    template<typename FirstTraitsArg, typename SecondTraitsArg>
219    struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
220        typedef FirstTraitsArg FirstTraits;
221        typedef SecondTraitsArg SecondTraits;
222        typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
223        typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondTraits::EmptyValueType> EmptyValueType;
224
225        static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
226        static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue()); }
227
228        static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
229
230        static const unsigned minimumTableSize = FirstTraits::minimumTableSize;
231
232        static void constructDeletedValue(TraitType& slot, bool zeroValue)
233        {
234            FirstTraits::constructDeletedValue(slot.first, zeroValue);
235            // For GC collections the memory for the backing is zeroed when it
236            // is allocated, and the constructors may take advantage of that,
237            // especially if a GC occurs during insertion of an entry into the
238            // table. This slot is being marked deleted, but If the slot is
239            // reused at a later point, the same assumptions around memory
240            // zeroing must hold as they did at the initial allocation.
241            // Therefore we zero the value part of the slot here for GC
242            // collections.
243            if (zeroValue)
244                memset(reinterpret_cast<void*>(&slot.second), 0, sizeof(slot.second));
245        }
246        static bool isDeletedValue(const TraitType& value) { return FirstTraits::isDeletedValue(value.first); }
247    };
248
249    template<typename First, typename Second>
250    struct HashTraits<std::pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
251
252    template<typename KeyTypeArg, typename ValueTypeArg>
253    struct KeyValuePair {
254        typedef KeyTypeArg KeyType;
255
256        KeyValuePair(const KeyTypeArg& _key, const ValueTypeArg& _value)
257            : key(_key)
258            , value(_value)
259        {
260        }
261
262        template <typename OtherKeyType, typename OtherValueType>
263        KeyValuePair(const KeyValuePair<OtherKeyType, OtherValueType>& other)
264            : key(other.key)
265            , value(other.value)
266        {
267        }
268
269        KeyTypeArg key;
270        ValueTypeArg value;
271    };
272
273    template<typename KeyTraitsArg, typename ValueTraitsArg>
274    struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyTraitsArg::TraitType, typename ValueTraitsArg::TraitType> > {
275        typedef KeyTraitsArg KeyTraits;
276        typedef ValueTraitsArg ValueTraits;
277        typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits::TraitType> TraitType;
278        typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType> EmptyValueType;
279
280        static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && ValueTraits::emptyValueIsZero;
281        static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue(), ValueTraits::emptyValue()); }
282
283        static const bool needsDestruction = KeyTraits::needsDestruction || ValueTraits::needsDestruction;
284        template<typename U = void>
285        struct NeedsTracingLazily {
286            static const bool value = ShouldBeTraced<KeyTraits>::value || ShouldBeTraced<ValueTraits>::value;
287        };
288        static const WeakHandlingFlag weakHandlingFlag = (KeyTraits::weakHandlingFlag == WeakHandlingInCollections || ValueTraits::weakHandlingFlag == WeakHandlingInCollections) ? WeakHandlingInCollections : NoWeakHandlingInCollections;
289
290        static const unsigned minimumTableSize = KeyTraits::minimumTableSize;
291
292        static void constructDeletedValue(TraitType& slot, bool zeroValue)
293        {
294            KeyTraits::constructDeletedValue(slot.key, zeroValue);
295            // See similar code in this file for why we need to do this.
296            if (zeroValue)
297                memset(reinterpret_cast<void*>(&slot.value), 0, sizeof(slot.value));
298        }
299        static bool isDeletedValue(const TraitType& value) { return KeyTraits::isDeletedValue(value.key); }
300    };
301
302    template<typename Key, typename Value>
303    struct HashTraits<KeyValuePair<Key, Value> > : public KeyValuePairHashTraits<HashTraits<Key>, HashTraits<Value> > { };
304
305    template<typename T>
306    struct NullableHashTraits : public HashTraits<T> {
307        static const bool emptyValueIsZero = false;
308        static T emptyValue() { return reinterpret_cast<T>(1); }
309    };
310
311    // This is for tracing inside collections that have special support for weak
312    // pointers. The trait has a trace method which returns true if there are weak
313    // pointers to things that have not (yet) been marked live. Returning true
314    // indicates that the entry in the collection may yet be removed by weak
315    // handling. Default implementation for non-weak types is to use the regular
316    // non-weak TraceTrait. Default implementation for types with weakness is to
317    // call traceInCollection on the type's trait.
318    template<WeakHandlingFlag weakHandlingFlag, ShouldWeakPointersBeMarkedStrongly strongify, typename T, typename Traits>
319    struct TraceInCollectionTrait;
320
321} // namespace WTF
322
323using WTF::HashTraits;
324using WTF::PairHashTraits;
325using WTF::NullableHashTraits;
326using WTF::SimpleClassHashTraits;
327
328#endif // WTF_HashTraits_h
329