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
28namespace WTF {
29
30template<typename T> struct KeyValuePairKeyExtractor {
31 static const typename T::KeyType& extract(const T& p) { return p.key; }
32};
33
34template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
35class HashMap final {
36 WTF_MAKE_FAST_ALLOCATED;
37private:
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
49public:
50 using KeyType = typename KeyTraits::TraitType;
51 using MappedType = typename MappedTraits::TraitType;
52 using KeyValuePairType = typename KeyValuePairTraits::TraitType;
53
54private:
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
67public:
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
88public:
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
189private:
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
202template<typename ValueTraits, typename HashFunctions>
203struct 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
213template<typename ValueTraits, typename HashFunctions>
214struct 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
224template<typename ValueTraits, typename Translator>
225struct 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
235template<typename T, typename U, typename V, typename W, typename X>
236inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
237{
238 m_impl.swap(other.m_impl);
239}
240
241template<typename T, typename U, typename V, typename W, typename X>
242inline unsigned HashMap<T, U, V, W, X>::size() const
243{
244 return m_impl.size();
245}
246
247template<typename T, typename U, typename V, typename W, typename X>
248inline unsigned HashMap<T, U, V, W, X>::capacity() const
249{
250 return m_impl.capacity();
251}
252
253template<typename T, typename U, typename V, typename W, typename X>
254inline bool HashMap<T, U, V, W, X>::isEmpty() const
255{
256 return m_impl.isEmpty();
257}
258
259template<typename T, typename U, typename V, typename W, typename X>
260inline auto HashMap<T, U, V, W, X>::begin() -> iterator
261{
262 return m_impl.begin();
263}
264
265template<typename T, typename U, typename V, typename W, typename X>
266inline auto HashMap<T, U, V, W, X>::end() -> iterator
267{
268 return m_impl.end();
269}
270
271template<typename T, typename U, typename V, typename W, typename X>
272inline auto HashMap<T, U, V, W, X>::begin() const -> const_iterator
273{
274 return m_impl.begin();
275}
276
277template<typename T, typename U, typename V, typename W, typename X>
278inline auto HashMap<T, U, V, W, X>::end() const -> const_iterator
279{
280 return m_impl.end();
281}
282
283template<typename T, typename U, typename V, typename W, typename X>
284inline auto HashMap<T, U, V, W, X>::find(const KeyType& key) -> iterator
285{
286 return m_impl.find(key);
287}
288
289template<typename T, typename U, typename V, typename W, typename X>
290inline auto HashMap<T, U, V, W, X>::find(const KeyType& key) const -> const_iterator
291{
292 return m_impl.find(key);
293}
294
295template<typename T, typename U, typename V, typename W, typename X>
296inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
297{
298 return m_impl.contains(key);
299}
300
301template<typename T, typename U, typename V, typename W, typename X>
302template<typename HashTranslator, typename TYPE>
303inline typename HashMap<T, U, V, W, X>::iterator
304HashMap<T, U, V, W, X>::find(const TYPE& value)
305{
306 return m_impl.template find<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
307}
308
309template<typename T, typename U, typename V, typename W, typename X>
310template<typename HashTranslator, typename TYPE>
311inline typename HashMap<T, U, V, W, X>::const_iterator
312HashMap<T, U, V, W, X>::find(const TYPE& value) const
313{
314 return m_impl.template find<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
315}
316
317template<typename T, typename U, typename V, typename W, typename X>
318template<typename HashTranslator, typename TYPE>
319auto 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
327template<typename T, typename U, typename V, typename W, typename X>
328template<typename HashTranslator, typename TYPE>
329auto 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
337template<typename T, typename U, typename V, typename W, typename X>
338template<typename HashTranslator, typename TYPE>
339inline 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
344template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
345template<typename K, typename V>
346auto 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
356template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
357template<typename K, typename V>
358ALWAYS_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
363template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
364template<typename K, typename F>
365ALWAYS_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
370template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
371template<typename T>
372auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(const KeyType& key, T&& mapped) -> AddResult
373{
374 return inlineSet(key, std::forward<T>(mapped));
375}
376
377template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
378template<typename T>
379auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(KeyType&& key, T&& mapped) -> AddResult
380{
381 return inlineSet(WTFMove(key), std::forward<T>(mapped));
382}
383
384template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
385template<typename HashTranslator, typename K, typename V>
386auto 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
391template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
392template<typename T>
393auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(const KeyType& key, T&& mapped) -> AddResult
394{
395 return inlineAdd(key, std::forward<T>(mapped));
396}
397
398template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
399template<typename T>
400auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(KeyType&& key, T&& mapped) -> AddResult
401{
402 return inlineAdd(WTFMove(key), std::forward<T>(mapped));
403}
404
405template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
406template<typename T>
407ALWAYS_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
412template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
413template<typename T>
414ALWAYS_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
419template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
420template<typename Functor>
421auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(const KeyType& key, Functor&& functor) -> AddResult
422{
423 return inlineEnsure(key, std::forward<Functor>(functor));
424}
425
426template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
427template<typename Functor>
428auto 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
433template<typename T, typename U, typename V, typename W, typename MappedTraits>
434inline auto HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const -> MappedPeekType
435{
436 return get<IdentityTranslatorType>(key);
437}
438
439template<typename T, typename U, typename V, typename W, typename MappedTraits>
440ALWAYS_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
448template<typename T, typename U, typename V, typename W, typename X>
449inline 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
458template<typename T, typename U, typename V, typename W, typename X>
459template<typename Functor>
460inline bool HashMap<T, U, V, W, X>::removeIf(Functor&& functor)
461{
462 return m_impl.removeIf(std::forward<Functor>(functor));
463}
464
465template<typename T, typename U, typename V, typename W, typename X>
466inline bool HashMap<T, U, V, W, X>::remove(const KeyType& key)
467{
468 return remove(find(key));
469}
470
471template<typename T, typename U, typename V, typename W, typename X>
472inline void HashMap<T, U, V, W, X>::clear()
473{
474 m_impl.clear();
475}
476
477template<typename T, typename U, typename V, typename W, typename MappedTraits>
478auto 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
488template<typename T, typename U, typename V, typename W, typename X>
489template<typename K>
490inline 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
495template<typename T, typename U, typename V, typename W, typename X>
496template<typename K>
497inline 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
502template<typename T, typename U, typename V, typename W, typename X>
503template<typename K>
504inline 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
509template<typename T, typename U, typename V, typename W, typename X>
510template<typename K>
511inline 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
519template<typename T, typename U, typename V, typename W, typename X>
520template<typename K>
521auto 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
526template<typename T, typename U, typename V, typename W, typename X>
527template<typename K>
528inline 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
533template<typename T, typename U, typename V, typename W, typename X>
534template<typename K>
535inline 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
545template<typename T, typename U, typename V, typename W, typename X>
546inline void HashMap<T, U, V, W, X>::checkConsistency() const
547{
548 m_impl.checkTableConsistency();
549}
550
551template<typename T, typename U, typename V, typename W, typename X>
552inline 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
568template<typename T, typename U, typename V, typename W, typename X>
569bool 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
587template<typename T, typename U, typename V, typename W, typename X>
588inline 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
595using WTF::HashMap;
596