1 /*

     2  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.

     3  *

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

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

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

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

     8  *

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

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

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

    12  * Library General Public License for more details.

    13  *

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

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

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

    17  * Boston, MA 02110-1301, USA.

    18  *

    19  */

    20 

    21 #ifndef WTF_HashSet_h

    22 #define WTF_HashSet_h

    23 

    24 #include "FastAllocBase.h"

    25 #include "HashTable.h"

    26 

    27 namespace WTF {

    28 

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

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

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

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

    33     void fastDeleteAllValues(const HashSet<Value, HashFunctions, Traits>&);

    34 

    35     template<typename T> struct IdentityExtractor;

    36 

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

    38         typename TraitsArg = HashTraits<ValueArg> > class HashSet : public FastAllocBase {

    39     private:

    40         typedef HashArg HashFunctions;

    41         typedef TraitsArg ValueTraits;

    42 

    43     public:

    44         typedef typename ValueTraits::TraitType ValueType;

    45 

    46     private:

    47         typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,

    48             HashFunctions, ValueTraits, ValueTraits> HashTableType;

    49 

    50     public:

    51         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;

    52         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;

    53 

    54         void swap(HashSet&);

    55 

    56         int size() const;

    57         int capacity() const;

    58         bool isEmpty() const;

    59 

    60         iterator begin() const;

    61         iterator end() const;

    62 

    63         iterator find(const ValueType&) const;

    64         bool contains(const ValueType&) const;

    65 

    66         // An alternate version of find() that finds the object by hashing and comparing

    67         // with some other type, to avoid the cost of type conversion. HashTranslator

    68         // must have the following function members:

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

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

    71         template<typename T, typename HashTranslator> iterator find(const T&) const;

    72         template<typename T, typename HashTranslator> bool contains(const T&) const;

    73 

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

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

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

    77 

    78         // An alternate version of add() that finds the object by hashing and comparing

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

    80         // in the table. HashTranslator must have the following function members:

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

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

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

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

    85 

    86         void remove(const ValueType&);

    87         void remove(iterator);

    88         void clear();

    89 

    90     private:

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

    92         friend void fastDeleteAllValues<>(const HashSet&);

    93 

    94         HashTableType m_impl;

    95     };

    96 

    97     template<typename T> struct IdentityExtractor {

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

    99     };

   100 

   101     template<typename ValueType, typename ValueTraits, typename T, typename Translator>

   102     struct HashSetTranslatorAdapter {

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

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

   105         static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)

   106         {

   107             Translator::translate(location, key, hashCode);

   108         }

   109     };

   110 

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

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

   113     {

   114         m_impl.swap(other.m_impl); 

   115     }

   116 

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

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

   119     {

   120         return m_impl.size(); 

   121     }

   122 

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

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

   125     {

   126         return m_impl.capacity(); 

   127     }

   128 

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

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

   131     {

   132         return m_impl.isEmpty(); 

   133     }

   134 

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

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

   137     {

   138         return m_impl.begin(); 

   139     }

   140 

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

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

   143     {

   144         return m_impl.end(); 

   145     }

   146 

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

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

   149     {

   150         return m_impl.find(value); 

   151     }

   152 

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

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

   155     {

   156         return m_impl.contains(value); 

   157     }

   158 

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

   160     template<typename T, typename HashTranslator>

   161     typename HashSet<Value, HashFunctions, Traits>::iterator

   162     inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const

   163     {

   164         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;

   165         return m_impl.template find<T, Adapter>(value);

   166     }

   167 

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

   169     template<typename T, typename HashTranslator>

   170     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const

   171     {

   172         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;

   173         return m_impl.template contains<T, Adapter>(value);

   174     }

   175 

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

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

   178     {

   179         return m_impl.add(value);

   180     }

   181 

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

   183     template<typename T, typename HashTranslator>

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

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

   186     {

   187         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;

   188         return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);

   189     }

   190 

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

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

   193     {

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

   195             return;

   196         m_impl.internalCheckTableConsistency();

   197         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);

   198     }

   199 

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

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

   202     {

   203         remove(find(value));

   204     }

   205 

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

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

   208     {

   209         m_impl.clear(); 

   210     }

   211 

   212     template<typename ValueType, typename HashTableType>

   213     void deleteAllValues(HashTableType& collection)

   214     {

   215         typedef typename HashTableType::const_iterator iterator;

   216         iterator end = collection.end();

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

   218             delete *it;

   219     }

   220 

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

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

   223     {

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

   225     }

   226 

   227     template<typename ValueType, typename HashTableType>

   228     void fastDeleteAllValues(HashTableType& collection)

   229     {

   230         typedef typename HashTableType::const_iterator iterator;

   231         iterator end = collection.end();

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

   233             fastDelete(*it);

   234     }

   235 

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

   237     inline void fastDeleteAllValues(const HashSet<T, U, V>& collection)

   238     {

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

   240     }

   241     

   242     template<typename T, typename U, typename V, typename W>

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

   244     {

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

   246         

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

   248         

   249         iterator it = collection.begin();

   250         iterator end = collection.end();

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

   252             vector[i] = *it;

   253     }  

   254 

   255 } // namespace WTF

   256 

   257 using WTF::HashSet;

   258 

   259 #endif /* WTF_HashSet_h */