aboutsummaryrefslogtreecommitdiff
path: root/llvm/unittests/ADT
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/unittests/ADT')
-rw-r--r--llvm/unittests/ADT/CMakeLists.txt1
-rw-r--r--llvm/unittests/ADT/RadixTreeTest.cpp379
-rw-r--r--llvm/unittests/ADT/STLExtrasTest.cpp32
-rw-r--r--llvm/unittests/ADT/STLForwardCompatTest.cpp2
-rw-r--r--llvm/unittests/ADT/SmallVectorTest.cpp39
5 files changed, 428 insertions, 25 deletions
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/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/STLExtrasTest.cpp b/llvm/unittests/ADT/STLExtrasTest.cpp
index 47469983..966b1f0 100644
--- a/llvm/unittests/ADT/STLExtrasTest.cpp
+++ b/llvm/unittests/ADT/STLExtrasTest.cpp
@@ -7,6 +7,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/StringRef.h"
#include "gmock/gmock.h"
#include "gtest/gtest.h"
@@ -27,6 +28,7 @@
using namespace llvm;
using testing::ElementsAre;
+using testing::ElementsAreArray;
using testing::UnorderedElementsAre;
namespace {
@@ -772,48 +774,30 @@ TEST(STLExtrasTest, DropBeginTest) {
SmallVector<int, 5> vec{0, 1, 2, 3, 4};
for (int n = 0; n < 5; ++n) {
- int i = n;
- for (auto &v : drop_begin(vec, n)) {
- EXPECT_EQ(v, i);
- i += 1;
- }
- EXPECT_EQ(i, 5);
+ EXPECT_THAT(drop_begin(vec, n),
+ ElementsAreArray(ArrayRef(&vec[n], vec.size() - n)));
}
}
TEST(STLExtrasTest, DropBeginDefaultTest) {
SmallVector<int, 5> vec{0, 1, 2, 3, 4};
- int i = 1;
- for (auto &v : drop_begin(vec)) {
- EXPECT_EQ(v, i);
- i += 1;
- }
- EXPECT_EQ(i, 5);
+ EXPECT_THAT(drop_begin(vec), ElementsAre(1, 2, 3, 4));
}
TEST(STLExtrasTest, DropEndTest) {
SmallVector<int, 5> vec{0, 1, 2, 3, 4};
for (int n = 0; n < 5; ++n) {
- int i = 0;
- for (auto &v : drop_end(vec, n)) {
- EXPECT_EQ(v, i);
- i += 1;
- }
- EXPECT_EQ(i, 5 - n);
+ EXPECT_THAT(drop_end(vec, n),
+ ElementsAreArray(ArrayRef(vec.data(), vec.size() - n)));
}
}
TEST(STLExtrasTest, DropEndDefaultTest) {
SmallVector<int, 5> vec{0, 1, 2, 3, 4};
- int i = 0;
- for (auto &v : drop_end(vec)) {
- EXPECT_EQ(v, i);
- i += 1;
- }
- EXPECT_EQ(i, 4);
+ EXPECT_THAT(drop_end(vec), ElementsAre(0, 1, 2, 3));
}
TEST(STLExtrasTest, MapRangeTest) {
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/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp
index e2e778f..1a01f30 100644
--- a/llvm/unittests/ADT/SmallVectorTest.cpp
+++ b/llvm/unittests/ADT/SmallVectorTest.cpp
@@ -13,6 +13,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/Support/Compiler.h"
+#include "gmock/gmock.h"
#include "gtest/gtest.h"
#include <list>
#include <stdarg.h>
@@ -599,6 +600,15 @@ TYPED_TEST(SmallVectorTest, AssignSmallVector) {
assertValuesInOrder(V, 2u, 7, 7);
}
+TYPED_TEST(SmallVectorTest, AssignArrayRef) {
+ SCOPED_TRACE("AssignArrayRef");
+ auto &V = this->theVector;
+ Constructable Other[] = {7, 8, 9};
+ V.push_back(Constructable(1));
+ V.assign(ArrayRef(Other));
+ assertValuesInOrder(V, 3u, 7, 8, 9);
+}
+
// Move-assign test
TYPED_TEST(SmallVectorTest, MoveAssignTest) {
SCOPED_TRACE("MoveAssignTest");
@@ -1147,6 +1157,17 @@ TEST(SmallVectorTest, InitializerList) {
EXPECT_TRUE(ArrayRef(V2).equals({4, 5, 3, 2}));
}
+namespace namespace_with_adl {
+struct MyVector {
+ std::vector<int> data;
+};
+
+std::vector<int>::const_iterator begin(const MyVector &V) {
+ return V.data.begin();
+}
+std::vector<int>::const_iterator end(const MyVector &V) { return V.data.end(); }
+} // namespace namespace_with_adl
+
TEST(SmallVectorTest, ToVector) {
{
std::vector<char> v = {'a', 'b', 'c'};
@@ -1164,6 +1185,15 @@ TEST(SmallVectorTest, ToVector) {
for (size_t I = 0; I < v.size(); ++I)
EXPECT_EQ(v[I], Vector[I]);
}
+ {
+ // Check that to_vector and to_vector_of work with types that require ADL
+ // for being/end iterators.
+ namespace_with_adl::MyVector V = {{1, 2, 3}};
+ auto IntVector = to_vector(V);
+ EXPECT_THAT(IntVector, testing::ElementsAre(1, 2, 3));
+ IntVector = to_vector<3>(V);
+ EXPECT_THAT(IntVector, testing::ElementsAre(1, 2, 3));
+ }
}
struct To {
@@ -1222,6 +1252,15 @@ TEST(SmallVectorTest, ToVectorOf) {
for (size_t I = 0; I < StdVector.size(); ++I)
EXPECT_EQ(StdVector[I], Vector[I]);
}
+ {
+ // Check that to_vector works with types that require ADL for being/end
+ // iterators.
+ namespace_with_adl::MyVector V = {{1, 2, 3}};
+ auto UnsignedVector = to_vector_of<unsigned>(V);
+ EXPECT_THAT(UnsignedVector, testing::ElementsAre(1u, 2u, 3u));
+ UnsignedVector = to_vector_of<unsigned, 3>(V);
+ EXPECT_THAT(UnsignedVector, testing::ElementsAre(1u, 2u, 3u));
+ }
}
template <class VectorT>
generated by cgit v1.1 at 2025-10-25 09:29:04 +0000