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