Support movable keys

Summary: Use the same trick as the values, so that non-copyable keys can be used in ConcurrentHashMap.

Reviewed By: yfeldblum

Differential Revision: D6252711

fbshipit-source-id: f0f168c4eb361d372bdfc3417f32222d66c11aaf

diff --git a/folly/concurrency/ConcurrentHashMap.h b/folly/concurrency/ConcurrentHashMap.h
index 4d8bd6e28ec4e06cac13a9c26e588c03fede759f..b4d2fc3a4a3e6c895c631b72e0786d34d3fa7109 100644 (file)
--- a/folly/concurrency/ConcurrentHashMap.h
+++ b/folly/concurrency/ConcurrentHashMap.h
@@ -201,25 +201,27 @@ class ConcurrentHashMap {
     return res;
   }
 
-  std::pair<ConstIterator, bool> insert(const KeyType& k, const ValueType& v) {
+  template <typename Key, typename Value>
+  std::pair<ConstIterator, bool> insert(Key&& k, Value&& v) {
     auto segment = pickSegment(k);
     std::pair<ConstIterator, bool> res(
         std::piecewise_construct,
         std::forward_as_tuple(this, segment),
         std::forward_as_tuple(false));
-    res.second = ensureSegment(segment)->insert(res.first.it_, k, v);
+    res.second = ensureSegment(segment)->insert(
+        res.first.it_, std::forward<Key>(k), std::forward<Value>(v));
     return res;
   }
 
-  template <typename... Args>
-  std::pair<ConstIterator, bool> try_emplace(const KeyType& k, Args&&... args) {
+  template <typename Key, typename... Args>
+  std::pair<ConstIterator, bool> try_emplace(Key&& k, Args&&... args) {
     auto segment = pickSegment(k);
     std::pair<ConstIterator, bool> res(
         std::piecewise_construct,
         std::forward_as_tuple(this, segment),
         std::forward_as_tuple(false));
     res.second = ensureSegment(segment)->try_emplace(
-        res.first.it_, k, std::forward<Args>(args)...);
+        res.first.it_, std::forward<Key>(k), std::forward<Args>(args)...);
     return res;
   }
 
@@ -242,26 +244,28 @@ class ConcurrentHashMap {
     return res;
   }
 
-  std::pair<ConstIterator, bool> insert_or_assign(
-      const KeyType& k,
-      const ValueType& v) {
+  template <typename Key, typename Value>
+  std::pair<ConstIterator, bool> insert_or_assign(Key&& k, Value&& v) {
     auto segment = pickSegment(k);
     std::pair<ConstIterator, bool> res(
         std::piecewise_construct,
         std::forward_as_tuple(this, segment),
         std::forward_as_tuple(false));
-    res.second = ensureSegment(segment)->insert_or_assign(res.first.it_, k, v);
+    res.second = ensureSegment(segment)->insert_or_assign(
+        res.first.it_, std::forward<Key>(k), std::forward<Value>(v));
     return res;
   }
 
-  folly::Optional<ConstIterator> assign(const KeyType& k, const ValueType& v) {
+  template <typename Key, typename Value>
+  folly::Optional<ConstIterator> assign(Key&& k, Value&& v) {
     auto segment = pickSegment(k);
     ConstIterator res(this, segment);
     auto seg = segments_[segment].load(std::memory_order_acquire);
     if (!seg) {
       return folly::Optional<ConstIterator>();
     } else {
-      auto r = seg->assign(res.it_, k, v);
+      auto r =
+          seg->assign(res.it_, std::forward<Key>(k), std::forward<Value>(v));
       if (!r) {
         return folly::Optional<ConstIterator>();
       }
@@ -270,17 +274,20 @@ class ConcurrentHashMap {
   }
 
   // Assign to desired if and only if key k is equal to expected
-  folly::Optional<ConstIterator> assign_if_equal(
-      const KeyType& k,
-      const ValueType& expected,
-      const ValueType& desired) {
+  template <typename Key, typename Value>
+  folly::Optional<ConstIterator>
+  assign_if_equal(Key&& k, const ValueType& expected, Value&& desired) {
     auto segment = pickSegment(k);
     ConstIterator res(this, segment);
     auto seg = segments_[segment].load(std::memory_order_acquire);
     if (!seg) {
       return folly::Optional<ConstIterator>();
     } else {
-      auto r = seg->assign_if_equal(res.it_, k, expected, desired);
+      auto r = seg->assign_if_equal(
+          res.it_,
+          std::forward<Key>(k),
+          expected,
+          std::forward<Value>(desired));
       if (!r) {
         return folly::Optional<ConstIterator>();
       }

diff --git a/folly/concurrency/detail/ConcurrentHashMap-detail.h b/folly/concurrency/detail/ConcurrentHashMap-detail.h
index 6af07feef71e461977e2ee9aaa33ab827b52ffc0..ecdf13a475cb9c4061c01253ffdd96f5d3fcd328 100644 (file)
--- a/folly/concurrency/detail/ConcurrentHashMap-detail.h
+++ b/folly/concurrency/detail/ConcurrentHashMap-detail.h
@@ -47,11 +47,11 @@ class ValueHolder {
 
   explicit ValueHolder(const ValueHolder& other) : item_(other.item_) {}
 
-  template <typename... Args>
-  ValueHolder(const KeyType& k, Args&&... args)
+  template <typename Arg, typename... Args>
+  ValueHolder(std::piecewise_construct_t, Arg&& k, Args&&... args)
       : item_(
             std::piecewise_construct,
-            std::forward_as_tuple(k),
+            std::forward_as_tuple(std::forward<Arg>(k)),
             std::forward_as_tuple(std::forward<Args>(args)...)) {}
   value_type& getItem() {
     return item_;
@@ -69,7 +69,9 @@ class ValueHolder<
     KeyType,
     ValueType,
     Allocator,
-    std::enable_if_t<!std::is_nothrow_copy_constructible<ValueType>::value>> {
+    std::enable_if_t<
+        !std::is_nothrow_copy_constructible<ValueType>::value ||
+        !std::is_nothrow_copy_constructible<KeyType>::value>> {
  public:
   typedef std::pair<const KeyType, ValueType> value_type;
 
@@ -78,12 +80,12 @@ class ValueHolder<
     item_ = other.item_;
   }
 
-  template <typename... Args>
-  ValueHolder(const KeyType& k, Args&&... args) {
+  template <typename Arg, typename... Args>
+  ValueHolder(std::piecewise_construct_t, Arg&& k, Args&&... args) {
     item_ = (value_type*)Allocator().allocate(sizeof(value_type));
     new (item_) value_type(
         std::piecewise_construct,
-        std::forward_as_tuple(k),
+        std::forward_as_tuple(std::forward<Arg>(k)),
         std::forward_as_tuple(std::forward<Args>(args)...));
   }
 
@@ -116,9 +118,12 @@ class NodeT : public folly::hazptr::hazptr_obj_base<
 
   explicit NodeT(NodeT* other) : item_(other->item_) {}
 
-  template <typename... Args>
-  NodeT(const KeyType& k, Args&&... args)
-      : item_(k, std::forward<Args>(args)...) {}
+  template <typename Arg, typename... Args>
+  NodeT(Arg&& k, Args&&... args)
+      : item_(
+            std::piecewise_construct,
+            std::forward<Arg>(k),
+            std::forward<Args>(args)...) {}
 
   /* Nodes are refcounted: If a node is retired() while a writer is
      traversing the chain, the rest of the chain must remain valid
@@ -244,19 +249,20 @@ class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
   }
 
   bool insert(Iterator& it, std::pair<key_type, mapped_type>&& foo) {
-    return insert(it, foo.first, foo.second);
+    return insert(it, std::move(foo.first), std::move(foo.second));
   }
 
-  bool insert(Iterator& it, const KeyType& k, const ValueType& v) {
+  template <typename Key, typename Value>
+  bool insert(Iterator& it, Key&& k, Value&& v) {
     auto node = (Node*)Allocator().allocate(sizeof(Node));
-    new (node) Node(k, v);
+    new (node) Node(std::forward<Key>(k), std::forward<Value>(v));
     auto res = insert_internal(
         it,
-        k,
+        node->getItem().first,
         InsertType::DOES_NOT_EXIST,
         [](const ValueType&) { return false; },
         node,
-        v);
+        node);
     if (!res) {
       node->~Node();
       Allocator().deallocate((uint8_t*)node, sizeof(Node));
@@ -264,14 +270,17 @@ class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
     return res;
   }
 
-  template <typename... Args>
-  bool try_emplace(Iterator& it, const KeyType& k, Args&&... args) {
+  template <typename Key, typename... Args>
+  bool try_emplace(Iterator& it, Key&& k, Args&&... args) {
+    // Note: first key is only ever compared.  Second is moved in to
+    // create the node, and the first key is never touched again.
     return insert_internal(
         it,
-        k,
+        std::forward<Key>(k),
         InsertType::DOES_NOT_EXIST,
         [](const ValueType&) { return false; },
         nullptr,
+        std::forward<Key>(k),
         std::forward<Args>(args)...);
   }
 
@@ -282,29 +291,39 @@ class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
         k,
         InsertType::DOES_NOT_EXIST,
         [](const ValueType&) { return false; },
+        node,
         node);
   }
 
-  bool insert_or_assign(Iterator& it, const KeyType& k, const ValueType& v) {
-    return insert_internal(
+  template <typename Key, typename Value>
+  bool insert_or_assign(Iterator& it, Key&& k, Value&& v) {
+    auto node = (Node*)Allocator().allocate(sizeof(Node));
+    new (node) Node(std::forward<Key>(k), std::forward<Value>(v));
+    auto res = insert_internal(
         it,
-        k,
+        node->getItem().first,
         InsertType::ANY,
         [](const ValueType&) { return false; },
-        nullptr,
-        v);
+        node,
+        node);
+    if (!res) {
+      node->~Node();
+      Allocator().deallocate((uint8_t*)node, sizeof(Node));
+    }
+    return res;
   }
 
-  bool assign(Iterator& it, const KeyType& k, const ValueType& v) {
+  template <typename Key, typename Value>
+  bool assign(Iterator& it, Key&& k, Value&& v) {
     auto node = (Node*)Allocator().allocate(sizeof(Node));
-    new (node) Node(k, v);
+    new (node) Node(std::forward<Key>(k), std::forward<Value>(v));
     auto res = insert_internal(
         it,
-        k,
+        node->getItem().first,
         InsertType::MUST_EXIST,
         [](const ValueType&) { return false; },
         node,
-        v);
+        node);
     if (!res) {
       node->~Node();
       Allocator().deallocate((uint8_t*)node, sizeof(Node));
@@ -312,18 +331,26 @@ class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
     return res;
   }
 
+  template <typename Key, typename Value>
   bool assign_if_equal(
       Iterator& it,
-      const KeyType& k,
+      Key&& k,
       const ValueType& expected,
-      const ValueType& desired) {
-    return insert_internal(
+      Value&& desired) {
+    auto node = (Node*)Allocator().allocate(sizeof(Node));
+    new (node) Node(std::forward<Key>(k), std::forward<Value>(desired));
+    auto res = insert_internal(
         it,
-        k,
+        node->getItem().first,
         InsertType::MATCH,
-        [expected](const ValueType& v) { return v == expected; },
-        nullptr,
-        desired);
+        [&expected](const ValueType& v) { return v == expected; },
+        node,
+        node);
+    if (!res) {
+      node->~Node();
+      Allocator().deallocate((uint8_t*)node, sizeof(Node));
+    }
+    return res;
   }
 
   template <typename MatchFunc, typename... Args>
@@ -369,7 +396,7 @@ class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
         } else {
           if (!cur) {
             cur = (Node*)Allocator().allocate(sizeof(Node));
-            new (cur) Node(k, std::forward<Args>(args)...);
+            new (cur) Node(std::forward<Args>(args)...);
           }
           auto next = node->next_.load(std::memory_order_relaxed);
           cur->next_.store(next, std::memory_order_relaxed);
@@ -415,7 +442,7 @@ class FOLLY_ALIGNED(64) ConcurrentHashMapSegment {
       // OR DOES_NOT_EXIST, but only in the try_emplace case
       DCHECK(type == InsertType::ANY || type == InsertType::DOES_NOT_EXIST);
       cur = (Node*)Allocator().allocate(sizeof(Node));
-      new (cur) Node(k, std::forward<Args>(args)...);
+      new (cur) Node(std::forward<Args>(args)...);
     }
     cur->next_.store(headnode, std::memory_order_relaxed);
     head->store(cur, std::memory_order_release);

diff --git a/folly/concurrency/test/ConcurrentHashMapTest.cpp b/folly/concurrency/test/ConcurrentHashMapTest.cpp
index 824d37da35f4940b711495fd1d95f63ef1f2f658..b1b18e42d7a34d2eaf86eb2c062209dd1f2f01e9 100644 (file)
--- a/folly/concurrency/test/ConcurrentHashMapTest.cpp
+++ b/folly/concurrency/test/ConcurrentHashMapTest.cpp
@@ -114,7 +114,8 @@ int foo::copied{0};
 
 TEST(ConcurrentHashMap, EmplaceTest) {
   ConcurrentHashMap<uint64_t, foo> foomap(200);
-  foomap.insert(1, foo());
+  foo bar; // Make sure to test copy
+  foomap.insert(1, bar);
   EXPECT_EQ(foo::moved, 0);
   EXPECT_EQ(foo::copied, 1);
   foo::copied = 0;
@@ -151,12 +152,21 @@ TEST(ConcurrentHashMap, MapResizeTest) {
 // Ensure we can insert objects without copy constructors.
 TEST(ConcurrentHashMap, MapNoCopiesTest) {
   struct Uncopyable {
+    int i_;
     Uncopyable(int i) {
-      (void*)&i;
+      i_ = i;
     }
     Uncopyable(const Uncopyable& that) = delete;
+    bool operator==(const Uncopyable& o) const {
+      return i_ == o.i_;
+    }
+  };
+  struct Hasher {
+    size_t operator()(const Uncopyable&) const {
+      return 0;
+    }
   };
-  ConcurrentHashMap<uint64_t, Uncopyable> foomap(2);
+  ConcurrentHashMap<Uncopyable, Uncopyable, Hasher> foomap(2);
   EXPECT_TRUE(foomap.try_emplace(1, 1).second);
   EXPECT_TRUE(foomap.try_emplace(2, 2).second);
   auto res = foomap.find(2);
@@ -169,6 +179,37 @@ TEST(ConcurrentHashMap, MapNoCopiesTest) {
   EXPECT_EQ(&(res->second), &(res2->second));
 }
 
+TEST(ConcurrentHashMap, MapMovableKeysTest) {
+  struct Movable {
+    int i_;
+    Movable(int i) {
+      i_ = i;
+    }
+    Movable(const Movable&) = delete;
+    Movable(Movable&& o) {
+      i_ = o.i_;
+      o.i_ = 0;
+    }
+    bool operator==(const Movable& o) const {
+      return i_ == o.i_;
+    }
+  };
+  struct Hasher {
+    size_t operator()(const Movable&) const {
+      return 0;
+    }
+  };
+  ConcurrentHashMap<Movable, Movable, Hasher> foomap(2);
+  EXPECT_TRUE(foomap.insert(std::make_pair(Movable(10), Movable(1))).second);
+  EXPECT_TRUE(foomap.assign(Movable(10), Movable(2)));
+  EXPECT_TRUE(foomap.insert(Movable(11), Movable(1)).second);
+  EXPECT_TRUE(foomap.emplace(Movable(12), Movable(1)).second);
+  EXPECT_TRUE(foomap.insert_or_assign(Movable(10), Movable(3)).second);
+  EXPECT_TRUE(foomap.assign_if_equal(Movable(10), Movable(3), Movable(4)));
+  EXPECT_FALSE(foomap.try_emplace(Movable(10), Movable(3)).second);
+  EXPECT_TRUE(foomap.try_emplace(Movable(13), Movable(3)).second);
+}
+
 TEST(ConcurrentHashMap, MapUpdateTest) {
   ConcurrentHashMap<uint64_t, uint64_t> foomap(2);
   EXPECT_TRUE(foomap.insert(1, 10).second);