f4e2cf7e376640d8e7ed9b32caf6c373bc15837d
[WebKit-https.git] / JavaScriptCore / wtf / HashSet.h
1 /*
2  * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
3  *
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.
8  *
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.
13  *
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.
18  *
19  */
20
21 #ifndef WTF_HashSet_h
22 #define WTF_HashSet_h
23
24 #include "FastAllocBase.h"
25 #include "HashTable.h"
26
27 namespace WTF {
28
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>&);
34
35     template<typename T> struct IdentityExtractor;
36
37     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
38         typename TraitsArg = HashTraits<ValueArg> > class HashSet : public FastAllocBase {
39     private:
40         typedef HashArg HashFunctions;
41         typedef TraitsArg ValueTraits;
42
43     public:
44         typedef typename ValueTraits::TraitType ValueType;
45
46     private:
47         typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
48             HashFunctions, ValueTraits, ValueTraits> HashTableType;
49
50     public:
51         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
52         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
53
54         void swap(HashSet&);
55
56         int size() const;
57         int capacity() const;
58         bool isEmpty() const;
59
60         iterator begin();
61         iterator end();
62         const_iterator begin() const;
63         const_iterator end() const;
64
65         iterator find(const ValueType&);
66         const_iterator find(const ValueType&) const;
67         bool contains(const ValueType&) const;
68
69         // An alternate version of find() that finds the object by hashing and comparing
70         // with some other type, to avoid the cost of type conversion. HashTranslator
71         // must have the following function members:
72         //   static unsigned hash(const T&);
73         //   static bool equal(const ValueType&, const T&);
74         template<typename T, typename HashTranslator> iterator find(const T&);
75         template<typename T, typename HashTranslator> const_iterator find(const T&) const;
76         template<typename T, typename HashTranslator> bool contains(const T&) const;
77
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         pair<iterator, bool> add(const ValueType&);
81
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 methods:
85         //   static unsigned hash(const T&);
86         //   static bool equal(const ValueType&, const T&);
87         //   static translate(ValueType&, const T&, unsigned hashCode);
88         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
89
90         void remove(const ValueType&);
91         void remove(iterator);
92         void clear();
93
94     private:
95         friend void deleteAllValues<>(const HashSet&);
96         friend void fastDeleteAllValues<>(const HashSet&);
97
98         HashTableType m_impl;
99     };
100
101     template<typename T> struct IdentityExtractor {
102         static const T& extract(const T& t) { return t; }
103     };
104
105     template<typename ValueType, typename ValueTraits, typename T, typename Translator>
106     struct HashSetTranslatorAdapter {
107         static unsigned hash(const T& key) { return Translator::hash(key); }
108         static bool equal(const ValueType& a, const T& b) { return Translator::equal(a, b); }
109         static void translate(ValueType& location, const T& key, const T&, unsigned hashCode)
110         {
111             Translator::translate(location, key, hashCode);
112         }
113     };
114
115     template<typename T, typename U, typename V>
116     inline void HashSet<T, U, V>::swap(HashSet& other)
117     {
118         m_impl.swap(other.m_impl); 
119     }
120
121     template<typename T, typename U, typename V>
122     inline int HashSet<T, U, V>::size() const
123     {
124         return m_impl.size(); 
125     }
126
127     template<typename T, typename U, typename V>
128     inline int HashSet<T, U, V>::capacity() const
129     {
130         return m_impl.capacity(); 
131     }
132
133     template<typename T, typename U, typename V>
134     inline bool HashSet<T, U, V>::isEmpty() const
135     {
136         return m_impl.isEmpty(); 
137     }
138
139     template<typename T, typename U, typename V>
140     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
141     {
142         return m_impl.begin(); 
143     }
144
145     template<typename T, typename U, typename V>
146     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
147     {
148         return m_impl.end(); 
149     }
150
151     template<typename T, typename U, typename V>
152     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
153     {
154         return m_impl.begin(); 
155     }
156
157     template<typename T, typename U, typename V>
158     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
159     {
160         return m_impl.end(); 
161     }
162
163     template<typename T, typename U, typename V>
164     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
165     {
166         return m_impl.find(value); 
167     }
168
169     template<typename T, typename U, typename V>
170     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
171     {
172         return m_impl.find(value); 
173     }
174
175     template<typename T, typename U, typename V>
176     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
177     {
178         return m_impl.contains(value); 
179     }
180
181     template<typename Value, typename HashFunctions, typename Traits>
182     template<typename T, typename HashTranslator>
183     typename HashSet<Value, HashFunctions, Traits>::iterator
184     inline HashSet<Value, HashFunctions, Traits>::find(const T& value)
185     {
186         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
187         return m_impl.template find<T, Adapter>(value);
188     }
189
190     template<typename Value, typename HashFunctions, typename Traits>
191     template<typename T, typename HashTranslator>
192     typename HashSet<Value, HashFunctions, Traits>::const_iterator
193     inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
194     {
195         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
196         return m_impl.template find<T, Adapter>(value);
197     }
198
199     template<typename Value, typename HashFunctions, typename Traits>
200     template<typename T, typename HashTranslator>
201     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
202     {
203         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
204         return m_impl.template contains<T, Adapter>(value);
205     }
206
207     template<typename T, typename U, typename V>
208     pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value)
209     {
210         return m_impl.add(value);
211     }
212
213     template<typename Value, typename HashFunctions, typename Traits>
214     template<typename T, typename HashTranslator>
215     pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
216     HashSet<Value, HashFunctions, Traits>::add(const T& value)
217     {
218         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
219         return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
220     }
221
222     template<typename T, typename U, typename V>
223     inline void HashSet<T, U, V>::remove(iterator it)
224     {
225         if (it.m_impl == m_impl.end())
226             return;
227         m_impl.checkTableConsistency();
228         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
229     }
230
231     template<typename T, typename U, typename V>
232     inline void HashSet<T, U, V>::remove(const ValueType& value)
233     {
234         remove(find(value));
235     }
236
237     template<typename T, typename U, typename V>
238     inline void HashSet<T, U, V>::clear()
239     {
240         m_impl.clear(); 
241     }
242
243     template<typename ValueType, typename HashTableType>
244     void deleteAllValues(HashTableType& collection)
245     {
246         typedef typename HashTableType::const_iterator iterator;
247         iterator end = collection.end();
248         for (iterator it = collection.begin(); it != end; ++it)
249             delete *it;
250     }
251
252     template<typename T, typename U, typename V>
253     inline void deleteAllValues(const HashSet<T, U, V>& collection)
254     {
255         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
256     }
257
258     template<typename ValueType, typename HashTableType>
259     void fastDeleteAllValues(HashTableType& collection)
260     {
261         typedef typename HashTableType::const_iterator iterator;
262         iterator end = collection.end();
263         for (iterator it = collection.begin(); it != end; ++it)
264             fastDelete(*it);
265     }
266
267     template<typename T, typename U, typename V>
268     inline void fastDeleteAllValues(const HashSet<T, U, V>& collection)
269     {
270         fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
271     }
272     
273     template<typename T, typename U, typename V, typename W>
274     inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
275     {
276         typedef typename HashSet<T, U, V>::const_iterator iterator;
277         
278         vector.resize(collection.size());
279         
280         iterator it = collection.begin();
281         iterator end = collection.end();
282         for (unsigned i = 0; it != end; ++it, ++i)
283             vector[i] = *it;
284     }  
285
286 } // namespace WTF
287
288 using WTF::HashSet;
289
290 #endif /* WTF_HashSet_h */