WTF::HashTable: Implement move semantics for keys and values.

third_party/WebKit/Source/wtf/HashMapTest.cpp

 /*
  * Copyright (C) 2011 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 284 matching lines @@
 
 TEST(HashMapTest, ValueTypeDestructed)
 {
     InstanceCounter::counter = 0;
     HashMap<int, InstanceCounter> map;
     map.set(1, InstanceCounter());
     map.clear();
     EXPECT_EQ(0, InstanceCounter::counter);
 }
 
+class MoveOnly {
+public:
+    // kEmpty and kDeleted have special meanings when MoveOnly is used as the key of a hash table.
+    enum {
+        kEmpty = 0,
+        kDeleted = -1,
+        kMovedOut = -2
+    };
+
+    explicit MoveOnly(int value = kEmpty) : m_value(value) { }
+    MoveOnly(MoveOnly&& other)
+        : m_value(other.m_value)
+    {
+        other.m_value = kMovedOut;
+    }
+    MoveOnly& operator=(MoveOnly&& other)
+    {
+        m_value = other.m_value;
+        other.m_value = kMovedOut;
+        return *this;
+    }
+
+    int value() const { return m_value; }
+
+private:
+    MoveOnly(const MoveOnly&) = delete;
+    MoveOnly& operator=(const MoveOnly&) = delete;
+
+    int m_value;
+};
+
+struct MoveOnlyHashTraits : public GenericHashTraits<MoveOnly> {
+    // This is actually true, but we pretend that it's false to disable the optimization.
+    static const bool emptyValueIsZero = false;
+
+    static const bool hasIsEmptyValueFunction = true;
+    static bool isEmptyValue(const MoveOnly& value) { return value.value() == MoveOnly::kEmpty; }
+    static void constructDeletedValue(MoveOnly& slot, bool) { slot = MoveOnly(MoveOnly::kDeleted); }
+    static bool isDeletedValue(const MoveOnly& value) { return value.value() == MoveOnly::kDeleted; }
+};
+
+struct MoveOnlyHash {
+    static unsigned hash(const MoveOnly& value) { return DefaultHash<int>::Hash::hash(value.value()); }
+    static bool equal(const MoveOnly& left, const MoveOnly& right)
+    {
+        return DefaultHash<int>::Hash::equal(left.value(), right.value());
+    }
+    static const bool safeToCompareToEmptyOrDeleted = true;
+};
+
+} // anonymous namespace
+
+template <>
+struct HashTraits<MoveOnly> : public MoveOnlyHashTraits { };
+
+template <>
+struct DefaultHash<MoveOnly> {
+    using Hash = MoveOnlyHash;
+};
+
+namespace {
+
+TEST(HashMapTest, MoveOnlyValueType)
+{
+    using TheMap = HashMap<int, MoveOnly>;
+    TheMap map;
+    {
+        TheMap::AddResult addResult = map.add(1, MoveOnly(10));
+        EXPECT_TRUE(addResult.isNewEntry);
+        EXPECT_EQ(1, addResult.storedValue->key);
+        EXPECT_EQ(10, addResult.storedValue->value.value());
+    }
+    auto iter = map.find(1);
+    ASSERT_TRUE(iter != map.end());
+    EXPECT_EQ(1, iter->key);
+    EXPECT_EQ(10, iter->value.value());
+
+    iter = map.find(2);
+    EXPECT_TRUE(iter == map.end());
+
+    // Try to add more to trigger rehashing.
+    for (int i = 2; i < 32; ++i) {
+        TheMap::AddResult addResult = map.add(i, MoveOnly(i * 10));
+        EXPECT_TRUE(addResult.isNewEntry);
+        EXPECT_EQ(i, addResult.storedValue->key);
+        EXPECT_EQ(i * 10, addResult.storedValue->value.value());
+    }
+
+    iter = map.find(1);
+    ASSERT_TRUE(iter != map.end());
+    EXPECT_EQ(1, iter->key);
+    EXPECT_EQ(10, iter->value.value());
+
+    iter = map.find(7);
+    ASSERT_TRUE(iter != map.end());
+    EXPECT_EQ(7, iter->key);
+    EXPECT_EQ(70, iter->value.value());
+
+    {
+        TheMap::AddResult addResult = map.set(9, MoveOnly(999));
+        EXPECT_FALSE(addResult.isNewEntry);
+        EXPECT_EQ(9, addResult.storedValue->key);
+        EXPECT_EQ(999, addResult.storedValue->value.value());
+    }
+
+    map.remove(11);
+    iter = map.find(11);
+    EXPECT_TRUE(iter == map.end());
+
+    MoveOnly oneThirty(map.take(13));
+    EXPECT_EQ(130, oneThirty.value());
+    iter = map.find(13);
+    EXPECT_TRUE(iter == map.end());
+
+    map.clear();
+}
+
+TEST(HashMapTest, MoveOnlyKeyType)
+{
+    // The content of this test is similar to the test above, except that the types of key and value are swapped.
+    using TheMap = HashMap<MoveOnly, int>;
+    TheMap map;
+    {
+        TheMap::AddResult addResult = map.add(MoveOnly(1), 10);
+        EXPECT_TRUE(addResult.isNewEntry);
+        EXPECT_EQ(1, addResult.storedValue->key.value());
+        EXPECT_EQ(10, addResult.storedValue->value);
+    }
+    auto iter = map.find(MoveOnly(1));
+    ASSERT_TRUE(iter != map.end());
+    EXPECT_EQ(1, iter->key.value());
+    EXPECT_EQ(10, iter->value);
+
+    iter = map.find(MoveOnly(2));
+    EXPECT_TRUE(iter == map.end());
+
+    for (int i = 2; i < 32; ++i) {
+        TheMap::AddResult addResult = map.add(MoveOnly(i), i * 10);
+        EXPECT_TRUE(addResult.isNewEntry);
+        EXPECT_EQ(i, addResult.storedValue->key.value());
+        EXPECT_EQ(i * 10, addResult.storedValue->value);
+    }
+
+    iter = map.find(MoveOnly(1));
+    ASSERT_TRUE(iter != map.end());
+    EXPECT_EQ(1, iter->key.value());
+    EXPECT_EQ(10, iter->value);
+
+    iter = map.find(MoveOnly(7));
+    ASSERT_TRUE(iter != map.end());
+    EXPECT_EQ(7, iter->key.value());
+    EXPECT_EQ(70, iter->value);
+
+    {
+        TheMap::AddResult addResult = map.set(MoveOnly(9), 999);
+        EXPECT_FALSE(addResult.isNewEntry);
+        EXPECT_EQ(9, addResult.storedValue->key.value());
+        EXPECT_EQ(999, addResult.storedValue->value);
+    }
+
+    map.remove(MoveOnly(11));
+    iter = map.find(MoveOnly(11));
+    EXPECT_TRUE(iter == map.end());
+
+    int oneThirty = map.take(MoveOnly(13));
+    EXPECT_EQ(130, oneThirty);
+    iter = map.find(MoveOnly(13));
+    EXPECT_TRUE(iter == map.end());
+
+    map.clear();
+}
+
 } // anonymous namespace
 
 } // namespace WTF