2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 <wtf/FastAllocBase.h>
25 #include <wtf/HashTable.h>
29 struct IdentityExtractor;
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 template<typename Value, typename HashFunctions, typename Traits>
35 void fastDeleteAllValues(const HashSet<Value, HashFunctions, Traits>&);
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,
49 HashFunctions, ValueTraits, ValueTraits> HashTableType;
52 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;
53 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
54 typedef typename HashTableType::AddResult AddResult;
62 iterator begin() const;
65 iterator find(const ValueType&) const;
66 bool contains(const ValueType&) const;
68 // An alternate version of find() that finds the object by hashing and comparing
69 // with some other type, to avoid the cost of type conversion. HashTranslator
70 // must have the following function members:
71 // static unsigned hash(const T&);
72 // static bool equal(const ValueType&, const T&);
73 // FIXME: We should reverse the order of the template arguments so that callers
74 // can just pass the translator and let the compiler deduce T.
75 template<typename T, typename HashTranslator> iterator find(const T&) const;
76 template<typename T, typename HashTranslator> bool contains(const T&) const;
78 // The return value is a pair of an interator to the new value's location,
79 // and a bool that is true if an new entry was added.
80 AddResult add(const ValueType&);
82 // An alternate version of add() that finds the object by hashing and comparing
83 // with some other type, to avoid the cost of type conversion if the object is already
84 // in the table. HashTranslator must have the following function members:
85 // static unsigned hash(const T&);
86 // static bool equal(const ValueType&, const T&);
87 // static translate(ValueType&, const T&, unsigned hashCode);
88 // FIXME: We should reverse the order of the template arguments so that callers
89 // can just pass the translator and let the compiler deduce T.
90 template<typename T, typename HashTranslator> AddResult add(const T&);
92 void remove(const ValueType&);
93 void remove(iterator);
97 friend void deleteAllValues<>(const HashSet&);
98 friend void fastDeleteAllValues<>(const HashSet&);
100 HashTableType m_impl;
103 struct IdentityExtractor {
104 template<typename T> static const T& extract(const T& t) { return t; }
107 template<typename Translator>
108 struct HashSetTranslatorAdapter {
109 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
110 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
111 template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
113 Translator::translate(location, key, hashCode);
117 template<typename T, typename U, typename V>
118 inline void HashSet<T, U, V>::swap(HashSet& other)
120 m_impl.swap(other.m_impl);
123 template<typename T, typename U, typename V>
124 inline int HashSet<T, U, V>::size() const
126 return m_impl.size();
129 template<typename T, typename U, typename V>
130 inline int HashSet<T, U, V>::capacity() const
132 return m_impl.capacity();
135 template<typename T, typename U, typename V>
136 inline bool HashSet<T, U, V>::isEmpty() const
138 return m_impl.isEmpty();
141 template<typename T, typename U, typename V>
142 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const
144 return m_impl.begin();
147 template<typename T, typename U, typename V>
148 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const
153 template<typename T, typename U, typename V>
154 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value) const
156 return m_impl.find(value);
159 template<typename T, typename U, typename V>
160 inline bool HashSet<T, U, V>::contains(const ValueType& value) const
162 return m_impl.contains(value);
165 template<typename Value, typename HashFunctions, typename Traits>
166 template<typename T, typename HashTranslator>
167 typename HashSet<Value, HashFunctions, Traits>::iterator
168 inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
170 return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(value);
173 template<typename Value, typename HashFunctions, typename Traits>
174 template<typename T, typename HashTranslator>
175 inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
177 return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator> >(value);
180 template<typename T, typename U, typename V>
181 inline typename HashSet<T, U, V>::AddResult HashSet<T, U, V>::add(const ValueType& value)
183 return m_impl.add(value);
186 template<typename Value, typename HashFunctions, typename Traits>
187 template<typename T, typename HashTranslator>
188 inline typename HashSet<Value, HashFunctions, Traits>::AddResult
189 HashSet<Value, HashFunctions, Traits>::add(const T& value)
191 return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator> >(value, value);
194 template<typename T, typename U, typename V>
195 inline void HashSet<T, U, V>::remove(iterator it)
197 if (it.m_impl == m_impl.end())
199 m_impl.internalCheckTableConsistency();
200 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
203 template<typename T, typename U, typename V>
204 inline void HashSet<T, U, V>::remove(const ValueType& value)
209 template<typename T, typename U, typename V>
210 inline void HashSet<T, U, V>::clear()
215 template<typename ValueType, typename HashTableType>
216 void deleteAllValues(HashTableType& collection)
218 typedef typename HashTableType::const_iterator iterator;
219 iterator end = collection.end();
220 for (iterator it = collection.begin(); it != end; ++it)
224 template<typename T, typename U, typename V>
225 inline void deleteAllValues(const HashSet<T, U, V>& collection)
227 deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
230 template<typename ValueType, typename HashTableType>
231 void fastDeleteAllValues(HashTableType& collection)
233 typedef typename HashTableType::const_iterator iterator;
234 iterator end = collection.end();
235 for (iterator it = collection.begin(); it != end; ++it)
239 template<typename T, typename U, typename V>
240 inline void fastDeleteAllValues(const HashSet<T, U, V>& collection)
242 fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
245 template<typename T, typename U, typename V, typename W>
246 inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
248 typedef typename HashSet<T, U, V>::const_iterator iterator;
250 vector.resize(collection.size());
252 iterator it = collection.begin();
253 iterator end = collection.end();
254 for (unsigned i = 0; it != end; ++it, ++i)
262 #endif /* WTF_HashSet_h */