Source/WTF/wtf/HashSet.h

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