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>&);
35 template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
36 typename TraitsArg = HashTraits<ValueArg> > class HashSet {
37 WTF_MAKE_FAST_ALLOCATED;
39 typedef HashArg HashFunctions;
40 typedef TraitsArg ValueTraits;
43 typedef typename ValueTraits::TraitType ValueType;
46 typedef HashTable<ValueType, ValueType, IdentityExtractor,
47 HashFunctions, ValueTraits, ValueTraits> HashTableType;
50 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;
51 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
52 typedef typename HashTableType::AddResult AddResult;
60 iterator begin() const;
63 iterator find(const ValueType&) const;
64 bool contains(const ValueType&) const;
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;
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&);
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&);
86 void remove(const ValueType&);
87 void remove(iterator);
90 static bool isValidValue(const ValueType&);
93 friend void deleteAllValues<>(const HashSet&);
98 struct IdentityExtractor {
99 template<typename T> static const T& extract(const T& t) { return t; }
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)
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 HashTranslator, typename T>
162 typename HashSet<Value, HashFunctions, Traits>::iterator
163 inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
165 return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(value);
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
172 return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator> >(value);
175 template<typename T, typename U, typename V>
176 inline typename HashSet<T, U, V>::AddResult HashSet<T, U, V>::add(const ValueType& value)
178 return m_impl.add(value);
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)
186 return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator> >(value, value);
189 template<typename T, typename U, typename V>
190 inline void HashSet<T, U, V>::remove(iterator it)
192 m_impl.remove(it.m_impl);
195 template<typename T, typename U, typename V>
196 inline void HashSet<T, U, V>::remove(const ValueType& value)
201 template<typename T, typename U, typename V>
202 inline void HashSet<T, U, V>::clear()
207 template<typename T, typename U, typename V>
208 inline bool HashSet<T, U, V>::isValidValue(const ValueType& value)
210 if (ValueTraits::isDeletedValue(value))
213 if (HashFunctions::safeToCompareToEmptyOrDeleted) {
214 if (value == ValueTraits::emptyValue())
217 if (isHashTraitsEmptyValue<ValueTraits>(value))
224 template<typename ValueType, typename HashTableType>
225 void deleteAllValues(HashTableType& collection)
227 typedef typename HashTableType::const_iterator iterator;
228 iterator end = collection.end();
229 for (iterator it = collection.begin(); it != end; ++it)
233 template<typename T, typename U, typename V>
234 inline void deleteAllValues(const HashSet<T, U, V>& collection)
236 deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
239 template<typename C, typename W>
240 inline void copyToVector(const C& collection, W& vector)
242 typedef typename C::const_iterator iterator;
244 vector.resize(collection.size());
246 iterator it = collection.begin();
247 iterator end = collection.end();
248 for (unsigned i = 0; it != end; ++it, ++i)
256 #endif /* WTF_HashSet_h */