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
24namespace 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
335