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