• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
hashRefPtrHashMapRawKeyTranslator35         static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); }
equalRefPtrHashMapRawKeyTranslator36         static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); }
translateRefPtrHashMapRawKeyTranslator37         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 HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
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(HashMap&);
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 
119     template<typename T, typename U, typename V, typename W, typename X>
swap(HashMap & other)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>
size()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>
capacity()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>
isEmpty()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>
begin()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>
end()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>
begin()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>
end()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>
find(const KeyType & key)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>
find(RawKeyType key)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<RawKeyType, RawKeyTranslator>(key);
177     }
178 
179     template<typename T, typename U, typename V, typename W, typename X>
find(const KeyType & key)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>
find(RawKeyType key)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<RawKeyType, RawKeyTranslator>(key);
189     }
190 
191     template<typename T, typename U, typename V, typename W, typename X>
contains(const KeyType & key)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>
contains(RawKeyType key)198     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
199     {
200         return m_impl.template contains<RawKeyType, RawKeyTranslator>(key);
201     }
202 
203     template<typename T, typename U, typename V, typename W, typename X>
204     inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
inlineAdd(const KeyType & key,const MappedType & mapped)205     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
206     {
207         typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;
208         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
209     }
210 
211     template<typename T, typename U, typename V, typename W, typename X>
212     inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
inlineAdd(RawKeyType key,const MappedType & mapped)213     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped)
214     {
215         return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped);
216     }
217 
218     template<typename T, typename U, typename V, typename W, typename X>
219     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
set(const KeyType & key,const MappedType & mapped)220     HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
221     {
222         pair<iterator, bool> result = inlineAdd(key, mapped);
223         if (!result.second) {
224             // add call above didn't change anything, so set the mapped value
225             result.first->second = mapped;
226         }
227         return result;
228     }
229 
230     template<typename T, typename U, typename V, typename W, typename X>
231     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
set(RawKeyType key,const MappedType & mapped)232     HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped)
233     {
234         pair<iterator, bool> result = inlineAdd(key, mapped);
235         if (!result.second) {
236             // add call above didn't change anything, so set the mapped value
237             result.first->second = mapped;
238         }
239         return result;
240     }
241 
242     template<typename T, typename U, typename V, typename W, typename X>
243     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
add(const KeyType & key,const MappedType & mapped)244     HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
245     {
246         return inlineAdd(key, mapped);
247     }
248 
249     template<typename T, typename U, typename V, typename W, typename X>
250     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
add(RawKeyType key,const MappedType & mapped)251     HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
252     {
253         return inlineAdd(key, mapped);
254     }
255 
256     template<typename T, typename U, typename V, typename W, typename MappedTraits>
257     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
get(const KeyType & key)258     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
259     {
260         ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
261         if (!entry)
262             return MappedTraits::emptyValue();
263         return entry->second;
264     }
265 
266     template<typename T, typename U, typename V, typename W, typename MappedTraits>
267     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
inlineGet(RawKeyType key)268     inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const
269     {
270         ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key);
271         if (!entry)
272             return MappedTraits::emptyValue();
273         return entry->second;
274     }
275 
276     template<typename T, typename U, typename V, typename W, typename MappedTraits>
277     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
get(RawKeyType key)278     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
279     {
280         return inlineGet(key);
281     }
282 
283     template<typename T, typename U, typename V, typename W, typename X>
remove(iterator it)284     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
285     {
286         if (it.m_impl == m_impl.end())
287             return;
288         m_impl.checkTableConsistency();
289         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
290     }
291 
292     template<typename T, typename U, typename V, typename W, typename X>
remove(const KeyType & key)293     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
294     {
295         remove(find(key));
296     }
297 
298     template<typename T, typename U, typename V, typename W, typename X>
remove(RawKeyType key)299     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)
300     {
301         remove(find(key));
302     }
303 
304     template<typename T, typename U, typename V, typename W, typename X>
clear()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     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
take(const KeyType & key)312     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
313     {
314         // This can probably be made more efficient to avoid ref/deref churn.
315         iterator it = find(key);
316         if (it == end())
317             return MappedTraits::emptyValue();
318         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
319         remove(it);
320         return result;
321     }
322 
323     template<typename T, typename U, typename V, typename W, typename MappedTraits>
324     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
take(RawKeyType key)325     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
326     {
327         // This can probably be made more efficient to avoid ref/deref churn.
328         iterator it = find(key);
329         if (it == end())
330             return MappedTraits::emptyValue();
331         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
332         remove(it);
333         return result;
334     }
335 
336 } // namespace WTF
337