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