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