third_party/WebKit/Source/wtf/HashMap.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 WTF_HashMap_h
  22 #define WTF_HashMap_h
  23
  24 #include "wtf/DefaultAllocator.h"
  25 #include "wtf/HashTable.h"
  26
  27 namespace WTF {
  28
  29     template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits;
  30
  31     template<typename T> struct ReferenceTypeMaker {
  32         typedef T& ReferenceType;
  33     };
  34     template<typename T> struct ReferenceTypeMaker<T&> {
  35         typedef T& ReferenceType;
  36     };
  37
  38     struct KeyValuePairKeyExtractor {
  39         template<typename T>
  40         static const typename T::KeyType& extract(const T& p) { return p.key; }
  41     };
  42
  43     // Note: empty or deleted key values are not allowed, using them may lead to undefined behavior.
  44     // For pointer keys this means that null pointers are not allowed unless you supply custom key traits.
  45     template<
  46         typename KeyArg,
  47         typename MappedArg,
  48         typename HashArg = typename DefaultHash<KeyArg>::Hash,
  49         typename KeyTraitsArg = HashTraits<KeyArg>,
  50         typename MappedTraitsArg = HashTraits<MappedArg>,
  51         typename Allocator = DefaultAllocator>
  52     class HashMap {
  53         WTF_USE_ALLOCATOR(HashMap, Allocator);
  54     private:
  55         typedef KeyTraitsArg KeyTraits;
  56         typedef MappedTraitsArg MappedTraits;
  57         typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits;
  58
  59     public:
  60         typedef typename KeyTraits::TraitType KeyType;
  61         typedef const typename KeyTraits::PeekInType& KeyPeekInType;
  62         typedef typename MappedTraits::TraitType MappedType;
  63         typedef typename ValueTraits::TraitType ValueType;
  64
  65     private:
  66         typedef typename MappedTraits::PassInType MappedPassInType;
  67         typedef typename MappedTraits::PassOutType MappedPassOutType;
  68         typedef typename MappedTraits::PeekOutType MappedPeekType;
  69
  70         typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType;
  71
  72         typedef HashArg HashFunctions;
  73
  74         typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor,
  75             HashFunctions, ValueTraits, KeyTraits, Allocator> HashTableType;
  76
  77         class HashMapKeysProxy;
  78         class HashMapValuesProxy;
  79
  80     public:
  81         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
  82         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
  83         typedef typename HashTableType::AddResult AddResult;
  84
  85     public:
  86         void swap(HashMap& ref)
  87         {
  88             m_impl.swap(ref.m_impl);
  89         }
  90
  91         void swap(typename Allocator::template OtherType<HashMap>::Type other)
  92         {
  93             HashMap& ref = Allocator::getOther(other);
  94             m_impl.swap(ref.m_impl);
  95         }
  96
  97         unsigned size() const;
  98         unsigned capacity() const;
  99         bool isEmpty() const;
 100
 101         // iterators iterate over pairs of keys and values
 102         iterator begin();
 103         iterator end();
 104         const_iterator begin() const;
 105         const_iterator end() const;
 106
 107         HashMapKeysProxy& keys() { return static_cast<HashMapKeysProxy&>(*this); }
 108         const HashMapKeysProxy& keys() const { return static_cast<const HashMapKeysProxy&>(*this); }
 109
 110         HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*this); }
 111         const HashMapValuesProxy& values() const { return static_cast<const HashMapValuesProxy&>(*this); }
 112
 113         iterator find(KeyPeekInType);
 114         const_iterator find(KeyPeekInType) const;
 115         bool contains(KeyPeekInType) const;
 116         MappedPeekType get(KeyPeekInType) const;
 117
 118         // replaces value but not key if key is already present
 119         // return value is a pair of the iterator to the key location,
 120         // and a boolean that's true if a new value was actually added
 121         AddResult set(KeyPeekInType, MappedPassInType);
 122
 123         // does nothing if key is already present
 124         // return value is a pair of the iterator to the key location,
 125         // and a boolean that's true if a new value was actually added
 126         AddResult add(KeyPeekInType, MappedPassInType);
 127
 128         void remove(KeyPeekInType);
 129         void remove(iterator);
 130         void clear();
 131         template<typename Collection>
 132         void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, toBeRemoved); }
 133
 134         MappedPassOutType take(KeyPeekInType); // efficient combination of get with remove
 135
 136         // An alternate version of find() that finds the object by hashing and comparing
 137         // with some other type, to avoid the cost of type conversion. HashTranslator
 138         // must have the following function members:
 139         //   static unsigned hash(const T&);
 140         //   static bool equal(const ValueType&, const T&);
 141         template<typename HashTranslator, typename T> iterator find(const T&);
 142         template<typename HashTranslator, typename T> const_iterator find(const T&) const;
 143         template<typename HashTranslator, typename T> bool contains(const T&) const;
 144
 145         // An alternate version of add() that finds the object by hashing and comparing
 146         // with some other type, to avoid the cost of type conversion if the object is already
 147         // in the table. HashTranslator must have the following function members:
 148         //   static unsigned hash(const T&);
 149         //   static bool equal(const ValueType&, const T&);
 150         //   static translate(ValueType&, const T&, unsigned hashCode);
 151         template<typename HashTranslator, typename T> AddResult add(const T&, MappedPassInType);
 152
 153         static bool isValidKey(KeyPeekInType);
 154
 155         template<typename VisitorDispatcher>
 156         void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); }
 157
 158     private:
 159         AddResult inlineAdd(KeyPeekInType, MappedPassInReferenceType);
 160
 161         HashTableType m_impl;
 162     };
 163
 164     template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg, typename Allocator>
 165     class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMapKeysProxy :
 166         private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> {
 167         public:
 168             typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> HashMapType;
 169             typedef typename HashMapType::iterator::Keys iterator;
 170             typedef typename HashMapType::const_iterator::Keys const_iterator;
 171
 172             iterator begin()
 173             {
 174                 return HashMapType::begin().keys();
 175             }
 176
 177             iterator end()
 178             {
 179                 return HashMapType::end().keys();
 180             }
 181
 182             const_iterator begin() const
 183             {
 184                 return HashMapType::begin().keys();
 185             }
 186
 187             const_iterator end() const
 188             {
 189                 return HashMapType::end().keys();
 190             }
 191
 192         private:
 193             friend class HashMap;
 194
 195             // These are intentionally not implemented.
 196             HashMapKeysProxy();
 197             HashMapKeysProxy(const HashMapKeysProxy&);
 198             HashMapKeysProxy& operator=(const HashMapKeysProxy&);
 199             ~HashMapKeysProxy();
 200     };
 201
 202     template<typename KeyArg, typename MappedArg, typename HashArg,  typename KeyTraitsArg, typename MappedTraitsArg, typename Allocator>
 203     class HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator>::HashMapValuesProxy :
 204         private HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> {
 205         public:
 206             typedef HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg, Allocator> HashMapType;
 207             typedef typename HashMapType::iterator::Values iterator;
 208             typedef typename HashMapType::const_iterator::Values const_iterator;
 209
 210             iterator begin()
 211             {
 212                 return HashMapType::begin().values();
 213             }
 214
 215             iterator end()
 216             {
 217                 return HashMapType::end().values();
 218             }
 219
 220             const_iterator begin() const
 221             {
 222                 return HashMapType::begin().values();
 223             }
 224
 225             const_iterator end() const
 226             {
 227                 return HashMapType::end().values();
 228             }
 229
 230         private:
 231             friend class HashMap;
 232
 233             // These are intentionally not implemented.
 234             HashMapValuesProxy();
 235             HashMapValuesProxy(const HashMapValuesProxy&);
 236             HashMapValuesProxy& operator=(const HashMapValuesProxy&);
 237             ~HashMapValuesProxy();
 238     };
 239
 240     template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits : KeyValuePairHashTraits<KeyTraits, MappedTraits> {
 241         static const bool hasIsEmptyValueFunction = true;
 242         static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits, MappedTraits>::TraitType& value)
 243         {
 244             return isHashTraitsEmptyValue<KeyTraits>(value.key);
 245         }
 246     };
 247
 248     template<typename ValueTraits, typename HashFunctions>
 249     struct HashMapTranslator {
 250         template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
 251         template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
 252         template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped)
 253         {
 254             location.key = key;
 255             ValueTraits::ValueTraits::store(mapped, location.value);
 256         }
 257     };
 258
 259     template<typename ValueTraits, typename Translator>
 260     struct HashMapTranslatorAdapter {
 261         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
 262         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
 263         template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped, unsigned hashCode)
 264         {
 265             Translator::translate(location.key, key, hashCode);
 266             ValueTraits::ValueTraits::store(mapped, location.value);
 267         }
 268     };
 269
 270     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 271     inline unsigned HashMap<T, U, V, W, X, Y>::size() const
 272     {
 273         return m_impl.size();
 274     }
 275
 276     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 277     inline unsigned HashMap<T, U, V, W, X, Y>::capacity() const
 278     {
 279         return m_impl.capacity();
 280     }
 281
 282     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 283     inline bool HashMap<T, U, V, W, X, Y>::isEmpty() const
 284     {
 285         return m_impl.isEmpty();
 286     }
 287
 288     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 289     inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::begin()
 290     {
 291         return m_impl.begin();
 292     }
 293
 294     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 295     inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::end()
 296     {
 297         return m_impl.end();
 298     }
 299
 300     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 301     inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::begin() const
 302     {
 303         return m_impl.begin();
 304     }
 305
 306     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 307     inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::end() const
 308     {
 309         return m_impl.end();
 310     }
 311
 312     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 313     inline typename HashMap<T, U, V, W, X, Y>::iterator HashMap<T, U, V, W, X, Y>::find(KeyPeekInType key)
 314     {
 315         return m_impl.find(key);
 316     }
 317
 318     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 319     inline typename HashMap<T, U, V, W, X, Y>::const_iterator HashMap<T, U, V, W, X, Y>::find(KeyPeekInType key) const
 320     {
 321         return m_impl.find(key);
 322     }
 323
 324     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 325     inline bool HashMap<T, U, V, W, X, Y>::contains(KeyPeekInType key) const
 326     {
 327         return m_impl.contains(key);
 328     }
 329
 330     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 331     template<typename HashTranslator, typename TYPE>
 332     inline typename HashMap<T, U, V, W, X, Y>::iterator
 333     HashMap<T, U, V, W, X, Y>::find(const TYPE& value)
 334     {
 335         return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator>>(value);
 336     }
 337
 338     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 339     template<typename HashTranslator, typename TYPE>
 340     inline typename HashMap<T, U, V, W, X, Y>::const_iterator
 341     HashMap<T, U, V, W, X, Y>::find(const TYPE& value) const
 342     {
 343         return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator>>(value);
 344     }
 345
 346     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 347     template<typename HashTranslator, typename TYPE>
 348     inline bool
 349     HashMap<T, U, V, W, X, Y>::contains(const TYPE& value) const
 350     {
 351         return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, HashTranslator>>(value);
 352     }
 353
 354     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 355     typename HashMap<T, U, V, W, X, Y>::AddResult
 356     HashMap<T, U, V, W, X, Y>::inlineAdd(KeyPeekInType key, MappedPassInReferenceType mapped)
 357     {
 358         return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions>>(key, mapped);
 359     }
 360
 361     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 362     typename HashMap<T, U, V, W, X, Y>::AddResult
 363     HashMap<T, U, V, W, X, Y>::set(KeyPeekInType key, MappedPassInType mapped)
 364     {
 365         AddResult result = inlineAdd(key, mapped);
 366         if (!result.isNewEntry) {
 367             // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
 368             MappedTraits::store(mapped, result.storedValue->value);
 369         }
 370         return result;
 371     }
 372
 373     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 374     template<typename HashTranslator, typename TYPE>
 375     typename HashMap<T, U, V, W, X, Y>::AddResult
 376     HashMap<T, U, V, W, X, Y>::add(const TYPE& key, MappedPassInType value)
 377     {
 378         return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<ValueTraits, HashTranslator>>(key, value);
 379     }
 380
 381     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 382     typename HashMap<T, U, V, W, X, Y>::AddResult
 383     HashMap<T, U, V, W, X, Y>::add(KeyPeekInType key, MappedPassInType mapped)
 384     {
 385         return inlineAdd(key, mapped);
 386     }
 387
 388     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 389     typename HashMap<T, U, V, W, X, Y>::MappedPeekType
 390     HashMap<T, U, V, W, X, Y>::get(KeyPeekInType key) const
 391     {
 392         ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
 393         if (!entry)
 394             return MappedTraits::peek(MappedTraits::emptyValue());
 395         return MappedTraits::peek(entry->value);
 396     }
 397
 398     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 399     inline void HashMap<T, U, V, W, X, Y>::remove(iterator it)
 400     {
 401         m_impl.remove(it.m_impl);
 402     }
 403
 404     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 405     inline void HashMap<T, U, V, W, X, Y>::remove(KeyPeekInType key)
 406     {
 407         remove(find(key));
 408     }
 409
 410     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 411     inline void HashMap<T, U, V, W, X, Y>::clear()
 412     {
 413         m_impl.clear();
 414     }
 415
 416     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 417     typename HashMap<T, U, V, W, X, Y>::MappedPassOutType
 418     HashMap<T, U, V, W, X, Y>::take(KeyPeekInType key)
 419     {
 420         iterator it = find(key);
 421         if (it == end())
 422             return MappedTraits::passOut(MappedTraits::emptyValue());
 423         MappedPassOutType result = MappedTraits::passOut(it->value);
 424         remove(it);
 425         return result;
 426     }
 427
 428     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 429     inline bool HashMap<T, U, V, W, X, Y>::isValidKey(KeyPeekInType key)
 430     {
 431         if (KeyTraits::isDeletedValue(key))
 432             return false;
 433
 434         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 435             if (key == KeyTraits::emptyValue())
 436                 return false;
 437         } else {
 438             if (isHashTraitsEmptyValue<KeyTraits>(key))
 439                 return false;
 440         }
 441
 442         return true;
 443     }
 444
 445     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 446     bool operator==(const HashMap<T, U, V, W, X, Y>& a, const HashMap<T, U, V, W, X, Y>& b)
 447     {
 448         if (a.size() != b.size())
 449             return false;
 450
 451         typedef typename HashMap<T, U, V, W, X, Y>::const_iterator const_iterator;
 452
 453         const_iterator aEnd = a.end();
 454         const_iterator bEnd = b.end();
 455         for (const_iterator it = a.begin(); it != aEnd; ++it) {
 456             const_iterator bPos = b.find(it->key);
 457             if (bPos == bEnd || it->value != bPos->value)
 458                 return false;
 459         }
 460
 461         return true;
 462     }
 463
 464     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 465     inline bool operator!=(const HashMap<T, U, V, W, X, Y>& a, const HashMap<T, U, V, W, X, Y>& b)
 466     {
 467         return !(a == b);
 468     }
 469
 470     template<typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
 471     inline void copyKeysToVector(const HashMap<T, U, V, W, X, Y>& collection, Z& vector)
 472     {
 473         typedef typename HashMap<T, U, V, W, X, Y>::const_iterator::Keys iterator;
 474
 475         vector.resize(collection.size());
 476
 477         iterator it = collection.begin().keys();
 478         iterator end = collection.end().keys();
 479         for (unsigned i = 0; it != end; ++it, ++i)
 480             vector[i] = *it;
 481     }
 482
 483     template<typename T, typename U, typename V, typename W, typename X, typename Y, typename Z>
 484     inline void copyValuesToVector(const HashMap<T, U, V, W, X, Y>& collection, Z& vector)
 485     {
 486         typedef typename HashMap<T, U, V, W, X, Y>::const_iterator::Values iterator;
 487
 488         vector.resize(collection.size());
 489
 490         iterator it = collection.begin().values();
 491         iterator end = collection.end().values();
 492         for (unsigned i = 0; it != end; ++it, ++i)
 493             vector[i] = *it;
 494     }
 495
 496 #if !ENABLE(OILPAN)
 497 template<typename T, typename U, typename V, typename W, typename X>
 498 struct NeedsTracing<HashMap<T, U, V, W, X>> {
 499     static const bool value = false;
 500 };
 501 #endif
 502
 503 } // namespace WTF
 504
 505 using WTF::HashMap;
 506
 507 #endif /* WTF_HashMap_h */