• 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 #ifndef WTF_HashMap_h
22 #define WTF_HashMap_h
23 
24 #include "HashTable.h"
25 
26 namespace WTF {
27 
28     template<typename PairType> struct PairFirstExtractor;
29 
30     template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
31         typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
32     class HashMap : public FastAllocBase {
33     private:
34         typedef KeyTraitsArg KeyTraits;
35         typedef MappedTraitsArg MappedTraits;
36         typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
37 
38     public:
39         typedef typename KeyTraits::TraitType KeyType;
40         typedef typename MappedTraits::TraitType MappedType;
41         typedef typename ValueTraits::TraitType ValueType;
42 
43     private:
44         typedef HashArg HashFunctions;
45 
46         typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>,
47             HashFunctions, ValueTraits, KeyTraits> HashTableType;
48 
49     public:
50         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
51         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
52 
53         void swap(HashMap&);
54 
55         int size() const;
56         int capacity() const;
57         bool isEmpty() const;
58 
59         // iterators iterate over pairs of keys and values
60         iterator begin();
61         iterator end();
62         const_iterator begin() const;
63         const_iterator end() const;
64 
65         iterator find(const KeyType&);
66         const_iterator find(const KeyType&) const;
67         bool contains(const KeyType&) const;
68         MappedType get(const KeyType&) const;
69 
70         // replaces value but not key if key is already present
71         // return value is a pair of the iterator to the key location,
72         // and a boolean that's true if a new value was actually added
73         pair<iterator, bool> set(const KeyType&, const MappedType&);
74 
75         // does nothing if key is already present
76         // return value is a pair of the iterator to the key location,
77         // and a boolean that's true if a new value was actually added
78         pair<iterator, bool> add(const KeyType&, const MappedType&);
79 
80         void remove(const KeyType&);
81         void remove(iterator);
82         void clear();
83 
84         MappedType take(const KeyType&); // efficient combination of get with remove
85 
86         // An alternate version of find() that finds the object by hashing and comparing
87         // with some other type, to avoid the cost of type conversion. HashTranslator
88         // must have the following function members:
89         //   static unsigned hash(const T&);
90         //   static bool equal(const ValueType&, const T&);
91         template<typename T, typename HashTranslator> iterator find(const T&);
92         template<typename T, typename HashTranslator> const_iterator find(const T&) const;
93         template<typename T, typename HashTranslator> bool contains(const T&) const;
94 
95         // An alternate version of add() that finds the object by hashing and comparing
96         // with some other type, to avoid the cost of type conversion if the object is already
97         // in the table. HashTranslator must have the following function members:
98         //   static unsigned hash(const T&);
99         //   static bool equal(const ValueType&, const T&);
100         //   static translate(ValueType&, const T&, unsigned hashCode);
101         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&, const MappedType&);
102 
103         void checkConsistency() const;
104 
105     private:
106         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
107 
108         HashTableType m_impl;
109     };
110 
111     template<typename PairType> struct PairFirstExtractor {
extractPairFirstExtractor112         static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
113     };
114 
115     template<typename ValueType, typename ValueTraits, typename HashFunctions>
116     struct HashMapTranslator {
117         typedef typename ValueType::first_type KeyType;
118         typedef typename ValueType::second_type MappedType;
119 
hashHashMapTranslator120         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
equalHashMapTranslator121         static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }
translateHashMapTranslator122         static void translate(ValueType& location, const KeyType& key, const MappedType& mapped)
123         {
124             location.first = key;
125             location.second = mapped;
126         }
127     };
128 
129     template<typename ValueType, typename ValueTraits, typename T, typename Translator>
130     struct HashMapTranslatorAdapter {
131         typedef typename ValueType::first_type KeyType;
132         typedef typename ValueType::second_type MappedType;
133 
hashHashMapTranslatorAdapter134         static unsigned hash(const T& key) { return Translator::hash(key); }
equalHashMapTranslatorAdapter135         static bool equal(const KeyType& a, const T& b) { return Translator::equal(a, b); }
translateHashMapTranslatorAdapter136         static void translate(ValueType& location, const T& key, const MappedType&, unsigned hashCode)
137         {
138             Translator::translate(location.first, key, hashCode);
139         }
140     };
141 
142     template<typename T, typename U, typename V, typename W, typename X>
swap(HashMap & other)143     inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
144     {
145         m_impl.swap(other.m_impl);
146     }
147 
148     template<typename T, typename U, typename V, typename W, typename X>
size()149     inline int HashMap<T, U, V, W, X>::size() const
150     {
151         return m_impl.size();
152     }
153 
154     template<typename T, typename U, typename V, typename W, typename X>
capacity()155     inline int HashMap<T, U, V, W, X>::capacity() const
156     {
157         return m_impl.capacity();
158     }
159 
160     template<typename T, typename U, typename V, typename W, typename X>
isEmpty()161     inline bool HashMap<T, U, V, W, X>::isEmpty() const
162     {
163         return m_impl.isEmpty();
164     }
165 
166     template<typename T, typename U, typename V, typename W, typename X>
begin()167     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
168     {
169         return m_impl.begin();
170     }
171 
172     template<typename T, typename U, typename V, typename W, typename X>
end()173     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
174     {
175         return m_impl.end();
176     }
177 
178     template<typename T, typename U, typename V, typename W, typename X>
begin()179     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
180     {
181         return m_impl.begin();
182     }
183 
184     template<typename T, typename U, typename V, typename W, typename X>
end()185     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
186     {
187         return m_impl.end();
188     }
189 
190     template<typename T, typename U, typename V, typename W, typename X>
find(const KeyType & key)191     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
192     {
193         return m_impl.find(key);
194     }
195 
196     template<typename T, typename U, typename V, typename W, typename X>
find(const KeyType & key)197     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
198     {
199         return m_impl.find(key);
200     }
201 
202     template<typename T, typename U, typename V, typename W, typename X>
contains(const KeyType & key)203     inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
204     {
205         return m_impl.contains(key);
206     }
207 
208     template<typename T, typename U, typename V, typename W, typename X>
209     template<typename TYPE, typename HashTranslator>
210     inline typename HashMap<T, U, V, W, X>::iterator
find(const TYPE & value)211     HashMap<T, U, V, W, X>::find(const TYPE& value)
212     {
213         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;
214         return m_impl.template find<TYPE, Adapter>(value);
215     }
216 
217     template<typename T, typename U, typename V, typename W, typename X>
218     template<typename TYPE, typename HashTranslator>
219     inline typename HashMap<T, U, V, W, X>::const_iterator
find(const TYPE & value)220     HashMap<T, U, V, W, X>::find(const TYPE& value) const
221     {
222         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;
223         return m_impl.template find<TYPE, Adapter>(value);
224     }
225 
226     template<typename T, typename U, typename V, typename W, typename X>
227     template<typename TYPE, typename HashTranslator>
228     inline bool
contains(const TYPE & value)229     HashMap<T, U, V, W, X>::contains(const TYPE& value) const
230     {
231         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;
232         return m_impl.template contains<TYPE, Adapter>(value);
233     }
234 
235     template<typename T, typename U, typename V, typename W, typename X>
236     inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
inlineAdd(const KeyType & key,const MappedType & mapped)237     HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
238     {
239         typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;
240         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
241     }
242 
243     template<typename T, typename U, typename V, typename W, typename X>
244     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
set(const KeyType & key,const MappedType & mapped)245     HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
246     {
247         pair<iterator, bool> result = inlineAdd(key, mapped);
248         if (!result.second) {
249             // add call above didn't change anything, so set the mapped value
250             result.first->second = mapped;
251         }
252         return result;
253     }
254 
255     template<typename T, typename U, typename V, typename W, typename X>
256     template<typename TYPE, typename HashTranslator>
257     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
add(const TYPE & key,const MappedType & value)258     HashMap<T, U, V, W, X>::add(const TYPE& key, const MappedType& value)
259     {
260         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;
261         return m_impl.template addPassingHashCode<TYPE, MappedType, Adapter>(key, value);
262     }
263 
264     template<typename T, typename U, typename V, typename W, typename X>
265     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
add(const KeyType & key,const MappedType & mapped)266     HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
267     {
268         return inlineAdd(key, mapped);
269     }
270 
271     template<typename T, typename U, typename V, typename W, typename MappedTraits>
272     typename HashMap<T, U, V, W, MappedTraits>::MappedType
get(const KeyType & key)273     HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
274     {
275         ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
276         if (!entry)
277             return MappedTraits::emptyValue();
278         return entry->second;
279     }
280 
281     template<typename T, typename U, typename V, typename W, typename X>
remove(iterator it)282     inline void HashMap<T, U, V, W, X>::remove(iterator it)
283     {
284         if (it.m_impl == m_impl.end())
285             return;
286         m_impl.internalCheckTableConsistency();
287         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
288     }
289 
290     template<typename T, typename U, typename V, typename W, typename X>
remove(const KeyType & key)291     inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
292     {
293         remove(find(key));
294     }
295 
296     template<typename T, typename U, typename V, typename W, typename X>
clear()297     inline void HashMap<T, U, V, W, X>::clear()
298     {
299         m_impl.clear();
300     }
301 
302     template<typename T, typename U, typename V, typename W, typename MappedTraits>
303     typename HashMap<T, U, V, W, MappedTraits>::MappedType
take(const KeyType & key)304     HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)
305     {
306         // This can probably be made more efficient to avoid ref/deref churn.
307         iterator it = find(key);
308         if (it == end())
309             return MappedTraits::emptyValue();
310         typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second;
311         remove(it);
312         return result;
313     }
314 
315     template<typename T, typename U, typename V, typename W, typename X>
checkConsistency()316     inline void HashMap<T, U, V, W, X>::checkConsistency() const
317     {
318         m_impl.checkTableConsistency();
319     }
320 
321 
322     template<typename T, typename U, typename V, typename W, typename X>
323     bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
324     {
325         if (a.size() != b.size())
326             return false;
327 
328         typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;
329 
330         const_iterator end = a.end();
331         const_iterator notFound = b.end();
332         for (const_iterator it = a.begin(); it != end; ++it) {
333             const_iterator bPos = b.find(it->first);
334             if (bPos == notFound || it->second != bPos->second)
335                 return false;
336         }
337 
338         return true;
339     }
340 
341     template<typename T, typename U, typename V, typename W, typename X>
342     inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
343     {
344         return !(a == b);
345     }
346 
347     template<typename MappedType, typename HashTableType>
deleteAllPairSeconds(HashTableType & collection)348     void deleteAllPairSeconds(HashTableType& collection)
349     {
350         typedef typename HashTableType::const_iterator iterator;
351         iterator end = collection.end();
352         for (iterator it = collection.begin(); it != end; ++it)
353             delete it->second;
354     }
355 
356     template<typename T, typename U, typename V, typename W, typename X>
deleteAllValues(const HashMap<T,U,V,W,X> & collection)357     inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)
358     {
359         deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
360     }
361 
362     template<typename KeyType, typename HashTableType>
deleteAllPairFirsts(HashTableType & collection)363     void deleteAllPairFirsts(HashTableType& collection)
364     {
365         typedef typename HashTableType::const_iterator iterator;
366         iterator end = collection.end();
367         for (iterator it = collection.begin(); it != end; ++it)
368             delete it->first;
369     }
370 
371     template<typename T, typename U, typename V, typename W, typename X>
deleteAllKeys(const HashMap<T,U,V,W,X> & collection)372     inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)
373     {
374         deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection);
375     }
376 
377     template<typename T, typename U, typename V, typename W, typename X, typename Y>
copyKeysToVector(const HashMap<T,U,V,W,X> & collection,Y & vector)378     inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
379     {
380         typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator;
381 
382         vector.resize(collection.size());
383 
384         iterator it = collection.begin().keys();
385         iterator end = collection.end().keys();
386         for (unsigned i = 0; it != end; ++it, ++i)
387             vector[i] = *it;
388     }
389 
390     template<typename T, typename U, typename V, typename W, typename X, typename Y>
copyValuesToVector(const HashMap<T,U,V,W,X> & collection,Y & vector)391     inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
392     {
393         typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator;
394 
395         vector.resize(collection.size());
396 
397         iterator it = collection.begin().values();
398         iterator end = collection.end().values();
399         for (unsigned i = 0; it != end; ++it, ++i)
400             vector[i] = *it;
401     }
402 
403 } // namespace WTF
404 
405 using WTF::HashMap;
406 
407 #include "RefPtrHashMap.h"
408 
409 #endif /* WTF_HashMap_h */
410