wtf/RefPtrHashMap.h

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