Source/WTF/wtf/HashMap.h

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