1 //===---- ADT/IntEqClassesTest.cpp - IntEqClasses unit tests ----*- C++ -*-===//
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/ADT/IntEqClasses.h"
10 #include "gtest/gtest.h"
11
12 using namespace llvm;
13
14 namespace {
15
TEST(IntEqClasses,Simple)16 TEST(IntEqClasses, Simple) {
17 IntEqClasses ec(10);
18
19 ec.join(0, 1);
20 ec.join(3, 2);
21 ec.join(4, 5);
22 ec.join(7, 6);
23
24 EXPECT_EQ(0u, ec.findLeader(0));
25 EXPECT_EQ(0u, ec.findLeader(1));
26 EXPECT_EQ(2u, ec.findLeader(2));
27 EXPECT_EQ(2u, ec.findLeader(3));
28 EXPECT_EQ(4u, ec.findLeader(4));
29 EXPECT_EQ(4u, ec.findLeader(5));
30 EXPECT_EQ(6u, ec.findLeader(6));
31 EXPECT_EQ(6u, ec.findLeader(7));
32 EXPECT_EQ(8u, ec.findLeader(8));
33 EXPECT_EQ(9u, ec.findLeader(9));
34
35 // join two non-leaders.
36 ec.join(1, 3);
37
38 EXPECT_EQ(0u, ec.findLeader(0));
39 EXPECT_EQ(0u, ec.findLeader(1));
40 EXPECT_EQ(0u, ec.findLeader(2));
41 EXPECT_EQ(0u, ec.findLeader(3));
42 EXPECT_EQ(4u, ec.findLeader(4));
43 EXPECT_EQ(4u, ec.findLeader(5));
44 EXPECT_EQ(6u, ec.findLeader(6));
45 EXPECT_EQ(6u, ec.findLeader(7));
46 EXPECT_EQ(8u, ec.findLeader(8));
47 EXPECT_EQ(9u, ec.findLeader(9));
48
49 // join two leaders.
50 ec.join(4, 8);
51
52 EXPECT_EQ(0u, ec.findLeader(0));
53 EXPECT_EQ(0u, ec.findLeader(1));
54 EXPECT_EQ(0u, ec.findLeader(2));
55 EXPECT_EQ(0u, ec.findLeader(3));
56 EXPECT_EQ(4u, ec.findLeader(4));
57 EXPECT_EQ(4u, ec.findLeader(5));
58 EXPECT_EQ(6u, ec.findLeader(6));
59 EXPECT_EQ(6u, ec.findLeader(7));
60 EXPECT_EQ(4u, ec.findLeader(8));
61 EXPECT_EQ(9u, ec.findLeader(9));
62
63 // join mixed.
64 ec.join(9, 1);
65
66 EXPECT_EQ(0u, ec.findLeader(0));
67 EXPECT_EQ(0u, ec.findLeader(1));
68 EXPECT_EQ(0u, ec.findLeader(2));
69 EXPECT_EQ(0u, ec.findLeader(3));
70 EXPECT_EQ(4u, ec.findLeader(4));
71 EXPECT_EQ(4u, ec.findLeader(5));
72 EXPECT_EQ(6u, ec.findLeader(6));
73 EXPECT_EQ(6u, ec.findLeader(7));
74 EXPECT_EQ(4u, ec.findLeader(8));
75 EXPECT_EQ(0u, ec.findLeader(9));
76
77 // compressed map.
78 ec.compress();
79 EXPECT_EQ(3u, ec.getNumClasses());
80
81 EXPECT_EQ(0u, ec[0]);
82 EXPECT_EQ(0u, ec[1]);
83 EXPECT_EQ(0u, ec[2]);
84 EXPECT_EQ(0u, ec[3]);
85 EXPECT_EQ(1u, ec[4]);
86 EXPECT_EQ(1u, ec[5]);
87 EXPECT_EQ(2u, ec[6]);
88 EXPECT_EQ(2u, ec[7]);
89 EXPECT_EQ(1u, ec[8]);
90 EXPECT_EQ(0u, ec[9]);
91
92 // uncompressed map.
93 ec.uncompress();
94 EXPECT_EQ(0u, ec.findLeader(0));
95 EXPECT_EQ(0u, ec.findLeader(1));
96 EXPECT_EQ(0u, ec.findLeader(2));
97 EXPECT_EQ(0u, ec.findLeader(3));
98 EXPECT_EQ(4u, ec.findLeader(4));
99 EXPECT_EQ(4u, ec.findLeader(5));
100 EXPECT_EQ(6u, ec.findLeader(6));
101 EXPECT_EQ(6u, ec.findLeader(7));
102 EXPECT_EQ(4u, ec.findLeader(8));
103 EXPECT_EQ(0u, ec.findLeader(9));
104 }
105
106 } // end anonymous namespace
107