← Back to branch summary

~ubuntu-branches/ubuntu/raring/qtwebkit-source/raring-proposed

« back to all changes in this revision

Viewing changes to Source/WTF/wtf/HashSet.h

  • Committer: Package Import Robot
  • Author(s): Jonathan Riddell
  • Date: 2013-02-18 14:24:18 UTC
  • Revision ID: package-import@ubuntu.com-20130218142418-eon0jmjg3nj438uy
Tags: upstream-2.3
Import upstream version 2.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
Source/WTF/wtf/HashSet.h
 
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
 
 
27
namespace 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
        int size() const;
 
57
        int 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
        // FIXME: We should reverse the order of the template arguments so that callers
 
72
        // can just pass the translator and let the compiler deduce T.
 
73
        template<typename T, typename HashTranslator> 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
        AddResult 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 function members:
 
83
        //   static unsigned hash(const T&);
 
84
        //   static bool equal(const ValueType&, const T&);
 
85
        //   static translate(ValueType&, const T&, unsigned hashCode);
 
86
        // FIXME: We should reverse the order of the template arguments so that callers
 
87
        // can just pass the translator and let the compiler deduce T.
 
88
        template<typename T, typename HashTranslator> AddResult 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
 
 
97
        HashTableType m_impl;
 
98
    };
 
99
 
 
100
    struct IdentityExtractor {
 
101
        template<typename T> static const T& extract(const T& t) { return t; }
 
102
    };
 
103
 
 
104
    template<typename Translator>
 
105
    struct HashSetTranslatorAdapter {
 
106
        template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
 
107
        template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
 
108
        template<typename T, typename U> static void translate(T& location, const U& key, const U&, unsigned hashCode)
 
109
        {
 
110
            Translator::translate(location, key, hashCode);
 
111
        }
 
112
    };
 
113
 
 
114
    template<typename T, typename U, typename V>
 
115
    inline void HashSet<T, U, V>::swap(HashSet& other)
 
116
    {
 
117
        m_impl.swap(other.m_impl); 
 
118
    }
 
119
 
 
120
    template<typename T, typename U, typename V>
 
121
    inline int HashSet<T, U, V>::size() const
 
122
    {
 
123
        return m_impl.size(); 
 
124
    }
 
125
 
 
126
    template<typename T, typename U, typename V>
 
127
    inline int HashSet<T, U, V>::capacity() const
 
128
    {
 
129
        return m_impl.capacity(); 
 
130
    }
 
131
 
 
132
    template<typename T, typename U, typename V>
 
133
    inline bool HashSet<T, U, V>::isEmpty() const
 
134
    {
 
135
        return m_impl.isEmpty(); 
 
136
    }
 
137
 
 
138
    template<typename T, typename U, typename V>
 
139
    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin() const
 
140
    {
 
141
        return m_impl.begin(); 
 
142
    }
 
143
 
 
144
    template<typename T, typename U, typename V>
 
145
    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end() const
 
146
    {
 
147
        return m_impl.end(); 
 
148
    }
 
149
 
 
150
    template<typename T, typename U, typename V>
 
151
    inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value) const
 
152
    {
 
153
        return m_impl.find(value); 
 
154
    }
 
155
 
 
156
    template<typename T, typename U, typename V>
 
157
    inline bool HashSet<T, U, V>::contains(const ValueType& value) const
 
158
    {
 
159
        return m_impl.contains(value); 
 
160
    }
 
161
 
 
162
    template<typename Value, typename HashFunctions, typename Traits>
 
163
    template<typename T, typename HashTranslator>
 
164
    typename HashSet<Value, HashFunctions, Traits>::iterator
 
165
    inline HashSet<Value, HashFunctions, Traits>::find(const T& value) const
 
166
    {
 
167
        return m_impl.template find<HashSetTranslatorAdapter<HashTranslator> >(value);
 
168
    }
 
169
 
 
170
    template<typename Value, typename HashFunctions, typename Traits>
 
171
    template<typename T, typename HashTranslator>
 
172
    inline bool HashSet<Value, HashFunctions, Traits>::contains(const T& value) const
 
173
    {
 
174
        return m_impl.template contains<HashSetTranslatorAdapter<HashTranslator> >(value);
 
175
    }
 
176
 
 
177
    template<typename T, typename U, typename V>
 
178
    inline typename HashSet<T, U, V>::AddResult HashSet<T, U, V>::add(const ValueType& value)
 
179
    {
 
180
        return m_impl.add(value);
 
181
    }
 
182
 
 
183
    template<typename Value, typename HashFunctions, typename Traits>
 
184
    template<typename T, typename HashTranslator>
 
185
    inline typename HashSet<Value, HashFunctions, Traits>::AddResult
 
186
    HashSet<Value, HashFunctions, Traits>::add(const T& value)
 
187
    {
 
188
        return m_impl.template addPassingHashCode<HashSetTranslatorAdapter<HashTranslator> >(value, value);
 
189
    }
 
190
 
 
191
    template<typename T, typename U, typename V>
 
192
    inline void HashSet<T, U, V>::remove(iterator it)
 
193
    {
 
194
        if (it.m_impl == m_impl.end())
 
195
            return;
 
196
        m_impl.internalCheckTableConsistency();
 
197
        m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
 
198
    }
 
199
 
 
200
    template<typename T, typename U, typename V>
 
201
    inline void HashSet<T, U, V>::remove(const ValueType& value)
 
202
    {
 
203
        remove(find(value));
 
204
    }
 
205
 
 
206
    template<typename T, typename U, typename V>
 
207
    inline void HashSet<T, U, V>::clear()
 
208
    {
 
209
        m_impl.clear(); 
 
210
    }
 
211
 
 
212
    template<typename ValueType, typename HashTableType>
 
213
    void deleteAllValues(HashTableType& collection)
 
214
    {
 
215
        typedef typename HashTableType::const_iterator iterator;
 
216
        iterator end = collection.end();
 
217
        for (iterator it = collection.begin(); it != end; ++it)
 
218
            delete *it;
 
219
    }
 
220
 
 
221
    template<typename T, typename U, typename V>
 
222
    inline void deleteAllValues(const HashSet<T, U, V>& collection)
 
223
    {
 
224
        deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
 
225
    }
 
226
 
 
227
    template<typename T, typename U, typename V, typename W>
 
228
    inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
 
229
    {
 
230
        typedef typename HashSet<T, U, V>::const_iterator iterator;
 
231
        
 
232
        vector.resize(collection.size());
 
233
        
 
234
        iterator it = collection.begin();
 
235
        iterator end = collection.end();
 
236
        for (unsigned i = 0; it != end; ++it, ++i)
 
237
            vector[i] = *it;
 
238
    }  
 
239
 
 
240
} // namespace WTF
 
241
 
 
242
using WTF::HashSet;
 
243
 
 
244
#endif /* WTF_HashSet_h */