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