2 * Copyright (C) 2005, 2006, 2007, 2008, 2011 Apple Inc. All rights reserved.
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.
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.
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.
24 #include <wtf/HashTable.h>
28 template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits;
30 template<typename T> struct ReferenceTypeMaker {
31 typedef T& ReferenceType;
33 template<typename T> struct ReferenceTypeMaker<T&> {
34 typedef T& ReferenceType;
37 template<typename T> struct KeyValuePairKeyExtractor {
38 static const typename T::KeyType& extract(const T& p) { return p.first; }
41 template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
42 typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> >
44 WTF_MAKE_FAST_ALLOCATED;
46 typedef KeyTraitsArg KeyTraits;
47 typedef MappedTraitsArg MappedTraits;
48 typedef HashMapValueTraits<KeyTraits, MappedTraits> ValueTraits;
51 typedef typename KeyTraits::TraitType KeyType;
52 typedef typename MappedTraits::TraitType MappedType;
53 typedef typename ValueTraits::TraitType ValueType;
56 typedef typename MappedTraits::PassInType MappedPassInType;
57 typedef typename MappedTraits::PassOutType MappedPassOutType;
58 typedef typename MappedTraits::PeekType MappedPeekType;
60 typedef typename ReferenceTypeMaker<MappedPassInType>::ReferenceType MappedPassInReferenceType;
62 typedef HashArg HashFunctions;
64 typedef HashTable<KeyType, ValueType, KeyValuePairKeyExtractor<ValueType>,
65 HashFunctions, ValueTraits, KeyTraits> HashTableType;
67 class HashMapKeysProxy;
68 class HashMapValuesProxy;
71 typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
72 typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
73 typedef typename HashTableType::AddResult AddResult;
82 // iterators iterate over pairs of keys and values
85 const_iterator begin() const;
86 const_iterator end() const;
88 HashMapKeysProxy& keys() { return static_cast<HashMapKeysProxy&>(*this); }
89 const HashMapKeysProxy& keys() const { return static_cast<const HashMapKeysProxy&>(*this); }
91 HashMapValuesProxy& values() { return static_cast<HashMapValuesProxy&>(*this); }
92 const HashMapValuesProxy& values() const { return static_cast<const HashMapValuesProxy&>(*this); }
94 iterator find(const KeyType&);
95 const_iterator find(const KeyType&) const;
96 bool contains(const KeyType&) const;
97 MappedPeekType get(const KeyType&) const;
99 // replaces value but not key if key is already present
100 // return value is a pair of the iterator to the key location,
101 // and a boolean that's true if a new value was actually added
102 AddResult set(const KeyType&, MappedPassInType);
104 // does nothing if key is already present
105 // return value is a pair of the iterator to the key location,
106 // and a boolean that's true if a new value was actually added
107 AddResult add(const KeyType&, MappedPassInType);
109 void remove(const KeyType&);
110 void remove(iterator);
113 MappedPassOutType take(const KeyType&); // efficient combination of get with remove
115 // An alternate version of find() that finds the object by hashing and comparing
116 // with some other type, to avoid the cost of type conversion. HashTranslator
117 // must have the following function members:
118 // static unsigned hash(const T&);
119 // static bool equal(const ValueType&, const T&);
120 template<typename T, typename HashTranslator> iterator find(const T&);
121 template<typename T, typename HashTranslator> const_iterator find(const T&) const;
122 template<typename T, typename HashTranslator> bool contains(const T&) const;
124 // An alternate version of add() that finds the object by hashing and comparing
125 // with some other type, to avoid the cost of type conversion if the object is already
126 // in the table. HashTranslator must have the following function members:
127 // static unsigned hash(const T&);
128 // static bool equal(const ValueType&, const T&);
129 // static translate(ValueType&, const T&, unsigned hashCode);
130 template<typename T, typename HashTranslator> AddResult add(const T&, MappedPassInType);
132 void checkConsistency() const;
135 AddResult inlineAdd(const KeyType&, MappedPassInReferenceType);
137 class HashMapKeysProxy : private HashMap {
139 typedef typename HashMap::iterator::Keys iterator;
140 typedef typename HashMap::const_iterator::Keys const_iterator;
144 return HashMap::begin().keys();
149 return HashMap::end().keys();
152 const_iterator begin() const
154 return HashMap::begin().keys();
157 const_iterator end() const
159 return HashMap::end().keys();
163 friend class HashMap;
165 // These are intentionally not implemented.
167 HashMapKeysProxy(const HashMapKeysProxy&);
168 HashMapKeysProxy& operator=(const HashMapKeysProxy&);
172 class HashMapValuesProxy : private HashMap {
174 typedef typename HashMap::iterator::Values iterator;
175 typedef typename HashMap::const_iterator::Values const_iterator;
179 return HashMap::begin().values();
184 return HashMap::end().values();
187 const_iterator begin() const
189 return HashMap::begin().values();
192 const_iterator end() const
194 return HashMap::end().values();
198 friend class HashMap;
200 // These are intentionally not implemented.
201 HashMapValuesProxy();
202 HashMapValuesProxy(const HashMapValuesProxy&);
203 HashMapValuesProxy& operator=(const HashMapValuesProxy&);
204 ~HashMapValuesProxy();
207 HashTableType m_impl;
210 template<typename KeyTraits, typename MappedTraits> struct HashMapValueTraits : KeyValuePairHashTraits<KeyTraits, MappedTraits> {
211 static const bool hasIsEmptyValueFunction = true;
212 static bool isEmptyValue(const typename KeyValuePairHashTraits<KeyTraits, MappedTraits>::TraitType& value)
214 return isHashTraitsEmptyValue<KeyTraits>(value.first);
218 template<typename ValueTraits, typename HashFunctions>
219 struct HashMapTranslator {
220 template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); }
221 template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); }
222 template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped)
224 location.first = key;
225 ValueTraits::ValueTraits::store(mapped, location.second);
229 template<typename ValueTraits, typename Translator>
230 struct HashMapTranslatorAdapter {
231 template<typename T> static unsigned hash(const T& key) { return Translator::hash(key); }
232 template<typename T, typename U> static bool equal(const T& a, const U& b) { return Translator::equal(a, b); }
233 template<typename T, typename U, typename V> static void translate(T& location, const U& key, const V& mapped, unsigned hashCode)
235 Translator::translate(location.first, key, hashCode);
236 ValueTraits::ValueTraits::store(mapped, location.second);
240 template<typename T, typename U, typename V, typename W, typename X>
241 inline void HashMap<T, U, V, W, X>::swap(HashMap& other)
243 m_impl.swap(other.m_impl);
246 template<typename T, typename U, typename V, typename W, typename X>
247 inline int HashMap<T, U, V, W, X>::size() const
249 return m_impl.size();
252 template<typename T, typename U, typename V, typename W, typename X>
253 inline int HashMap<T, U, V, W, X>::capacity() const
255 return m_impl.capacity();
258 template<typename T, typename U, typename V, typename W, typename X>
259 inline bool HashMap<T, U, V, W, X>::isEmpty() const
261 return m_impl.isEmpty();
264 template<typename T, typename U, typename V, typename W, typename X>
265 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
267 return m_impl.begin();
270 template<typename T, typename U, typename V, typename W, typename X>
271 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
276 template<typename T, typename U, typename V, typename W, typename X>
277 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
279 return m_impl.begin();
282 template<typename T, typename U, typename V, typename W, typename X>
283 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
288 template<typename T, typename U, typename V, typename W, typename X>
289 inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
291 return m_impl.find(key);
294 template<typename T, typename U, typename V, typename W, typename X>
295 inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
297 return m_impl.find(key);
300 template<typename T, typename U, typename V, typename W, typename X>
301 inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
303 return m_impl.contains(key);
306 template<typename T, typename U, typename V, typename W, typename X>
307 template<typename TYPE, typename HashTranslator>
308 inline typename HashMap<T, U, V, W, X>::iterator
309 HashMap<T, U, V, W, X>::find(const TYPE& value)
311 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value);
314 template<typename T, typename U, typename V, typename W, typename X>
315 template<typename TYPE, typename HashTranslator>
316 inline typename HashMap<T, U, V, W, X>::const_iterator
317 HashMap<T, U, V, W, X>::find(const TYPE& value) const
319 return m_impl.template find<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value);
322 template<typename T, typename U, typename V, typename W, typename X>
323 template<typename TYPE, typename HashTranslator>
325 HashMap<T, U, V, W, X>::contains(const TYPE& value) const
327 return m_impl.template contains<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(value);
330 template<typename T, typename U, typename V, typename W, typename X>
331 typename HashMap<T, U, V, W, X>::AddResult
332 HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, MappedPassInReferenceType mapped)
334 return m_impl.template add<HashMapTranslator<ValueTraits, HashFunctions> >(key, mapped);
337 template<typename T, typename U, typename V, typename W, typename X>
338 typename HashMap<T, U, V, W, X>::AddResult
339 HashMap<T, U, V, W, X>::set(const KeyType& key, MappedPassInType mapped)
341 AddResult result = inlineAdd(key, mapped);
342 if (!result.isNewEntry) {
343 // The inlineAdd call above found an existing hash table entry; we need to set the mapped value.
344 MappedTraits::store(mapped, result.iterator->second);
349 template<typename T, typename U, typename V, typename W, typename X>
350 template<typename TYPE, typename HashTranslator>
351 typename HashMap<T, U, V, W, X>::AddResult
352 HashMap<T, U, V, W, X>::add(const TYPE& key, MappedPassInType value)
354 return m_impl.template addPassingHashCode<HashMapTranslatorAdapter<ValueTraits, HashTranslator> >(key, value);
357 template<typename T, typename U, typename V, typename W, typename X>
358 typename HashMap<T, U, V, W, X>::AddResult
359 HashMap<T, U, V, W, X>::add(const KeyType& key, MappedPassInType mapped)
361 return inlineAdd(key, mapped);
364 template<typename T, typename U, typename V, typename W, typename MappedTraits>
365 typename HashMap<T, U, V, W, MappedTraits>::MappedPeekType
366 HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
368 ValueType* entry = const_cast<HashTableType&>(m_impl).lookup(key);
370 return MappedTraits::peek(MappedTraits::emptyValue());
371 return MappedTraits::peek(entry->second);
374 template<typename T, typename U, typename V, typename W, typename X>
375 inline void HashMap<T, U, V, W, X>::remove(iterator it)
377 if (it.m_impl == m_impl.end())
379 m_impl.internalCheckTableConsistency();
380 m_impl.removeWithoutEntryConsistencyCheck(it.m_impl);
383 template<typename T, typename U, typename V, typename W, typename X>
384 inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
389 template<typename T, typename U, typename V, typename W, typename X>
390 inline void HashMap<T, U, V, W, X>::clear()
395 template<typename T, typename U, typename V, typename W, typename MappedTraits>
396 typename HashMap<T, U, V, W, MappedTraits>::MappedPassOutType
397 HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key)
399 iterator it = find(key);
401 return MappedTraits::passOut(MappedTraits::emptyValue());
402 MappedPassOutType result = MappedTraits::passOut(it->second);
407 template<typename T, typename U, typename V, typename W, typename X>
408 inline void HashMap<T, U, V, W, X>::checkConsistency() const
410 m_impl.checkTableConsistency();
413 template<typename T, typename U, typename V, typename W, typename X>
414 bool operator==(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
416 if (a.size() != b.size())
419 typedef typename HashMap<T, U, V, W, X>::const_iterator const_iterator;
421 const_iterator end = a.end();
422 const_iterator notFound = b.end();
423 for (const_iterator it = a.begin(); it != end; ++it) {
424 const_iterator bPos = b.find(it->first);
425 if (bPos == notFound || it->second != bPos->second)
432 template<typename T, typename U, typename V, typename W, typename X>
433 inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W, X>& b)
438 template<typename HashTableType>
439 void deleteAllPairSeconds(HashTableType& collection)
441 typedef typename HashTableType::const_iterator iterator;
442 iterator end = collection.end();
443 for (iterator it = collection.begin(); it != end; ++it)
447 template<typename T, typename U, typename V, typename W, typename X>
448 inline void deleteAllValues(const HashMap<T, U, V, W, X>& collection)
450 deleteAllPairSeconds(collection);
453 template<typename HashTableType>
454 void deleteAllPairFirsts(HashTableType& collection)
456 typedef typename HashTableType::const_iterator iterator;
457 iterator end = collection.end();
458 for (iterator it = collection.begin(); it != end; ++it)
462 template<typename T, typename U, typename V, typename W, typename X>
463 inline void deleteAllKeys(const HashMap<T, U, V, W, X>& collection)
465 deleteAllPairFirsts(collection);
468 template<typename T, typename U, typename V, typename W, typename X, typename Y>
469 inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
471 typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator;
473 vector.resize(collection.size());
475 iterator it = collection.begin().keys();
476 iterator end = collection.end().keys();
477 for (unsigned i = 0; it != end; ++it, ++i)
481 template<typename T, typename U, typename V, typename W, typename X, typename Y>
482 inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vector)
484 typedef typename HashMap<T, U, V, W, X>::const_iterator::Values iterator;
486 vector.resize(collection.size());
488 iterator it = collection.begin().values();
489 iterator end = collection.end().values();
490 for (unsigned i = 0; it != end; ++it, ++i)
498 #include <wtf/RefPtrHashMap.h>
500 #endif /* WTF_HashMap_h */