aboutsummaryrefslogtreecommitdiff
path: root/llvm/unittests/ADT
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/unittests/ADT')
-rw-r--r--llvm/unittests/ADT/APFloatTest.cpp83
-rw-r--r--llvm/unittests/ADT/CMakeLists.txt1
-rw-r--r--llvm/unittests/ADT/DenseMapTest.cpp70
-rw-r--r--llvm/unittests/ADT/RadixTreeTest.cpp379
-rw-r--r--llvm/unittests/ADT/STLForwardCompatTest.cpp2
-rw-r--r--llvm/unittests/ADT/StringSwitchTest.cpp4
-rw-r--r--llvm/unittests/ADT/TrieRawHashMapTest.cpp2
7 files changed, 495 insertions, 46 deletions
diff --git a/llvm/unittests/ADT/APFloatTest.cpp b/llvm/unittests/ADT/APFloatTest.cpp
index 30f0a8e5..fbe96bb 100644
--- a/llvm/unittests/ADT/APFloatTest.cpp
+++ b/llvm/unittests/ADT/APFloatTest.cpp
@@ -5062,8 +5062,8 @@ TEST(APFloatTest, PPCDoubleDoubleAddSpecial) {
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected, RM) = Tp;
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.add(A2, RM);
EXPECT_EQ(Expected, A1.getCategory())
@@ -5072,8 +5072,8 @@ TEST(APFloatTest, PPCDoubleDoubleAddSpecial) {
.str();
}
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A2.add(A1, RM);
EXPECT_EQ(Expected, A2.getCategory())
@@ -5126,8 +5126,8 @@ TEST(APFloatTest, PPCDoubleDoubleAdd) {
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected[0], Expected[1], RM) = Tp;
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.add(A2, RM);
EXPECT_EQ(Expected[0], A1.bitcastToAPInt().getRawData()[0])
@@ -5140,8 +5140,8 @@ TEST(APFloatTest, PPCDoubleDoubleAdd) {
.str();
}
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A2.add(A1, RM);
EXPECT_EQ(Expected[0], A2.bitcastToAPInt().getRawData()[0])
@@ -5175,8 +5175,8 @@ TEST(APFloatTest, PPCDoubleDoubleSubtract) {
APFloat::roundingMode RM;
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected[0], Expected[1], RM) = Tp;
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.subtract(A2, RM);
EXPECT_EQ(Expected[0], A1.bitcastToAPInt().getRawData()[0])
@@ -5230,8 +5230,8 @@ TEST(APFloatTest, PPCDoubleDoubleMultiplySpecial) {
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected, RM) = Tp;
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.multiply(A2, RM);
EXPECT_EQ(Expected, A1.getCategory())
@@ -5240,8 +5240,8 @@ TEST(APFloatTest, PPCDoubleDoubleMultiplySpecial) {
.str();
}
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A2.multiply(A1, RM);
EXPECT_EQ(Expected, A2.getCategory())
@@ -5303,8 +5303,8 @@ TEST(APFloatTest, PPCDoubleDoubleMultiply) {
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected[0], Expected[1], RM) = Tp;
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.multiply(A2, RM);
EXPECT_EQ(Expected[0], A1.bitcastToAPInt().getRawData()[0])
@@ -5317,8 +5317,8 @@ TEST(APFloatTest, PPCDoubleDoubleMultiply) {
.str();
}
{
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A2.multiply(A1, RM);
EXPECT_EQ(Expected[0], A2.bitcastToAPInt().getRawData()[0])
@@ -5350,8 +5350,8 @@ TEST(APFloatTest, PPCDoubleDoubleDivide) {
APFloat::roundingMode RM;
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected[0], Expected[1], RM) = Tp;
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.divide(A2, RM);
EXPECT_EQ(Expected[0], A1.bitcastToAPInt().getRawData()[0])
@@ -5383,8 +5383,8 @@ TEST(APFloatTest, PPCDoubleDoubleRemainder) {
uint64_t Op1[2], Op2[2], Expected[2];
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected[0], Expected[1]) = Tp;
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.remainder(A2);
EXPECT_EQ(Expected[0], A1.bitcastToAPInt().getRawData()[0])
@@ -5418,8 +5418,8 @@ TEST(APFloatTest, PPCDoubleDoubleMod) {
uint64_t Op1[2], Op2[2], Expected[2];
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected[0], Expected[1]) = Tp;
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
A1.mod(A2);
EXPECT_EQ(Expected[0], A1.bitcastToAPInt().getRawData()[0])
@@ -6282,8 +6282,8 @@ TEST(APFloatTest, PPCDoubleDoubleCompare) {
APFloat::cmpResult Expected;
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected) = Tp;
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
EXPECT_EQ(Expected, A1.compare(A2))
<< formatv("compare(({0:x} + {1:x}), ({2:x} + {3:x}))", Op1[0], Op1[1],
Op2[0], Op2[1])
@@ -6410,8 +6410,8 @@ TEST(APFloatTest, PPCDoubleDoubleBitwiseIsEqual) {
bool Expected;
std::tie(Op1[0], Op1[1], Op2[0], Op2[1], Expected) = Tp;
- APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, 2, Op1));
- APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, 2, Op2));
+ APFloat A1(APFloat::PPCDoubleDouble(), APInt(128, Op1));
+ APFloat A2(APFloat::PPCDoubleDouble(), APInt(128, Op2));
EXPECT_EQ(Expected, A1.bitwiseIsEqual(A2))
<< formatv("({0:x} + {1:x}) = ({2:x} + {3:x})", Op1[0], Op1[1], Op2[0],
Op2[1])
@@ -6423,16 +6423,15 @@ TEST(APFloatTest, PPCDoubleDoubleHashValue) {
uint64_t Data1[] = {0x3ff0000000000001ull, 0x0000000000000001ull};
uint64_t Data2[] = {0x3ff0000000000001ull, 0};
// The hash values are *hopefully* different.
- EXPECT_NE(
- hash_value(APFloat(APFloat::PPCDoubleDouble(), APInt(128, 2, Data1))),
- hash_value(APFloat(APFloat::PPCDoubleDouble(), APInt(128, 2, Data2))));
+ EXPECT_NE(hash_value(APFloat(APFloat::PPCDoubleDouble(), APInt(128, Data1))),
+ hash_value(APFloat(APFloat::PPCDoubleDouble(), APInt(128, Data2))));
}
TEST(APFloatTest, PPCDoubleDoubleChangeSign) {
uint64_t Data[] = {
0x400f000000000000ull, 0xbcb0000000000000ull,
};
- APFloat Float(APFloat::PPCDoubleDouble(), APInt(128, 2, Data));
+ APFloat Float(APFloat::PPCDoubleDouble(), APInt(128, Data));
{
APFloat Actual =
APFloat::copySign(Float, APFloat(APFloat::IEEEdouble(), "1"));
@@ -6452,14 +6451,14 @@ TEST(APFloatTest, PPCDoubleDoubleFactories) {
uint64_t Data[] = {
0, 0,
};
- EXPECT_EQ(APInt(128, 2, Data),
+ EXPECT_EQ(APInt(128, Data),
APFloat::getZero(APFloat::PPCDoubleDouble()).bitcastToAPInt());
}
{
uint64_t Data[] = {
0x7fefffffffffffffull, 0x7c8ffffffffffffeull,
};
- EXPECT_EQ(APInt(128, 2, Data),
+ EXPECT_EQ(APInt(128, Data),
APFloat::getLargest(APFloat::PPCDoubleDouble()).bitcastToAPInt());
}
{
@@ -6467,12 +6466,12 @@ TEST(APFloatTest, PPCDoubleDoubleFactories) {
0x0000000000000001ull, 0,
};
EXPECT_EQ(
- APInt(128, 2, Data),
+ APInt(128, Data),
APFloat::getSmallest(APFloat::PPCDoubleDouble()).bitcastToAPInt());
}
{
uint64_t Data[] = {0x0360000000000000ull, 0};
- EXPECT_EQ(APInt(128, 2, Data),
+ EXPECT_EQ(APInt(128, Data),
APFloat::getSmallestNormalized(APFloat::PPCDoubleDouble())
.bitcastToAPInt());
}
@@ -6481,7 +6480,7 @@ TEST(APFloatTest, PPCDoubleDoubleFactories) {
0x8000000000000000ull, 0x0000000000000000ull,
};
EXPECT_EQ(
- APInt(128, 2, Data),
+ APInt(128, Data),
APFloat::getZero(APFloat::PPCDoubleDouble(), true).bitcastToAPInt());
}
{
@@ -6489,14 +6488,14 @@ TEST(APFloatTest, PPCDoubleDoubleFactories) {
0xffefffffffffffffull, 0xfc8ffffffffffffeull,
};
EXPECT_EQ(
- APInt(128, 2, Data),
+ APInt(128, Data),
APFloat::getLargest(APFloat::PPCDoubleDouble(), true).bitcastToAPInt());
}
{
uint64_t Data[] = {
0x8000000000000001ull, 0x0000000000000000ull,
};
- EXPECT_EQ(APInt(128, 2, Data),
+ EXPECT_EQ(APInt(128, Data),
APFloat::getSmallest(APFloat::PPCDoubleDouble(), true)
.bitcastToAPInt());
}
@@ -6504,7 +6503,7 @@ TEST(APFloatTest, PPCDoubleDoubleFactories) {
uint64_t Data[] = {
0x8360000000000000ull, 0x0000000000000000ull,
};
- EXPECT_EQ(APInt(128, 2, Data),
+ EXPECT_EQ(APInt(128, Data),
APFloat::getSmallestNormalized(APFloat::PPCDoubleDouble(), true)
.bitcastToAPInt());
}
@@ -6523,7 +6522,7 @@ TEST(APFloatTest, PPCDoubleDoubleIsDenormal) {
0x4010000000000000ull, 0x4008000000000000ull,
};
EXPECT_TRUE(
- APFloat(APFloat::PPCDoubleDouble(), APInt(128, 2, Data)).isDenormal());
+ APFloat(APFloat::PPCDoubleDouble(), APInt(128, Data)).isDenormal());
}
}
@@ -6533,7 +6532,7 @@ TEST(APFloatTest, PPCDoubleDoubleScalbn) {
0x4008000000000000ull, 0x3cb8000000000000ull,
};
APFloat Result =
- scalbn(APFloat(APFloat::PPCDoubleDouble(), APInt(128, 2, Input)), 1,
+ scalbn(APFloat(APFloat::PPCDoubleDouble(), APInt(128, Input)), 1,
APFloat::rmNearestTiesToEven);
// 6.0 + 6.0 << 53
EXPECT_EQ(0x4018000000000000ull, Result.bitcastToAPInt().getRawData()[0]);
diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt
index 848ccba..af503d9 100644
--- a/llvm/unittests/ADT/CMakeLists.txt
+++ b/llvm/unittests/ADT/CMakeLists.txt
@@ -63,6 +63,7 @@ add_llvm_unittest(ADTTests
PointerUnionTest.cpp
PostOrderIteratorTest.cpp
PriorityWorklistTest.cpp
+ RadixTreeTest.cpp
RangeAdapterTest.cpp
RewriteBufferTest.cpp
SCCIteratorTest.cpp
diff --git a/llvm/unittests/ADT/DenseMapTest.cpp b/llvm/unittests/ADT/DenseMapTest.cpp
index 50e9c6e..aceb4f3 100644
--- a/llvm/unittests/ADT/DenseMapTest.cpp
+++ b/llvm/unittests/ADT/DenseMapTest.cpp
@@ -70,6 +70,16 @@ public:
int getValue() const { return Value; }
bool operator==(const CtorTester &RHS) const { return Value == RHS.Value; }
+
+ // Return the number of live CtorTester objects, excluding the empty and
+ // tombstone keys.
+ static size_t getNumConstructed() {
+ return std::count_if(Constructed.begin(), Constructed.end(),
+ [](const CtorTester *Obj) {
+ int V = Obj->getValue();
+ return V != -1 && V != -2;
+ });
+ }
};
std::set<CtorTester *> CtorTester::Constructed;
@@ -1031,4 +1041,64 @@ TEST(SmallDenseMapCustomTest, InitSize) {
}
}
+TEST(DenseMapCustomTest, KeyDtor) {
+ // This test relies on CtorTester being non-trivially destructible.
+ static_assert(!std::is_trivially_destructible_v<CtorTester>,
+ "CtorTester must not be trivially destructible");
+
+ // Test that keys are destructed on scope exit.
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+ {
+ DenseMap<CtorTester, int, CtorTesterMapInfo> Map;
+ Map.try_emplace(CtorTester(0), 1);
+ Map.try_emplace(CtorTester(1), 2);
+ EXPECT_EQ(2u, CtorTester::getNumConstructed());
+ }
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+
+ // Test that keys are destructed on erase and shrink_and_clear.
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+ {
+ DenseMap<CtorTester, int, CtorTesterMapInfo> Map;
+ Map.try_emplace(CtorTester(0), 1);
+ Map.try_emplace(CtorTester(1), 2);
+ EXPECT_EQ(2u, CtorTester::getNumConstructed());
+ Map.erase(CtorTester(1));
+ EXPECT_EQ(1u, CtorTester::getNumConstructed());
+ Map.shrink_and_clear();
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+ }
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+}
+
+TEST(DenseMapCustomTest, ValueDtor) {
+ // This test relies on CtorTester being non-trivially destructible.
+ static_assert(!std::is_trivially_destructible_v<CtorTester>,
+ "CtorTester must not be trivially destructible");
+
+ // Test that values are destructed on scope exit.
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+ {
+ DenseMap<int, CtorTester> Map;
+ Map.try_emplace(0, CtorTester(1));
+ Map.try_emplace(1, CtorTester(2));
+ EXPECT_EQ(2u, CtorTester::getNumConstructed());
+ }
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+
+ // Test that values are destructed on erase and shrink_and_clear.
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+ {
+ DenseMap<int, CtorTester> Map;
+ Map.try_emplace(0, CtorTester(1));
+ Map.try_emplace(1, CtorTester(2));
+ EXPECT_EQ(2u, CtorTester::getNumConstructed());
+ Map.erase(1);
+ EXPECT_EQ(1u, CtorTester::getNumConstructed());
+ Map.shrink_and_clear();
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+ }
+ EXPECT_EQ(0u, CtorTester::getNumConstructed());
+}
+
} // namespace
diff --git a/llvm/unittests/ADT/RadixTreeTest.cpp b/llvm/unittests/ADT/RadixTreeTest.cpp
new file mode 100644
index 0000000..b2dd67c
--- /dev/null
+++ b/llvm/unittests/ADT/RadixTreeTest.cpp
@@ -0,0 +1,379 @@
+//===- llvm/unittest/ADT/RadixTreeTest.cpp --------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/RadixTree.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <iterator>
+#include <list>
+#include <vector>
+
+using namespace llvm;
+namespace {
+
+using ::testing::ElementsAre;
+using ::testing::ElementsAreArray;
+using ::testing::Pair;
+using ::testing::UnorderedElementsAre;
+
+// Test with StringRef.
+
+TEST(RadixTreeTest, Empty) {
+ RadixTree<StringRef, int> T;
+ EXPECT_TRUE(T.empty());
+ EXPECT_EQ(T.size(), 0u);
+
+ EXPECT_TRUE(T.find_prefixes("").empty());
+ EXPECT_TRUE(T.find_prefixes("A").empty());
+
+ EXPECT_EQ(T.countNodes(), 1u);
+}
+
+TEST(RadixTreeTest, InsertEmpty) {
+ RadixTree<StringRef, int> T;
+ auto [It, IsNew] = T.emplace("", 4);
+ EXPECT_TRUE(!T.empty());
+ EXPECT_EQ(T.size(), 1u);
+ EXPECT_TRUE(IsNew);
+ const auto &[K, V] = *It;
+ EXPECT_TRUE(K.empty());
+ EXPECT_EQ(4, V);
+
+ EXPECT_THAT(T, ElementsAre(Pair("", 4)));
+
+ EXPECT_THAT(T.find_prefixes(""), ElementsAre(Pair("", 4)));
+
+ EXPECT_THAT(T.find_prefixes("a"), ElementsAre(Pair("", 4)));
+
+ EXPECT_EQ(T.countNodes(), 1u);
+}
+
+TEST(RadixTreeTest, Complex) {
+ RadixTree<StringRef, int> T;
+ T.emplace("abcd", 1);
+ EXPECT_EQ(T.countNodes(), 2u);
+ T.emplace("abklm", 2);
+ EXPECT_EQ(T.countNodes(), 4u);
+ T.emplace("123abklm", 3);
+ EXPECT_EQ(T.countNodes(), 5u);
+ T.emplace("123abklm", 4);
+ EXPECT_EQ(T.countNodes(), 5u);
+ T.emplace("ab", 5);
+ EXPECT_EQ(T.countNodes(), 5u);
+ T.emplace("1234567", 6);
+ EXPECT_EQ(T.countNodes(), 7u);
+ T.emplace("123456", 7);
+ EXPECT_EQ(T.countNodes(), 8u);
+ T.emplace("123456789", 8);
+ EXPECT_EQ(T.countNodes(), 9u);
+
+ EXPECT_THAT(T, UnorderedElementsAre(Pair("abcd", 1), Pair("abklm", 2),
+ Pair("123abklm", 3), Pair("ab", 5),
+ Pair("1234567", 6), Pair("123456", 7),
+ Pair("123456789", 8)));
+
+ EXPECT_THAT(T.find_prefixes("1234567890"),
+ UnorderedElementsAre(Pair("1234567", 6), Pair("123456", 7),
+ Pair("123456789", 8)));
+
+ EXPECT_THAT(T.find_prefixes("123abklm"),
+ UnorderedElementsAre(Pair("123abklm", 3)));
+
+ EXPECT_THAT(T.find_prefixes("abcdefg"),
+ UnorderedElementsAre(Pair("abcd", 1), Pair("ab", 5)));
+
+ EXPECT_EQ(T.countNodes(), 9u);
+}
+
+TEST(RadixTreeTest, ValueWith2Parameters) {
+ RadixTree<StringRef, std::pair<std::string, int>> T;
+ T.emplace("abcd", "a", 3);
+
+ EXPECT_THAT(T, UnorderedElementsAre(Pair("abcd", Pair("a", 3))));
+}
+
+// Test different types, less readable.
+
+template <typename T> struct TestData {
+ static const T Data1[];
+ static const T Data2[];
+};
+
+template <> const char TestData<char>::Data1[] = "abcdedcba";
+template <> const char TestData<char>::Data2[] = "abCDEDCba";
+
+template <> const int TestData<int>::Data1[] = {1, 2, 3, 4, 5, 4, 3, 2, 1};
+template <> const int TestData<int>::Data2[] = {1, 2, 4, 8, 16, 8, 4, 2, 1};
+
+template <typename T> class RadixTreeTypeTest : public ::testing::Test {
+public:
+ using IteratorType = decltype(adl_begin(std::declval<const T &>()));
+ using CharType = remove_cvref_t<decltype(*adl_begin(std::declval<T &>()))>;
+
+ T make(const CharType *Data, size_t N) { return T(StringRef(Data, N)); }
+
+ T make1(size_t N) { return make(TestData<CharType>::Data1, N); }
+ T make2(size_t N) { return make(TestData<CharType>::Data2, N); }
+};
+
+template <>
+iterator_range<StringRef::const_iterator>
+RadixTreeTypeTest<iterator_range<StringRef::const_iterator>>::make(
+ const char *Data, size_t N) {
+ return StringRef(Data).take_front(N);
+}
+
+template <>
+iterator_range<StringRef::const_reverse_iterator>
+RadixTreeTypeTest<iterator_range<StringRef::const_reverse_iterator>>::make(
+ const char *Data, size_t N) {
+ return reverse(StringRef(Data).take_back(N));
+}
+
+template <>
+ArrayRef<int> RadixTreeTypeTest<ArrayRef<int>>::make(const int *Data,
+ size_t N) {
+ return ArrayRef<int>(Data, Data + N);
+}
+
+template <>
+std::vector<int> RadixTreeTypeTest<std::vector<int>>::make(const int *Data,
+ size_t N) {
+ return std::vector<int>(Data, Data + N);
+}
+
+template <>
+std::list<int> RadixTreeTypeTest<std::list<int>>::make(const int *Data,
+ size_t N) {
+ return std::list<int>(Data, Data + N);
+}
+
+class TypeNameGenerator {
+public:
+ template <typename T> static std::string GetName(int) {
+ if (std::is_same_v<T, StringRef>)
+ return "StringRef";
+ if (std::is_same_v<T, std::string>)
+ return "string";
+ if (std::is_same_v<T, iterator_range<StringRef::const_iterator>>)
+ return "iterator_range";
+ if (std::is_same_v<T, iterator_range<StringRef::const_reverse_iterator>>)
+ return "reverse_iterator_range";
+ if (std::is_same_v<T, ArrayRef<int>>)
+ return "ArrayRef";
+ if (std::is_same_v<T, std::vector<int>>)
+ return "vector";
+ if (std::is_same_v<T, std::list<int>>)
+ return "list";
+ return "Unknown";
+ }
+};
+
+using TestTypes =
+ ::testing::Types<StringRef, std::string,
+ iterator_range<StringRef::const_iterator>,
+ iterator_range<StringRef::const_reverse_iterator>,
+ ArrayRef<int>, std::vector<int>, std::list<int>>;
+
+TYPED_TEST_SUITE(RadixTreeTypeTest, TestTypes, TypeNameGenerator);
+
+TYPED_TEST(RadixTreeTypeTest, Helpers) {
+ for (size_t i = 0; i < 9; ++i) {
+ auto R1 = this->make1(i);
+ auto R2 = this->make2(i);
+ EXPECT_EQ(llvm::range_size(R1), i);
+ EXPECT_EQ(llvm::range_size(R2), i);
+ auto [I1, I2] = llvm::mismatch(R1, R2);
+ // Exactly 2 first elements of Data1 and Data2 must match.
+ EXPECT_EQ(std::distance(R1.begin(), I1), std::min<int>(2, i));
+ }
+}
+
+TYPED_TEST(RadixTreeTypeTest, Empty) {
+ RadixTree<TypeParam, int> T;
+ EXPECT_TRUE(T.empty());
+ EXPECT_EQ(T.size(), 0u);
+
+ EXPECT_TRUE(T.find_prefixes(this->make1(0)).empty());
+ EXPECT_TRUE(T.find_prefixes(this->make2(1)).empty());
+
+ EXPECT_EQ(T.countNodes(), 1u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertEmpty) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+ auto [It, IsNew] = T.emplace(this->make1(0), 5);
+ EXPECT_TRUE(!T.empty());
+ EXPECT_EQ(T.size(), 1u);
+ EXPECT_TRUE(IsNew);
+ const auto &[K, V] = *It;
+ EXPECT_TRUE(K.empty());
+ EXPECT_EQ(5, V);
+
+ EXPECT_THAT(T.find_prefixes(this->make1(0)),
+ ElementsAre(Pair(ElementsAre(), 5)));
+
+ EXPECT_THAT(T.find_prefixes(this->make2(1)),
+ ElementsAre(Pair(ElementsAre(), 5)));
+
+ EXPECT_THAT(T, ElementsAre(Pair(ElementsAre(), 5)));
+
+ EXPECT_EQ(T.countNodes(), 1u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertEmptyTwice) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+ T.emplace(this->make1(0), 5);
+ auto [It, IsNew] = T.emplace(this->make1(0), 6);
+ EXPECT_TRUE(!T.empty());
+ EXPECT_EQ(T.size(), 1u);
+ EXPECT_TRUE(!IsNew);
+ const auto &[K, V] = *It;
+ EXPECT_TRUE(K.empty());
+ EXPECT_EQ(5, V);
+
+ EXPECT_THAT(T.find_prefixes(this->make1(0)),
+ ElementsAre(Pair(ElementsAre(), 5)));
+
+ EXPECT_THAT(T.find_prefixes(this->make2(1)),
+ ElementsAre(Pair(ElementsAre(), 5)));
+
+ EXPECT_THAT(T, ElementsAre(Pair(ElementsAre(), 5)));
+
+ EXPECT_EQ(T.countNodes(), 1u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertOne) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+ auto [It, IsNew] = T.emplace(this->make1(1), 4);
+ EXPECT_TRUE(!T.empty());
+ EXPECT_EQ(T.size(), 1u);
+ EXPECT_TRUE(IsNew);
+ const auto &[K, V] = *It;
+ EXPECT_THAT(K, ElementsAreArray(this->make1(1)));
+ EXPECT_EQ(4, V);
+
+ EXPECT_THAT(T, ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(1)),
+ ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(2)),
+ ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));
+
+ EXPECT_EQ(T.countNodes(), 2u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertOneTwice) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+ T.emplace(this->make1(1), 4);
+ auto [It, IsNew] = T.emplace(this->make1(1), 4);
+ EXPECT_TRUE(!T.empty());
+ EXPECT_EQ(T.size(), 1u);
+ EXPECT_TRUE(!IsNew);
+
+ EXPECT_THAT(T, ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));
+ EXPECT_EQ(T.countNodes(), 2u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertSuperStrings) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+
+ for (size_t Len = 0; Len < 7; Len += 2) {
+ auto [It, IsNew] = T.emplace(this->make1(Len), Len);
+ EXPECT_TRUE(IsNew);
+ }
+
+ EXPECT_THAT(T,
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0),
+ Pair(ElementsAreArray(this->make1(2)), 2),
+ Pair(ElementsAreArray(this->make1(4)), 4),
+ Pair(ElementsAreArray(this->make1(6)), 6)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(0)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(3)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0),
+ Pair(ElementsAreArray(this->make1(2)), 2)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(7)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0),
+ Pair(ElementsAreArray(this->make1(2)), 2),
+ Pair(ElementsAreArray(this->make1(4)), 4),
+ Pair(ElementsAreArray(this->make1(6)), 6)));
+
+ EXPECT_EQ(T.countNodes(), 4u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertSubStrings) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+
+ for (size_t Len = 0; Len < 7; Len += 2) {
+ auto [It, IsNew] = T.emplace(this->make1(7 - Len), 7 - Len);
+ EXPECT_TRUE(IsNew);
+ }
+
+ EXPECT_THAT(T,
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1),
+ Pair(ElementsAreArray(this->make1(3)), 3),
+ Pair(ElementsAreArray(this->make1(5)), 5),
+ Pair(ElementsAreArray(this->make1(7)), 7)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(0)), UnorderedElementsAre());
+
+ EXPECT_THAT(T.find_prefixes(this->make1(3)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1),
+ Pair(ElementsAreArray(this->make1(3)), 3)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(6)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1),
+ Pair(ElementsAreArray(this->make1(3)), 3),
+ Pair(ElementsAreArray(this->make1(5)), 5)));
+
+ EXPECT_EQ(T.countNodes(), 5u);
+}
+
+TYPED_TEST(RadixTreeTypeTest, InsertVShape) {
+ using TreeType = RadixTree<TypeParam, int>;
+ TreeType T;
+
+ EXPECT_EQ(T.countNodes(), 1u);
+ T.emplace(this->make1(5), 15);
+ EXPECT_EQ(T.countNodes(), 2u);
+ T.emplace(this->make2(6), 26);
+ EXPECT_EQ(T.countNodes(), 4u);
+ T.emplace(this->make2(1), 21);
+ EXPECT_EQ(T.countNodes(), 5u);
+
+ EXPECT_THAT(T,
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make1(5)), 15),
+ Pair(ElementsAreArray(this->make2(6)), 26),
+ Pair(ElementsAreArray(this->make2(1)), 21)));
+
+ EXPECT_THAT(T.find_prefixes(this->make1(7)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make2(1)), 21),
+ Pair(ElementsAreArray(this->make1(5)), 15)));
+
+ EXPECT_THAT(T.find_prefixes(this->make2(7)),
+ UnorderedElementsAre(Pair(ElementsAreArray(this->make2(1)), 21),
+ Pair(ElementsAreArray(this->make2(6)), 26)));
+
+ EXPECT_EQ(T.countNodes(), 5u);
+}
+
+} // namespace
diff --git a/llvm/unittests/ADT/STLForwardCompatTest.cpp b/llvm/unittests/ADT/STLForwardCompatTest.cpp
index 2a97e8d..c6ae6e3 100644
--- a/llvm/unittests/ADT/STLForwardCompatTest.cpp
+++ b/llvm/unittests/ADT/STLForwardCompatTest.cpp
@@ -185,7 +185,7 @@ TEST(TransformTest, ToUnderlying) {
}
TEST(STLForwardCompatTest, IdentityCxx20) {
- llvm::identity_cxx20 identity;
+ llvm::identity identity;
// Test with an lvalue.
int X = 42;
diff --git a/llvm/unittests/ADT/StringSwitchTest.cpp b/llvm/unittests/ADT/StringSwitchTest.cpp
index d88a0ff..c94feb5 100644
--- a/llvm/unittests/ADT/StringSwitchTest.cpp
+++ b/llvm/unittests/ADT/StringSwitchTest.cpp
@@ -157,7 +157,7 @@ TEST(StringSwitchTest, Cases) {
auto Translate = [](StringRef S) {
return llvm::StringSwitch<OSType>(S)
- .Cases(StringLiteral::withInnerNUL("wind\0ws"), "win32", "winnt",
+ .Cases({StringLiteral::withInnerNUL("wind\0ws"), "win32", "winnt"},
OSType::Windows)
.Cases({"linux", "unix", "*nix", "posix"}, OSType::Linux)
.Cases({"macos", "osx"}, OSType::MacOS)
@@ -189,7 +189,7 @@ TEST(StringSwitchTest, CasesLower) {
auto Translate = [](StringRef S) {
return llvm::StringSwitch<OSType>(S)
- .CasesLower(StringLiteral::withInnerNUL("wind\0ws"), "win32", "winnt",
+ .CasesLower({StringLiteral::withInnerNUL("wind\0ws"), "win32", "winnt"},
OSType::Windows)
.CasesLower({"linux", "unix", "*nix", "posix"}, OSType::Linux)
.CasesLower({"macos", "osx"}, OSType::MacOS)
diff --git a/llvm/unittests/ADT/TrieRawHashMapTest.cpp b/llvm/unittests/ADT/TrieRawHashMapTest.cpp
index c9081f5..7a95f1d 100644
--- a/llvm/unittests/ADT/TrieRawHashMapTest.cpp
+++ b/llvm/unittests/ADT/TrieRawHashMapTest.cpp
@@ -64,7 +64,7 @@ public:
}
void destroyTrie() { Trie.reset(); }
- ~SimpleTrieHashMapTest() { destroyTrie(); }
+ ~SimpleTrieHashMapTest() override { destroyTrie(); }
// Use the number itself as hash to test the pathological case.
static HashType hash(uint64_t Num) {
generated by cgit v1.1 at 2025-10-28 19:59:25 +0000