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