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