OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 * Library General Public License for more details. | 12 * Library General Public License for more details. |
13 * | 13 * |
14 * You should have received a copy of the GNU Library General Public License | 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 | 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, | 16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
17 * Boston, MA 02110-1301, USA. | 17 * Boston, MA 02110-1301, USA. |
18 * | 18 * |
19 */ | 19 */ |
20 | 20 |
21 #ifndef WTF_HashSet_h | 21 #ifndef WTF_HashSet_h |
22 #define WTF_HashSet_h | 22 #define WTF_HashSet_h |
23 | 23 |
24 #include "wtf/FastAllocBase.h" | 24 #include "wtf/FastAllocBase.h" |
25 #include "wtf/HashTable.h" | 25 #include "wtf/HashTable.h" |
26 | 26 |
27 namespace WTF { | 27 namespace WTF { |
28 | 28 |
29 struct IdentityExtractor; | 29 struct IdentityExtractor; |
30 | 30 |
31 template<typename Value, typename HashFunctions, typename Traits> class Hash
Set; | 31 template<typename Value, typename HashFunctions, typename Traits> class Hash
Set; |
32 template<typename Value, typename HashFunctions, typename Traits> | 32 template<typename Value, typename HashFunctions, typename Traits> |
33 void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&); | 33 void deleteAllValues(const HashSet<Value, HashFunctions, Traits>&); |
34 | 34 |
35 template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg
>::Hash, | 35 template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg
>::Hash, |
36 typename TraitsArg = HashTraits<ValueArg> > class HashSet { | 36 typename TraitsArg = HashTraits<ValueArg> > class HashSet { |
37 WTF_MAKE_FAST_ALLOCATED; | 37 WTF_MAKE_FAST_ALLOCATED; |
38 private: | 38 private: |
39 typedef HashArg HashFunctions; | 39 typedef HashArg HashFunctions; |
40 typedef TraitsArg ValueTraits; | 40 typedef TraitsArg ValueTraits; |
(...skipping 23 matching lines...) Expand all Loading... |
64 bool contains(const ValueType&) const; | 64 bool contains(const ValueType&) const; |
65 | 65 |
66 // An alternate version of find() that finds the object by hashing and c
omparing | 66 // An alternate version of find() that finds the object by hashing and c
omparing |
67 // with some other type, to avoid the cost of type conversion. HashTrans
lator | 67 // with some other type, to avoid the cost of type conversion. HashTrans
lator |
68 // must have the following function members: | 68 // must have the following function members: |
69 // static unsigned hash(const T&); | 69 // static unsigned hash(const T&); |
70 // static bool equal(const ValueType&, const T&); | 70 // static bool equal(const ValueType&, const T&); |
71 template<typename HashTranslator, typename T> iterator find(const T&) co
nst; | 71 template<typename HashTranslator, typename T> iterator find(const T&) co
nst; |
72 template<typename HashTranslator, typename T> bool contains(const T&) co
nst; | 72 template<typename HashTranslator, typename T> bool contains(const T&) co
nst; |
73 | 73 |
74 // The return value is a pair of an interator to the new value's locatio
n, | 74 // The return value is a pair of an interator to the new value's locatio
n, |
75 // and a bool that is true if an new entry was added. | 75 // and a bool that is true if an new entry was added. |
76 AddResult add(const ValueType&); | 76 AddResult add(const ValueType&); |
77 | 77 |
78 // An alternate version of add() that finds the object by hashing and co
mparing | 78 // An alternate version of add() that finds the object by hashing and co
mparing |
79 // with some other type, to avoid the cost of type conversion if the obj
ect is already | 79 // with some other type, to avoid the cost of type conversion if the obj
ect is already |
80 // in the table. HashTranslator must have the following function members
: | 80 // in the table. HashTranslator must have the following function members
: |
81 // static unsigned hash(const T&); | 81 // static unsigned hash(const T&); |
82 // static bool equal(const ValueType&, const T&); | 82 // static bool equal(const ValueType&, const T&); |
83 // static translate(ValueType&, const T&, unsigned hashCode); | 83 // static translate(ValueType&, const T&, unsigned hashCode); |
84 template<typename HashTranslator, typename T> AddResult add(const T&); | 84 template<typename HashTranslator, typename T> AddResult add(const T&); |
(...skipping 20 matching lines...) Expand all Loading... |
105 template<typename T, typename U> static bool equal(const T& a, const U&
b) { return Translator::equal(a, b); } | 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, cons
t U& key, const U&, unsigned hashCode) | 106 template<typename T, typename U> static void translate(T& location, cons
t U& key, const U&, unsigned hashCode) |
107 { | 107 { |
108 Translator::translate(location, key, hashCode); | 108 Translator::translate(location, key, hashCode); |
109 } | 109 } |
110 }; | 110 }; |
111 | 111 |
112 template<typename T, typename U, typename V> | 112 template<typename T, typename U, typename V> |
113 inline void HashSet<T, U, V>::swap(HashSet& other) | 113 inline void HashSet<T, U, V>::swap(HashSet& other) |
114 { | 114 { |
115 m_impl.swap(other.m_impl); | 115 m_impl.swap(other.m_impl); |
116 } | 116 } |
117 | 117 |
118 template<typename T, typename U, typename V> | 118 template<typename T, typename U, typename V> |
119 inline int HashSet<T, U, V>::size() const | 119 inline int HashSet<T, U, V>::size() const |
120 { | 120 { |
121 return m_impl.size(); | 121 return m_impl.size(); |
122 } | 122 } |
123 | 123 |
124 template<typename T, typename U, typename V> | 124 template<typename T, typename U, typename V> |
125 inline int HashSet<T, U, V>::capacity() const | 125 inline int HashSet<T, U, V>::capacity() const |
126 { | 126 { |
127 return m_impl.capacity(); | 127 return m_impl.capacity(); |
128 } | 128 } |
129 | 129 |
130 template<typename T, typename U, typename V> | 130 template<typename T, typename U, typename V> |
131 inline bool HashSet<T, U, V>::isEmpty() const | 131 inline bool HashSet<T, U, V>::isEmpty() const |
132 { | 132 { |
133 return m_impl.isEmpty(); | 133 return m_impl.isEmpty(); |
134 } | 134 } |
135 | 135 |
136 template<typename T, typename U, typename V> | 136 template<typename T, typename U, typename V> |
137 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const | 137 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const |
138 { | 138 { |
139 return m_impl.begin(); | 139 return m_impl.begin(); |
140 } | 140 } |
141 | 141 |
142 template<typename T, typename U, typename V> | 142 template<typename T, typename U, typename V> |
143 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const | 143 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const |
144 { | 144 { |
145 return m_impl.end(); | 145 return m_impl.end(); |
146 } | 146 } |
147 | 147 |
148 template<typename T, typename U, typename V> | 148 template<typename T, typename U, typename V> |
149 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const Valu
eType& value) const | 149 inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const Valu
eType& value) const |
150 { | 150 { |
151 return m_impl.find(value); | 151 return m_impl.find(value); |
152 } | 152 } |
153 | 153 |
154 template<typename T, typename U, typename V> | 154 template<typename T, typename U, typename V> |
155 inline bool HashSet<T, U, V>::contains(const ValueType& value) const | 155 inline bool HashSet<T, U, V>::contains(const ValueType& value) const |
156 { | 156 { |
157 return m_impl.contains(value); | 157 return m_impl.contains(value); |
158 } | 158 } |
159 | 159 |
160 template<typename Value, typename HashFunctions, typename Traits> | 160 template<typename Value, typename HashFunctions, typename Traits> |
161 template<typename HashTranslator, typename T> | 161 template<typename HashTranslator, typename T> |
162 typename HashSet<Value, HashFunctions, Traits>::iterator | 162 typename HashSet<Value, HashFunctions, Traits>::iterator |
163 inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const | 163 inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const |
164 { | 164 { |
165 return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(v
alue); | 165 return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(v
alue); |
166 } | 166 } |
167 | 167 |
(...skipping 29 matching lines...) Expand all Loading... |
197 | 197 |
198 template<typename T, typename U, typename V> | 198 template<typename T, typename U, typename V> |
199 inline void HashSet<T, U, V>::remove(const ValueType& value) | 199 inline void HashSet<T, U, V>::remove(const ValueType& value) |
200 { | 200 { |
201 remove(find(value)); | 201 remove(find(value)); |
202 } | 202 } |
203 | 203 |
204 template<typename T, typename U, typename V> | 204 template<typename T, typename U, typename V> |
205 inline void HashSet<T, U, V>::clear() | 205 inline void HashSet<T, U, V>::clear() |
206 { | 206 { |
207 m_impl.clear(); | 207 m_impl.clear(); |
208 } | 208 } |
209 | 209 |
210 template<typename T, typename U, typename V> | 210 template<typename T, typename U, typename V> |
211 inline bool HashSet<T, U, V>::isValidValue(const ValueType& value) | 211 inline bool HashSet<T, U, V>::isValidValue(const ValueType& value) |
212 { | 212 { |
213 if (ValueTraits::isDeletedValue(value)) | 213 if (ValueTraits::isDeletedValue(value)) |
214 return false; | 214 return false; |
215 | 215 |
216 if (HashFunctions::safeToCompareToEmptyOrDeleted) { | 216 if (HashFunctions::safeToCompareToEmptyOrDeleted) { |
217 if (value == ValueTraits::emptyValue()) | 217 if (value == ValueTraits::emptyValue()) |
(...skipping 18 matching lines...) Expand all Loading... |
236 template<typename T, typename U, typename V> | 236 template<typename T, typename U, typename V> |
237 inline void deleteAllValues(const HashSet<T, U, V>& collection) | 237 inline void deleteAllValues(const HashSet<T, U, V>& collection) |
238 { | 238 { |
239 deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl)
; | 239 deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl)
; |
240 } | 240 } |
241 | 241 |
242 template<typename C, typename W> | 242 template<typename C, typename W> |
243 inline void copyToVector(const C& collection, W& vector) | 243 inline void copyToVector(const C& collection, W& vector) |
244 { | 244 { |
245 typedef typename C::const_iterator iterator; | 245 typedef typename C::const_iterator iterator; |
246 | 246 |
247 vector.resize(collection.size()); | 247 vector.resize(collection.size()); |
248 | 248 |
249 iterator it = collection.begin(); | 249 iterator it = collection.begin(); |
250 iterator end = collection.end(); | 250 iterator end = collection.end(); |
251 for (unsigned i = 0; it != end; ++it, ++i) | 251 for (unsigned i = 0; it != end; ++it, ++i) |
252 vector[i] = *it; | 252 vector[i] = *it; |
253 } | 253 } |
254 | 254 |
255 } // namespace WTF | 255 } // namespace WTF |
256 | 256 |
257 using WTF::HashSet; | 257 using WTF::HashSet; |
258 | 258 |
259 #endif /* WTF_HashSet_h */ | 259 #endif /* WTF_HashSet_h */ |
OLD | NEW |