Record the HashSet/HashMap operations in DFG/FTL/B3 and replay them in a benchmark
[WebKit-https.git] / Source / WTF / wtf / HashSet.h
1 /*
2  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2013, 2017 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         template<typename OtherCollection>
128         bool operator!=(const OtherCollection&) const;
129
130     private:
131         HashTableType m_impl;
132     };
133
134     struct IdentityExtractor {
135         template<typename T> static const T& extract(const T& t) { return t; }
136     };
137
138     template<typename ValueTraits, typename HashFunctions>
139     struct HashSetTranslator {
140         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
141         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
142         template<typename T, typename U, typename V> static void translate(T& location, U&&, V&& value)
143         { 
144             ValueTraits::assignToEmpty(location, std::forward<V>(value));
145         }
146     };
147
148     template<typename Translator>
149     struct HashSetTranslatorAdapter {
150         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
151         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
152         template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
153         {
154             Translator::translate(location, key, hashCode);
155         }
156     };
157
158     template<typename T, typename U, typename V>
159     inline void HashSet<T, U, V>::swap(HashSet& other)
160     {
161         m_impl.swap(other.m_impl); 
162     }
163
164     template<typename T, typename U, typename V>
165     inline unsigned HashSet<T, U, V>::size() const
166     {
167         return m_impl.size(); 
168     }
169
170     template<typename T, typename U, typename V>
171     inline unsigned HashSet<T, U, V>::capacity() const
172     {
173         return m_impl.capacity(); 
174     }
175
176     template<typename T, typename U, typename V>
177     inline bool HashSet<T, U, V>::isEmpty() const
178     {
179         return m_impl.isEmpty(); 
180     }
181
182     template<typename T, typename U, typename V>
183     inline auto HashSet<T, U, V>::begin() const -> iterator
184     {
185         return m_impl.begin(); 
186     }
187
188     template<typename T, typename U, typename V>
189     inline auto HashSet<T, U, V>::end() const -> iterator
190     {
191         return m_impl.end(); 
192     }
193
194     template<typename T, typename U, typename V>
195     inline auto HashSet<T, U, V>::find(const ValueType& value) const -> iterator
196     {
197         return m_impl.find(value); 
198     }
199
200     template<typename T, typename U, typename V>
201     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
202     {
203         return m_impl.contains(value); 
204     }
205
206     template<typename Value, typename HashFunctions, typename Traits>
207     template<typename HashTranslator, typename T>
208     inline auto HashSet<Value, HashFunctions, Traits>::find(const T& value) const -> iterator
209     {
210         return m_impl.template find<HashSetTranslatorAdapter<HashTranslator>>(value);
211     }
212
213     template<typename Value, typename HashFunctions, typename Traits>
214     template<typename HashTranslator, typename T>
215     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
216     {
217         return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator>>(value);
218     }
219
220     template<typename T, typename U, typename V>
221     inline auto HashSet<T, U, V>::add(const ValueType& value) -> AddResult
222     {
223         return m_impl.add(value);
224     }
225
226     template<typename T, typename U, typename V>
227     inline auto HashSet<T, U, V>::add(ValueType&& value) -> AddResult
228     {
229         return m_impl.add(WTFMove(value));
230     }
231
232     template<typename T, typename U, typename V>
233     inline void HashSet<T, U, V>::addVoid(const ValueType& value)
234     {
235         m_impl.add(value);
236     }
237
238     template<typename T, typename U, typename V>
239     inline void HashSet<T, U, V>::addVoid(ValueType&& value)
240     {
241         m_impl.add(WTFMove(value));
242     }
243
244     template<typename Value, typename HashFunctions, typename Traits>
245     template<typename HashTranslator, typename T>
246     inline auto HashSet<Value, HashFunctions, Traits>::add(const T& value) -> AddResult
247     {
248         return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator>>(value, value);
249     }
250
251     template<typename T, typename U, typename V>
252     template<typename IteratorType>
253     inline bool HashSet<T, U, V>::add(IteratorType begin, IteratorType end)
254     {
255         bool changed = false;
256         for (IteratorType iter = begin; iter != end; ++iter)
257             changed |= add(*iter).isNewEntry;
258         return changed;
259     }
260
261     template<typename T, typename U, typename V>
262     inline bool HashSet<T, U, V>::remove(iterator it)
263     {
264         if (it.m_impl == m_impl.end())
265             return false;
266         m_impl.internalCheckTableConsistency();
267         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
268         return true;
269     }
270
271     template<typename T, typename U, typename V>
272     inline bool HashSet<T, U, V>::remove(const ValueType& value)
273     {
274         return remove(find(value));
275     }
276
277     template<typename T, typename U, typename V>
278     template<typename Functor>
279     inline void HashSet<T, U, V>::removeIf(const Functor& functor)
280     {
281         m_impl.removeIf(functor);
282     }
283
284     template<typename T, typename U, typename V>
285     inline void HashSet<T, U, V>::clear()
286     {
287         m_impl.clear(); 
288     }
289
290     template<typename T, typename U, typename V>
291     inline auto HashSet<T, U, V>::take(iterator it) -> TakeType
292     {
293         if (it == end())
294             return ValueTraits::take(ValueTraits::emptyValue());
295
296         auto result = ValueTraits::take(WTFMove(const_cast<ValueType&>(*it)));
297         remove(it);
298         return result;
299     }
300
301     template<typename T, typename U, typename V>
302     inline auto HashSet<T, U, V>::take(const ValueType& value) -> TakeType
303     {
304         return take(find(value));
305     }
306
307     template<typename T, typename U, typename V>
308     inline auto HashSet<T, U, V>::takeAny() -> TakeType
309     {
310         return take(begin());
311     }
312
313     template<typename Value, typename HashFunctions, typename Traits>
314     template<typename V>
315     inline auto HashSet<Value, HashFunctions, Traits>::find(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type
316     {
317         return m_impl.template find<HashSetTranslator<Traits, HashFunctions>>(value);
318     }
319
320     template<typename Value, typename HashFunctions, typename Traits>
321     template<typename V>
322     inline auto HashSet<Value, HashFunctions, Traits>::contains(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
323     {
324         return m_impl.template contains<HashSetTranslator<Traits, HashFunctions>>(value);
325     }
326
327     template<typename Value, typename HashFunctions, typename Traits>
328     template<typename V>
329     inline auto HashSet<Value, HashFunctions, Traits>::remove(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
330     {
331         return remove(find(value));
332     }
333
334     template<typename Value, typename HashFunctions, typename Traits>
335     template<typename V>
336     inline auto HashSet<Value, HashFunctions, Traits>::take(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, TakeType>::type
337     {
338         return take(find(value));
339     }
340
341     template<typename T, typename U, typename V>
342     inline bool HashSet<T, U, V>::isValidValue(const ValueType& value)
343     {
344         if (ValueTraits::isDeletedValue(value))
345             return false;
346
347         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
348             if (value == ValueTraits::emptyValue())
349                 return false;
350         } else {
351             if (isHashTraitsEmptyValue<ValueTraits>(value))
352                 return false;
353         }
354
355         return true;
356     }
357
358     template<typename C, typename W>
359     inline void copyToVector(const C& collection, W& vector)
360     {
361         typedef typename C::const_iterator iterator;
362         
363         vector.resize(collection.size());
364         
365         iterator it = collection.begin();
366         iterator end = collection.end();
367         for (unsigned i = 0; it != end; ++it, ++i)
368             vector[i] = *it;
369     }  
370
371     template<typename T, typename U, typename V>
372     template<typename OtherCollection>
373     inline bool HashSet<T, U, V>::operator==(const OtherCollection& otherCollection) const
374     {
375         if (size() != otherCollection.size())
376             return false;
377         for (const auto& other : otherCollection) {
378             if (!contains(other))
379                 return false;
380         }
381         return true;
382     }
383     
384     template<typename T, typename U, typename V>
385     template<typename OtherCollection>
386     inline bool HashSet<T, U, V>::operator!=(const OtherCollection& otherCollection) const
387     {
388         return !(*this == otherCollection);
389     }
390
391 } // namespace WTF
392
393 using WTF::HashSet;
394
395 #endif /* WTF_HashSet_h */