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 } // namespace WTF 276 277 using WTF::HashSet; 278 279 #endif /* WTF_HashSet_h */ 280
