Record the HashSet/HashMap operations in DFG/FTL/B3 and replay them in a benchmark
[WebKit-https.git] / Source / WTF / wtf / HashMap.h
1 /*
2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2013 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_HashMap_h
22 #define WTF_HashMap_h
23
24 #include <initializer_list>
25 #include <wtf/DataLog.h>
26 #include <wtf/HashTable.h>
27 #include <wtf/IteratorRange.h>
28
29 namespace WTF {
30
31 template<typename T> struct KeyValuePairKeyExtractor {
32     static const typename T::KeyType& extract(const T& p) { return p.key; }
33 };
34
35 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
36     typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg>>
37 class HashMap final {
38     WTF_MAKE_FAST_ALLOCATED;
39 private:
40     typedef KeyTraitsArg KeyTraits;
41     typedef MappedTraitsArg MappedTraits;
42
43     struct KeyValuePairTraits : KeyValuePairHashTraits<KeyTraits, MappedTraits> {
44         static const bool hasIsEmptyValueFunction = true;
45         static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits, MappedTraits>::TraitType& value)
46         {
47             return isHashTraitsEmptyValue<KeyTraits>(value.key);
48         }
49     };
50
51 public:
52     typedef typename KeyTraits::TraitType KeyType;
53     typedef typename MappedTraits::TraitType MappedType;
54     typedef typename KeyValuePairTraits::TraitType KeyValuePairType;
55
56 private:
57     typedef typename MappedTraits::PeekType MappedPeekType;
58     typedef typename MappedTraits::TakeType MappedTakeType;
59
60     typedef HashArg HashFunctions;
61
62     typedef HashTable<KeyType, KeyValuePairType, KeyValuePairKeyExtractor<KeyValuePairType>,
63         HashFunctions, KeyValuePairTraits, KeyTraits> HashTableType;
64
65     class HashMapKeysProxy;
66     class HashMapValuesProxy;
67
68 public:
69     typedef HashTableIteratorAdapter<HashTableType, KeyValuePairType> iterator;
70     typedef HashTableConstIteratorAdapter<HashTableType, KeyValuePairType> const_iterator;
71     typedef typename HashTableType::AddResult AddResult;
72
73 public:
74     HashMap()
75     {
76     }
77
78     HashMap(std::initializer_list<KeyValuePairType> initializerList)
79     {
80         for (const auto& keyValuePair : initializerList)
81             add(keyValuePair.key, keyValuePair.value);
82     }
83     
84     void swap(HashMap&);
85
86     unsigned size() const;
87     unsigned capacity() const;
88     bool isEmpty() const;
89
90     // iterators iterate over pairs of keys and values
91     iterator begin();
92     iterator end();
93     const_iterator begin() const;
94     const_iterator end() const;
95
96     IteratorRange<typename iterator::Keys> keys() { return makeIteratorRange(begin().keys(), end().keys()); }
97     const IteratorRange<typename const_iterator::Keys> keys() const { return makeIteratorRange(begin().keys(), end().keys()); }
98
99     IteratorRange<typename iterator::Values> values() { return makeIteratorRange(begin().values(), end().values()); }
100     const IteratorRange<typename const_iterator::Values> values() const { return makeIteratorRange(begin().values(), end().values()); }
101
102     iterator find(const KeyType&);
103     const_iterator find(const KeyType&) const;
104     bool contains(const KeyType&) const;
105     MappedPeekType get(const KeyType&) const;
106
107     // Same as get(), but aggressively inlined.
108     MappedPeekType fastGet(const KeyType&) const;
109
110     // Replaces the value but not the key if the key is already present.
111     // Return value includes both an iterator to the key location,
112     // and an isNewEntry boolean that's true if a new entry was added.
113     template<typename V> AddResult set(const KeyType&, V&&);
114     template<typename V> AddResult set(KeyType&&, V&&);
115
116     // Does nothing if the key is already present.
117     // Return value includes both an iterator to the key location,
118     // and an isNewEntry boolean that's true if a new entry was added.
119     template<typename V> AddResult add(const KeyType&, V&&);
120     template<typename V> AddResult add(KeyType&&, V&&);
121
122     // Same as add(), but aggressively inlined.
123     template<typename V> AddResult fastAdd(const KeyType&, V&&);
124     template<typename V> AddResult fastAdd(KeyType&&, V&&);
125
126     template<typename Functor> AddResult ensure(const KeyType&, Functor&&);
127     template<typename Functor> AddResult ensure(KeyType&&, Functor&&);
128
129     bool remove(const KeyType&);
130     bool remove(iterator);
131     template<typename Functor>
132     void removeIf(Functor&&);
133     void clear();
134
135     MappedTakeType take(const KeyType&); // efficient combination of get with remove
136
137     // An alternate version of find() that finds the object by hashing and comparing
138     // with some other type, to avoid the cost of type conversion. HashTranslator
139     // must have the following function members:
140     //   static unsigned hash(const T&);
141     //   static bool equal(const ValueType&, const T&);
142     template<typename HashTranslator, typename T> iterator find(const T&);
143     template<typename HashTranslator, typename T> const_iterator find(const T&) const;
144     template<typename HashTranslator, typename T> bool contains(const T&) const;
145
146     // An alternate version of add() that finds the object by hashing and comparing
147     // with some other type, to avoid the cost of type conversion if the object is already
148     // in the table. HashTranslator must have the following function members:
149     //   static unsigned hash(const T&);
150     //   static bool equal(const ValueType&, const T&);
151     //   static translate(ValueType&, const T&, unsigned hashCode);
152     template<typename HashTranslator, typename K, typename V> AddResult add(K&&, V&&);
153
154     // Overloads for smart pointer keys that take the raw pointer type as the parameter.
155     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, iterator>::type find(typename GetPtrHelper<K>::PtrType);
156     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, const_iterator>::type find(typename GetPtrHelper<K>::PtrType) const;
157     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, bool>::type contains(typename GetPtrHelper<K>::PtrType) const;
158     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type inlineGet(typename GetPtrHelper<K>::PtrType) const;
159     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type get(typename GetPtrHelper<K>::PtrType) const;
160     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, bool>::type remove(typename GetPtrHelper<K>::PtrType);
161     template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedTakeType>::type take(typename GetPtrHelper<K>::PtrType);
162
163     void checkConsistency() const;
164
165     static bool isValidKey(const KeyType&);
166
167 private:
168     template<typename K, typename V>
169     AddResult inlineSet(K&&, V&&);
170
171     template<typename K, typename V>
172     AddResult inlineAdd(K&&, V&&);
173
174     template<typename K, typename F>
175     AddResult inlineEnsure(K&&, F&&);
176
177     HashTableType m_impl;
178 };
179
180 template<typename ValueTraits, typename HashFunctions>
181 struct HashMapTranslator {
182     template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
183     template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
184     template<typename T, typename U, typename V> static void translate(T& location, U&& key, V&& mapped)
185     {
186         ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward<U>(key));
187         ValueTraits::ValueTraits::assignToEmpty(location.value, std::forward<V>(mapped));
188     }
189 };
190
191 template<typename ValueTraits, typename HashFunctions>
192 struct HashMapEnsureTranslator {
193     template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
194     template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
195     template<typename T, typename U, typename Functor> static void translate(T& location, U&& key, Functor&& functor)
196     {
197         ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward<U>(key));
198         ValueTraits::ValueTraits::assignToEmpty(location.value, functor());
199     }
200 };
201
202 template<typename ValueTraits, typename Translator>
203 struct HashMapTranslatorAdapter {
204     template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
205     template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
206     template<typename T, typename U, typename V> static void translate(T& location, U&& key, V&& mapped, unsigned hashCode)
207     {
208         Translator::translate(location.key, key, hashCode);
209         location.value = std::forward<V>(mapped);
210     }
211 };
212
213 template<typename T, typename U, typename V, typename W, typename X>
214 inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
215 {
216     m_impl.swap(other.m_impl);
217 }
218
219 template<typename T, typename U, typename V, typename W, typename X>
220 inline unsigned HashMap<T, U, V, W, X>::size() const
221 {
222     return m_impl.size(); 
223 }
224
225 template<typename T, typename U, typename V, typename W, typename X>
226 inline unsigned HashMap<T, U, V, W, X>::capacity() const
227
228     return m_impl.capacity(); 
229 }
230
231 template<typename T, typename U, typename V, typename W, typename X>
232 inline bool HashMap<T, U, V, W, X>::isEmpty() const
233 {
234     return m_impl.isEmpty();
235 }
236
237 template<typename T, typename U, typename V, typename W, typename X>
238 inline auto HashMap<T, U, V, W, X>::begin() -> iterator
239 {
240     return m_impl.begin();
241 }
242
243 template<typename T, typename U, typename V, typename W, typename X>
244 inline auto HashMap<T, U, V, W, X>::end() -> iterator
245 {
246     return m_impl.end();
247 }
248
249 template<typename T, typename U, typename V, typename W, typename X>
250 inline auto HashMap<T, U, V, W, X>::begin() const -> const_iterator
251 {
252     return m_impl.begin();
253 }
254
255 template<typename T, typename U, typename V, typename W, typename X>
256 inline auto HashMap<T, U, V, W, X>::end() const -> const_iterator
257 {
258     return m_impl.end();
259 }
260
261 template<typename T, typename U, typename V, typename W, typename X>
262 inline auto HashMap<T, U, V, W, X>::find(const KeyType& key) -> iterator
263 {
264     return m_impl.find(key);
265 }
266
267 template<typename T, typename U, typename V, typename W, typename X>
268 inline auto HashMap<T, U, V, W, X>::find(const KeyType& key) const -> const_iterator
269 {
270     return m_impl.find(key);
271 }
272
273 template<typename T, typename U, typename V, typename W, typename X>
274 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
275 {
276     return m_impl.contains(key);
277 }
278
279 template<typename T, typename U, typename V, typename W, typename X>
280 template<typename HashTranslator, typename TYPE>
281 inline typename HashMap<T, U, V, W, X>::iterator
282 HashMap<T, U, V, W, X>::find(const TYPE& value)
283 {
284     return m_impl.template find<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
285 }
286
287 template<typename T, typename U, typename V, typename W, typename X>
288 template<typename HashTranslator, typename TYPE>
289 inline typename HashMap<T, U, V, W, X>::const_iterator 
290 HashMap<T, U, V, W, X>::find(const TYPE& value) const
291 {
292     return m_impl.template find<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
293 }
294
295 template<typename T, typename U, typename V, typename W, typename X>
296 template<typename HashTranslator, typename TYPE>
297 inline bool HashMap<T, U, V, W, X>::contains(const TYPE& value) const
298 {
299     return m_impl.template contains<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
300 }
301
302 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
303 template<typename K, typename V>
304 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineSet(K&& key, V&& value) -> AddResult
305 {
306     AddResult result = inlineAdd(std::forward<K>(key), std::forward<V>(value));
307     if (!result.isNewEntry) {
308         // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
309         result.iterator->value = std::forward<V>(value);
310     }
311     return result;
312 }
313
314 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
315 template<typename K, typename V>
316 ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineAdd(K&& key, V&& value) -> AddResult
317 {
318     return m_impl.template add<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(std::forward<K>(key), std::forward<V>(value));
319 }
320
321 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
322 template<typename K, typename F>
323 ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineEnsure(K&& key, F&& functor) -> AddResult
324 {
325     return m_impl.template add<HashMapEnsureTranslator<KeyValuePairTraits, HashFunctions>>(std::forward<K>(key), std::forward<F>(functor));
326 }
327
328 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
329 template<typename T>
330 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(const KeyType& key, T&& mapped) -> AddResult
331 {
332     return inlineSet(key, std::forward<T>(mapped));
333 }
334
335 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
336 template<typename T>
337 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(KeyType&& key, T&& mapped) -> AddResult
338 {
339     return inlineSet(WTFMove(key), std::forward<T>(mapped));
340 }
341
342 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
343 template<typename HashTranslator, typename K, typename V>
344 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(K&& key, V&& value) -> AddResult
345 {
346     return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(std::forward<K>(key), std::forward<V>(value));
347 }
348
349 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
350 template<typename T>
351 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(const KeyType& key, T&& mapped) -> AddResult
352 {
353     return inlineAdd(key, std::forward<T>(mapped));
354 }
355
356 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
357 template<typename T>
358 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(KeyType&& key, T&& mapped) -> AddResult
359 {
360     return inlineAdd(WTFMove(key), std::forward<T>(mapped));
361 }
362
363 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
364 template<typename T>
365 ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::fastAdd(const KeyType& key, T&& mapped) -> AddResult
366 {
367     return inlineAdd(key, std::forward<T>(mapped));
368 }
369
370 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
371 template<typename T>
372 ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::fastAdd(KeyType&& key, T&& mapped) -> AddResult
373 {
374     return inlineAdd(WTFMove(key), std::forward<T>(mapped));
375 }
376
377 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
378 template<typename Functor>
379 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(const KeyType& key, Functor&& functor) -> AddResult
380 {
381     return inlineEnsure(key, std::forward<Functor>(functor));
382 }
383
384 template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
385 template<typename Functor>
386 auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(KeyType&& key, Functor&& functor) -> AddResult
387 {
388     return inlineEnsure(std::forward<KeyType>(key), std::forward<Functor>(functor));
389 }
390     
391 template<typename T, typename U, typename V, typename W, typename MappedTraits>
392 auto HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const -> MappedPeekType
393 {
394     KeyValuePairType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
395     if (!entry)
396         return MappedTraits::peek(MappedTraits::emptyValue());
397     return MappedTraits::peek(entry->value);
398 }
399
400 template<typename T, typename U, typename V, typename W, typename MappedTraits>
401 ALWAYS_INLINE auto HashMap<T, U, V, W, MappedTraits>::fastGet(const KeyType& key) const -> MappedPeekType
402 {
403     KeyValuePairType* entry = const_cast<HashTableType&>(m_impl).template inlineLookup<typename HashTableType::IdentityTranslatorType>(key);
404     if (!entry)
405         return MappedTraits::peek(MappedTraits::emptyValue());
406     return MappedTraits::peek(entry->value);
407 }
408
409 template<typename T, typename U, typename V, typename W, typename X>
410 inline bool HashMap<T, U, V, W, X>::remove(iterator it)
411 {
412     if (it.m_impl == m_impl.end())
413         return false;
414     m_impl.internalCheckTableConsistency();
415     m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
416     return true;
417 }
418
419 template<typename T, typename U, typename V, typename W, typename X>
420 template<typename Functor>
421 inline void HashMap<T, U, V, W, X>::removeIf(Functor&& functor)
422 {
423     m_impl.removeIf(std::forward<Functor>(functor));
424 }
425
426 template<typename T, typename U, typename V, typename W, typename X>
427 inline bool HashMap<T, U, V, W, X>::remove(const KeyType& key)
428 {
429     return remove(find(key));
430 }
431
432 template<typename T, typename U, typename V, typename W, typename X>
433 inline void HashMap<T, U, V, W, X>::clear()
434 {
435     m_impl.clear();
436 }
437
438 template<typename T, typename U, typename V, typename W, typename MappedTraits>
439 auto HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) -> MappedTakeType
440 {
441     iterator it = find(key);
442     if (it == end())
443         return MappedTraits::take(MappedTraits::emptyValue());
444     auto value = MappedTraits::take(WTFMove(it->value));
445     remove(it);
446     return value;
447 }
448
449 template<typename T, typename U, typename V, typename W, typename X>
450 template<typename K>
451 inline auto HashMap<T, U, V, W, X>::find(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, iterator>::type
452 {
453     return m_impl.template find<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key);
454 }
455
456 template<typename T, typename U, typename V, typename W, typename X>
457 template<typename K>
458 inline auto HashMap<T, U, V, W, X>::find(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, const_iterator>::type
459 {
460     return m_impl.template find<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key);
461 }
462
463 template<typename T, typename U, typename V, typename W, typename X>
464 template<typename K>
465 inline auto HashMap<T, U, V, W, X>::contains(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, bool>::type
466 {
467     return m_impl.template contains<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key);
468 }
469
470 template<typename T, typename U, typename V, typename W, typename X>
471 template<typename K>
472 inline auto HashMap<T, U, V, W, X>::inlineGet(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type
473 {
474     KeyValuePairType* entry = const_cast<HashTableType&>(m_impl).template inlineLookup<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key);
475     if (!entry)
476         return MappedTraits::peek(MappedTraits::emptyValue());
477     return MappedTraits::peek(entry->value);
478 }
479
480 template<typename T, typename U, typename V, typename W, typename X>
481 template<typename K>
482 auto HashMap<T, U, V, W, X>::get(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type
483 {
484     return inlineGet(key);
485 }
486
487 template<typename T, typename U, typename V, typename W, typename X>
488 template<typename K>
489 inline auto HashMap<T, U, V, W, X>::remove(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, bool>::type
490 {
491     return remove(find(key));
492 }
493
494 template<typename T, typename U, typename V, typename W, typename X>
495 template<typename K>
496 inline auto HashMap<T, U, V, W, X>::take(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, MappedTakeType>::type
497 {
498     iterator it = find(key);
499     if (it == end())
500         return MappedTraits::take(MappedTraits::emptyValue());
501     auto value = MappedTraits::take(WTFMove(it->value));
502     remove(it);
503     return value;
504 }
505
506 template<typename T, typename U, typename V, typename W, typename X>
507 inline void HashMap<T, U, V, W, X>::checkConsistency() const
508 {
509     m_impl.checkTableConsistency();
510 }
511
512 template<typename T, typename U, typename V, typename W, typename X>
513 inline bool HashMap<T, U, V, W, X>::isValidKey(const KeyType& key)
514 {
515     if (KeyTraits::isDeletedValue(key))
516         return false;
517
518     if (HashFunctions::safeToCompareToEmptyOrDeleted) {
519         if (key == KeyTraits::emptyValue())
520             return false;
521     } else {
522         if (isHashTraitsEmptyValue<KeyTraits>(key))
523             return false;
524     }
525
526     return true;
527 }
528
529 template<typename T, typename U, typename V, typename W, typename X>
530 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
531 {
532     if (a.size() != b.size())
533         return false;
534
535     typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;
536
537     const_iterator end = a.end();
538     const_iterator notFound = b.end();
539     for (const_iterator it = a.begin(); it != end; ++it) {
540         const_iterator bPos = b.find(it->key);
541         if (bPos == notFound || it->value != bPos->value)
542             return false;
543     }
544
545     return true;
546 }
547
548 template<typename T, typename U, typename V, typename W, typename X>
549 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
550 {
551     return !(a == b);
552 }
553
554 template<typename T, typename U, typename V, typename W, typename X, typename Y>
555 inline void copyToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
556 {
557     typedef typename HashMap<T, U, V, W, X>::const_iterator iterator;
558
559     vector.resize(collection.size());
560
561     iterator it = collection.begin();
562     iterator end = collection.end();
563     for (unsigned i = 0; it != end; ++it, ++i)
564         vector[i] = { (*it).key, (*it).value };
565 }
566
567 template<typename T, typename U, typename V, typename W, typename X, typename Y>
568 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
569 {
570     typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator;
571     
572     vector.resize(collection.size());
573     
574     iterator it = collection.begin().keys();
575     iterator end = collection.end().keys();
576     for (unsigned i = 0; it != end; ++it, ++i)
577         vector[i] = *it;
578 }  
579
580 template<typename T, typename U, typename V, typename W, typename X, typename Y>
581 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
582 {
583     typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator;
584     
585     vector.resize(collection.size());
586     
587     iterator it = collection.begin().values();
588     iterator end = collection.end().values();
589     for (unsigned i = 0; it != end; ++it, ++i)
590         vector[i] = *it;
591 }   
592
593 } // namespace WTF
594
595 using WTF::HashMap;
596
597 #endif /* WTF_HashMap_h */