summaryrefslogtreecommitdiff
path: root/Source/WTF/wtf/HashMap.h
diff options
context:
space:
mode:
authorLorry Tar Creator <lorry-tar-importer@lorry>2017-06-27 06:07:23 +0000
committerLorry Tar Creator <lorry-tar-importer@lorry>2017-06-27 06:07:23 +0000
commit1bf1084f2b10c3b47fd1a588d85d21ed0eb41d0c (patch)
tree46dcd36c86e7fbc6e5df36deb463b33e9967a6f7 /Source/WTF/wtf/HashMap.h
parent32761a6cee1d0dee366b885b7b9c777e67885688 (diff)
downloadWebKitGtk-tarball-master.tar.gz
Diffstat (limited to 'Source/WTF/wtf/HashMap.h')
-rw-r--r--Source/WTF/wtf/HashMap.h187
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 */