wtf/RefPtrHashMap.h

   1 // -*- mode: c++; c-basic-offset: 4 -*-
   2 /*
   3  * Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Library General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public License
  16  * along with this library; see the file COPYING.LIB.  If not, write to
  17  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18  * Boston, MA 02110-1301, USA.
  19  *
  20  */
  21
  22 namespace WTF {
  23
  24     // This specialization is a direct copy of HashMap, with overloaded functions
  25     // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
  26
  27     // FIXME: Is there a better way to do this that doesn't just copy HashMap?
  28
  29     template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
  30     class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
  31     private:
  32         typedef KeyTraitsArg KeyTraits;
  33         typedef MappedTraitsArg MappedTraits;
  34         typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
  35
  36     public:
  37         typedef typename KeyTraits::TraitType KeyType;
  38         typedef T* RawKeyType;
  39         typedef typename MappedTraits::TraitType MappedType;
  40         typedef typename ValueTraits::TraitType ValueType;
  41
  42     private:
  43         typedef HashArg HashFunctions;
  44
  45         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
  46
  47         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
  48         typedef typename MappedTraits::StorageTraits MappedStorageTraits;
  49         typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
  50
  51         typedef typename KeyStorageTraits::TraitType KeyStorageType;
  52         typedef typename MappedStorageTraits::TraitType MappedStorageType;
  53         typedef typename ValueStorageTraits::TraitType ValueStorageType;
  54
  55         typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
  56             StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
  57
  58     public:
  59         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
  60         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
  61
  62         HashMap();
  63         HashMap(const HashMap&);
  64         HashMap& operator=(const HashMap&);
  65         ~HashMap();
  66
  67         void swap(HashMap&);
  68
  69         int size() const;
  70         int capacity() const;
  71         bool isEmpty() const;
  72
  73         // iterators iterate over pairs of keys and values
  74         iterator begin();
  75         iterator end();
  76         const_iterator begin() const;
  77         const_iterator end() const;
  78
  79         iterator find(const KeyType&);
  80         iterator find(RawKeyType);
  81         const_iterator find(const KeyType&) const;
  82         const_iterator find(RawKeyType) const;
  83         bool contains(const KeyType&) const;
  84         bool contains(RawKeyType) const;
  85         MappedType get(const KeyType&) const;
  86         MappedType get(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         pair<iterator, bool> set(const KeyType&, const MappedType&);
  92         pair<iterator, bool> set(RawKeyType, const MappedType&);
  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         pair<iterator, bool> add(const KeyType&, const MappedType&);
  98         pair<iterator, bool> add(RawKeyType, const MappedType&);
  99
 100         void remove(const KeyType&);
 101         void remove(RawKeyType);
 102         void remove(iterator);
 103         void clear();
 104
 105         MappedType take(const KeyType&); // efficient combination of get with remove
 106         MappedType take(RawKeyType); // efficient combination of get with remove
 107
 108     private:
 109         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
 110         pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);
 111         void refAll();
 112         void derefAll();
 113
 114         HashTableType m_impl;
 115     };
 116
 117     template<typename T, typename U, typename V, typename W, typename X>
 118     inline void HashMap<RefPtr<T>, U, V, W, X>::refAll()
 119     {
 120         HashTableRefCounter<HashTableType, ValueTraits>::refAll(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>::derefAll()
 125     {
 126         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
 127     }
 128
 129     template<typename T, typename U, typename V, typename W, typename X>
 130     inline HashMap<RefPtr<T>, U, V, W, X>::HashMap()
 131     {
 132     }
 133
 134     template<typename T, typename U, typename V, typename W, typename X>
 135     inline HashMap<RefPtr<T>, U, V, W, X>::HashMap(const HashMap& other)
 136         : m_impl(other.m_impl)
 137     {
 138         refAll();
 139     }
 140
 141     template<typename T, typename U, typename V, typename W, typename X>
 142     inline HashMap<RefPtr<T>, U, V, W, X>& HashMap<RefPtr<T>, U, V, W, X>::operator=(const HashMap& other)
 143     {
 144         HashMap tmp(other);
 145         swap(tmp);
 146         return *this;
 147     }
 148
 149     template<typename T, typename U, typename V, typename W, typename X>
 150     inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other)
 151     {
 152         m_impl.swap(other.m_impl);
 153     }
 154
 155     template<typename T, typename U, typename V, typename W, typename X>
 156     inline HashMap<RefPtr<T>, U, V, W, X>::~HashMap()
 157     {
 158         derefAll();
 159     }
 160
 161     template<typename T, typename U, typename V, typename W, typename X>
 162     inline int HashMap<RefPtr<T>, U, V, W, X>::size() const
 163     {
 164         return m_impl.size();
 165     }
 166
 167     template<typename T, typename U, typename V, typename W, typename X>
 168     inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const
 169     {
 170         return m_impl.capacity();
 171     }
 172
 173     template<typename T, typename U, typename V, typename W, typename X>
 174     inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const
 175     {
 176         return m_impl.isEmpty();
 177     }
 178
 179     template<typename T, typename U, typename V, typename W, typename X>
 180     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin()
 181     {
 182         return m_impl.begin();
 183     }
 184
 185     template<typename T, typename U, typename V, typename W, typename X>
 186     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end()
 187     {
 188         return m_impl.end();
 189     }
 190
 191     template<typename T, typename U, typename V, typename W, typename X>
 192     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const
 193     {
 194         return m_impl.begin();
 195     }
 196
 197     template<typename T, typename U, typename V, typename W, typename X>
 198     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const
 199     {
 200         return m_impl.end();
 201     }
 202
 203     template<typename T, typename U, typename V, typename W, typename X>
 204     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key)
 205     {
 206         return m_impl.find(*(const KeyStorageType*)&key);
 207     }
 208
 209     template<typename T, typename U, typename V, typename W, typename X>
 210     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
 211     {
 212         return m_impl.find(*(const KeyStorageType*)&key);
 213     }
 214
 215     template<typename T, typename U, typename V, typename W, typename X>
 216     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const
 217     {
 218         return m_impl.find(*(const KeyStorageType*)&key);
 219     }
 220
 221     template<typename T, typename U, typename V, typename W, typename X>
 222     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
 223     {
 224         return m_impl.find(*(const KeyStorageType*)&key);
 225     }
 226
 227     template<typename T, typename U, typename V, typename W, typename X>
 228     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const
 229     {
 230         return m_impl.contains(*(const KeyStorageType*)&key);
 231     }
 232
 233     template<typename T, typename U, typename V, typename W, typename X>
 234     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
 235     {
 236         return m_impl.contains(*(const KeyStorageType*)&key);
 237     }
 238
 239     template<typename T, typename U, typename V, typename W, typename X>
 240     inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
 241     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
 242     {
 243         const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
 244         typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;
 245         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
 246     }
 247
 248     template<typename T, typename U, typename V, typename W, typename X>
 249     inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
 250     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped)
 251     {
 252         return inlineAdd(*(const KeyType*)&key, mapped);
 253     }
 254
 255     template<typename T, typename U, typename V, typename W, typename X>
 256     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
 257     HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
 258     {
 259         pair<iterator, bool> result = inlineAdd(key, mapped);
 260         if (!result.second)
 261             // add call above didn't change anything, so set the mapped value
 262             result.first->second = mapped;
 263         return result;
 264     }
 265
 266     template<typename T, typename U, typename V, typename W, typename X>
 267     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
 268     HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped)
 269     {
 270         pair<iterator, bool> result = inlineAdd(key, mapped);
 271         if (!result.second)
 272             // add call above didn't change anything, so set the mapped value
 273             result.first->second = mapped;
 274         return result;
 275     }
 276
 277     template<typename T, typename U, typename V, typename W, typename X>
 278     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
 279     HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
 280     {
 281         return inlineAdd(key, mapped);
 282     }
 283
 284     template<typename T, typename U, typename V, typename W, typename X>
 285     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
 286     HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
 287     {
 288         return inlineAdd(key, mapped);
 289     }
 290
 291     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 292     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
 293     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
 294     {
 295         if (m_impl.isEmpty())
 296             return MappedTraits::emptyValue();
 297         ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
 298         if (!entry)
 299             return MappedTraits::emptyValue();
 300         return ((ValueType *)entry)->second;
 301     }
 302
 303     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 304     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
 305     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
 306     {
 307         if (m_impl.isEmpty())
 308             return MappedTraits::emptyValue();
 309         ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
 310         if (!entry)
 311             return MappedTraits::emptyValue();
 312         return ((ValueType *)entry)->second;
 313     }
 314
 315     template<typename T, typename U, typename V, typename W, typename X>
 316     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
 317     {
 318         if (it.m_impl == m_impl.end())
 319             return;
 320         m_impl.checkTableConsistency();
 321         RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);
 322         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
 323     }
 324
 325     template<typename T, typename U, typename V, typename W, typename X>
 326     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
 327     {
 328         remove(find(key));
 329     }
 330
 331     template<typename T, typename U, typename V, typename W, typename X>
 332     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)
 333     {
 334         remove(find(key));
 335     }
 336
 337     template<typename T, typename U, typename V, typename W, typename X>
 338     inline void HashMap<RefPtr<T>, U, V, W, X>::clear()
 339     {
 340         derefAll();
 341         m_impl.clear();
 342     }
 343
 344     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 345     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
 346     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
 347     {
 348         // This can probably be made more efficient to avoid ref/deref churn.
 349         iterator it = find(key);
 350         if (it == end())
 351             return MappedTraits::emptyValue();
 352         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
 353         remove(it);
 354         return result;
 355     }
 356
 357     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 358     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
 359     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
 360     {
 361         // This can probably be made more efficient to avoid ref/deref churn.
 362         iterator it = find(key);
 363         if (it == end())
 364             return MappedTraits::emptyValue();
 365         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
 366         remove(it);
 367         return result;
 368     }
 369
 370 } // namespace WTF