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 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