diff options
author | Lorry Tar Creator <lorry-tar-importer@lorry> | 2017-06-27 06:07:23 +0000 |
---|---|---|
committer | Lorry Tar Creator <lorry-tar-importer@lorry> | 2017-06-27 06:07:23 +0000 |
commit | 1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c (patch) | |
tree | 46dcd36c86e7fbc6e5df36deb463b33e9967a6f7 /Source/WTF/wtf/HashMap.h | |
parent | 32761a6cee1d0dee366b885b7b9c777e67885688 (diff) | |
download | WebKitGtk-tarball-master.tar.gz |
webkitgtk-2.16.5HEADwebkitgtk-2.16.5master
Diffstat (limited to 'Source/WTF/wtf/HashMap.h')
-rw-r--r-- | Source/WTF/wtf/HashMap.h | 187 |
1 files changed, 171 insertions, 16 deletions
diff --git a/Source/WTF/wtf/HashMap.h b/Source/WTF/wtf/HashMap.h index be3001403..53c40f303 100644 --- a/Source/WTF/wtf/HashMap.h +++ b/Source/WTF/wtf/HashMap.h @@ -33,7 +33,7 @@ template<typename T> struct KeyValuePairKeyExtractor { template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash, typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg>> -class HashMap { +class HashMap final { WTF_MAKE_FAST_ALLOCATED; private: typedef KeyTraitsArg KeyTraits; @@ -54,6 +54,7 @@ public: private: typedef typename MappedTraits::PeekType MappedPeekType; + typedef typename MappedTraits::TakeType MappedTakeType; typedef HashArg HashFunctions; @@ -81,8 +82,8 @@ public: void swap(HashMap&); - int size() const; - int capacity() const; + unsigned size() const; + unsigned capacity() const; bool isEmpty() const; // iterators iterate over pairs of keys and values @@ -102,6 +103,9 @@ public: bool contains(const KeyType&) const; MappedPeekType get(const KeyType&) const; + // Same as get(), but aggressively inlined. + MappedPeekType fastGet(const KeyType&) const; + // Replaces the value but not the key if the key is already present. // Return value includes both an iterator to the key location, // and an isNewEntry boolean that's true if a new entry was added. @@ -114,11 +118,20 @@ public: template<typename V> AddResult add(const KeyType&, V&&); template<typename V> AddResult add(KeyType&&, V&&); + // Same as add(), but aggressively inlined. + template<typename V> AddResult fastAdd(const KeyType&, V&&); + template<typename V> AddResult fastAdd(KeyType&&, V&&); + + template<typename Functor> AddResult ensure(const KeyType&, Functor&&); + template<typename Functor> AddResult ensure(KeyType&&, Functor&&); + bool remove(const KeyType&); bool remove(iterator); + template<typename Functor> + void removeIf(Functor&&); void clear(); - MappedType take(const KeyType&); // efficient combination of get with remove + MappedTakeType take(const KeyType&); // efficient combination of get with remove // An alternate version of find() that finds the object by hashing and comparing // with some other type, to avoid the cost of type conversion. HashTranslator @@ -137,6 +150,15 @@ public: // static translate(ValueType&, const T&, unsigned hashCode); template<typename HashTranslator, typename K, typename V> AddResult add(K&&, V&&); + // Overloads for smart pointer keys that take the raw pointer type as the parameter. + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, iterator>::type find(typename GetPtrHelper<K>::PtrType); + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, const_iterator>::type find(typename GetPtrHelper<K>::PtrType) const; + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, bool>::type contains(typename GetPtrHelper<K>::PtrType) const; + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type inlineGet(typename GetPtrHelper<K>::PtrType) const; + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type get(typename GetPtrHelper<K>::PtrType) const; + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, bool>::type remove(typename GetPtrHelper<K>::PtrType); + template<typename K = KeyType> typename std::enable_if<IsSmartPtr<K>::value, MappedTakeType>::type take(typename GetPtrHelper<K>::PtrType); + void checkConsistency() const; static bool isValidKey(const KeyType&); @@ -148,6 +170,9 @@ private: template<typename K, typename V> AddResult inlineAdd(K&&, V&&); + template<typename K, typename F> + AddResult inlineEnsure(K&&, F&&); + HashTableType m_impl; }; @@ -157,8 +182,19 @@ struct HashMapTranslator { template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } template<typename T, typename U, typename V> static void translate(T& location, U&& key, V&& mapped) { - location.key = std::forward<U>(key); - location.value = std::forward<V>(mapped); + ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward<U>(key)); + ValueTraits::ValueTraits::assignToEmpty(location.value, std::forward<V>(mapped)); + } +}; + +template<typename ValueTraits, typename HashFunctions> +struct HashMapEnsureTranslator { + template<typename T> static unsigned hash(const T& key) { return HashFunctions::hash(key); } + template<typename T, typename U> static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } + template<typename T, typename U, typename Functor> static void translate(T& location, U&& key, Functor&& functor) + { + ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward<U>(key)); + ValueTraits::ValueTraits::assignToEmpty(location.value, functor()); } }; @@ -180,13 +216,13 @@ inline void HashMap<T, U, V, W, X>::swap(HashMap& other) } template<typename T, typename U, typename V, typename W, typename X> -inline int HashMap<T, U, V, W, X>::size() const +inline unsigned HashMap<T, U, V, W, X>::size() const { return m_impl.size(); } template<typename T, typename U, typename V, typename W, typename X> -inline int HashMap<T, U, V, W, X>::capacity() const +inline unsigned HashMap<T, U, V, W, X>::capacity() const { return m_impl.capacity(); } @@ -276,12 +312,19 @@ auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineS template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> template<typename K, typename V> -auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineAdd(K&& key, V&& value) -> AddResult +ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineAdd(K&& key, V&& value) -> AddResult { return m_impl.template add<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(std::forward<K>(key), std::forward<V>(value)); } template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> +template<typename K, typename F> +ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::inlineEnsure(K&& key, F&& functor) -> AddResult +{ + return m_impl.template add<HashMapEnsureTranslator<KeyValuePairTraits, HashFunctions>>(std::forward<K>(key), std::forward<F>(functor)); +} + +template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> template<typename T> auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(const KeyType& key, T&& mapped) -> AddResult { @@ -292,7 +335,7 @@ template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTrai template<typename T> auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::set(KeyType&& key, T&& mapped) -> AddResult { - return inlineSet(std::move(key), std::forward<T>(mapped)); + return inlineSet(WTFMove(key), std::forward<T>(mapped)); } template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> @@ -313,9 +356,37 @@ template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTrai template<typename T> auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::add(KeyType&& key, T&& mapped) -> AddResult { - return inlineAdd(std::move(key), std::forward<T>(mapped)); + return inlineAdd(WTFMove(key), std::forward<T>(mapped)); +} + +template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> +template<typename T> +ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::fastAdd(const KeyType& key, T&& mapped) -> AddResult +{ + return inlineAdd(key, std::forward<T>(mapped)); +} + +template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> +template<typename T> +ALWAYS_INLINE auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::fastAdd(KeyType&& key, T&& mapped) -> AddResult +{ + return inlineAdd(WTFMove(key), std::forward<T>(mapped)); +} + +template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> +template<typename Functor> +auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(const KeyType& key, Functor&& functor) -> AddResult +{ + return inlineEnsure(key, std::forward<Functor>(functor)); } +template<typename KeyArg, typename MappedArg, typename HashArg, typename KeyTraitsArg, typename MappedTraitsArg> +template<typename Functor> +auto HashMap<KeyArg, MappedArg, HashArg, KeyTraitsArg, MappedTraitsArg>::ensure(KeyType&& key, Functor&& functor) -> AddResult +{ + return inlineEnsure(std::forward<KeyType>(key), std::forward<Functor>(functor)); +} + template<typename T, typename U, typename V, typename W, typename MappedTraits> auto HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const -> MappedPeekType { @@ -325,6 +396,15 @@ auto HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const -> MappedP return MappedTraits::peek(entry->value); } +template<typename T, typename U, typename V, typename W, typename MappedTraits> +ALWAYS_INLINE auto HashMap<T, U, V, W, MappedTraits>::fastGet(const KeyType& key) const -> MappedPeekType +{ + KeyValuePairType* entry = const_cast<HashTableType&>(m_impl).template inlineLookup<typename HashTableType::IdentityTranslatorType>(key); + if (!entry) + return MappedTraits::peek(MappedTraits::emptyValue()); + return MappedTraits::peek(entry->value); +} + template<typename T, typename U, typename V, typename W, typename X> inline bool HashMap<T, U, V, W, X>::remove(iterator it) { @@ -336,6 +416,13 @@ inline bool HashMap<T, U, V, W, X>::remove(iterator it) } template<typename T, typename U, typename V, typename W, typename X> +template<typename Functor> +inline void HashMap<T, U, V, W, X>::removeIf(Functor&& functor) +{ + m_impl.removeIf(std::forward<Functor>(functor)); +} + +template<typename T, typename U, typename V, typename W, typename X> inline bool HashMap<T, U, V, W, X>::remove(const KeyType& key) { return remove(find(key)); @@ -348,12 +435,69 @@ inline void HashMap<T, U, V, W, X>::clear() } template<typename T, typename U, typename V, typename W, typename MappedTraits> -auto HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) -> MappedType +auto HashMap<T, U, V, W, MappedTraits>::take(const KeyType& key) -> MappedTakeType +{ + iterator it = find(key); + if (it == end()) + return MappedTraits::take(MappedTraits::emptyValue()); + auto value = MappedTraits::take(WTFMove(it->value)); + remove(it); + return value; +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +inline auto HashMap<T, U, V, W, X>::find(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, iterator>::type +{ + return m_impl.template find<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key); +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +inline auto HashMap<T, U, V, W, X>::find(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, const_iterator>::type +{ + return m_impl.template find<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key); +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +inline auto HashMap<T, U, V, W, X>::contains(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, bool>::type +{ + return m_impl.template contains<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key); +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +inline auto HashMap<T, U, V, W, X>::inlineGet(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type +{ + KeyValuePairType* entry = const_cast<HashTableType&>(m_impl).template inlineLookup<HashMapTranslator<KeyValuePairTraits, HashFunctions>>(key); + if (!entry) + return MappedTraits::peek(MappedTraits::emptyValue()); + return MappedTraits::peek(entry->value); +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +auto HashMap<T, U, V, W, X>::get(typename GetPtrHelper<K>::PtrType key) const -> typename std::enable_if<IsSmartPtr<K>::value, MappedPeekType>::type +{ + return inlineGet(key); +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +inline auto HashMap<T, U, V, W, X>::remove(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, bool>::type +{ + return remove(find(key)); +} + +template<typename T, typename U, typename V, typename W, typename X> +template<typename K> +inline auto HashMap<T, U, V, W, X>::take(typename GetPtrHelper<K>::PtrType key) -> typename std::enable_if<IsSmartPtr<K>::value, MappedTakeType>::type { iterator it = find(key); if (it == end()) - return MappedTraits::emptyValue(); - MappedType value = std::move(it->value); + return MappedTraits::take(MappedTraits::emptyValue()); + auto value = MappedTraits::take(WTFMove(it->value)); remove(it); return value; } @@ -407,6 +551,19 @@ inline bool operator!=(const HashMap<T, U, V, W, X>& a, const HashMap<T, U, V, W } template<typename T, typename U, typename V, typename W, typename X, typename Y> +inline void copyToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) +{ + typedef typename HashMap<T, U, V, W, X>::const_iterator iterator; + + vector.resize(collection.size()); + + iterator it = collection.begin(); + iterator end = collection.end(); + for (unsigned i = 0; it != end; ++it, ++i) + vector[i] = { (*it).key, (*it).value }; +} + +template<typename T, typename U, typename V, typename W, typename X, typename Y> inline void copyKeysToVector(const HashMap<T, U, V, W, X>& collection, Y& vector) { typedef typename HashMap<T, U, V, W, X>::const_iterator::Keys iterator; @@ -436,6 +593,4 @@ inline void copyValuesToVector(const HashMap<T, U, V, W, X>& collection, Y& vect using WTF::HashMap; -#include <wtf/RefPtrHashMap.h> - #endif /* WTF_HashMap_h */ |