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