HashSet.h revision 231d4e3152a9c27a73b6ac7badbe6be673aa3ddf 
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
27namespace 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
288using WTF::HashSet;
289
290#endif /* WTF_HashSet_h */
291