1 // -*- mode: c++; c-basic-offset: 4 -*-

     2 /*

     3  * This file is part of the KDE libraries

     4  *

     5  * Copyright (C) 2005, 2006 Apple Computer, Inc.

     6  *

     7  * This library is free software; you can redistribute it and/or

     8  * modify it under the terms of the GNU Library General Public

     9  * License as published by the Free Software Foundation; either

    10  * version 2 of the License, or (at your option) any later version.

    11  *

    12  * This library is distributed in the hope that it will be useful,

    13  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    15  * Library General Public License for more details.

    16  *

    17  * You should have received a copy of the GNU Library General Public License

    18  * along with this library; see the file COPYING.LIB.  If not, write to

    19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    20  * Boston, MA 02110-1301, USA.

    21  *

    22  */

    23 

    24 #ifndef WTF_HashSet_h

    25 #define WTF_HashSet_h

    26 

    27 #include "HashTable.h"

    28 #include <wtf/Vector.h>

    29 

    30 namespace WTF {

    31 

    32     template<typename T> struct IdentityExtractor;

    33 

    34     template<typename Value, typename HashFunctions, typename Traits> class HashSet;

    35     template<typename Value, typename HashFunctions, typename Traits>

    36     void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&);

    37 

    38     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,

    39         typename TraitsArg = HashTraits<ValueArg> > class HashSet {

    40     private:

    41         typedef HashArg HashFunctions;

    42         typedef TraitsArg ValueTraits;

    43 

    44         typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Hash StorageHashFunctions;

    45 

    46         typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Traits StorageTraits;

    47         typedef typename StorageTraits::TraitType StorageType;

    48 

    49         typedef HashTable<StorageType, StorageType, IdentityExtractor<StorageType>,

    50             StorageHashFunctions, StorageTraits, StorageTraits> HashTableType;

    51 

    52     public:

    53         typedef typename ValueTraits::TraitType ValueType;

    54         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;

    55         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;

    56 

    57         HashSet();

    58         HashSet(const HashSet&);

    59         HashSet& operator=(const HashSet&);

    60         ~HashSet();

    61 

    62         void swap(HashSet&);

    63 

    64         int size() const;

    65         int capacity() const;

    66         bool isEmpty() const;

    67 

    68         iterator begin();

    69         iterator end();

    70         const_iterator begin() const;

    71         const_iterator end() const;

    72 

    73         iterator find(const ValueType&);

    74         const_iterator find(const ValueType&) const;

    75         bool contains(const ValueType&) const;

    76 

    77         // the return value is a pair of an interator to the new value's location, 

    78         // and a bool that is true if an new entry was added

    79         pair<iterator, bool> add(const ValueType&);

    80 

    81         // a special version of add() that finds the object by hashing and comparing

    82         // with some other type, to avoid the cost of type conversion if the object is already

    83         // in the table. HashTranslator should have the following methods:

    84         //   static unsigned hash(const T&);

    85         //   static bool equal(const ValueType&, const T&);

    86         //   static translate(ValueType&, const T&, unsigned hashCode);

    87         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);

    88 

    89         void remove(const ValueType&);

    90         void remove(iterator);

    91         void clear();

    92 

    93     private:

    94         void refAll();

    95         void derefAll();

    96 

    97         friend void deleteAllValues<>(const HashSet&);

    98 

    99         HashTableType m_impl;

   100     };

   101 

   102     template<typename T> struct IdentityExtractor {

   103         static const T& extract(const T& t) { return t; }

   104     };

   105 

   106     template<bool canReplaceDeletedValue, typename ValueType, typename ValueTraits, typename StorageTraits, typename HashFunctions>

   107     struct HashSetTranslator;

   108 

   109     template<typename ValueType, typename ValueTraits, typename StorageTraits, typename HashFunctions>

   110     struct HashSetTranslator<true, ValueType, ValueTraits, StorageTraits, HashFunctions> {

   111         typedef typename StorageTraits::TraitType StorageType;

   112         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }

   113         static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }

   114         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)

   115         {

   116             Assigner<ValueTraits::needsRef, ValueType, StorageType, ValueTraits>::assign(key, location);

   117         }

   118     };

   119 

   120     template<typename ValueType, typename ValueTraits, typename StorageTraits, typename HashFunctions>

   121     struct HashSetTranslator<false, ValueType, ValueTraits, StorageTraits, HashFunctions> {

   122         typedef typename StorageTraits::TraitType StorageType;

   123         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }

   124         static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }

   125         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)

   126         {

   127             if (location == StorageTraits::deletedValue())

   128                 location = StorageTraits::emptyValue();

   129             Assigner<ValueTraits::needsRef, ValueType, StorageType, ValueTraits>::assign(key, location);

   130         }

   131     };

   132 

   133     template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename T, typename Translator>

   134     struct HashSetTranslatorAdapter;

   135 

   136     template<typename ValueType, typename StorageTraits, typename T, typename Translator>

   137     struct HashSetTranslatorAdapter<true, ValueType, StorageTraits, T, Translator> {

   138         typedef typename StorageTraits::TraitType StorageType;

   139         static unsigned hash(const T& key) { return Translator::hash(key); }

   140         static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }

   141         static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)

   142         {

   143             Translator::translate(*(ValueType*)&location, key, hashCode);

   144         }

   145     };

   146 

   147     template<typename ValueType, typename StorageTraits, typename T, typename Translator>

   148     struct HashSetTranslatorAdapter<false, ValueType, StorageTraits, T, Translator> {

   149         typedef typename StorageTraits::TraitType StorageType;

   150         static unsigned hash(const T& key) { return Translator::hash(key); }

   151         static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }

   152         static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)

   153         {

   154             if (location == StorageTraits::deletedValue())

   155                 location = StorageTraits::emptyValue();

   156             Translator::translate(*(ValueType*)&location, key, hashCode);

   157         }

   158     };

   159 

   160     template<typename T, typename U, typename V>

   161     inline void HashSet<T, U, V>::refAll()

   162     {

   163         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);

   164     }

   165 

   166     template<typename T, typename U, typename V>

   167     inline void HashSet<T, U, V>::derefAll()

   168     {

   169         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);

   170     }

   171 

   172     template<typename T, typename U, typename V>

   173     inline HashSet<T, U, V>::HashSet()

   174     {

   175     }

   176 

   177     template<typename T, typename U, typename V>

   178     inline HashSet<T, U, V>::HashSet(const HashSet& other)

   179         : m_impl(other.m_impl)

   180     {

   181         refAll();

   182     }

   183 

   184     template<typename T, typename U, typename V>

   185     inline HashSet<T, U, V>& HashSet<T, U, V>::operator=(const HashSet& other)

   186     {

   187         HashSet tmp(other);

   188         swap(tmp); 

   189         return *this;

   190     }

   191 

   192     template<typename T, typename U, typename V>

   193     inline void HashSet<T, U, V>::swap(HashSet& other)

   194     {

   195         m_impl.swap(other.m_impl); 

   196     }

   197 

   198     template<typename T, typename U, typename V>

   199     inline HashSet<T, U, V>::~HashSet()

   200     {

   201         derefAll();

   202     }

   203 

   204     template<typename T, typename U, typename V>

   205     inline int HashSet<T, U, V>::size() const

   206     {

   207         return m_impl.size(); 

   208     }

   209 

   210     template<typename T, typename U, typename V>

   211     inline int HashSet<T, U, V>::capacity() const

   212     {

   213         return m_impl.capacity(); 

   214     }

   215 

   216     template<typename T, typename U, typename V>

   217     inline bool HashSet<T, U, V>::isEmpty() const

   218     {

   219         return m_impl.isEmpty(); 

   220     }

   221 

   222     template<typename T, typename U, typename V>

   223     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()

   224     {

   225         return m_impl.begin(); 

   226     }

   227 

   228     template<typename T, typename U, typename V>

   229     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()

   230     {

   231         return m_impl.end(); 

   232     }

   233 

   234     template<typename T, typename U, typename V>

   235     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const

   236     {

   237         return m_impl.begin(); 

   238     }

   239 

   240     template<typename T, typename U, typename V>

   241     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const

   242     {

   243         return m_impl.end(); 

   244     }

   245 

   246     template<typename T, typename U, typename V>

   247     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)

   248     {

   249         return m_impl.find(*(const StorageType*)&value); 

   250     }

   251 

   252     template<typename T, typename U, typename V>

   253     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const

   254     {

   255         return m_impl.find(*(const StorageType*)&value); 

   256     }

   257 

   258     template<typename T, typename U, typename V>

   259     inline bool HashSet<T, U, V>::contains(const ValueType& value) const

   260     {

   261         return m_impl.contains(*(const StorageType*)&value); 

   262     }

   263 

   264     template<typename T, typename U, typename V>

   265     pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value)

   266     {

   267 #if PLATFORM(SYMBIAN)

   268         typedef HashSetTranslator< !ValueTraits::needsDestruction || StorageTraits::needsDestruction, ValueType, ValueTraits, StorageTraits, HashFunctions> Translator;

   269 #else

   270         const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;

   271         typedef HashSetTranslator<canReplaceDeletedValue, ValueType, ValueTraits, StorageTraits, HashFunctions> Translator;

   272 #endif

   273         return m_impl.template add<ValueType, ValueType, Translator>(value, value);

   274     }

   275 

   276     template<typename Value, typename HashFunctions, typename Traits>

   277 #if PLATFORM(SYMBIAN)

   278     template<typename T, typename HashTranslator> 

   279 #else

   280     template<typename T, typename Translator> 

   281 #endif

   282     pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>

   283     HashSet<Value, HashFunctions, Traits>::add(const T& value)

   284     {

   285 #if PLATFORM(SYMBIAN)

   286         typedef HashSetTranslatorAdapter< !ValueTraits::needsDestruction || StorageTraits::needsDestruction, ValueType, StorageTraits, T, HashTranslator> Adapter;

   287 #else

   288         const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;

   289         typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;

   290 #endif

   291         return m_impl.template add<T, T, Adapter>(value, value);

   292     }

   293 

   294     template<typename T, typename U, typename V>

   295     inline void HashSet<T, U, V>::remove(iterator it)

   296     {

   297         if (it.m_impl == m_impl.end())

   298             return;

   299         RefCounter<ValueTraits, StorageTraits>::deref(*it.m_impl);

   300         m_impl.remove(it.m_impl);

   301     }

   302 

   303     template<typename T, typename U, typename V>

   304     inline void HashSet<T, U, V>::remove(const ValueType& value)

   305     {

   306         remove(find(value));

   307     }

   308 

   309     template<typename T, typename U, typename V>

   310     inline void HashSet<T, U, V>::clear()

   311     {

   312         derefAll();

   313         m_impl.clear(); 

   314     }

   315 

   316     template<typename ValueType, typename HashTableType>

   317     void deleteAllValues(HashTableType& collection)

   318     {

   319         typedef typename HashTableType::const_iterator iterator;

   320         iterator end = collection.end();

   321         for (iterator it = collection.begin(); it != end; ++it)

   322             delete *(ValueType*)&*it;

   323     }

   324 

   325     template<typename T, typename U, typename V>

   326     inline void deleteAllValues(const HashSet<T, U, V>& collection)

   327     {

   328         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);

   329     }

   330     

   331     template<typename T, typename U, typename V>

   332     inline void copyToVector(const HashSet<T, U, V>& collection, Vector<T>& vector)

   333     {

   334         typedef typename HashSet<T, U, V>::const_iterator iterator;

   335         

   336         vector.resize(collection.size());

   337         

   338         iterator it = collection.begin();

   339         iterator end = collection.end();

   340         for (unsigned i = 0; it != end; ++it, ++i)

   341             vector[i] = *it;

   342     }  

   343 } // namespace WTF

   344 

   345 using WTF::HashSet;

   346 

   347 #endif /* WTF_HashSet_h */