OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 <wtf/HashTable.h> | |
25 | |
26 namespace WTF { | |
27 | |
28 template<typename KeyTraits, typename MappedTraits> struct HashMapValueTrait
s; | |
29 | |
30 template<typename T> struct ReferenceTypeMaker { | |
31 typedef T& ReferenceType; | |
32 }; | |
33 template<typename T> struct ReferenceTypeMaker<T&> { | |
34 typedef T& ReferenceType; | |
35 }; | |
36 | |
37 template<typename T> struct KeyValuePairKeyExtractor { | |
38 static const typename T::KeyType& extract(const T& p) { return p.key; } | |
39 }; | |
40 | |
41 template<typename KeyArg, typename MappedArg, typename HashArg = typename De
faultHash<KeyArg>::Hash, | |
42 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = H
ashTraits<MappedArg> > | |
43 class HashMap { | |
44 WTF_MAKE_FAST_ALLOCATED; | |
45 private: | |
46 typedef KeyTraitsArg KeyTraits; | |
47 typedef MappedTraitsArg MappedTraits; | |
48 typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits; | |
49 | |
50 public: | |
51 typedef typename KeyTraits::TraitType KeyType; | |
52 typedef typename MappedTraits::TraitType MappedType; | |
53 typedef typename ValueTraits::TraitType ValueType; | |
54 | |
55 private: | |
56 typedef typename MappedTraits::PassInType MappedPassInType; | |
57 typedef typename MappedTraits::PassOutType MappedPassOutType; | |
58 typedef typename MappedTraits::PeekType MappedPeekType; | |
59 | |
60 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType Map
pedPassInReferenceType; | |
61 | |
62 typedef HashArg HashFunctions; | |
63 | |
64 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType
>, | |
65 HashFunctions, ValueTraits, KeyTraits> HashTableType; | |
66 | |
67 class HashMapKeysProxy; | |
68 class HashMapValuesProxy; | |
69 | |
70 public: | |
71 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; | |
72 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_it
erator; | |
73 typedef typename HashTableType::AddResult AddResult; | |
74 | |
75 public: | |
76 void swap(HashMap&); | |
77 | |
78 int size() const; | |
79 int capacity() const; | |
80 bool isEmpty() const; | |
81 | |
82 // iterators iterate over pairs of keys and values | |
83 iterator begin(); | |
84 iterator end(); | |
85 const_iterator begin() const; | |
86 const_iterator end() const; | |
87 | |
88 HashMapKeysProxy& keys() { return static_cast<HashMapKeysProxy&>(*this);
} | |
89 const HashMapKeysProxy& keys() const { return static_cast<const HashMapK
eysProxy&>(*this); } | |
90 | |
91 HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*
this); } | |
92 const HashMapValuesProxy& values() const { return static_cast<const Hash
MapValuesProxy&>(*this); } | |
93 | |
94 iterator find(const KeyType&); | |
95 const_iterator find(const KeyType&) const; | |
96 bool contains(const KeyType&) const; | |
97 MappedPeekType get(const KeyType&) const; | |
98 | |
99 // replaces value but not key if key is already present | |
100 // return value is a pair of the iterator to the key location, | |
101 // and a boolean that's true if a new value was actually added | |
102 AddResult set(const KeyType&, MappedPassInType); | |
103 | |
104 // does nothing if key is already present | |
105 // return value is a pair of the iterator to the key location, | |
106 // and a boolean that's true if a new value was actually added | |
107 AddResult add(const KeyType&, MappedPassInType); | |
108 | |
109 void remove(const KeyType&); | |
110 void remove(iterator); | |
111 void clear(); | |
112 | |
113 MappedPassOutType take(const KeyType&); // efficient combination of get
with remove | |
114 | |
115 // An alternate version of find() that finds the object by hashing and c
omparing | |
116 // with some other type, to avoid the cost of type conversion. HashTrans
lator | |
117 // must have the following function members: | |
118 // static unsigned hash(const T&); | |
119 // static bool equal(const ValueType&, const T&); | |
120 template<typename T, typename HashTranslator> iterator find(const T&); | |
121 template<typename T, typename HashTranslator> const_iterator find(const
T&) const; | |
122 template<typename T, typename HashTranslator> bool contains(const T&) co
nst; | |
123 | |
124 // An alternate version of add() that finds the object by hashing and co
mparing | |
125 // with some other type, to avoid the cost of type conversion if the obj
ect is already | |
126 // in the table. HashTranslator must have the following function members
: | |
127 // static unsigned hash(const T&); | |
128 // static bool equal(const ValueType&, const T&); | |
129 // static translate(ValueType&, const T&, unsigned hashCode); | |
130 template<typename T, typename HashTranslator> AddResult add(const T&, Ma
ppedPassInType); | |
131 | |
132 void checkConsistency() const; | |
133 | |
134 static bool isValidKey(const KeyType&); | |
135 | |
136 private: | |
137 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); | |
138 | |
139 HashTableType m_impl; | |
140 }; | |
141 | |
142 template<typename KeyArg, typename MappedArg, typename HashArg, typename Key
TraitsArg, typename MappedTraitsArg> | |
143 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::Ha
shMapKeysProxy : | |
144 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g> { | |
145 public: | |
146 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg> HashMapType; | |
147 typedef typename HashMapType::iterator::Keys iterator; | |
148 typedef typename HashMapType::const_iterator::Keys const_iterator; | |
149 | |
150 iterator begin() | |
151 { | |
152 return HashMapType::begin().keys(); | |
153 } | |
154 | |
155 iterator end() | |
156 { | |
157 return HashMapType::end().keys(); | |
158 } | |
159 | |
160 const_iterator begin() const | |
161 { | |
162 return HashMapType::begin().keys(); | |
163 } | |
164 | |
165 const_iterator end() const | |
166 { | |
167 return HashMapType::end().keys(); | |
168 } | |
169 | |
170 private: | |
171 friend class HashMap; | |
172 | |
173 // These are intentionally not implemented. | |
174 HashMapKeysProxy(); | |
175 HashMapKeysProxy(const HashMapKeysProxy&); | |
176 HashMapKeysProxy& operator=(const HashMapKeysProxy&); | |
177 ~HashMapKeysProxy(); | |
178 }; | |
179 | |
180 template<typename KeyArg, typename MappedArg, typename HashArg, typename Ke
yTraitsArg, typename MappedTraitsArg> | |
181 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::Ha
shMapValuesProxy : | |
182 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g> { | |
183 public: | |
184 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg> HashMapType; | |
185 typedef typename HashMapType::iterator::Values iterator; | |
186 typedef typename HashMapType::const_iterator::Values const_iterator; | |
187 | |
188 iterator begin() | |
189 { | |
190 return HashMapType::begin().values(); | |
191 } | |
192 | |
193 iterator end() | |
194 { | |
195 return HashMapType::end().values(); | |
196 } | |
197 | |
198 const_iterator begin() const | |
199 { | |
200 return HashMapType::begin().values(); | |
201 } | |
202 | |
203 const_iterator end() const | |
204 { | |
205 return HashMapType::end().values(); | |
206 } | |
207 | |
208 private: | |
209 friend class HashMap; | |
210 | |
211 // These are intentionally not implemented. | |
212 HashMapValuesProxy(); | |
213 HashMapValuesProxy(const HashMapValuesProxy&); | |
214 HashMapValuesProxy& operator=(const HashMapValuesProxy&); | |
215 ~HashMapValuesProxy(); | |
216 }; | |
217 | |
218 template<typename KeyTraits, typename MappedTraits> struct HashMapValueTrait
s : KeyValuePairHashTraits<KeyTraits, MappedTraits> { | |
219 static const bool hasIsEmptyValueFunction = true; | |
220 static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits
, MappedTraits>::TraitType& value) | |
221 { | |
222 return isHashTraitsEmptyValue<KeyTraits>(value.key); | |
223 } | |
224 }; | |
225 | |
226 template<typename ValueTraits, typename HashFunctions> | |
227 struct HashMapTranslator { | |
228 template<typename T> static unsigned hash(const T& key) { return HashFun
ctions::hash(key); } | |
229 template<typename T, typename U> static bool equal(const T& a, const U&
b) { return HashFunctions::equal(a, b); } | |
230 template<typename T, typename U, typename V> static void translate(T& lo
cation, const U& key, const V& mapped) | |
231 { | |
232 location.key = key; | |
233 ValueTraits::ValueTraits::store(mapped, location.value); | |
234 } | |
235 }; | |
236 | |
237 template<typename ValueTraits, typename Translator> | |
238 struct HashMapTranslatorAdapter { | |
239 template<typename T> static unsigned hash(const T& key) { return Transla
tor::hash(key); } | |
240 template<typename T, typename U> static bool equal(const T& a, const U&
b) { return Translator::equal(a, b); } | |
241 template<typename T, typename U, typename V> static void translate(T& lo
cation, const U& key, const V& mapped, unsigned hashCode) | |
242 { | |
243 Translator::translate(location.key, key, hashCode); | |
244 ValueTraits::ValueTraits::store(mapped, location.value); | |
245 } | |
246 }; | |
247 | |
248 template<typename T, typename U, typename V, typename W, typename X> | |
249 inline void HashMap<T, U, V, W, X>::swap(HashMap& other) | |
250 { | |
251 m_impl.swap(other.m_impl); | |
252 } | |
253 | |
254 template<typename T, typename U, typename V, typename W, typename X> | |
255 inline int HashMap<T, U, V, W, X>::size() const | |
256 { | |
257 return m_impl.size(); | |
258 } | |
259 | |
260 template<typename T, typename U, typename V, typename W, typename X> | |
261 inline int HashMap<T, U, V, W, X>::capacity() const | |
262 { | |
263 return m_impl.capacity(); | |
264 } | |
265 | |
266 template<typename T, typename U, typename V, typename W, typename X> | |
267 inline bool HashMap<T, U, V, W, X>::isEmpty() const | |
268 { | |
269 return m_impl.isEmpty(); | |
270 } | |
271 | |
272 template<typename T, typename U, typename V, typename W, typename X> | |
273 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::beg
in() | |
274 { | |
275 return m_impl.begin(); | |
276 } | |
277 | |
278 template<typename T, typename U, typename V, typename W, typename X> | |
279 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end
() | |
280 { | |
281 return m_impl.end(); | |
282 } | |
283 | |
284 template<typename T, typename U, typename V, typename W, typename X> | |
285 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X
>::begin() const | |
286 { | |
287 return m_impl.begin(); | |
288 } | |
289 | |
290 template<typename T, typename U, typename V, typename W, typename X> | |
291 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X
>::end() const | |
292 { | |
293 return m_impl.end(); | |
294 } | |
295 | |
296 template<typename T, typename U, typename V, typename W, typename X> | |
297 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::fin
d(const KeyType& key) | |
298 { | |
299 return m_impl.find(key); | |
300 } | |
301 | |
302 template<typename T, typename U, typename V, typename W, typename X> | |
303 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X
>::find(const KeyType& key) const | |
304 { | |
305 return m_impl.find(key); | |
306 } | |
307 | |
308 template<typename T, typename U, typename V, typename W, typename X> | |
309 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const | |
310 { | |
311 return m_impl.contains(key); | |
312 } | |
313 | |
314 template<typename T, typename U, typename V, typename W, typename X> | |
315 template<typename TYPE, typename HashTranslator> | |
316 inline typename HashMap<T, U, V, W, X>::iterator | |
317 HashMap<T, U, V, W, X>::find(const TYPE& value) | |
318 { | |
319 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTr
anslator> >(value); | |
320 } | |
321 | |
322 template<typename T, typename U, typename V, typename W, typename X> | |
323 template<typename TYPE, typename HashTranslator> | |
324 inline typename HashMap<T, U, V, W, X>::const_iterator | |
325 HashMap<T, U, V, W, X>::find(const TYPE& value) const | |
326 { | |
327 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTr
anslator> >(value); | |
328 } | |
329 | |
330 template<typename T, typename U, typename V, typename W, typename X> | |
331 template<typename TYPE, typename HashTranslator> | |
332 inline bool | |
333 HashMap<T, U, V, W, X>::contains(const TYPE& value) const | |
334 { | |
335 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, Ha
shTranslator> >(value); | |
336 } | |
337 | |
338 template<typename T, typename U, typename V, typename W, typename X> | |
339 typename HashMap<T, U, V, W, X>::AddResult | |
340 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceT
ype mapped) | |
341 { | |
342 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions>
>(key, mapped); | |
343 } | |
344 | |
345 template<typename T, typename U, typename V, typename W, typename X> | |
346 typename HashMap<T, U, V, W, X>::AddResult | |
347 HashMap<T, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped) | |
348 { | |
349 AddResult result = inlineAdd(key, mapped); | |
350 if (!result.isNewEntry) { | |
351 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | |
352 MappedTraits::store(mapped, result.iterator->value); | |
353 } | |
354 return result; | |
355 } | |
356 | |
357 template<typename T, typename U, typename V, typename W, typename X> | |
358 template<typename TYPE, typename HashTranslator> | |
359 typename HashMap<T, U, V, W, X>::AddResult | |
360 HashMap<T, U, V, W, X>::add(const TYPE& key, MappedPassInType value) | |
361 { | |
362 return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<Value
Traits, HashTranslator> >(key, value); | |
363 } | |
364 | |
365 template<typename T, typename U, typename V, typename W, typename X> | |
366 typename HashMap<T, U, V, W, X>::AddResult | |
367 HashMap<T, U, V, W, X>::add(const KeyType& key, MappedPassInType mapped) | |
368 { | |
369 return inlineAdd(key, mapped); | |
370 } | |
371 | |
372 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
373 typename HashMap<T, U, V, W, MappedTraits>::MappedPeekType | |
374 HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const | |
375 { | |
376 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); | |
377 if (!entry) | |
378 return MappedTraits::peek(MappedTraits::emptyValue()); | |
379 return MappedTraits::peek(entry->value); | |
380 } | |
381 | |
382 template<typename T, typename U, typename V, typename W, typename X> | |
383 inline void HashMap<T, U, V, W, X>::remove(iterator it) | |
384 { | |
385 if (it.m_impl == m_impl.end()) | |
386 return; | |
387 m_impl.internalCheckTableConsistency(); | |
388 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); | |
389 } | |
390 | |
391 template<typename T, typename U, typename V, typename W, typename X> | |
392 inline void HashMap<T, U, V, W, X>::remove(const KeyType& key) | |
393 { | |
394 remove(find(key)); | |
395 } | |
396 | |
397 template<typename T, typename U, typename V, typename W, typename X> | |
398 inline void HashMap<T, U, V, W, X>::clear() | |
399 { | |
400 m_impl.clear(); | |
401 } | |
402 | |
403 template<typename T, typename U, typename V, typename W, typename MappedTrai
ts> | |
404 typename HashMap<T, U, V, W, MappedTraits>::MappedPassOutType | |
405 HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) | |
406 { | |
407 iterator it = find(key); | |
408 if (it == end()) | |
409 return MappedTraits::passOut(MappedTraits::emptyValue()); | |
410 MappedPassOutType result = MappedTraits::passOut(it->value); | |
411 remove(it); | |
412 return result; | |
413 } | |
414 | |
415 template<typename T, typename U, typename V, typename W, typename X> | |
416 inline void HashMap<T, U, V, W, X>::checkConsistency() const | |
417 { | |
418 m_impl.checkTableConsistency(); | |
419 } | |
420 | |
421 template<typename T, typename U, typename V, typename W, typename X> | |
422 inline bool HashMap<T, U, V, W, X>::isValidKey(const KeyType& key) | |
423 { | |
424 if (KeyTraits::isDeletedValue(key)) | |
425 return false; | |
426 | |
427 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | |
428 if (key == KeyTraits::emptyValue()) | |
429 return false; | |
430 } else { | |
431 if (isHashTraitsEmptyValue<KeyTraits>(key)) | |
432 return false; | |
433 } | |
434 | |
435 return true; | |
436 } | |
437 | |
438 template<typename T, typename U, typename V, typename W, typename X> | |
439 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X
>& b) | |
440 { | |
441 if (a.size() != b.size()) | |
442 return false; | |
443 | |
444 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator; | |
445 | |
446 const_iterator end = a.end(); | |
447 const_iterator notFound = b.end(); | |
448 for (const_iterator it = a.begin(); it != end; ++it) { | |
449 const_iterator bPos = b.find(it->key); | |
450 if (bPos == notFound || it->value != bPos->value) | |
451 return false; | |
452 } | |
453 | |
454 return true; | |
455 } | |
456 | |
457 template<typename T, typename U, typename V, typename W, typename X> | |
458 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U,
V, W, X>& b) | |
459 { | |
460 return !(a == b); | |
461 } | |
462 | |
463 template<typename T, typename U, typename V, typename W, typename X> | |
464 inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection) | |
465 { | |
466 typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; | |
467 iterator end = collection.end(); | |
468 for (iterator it = collection.begin(); it != end; ++it) | |
469 delete it->value; | |
470 } | |
471 | |
472 template<typename T, typename U, typename V, typename W, typename X> | |
473 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) | |
474 { | |
475 typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; | |
476 iterator end = collection.end(); | |
477 for (iterator it = collection.begin(); it != end; ++it) | |
478 delete it->key; | |
479 } | |
480 | |
481 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | |
482 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& ve
ctor) | |
483 { | |
484 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; | |
485 | |
486 vector.resize(collection.size()); | |
487 | |
488 iterator it = collection.begin().keys(); | |
489 iterator end = collection.end().keys(); | |
490 for (unsigned i = 0; it != end; ++it, ++i) | |
491 vector[i] = *it; | |
492 } | |
493 | |
494 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | |
495 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y&
vector) | |
496 { | |
497 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator
; | |
498 | |
499 vector.resize(collection.size()); | |
500 | |
501 iterator it = collection.begin().values(); | |
502 iterator end = collection.end().values(); | |
503 for (unsigned i = 0; it != end; ++it, ++i) | |
504 vector[i] = *it; | |
505 } | |
506 | |
507 } // namespace WTF | |
508 | |
509 using WTF::HashMap; | |
510 | |
511 #include <wtf/RefPtrHashMap.h> | |
512 | |
513 #endif /* WTF_HashMap_h */ | |
OLD | NEW |