380 lines · cpp
1//===- llvm/unittest/ADT/RadixTreeTest.cpp --------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/RadixTree.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/STLExtras.h"12#include "llvm/ADT/StringRef.h"13#include "gmock/gmock.h"14#include "gtest/gtest.h"15#include <iterator>16#include <list>17#include <vector>18 19using namespace llvm;20namespace {21 22using ::testing::ElementsAre;23using ::testing::ElementsAreArray;24using ::testing::Pair;25using ::testing::UnorderedElementsAre;26 27// Test with StringRef.28 29TEST(RadixTreeTest, Empty) {30 RadixTree<StringRef, int> T;31 EXPECT_TRUE(T.empty());32 EXPECT_EQ(T.size(), 0u);33 34 EXPECT_TRUE(T.find_prefixes("").empty());35 EXPECT_TRUE(T.find_prefixes("A").empty());36 37 EXPECT_EQ(T.countNodes(), 1u);38}39 40TEST(RadixTreeTest, InsertEmpty) {41 RadixTree<StringRef, int> T;42 auto [It, IsNew] = T.emplace("", 4);43 EXPECT_TRUE(!T.empty());44 EXPECT_EQ(T.size(), 1u);45 EXPECT_TRUE(IsNew);46 const auto &[K, V] = *It;47 EXPECT_TRUE(K.empty());48 EXPECT_EQ(4, V);49 50 EXPECT_THAT(T, ElementsAre(Pair("", 4)));51 52 EXPECT_THAT(T.find_prefixes(""), ElementsAre(Pair("", 4)));53 54 EXPECT_THAT(T.find_prefixes("a"), ElementsAre(Pair("", 4)));55 56 EXPECT_EQ(T.countNodes(), 1u);57}58 59TEST(RadixTreeTest, Complex) {60 RadixTree<StringRef, int> T;61 T.emplace("abcd", 1);62 EXPECT_EQ(T.countNodes(), 2u);63 T.emplace("abklm", 2);64 EXPECT_EQ(T.countNodes(), 4u);65 T.emplace("123abklm", 3);66 EXPECT_EQ(T.countNodes(), 5u);67 T.emplace("123abklm", 4);68 EXPECT_EQ(T.countNodes(), 5u);69 T.emplace("ab", 5);70 EXPECT_EQ(T.countNodes(), 5u);71 T.emplace("1234567", 6);72 EXPECT_EQ(T.countNodes(), 7u);73 T.emplace("123456", 7);74 EXPECT_EQ(T.countNodes(), 8u);75 T.emplace("123456789", 8);76 EXPECT_EQ(T.countNodes(), 9u);77 78 EXPECT_THAT(T, UnorderedElementsAre(Pair("abcd", 1), Pair("abklm", 2),79 Pair("123abklm", 3), Pair("ab", 5),80 Pair("1234567", 6), Pair("123456", 7),81 Pair("123456789", 8)));82 83 EXPECT_THAT(T.find_prefixes("1234567890"),84 UnorderedElementsAre(Pair("1234567", 6), Pair("123456", 7),85 Pair("123456789", 8)));86 87 EXPECT_THAT(T.find_prefixes("123abklm"),88 UnorderedElementsAre(Pair("123abklm", 3)));89 90 EXPECT_THAT(T.find_prefixes("abcdefg"),91 UnorderedElementsAre(Pair("abcd", 1), Pair("ab", 5)));92 93 EXPECT_EQ(T.countNodes(), 9u);94}95 96TEST(RadixTreeTest, ValueWith2Parameters) {97 RadixTree<StringRef, std::pair<std::string, int>> T;98 T.emplace("abcd", "a", 3);99 100 EXPECT_THAT(T, UnorderedElementsAre(Pair("abcd", Pair("a", 3))));101}102 103// Test different types, less readable.104 105template <typename T> struct TestData {106 static const T Data1[];107 static const T Data2[];108};109 110template <> const char TestData<char>::Data1[] = "abcdedcba";111template <> const char TestData<char>::Data2[] = "abCDEDCba";112 113template <> const int TestData<int>::Data1[] = {1, 2, 3, 4, 5, 4, 3, 2, 1};114template <> const int TestData<int>::Data2[] = {1, 2, 4, 8, 16, 8, 4, 2, 1};115 116template <typename T> class RadixTreeTypeTest : public ::testing::Test {117public:118 using IteratorType = decltype(adl_begin(std::declval<const T &>()));119 using CharType = remove_cvref_t<decltype(*adl_begin(std::declval<T &>()))>;120 121 T make(const CharType *Data, size_t N) { return T(StringRef(Data, N)); }122 123 T make1(size_t N) { return make(TestData<CharType>::Data1, N); }124 T make2(size_t N) { return make(TestData<CharType>::Data2, N); }125};126 127template <>128iterator_range<StringRef::const_iterator>129RadixTreeTypeTest<iterator_range<StringRef::const_iterator>>::make(130 const char *Data, size_t N) {131 return StringRef(Data).take_front(N);132}133 134template <>135iterator_range<StringRef::const_reverse_iterator>136RadixTreeTypeTest<iterator_range<StringRef::const_reverse_iterator>>::make(137 const char *Data, size_t N) {138 return reverse(StringRef(Data).take_back(N));139}140 141template <>142ArrayRef<int> RadixTreeTypeTest<ArrayRef<int>>::make(const int *Data,143 size_t N) {144 return ArrayRef<int>(Data, Data + N);145}146 147template <>148std::vector<int> RadixTreeTypeTest<std::vector<int>>::make(const int *Data,149 size_t N) {150 return std::vector<int>(Data, Data + N);151}152 153template <>154std::list<int> RadixTreeTypeTest<std::list<int>>::make(const int *Data,155 size_t N) {156 return std::list<int>(Data, Data + N);157}158 159class TypeNameGenerator {160public:161 template <typename T> static std::string GetName(int) {162 if (std::is_same_v<T, StringRef>)163 return "StringRef";164 if (std::is_same_v<T, std::string>)165 return "string";166 if (std::is_same_v<T, iterator_range<StringRef::const_iterator>>)167 return "iterator_range";168 if (std::is_same_v<T, iterator_range<StringRef::const_reverse_iterator>>)169 return "reverse_iterator_range";170 if (std::is_same_v<T, ArrayRef<int>>)171 return "ArrayRef";172 if (std::is_same_v<T, std::vector<int>>)173 return "vector";174 if (std::is_same_v<T, std::list<int>>)175 return "list";176 return "Unknown";177 }178};179 180using TestTypes =181 ::testing::Types<StringRef, std::string,182 iterator_range<StringRef::const_iterator>,183 iterator_range<StringRef::const_reverse_iterator>,184 ArrayRef<int>, std::vector<int>, std::list<int>>;185 186TYPED_TEST_SUITE(RadixTreeTypeTest, TestTypes, TypeNameGenerator);187 188TYPED_TEST(RadixTreeTypeTest, Helpers) {189 for (size_t i = 0; i < 9; ++i) {190 auto R1 = this->make1(i);191 auto R2 = this->make2(i);192 EXPECT_EQ(llvm::range_size(R1), i);193 EXPECT_EQ(llvm::range_size(R2), i);194 auto [I1, I2] = llvm::mismatch(R1, R2);195 // Exactly 2 first elements of Data1 and Data2 must match.196 EXPECT_EQ(std::distance(R1.begin(), I1), std::min<int>(2, i));197 }198}199 200TYPED_TEST(RadixTreeTypeTest, Empty) {201 RadixTree<TypeParam, int> T;202 EXPECT_TRUE(T.empty());203 EXPECT_EQ(T.size(), 0u);204 205 EXPECT_TRUE(T.find_prefixes(this->make1(0)).empty());206 EXPECT_TRUE(T.find_prefixes(this->make2(1)).empty());207 208 EXPECT_EQ(T.countNodes(), 1u);209}210 211TYPED_TEST(RadixTreeTypeTest, InsertEmpty) {212 using TreeType = RadixTree<TypeParam, int>;213 TreeType T;214 auto [It, IsNew] = T.emplace(this->make1(0), 5);215 EXPECT_TRUE(!T.empty());216 EXPECT_EQ(T.size(), 1u);217 EXPECT_TRUE(IsNew);218 const auto &[K, V] = *It;219 EXPECT_TRUE(K.empty());220 EXPECT_EQ(5, V);221 222 EXPECT_THAT(T.find_prefixes(this->make1(0)),223 ElementsAre(Pair(ElementsAre(), 5)));224 225 EXPECT_THAT(T.find_prefixes(this->make2(1)),226 ElementsAre(Pair(ElementsAre(), 5)));227 228 EXPECT_THAT(T, ElementsAre(Pair(ElementsAre(), 5)));229 230 EXPECT_EQ(T.countNodes(), 1u);231}232 233TYPED_TEST(RadixTreeTypeTest, InsertEmptyTwice) {234 using TreeType = RadixTree<TypeParam, int>;235 TreeType T;236 T.emplace(this->make1(0), 5);237 auto [It, IsNew] = T.emplace(this->make1(0), 6);238 EXPECT_TRUE(!T.empty());239 EXPECT_EQ(T.size(), 1u);240 EXPECT_TRUE(!IsNew);241 const auto &[K, V] = *It;242 EXPECT_TRUE(K.empty());243 EXPECT_EQ(5, V);244 245 EXPECT_THAT(T.find_prefixes(this->make1(0)),246 ElementsAre(Pair(ElementsAre(), 5)));247 248 EXPECT_THAT(T.find_prefixes(this->make2(1)),249 ElementsAre(Pair(ElementsAre(), 5)));250 251 EXPECT_THAT(T, ElementsAre(Pair(ElementsAre(), 5)));252 253 EXPECT_EQ(T.countNodes(), 1u);254}255 256TYPED_TEST(RadixTreeTypeTest, InsertOne) {257 using TreeType = RadixTree<TypeParam, int>;258 TreeType T;259 auto [It, IsNew] = T.emplace(this->make1(1), 4);260 EXPECT_TRUE(!T.empty());261 EXPECT_EQ(T.size(), 1u);262 EXPECT_TRUE(IsNew);263 const auto &[K, V] = *It;264 EXPECT_THAT(K, ElementsAreArray(this->make1(1)));265 EXPECT_EQ(4, V);266 267 EXPECT_THAT(T, ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));268 269 EXPECT_THAT(T.find_prefixes(this->make1(1)),270 ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));271 272 EXPECT_THAT(T.find_prefixes(this->make1(2)),273 ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));274 275 EXPECT_EQ(T.countNodes(), 2u);276}277 278TYPED_TEST(RadixTreeTypeTest, InsertOneTwice) {279 using TreeType = RadixTree<TypeParam, int>;280 TreeType T;281 T.emplace(this->make1(1), 4);282 auto [It, IsNew] = T.emplace(this->make1(1), 4);283 EXPECT_TRUE(!T.empty());284 EXPECT_EQ(T.size(), 1u);285 EXPECT_TRUE(!IsNew);286 287 EXPECT_THAT(T, ElementsAre(Pair(ElementsAreArray(this->make1(1)), 4)));288 EXPECT_EQ(T.countNodes(), 2u);289}290 291TYPED_TEST(RadixTreeTypeTest, InsertSuperStrings) {292 using TreeType = RadixTree<TypeParam, int>;293 TreeType T;294 295 for (size_t Len = 0; Len < 7; Len += 2) {296 auto [It, IsNew] = T.emplace(this->make1(Len), Len);297 EXPECT_TRUE(IsNew);298 }299 300 EXPECT_THAT(T,301 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0),302 Pair(ElementsAreArray(this->make1(2)), 2),303 Pair(ElementsAreArray(this->make1(4)), 4),304 Pair(ElementsAreArray(this->make1(6)), 6)));305 306 EXPECT_THAT(T.find_prefixes(this->make1(0)),307 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0)));308 309 EXPECT_THAT(T.find_prefixes(this->make1(3)),310 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0),311 Pair(ElementsAreArray(this->make1(2)), 2)));312 313 EXPECT_THAT(T.find_prefixes(this->make1(7)),314 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(0)), 0),315 Pair(ElementsAreArray(this->make1(2)), 2),316 Pair(ElementsAreArray(this->make1(4)), 4),317 Pair(ElementsAreArray(this->make1(6)), 6)));318 319 EXPECT_EQ(T.countNodes(), 4u);320}321 322TYPED_TEST(RadixTreeTypeTest, InsertSubStrings) {323 using TreeType = RadixTree<TypeParam, int>;324 TreeType T;325 326 for (size_t Len = 0; Len < 7; Len += 2) {327 auto [It, IsNew] = T.emplace(this->make1(7 - Len), 7 - Len);328 EXPECT_TRUE(IsNew);329 }330 331 EXPECT_THAT(T,332 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1),333 Pair(ElementsAreArray(this->make1(3)), 3),334 Pair(ElementsAreArray(this->make1(5)), 5),335 Pair(ElementsAreArray(this->make1(7)), 7)));336 337 EXPECT_THAT(T.find_prefixes(this->make1(0)), UnorderedElementsAre());338 339 EXPECT_THAT(T.find_prefixes(this->make1(3)),340 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1),341 Pair(ElementsAreArray(this->make1(3)), 3)));342 343 EXPECT_THAT(T.find_prefixes(this->make1(6)),344 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(1)), 1),345 Pair(ElementsAreArray(this->make1(3)), 3),346 Pair(ElementsAreArray(this->make1(5)), 5)));347 348 EXPECT_EQ(T.countNodes(), 5u);349}350 351TYPED_TEST(RadixTreeTypeTest, InsertVShape) {352 using TreeType = RadixTree<TypeParam, int>;353 TreeType T;354 355 EXPECT_EQ(T.countNodes(), 1u);356 T.emplace(this->make1(5), 15);357 EXPECT_EQ(T.countNodes(), 2u);358 T.emplace(this->make2(6), 26);359 EXPECT_EQ(T.countNodes(), 4u);360 T.emplace(this->make2(1), 21);361 EXPECT_EQ(T.countNodes(), 5u);362 363 EXPECT_THAT(T,364 UnorderedElementsAre(Pair(ElementsAreArray(this->make1(5)), 15),365 Pair(ElementsAreArray(this->make2(6)), 26),366 Pair(ElementsAreArray(this->make2(1)), 21)));367 368 EXPECT_THAT(T.find_prefixes(this->make1(7)),369 UnorderedElementsAre(Pair(ElementsAreArray(this->make2(1)), 21),370 Pair(ElementsAreArray(this->make1(5)), 15)));371 372 EXPECT_THAT(T.find_prefixes(this->make2(7)),373 UnorderedElementsAre(Pair(ElementsAreArray(this->make2(1)), 21),374 Pair(ElementsAreArray(this->make2(6)), 26)));375 376 EXPECT_EQ(T.countNodes(), 5u);377}378 379} // namespace380