| 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 |
| 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 12 * Library General Public License for more details. | 12 * Library General Public License for more details. |
| 13 * | 13 * |
| 14 * You should have received a copy of the GNU Library General Public License | 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 | 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, | 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
| 17 * Boston, MA 02110-1301, USA. | 17 * Boston, MA 02110-1301, USA. |
| 18 * | 18 * |
| 19 */ | 19 */ |
| 20 | 20 |
| 21 #ifndef RefPtrHashMap_h | 21 #ifndef RefPtrHashMap_h |
| 22 #define RefPtrHashMap_h | 22 #define RefPtrHashMap_h |
| 23 | 23 |
| 24 namespace WTF { | 24 namespace WTF { |
| 25 | 25 |
| 26 // This specialization is a copy of HashMap for use with RefPtr keys, with o
verloaded functions | 26 // This specialization is a copy of HashMap for use with RefPtr keys, with o
verloaded functions |
| 27 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count chur
n. | 27 // to allow for lookup by pointer instead of RefPtr, avoiding ref-count chur
n. |
| 28 | 28 |
| 29 // FIXME: Find a way to do this with traits that doesn't require a copy of
the HashMap template. | 29 // FIXME: Find a way to do this with traits that doesn't require a copy of
the HashMap template. |
| 30 | 30 |
| 31 template<typename T, typename MappedArg, typename HashArg, typename KeyTrait
sArg, typename MappedTraitsArg> | 31 template<typename T, typename MappedArg, typename HashArg, typename KeyTrait
sArg, typename MappedTraitsArg> |
| 32 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>
{ | 32 class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>
{ |
| 33 WTF_MAKE_FAST_ALLOCATED; | 33 WTF_MAKE_FAST_ALLOCATED; |
| 34 private: | 34 private: |
| 35 typedef KeyTraitsArg KeyTraits; | 35 typedef KeyTraitsArg KeyTraits; |
| 36 typedef MappedTraitsArg MappedTraits; | 36 typedef MappedTraitsArg MappedTraits; |
| 37 typedef KeyValuePairHashTraits<KeyTraits, MappedTraits> ValueTraits; | 37 typedef KeyValuePairHashTraits<KeyTraits, MappedTraits> ValueTraits; |
| 38 | 38 |
| 39 public: | 39 public: |
| 40 typedef typename KeyTraits::TraitType KeyType; | 40 typedef typename KeyTraits::TraitType KeyType; |
| 41 typedef T* RawKeyType; | 41 typedef T* RawKeyType; |
| 42 typedef typename MappedTraits::TraitType MappedType; | 42 typedef typename MappedTraits::TraitType MappedType; |
| 43 typedef typename ValueTraits::TraitType ValueType; | 43 typedef typename ValueTraits::TraitType ValueType; |
| 44 | 44 |
| 45 private: | 45 private: |
| 46 typedef typename MappedTraits::PassInType MappedPassInType; | 46 typedef typename MappedTraits::PassInType MappedPassInType; |
| 47 typedef typename MappedTraits::PassOutType MappedPassOutType; | 47 typedef typename MappedTraits::PassOutType MappedPassOutType; |
| 48 typedef typename MappedTraits::PeekType MappedPeekType; | 48 typedef typename MappedTraits::PeekType MappedPeekType; |
| 49 | 49 |
| 50 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType Map
pedPassInReferenceType; | 50 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType Map
pedPassInReferenceType; |
| 51 | 51 |
| 52 typedef HashArg HashFunctions; | 52 typedef HashArg HashFunctions; |
| 53 | 53 |
| 54 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType
>, | 54 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType
>, |
| 55 HashFunctions, ValueTraits, KeyTraits> HashTableType; | 55 HashFunctions, ValueTraits, KeyTraits> HashTableType; |
| 56 | 56 |
| 57 typedef HashMapTranslator<ValueTraits, HashFunctions> | 57 typedef HashMapTranslator<ValueTraits, HashFunctions> |
| 58 Translator; | 58 Translator; |
| 59 | 59 |
| 60 public: | 60 public: |
| 61 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; | 61 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; |
| (...skipping 16 matching lines...) Expand all Loading... |
| 78 iterator find(RawKeyType); | 78 iterator find(RawKeyType); |
| 79 const_iterator find(const KeyType&) const; | 79 const_iterator find(const KeyType&) const; |
| 80 const_iterator find(RawKeyType) const; | 80 const_iterator find(RawKeyType) const; |
| 81 bool contains(const KeyType&) const; | 81 bool contains(const KeyType&) const; |
| 82 bool contains(RawKeyType) const; | 82 bool contains(RawKeyType) const; |
| 83 MappedPeekType get(const KeyType&) const; | 83 MappedPeekType get(const KeyType&) const; |
| 84 MappedPeekType get(RawKeyType) const; | 84 MappedPeekType get(RawKeyType) const; |
| 85 MappedPeekType inlineGet(RawKeyType) const; | 85 MappedPeekType inlineGet(RawKeyType) const; |
| 86 | 86 |
| 87 // replaces value but not key if key is already present | 87 // replaces value but not key if key is already present |
| 88 // return value is a pair of the iterator to the key location, | 88 // return value is a pair of the iterator to the key location, |
| 89 // and a boolean that's true if a new value was actually added | 89 // and a boolean that's true if a new value was actually added |
| 90 AddResult set(const KeyType&, MappedPassInType); | 90 AddResult set(const KeyType&, MappedPassInType); |
| 91 AddResult set(RawKeyType, MappedPassInType); | 91 AddResult set(RawKeyType, MappedPassInType); |
| 92 | 92 |
| 93 // does nothing if key is already present | 93 // does nothing if key is already present |
| 94 // return value is a pair of the iterator to the key location, | 94 // return value is a pair of the iterator to the key location, |
| 95 // and a boolean that's true if a new value was actually added | 95 // and a boolean that's true if a new value was actually added |
| 96 AddResult add(const KeyType&, MappedPassInType); | 96 AddResult add(const KeyType&, MappedPassInType); |
| 97 AddResult add(RawKeyType, MappedPassInType); | 97 AddResult add(RawKeyType, MappedPassInType); |
| 98 | 98 |
| 99 void remove(const KeyType&); | 99 void remove(const KeyType&); |
| 100 void remove(RawKeyType); | 100 void remove(RawKeyType); |
| 101 void remove(iterator); | 101 void remove(iterator); |
| 102 void clear(); | 102 void clear(); |
| 103 | 103 |
| 104 MappedPassOutType take(const KeyType&); // efficient combination of get
with remove | 104 MappedPassOutType take(const KeyType&); // efficient combination of get
with remove |
| 105 MappedPassOutType take(RawKeyType); // efficient combination of get with
remove | 105 MappedPassOutType take(RawKeyType); // efficient combination of get with
remove |
| 106 | 106 |
| 107 private: | 107 private: |
| 108 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); | 108 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType); |
| 109 AddResult inlineAdd(RawKeyType, MappedPassInReferenceType); | 109 AddResult inlineAdd(RawKeyType, MappedPassInReferenceType); |
| 110 | 110 |
| 111 HashTableType m_impl; | 111 HashTableType m_impl; |
| 112 }; | 112 }; |
| 113 | 113 |
| 114 template<typename T, typename U, typename V, typename W, typename X> | 114 template<typename T, typename U, typename V, typename W, typename X> |
| 115 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other) | 115 inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other) |
| 116 { | 116 { |
| 117 m_impl.swap(other.m_impl); | 117 m_impl.swap(other.m_impl); |
| 118 } | 118 } |
| 119 | 119 |
| 120 template<typename T, typename U, typename V, typename W, typename X> | 120 template<typename T, typename U, typename V, typename W, typename X> |
| 121 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const | 121 inline int HashMap<RefPtr<T>, U, V, W, X>::size() const |
| 122 { | 122 { |
| 123 return m_impl.size(); | 123 return m_impl.size(); |
| 124 } | 124 } |
| 125 | 125 |
| 126 template<typename T, typename U, typename V, typename W, typename X> | 126 template<typename T, typename U, typename V, typename W, typename X> |
| 127 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const | 127 inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const |
| 128 { | 128 { |
| 129 return m_impl.capacity(); | 129 return m_impl.capacity(); |
| 130 } | 130 } |
| 131 | 131 |
| 132 template<typename T, typename U, typename V, typename W, typename X> | 132 template<typename T, typename U, typename V, typename W, typename X> |
| 133 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const | 133 inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const |
| 134 { | 134 { |
| 135 return m_impl.isEmpty(); | 135 return m_impl.isEmpty(); |
| 136 } | 136 } |
| 137 | 137 |
| 138 template<typename T, typename U, typename V, typename W, typename X> | 138 template<typename T, typename U, typename V, typename W, typename X> |
| 139 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>,
U, V, W, X>::begin() | 139 inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>,
U, V, W, X>::begin() |
| (...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 190 } | 190 } |
| 191 | 191 |
| 192 template<typename T, typename U, typename V, typename W, typename X> | 192 template<typename T, typename U, typename V, typename W, typename X> |
| 193 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const | 193 inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const |
| 194 { | 194 { |
| 195 return m_impl.template contains<Translator>(key); | 195 return m_impl.template contains<Translator>(key); |
| 196 } | 196 } |
| 197 | 197 |
| 198 template<typename T, typename U, typename V, typename W, typename X> | 198 template<typename T, typename U, typename V, typename W, typename X> |
| 199 inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | 199 inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult |
| 200 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInRe
ferenceType mapped) | 200 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInRe
ferenceType mapped) |
| 201 { | 201 { |
| 202 return m_impl.template add<Translator>(key, mapped); | 202 return m_impl.template add<Translator>(key, mapped); |
| 203 } | 203 } |
| 204 | 204 |
| 205 template<typename T, typename U, typename V, typename W, typename X> | 205 template<typename T, typename U, typename V, typename W, typename X> |
| 206 inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | 206 inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult |
| 207 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInRefere
nceType mapped) | 207 HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInRefere
nceType mapped) |
| 208 { | 208 { |
| 209 return m_impl.template add<Translator>(key, mapped); | 209 return m_impl.template add<Translator>(key, mapped); |
| 210 } | 210 } |
| 211 | 211 |
| 212 template<typename T, typename U, typename V, typename W, typename X> | 212 template<typename T, typename U, typename V, typename W, typename X> |
| 213 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | 213 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult |
| 214 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, MappedPassInType map
ped) | 214 HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, MappedPassInType map
ped) |
| 215 { | 215 { |
| 216 AddResult result = inlineAdd(key, mapped); | 216 AddResult result = inlineAdd(key, mapped); |
| 217 if (!result.isNewEntry) { | 217 if (!result.isNewEntry) { |
| 218 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | 218 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. |
| 219 MappedTraits::store(mapped, result.iterator->value); | 219 MappedTraits::store(mapped, result.iterator->value); |
| 220 } | 220 } |
| 221 return result; | 221 return result; |
| 222 } | 222 } |
| 223 | 223 |
| 224 template<typename T, typename U, typename V, typename W, typename X> | 224 template<typename T, typename U, typename V, typename W, typename X> |
| 225 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult | 225 typename HashMap<RefPtr<T>, U, V, W, X>::AddResult |
| 226 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, MappedPassInType mapped)
| 226 HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, MappedPassInType mapped) |
| 227 { | 227 { |
| 228 AddResult result = inlineAdd(key, mapped); | 228 AddResult result = inlineAdd(key, mapped); |
| 229 if (!result.isNewEntry) { | 229 if (!result.isNewEntry) { |
| 230 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. | 230 // The inlineAdd call above found an existing hash table entry; we n
eed to set the mapped value. |
| 231 MappedTraits::store(mapped, result.iterator->value); | 231 MappedTraits::store(mapped, result.iterator->value); |
| 232 } | 232 } |
| 233 return result; | 233 return result; |
| 234 } | 234 } |
| 235 | 235 |
| 236 template<typename T, typename U, typename V, typename W, typename X> | 236 template<typename T, typename U, typename V, typename W, typename X> |
| (...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 321 if (it == end()) | 321 if (it == end()) |
| 322 return MappedTraits::passOut(MappedTraits::emptyValue()); | 322 return MappedTraits::passOut(MappedTraits::emptyValue()); |
| 323 MappedPassOutType result = MappedTraits::passOut(it->value); | 323 MappedPassOutType result = MappedTraits::passOut(it->value); |
| 324 remove(it); | 324 remove(it); |
| 325 return result; | 325 return result; |
| 326 } | 326 } |
| 327 | 327 |
| 328 } // namespace WTF | 328 } // namespace WTF |
| 329 | 329 |
| 330 #endif // RefPtrHashMap_h | 330 #endif // RefPtrHashMap_h |
| OLD | NEW |