From 1b782176624c002a94e28d94b0ef3a8a900015d7 Mon Sep 17 00:00:00 2001
From: Justin Lebar <jlebar@google.com>
Date: Mon, 10 Oct 2016 16:25:59 +0000
Subject: [PATCH] [ADT] Let MapVector handle non-copyable values.

Summary: The keys must still be copyable, because we store two copies of them.

Reviewers: timshen

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D25404

llvm-svn: 283764
---
 llvm/include/llvm/ADT/MapVector.h    | 16 ++++++++++++++++
 llvm/unittests/ADT/MapVectorTest.cpp | 18 ++++++++++++++++++
 2 files changed, 34 insertions(+)

diff --git a/llvm/include/llvm/ADT/MapVector.h b/llvm/include/llvm/ADT/MapVector.h
index f19a50b..f4a29ef 100644
--- a/llvm/include/llvm/ADT/MapVector.h
+++ b/llvm/include/llvm/ADT/MapVector.h
@@ -83,7 +83,10 @@ public:
     return Vector[I].second;
   }
 
+  // Returns a copy of the value.  Only allowed if ValueT is copyable.
   ValueT lookup(const KeyT &Key) const {
+    static_assert(std::is_copy_constructible<ValueT>::value,
+                  "Cannot call lookup() if ValueT is not copyable.");
     typename MapType::const_iterator Pos = Map.find(Key);
     return Pos == Map.end()? ValueT() : Vector[Pos->second].second;
   }
@@ -100,6 +103,19 @@ public:
     return std::make_pair(begin() + I, false);
   }
 
+  std::pair<iterator, bool> insert(std::pair<KeyT, ValueT> &&KV) {
+    // Copy KV.first into the map, then move it into the vector.
+    std::pair<KeyT, unsigned> Pair = std::make_pair(KV.first, 0);
+    std::pair<typename MapType::iterator, bool> Result = Map.insert(Pair);
+    unsigned &I = Result.first->second;
+    if (Result.second) {
+      Vector.push_back(std::move(KV));
+      I = Vector.size() - 1;
+      return std::make_pair(std::prev(end()), true);
+    }
+    return std::make_pair(begin() + I, false);
+  }
+
   size_type count(const KeyT &Key) const {
     typename MapType::const_iterator Pos = Map.find(Key);
     return Pos == Map.end()? 0 : 1;
diff --git a/llvm/unittests/ADT/MapVectorTest.cpp b/llvm/unittests/ADT/MapVectorTest.cpp
index ff84642..f5b094f 100644
--- a/llvm/unittests/ADT/MapVectorTest.cpp
+++ b/llvm/unittests/ADT/MapVectorTest.cpp
@@ -148,6 +148,15 @@ TEST(MapVectorTest, iteration_test) {
   }
 }
 
+TEST(MapVectorTest, NonCopyable) {
+  MapVector<int, std::unique_ptr<int>> MV;
+  MV.insert(std::make_pair(1, llvm::make_unique<int>(1)));
+  MV.insert(std::make_pair(2, llvm::make_unique<int>(2)));
+
+  ASSERT_EQ(MV.count(1), 1u);
+  ASSERT_EQ(*MV.find(2)->second, 2);
+}
+
 TEST(SmallMapVectorSmallTest, insert_pop) {
   SmallMapVector<int, int, 32> MV;
   std::pair<SmallMapVector<int, int, 32>::iterator, bool> R;
@@ -257,6 +266,15 @@ TEST(SmallMapVectorSmallTest, iteration_test) {
   }
 }
 
+TEST(SmallMapVectorSmallTest, NonCopyable) {
+  SmallMapVector<int, std::unique_ptr<int>, 8> MV;
+  MV.insert(std::make_pair(1, llvm::make_unique<int>(1)));
+  MV.insert(std::make_pair(2, llvm::make_unique<int>(2)));
+
+  ASSERT_EQ(MV.count(1), 1u);
+  ASSERT_EQ(*MV.find(2)->second, 2);
+}
+
 TEST(SmallMapVectorLargeTest, insert_pop) {
   SmallMapVector<int, int, 1> MV;
   std::pair<SmallMapVector<int, int, 1>::iterator, bool> R;
-- 
2.7.4