990670d4efdf26d3890b88f231b9883394acde31
[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
33     template<typename T> struct IdentityExtractor;
34
35     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
36         typename TraitsArg = HashTraits<ValueArg> > class HashSet : public FastAllocBase {
37     private:
38         typedef HashArg HashFunctions;
39         typedef TraitsArg ValueTraits;
40
41     public:
42         typedef typename ValueTraits::TraitType ValueType;
43
44     private:
45         typedef HashTable<ValueType, ValueType, IdentityExtractor<ValueType>,
46             HashFunctions, ValueTraits, ValueTraits> HashTableType;
47
48     public:
49         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
50         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
51
52         void swap(HashSet&);
53
54         int size() const;
55         int capacity() const;
56         bool isEmpty() const;
57
58         iterator begin();
59         iterator end();
60         const_iterator begin() const;
61         const_iterator end() const;
62
63         iterator find(const ValueType&);
64         const_iterator find(const ValueType&) const;
65         bool contains(const ValueType&) const;
66
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&);
73         template<typename T, typename HashTranslator> const_iterator find(const T&) const;
74         template<typename T, typename HashTranslator> bool contains(const T&) const;
75
76         // The return value is a pair of an interator to the new value's location, 
77         // and a bool that is true if an new entry was added.
78         pair<iterator, bool> add(const ValueType&);
79
80         // An alternate version of add() that finds the object by hashing and comparing
81         // with some other type, to avoid the cost of type conversion if the object is already
82         // in the table. HashTranslator must have the following methods:
83         //   static unsigned hash(const T&);
84         //   static bool equal(const ValueType&, const T&);
85         //   static translate(ValueType&, const T&, unsigned hashCode);
86         template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
87
88         void remove(const ValueType&);
89         void remove(iterator);
90         void clear();
91
92     private:
93         friend void deleteAllValues<>(const HashSet&);
94
95         HashTableType m_impl;
96     };
97
98     template<typename T> struct IdentityExtractor {
99         static const T& extract(const T& t) { return t; }
100     };
101
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)
107         {
108             Translator::translate(location, key, hashCode);
109         }
110     };
111
112     template<typename T, typename U, typename V>
113     inline void HashSet<T, U, V>::swap(HashSet& other)
114     {
115         m_impl.swap(other.m_impl); 
116     }
117
118     template<typename T, typename U, typename V>
119     inline int HashSet<T, U, V>::size() const
120     {
121         return m_impl.size(); 
122     }
123
124     template<typename T, typename U, typename V>
125     inline int HashSet<T, U, V>::capacity() const
126     {
127         return m_impl.capacity(); 
128     }
129
130     template<typename T, typename U, typename V>
131     inline bool HashSet<T, U, V>::isEmpty() const
132     {
133         return m_impl.isEmpty(); 
134     }
135
136     template<typename T, typename U, typename V>
137     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
138     {
139         return m_impl.begin(); 
140     }
141
142     template<typename T, typename U, typename V>
143     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
144     {
145         return m_impl.end(); 
146     }
147
148     template<typename T, typename U, typename V>
149     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
150     {
151         return m_impl.begin(); 
152     }
153
154     template<typename T, typename U, typename V>
155     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
156     {
157         return m_impl.end(); 
158     }
159
160     template<typename T, typename U, typename V>
161     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
162     {
163         return m_impl.find(value); 
164     }
165
166     template<typename T, typename U, typename V>
167     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
168     {
169         return m_impl.find(value); 
170     }
171
172     template<typename T, typename U, typename V>
173     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
174     {
175         return m_impl.contains(value); 
176     }
177
178     template<typename Value, typename HashFunctions, typename Traits>
179     template<typename T, typename HashTranslator>
180     typename HashSet<Value, HashFunctions, Traits>::iterator
181     inline HashSet<Value, HashFunctions, Traits>::find(const T& value)
182     {
183         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
184         return m_impl.template find<T, Adapter>(value);
185     }
186
187     template<typename Value, typename HashFunctions, typename Traits>
188     template<typename T, typename HashTranslator>
189     typename HashSet<Value, HashFunctions, Traits>::const_iterator
190     inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
191     {
192         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
193         return m_impl.template find<T, Adapter>(value);
194     }
195
196     template<typename Value, typename HashFunctions, typename Traits>
197     template<typename T, typename HashTranslator>
198     inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
199     {
200         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
201         return m_impl.template contains<T, Adapter>(value);
202     }
203
204     template<typename T, typename U, typename V>
205     pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType& value)
206     {
207         return m_impl.add(value);
208     }
209
210     template<typename Value, typename HashFunctions, typename Traits>
211     template<typename T, typename HashTranslator>
212     pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
213     HashSet<Value, HashFunctions, Traits>::add(const T& value)
214     {
215         typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
216         return m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
217     }
218
219     template<typename T, typename U, typename V>
220     inline void HashSet<T, U, V>::remove(iterator it)
221     {
222         if (it.m_impl == m_impl.end())
223             return;
224         m_impl.checkTableConsistency();
225         m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
226     }
227
228     template<typename T, typename U, typename V>
229     inline void HashSet<T, U, V>::remove(const ValueType& value)
230     {
231         remove(find(value));
232     }
233
234     template<typename T, typename U, typename V>
235     inline void HashSet<T, U, V>::clear()
236     {
237         m_impl.clear(); 
238     }
239
240     template<typename ValueType, typename HashTableType>
241     void deleteAllValues(HashTableType& collection)
242     {
243         typedef typename HashTableType::const_iterator iterator;
244         iterator end = collection.end();
245         for (iterator it = collection.begin(); it != end; ++it)
246             delete *it;
247     }
248
249     template<typename T, typename U, typename V>
250     inline void deleteAllValues(const HashSet<T, U, V>& collection)
251     {
252         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
253     }
254     
255     template<typename T, typename U, typename V, typename W>
256     inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
257     {
258         typedef typename HashSet<T, U, V>::const_iterator iterator;
259         
260         vector.resize(collection.size());
261         
262         iterator it = collection.begin();
263         iterator end = collection.end();
264         for (unsigned i = 0; it != end; ++it, ++i)
265             vector[i] = *it;
266     }  
267
268 } // namespace WTF
269
270 using WTF::HashSet;
271
272 #endif /* WTF_HashSet_h */