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