83 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/CGData/OutlinedHashTree.h"10#include "gmock/gmock.h"11#include "gtest/gtest.h"12 13using namespace llvm;14 15namespace {16 17TEST(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 25TEST(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 45TEST(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 58TEST(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 each66 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 namespace83