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 |