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_HashMap_h |
22 | #define WTF_HashMap_h |
23 | |
24 | #include "HashTable.h" |
25 | |
26 | namespace WTF { |
27 | |
28 | template<typename PairType> struct PairFirstExtractor; |
29 | |
30 | template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash, |
31 | typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > |
32 | class HashMap : public FastAllocBase { |
33 | private: |
34 | typedef KeyTraitsArg KeyTraits; |
35 | typedef MappedTraitsArg MappedTraits; |
36 | typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; |
37 | |
38 | public: |
39 | typedef typename KeyTraits::TraitType KeyType; |
40 | typedef typename MappedTraits::TraitType MappedType; |
41 | typedef typename ValueTraits::TraitType ValueType; |
42 | |
43 | private: |
44 | typedef HashArg HashFunctions; |
45 | |
46 | typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, |
47 | HashFunctions, ValueTraits, KeyTraits> HashTableType; |
48 | |
49 | public: |
50 | typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; |
51 | typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; |
52 | |
53 | void swap(HashMap&); |
54 | |
55 | int size() const; |
56 | int capacity() const; |
57 | bool isEmpty() const; |
58 | |
59 | // iterators iterate over pairs of keys and values |
60 | iterator begin(); |
61 | iterator end(); |
62 | const_iterator begin() const; |
63 | const_iterator end() const; |
64 | |
65 | iterator find(const KeyType&); |
66 | const_iterator find(const KeyType&) const; |
67 | bool contains(const KeyType&) const; |
68 | MappedType get(const KeyType&) const; |
69 | |
70 | // replaces value but not key if key is already present |
71 | // return value is a pair of the iterator to the key location, |
72 | // and a boolean that's true if a new value was actually added |
73 | pair<iterator, bool> set(const KeyType&, const MappedType&); |
74 | |
75 | // does nothing if key is already present |
76 | // return value is a pair of the iterator to the key location, |
77 | // and a boolean that's true if a new value was actually added |
78 | pair<iterator, bool> add(const KeyType&, const MappedType&); |
79 | |
80 | void remove(const KeyType&); |
81 | void remove(iterator); |
82 | void clear(); |
83 | |
84 | MappedType take(const KeyType&); // efficient combination of get with remove |
85 | |
86 | // An alternate version of find() that finds the object by hashing and comparing |
87 | // with some other type, to avoid the cost of type conversion. HashTranslator |
88 | // must have the following function members: |
89 | // static unsigned hash(const T&); |
90 | // static bool equal(const ValueType&, const T&); |
91 | template<typename T, typename HashTranslator> iterator find(const T&); |
92 | template<typename T, typename HashTranslator> const_iterator find(const T&) const; |
93 | template<typename T, typename HashTranslator> bool contains(const T&) const; |
94 | |
95 | // An alternate version of add() that finds the object by hashing and comparing |
96 | // with some other type, to avoid the cost of type conversion if the object is already |
97 | // in the table. HashTranslator must have the following function members: |
98 | // static unsigned hash(const T&); |
99 | // static bool equal(const ValueType&, const T&); |
100 | // static translate(ValueType&, const T&, unsigned hashCode); |
101 | template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&, const MappedType&); |
102 | |
103 | private: |
104 | pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&); |
105 | |
106 | HashTableType m_impl; |
107 | }; |
108 | |
109 | template<typename PairType> struct { |
110 | static const typename PairType::first_type& (const PairType& p) { return p.first; } |
111 | }; |
112 | |
113 | template<typename ValueType, typename ValueTraits, typename HashFunctions> |
114 | struct HashMapTranslator { |
115 | typedef typename ValueType::first_type KeyType; |
116 | typedef typename ValueType::second_type MappedType; |
117 | |
118 | static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); } |
119 | static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); } |
120 | static void translate(ValueType& location, const KeyType& key, const MappedType& mapped) |
121 | { |
122 | location.first = key; |
123 | location.second = mapped; |
124 | } |
125 | }; |
126 | |
127 | template<typename ValueType, typename ValueTraits, typename T, typename Translator> |
128 | struct HashMapTranslatorAdapter { |
129 | typedef typename ValueType::first_type KeyType; |
130 | typedef typename ValueType::second_type MappedType; |
131 | |
132 | static unsigned hash(const T& key) { return Translator::hash(key); } |
133 | static bool equal(const KeyType& a, const T& b) { return Translator::equal(a, b); } |
134 | static void translate(ValueType& location, const T& key, const MappedType&, unsigned hashCode) |
135 | { |
136 | Translator::translate(location.first, key, hashCode); |
137 | } |
138 | }; |
139 | |
140 | template<typename T, typename U, typename V, typename W, typename X> |
141 | inline void HashMap<T, U, V, W, X>::swap(HashMap& other) |
142 | { |
143 | m_impl.swap(other.m_impl); |
144 | } |
145 | |
146 | template<typename T, typename U, typename V, typename W, typename X> |
147 | inline int HashMap<T, U, V, W, X>::size() const |
148 | { |
149 | return m_impl.size(); |
150 | } |
151 | |
152 | template<typename T, typename U, typename V, typename W, typename X> |
153 | inline int HashMap<T, U, V, W, X>::capacity() const |
154 | { |
155 | return m_impl.capacity(); |
156 | } |
157 | |
158 | template<typename T, typename U, typename V, typename W, typename X> |
159 | inline bool HashMap<T, U, V, W, X>::isEmpty() const |
160 | { |
161 | return m_impl.isEmpty(); |
162 | } |
163 | |
164 | template<typename T, typename U, typename V, typename W, typename X> |
165 | inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin() |
166 | { |
167 | return m_impl.begin(); |
168 | } |
169 | |
170 | template<typename T, typename U, typename V, typename W, typename X> |
171 | inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end() |
172 | { |
173 | return m_impl.end(); |
174 | } |
175 | |
176 | template<typename T, typename U, typename V, typename W, typename X> |
177 | inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const |
178 | { |
179 | return m_impl.begin(); |
180 | } |
181 | |
182 | template<typename T, typename U, typename V, typename W, typename X> |
183 | inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const |
184 | { |
185 | return m_impl.end(); |
186 | } |
187 | |
188 | template<typename T, typename U, typename V, typename W, typename X> |
189 | inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key) |
190 | { |
191 | return m_impl.find(key); |
192 | } |
193 | |
194 | template<typename T, typename U, typename V, typename W, typename X> |
195 | inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const |
196 | { |
197 | return m_impl.find(key); |
198 | } |
199 | |
200 | template<typename T, typename U, typename V, typename W, typename X> |
201 | inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const |
202 | { |
203 | return m_impl.contains(key); |
204 | } |
205 | |
206 | template<typename T, typename U, typename V, typename W, typename X> |
207 | template<typename TYPE, typename HashTranslator> |
208 | inline typename HashMap<T, U, V, W, X>::iterator |
209 | HashMap<T, U, V, W, X>::find(const TYPE& value) |
210 | { |
211 | typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; |
212 | return m_impl.template find<TYPE, Adapter>(value); |
213 | } |
214 | |
215 | template<typename T, typename U, typename V, typename W, typename X> |
216 | template<typename TYPE, typename HashTranslator> |
217 | inline typename HashMap<T, U, V, W, X>::const_iterator |
218 | HashMap<T, U, V, W, X>::find(const TYPE& value) const |
219 | { |
220 | typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; |
221 | return m_impl.template find<TYPE, Adapter>(value); |
222 | } |
223 | |
224 | template<typename T, typename U, typename V, typename W, typename X> |
225 | template<typename TYPE, typename HashTranslator> |
226 | inline bool |
227 | HashMap<T, U, V, W, X>::contains(const TYPE& value) const |
228 | { |
229 | typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; |
230 | return m_impl.template contains<TYPE, Adapter>(value); |
231 | } |
232 | |
233 | template<typename T, typename U, typename V, typename W, typename X> |
234 | inline pair<typename HashMap<T, U, V, W, X>::iterator, bool> |
235 | HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) |
236 | { |
237 | typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; |
238 | pair<typename HashTableType::iterator, bool> p = m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); |
239 | typename HashMap<T, U, V, W, X>::iterator temp = p.first; |
240 | return std::pair<typename HashMap<T, U, V, W, X>::iterator, bool>(temp, p.second); |
241 | // return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); |
242 | } |
243 | |
244 | template<typename T, typename U, typename V, typename W, typename X> |
245 | pair<typename HashMap<T, U, V, W, X>::iterator, bool> |
246 | HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) |
247 | { |
248 | pair<iterator, bool> result = inlineAdd(key, mapped); |
249 | if (!result.second) { |
250 | // add call above didn't change anything, so set the mapped value |
251 | result.first->second = mapped; |
252 | } |
253 | return result; |
254 | } |
255 | |
256 | template<typename T, typename U, typename V, typename W, typename X> |
257 | template<typename TYPE, typename HashTranslator> |
258 | pair<typename HashMap<T, U, V, W, X>::iterator, bool> |
259 | HashMap<T, U, V, W, X>::add(const TYPE& key, const MappedType& value) |
260 | { |
261 | typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter; |
262 | return m_impl.template addPassingHashCode<TYPE, MappedType, Adapter>(key, value); |
263 | } |
264 | |
265 | template<typename T, typename U, typename V, typename W, typename X> |
266 | pair<typename HashMap<T, U, V, W, X>::iterator, bool> |
267 | HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) |
268 | { |
269 | return inlineAdd(key, mapped); |
270 | } |
271 | |
272 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
273 | typename HashMap<T, U, V, W, MappedTraits>::MappedType |
274 | HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const |
275 | { |
276 | ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); |
277 | if (!entry) |
278 | return MappedTraits::emptyValue(); |
279 | return entry->second; |
280 | } |
281 | |
282 | template<typename T, typename U, typename V, typename W, typename X> |
283 | inline void HashMap<T, U, V, W, X>::(iterator it) |
284 | { |
285 | if (it.m_impl == m_impl.end()) |
286 | return; |
287 | m_impl.checkTableConsistency(); |
288 | m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); |
289 | } |
290 | |
291 | template<typename T, typename U, typename V, typename W, typename X> |
292 | inline void HashMap<T, U, V, W, X>::remove(const KeyType& key) |
293 | { |
294 | remove(find(key)); |
295 | } |
296 | |
297 | template<typename T, typename U, typename V, typename W, typename X> |
298 | inline void HashMap<T, U, V, W, X>::clear() |
299 | { |
300 | m_impl.clear(); |
301 | } |
302 | |
303 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
304 | typename HashMap<T, U, V, W, MappedTraits>::MappedType |
305 | HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) |
306 | { |
307 | // This can probably be made more efficient to avoid ref/deref churn. |
308 | iterator it = find(key); |
309 | if (it == end()) |
310 | return MappedTraits::emptyValue(); |
311 | typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second; |
312 | remove(it); |
313 | return result; |
314 | } |
315 | |
316 | template<typename T, typename U, typename V, typename W, typename X> |
317 | bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) |
318 | { |
319 | if (a.size() != b.size()) |
320 | return false; |
321 | |
322 | typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator; |
323 | |
324 | const_iterator end = a.end(); |
325 | const_iterator notFound = b.end(); |
326 | for (const_iterator it = a.begin(); it != end; ++it) { |
327 | const_iterator bPos = b.find(it->first); |
328 | if (bPos == notFound || it->second != bPos->second) |
329 | return false; |
330 | } |
331 | |
332 | return true; |
333 | } |
334 | |
335 | template<typename T, typename U, typename V, typename W, typename X> |
336 | inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b) |
337 | { |
338 | return !(a == b); |
339 | } |
340 | |
341 | template<typename MappedType, typename HashTableType> |
342 | void deleteAllPairSeconds(HashTableType& collection) |
343 | { |
344 | typedef typename HashTableType::const_iterator iterator; |
345 | iterator end = collection.end(); |
346 | for (iterator it = collection.begin(); it != end; ++it) |
347 | delete it->second; |
348 | } |
349 | |
350 | template<typename T, typename U, typename V, typename W, typename X> |
351 | inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection) |
352 | { |
353 | deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection); |
354 | } |
355 | |
356 | template<typename KeyType, typename HashTableType> |
357 | void deleteAllPairFirsts(HashTableType& collection) |
358 | { |
359 | typedef typename HashTableType::const_iterator iterator; |
360 | iterator end = collection.end(); |
361 | for (iterator it = collection.begin(); it != end; ++it) |
362 | delete it->first; |
363 | } |
364 | |
365 | template<typename T, typename U, typename V, typename W, typename X> |
366 | inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) |
367 | { |
368 | deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection); |
369 | } |
370 | |
371 | template<typename T, typename U, typename V, typename W, typename X, typename Y> |
372 | inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) |
373 | { |
374 | typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; |
375 | |
376 | vector.resize(collection.size()); |
377 | |
378 | iterator it = collection.begin().keys(); |
379 | iterator end = collection.end().keys(); |
380 | for (unsigned i = 0; it != end; ++it, ++i) |
381 | vector[i] = *it; |
382 | } |
383 | |
384 | template<typename T, typename U, typename V, typename W, typename X, typename Y> |
385 | inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) |
386 | { |
387 | typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator; |
388 | |
389 | vector.resize(collection.size()); |
390 | |
391 | iterator it = collection.begin().values(); |
392 | iterator end = collection.end().values(); |
393 | for (unsigned i = 0; it != end; ++it, ++i) |
394 | vector[i] = *it; |
395 | } |
396 | |
397 | } // namespace WTF |
398 | |
399 | using WTF::HashMap; |
400 | |
401 | #include "RefPtrHashMap.h" |
402 | |
403 | #endif /* WTF_HashMap_h */ |
404 | |