1 //===- OutlinedHashTreeTest.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-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "llvm/CGData/OutlinedHashTree.h" 10 #include "gmock/gmock.h" 11 #include "gtest/gtest.h" 12 13 using namespace llvm; 14 15 namespace { 16 17 TEST(OutlinedHashTreeTest, Empty) { 18 OutlinedHashTree HashTree; 19 EXPECT_TRUE(HashTree.empty()); 20 // The header node is always present. 21 EXPECT_EQ(HashTree.size(), 1u); 22 EXPECT_EQ(HashTree.depth(), 0u); 23 } 24 25 TEST(OutlinedHashTreeTest, Insert) { 26 OutlinedHashTree HashTree; 27 HashTree.insert({{1, 2, 3}, 1}); 28 // The node count is 4 (including the root node). 29 EXPECT_EQ(HashTree.size(), 4u); 30 // The terminal count is 1. 31 EXPECT_EQ(HashTree.size(/*GetTerminalCountOnly=*/true), 1u); 32 // The depth is 3. 33 EXPECT_EQ(HashTree.depth(), 3u); 34 35 HashTree.clear(); 36 EXPECT_TRUE(HashTree.empty()); 37 38 HashTree.insert({{1, 2, 3}, 1}); 39 HashTree.insert({{1, 2, 4}, 2}); 40 // The nodes of 1 and 2 are shared with the same prefix. 41 // The nodes are root, 1, 2, 3 and 4, whose counts are 5. 42 EXPECT_EQ(HashTree.size(), 5u); 43 } 44 45 TEST(OutlinedHashTreeTest, Find) { 46 OutlinedHashTree HashTree; 47 HashTree.insert({{1, 2, 3}, 1}); 48 HashTree.insert({{1, 2, 3}, 2}); 49 50 // The node count does not change as the same sequences are added. 51 EXPECT_EQ(HashTree.size(), 4u); 52 // The terminal counts are accumulated from two same sequences. 53 EXPECT_TRUE(HashTree.find({1, 2, 3})); 54 EXPECT_EQ(HashTree.find({1, 2, 3}).value(), 3u); 55 EXPECT_FALSE(HashTree.find({1, 2})); 56 } 57 58 TEST(OutlinedHashTreeTest, Merge) { 59 // Build HashTree1 inserting 2 sequences. 60 OutlinedHashTree HashTree1; 61 62 HashTree1.insert({{1, 2}, 20}); 63 HashTree1.insert({{1, 4}, 30}); 64 65 // Build HashTree2 and HashTree3 for each 66 OutlinedHashTree HashTree2; 67 HashTree2.insert({{1, 2}, 20}); 68 OutlinedHashTree HashTree3; 69 HashTree3.insert({{1, 4}, 30}); 70 71 // Merge HashTree3 into HashTree2. 72 HashTree2.merge(&HashTree3); 73 74 // Compare HashTree1 and HashTree2. 75 EXPECT_EQ(HashTree1.size(), HashTree2.size()); 76 EXPECT_EQ(HashTree1.depth(), HashTree2.depth()); 77 EXPECT_EQ(HashTree1.find({1, 2}), HashTree2.find({1, 2})); 78 EXPECT_EQ(HashTree1.find({1, 4}), HashTree2.find({1, 4})); 79 EXPECT_EQ(HashTree1.find({1, 3}), HashTree2.find({1, 3})); 80 } 81 82 } // end namespace 83