- attempt to fix Windows build
[WebKit-https.git] / JavaScriptCore / kxmlcore / HashSet.h
1 // -*- mode: c++; c-basic-offset: 4 -*-
2 /*
3  * This file is part of the KDE libraries
4  *
5  * Copyright (C) 2005, 2006 Apple Computer, Inc.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Library General Public
9  * License as published by the Free Software Foundation; either
10  * version 2 of the License, or (at your option) any later version.
11  *
12  * This library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  * Library General Public License for more details.
16  *
17  * You should have received a copy of the GNU Library General Public License
18  * along with this library; see the file COPYING.LIB.  If not, write to
19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  * Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #ifndef KXMLCORE_HASH_SET_H
25 #define KXMLCORE_HASH_SET_H
26
27 #include "HashTable.h"
28
29 namespace KXMLCore {
30
31     template<typename T> struct IdentityExtractor;
32
33     template<typename Value, typename HashFunctions, typename Traits> class HashSet;
34     template<typename Value, typename HashFunctions, typename Traits>
35     void deleteAllValues(HashSet<Value, HashFunctions, Traits>&);
36
37     template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
38         typename TraitsArg = HashTraits<ValueArg> > class HashSet {
39     private:
40         typedef HashArg HashFunctions;
41         typedef TraitsArg ValueTraits;
42
43         typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Hash StorageHashFunctions;
44
45         typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Traits StorageTraits;
46         typedef typename StorageTraits::TraitType StorageType;
47
48         typedef HashTable<StorageType, StorageType, IdentityExtractor<StorageType>,
49             StorageHashFunctions, StorageTraits, StorageTraits> HashTableType;
50
51     public:
52         typedef typename ValueTraits::TraitType ValueType;
53         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
54         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
55
56         HashSet();
57         HashSet(const HashSet&);
58         HashSet& operator=(const HashSet&);
59         ~HashSet();
60
61         int size() const;
62         int capacity() const;
63         bool isEmpty() const;
64
65         iterator begin();
66         iterator end();
67         const_iterator begin() const;
68         const_iterator end() const;
69
70         iterator find(const ValueType&);
71         const_iterator find(const ValueType&) const;
72         bool contains(const ValueType&) 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         pair<iterator, bool> add(const ValueType&);
77
78         // a special 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 should have the following methods:
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 T, typename HashTranslator> pair<iterator, bool> add(const T&);
85
86         void remove(const ValueType&);
87         void remove(iterator);
88         void clear();
89
90     private:
91         void refAll();
92         void derefAll();
93
94         friend void deleteAllValues<>(HashSet&);
95
96         HashTableType m_impl;
97     };
98
99     template<typename T> struct IdentityExtractor {
100         static const T& extract(const T& t) { return t; }
101     };
102
103     template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename HashFunctions>
104     struct HashSetTranslator;
105
106     template<typename ValueType, typename StorageTraits, typename HashFunctions>
107     struct HashSetTranslator<true, ValueType, StorageTraits, HashFunctions> {
108         typedef typename StorageTraits::TraitType StorageType;
109         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
110         static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
111         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
112         {
113             *(ValueType*)&location = key;
114         }
115     };
116
117     template<typename ValueType, typename StorageTraits, typename HashFunctions>
118     struct HashSetTranslator<false, ValueType, StorageTraits, HashFunctions> {
119         typedef typename StorageTraits::TraitType StorageType;
120         static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
121         static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
122         static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
123         {
124             if (location == StorageTraits::deletedValue())
125                 location = StorageTraits::emptyValue();
126             *(ValueType*)&location = key;
127         }
128     };
129
130     template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename T, typename Translator>
131     struct HashSetTranslatorAdapter;
132
133     template<typename ValueType, typename StorageTraits, typename T, typename Translator>
134     struct HashSetTranslatorAdapter<true, ValueType, StorageTraits, T, Translator> {
135         typedef typename StorageTraits::TraitType StorageType;
136         static unsigned hash(const T& key) { return Translator::hash(key); }
137         static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
138         static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
139         {
140             Translator::translate(*(ValueType*)&location, key, hashCode);
141         }
142     };
143
144     template<typename ValueType, typename StorageTraits, typename T, typename Translator>
145     struct HashSetTranslatorAdapter<false, ValueType, StorageTraits, T, Translator> {
146         typedef typename StorageTraits::TraitType StorageType;
147         static unsigned hash(const T& key) { return Translator::hash(key); }
148         static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
149         static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
150         {
151             if (location == StorageTraits::deletedValue())
152                 location = StorageTraits::emptyValue();
153             Translator::translate(*(ValueType*)&location, key, hashCode);
154         }
155     };
156
157     template<typename T, typename U, typename V>
158     inline void HashSet<T, U, V>::refAll()
159     {
160         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
161     }
162
163     template<typename T, typename U, typename V>
164     inline void HashSet<T, U, V>::derefAll()
165     {
166         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
167     }
168
169     template<typename T, typename U, typename V>
170     inline HashSet<T, U, V>::HashSet()
171     {
172     }
173
174     template<typename T, typename U, typename V>
175     inline HashSet<T, U, V>::HashSet(const HashSet& other)
176         : m_impl(other.m_impl)
177     {
178         refAll();
179     }
180
181     template<typename T, typename U, typename V>
182     inline HashSet<T, U, V>& HashSet<T, U, V>::operator=(const HashSet& other)
183     {
184         HashSet tmp(other);
185         m_impl.swap(tmp.m_impl); 
186     }
187
188     template<typename T, typename U, typename V>
189     inline HashSet<T, U, V>::~HashSet()
190     {
191         derefAll();
192     }
193
194     template<typename T, typename U, typename V>
195     inline int HashSet<T, U, V>::size() const
196     {
197         return m_impl.size(); 
198     }
199
200     template<typename T, typename U, typename V>
201     inline int HashSet<T, U, V>::capacity() const
202     {
203         return m_impl.capacity(); 
204     }
205
206     template<typename T, typename U, typename V>
207     inline bool HashSet<T, U, V>::isEmpty() const
208     {
209         return m_impl.isEmpty(); 
210     }
211
212     template<typename T, typename U, typename V>
213     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
214     {
215         return m_impl.begin(); 
216     }
217
218     template<typename T, typename U, typename V>
219     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::end()
220     {
221         return m_impl.end(); 
222     }
223
224     template<typename T, typename U, typename V>
225     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::begin() const
226     {
227         return m_impl.begin(); 
228     }
229
230     template<typename T, typename U, typename V>
231     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::end() const
232     {
233         return m_impl.end(); 
234     }
235
236     template<typename T, typename U, typename V>
237     inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
238     {
239         return m_impl.find(*(const StorageType*)&value); 
240     }
241
242     template<typename T, typename U, typename V>
243     inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
244     {
245         return m_impl.find(*(const StorageType*)&value); 
246     }
247
248     template<typename T, typename U, typename V>
249     inline bool HashSet<T, U, V>::contains(const ValueType& value) const
250     {
251         return m_impl.contains(*(const StorageType*)&value); 
252     }
253
254     template<typename T, typename U, typename V>
255     pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value)
256     {
257         const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
258         typedef HashSetTranslator<canReplaceDeletedValue, ValueType, StorageTraits, HashFunctions> Translator;
259         return m_impl.template add<ValueType, ValueType, Translator>(value, value);
260     }
261
262     template<typename Value, typename HashFunctions, typename Traits>
263     template<typename T, typename Translator> 
264     pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
265     HashSet<Value, HashFunctions, Traits>::add(const T& value)
266     {
267         const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
268         typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;
269         return m_impl.template add<T, T, Adapter>(value, value);
270     }
271
272     template<typename T, typename U, typename V>
273     inline void HashSet<T, U, V>::remove(iterator it)
274     {
275         if (it.m_impl == m_impl.end())
276             return;
277         // Use "(*it)." instead of "it->" to work around a problem seen with the Visual C++ compiler.
278         (*it).~ValueType();
279         m_impl.remove(it.m_impl);
280     }
281
282     template<typename T, typename U, typename V>
283     inline void HashSet<T, U, V>::remove(const ValueType& value)
284     {
285         remove(find(value));
286     }
287
288     template<typename T, typename U, typename V>
289     inline void HashSet<T, U, V>::clear()
290     {
291         derefAll();
292         m_impl.clear(); 
293     }
294
295     template<typename ValueType, typename HashTableType>
296     void deleteAllValues(HashTableType& collection)
297     {
298         typedef typename HashTableType::iterator iterator;
299         iterator end = collection.end();
300         for (iterator it = collection.begin(); it != end; ++it)
301             delete *(ValueType*)&*it;
302     }
303
304     template<typename T, typename U, typename V>
305     inline void deleteAllValues(HashSet<T, U, V>& collection)
306     {
307         deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
308     }
309
310 } // namespace KXMLCore
311
312 using KXMLCore::HashSet;
313
314 #endif /* KXMLCORE_HASH_SET_H */