1 | /* |
2 | * Copyright (C) 2005, 2006, 2007, 2008 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 | namespace WTF { |
22 | |
23 | // This specialization is a direct copy of HashMap, with overloaded functions |
24 | // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn. |
25 | |
26 | // FIXME: Find a better way that doesn't require an entire copy of the HashMap template. |
27 | |
28 | template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions> |
29 | struct RefPtrHashMapRawKeyTranslator { |
30 | typedef typename ValueType::first_type KeyType; |
31 | typedef typename ValueType::second_type MappedType; |
32 | typedef typename ValueTraits::FirstTraits KeyTraits; |
33 | typedef typename ValueTraits::SecondTraits MappedTraits; |
34 | |
35 | static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); } |
36 | static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); } |
37 | static void translate(ValueType& location, RawKeyType key, const MappedType& mapped) |
38 | { |
39 | location.first = key; |
40 | location.second = mapped; |
41 | } |
42 | }; |
43 | |
44 | template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> |
45 | class RefPtrHashMap : public FastAllocBase { |
46 | private: |
47 | typedef KeyTraitsArg KeyTraits; |
48 | typedef MappedTraitsArg MappedTraits; |
49 | typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits; |
50 | |
51 | public: |
52 | typedef typename KeyTraits::TraitType KeyType; |
53 | typedef T* RawKeyType; |
54 | typedef typename MappedTraits::TraitType MappedType; |
55 | typedef typename ValueTraits::TraitType ValueType; |
56 | |
57 | private: |
58 | typedef HashArg HashFunctions; |
59 | |
60 | typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>, |
61 | HashFunctions, ValueTraits, KeyTraits> HashTableType; |
62 | |
63 | typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions> |
64 | RawKeyTranslator; |
65 | |
66 | public: |
67 | typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; |
68 | typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; |
69 | |
70 | void swap(RefPtrHashMap&); |
71 | |
72 | int size() const; |
73 | int capacity() const; |
74 | bool isEmpty() const; |
75 | |
76 | // iterators iterate over pairs of keys and values |
77 | iterator begin(); |
78 | iterator end(); |
79 | const_iterator begin() const; |
80 | const_iterator end() const; |
81 | |
82 | iterator find(const KeyType&); |
83 | iterator find(RawKeyType); |
84 | const_iterator find(const KeyType&) const; |
85 | const_iterator find(RawKeyType) const; |
86 | bool contains(const KeyType&) const; |
87 | bool contains(RawKeyType) const; |
88 | MappedType get(const KeyType&) const; |
89 | MappedType get(RawKeyType) const; |
90 | MappedType inlineGet(RawKeyType) const; |
91 | |
92 | // replaces value but not key if key is already present |
93 | // return value is a pair of the iterator to the key location, |
94 | // and a boolean that's true if a new value was actually added |
95 | pair<iterator, bool> set(const KeyType&, const MappedType&); |
96 | pair<iterator, bool> set(RawKeyType, const MappedType&); |
97 | |
98 | // does nothing if key is already present |
99 | // return value is a pair of the iterator to the key location, |
100 | // and a boolean that's true if a new value was actually added |
101 | pair<iterator, bool> add(const KeyType&, const MappedType&); |
102 | pair<iterator, bool> add(RawKeyType, const MappedType&); |
103 | |
104 | void remove(const KeyType&); |
105 | void remove(RawKeyType); |
106 | void remove(iterator); |
107 | void clear(); |
108 | |
109 | MappedType take(const KeyType&); // efficient combination of get with remove |
110 | MappedType take(RawKeyType); // efficient combination of get with remove |
111 | |
112 | private: |
113 | pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&); |
114 | pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&); |
115 | |
116 | HashTableType m_impl; |
117 | }; |
118 | template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> |
119 | class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> : |
120 | public RefPtrHashMap<T, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> |
121 | { |
122 | }; |
123 | |
124 | template<typename T, typename U, typename V, typename W, typename X> |
125 | inline void RefPtrHashMap<T, U, V, W, X>::swap(RefPtrHashMap& other) |
126 | { |
127 | m_impl.swap(other.m_impl); |
128 | } |
129 | |
130 | template<typename T, typename U, typename V, typename W, typename X> |
131 | inline int RefPtrHashMap<T, U, V, W, X>::size() const |
132 | { |
133 | return m_impl.size(); |
134 | } |
135 | |
136 | template<typename T, typename U, typename V, typename W, typename X> |
137 | inline int RefPtrHashMap<T, U, V, W, X>::capacity() const |
138 | { |
139 | return m_impl.capacity(); |
140 | } |
141 | |
142 | template<typename T, typename U, typename V, typename W, typename X> |
143 | inline bool RefPtrHashMap<T, U, V, W, X>::isEmpty() const |
144 | { |
145 | return m_impl.isEmpty(); |
146 | } |
147 | |
148 | template<typename T, typename U, typename V, typename W, typename X> |
149 | inline typename RefPtrHashMap<T, U, V, W, X>::iterator RefPtrHashMap<T, U, V, W, X>::begin() |
150 | { |
151 | return m_impl.begin(); |
152 | } |
153 | |
154 | template<typename T, typename U, typename V, typename W, typename X> |
155 | inline typename RefPtrHashMap<T, U, V, W, X>::iterator RefPtrHashMap<T, U, V, W, X>::end() |
156 | { |
157 | return m_impl.end(); |
158 | } |
159 | |
160 | template<typename T, typename U, typename V, typename W, typename X> |
161 | inline typename RefPtrHashMap<T, U, V, W, X>::const_iterator RefPtrHashMap<T, U, V, W, X>::begin() const |
162 | { |
163 | return m_impl.begin(); |
164 | } |
165 | |
166 | template<typename T, typename U, typename V, typename W, typename X> |
167 | inline typename RefPtrHashMap<T, U, V, W, X>::const_iterator RefPtrHashMap<T, U, V, W, X>::end() const |
168 | { |
169 | return m_impl.end(); |
170 | } |
171 | |
172 | template<typename T, typename U, typename V, typename W, typename X> |
173 | inline typename RefPtrHashMap<T, U, V, W, X>::iterator RefPtrHashMap<T, U, V, W, X>::find(const KeyType& key) |
174 | { |
175 | return m_impl.find(key); |
176 | } |
177 | |
178 | template<typename T, typename U, typename V, typename W, typename X> |
179 | inline typename RefPtrHashMap<T, U, V, W, X>::iterator RefPtrHashMap<T, U, V, W, X>::find(RawKeyType key) |
180 | { |
181 | return m_impl.template find<RawKeyType, RawKeyTranslator>(key); |
182 | } |
183 | |
184 | template<typename T, typename U, typename V, typename W, typename X> |
185 | inline typename RefPtrHashMap<T, U, V, W, X>::const_iterator RefPtrHashMap<T, U, V, W, X>::find(const KeyType& key) const |
186 | { |
187 | return m_impl.find(key); |
188 | } |
189 | |
190 | template<typename T, typename U, typename V, typename W, typename X> |
191 | inline typename RefPtrHashMap<T, U, V, W, X>::const_iterator RefPtrHashMap<T, U, V, W, X>::find(RawKeyType key) const |
192 | { |
193 | return m_impl.template find<RawKeyType, RawKeyTranslator>(key); |
194 | } |
195 | |
196 | template<typename T, typename U, typename V, typename W, typename X> |
197 | inline bool RefPtrHashMap<T, U, V, W, X>::contains(const KeyType& key) const |
198 | { |
199 | return m_impl.contains(key); |
200 | } |
201 | |
202 | template<typename T, typename U, typename V, typename W, typename X> |
203 | inline bool RefPtrHashMap<T, U, V, W, X>::contains(RawKeyType key) const |
204 | { |
205 | return m_impl.template contains<RawKeyType, RawKeyTranslator>(key); |
206 | } |
207 | |
208 | template<typename T, typename U, typename V, typename W, typename X> |
209 | inline pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool> |
210 | RefPtrHashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) |
211 | { |
212 | typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType; |
213 | pair<typename HashTableType::iterator, bool> p = m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); |
214 | // typename RefPtrHashMap<T, U, V, W, X>::iterator temp = p.first; |
215 | return std::pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool>( |
216 | typename RefPtrHashMap<T, U, V, W, X>::iterator(p.first), p.second); |
217 | |
218 | // return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped); |
219 | } |
220 | |
221 | template<typename T, typename U, typename V, typename W, typename X> |
222 | inline pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool> |
223 | RefPtrHashMap<T, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) |
224 | { |
225 | pair<typename HashTableType::iterator, bool> p = m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped); |
226 | return std::pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool>( |
227 | typename RefPtrHashMap<T, U, V, W, X>::iterator(p.first), p.second); |
228 | |
229 | // return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped); |
230 | } |
231 | |
232 | template<typename T, typename U, typename V, typename W, typename X> |
233 | pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool> |
234 | RefPtrHashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) |
235 | { |
236 | pair<iterator, bool> result = inlineAdd(key, mapped); |
237 | if (!result.second) { |
238 | // add call above didn't change anything, so set the mapped value |
239 | result.first->second = mapped; |
240 | } |
241 | return result; |
242 | } |
243 | |
244 | template<typename T, typename U, typename V, typename W, typename X> |
245 | pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool> |
246 | RefPtrHashMap<T, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) |
247 | { |
248 | pair<iterator, bool> result = inlineAdd(key, mapped); |
249 | if (!result.second) { |
250 | // add call above didn't change anything, so set the mapped value |
251 | result.first->second = mapped; |
252 | } |
253 | return result; |
254 | } |
255 | |
256 | template<typename T, typename U, typename V, typename W, typename X> |
257 | pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool> |
258 | RefPtrHashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped) |
259 | { |
260 | return inlineAdd(key, mapped); |
261 | } |
262 | |
263 | template<typename T, typename U, typename V, typename W, typename X> |
264 | pair<typename RefPtrHashMap<T, U, V, W, X>::iterator, bool> |
265 | RefPtrHashMap<T, U, V, W, X>::add(RawKeyType key, const MappedType& mapped) |
266 | { |
267 | return inlineAdd(key, mapped); |
268 | } |
269 | |
270 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
271 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType |
272 | RefPtrHashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const |
273 | { |
274 | ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key); |
275 | if (!entry) |
276 | return MappedTraits::emptyValue(); |
277 | return entry->second; |
278 | } |
279 | |
280 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
281 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType |
282 | inline RefPtrHashMap<T, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const |
283 | { |
284 | ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key); |
285 | if (!entry) |
286 | return MappedTraits::emptyValue(); |
287 | return entry->second; |
288 | } |
289 | |
290 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
291 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType |
292 | RefPtrHashMap<T, U, V, W, MappedTraits>::get(RawKeyType key) const |
293 | { |
294 | return inlineGet(key); |
295 | } |
296 | |
297 | template<typename T, typename U, typename V, typename W, typename X> |
298 | inline void RefPtrHashMap<T, U, V, W, X>::(iterator it) |
299 | { |
300 | if (it.m_impl == m_impl.end()) |
301 | return; |
302 | m_impl.checkTableConsistency(); |
303 | m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); |
304 | } |
305 | |
306 | template<typename T, typename U, typename V, typename W, typename X> |
307 | inline void RefPtrHashMap<T, U, V, W, X>::remove(const KeyType& key) |
308 | { |
309 | remove(find(key)); |
310 | } |
311 | |
312 | template<typename T, typename U, typename V, typename W, typename X> |
313 | inline void RefPtrHashMap<T, U, V, W, X>::remove(RawKeyType key) |
314 | { |
315 | remove(find(key)); |
316 | } |
317 | |
318 | template<typename T, typename U, typename V, typename W, typename X> |
319 | inline void RefPtrHashMap<T, U, V, W, X>::clear() |
320 | { |
321 | m_impl.clear(); |
322 | } |
323 | |
324 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
325 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType |
326 | RefPtrHashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) |
327 | { |
328 | // This can probably be made more efficient to avoid ref/deref churn. |
329 | iterator it = find(key); |
330 | if (it == end()) |
331 | return MappedTraits::emptyValue(); |
332 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType result = it->second; |
333 | remove(it); |
334 | return result; |
335 | } |
336 | |
337 | template<typename T, typename U, typename V, typename W, typename MappedTraits> |
338 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType |
339 | RefPtrHashMap<T, U, V, W, MappedTraits>::take(RawKeyType key) |
340 | { |
341 | // This can probably be made more efficient to avoid ref/deref churn. |
342 | iterator it = find(key); |
343 | if (it == end()) |
344 | return MappedTraits::emptyValue(); |
345 | typename RefPtrHashMap<T, U, V, W, MappedTraits>::MappedType result = it->second; |
346 | remove(it); |
347 | return result; |
348 | } |
349 | |
350 | } // namespace WTF |
351 | |