1/*
2 * Copyright (C) 2005, 2006, 2008, 2013, 2016 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_HashCountedSet_h
22#define WTF_HashCountedSet_h
23
24#include <initializer_list>
25#include <wtf/Assertions.h>
26#include <wtf/HashMap.h>
27#include <wtf/Vector.h>
28
29namespace WTF {
30
31 template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, typename Traits = HashTraits<Value>>
32 class HashCountedSet final {
33 WTF_MAKE_FAST_ALLOCATED;
34 private:
35 typedef HashMap<Value, unsigned, HashFunctions, Traits> ImplType;
36 public:
37 typedef Value ValueType;
38 typedef typename ImplType::iterator iterator;
39 typedef typename ImplType::const_iterator const_iterator;
40 typedef typename ImplType::AddResult AddResult;
41
42 HashCountedSet()
43 {
44 }
45
46 HashCountedSet(std::initializer_list<typename ImplType::KeyValuePairType> initializerList)
47 {
48 for (const auto& keyValuePair : initializerList)
49 add(keyValuePair.key, keyValuePair.value);
50 }
51
52 HashCountedSet(std::initializer_list<typename ImplType::KeyType> initializerList)
53 {
54 for (const auto& value : initializerList)
55 add(value);
56 }
57
58 void swap(HashCountedSet&);
59
60 unsigned size() const;
61 unsigned capacity() const;
62 bool isEmpty() const;
63
64 // Iterators iterate over pairs of values and counts.
65 iterator begin();
66 iterator end();
67 const_iterator begin() const;
68 const_iterator end() const;
69
70 iterator find(const ValueType&);
71 const_iterator find(const ValueType&) const;
72 bool contains(const ValueType&) const;
73 unsigned count(const ValueType&) const;
74
75 // Increments the count if an equal value is already present.
76 // The return value includes both an iterator to the value's location,
77 // and an isNewEntry bool that indicates whether it is a new or existing entry.
78 AddResult add(const ValueType&);
79 AddResult add(ValueType&&);
80
81 // Increments the count of a value by the passed amount.
82 AddResult add(const ValueType&, unsigned);
83 AddResult add(ValueType&&, unsigned);
84
85 // Decrements the count of the value, and removes it if count goes down to zero.
86 // Returns true if the value is removed.
87 bool remove(const ValueType&);
88 bool remove(iterator);
89
90 // Removes the value, regardless of its count.
91 // Returns true if a value was removed.
92 bool removeAll(iterator);
93 bool removeAll(const ValueType&);
94
95 // Clears the whole set.
96 void clear();
97
98 // Overloads for smart pointer keys that take the raw pointer type as the parameter.
99 template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type find(typename GetPtrHelper<V>::PtrType);
100 template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, const_iterator>::type find(typename GetPtrHelper<V>::PtrType) const;
101 template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, bool>::type contains(typename GetPtrHelper<V>::PtrType) const;
102 template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, unsigned>::type count(typename GetPtrHelper<V>::PtrType) const;
103 template<typename V = ValueType> typename std::enable_if<IsSmartPtr<V>::value, bool>::type remove(typename GetPtrHelper<V>::PtrType);
104
105 private:
106 ImplType m_impl;
107 };
108
109
110 template<typename Value, typename HashFunctions, typename Traits>
111 inline void HashCountedSet<Value, HashFunctions, Traits>::swap(HashCountedSet& other)
112 {
113 m_impl.swap(other.m_impl);
114 }
115
116 template<typename Value, typename HashFunctions, typename Traits>
117 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::size() const
118 {
119 return m_impl.size();
120 }
121
122 template<typename Value, typename HashFunctions, typename Traits>
123 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::capacity() const
124 {
125 return m_impl.capacity();
126 }
127
128 template<typename Value, typename HashFunctions, typename Traits>
129 inline bool HashCountedSet<Value, HashFunctions, Traits>::isEmpty() const
130 {
131 return size() == 0;
132 }
133
134 template<typename Value, typename HashFunctions, typename Traits>
135 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::begin()
136 {
137 return m_impl.begin();
138 }
139
140 template<typename Value, typename HashFunctions, typename Traits>
141 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::end()
142 {
143 return m_impl.end();
144 }
145
146 template<typename Value, typename HashFunctions, typename Traits>
147 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::begin() const
148 {
149 return m_impl.begin();
150 }
151
152 template<typename Value, typename HashFunctions, typename Traits>
153 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::end() const
154 {
155 return m_impl.end();
156 }
157
158 template<typename Value, typename HashFunctions, typename Traits>
159 inline typename HashCountedSet<Value, HashFunctions, Traits>::iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value)
160 {
161 return m_impl.find(value);
162 }
163
164 template<typename Value, typename HashFunctions, typename Traits>
165 inline typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator HashCountedSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
166 {
167 return m_impl.find(value);
168 }
169
170 template<typename Value, typename HashFunctions, typename Traits>
171 inline bool HashCountedSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
172 {
173 return m_impl.contains(value);
174 }
175
176 template<typename Value, typename HashFunctions, typename Traits>
177 inline unsigned HashCountedSet<Value, HashFunctions, Traits>::count(const ValueType& value) const
178 {
179 return m_impl.get(value);
180 }
181
182 template<typename Value, typename HashFunctions, typename Traits>
183 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType &value)
184 {
185 AddResult result = m_impl.add(value, 0);
186 ++result.iterator->value;
187 return result;
188 }
189
190 template<typename Value, typename HashFunctions, typename Traits>
191 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(ValueType&& value)
192 {
193 AddResult result = m_impl.add(std::forward<Value>(value), 0);
194 ++result.iterator->value;
195 return result;
196 }
197
198 template<typename Value, typename HashFunctions, typename Traits>
199 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(const ValueType& value, unsigned count)
200 {
201 AddResult result = m_impl.add(value, 0);
202 result.iterator->value += count;
203 return result;
204 }
205
206 template<typename Value, typename HashFunctions, typename Traits>
207 inline typename HashCountedSet<Value, HashFunctions, Traits>::AddResult HashCountedSet<Value, HashFunctions, Traits>::add(ValueType&& value, unsigned count)
208 {
209 AddResult result = m_impl.add(std::forward<Value>(value), 0);
210 result.iterator->value += count;
211 return result;
212 }
213
214 template<typename Value, typename HashFunctions, typename Traits>
215 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
216 {
217 return remove(find(value));
218 }
219
220 template<typename Value, typename HashFunctions, typename Traits>
221 inline bool HashCountedSet<Value, HashFunctions, Traits>::remove(iterator it)
222 {
223 if (it == end())
224 return false;
225
226 unsigned oldVal = it->value;
227 ASSERT(oldVal);
228 unsigned newVal = oldVal - 1;
229 if (newVal) {
230 it->value = newVal;
231 return false;
232 }
233
234 m_impl.remove(it);
235 return true;
236 }
237
238 template<typename Value, typename HashFunctions, typename Traits>
239 inline bool HashCountedSet<Value, HashFunctions, Traits>::removeAll(const ValueType& value)
240 {
241 return removeAll(find(value));
242 }
243
244 template<typename Value, typename HashFunctions, typename Traits>
245 inline bool HashCountedSet<Value, HashFunctions, Traits>::removeAll(iterator it)
246 {
247 if (it == end())
248 return false;
249
250 m_impl.remove(it);
251 return true;
252 }
253
254 template<typename Value, typename HashFunctions, typename Traits>
255 inline void HashCountedSet<Value, HashFunctions, Traits>::clear()
256 {
257 m_impl.clear();
258 }
259
260 template<typename Value, typename HashFunctions, typename Traits, typename VectorType>
261 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, VectorType& vector)
262 {
263 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
264
265 vector.resize(collection.size());
266
267 iterator it = collection.begin();
268 iterator end = collection.end();
269 for (unsigned i = 0; it != end; ++it, ++i)
270 vector[i] = *it;
271 }
272
273 template<typename Value, typename HashFunctions, typename Traits>
274 inline void copyToVector(const HashCountedSet<Value, HashFunctions, Traits>& collection, Vector<Value>& vector)
275 {
276 typedef typename HashCountedSet<Value, HashFunctions, Traits>::const_iterator iterator;
277
278 vector.resize(collection.size());
279
280 iterator it = collection.begin();
281 iterator end = collection.end();
282 for (unsigned i = 0; it != end; ++it, ++i)
283 vector[i] = (*it).key;
284 }
285
286 template<typename Value, typename HashFunctions, typename Traits>
287 template<typename V>
288 inline auto HashCountedSet<Value, HashFunctions, Traits>::find(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, iterator>::type
289 {
290 return m_impl.find(value);
291 }
292
293 template<typename Value, typename HashFunctions, typename Traits>
294 template<typename V>
295 inline auto HashCountedSet<Value, HashFunctions, Traits>::find(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, const_iterator>::type
296 {
297 return m_impl.find(value);
298 }
299
300 template<typename Value, typename HashFunctions, typename Traits>
301 template<typename V>
302 inline auto HashCountedSet<Value, HashFunctions, Traits>::contains(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
303 {
304 return m_impl.contains(value);
305 }
306
307 template<typename Value, typename HashFunctions, typename Traits>
308 template<typename V>
309 inline auto HashCountedSet<Value, HashFunctions, Traits>::count(typename GetPtrHelper<V>::PtrType value) const -> typename std::enable_if<IsSmartPtr<V>::value, unsigned>::type
310 {
311 return m_impl.get(value);
312 }
313
314 template<typename Value, typename HashFunctions, typename Traits>
315 template<typename V>
316 inline auto HashCountedSet<Value, HashFunctions, Traits>::remove(typename GetPtrHelper<V>::PtrType value) -> typename std::enable_if<IsSmartPtr<V>::value, bool>::type
317 {
318 return remove(find(value));
319 }
320
321} // namespace WTF
322
323using WTF::HashCountedSet;
324
325#endif /* WTF_HashCountedSet_h */
326