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