OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserv
ed. | |
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/StdLibExtras.h> | |
26 #include <wtf/TypeTraits.h> | |
27 #include <utility> | |
28 #include <limits> | |
29 | |
30 namespace WTF { | |
31 | |
32 class String; | |
33 | |
34 template<typename T> class OwnPtr; | |
35 template<typename T> class PassOwnPtr; | |
36 | |
37 template<typename T> struct HashTraits; | |
38 | |
39 template<bool isInteger, typename T> struct GenericHashTraitsBase; | |
40 | |
41 template<typename T> struct GenericHashTraitsBase<false, T> { | |
42 // The emptyValueIsZero flag is used to optimize allocation of empty has
h tables with zeroed memory. | |
43 static const bool emptyValueIsZero = false; | |
44 | |
45 // The hasIsEmptyValueFunction flag allows the hash table to automatical
ly generate code to check | |
46 // for the empty value when it can be done with the equality operator, b
ut allows custom functions | |
47 // for cases like String that need them. | |
48 static const bool hasIsEmptyValueFunction = false; | |
49 | |
50 // The needsDestruction flag is used to optimize destruction and rehashi
ng. | |
51 static const bool needsDestruction = true; | |
52 | |
53 // The starting table size. Can be overridden when we know beforehand th
at | |
54 // a hash table will have at least N entries. | |
55 static const int minimumTableSize = 8; | |
56 }; | |
57 | |
58 // Default integer traits disallow both 0 and -1 as keys (max value instead
of -1 for unsigned). | |
59 template<typename T> struct GenericHashTraitsBase<true, T> : GenericHashTrai
tsBase<false, T> { | |
60 static const bool emptyValueIsZero = true; | |
61 static const bool needsDestruction = false; | |
62 static void constructDeletedValue(T& slot) { slot = static_cast<T>(-1);
} | |
63 static bool isDeletedValue(T value) { return value == static_cast<T>(-1)
; } | |
64 }; | |
65 | |
66 template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInte
ger<T>::value, T> { | |
67 typedef T TraitType; | |
68 typedef T EmptyValueType; | |
69 | |
70 static T emptyValue() { return T(); } | |
71 | |
72 // Type for functions that take ownership, such as add. | |
73 // The store function either not be called or called once to store somet
hing passed in. | |
74 // The value passed to the store function will be either PassInType or P
assInType&. | |
75 typedef const T& PassInType; | |
76 static void store(const T& value, T& storage) { storage = value; } | |
77 | |
78 // Type for return value of functions that transfer ownership, such as t
ake. | |
79 typedef T PassOutType; | |
80 static PassOutType passOut(const T& value) { return value; } | |
81 | |
82 // Type for return value of functions that do not transfer ownership, su
ch as get. | |
83 // FIXME: We could change this type to const T& for better performance i
f we figured out | |
84 // a way to handle the return value from emptyValue, which is a temporar
y. | |
85 typedef T PeekType; | |
86 static PeekType peek(const T& value) { return value; } | |
87 }; | |
88 | |
89 template<typename T> struct HashTraits : GenericHashTraits<T> { }; | |
90 | |
91 template<typename T> struct FloatHashTraits : GenericHashTraits<T> { | |
92 static const bool needsDestruction = false; | |
93 static T emptyValue() { return std::numeric_limits<T>::infinity(); } | |
94 static void constructDeletedValue(T& slot) { slot = -std::numeric_limits
<T>::infinity(); } | |
95 static bool isDeletedValue(T value) { return value == -std::numeric_limi
ts<T>::infinity(); } | |
96 }; | |
97 | |
98 template<> struct HashTraits<float> : FloatHashTraits<float> { }; | |
99 template<> struct HashTraits<double> : FloatHashTraits<double> { }; | |
100 | |
101 // Default unsigned traits disallow both 0 and max as keys -- use these trai
ts to allow zero and disallow max - 1. | |
102 template<typename T> struct UnsignedWithZeroKeyHashTraits : GenericHashTrait
s<T> { | |
103 static const bool emptyValueIsZero = false; | |
104 static const bool needsDestruction = false; | |
105 static T emptyValue() { return std::numeric_limits<T>::max(); } | |
106 static void constructDeletedValue(T& slot) { slot = std::numeric_limits<
T>::max() - 1; } | |
107 static bool isDeletedValue(T value) { return value == std::numeric_limit
s<T>::max() - 1; } | |
108 }; | |
109 | |
110 template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> { | |
111 static const bool emptyValueIsZero = true; | |
112 static const bool needsDestruction = false; | |
113 static void constructDeletedValue(P*& slot) { slot = reinterpret_cast<P*
>(-1); } | |
114 static bool isDeletedValue(P* value) { return value == reinterpret_cast<
P*>(-1); } | |
115 }; | |
116 | |
117 template<typename T> struct SimpleClassHashTraits : GenericHashTraits<T> { | |
118 static const bool emptyValueIsZero = true; | |
119 static void constructDeletedValue(T& slot) { new (NotNull, &slot) T(Hash
TableDeletedValue); } | |
120 static bool isDeletedValue(const T& value) { return value.isHashTableDel
etedValue(); } | |
121 }; | |
122 | |
123 template<typename P> struct HashTraits<OwnPtr<P> > : SimpleClassHashTraits<O
wnPtr<P> > { | |
124 typedef std::nullptr_t EmptyValueType; | |
125 | |
126 static EmptyValueType emptyValue() { return nullptr; } | |
127 | |
128 typedef PassOwnPtr<P> PassInType; | |
129 static void store(PassOwnPtr<P> value, OwnPtr<P>& storage) { storage = v
alue; } | |
130 | |
131 typedef PassOwnPtr<P> PassOutType; | |
132 static PassOwnPtr<P> passOut(OwnPtr<P>& value) { return value.release();
} | |
133 static PassOwnPtr<P> passOut(std::nullptr_t) { return nullptr; } | |
134 | |
135 typedef typename OwnPtr<P>::PtrType PeekType; | |
136 static PeekType peek(const OwnPtr<P>& value) { return value.get(); } | |
137 static PeekType peek(std::nullptr_t) { return 0; } | |
138 }; | |
139 | |
140 template<typename P> struct HashTraits<RefPtr<P> > : SimpleClassHashTraits<R
efPtr<P> > { | |
141 typedef PassRefPtr<P> PassInType; | |
142 static void store(PassRefPtr<P> value, RefPtr<P>& storage) { storage = v
alue; } | |
143 | |
144 // FIXME: We should change PassOutType to PassRefPtr for better performa
nce. | |
145 // FIXME: We should consider changing PeekType to a raw pointer for bett
er performance, | |
146 // but then callers won't need to call get; doing so will require updati
ng many call sites. | |
147 }; | |
148 | |
149 template<> struct HashTraits<String> : SimpleClassHashTraits<String> { | |
150 static const bool hasIsEmptyValueFunction = true; | |
151 static bool isEmptyValue(const String&); | |
152 }; | |
153 | |
154 // This struct template is an implementation detail of the isHashTraitsEmpty
Value function, | |
155 // which selects either the emptyValue function or the isEmptyValue function
to check for empty values. | |
156 template<typename Traits, bool hasEmptyValueFunction> struct HashTraitsEmpty
ValueChecker; | |
157 template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, true> { | |
158 template<typename T> static bool isEmptyValue(const T& value) { return T
raits::isEmptyValue(value); } | |
159 }; | |
160 template<typename Traits> struct HashTraitsEmptyValueChecker<Traits, false>
{ | |
161 template<typename T> static bool isEmptyValue(const T& value) { return v
alue == Traits::emptyValue(); } | |
162 }; | |
163 template<typename Traits, typename T> inline bool isHashTraitsEmptyValue(con
st T& value) | |
164 { | |
165 return HashTraitsEmptyValueChecker<Traits, Traits::hasIsEmptyValueFuncti
on>::isEmptyValue(value); | |
166 } | |
167 | |
168 template<typename FirstTraitsArg, typename SecondTraitsArg> | |
169 struct PairHashTraits : GenericHashTraits<std::pair<typename FirstTraitsArg:
:TraitType, typename SecondTraitsArg::TraitType> > { | |
170 typedef FirstTraitsArg FirstTraits; | |
171 typedef SecondTraitsArg SecondTraits; | |
172 typedef std::pair<typename FirstTraits::TraitType, typename SecondTraits
::TraitType> TraitType; | |
173 typedef std::pair<typename FirstTraits::EmptyValueType, typename SecondT
raits::EmptyValueType> EmptyValueType; | |
174 | |
175 static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && Se
condTraits::emptyValueIsZero; | |
176 static EmptyValueType emptyValue() { return std::make_pair(FirstTraits::
emptyValue(), SecondTraits::emptyValue()); } | |
177 | |
178 static const bool needsDestruction = FirstTraits::needsDestruction || Se
condTraits::needsDestruction; | |
179 | |
180 static const int minimumTableSize = FirstTraits::minimumTableSize; | |
181 | |
182 static void constructDeletedValue(TraitType& slot) { FirstTraits::constr
uctDeletedValue(slot.first); } | |
183 static bool isDeletedValue(const TraitType& value) { return FirstTraits:
:isDeletedValue(value.first); } | |
184 }; | |
185 | |
186 template<typename First, typename Second> | |
187 struct HashTraits<std::pair<First, Second> > : public PairHashTraits<HashTra
its<First>, HashTraits<Second> > { }; | |
188 | |
189 template<typename KeyTypeArg, typename ValueTypeArg> | |
190 struct KeyValuePair { | |
191 typedef KeyTypeArg KeyType; | |
192 | |
193 KeyValuePair() | |
194 { | |
195 } | |
196 | |
197 KeyValuePair(const KeyTypeArg& key, const ValueTypeArg& value) | |
198 : key(key) | |
199 , value(value) | |
200 { | |
201 } | |
202 | |
203 template <typename OtherKeyType, typename OtherValueType> | |
204 KeyValuePair(const KeyValuePair<OtherKeyType, OtherValueType>& other) | |
205 : key(other.key) | |
206 , value(other.value) | |
207 { | |
208 } | |
209 | |
210 KeyTypeArg key; | |
211 ValueTypeArg value; | |
212 }; | |
213 | |
214 template<typename KeyTraitsArg, typename ValueTraitsArg> | |
215 struct KeyValuePairHashTraits : GenericHashTraits<KeyValuePair<typename KeyT
raitsArg::TraitType, typename ValueTraitsArg::TraitType> > { | |
216 typedef KeyTraitsArg KeyTraits; | |
217 typedef ValueTraitsArg ValueTraits; | |
218 typedef KeyValuePair<typename KeyTraits::TraitType, typename ValueTraits
::TraitType> TraitType; | |
219 typedef KeyValuePair<typename KeyTraits::EmptyValueType, typename ValueT
raits::EmptyValueType> EmptyValueType; | |
220 | |
221 static const bool emptyValueIsZero = KeyTraits::emptyValueIsZero && Valu
eTraits::emptyValueIsZero; | |
222 static EmptyValueType emptyValue() { return KeyValuePair<typename KeyTra
its::EmptyValueType, typename ValueTraits::EmptyValueType>(KeyTraits::emptyValue
(), ValueTraits::emptyValue()); } | |
223 | |
224 static const bool needsDestruction = KeyTraits::needsDestruction || Valu
eTraits::needsDestruction; | |
225 | |
226 static const int minimumTableSize = KeyTraits::minimumTableSize; | |
227 | |
228 static void constructDeletedValue(TraitType& slot) { KeyTraits::construc
tDeletedValue(slot.key); } | |
229 static bool isDeletedValue(const TraitType& value) { return KeyTraits::i
sDeletedValue(value.key); } | |
230 }; | |
231 | |
232 template<typename Key, typename Value> | |
233 struct HashTraits<KeyValuePair<Key, Value> > : public KeyValuePairHashTraits
<HashTraits<Key>, HashTraits<Value> > { }; | |
234 | |
235 template<typename T> | |
236 struct NullableHashTraits : public HashTraits<T> { | |
237 static const bool emptyValueIsZero = false; | |
238 static T emptyValue() { return reinterpret_cast<T>(1); } | |
239 }; | |
240 | |
241 } // namespace WTF | |
242 | |
243 using WTF::HashTraits; | |
244 using WTF::PairHashTraits; | |
245 using WTF::NullableHashTraits; | |
246 using WTF::SimpleClassHashTraits; | |
247 | |
248 #endif // WTF_HashTraits_h | |
OLD | NEW |