1/*
2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 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 "wtf/FastAllocBase.h"
25#include "wtf/HashTable.h"
26
27namespace WTF {
28
29    struct IdentityExtractor;
30
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>&);
34
35    template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
36        typename TraitsArg = HashTraits<ValueArg> > class HashSet {
37        WTF_MAKE_FAST_ALLOCATED;
38    private:
39        typedef HashArg HashFunctions;
40        typedef TraitsArg ValueTraits;
41
42    public:
43        typedef typename ValueTraits::TraitType ValueType;
44
45    private:
46        typedef HashTable<ValueType, ValueType, IdentityExtractor,
47            HashFunctions, ValueTraits, ValueTraits> HashTableType;
48
49    public:
50        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> iterator;
51        typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
52        typedef typename HashTableType::AddResult AddResult;
53
54        void swap(HashSet&);
55
56        unsigned size() const;
57        unsigned capacity() const;
58        bool isEmpty() const;
59
60        iterator begin() const;
61        iterator end() const;
62
63        iterator find(const ValueType&) const;
64        bool contains(const ValueType&) const;
65
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;
73
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&);
77
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&);
85
86        void remove(const ValueType&);
87        void remove(iterator);
88        void clear();
89
90        static bool isValidValue(const ValueType&);
91
92    private:
93        friend void deleteAllValues<>(const HashSet&);
94
95        HashTableType m_impl;
96    };
97
98    struct IdentityExtractor {
99        template<typename T> static const T& extract(const T& t) { return t; }
100    };
101
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)
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 unsigned HashSet<T, U, V>::size() const
120    {
121        return m_impl.size();
122    }
123
124    template<typename T, typename U, typename V>
125    inline unsigned 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() const
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() const
144    {
145        return m_impl.end();
146    }
147
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
150    {
151        return m_impl.find(value);
152    }
153
154    template<typename T, typename U, typename V>
155    inline bool HashSet<T, U, V>::contains(const ValueType& value) const
156    {
157        return m_impl.contains(value);
158    }
159
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
164    {
165        return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(value);
166    }
167
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
171    {
172        return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator> >(value);
173    }
174
175    template<typename T, typename U, typename V>
176    inline typename HashSet<T, U, V>::AddResult HashSet<T, U, V>::add(const ValueType& value)
177    {
178        return m_impl.add(value);
179    }
180
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)
185    {
186        return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator> >(value, value);
187    }
188
189    template<typename T, typename U, typename V>
190    inline void HashSet<T, U, V>::remove(iterator it)
191    {
192        m_impl.remove(it.m_impl);
193    }
194
195    template<typename T, typename U, typename V>
196    inline void HashSet<T, U, V>::remove(const ValueType& value)
197    {
198        remove(find(value));
199    }
200
201    template<typename T, typename U, typename V>
202    inline void HashSet<T, U, V>::clear()
203    {
204        m_impl.clear();
205    }
206
207    template<typename T, typename U, typename V>
208    inline bool HashSet<T, U, V>::isValidValue(const ValueType& value)
209    {
210        if (ValueTraits::isDeletedValue(value))
211            return false;
212
213        if (HashFunctions::safeToCompareToEmptyOrDeleted) {
214            if (value == ValueTraits::emptyValue())
215                return false;
216        } else {
217            if (isHashTraitsEmptyValue<ValueTraits>(value))
218                return false;
219        }
220
221        return true;
222    }
223
224    template<typename ValueType, typename HashTableType>
225    void deleteAllValues(HashTableType& collection)
226    {
227        typedef typename HashTableType::const_iterator iterator;
228        iterator end = collection.end();
229        for (iterator it = collection.begin(); it != end; ++it)
230            delete *it;
231    }
232
233    template<typename T, typename U, typename V>
234    inline void deleteAllValues(const HashSet<T, U, V>& collection)
235    {
236        deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
237    }
238
239    template<typename C, typename W>
240    inline void copyToVector(const C& collection, W& vector)
241    {
242        typedef typename C::const_iterator iterator;
243
244        vector.resize(collection.size());
245
246        iterator it = collection.begin();
247        iterator end = collection.end();
248        for (unsigned i = 0; it != end; ++it, ++i)
249            vector[i] = *it;
250    }
251
252} // namespace WTF
253
254using WTF::HashSet;
255
256#endif /* WTF_HashSet_h */
257