• Skip to content
  • Skip to link menu
KDE 4.1 API Reference
  • KDE API Reference
  • kdelibs
  • Sitemap
  • Contact Us
 

WTF

HashMap.h

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

WTF

Skip menu "WTF"
  • Main Page
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • KIO
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • Kross
  • KUtils
  • Nepomuk
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.4
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal