wtf/HashMap.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 #ifndef WTF_HashMap_h
  23 #define WTF_HashMap_h
  24
  25 #include "HashTable.h"
  26
  27 namespace WTF {
  28
  29     template<typename PairType> struct PairFirstExtractor;
  30
  31     template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
  32         typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
  33     class HashMap {
  34     private:
  35         typedef KeyTraitsArg KeyTraits;
  36         typedef MappedTraitsArg MappedTraits;
  37         typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
  38
  39     public:
  40         typedef typename KeyTraits::TraitType KeyType;
  41         typedef typename MappedTraits::TraitType MappedType;
  42         typedef typename ValueTraits::TraitType ValueType;
  43
  44     private:
  45         typedef HashArg HashFunctions;
  46
  47         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
  48
  49         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
  50         typedef typename MappedTraits::StorageTraits MappedStorageTraits;
  51         typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
  52
  53         typedef typename KeyStorageTraits::TraitType KeyStorageType;
  54         typedef typename MappedStorageTraits::TraitType MappedStorageType;
  55         typedef typename ValueStorageTraits::TraitType ValueStorageType;
  56
  57         typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
  58             StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
  59
  60     public:
  61         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
  62         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
  63
  64         HashMap();
  65         HashMap(const HashMap&);
  66         HashMap& operator=(const HashMap&);
  67         ~HashMap();
  68
  69         void swap(HashMap&);
  70
  71         int size() const;
  72         int capacity() const;
  73         bool isEmpty() const;
  74
  75         // iterators iterate over pairs of keys and values
  76         iterator begin();
  77         iterator end();
  78         const_iterator begin() const;
  79         const_iterator end() const;
  80
  81         iterator find(const KeyType&);
  82         const_iterator find(const KeyType&) const;
  83         bool contains(const KeyType&) const;
  84         MappedType get(const KeyType&) const;
  85
  86         // replaces value but not key if key is already present
  87         // return value is a pair of the iterator to the key location,
  88         // and a boolean that's true if a new value was actually added
  89         pair<iterator, bool> set(const KeyType&, const MappedType&);
  90
  91         // does nothing if key is already present
  92         // return value is a pair of the iterator to the key location,
  93         // and a boolean that's true if a new value was actually added
  94         pair<iterator, bool> add(const KeyType&, const MappedType&);
  95
  96         void remove(const KeyType&);
  97         void remove(iterator);
  98         void clear();
  99
 100         MappedType take(const KeyType&); // efficient combination of get with remove
 101
 102     private:
 103         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
 104         void refAll();
 105         void derefAll();
 106
 107         HashTableType m_impl;
 108     };
 109
 110     template<typename PairType> struct PairFirstExtractor {
 111         static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
 112     };
 113
 114     template<bool canReplaceDeletedKey, typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
 115     struct HashMapTranslator;
 116
 117     template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
 118     struct HashMapTranslator<true, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {
 119         typedef typename ValueType::first_type KeyType;
 120         typedef typename ValueType::second_type MappedType;
 121         typedef typename ValueStorageTraits::TraitType ValueStorageType;
 122         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
 123         typedef typename KeyStorageTraits::TraitType KeyStorageType;
 124         typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;
 125         typedef typename MappedStorageTraits::TraitType MappedStorageType;
 126         typedef typename ValueTraits::FirstTraits KeyTraits;
 127         typedef typename ValueTraits::SecondTraits MappedTraits;
 128
 129         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
 130         static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
 131         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped)
 132         {
 133             Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
 134             Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);
 135         }
 136     };
 137
 138     template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
 139     struct HashMapTranslator<false, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {
 140         typedef typename ValueType::first_type KeyType;
 141         typedef typename ValueType::second_type MappedType;
 142         typedef typename ValueStorageTraits::TraitType ValueStorageType;
 143         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
 144         typedef typename KeyStorageTraits::TraitType KeyStorageType;
 145         typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;
 146         typedef typename MappedStorageTraits::TraitType MappedStorageType;
 147         typedef typename ValueTraits::FirstTraits KeyTraits;
 148         typedef typename ValueTraits::SecondTraits MappedTraits;
 149
 150         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
 151         static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
 152         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped)
 153         {
 154             if (location.first == KeyStorageTraits::deletedValue())
 155                 location.first = KeyStorageTraits::emptyValue();
 156             Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
 157             Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);
 158         }
 159     };
 160
 161     template<typename T, typename U, typename V, typename W, typename X>
 162     inline void HashMap<T, U, V, W, X>::refAll()
 163     {
 164         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
 165     }
 166
 167     template<typename T, typename U, typename V, typename W, typename X>
 168     inline void HashMap<T, U, V, W, X>::derefAll()
 169     {
 170         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
 171     }
 172
 173     template<typename T, typename U, typename V, typename W, typename X>
 174     inline HashMap<T, U, V, W, X>::HashMap()
 175     {
 176     }
 177
 178     template<typename T, typename U, typename V, typename W, typename X>
 179     inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)
 180         : m_impl(other.m_impl)
 181     {
 182         refAll();
 183     }
 184
 185     template<typename T, typename U, typename V, typename W, typename X>
 186     inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)
 187     {
 188         HashMap tmp(other);
 189         swap(tmp);
 190         return *this;
 191     }
 192
 193     template<typename T, typename U, typename V, typename W, typename X>
 194     inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
 195     {
 196         m_impl.swap(other.m_impl);
 197     }
 198
 199     template<typename T, typename U, typename V, typename W, typename X>
 200     inline HashMap<T, U, V, W, X>::~HashMap()
 201     {
 202         derefAll();
 203     }
 204
 205     template<typename T, typename U, typename V, typename W, typename X>
 206     inline int HashMap<T, U, V, W, X>::size() const
 207     {
 208         return m_impl.size();
 209     }
 210
 211     template<typename T, typename U, typename V, typename W, typename X>
 212     inline int HashMap<T, U, V, W, X>::capacity() const
 213     {
 214         return m_impl.capacity();
 215     }
 216
 217     template<typename T, typename U, typename V, typename W, typename X>
 218     inline bool HashMap<T, U, V, W, X>::isEmpty() const
 219     {
 220         return m_impl.isEmpty();
 221     }
 222
 223     template<typename T, typename U, typename V, typename W, typename X>
 224     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
 225     {
 226         return m_impl.begin();
 227     }
 228
 229     template<typename T, typename U, typename V, typename W, typename X>
 230     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
 231     {
 232         return m_impl.end();
 233     }
 234
 235     template<typename T, typename U, typename V, typename W, typename X>
 236     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
 237     {
 238         return m_impl.begin();
 239     }
 240
 241     template<typename T, typename U, typename V, typename W, typename X>
 242     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
 243     {
 244         return m_impl.end();
 245     }
 246
 247     template<typename T, typename U, typename V, typename W, typename X>
 248     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
 249     {
 250         return m_impl.find(*(const KeyStorageType*)&key);
 251     }
 252
 253     template<typename T, typename U, typename V, typename W, typename X>
 254     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
 255     {
 256         return m_impl.find(*(const KeyStorageType*)&key);
 257     }
 258
 259     template<typename T, typename U, typename V, typename W, typename X>
 260     inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
 261     {
 262         return m_impl.contains(*(const KeyStorageType*)&key);
 263     }
 264
 265     template<typename T, typename U, typename V, typename W, typename X>
 266     inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
 267     HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
 268     {
 269         const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
 270         typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;
 271         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
 272     }
 273
 274     template<typename T, typename U, typename V, typename W, typename X>
 275     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
 276     HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
 277     {
 278         pair<iterator, bool> result = inlineAdd(key, mapped);
 279         if (!result.second)
 280             // add call above didn't change anything, so set the mapped value
 281             result.first->second = mapped;
 282         return result;
 283     }
 284
 285     template<typename T, typename U, typename V, typename W, typename X>
 286     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
 287     HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
 288     {
 289         return inlineAdd(key, mapped);
 290     }
 291
 292     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 293     typename HashMap<T, U, V, W, MappedTraits>::MappedType
 294     HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
 295     {
 296         if (m_impl.isEmpty())
 297             return MappedTraits::emptyValue();
 298         ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
 299         if (!entry)
 300             return MappedTraits::emptyValue();
 301         return ((ValueType *)entry)->second;
 302     }
 303
 304     template<typename T, typename U, typename V, typename W, typename X>
 305     inline void HashMap<T, U, V, W, X>::remove(iterator it)
 306     {
 307         if (it.m_impl == m_impl.end())
 308             return;
 309         m_impl.checkTableConsistency();
 310         RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);
 311         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
 312     }
 313
 314     template<typename T, typename U, typename V, typename W, typename X>
 315     inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
 316     {
 317         remove(find(key));
 318     }
 319
 320     template<typename T, typename U, typename V, typename W, typename X>
 321     inline void HashMap<T, U, V, W, X>::clear()
 322     {
 323         derefAll();
 324         m_impl.clear();
 325     }
 326
 327     template<typename T, typename U, typename V, typename W, typename MappedTraits>
 328     typename HashMap<T, U, V, W, MappedTraits>::MappedType
 329     HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)
 330     {
 331         // This can probably be made more efficient to avoid ref/deref churn.
 332         iterator it = find(key);
 333         if (it == end())
 334             return MappedTraits::emptyValue();
 335         typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second;
 336         remove(it);
 337         return result;
 338     }
 339
 340     template<typename T, typename U, typename V, typename W, typename X>
 341     bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
 342     {
 343         if (a.size() != b.size())
 344             return false;
 345
 346         typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;
 347
 348         const_iterator end = a.end();
 349         const_iterator notFound = b.end();
 350         for (const_iterator it = a.begin(); it != end; ++it) {
 351             const_iterator bPos = b.find(it->first);
 352             if (bPos == notFound || it->second != bPos->second)
 353                 return false;
 354         }
 355
 356         return true;
 357     }
 358
 359     template<typename T, typename U, typename V, typename W, typename X>
 360     inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
 361     {
 362         return !(a == b);
 363     }
 364
 365     template<typename MappedType, typename HashTableType>
 366     void deleteAllPairSeconds(HashTableType& collection)
 367     {
 368         typedef typename HashTableType::const_iterator iterator;
 369         iterator end = collection.end();
 370         for (iterator it = collection.begin(); it != end; ++it)
 371             delete *(MappedType*)&it->second;
 372     }
 373
 374     template<typename T, typename U, typename V, typename W, typename X>
 375     inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)
 376     {
 377         deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
 378     }
 379
 380     template<typename KeyType, typename HashTableType>
 381     void deleteAllPairFirsts(HashTableType& collection)
 382     {
 383         typedef typename HashTableType::const_iterator iterator;
 384         iterator end = collection.end();
 385         for (iterator it = collection.begin(); it != end; ++it)
 386             delete *(KeyType*)&it->first;
 387     }
 388
 389     template<typename T, typename U, typename V, typename W, typename X>
 390     inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)
 391     {
 392         deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection);
 393     }
 394
 395     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 396     inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
 397     {
 398         typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator;
 399
 400         vector.resize(collection.size());
 401
 402         iterator it = collection.begin().keys();
 403         iterator end = collection.end().keys();
 404         for (unsigned i = 0; it != end; ++it, ++i)
 405             vector[i] = *it;
 406     }
 407
 408     template<typename T, typename U, typename V, typename W, typename X, typename Y>
 409     inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
 410     {
 411         typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator;
 412
 413         vector.resize(collection.size());
 414
 415         iterator it = collection.begin().values();
 416         iterator end = collection.end().values();
 417         for (unsigned i = 0; it != end; ++it, ++i)
 418             vector[i] = *it;
 419     }
 420
 421 } // namespace WTF
 422
 423 using WTF::HashMap;
 424
 425 #include "RefPtrHashMap.h"
 426
 427 #endif /* WTF_HashMap_h */