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 { |
126 | template<typename T> static const T& (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>::(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>::(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 */ |
358 | |