1/*
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 "wtf/DefaultAllocator.h"
25#include "wtf/HashTable.h"
26
27namespace WTF {
28
29    template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits;
30
31    template<typename T> struct ReferenceTypeMaker {
32        typedef T& ReferenceType;
33    };
34    template<typename T> struct ReferenceTypeMaker<T&> {
35        typedef T& ReferenceType;
36    };
37
38    struct KeyValuePairKeyExtractor {
39        template<typename T>
40        static const typename T::KeyType& extract(const T& p) { return p.key; }
41    };
42
43    // Note: empty or deleted key values are not allowed, using them may lead to undefined behavior.
44    // For pointer keys this means that null pointers are not allowed unless you supply custom key traits.
45    template<
46        typename KeyArg,
47        typename MappedArg,
48        typename HashArg = typename DefaultHash<KeyArg>::Hash,
49        typename KeyTraitsArg = HashTraits<KeyArg>,
50        typename MappedTraitsArg = HashTraits<MappedArg>,
51        typename Allocator = DefaultAllocator>
52    class HashMap {
53        WTF_USE_ALLOCATOR(HashMap, Allocator);
54    private:
55        typedef KeyTraitsArg KeyTraits;
56        typedef MappedTraitsArg MappedTraits;
57        typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits;
58
59    public:
60        typedef typename KeyTraits::TraitType KeyType;
61        typedef const typename KeyTraits::PeekInType& KeyPeekInType;
62        typedef typename MappedTraits::TraitType MappedType;
63        typedef typename ValueTraits::TraitType ValueType;
64
65    private:
66        typedef typename MappedTraits::PassInType MappedPassInType;
67        typedef typename MappedTraits::PassOutType MappedPassOutType;
68        typedef typename MappedTraits::PeekOutType MappedPeekType;
69
70        typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType;
71
72        typedef HashArg HashFunctions;
73
74        typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor,
75            HashFunctions, ValueTraits, KeyTraits, Allocator> HashTableType;
76
77        class HashMapKeysProxy;
78        class HashMapValuesProxy;
79
80    public:
81        typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
82        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
83        typedef typename HashTableType::AddResult AddResult;
84
85    public:
86        void swap(HashMap& ref)
87        {
88            m_impl.swap(ref.m_impl);
89        }
90
91        void swap(typename Allocator::template OtherType<HashMap>::Type other)
92        {
93            HashMap& ref = Allocator::getOther(other);
94            m_impl.swap(ref.m_impl);
95        }
96
97        unsigned size() const;
98        unsigned capacity() const;
99        bool isEmpty() const;
100
101        // iterators iterate over pairs of keys and values
102        iterator begin();
103        iterator end();
104        const_iterator begin() const;
105        const_iterator end() const;
106
107        HashMapKeysProxy& keys() { return static_cast<HashMapKeysProxy&>(*this); }
108        const HashMapKeysProxy& keys() const { return static_cast<const HashMapKeysProxy&>(*this); }
109
110        HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*this); }
111        const HashMapValuesProxy& values() const { return static_cast<const HashMapValuesProxy&>(*this); }
112
113        iterator find(KeyPeekInType);
114        const_iterator find(KeyPeekInType) const;
115        bool contains(KeyPeekInType) const;
116        MappedPeekType get(KeyPeekInType) const;
117
118        // replaces value but not key if key is already present
119        // return value is a pair of the iterator to the key location,
120        // and a boolean that's true if a new value was actually added
121        AddResult set(KeyPeekInType, MappedPassInType);
122
123        // does nothing if key is already present
124        // return value is a pair of the iterator to the key location,
125        // and a boolean that's true if a new value was actually added
126        AddResult add(KeyPeekInType, MappedPassInType);
127
128        void remove(KeyPeekInType);
129        void remove(iterator);
130        void clear();
131        template<typename Collection>
132        void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, toBeRemoved); }
133
134        MappedPassOutType take(KeyPeekInType); // efficient combination of get with remove
135
136        // An alternate version of find() that finds the object by hashing and comparing
137        // with some other type, to avoid the cost of type conversion. HashTranslator
138        // must have the following function members:
139        //   static unsigned hash(const T&);
140        //   static bool equal(const ValueType&, const T&);
141        template<typename HashTranslator, typename T> iterator find(const T&);
142        template<typename HashTranslator, typename T> const_iterator find(const T&) const;
143        template<typename HashTranslator, typename T> bool contains(const T&) const;
144
145        // An alternate version of add() that finds the object by hashing and comparing
146        // with some other type, to avoid the cost of type conversion if the object is already
147        // in the table. HashTranslator must have the following function members:
148        //   static unsigned hash(const T&);
149        //   static bool equal(const ValueType&, const T&);
150        //   static translate(ValueType&, const T&, unsigned hashCode);
151        template<typename HashTranslator, typename T> AddResult add(const T&, MappedPassInType);
152
153        static bool isValidKey(KeyPeekInType);
154
155        void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); }
156
157    private:
158        AddResult inlineAdd(KeyPeekInType, MappedPassInReferenceType);
159
160        HashTableType m_impl;
161    };
162
163    template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg, typename Allocator>
164    class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMapKeysProxy :
165        private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> {
166        public:
167            typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> HashMapType;
168            typedef typename HashMapType::iterator::Keys iterator;
169            typedef typename HashMapType::const_iterator::Keys const_iterator;
170
171            iterator begin()
172            {
173                return HashMapType::begin().keys();
174            }
175
176            iterator end()
177            {
178                return HashMapType::end().keys();
179            }
180
181            const_iterator begin() const
182            {
183                return HashMapType::begin().keys();
184            }
185
186            const_iterator end() const
187            {
188                return HashMapType::end().keys();
189            }
190
191        private:
192            friend class HashMap;
193
194            // These are intentionally not implemented.
195            HashMapKeysProxy();
196            HashMapKeysProxy(const HashMapKeysProxy&);
197            HashMapKeysProxy& operator=(const HashMapKeysProxy&);
198            ~HashMapKeysProxy();
199    };
200
201    template<typename KeyArg, typename MappedArg, typename HashArg,  typename KeyTraitsArg, typename MappedTraitsArg, typename Allocator>
202    class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMapValuesProxy :
203        private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> {
204        public:
205            typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> HashMapType;
206            typedef typename HashMapType::iterator::Values iterator;
207            typedef typename HashMapType::const_iterator::Values const_iterator;
208
209            iterator begin()
210            {
211                return HashMapType::begin().values();
212            }
213
214            iterator end()
215            {
216                return HashMapType::end().values();
217            }
218
219            const_iterator begin() const
220            {
221                return HashMapType::begin().values();
222            }
223
224            const_iterator end() const
225            {
226                return HashMapType::end().values();
227            }
228
229        private:
230            friend class HashMap;
231
232            // These are intentionally not implemented.
233            HashMapValuesProxy();
234            HashMapValuesProxy(const HashMapValuesProxy&);
235            HashMapValuesProxy& operator=(const HashMapValuesProxy&);
236            ~HashMapValuesProxy();
237    };
238
239    template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits : KeyValuePairHashTraits<KeyTraits, MappedTraits> {
240        static const bool hasIsEmptyValueFunction = true;
241        static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits, MappedTraits>::TraitType& value)
242        {
243            return isHashTraitsEmptyValue<KeyTraits>(value.key);
244        }
245    };
246
247    template<typename ValueTraits, typename HashFunctions>
248    struct HashMapTranslator {
249        template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
250        template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
251        template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped)
252        {
253            location.key = key;
254            ValueTraits::ValueTraits::store(mapped, location.value);
255        }
256    };
257
258    template<typename ValueTraits, typename Translator>
259    struct HashMapTranslatorAdapter {
260        template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
261        template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
262        template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped, unsigned hashCode)
263        {
264            Translator::translate(location.key, key, hashCode);
265            ValueTraits::ValueTraits::store(mapped, location.value);
266        }
267    };
268
269    template<typename T, typename U, typename V, typename W, typename X, typename Y>
270    inline unsigned HashMap<T, U, V, W, X, Y>::size() const
271    {
272        return m_impl.size();
273    }
274
275    template<typename T, typename U, typename V, typename W, typename X, typename Y>
276    inline unsigned HashMap<T, U, V, W, X, Y>::capacity() const
277    {
278        return m_impl.capacity();
279    }
280
281    template<typename T, typename U, typename V, typename W, typename X, typename Y>
282    inline bool HashMap<T, U, V, W, X, Y>::isEmpty() const
283    {
284        return m_impl.isEmpty();
285    }
286
287    template<typename T, typename U, typename V, typename W, typename X, typename Y>
288    inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::begin()
289    {
290        return m_impl.begin();
291    }
292
293    template<typename T, typename U, typename V, typename W, typename X, typename Y>
294    inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::end()
295    {
296        return m_impl.end();
297    }
298
299    template<typename T, typename U, typename V, typename W, typename X, typename Y>
300    inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::begin() const
301    {
302        return m_impl.begin();
303    }
304
305    template<typename T, typename U, typename V, typename W, typename X, typename Y>
306    inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::end() const
307    {
308        return m_impl.end();
309    }
310
311    template<typename T, typename U, typename V, typename W, typename X, typename Y>
312    inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::find(KeyPeekInType key)
313    {
314        return m_impl.find(key);
315    }
316
317    template<typename T, typename U, typename V, typename W, typename X, typename Y>
318    inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::find(KeyPeekInType key) const
319    {
320        return m_impl.find(key);
321    }
322
323    template<typename T, typename U, typename V, typename W, typename X, typename Y>
324    inline bool HashMap<T, U, V, W, X, Y>::contains(KeyPeekInType key) const
325    {
326        return m_impl.contains(key);
327    }
328
329    template<typename T, typename U, typename V, typename W, typename X, typename Y>
330    template<typename HashTranslator, typename TYPE>
331    inline typename HashMap<T, U, V, W, X, Y>::iterator
332    HashMap<T, U, V, W, X, Y>::find(const TYPE& value)
333    {
334        return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value);
335    }
336
337    template<typename T, typename U, typename V, typename W, typename X, typename Y>
338    template<typename HashTranslator, typename TYPE>
339    inline typename HashMap<T, U, V, W, X, Y>::const_iterator
340    HashMap<T, U, V, W, X, Y>::find(const TYPE& value) const
341    {
342        return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value);
343    }
344
345    template<typename T, typename U, typename V, typename W, typename X, typename Y>
346    template<typename HashTranslator, typename TYPE>
347    inline bool
348    HashMap<T, U, V, W, X, Y>::contains(const TYPE& value) const
349    {
350        return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value);
351    }
352
353    template<typename T, typename U, typename V, typename W, typename X, typename Y>
354    typename HashMap<T, U, V, W, X, Y>::AddResult
355    HashMap<T, U, V, W, X, Y>::inlineAdd(KeyPeekInType key, MappedPassInReferenceType mapped)
356    {
357        return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions> >(key, mapped);
358    }
359
360    template<typename T, typename U, typename V, typename W, typename X, typename Y>
361    typename HashMap<T, U, V, W, X, Y>::AddResult
362    HashMap<T, U, V, W, X, Y>::set(KeyPeekInType key, MappedPassInType mapped)
363    {
364        AddResult result = inlineAdd(key, mapped);
365        if (!result.isNewEntry) {
366            // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
367            MappedTraits::store(mapped, result.storedValue->value);
368        }
369        return result;
370    }
371
372    template<typename T, typename U, typename V, typename W, typename X, typename Y>
373    template<typename HashTranslator, typename TYPE>
374    typename HashMap<T, U, V, W, X, Y>::AddResult
375    HashMap<T, U, V, W, X, Y>::add(const TYPE& key, MappedPassInType value)
376    {
377        return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(key, value);
378    }
379
380    template<typename T, typename U, typename V, typename W, typename X, typename Y>
381    typename HashMap<T, U, V, W, X, Y>::AddResult
382    HashMap<T, U, V, W, X, Y>::add(KeyPeekInType key, MappedPassInType mapped)
383    {
384        return inlineAdd(key, mapped);
385    }
386
387    template<typename T, typename U, typename V, typename W, typename X, typename Y>
388    typename HashMap<T, U, V, W, X, Y>::MappedPeekType
389    HashMap<T, U, V, W, X, Y>::get(KeyPeekInType key) const
390    {
391        ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
392        if (!entry)
393            return MappedTraits::peek(MappedTraits::emptyValue());
394        return MappedTraits::peek(entry->value);
395    }
396
397    template<typename T, typename U, typename V, typename W, typename X, typename Y>
398    inline void HashMap<T, U, V, W, X, Y>::remove(iterator it)
399    {
400        m_impl.remove(it.m_impl);
401    }
402
403    template<typename T, typename U, typename V, typename W, typename X, typename Y>
404    inline void HashMap<T, U, V, W, X, Y>::remove(KeyPeekInType key)
405    {
406        remove(find(key));
407    }
408
409    template<typename T, typename U, typename V, typename W, typename X, typename Y>
410    inline void HashMap<T, U, V, W, X, Y>::clear()
411    {
412        m_impl.clear();
413    }
414
415    template<typename T, typename U, typename V, typename W, typename X, typename Y>
416    typename HashMap<T, U, V, W, X, Y>::MappedPassOutType
417    HashMap<T, U, V, W, X, Y>::take(KeyPeekInType key)
418    {
419        iterator it = find(key);
420        if (it == end())
421            return MappedTraits::passOut(MappedTraits::emptyValue());
422        MappedPassOutType result = MappedTraits::passOut(it->value);
423        remove(it);
424        return result;
425    }
426
427    template<typename T, typename U, typename V, typename W, typename X, typename Y>
428    inline bool HashMap<T, U, V, W, X, Y>::isValidKey(KeyPeekInType key)
429    {
430        if (KeyTraits::isDeletedValue(key))
431            return false;
432
433        if (HashFunctions::safeToCompareToEmptyOrDeleted) {
434            if (key == KeyTraits::emptyValue())
435                return false;
436        } else {
437            if (isHashTraitsEmptyValue<KeyTraits>(key))
438                return false;
439        }
440
441        return true;
442    }
443
444    template<typename T, typename U, typename V, typename W, typename X, typename Y>
445    bool operator==(const HashMap<T, U, V, W, X, Y>& a, const HashMap<T, U, V, W, X, Y>& b)
446    {
447        if (a.size() != b.size())
448            return false;
449
450        typedef typename HashMap<T, U, V, W, X, Y>::const_iterator const_iterator;
451
452        const_iterator aEnd = a.end();
453        const_iterator bEnd = b.end();
454        for (const_iterator it = a.begin(); it != aEnd; ++it) {
455            const_iterator bPos = b.find(it->key);
456            if (bPos == bEnd || it->value != bPos->value)
457                return false;
458        }
459
460        return true;
461    }
462
463    template<typename T, typename U, typename V, typename W, typename X, typename Y>
464    inline bool operator!=(const HashMap<T, U, V, W, X, Y>& a, const HashMap<T, U, V, W, X, Y>& b)
465    {
466        return !(a == b);
467    }
468
469    template<typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
470    inline void copyKeysToVector(const HashMap<T, U, V, W, X, Y>& collection, Z& vector)
471    {
472        typedef typename HashMap<T, U, V, W, X, Y>::const_iterator::Keys iterator;
473
474        vector.resize(collection.size());
475
476        iterator it = collection.begin().keys();
477        iterator end = collection.end().keys();
478        for (unsigned i = 0; it != end; ++it, ++i)
479            vector[i] = *it;
480    }
481
482    template<typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
483    inline void copyValuesToVector(const HashMap<T, U, V, W, X, Y>& collection, Z& vector)
484    {
485        typedef typename HashMap<T, U, V, W, X, Y>::const_iterator::Values iterator;
486
487        vector.resize(collection.size());
488
489        iterator it = collection.begin().values();
490        iterator end = collection.end().values();
491        for (unsigned i = 0; it != end; ++it, ++i)
492            vector[i] = *it;
493    }
494
495#if !ENABLE(OILPAN)
496template<typename T, typename U, typename V, typename W, typename X>
497struct NeedsTracing<HashMap<T, U, V, W, X> > {
498    static const bool value = false;
499};
500#endif
501
502} // namespace WTF
503
504using WTF::HashMap;
505
506#endif /* WTF_HashMap_h */
507