Make possible HashSet<std::unique_ptr<>>
[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         int size() const;
67         int 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         bool operator==(const HashSet&) const;
119
120     private:
121         HashTableType m_impl;
122     };
123
124     struct IdentityExtractor {
125         template<typename T> static const T& extract(const T& t) { return t; }
126     };
127
128     template<typename HashFunctions>
129     struct HashSetTranslator {
130         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
131         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
132         template<typename T, typename U, typename V> static void translate(T& location, U&&, V&& value) { location = std::forward<V>(value); }
133     };
134
135     template<typename Translator>
136     struct HashSetTranslatorAdapter {
137         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
138         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
139         template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
140         {
141             Translator::translate(location, key, hashCode);
142         }
143     };
144
145     template<typename T, typename U, typename V>
146     inline void HashSet<T, U, V>::swap(HashSet& other)
147     {
148         m_impl.swap(other.m_impl); 
149     }
150
151     template<typename T, typename U, typename V>
152     inline int HashSet<T, U, V>::size() const
153     {
154         return m_impl.size(); 
155     }
156
157     template<typename T, typename U, typename V>
158     inline int HashSet<T, U, V>::capacity() const
159     {
160         return m_impl.capacity(); 
161     }
162
163     template<typename T, typename U, typename V>
164     inline bool HashSet<T, U, V>::isEmpty() const
165     {
166         return m_impl.isEmpty(); 
167     }
168
169     template<typename T, typename U, typename V>
170     inline auto HashSet<T, U, V>::begin() const -> iterator
171     {
172         return m_impl.begin(); 
173     }
174
175     template<typename T, typename U, typename V>
176     inline auto HashSet<T, U, V>::end() const -> iterator
177     {
178         return m_impl.end(); 
179     }
180
181     template<typename T, typename U, typename V>
182     inline auto HashSet<T, U, V>::find(const ValueType& value) const -> iterator
183     {
184         return m_impl.find(value); 
185     }
186
187     template<typename T, typename U, typename V>
188     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
189     {
190         return m_impl.contains(value); 
191     }
192
193     template<typename Value, typename HashFunctions, typename Traits>
194     template<typename HashTranslator, typename T>
195     inline auto HashSet<Value, HashFunctions, Traits>::find(const T& value) const -> iterator
196     {
197         return m_impl.template find<HashSetTranslatorAdapter<HashTranslator>>(value);
198     }
199
200     template<typename Value, typename HashFunctions, typename Traits>
201     template<typename HashTranslator, typename T>
202     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
203     {
204         return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator>>(value);
205     }
206
207     template<typename T, typename U, typename V>
208     inline auto HashSet<T, U, V>::add(const ValueType& value) -> AddResult
209     {
210         return m_impl.add(value);
211     }
212
213     template<typename T, typename U, typename V>
214     inline auto HashSet<T, U, V>::add(ValueType&& value) -> AddResult
215     {
216         return m_impl.add(WTF::move(value));
217     }
218
219     template<typename Value, typename HashFunctions, typename Traits>
220     template<typename HashTranslator, typename T>
221     inline auto HashSet<Value, HashFunctions, Traits>::add(const T& value) -> AddResult
222     {
223         return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator>>(value, value);
224     }
225
226     template<typename T, typename U, typename V>
227     template<typename IteratorType>
228     inline bool HashSet<T, U, V>::add(IteratorType begin, IteratorType end)
229     {
230         bool changed = false;
231         for (IteratorType iter = begin; iter != end; ++iter)
232             changed |= add(*iter).isNewEntry;
233         return changed;
234     }
235
236     template<typename T, typename U, typename V>
237     inline bool HashSet<T, U, V>::remove(iterator it)
238     {
239         if (it.m_impl == m_impl.end())
240             return false;
241         m_impl.internalCheckTableConsistency();
242         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
243         return true;
244     }
245
246     template<typename T, typename U, typename V>
247     inline bool HashSet<T, U, V>::remove(const ValueType& value)
248     {
249         return remove(find(value));
250     }
251
252     template<typename T, typename U, typename V>
253     inline void HashSet<T, U, V>::clear()
254     {
255         m_impl.clear(); 
256     }
257
258     template<typename T, typename U, typename V>
259     inline auto HashSet<T, U, V>::take(iterator it) -> ValueType
260     {
261         if (it == end())
262             return ValueTraits::emptyValue();
263
264         ValueType result = WTF::move(const_cast<ValueType&>(*it));
265         remove(it);
266         return result;
267     }
268
269     template<typename T, typename U, typename V>
270     inline auto HashSet<T, U, V>::take(const ValueType& value) -> ValueType
271     {
272         return take(find(value));
273     }
274
275     template<typename T, typename U, typename V>
276     inline auto HashSet<T, U, V>::takeAny() -> ValueType
277     {
278         return take(begin());
279     }
280
281     template<typename Value, typename HashFunctions, typename Traits>
282     template<typename V>
283     inline auto HashSet<Value, HashFunctions, Traits>::find(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type
284     {
285         return m_impl.template find<HashSetTranslator<HashFunctions>>(value);
286     }
287
288     template<typename Value, typename HashFunctions, typename Traits>
289     template<typename V>
290     inline auto HashSet<Value, HashFunctions, Traits>::contains(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
291     {
292         return m_impl.template contains<HashSetTranslator<HashFunctions>>(value);
293     }
294
295     template<typename Value, typename HashFunctions, typename Traits>
296     template<typename V>
297     inline auto HashSet<Value, HashFunctions, Traits>::remove(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
298     {
299         return remove(find(value));
300     }
301
302     template<typename Value, typename HashFunctions, typename Traits>
303     template<typename V>
304     inline auto HashSet<Value, HashFunctions, Traits>::take(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, ValueType>::type
305     {
306         return take(find(value));
307     }
308
309     template<typename T, typename U, typename V>
310     inline bool HashSet<T, U, V>::isValidValue(const ValueType& value)
311     {
312         if (ValueTraits::isDeletedValue(value))
313             return false;
314
315         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
316             if (value == ValueTraits::emptyValue())
317                 return false;
318         } else {
319             if (isHashTraitsEmptyValue<ValueTraits>(value))
320                 return false;
321         }
322
323         return true;
324     }
325
326     template<typename C, typename W>
327     inline void copyToVector(const C& collection, W& vector)
328     {
329         typedef typename C::const_iterator iterator;
330         
331         vector.resize(collection.size());
332         
333         iterator it = collection.begin();
334         iterator end = collection.end();
335         for (unsigned i = 0; it != end; ++it, ++i)
336             vector[i] = *it;
337     }  
338
339     template<typename T, typename U, typename V>
340     inline bool HashSet<T, U, V>::operator==(const HashSet& other) const
341     {
342         if (size() != other.size())
343             return false;
344         for (const_iterator iter = begin(); iter != end(); ++iter) {
345             if (!other.contains(*iter))
346                 return false;
347         }
348         return true;
349     }
350
351 } // namespace WTF
352
353 using WTF::HashSet;
354
355 #endif /* WTF_HashSet_h */