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