1 // -*- mode: c++; c-basic-offset: 4 -*-

     2 /*

     3  * This file is part of the KDE libraries

     4  *

     5  * Copyright (C) 2005, 2006 Apple Computer, Inc.

     6  *

     7  * This library is free software; you can redistribute it and/or

     8  * modify it under the terms of the GNU Library General Public

     9  * License as published by the Free Software Foundation; either

    10  * version 2 of the License, or (at your option) any later version.

    11  *

    12  * This library is distributed in the hope that it will be useful,

    13  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    15  * Library General Public License for more details.

    16  *

    17  * You should have received a copy of the GNU Library General Public License

    18  * along with this library; see the file COPYING.LIB.  If not, write to

    19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    20  * Boston, MA 02110-1301, USA.

    21  *

    22  */

    23 

    24 #ifndef WTF_HashMap_h

    25 #define WTF_HashMap_h

    26 

    27 #include "HashTable.h"

    28 #include <wtf/Vector.h>

    29 

    30 namespace WTF {

    31 

    32     template<typename PairType> struct PairFirstExtractor;

    33 

    34     template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,

    35         typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >

    36     class HashMap {

    37     private:

    38         typedef KeyTraitsArg KeyTraits;

    39         typedef MappedTraitsArg MappedTraits;

    40         typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;

    41 

    42     public:

    43         typedef typename KeyTraits::TraitType KeyType;

    44         typedef typename MappedTraits::TraitType MappedType;

    45         typedef typename ValueTraits::TraitType ValueType;

    46 

    47     private:

    48         typedef HashArg HashFunctions;

    49 

    50         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;

    51 

    52         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;

    53         typedef typename MappedTraits::StorageTraits MappedStorageTraits;

    54         typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;

    55 

    56         typedef typename KeyStorageTraits::TraitType KeyStorageType;

    57         typedef typename MappedStorageTraits::TraitType MappedStorageType;

    58         typedef typename ValueStorageTraits::TraitType ValueStorageType;

    59 

    60         typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,

    61             StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;

    62 

    63     public:

    64         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;

    65         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;

    66 

    67         HashMap();

    68         HashMap(const HashMap&);

    69         HashMap& operator=(const HashMap&);

    70         ~HashMap();

    71 

    72         void swap(HashMap&);

    73 

    74         int size() const;

    75         int capacity() const;

    76         bool isEmpty() const;

    77 

    78         // iterators iterate over pairs of keys and values

    79         iterator begin();

    80         iterator end();

    81         const_iterator begin() const;

    82         const_iterator end() const;

    83 

    84         iterator find(const KeyType&);

    85         const_iterator find(const KeyType&) const;

    86         bool contains(const KeyType&) const;

    87         MappedType get(const KeyType&) const;

    88 

    89         // replaces value but not key if key is already present

    90         // return value is a pair of the iterator to the key location, 

    91         // and a boolean that's true if a new value was actually added

    92         pair<iterator, bool> set(const KeyType&, const MappedType&); 

    93 

    94         // does nothing if key is already present

    95         // return value is a pair of the iterator to the key location, 

    96         // and a boolean that's true if a new value was actually added

    97         pair<iterator, bool> add(const KeyType&, const MappedType&); 

    98 

    99         void remove(const KeyType&);

   100         void remove(iterator it);

   101         void clear();

   102 

   103     private:

   104         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);

   105         void refAll();

   106         void derefAll();

   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<bool canReplaceDeletedKey, typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>

   116     struct HashMapTranslator;

   117 

   118     template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>

   119     struct HashMapTranslator<true, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {

   120         typedef typename ValueType::first_type KeyType;

   121         typedef typename ValueType::second_type MappedType;

   122         typedef typename ValueStorageTraits::TraitType ValueStorageType;

   123         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;

   124         typedef typename KeyStorageTraits::TraitType KeyStorageType;

   125         typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;

   126         typedef typename MappedStorageTraits::TraitType MappedStorageType;

   127         typedef typename ValueTraits::FirstTraits KeyTraits;

   128         typedef typename ValueTraits::SecondTraits MappedTraits;

   129 

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

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

   132         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)

   133         {

   134             Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);

   135             Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);

   136         }

   137     };

   138 

   139     template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>

   140     struct HashMapTranslator<false, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {

   141         typedef typename ValueType::first_type KeyType;

   142         typedef typename ValueType::second_type MappedType;

   143         typedef typename ValueStorageTraits::TraitType ValueStorageType;

   144         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;

   145         typedef typename KeyStorageTraits::TraitType KeyStorageType;

   146         typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;

   147         typedef typename MappedStorageTraits::TraitType MappedStorageType;

   148         typedef typename ValueTraits::FirstTraits KeyTraits;

   149         typedef typename ValueTraits::SecondTraits MappedTraits;

   150         

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

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

   153         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)

   154         {

   155             if (location.first == KeyStorageTraits::deletedValue())

   156                 location.first = KeyStorageTraits::emptyValue();

   157             Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);

   158             Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);

   159         }

   160     };

   161 

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

   163     inline void HashMap<T, U, V, W, X>::refAll()

   164     {

   165         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);

   166     }

   167 

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

   169     inline void HashMap<T, U, V, W, X>::derefAll()

   170     {

   171         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);

   172     }

   173 

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

   175     inline HashMap<T, U, V, W, X>::HashMap()

   176     {

   177     }

   178 

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

   180     inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)

   181         : m_impl(other.m_impl)

   182     {

   183         refAll();

   184     }

   185 

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

   187     inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)

   188     {

   189         HashMap tmp(other);

   190         swap(tmp); 

   191         return *this;

   192     }

   193 

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

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

   196     {

   197         m_impl.swap(other.m_impl); 

   198     }

   199 

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

   201     inline HashMap<T, U, V, W, X>::~HashMap()

   202     {

   203         derefAll();

   204     }

   205 

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

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

   208     {

   209         return m_impl.size(); 

   210     }

   211 

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

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

   214     { 

   215         return m_impl.capacity(); 

   216     }

   217 

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

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

   220     {

   221         return m_impl.isEmpty();

   222     }

   223 

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

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

   226     {

   227         return m_impl.begin();

   228     }

   229 

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

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

   232     {

   233         return m_impl.end();

   234     }

   235 

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

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

   238     {

   239         return m_impl.begin();

   240     }

   241 

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

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

   244     {

   245         return m_impl.end();

   246     }

   247 

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

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

   250     {

   251         return m_impl.find(*(const KeyStorageType*)&key);

   252     }

   253 

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

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

   256     {

   257         return m_impl.find(*(const KeyStorageType*)&key);

   258     }

   259 

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

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

   262     {

   263         return m_impl.contains(*(const KeyStorageType*)&key);

   264     }

   265 

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

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

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

   269     {

   270 #ifndef __ARMCC__

   271         const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;

   272         typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;

   273 #else

   274         // armcc compiler

   275         typedef HashMapTranslator< !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;

   276 #endif

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

   278     }

   279 

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

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

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

   283     {

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

   285         if (!result.second)

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

   287             result.first->second = mapped;

   288         return result;

   289     }

   290 

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

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

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

   294     {

   295         return inlineAdd(key, mapped);

   296     }

   297 

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

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

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

   301     {

   302         const_iterator it = find(key);

   303         if (it == end())

   304             return MappedTraits::emptyValue();

   305         return it->second;

   306     }

   307 

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

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

   310     {

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

   312             return;

   313         RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);

   314         m_impl.remove(it.m_impl);

   315     }

   316 

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

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

   319     {

   320         remove(find(key));

   321     }

   322 

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

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

   325     {

   326         derefAll();

   327         m_impl.clear();

   328     }

   329 

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

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

   332     {

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

   334             return false;

   335 

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

   337 

   338         const_iterator end = a.end();

   339         const_iterator notFound = b.end();

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

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

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

   343                 return false;

   344         }

   345 

   346         return true;

   347     }

   348 

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

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

   351     {

   352         return !(a == b);

   353     }

   354 

   355     template<typename MappedType, typename HashTableType>

   356     void deleteAllPairSeconds(HashTableType& collection)

   357     {

   358         typedef typename HashTableType::const_iterator iterator;

   359         iterator end = collection.end();

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

   361             delete *(MappedType*)&it->second;

   362     }

   363 

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

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

   366     {

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

   368     }

   369 

   370     template<typename KeyType, typename HashTableType>

   371     void deleteAllPairFirsts(HashTableType& collection)

   372     {

   373         typedef typename HashTableType::const_iterator iterator;

   374         iterator end = collection.end();

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

   376             delete *(KeyType*)&it->first;

   377     }

   378 

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

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

   381     {

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

   383     }

   384     

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

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

   387     {

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

   389         

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

   391         

   392         iterator it = collection.begin();

   393         iterator end = collection.end();

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

   395             vector[i] = (*it).second;

   396     }   

   397 

   398 } // namespace WTF

   399 

   400 using WTF::HashMap;

   401 

   402 #endif /* WTF_HashMap_h */