← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/3rdparty/javascriptcore/JavaScriptCore/wtf/HashSet.h

  • Committer: Bazaar Package Importer
  • Author(s): Alessandro Ghersi
  • Date: 2009-11-02 18:30:08 UTC
  • mfrom: (1.2.2 upstream)
  • mto: (15.2.5 experimental)
  • mto: This revision was merged to the branch mainline in revision 88.
  • Revision ID: james.westby@ubuntu.com-20091102183008-b6a4gcs128mvfb3m
Tags: upstream-4.6.0~beta1
Import upstream version 4.6.0~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/3rdparty/javascriptcore/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
        pair<typename HashTable<T, T, IdentityExtractor<T>, U, V, V>::iterator, bool> p = m_impl.add(value);
 
211
        typename HashSet<T, U, V>::iterator temp = p.first;
 
212
        pair<typename HashSet<T, U, V>::iterator, bool> p2 = make_pair<typename HashSet<T, U, V>::iterator, bool>(temp, p.second);
 
213
 //       p2.first = p.first;
 
214
 //       p2.second = p.second;
 
215
        return p2;
 
216
    }
 
217
 
 
218
    template<typename Value, typename HashFunctions, typename Traits>
 
219
    template<typename T, typename HashTranslator>
 
220
    pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
 
221
    HashSet<Value, HashFunctions, Traits>::add(const T& value)
 
222
    {
 
223
        typedef HashSetTranslatorAdapter<ValueType, ValueTraits, T, HashTranslator> Adapter;
 
224
        pair<typename HashTableType::iterator, bool> p = m_impl.template addPassingHashCode<T, T, Adapter>(value, value);
 
225
        return make_pair<iterator, bool>(p.first, p.second);
 
226
    }
 
227
 
 
228
    template<typename T, typename U, typename V>
 
229
    inline void HashSet<T, U, V>::remove(iterator it)
 
230
    {
 
231
        if (it.m_impl == m_impl.end())
 
232
            return;
 
233
        m_impl.checkTableConsistency();
 
234
        m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
 
235
    }
 
236
 
 
237
    template<typename T, typename U, typename V>
 
238
    inline void HashSet<T, U, V>::remove(const ValueType& value)
 
239
    {
 
240
        remove(find(value));
 
241
    }
 
242
 
 
243
    template<typename T, typename U, typename V>
 
244
    inline void HashSet<T, U, V>::clear()
 
245
    {
 
246
        m_impl.clear(); 
 
247
    }
 
248
 
 
249
    template<typename ValueType, typename HashTableType>
 
250
    void deleteAllValues(HashTableType& collection)
 
251
    {
 
252
        typedef typename HashTableType::const_iterator iterator;
 
253
        iterator end = collection.end();
 
254
        for (iterator it = collection.begin(); it != end; ++it)
 
255
            delete *it;
 
256
    }
 
257
 
 
258
    template<typename T, typename U, typename V>
 
259
    inline void deleteAllValues(const HashSet<T, U, V>& collection)
 
260
    {
 
261
        deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
 
262
    }
 
263
 
 
264
    template<typename ValueType, typename HashTableType>
 
265
    void fastDeleteAllValues(HashTableType& collection)
 
266
    {
 
267
        typedef typename HashTableType::const_iterator iterator;
 
268
        iterator end = collection.end();
 
269
        for (iterator it = collection.begin(); it != end; ++it)
 
270
            fastDelete(*it);
 
271
    }
 
272
 
 
273
    template<typename T, typename U, typename V>
 
274
    inline void fastDeleteAllValues(const HashSet<T, U, V>& collection)
 
275
    {
 
276
        fastDeleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
 
277
    }
 
278
    
 
279
    template<typename T, typename U, typename V, typename W>
 
280
    inline void copyToVector(const HashSet<T, U, V>& collection, W& vector)
 
281
    {
 
282
        typedef typename HashSet<T, U, V>::const_iterator iterator;
 
283
        
 
284
        vector.resize(collection.size());
 
285
        
 
286
        iterator it = collection.begin();
 
287
        iterator end = collection.end();
 
288
        for (unsigned i = 0; it != end; ++it, ++i)
 
289
            vector[i] = *it;
 
290
    }  
 
291
 
 
292
} // namespace WTF
 
293
 
 
294
using WTF::HashSet;
 
295
 
 
296
#endif /* WTF_HashSet_h */