OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 79 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
90 | 90 |
91 HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*
this); } | 91 HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*
this); } |
92 const HashMapValuesProxy& values() const { return static_cast<const Hash
MapValuesProxy&>(*this); } | 92 const HashMapValuesProxy& values() const { return static_cast<const Hash
MapValuesProxy&>(*this); } |
93 | 93 |
94 iterator find(const KeyType&); | 94 iterator find(const KeyType&); |
95 const_iterator find(const KeyType&) const; | 95 const_iterator find(const KeyType&) const; |
96 bool contains(const KeyType&) const; | 96 bool contains(const KeyType&) const; |
97 MappedPeekType get(const KeyType&) const; | 97 MappedPeekType get(const KeyType&) const; |
98 | 98 |
99 // replaces value but not key if key is already present | 99 // replaces value but not key if key is already present |
100 // return value is a pair of the iterator to the key location, | 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 | 101 // and a boolean that's true if a new value was actually added |
102 AddResult set(const KeyType&, MappedPassInType); | 102 AddResult set(const KeyType&, MappedPassInType); |
103 | 103 |
104 // does nothing if key is already present | 104 // does nothing if key is already present |
105 // return value is a pair of the iterator to the key location, | 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 | 106 // and a boolean that's true if a new value was actually added |
107 AddResult add(const KeyType&, MappedPassInType); | 107 AddResult add(const KeyType&, MappedPassInType); |
108 | 108 |
109 void remove(const KeyType&); | 109 void remove(const KeyType&); |
110 void remove(iterator); | 110 void remove(iterator); |
111 void clear(); | 111 void clear(); |
112 | 112 |
113 MappedPassOutType take(const KeyType&); // efficient combination of get
with remove | 113 MappedPassOutType take(const KeyType&); // efficient combination of get
with remove |
114 | 114 |
115 // An alternate version of find() that finds the object by hashing and c
omparing | 115 // An alternate version of find() that finds the object by hashing and c
omparing |
(...skipping 17 matching lines...) Expand all Loading... |
133 | 133 |
134 static bool isValidKey(const KeyType&); | 134 static bool isValidKey(const KeyType&); |
135 | 135 |
136 private: | 136 private: |
137 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); | 137 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); |
138 | 138 |
139 HashTableType m_impl; | 139 HashTableType m_impl; |
140 }; | 140 }; |
141 | 141 |
142 template<typename KeyArg, typename MappedArg, typename HashArg, typename Key
TraitsArg, typename MappedTraitsArg> | 142 template<typename KeyArg, typename MappedArg, typename HashArg, typename Key
TraitsArg, typename MappedTraitsArg> |
143 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::Ha
shMapKeysProxy : | 143 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::Ha
shMapKeysProxy : |
144 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g> { | 144 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g> { |
145 public: | 145 public: |
146 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg> HashMapType; | 146 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg> HashMapType; |
147 typedef typename HashMapType::iterator::Keys iterator; | 147 typedef typename HashMapType::iterator::Keys iterator; |
148 typedef typename HashMapType::const_iterator::Keys const_iterator; | 148 typedef typename HashMapType::const_iterator::Keys const_iterator; |
149 | 149 |
150 iterator begin() | 150 iterator begin() |
151 { | 151 { |
152 return HashMapType::begin().keys(); | 152 return HashMapType::begin().keys(); |
153 } | 153 } |
(...skipping 17 matching lines...) Expand all Loading... |
171 friend class HashMap; | 171 friend class HashMap; |
172 | 172 |
173 // These are intentionally not implemented. | 173 // These are intentionally not implemented. |
174 HashMapKeysProxy(); | 174 HashMapKeysProxy(); |
175 HashMapKeysProxy(const HashMapKeysProxy&); | 175 HashMapKeysProxy(const HashMapKeysProxy&); |
176 HashMapKeysProxy& operator=(const HashMapKeysProxy&); | 176 HashMapKeysProxy& operator=(const HashMapKeysProxy&); |
177 ~HashMapKeysProxy(); | 177 ~HashMapKeysProxy(); |
178 }; | 178 }; |
179 | 179 |
180 template<typename KeyArg, typename MappedArg, typename HashArg, typename Ke
yTraitsArg, typename MappedTraitsArg> | 180 template<typename KeyArg, typename MappedArg, typename HashArg, typename Ke
yTraitsArg, typename MappedTraitsArg> |
181 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::Ha
shMapValuesProxy : | 181 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::Ha
shMapValuesProxy : |
182 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g> { | 182 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g> { |
183 public: | 183 public: |
184 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg> HashMapType; | 184 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg> HashMapType; |
185 typedef typename HashMapType::iterator::Values iterator; | 185 typedef typename HashMapType::iterator::Values iterator; |
186 typedef typename HashMapType::const_iterator::Values const_iterator; | 186 typedef typename HashMapType::const_iterator::Values const_iterator; |
187 | 187 |
188 iterator begin() | 188 iterator begin() |
189 { | 189 { |
190 return HashMapType::begin().values(); | 190 return HashMapType::begin().values(); |
191 } | 191 } |
(...skipping 49 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
241 template<typename T, typename U, typename V> static void translate(T& lo
cation, const U& key, const V& mapped, unsigned hashCode) | 241 template<typename T, typename U, typename V> static void translate(T& lo
cation, const U& key, const V& mapped, unsigned hashCode) |
242 { | 242 { |
243 Translator::translate(location.key, key, hashCode); | 243 Translator::translate(location.key, key, hashCode); |
244 ValueTraits::ValueTraits::store(mapped, location.value); | 244 ValueTraits::ValueTraits::store(mapped, location.value); |
245 } | 245 } |
246 }; | 246 }; |
247 | 247 |
248 template<typename T, typename U, typename V, typename W, typename X> | 248 template<typename T, typename U, typename V, typename W, typename X> |
249 inline void HashMap<T, U, V, W, X>::swap(HashMap& other) | 249 inline void HashMap<T, U, V, W, X>::swap(HashMap& other) |
250 { | 250 { |
251 m_impl.swap(other.m_impl); | 251 m_impl.swap(other.m_impl); |
252 } | 252 } |
253 | 253 |
254 template<typename T, typename U, typename V, typename W, typename X> | 254 template<typename T, typename U, typename V, typename W, typename X> |
255 inline int HashMap<T, U, V, W, X>::size() const | 255 inline int HashMap<T, U, V, W, X>::size() const |
256 { | 256 { |
257 return m_impl.size(); | 257 return m_impl.size(); |
258 } | 258 } |
259 | 259 |
260 template<typename T, typename U, typename V, typename W, typename X> | 260 template<typename T, typename U, typename V, typename W, typename X> |
261 inline int HashMap<T, U, V, W, X>::capacity() const | 261 inline int HashMap<T, U, V, W, X>::capacity() const |
262 { | 262 { |
263 return m_impl.capacity(); | 263 return m_impl.capacity(); |
264 } | 264 } |
265 | 265 |
266 template<typename T, typename U, typename V, typename W, typename X> | 266 template<typename T, typename U, typename V, typename W, typename X> |
267 inline bool HashMap<T, U, V, W, X>::isEmpty() const | 267 inline bool HashMap<T, U, V, W, X>::isEmpty() const |
268 { | 268 { |
269 return m_impl.isEmpty(); | 269 return m_impl.isEmpty(); |
270 } | 270 } |
271 | 271 |
272 template<typename T, typename U, typename V, typename W, typename X> | 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() | 273 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::beg
in() |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
314 template<typename T, typename U, typename V, typename W, typename X> | 314 template<typename T, typename U, typename V, typename W, typename X> |
315 template<typename HashTranslator, typename TYPE> | 315 template<typename HashTranslator, typename TYPE> |
316 inline typename HashMap<T, U, V, W, X>::iterator | 316 inline typename HashMap<T, U, V, W, X>::iterator |
317 HashMap<T, U, V, W, X>::find(const TYPE& value) | 317 HashMap<T, U, V, W, X>::find(const TYPE& value) |
318 { | 318 { |
319 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTr
anslator> >(value); | 319 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTr
anslator> >(value); |
320 } | 320 } |
321 | 321 |
322 template<typename T, typename U, typename V, typename W, typename X> | 322 template<typename T, typename U, typename V, typename W, typename X> |
323 template<typename HashTranslator, typename TYPE> | 323 template<typename HashTranslator, typename TYPE> |
324 inline typename HashMap<T, U, V, W, X>::const_iterator | 324 inline typename HashMap<T, U, V, W, X>::const_iterator |
325 HashMap<T, U, V, W, X>::find(const TYPE& value) const | 325 HashMap<T, U, V, W, X>::find(const TYPE& value) const |
326 { | 326 { |
327 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTr
anslator> >(value); | 327 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTr
anslator> >(value); |
328 } | 328 } |
329 | 329 |
330 template<typename T, typename U, typename V, typename W, typename X> | 330 template<typename T, typename U, typename V, typename W, typename X> |
331 template<typename HashTranslator, typename TYPE> | 331 template<typename HashTranslator, typename TYPE> |
332 inline bool | 332 inline bool |
333 HashMap<T, U, V, W, X>::contains(const TYPE& value) const | 333 HashMap<T, U, V, W, X>::contains(const TYPE& value) const |
334 { | 334 { |
335 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, Ha
shTranslator> >(value); | 335 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, Ha
shTranslator> >(value); |
336 } | 336 } |
337 | 337 |
338 template<typename T, typename U, typename V, typename W, typename X> | 338 template<typename T, typename U, typename V, typename W, typename X> |
339 typename HashMap<T, U, V, W, X>::AddResult | 339 typename HashMap<T, U, V, W, X>::AddResult |
340 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceT
ype mapped) | 340 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceT
ype mapped) |
341 { | 341 { |
342 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions>
>(key, mapped); | 342 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions>
>(key, mapped); |
343 } | 343 } |
344 | 344 |
345 template<typename T, typename U, typename V, typename W, typename X> | 345 template<typename T, typename U, typename V, typename W, typename X> |
346 typename HashMap<T, U, V, W, X>::AddResult | 346 typename HashMap<T, U, V, W, X>::AddResult |
347 HashMap<T, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped) | 347 HashMap<T, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped) |
348 { | 348 { |
349 AddResult result = inlineAdd(key, mapped); | 349 AddResult result = inlineAdd(key, mapped); |
350 if (!result.isNewEntry) { | 350 if (!result.isNewEntry) { |
351 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | 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); | 352 MappedTraits::store(mapped, result.iterator->value); |
353 } | 353 } |
354 return result; | 354 return result; |
355 } | 355 } |
356 | 356 |
357 template<typename T, typename U, typename V, typename W, typename X> | 357 template<typename T, typename U, typename V, typename W, typename X> |
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
470 } | 470 } |
471 | 471 |
472 template<typename T, typename U, typename V, typename W, typename X> | 472 template<typename T, typename U, typename V, typename W, typename X> |
473 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) | 473 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection) |
474 { | 474 { |
475 typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; | 475 typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; |
476 iterator end = collection.end(); | 476 iterator end = collection.end(); |
477 for (iterator it = collection.begin(); it != end; ++it) | 477 for (iterator it = collection.begin(); it != end; ++it) |
478 delete it->key; | 478 delete it->key; |
479 } | 479 } |
480 | 480 |
481 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 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) | 482 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& ve
ctor) |
483 { | 483 { |
484 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; | 484 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; |
485 | 485 |
486 vector.resize(collection.size()); | 486 vector.resize(collection.size()); |
487 | 487 |
488 iterator it = collection.begin().keys(); | 488 iterator it = collection.begin().keys(); |
489 iterator end = collection.end().keys(); | 489 iterator end = collection.end().keys(); |
490 for (unsigned i = 0; it != end; ++it, ++i) | 490 for (unsigned i = 0; it != end; ++it, ++i) |
491 vector[i] = *it; | 491 vector[i] = *it; |
492 } | 492 } |
493 | 493 |
494 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 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) | 495 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y&
vector) |
496 { | 496 { |
497 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator
; | 497 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator
; |
498 | 498 |
499 vector.resize(collection.size()); | 499 vector.resize(collection.size()); |
500 | 500 |
501 iterator it = collection.begin().values(); | 501 iterator it = collection.begin().values(); |
502 iterator end = collection.end().values(); | 502 iterator end = collection.end().values(); |
503 for (unsigned i = 0; it != end; ++it, ++i) | 503 for (unsigned i = 0; it != end; ++it, ++i) |
504 vector[i] = *it; | 504 vector[i] = *it; |
505 } | 505 } |
506 | 506 |
507 } // namespace WTF | 507 } // namespace WTF |
508 | 508 |
509 using WTF::HashMap; | 509 using WTF::HashMap; |
510 | 510 |
511 #include "wtf/RefPtrHashMap.h" | 511 #include "wtf/RefPtrHashMap.h" |
512 | 512 |
513 #endif /* WTF_HashMap_h */ | 513 #endif /* WTF_HashMap_h */ |
OLD | NEW |