2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
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.
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.
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.
24 #include "FastAllocBase.h"
25 #include "HashTable.h"
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>&);
35 template<typename T> struct IdentityExtractor;
37 template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
38 typename TraitsArg = HashTraits<ValueArg> > class HashSet {
39 WTF_MAKE_FAST_ALLOCATED;
41 typedef HashArg HashFunctions;
42 typedef TraitsArg ValueTraits;
45 typedef typename ValueTraits::TraitType ValueType;
48 typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
49 HashFunctions, ValueTraits, ValueTraits> HashTableType;
52 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;
53 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
61 iterator begin() const;
64 iterator find(const ValueType&) const;
65 bool contains(const ValueType&) const;
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&) const;
73 template<typename T, typename HashTranslator> bool contains(const T&) const;
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&);
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 function members:
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&);
87 void remove(const ValueType&);
88 void remove(iterator);
92 friend void deleteAllValues<>(const HashSet&);
93 friend void fastDeleteAllValues<>(const HashSet&);
98 template<typename T> struct IdentityExtractor {
99 static const T& extract(const T& t) { return t; }
102 template<typename ValueType, typename ValueTraits, typename T, typename Translator>
103 struct HashSetTranslatorAdapter {
104 static unsigned hash(const T& key) { return Translator::hash(key); }
105 static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); }
106 static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)
108 Translator::translate(location, key, hashCode);
112 template<typename T, typename U, typename V>
113 inline void HashSet<T, U, V>::swap(HashSet& other)
115 m_impl.swap(other.m_impl);
118 template<typename T, typename U, typename V>
119 inline int HashSet<T, U, V>::size() const
121 return m_impl.size();
124 template<typename T, typename U, typename V>
125 inline int HashSet<T, U, V>::capacity() const
127 return m_impl.capacity();
130 template<typename T, typename U, typename V>
131 inline bool HashSet<T, U, V>::isEmpty() const
133 return m_impl.isEmpty();
136 template<typename T, typename U, typename V>
137 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const
139 return m_impl.begin();
142 template<typename T, typename U, typename V>
143 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const
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
151 return m_impl.find(value);
154 template<typename T, typename U, typename V>
155 inline bool HashSet<T, U, V>::contains(const ValueType& value) const
157 return m_impl.contains(value);
160 template<typename Value, typename HashFunctions, typename Traits>
161 template<typename T, typename HashTranslator>
162 typename HashSet<Value, HashFunctions, Traits>::iterator
163 inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
165 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
166 return m_impl.template find<T, Adapter>(value);
169 template<typename Value, typename HashFunctions, typename Traits>
170 template<typename T, typename HashTranslator>
171 inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
173 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
174 return m_impl.template contains<T, Adapter>(value);
177 template<typename T, typename U, typename V>
178 inline pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value)
180 return m_impl.add(value);
183 template<typename Value, typename HashFunctions, typename Traits>
184 template<typename T, typename HashTranslator>
185 inline pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
186 HashSet<Value, HashFunctions, Traits>::add(const T& value)
188 typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
189 return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
192 template<typename T, typename U, typename V>
193 inline void HashSet<T, U, V>::remove(iterator it)
195 if (it.m_impl == m_impl.end())
197 m_impl.internalCheckTableConsistency();
198 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
201 template<typename T, typename U, typename V>
202 inline void HashSet<T, U, V>::remove(const ValueType& value)
207 template<typename T, typename U, typename V>
208 inline void HashSet<T, U, V>::clear()
213 template<typename ValueType, typename HashTableType>
214 void deleteAllValues(HashTableType& collection)
216 typedef typename HashTableType::const_iterator iterator;
217 iterator end = collection.end();
218 for (iterator it = collection.begin(); it != end; ++it)
222 template<typename T, typename U, typename V>
223 inline void deleteAllValues(const HashSet<T, U, V>& collection)
225 deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
228 template<typename ValueType, typename HashTableType>
229 void fastDeleteAllValues(HashTableType& collection)
231 typedef typename HashTableType::const_iterator iterator;
232 iterator end = collection.end();
233 for (iterator it = collection.begin(); it != end; ++it)
237 template<typename T, typename U, typename V>
238 inline void fastDeleteAllValues(const HashSet<T, U, V>& collection)
240 fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
243 template<typename T, typename U, typename V, typename W>
244 inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
246 typedef typename HashSet<T, U, V>::const_iterator iterator;
248 vector.resize(collection.size());
250 iterator it = collection.begin();
251 iterator end = collection.end();
252 for (unsigned i = 0; it != end; ++it, ++i)
260 #endif /* WTF_HashSet_h */