Home | History | Annotate | Download | only in wtf
      1 /*
      2  * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 "wtf/DefaultAllocator.h"
     25 #include "wtf/HashTable.h"
     26 
     27 namespace WTF {
     28 
     29     struct IdentityExtractor;
     30 
     31     // Note: empty or deleted values are not allowed, using them may lead to undefined behavior.
     32     // For pointer valuess this means that null pointers are not allowed unless you supply custom traits.
     33     template<
     34         typename ValueArg,
     35         typename HashArg = typename DefaultHash<ValueArg>::Hash,
     36         typename TraitsArg = HashTraits<ValueArg>,
     37         typename Allocator = DefaultAllocator> class HashSet {
     38         WTF_USE_ALLOCATOR(HashSet, Allocator);
     39     private:
     40         typedef HashArg HashFunctions;
     41         typedef TraitsArg ValueTraits;
     42         typedef typename ValueTraits::PeekInType ValuePeekInType;
     43         typedef typename ValueTraits::PassInType ValuePassInType;
     44         typedef typename ValueTraits::PassOutType ValuePassOutType;
     45 
     46     public:
     47         typedef typename ValueTraits::TraitType ValueType;
     48 
     49     private:
     50         typedef HashTable<ValueType, ValueType, IdentityExtractor,
     51             HashFunctions, ValueTraits, ValueTraits, Allocator> HashTableType;
     52 
     53     public:
     54         typedef HashTableConstIteratorAdapter<HashTableType, ValueTraits> iterator;
     55         typedef HashTableConstIteratorAdapter<HashTableType, ValueTraits> const_iterator;
     56         typedef typename HashTableType::AddResult AddResult;
     57 
     58         void swap(HashSet& ref)
     59         {
     60             m_impl.swap(ref.m_impl);
     61         }
     62 
     63         void swap(typename Allocator::template OtherType<HashSet>::Type other)
     64         {
     65             HashSet& ref = Allocator::getOther(other);
     66             m_impl.swap(ref.m_impl);
     67         }
     68 
     69         unsigned size() const;
     70         unsigned capacity() const;
     71         bool isEmpty() const;
     72 
     73         iterator begin() const;
     74         iterator end() const;
     75 
     76         iterator find(ValuePeekInType) const;
     77         bool contains(ValuePeekInType) const;
     78 
     79         // An alternate version of find() that finds the object by hashing and comparing
     80         // with some other type, to avoid the cost of type conversion. HashTranslator
     81         // must have the following function members:
     82         //   static unsigned hash(const T&);
     83         //   static bool equal(const ValueType&, const T&);
     84         template<typename HashTranslator, typename T> iterator find(const T&) const;
     85         template<typename HashTranslator, typename T> bool contains(const T&) const;
     86 
     87         // The return value is a pair of an iterator to the new value's location,
     88         // and a bool that is true if an new entry was added.
     89         AddResult add(ValuePassInType);
     90 
     91         // An alternate version of add() that finds the object by hashing and comparing
     92         // with some other type, to avoid the cost of type conversion if the object is already
     93         // in the table. HashTranslator must have the following function members:
     94         //   static unsigned hash(const T&);
     95         //   static bool equal(const ValueType&, const T&);
     96         //   static translate(ValueType&, const T&, unsigned hashCode);
     97         template<typename HashTranslator, typename T> AddResult add(const T&);
     98 
     99         void remove(ValuePeekInType);
    100         void remove(iterator);
    101         void clear();
    102         template<typename Collection>
    103         void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, toBeRemoved); }
    104 
    105         static bool isValidValue(ValuePeekInType);
    106 
    107         ValuePassOutType take(iterator);
    108         ValuePassOutType take(ValuePeekInType);
    109         ValuePassOutType takeAny();
    110 
    111         void trace(typename Allocator::Visitor* visitor) { m_impl.trace(visitor); }
    112 
    113     private:
    114         HashTableType m_impl;
    115     };
    116 
    117     struct IdentityExtractor {
    118         template<typename T>
    119         static const T& extract(const T& t) { return t; }
    120     };
    121 
    122     template<typename Translator>
    123     struct HashSetTranslatorAdapter {
    124         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
    125         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
    126         template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
    127         {
    128             Translator::translate(location, key, hashCode);
    129         }
    130     };
    131 
    132     template<typename T, typename U, typename V, typename W>
    133     inline unsigned HashSet<T, U, V, W>::size() const
    134     {
    135         return m_impl.size();
    136     }
    137 
    138     template<typename T, typename U, typename V, typename W>
    139     inline unsigned HashSet<T, U, V, W>::capacity() const
    140     {
    141         return m_impl.capacity();
    142     }
    143 
    144     template<typename T, typename U, typename V, typename W>
    145     inline bool HashSet<T, U, V, W>::isEmpty() const
    146     {
    147         return m_impl.isEmpty();
    148     }
    149 
    150     template<typename T, typename U, typename V, typename W>
    151     inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::begin() const
    152     {
    153         return m_impl.begin();
    154     }
    155 
    156     template<typename T, typename U, typename V, typename W>
    157     inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::end() const
    158     {
    159         return m_impl.end();
    160     }
    161 
    162     template<typename T, typename U, typename V, typename W>
    163     inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::find(ValuePeekInType value) const
    164     {
    165         return m_impl.find(value);
    166     }
    167 
    168     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
    169     inline bool HashSet<Value, HashFunctions, Traits, Allocator>::contains(ValuePeekInType value) const
    170     {
    171         return m_impl.contains(value);
    172     }
    173 
    174     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
    175     template<typename HashTranslator, typename T>
    176     typename HashSet<Value, HashFunctions, Traits, Allocator>::iterator
    177     inline HashSet<Value, HashFunctions, Traits, Allocator>::find(const T& value) const
    178     {
    179         return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(value);
    180     }
    181 
    182     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
    183     template<typename HashTranslator, typename T>
    184     inline bool HashSet<Value, HashFunctions, Traits, Allocator>::contains(const T& value) const
    185     {
    186         return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator> >(value);
    187     }
    188 
    189     template<typename T, typename U, typename V, typename W>
    190     inline typename HashSet<T, U, V, W>::AddResult HashSet<T, U, V, W>::add(ValuePassInType value)
    191     {
    192         return m_impl.add(value);
    193     }
    194 
    195     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
    196     template<typename HashTranslator, typename T>
    197     inline typename HashSet<Value, HashFunctions, Traits, Allocator>::AddResult
    198     HashSet<Value, HashFunctions, Traits, Allocator>::add(const T& value)
    199     {
    200         return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator> >(value, value);
    201     }
    202 
    203     template<typename T, typename U, typename V, typename W>
    204     inline void HashSet<T, U, V, W>::remove(iterator it)
    205     {
    206         m_impl.remove(it.m_impl);
    207     }
    208 
    209     template<typename T, typename U, typename V, typename W>
    210     inline void HashSet<T, U, V, W>::remove(ValuePeekInType value)
    211     {
    212         remove(find(value));
    213     }
    214 
    215     template<typename T, typename U, typename V, typename W>
    216     inline void HashSet<T, U, V, W>::clear()
    217     {
    218         m_impl.clear();
    219     }
    220 
    221     template<typename T, typename U, typename V, typename W>
    222     inline bool HashSet<T, U, V, W>::isValidValue(ValuePeekInType value)
    223     {
    224         if (ValueTraits::isDeletedValue(value))
    225             return false;
    226 
    227         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
    228             if (value == ValueTraits::emptyValue())
    229                 return false;
    230         } else {
    231             if (isHashTraitsEmptyValue<ValueTraits>(value))
    232                 return false;
    233         }
    234 
    235         return true;
    236     }
    237 
    238     template<typename T, typename U, typename V, typename W>
    239     inline typename HashSet<T, U, V, W>::ValuePassOutType HashSet<T, U, V, W>::take(iterator it)
    240     {
    241         if (it == end())
    242             return ValueTraits::emptyValue();
    243 
    244         ValuePassOutType result = ValueTraits::passOut(const_cast<ValueType&>(*it));
    245         remove(it);
    246 
    247         return result;
    248     }
    249 
    250     template<typename T, typename U, typename V, typename W>
    251     inline typename HashSet<T, U, V, W>::ValuePassOutType HashSet<T, U, V, W>::take(ValuePeekInType value)
    252     {
    253         return take(find(value));
    254     }
    255 
    256     template<typename T, typename U, typename V, typename W>
    257     inline typename HashSet<T, U, V, W>::ValuePassOutType HashSet<T, U, V, W>::takeAny()
    258     {
    259         return take(begin());
    260     }
    261 
    262     template<typename C, typename W>
    263     inline void copyToVector(const C& collection, W& vector)
    264     {
    265         typedef typename C::const_iterator iterator;
    266 
    267         vector.resize(collection.size());
    268 
    269         iterator it = collection.begin();
    270         iterator end = collection.end();
    271         for (unsigned i = 0; it != end; ++it, ++i)
    272             vector[i] = *it;
    273     }
    274 
    275 #if !ENABLE(OILPAN)
    276     template<typename T, typename U, typename V>
    277     struct NeedsTracing<HashSet<T, U, V> > {
    278         static const bool value = false;
    279     };
    280 #endif
    281 
    282 } // namespace WTF
    283 
    284 using WTF::HashSet;
    285 
    286 #endif /* WTF_HashSet_h */
    287