WTF

HashMap.h

00001 // -*- mode: c++; c-basic-offset: 4 -*-
00002 /*
00003  * This file is part of the KDE libraries
00004  *
00005  * Copyright (C) 2005, 2006 Apple Computer, Inc.
00006  *
00007  * This library is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU Library General Public
00009  * License as published by the Free Software Foundation; either
00010  * version 2 of the License, or (at your option) any later version.
00011  *
00012  * This library is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015  * Library General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU Library General Public License
00018  * along with this library; see the file COPYING.LIB.  If not, write to
00019  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00020  * Boston, MA 02110-1301, USA.
00021  *
00022  */
00023 
00024 #ifndef WTF_HashMap_h
00025 #define WTF_HashMap_h
00026 
00027 #include "HashTable.h"
00028 
00029 namespace WTF {
00030 
00031     template<typename PairType> struct PairFirstExtractor;
00032 
00033     template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
00034         typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
00035     class HashMap {
00036     private:
00037         typedef KeyTraitsArg KeyTraits;
00038         typedef MappedTraitsArg MappedTraits;
00039         typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
00040 
00041     public:
00042         typedef typename KeyTraits::TraitType KeyType;
00043         typedef typename MappedTraits::TraitType MappedType;
00044         typedef typename ValueTraits::TraitType ValueType;
00045 
00046     private:
00047         typedef HashArg HashFunctions;
00048 
00049         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
00050 
00051         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
00052         typedef typename MappedTraits::StorageTraits MappedStorageTraits;
00053         typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
00054 
00055         typedef typename KeyStorageTraits::TraitType KeyStorageType;
00056         typedef typename MappedStorageTraits::TraitType MappedStorageType;
00057         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00058 
00059         typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
00060             StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
00061 
00062     public:
00063         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
00064         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
00065 
00066         HashMap();
00067         HashMap(const HashMap&);
00068         HashMap& operator=(const HashMap&);
00069         ~HashMap();
00070 
00071         void swap(HashMap&);
00072 
00073         int size() const;
00074         int capacity() const;
00075         bool isEmpty() const;
00076 
00077         // iterators iterate over pairs of keys and values
00078         iterator begin();
00079         iterator end();
00080         const_iterator begin() const;
00081         const_iterator end() const;
00082 
00083         iterator find(const KeyType&);
00084         const_iterator find(const KeyType&) const;
00085         bool contains(const KeyType&) const;
00086         MappedType get(const KeyType&) const;
00087 
00088         // replaces value but not key if key is already present
00089         // return value is a pair of the iterator to the key location, 
00090         // and a boolean that's true if a new value was actually added
00091         pair<iterator, bool> set(const KeyType&, const MappedType&); 
00092 
00093         // does nothing if key is already present
00094         // return value is a pair of the iterator to the key location, 
00095         // and a boolean that's true if a new value was actually added
00096         pair<iterator, bool> add(const KeyType&, const MappedType&); 
00097 
00098         void remove(const KeyType&);
00099         void remove(iterator it);
00100         void clear();
00101 
00102     private:
00103         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
00104         void refAll();
00105         void derefAll();
00106 
00107         HashTableType m_impl;
00108     };
00109 
00110     template<typename PairType> struct PairFirstExtractor {
00111         static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
00112     };
00113 
00114     template<bool canReplaceDeletedKey, typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
00115     struct HashMapTranslator;
00116 
00117     template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
00118     struct HashMapTranslator<true, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {
00119         typedef typename ValueType::first_type KeyType;
00120         typedef typename ValueType::second_type MappedType;
00121         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00122         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
00123         typedef typename KeyStorageTraits::TraitType KeyStorageType;
00124         typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;
00125         typedef typename MappedStorageTraits::TraitType MappedStorageType;
00126         typedef typename ValueTraits::FirstTraits KeyTraits;
00127         typedef typename ValueTraits::SecondTraits MappedTraits;
00128 
00129         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
00130         static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
00131         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
00132         {
00133             Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
00134             Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);
00135         }
00136     };
00137 
00138     template<typename ValueType, typename ValueTraits, typename ValueStorageTraits, typename HashFunctions>
00139     struct HashMapTranslator<false, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> {
00140         typedef typename ValueType::first_type KeyType;
00141         typedef typename ValueType::second_type MappedType;
00142         typedef typename ValueStorageTraits::TraitType ValueStorageType;
00143         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
00144         typedef typename KeyStorageTraits::TraitType KeyStorageType;
00145         typedef typename ValueStorageTraits::SecondTraits MappedStorageTraits;
00146         typedef typename MappedStorageTraits::TraitType MappedStorageType;
00147         typedef typename ValueTraits::FirstTraits KeyTraits;
00148         typedef typename ValueTraits::SecondTraits MappedTraits;
00149         
00150         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
00151         static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
00152         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
00153         {
00154             if (location.first == KeyStorageTraits::deletedValue())
00155                 location.first = KeyStorageTraits::emptyValue();
00156             Assigner<KeyTraits::needsRef, KeyType, KeyStorageType, KeyTraits>::assign(key, location.first);
00157             Assigner<MappedTraits::needsRef, MappedType, MappedStorageType, MappedTraits>::assign(mapped, location.second);
00158         }
00159     };
00160 
00161     template<typename T, typename U, typename V, typename W, typename X>
00162     inline void HashMap<T, U, V, W, X>::refAll()
00163     {
00164         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
00165     }
00166 
00167     template<typename T, typename U, typename V, typename W, typename X>
00168     inline void HashMap<T, U, V, W, X>::derefAll()
00169     {
00170         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
00171     }
00172 
00173     template<typename T, typename U, typename V, typename W, typename X>
00174     inline HashMap<T, U, V, W, X>::HashMap()
00175     {
00176     }
00177 
00178     template<typename T, typename U, typename V, typename W, typename X>
00179     inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)
00180         : m_impl(other.m_impl)
00181     {
00182         refAll();
00183     }
00184 
00185     template<typename T, typename U, typename V, typename W, typename X>
00186     inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)
00187     {
00188         HashMap tmp(other);
00189         swap(tmp); 
00190         return *this;
00191     }
00192 
00193     template<typename T, typename U, typename V, typename W, typename X>
00194     inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
00195     {
00196         m_impl.swap(other.m_impl); 
00197     }
00198 
00199     template<typename T, typename U, typename V, typename W, typename X>
00200     inline HashMap<T, U, V, W, X>::~HashMap()
00201     {
00202         derefAll();
00203     }
00204 
00205     template<typename T, typename U, typename V, typename W, typename X>
00206     inline int HashMap<T, U, V, W, X>::size() const
00207     {
00208         return m_impl.size(); 
00209     }
00210 
00211     template<typename T, typename U, typename V, typename W, typename X>
00212     inline int HashMap<T, U, V, W, X>::capacity() const
00213     { 
00214         return m_impl.capacity(); 
00215     }
00216 
00217     template<typename T, typename U, typename V, typename W, typename X>
00218     inline bool HashMap<T, U, V, W, X>::isEmpty() const
00219     {
00220         return m_impl.isEmpty();
00221     }
00222 
00223     template<typename T, typename U, typename V, typename W, typename X>
00224     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
00225     {
00226         return m_impl.begin();
00227     }
00228 
00229     template<typename T, typename U, typename V, typename W, typename X>
00230     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
00231     {
00232         return m_impl.end();
00233     }
00234 
00235     template<typename T, typename U, typename V, typename W, typename X>
00236     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
00237     {
00238         return m_impl.begin();
00239     }
00240 
00241     template<typename T, typename U, typename V, typename W, typename X>
00242     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
00243     {
00244         return m_impl.end();
00245     }
00246 
00247     template<typename T, typename U, typename V, typename W, typename X>
00248     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
00249     {
00250         return m_impl.find(*(const KeyStorageType*)&key);
00251     }
00252 
00253     template<typename T, typename U, typename V, typename W, typename X>
00254     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
00255     {
00256         return m_impl.find(*(const KeyStorageType*)&key);
00257     }
00258 
00259     template<typename T, typename U, typename V, typename W, typename X>
00260     inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
00261     {
00262         return m_impl.contains(*(const KeyStorageType*)&key);
00263     }
00264 
00265     template<typename T, typename U, typename V, typename W, typename X>
00266     inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
00267     HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 
00268     {
00269         const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
00270         typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueTraits, ValueStorageTraits, HashFunctions> TranslatorType;
00271         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
00272     }
00273 
00274     template<typename T, typename U, typename V, typename W, typename X>
00275     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
00276     HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 
00277     {
00278         pair<iterator, bool> result = inlineAdd(key, mapped);
00279         if (!result.second)
00280             // add call above didn't change anything, so set the mapped value
00281             result.first->second = mapped;
00282         return result;
00283     }
00284 
00285     template<typename T, typename U, typename V, typename W, typename X>
00286     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
00287     HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
00288     {
00289         return inlineAdd(key, mapped);
00290     }
00291 
00292     template<typename T, typename U, typename V, typename W, typename MappedTraits>
00293     inline typename HashMap<T, U, V, W, MappedTraits>::MappedType
00294     HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
00295     {
00296         const_iterator it = find(key);
00297         if (it == end())
00298             return MappedTraits::emptyValue();
00299         return it->second;
00300     }
00301 
00302     template<typename T, typename U, typename V, typename W, typename X>
00303     inline void HashMap<T, U, V, W, X>::remove(iterator it)
00304     {
00305         if (it.m_impl == m_impl.end())
00306             return;
00307         RefCounter<ValueTraits, ValueStorageTraits>::deref(*it.m_impl);
00308         m_impl.remove(it.m_impl);
00309     }
00310 
00311     template<typename T, typename U, typename V, typename W, typename X>
00312     inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
00313     {
00314         remove(find(key));
00315     }
00316 
00317     template<typename T, typename U, typename V, typename W, typename X>
00318     inline void HashMap<T, U, V, W, X>::clear()
00319     {
00320         derefAll();
00321         m_impl.clear();
00322     }
00323 
00324     template<typename T, typename U, typename V, typename W, typename X>
00325     bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
00326     {
00327         if (a.size() != b.size())
00328             return false;
00329 
00330         typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;
00331 
00332         const_iterator end = a.end();
00333         const_iterator notFound = b.end();
00334         for (const_iterator it = a.begin(); it != end; ++it) {
00335             const_iterator bPos = b.find(it->first);
00336             if (bPos == notFound || it->second != bPos->second)
00337                 return false;
00338         }
00339 
00340         return true;
00341     }
00342 
00343     template<typename T, typename U, typename V, typename W, typename X>
00344     inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
00345     {
00346         return !(a == b);
00347     }
00348 
00349     template<typename MappedType, typename HashTableType>
00350     void deleteAllPairSeconds(HashTableType& collection)
00351     {
00352         typedef typename HashTableType::const_iterator iterator;
00353         iterator end = collection.end();
00354         for (iterator it = collection.begin(); it != end; ++it)
00355             delete *(MappedType*)&it->second;
00356     }
00357 
00358     template<typename T, typename U, typename V, typename W, typename X>
00359     inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)
00360     {
00361         deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
00362     }
00363 
00364     template<typename KeyType, typename HashTableType>
00365     void deleteAllPairFirsts(HashTableType& collection)
00366     {
00367         typedef typename HashTableType::const_iterator iterator;
00368         iterator end = collection.end();
00369         for (iterator it = collection.begin(); it != end; ++it)
00370             delete *(KeyType*)&it->first;
00371     }
00372 
00373     template<typename T, typename U, typename V, typename W, typename X>
00374     inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)
00375     {
00376         deleteAllPairFirsts<typename HashMap<T, U, V, W, X>::KeyType>(collection);
00377     }
00378 
00379 } // namespace WTF
00380 
00381 using WTF::HashMap;
00382 
00383 #endif /* WTF_HashMap_h */
WTF

HashMap.h

WTF

kdelibs
