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 namespace WTF {

    22 

    23     // This specialization is a direct copy of HashMap, with overloaded functions

    24     // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.

    25     

    26     // FIXME: Find a better way that doesn't require an entire copy of the HashMap template.

    27     

    28     template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions>

    29     struct RefPtrHashMapRawKeyTranslator {

    30         typedef typename ValueType::first_type KeyType;

    31         typedef typename ValueType::second_type MappedType;

    32         typedef typename ValueTraits::FirstTraits KeyTraits;

    33         typedef typename ValueTraits::SecondTraits MappedTraits;

    34 

    35         static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); }

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

    37         static void translate(ValueType& location, RawKeyType key, const MappedType& mapped)

    38         {

    39             location.first = key;

    40             location.second = mapped;

    41         }

    42     };

    43 

    44     template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>

    45     class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> : public FastAllocBase {

    46     private:

    47         typedef KeyTraitsArg KeyTraits;

    48         typedef MappedTraitsArg MappedTraits;

    49         typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;

    50 

    51     public:

    52         typedef typename KeyTraits::TraitType KeyType;

    53         typedef T* RawKeyType;

    54         typedef typename MappedTraits::TraitType MappedType;

    55         typedef typename ValueTraits::TraitType ValueType;

    56 

    57     private:

    58         typedef HashArg HashFunctions;

    59 

    60         typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>,

    61             HashFunctions, ValueTraits, KeyTraits> HashTableType;

    62 

    63         typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions>

    64             RawKeyTranslator;

    65 

    66     public:

    67         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;

    68         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;

    69 

    70         void swap(HashMap&);

    71 

    72         int size() const;

    73         int capacity() const;

    74         bool isEmpty() const;

    75 

    76         // iterators iterate over pairs of keys and values

    77         iterator begin();

    78         iterator end();

    79         const_iterator begin() const;

    80         const_iterator end() const;

    81 

    82         iterator find(const KeyType&);

    83         iterator find(RawKeyType);

    84         const_iterator find(const KeyType&) const;

    85         const_iterator find(RawKeyType) const;

    86         bool contains(const KeyType&) const;

    87         bool contains(RawKeyType) const;

    88         MappedType get(const KeyType&) const;

    89         MappedType get(RawKeyType) const;

    90         MappedType inlineGet(RawKeyType) const;

    91 

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

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

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

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

    96         pair<iterator, bool> set(RawKeyType, const MappedType&); 

    97 

    98         // does nothing if key is already present

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

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

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

   102         pair<iterator, bool> add(RawKeyType, const MappedType&); 

   103 

   104         void remove(const KeyType&);

   105         void remove(RawKeyType);

   106         void remove(iterator);

   107         void clear();

   108 

   109         MappedType take(const KeyType&); // efficient combination of get with remove

   110         MappedType take(RawKeyType); // efficient combination of get with remove

   111 

   112     private:

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

   114         pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);

   115 

   116         HashTableType m_impl;

   117     };

   118     

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

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

   121     {

   122         m_impl.swap(other.m_impl); 

   123     }

   124 

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

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

   127     {

   128         return m_impl.size(); 

   129     }

   130 

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

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

   133     { 

   134         return m_impl.capacity(); 

   135     }

   136 

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

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

   139     {

   140         return m_impl.isEmpty();

   141     }

   142 

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

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

   145     {

   146         return m_impl.begin();

   147     }

   148 

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

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

   151     {

   152         return m_impl.end();

   153     }

   154 

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

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

   157     {

   158         return m_impl.begin();

   159     }

   160 

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

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

   163     {

   164         return m_impl.end();

   165     }

   166 

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

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

   169     {

   170         return m_impl.find(key);

   171     }

   172 

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

   174     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)

   175     {

   176         return m_impl.template find<RawKeyType, RawKeyTranslator>(key);

   177     }

   178 

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

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

   181     {

   182         return m_impl.find(key);

   183     }

   184 

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

   186     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const

   187     {

   188         return m_impl.template find<RawKeyType, RawKeyTranslator>(key);

   189     }

   190 

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

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

   193     {

   194         return m_impl.contains(key);

   195     }

   196 

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

   198     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const

   199     {

   200         return m_impl.template contains<RawKeyType, RawKeyTranslator>(key);

   201     }

   202 

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

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

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

   206     {

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

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

   209     }

   210 

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

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

   213     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) 

   214     {

   215         return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped);

   216     }

   217 

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

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

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

   221     {

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

   223         if (!result.second) {

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

   225             result.first->second = mapped;

   226         }

   227         return result;

   228     }

   229 

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

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

   232     HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) 

   233     {

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

   235         if (!result.second) {

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

   237             result.first->second = mapped;

   238         }

   239         return result;

   240     }

   241 

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

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

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

   245     {

   246         return inlineAdd(key, mapped);

   247     }

   248 

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

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

   251     HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)

   252     {

   253         return inlineAdd(key, mapped);

   254     }

   255 

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

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

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

   259     {

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

   261         if (!entry)

   262             return MappedTraits::emptyValue();

   263         return entry->second;

   264     }

   265 

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

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

   268     inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const

   269     {

   270         ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key);

   271         if (!entry)

   272             return MappedTraits::emptyValue();

   273         return entry->second;

   274     }

   275 

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

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

   278     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const

   279     {

   280         return inlineGet(key);

   281     }

   282 

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

   284     inline void HashMap<RefPtr<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<RefPtr<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<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)

   300     {

   301         remove(find(key));

   302     }

   303 

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

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

   306     {

   307         m_impl.clear();

   308     }

   309 

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

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

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

   313     {

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

   315         iterator it = find(key);

   316         if (it == end())

   317             return MappedTraits::emptyValue();

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

   319         remove(it);

   320         return result;

   321     }

   322 

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

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

   325     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)

   326     {

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

   328         iterator it = find(key);

   329         if (it == end())

   330             return MappedTraits::emptyValue();

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

   332         remove(it);

   333         return result;

   334     }

   335 

   336 } // namespace WTF