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 {

   112         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 

   120         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }

   121         static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }

   122         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 

   134         static unsigned hash(const T& key) { return Translator::hash(key); }

   135         static bool equal(const KeyType& a, const T& b) { return Translator::equal(a, b); }

   136         static void translate(ValueType& location, const T& key, const MappedType& mapped, unsigned hashCode)

   137         {

   138             Translator::translate(location.first, key, hashCode);

   139             location.second = mapped;

   140         }

   141     };

   142 

   143     template<typename T, typename U, typename V, typename W, typename X>

   144     inline void HashMap<T, U, V, W, X>::swap(HashMap& other)

   145     {

   146         m_impl.swap(other.m_impl); 

   147     }

   148 

   149     template<typename T, typename U, typename V, typename W, typename X>

   150     inline int HashMap<T, U, V, W, X>::size() const

   151     {

   152         return m_impl.size(); 

   153     }

   154 

   155     template<typename T, typename U, typename V, typename W, typename X>

   156     inline int HashMap<T, U, V, W, X>::capacity() const

   157     { 

   158         return m_impl.capacity(); 

   159     }

   160 

   161     template<typename T, typename U, typename V, typename W, typename X>

   162     inline bool HashMap<T, U, V, W, X>::isEmpty() const

   163     {

   164         return m_impl.isEmpty();

   165     }

   166 

   167     template<typename T, typename U, typename V, typename W, typename X>

   168     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()

   169     {

   170         return m_impl.begin();

   171     }

   172 

   173     template<typename T, typename U, typename V, typename W, typename X>

   174     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()

   175     {

   176         return m_impl.end();

   177     }

   178 

   179     template<typename T, typename U, typename V, typename W, typename X>

   180     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const

   181     {

   182         return m_impl.begin();

   183     }

   184 

   185     template<typename T, typename U, typename V, typename W, typename X>

   186     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const

   187     {

   188         return m_impl.end();

   189     }

   190 

   191     template<typename T, typename U, typename V, typename W, typename X>

   192     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)

   193     {

   194         return m_impl.find(key);

   195     }

   196 

   197     template<typename T, typename U, typename V, typename W, typename X>

   198     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const

   199     {

   200         return m_impl.find(key);

   201     }

   202 

   203     template<typename T, typename U, typename V, typename W, typename X>

   204     inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const

   205     {

   206         return m_impl.contains(key);

   207     }

   208 

   209     template<typename T, typename U, typename V, typename W, typename X>

   210     template<typename TYPE, typename HashTranslator>

   211     inline typename HashMap<T, U, V, W, X>::iterator

   212     HashMap<T, U, V, W, X>::find(const TYPE& value)

   213     {

   214         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;

   215         return m_impl.template find<TYPE, Adapter>(value);

   216     }

   217 

   218     template<typename T, typename U, typename V, typename W, typename X>

   219     template<typename TYPE, typename HashTranslator>

   220     inline typename HashMap<T, U, V, W, X>::const_iterator 

   221     HashMap<T, U, V, W, X>::find(const TYPE& value) const

   222     {

   223         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;

   224         return m_impl.template find<TYPE, Adapter>(value);

   225     }

   226 

   227     template<typename T, typename U, typename V, typename W, typename X>

   228     template<typename TYPE, typename HashTranslator>

   229     inline bool

   230     HashMap<T, U, V, W, X>::contains(const TYPE& value) const

   231     {

   232         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;

   233         return m_impl.template contains<TYPE, Adapter>(value);

   234     }

   235 

   236     template<typename T, typename U, typename V, typename W, typename X>

   237     inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>

   238     HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 

   239     {

   240         typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;

   241         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);

   242     }

   243 

   244     template<typename T, typename U, typename V, typename W, typename X>

   245     pair<typename HashMap<T, U, V, W, X>::iterator, bool>

   246     HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 

   247     {

   248         pair<iterator, bool> result = inlineAdd(key, mapped);

   249         if (!result.second) {

   250             // add call above didn't change anything, so set the mapped value

   251             result.first->second = mapped;

   252         }

   253         return result;

   254     }

   255 

   256     template<typename T, typename U, typename V, typename W, typename X>

   257     template<typename TYPE, typename HashTranslator>

   258     pair<typename HashMap<T, U, V, W, X>::iterator, bool>

   259     HashMap<T, U, V, W, X>::add(const TYPE& key, const MappedType& value)

   260     {

   261         typedef HashMapTranslatorAdapter<ValueType, ValueTraits, TYPE, HashTranslator> Adapter;

   262         return m_impl.template addPassingHashCode<TYPE, MappedType, Adapter>(key, value);

   263     }

   264 

   265     template<typename T, typename U, typename V, typename W, typename X>

   266     pair<typename HashMap<T, U, V, W, X>::iterator, bool>

   267     HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)

   268     {

   269         return inlineAdd(key, mapped);

   270     }

   271 

   272     template<typename T, typename U, typename V, typename W, typename MappedTraits>

   273     typename HashMap<T, U, V, W, MappedTraits>::MappedType

   274     HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const

   275     {

   276         ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);

   277         if (!entry)

   278             return MappedTraits::emptyValue();

   279         return entry->second;

   280     }

   281 

   282     template<typename T, typename U, typename V, typename W, typename X>

   283     inline void HashMap<T, U, V, W, X>::remove(iterator it)

   284     {

   285         if (it.m_impl == m_impl.end())

   286             return;

   287         m_impl.internalCheckTableConsistency();

   288         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);

   289     }

   290 

   291     template<typename T, typename U, typename V, typename W, typename X>

   292     inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)

   293     {

   294         remove(find(key));

   295     }

   296 

   297     template<typename T, typename U, typename V, typename W, typename X>

   298     inline void HashMap<T, U, V, W, X>::clear()

   299     {

   300         m_impl.clear();

   301     }

   302 

   303     template<typename T, typename U, typename V, typename W, typename MappedTraits>

   304     typename HashMap<T, U, V, W, MappedTraits>::MappedType

   305     HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)

   306     {

   307         // This can probably be made more efficient to avoid ref/deref churn.

   308         iterator it = find(key);

   309         if (it == end())

   310             return MappedTraits::emptyValue();

   311         typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second;

   312         remove(it);

   313         return result;

   314     }

   315 

   316     template<typename T, typename U, typename V, typename W, typename X>

   317     inline void HashMap<T, U, V, W, X>::checkConsistency() const

   318     {

   319         m_impl.checkTableConsistency();

   320     }

   321 

   322 

   323     template<typename T, typename U, typename V, typename W, typename X>

   324     bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)

   325     {

   326         if (a.size() != b.size())

   327             return false;

   328 

   329         typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;

   330 

   331         const_iterator end = a.end();

   332         const_iterator notFound = b.end();

   333         for (const_iterator it = a.begin(); it != end; ++it) {

   334             const_iterator bPos = b.find(it->first);

   335             if (bPos == notFound || it->second != bPos->second)

   336                 return false;

   337         }

   338 

   339         return true;

   340     }

   341 

   342     template<typename T, typename U, typename V, typename W, typename X>

   343     inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)

   344     {

   345         return !(a == b);

   346     }

   347 

   348     template<typename MappedType, typename HashTableType>

   349     void deleteAllPairSeconds(HashTableType& collection)

   350     {

   351         typedef typename HashTableType::const_iterator iterator;

   352         iterator end = collection.end();

   353         for (iterator it = collection.begin(); it != end; ++it)

   354             delete it->second;

   355     }

   356 

   357     template<typename T, typename U, typename V, typename W, typename X>

   358     inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)

   359     {

   360         deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);

   361     }

   362 

   363     template<typename KeyType, typename HashTableType>

   364     void deleteAllPairFirsts(HashTableType& collection)

   365     {

   366         typedef typename HashTableType::const_iterator iterator;

   367         iterator end = collection.end();

   368         for (iterator it = collection.begin(); it != end; ++it)

   369             delete it->first;

   370     }

   371 

   372     template<typename T, typename U, typename V, typename W, typename X>

   373     inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)

   374     {

   375         deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection);

   376     }

   377     

   378     template<typename T, typename U, typename V, typename W, typename X, typename Y>

   379     inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)

   380     {

   381         typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator;

   382         

   383         vector.resize(collection.size());

   384         

   385         iterator it = collection.begin().keys();

   386         iterator end = collection.end().keys();

   387         for (unsigned i = 0; it != end; ++it, ++i)

   388             vector[i] = *it;

   389     }  

   390 

   391     template<typename T, typename U, typename V, typename W, typename X, typename Y>

   392     inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)

   393     {

   394         typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator;

   395         

   396         vector.resize(collection.size());

   397         

   398         iterator it = collection.begin().values();

   399         iterator end = collection.end().values();

   400         for (unsigned i = 0; it != end; ++it, ++i)

   401             vector[i] = *it;

   402     }   

   403 

   404 } // namespace WTF

   405 

   406 using WTF::HashMap;

   407 

   408 #include "RefPtrHashMap.h"

   409 

   410 #endif /* WTF_HashMap_h */