WTF: Implement move semantics for values of {List,Linked}HashSet.

third_party/WebKit/Source/wtf/ListHashSet.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2011, Benjamin Poulain <ikipou@gmail.com>
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
  * License as published by the Free Software Foundation; either
  * version 2 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
@@ skipping 126 matching lines @@
 
     // An alternate version of find() that finds the object by hashing and
     // comparing with some other type, to avoid the cost of type conversion.
     // The HashTranslator interface is defined in HashSet.
     template <typename HashTranslator, typename T> iterator find(const T&);
     template <typename HashTranslator, typename T> const_iterator find(const T&) const;
     template <typename HashTranslator, typename T> bool contains(const T&) const;
 
     // The return value of add is a pair of a pointer to the stored value, and a
     // bool that is true if an new entry was added.
-    AddResult add(ValuePassInType);

[Mikhail, 2016/03/17 09:17:48]

if 'ValuePassInType' is not used any more, maybe it should not be declared?

[Yuta Kitamura, 2016/03/18 04:42:11]

Done.

+    template <typename IncomingValueType>
+    AddResult add(IncomingValueType&&);

[Mikhail, 2016/03/17 09:17:48]

Does this converting to template methods (here and in the other places in the
patch) affect binary size?

[Yuta Kitamura, 2016/03/18 04:42:11]

I did this kind of transmutation many times in the earlier
patches and I haven't received any complaints so far.
In general compilers are good at inlining this kind of stuff.

 
     // Same as add() except that the return value is an iterator. Useful in
     // cases where it's needed to have the same return value as find() and where
     // it's not possible to use a pointer to the storedValue.
-    iterator addReturnIterator(ValuePassInType);
+    template <typename IncomingValueType>
+    iterator addReturnIterator(IncomingValueType&&);
 
     // Add the value to the end of the collection. If the value was already in
     // the list, it is moved to the end.
-    AddResult appendOrMoveToLast(ValuePassInType);
+    template <typename IncomingValueType>
+    AddResult appendOrMoveToLast(IncomingValueType&&);
 
     // Add the value to the beginning of the collection. If the value was
     // already in the list, it is moved to the beginning.
-    AddResult prependOrMoveToFirst(ValuePassInType);
+    template <typename IncomingValueType>
+    AddResult prependOrMoveToFirst(IncomingValueType&&);
 
-    AddResult insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue);
-    AddResult insertBefore(iterator, ValuePassInType);
+    template <typename IncomingValueType>
+    AddResult insertBefore(ValuePeekInType beforeValue, IncomingValueType&& newValue);
+    template <typename IncomingValueType>
+    AddResult insertBefore(iterator, IncomingValueType&&);
 
     void remove(ValuePeekInType value) { return remove(find(value)); }
     void remove(iterator);
     void clear();
     template <typename Collection>
     void removeAll(const Collection& other) { WTF::removeAll(*this, other); }
 
     ValuePassOutType take(iterator);
     ValuePassOutType take(ValuePeekInType);
     ValuePassOutType takeFirst();
@@ skipping 22 matching lines @@
     Node* m_tail;
     typename Allocator::AllocatorProvider m_allocatorProvider;
 };
 
 // ListHashSetNode has this base class to hold the members because the MSVC
 // compiler otherwise gets into circular template dependencies when trying to do
 // sizeof on a node.
 template <typename ValueArg> class ListHashSetNodeBase {
     DISALLOW_NEW();
 protected:
-    ListHashSetNodeBase(const ValueArg& value)
-        : m_value(value)
+    template <typename U>
+    explicit ListHashSetNodeBase(U&& value)
+        : m_value(std::forward<U>(value))
         , m_prev(nullptr)
         , m_next(nullptr)
 #if ENABLE(ASSERT)
-        , m_isAllocated(true)
-#endif
-    {
-    }
-
-    template <typename U>
-    ListHashSetNodeBase(const U& value)
-        : m_value(value)
-        , m_prev(nullptr)
-        , m_next(nullptr)
-#if ENABLE(ASSERT)
         , m_isAllocated(true)
 #endif
     {
     }
 
 public:
     ValueArg m_value;
     ListHashSetNodeBase* m_prev;
     ListHashSetNodeBase* m_next;
 #if ENABLE(ASSERT)
@@ skipping 117 matching lines @@
 #endif
     AlignedBuffer<sizeof(NodeBase) * m_poolSize, WTF_ALIGN_OF(NodeBase)> m_pool;
 };
 
 template <typename ValueArg, typename AllocatorArg> class ListHashSetNode : public ListHashSetNodeBase<ValueArg> {
 public:
     typedef AllocatorArg NodeAllocator;
     typedef ValueArg Value;
 
     template <typename U>
-    ListHashSetNode(U value)
-        : ListHashSetNodeBase<ValueArg>(value) {}
+    ListHashSetNode(U&& value)
+        : ListHashSetNodeBase<ValueArg>(std::forward<U>(value)) {}
 
     void* operator new(size_t, NodeAllocator* allocator)
     {
         static_assert(sizeof(ListHashSetNode) == sizeof(ListHashSetNodeBase<ValueArg>), "please add any fields to the base");
         return allocator->allocateNode();
     }
 
     void setWasAlreadyDestructed()
     {
         if (NodeAllocator::isGarbageCollected && !IsTriviallyDestructible<ValueArg>::value)
@@ skipping 286 matching lines @@
 
     template <typename T, size_t inlineCapacity, typename U, typename V>
     friend class ListHashSet;
 };
 
 template <typename HashFunctions>
 struct ListHashSetTranslator {
     STATIC_ONLY(ListHashSetTranslator);
     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->m_value, b); }
-    template <typename T, typename U, typename V> static void translate(T*& location, const U& key, const V& allocator)
+    template <typename T, typename U, typename V> static void translate(T*& location, U&& key, const V& allocator)
     {
-        location = new (const_cast<V*>(&allocator)) T(key);
+        location = new (const_cast<V*>(&allocator)) T(std::forward<U>(key));
     }
 };
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
 inline ListHashSet<T, inlineCapacity, U, V>::ListHashSet()
     : m_head(nullptr)
     , m_tail(nullptr)
 {
 }
 
@@ skipping 143 matching lines @@
     return m_impl.template contains<ListHashSetTranslatorAdapter<HashTranslator>>(value);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
 inline bool ListHashSet<T, inlineCapacity, U, V>::contains(ValuePeekInType value) const
 {
     return m_impl.template contains<BaseTranslator>(value);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
-typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::add(ValuePassInType value)
+template <typename IncomingValueType>
+typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::add(IncomingValueType&& value)
 {
     createAllocatorIfNeeded();
     // The second argument is a const ref. This is useful for the HashTable
     // because it lets it take lvalues by reference, but for our purposes it's
     // inconvenient, since it constrains us to be const, whereas the allocator
     // actually changes when it does allocations.
-    auto result = m_impl.template add<BaseTranslator>(value, *this->allocator());
+    auto result = m_impl.template add<BaseTranslator>(std::forward<IncomingValueType>(value), *this->allocator());
     if (result.isNewEntry)
         appendNode(*result.storedValue);
     return AddResult(*result.storedValue, result.isNewEntry);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
-typename ListHashSet<T, inlineCapacity, U, V>::iterator ListHashSet<T, inlineCapacity, U, V>::addReturnIterator(ValuePassInType value)
+template <typename IncomingValueType>
+typename ListHashSet<T, inlineCapacity, U, V>::iterator ListHashSet<T, inlineCapacity, U, V>::addReturnIterator(IncomingValueType&& value)
 {
-    return makeIterator(add(value).m_node);
+    return makeIterator(add(std::forward<IncomingValueType>(value)).m_node);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
-typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::appendOrMoveToLast(ValuePassInType value)
+template <typename IncomingValueType>
+typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::appendOrMoveToLast(IncomingValueType&& value)
 {
     createAllocatorIfNeeded();
-    auto result = m_impl.template add<BaseTranslator>(value, *this->allocator());
+    auto result = m_impl.template add<BaseTranslator>(std::forward<IncomingValueType>(value), *this->allocator());
     Node* node = *result.storedValue;
     if (!result.isNewEntry)
         unlink(node);
     appendNode(node);
     return AddResult(*result.storedValue, result.isNewEntry);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
-typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::prependOrMoveToFirst(ValuePassInType value)
+template <typename IncomingValueType>
+typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::prependOrMoveToFirst(IncomingValueType&& value)
 {
     createAllocatorIfNeeded();
-    auto result = m_impl.template add<BaseTranslator>(value, *this->allocator());
+    auto result = m_impl.template add<BaseTranslator>(std::forward<IncomingValueType>(value), *this->allocator());
     Node* node = *result.storedValue;
     if (!result.isNewEntry)
         unlink(node);
     prependNode(node);
     return AddResult(*result.storedValue, result.isNewEntry);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
-typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(iterator it, ValuePassInType newValue)
+template <typename IncomingValueType>
+typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(iterator it, IncomingValueType&& newValue)
 {
     createAllocatorIfNeeded();
-    auto result = m_impl.template add<BaseTranslator>(newValue, *this->allocator());
+    auto result = m_impl.template add<BaseTranslator>(std::forward<IncomingValueType>(newValue), *this->allocator());
     if (result.isNewEntry)
         insertNodeBefore(it.node(), *result.storedValue);
     return AddResult(*result.storedValue, result.isNewEntry);
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
-typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(ValuePeekInType beforeValue, ValuePassInType newValue)
+template <typename IncomingValueType>
+typename ListHashSet<T, inlineCapacity, U, V>::AddResult ListHashSet<T, inlineCapacity, U, V>::insertBefore(ValuePeekInType beforeValue, IncomingValueType&& newValue)
 {
     createAllocatorIfNeeded();
-    return insertBefore(find(beforeValue), newValue);
+    return insertBefore(find(beforeValue), std::forward<IncomingValueType>(newValue));
 }
 
 template <typename T, size_t inlineCapacity, typename U, typename V>
 inline void ListHashSet<T, inlineCapacity, U, V>::remove(iterator it)
 {
     if (it == end())
         return;
     m_impl.remove(it.node());
     unlinkAndDelete(it.node());
 }
@@ skipping 137 matching lines @@
 struct NeedsTracing<ListHashSet<T, U, V>> {
     static const bool value = false;
 };
 #endif
 
 } // namespace WTF
 
 using WTF::ListHashSet;
 
 #endif // WTF_ListHashSet_h