Source/WTF/wtf/RefPtrHashMap.h

   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 RefPtrHashMap_h
  22 #define RefPtrHashMap_h
  23
  24 namespace WTF {
  25
  26     // This specialization is a copy of HashMap for use with RefPtr keys, with overloaded functions
  27     // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
  28
  29      // FIXME: Find a way to do this with traits that doesn't require a copy of the HashMap template.
  30
  31     template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
  32     class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
  33         WTF_MAKE_FAST_ALLOCATED;
  34     private:
  35         typedef KeyTraitsArg KeyTraits;
  36         typedef MappedTraitsArg MappedTraits;
  37         typedef KeyValuePairHashTraits<KeyTraits, MappedTraits> ValueTraits;
  38
  39     public:
  40         typedef typename KeyTraits::TraitType KeyType;
  41         typedef T* RawKeyType;
  42         typedef typename MappedTraits::TraitType MappedType;
  43         typedef typename ValueTraits::TraitType ValueType;
  44
  45     private:
  46         typedef typename MappedTraits::PassInType MappedPassInType;
  47         typedef typename MappedTraits::PassOutType MappedPassOutType;
  48         typedef typename MappedTraits::PeekType MappedPeekType;
  49
  50         typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType;
  51
  52         typedef HashArg HashFunctions;
  53
  54         typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType>,
  55             HashFunctions, ValueTraits, KeyTraits> HashTableType;
  56
  57         typedef HashMapTranslator<ValueTraits, HashFunctions>
  58             Translator;
  59
  60     public:
  61         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
  62         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
  63         typedef typename HashTableType::AddResult AddResult;
  64
  65         void swap(HashMap&);
  66
  67         int size() const;
  68         int capacity() const;
  69         bool isEmpty() const;
  70
  71         // iterators iterate over pairs of keys and values
  72         iterator begin();
  73         iterator end();
  74         const_iterator begin() const;
  75         const_iterator end() const;
  76
  77         iterator find(const KeyType&);
  78         iterator find(RawKeyType);
  79         const_iterator find(const KeyType&) const;
  80         const_iterator find(RawKeyType) const;
  81         bool contains(const KeyType&) const;
  82         bool contains(RawKeyType) const;
  83         MappedPeekType get(const KeyType&) const;
  84         MappedPeekType get(RawKeyType) const;
  85         MappedPeekType inlineGet(RawKeyType) const;
  86
  87         // replaces value but not key if key is already present
  88         // return value is a pair of the iterator to the key location,
  89         // and a boolean that's true if a new value was actually added
  90         AddResult set(const KeyType&, MappedPassInType);
  91         AddResult set(RawKeyType, MappedPassInType);
  92
  93         // does nothing if key is already present
  94         // return value is a pair of the iterator to the key location,
  95         // and a boolean that's true if a new value was actually added
  96         AddResult add(const KeyType&, MappedPassInType);
  97         AddResult add(RawKeyType, MappedPassInType);
  98
  99         void remove(const KeyType&);
 100         void remove(RawKeyType);
 101         void remove(iterator);
 102         void clear();
 103
 104         MappedPassOutType take(const KeyType&); // efficient combination of get with remove
 105         MappedPassOutType take(RawKeyType); // efficient combination of get with remove
 106
 107     private:
 108         AddResult inlineAdd(const KeyType&, MappedPassInReferenceType);
 109         AddResult inlineAdd(RawKeyType, MappedPassInReferenceType);
 110
 111         HashTableType m_impl;
 112     };
 113
 114     template<typename T, typename U, typename V, typename W, typename X>
 115     inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other)
 116     {
 117         m_impl.swap(other.m_impl);
 118     }
 119
 120     template<typename T, typename U, typename V, typename W, typename X>
 121     inline int HashMap<RefPtr<T>, U, V, W, X>::size() const
 122     {
 123         return m_impl.size();
 124     }
 125
 126     template<typename T, typename U, typename V, typename W, typename X>
 127     inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const
 128     {
 129         return m_impl.capacity();
 130     }
 131
 132     template<typename T, typename U, typename V, typename W, typename X>
 133     inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const
 134     {
 135         return m_impl.isEmpty();
 136     }
 137
 138     template<typename T, typename U, typename V, typename W, typename X>
 139     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin()
 140     {
 141         return m_impl.begin();
 142     }
 143
 144     template<typename T, typename U, typename V, typename W, typename X>
 145     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end()
 146     {
 147         return m_impl.end();
 148     }
 149
 150     template<typename T, typename U, typename V, typename W, typename X>
 151     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const
 152     {
 153         return m_impl.begin();
 154     }
 155
 156     template<typename T, typename U, typename V, typename W, typename X>
 157     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const
 158     {
 159         return m_impl.end();
 160     }
 161
 162     template<typename T, typename U, typename V, typename W, typename X>
 163     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key)
 164     {
 165         return m_impl.find(key);
 166     }
 167
 168     template<typename T, typename U, typename V, typename W, typename X>
 169     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
 170     {
 171         return m_impl.template find<Translator>(key);
 172     }
 173
 174     template<typename T, typename U, typename V, typename W, typename X>
 175     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const
 176     {
 177         return m_impl.find(key);
 178     }
 179
 180     template<typename T, typename U, typename V, typename W, typename X>
 181     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
 182     {
 183         return m_impl.template find<Translator>(key);
 184     }
 185
 186     template<typename T, typename U, typename V, typename W, typename X>
 187     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const
 188     {
 189         return m_impl.contains(key);
 190     }
 191
 192     template<typename T, typename U, typename V, typename W, typename X>
 193     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
 194     {
 195         return m_impl.template contains<Translator>(key);
 196     }
 197
 198     template<typename T, typename U, typename V, typename W, typename X>
 199     inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult
 200     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceType mapped)
 201     {
 202         return m_impl.template add<Translator>(key, mapped);
 203     }
 204
 205     template<typename T, typename U, typename V, typename W, typename X>
 206     inline typename HashMap<RefPtr<T>, U, V, W, X>::AddResult
 207     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, MappedPassInReferenceType mapped)
 208     {
 209         return m_impl.template add<Translator>(key, mapped);
 210     }
 211
 212     template<typename T, typename U, typename V, typename W, typename X>
 213     typename HashMap<RefPtr<T>, U, V, W, X>::AddResult
 214     HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped)
 215     {
 216         AddResult result = inlineAdd(key, mapped);
 217         if (!result.isNewEntry) {
 218             // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
 219             MappedTraits::store(mapped, result.iterator->second);
 220         }
 221         return result;
 222     }
 223
 224     template<typename T, typename U, typename V, typename W, typename X>
 225     typename HashMap<RefPtr<T>, U, V, W, X>::AddResult
 226     HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, MappedPassInType mapped)
 227     {
 228         AddResult result = inlineAdd(key, mapped);
 229         if (!result.isNewEntry) {
 230             // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
 231             MappedTraits::store(mapped, result.iterator->second);
 232         }
 233         return result;
 234     }
 235
 236     template<typename T, typename U, typename V, typename W, typename X>
 237     typename HashMap<RefPtr<T>, U, V, W, X>::AddResult
 238     HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, MappedPassInType mapped)
 239     {
 240         return inlineAdd(key, mapped);
 241     }
 242
 243     template<typename T, typename U, typename V, typename W, typename X>
 244     typename HashMap<RefPtr<T>, U, V, W, X>::AddResult
 245     HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, MappedPassInType mapped)
 246     {
 247         return inlineAdd(key, mapped);
 248     }
 249
 250     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 251     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType
 252     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
 253     {
 254         ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
 255         if (!entry)
 256             return MappedTraits::peek(MappedTraits::emptyValue());
 257         return MappedTraits::peek(entry->second);
 258     }
 259
 260     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 261     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType
 262     inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const
 263     {
 264         ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<Translator>(key);
 265         if (!entry)
 266             return MappedTraits::peek(MappedTraits::emptyValue());
 267         return MappedTraits::peek(entry->second);
 268     }
 269
 270     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 271     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPeekType
 272     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
 273     {
 274         return inlineGet(key);
 275     }
 276
 277     template<typename T, typename U, typename V, typename W, typename X>
 278     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
 279     {
 280         if (it.m_impl == m_impl.end())
 281             return;
 282         m_impl.internalCheckTableConsistency();
 283         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
 284     }
 285
 286     template<typename T, typename U, typename V, typename W, typename X>
 287     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
 288     {
 289         remove(find(key));
 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(RawKeyType 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>::clear()
 300     {
 301         m_impl.clear();
 302     }
 303
 304     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 305     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType
 306     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
 307     {
 308         iterator it = find(key);
 309         if (it == end())
 310             return MappedTraits::passOut(MappedTraits::emptyValue());
 311         MappedPassOutType result = MappedTraits::passOut(it->second);
 312         remove(it);
 313         return result;
 314     }
 315
 316     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 317     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedPassOutType
 318     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
 319     {
 320         iterator it = find(key);
 321         if (it == end())
 322             return MappedTraits::passOut(MappedTraits::emptyValue());
 323         MappedPassOutType result = MappedTraits::passOut(it->second);
 324         remove(it);
 325         return result;
 326     }
 327
 328 } // namespace WTF
 329
 330 #endif // RefPtrHashMap_h