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
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 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
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 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
78public:
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
177private:
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
190template<typename ValueTraits, typename HashFunctions>
191struct 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
201template<typename ValueTraits, typename HashFunctions>
202struct 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
212template<typename ValueTraits, typename Translator>
213struct 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
223template<typename T, typename U, typename V, typename W, typename X>
224inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
225{
226 m_impl.swap(other.m_impl);
227}
228
229template<typename T, typename U, typename V, typename W, typename X>
230inline unsigned HashMap<T, U, V, W, X>::size() const
231{
232 return m_impl.size();
233}
234
235template<typename T, typename U, typename V, typename W, typename X>
236inline unsigned HashMap<T, U, V, W, X>::capacity() const
237{
238 return m_impl.capacity();
239}
240
241template<typename T, typename U, typename V, typename W, typename X>
242inline bool HashMap<T, U, V, W, X>::isEmpty() const
243{
244 return m_impl.isEmpty();
245}
246
247template<typename T, typename U, typename V, typename W, typename X>
248inline auto HashMap<T, U, V, W, X>::begin() -> iterator
249{
250 return m_impl.begin();
251}
252
253template<typename T, typename U, typename V, typename W, typename X>
254inline auto HashMap<T, U, V, W, X>::end() -> iterator
255{
256 return m_impl.end();
257}
258
259template<typename T, typename U, typename V, typename W, typename X>
260inline auto HashMap<T, U, V, W, X>::begin() const -> const_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() const -> const_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>::find(const KeyType& key) -> iterator
273{
274 return m_impl.find(key);
275}
276
277template<typename T, typename U, typename V, typename W, typename X>
278inline auto HashMap<T, U, V, W, X>::find(const KeyType& key) const -> const_iterator
279{
280 return m_impl.find(key);
281}
282
283template<typename T, typename U, typename V, typename W, typename X>
284inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
285{
286 return m_impl.contains(key);
287}
288
289template<typename T, typename U, typename V, typename W, typename X>
290template<typename HashTranslator, typename TYPE>
291inline typename HashMap<T, U, V, W, X>::iterator
292HashMap<T, U, V, W, X>::find(const TYPE& value)
293{
294 return m_impl.template find<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
295}
296
297template<typename T, typename U, typename V, typename W, typename X>
298template<typename HashTranslator, typename TYPE>
299inline typename HashMap<T, U, V, W, X>::const_iterator
300HashMap<T, U, V, W, X>::find(const TYPE& value) const
301{
302 return m_impl.template find<HashMapTranslatorAdapter<KeyValuePairTraits, HashTranslator>>(value);
303}
304
305template<typename T, typename U, typename V, typename W, typename X>
306template<typename HashTranslator, typename TYPE>
307auto 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
315template<typename T, typename U, typename V, typename W, typename X>
316template<typename HashTranslator, typename TYPE>
317auto 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
325template<typename T, typename U, typename V, typename W, typename X>
326template<typename HashTranslator, typename TYPE>
327inline 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
332template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
333template<typename K, typename V>
334auto 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
344template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
345template<typename K, typename V>
346ALWAYS_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
351template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
352template<typename K, typename F>
353ALWAYS_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
358template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
359template<typename T>
360auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(const KeyType& key, T&& mapped) -> AddResult
361{
362 return inlineSet(key, std::forward<T>(mapped));
363}
364
365template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
366template<typename T>
367auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(KeyType&& key, T&& mapped) -> AddResult
368{
369 return inlineSet(WTFMove(key), std::forward<T>(mapped));
370}
371
372template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
373template<typename HashTranslator, typename K, typename V>
374auto 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
379template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
380template<typename T>
381auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(const KeyType& key, T&& mapped) -> AddResult
382{
383 return inlineAdd(key, std::forward<T>(mapped));
384}
385
386template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
387template<typename T>
388auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(KeyType&& key, T&& mapped) -> AddResult
389{
390 return inlineAdd(WTFMove(key), std::forward<T>(mapped));
391}
392
393template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
394template<typename T>
395ALWAYS_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
400template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
401template<typename T>
402ALWAYS_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
407template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
408template<typename Functor>
409auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(const KeyType& key, Functor&& functor) -> AddResult
410{
411 return inlineEnsure(key, std::forward<Functor>(functor));
412}
413
414template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
415template<typename Functor>
416auto 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
421template<typename T, typename U, typename V, typename W, typename MappedTraits>
422inline auto HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const -> MappedPeekType
423{
424 return get<IdentityTranslatorType>(key);
425}
426
427template<typename T, typename U, typename V, typename W, typename MappedTraits>
428ALWAYS_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
436template<typename T, typename U, typename V, typename W, typename X>
437inline 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
446template<typename T, typename U, typename V, typename W, typename X>
447template<typename Functor>
448inline bool HashMap<T, U, V, W, X>::removeIf(Functor&& functor)
449{
450 return m_impl.removeIf(std::forward<Functor>(functor));
451}
452
453template<typename T, typename U, typename V, typename W, typename X>
454inline bool HashMap<T, U, V, W, X>::remove(const KeyType& key)
455{
456 return remove(find(key));
457}
458
459template<typename T, typename U, typename V, typename W, typename X>
460inline void HashMap<T, U, V, W, X>::clear()
461{
462 m_impl.clear();
463}
464
465template<typename T, typename U, typename V, typename W, typename MappedTraits>
466auto 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
476template<typename T, typename U, typename V, typename W, typename X>
477template<typename K>
478inline 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
483template<typename T, typename U, typename V, typename W, typename X>
484template<typename K>
485inline 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
490template<typename T, typename U, typename V, typename W, typename X>
491template<typename K>
492inline 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
497template<typename T, typename U, typename V, typename W, typename X>
498template<typename K>
499inline 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
507template<typename T, typename U, typename V, typename W, typename X>
508template<typename K>
509auto 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
514template<typename T, typename U, typename V, typename W, typename X>
515template<typename K>
516inline 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
521template<typename T, typename U, typename V, typename W, typename X>
522template<typename K>
523inline 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
533template<typename T, typename U, typename V, typename W, typename X>
534inline void HashMap<T, U, V, W, X>::checkConsistency() const
535{
536 m_impl.checkTableConsistency();
537}
538
539template<typename T, typename U, typename V, typename W, typename X>
540inline 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
556template<typename T, typename U, typename V, typename W, typename X>
557bool 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
575template<typename T, typename U, typename V, typename W, typename X>
576inline 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
583using WTF::HashMap;
584