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