File indexing completed on 2024-05-12 15:43:38
0001 /* 0002 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. 0003 * 0004 * This library is free software; you can redistribute it and/or 0005 * modify it under the terms of the GNU Library General Public 0006 * License as published by the Free Software Foundation; either 0007 * version 2 of the License, or (at your option) any later version. 0008 * 0009 * This library is distributed in the hope that it will be useful, 0010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 0012 * Library General Public License for more details. 0013 * 0014 * You should have received a copy of the GNU Library General Public License 0015 * along with this library; see the file COPYING.LIB. If not, write to 0016 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 * Boston, MA 02110-1301, USA. 0018 * 0019 */ 0020 0021 #ifndef WTF_HashSet_h 0022 #define WTF_HashSet_h 0023 0024 #include <wtf/HashTable.h> 0025 #include <kjs/CommonIdentifiers.h> 0026 0027 namespace WTF 0028 { 0029 0030 template<typename Value, typename HashFunctions, typename Traits> class HashSet; 0031 template<typename Value, typename HashFunctions, typename Traits> 0032 void deleteAllValues(const HashSet<Value, HashFunctions, Traits> &); 0033 0034 template<typename T> struct IdentityExtractor; 0035 0036 template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash, 0037 typename TraitsArg = HashTraits<ValueArg> > class HashSet 0038 { 0039 private: 0040 typedef HashArg HashFunctions; 0041 typedef TraitsArg ValueTraits; 0042 0043 public: 0044 typedef typename ValueTraits::TraitType ValueType; 0045 0046 private: 0047 typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>, 0048 HashFunctions, ValueTraits, ValueTraits> HashTableType; 0049 0050 public: 0051 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator; 0052 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator; 0053 0054 void swap(HashSet &); 0055 0056 int size() const; 0057 int capacity() const; 0058 bool isEmpty() const; 0059 0060 iterator begin(); 0061 iterator end(); 0062 const_iterator begin() const; 0063 const_iterator end() const; 0064 0065 iterator find(const ValueType &); 0066 const_iterator find(const ValueType &) const; 0067 bool contains(const ValueType &) const; 0068 0069 // An alternate version of find() that finds the object by hashing and comparing 0070 // with some other type, to avoid the cost of type conversion. HashTranslator 0071 // must have the following function members: 0072 // static unsigned hash(const T&); 0073 // static bool equal(const ValueType&, const T&); 0074 template<typename T, typename HashTranslator> iterator find(const T &); 0075 template<typename T, typename HashTranslator> const_iterator find(const T &) const; 0076 template<typename T, typename HashTranslator> bool contains(const T &) const; 0077 0078 // The return value is a pair of an iterator to the new value's location, 0079 // and a bool that is true if an new entry was added. 0080 pair<iterator, bool> add(const ValueType &); 0081 0082 // An alternate version of add() that finds the object by hashing and comparing 0083 // with some other type, to avoid the cost of type conversion if the object is already 0084 // in the table. HashTranslator must have the following methods: 0085 // static unsigned hash(const T&); 0086 // static bool equal(const ValueType&, const T&); 0087 // static translate(ValueType&, const T&, unsigned hashCode); 0088 template<typename T, typename HashTranslator> pair<iterator, bool> add(const T &); 0089 0090 void remove(const ValueType &); 0091 void remove(iterator); 0092 void clear(); 0093 0094 private: 0095 friend void deleteAllValues<>(const HashSet &); 0096 0097 HashTableType m_impl; 0098 }; 0099 0100 template<typename T> struct IdentityExtractor { 0101 static const T &extract(const T &t) 0102 { 0103 return t; 0104 } 0105 }; 0106 0107 template<typename ValueType, typename ValueTraits, typename T, typename Translator> 0108 struct HashSetTranslatorAdapter { 0109 static unsigned hash(const T &key) 0110 { 0111 return Translator::hash(key); 0112 } 0113 static bool equal(const ValueType &a, const T &b) 0114 { 0115 return Translator::equal(a, b); 0116 } 0117 static void translate(ValueType &location, const T &key, const T &, unsigned hashCode) 0118 { 0119 Translator::translate(location, key, hashCode); 0120 } 0121 }; 0122 0123 template<typename T, typename U, typename V> 0124 inline void HashSet<T, U, V>::swap(HashSet &other) 0125 { 0126 m_impl.swap(other.m_impl); 0127 } 0128 0129 template<typename T, typename U, typename V> 0130 inline int HashSet<T, U, V>::size() const 0131 { 0132 return m_impl.size(); 0133 } 0134 0135 template<typename T, typename U, typename V> 0136 inline int HashSet<T, U, V>::capacity() const 0137 { 0138 return m_impl.capacity(); 0139 } 0140 0141 template<typename T, typename U, typename V> 0142 inline bool HashSet<T, U, V>::isEmpty() const 0143 { 0144 return m_impl.isEmpty(); 0145 } 0146 0147 template<typename T, typename U, typename V> 0148 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() 0149 { 0150 return m_impl.begin(); 0151 } 0152 0153 template<typename T, typename U, typename V> 0154 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() 0155 { 0156 return m_impl.end(); 0157 } 0158 0159 template<typename T, typename U, typename V> 0160 inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const 0161 { 0162 return m_impl.begin(); 0163 } 0164 0165 template<typename T, typename U, typename V> 0166 inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const 0167 { 0168 return m_impl.end(); 0169 } 0170 0171 template<typename T, typename U, typename V> 0172 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType &value) 0173 { 0174 return m_impl.find(value); 0175 } 0176 0177 template<typename T, typename U, typename V> 0178 inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType &value) const 0179 { 0180 return m_impl.find(value); 0181 } 0182 0183 template<typename T, typename U, typename V> 0184 inline bool HashSet<T, U, V>::contains(const ValueType &value) const 0185 { 0186 return m_impl.contains(value); 0187 } 0188 0189 template<typename Value, typename HashFunctions, typename Traits> 0190 template<typename T, typename Translator> 0191 typename HashSet<Value, HashFunctions, Traits>::iterator 0192 inline HashSet<Value, HashFunctions, Traits>::find(const T &value) 0193 { 0194 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter; 0195 return m_impl.template find<T, Adapter>(value); 0196 } 0197 0198 template<typename Value, typename HashFunctions, typename Traits> 0199 template<typename T, typename Translator> 0200 typename HashSet<Value, HashFunctions, Traits>::const_iterator 0201 inline HashSet<Value, HashFunctions, Traits>::find(const T &value) const 0202 { 0203 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter; 0204 return m_impl.template find<T, Adapter>(value); 0205 } 0206 0207 template<typename Value, typename HashFunctions, typename Traits> 0208 template<typename T, typename Translator> 0209 inline bool HashSet<Value, HashFunctions, Traits>::contains(const T &value) const 0210 { 0211 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter; 0212 return m_impl.template contains<T, Adapter>(value); 0213 } 0214 0215 template<typename T, typename U, typename V> 0216 pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value) 0217 { 0218 return m_impl.add(value); 0219 } 0220 0221 template<typename Value, typename HashFunctions, typename Traits> 0222 template<typename T, typename Translator> 0223 pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> 0224 HashSet<Value, HashFunctions, Traits>::add(const T &value) 0225 { 0226 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, Translator> Adapter; 0227 return m_impl.template addPassingHashCode<T, T, Adapter>(value, value); 0228 } 0229 0230 template<typename T, typename U, typename V> 0231 inline void HashSet<T, U, V>::remove(iterator it) 0232 { 0233 if (it.m_impl == m_impl.end()) { 0234 return; 0235 } 0236 m_impl.checkTableConsistency(); 0237 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl); 0238 } 0239 0240 template<typename T, typename U, typename V> 0241 inline void HashSet<T, U, V>::remove(const ValueType &value) 0242 { 0243 remove(find(value)); 0244 } 0245 0246 template<typename T, typename U, typename V> 0247 inline void HashSet<T, U, V>::clear() 0248 { 0249 m_impl.clear(); 0250 } 0251 0252 template<typename ValueType, typename HashTableType> 0253 void deleteAllValues(HashTableType &collection) 0254 { 0255 typedef typename HashTableType::const_iterator iterator; 0256 iterator end = collection.end(); 0257 for (iterator it = collection.begin(); it != end; ++it) { 0258 delete *it; 0259 } 0260 } 0261 0262 template<typename T, typename U, typename V> 0263 inline void deleteAllValues(const HashSet<T, U, V> &collection) 0264 { 0265 deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl); 0266 } 0267 0268 template<typename T, typename U, typename V, typename W> 0269 inline void copyToVector(const HashSet<T, U, V> &collection, W &vector) 0270 { 0271 typedef typename HashSet<T, U, V>::const_iterator iterator; 0272 0273 vector.resize(collection.size()); 0274 0275 iterator it = collection.begin(); 0276 iterator end = collection.end(); 0277 for (unsigned i = 0; it != end; ++it, ++i) { 0278 vector[i] = *it; 0279 } 0280 } 0281 0282 } // namespace WTF 0283 0284 using WTF::HashSet; 0285 0286 #endif /* WTF_HashSet_h */