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