HashMap.h 16.1 KB
Newer Older
mjs's avatar
mjs committed
1 2
// -*- mode: c++; c-basic-offset: 4 -*-
/*
darin@apple.com's avatar
darin@apple.com committed
3
 * Copyright (C) 2005, 2006, 2007 Apple Inc. All rights reserved.
darin's avatar
darin committed
4
 *
mjs's avatar
mjs committed
5 6 7 8 9 10 11 12 13 14 15 16
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
staikos's avatar
staikos committed
17 18
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
mjs's avatar
mjs committed
19 20 21
 *
 */

mjs's avatar
mjs committed
22 23
#ifndef WTF_HashMap_h
#define WTF_HashMap_h
mjs's avatar
mjs committed
24 25

#include "HashTable.h"
mjs's avatar
mjs committed
26
#include "Vector.h"
mjs's avatar
mjs committed
27

mjs's avatar
mjs committed
28
namespace WTF {
mjs's avatar
mjs committed
29

darin's avatar
darin committed
30 31
    template<typename PairType> struct PairFirstExtractor;

darin's avatar
darin committed
32 33 34
    template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
        typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
    class HashMap {
darin's avatar
darin committed
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
    private:
        typedef KeyTraitsArg KeyTraits;
        typedef MappedTraitsArg MappedTraits;
        typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;

    public:
        typedef typename KeyTraits::TraitType KeyType;
        typedef typename MappedTraits::TraitType MappedType;
        typedef typename ValueTraits::TraitType ValueType;

    private:
        typedef HashArg HashFunctions;

        typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;

        typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
        typedef typename MappedTraits::StorageTraits MappedStorageTraits;
        typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;

        typedef typename KeyStorageTraits::TraitType KeyStorageType;
        typedef typename MappedStorageTraits::TraitType MappedStorageType;
        typedef typename ValueStorageTraits::TraitType ValueStorageType;

        typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
            StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;

    public:
        typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;

        HashMap();
        HashMap(const HashMap&);
        HashMap& operator=(const HashMap&);
        ~HashMap();

ggaren's avatar
ggaren committed
70 71
        void swap(HashMap&);

darin's avatar
darin committed
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
        int size() const;
        int capacity() const;
        bool isEmpty() const;

        // iterators iterate over pairs of keys and values
        iterator begin();
        iterator end();
        const_iterator begin() const;
        const_iterator end() const;

        iterator find(const KeyType&);
        const_iterator find(const KeyType&) const;
        bool contains(const KeyType&) const;
        MappedType get(const KeyType&) const;

        // replaces value but not key if key is already present
        // return value is a pair of the iterator to the key location, 
        // and a boolean that's true if a new value was actually added
        pair<iterator, bool> set(const KeyType&, const MappedType&); 

        // does nothing if key is already present
        // return value is a pair of the iterator to the key location, 
        // and a boolean that's true if a new value was actually added
        pair<iterator, bool> add(const KeyType&, const MappedType&); 

        void remove(const KeyType&);
darin@apple.com's avatar
darin@apple.com committed
98
        void remove(iterator);
darin's avatar
darin committed
99 100
        void clear();

darin@apple.com's avatar
darin@apple.com committed
101 102
        MappedType take(const KeyType&); // efficient combination of get with remove

darin's avatar
darin committed
103 104 105 106 107 108 109 110 111 112 113 114
    private:
        pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
        void refAll();
        void derefAll();

        HashTableType m_impl;
    };

    template<typename PairType> struct PairFirstExtractor {
        static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
    };

mjs's avatar
mjs committed
115
    template<bool canReplaceDeletedKey, typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
darin's avatar
darin committed
116 117
    struct HashMapTranslator;

mjs's avatar
mjs committed
118 119
    template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
    struct HashMapTranslator<true, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {
darin's avatar
darin committed
120 121 122 123 124
        typedef typename ValueType::first_type KeyType;
        typedef typename ValueType::second_type MappedType;
        typedef typename ValueStorageTraits::TraitType ValueStorageType;
        typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
        typedef typename KeyStorageTraits::TraitType KeyStorageType;
mjs's avatar
mjs committed
125 126 127 128
        typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;
        typedef typename MappedStorageTraits::TraitType MappedStorageType;
        typedef typename ValueTraits::FirstTraits KeyTraits;
        typedef typename ValueTraits::SecondTraits MappedTraits;
darin's avatar
darin committed
129 130 131

        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
        static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
mjs's avatar
mjs committed
132
        static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped)
darin's avatar
darin committed
133
        {
mjs's avatar
mjs committed
134 135
            Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
            Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);
darin's avatar
darin committed
136 137 138
        }
    };

mjs's avatar
mjs committed
139 140
    template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
    struct HashMapTranslator<false, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {
darin's avatar
darin committed
141 142 143 144 145
        typedef typename ValueType::first_type KeyType;
        typedef typename ValueType::second_type MappedType;
        typedef typename ValueStorageTraits::TraitType ValueStorageType;
        typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
        typedef typename KeyStorageTraits::TraitType KeyStorageType;
mjs's avatar
mjs committed
146 147 148 149 150
        typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;
        typedef typename MappedStorageTraits::TraitType MappedStorageType;
        typedef typename ValueTraits::FirstTraits KeyTraits;
        typedef typename ValueTraits::SecondTraits MappedTraits;
        
darin's avatar
darin committed
151 152
        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
        static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
mjs's avatar
mjs committed
153
        static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped)
darin's avatar
darin committed
154 155 156
        {
            if (location.first == KeyStorageTraits::deletedValue())
                location.first = KeyStorageTraits::emptyValue();
mjs's avatar
mjs committed
157 158
            Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
            Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);
darin's avatar
darin committed
159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
        }
    };

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<T, U, V, W, X>::refAll()
    {
        HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<T, U, V, W, X>::derefAll()
    {
        HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<T, U, V, W, X>::HashMap()
    {
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)
        : m_impl(other.m_impl)
    {
        refAll();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)
    {
        HashMap tmp(other);
ggaren's avatar
ggaren committed
190
        swap(tmp); 
191
        return *this;
darin's avatar
darin committed
192 193
    }

ggaren's avatar
ggaren committed
194 195 196 197 198 199
    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
    {
        m_impl.swap(other.m_impl); 
    }

darin's avatar
darin committed
200 201 202 203 204 205 206 207 208 209 210 211 212 213
    template<typename T, typename U, typename V, typename W, typename X>
    inline HashMap<T, U, V, W, X>::~HashMap()
    {
        derefAll();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline int HashMap<T, U, V, W, X>::size() const
    {
        return m_impl.size(); 
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline int HashMap<T, U, V, W, X>::capacity() const
mjs's avatar
mjs committed
214
    { 
darin's avatar
darin committed
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270
        return m_impl.capacity(); 
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<T, U, V, W, X>::isEmpty() const
    {
        return m_impl.isEmpty();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
    {
        return m_impl.begin();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
    {
        return m_impl.end();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
    {
        return m_impl.begin();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
    {
        return m_impl.end();
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
    {
        return m_impl.find(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
    {
        return m_impl.find(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
    {
        return m_impl.contains(*(const KeyStorageType*)&key);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
    HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 
    {
        const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
mjs's avatar
mjs committed
271
        typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;
darin's avatar
darin committed
272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
        return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
    }

    template<typename T, typename U, typename V, typename W, typename X>
    pair<typename HashMap<T, U, V, W, X>::iterator, bool>
    HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 
    {
        pair<iterator, bool> result = inlineAdd(key, mapped);
        if (!result.second)
            // add call above didn't change anything, so set the mapped value
            result.first->second = mapped;
        return result;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    pair<typename HashMap<T, U, V, W, X>::iterator, bool>
    HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
    {
        return inlineAdd(key, mapped);
    }

    template<typename T, typename U, typename V, typename W, typename MappedTraits>
mjs's avatar
mjs committed
294
    typename HashMap<T, U, V, W, MappedTraits>::MappedType
darin's avatar
darin committed
295 296
    HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
    {
mjs's avatar
mjs committed
297
        if (m_impl.isEmpty())
darin's avatar
darin committed
298
            return MappedTraits::emptyValue();
mjs's avatar
mjs committed
299 300 301 302
        ValueStorageType* entry = const_cast<HashTableType&>(m_impl).lookup(*(const KeyStorageType*)&key);
        if (!entry)
            return MappedTraits::emptyValue();
        return ((ValueType *)entry)->second;
darin's avatar
darin committed
303 304 305 306 307 308 309
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<T, U, V, W, X>::remove(iterator it)
    {
        if (it.m_impl == m_impl.end())
            return;
310
        m_impl.checkTableConsistency();
mjs's avatar
mjs committed
311
        RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);
312
        m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
darin's avatar
darin committed
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
    {
        remove(find(key));
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void HashMap<T, U, V, W, X>::clear()
    {
        derefAll();
        m_impl.clear();
    }

darin@apple.com's avatar
darin@apple.com committed
328 329 330 331 332 333 334 335 336 337 338 339 340
    template<typename T, typename U, typename V, typename W, typename MappedTraits>
    typename HashMap<T, U, V, W, MappedTraits>::MappedType
    HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)
    {
        // This can probably be made more efficient to avoid ref/deref churn.
        iterator it = find(key);
        if (it == end())
            return MappedTraits::emptyValue();
        typename HashMap<T, U, V, W, MappedTraits>::MappedType result = it->second;
        remove(it);
        return result;
    }

mjs's avatar
mjs committed
341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
    template<typename T, typename U, typename V, typename W, typename X>
    bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
    {
        if (a.size() != b.size())
            return false;

        typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;

        const_iterator end = a.end();
        const_iterator notFound = b.end();
        for (const_iterator it = a.begin(); it != end; ++it) {
            const_iterator bPos = b.find(it->first);
            if (bPos == notFound || it->second != bPos->second)
                return false;
        }

        return true;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
    {
        return !(a == b);
    }

darin's avatar
darin committed
366 367 368
    template<typename MappedType, typename HashTableType>
    void deleteAllPairSeconds(HashTableType& collection)
    {
darin's avatar
darin committed
369
        typedef typename HashTableType::const_iterator iterator;
darin's avatar
darin committed
370 371 372 373 374 375
        iterator end = collection.end();
        for (iterator it = collection.begin(); it != end; ++it)
            delete *(MappedType*)&it->second;
    }

    template<typename T, typename U, typename V, typename W, typename X>
darin's avatar
darin committed
376
    inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)
darin's avatar
darin committed
377 378 379
    {
        deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
    }
mjs's avatar
mjs committed
380

381 382 383 384 385 386 387 388 389 390 391 392 393 394
    template<typename KeyType, typename HashTableType>
    void deleteAllPairFirsts(HashTableType& collection)
    {
        typedef typename HashTableType::const_iterator iterator;
        iterator end = collection.end();
        for (iterator it = collection.begin(); it != end; ++it)
            delete *(KeyType*)&it->first;
    }

    template<typename T, typename U, typename V, typename W, typename X>
    inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)
    {
        deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection);
    }
mjs's avatar
mjs committed
395 396 397 398 399 400 401 402 403 404 405 406 407
    
    template<typename T, typename U, typename V, typename W, typename X>
    inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Vector<U>& vector)
    {
        typedef typename HashMap<T, U, V, W, X>::const_iterator iterator;
        
        vector.resize(collection.size());
        
        iterator it = collection.begin();
        iterator end = collection.end();
        for (unsigned i = 0; it != end; ++it, ++i)
            vector[i] = (*it).second;
    }   
408

mjs's avatar
mjs committed
409
} // namespace WTF
mjs's avatar
mjs committed
410

mjs's avatar
mjs committed
411
using WTF::HashMap;
mjs's avatar
mjs committed
412

mjs's avatar
mjs committed
413
#endif /* WTF_HashMap_h */