cd4de5c3ca3314a4f64a79a9579e7f6474a315af
[WebKit-https.git] / JavaScriptCore / kxmlcore / HashMap.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_MAP_H
25 #define KXMLCORE_HASH_MAP_H
26
27 #include "HashTable.h"
28
29 namespace KXMLCore {
30
31     template<typename PairType> struct PairFirstExtractor;
32
33     template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
34         typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > class HashMap {
35     private:
36         typedef KeyTraitsArg KeyTraits;
37         typedef MappedTraitsArg MappedTraits;
38         typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
39
40     public:
41         typedef typename KeyTraits::TraitType KeyType;
42         typedef typename MappedTraits::TraitType MappedType;
43         typedef typename ValueTraits::TraitType ValueType;
44
45     private:
46         typedef HashArg HashFunctions;
47
48         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
49
50         typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
51         typedef typename MappedTraits::StorageTraits MappedStorageTraits;
52         typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
53
54         typedef typename KeyStorageTraits::TraitType KeyStorageType;
55         typedef typename MappedStorageTraits::TraitType MappedStorageType;
56         typedef typename ValueStorageTraits::TraitType ValueStorageType;
57
58         typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
59             StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
60
61     public:
62         typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
63         typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
64
65         HashMap();
66         HashMap(const HashMap&);
67         HashMap& operator=(const HashMap&);
68         ~HashMap();
69
70         int size() const;
71         int capacity() const;
72         bool isEmpty() const;
73
74         // iterators iterate over pairs of keys and values
75         iterator begin();
76         iterator end();
77         const_iterator begin() const;
78         const_iterator end() const;
79
80         iterator find(const KeyType&);
81         const_iterator find(const KeyType&) const;
82         bool contains(const KeyType&) const;
83         MappedType get(const KeyType&) const;
84
85         // replaces value but not key if key is already present
86         // return value is a pair of the iterator to the key location, 
87         // and a boolean that's true if a new value was actually added
88         pair<iterator, bool> set(const KeyType&, const MappedType&); 
89
90         // does nothing if key is already present
91         // return value is a pair of the iterator to the key location, 
92         // and a boolean that's true if a new value was actually added
93         pair<iterator, bool> add(const KeyType&, const MappedType&); 
94
95         void remove(const KeyType&);
96         void remove(iterator it);
97         void clear();
98
99     private:
100         pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
101         void refAll();
102         void derefAll();
103
104         HashTableType m_impl;
105     };
106
107     template<typename PairType> struct PairFirstExtractor {
108         static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
109     };
110
111     template<bool canReplaceDeletedKey, typename ValueType, typename ValueStorageTraits, typename HashFunctions>
112     struct HashMapTranslator;
113
114     template<typename ValueType, typename ValueStorageTraits, typename HashFunctions>
115     struct HashMapTranslator<true, ValueType, ValueStorageTraits, HashFunctions> {
116         typedef typename ValueType::first_type KeyType;
117         typedef typename ValueType::second_type MappedType;
118         typedef typename ValueStorageTraits::TraitType ValueStorageType;
119         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
120         typedef typename KeyStorageTraits::TraitType KeyStorageType;
121
122         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
123         static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
124         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
125         {
126             *(KeyType*)&location.first = key;
127             *(MappedType*)&location.second = mapped;
128         }
129     };
130
131     template<typename ValueType, typename ValueStorageTraits, typename HashFunctions>
132     struct HashMapTranslator<false, ValueType, ValueStorageTraits, HashFunctions> {
133         typedef typename ValueType::first_type KeyType;
134         typedef typename ValueType::second_type MappedType;
135         typedef typename ValueStorageTraits::TraitType ValueStorageType;
136         typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
137         typedef typename KeyStorageTraits::TraitType KeyStorageType;
138
139         static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
140         static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
141         static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
142         {
143             if (location.first == KeyStorageTraits::deletedValue())
144                 location.first = KeyStorageTraits::emptyValue();
145             *(KeyType*)&location.first = key;
146             *(MappedType*)&location.second = mapped;
147         }
148     };
149
150     template<typename T, typename U, typename V, typename W, typename X>
151     inline void HashMap<T, U, V, W, X>::refAll()
152     {
153         HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
154     }
155
156     template<typename T, typename U, typename V, typename W, typename X>
157     inline void HashMap<T, U, V, W, X>::derefAll()
158     {
159         HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
160     }
161
162     template<typename T, typename U, typename V, typename W, typename X>
163     inline HashMap<T, U, V, W, X>::HashMap()
164     {
165     }
166
167     template<typename T, typename U, typename V, typename W, typename X>
168     inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)
169         : m_impl(other.m_impl)
170     {
171         refAll();
172     }
173
174     template<typename T, typename U, typename V, typename W, typename X>
175     inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)
176     {
177         HashMap tmp(other);
178         m_impl.swap(tmp.m_impl); 
179     }
180
181     template<typename T, typename U, typename V, typename W, typename X>
182     inline HashMap<T, U, V, W, X>::~HashMap()
183     {
184         derefAll();
185     }
186
187     template<typename T, typename U, typename V, typename W, typename X>
188     inline int HashMap<T, U, V, W, X>::size() const
189     {
190         return m_impl.size(); 
191     }
192
193     template<typename T, typename U, typename V, typename W, typename X>
194     inline int HashMap<T, U, V, W, X>::capacity() const
195     { 
196         return m_impl.capacity(); 
197     }
198
199     template<typename T, typename U, typename V, typename W, typename X>
200     inline bool HashMap<T, U, V, W, X>::isEmpty() const
201     {
202         return m_impl.isEmpty();
203     }
204
205     template<typename T, typename U, typename V, typename W, typename X>
206     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
207     {
208         return m_impl.begin();
209     }
210
211     template<typename T, typename U, typename V, typename W, typename X>
212     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
213     {
214         return m_impl.end();
215     }
216
217     template<typename T, typename U, typename V, typename W, typename X>
218     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
219     {
220         return m_impl.begin();
221     }
222
223     template<typename T, typename U, typename V, typename W, typename X>
224     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
225     {
226         return m_impl.end();
227     }
228
229     template<typename T, typename U, typename V, typename W, typename X>
230     inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
231     {
232         return m_impl.find(*(const KeyStorageType*)&key);
233     }
234
235     template<typename T, typename U, typename V, typename W, typename X>
236     inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
237     {
238         return m_impl.find(*(const KeyStorageType*)&key);
239     }
240
241     template<typename T, typename U, typename V, typename W, typename X>
242     inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
243     {
244         return m_impl.contains(*(const KeyStorageType*)&key);
245     }
246
247     template<typename T, typename U, typename V, typename W, typename X>
248     inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
249     HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped) 
250     {
251         const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
252         typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueStorageTraits, HashFunctions> TranslatorType;
253         return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
254     }
255
256     template<typename T, typename U, typename V, typename W, typename X>
257     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
258     HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped) 
259     {
260         pair<iterator, bool> result = inlineAdd(key, mapped);
261         if (!result.second)
262             // add call above didn't change anything, so set the mapped value
263             result.first->second = mapped;
264         return result;
265     }
266
267     template<typename T, typename U, typename V, typename W, typename X>
268     pair<typename HashMap<T, U, V, W, X>::iterator, bool>
269     HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
270     {
271         return inlineAdd(key, mapped);
272     }
273
274     template<typename T, typename U, typename V, typename W, typename MappedTraits>
275     inline typename HashMap<T, U, V, W, MappedTraits>::MappedType
276     HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
277     {
278         const_iterator it = find(key);
279         if (it == end())
280             return MappedTraits::emptyValue();
281         return it->second;
282     }
283
284     template<typename T, typename U, typename V, typename W, typename X>
285     inline void HashMap<T, U, V, W, X>::remove(iterator it)
286     {
287         if (it.m_impl == m_impl.end())
288             return;
289         // Use "(*it)." instead of "it->" to work around a problem seen with the Visual C++ compiler.
290         (*it).~ValueType();
291         m_impl.remove(it.m_impl);
292     }
293
294     template<typename T, typename U, typename V, typename W, typename X>
295     inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
296     {
297         remove(find(key));
298     }
299
300     template<typename T, typename U, typename V, typename W, typename X>
301     inline void HashMap<T, U, V, W, X>::clear()
302     {
303         derefAll();
304         m_impl.clear();
305     }
306
307     template<typename MappedType, typename HashTableType>
308     void deleteAllPairSeconds(HashTableType& collection)
309     {
310         typedef typename HashTableType::iterator iterator;
311         iterator end = collection.end();
312         for (iterator it = collection.begin(); it != end; ++it)
313             delete *(MappedType*)&it->second;
314     }
315
316     template<typename T, typename U, typename V, typename W, typename X>
317     inline void deleteAllValues(HashMap<T, U, V, W, X>& collection)
318     {
319         deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
320     }
321
322 } // namespace KXMLCore
323
324 using KXMLCore::HashMap;
325
326 #endif /* KXMLCORE_HASH_MAP_H */