source: webkit/trunk/JavaScriptCore/wtf/HashSet.h@ 38514

Last change on this file since 38514 was 37062, checked in by Simon Hausmann, 17 years ago

2008-09-29 Bradley T. Hughes <​[email protected]>

Reviewed by Simon.

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