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