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