Modified: trunk/Source/WTF/wtf/ListHashSet.h (156293 => 156294)
--- trunk/Source/WTF/wtf/ListHashSet.h 2013-09-23 21:20:13 UTC (rev 156293)
+++ trunk/Source/WTF/wtf/ListHashSet.h 2013-09-23 21:39:30 UTC (rev 156294)
@@ -123,17 +123,22 @@
// The return value of add is a pair of an iterator to the new value's location,
// and a bool that is true if an new entry was added.
AddResult add(const ValueType&);
+ AddResult add(ValueType&&);
// 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(const ValueType&);
+ AddResult appendOrMoveToLast(ValueType&&);
// 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(const ValueType&);
+ AddResult prependOrMoveToFirst(ValueType&&);
AddResult insertBefore(const ValueType& beforeValue, const ValueType& newValue);
+ AddResult insertBefore(const ValueType& beforeValue, ValueType&& newValue);
AddResult insertBefore(iterator, const ValueType&);
+ AddResult insertBefore(iterator, ValueType&&);
bool remove(const ValueType&);
bool remove(iterator);
@@ -229,8 +234,9 @@
template<typename ValueArg, size_t inlineCapacity> struct ListHashSetNode {
typedef ListHashSetNodeAllocator<ValueArg, inlineCapacity> NodeAllocator;
- ListHashSetNode(ValueArg value)
- : m_value(value)
+ template<typename T>
+ ListHashSetNode(T&& value)
+ : m_value(std::forward<T>(value))
, m_prev(0)
, m_next(0)
#ifndef NDEBUG
@@ -389,9 +395,9 @@
struct 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 (allocator) T(key);
+ location = new (allocator) T(std::forward<U>(key));
}
};
@@ -464,16 +470,19 @@
template<typename T, size_t inlineCapacity, typename U>
inline void ListHashSet<T, inlineCapacity, U>::removeFirst()
{
- ASSERT(!isEmpty());
- m_impl.remove(m_head);
- unlinkAndDelete(m_head);
+ takeFirst();
}
template<typename T, size_t inlineCapacity, typename U>
inline T ListHashSet<T, inlineCapacity, U>::takeFirst()
{
- T result = first();
- removeFirst();
+ ASSERT(!isEmpty());
+ auto it = m_impl.find(m_head);
+
+ T result = std::move((*it)->m_value);
+ m_impl.remove(it);
+ unlinkAndDelete(m_head);
+
return result;
}
@@ -501,7 +510,7 @@
template<typename T, size_t inlineCapacity, typename U>
inline void ListHashSet<T, inlineCapacity, U>::removeLast()
{
- ASSERT(!isEmpty());
+ takeLast();
m_impl.remove(m_tail);
unlinkAndDelete(m_tail);
}
@@ -509,8 +518,13 @@
template<typename T, size_t inlineCapacity, typename U>
inline T ListHashSet<T, inlineCapacity, U>::takeLast()
{
- T result = last();
- removeLast();
+ ASSERT(!isEmpty());
+ auto it = m_impl.find(m_tail);
+
+ T result = std::move((*it)->m_value);
+ m_impl.remove(it);
+ unlinkAndDelete(m_tail);
+
return result;
}
@@ -572,7 +586,7 @@
}
template<typename T, size_t inlineCapacity, typename U>
-auto ListHashSet<T, inlineCapacity, U>::add(const ValueType &value) -> AddResult
+auto ListHashSet<T, inlineCapacity, U>::add(const ValueType& value) -> AddResult
{
auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
if (result.isNewEntry)
@@ -581,8 +595,17 @@
}
template<typename T, size_t inlineCapacity, typename U>
-auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType &value) -> AddResult
+auto ListHashSet<T, inlineCapacity, U>::add(ValueType&& value) -> AddResult
{
+ auto result = m_impl.template add<BaseTranslator>(std::move(value), m_allocator.get());
+ if (result.isNewEntry)
+ appendNode(*result.iterator);
+ return AddResult(makeIterator(*result.iterator), result.isNewEntry);
+}
+
+template<typename T, size_t inlineCapacity, typename U>
+auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(const ValueType& value) -> AddResult
+{
auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
Node* node = *result.iterator;
if (!result.isNewEntry)
@@ -593,8 +616,20 @@
}
template<typename T, size_t inlineCapacity, typename U>
-auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType &value) -> AddResult
+auto ListHashSet<T, inlineCapacity, U>::appendOrMoveToLast(ValueType&& value) -> AddResult
{
+ auto result = m_impl.template add<BaseTranslator>(std::move(value), m_allocator.get());
+ Node* node = *result.iterator;
+ if (!result.isNewEntry)
+ unlink(node);
+ appendNode(node);
+
+ return AddResult(makeIterator(*result.iterator), result.isNewEntry);
+}
+
+template<typename T, size_t inlineCapacity, typename U>
+auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(const ValueType& value) -> AddResult
+{
auto result = m_impl.template add<BaseTranslator>(value, m_allocator.get());
Node* node = *result.iterator;
if (!result.isNewEntry)
@@ -605,6 +640,30 @@
}
template<typename T, size_t inlineCapacity, typename U>
+auto ListHashSet<T, inlineCapacity, U>::prependOrMoveToFirst(ValueType&& value) -> AddResult
+{
+ auto result = m_impl.template add<BaseTranslator>(std::move(value), m_allocator.get());
+ Node* node = *result.iterator;
+ if (!result.isNewEntry)
+ unlink(node);
+ prependNode(node);
+
+ return AddResult(makeIterator(*result.iterator), result.isNewEntry);
+}
+
+template<typename T, size_t inlineCapacity, typename U>
+auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
+{
+ return insertBefore(find(beforeValue), newValue);
+}
+
+template<typename T, size_t inlineCapacity, typename U>
+auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, ValueType&& newValue) -> AddResult
+{
+ return insertBefore(find(beforeValue), std::move(newValue));
+}
+
+template<typename T, size_t inlineCapacity, typename U>
auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, const ValueType& newValue) -> AddResult
{
auto result = m_impl.template add<BaseTranslator>(newValue, m_allocator.get());
@@ -614,9 +673,12 @@
}
template<typename T, size_t inlineCapacity, typename U>
-auto ListHashSet<T, inlineCapacity, U>::insertBefore(const ValueType& beforeValue, const ValueType& newValue) -> AddResult
+auto ListHashSet<T, inlineCapacity, U>::insertBefore(iterator it, ValueType&& newValue) -> AddResult
{
- return insertBefore(find(beforeValue), newValue);
+ auto result = m_impl.template add<BaseTranslator>(std::move(newValue), m_allocator.get());
+ if (result.isNewEntry)
+ insertNodeBefore(it.node(), *result.iterator);
+ return AddResult(makeIterator(*result.iterator), result.isNewEntry);
}
template<typename T, size_t inlineCapacity, typename U>
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp (156293 => 156294)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp 2013-09-23 21:20:13 UTC (rev 156293)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/ListHashSet.cpp 2013-09-23 21:39:30 UTC (rev 156294)
@@ -25,6 +25,7 @@
#include "config.h"
+#include "MoveOnly.h"
#include <wtf/ListHashSet.h>
namespace TestWebKitAPI {
@@ -199,4 +200,51 @@
ASSERT_TRUE(constIt == listHashSet.rend());
}
+TEST(WTF_ListHashSet, MoveOnly)
+{
+ ListHashSet<MoveOnly> list;
+ list.add(MoveOnly(2));
+ list.add(MoveOnly(4));
+
+ // { 2, 4 }
+ ASSERT_EQ(2U, list.first().value());
+ ASSERT_EQ(4U, list.last().value());
+
+ list.appendOrMoveToLast(MoveOnly(3));
+
+ // { 2, 4, 3 }
+ ASSERT_EQ(3U, list.last().value());
+
+ // { 4, 3, 2 }
+ list.appendOrMoveToLast(MoveOnly(2));
+ ASSERT_EQ(4U, list.first().value());
+ ASSERT_EQ(2U, list.last().value());
+
+ list.prependOrMoveToFirst(MoveOnly(5));
+
+ // { 5, 2, 4, 3 }
+ ASSERT_EQ(5U, list.first().value());
+
+ list.prependOrMoveToFirst(MoveOnly(3));
+
+ // { 3, 5, 4, 2 }
+ ASSERT_EQ(3U, list.first().value());
+ ASSERT_EQ(2U, list.last().value());
+
+ list.insertBefore(MoveOnly(4), MoveOnly(1));
+ list.insertBefore(list.end(), MoveOnly(6));
+
+ // { 3, 5, 1, 4, 2, 6 }
+ ASSERT_EQ(3U, list.takeFirst().value());
+ ASSERT_EQ(5U, list.takeFirst().value());
+ ASSERT_EQ(1U, list.takeFirst().value());
+
+ // { 4, 2, 6 }
+ ASSERT_EQ(6U, list.takeLast().value());
+ ASSERT_EQ(2U, list.takeLast().value());
+ ASSERT_EQ(4U, list.takeLast().value());
+
+ ASSERT_TRUE(list.isEmpty());
+}
+
} // namespace TestWebKitAPI
