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