From 1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c Mon Sep 17 00:00:00 2001 From: Lorry Tar Creator Date: Tue, 27 Jun 2017 06:07:23 +0000 Subject: webkitgtk-2.16.5 --- Source/WTF/wtf/HashMap.h | 187 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 171 insertions(+), 16 deletions(-) (limited to 'Source/WTF/wtf/HashMap.h') 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 struct KeyValuePairKeyExtractor { template::Hash, typename KeyTraitsArg = HashTraits, typename MappedTraitsArg = HashTraits> -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 AddResult add(const KeyType&, V&&); template AddResult add(KeyType&&, V&&); + // Same as add(), but aggressively inlined. + template AddResult fastAdd(const KeyType&, V&&); + template AddResult fastAdd(KeyType&&, V&&); + + template AddResult ensure(const KeyType&, Functor&&); + template AddResult ensure(KeyType&&, Functor&&); + bool remove(const KeyType&); bool remove(iterator); + template + 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 AddResult add(K&&, V&&); + // Overloads for smart pointer keys that take the raw pointer type as the parameter. + template typename std::enable_if::value, iterator>::type find(typename GetPtrHelper::PtrType); + template typename std::enable_if::value, const_iterator>::type find(typename GetPtrHelper::PtrType) const; + template typename std::enable_if::value, bool>::type contains(typename GetPtrHelper::PtrType) const; + template typename std::enable_if::value, MappedPeekType>::type inlineGet(typename GetPtrHelper::PtrType) const; + template typename std::enable_if::value, MappedPeekType>::type get(typename GetPtrHelper::PtrType) const; + template typename std::enable_if::value, bool>::type remove(typename GetPtrHelper::PtrType); + template typename std::enable_if::value, MappedTakeType>::type take(typename GetPtrHelper::PtrType); + void checkConsistency() const; static bool isValidKey(const KeyType&); @@ -148,6 +170,9 @@ private: template AddResult inlineAdd(K&&, V&&); + template + AddResult inlineEnsure(K&&, F&&); + HashTableType m_impl; }; @@ -157,8 +182,19 @@ struct HashMapTranslator { template static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } template static void translate(T& location, U&& key, V&& mapped) { - location.key = std::forward(key); - location.value = std::forward(mapped); + ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward(key)); + ValueTraits::ValueTraits::assignToEmpty(location.value, std::forward(mapped)); + } +}; + +template +struct HashMapEnsureTranslator { + template static unsigned hash(const T& key) { return HashFunctions::hash(key); } + template static bool equal(const T& a, const U& b) { return HashFunctions::equal(a, b); } + template static void translate(T& location, U&& key, Functor&& functor) + { + ValueTraits::KeyTraits::assignToEmpty(location.key, std::forward(key)); + ValueTraits::ValueTraits::assignToEmpty(location.value, functor()); } }; @@ -180,13 +216,13 @@ inline void HashMap::swap(HashMap& other) } template -inline int HashMap::size() const +inline unsigned HashMap::size() const { return m_impl.size(); } template -inline int HashMap::capacity() const +inline unsigned HashMap::capacity() const { return m_impl.capacity(); } @@ -276,11 +312,18 @@ auto HashMap::inlineS template template -auto HashMap::inlineAdd(K&& key, V&& value) -> AddResult +ALWAYS_INLINE auto HashMap::inlineAdd(K&& key, V&& value) -> AddResult { return m_impl.template add>(std::forward(key), std::forward(value)); } +template +template +ALWAYS_INLINE auto HashMap::inlineEnsure(K&& key, F&& functor) -> AddResult +{ + return m_impl.template add>(std::forward(key), std::forward(functor)); +} + template template auto HashMap::set(const KeyType& key, T&& mapped) -> AddResult @@ -292,7 +335,7 @@ template auto HashMap::set(KeyType&& key, T&& mapped) -> AddResult { - return inlineSet(std::move(key), std::forward(mapped)); + return inlineSet(WTFMove(key), std::forward(mapped)); } template @@ -313,9 +356,37 @@ template auto HashMap::add(KeyType&& key, T&& mapped) -> AddResult { - return inlineAdd(std::move(key), std::forward(mapped)); + return inlineAdd(WTFMove(key), std::forward(mapped)); +} + +template +template +ALWAYS_INLINE auto HashMap::fastAdd(const KeyType& key, T&& mapped) -> AddResult +{ + return inlineAdd(key, std::forward(mapped)); +} + +template +template +ALWAYS_INLINE auto HashMap::fastAdd(KeyType&& key, T&& mapped) -> AddResult +{ + return inlineAdd(WTFMove(key), std::forward(mapped)); +} + +template +template +auto HashMap::ensure(const KeyType& key, Functor&& functor) -> AddResult +{ + return inlineEnsure(key, std::forward(functor)); } +template +template +auto HashMap::ensure(KeyType&& key, Functor&& functor) -> AddResult +{ + return inlineEnsure(std::forward(key), std::forward(functor)); +} + template auto HashMap::get(const KeyType& key) const -> MappedPeekType { @@ -325,6 +396,15 @@ auto HashMap::get(const KeyType& key) const -> MappedP return MappedTraits::peek(entry->value); } +template +ALWAYS_INLINE auto HashMap::fastGet(const KeyType& key) const -> MappedPeekType +{ + KeyValuePairType* entry = const_cast(m_impl).template inlineLookup(key); + if (!entry) + return MappedTraits::peek(MappedTraits::emptyValue()); + return MappedTraits::peek(entry->value); +} + template inline bool HashMap::remove(iterator it) { @@ -335,6 +415,13 @@ inline bool HashMap::remove(iterator it) return true; } +template +template +inline void HashMap::removeIf(Functor&& functor) +{ + m_impl.removeIf(std::forward(functor)); +} + template inline bool HashMap::remove(const KeyType& key) { @@ -348,12 +435,69 @@ inline void HashMap::clear() } template -auto HashMap::take(const KeyType& key) -> MappedType +auto HashMap::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 +template +inline auto HashMap::find(typename GetPtrHelper::PtrType key) -> typename std::enable_if::value, iterator>::type +{ + return m_impl.template find>(key); +} + +template +template +inline auto HashMap::find(typename GetPtrHelper::PtrType key) const -> typename std::enable_if::value, const_iterator>::type +{ + return m_impl.template find>(key); +} + +template +template +inline auto HashMap::contains(typename GetPtrHelper::PtrType key) const -> typename std::enable_if::value, bool>::type +{ + return m_impl.template contains>(key); +} + +template +template +inline auto HashMap::inlineGet(typename GetPtrHelper::PtrType key) const -> typename std::enable_if::value, MappedPeekType>::type +{ + KeyValuePairType* entry = const_cast(m_impl).template inlineLookup>(key); + if (!entry) + return MappedTraits::peek(MappedTraits::emptyValue()); + return MappedTraits::peek(entry->value); +} + +template +template +auto HashMap::get(typename GetPtrHelper::PtrType key) const -> typename std::enable_if::value, MappedPeekType>::type +{ + return inlineGet(key); +} + +template +template +inline auto HashMap::remove(typename GetPtrHelper::PtrType key) -> typename std::enable_if::value, bool>::type +{ + return remove(find(key)); +} + +template +template +inline auto HashMap::take(typename GetPtrHelper::PtrType key) -> typename std::enable_if::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; } @@ -406,6 +550,19 @@ inline bool operator!=(const HashMap& a, const HashMap +inline void copyToVector(const HashMap& collection, Y& vector) +{ + typedef typename HashMap::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 inline void copyKeysToVector(const HashMap& collection, Y& vector) { @@ -436,6 +593,4 @@ inline void copyValuesToVector(const HashMap& collection, Y& vect using WTF::HashMap; -#include - #endif /* WTF_HashMap_h */ -- cgit v1.2.1