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

WTF

RefPtrHashMap.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 namespace WTF {
00023 
00024     // This specialization is a direct copy of HashMap, with overloaded functions
00025     // to allow for lookup by pointer instead of RefPtr, avoiding ref-count churn.
00026     
00027     // FIXME: Find a better way that doesn't require an entire copy of the HashMap template.
00028     
00029     template<typename RawKeyType, typename ValueType, typename ValueTraits, typename HashFunctions>
00030     struct RefPtrHashMapRawKeyTranslator {
00031         typedef typename ValueType::first_type KeyType;
00032         typedef typename ValueType::second_type MappedType;
00033         typedef typename ValueTraits::FirstTraits KeyTraits;
00034         typedef typename ValueTraits::SecondTraits MappedTraits;
00035 
00036         static unsigned hash(RawKeyType key) { return HashFunctions::hash(key); }
00037         static bool equal(const KeyType& a, RawKeyType b) { return HashFunctions::equal(a, b); }
00038         static void translate(ValueType& location, RawKeyType key, const MappedType& mapped)
00039         {
00040             location.first = key;
00041             location.second = mapped;
00042         }
00043     };
00044 
00045     template<typename T, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg>
00046     class HashMap<RefPtr<T>, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg> {
00047     private:
00048         typedef KeyTraitsArg KeyTraits;
00049         typedef MappedTraitsArg MappedTraits;
00050         typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
00051 
00052     public:
00053         typedef typename KeyTraits::TraitType KeyType;
00054         typedef T* RawKeyType;
00055         typedef typename MappedTraits::TraitType MappedType;
00056         typedef typename ValueTraits::TraitType ValueType;
00057 
00058     private:
00059         typedef HashArg HashFunctions;
00060 
00061         typedef HashTable<KeyType, ValueType, PairFirstExtractor<ValueType>,
00062             HashFunctions, ValueTraits, KeyTraits> HashTableType;
00063 
00064         typedef RefPtrHashMapRawKeyTranslator<RawKeyType, ValueType, ValueTraits, HashFunctions>
00065             RawKeyTranslator;
00066 
00067     public:
00068         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
00069         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
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         iterator find(RawKeyType);
00085         const_iterator find(const KeyType&) const;
00086         const_iterator find(RawKeyType) const;
00087         bool contains(const KeyType&) const;
00088         bool contains(RawKeyType) const;
00089         MappedType get(const KeyType&) const;
00090         MappedType get(RawKeyType) const;
00091         MappedType inlineGet(RawKeyType) const;
00092 
00093         // replaces value but not key 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> set(const KeyType&, const MappedType&); 
00097         pair<iterator, bool> set(RawKeyType, const MappedType&); 
00098 
00099         // does nothing if key is already present
00100         // return value is a pair of the iterator to the key location, 
00101         // and a boolean that's true if a new value was actually added
00102         pair<iterator, bool> add(const KeyType&, const MappedType&); 
00103         pair<iterator, bool> add(RawKeyType, const MappedType&); 
00104 
00105         void remove(const KeyType&);
00106         void remove(RawKeyType);
00107         void remove(iterator);
00108         void clear();
00109 
00110         MappedType take(const KeyType&); // efficient combination of get with remove
00111         MappedType take(RawKeyType); // efficient combination of get with remove
00112 
00113     private:
00114         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
00115         pair<iterator, bool> inlineAdd(RawKeyType, const MappedType&);
00116 
00117         HashTableType m_impl;
00118     };
00119     
00120     template<typename T, typename U, typename V, typename W, typename X>
00121     inline void HashMap<RefPtr<T>, U, V, W, X>::swap(HashMap& other)
00122     {
00123         m_impl.swap(other.m_impl); 
00124     }
00125 
00126     template<typename T, typename U, typename V, typename W, typename X>
00127     inline int HashMap<RefPtr<T>, U, V, W, X>::size() const
00128     {
00129         return m_impl.size(); 
00130     }
00131 
00132     template<typename T, typename U, typename V, typename W, typename X>
00133     inline int HashMap<RefPtr<T>, U, V, W, X>::capacity() const
00134     { 
00135         return m_impl.capacity(); 
00136     }
00137 
00138     template<typename T, typename U, typename V, typename W, typename X>
00139     inline bool HashMap<RefPtr<T>, U, V, W, X>::isEmpty() const
00140     {
00141         return m_impl.isEmpty();
00142     }
00143 
00144     template<typename T, typename U, typename V, typename W, typename X>
00145     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::begin()
00146     {
00147         return m_impl.begin();
00148     }
00149 
00150     template<typename T, typename U, typename V, typename W, typename X>
00151     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::end()
00152     {
00153         return m_impl.end();
00154     }
00155 
00156     template<typename T, typename U, typename V, typename W, typename X>
00157     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::begin() const
00158     {
00159         return m_impl.begin();
00160     }
00161 
00162     template<typename T, typename U, typename V, typename W, typename X>
00163     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::end() const
00164     {
00165         return m_impl.end();
00166     }
00167 
00168     template<typename T, typename U, typename V, typename W, typename X>
00169     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key)
00170     {
00171         return m_impl.find(key);
00172     }
00173 
00174     template<typename T, typename U, typename V, typename W, typename X>
00175     inline typename HashMap<RefPtr<T>, U, V, W, X>::iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key)
00176     {
00177         return m_impl.template find<RawKeyType, RawKeyTranslator>(key);
00178     }
00179 
00180     template<typename T, typename U, typename V, typename W, typename X>
00181     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(const KeyType& key) const
00182     {
00183         return m_impl.find(key);
00184     }
00185 
00186     template<typename T, typename U, typename V, typename W, typename X>
00187     inline typename HashMap<RefPtr<T>, U, V, W, X>::const_iterator HashMap<RefPtr<T>, U, V, W, X>::find(RawKeyType key) const
00188     {
00189         return m_impl.template find<RawKeyType, RawKeyTranslator>(key);
00190     }
00191 
00192     template<typename T, typename U, typename V, typename W, typename X>
00193     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(const KeyType& key) const
00194     {
00195         return m_impl.contains(key);
00196     }
00197 
00198     template<typename T, typename U, typename V, typename W, typename X>
00199     inline bool HashMap<RefPtr<T>, U, V, W, X>::contains(RawKeyType key) const
00200     {
00201         return m_impl.template contains<RawKeyType, RawKeyTranslator>(key);
00202     }
00203 
00204     template<typename T, typename U, typename V, typename W, typename X>
00205     inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
00206     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 
00207     {
00208         typedef HashMapTranslator<ValueType, ValueTraits, HashFunctions> TranslatorType;
00209         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
00210     }
00211 
00212     template<typename T, typename U, typename V, typename W, typename X>
00213     inline pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
00214     HashMap<RefPtr<T>, U, V, W, X>::inlineAdd(RawKeyType key, const MappedType& mapped) 
00215     {
00216         return m_impl.template add<RawKeyType, MappedType, RawKeyTranslator>(key, mapped);
00217     }
00218 
00219     template<typename T, typename U, typename V, typename W, typename X>
00220     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
00221     HashMap<RefPtr<T>, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 
00222     {
00223         pair<iterator, bool> result = inlineAdd(key, mapped);
00224         if (!result.second) {
00225             // add call above didn't change anything, so set the mapped value
00226             result.first->second = mapped;
00227         }
00228         return result;
00229     }
00230 
00231     template<typename T, typename U, typename V, typename W, typename X>
00232     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
00233     HashMap<RefPtr<T>, U, V, W, X>::set(RawKeyType key, const MappedType& mapped) 
00234     {
00235         pair<iterator, bool> result = inlineAdd(key, mapped);
00236         if (!result.second) {
00237             // add call above didn't change anything, so set the mapped value
00238             result.first->second = mapped;
00239         }
00240         return result;
00241     }
00242 
00243     template<typename T, typename U, typename V, typename W, typename X>
00244     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
00245     HashMap<RefPtr<T>, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
00246     {
00247         return inlineAdd(key, mapped);
00248     }
00249 
00250     template<typename T, typename U, typename V, typename W, typename X>
00251     pair<typename HashMap<RefPtr<T>, U, V, W, X>::iterator, bool>
00252     HashMap<RefPtr<T>, U, V, W, X>::add(RawKeyType key, const MappedType& mapped)
00253     {
00254         return inlineAdd(key, mapped);
00255     }
00256 
00257     template<typename T, typename U, typename V, typename W, typename MappedTraits>
00258     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
00259     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(const KeyType& key) const
00260     {
00261         ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
00262         if (!entry)
00263             return MappedTraits::emptyValue();
00264         return entry->second;
00265     }
00266 
00267     template<typename T, typename U, typename V, typename W, typename MappedTraits>
00268     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
00269     inline HashMap<RefPtr<T>, U, V, W, MappedTraits>::inlineGet(RawKeyType key) const
00270     {
00271         ValueType* entry = const_cast<HashTableType&>(m_impl).template lookup<RawKeyType, RawKeyTranslator>(key);
00272         if (!entry)
00273             return MappedTraits::emptyValue();
00274         return entry->second;
00275     }
00276 
00277     template<typename T, typename U, typename V, typename W, typename MappedTraits>
00278     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
00279     HashMap<RefPtr<T>, U, V, W, MappedTraits>::get(RawKeyType key) const
00280     {
00281         return inlineGet(key);
00282     }
00283 
00284     template<typename T, typename U, typename V, typename W, typename X>
00285     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(iterator it)
00286     {
00287         if (it.m_impl == m_impl.end())
00288             return;
00289         m_impl.checkTableConsistency();
00290         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
00291     }
00292 
00293     template<typename T, typename U, typename V, typename W, typename X>
00294     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(const KeyType& key)
00295     {
00296         remove(find(key));
00297     }
00298 
00299     template<typename T, typename U, typename V, typename W, typename X>
00300     inline void HashMap<RefPtr<T>, U, V, W, X>::remove(RawKeyType key)
00301     {
00302         remove(find(key));
00303     }
00304 
00305     template<typename T, typename U, typename V, typename W, typename X>
00306     inline void HashMap<RefPtr<T>, U, V, W, X>::clear()
00307     {
00308         m_impl.clear();
00309     }
00310 
00311     template<typename T, typename U, typename V, typename W, typename MappedTraits>
00312     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
00313     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(const KeyType& key)
00314     {
00315         // This can probably be made more efficient to avoid ref/deref churn.
00316         iterator it = find(key);
00317         if (it == end())
00318             return MappedTraits::emptyValue();
00319         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
00320         remove(it);
00321         return result;
00322     }
00323 
00324     template<typename T, typename U, typename V, typename W, typename MappedTraits>
00325     typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType
00326     HashMap<RefPtr<T>, U, V, W, MappedTraits>::take(RawKeyType key)
00327     {
00328         // This can probably be made more efficient to avoid ref/deref churn.
00329         iterator it = find(key);
00330         if (it == end())
00331             return MappedTraits::emptyValue();
00332         typename HashMap<RefPtr<T>, U, V, W, MappedTraits>::MappedType result = it->second;
00333         remove(it);
00334         return result;
00335     }
00336 
00337 } // namespace WTF

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