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
21namespace 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>::remove(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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/wtf/RefPtrHashMap.h