third_party/WebKit/Source/wtf/HashSet.h

   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         void reserveCapacityForSize(unsigned size)
  74         {
  75             m_impl.reserveCapacityForSize(size);
  76         }
  77
  78         iterator begin() const;
  79         iterator end() const;
  80
  81         iterator find(ValuePeekInType) const;
  82         bool contains(ValuePeekInType) const;
  83
  84         // An alternate version of find() that finds the object by hashing and comparing
  85         // with some other type, to avoid the cost of type conversion. HashTranslator
  86         // must have the following function members:
  87         //   static unsigned hash(const T&);
  88         //   static bool equal(const ValueType&, const T&);
  89         template<typename HashTranslator, typename T> iterator find(const T&) const;
  90         template<typename HashTranslator, typename T> bool contains(const T&) const;
  91
  92         // The return value is a pair of an iterator to the new value's location,
  93         // and a bool that is true if an new entry was added.
  94         AddResult add(ValuePassInType);
  95
  96         // An alternate version of add() that finds the object by hashing and comparing
  97         // with some other type, to avoid the cost of type conversion if the object is already
  98         // in the table. HashTranslator must have the following function members:
  99         //   static unsigned hash(const T&);
 100         //   static bool equal(const ValueType&, const T&);
 101         //   static translate(ValueType&, const T&, unsigned hashCode);
 102         template<typename HashTranslator, typename T> AddResult add(const T&);
 103
 104         void remove(ValuePeekInType);
 105         void remove(iterator);
 106         void clear();
 107         template<typename Collection>
 108         void removeAll(const Collection& toBeRemoved) { WTF::removeAll(*this, toBeRemoved); }
 109
 110         static bool isValidValue(ValuePeekInType);
 111
 112         ValuePassOutType take(iterator);
 113         ValuePassOutType take(ValuePeekInType);
 114         ValuePassOutType takeAny();
 115
 116         template<typename VisitorDispatcher>
 117         void trace(VisitorDispatcher visitor) { m_impl.trace(visitor); }
 118
 119     private:
 120         HashTableType m_impl;
 121     };
 122
 123     struct IdentityExtractor {
 124         template<typename T>
 125         static const T& extract(const T& t) { return t; }
 126     };
 127
 128     template<typename Translator>
 129     struct HashSetTranslatorAdapter {
 130         template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
 131         template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
 132         template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
 133         {
 134             Translator::translate(location, key, hashCode);
 135         }
 136     };
 137
 138     template<typename T, typename U, typename V, typename W>
 139     inline unsigned HashSet<T, U, V, W>::size() const
 140     {
 141         return m_impl.size();
 142     }
 143
 144     template<typename T, typename U, typename V, typename W>
 145     inline unsigned HashSet<T, U, V, W>::capacity() const
 146     {
 147         return m_impl.capacity();
 148     }
 149
 150     template<typename T, typename U, typename V, typename W>
 151     inline bool HashSet<T, U, V, W>::isEmpty() const
 152     {
 153         return m_impl.isEmpty();
 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>::begin() const
 158     {
 159         return m_impl.begin();
 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>::end() const
 164     {
 165         return m_impl.end();
 166     }
 167
 168     template<typename T, typename U, typename V, typename W>
 169     inline typename HashSet<T, U, V, W>::iterator HashSet<T, U, V, W>::find(ValuePeekInType value) const
 170     {
 171         return m_impl.find(value);
 172     }
 173
 174     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
 175     inline bool HashSet<Value, HashFunctions, Traits, Allocator>::contains(ValuePeekInType value) const
 176     {
 177         return m_impl.contains(value);
 178     }
 179
 180     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
 181     template<typename HashTranslator, typename T>
 182     typename HashSet<Value, HashFunctions, Traits, Allocator>::iterator
 183     inline HashSet<Value, HashFunctions, Traits, Allocator>::find(const T& value) const
 184     {
 185         return m_impl.template find<HashSetTranslatorAdapter<HashTranslator>>(value);
 186     }
 187
 188     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
 189     template<typename HashTranslator, typename T>
 190     inline bool HashSet<Value, HashFunctions, Traits, Allocator>::contains(const T& value) const
 191     {
 192         return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator>>(value);
 193     }
 194
 195     template<typename T, typename U, typename V, typename W>
 196     inline typename HashSet<T, U, V, W>::AddResult HashSet<T, U, V, W>::add(ValuePassInType value)
 197     {
 198         return m_impl.add(value);
 199     }
 200
 201     template<typename Value, typename HashFunctions, typename Traits, typename Allocator>
 202     template<typename HashTranslator, typename T>
 203     inline typename HashSet<Value, HashFunctions, Traits, Allocator>::AddResult
 204     HashSet<Value, HashFunctions, Traits, Allocator>::add(const T& value)
 205     {
 206         return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator>>(value, value);
 207     }
 208
 209     template<typename T, typename U, typename V, typename W>
 210     inline void HashSet<T, U, V, W>::remove(iterator it)
 211     {
 212         m_impl.remove(it.m_impl);
 213     }
 214
 215     template<typename T, typename U, typename V, typename W>
 216     inline void HashSet<T, U, V, W>::remove(ValuePeekInType value)
 217     {
 218         remove(find(value));
 219     }
 220
 221     template<typename T, typename U, typename V, typename W>
 222     inline void HashSet<T, U, V, W>::clear()
 223     {
 224         m_impl.clear();
 225     }
 226
 227     template<typename T, typename U, typename V, typename W>
 228     inline bool HashSet<T, U, V, W>::isValidValue(ValuePeekInType value)
 229     {
 230         if (ValueTraits::isDeletedValue(value))
 231             return false;
 232
 233         if (HashFunctions::safeToCompareToEmptyOrDeleted) {
 234             if (value == ValueTraits::emptyValue())
 235                 return false;
 236         } else {
 237             if (isHashTraitsEmptyValue<ValueTraits>(value))
 238                 return false;
 239         }
 240
 241         return true;
 242     }
 243
 244     template<typename T, typename U, typename V, typename W>
 245     inline typename HashSet<T, U, V, W>::ValuePassOutType HashSet<T, U, V, W>::take(iterator it)
 246     {
 247         if (it == end())
 248             return ValueTraits::emptyValue();
 249
 250         ValuePassOutType result = ValueTraits::passOut(const_cast<ValueType&>(*it));
 251         remove(it);
 252
 253         return result;
 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>::take(ValuePeekInType value)
 258     {
 259         return take(find(value));
 260     }
 261
 262     template<typename T, typename U, typename V, typename W>
 263     inline typename HashSet<T, U, V, W>::ValuePassOutType HashSet<T, U, V, W>::takeAny()
 264     {
 265         return take(begin());
 266     }
 267
 268     template<typename C, typename W>
 269     inline void copyToVector(const C& collection, W& vector)
 270     {
 271         typedef typename C::const_iterator iterator;
 272
 273         vector.resize(collection.size());
 274
 275         iterator it = collection.begin();
 276         iterator end = collection.end();
 277         for (unsigned i = 0; it != end; ++it, ++i)
 278             vector[i] = *it;
 279     }
 280
 281 #if !ENABLE(OILPAN)
 282     template<typename T, typename U, typename V>
 283     struct NeedsTracing<HashSet<T, U, V>> {
 284         static const bool value = false;
 285     };
 286 #endif
 287
 288 } // namespace WTF
 289
 290 using WTF::HashSet;
 291
 292 #endif /* WTF_HashSet_h */