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
27namespace 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 IdentityExtractor {
102 static const T& extract(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>::remove(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
294using WTF::HashSet;
295
296#endif /* WTF_HashSet_h */
297

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/HashSet.h