https://github.com/optimisan updated
https://github.com/llvm/llvm-project/pull/116617
>From 69c604aacd3a71b3559dbc96721eef2ef06200f7 Mon Sep 17 00:00:00 2001
From: Akshat Oke <akshat....@amd.com>
Date: Mon, 18 Nov 2024 10:15:19 +0000
Subject: [PATCH 1/2] [NFC] Use unique_ptr in SparseSet
This allows implementing the move constructor.
---
llvm/include/llvm/ADT/SparseSet.h | 18 +++++++++++-------
1 file changed, 11 insertions(+), 7 deletions(-)
diff --git a/llvm/include/llvm/ADT/SparseSet.h
b/llvm/include/llvm/ADT/SparseSet.h
index c7793117ff5408..1adae0d4595ac4 100644
--- a/llvm/include/llvm/ADT/SparseSet.h
+++ b/llvm/include/llvm/ADT/SparseSet.h
@@ -129,7 +129,12 @@ class SparseSet {
using DenseT = SmallVector<ValueT, 8>;
using size_type = unsigned;
DenseT Dense;
- SparseT *Sparse = nullptr;
+
+ struct Deleter {
+ void operator()(SparseT *S) { free(S); }
+ };
+ std::unique_ptr<SparseT, Deleter> Sparse;
+
unsigned Universe = 0;
KeyFunctorT KeyIndexOf;
SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf;
@@ -144,7 +149,7 @@ class SparseSet {
SparseSet() = default;
SparseSet(const SparseSet &) = delete;
SparseSet &operator=(const SparseSet &) = delete;
- ~SparseSet() { free(Sparse); }
+ SparseSet(SparseSet &&) = default;
/// setUniverse - Set the universe size which determines the largest key the
/// set can hold. The universe must be sized before any elements can be
@@ -159,11 +164,10 @@ class SparseSet {
// Hysteresis prevents needless reallocations.
if (U >= Universe/4 && U <= Universe)
return;
- free(Sparse);
// The Sparse array doesn't actually need to be initialized, so malloc
// would be enough here, but that will cause tools like valgrind to
// complain about branching on uninitialized data.
- Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT)));
+ Sparse.reset(static_cast<SparseT *>(safe_calloc(U, sizeof(SparseT))));
Universe = U;
}
@@ -205,7 +209,7 @@ class SparseSet {
assert(Idx < Universe && "Key out of range");
assert(Sparse != nullptr && "Invalid sparse type");
const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u;
- for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) {
+ for (unsigned i = Sparse.get()[Idx], e = size(); i < e; i += Stride) {
const unsigned FoundIdx = ValIndexOf(Dense[i]);
assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?");
if (Idx == FoundIdx)
@@ -255,7 +259,7 @@ class SparseSet {
iterator I = findIndex(Idx);
if (I != end())
return std::make_pair(I, false);
- Sparse[Idx] = size();
+ Sparse.get()[Idx] = size();
Dense.push_back(Val);
return std::make_pair(end() - 1, true);
}
@@ -292,7 +296,7 @@ class SparseSet {
*I = Dense.back();
unsigned BackIdx = ValIndexOf(Dense.back());
assert(BackIdx < Universe && "Invalid key in set. Did object mutate?");
- Sparse[BackIdx] = I - begin();
+ Sparse.get()[BackIdx] = I - begin();
}
// This depends on SmallVector::pop_back() not invalidating iterators.
// std::vector::pop_back() doesn't give that guarantee.
>From a1eb74abec2072a368fc7e7d63331c266533652f Mon Sep 17 00:00:00 2001
From: Akshat Oke <akshat....@amd.com>
Date: Tue, 19 Nov 2024 08:40:06 +0000
Subject: [PATCH 2/2] Use SparseT[] and add test
---
llvm/include/llvm/ADT/SparseSet.h | 8 ++++----
llvm/unittests/ADT/SparseSetTest.cpp | 12 ++++++++++++
2 files changed, 16 insertions(+), 4 deletions(-)
diff --git a/llvm/include/llvm/ADT/SparseSet.h
b/llvm/include/llvm/ADT/SparseSet.h
index 1adae0d4595ac4..d9ded9875d3779 100644
--- a/llvm/include/llvm/ADT/SparseSet.h
+++ b/llvm/include/llvm/ADT/SparseSet.h
@@ -133,7 +133,7 @@ class SparseSet {
struct Deleter {
void operator()(SparseT *S) { free(S); }
};
- std::unique_ptr<SparseT, Deleter> Sparse;
+ std::unique_ptr<SparseT[], Deleter> Sparse;
unsigned Universe = 0;
KeyFunctorT KeyIndexOf;
@@ -209,7 +209,7 @@ class SparseSet {
assert(Idx < Universe && "Key out of range");
assert(Sparse != nullptr && "Invalid sparse type");
const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u;
- for (unsigned i = Sparse.get()[Idx], e = size(); i < e; i += Stride) {
+ for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride) {
const unsigned FoundIdx = ValIndexOf(Dense[i]);
assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?");
if (Idx == FoundIdx)
@@ -259,7 +259,7 @@ class SparseSet {
iterator I = findIndex(Idx);
if (I != end())
return std::make_pair(I, false);
- Sparse.get()[Idx] = size();
+ Sparse[Idx] = size();
Dense.push_back(Val);
return std::make_pair(end() - 1, true);
}
@@ -296,7 +296,7 @@ class SparseSet {
*I = Dense.back();
unsigned BackIdx = ValIndexOf(Dense.back());
assert(BackIdx < Universe && "Invalid key in set. Did object mutate?");
- Sparse.get()[BackIdx] = I - begin();
+ Sparse[BackIdx] = I - begin();
}
// This depends on SmallVector::pop_back() not invalidating iterators.
// std::vector::pop_back() doesn't give that guarantee.
diff --git a/llvm/unittests/ADT/SparseSetTest.cpp
b/llvm/unittests/ADT/SparseSetTest.cpp
index 3eea4bde8c07cc..4fbf1caa247b79 100644
--- a/llvm/unittests/ADT/SparseSetTest.cpp
+++ b/llvm/unittests/ADT/SparseSetTest.cpp
@@ -204,4 +204,16 @@ TEST(SparseSetTest, PopBack) {
for (unsigned i = 0; i < UpperBound; ++i)
ASSERT_TRUE(Set.insert(i).second);
}
+
+TEST(SparseSetTest, MoveConstructor) {
+ USet Set;
+ Set.setUniverse(2);
+ Set.insert(1);
+ EXPECT_FALSE(Set.empty());
+ // Move and check original is empty.
+ USet OtherSet(std::move(Set));
+ EXPECT_TRUE(Set.empty());
+ EXPECT_TRUE(OtherSet.contains(1));
+}
+
} // namespace
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
