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