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 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
51 typename Allocator = DefaultAllocator> | 51 typename Allocator = DefaultAllocator> |
52 class HashMap { | 52 class HashMap { |
53 WTF_USE_ALLOCATOR(HashMap, Allocator); | 53 WTF_USE_ALLOCATOR(HashMap, Allocator); |
54 private: | 54 private: |
55 typedef KeyTraitsArg KeyTraits; | 55 typedef KeyTraitsArg KeyTraits; |
56 typedef MappedTraitsArg MappedTraits; | 56 typedef MappedTraitsArg MappedTraits; |
57 typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits; | 57 typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits; |
58 | 58 |
59 public: | 59 public: |
60 typedef typename KeyTraits::TraitType KeyType; | 60 typedef typename KeyTraits::TraitType KeyType; |
| 61 typedef typename KeyTraits::PassInType KeyPassInType; |
61 typedef const typename KeyTraits::PeekInType& KeyPeekInType; | 62 typedef const typename KeyTraits::PeekInType& KeyPeekInType; |
62 typedef typename MappedTraits::TraitType MappedType; | 63 typedef typename MappedTraits::TraitType MappedType; |
63 typedef typename ValueTraits::TraitType ValueType; | 64 typedef typename ValueTraits::TraitType ValueType; |
64 | 65 |
65 private: | 66 private: |
66 typedef typename MappedTraits::PassInType MappedPassInType; | 67 typedef typename MappedTraits::PassInType MappedPassInType; |
67 typedef typename MappedTraits::PassOutType MappedPassOutType; | 68 typedef typename MappedTraits::PassOutType MappedPassOutType; |
68 typedef typename MappedTraits::PeekOutType MappedPeekType; | 69 typedef typename MappedTraits::PeekOutType MappedPeekType; |
69 | 70 |
70 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType Map
pedPassInReferenceType; | 71 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType Map
pedPassInReferenceType; |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
111 const HashMapValuesProxy& values() const { return static_cast<const Hash
MapValuesProxy&>(*this); } | 112 const HashMapValuesProxy& values() const { return static_cast<const Hash
MapValuesProxy&>(*this); } |
112 | 113 |
113 iterator find(KeyPeekInType); | 114 iterator find(KeyPeekInType); |
114 const_iterator find(KeyPeekInType) const; | 115 const_iterator find(KeyPeekInType) const; |
115 bool contains(KeyPeekInType) const; | 116 bool contains(KeyPeekInType) const; |
116 MappedPeekType get(KeyPeekInType) const; | 117 MappedPeekType get(KeyPeekInType) const; |
117 | 118 |
118 // replaces value but not key if key is already present | 119 // replaces value but not key if key is already present |
119 // return value is a pair of the iterator to the key location, | 120 // return value is a pair of the iterator to the key location, |
120 // and a boolean that's true if a new value was actually added | 121 // and a boolean that's true if a new value was actually added |
121 AddResult set(KeyPeekInType, MappedPassInType); | 122 AddResult set(KeyPassInType, MappedPassInType); |
122 | 123 |
123 // does nothing if key is already present | 124 // does nothing if key is already present |
124 // return value is a pair of the iterator to the key location, | 125 // return value is a pair of the iterator to the key location, |
125 // and a boolean that's true if a new value was actually added | 126 // and a boolean that's true if a new value was actually added |
126 AddResult add(KeyPeekInType, MappedPassInType); | 127 AddResult add(KeyPassInType, MappedPassInType); |
127 | 128 |
128 void remove(KeyPeekInType); | 129 void remove(KeyPeekInType); |
129 void remove(iterator); | 130 void remove(iterator); |
130 void clear(); | 131 void clear(); |
131 template<typename Collection> | 132 template<typename Collection> |
132 void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, to
BeRemoved); } | 133 void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, to
BeRemoved); } |
133 | 134 |
134 MappedPassOutType take(KeyPeekInType); // efficient combination of get w
ith remove | 135 MappedPassOutType take(KeyPeekInType); // efficient combination of get w
ith remove |
135 | 136 |
136 // An alternate version of find() that finds the object by hashing and c
omparing | 137 // An alternate version of find() that finds the object by hashing and c
omparing |
(...skipping 11 matching lines...) Expand all Loading... |
148 // static unsigned hash(const T&); | 149 // static unsigned hash(const T&); |
149 // static bool equal(const ValueType&, const T&); | 150 // static bool equal(const ValueType&, const T&); |
150 // static translate(ValueType&, const T&, unsigned hashCode); | 151 // static translate(ValueType&, const T&, unsigned hashCode); |
151 template<typename HashTranslator, typename T> AddResult add(const T&, Ma
ppedPassInType); | 152 template<typename HashTranslator, typename T> AddResult add(const T&, Ma
ppedPassInType); |
152 | 153 |
153 static bool isValidKey(KeyPeekInType); | 154 static bool isValidKey(KeyPeekInType); |
154 | 155 |
155 void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor)
; } | 156 void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor)
; } |
156 | 157 |
157 private: | 158 private: |
158 AddResult inlineAdd(KeyPeekInType, MappedPassInReferenceType); | 159 AddResult inlineAdd(KeyPassInType, MappedPassInReferenceType); |
159 | 160 |
160 HashTableType m_impl; | 161 HashTableType m_impl; |
161 }; | 162 }; |
162 | 163 |
163 template<typename KeyArg, typename MappedArg, typename HashArg, typename Key
TraitsArg, typename MappedTraitsArg, typename Allocator> | 164 template<typename KeyArg, typename MappedArg, typename HashArg, typename Key
TraitsArg, typename MappedTraitsArg, typename Allocator> |
164 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, All
ocator>::HashMapKeysProxy : | 165 class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, All
ocator>::HashMapKeysProxy : |
165 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g, Allocator> { | 166 private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsAr
g, Allocator> { |
166 public: | 167 public: |
167 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg, Allocator> HashMapType; | 168 typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTrai
tsArg, Allocator> HashMapType; |
168 typedef typename HashMapType::iterator::Keys iterator; | 169 typedef typename HashMapType::iterator::Keys iterator; |
(...skipping 176 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
345 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 346 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> |
346 template<typename HashTranslator, typename TYPE> | 347 template<typename HashTranslator, typename TYPE> |
347 inline bool | 348 inline bool |
348 HashMap<T, U, V, W, X, Y>::contains(const TYPE& value) const | 349 HashMap<T, U, V, W, X, Y>::contains(const TYPE& value) const |
349 { | 350 { |
350 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, Ha
shTranslator> >(value); | 351 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, Ha
shTranslator> >(value); |
351 } | 352 } |
352 | 353 |
353 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 354 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> |
354 typename HashMap<T, U, V, W, X, Y>::AddResult | 355 typename HashMap<T, U, V, W, X, Y>::AddResult |
355 HashMap<T, U, V, W, X, Y>::inlineAdd(KeyPeekInType key, MappedPassInReferenc
eType mapped) | 356 HashMap<T, U, V, W, X, Y>::inlineAdd(KeyPassInType key, MappedPassInReferenc
eType mapped) |
356 { | 357 { |
357 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions>
>(key, mapped); | 358 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions>
>(key, mapped); |
358 } | 359 } |
359 | 360 |
360 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 361 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> |
361 typename HashMap<T, U, V, W, X, Y>::AddResult | 362 typename HashMap<T, U, V, W, X, Y>::AddResult |
362 HashMap<T, U, V, W, X, Y>::set(KeyPeekInType key, MappedPassInType mapped) | 363 HashMap<T, U, V, W, X, Y>::set(KeyPassInType key, MappedPassInType mapped) |
363 { | 364 { |
364 AddResult result = inlineAdd(key, mapped); | 365 AddResult result = inlineAdd(key, mapped); |
365 if (!result.isNewEntry) { | 366 if (!result.isNewEntry) { |
366 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | 367 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. |
367 MappedTraits::store(mapped, result.storedValue->value); | 368 MappedTraits::store(mapped, result.storedValue->value); |
368 } | 369 } |
369 return result; | 370 return result; |
370 } | 371 } |
371 | 372 |
372 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 373 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> |
373 template<typename HashTranslator, typename TYPE> | 374 template<typename HashTranslator, typename TYPE> |
374 typename HashMap<T, U, V, W, X, Y>::AddResult | 375 typename HashMap<T, U, V, W, X, Y>::AddResult |
375 HashMap<T, U, V, W, X, Y>::add(const TYPE& key, MappedPassInType value) | 376 HashMap<T, U, V, W, X, Y>::add(const TYPE& key, MappedPassInType value) |
376 { | 377 { |
377 return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<Value
Traits, HashTranslator> >(key, value); | 378 return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<Value
Traits, HashTranslator> >(key, value); |
378 } | 379 } |
379 | 380 |
380 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 381 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> |
381 typename HashMap<T, U, V, W, X, Y>::AddResult | 382 typename HashMap<T, U, V, W, X, Y>::AddResult |
382 HashMap<T, U, V, W, X, Y>::add(KeyPeekInType key, MappedPassInType mapped) | 383 HashMap<T, U, V, W, X, Y>::add(KeyPassInType key, MappedPassInType mapped) |
383 { | 384 { |
384 return inlineAdd(key, mapped); | 385 return inlineAdd(key, mapped); |
385 } | 386 } |
386 | 387 |
387 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> | 388 template<typename T, typename U, typename V, typename W, typename X, typenam
e Y> |
388 typename HashMap<T, U, V, W, X, Y>::MappedPeekType | 389 typename HashMap<T, U, V, W, X, Y>::MappedPeekType |
389 HashMap<T, U, V, W, X, Y>::get(KeyPeekInType key) const | 390 HashMap<T, U, V, W, X, Y>::get(KeyPeekInType key) const |
390 { | 391 { |
391 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); | 392 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); |
392 if (!entry) | 393 if (!entry) |
(...skipping 104 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
497 struct NeedsTracing<HashMap<T, U, V, W, X> > { | 498 struct NeedsTracing<HashMap<T, U, V, W, X> > { |
498 static const bool value = false; | 499 static const bool value = false; |
499 }; | 500 }; |
500 #endif | 501 #endif |
501 | 502 |
502 } // namespace WTF | 503 } // namespace WTF |
503 | 504 |
504 using WTF::HashMap; | 505 using WTF::HashMap; |
505 | 506 |
506 #endif /* WTF_HashMap_h */ | 507 #endif /* WTF_HashMap_h */ |
OLD | NEW |