Replace WTF::move with WTFMove
[WebKit-https.git] / Source / WTF / wtf / HashSet.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_HashSet_h
22 #define WTF_HashSet_h
23
24 #include <initializer_list>
25 #include <wtf/FastMalloc.h>
26 #include <wtf/GetPtr.h>
27 #include <wtf/HashTable.h>
28
29 namespace WTF {
30
31     struct IdentityExtractor;
32     
33     template<typename Value, typename HashFunctions, typename Traits> class HashSet;
34
35     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
36         typename TraitsArg = HashTraits<ValueArg>> class HashSet final {
37         WTF_MAKE_FAST_ALLOCATED;
38     private:
39         typedef HashArg HashFunctions;
40         typedef TraitsArg ValueTraits;
41
42     public:
43         typedef typename ValueTraits::TraitType ValueType;
44
45     private:
46         typedef HashTable<ValueType, ValueType, IdentityExtractor,
47             HashFunctions, ValueTraits, ValueTraits> HashTableType;
48
49     public:
50         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;
51         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
52         typedef typename HashTableType::AddResult AddResult;
53
54         HashSet()
55         {
56         }
57
58         HashSet(std::initializer_list<ValueArg> initializerList)
59         {
60             for (const auto& value : initializerList)
61                 add(value);
62         }
63
64         void swap(HashSet&);
65
66         unsigned size() const;
67         unsigned capacity() const;
68         bool isEmpty() const;
69
70         iterator begin() const;
71         iterator end() const;
72
73         iterator find(const ValueType&) const;
74         bool contains(const ValueType&) const;
75
76         // An alternate version of find() that finds the object by hashing and comparing
77         // with some other type, to avoid the cost of type conversion. HashTranslator
78         // must have the following function members:
79         //   static unsigned hash(const T&);
80         //   static bool equal(const ValueType&, const T&);
81         template<typename HashTranslator, typename T> iterator find(const T&) const;
82         template<typename HashTranslator, typename T> bool contains(const T&) const;
83
84         // The return value includes both an iterator to the added value's location,
85         // and an isNewEntry bool that indicates if it is a new or existing entry in the set.
86         AddResult add(const ValueType&);
87         AddResult add(ValueType&&);
88
89         // An alternate version of add() that finds the object by hashing and comparing
90         // with some other type, to avoid the cost of type conversion if the object is already
91         // in the table. HashTranslator must have the following function members:
92         //   static unsigned hash(const T&);
93         //   static bool equal(const ValueType&, const T&);
94         //   static translate(ValueType&, const T&, unsigned hashCode);
95         template<typename HashTranslator, typename T> AddResult add(const T&);
96         
97         // Attempts to add a list of things to the set. Returns true if any of
98         // them are new to the set. Returns false if the set is unchanged.
99         template<typename IteratorType>
100         bool add(IteratorType begin, IteratorType end);
101
102         bool remove(const ValueType&);
103         bool remove(iterator);
104         void clear();
105
106         ValueType take(const ValueType&);
107         ValueType take(iterator);
108         ValueType takeAny();
109
110         // Overloads for smart pointer values that take the raw pointer type as the parameter.
111         template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type find(typename GetPtrHelper<V>::PtrType) const;
112         template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, bool>::type contains(typename GetPtrHelper<V>::PtrType) const;
113         template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, bool>::type remove(typename GetPtrHelper<V>::PtrType);
114         template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, ValueType>::type take(typename GetPtrHelper<V>::PtrType);
115
116         static bool isValidValue(const ValueType&);
117
118         template<typename OtherCollection>
119         bool operator==(const OtherCollection&) const;
120
121     private:
122         HashTableType m_impl;
123     };
124
125     struct IdentityExtractor {
126         template<typename T> static const T& extract(const T& t) { return t; }
127     };
128
129     template<typename HashFunctions>
130     struct HashSetTranslator {
131         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
132         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
133         template<typename T, typename U, typename V> static void translate(T& location, U&&, V&& value) { location = std::forward<V>(value); }
134     };
135
136     template<typename Translator>
137     struct HashSetTranslatorAdapter {
138         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
139         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
140         template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
141         {
142             Translator::translate(location, key, hashCode);
143         }
144     };
145
146     template<typename T, typename U, typename V>
147     inline void HashSet<T, U, V>::swap(HashSet& other)
148     {
149         m_impl.swap(other.m_impl); 
150     }
151
152     template<typename T, typename U, typename V>
153     inline unsigned HashSet<T, U, V>::size() const
154     {
155         return m_impl.size(); 
156     }
157
158     template<typename T, typename U, typename V>
159     inline unsigned HashSet<T, U, V>::capacity() const
160     {
161         return m_impl.capacity(); 
162     }
163
164     template<typename T, typename U, typename V>
165     inline bool HashSet<T, U, V>::isEmpty() const
166     {
167         return m_impl.isEmpty(); 
168     }
169
170     template<typename T, typename U, typename V>
171     inline auto HashSet<T, U, V>::begin() const -> iterator
172     {
173         return m_impl.begin(); 
174     }
175
176     template<typename T, typename U, typename V>
177     inline auto HashSet<T, U, V>::end() const -> iterator
178     {
179         return m_impl.end(); 
180     }
181
182     template<typename T, typename U, typename V>
183     inline auto HashSet<T, U, V>::find(const ValueType& value) const -> iterator
184     {
185         return m_impl.find(value); 
186     }
187
188     template<typename T, typename U, typename V>
189     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
190     {
191         return m_impl.contains(value); 
192     }
193
194     template<typename Value, typename HashFunctions, typename Traits>
195     template<typename HashTranslator, typename T>
196     inline auto HashSet<Value, HashFunctions, Traits>::find(const T& value) const -> iterator
197     {
198         return m_impl.template find<HashSetTranslatorAdapter<HashTranslator>>(value);
199     }
200
201     template<typename Value, typename HashFunctions, typename Traits>
202     template<typename HashTranslator, typename T>
203     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
204     {
205         return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator>>(value);
206     }
207
208     template<typename T, typename U, typename V>
209     inline auto HashSet<T, U, V>::add(const ValueType& value) -> AddResult
210     {
211         return m_impl.add(value);
212     }
213
214     template<typename T, typename U, typename V>
215     inline auto HashSet<T, U, V>::add(ValueType&& value) -> AddResult
216     {
217         return m_impl.add(WTFMove(value));
218     }
219
220     template<typename Value, typename HashFunctions, typename Traits>
221     template<typename HashTranslator, typename T>
222     inline auto HashSet<Value, HashFunctions, Traits>::add(const T& value) -> AddResult
223     {
224         return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator>>(value, value);
225     }
226
227     template<typename T, typename U, typename V>
228     template<typename IteratorType>
229     inline bool HashSet<T, U, V>::add(IteratorType begin, IteratorType end)
230     {
231         bool changed = false;
232         for (IteratorType iter = begin; iter != end; ++iter)
233             changed |= add(*iter).isNewEntry;
234         return changed;
235     }
236
237     template<typename T, typename U, typename V>
238     inline bool HashSet<T, U, V>::remove(iterator it)
239     {
240         if (it.m_impl == m_impl.end())
241             return false;
242         m_impl.internalCheckTableConsistency();
243         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
244         return true;
245     }
246
247     template<typename T, typename U, typename V>
248     inline bool HashSet<T, U, V>::remove(const ValueType& value)
249     {
250         return remove(find(value));
251     }
252
253     template<typename T, typename U, typename V>
254     inline void HashSet<T, U, V>::clear()
255     {
256         m_impl.clear(); 
257     }
258
259     template<typename T, typename U, typename V>
260     inline auto HashSet<T, U, V>::take(iterator it) -> ValueType
261     {
262         if (it == end())
263             return ValueTraits::emptyValue();
264
265         ValueType result = WTFMove(const_cast<ValueType&>(*it));
266         remove(it);
267         return result;
268     }
269
270     template<typename T, typename U, typename V>
271     inline auto HashSet<T, U, V>::take(const ValueType& value) -> ValueType
272     {
273         return take(find(value));
274     }
275
276     template<typename T, typename U, typename V>
277     inline auto HashSet<T, U, V>::takeAny() -> ValueType
278     {
279         return take(begin());
280     }
281
282     template<typename Value, typename HashFunctions, typename Traits>
283     template<typename V>
284     inline auto HashSet<Value, HashFunctions, Traits>::find(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type
285     {
286         return m_impl.template find<HashSetTranslator<HashFunctions>>(value);
287     }
288
289     template<typename Value, typename HashFunctions, typename Traits>
290     template<typename V>
291     inline auto HashSet<Value, HashFunctions, Traits>::contains(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
292     {
293         return m_impl.template contains<HashSetTranslator<HashFunctions>>(value);
294     }
295
296     template<typename Value, typename HashFunctions, typename Traits>
297     template<typename V>
298     inline auto HashSet<Value, HashFunctions, Traits>::remove(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
299     {
300         return remove(find(value));
301     }
302
303     template<typename Value, typename HashFunctions, typename Traits>
304     template<typename V>
305     inline auto HashSet<Value, HashFunctions, Traits>::take(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, ValueType>::type
306     {
307         return take(find(value));
308     }
309
310     template<typename T, typename U, typename V>
311     inline bool HashSet<T, U, V>::isValidValue(const ValueType& value)
312     {
313         if (ValueTraits::isDeletedValue(value))
314             return false;
315
316         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
317             if (value == ValueTraits::emptyValue())
318                 return false;
319         } else {
320             if (isHashTraitsEmptyValue<ValueTraits>(value))
321                 return false;
322         }
323
324         return true;
325     }
326
327     template<typename C, typename W>
328     inline void copyToVector(const C& collection, W& vector)
329     {
330         typedef typename C::const_iterator iterator;
331         
332         vector.resize(collection.size());
333         
334         iterator it = collection.begin();
335         iterator end = collection.end();
336         for (unsigned i = 0; it != end; ++it, ++i)
337             vector[i] = *it;
338     }  
339
340     template<typename T, typename U, typename V>
341     template<typename OtherCollection>
342     inline bool HashSet<T, U, V>::operator==(const OtherCollection& otherCollection) const
343     {
344         if (size() != otherCollection.size())
345             return false;
346         for (const auto& other : otherCollection) {
347             if (!contains(other))
348                 return false;
349         }
350         return true;
351     }
352
353 } // namespace WTF
354
355 using WTF::HashSet;
356
357 #endif /* WTF_HashSet_h */