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