1 | /* |
2 | * Copyright (C) 2005, 2006, 2007, 2008 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 "FastAllocBase.h" |
25 | #include "HashTable.h" |
26 | |
27 | namespace WTF { |
28 | |
29 | template<typename Value, typename HashFunctions, typename Traits> class HashSet; |
30 | template<typename Value, typename HashFunctions, typename Traits> |
31 | void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&); |
32 | template<typename Value, typename HashFunctions, typename Traits> |
33 | void fastDeleteAllValues(const HashSet<Value, HashFunctions, Traits>&); |
34 | |
35 | template<typename T> struct IdentityExtractor; |
36 | |
37 | template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash, |
38 | typename TraitsArg = HashTraits<ValueArg> > class HashSet : public FastAllocBase { |
39 | private: |
40 | typedef HashArg HashFunctions; |
41 | typedef TraitsArg ValueTraits; |
42 | |
43 | public: |
44 | typedef typename ValueTraits::TraitType ValueType; |
45 | |
46 | private: |
47 | typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>, |
48 | HashFunctions, ValueTraits, ValueTraits> HashTableType; |
49 | |
50 | public: |
51 | typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; |
52 | typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; |
53 | |
54 | void swap(HashSet&); |
55 | |
56 | int size() const; |
57 | int capacity() const; |
58 | bool isEmpty() const; |
59 | |
60 | iterator begin(); |
61 | iterator end(); |
62 | const_iterator begin() const; |
63 | const_iterator end() const; |
64 | |
65 | iterator find(const ValueType&); |
66 | const_iterator find(const ValueType&) const; |
67 | bool contains(const ValueType&) const; |
68 | |
69 | // An alternate version of find() that finds the object by hashing and comparing |
70 | // with some other type, to avoid the cost of type conversion. HashTranslator |
71 | // must have the following function members: |
72 | // static unsigned hash(const T&); |
73 | // static bool equal(const ValueType&, const T&); |
74 | template<typename T, typename HashTranslator> iterator find(const T&); |
75 | template<typename T, typename HashTranslator> const_iterator find(const T&) const; |
76 | template<typename T, typename HashTranslator> bool contains(const T&) const; |
77 | |
78 | // The return value is a pair of an interator to the new value's location, |
79 | // and a bool that is true if an new entry was added. |
80 | pair<iterator, bool> add(const ValueType&); |
81 | |
82 | // An alternate version of add() that finds the object by hashing and comparing |
83 | // with some other type, to avoid the cost of type conversion if the object is already |
84 | // in the table. HashTranslator must have the following function members: |
85 | // static unsigned hash(const T&); |
86 | // static bool equal(const ValueType&, const T&); |
87 | // static translate(ValueType&, const T&, unsigned hashCode); |
88 | template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&); |
89 | |
90 | void remove(const ValueType&); |
91 | void remove(iterator); |
92 | void clear(); |
93 | |
94 | private: |
95 | friend void deleteAllValues<>(const HashSet&); |
96 | friend void fastDeleteAllValues<>(const HashSet&); |
97 | |
98 | HashTableType m_impl; |
99 | }; |
100 | |
101 | template<typename T> struct { |
102 | static const T& (const T& t) { return t; } |
103 | }; |
104 | |
105 | template<typename ValueType, typename ValueTraits, typename T, typename Translator> |
106 | struct HashSetTranslatorAdapter { |
107 | static unsigned hash(const T& key) { return Translator::hash(key); } |
108 | static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); } |
109 | static void translate(ValueType& location, const T& key, const T&, unsigned hashCode) |
110 | { |
111 | Translator::translate(location, key, hashCode); |
112 | } |
113 | }; |
114 | |
115 | template<typename T, typename U, typename V> |
116 | inline void HashSet<T, U, V>::swap(HashSet& other) |
117 | { |
118 | m_impl.swap(other.m_impl); |
119 | } |
120 | |
121 | template<typename T, typename U, typename V> |
122 | inline int HashSet<T, U, V>::size() const |
123 | { |
124 | return m_impl.size(); |
125 | } |
126 | |
127 | template<typename T, typename U, typename V> |
128 | inline int HashSet<T, U, V>::capacity() const |
129 | { |
130 | return m_impl.capacity(); |
131 | } |
132 | |
133 | template<typename T, typename U, typename V> |
134 | inline bool HashSet<T, U, V>::isEmpty() const |
135 | { |
136 | return m_impl.isEmpty(); |
137 | } |
138 | |
139 | template<typename T, typename U, typename V> |
140 | inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() |
141 | { |
142 | return m_impl.begin(); |
143 | } |
144 | |
145 | template<typename T, typename U, typename V> |
146 | inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() |
147 | { |
148 | return m_impl.end(); |
149 | } |
150 | |
151 | template<typename T, typename U, typename V> |
152 | inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const |
153 | { |
154 | return m_impl.begin(); |
155 | } |
156 | |
157 | template<typename T, typename U, typename V> |
158 | inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const |
159 | { |
160 | return m_impl.end(); |
161 | } |
162 | |
163 | template<typename T, typename U, typename V> |
164 | inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value) |
165 | { |
166 | return m_impl.find(value); |
167 | } |
168 | |
169 | template<typename T, typename U, typename V> |
170 | inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const |
171 | { |
172 | return m_impl.find(value); |
173 | } |
174 | |
175 | template<typename T, typename U, typename V> |
176 | inline bool HashSet<T, U, V>::contains(const ValueType& value) const |
177 | { |
178 | return m_impl.contains(value); |
179 | } |
180 | |
181 | template<typename Value, typename HashFunctions, typename Traits> |
182 | template<typename T, typename HashTranslator> |
183 | typename HashSet<Value, HashFunctions, Traits>::iterator |
184 | inline HashSet<Value, HashFunctions, Traits>::find(const T& value) |
185 | { |
186 | typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; |
187 | return m_impl.template find<T, Adapter>(value); |
188 | } |
189 | |
190 | template<typename Value, typename HashFunctions, typename Traits> |
191 | template<typename T, typename HashTranslator> |
192 | typename HashSet<Value, HashFunctions, Traits>::const_iterator |
193 | inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const |
194 | { |
195 | typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; |
196 | return m_impl.template find<T, Adapter>(value); |
197 | } |
198 | |
199 | template<typename Value, typename HashFunctions, typename Traits> |
200 | template<typename T, typename HashTranslator> |
201 | inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const |
202 | { |
203 | typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; |
204 | return m_impl.template contains<T, Adapter>(value); |
205 | } |
206 | |
207 | template<typename T, typename U, typename V> |
208 | pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value) |
209 | { |
210 | pair<typename HashTable<T, T, IdentityExtractor<T>, U, V, V>::iterator, bool> p = m_impl.add(value); |
211 | typename HashSet<T, U, V>::iterator temp = p.first; |
212 | pair<typename HashSet<T, U, V>::iterator, bool> p2 = pair<typename HashSet<T, U, V>::iterator, bool>(temp, p.second); |
213 | // p2.first = p.first; |
214 | // p2.second = p.second; |
215 | return p2; |
216 | } |
217 | |
218 | template<typename Value, typename HashFunctions, typename Traits> |
219 | template<typename T, typename HashTranslator> |
220 | pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> |
221 | HashSet<Value, HashFunctions, Traits>::add(const T& value) |
222 | { |
223 | typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter; |
224 | pair<typename HashTableType::iterator, bool> p = m_impl.template addPassingHashCode<T, T, Adapter>(value, value); |
225 | return pair<iterator, bool>(p.first, p.second); |
226 | } |
227 | |
228 | template<typename T, typename U, typename V> |
229 | inline void HashSet<T, U, V>::(iterator it) |
230 | { |
231 | if (it.m_impl == m_impl.end()) |
232 | return; |
233 | m_impl.checkTableConsistency(); |
234 | m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); |
235 | } |
236 | |
237 | template<typename T, typename U, typename V> |
238 | inline void HashSet<T, U, V>::remove(const ValueType& value) |
239 | { |
240 | remove(find(value)); |
241 | } |
242 | |
243 | template<typename T, typename U, typename V> |
244 | inline void HashSet<T, U, V>::clear() |
245 | { |
246 | m_impl.clear(); |
247 | } |
248 | |
249 | template<typename ValueType, typename HashTableType> |
250 | void deleteAllValues(HashTableType& collection) |
251 | { |
252 | typedef typename HashTableType::const_iterator iterator; |
253 | iterator end = collection.end(); |
254 | for (iterator it = collection.begin(); it != end; ++it) |
255 | delete *it; |
256 | } |
257 | |
258 | template<typename T, typename U, typename V> |
259 | inline void deleteAllValues(const HashSet<T, U, V>& collection) |
260 | { |
261 | deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl); |
262 | } |
263 | |
264 | template<typename ValueType, typename HashTableType> |
265 | void fastDeleteAllValues(HashTableType& collection) |
266 | { |
267 | typedef typename HashTableType::const_iterator iterator; |
268 | iterator end = collection.end(); |
269 | for (iterator it = collection.begin(); it != end; ++it) |
270 | fastDelete(*it); |
271 | } |
272 | |
273 | template<typename T, typename U, typename V> |
274 | inline void fastDeleteAllValues(const HashSet<T, U, V>& collection) |
275 | { |
276 | fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl); |
277 | } |
278 | |
279 | template<typename T, typename U, typename V, typename W> |
280 | inline void copyToVector(const HashSet<T, U, V>& collection, W& vector) |
281 | { |
282 | typedef typename HashSet<T, U, V>::const_iterator iterator; |
283 | |
284 | vector.resize(collection.size()); |
285 | |
286 | iterator it = collection.begin(); |
287 | iterator end = collection.end(); |
288 | for (unsigned i = 0; it != end; ++it, ++i) |
289 | vector[i] = *it; |
290 | } |
291 | |
292 | } // namespace WTF |
293 | |
294 | using WTF::HashSet; |
295 | |
296 | #endif /* WTF_HashSet_h */ |
297 | |