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

third_party/WebKit/Source/wtf/HashTable.h

 /*
  * Copyright (C) 2005, 2006, 2007, 2008, 2011, 2012 Apple Inc. All rights reserved.
  * Copyright (C) 2008 David Levin <levin@chromium.org>
  *
  * 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 256 matching lines @@
         new (NotNull, &to) T(std::move(from));
         Allocator::leaveGCForbiddenScope();
     }
 };
 
 template <typename HashFunctions> class IdentityHashTranslator {
     STATIC_ONLY(IdentityHashTranslator);
 public:
     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 V> static void translate(T& location, const U&, const V& value) { location = value; }
+    template <typename T, typename U, typename V> static void translate(T& location, U&&, V&& value) { location = std::forward<V>(value); }
 };
 
 template <typename HashTableType, typename ValueType> struct HashTableAddResult final {
     STACK_ALLOCATED();
     HashTableAddResult(const HashTableType* container, ValueType* storedValue, bool isNewEntry)
         : storedValue(storedValue)
         , isNewEntry(isNewEntry)
 #if ENABLE(SECURITY_ASSERT)
         , m_container(container)
         , m_containerModifications(container->modifications())
@@ skipping 167 matching lines @@
     void reserveCapacityForSize(unsigned size);
 
     AddResult add(ValuePassInType value)
     {
         return add<IdentityTranslatorType>(Extractor::extract(value), value);
     }
 
     // A special version of add() that finds the object by hashing and comparing
     // with some other type, to avoid the cost of type conversion if the object
     // is already in the table.
-    template <typename HashTranslator, typename T, typename Extra> AddResult add(const T& key, const Extra&);
+    template <typename HashTranslator, typename T, typename Extra> AddResult add(T&& key, Extra&&);
     template <typename HashTranslator, typename T, typename Extra> AddResult addPassingHashCode(const T& key, const Extra&);
 
     iterator find(KeyPeekInType key) { return find<IdentityTranslatorType>(key); }
     const_iterator find(KeyPeekInType key) const { return find<IdentityTranslatorType>(key); }
     bool contains(KeyPeekInType key) const { return contains<IdentityTranslatorType>(key); }
 
     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;
 
     void remove(KeyPeekInType);
     void remove(iterator);
     void remove(const_iterator);
     void clear();
 
     static bool isEmptyBucket(const ValueType& value) { return isHashTraitsEmptyValue<KeyTraits>(Extractor::extract(value)); }
     static bool isDeletedBucket(const ValueType& value) { return KeyTraits::isDeletedValue(Extractor::extract(value)); }
     static bool isEmptyOrDeletedBucket(const ValueType& value) { return HashTableHelper<ValueType, Extractor, KeyTraits>:: isEmptyOrDeletedBucket(value); }
 
     ValueType* lookup(KeyPeekInType key) { return lookup<IdentityTranslatorType, KeyPeekInType>(key); }
-    template <typename HashTranslator, typename T> ValueType* lookup(T);
-    template <typename HashTranslator, typename T> const ValueType* lookup(T) const;
+    template <typename HashTranslator, typename T> ValueType* lookup(const T&);

[Mikhail, 2016/03/04 12:58:02]

why not T&& ?

[Yuta Kitamura, 2016/03/04 13:55:37]

This is used to calculate the hash value of T, so this function does
not employ ownership movement. Thus we don't have to (and actually
can't) use T&& here.

The reason of changing |T| to |const T&| is to make it possible to
calculate a hash value of non-copyable (move-only) T. The old code
did a copy here.

+    template <typename HashTranslator, typename T> const ValueType* lookup(const T&) const;
 
     template <typename VisitorDispatcher> void trace(VisitorDispatcher);
 
 #if ENABLE(ASSERT)
     bool accessForbidden() const { return m_accessForbidden; }
     int64_t modifications() const { return m_modifications; }
     void registerModification() { m_modifications++; }
     // HashTable and collections that build on it do not support modifications
     // while there is an iterator in use. The exception is ListHashSet, which
     // has its own iterators that tolerate modification of the underlying set.
@@ skipping 129 matching lines @@
         newCapacity = KeyTraits::minimumTableSize;
 
     if (newCapacity > capacity()) {
         RELEASE_ASSERT(!static_cast<int>(newCapacity >> 31)); // HashTable capacity should not overflow 32bit int.
         rehash(newCapacity, 0);
     }
 }
 
 template <typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 template <typename HashTranslator, typename T>
-inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key)
+inline Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(const T& key)
 {
-    return const_cast<Value*>(const_cast<const HashTable*>(this)->lookup<HashTranslator, T>(key));
+    return const_cast<Value*>(const_cast<const HashTable*>(this)->lookup<HashTranslator>(key));
 }
 
 template <typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 template <typename HashTranslator, typename T>
-inline const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(T key) const
+inline const Value* HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::lookup(const T& key) const
 {
     ASSERT(!m_accessForbidden);
     ASSERT((HashTableKeyChecker<HashTranslator, KeyTraits, HashFunctions::safeToCompareToEmptyOrDeleted>::checkKey(key)));
     const ValueType* table = m_table;
     if (!table)
         return nullptr;
 
     size_t k = 0;
     size_t sizeMask = tableSizeMask();
     unsigned h = HashTranslator::hash(key);
@@ skipping 133 matching lines @@
 };
 
 template <typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::initializeBucket(ValueType& bucket)
 {
     HashTableBucketInitializer<Traits::emptyValueIsZero>::template initialize<Traits>(bucket);
 }
 
 template <typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits, typename Allocator>
 template <typename HashTranslator, typename T, typename Extra>
-typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::add(const T& key, const Extra& extra)
+typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::AddResult HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits, Allocator>::add(T&& key, Extra&& extra)
 {
     ASSERT(!m_accessForbidden);
     ASSERT(Allocator::isAllocationAllowed());
     if (!m_table)
         expand();
 
     ASSERT(m_table);
 
     ValueType* table = m_table;
     size_t k = 0;
     size_t sizeMask = tableSizeMask();
     unsigned h = HashTranslator::hash(key);

[tzik, 2016/03/04 15:29:59]

This is not directly related to this CL, but it makes me uneasy to use |key|
multiple times in this function.

If T is a different type to Key and is implicitly convertible to Key, e.g. T =
const char*, and Key = WTF::String, then each conversion from T&& to const Key&
will run Key::Key(const T&).
So, I think each HashTranslator::hash(key) and HashTranslator::equal(..., key)
make one WTF::String if the user passed a "foo" as |key|.

[Yuta Kitamura, 2016/03/07 04:36:27]

I don't plan to do that in this patch, but sounds plausible.

I think the complication here is we don't have a permanent storage for
key at this point, because that is what we are trying to find in this
function. Hmmm...

     size_t i = h & sizeMask;
 
     UPDATE_ACCESS_COUNTS();
 
     ValueType* deletedEntry = nullptr;
     ValueType* entry;
     while (1) {
         entry = table + i;
 
         if (isEmptyBucket(*entry))
@@ skipping 20 matching lines @@
     registerModification();
 
     if (deletedEntry) {
         // Overwrite any data left over from last use, using placement new or
         // memset.
         initializeBucket(*deletedEntry);
         entry = deletedEntry;
         --m_deletedCount;
     }
 
-    HashTranslator::translate(*entry, key, extra);
+    HashTranslator::translate(*entry, std::forward<T>(key), std::forward<Extra>(extra));
     ASSERT(!isEmptyOrDeletedBucket(*entry));
 
     ++m_keyCount;
 
     if (shouldExpand())
         entry = expand(entry);
 
     return AddResult(this, entry, true);
 }
 
@@ skipping 633 matching lines @@
     CollectionIterator end(toBeRemoved.end());
     for (CollectionIterator it(toBeRemoved.begin()); it != end; ++it)
         collection.remove(*it);
 }
 
 } // namespace WTF
 
 #include "wtf/HashIterators.h"
 
 #endif // WTF_HashTable_h